《强化学习与最优控制》【学习笔记06】策略前展与蒙特卡洛树搜索

《强化学习与最优控制》第 2.2-2.4 节 · 策略前展

策略前展（Policy Rollout）是值空间近似最直观的实例：用一个已知的次优策略（基础策略）来估计未来费用，然后在此基础上做一步前瞻。它简单、有效、适用面广——从离散优化到棋类游戏都能用。

一、策略前展的基本思想

设定

• 有一个基础策略 $\mu$（已知的、容易计算的次优策略）
• 想要得到一个更好的策略 $\tilde{\mu}$

方法

用 $\mu$ 的费用函数 $J_\mu$ 作为 $\tilde{J}$：

$$\tilde{\mu}_k(x_k) = \arg\min_{u_k} \left[ g_k(x_k, u_k) + J_{\mu, k+1}(f_k(x_k, u_k)) \right]$$

其中 $J_{\mu, k+1}(x_{k+1})$ 是从 $x_{k+1}$ 出发，按照基础策略 $\mu$ 走到底的期望费用。

直觉

基础策略 μ：  不管三七二十一，按 μ 走到底
前展策略 μ̃：  先往前看一步，对每个候选动作 u，
              评估"做 u 之后按 μ 走到底"的费用，
              选费用最小的 u

学习心得：策略前展的本质是"站在巨人的肩膀上往前多看一步"。基础策略 $\mu$ 不需要很好——哪怕是个贪心策略都行。只要 $\mu$ 不是完全随机的，往前看一步通常就能显著提升性能。

二、策略改进保证

策略前展有一个重要的理论保证：前展策略不会比基础策略差。

$$J_{\tilde{\mu}}(x) \leq J_\mu(x), \quad \forall x$$

这是因为一步前瞻考虑了所有可能的动作（包括 $\mu$ 会选的动作），所以至少不会更差。

注意：这是有限阶段问题的结论。对于无穷阶段问题，需要额外条件（如折扣因子 $< 1$）才能保证改进。

三、在线策略前展

为什么"在线"？

计算 $J_\mu(x_{k+1})$ 需要从 $x_{k+1}$ 出发，按 $\mu$ 模拟到终点。对于：

• 确定性问题：直接按 $\mu$ 走一遍即可
• 随机问题：需要多次模拟取平均（蒙特卡洛）

关键：只在需要决策的状态上计算，不需要预先计算所有状态。

算法流程

输入：当前状态 x_k，基础策略 μ
1. 对每个候选控制 u ∈ U_k(x_k)：
   a. 计算下一状态 x_{k+1} = f_k(x_k, u)（或采样）
   b. 从 x_{k+1} 出发，按 μ 模拟到终点，计算费用 J_μ(x_{k+1})
   c. 计算总费用 g_k(x_k, u) + J_μ(x_{k+1})
2. 选择总费用最小的 u 作为 μ̃(x_k)

计算量

• 每次决策：$|U_k(x_k)|$ 次模拟（$|U_k|$ 为可用控制数）
• 每次模拟：$N - k - 1$ 步（从 $k+1$ 到终点）
• 随机问题：每条路径重复多次取平均

优点：不需要预先计算，不需要存储 $\tilde{J}$，适合大状态空间。
缺点：每次决策都需要模拟，实时性可能不够。

四、蒙特卡洛树搜索（MCTS）

MCTS 是策略前展在博弈树搜索中的精化版本。它通过选择性扩展来减少模拟次数。

四个步骤

1. 选择（Selection）：从根节点出发，用 UCT 公式选择子节点，直到到达未扩展的节点
2. 扩展（Expansion）：为选中的节点添加一个子节点
3. 模拟（Simulation）：从新节点出发，用基础策略（随机策略）走到底
4. 回传（Backpropagation）：将模拟结果沿路径回传，更新各节点的统计量

UCT 公式

选择子节点时，平衡利用（exploitation）和探索（exploration）：

$$\text{UCT} = \bar{X}_j + c \sqrt{\frac{\ln n}{n_j}}$$

• $\bar{X}_j$：子节点 $j$ 的平均费用（利用）
• $n$：父节点的访问次数
• $n_j$：子节点 $j$ 的访问次数
• $c$：探索常数

与策略前展的关系：MCTS 本质上是多步前瞻 + 策略前展，但通过 UCT 选择性地扩展有前途的分支，而不是均匀地展开所有分支。这使得它能在巨大的博弈树中找到好的动作。AlphaZero 就是 MCTS + 神经网络的组合。

五、随机策略前展

对于随机问题，$J_\mu(x_{k+1})$ 是期望费用，需要用蒙特卡洛采样来近似：

$$\tilde{J}_\mu(x_{k+1}) \approx \frac{1}{M} \sum_{m=1}^{M} \text{Cost}^{(m)}$$

其中 $\text{Cost}^{(m)}$ 是第 $m$ 次从 $x_{k+1}$ 出发按 $\mu$ 模拟的总费用。

采样次数的权衡

• $M$ 太小：估计方差大，策略可能不好
• $M$ 太大：计算量大，实时性差
• 实践中通常用 $M = 10 \sim 1000$，取决于问题

学习心得：随机策略前展的精度取决于采样次数。一个实用的技巧是：先用少量样本快速估计，如果几个候选动作的费用差距明显就足够了；如果差距不明显，再增加采样次数。

六、基于专家的策略前展

当有专家策略（expert policy）可用时，可以用专家策略作为基础策略：

$$\mu_{\text{expert}} \longrightarrow \tilde{\mu} = \text{Rollout}(\mu_{\text{expert}})$$

专家策略的来源：

• 人类专家的决策
• 已有的启发式算法
• 预训练的模型

与模仿学习的关系：基于专家的策略前展可以看作"模仿学习 + 一步前瞻优化"。模仿学习直接学专家的策略，而策略前展在专家策略的基础上进一步优化。

七、策略前展的应用实例

1. 旅行商问题（TSP）

• 基础策略：最近邻启发式（每次去最近的未访问城市）
• 前展策略：对每个候选下一城市，用最近邻走完剩余路程，选总距离最短的
• 效果：通常比纯最近邻好 5-15%

2. 棋类游戏

• 基础策略：随机走子或简单评估函数
• 前展策略：MCTS
• 效果：AlphaGo、AlphaZero 的核心组件

3. 调度问题

• 基础策略：贪心调度规则
• 前展策略：对每个候选调度决策，用贪心规则走完，选最优
• 效果：在组合优化中广泛使用

八、策略前展的局限

1. 计算量：每次决策需要多次模拟，对实时性要求高的问题可能不适用
2. 基础策略依赖：如果基础策略太差，前展策略的提升有限
3. 没有学习：策略前展是"即时"的——每次决策都重新模拟，不积累经验
4. 不适用于连续控制：当控制空间连续时，无法枚举所有候选控制

改进方向：

• 用神经网络近似 $J_\mu$，避免每次都模拟 → 这就是 DQN 的思路
• 用参数化策略代替固定基础策略 → 这就是策略梯度方法
• 多步前瞻 + 剪枝 → MCTS

九、策略前展在全书中的位置

值空间近似
├── 策略前展 ← 本篇
│   ├── 在线前展（每次实时模拟）
│   ├── MCTS（选择性树搜索）
│   └── 专家前展
├── 问题近似 ← 下一篇
│   ├── 确定性等价
│   └── 聚集
└── 参数化近似 ← 第 3 章
    └── 神经网络训练