Gradient-Free Reinforcement Learning: CMA-ES, Evolution Strategies, and Augmented Random Search

TL;DR

Every method covered elsewhere on this site — Q-learning, actor-critic, policy gradients — computes an explicit gradient via backpropagation through the policy network. Gradient-free methods skip this entirely: they perturb a policy’s parameters directly, evaluate the perturbed versions by just running them in the environment, and update based purely on which perturbations did better, with no backward pass at all. CMA-ES adapts a full covariance matrix to shape its search distribution intelligently; OpenAI’s Evolution Strategies (ES) shows this scales embarrassingly well across thousands of parallel machines with minimal communication; Augmented Random Search (ARS) strips the idea down to something almost trivially simple and still matches deep RL benchmarks; and NEAT evolves network topology itself, not just weights. Used for hyperparameter-sensitive or non-differentiable objectives, in robotics research, and anywhere massive parallelism is cheaper to access than gradient computation.

The Gradient-Free Search Loop

graph LR
    A[Current Parameters] --> B[Sample Perturbed Population]
    B --> C[Evaluate Each in the Environment]
    C --> D[Update Toward Better Performers]
    D -->|repeat| A

    style D fill:#6366f1,color:#fff

Problem Statement

Backpropagation requires a differentiable objective — but plenty of real objectives aren’t differentiable, or the policy itself has discrete or hard-to-differentiate structure. Separately, gradient-based RL methods (especially policy gradients) can be plagued by high variance and sensitive hyperparameters. Gradient-free, population-based search sidesteps both problems: since it never needs a gradient, it works on non-differentiable objectives, and because it evaluates whole parameter perturbations directly against real return, it can be strikingly robust and simple to implement.

CMA-ES: Adapting the Search Distribution Itself

CMA-ES (Covariance Matrix Adaptation Evolution Strategy) maintains a multivariate Gaussian distribution over policy parameters, samples a population of candidate parameter vectors from it, evaluates each by running it in the environment, and then updates both the mean (toward better-performing samples) and the full covariance matrix (to reshape the search distribution toward directions that have historically found improvement).

def cma_es_step(mean, covariance, fitness_fn, population_size=50):
    population = np.random.multivariate_normal(mean, covariance, size=population_size)
    fitness = np.array([fitness_fn(individual) for individual in population])

    ranked = population[np.argsort(-fitness)]
    top_k = ranked[:population_size // 4]

    new_mean = top_k.mean(axis=0)
    deviations = top_k - new_mean
    new_covariance = (deviations.T @ deviations) / len(top_k)   # adapt search shape to recent success

    return new_mean, new_covariance

Adapting the covariance matrix means CMA-ES automatically learns which parameter directions matter most for improvement and concentrates its search there — a form of automatic step-size and search-shape tuning that plain random search doesn’t get.

OpenAI’s Evolution Strategies: Scaling With Almost No Communication

OpenAI-ES (Salimans et al., 2017) demonstrated that a much simpler evolution strategy — perturb the current parameters with random Gaussian noise, evaluate each perturbation’s return, and take a weighted average step in the direction of the better-performing perturbations — scales remarkably well across thousands of parallel workers, because each worker only needs to communicate a single scalar (its perturbation’s fitness score) back to a central coordinator, not full gradients or parameters.

def openai_es_step(params, fitness_fn, population_size=100, sigma=0.1, lr=0.01):
    noise = np.random.randn(population_size, len(params))
    fitness = np.array([fitness_fn(params + sigma * noise[i]) for i in range(population_size)])

    normalized_fitness = (fitness - fitness.mean()) / (fitness.std() + 1e-8)
    gradient_estimate = (noise.T @ normalized_fitness) / (population_size * sigma)

    return params + lr * gradient_estimate

Because every worker can independently regenerate the same random noise from a shared seed, workers only ever need to exchange a single fitness number per worker per iteration — an extremely communication-efficient scheme that let OpenAI train competitive MuJoCo locomotion policies using over a thousand parallel workers with near-linear speedup.

Augmented Random Search: Radically Simple, Surprisingly Strong

ARS (Mania et al., 2018) strips the idea down even further: sample random directions, evaluate the return for a positive and negative perturbation along each direction, and take a step weighted by the difference between the two — no covariance adaptation, no neural-network-specific machinery, often applied directly to a linear policy.

def ars_step(params, fitness_fn, n_directions=16, sigma=0.03, lr=0.02):
    directions = np.random.randn(n_directions, len(params))
    rewards_plus = np.array([fitness_fn(params + sigma * d) for d in directions])
    rewards_minus = np.array([fitness_fn(params - sigma * d) for d in directions])

    step = sum((rewards_plus[i] - rewards_minus[i]) * directions[i] for i in range(n_directions))
    return params + (lr / (n_directions * (rewards_plus.tolist() + rewards_minus.tolist()).__len__() ** 0.5)) * step

That ARS, using nothing more than paired finite-difference-style perturbations on a linear policy, matched deep RL benchmark performance on standard MuJoCo continuous-control tasks was a notable result — a reminder that some of what looks like it requires deep networks and gradients may really be a property of the task, not a requirement of the solution.

NEAT: Evolving Network Topology, Not Just Weights

NEAT (NeuroEvolution of Augmenting Topologies, Stanley & Miikkulainen, 2002) evolves both the weights and the structure of a neural network simultaneously — starting from minimal networks and incrementally adding nodes and connections via mutation, while using a “speciation” mechanism that protects structurally novel mutations from being outcompeted before they’ve had a chance to have their weights optimized.

def neat_mutate(genome, add_node_prob=0.03, add_connection_prob=0.05):
    if random.random() < add_node_prob:
        genome.split_random_connection_with_new_node()
    if random.random() < add_connection_prob:
        genome.add_random_connection()
    genome.mutate_weights(perturbation_std=0.1)
    return genome

Because NEAT searches over architecture as well as weights, it can discover network structures suited to a problem without a human specifying layer sizes or connectivity ahead of time — at the cost of being far less scalable to the very large networks used in modern deep RL.

Comparison Table

Applications

• Hyperparameter-sensitive or non-differentiable objectives — anywhere the reward signal itself isn’t differentiable or the policy has non-differentiable components.
• Massively parallel compute settings — OpenAI-ES’s communication efficiency makes it attractive specifically when you have access to many machines but want to minimize network overhead between them.
• Robotics locomotion research — ARS’s strong results on MuJoCo locomotion tasks made it a standard baseline comparison for new continuous-control methods.
• Automated architecture search — NEAT-style topology evolution has influenced neural architecture search research beyond RL specifically.

Key Learnings

1. Gradient-free doesn’t mean worse — it means a different bias-variance and scalability trade-off. ARS matching deep RL performance with a linear policy is a genuine result, not a fluke, and it’s a useful sanity check against assuming a problem needs a deep network and gradients by default.
2. Communication cost is a first-class design constraint at scale, and OpenAI-ES’s shared-seed trick (recomputing noise locally instead of transmitting it) is a clever systems-level solution as much as an algorithmic one.
3. Evolutionary methods and gradient-based RL are not mutually exclusive. In practice, evolutionary search is often used for outer-loop concerns (hyperparameters, architecture, or as an alternative optimizer when gradients are unavailable or unreliable) alongside, not instead of, the gradient-based methods covered elsewhere on this site.

References

• Hansen, N. (2006). The CMA Evolution Strategy: A Comparing Review. In Towards a New Evolutionary Computation.
• Salimans, T. et al. (2017). Evolution Strategies as a Scalable Alternative to Reinforcement Learning.
• Mania, H., Guy, A., Recht, B. (2018). Simple Random Search Provides a Competitive Approach to Reinforcement Learning.
• Stanley, K., Miikkulainen, R. (2002). Evolving Neural Networks through Augmenting Topologies. Evolutionary Computation, 10(2).