Part I · 第 6 章优化 · 6.11Part I · Ch. 6 Optimization · 6.11

无梯度与采样优化Derivative-free & Sampling-based Optimization

并不是所有代价函数都能求导：碰撞是 0 或 1，仿真器是个黑盒，策略的回报要跑完整个回合才知道。这时我们只能"问"函数在某些点的值。采样优化的做法很朴素：撒一把点，看哪些好，把分布挪向好的地方。随机搜索、交叉熵法 (CEM)、CMA-ES 和 MPPI 都是这一思路的变体，其中 MPPI 已经成了机器人实时控制的主力之一。 Not every cost function can be differentiated: a collision is 0 or 1, a simulator is a black box, a policy's return is known only after a whole episode. All we can do is "ask" the function for its value at chosen points. Sampling-based optimization is beautifully plain: scatter some points, see which are good, and shift the distribution toward them. Random search, the cross-entropy method (CEM), CMA-ES and MPPI are all variants of that idea, and MPPI has become a workhorse of real-time robot control.

约 30 分钟~30 min 前置：4.4 高斯分布 · 6.3 梯度下降 · 6.1 什么是优化问题Prereqs: 4.4 Gaussian · 6.3 Gradient descent · 6.1 Optimization problems 4 个交互4 interactives

1为什么机器人需要它Why robots need this

前面几节的所有优化器（6.3、6.6、6.9）都靠一件事吃饭：导数。可机器人的代价函数常常不配合：

不连续：路径与障碍物相撞的代价是"撞了 / 没撞"，跳变处没有导数，平坦处导数为零，梯度什么也告诉不了你。
黑盒：物理仿真器、渲染器、一个已经训练好的神经网络。你可以运行它，但没人写过它的雅可比，用自动微分穿过一个含接触的仿真往往得到噪声很大的梯度。
多峰：绕左边还是绕右边？抓杯子的把手还是杯身？每一种选择都是一个局部最小，局部的梯度只会把你带进最近的那一个。
噪声：真机上评估一次代价就是做一次实验，结果带随机性。

这时只要能"算出某个候选解的代价"就够了。采样优化不求导，而是让一个分布（通常是高斯）产生一批候选，根据它们的代价更新这个分布。它天然并行（每个候选互不相干，GPU 上一批同时算），对代价函数的形状几乎没有要求，因此成了实时 MPC（MPPI）、强化学习（进化策略 ES）、参数调优（CMA-ES）和任务规划里的常用工具。代价是：在高维空间里它需要的样本数比有梯度时多得多（本节末尾会量化）。

Every optimizer so far (Lessons 6.3, 6.6, 6.9) lives on one thing: derivatives. But robot cost functions often refuse to cooperate:

Discontinuous: the cost of a path hitting an obstacle is "hit / not hit". There is no derivative at the jump and the derivative is zero on the flats; the gradient tells you nothing.
Black boxes: a physics simulator, a renderer, an already-trained neural network. You can run it but nobody wrote its Jacobian, and differentiating through a simulator with contacts often gives very noisy gradients.
Multimodal: pass on the left or the right? Grasp the mug by its handle or its body? Every choice is a local minimum, and a local gradient only drags you into the nearest one.
Noisy: on a real robot, evaluating the cost means running an experiment, and results are random.

In such cases all we need is the ability to "compute the cost of a candidate". Sampling-based optimization takes no derivatives: a distribution (usually Gaussian) proposes a batch of candidates, and their costs update that distribution. It is naturally parallel (candidates are independent, a whole batch runs at once on a GPU), makes almost no assumptions about the shape of the cost, and so has become a common tool in real-time MPC (MPPI), reinforcement learning (evolution strategies, ES), parameter tuning (CMA-ES) and task planning. The price: in high dimensions it needs many more samples than a method with gradients (quantified at the end of this lesson).

2直觉：撒点就是在估计一个"模糊梯度"Intuition: scattering points estimates a "blurred gradient"

想象在一维曲线上，当前的猜测是 $\mu$。我们从 $\mathcal N(\mu,\sigma^2)$ 里抽 $N$ 个点 $x_i$，量出每个点的代价 $f(x_i)$。代价低的点更好，所以新的均值应该往它们那边挪：把每个点按它的"好坏程度"打一个权重 $w_i$，新均值取加权平均 $\mu'=\sum_iw_ix_i/\sum_iw_i$。

两种常见的打分办法：精英法 (CEM)，只保留最好的 $\rho N$ 个，权重 1，其余 0；softmax 法 (MPPI)，权重 $w_i=\exp\!\big(-(f_i-f_{\min})/\lambda\big)$，温度 $\lambda$ 控制"有多挑剔"。

有一个值得记住的事实：这样得到的更新方向，其实是在估计高斯平滑后的函数 $f_\sigma(x)=\mathbb E_{\epsilon}[f(x+\sigma\epsilon)]$ 的负梯度，与 $\sigma^2/\lambda$ 成正比。平滑相当于把尖锐的小坑填平，所以 $\sigma$ 就是它的"视野"：$\sigma$ 小，只看得见脚下的局部最小；$\sigma$ 大，能越过小山包，但也会把真正最小点的位置抹糊。下图中，琥珀色虚线就是 $f_\sigma$。

Picture a 1D curve and a current guess $\mu$. Draw $N$ points $x_i$ from $\mathcal N(\mu,\sigma^2)$ and measure each cost $f(x_i)$. Low-cost points are better, so the new mean should move toward them: give each point a weight $w_i$ according to how good it is and take the weighted average $\mu'=\sum_iw_ix_i/\sum_iw_i$.

Two common ways to weigh: the elite rule (CEM) keeps only the best $\rho N$ points with weight 1 and gives the rest 0; the softmax rule (MPPI) uses $w_i=\exp\!\big(-(f_i-f_{\min})/\lambda\big)$, where the temperature $\lambda$ sets "how picky" we are.

One fact worth remembering: the resulting update direction actually estimates the negative gradient of the Gaussian-smoothed function $f_\sigma(x)=\mathbb E_{\epsilon}[f(x+\sigma\epsilon)]$, scaled by $\sigma^2/\lambda$. Smoothing fills in sharp little pits, so $\sigma$ acts as a "field of view": with small $\sigma$ you see only the local minimum underfoot; with large $\sigma$ you can hop over small hills, but the position of the true minimum also gets blurred. In the figure the dashed amber curve is $f_\sigma$.

FIG 1采样如何估计"模糊的梯度"How sampling estimates a "blurred gradient"

灰色实线是代价 $f(x)=0.08x^2+0.8\sin 1.5x$（有三个局部最小），琥珀色虚线是平滑后的 $f_\sigma$。拖动底部的橙色手柄移动均值 $\mu$。每个采样点在曲线上画成一个圆点，半径表示它的权重；竖线是权重本身。底部的橙色箭头是 $\mu\to\mu'$。拖大 $\sigma$，$f_\sigma$ 里的小坑会消失。 The solid grey curve is the cost $f(x)=0.08x^2+0.8\sin 1.5x$ (three local minima) and the dashed amber curve is the smoothed $f_\sigma$. Drag the amber handle at the bottom to move the mean $\mu$. Each sample is a dot on the curve whose radius is its weight; the vertical bars are the weights themselves. The amber arrow at the bottom is $\mu\to\mu'$. Increase $\sigma$ and the small pits of $f_\sigma$ disappear.

试一试Try this

保持 $\mu\approx 2.9$（右边的局部最小）、$\sigma$ 很小，按"运行"：均值纹丝不动，被局部最小困住。Keep $\mu\approx 2.9$ (the local minimum on the right) and $\sigma$ small, press "Run": the mean does not budge, trapped by the local minimum.
把 $\sigma$ 调到 1.2 以上，再按"运行"：均值越过小山包，跑到左边的全局最小（$x\approx-0.96$）。Raise $\sigma$ above 1.2 and press "Run" again: the mean hops the hill and reaches the global minimum on the left ($x\approx-0.96$).
在 MPPI 模式下把温度 $\lambda$ 拖到最大：权重几乎均匀，新均值几乎不动（"有效样本数"接近 $N$，等于没有挑剔）。再拖到最小：只有一个点有权重，容易被噪声带跑。In MPPI mode, drag the temperature $\lambda$ to its maximum: weights become almost uniform and the mean barely moves (the "effective sample size" approaches $N$, i.e. no picking at all). Then to the minimum: one point takes all the weight and noise can mislead you.

3动手玩：四种采样器与梯度的竞技场Play: four samplers and gradient descent in the arena

下面把四种方法放到同一张二维地形上：

随机搜索（(1+λ)-ES）：围绕当前最好点撒一批，谁比当前点好就搬过去。
CEM：取最好的 25% 作为精英，用它们的均值和协方差作为下一代的高斯。
CMA-ES：CEM 的"加强版"，对精英加权，并用进化路径平滑地调整协方差和步长（第 4 节）。
MPPI：固定高斯，样本按 softmax 权重取加权平均。

作对比的是普通梯度下降（用有限差分求数值梯度）。点击地图设定起点；"运行"让所选方法跑完 1200 次函数求值；下方的曲线记录"到目前为止最好的代价"，不同方法的曲线可以叠加比较。

Below, four methods share one 2D terrain:

Random search ((1+λ)-ES): scatter a batch around the current best point and move there if anyone beats it.
CEM: keep the best 25% as elites and use their mean and covariance as the next Gaussian.
CMA-ES: the "enhanced CEM", weighting the elites and adapting covariance and step size smoothly through evolution paths (Section 4).
MPPI: a fixed Gaussian whose samples are averaged with softmax weights.

For comparison there is plain gradient descent (a numerical gradient from finite differences). Click the map to set the start; "Run" lets the chosen method spend 1200 function evaluations; the chart below records the "best cost so far", and curves of different methods stack up for comparison.

FIG 2竞技场：多峰、病态与不连续的地形The arena: multimodal, ill-conditioned and discontinuous terrain

最好代价 vs. 函数求值次数best cost so far vs. function evaluations

蓝点是本代的样本（精英或权重大的点更大、更不透明），橙色粗点是当前均值，紫色轨迹是均值的历史，紫色椭圆是当前的采样分布（1 个标准差）。"Rastrigin"有上百个局部最小，"不连续"地形里有一块高台（圆盘）把起点和终点隔开，其中 $|x-2.4|+|y-1.6|$ 的尖点是 L1 的"V 形谷"，有限差分在高台边缘会得到巨大且误导的梯度。 Blue dots are this generation's samples (elites or heavy-weight ones are larger and more opaque), the big amber dot is the current mean, the purple trail is the mean's history, and the purple ellipse is the current sampling distribution (one standard deviation). "Rastrigin" has over a hundred local minima; the "Discontinuous" terrain has a raised plateau (a disc) between start and goal, with an L1 "V-shaped valley" at $|x-2.4|+|y-1.6|$; finite differences at the plateau's edge give huge, misleading gradients.

试一试Try this

在 Rastrigin 上从默认起点运行梯度下降：它很快停在最近的局部最小，再也不动。On Rastrigin, run gradient descent from the default start: it quickly parks in the nearest local minimum and never moves again.
在同一地形上运行 CMA-ES（样本数默认 30）：它越过无数个小坑，找到全局最小 $(0,0)$（最好代价低于 0.05）。若样本数太少，会怎样？On the same terrain run CMA-ES (default population 30): it hops over countless small pits and finds the global minimum $(0,0)$ (best cost below 0.05). What if the population is too small?
切到"不连续"地形，运行 MPPI，把最好代价压到 0.1 以下，而梯度下降做不到。再试 CEM：默认设置下它的方差很快塌缩，停在半路（误区 3），要把样本数和 $\sigma$ 调大才行。Switch to the "Discontinuous" terrain and run MPPI to get the best cost below 0.1, which gradient descent cannot. Then try CEM: with the default settings its variance collapses and it stalls halfway (Pitfall 3) unless you raise the population and $\sigma$.

核心洞见Key insight

采样法用全局的视野换局部的精度：它不会被小坑或悬崖卡住，但每一步要付出一批函数求值，而且越接近最小值，需要缩小 $\sigma$ 才能精确（CEM 和 CMA-ES 自己会缩，MPPI 和随机搜索的 $\sigma$ 是你给的）。有梯度、且问题是光滑的时候，梯度法几乎总是更快；两者常常搭配：先采样找到好的盆地，再用梯度精修。

Sampling trades local precision for a global field of view: it is not trapped by small pits or cliffs, but every step costs a batch of function evaluations, and to be precise near the minimum $\sigma$ must shrink (CEM and CMA-ES shrink it themselves; for MPPI and random search $\sigma$ is whatever you set). When gradients exist and the problem is smooth, gradient methods are almost always faster; the two are often combined: sample to find a good basin, then polish with gradients.

4再看数学The math

提示：把鼠标悬停在公式中带底色的符号上，FIG 1 中对应的元素会被高亮（权重、新均值、平滑函数）。Tip: hover the highlighted symbols in the formulas; the matching elements in FIG 1 light up (weights, new mean, the smoothed function).

平滑函数的梯度，用采样估计The gradient of the smoothed function, estimated by sampling

定义 $\hl{fs}{f_\sigma(\x)}=\mathbb E_{\boldsymbol\epsilon\sim\mathcal N(0,I)}\,f(\x+\sigma\boldsymbol\epsilon)$。对高斯求导有一个漂亮的恒等式：

Define $\hl{fs}{f_\sigma(\x)}=\mathbb E_{\boldsymbol\epsilon\sim\mathcal N(0,I)}\,f(\x+\sigma\boldsymbol\epsilon)$. Differentiating a Gaussian gives a lovely identity:

$$ \nabla f_\sigma(\x)=\frac1\sigma\,\mathbb E\big[f(\x+\sigma\boldsymbol\epsilon)\,\boldsymbol\epsilon\big]\ \approx\ \frac{1}{N\sigma}\sum_{i=1}^N\big(f(\x+\sigma\boldsymbol\epsilon_i)-f(\x)\big)\,\boldsymbol\epsilon_i $$

右边只用到函数值，不用导数，这是进化策略 (ES)、有限差分的随机版本、策略梯度里 REINFORCE 的共同祖先。减去 $f(\x)$ 不改变期望，却大幅降低方差（这叫基线）。

The right-hand side uses only function values, no derivatives. It is the common ancestor of evolution strategies (ES), randomized finite differences and the REINFORCE of policy gradients. Subtracting $f(\x)$ leaves the expectation unchanged but greatly reduces variance (that is a baseline).

加权平均：CEM 与 MPPIWeighted averaging: CEM and MPPI

设样本 $\x_i\sim\mathcal N(\mathbf m,\Sigma)$，代价 $f_i=f(\x_i)$。它们共用同一个更新形式：

With samples $\x_i\sim\mathcal N(\mathbf m,\Sigma)$ and costs $f_i=f(\x_i)$, both share one update form:

$$ \hl{mean}{\mathbf m'}=\sum_i \hl{w}{\bar w_i}\,\x_i,\qquad \bar w_i=\frac{w_i}{\sum_jw_j},\qquad w_i=\begin{cases}\mathbb 1[\,f_i\ \text{among best }\rho N\,] & \text{CEM}\\[2pt] \exp\!\big(-(f_i-f_{\min})/\hl{lam}{\lambda}\big) & \text{MPPI}\end{cases} $$

MPPI 的权重是 $\exp(-f/\lambda)$ 的重要性采样：把目标分布取为 $q^\star(\x)\propto p(\x)e^{-f(\x)/\lambda}$（"低代价的地方概率更大"），$\mathbf m'$ 就是 $q^\star$ 的均值，用样本估计。把它代入上面的高斯恒等式可得，当 $f$ 在样本云内变化不大时

MPPI's weights are importance sampling with $\exp(-f/\lambda)$: take the target distribution $q^\star(\x)\propto p(\x)e^{-f(\x)/\lambda}$ ("more probability where cost is low"); $\mathbf m'$ is then the mean of $q^\star$, estimated from the samples. Combining with the Gaussian identity above, when $f$ varies little across the cloud,

$$ \mathbf m'-\mathbf m\ \approx\ -\frac{\sigma^2}{\lambda}\,\nabla f_\sigma(\mathbf m) $$

所以 MPPI 是对平滑代价的梯度下降，步长为 $\sigma^2/\lambda$，只是梯度用采样估计。温度 $\lambda$ 太小，权重集中在一个样本上（"有效样本数" $(\sum w)^2/\sum w^2\to1$），估计噪声大；太大，权重趋于均匀，$\mathbf m'\approx\mathbf m$，不再前进。CEM 的精英法是一个不需要调温度的"秩"版本：只看排名，对代价的尺度不敏感。CEM 还要更新协方差：取精英的经验协方差（矩匹配，等价于让高斯到精英分布的 KL 散度最小）。

So MPPI is gradient descent on the smoothed cost with step $\sigma^2/\lambda$, the gradient being estimated by sampling. Too small a temperature $\lambda$ concentrates the weight on one sample (the "effective sample size" $(\sum w)^2/\sum w^2\to1$) and the estimate is noisy; too large and the weights become uniform, $\mathbf m'\approx\mathbf m$, and progress stops. CEM's elite rule is a "rank-based" version that needs no temperature: only the ranking matters, so it is insensitive to the scale of the cost. CEM also updates the covariance, taking the elites' empirical covariance (moment matching, equivalent to minimizing the KL divergence from the Gaussian to the elite distribution).

CMA-ES 一瞥A glimpse of CMA-ES

CMA-ES 把排名前 $\mu$ 的样本 $\mathbf y_{(i)}=(\x_{(i)}-\mathbf m)/\sigma$ 加权（权重 $w_i$ 随名次递减），更新均值、协方差与步长：

CMA-ES weights the top $\mu$ samples $\mathbf y_{(i)}=(\x_{(i)}-\mathbf m)/\sigma$ (weights $w_i$ decreasing with rank) and updates mean, covariance and step size:

$$ \mathbf m\leftarrow\mathbf m+\sigma\sum_{i=1}^\mu w_i\mathbf y_{(i)},\qquad C\leftarrow(1-c_1-c_\mu)C+c_1\,\mathbf p_c\mathbf p_c^\top+c_\mu\sum_{i=1}^{\mu} w_i\,\mathbf y_{(i)}\mathbf y_{(i)}^\top,\qquad \sigma\leftarrow\sigma\exp\!\Big(\tfrac{c_\sigma}{d_\sigma}\Big(\tfrac{\|\mathbf p_\sigma\|}{\mathbb E\|\mathcal N(0,I)\|}-1\Big)\Big) $$

其中 $\mathbf p_c,\mathbf p_\sigma$ 是"进化路径"，即各代均值位移的指数滑动平均：如果连续几代都朝同一个方向走，路径就长，$\sigma$ 变大；来回打转，路径短，$\sigma$ 变小。协方差会逐渐"对齐"到地形的狭长方向，这相当于在没有 Hessian 的情况下学出了一个近似的二阶度量。FIG 2 里的 CMA-ES 就是这套更新（$n=2$ 的精确实现，参数取 Hansen 教程的默认值）。

Here $\mathbf p_c,\mathbf p_\sigma$ are "evolution paths", exponential moving averages of the mean's displacements: if the mean keeps heading the same way for several generations the path is long and $\sigma$ grows; if it dithers, the path is short and $\sigma$ shrinks. The covariance gradually "aligns" with the long axis of the terrain, learning an approximate second-order metric with no Hessian at all. The CMA-ES in FIG 2 implements exactly these updates (for $n=2$, with the default constants of Hansen's tutorial).

5机器人中的它：MPPI 实时避障In robotics: real-time obstacle avoidance with MPPI

MPPI（Model Predictive Path Integral control，Williams 等）把 MPC（6.8 节）的"预测未来、选最好的控制序列、只执行第一个"和上面的采样更新结合起来：每个控制周期，在当前计划 $U=(\mathbf u_0,\dots,\mathbf u_{H-1})$ 上加 $K$ 份随机扰动，用模型把每一份往前仿真 $H$ 步，得到总代价 $S_k$，按 $\exp(-S_k/\lambda)$ 加权平均，更新计划，执行 $\mathbf u_0$，把计划向前平移一格，下个周期重来。

它不要求代价和动力学可导，所以可以直接用"撞了就罚一个大数"这种不连续代价（下图里每步撞障罚 160），也可以用任何非线性动力学（轮式、四旋翼、带摩擦的接触）。下图是一个质点机器人（加速度控制）要穿过三个障碍物到达绿色目标。每条细线是一次 rollout，越不透明权重越大（红色表示撞到了），琥珀色粗线是加权平均后的计划。拖动目标或障碍物，计划会实时重新规划。

MPPI (Model Predictive Path Integral control, Williams et al.) combines the MPC idea of Lesson 6.8 ("predict the future, pick the best control sequence, execute only the first") with the sampling update above: each control cycle, add $K$ random perturbations to the current plan $U=(\mathbf u_0,\dots,\mathbf u_{H-1})$, simulate each forward $H$ steps with the model to get a total cost $S_k$, average with weights $\exp(-S_k/\lambda)$, update the plan, execute $\mathbf u_0$, shift the plan one step and repeat next cycle.

It needs neither differentiable costs nor differentiable dynamics, so it can use discontinuous costs like "hit = a large penalty" directly (160 per colliding step in the figure below), with any nonlinear dynamics (wheeled, quadrotor, contact with friction). Below, a point-mass robot (acceleration control) must pass three obstacles to reach the green goal. Each thin line is one rollout, more opaque for larger weight (red means a collision); the thick amber line is the weighted-average plan. Drag the goal or an obstacle and the plan re-optimizes in real time.

FIG 3MPPI：采样 rollout，加权平均出计划MPPI: sample rollouts, weight-average into a plan

每个控制周期（0.1 s）用 $K$ 条 rollout 做一次 MPPI 更新（视野 $H=25$ 步 = 2.5 s）。代价：到目标的距离平方 + 对速度的轻微惩罚 + 撞到障碍物的惩罚（0/1 不连续，膨胀 0.25 m）。温度以"代价标准差的倍数"给出，所以不用随问题改量纲。红色带圈的点是碰撞发生的位置。 Each control cycle (0.1 s) does one MPPI update with $K$ rollouts (horizon $H=25$ steps = 2.5 s). Cost: squared distance to the goal + a mild velocity penalty + an obstacle-hit penalty (0/1, discontinuous, inflated by 0.25 m). The temperature is given in multiples of the cost standard deviation, so it needs no rescaling from problem to problem. A red ringed dot marks where a collision happened.

按"开始"，让机器人不碰任何障碍物地到达目标（距离 0.4 以内）。Press "Start" and get the robot to the goal (within 0.4) without touching any obstacle.
机器人运动途中，把一个障碍物拖到它的前方：看计划如何实时绕开。While the robot is moving, drag an obstacle in front of it and watch the plan swerve in real time.
把样本数 $K$ 降到 8：轨迹变得抖动，更容易撞到障碍物。样本越多，计划越稳。Reduce the sample count $K$ to 8: trajectories get jittery and collisions become likelier. More samples, steadier plans.

没有免费午餐：维数的代价No free lunch: the price of dimension

采样法的弱点是维度。下面是一个真实的小实验：在 $d$ 维的病态二次函数 $f(\x)=\tfrac12\sum_ic_ix_i^2$（$c_i$ 从 1 到 $\kappa$ 几何分布）上，数一数把代价压到初值的百万分之一需要多少次函数求值：①用有限差分求梯度的梯度下降（每个梯度要 $2d$ 次求值）；②(1+1)-ES（每次只采 1 个点，用"1/5 成功率法则"调步长，是最简单的无梯度方法）；③有解析梯度的梯度下降（一次梯度约等于 3 次函数求值，与 $d$ 无关）。按"运行"开始。

The weakness of sampling is dimension. Here is a real little experiment: on an ill-conditioned $d$-dimensional quadratic $f(\x)=\tfrac12\sum_ic_ix_i^2$ ($c_i$ geometrically spaced from 1 to $\kappa$), count how many function evaluations it takes to reduce the cost to one millionth of its initial value with: (1) gradient descent with a finite-difference gradient (each gradient costs $2d$ evaluations); (2) (1+1)-ES (one point per step, step size tuned by the "1/5 success rule", the simplest derivative-free method); (3) gradient descent with an analytic gradient (a gradient costs about 3 function evaluations, independent of $d$). Press "Run".

FIG 4无梯度的价格：求值次数随维度增长The price of no gradient: evaluations vs. dimension

双对数坐标，每个点是一次真正跑出来的结果（(1+1)-ES 取 3 个随机种子的中位数）。灰色虚线是斜率为 1 的参考线：有限差分和随机采样的开销都随 $d$ 线性增长，只有能拿到梯度（比如自动微分）时才与维度无关。条件数 $\kappa$ 越大，三者都变慢。 Log–log axes; every point is an actual run ((1+1)-ES uses the median of 3 random seeds). The grey dashed line has slope 1 for reference: the cost of finite differences and of random sampling both grow linearly with $d$; only with a gradient oracle (e.g. automatic differentiation) is it independent of dimension. The larger the condition number $\kappa$, the slower all three get.

按"运行"，再把条件数 $\kappa$ 拖到 100：三条曲线都上移，但斜率不变。Press "Run", then drag the condition number $\kappa$ to 100: all three curves move up, but their slopes stay the same.

真实系统里In real systems

MPPI 在越野自动驾驶（如 AutoRally 的激进驾驶）、四旋翼避障、足式机器人的实时规划里被广泛使用，一次更新通常并行评估几千条 rollout（GPU 上几毫秒）。实用中还要加：对控制序列做平滑滤波（否则输出抖动）、用上一周期的计划热启动（FIG 3 的"平移计划"）、对采样噪声使用相关性（让控制序列更平滑）。CMA-ES 则常用于调超参数、标定、步态参数和奖励函数的优化；进化策略 (OpenAI-ES) 还被用来训练神经网络策略，利用的正是上面的 $\nabla f_\sigma$ 估计与海量并行。

MPPI is widely used in off-road autonomous driving (e.g. the aggressive driving of AutoRally), quadrotor obstacle avoidance and legged-robot real-time planning, typically evaluating thousands of rollouts in parallel per update (milliseconds on a GPU). Practical versions add smoothing filters on the control sequence (otherwise the output chatters), warm starts from the previous cycle's plan (the "shifted plan" of FIG 3), and temporally correlated sampling noise (for smoother controls). CMA-ES is a favorite for tuning hyperparameters, calibration, gait parameters and reward functions; evolution strategies (OpenAI-ES) even train neural-network policies, using exactly the $\nabla f_\sigma$ estimator above and massive parallelism.

6常见误区Common pitfalls

误区 1：低估样本数与维度的关系Pitfall 1: underestimating how samples scale with dimension

FIG 4 的结论很直白：维度翻倍，需要的求值次数大约也翻倍。在 FIG 2 把 CMA-ES 的样本数调到很小，在多峰地形上就会掉进局部最小。MPPI 的维度是"$H\times$ 控制维数"，视野越长、控制通道越多，需要的 rollout 越多。别指望用几十个样本优化几百维的东西。

The conclusion of FIG 4 is blunt: double the dimension and you need roughly double the evaluations. Shrink CMA-ES's population in FIG 2 and it falls into local minima on the multimodal terrain. MPPI's dimension is "$H\times$ control dimension": the longer the horizon and the more control channels, the more rollouts you need. Do not hope to optimize hundreds of dimensions with a few dozen samples.

误区 2：温度 $\lambda$ 与代价的尺度脱节Pitfall 2: a temperature $\lambda$ unrelated to the cost scale

$\exp(-f/\lambda)$ 里 $f$ 与 $\lambda$ 的比值才是关键。把代价乘 100，同样的 $\lambda$ 就从"适中"变成"只有最好的一个样本有权重"。务必减去最小值（数值稳定），并把 $\lambda$ 设成相对于样本代价散布的量（如 FIG 3 的"×标准差"），或者干脆用 CEM 那样的排名权重。

In $\exp(-f/\lambda)$ only the ratio of $f$ to $\lambda$ matters. Multiply the cost by 100 and the same $\lambda$ goes from "moderate" to "only the single best sample counts". Always subtract the minimum (numerical stability), and set $\lambda$ relative to the spread of the sampled costs (the "× standard deviation" of FIG 3) or use rank-based weights as CEM does.

误区 3：CEM 的方差塌缩Pitfall 3: CEM's variance collapse

CEM 用精英的协方差当下一代的协方差；精英总是比整体更集中，所以方差一代比一代小，常常在到达最小点之前就缩没了（早熟收敛）。常见补救：给协方差加一个下限、对新旧协方差做平滑混合、或增加样本数。CMA-ES 的进化路径机制正是为了避免这个问题。

CEM uses the elites' covariance as the next covariance; elites are always more concentrated than the population, so the variance shrinks generation after generation and often vanishes before the minimum is reached (premature convergence). Typical fixes: floor the covariance, blend old and new covariances, or use more samples. CMA-ES's evolution-path machinery exists to avoid exactly this.

误区 4：用有噪声的代价却当成确定的Pitfall 4: treating a noisy cost as deterministic

真机上评估一次代价可能带噪声。如果只跑一次，随机搜索里的"谁更好"可能被噪声翻转，整个搜索被误导。对噪声问题要用更多样本、对代价重复评估取平均，或使用对噪声更稳健的权重方案（排名比绝对值更稳健）。

On a real robot a single cost evaluation can be noisy. If you run it only once, "who is better" in random search may be flipped by noise and the whole search misled. For noisy problems use more samples, average repeated evaluations, or choose weighting schemes that tolerate noise (ranks are more robust than absolute values).

7小练习Check yourself

1. 增大采样分布的标准差 $\sigma$，对所优化的"平滑函数" $f_\sigma$ 有什么影响？1. What does increasing the sampling standard deviation $\sigma$ do to the smoothed function $f_\sigma$ being optimized?

$f_\sigma$ 是 $f$ 与高斯核的卷积：窄坑（比 $\sigma$ 窄的特征）被平均掉，宽的盆地保留，但因为是平均，极小点位置也有偏移。这就是 FIG 1 里"拖大 $\sigma$ 就能逃出局部最小"的原因。$f_\sigma$ is $f$ convolved with a Gaussian: features narrower than $\sigma$ are averaged away while wide basins survive, but since it is an average the minimizer's position also shifts. That is why "raising $\sigma$" lets FIG 1 escape the local minimum.

2. MPPI 的权重 $w_i=\exp(-(S_i-S_{\min})/\lambda)$。当 $\lambda\to\infty$ 时，更新规则变成什么？2. MPPI's weights are $w_i=\exp(-(S_i-S_{\min})/\lambda)$. What does the update become as $\lambda\to\infty$?

$\lambda\to\infty$ 时所有 $e^{-(\cdot)/\lambda}\to1$，权重相等，没有任何挑剔，新均值只是随机噪声的平均，期望上不动。$\lambda\to0$ 才是"只取最好的一个"（硬 min）。As $\lambda\to\infty$ every $e^{-(\cdot)/\lambda}\to1$: equal weights, no picking, and the new mean is just the average of random noise, stationary in expectation. It is $\lambda\to0$ that gives "take only the best one" (a hard min).

3. CEM 每代采样 $N=80$ 个点，精英比例 $\rho=0.25$。新的均值由多少个点算出？3. CEM samples $N=80$ points per generation with elite fraction $\rho=0.25$. How many points go into the new mean?

$\rho N=0.25\times80=20$：只用代价最低的 20 个点的均值（和协方差）更新分布，其余 60 个点只起"排名"的作用。$\rho N=0.25\times80=20$: the distribution is updated from the mean (and covariance) of the 20 lowest-cost points only; the other 60 serve only to establish the ranking.

4. 对 $d=100$ 维的函数，用中心有限差分算一次完整梯度，需要多少次函数求值？4. For a $d=100$-dimensional function, how many function evaluations does one full gradient by central finite differences need?

每个坐标需要 $f(\x+h\mathbf e_i)$ 和 $f(\x-h\mathbf e_i)$ 两次求值，共 $2d=200$（前向差分是 $d+1=101$）。自动微分的反向模式则只需约 3 次函数求值的时间，与 $d$ 无关，这就是"有梯度"的巨大价值。Each coordinate needs $f(\x+h\mathbf e_i)$ and $f(\x-h\mathbf e_i)$: $2d=200$ in total (forward differences need $d+1=101$). Reverse-mode automatic differentiation needs only about 3 function evaluations' worth of time, independent of $d$: that is the huge value of "having a gradient".

5. 为什么 MPPI 可以直接使用"碰到障碍物就罚一个大数"这样的不连续代价？5. Why can MPPI use a discontinuous cost like "hit an obstacle = a large penalty" directly?

采样 + 加权平均只用代价的值。带碰撞的 rollout 代价高，$\exp(-S/\lambda)$ 把它们的权重压得很低，等价于计划被推向无碰撞的方向。（"平滑"是隐式发生的：平均本身就是对 $f$ 的平滑。）Sampling plus weighted averaging uses only cost values. Colliding rollouts have high cost and $\exp(-S/\lambda)$ crushes their weights, which pushes the plan toward collision-free directions. (The smoothing happens implicitly: averaging is itself smoothing of $f$.)

8延伸阅读Further reading

N. Hansen, The CMA Evolution Strategy: A Tutorial, arXiv:1604.00772, 2016 — FIG 2 中 CMA-ES 的出处，参数默认值和每一步更新都在里面the source of the CMA-ES in FIG 2; default constants and every update are in it
G. Williams, P. Drews, B. Goldfain, J. M. Rehg & E. A. Theodorou, Information Theoretic MPC for Model-Based Reinforcement Learning, ICRA 2017 — MPPI 的信息论推导与越野驾驶实验the information-theoretic derivation of MPPI and its off-road driving experiments
R. Y. Rubinstein & D. P. Kroese, The Cross-Entropy Method, Springer, 2004 — 交叉熵法的经典专著the classic monograph on the cross-entropy method
T. Salimans, J. Ho, X. Chen, S. Sidor & I. Sutskever, Evolution Strategies as a Scalable Alternative to Reinforcement Learning, arXiv:1703.03864, 2017 — 用 $\nabla f_\sigma$ 估计训练神经网络策略training neural-network policies with the $\nabla f_\sigma$ estimator
J. Nocedal & S. J. Wright, Numerical Optimization, 2nd ed., Springer, 2006 — 有限差分梯度与无导数方法的背景background on finite-difference gradients and derivative-free methods