Comparison of reinforcement algorithms on discrete functions: learnability, time complexity, and scaling

The authors compare the performances of a variety of algorithms in a reinforcement learning paradigm, including Ar-p, Ar-i, reinforcement-comparison (plus a new variation), and backpropagation of reinforcement gradient through a forward model. The task domain is discrete multioutput functions. Performance is measured in terms of learnability, training time, and scaling. Ar-p outperforms all others and scales well relative to supervised backpropagation. An ergodic variant of reinforcement-comparison approaches Ar-p performance. For the tasks studied, total training time (including model and controller) for the forward model algorithm is 1 to 2 orders of magnitude more costly than for Ar-p, and the controller´s success is sensitive to forward model accuracy. Distortions of the reinforcement gradient predicted by an inaccurate forward model cause the controller´s failures