Hoeffding 不等式与 UCB/UCT 算法解析

本篇笔记将从 Hoeffding 不等式出发，系统推导出置信上界公式，并说明其在 UCB 与 UCT 算法中的实际应用，从而揭示现代强化学习中“探索与利用”平衡的理论基础。

1. Hoeffding 不等式（统计基础）

Hoeffding 不等式提供了有界随机变量的样本均值与真实期望之间偏差的概率上界，（单边）形式如下：

其中：

：真实期望值（未知）
：样本均值（可观测）
：样本均值与真实值之间的偏差
：样本数量

该不等式说明：样本均值偏离真实值的概率，会随着样本数量增多而以指数速率下降。这为我们构造置信区间提供了严谨的理论依据。

2. 推导置信上界表达式

目标是构造一个上置信界，使得真实均值不会高于它的概率至少为：

等价于：

由 Hoeffding 不等式有：

两边取自然对数并整理：

因此我们得到置信上界：

这表示：

在置信度至少为的前提下，真实期望值不会超过该上界。

也就是说，我们有至少的把握认为：

当前观测均值与真实均值的偏差不会超过；
因此可以将该上界视为真实期望的“最乐观估计”，并在不确定条件下用于决策。

若进一步设定，即让置信度随着总尝试次数增加而提升，则有：

这就是我们后续在 UCB/UCT 中所用的探索项来源。

3. UCB 算法：多臂老虎机中的应用

UCB（Upper Confidence Bound）算法利用上述置信上界实现 探索与利用平衡，解决“选哪个动作”的核心问题。

UCB1 选择公式：

其中：

：第个臂的平均回报（利用）
：该臂被选择的次数
：总的尝试次数（全局探索量）

理解与意义：

当某个臂被选次数少时，其第二项（探索项）较大，鼓励尝试；
被尝试次数多后，探索项缩小，更依赖经验均值；
实现了“乐观估计”策略：即使初期回报不高，也因不确定性高而有尝试机会。

特性：

后悔值，已被证明近似最优；
算法简单直观，适合在线学习与强化学习等场景。

4. UCT 算法：在树结构中的推广

UCT（Upper Confidence bounds for Trees）是将 UCB 应用于 博弈搜索树（如 MCTS） 的变种，旨在选择当前子树中最优的模拟路径。

子节点选择公式：

其中：

：子节点累计回报
：子节点访问次数
：父节点访问次数
：探索强度调节参数（如 √2）

搜索过程（MCTS 四步）：

Selection：沿着 score 最大的路径向下走；
Expansion：展开当前未完全扩展的节点；
Simulation：从该节点模拟一局随机游戏；
Backpropagation：将模拟结果反向更新回路径中的所有节点。

应用场景：

UCT 是 AlphaGo 等博弈 AI 的搜索核心；
能在有限计算预算下迅速定位最优路径；
树中使用置信上界公式，有效引导模拟分布。

5. 补充说明：置信上界行为分析

✅ 为什么设？

控制整棵树中所有节点的累积错误率；
随着总尝试次数增加，置信度提高，策略更可靠。

✅ 探索项随时间增长如何变化？

虽然会缓慢增长，但节点访问次数增长更快，因此：

是 单调下降的，即探索项会收缩。

✅ 总结性直觉图示：

阶段	特征
初始探索	小，探索项大，鼓励尝试新动作
中期探索	平衡两者，选强动作同时继续试弱动作
收敛阶段	大，探索项小，主要依赖经验均值

6. 总结与对比

算法	应用场景	核心公式	特点
UCB	多臂老虎机		探索与利用平衡，后悔值最优级
UCT	蒙特卡洛树搜索		将 UCB 应用于树结构，博弈搜索核心

7. 延伸阅读与参考资料

Hoeffding, W. (1963). Probability Inequalities for Sums of Bounded Random Variables.
Auer et al. (2002). Finite-Time Analysis of the Multiarmed Bandit Problem — 提出 UCB1。
Kocsis & Szepesvári (2006). Bandit Based Monte-Carlo Planning — 提出 UCT，广泛用于 MCTS。
Silver et al. (2016). Mastering the Game of Go with Deep Neural Networks and Tree Search — AlphaGo 使用 UCT + 深度网络。

Hoeffding 不等式的置信上界推导与 UCB/UCT 算法解读