On-line Policy Improvement using Monte-Carlo Search

• ArXiv URL: http://arxiv.org/abs/2501.05407v1

• 作者: Gregory R. Galperin; G. Tesauro

• 发布机构: IBM; MIT

---

TL;DR

本文提出了一种在线策略改进算法，该算法通过蒙特卡洛搜索（Monte-Carlo search）实时评估当前状态下所有可能动作的长期期望回报，并选择最优动作，从而显著提升一个已有“基础策略”的表现。

关键定义

• 在线策略改进 (On-line Policy Improvement)：与需要大量离线训练的传统方法不同，这是一种在决策时刻实时计算出更优策略的技术。它不更新模型的永久参数，而是在当前状态下，通过搜索找到比基础策略更好的单步动作。
• 蒙特卡洛搜索 (Monte-Carlo Search)：本文中指一种统计评估方法。具体而言，为了评估在状态 \(x\) 下采取动作 \(a\) 的价值，算法会从该点开始，使用一个固定的“基础策略”\(P\) 进行多次模拟（称为“rollout”），直到模拟结束。通过对所有模拟结果的最终奖励取平均，来估计动作 \(a\) 的期望价值 \(V_P(x,a)\)。
• 基础策略 (Base Policy)：一个预先给定的、用于在蒙特卡洛模拟中做出决策的策略。该策略的性能可以是任意的，从随机策略到专家级策略均可。本文方法的目标就是在线改进这个基础策略。
• Rollout：在西洋双陆棋（backgammon）领域，这个术语指代从一个特定局面开始，使用固定策略一直模拟到游戏结束的单次蒙特卡洛试验。
• 截断Rollout (Truncated Rollout)：一种为提高效率而设计的变体。模拟过程不会进行到游戏结束，而是在执行有限步数后提前终止，并使用一个价值函数（如基础策略的神经网络）来估计当前局面的价值，作为该次模拟的最终回报。

相关工作

传统的策略迭代（policy iteration）算法，无论是基于动态规划的全状态空间扫描，还是基于强化学习的轨迹训练，通常都是一个计算量巨大的离线过程。例如，使用非线性函数逼近器（如神经网络）的强化学习方法需要对大量轨迹进行长时间的离线训练才能达到满意的性能。

这些方法的共同瓶颈在于，它们的速度太慢，无法在实时决策中计算出改进的策略。本文旨在解决这一问题，即开发一种能够在线（on-line）、实时（real-time）地对一个已有策略进行改进的算法，从而在当前决策点立即做出更好的选择。

本文方法

本文提出的在线策略改进算法本质上是执行单步的策略迭代，但这一步是在决策的当下通过蒙特卡洛搜索完成的。

核心算法

对于一个给定的当前状态 \(x\) 和一个基础策略 \(P\)，算法的执行步骤如下：

1. 动作评估：对每一个合法的动作 \(a\)，算法通过蒙特卡洛模拟来估计其价值 \(V_P(x, a)\)，即在状态 \(x\) 执行动作 \(a\) 后，后续所有步骤都遵循基础策略 \(P\) 所能带来的长期期望回报。
2. 模拟过程：为了估计 \(V_P(x, a)\)，算法会进行大量的模拟试验（rollouts）。每一次试验都从执行动作 \(a\) 后的新状态开始，然后使用基础策略 \(P\) 来选择后续的动作，直到游戏结束。
3. 价值计算：将所有从 \((x, a)\) 出发的模拟试验所获得的最终奖励（例如，游戏胜负的得分）进行平均，得到对 \(V_P(x, a)\) 的统计估计。

4. 策略改进：算法选择具有最高估计值的动作作为改进策略 \(P'\) 在状态 \(x\) 的决策：

   \[P^{\prime}(x)=\arg\max_{a}V_{P}(x,a)\]

这就在当前状态 \(x\) 实现了一次实时的策略改进。

创新点

• 在线决策优化：与传统的离线训练模式根本不同，该方法将策略改进转化为一个针对当前状态的实时搜索问题。它不是学习一个全局更优的策略函数，而是在每一步决策时即时找到一个更优的动作。
• 通用性：该方法可以作用于任何形式、任何水平的基础策略 \(P\)，无论是随机策略还是专家级网络，都能在其基础上进行提升。
• 高度并行性：各个蒙特卡洛模拟试验是相互独立的，因此该算法极易并行化，能够利用并行计算硬件（如文中的IBM SP1/SP2超级计算机）大幅缩短决策时间，从而实现实时应用。

效率优化

为了应对巨大的计算需求，本文采用了两种关键的效率优化技术：

1. 并行计算：如上所述，独立的模拟试验可以被分配到多个处理器上同时运行，通信开销极小，并行效率很高。
2. 统计剪枝 (Statistical Pruning)：在模拟过程中持续监控各个候选动作的统计数据。如果某个动作的估计价值显著低于当前最优动作（超出某个置信区间），则可以提前停止对该动作的模拟，从而节省计算资源。

截断Rollout (Truncated Rollout)

对于那些基础策略本身计算就非常耗时（例如大型多层神经网络）的情况，进行完整的rollout到游戏结束是不可行的。为此，本文提出了一种“截断Rollout”的变体：

• 模拟不再进行到游戏结束，而是只向前模拟固定的几步。
• 在模拟终止时，使用基础策略自身的价值评估函数（例如神经网络的输出）来估计当前局面的期望回报，并以此作为该次试验的最终奖励。
• 这种方法有两个优点：首先，模拟路径更短；其次，由于使用的是一个实数值的评估函数而非离散的游戏结局，试验结果的方差更小。这两个因素共同作用，使得计算速度比完整rollout快一个数量级以上。

实验结论

本文通过在西洋双陆棋（backgammon）领域的实验，验证了该方法的有效性。

对弱基础策略的提升

实验使用了一些较弱的单层神经网络作为基础策略。结果显示，蒙特卡洛方法带来了巨大的性能提升。

• 游戏对战结果：如下表所示，原本表现为中级甚至初学者水平的基础策略（如 Lin-1, Lin-2），经过蒙特卡洛改进后，其表现（以 ppg，即每局游戏得分衡量）能够与强大的TD-Gammon 2.1（1-ply）相匹敌，甚至超越。

网络	基础策略性能	蒙特卡洛策略性能	蒙特卡洛CPU时间
Lin-1	-0.52 ppg	-0.01 ppg	5 秒/步
Lin-2	-0.65 ppg	-0.02 ppg	5 秒/步
Lin-3	-0.32 ppg	+0.04 ppg	10 秒/步

表1：简单线性评估器的性能对比（对战TD-Gammon 2.1 1-ply）。正值表示更优。

• 错误率降低：在包含800个局面的测试集上，通过测量每步决策的平均权益损失（equity loss），发现蒙特卡洛方法能将基础策略的错误率降低为原来的1/3到1/4，错误率降低了3-4倍。

评估器	基础策略损失	蒙特卡洛策略损失	降低比率
随机策略	0.330	0.131	2.5
Lin-1	0.040	0.0124	3.2
Lin-2	0.0665	0.0175	3.8
Lin-3	0.0291	0.00749	3.9

表2：在800个测试局面上的平均权益损失对比。损失值越小越好。

对强基础策略的提升 (截断Rollout)

对于像TD-Gammon这样强大的多层神经网络，实验采用了“截断Rollout”方法。

• 超人水平：如下表所示，即使是强大的TD-Gammon（80个隐藏单元），其基础错误率也能通过截断rollout被大幅降低（降低率高达4.5倍甚至6.6倍）。
• 性能与效率的权衡：实验显示，通过调整rollout的积极程度（thorough vs. optimistic），可以在决策质量和计算时间之间进行权衡。即便在较快的设置下（如9秒/步），所达到的性能也远超原有的基础策略。
• 结论：该方法得到的策略表现超过了TD-Gammon的2-ply版本，甚至可能达到了超越世界顶尖人类玩家的水平。

隐藏单元数	基础策略损失	截断蒙特卡洛损失	降低比率	蒙特卡洛CPU时间
10	0.0152	0.00318 (11步, thorough)	4.8	25 秒/步
		0.00433 (11步, optimistic)	3.5	9 秒/步
80	0.0120	0.00181 (7步, thorough)	6.6	65 秒/步
		0.00269 (7步, optimistic)	4.5	18 秒/步

表3：使用截断Rollout对多层神经网络的性能提升。

最终结论

• 在线蒙特卡洛搜索是一种非常有效的策略改进方法，能够将各种水平的基础策略的错误率降低80%以上。
• 实验观察到一个有趣的趋势：基础策略越强，蒙特卡洛方法带来的错误率降低比率反而越高，这可能反映了策略迭代方法的超线性收敛特性。
• 对于拥有价值评估函数的基础策略，“截断Rollout”提供了一种非常有吸引力的权衡，它能够在可接受的计算时间内，使用更强的基础模型来获得比完整rollout更好的决策质量。
• 该方法具有广泛的应用前景，适用于任何能够提供环境模拟器的自适应控制问题，例如电梯调度、作业车间调度等。