Policy Search

Chapter 1: Approximate Policy Evaluation

Before we can search, we need to score. Given a candidate π_θ, we want a number: how good is it? The true expected return is

This expectation is over all rollout trajectories τ = (s₀, a₀, s₁, a₁, …) generated by running π_θ in the environment. We can't compute it exactly, but we can Monte Carlo estimate it by running m actual rollouts.

Why m rollouts and not just 1? Because the environment is stochastic. A single rollout can be an outlier. Averaging over m rollouts reduces the estimation variance. The standard error of your estimate is σ/√m, where σ is the standard deviation of a single rollout's return.

How many rollouts do you need? If returns vary wildly (chaotic environment, long horizon), you need more. Double your precision, quadruple m. This is the fundamental evaluation budget problem in policy search.

Chapter 2: Local Search

The simplest strategy: stand at your current best θ, look around in a small neighborhood, and move to wherever U is higher. This is local search — also called hill climbing in the policy optimization context.

Concretely: start with an initial θ₀. At each iteration, generate candidate perturbations by adding small random noise. Evaluate each candidate with Monte Carlo rollouts. If any candidate beats the current best, move there. Repeat.

The step size σ controls the neighborhood radius. Large σ explores widely but may jump over fine features of U. Small σ is precise but slow. A common trick: adaptive step size — shrink σ when progress stalls, expand when making consistent progress.

Local search has one Achilles heel: local optima. If U(θ) has many hills, local search climbs to the nearest peak and stops, unaware that a distant mountain is much taller. For policy spaces with many local optima (common in robotics), population-based methods handle this much better.

Chapter 3: Nelder-Mead Simplex

Imagine placing d+1 explorers on the policy landscape (for d = dim(θ)). These explorers form a simplex: in 2D a triangle, in 3D a tetrahedron. Their positions are θ⁽¹⁾, …, θ^(d+1). The game: iteratively deform the simplex so it crawls toward the optimum.

The Nelder-Mead method (1965) uses four geometric operations on the simplex at each step. It doesn't use derivatives. It uses geometry.

The reflection step in detail: the centroid of all vertices except the worst is θ_c = (1/d) ∑_i≠w θ⁽ⁱ⁾. The reflected vertex is θ_r = θ_c + (θ_c − θ_w). Evaluate U(θ_r) and compare to the current best and second-worst. The four cases (best, good, bad, terrible) determine which operation to apply.

Chapter 4: Genetic Algorithms

Nature solved optimization over billions of years: keep good solutions, randomly mutate them, and combine successful parents. Genetic algorithms (GAs) copy this strategy — maintain a population of candidate policies, evaluate each, and breed the next generation from the best survivors.

The key insight: by keeping a population rather than a single candidate, GAs naturally explore multiple basins of attraction simultaneously. This makes them far less prone to local optima than local search.

For continuous parameter vectors θ ∈ R^d, the most common operations:

Uniform crossover: Given parents θ^A and θ^B, create offspring θ^C by taking each component from A with probability 0.5, or from B otherwise: θ^C_j ~ Bernoulli(½) ? θ^A_j : θ^B_j. Works well when parameters are independent.

Mutation: Add Gaussian noise: θ^C ← θ^C + ε where ε ~ 𝒩(0, σ²I). σ is the mutation rate. Large σ = wild exploration; small σ = fine-tuning.

Chapter 5: Cross-Entropy Method

Genetic algorithms maintain a set of point candidates. The cross-entropy method (CEM) is more principled: maintain a distribution over candidates. Concretely, CEM keeps a Gaussian p(θ) = 𝒩(μ, Σ) and iteratively updates (μ, Σ) so the distribution concentrates around high-return regions.

The name comes from information theory: updating the parameters to maximize the likelihood of the elite samples is equivalent to minimizing the KL-divergence between the current distribution and an idealized distribution concentrated on the optimal θ*.

The update equations are sample statistics of the elite set Θ_elite:

These are maximum likelihood estimates of a Gaussian fitted to the elites. No optimization required — just two matrix computations. The εI term (noise injection) prevents Σ from collapsing prematurely and stops exploration too early.

python
import numpy as np

def cross_entropy_method(evaluate, d, n_iter=50, N=100, rho=0.2, noise=1e-3):
    """evaluate: theta -> scalar return. d: dimension of theta."""
    mu = np.zeros(d)
    sigma = np.eye(d)   # full covariance
    k = int(rho * N)    # number of elites to keep

    for t in range(n_iter):
        # 1. Sample candidates from current distribution
        thetas = np.random.multivariate_normal(mu, sigma, N)

        # 2. Evaluate each candidate (embarrassingly parallel)
        returns = np.array([evaluate(th) for th in thetas])

        # 3. Select top-k elites
        elite_idx = np.argsort(returns)[-k:]
        elites = thetas[elite_idx]

        # 4. Update distribution: MLE Gaussian on elites
        mu = elites.mean(axis=0)
        diff = elites - mu
        sigma = (diff.T @ diff) / k + noise * np.eye(d)

    return mu

Chapter 6: Evolution Strategies

CEM uses hard selection: keep the top ρ·N, discard the rest. Evolution strategies (ES) use soft selection: weight every sample by its return. The distribution update becomes a weighted average rather than a sample mean of elites.

ES keeps a Gaussian p(θ; μ, Σ) and performs the update:

where w_i are weights derived from the returns. The most robust choice: rank-based weights. Rank the N candidates by return. Assign w_i ∝ max(0, log(N/2 + 1) − log(rank_i)), normalized to sum to 1. This gives large weight to the best, zero to the worst half, and smooth interpolation between.

python
import numpy as np

def evolution_strategy(evaluate, d, n_iter=50, N=50, sigma=0.1, alpha=0.01):
    """Diagonal-covariance ES with rank-based weights."""
    mu = np.zeros(d)

    for t in range(n_iter):
        eps = np.random.randn(N // 2, d)
        # Mirrored sampling: evaluate +eps and -eps
        thetas = np.concatenate([mu + sigma * eps, mu - sigma * eps])
        returns = np.array([evaluate(th) for th in thetas])

        # Rank-based weights: top half gets positive weight, bottom zero
        ranks = np.argsort(np.argsort(returns))  # double-argsort = ranks
        w = np.maximum(0, np.log(N/2 + 1) - np.log(N - ranks))
        w /= w.sum()

        # Weighted mean update
        mu = (w[:, None] * thetas).sum(axis=0)

    return mu

Chapter 7: Isotropic Evolution Strategies

When the policy parameter θ has thousands or millions of dimensions (a neural network), maintaining a full d×d covariance matrix is intractable. Isotropic ES simplifies by fixing Σ = σ²I — the same noise in every direction. This reduces the search to tuning a single scalar σ.

This sounds like a drastic limitation. Surprisingly, it works even for deep networks with millions of parameters. The key insight: the update

is actually a gradient estimate of E_ε~𝒩(0,I)[U(μ + σε)] with respect to μ. Isotropic ES is secretly a smoothed gradient descent on the Gaussian-blurred objective!

python
import numpy as np

def isotropic_es(evaluate, d, n_iter=100, N=50, sigma=0.05, alpha=0.01):
    """Isotropic ES with mirrored sampling and baseline subtraction."""
    mu = np.zeros(d)

    for t in range(n_iter):
        eps = np.random.randn(N, d)   # N perturbation directions

        # Mirrored: evaluate +eps and -eps pairs
        R_pos = np.array([evaluate(mu + sigma * e) for e in eps])
        R_neg = np.array([evaluate(mu - sigma * e) for e in eps])

        # Gradient estimate with baseline subtraction
        advantages = R_pos - R_neg  # baseline cancels exactly
        grad = (advantages[:, None] * eps).sum(axis=0) / (N * sigma)
        mu += alpha * grad

    return mu

Chapter 8: Showcase — Policy Search Race

Three algorithms compete to optimize the same 2D policy landscape in real time. The landscape has a global optimum (gold star) and sometimes local traps. Watch how each method navigates.

Chapter 9: Connections & What's Next

Policy search occupies a special niche: the method of choice when you can evaluate but not differentiate the objective. The next chapters open the black box.

Related chapters:

• Ch 9: Online Planning — evaluating policies in online decision-making
• Ch 11: Policy Gradient Estimation — gradient-based policy optimization
• Ch 12: Policy Gradient Optimization — trust regions, PPO
• Ch 16: Model-Based RL — CEM as a planner in learned world models

"Evolution is smarter than you are." — Leslie Orgel, biologist. The same humility applies to policy space: when gradients fail, let the landscape speak through samples.