# Simple random search provides a competitive approach to reinforcement learning

arXiv: https://arxiv.org/abs/1803.07055 · HTML: https://mlsanity.com/paper/1803.07055/

## Key facts

- Cited by 75 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2018.

## Built on by (most cited first, 30 of 75)

- [Deep Reinforcement Learning at the Edge of the Statistical Precipice](https://mlsanity.com/paper/2108.13264/) (2021)
- [Multi-Game Decision Transformers](https://mlsanity.com/paper/2205.15241/) (2022)
- [For SALE: State-Action Representation Learning for Deep Reinforcement Learning](https://mlsanity.com/paper/2306.02451/) (2023)
- [Saute RL: Almost Surely Safe Reinforcement Learning Using State Augmentation](https://mlsanity.com/paper/2202.06558/) (2022)
- [DouZero: Mastering DouDizhu with Self-Play Deep Reinforcement Learning](https://mlsanity.com/paper/2106.06135/) (2021)
- [Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectification](https://mlsanity.com/paper/2111.11188/) (2021)
- [Unbiased Gradient Estimation in Unrolled Computation Graphs with Persistent Evolution Strategies](https://mlsanity.com/paper/2112.13835/) (2021)
- [Same State, Different Task: Continual Reinforcement Learning without Interference](https://mlsanity.com/paper/2106.02940/) (2021)
- [State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewards](https://mlsanity.com/paper/2102.11941/) (2021)
- [Learning Long-Term Reward Redistribution via Randomized Return Decomposition](https://mlsanity.com/paper/2111.13485/) (2021)
- [Learning Dexterous Manipulation from Exemplar Object Trajectories and Pre-Grasps](https://mlsanity.com/paper/2209.11221/) (2022)
- [Neural Thickets: Diverse Task Experts Are Dense Around Pretrained Weights](https://mlsanity.com/paper/2603.12228/) (2026)
- [Deep Inventory Management](https://mlsanity.com/paper/2210.03137/) (2022)
- [Action Noise in Off-Policy Deep Reinforcement Learning: Impact on Exploration and Performance](https://mlsanity.com/paper/2206.03787/) (2022)
- [CoMAL: Collaborative Multi-Agent Large Language Models for Mixed-Autonomy Traffic](https://mlsanity.com/paper/2410.14368/) (2024)
- [SARA-RT: Scaling up Robotics Transformers with Self-Adaptive Robust Attention](https://mlsanity.com/paper/2312.01990/) (2023)
- [Reward Reports for Reinforcement Learning](https://mlsanity.com/paper/2204.10817/) (2022)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [FZOO: Fast Zeroth-Order Optimizer for Fine-Tuning Large Language Models towards Adam-Scale Speed](https://mlsanity.com/paper/2506.09034/) (2025)
- [Robotic Table Tennis: A Case Study into a High Speed Learning System](https://mlsanity.com/paper/2309.03315/) (2023)
- [A Survey of Automated Data Augmentation Algorithms for Deep Learning-based Image Classification Tasks](https://mlsanity.com/paper/2206.06544/) (2022)
- [Reinforcement Learning for Datacenter Congestion Control](https://mlsanity.com/paper/2102.09337/) (2021)
- [Probabilistic Constraint for Safety-Critical Reinforcement Learning](https://mlsanity.com/paper/2306.17279/) (2023)
- [Monte Carlo Tree Search based Hybrid Optimization of Variational Quantum Circuits](https://mlsanity.com/paper/2203.16707/) (2022)
- [PI-ARS: Accelerating Evolution-Learned Visual-Locomotion with Predictive Information Representations](https://mlsanity.com/paper/2207.13224/) (2022)
- [Improving sample efficiency of high dimensional Bayesian optimization with MCMC](https://mlsanity.com/paper/2401.02650/) (2024)
- [LIFT: Reinforcement Learning in Computer Systems by Learning From Demonstrations](https://mlsanity.com/paper/1808.07903/) (2018)
- [Continuous Versatile Jumping Using Learned Action Residuals](https://mlsanity.com/paper/2304.08663/) (2023)
- [Acceleration for Deep Reinforcement Learning using Parallel and Distributed Computing: A Survey](https://mlsanity.com/paper/2411.05614/) (2024)

## Abstract (arXiv)

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.