基于图的随机Power-UCT：基于幂均值估计的蒙特卡洛图搜索

# 基于幂均值估计的蒙特卡洛图搜索

来源：https://arxiv.org/html/2609.19956

Tung Tran  
所属机构：信息通信技术学院  
所属机构：河内科技大学  
所属机构：越南河内  
邮箱：[Tung\.td235240@sis\.hust\.edu\.vn](mailto:)  

Viet Bao Mai  
所属机构：信息通信技术学院  
所属机构：河内科技大学  
所属机构：越南河内  
邮箱：[bao\.MV225474@sis\.hust\.edu\.vn](mailto:)  

Hoang Ta  
所属机构：信息通信技术学院  
所属机构：河内科技大学  
所属机构：越南河内  
邮箱：[hoang\.taduy@hust\.edu\.vn](mailto:)  

Tuan Dam  
所属机构：信息通信技术学院  
所属机构：河内科技大学  
所属机构：越南河内  
邮箱：[tuan\.dam@hust\.edu\.vn](mailto:)  

###### 摘要
基于树的蒙特卡洛树搜索 (MCTS) 在通过不同轨迹到达同一状态时会重复存储该状态，这在随机马尔可夫决策过程中会浪费模拟资源。我们引入了**基于图的随机幂-UCT (GS-Power-UCT)**，它共享在相同规划深度达到的状态，同时为在不同深度达到的状态保持独立的价值估计。此设计适用于一般随机马尔可夫决策过程，包括存在循环的问题。我们证明，对于固定的规划时界，根节点估计以 $O(n^{-1/2})$ 的速率收敛到有限时界价值，这与基于树的随机幂-UCT 相匹配，同时在共享状态间重用样本。我们还研究了两种全状态变体：GS-Power-UCT-F（为每个物理状态存储一个节点以增加样本共享，但可能混合不同剩余时界的价值），以及 GS-Power-UCT-F+（使用自适应时界来控制此偏差）。后者在经验跨深度差距消失时，收敛到根状态 $s_0$ 处的最优无限时界折扣价值 $V^\star(s_0)$。在随机规划基准测试上的实验表明，与基于树和基于图的基线相比，样本效率得到了提升。

## 1 引言
蒙特卡洛树搜索 (MCTS) [3 (https://arxiv.org/html/2609.19956#bib.bib3), 2 (https://arxiv.org/html/2609.19956#bib.bib2)] 是一类广泛使用的在线规划算法，它将蒙特卡洛采样与前向树搜索相结合。MCTS 的成功得益于受多臂老虎机 (MAB) 文献启发的自适应探索策略，其中最著名的是树上置信上界 (UCT) 算法 [7 (https://arxiv.org/html/2609.19956#bib.bib7)]。近期，将 MCTS 与深度学习相结合的进展 [12 (https://arxiv.org/html/2609.19956#bib.bib12), 13 (https://arxiv.org/html/2609.19956#bib.bib13), 9 (https://arxiv.org/html/2609.19956#bib.bib9)] 已在复杂决策问题中实现了突破。

尽管取得了这些成功，基于树的 MCTS 仍存在两个基本局限性。首先，由于 Shah 等人 [10] (https://arxiv.org/html/2609.19956#bib.bib10) 指出的问题，UCT 中对数探索奖励的理论分析尚不完整，这导致了具有多项式奖励的固定深度 MCTS (Fixed-Depth-MCTS) [11 (https://arxiv.org/html/2609.19956#bib.bib11)] 的发展。其次，也是与本工作更相关的一点，基于树的 MCTS 无法识别通过多条轨迹可达的状态。当状态 $s$ 可通过两个不同的动作序列到达时，它在搜索树中被表示为两个独立的节点，导致了冗余探索和计算预算的次优利用。[Leurent and Maillard [8]](https://arxiv.org/html/2609.19956#bib.bib8) 通过提出蒙特卡洛图搜索 (MCGS) 来解决第二个局限性，该算法将相同状态合并为有向图中的单个节点。他们证明，这种合并可以将有效分支因子从 $\kappa$ (树) 降低到 $\kappa_\infty \leq \kappa$ (图)，从而改进了遗憾界。然而，他们的理论分析仅限于*确定性*马尔可夫决策过程 (MDP) 和基于不确定性的乐观 (OFU) 规划风格，其向随机马尔可夫决策过程的扩展纯粹是经验性的。

另一方面，随机幂-UCT 算法 [5 (https://arxiv.org/html/2609.19956#bib.bib5)] 通过引入具有多项式探索奖励的幂均值价值估计来解决第一个局限性，为随机 MCTS 建立了根节点价值估计的 $O(n^{-1/2})$ 收敛速率。

##### 贡献。我们做出以下贡献：
1. 我们引入了**基于图的随机幂-UCT** (GS-Power-UCT)，它结合了幂均值备份、多项式探索奖励和深度增强图搜索。通过将节点键控为 $(s, h)$，对于任何随机马尔可夫决策过程（包括具有循环的马尔可夫决策过程），搜索图从构造上就是一个有向无环图 (DAG)。
2. 我们证明 GS-Power-UCT 在深度增强图上保留了 Stochastic-Power-UCT 的 $(\alpha, \beta)$-集中性（定义 1 (https://arxiv.org/html/2609.19956#Thmdefinition1)）保证。关键步骤是引理 1 (https://arxiv.org/html/2609.19956#Thmlemma1) 中的一个广义图 Q-集中性引理，该引理处理了来自多个父节点聚合访问次数的子节点估计。这得出了截断价值 $\widetilde{V}(s_0, 0)$ 的根期望误差 $O(n^{-1/2})$；参见定理 6 (https://arxiv.org/html/2609.19956#Thmtheorem6) 和定理 1 (https://arxiv.org/html/2609.19956#Thmtheorem1)。
3. 我们分析了跨深度合并状态的成本。命题 3 (https://arxiv.org/html/2609.19956#Thmproposition3) 表明，朴素的全状态合并可能引入不可约的跨深度偏差。对于实用的全合并变体，我们在定理 3 (https://arxiv.org/html/2609.19956#Thmtheorem3) 中给出了受控偏差界，并在定理 4 (https://arxiv.org/html/2609.19956#Thmtheorem4) 中给出了 GS-Power-UCT-F+ 的自适应时界保证，当经验跨深度差距消失时，它收敛到 $V^\star(s_0)$。
4. 我们量化了深度增强图搜索的样本共享效应。对于固定收集的模拟轨迹，图表示是通过识别相等的 $(s, h)$ 对，由展开的树表示得到的商图。定理 2 (https://arxiv.org/html/2609.19956#Thmtheorem2) 给出了一个确定性样本共享恒等式，并表明在相同的递归证明框架下，聚合不会扩大相应的同轨迹证明界。这是一种表示层面的比较，而非声称对独立运行的树 MCTS 算法具有算法层面的优越性。

## 2 预备知识
### 2.1 马尔可夫决策过程
我们考虑一个离散时间折扣马尔可夫决策过程 $\mathcal{M}=\langle\mathcal{S},\mathcal{A},R,P,\gamma\rangle$，其中 $\mathcal{S}$ 是状态空间，$\mathcal{A}_s \subseteq \mathcal{A}$ 是在状态 $s$ 处的非空允许动作集，令 $K \triangleq \max_{s} |\mathcal{A}_{s}| < \infty$。在 $(s, a)$ 处的模拟器响应包括一个从 $P(\cdot \mid s, a)$ 中抽取的后继状态和一个在 $[0, R_{\max}]$ 范围内的奖励；$R(s,a,s')$ 表示给定 $s'$ 时的条件均值。折扣因子为 $\gamma \in [0, 1)$。最优价值函数满足贝尔曼最优方程：
$$V^\star(s)=\max_{a\in\mathcal{A}_{s}}Q^\star(s,a),\quad Q^\star(s,a)=\sum_{s'}P(s'|s,a)\left[R(s,a,s')+\gamma V^\star(s')\right].$$
(1)

### 2.2 基于幂均值价值备份的 MCTS
给定规划时界 $H$ 和价值为 $V_0$ 的推演策略 $\pi_0$，我们递归定义 $\widetilde{V}(s_H)=V_0(s_H)$，对于 $h \leq H-1$：
$$\widetilde{Q}(s_h,a)=r(s_h,a)+\gamma\sum_{s_{h+1}}P(s_{h+1}|s_h,a)\widetilde{V}(s_{h+1}),\quad \widetilde{V}(s_h)=\max_{a\in\mathcal{A}_{s_h}}\widetilde{Q}(s_h,a),$$
(2)
其中 $r(s_h,a)$ 是期望即时奖励；截断误差满足 $\|Q^\star(s_0,a)-\widetilde{Q}(s_0,a)\| \leq \gamma^H \|V^\star-V_0\|_\infty$。等价地，使用贝尔曼最优算子 $(\mathcal{B}V)(s) \triangleq \max_{a\in\mathcal{A}_{s}}\sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma V(s')]$，$V^\star$ 是 $\mathcal{B}$ 的唯一不动点，深度 $h$ 截断价值为 $\widetilde{V}(s,h)=(\mathcal{B}^{H-h}V_0)(s)$。在 $t$ 条轨迹后，内部节点 $s_h$ 处的*幂均值价值估计*为
$$\widehat{V}_t(s_h)=\left(\sum_{a\in\mathcal{A}_{s_h}}\frac{T_{s_h,a}(t)}{t}\left(\widehat{Q}_{T_{s_h,a}(t)}(s_h,a)\right)^p\right)^{1/p},$$
(3)
其中 $p \in [1, +\infty)$ 且 $T_{s_h,a}(t)$ 是访问 $(s_h, a)$ 的次数。

### 2.3 集中性框架
遵循 Shah 等人 [11] (https://arxiv.org/html/2609.19956#bib.bib11) 和 Dam 等人 [5] (https://arxiv.org/html/2609.19956#bib.bib5)，我们使用以下多项式集中性的概念。

###### 定义 1（$(\alpha, \beta)$-集中性）
估计量序列 $(\widehat{V}_{n})_{n\geq 1}$ 以速率 $(\alpha, \beta)$ 集中到某个极限 $V$，如果存在常数 $c > 0$，使得：
$$\forall n \geq 1,\;\forall\varepsilon>0:\quad\mathbb{P}\left(\|\widehat{V}_{n}-V\|>\varepsilon\right)\leq c\,n^{-\alpha}\varepsilon^{-\beta}.$$
(4)
我们记作 $\widehat{V}_{n} \xrightarrow[n\to\infty]{\alpha,\beta} V$。

## 3 基于图的随机幂-UCT
基于图的马尔可夫决策过程规划效率取决于用于合并轨迹的机制。我们介绍 GS-Power-UCT，该算法旨在平衡**估计精度**（保持价值一致性）和**样本效率**（最大化状态重用）。我们通过状态映射函数 $\phi(s,h)$ 形式化这种平衡，该函数定义了物理状态 $s$ 和轨迹深度 $h$ 在搜索图 $\mathcal{G}_{n}$ 中的索引方式，使我们能在理论上一致的模型和计算上高通量的变体之间进行切换。

### 3.1 搜索图构建
我们维护一个图 $\mathcal{G}_{n}=(\mathcal{N}_{n},\mathcal{E}_{n})$，其中每个节点 $v \in \mathcal{N}_{n}$ 表示一个聚合状态 $v=\phi(s,h)$，$\phi$ 的选择决定了搜索空间的拓扑结构。*深度增强映射* $\phi(s,h)=(s,h)$ 区分了相同物理状态在不同深度的情况，是有限时界马尔可夫决策过程的标准形式，因为状态的价值本质上是相对于剩余时界 $H-h$ 非平稳的；它确保 $\mathcal{G}_{n}$ 从构造上就是一个有向无环图（命题 1 (https://arxiv.org/html/2609.19956#Thmproposition1)），消除了由深度截断引起的偏差，并合并了所有相同深度的置换（这在结构化马尔可夫决策过程中最常见）。*全状态映射* $\phi(s,h)=s$ 则合并所有对物理状态的访问，无论其深度如何，这极大地减小了图的大小，并最大化跨轨迹各阶段的信息共享；当环境是循环的，或者 $V_0$ 是一个强有力的估计器时，这种放宽尤其有效，使得时界引起的偏差可以忽略不计。

### 3.2 分析合并权衡
从深度增强到全状态合并的转变涉及一个基本权衡：前者保证收敛到最优截断价值，而后者引入了我们现在要量化的跨深度偏差 $\Delta_{\text{cross}}$。对于每个物理状态 $s$，令 $\mathcal{D}(s)=\{h:s \text{ 在深度 } h \text{ 被访问}\}$，其中 $h_{\min}(s)=\min \mathcal{D}(s)$ 且 $h_{\max}(s)=\max \mathcal{D}(s)$。状态 $s$ 处的跨深度差距为
$$\delta(s)=\max_{h_{1},h_{2}\in\mathcal{D}(s)}\left\|\widetilde{V}(s,h_{1})-\widetilde{V}(s,h_{2})\right\|.$$
(5)
由于 $\widetilde{V}(s,h)=(\mathcal{B}^{H-h}V_0)(s)$ 且 $\mathcal{B}$ 在 $\|\cdot\|_\infty$ 下是一个 $\gamma$-压缩，
$$\delta(s)\leq\frac{\gamma^{H-h_{\max}(s)}-\gamma^{H-h_{\min}(s)}}{1-\gamma}\,\|\mathcal{B}V_{0}-V_{0}\|_{\infty}\leq\frac{(1+\gamma)\bigl(\gamma^{H-h_{\max}(s)}-\gamma^{H-h_{\min}(s)}\bigr)}{1-\gamma}\,\|V^{\star}-V_{0}\|_{\infty},$$
(6)
其中第二种形式使用了 $\|\mathcal{B}V_{0}-V_{0}\|_{\infty}\leq(1+\gamma)\|V^{\star}-V_{0}\|_{\infty}$。全局跨深度差距为 $\Delta_{\text{cross}}=\max_{s\in\mathcal{G}}\delta(s)$。因此，当推演价值的贝尔曼残差很小、相关深度接近，或者所有剩余时界 $H-h$ 都很大时，全状态合并是可靠的；如果每个物理状态都只在单一深度被访问，则 $\delta(s)=0$。

为了解决这个问题，我们使用*深度增强节点*：图 $\mathcal{G}_{n}=(\mathcal{N}_{n},\mathcal{E}_{n})$ 包含节点 $(s,h) \in \mathcal{S} \times \{0,\ldots,H\}$，其中 $s$ 是物理状态，$h$ 是节点被创建时的轨迹深度。形式化地，$\mathcal{N}_{n} \subseteq \mathcal{S} \times \{0,\ldots,H\}$ 收集了迄今为止发现的深度增强节点，$\mathcal{E}_{n}$ 包含观测到的转移 $((s,h),a,(s',h+1))$，其中 $(s,h), (s',h+1) \in \mathcal{N}_{n}$ 且 $a \in \mathcal{A}_{s}$。由于每条边严格增加深度坐标，$\mathcal{G}_{n}$ 从构造上就是一个有向无环图。关键是，到达相同物理状态 $s$ 且在相同深度 $h$ 的两条轨迹*被合并*——它们共享节点 $(s,h)$ 及其价值估计 $\widehat{V}(s,h)$——这捕捉了基于图规划的关键优势，同时确保每个节点都有一个明确的价值目标 $\widetilde{V}(s_h)$ 来自 (2 (https://arxiv.org/html/2609.19956#S2.E2))。

###### 命题 1（构造即 DAG）
GS-Power-UCT 维护的搜索图 $\mathcal{G}_{n}$ 对于任何马尔可夫决策过程（包括具有循环转移的）都是一个有向无环图；每条边连接 $(s,h)$ 到 $(s',h+1)$，严格增加深度坐标，因此不可能存在有向环。

完全展开的内部节点 $\mathring{\mathcal{G}}_{n}$ 和尚未展开的边界节点 $\partial\mathcal{G}_{n}$ 划分了 $\mathcal{N}_{n}$。对于每个 $(s,h) \in \mathcal{N}_{n}$，我们维护全局访问次数 $T_{s,h}(n)$（对 $(s,h)$ 的总访问次数），$T_{s,h,a}(n)$（在 $(s,h)$ 处采取动作 $a$ 的次数）。