不确定性下的乐观主义：UCB 方法

虽然像 $\epsilon$-贪婪这样的简单试探方法能确保所有行动最终都会被尝试，但它们是随机进行试探，没有考虑到对每个行动的了解程度。偶然发现好策略在复杂问题中效率低下。我们需要更明智地引导试探，趋向有前景但尚不明晰的选择。“不确定性下的乐观主义”原则提供了一种正式的方法：根据现有信息，假设一切都尽可能地好。上限置信区间（UCB）算法体现了这一原则。

多臂老虎机类比

UCB 方法起源于多臂老虎机（MABs）的更简单环境。想象一下，你面对多台老虎机（“臂”），每台机器的回报都来自一个未知的概率分布。你的目标是在一系列拉动中最大化总回报。你应该继续拉动迄今为止给出最佳平均回报的臂（采纳当前最佳），还是尝试那些可能更好但尚未被充分试探的臂（进行试探）？

UCB 提供了一个在每个时间步 $t$ 选择臂 $a$ 的标准。它依赖于两个组成部分：

1. 估计价值 ($Q_t(a)$)： 截至时间 $t$ 从臂 $a$ 获得的平均回报。这代表了当前的采纳最佳价值。
2. 不确定性奖励项： 一个量化我们对臂 $a$ 真实价值不确定程度的项。对于被拉动次数较少的臂，此项会更高。

一种流行的 UCB 算法，UCB1，选择使这两个项之和最大的行动：

$$A_t = \underset{a}{\mathrm{argmax}} \left[ Q_t(a) + c \sqrt{\frac{\ln N_t}{N_t(a)}} \right]$$

此处：

• $A_t$ 是在时间 $t$ 选择的行动。
• $Q_t(a)$ 是在 $t$ 轮后行动 $a$ 的估计价值（平均回报）。
• $N_t$ 是在时间 $t$ 之前所有臂被拉动的总次数。
• $N_t(a)$ 是在时间 $t$ 之前行动 $a$ 被拉动的次数。
• $c$ 是一个常数（$c > 0$），控制了试探的程度。较高的 $c$ 值鼓励更多的试探。

项 $\sqrt{\frac{\ln N_t}{N_t(a)}}$ 充当不确定性度量。它随总游戏次数（$N_t$）对数增长，并随着特定臂被玩次数的增加（$N_t(a)$ 增加）而减小。这确保了那些不常尝试的行动，或估计值可能不准确的行动，会获得奖励，从而使它们更有可能被选中。如果 $N_t(a) = 0$，奖励项被认为是无限的，确保每个行动至少被尝试一次（假设进行了适当的初始化）。

这种“乐观”的方法有效地平衡了试探与采纳。具有高估计价值的行动受到偏爱，但不确定性高的行动也获得机会，尤其是在早期或其潜在上限具有竞争力时。

在强化学习中应用UCB

将 UCB 从无状态老虎机环境扩展到马尔可夫决策过程（MDPs）中的序贯决策，带来了挑战，但遵循相同的核心原则。状态增加了复杂性，因为一个行动的价值取决于它所处的状态。

调整 UCB 的常见方式是在每个状态 $s$ 内将其应用于行动选择。选择规则变为：

$$A_t = \underset{a}{\mathrm{argmax}} \left[ Q(s, a) + c \sqrt{\frac{\ln N(s)}{N(s, a)}} \right]$$

此处：

• $Q(s, a)$ 是在状态 $s$ 中采取行动 $a$ 的估计价值。
• $N(s)$ 是状态 $s$ 被访问的次数计数。
• $N(s, a)$ 是在状态 $s$ 中行动 $a$ 被采取的次数计数。

这需要维护 Q 值的估计（例如，使用 Q-learning 或 SARSA 更新），同时跟踪状态访问计数 $N(s)$ 和状态-行动计数 $N(s, a)$。

Q 值、不确定性奖励项以及由此产生的 UCB 分数的演变，针对真实平均值分别为 0.6 和 0.7 的两个行动（A 和 B）。随着行动 B 更高潜力的得以展现，其 UCB 分数最终超过了 A。

挑战与调整

上述直接应用在表格化设置或具有离散、可管理状态空间的环境中效果良好。然而，在具有大型或连续状态和行动空间的环境中，它面临重大障碍：

1. 计数跟踪： 当状态连续或状态空间庞大时，维护精确计数 $N(s)$ 和 $N(s, a)$ 变得不可能。需要函数逼近技术来估计这些计数或密度模型。从密度模型或哈希函数导出的伪计数通常用作近似值（本章稍后讨论）。
2. 函数逼近： 当使用深度神经网络或其他函数逼近器来估计 $Q(s, a)$ 时，函数逼近器与 UCB 奖励项之间的相互影响需要仔细考量。简单地将奖励项添加到近似 Q 值可能在统计上不合理或不稳定。
3. 试探常数： 参数 $c$ 平衡了试探与采纳。其最优值可能取决于具体问题，并可能需要仔细调整。从老虎机问题导出的理论值可能不直接适用。
4. 非平稳性： 标准 UCB 假设奖励分布是平稳的。在强化学习中，状态-行动对的有效奖励分布可能发生变化，因为策略会演变，并到达不同的后续状态。

尽管存在这些挑战，UCB 的核心原则影响了许多高级试探方法。例如，在基于模型的强化学习中，UCB 经常用于蒙特卡洛树搜索（MCTS）等规划算法中，以引导模拟过程趋向不确定但可能有益的行动序列（如第 5 章所示）。结合函数逼近和处理广阔状态空间的改进也得到了发展，通常将 UCB 的思想与其他方法（如自举法或内在激励）结合。

总结

UCB 方法通过显式建模不确定性，提供了一种原则性的方式来管理试探与采纳的权衡。通过向估计的行动价值添加不确定性奖励项，UCB 鼓励对那些尚不清晰但可能带来高回报的行动进行试探。尽管在大规模强化学习中的直接应用需要进行调整以处理广阔的状态空间和函数逼近，但“不确定性下的乐观主义”这一思想在设计复杂序贯决策问题的试探策略时仍具有重要意义。这代表了迈向更具方向性且可能更高效地发现最优策略的一步。