Source-linked AI summary
Simple random search provides a competitive approach to reinforcement learning
Horia Mania, Aurelia Guy, Benjamin Recht
TL;DR
Model-free RL lacks simple, data-efficient, reproducible methods for physical control, and parameter-space random search is widely viewed as sample-inefficient. The paper introduces ARS, a random-search method for static linear policies, and finds state-of-the-art MuJoCo sample efficiency, near-optimal unknown-dynamics LQR control, and at least 15× greater computational efficiency than the fastest competing model-free method. Extensive evaluations also reveal substantial variability across random seeds and hyperparameters.
Problem
Model-free RL methods face data, complexity, and reproducibility barriers, while parameter-space random search is commonly believed to have poor sample complexity.
Method
The paper augments basic derivative-free random search with reward scaling, online state normalization, and top-direction selection to train static linear policies.
Results
ARS matches or exceeds state-of-the-art sample efficiency on MuJoCo locomotion tasks, achieves over 11500 average reward on Humanoid-v1, and is at least 15 times more computationally efficient than ES.
Takeaways & Limitations
Simple random search and linear policies can achieve competitive continuous-control performance while enabling extensive sensitivity studies over seeds and hyperparameters.
Takeaways & Limitations
MuJoCo benchmarks have unknown maximal rewards and optimal policies, high variance, and a risk that the community is overfitting to a small test suite.
Abstract
from arXiv · showhide
A common belief in model-free reinforcement learning is that methods based on random search in the parameter space of policies exhibit significantly worse sample complexity than those that explore the space of actions. We dispel such beliefs by introducing a random search method for training static, linear policies for continuous control problems, matching state-of-the-art sample efficiency on the benchmark MuJoCo locomotion tasks. Our method also finds a nearly optimal controller for a challenging instance of the Linear Quadratic Regulator, a classical problem in control theory, when the dynamics are not known. Computationally, our random search algorithm is at least 15 times more efficient than the fastest competing model-free methods on these benchmarks. We take advantage of this computational efficiency to evaluate the performance of our method over hundreds of random seeds and many different hyperparameter configurations for each benchmark task. Our simulations highlight a high variability in performance in these benchmark tasks, suggesting that commonly used estimations of sample efficiency do not adequately evaluate the performance of RL algorithms.
1 Introduction
The paper seeks a simple, reproducible model-free RL method for continuous control, challenging the perceived inefficiency of parameter-space random search. ARS uses derivative-free optimization of linear policies and matches state-of-the-art benchmark performance while enabling broader evaluation.
- Motivation: Model-free RL aims to control dynamical systems without requiring models, but physical deployment is limited by data demands, methodological complexity, and implementation difficulty.
- Contribution: The paper combines derivative-free optimization with linear policies to obtain a simple random-search method for continuous control.
- Results: ARS trains static linear policies without neural networks and achieves average rewards over 11500 on Humanoid-v1, the highest reward reported in the literature.
- Results: ARS matches or exceeds state-of-the-art sample efficiency on the MuJoCo locomotion tasks when evaluated over three random seeds.
- Efficiency: ARS is at least 15 times more computationally efficient than Evolution Strategies, the fastest competing method.
- Evaluation: The method’s efficiency supports evaluation over many random seeds, addressing documented sensitivity of RL results to seeds and hyperparameters.
2 Problem setup
The paper formulates model-free RL as noisy derivative-free optimization over policy parameters and studies random search as a parameter-space alternative to action-space exploration. Basic random search estimates improvement from paired perturbed-policy rollouts and updates the policy parameters accordingly.
- Problem formulation: RL seeks policy parameters that maximize average reward for controlling dynamical systems.
- Problem formulation: The policy is parameterized by θ, while environment randomness affects trajectory rewards; the proposed method uses deterministic policies.
- Problem formulation: Exploring policy-parameter space makes RL equivalent to derivative-free optimization with noisy function evaluations.
- Basic random search: Random search samples a direction and estimates improvement using finite differences from positively and negatively perturbed policies.
- Oracle model: Each rollout is an oracle query returning a trajectory of states, actions, and rewards, and sample complexity counts the queries needed to approximately solve the problem.
3 Our proposed algorithm
ARS augments basic random search with reward-scale normalization, online state normalization, and optional selection of top-performing perturbation directions. These simple features support strong linear-policy performance, while their benefits and boundaries vary across tasks.
- 3 Our proposed algorithm: ARS V1 scales update steps by reward standard deviation, while ARS V2 additionally uses states normalized by online mean and standard deviation estimates.
- 3.2 Normalization of the states: State normalization acts like whitening and can be viewed for linear policies as non-isotropic parameter-space exploration.
- 3.2 Normalization of the states: Without state normalization, the authors could not train a linear Humanoid-v1 policy; ARS V2 also improves measured sample complexity on other MuJoCo tasks.
- 3. Our proposed algorithm: ARS V2 matches or exceeds state-of-the-art performance on Swimmer-v1, Hopper-v1, HalfCheetah-v1, and Humanoid-v1, but needs two to three times more rollouts on Walker2d-v1 and Ant-v1.
- 3 Our proposed algorithm: ARS V1-t and V2-t sort perturbation directions by the better paired reward and update using only the top b directions.
- 3. Our proposed algorithm: ARS surpasses ES without action-space binning and achieves state-of-the-art performance with linear rather than neural-network policies.
4 Experimental results
ARS achieves strong MuJoCo control performance with simple linear policies, while broad evaluations reveal substantial variability across random seeds and hyperparameters. Its computational efficiency enables extensive testing, but benchmark limitations and LQR comparisons mark important boundaries.
- Method: ARS uses parallelized random search with linear policies and lightweight state, reward, and direction-selection modifications.The implementation uses shared noise tables to reduce communication of perturbations.
- MuJoCo performance: ARS matches or exceeds state-of-the-art sample efficiency across the MuJoCo locomotion tasks, although task-level comparisons vary by baseline and environment.It surpasses several methods on selected tasks while being outperformed on others, including Walker2d-v1 by PPO and HalfCheetah-v1 by SAC, DDPG, and SQL.
- Robustness: 70%: ARS trains successful policies on all MuJoCo tasks except Walker2d-v1 in 70% of runs, while Walker2d-v1 succeeds in only 20%.The 100-seed evaluation also identifies both delayed discovery of high-reward policies and locally optimal behaviors.
- Robustness: ARS is least sensitive to random seeds on HalfCheetah-v1, while hyperparameter variation produces success rates similar to independent trials with good fixed settings.Median performance decreases with hyperparameter variation only for Ant-v1 and Humanoid-v1.
- Limitations: MuJoCo benchmarks have unknown maximal rewards and optimal policies, high variance, and few new instances, so benchmark results may not distinguish quality reliably.These properties create a risk that the field overfits to a small test suite.
- LQR comparison: ARS requires no special initialization, unlike LSPI, but the nominal control method is orders of magnitude more sample efficient than both LSPI and ARS on the evaluated LQR instance.The result leaves substantial room for improvement for pure model-free approaches.
5 Conclusion
The paper argues that simple, carefully evaluated model-free RL baselines can perform strongly, while common evaluation practices can misrepresent sample efficiency. It recommends broader, problem-specific evaluation and greater attention to model-based methods.
- Basic random search with a few augmentations trains linear policies achieving state-of-the-art sample efficiency on MuJoCo locomotion tasks.The authors report that linear policies can match complex neural-network policies on these benchmarks.
- Small numbers of random seeds do not adequately capture RL performance because training variance is high.The paper connects this variance to concerns about the reliability of commonly reported learning curves and sample-complexity estimates.
- Reported sample complexity can be artificially improved by tuning hyperparameters and testing algorithmic enhancements without counting those additional rollouts.The paper argues that meaningful sample complexity should reflect the samples needed to solve a new, previously unseen task.
- Simple baselines should precede more complex benchmarks and methods, with LQR proposed because it is well understood, tunable in difficulty, and easy to replicate.The authors specifically recommend LQR with unknown dynamics as an extensible and reproducible benchmark.
- Simulation-only comparisons are limited because simulator-specific regularities may let one algorithm exploit particularities that do not generalize to intended problem distributions.The paper recommends separate instances for tuning and evaluation, while acknowledging that simulation remains an imperfect proxy.
- The paper suggests focusing on targeted solutions for specific problems and increasing emphasis on model-based methods, which often require fewer samples.It also notes that model-based approaches introduce computational challenges of their own.
A.1 Maximum reward achieved after a prescribed number of timesteps
The appendix defines a three-seed procedure for estimating ARS’s maximum reward under a timestep budget. The resulting estimate is conservative because the budget must be respected across seeds.
- ARS training curves are averaged across three random seeds before estimating maximum reward under a prescribed timestep budget.The appendix defines per-seed rewards and cumulative sampled timesteps before averaging the curves.
- The resulting maximum-reward estimate is conservative because it uses the slowest seed to determine the usable iteration range.The appendix explicitly identifies the minimum over seeds as the source of conservatism.
A.2 Hyperparameters
The appendix lists the hyperparameter grids used for tuning and the configurations used to produce the reported ARS V2 and V2-t results.
- Table 8 contains the hyperparameter grids used during hyperparameter tuning.
- Table 9 contains the ARS V2 and V2-t hyperparameters used for the results shown in Figure 2.