Covariance Matrix Adaptation Evolution Strategy (CMA-ES)

Why Does This Exist?

Some problems hand you no gradient. The simulator will not differentiate, the score lands once per episode, or the surface jumps. Stochastic gradient descent has nothing to chew on there, and even policy gradient methods want a gradient signal you may not trust.

Plain evolution fills the gap with a fixed cloud: sample around a mean, keep the best, move on. Round clouds waste samples on stretched problems. Picture one dial a hundred times touchier than the next, or a thin curved valley. Too wide across the valley, too timid along it. For the general spread question, see exploration vs exploitation and evolution strategies.

CMA-ES learns the cloud instead of hand-setting it. Each generation it relearns the center, the shape, and the stride from the winners. This page teaches that loop.

Think of It Like This

How It Actually Works

One distribution rules every generation:

$x = m + \sigma C^{1/2} z, \quad z \sim \mathcal{N}(0, I)$

Here $m$ is the mean, the current best guess at the center. The scalar $\sigma$ is the step size, one global stride. The matrix $C$ is the covariance, whose axes set the ellipse directions and whose eigenvalues set their squared lengths. Each draw $z$ is standard normal, reshaped by $C$ and scaled by $\sigma$ into a candidate $x$.

Each round samples $\lambda$ candidates, scores them with fitness $f$ (lower better here), ranks them best first, and keeps the top $\mu$ with fixed weights $w_1 \ge \dots \ge w_\mu$ summing to 1. Only the ranking matters, never the raw scores.

Worked example

Start at $m = [0, 0]$ with $\sigma = 1$ and $C = I$. Three samples return ranked:

• $x_1 = [1.0, 0.5]$, weight $w_1 = 0.5$
• $x_2 = [0.2, 1.2]$, weight $w_2 = 0.3$
• $x_3 = [-0.8, -0.3]$, weight $w_3 = 0.2$

New mean is the weighted mix $m' = \sum w_i x_i$. First coordinate: $0.5 \times 1.0 + 0.3 \times 0.2 + 0.2 \times (-0.8) = 0.50 + 0.06 - 0.16 = 0.40$. Second: $0.5 \times 0.5 + 0.3 \times 1.2 + 0.2 \times (-0.3) = 0.25 + 0.36 - 0.06 = 0.55$. So $m' = [0.40, 0.55]$.

Selection mass is $\mu_{\text{eff}} = 1 / (0.25 + 0.09 + 0.04) = 1 / 0.38 \approx 2.63$, so this round counts as about two and a half independent winners.

How shape and stride follow

Covariance blends three terms: most of the old $C$, a rank-one stretch along the multi-round path $p_c$, and a rank-$\mu$ stretch along this round's winning steps. One lucky round cannot yank it because the learning rates $c_1$ and $c_\mu$ stay small and keep $C$ positive-definite.

Step size watches a second path $p_\sigma$. Marches in one direction grow it past its random baseline near $1.25$ in two dimensions, so $\sigma$ grows and strides lengthen. Zigzags shrink it and the cloud fine-tunes.

Ranking-only choice buys three invariances: shifting the problem changes nothing, rotating it costs the same since $C$ learns orientation, and any increasing rescale of $f$ behaves identically. The bill is samples: populations grow like $4 + 3 \ln n$ and full $C$ learning costs on the order of $n^2$ in dimension $n$.

Code

The weighted mean step in plain Python:

1samples: list[tuple[float, float]] = [(1.0, 0.5), (0.2, 1.2), (-0.8, -0.3)]2weights: list[float] = [0.5, 0.3, 0.2]3
4mean_x: float = sum(w * x for w, (x, _) in zip(weights, samples))5mean_y: float = sum(w * y for w, (_, y) in zip(weights, samples))6mu_eff: float = 1.0 / sum(w * w for w in weights)7
8print(f"{mean_x:.2f} {mean_y:.2f}")  # -> 0.40 0.559print(f"{mu_eff:.2f}")  # -> 2.63

Both lines match the hand arithmetic. Swap the weights and watch the mean chase the heaviest try.

Watch Out For

The Quick Version

• Candidates come from one Gaussian $m + \sigma C^{1/2} z$ and the mean moves to the weighted winners, here $[0.40, 0.55]$ from weights $[0.5, 0.3, 0.2]$.
• Covariance pairs a rank-$\mu$ stretch along this round with a rank-one stretch along the multi-round path.
• Step size grows on steady marches and shrinks on zigzags against a random baseline near $1.25$ in two dimensions.
• Rank-only selection gives translation, rotation, and rescale invariance for free.
• No gradients needed, which suits black-box simulators, but full shape learning costs on the order of $n^2$ samples.

What to Read Next

• Stochastic Gradient Descent in RL
• Exploration vs. Exploitation
• Policy Gradient Methods