Simple random search provides a competitive approach to reinforcement learning

By Horia Mania, Aurelia Guy, B. Recht. 2018

338 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research, Reinforcement Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

Learning data augmentation policies using augmented random search (2018, methodology): “Recently, an Augmented Random Search method (ARS) [5] has shown its immense potential in dealing with continuous control problems.”
Deep Reinforcement Learning for Autonomous Driving: A Survey (2020, background): “A recent study in [97] demonstrates that random search over the parameters for a policy network can perform as well as LQR.”
Same State, Different Task: Continual Reinforcement Learning without Interference (2021, background): “The MAB approach can also behave similarly to a random policy head selection can perform well [11, 42].”
Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, background): “We did not have the chance to implement the competitive random search algorithms in (Mania et al., 2018) yet, although our test performance with 500 episode length is higher than theirs with 1000 episode on Half Cheetach (3950 by ours vs 2345 by theirs) and Walker (3650 by ours vs 894 by theirs).”
Dual Policy Iteration (2018, methodology): “Sample inefficiency due to random exploration can cause even sophisticated RL methods to perform worse than simple black-box optimization with random search in parameter space [14].”
Randomized Prior Functions for Deep Reinforcement Learning (2018, background): “However, if our goal is artificial general intelligence, then it is disconcerting that our best agents can perform very poorly even in simple problems [33, 39].”
Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective (2019, methodology): “The hyperpa-rameters used are shown in Table 2 and we closely follow the algorithm outlined in (Mania et al., 2018).”
Are We Learning Yet? A Meta Review of Evaluation Failures Across Machine Learning (2021, background): “One particularly prominent case is in deep RL, where simple random search, combined with a handful of minor modiﬁcations, outperforms many deep RL algorithms on a variety of MuJoCo continuous control tasks [90].”
Observational Overfitting in Reinforcement Learning (2019, background): “While there have been numerous works which avoid overparametrization on simplifying policies (Rajeswaran et al., 2017; Mania et al., 2018) or compactifying networks (Choromanski et al.”
Effective Diversity in Population-Based Reinforcement Learning (2020, methodology): “The Humanoid-v2 task requires a significant degree of exploration, as there is a well-known local optimum at 5000, since the agent is provided with a survival bonus of 5 per timestep (Mania et al., 2018).”
A Closer Look at Deep Policy Gradients (2018, background): “(Rajeswaran et al., 2017) and (Mania et al., 2018) demonstrate that on many benchmark tasks, state-of-the-art performance can be attained by augmented randomized search approaches.”
How to pick the domain randomization parameters for sim-to-real transfer of reinforcement learning policies? (2019, background): “| s ) over the action space A . θ represents the parameters of the policy, which can be linear operators ([17], [18]) or the weights and biases of a deep neural network.”
Constrained Reinforcement Learning Has Zero Duality Gap (2019, methodology): “In practice, the exact coefﬁcient is selected through a time consuming and a computationally intensive process of hyper-parameter tuning that often times are domain dependent, as showed in [7–9].”
Implementation Matters in Deep RL: A Case Study on PPO and TRPO (2020, background): “, 2017; 2018), and sometimes outperformed by simple baselines (Mania et al., 2018).”
S-RL Toolbox: Environments, Datasets and Evaluation Metrics for State Representation Learning (2018, background): “, 2017)), Augmented Random Search (ARS) (Mania et al., 2018), Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES) (Hansen et al.”