Part I · 第 6 章 优化 · 6.11

无梯度与采样优化

并不是所有代价函数都能求导：碰撞是 0 或 1，仿真器是个黑盒，策略的回报要跑完整个回合才知道。这时我们只能"问"函数在某些点的值。采样优化的做法很朴素：撒一把点，看哪些好，把分布挪向好的地方。随机搜索、交叉熵法 (CEM)、CMA-ES 和 MPPI 都是这一思路的变体，其中 MPPI 已经成了机器人实时控制的主力之一。

约 30 分钟 前置：4.4 高斯分布 · 6.3 梯度下降 · 6.1 什么是优化问题 4 个交互

    1为什么机器人需要它

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

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

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

    2直觉：撒点就是在估计一个"模糊梯度"

    想象在一维曲线上，当前的猜测是 \(\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\)。

    FIG 1采样如何估计"模糊的梯度"
    灰色实线是代价 \(f(x)=0.08x^2+0.8\sin 1.5x\)（有三个局部最小），琥珀色虚线是平滑后的 \(f_\sigma\)。拖动底部的橙色手柄移动均值 \(\mu\)。每个采样点在曲线上画成一个圆点，半径表示它的权重；竖线是权重本身。底部的橙色箭头是 \(\mu\to\mu'\)。拖大 \(\sigma\)，\(f_\sigma\) 里的小坑会消失。
    试一试
    • 保持 \(\mu\approx 2.9\)（右边的局部最小）、\(\sigma\) 很小，按"运行"：均值纹丝不动，被局部最小困住。
    • 把 \(\sigma\) 调到 1.2 以上，再按"运行"：均值越过小山包，跑到左边的全局最小（\(x\approx-0.96\)）。
    • 在 MPPI 模式下把温度 \(\lambda\) 拖到最大：权重几乎均匀，新均值几乎不动（"有效样本数"接近 \(N\)，等于没有挑剔）。再拖到最小：只有一个点有权重，容易被噪声带跑。

    3动手玩：四种采样器与梯度的竞技场

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

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

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

    FIG 2竞技场：多峰、病态与不连续的地形
    最好代价 vs. 函数求值次数
    蓝点是本代的样本（精英或权重大的点更大、更不透明），橙色粗点是当前均值，紫色轨迹是均值的历史，紫色椭圆是当前的采样分布（1 个标准差）。"Rastrigin"有上百个局部最小，"不连续"地形里有一块高台（圆盘）把起点和终点隔开，其中 \(|x-2.4|+|y-1.6|\) 的尖点是 L1 的"V 形谷"，有限差分在高台边缘会得到巨大且误导的梯度。
    试一试
    • 在 Rastrigin 上从默认起点运行梯度下降：它很快停在最近的局部最小，再也不动。
    • 在同一地形上运行 CMA-ES（样本数默认 30）：它越过无数个小坑，找到全局最小 \((0,0)\)（最好代价低于 0.05）。若样本数太少，会怎样？
    • 切到"不连续"地形，运行 MPPI，把最好代价压到 0.1 以下，而梯度下降做不到。再试 CEM：默认设置下它的方差很快塌缩，停在半路（误区 3），要把样本数和 \(\sigma\) 调大才行。
    核心洞见

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

    4再看数学

    提示：把鼠标悬停在公式中带底色的符号上，FIG 1 中对应的元素会被高亮（权重、新均值、平滑函数）。

    平滑函数的梯度，用采样估计

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

    $$ \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)\) 不改变期望，却大幅降低方差（这叫基线）。

    加权平均：CEM 与 MPPI

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

    $$ \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\) 在样本云内变化不大时

    $$ \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 散度最小）。

    CMA-ES 一瞥

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

    $$ \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 教程的默认值）。

    5机器人中的它：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，越不透明权重越大（红色表示撞到了），琥珀色粗线是加权平均后的计划。拖动目标或障碍物，计划会实时重新规划。

    FIG 3MPPI：采样 rollout，加权平均出计划
    每个控制周期（0.1 s）用 \(K\) 条 rollout 做一次 MPPI 更新（视野 \(H=25\) 步 = 2.5 s）。代价：到目标的距离平方 + 对速度的轻微惩罚 + 撞到障碍物的惩罚（0/1 不连续，膨胀 0.25 m）。温度以"代价标准差的倍数"给出，所以不用随问题改量纲。红色带圈的点是碰撞发生的位置。
    • 按"开始"，让机器人不碰任何障碍物地到达目标（距离 0.4 以内）。
    • 机器人运动途中，把一个障碍物拖到它的前方：看计划如何实时绕开。
    • 把样本数 \(K\) 降到 8：轨迹变得抖动，更容易撞到障碍物。样本越多，计划越稳。

    没有免费午餐：维数的代价

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

    FIG 4无梯度的价格：求值次数随维度增长
    双对数坐标，每个点是一次真正跑出来的结果（(1+1)-ES 取 3 个随机种子的中位数）。灰色虚线是斜率为 1 的参考线：有限差分和随机采样的开销都随 \(d\) 线性增长，只有能拿到梯度（比如自动微分）时才与维度无关。条件数 \(\kappa\) 越大，三者都变慢。
    • 按"运行"，再把条件数 \(\kappa\) 拖到 100：三条曲线都上移，但斜率不变。
    真实系统里

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

    6常见误区

    误区 1：低估样本数与维度的关系

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

    误区 2：温度 \(\lambda\) 与代价的尺度脱节

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

    误区 3：CEM 的方差塌缩

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

    误区 4：用有噪声的代价却当成确定的

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

    7小练习

    1. 增大采样分布的标准差 \(\sigma\)，对所优化的"平滑函数" \(f_\sigma\) 有什么影响？
    \(f_\sigma\) 是 \(f\) 与高斯核的卷积：窄坑（比 \(\sigma\) 窄的特征）被平均掉，宽的盆地保留，但因为是平均，极小点位置也有偏移。这就是 FIG 1 里"拖大 \(\sigma\) 就能逃出局部最小"的原因。
    2. MPPI 的权重 \(w_i=\exp(-(S_i-S_{\min})/\lambda)\)。当 \(\lambda\to\infty\) 时，更新规则变成什么？
    \(\lambda\to\infty\) 时所有 \(e^{-(\cdot)/\lambda}\to1\)，权重相等，没有任何挑剔，新均值只是随机噪声的平均，期望上不动。\(\lambda\to0\) 才是"只取最好的一个"（硬 min）。
    3. CEM 每代采样 \(N=80\) 个点，精英比例 \(\rho=0.25\)。新的均值由多少个点算出？
    \(\rho N=0.25\times80=20\)：只用代价最低的 20 个点的均值（和协方差）更新分布，其余 60 个点只起"排名"的作用。
    4. 对 \(d=100\) 维的函数，用中心有限差分算一次完整梯度，需要多少次函数求值？
    每个坐标需要 \(f(\x+h\mathbf e_i)\) 和 \(f(\x-h\mathbf e_i)\) 两次求值，共 \(2d=200\)（前向差分是 \(d+1=101\)）。自动微分的反向模式则只需约 3 次函数求值的时间，与 \(d\) 无关，这就是"有梯度"的巨大价值。
    5. 为什么 MPPI 可以直接使用"碰到障碍物就罚一个大数"这样的不连续代价？
    采样 + 加权平均只用代价的值。带碰撞的 rollout 代价高，\(\exp(-S/\lambda)\) 把它们的权重压得很低，等价于计划被推向无碰撞的方向。（"平滑"是隐式发生的：平均本身就是对 \(f\) 的平滑。）

    8延伸阅读