Simple random search of static linear policies is competitive for reinforcement learning
Model-free reinforcement learning aims to offer off-the-shelf solutions for controlling dynamical systems without requiring models of the system dynamics. We introduce a model-free random search algorithm for training static, linear policies for continuous control problems. Common evaluation methodology shows that our method matches state-of-the-art sample efficiency on the benchmark MuJoCo locomotion tasks. Nonetheless, more rigorous evaluation reveals that the assessment of performance on these benchmarks is optimistic. We evaluate the performance of our method over hundreds of random seeds and many different hyperparameter configurations for each benchmark task. This extensive evaluation is possible because of the small computational footprint of our method. Our simulations highlight a high variability in performance in these benchmark tasks, indicating that commonly used estimations of sample efficiency do not adequately evaluate the performance of RL algorithms. Our results stress the need for new baselines, benchmarks and evaluation methodology for RL algorithms.
Post rebuttal:  I agree with the concerns raised about MujoCo environment used for benchmarking RL algorithms. After reading the other reviews and authors' response I remain unconvinced that they make a good case. My concern is with the methodology of the approach, and I cannot see how it can be addressed in the final version.   In the rebuttal, lines 8-12, the authors state: "We offer evidence for the need of new baselines, benchmarks and evaluation methodology for RL algorithms. We show that under current evaluation standards a simple method with linear policies can match or outperform the performance of more complicated methods on current, standard benchmark tasks. Nonetheless, more rigorous evaluation reveals that the assessment of performance on these benchmarks remains overly optimistic because it restricts its attention to too few random seeds."  This argument would hold if the paper showed that vanilla random policies reach near RL performance. Instead, the authors tweak and customize algorithms to specific problems. It is the modification of the algorithms that take away from the argument. Hand-coded and highly-custom algorithms generally perform well for specific problems, and the power of more complex learning methods lies in their generality.   The authors did not address in rebuttal the differences to Choromanski et al., “Structured Evolution with Compact Architectures for Scalable Policy Optimization,” ICML 2018. This paper uses a more generic and simple algorithm on MojoCo tasks. Methods such in Choromanski et al. can be used to make a better case about the complexity of MujoCo. ------------------  This paper argues for simple baselines on reinforcement learning tasks, and proposes a new such baseline. ARS (Augmented Random Search) is a simple, gradient-free algorithm for training linear policies. The authors compare ARS to a number of RL algorithms, presenting results on sample efficiency, sensitivity, and rewards achieved on MuJoCo locomotion tasks. They redefine “sample efficiency” to include hyperparameter search and argue for more sensitivity analysis in the literature.  The paper comes at a good time, with the recent reproducibility issues in RL. The paper’s arguments on sample efficiency and transparency are compelling. The analysis of hyperparameter search and random seed sensitivity sets a good example for the field. The intuition behind the algorithm augmentations is clear. The algorithm, being random search over linear policies, is quite simple and makes me reconsider the need for complex algorithms on these tasks.  It is unclear what the main contribution of the paper is: to show that MuJoCo is too simple, to show how RL algorithms should be evaluated, or to introduce a good baseline algorithm? The paper tries to do all of these, but it would be more effective to focus on one and frame the paper around it. For example, if the goal is to introduce a simple, effective baseline, ARS V2-t should be sufficient, without discussing V1.  Specifically, in Figure 1, it’s strange to present one algorithm ARS V1 on Swimmer-v1 and use ARS V2 and V2-t on other tasks. It’s somewhat acceptable to use both V2 and V2-t, since as mentioned the difference is just tuning hyperparameter b. In a paper contributing a simple, robust baseline to the field, a single algorithm should work on all tasks? A similar argument could be made against choosing the hyperparameters differently for the sample efficiency and maximum rewards results.  In the discussion section, it is argued that “a meaningful sample complexity of an algorithm should inform us on the number of samples required to solve a new, previously unseen task.” Under this definition, it would be nice to see a comparison to metalearning algorithms.  Other smaller comments: It would be great if the sensitivity analysis were presented for other algorithms as well, especially on HalfCheetah-v1, as you say this is often used for evaluation of sensitivity. Table 1: bold the most sample efficient algorithm for each task? Table 1: the humanoid-v1 comparison isn’t compelling. Maybe include more results from other algorithms, or remove all discussion of humanoid-v1? In Table 2, it would be great to show the highest reward encountered in the literature for each task, some of what you have in appendix tables 4 and 5. Paper “Structured Evolution with Compact Architectures for Scalable Policy Optimization,” ICML 2018 should be cited as an evidence that more simple, evolutionary policies solve complex tasks.  Questions:  Why weights initialized to 0, not random?  Why grid of hyperparameters instead of random?