强化学习实验1：多臂老虎机问题

问题的本质

多臂老虎机问题是强化学习中最基础的问题类型。想象你面前有 k 台老虎机，每台机器拉动手臂后会给你一个随机奖励，但你不知道每台机器的奖励规律。你有有限的尝试次数（比如1000个硬币），目标是最大化总收益。

这个问题的核心难点在于探索与开发的权衡。如果你花太多时间去测试每台机器（探索），就浪费了本可以用在好机器上的机会；但如果你过早地认定某台机器最好并一直使用它（开发），可能因为前几次的运气而错过了真正最好的机器。

数学框架

在时间 n，智能体从 k 个动作中选择一个动作 a \in \mathcal{A} = \{1, \ldots, k\}，每个动作对应一个手臂。每个动作 a 都有一个真实的期望奖励，记为：

这个 q_n^*(a) 是我们想要知道但实际上不知道的量。它表示如果在时间 n 选择动作 a，平均能得到多少奖励。我们的目标就是找到使 q_n^*(a) 最大的那个动作。

图中展示了一个10臂老虎机的可能奖励分布，我们假设奖励是独立同分布的，这意味着每次拉动同一个手臂，奖励的概率分布不会随时间改变，并且每次拉动之间相互独立。这个假设简化了问题，让我们可以通过多次采样来估计真实的期望值。

估计真实期望奖励

假设到情节 n 为止，动作 a 已经被选择了 N_n(a) 次，获得的奖励序列是 r_1, \ldots, r_{N_n(a)}。最自然的估计方法是样本平均法：

这个 Q_n(a) 是我们对真实期望 q^*(a) 的估计。根据大数定律，当 N_n(a) \to \infty 时，Q_n(a) \to q^*(a)，所以这是一个无偏估计。理论上，如果我们能无限次地选择某个动作，就能精确知道它的真实期望奖励。

增量更新公式的推导

每次获得新奖励后重新计算所有奖励的平均值效率很低。假设在情节 n+1 我们选择了动作 a，观察到新奖励 r_{N_{n+1}(a)}，此时 N_{n+1}(a) = N_n(a) + 1。我们可以用旧的估计值 Q_n(a) 来递推出新的估计值。

新的估计值应该是所有奖励的平均：

注意到 \sum_{i=1}^{N_n(a)} r_i = N_n(a) \cdot Q_n(a)，代入得：

由于 N_{n+1}(a) = N_n(a) + 1，可以改写为：

化简得到增量形式：

这个公式有明确的含义：新估计 = 旧估计 + 学习率 × 预测误差。其中学习率为 \frac{1}{N_{n+1}(a)}，预测误差为 (r_{N_{n+1}(a)} - Q_n(a))。

如果新观察到的奖励比当前估计值大，就向上调整估计值；反之则向下调整。学习率随着尝试次数增加而递减，这意味着后续的新观察对估计值的影响越来越小，估计值会逐渐稳定。

对于在情节 n+1 没有被选择的动作 a'，由于没有获得新信息，它们的估计值和选择次数都保持不变：

\varepsilon-贪婪策略

纯贪婪策略（\varepsilon = 0）总是选择当前估计值最大的动作：

但这种策略的问题是可能过早地收敛到次优动作。如果某个次优动作在前几次尝试中运气好获得了较高奖励，贪婪策略会一直选择它，永远不会发现真正的最优动作。

\varepsilon-贪婪策略通过引入探索来解决这个问题。在每个时刻 n+1，策略按以下规则选择动作：

• 以概率 \varepsilon，从所有 k 个动作中均匀随机选择一个（探索）。这确保了每个动作都有机会被尝试，即使它当前的估计值不是最高的。

• 以概率 1-\varepsilon，选择当前估计值最大的动作（开发）。这利用了我们已经学到的知识来获取高奖励。

参数 \varepsilon \in [0, 1] 控制了探索和开发的平衡。\varepsilon 越大，探索越多但可能浪费在次优动作上的尝试也越多；\varepsilon 越小，开发越多但可能错过最优动作的风险也越大。当 \varepsilon = 0 时，就退化为纯贪婪策略。

Python实现与实验设计

bandit类的结构

构造函数 __init__(self, k, mu='random') 初始化一个 k 臂老虎机。参数 mu 控制每个手臂的真实平均奖励 q^*(a)。默认情况下，mu='random' 表示从标准正态分布 \mathcal{N}(0, 1) 中随机抽取 k 个值作为各手臂的真实期望奖励。这种随机初始化模拟了现实中我们不知道哪个手臂更好的情况。

方法 pull(self, eps) 执行一次手臂选择。它根据 \varepsilon-贪婪策略决定拉哪个手臂：生成一个 [0,1] 之间的随机数，如果小于 \varepsilon 就随机选择，否则选择当前估计值 Q_n(a) 最大的手臂。选择后，根据该手臂的真实分布生成一个奖励，然后用我们之前推导的增量公式更新该手臂的估计值。

方法 run(self, eps, nb_episodes) 是对 pull 的封装，连续执行 nb_episodes 次手臂拉动。这个方法内部会记录每次拉动获得的奖励，方便后续分析。

方法 reset(self) 将所有估计值 Q_n(a) 和选择次数 N_n(a) 清零，但保持手臂数量和真实期望奖励不变。这让我们可以在同一个老虎机上重复实验，而不用重新创建对象。

实验设计的逻辑

# Main part of the program
# Number of arms
k = 10
# Number of episodes for each iteration
nb_episodes = 1000
# Number of iterations for the simulation
nb_iters = 10

实验设置了 k = 10 个手臂和 1000 个情节。关键问题是：为什么要进行多次迭代（nb_iters = 10）？

因为每次实验中，手臂的真实期望奖励是随机生成的，智能体的探索过程也包含随机性。单次实验的结果可能受运气影响。比如某次实验中恰好最优手臂在前几次尝试中给出了很低的奖励，导致智能体没能及时发现它；而另一次实验中可能很快就找到了最优手臂。为了评估策略的真实性能，需要对多个不同的老虎机实例运行实验，然后对结果取平均。

初始化时创建数组 eps_01_rewards = np.zeros(nb_episodes) 来存储平均奖励。注意这不是单次实验的奖励，而是多次迭代后在每个情节位置上的平均值。

# Array to store the average rewards as a function of the episodes
eps_01_rewards = np.zeros(nb_episodes)

主循环 for i in range(iters) 中，每次迭代都创建一个新的 bandit(k) 实例，这意味着每次迭代都有一组新的随机真实期望奖励。然后调用 eps_1.run(0.1, nb_episodes) 执行 1000 次情节，参数 \varepsilon = 0.1 表示 10\% 的时间进行随机探索。

# Run experiments
for i in range(iters):
# Initialize bandits
eps_1 = bandit(k)

# Run experiments
eps_1.run(0.1, nb_episodes)
# Update long-term averages among iterations
eps_1_rewards = eps_1_rewards + (eps_1.reward - eps_1_rewards) / (i + 1)

这里 eps_1.reward 是一个长度为 1000 的数组，存储了本次迭代中每个情节获得的奖励。这行代码的含义是对每个情节位置，计算该位置上所有迭代的奖励的增量平均。具体来说，对于第 t 个情节：

其中 \bar{R}_t^{(i)} 是前 i 次迭代在第 t 个情节的平均奖励，R_t^{(i+1)} 是第 i+1 次迭代在第 t 个情节获得的奖励。这个公式和我们之前推导的动作价值增量更新公式形式完全一致，只是这里是对不同迭代的奖励取平均，而之前是对同一个动作的多次奖励取平均。

然后我们可视化结果：

plt.figure(figsize=(14,8))
plt.plot(eps_1_rewards, label="$\epsilon=0.1$")
plt.legend(bbox_to_anchor=(0.6, 0.5))
plt.xlabel("Episode")
plt.ylabel("Average_reward")
plt.title("Average_rewards_evaluated_over_" + str(nb_iters)
+ "_iterations")
plt.show()

横轴是情节编号（1 到 1000），纵轴是在该情节位置上所有 10 次迭代的平均奖励。这条曲线反映了策略的学习过程：开始时智能体对各手臂了解很少，获得的奖励较低且波动大；随着尝试次数增加，智能体逐渐找到较好的手臂，平均奖励趋于稳定并接近最优手臂的真实期望值。

实验部分：\varepsilon-贪婪策略的性能评估

实验一：基础性能评估

实验的第一步是实现主程序来评估 \varepsilon-贪婪策略在不同情节上获得的平均奖励。程序的核心逻辑是创建一个 k = 10 臂的老虎机，使用 \varepsilon = 0.1 的策略运行 1000 个情节，并且重复这个过程多次迭代来消除随机性的影响。每次迭代都会创建一个新的老虎机实例，这意味着手臂的真实期望奖励 q^*(a) 会重新从标准正态分布中采样，模拟了不同的问题实例。

迭代次数对结果稳定性的影响

第二个要求是比较 10、100 和 1000 次迭代的结果。迭代次数本质上决定了我们对策略性能估计的精度。当我们运行单次实验时，获得的平均奖励曲线包含了大量的随机波动，这些波动来自两个层面：一是老虎机本身的随机性（真实期望奖励的随机初始化以及每次拉动手臂时奖励的随机性），二是智能体探索过程的随机性（\varepsilon-贪婪策略中随机选择手臂的部分）。

情节数量对学习过程的影响

第三个要求是将情节数从 1000 增加到 2000、5000 和 10000，并评论结果。情节数量直接决定了智能体有多少次机会来学习最优策略。

多策略对比实验设计

第四部分要求创建三个老虎机来比较不同策略。代码中使用 eps_1.mu.copy() 将第一个老虎机的真实期望奖励复制给其他两个老虎机。这一步操作至关重要。

实验对照的公平性

如果三个老虎机的真实期望奖励向量 \mu 不同，它们实际上面对的是三个完全不同的问题。假设第一个老虎机的 \mu 是 [1.5, 0.2, -0.1, 0.3, -0.5, 0.8, -0.2, 0.1, -0.3, 0.4]，最优手臂在位置 1，期望奖励是 1.5。第二个老虎机的 \mu 是 [0.1, 0.15, 0.12, 0.09, 0.11, 0.14, 0.13, 0.08, 0.16, 0.10]，最优手臂在位置 9，期望奖励是 0.16。即使两个老虎机使用相同的策略，第一个老虎机的平均奖励也会远高于第二个，因为它的最优手臂本身就有更高的期望奖励。更重要的是，第二个老虎机的问题更难：所有手臂的期望奖励非常接近，智能体需要大量采样才能区分它们；而第一个老虎机中最优手臂明显优于其他手臂，容易识别。

通过让三个老虎机共享相同的 \mu 向量，我们确保了它们面对完全相同的问题：相同的最优手臂位置，相同的期望奖励分布，相同的识别难度。此时，三个老虎机平均奖励的任何差异都只能归因于策略本身的差异（\varepsilon = 0、0.01、0.1），而不是问题难度的差异。这是科学实验中的对照原则：当我们想要研究某个变量（这里是 \varepsilon 值）的影响时，必须控制其他所有变量保持不变。

三种策略的性能特征

根据1000次迭代的实验结果：

纯贪婪策略（\varepsilon = 0）完全不进行探索，每次都选择当前估计值 Q_n(a) 最大的手臂。这种策略的行为完全依赖于初期的随机经历。在最开始的几个情节中，每个手臂都会被尝试一次来初始化估计值（这取决于具体实现），之后策略就会锁定在估计值最高的那个手臂上。由于初期的估计值是基于单次或少数几次采样得到的，充满了噪声。一个期望奖励为 0.5 的手臂可能因为运气好在第一次尝试时给出了 1.2 的奖励，而真正的最优手臂（期望奖励为 1.0）可能第一次只给出了 0.3 的奖励。贪婪策略会认定前者是最优的，从此只选择它，永远不会再尝试真正的最优手臂。这就是贪婪策略的根本问题：它过早地确信了基于有限信息的判断，失去了发现更好选择的机会。从曲线上看，贪婪策略会在前期快速上升，因为它很快确定了一个手臂并反复选择，获得了该手臂的期望奖励。但这个期望奖励往往不是最优的，曲线会停滞在一个次优水平。多次迭代取平均后，贪婪策略的最终平均奖励是所有手臂期望奖励的某种加权平均，权重取决于每个手臂在初期采样中看起来最优的概率。

低探索策略（\varepsilon = 0.01）以 1\% 的概率进行随机探索。这个小概率的探索看似微不足道，但从长期来看会产生质变。虽然大部分时间智能体都在选择当前估计最优的手臂，但每 100 次选择中平均有 1 次是随机的。这意味着所有手臂都有机会被重新采样，估计值会随着时间不断更新。如果某个手臂在初期因为坏运气被低估了，后续的探索会给它重新证明自己的机会。一旦真正的最优手臂积累了足够的采样次数，它的估计值 Q_n(a^*) 会逐渐上升并超过其他手臂，智能体就会在开发阶段主要选择它。这个过程需要时间，所以低探索策略在前期的学习速度比高探索策略慢。对于 1000 个情节，探索阶段只有约 10 次机会，平均每个手臂被探索 1 次，这不足以充分学习。但当情节数增加到 10000 时，探索机会达到 100 次，每个手臂平均被探索 10 次，足以获得较准确的估计。此时低探索策略的性能会显著提升，最终平均奖励接近 0.99 \cdot q^*(a^*) + 0.01 \cdot \bar{q}，非常接近最优手臂的真实期望奖励。

高探索策略（\varepsilon = 0.1）以 10\% 的概率探索。相比低探索策略，它在相同情节数下能够对每个手臂进行多 10 倍的采样。这使得估计值的收敛速度大大加快。在 1000 个情节中，每个手臂期望被探索 10 次，根据中心极限定理，样本均值的标准误差约为 \sigma / \sqrt{10} \approx 0.32\sigma（假设奖励的标准差为 \sigma）。如果手臂之间的期望奖励差异大于这个标准误差，智能体就能可靠地识别出最优手臂。因此高探索策略的平均奖励曲线上升最快，能在较短时间内达到接近最优的水平。但代价是长期性能的损失：即使智能体已经准确识别了最优手臂，它仍然有 10\% 的时间在随机选择，这些随机选择的平均奖励是 \bar{q}，通常远低于 q^*(a^*)。最终的稳态平均奖励是

比较三条曲线可以清楚地看到探索-开发权衡的不同表现形式。贪婪策略选择了极端的开发，代价是容易陷入局部最优；高探索策略选择了较多的探索，代价是即使找到最优解也无法完全利用；低探索策略在两者之间寻找平衡，在足够长的时间尺度上能够接近最优性能。实际应用中，\varepsilon 的选择应该基于问题的特性：如果手臂之间的差异很小，需要更多探索来准确区分它们，适合较大的 \varepsilon；如果我们只有有限的情节数，也需要较大的 \varepsilon 来快速学习；如果我们追求长期最优并且有足够的时间，较小的 \varepsilon 更合适。

练习2：确定性环境下的策略评估

实验设计的改进

练习2在练习1的基础上引入了两个重要改进。第一个改进是增加了对动作选择率的追踪，这让我们不仅能看到策略获得了多少平均奖励，还能看到策略实际上在选择哪些手臂。第二个改进是使用确定性设置的平均奖励而不是随机生成，这使得实验结果更容易解释。

记录动作选择率的必要性

在练习1中，我们只关注了平均奖励这个指标。但平均奖励是一个综合性的结果，它无法告诉我们策略的具体行为。比如两个策略可能获得相同的平均奖励，但一个策略是通过频繁选择最优手臂实现的，另一个是通过在多个次优手臂之间分散选择实现的。要真正理解策略的行为，我们需要知道每个手臂被选择的频率。

为此，代码中添加了向量 eps_1_selection = np.zeros(k) 来存储每个动作的平均选择率。这是一个长度为 k 的向量，第 a 个元素记录了动作 a 在所有情节中被选择的平均次数。注意这里说的是"平均"，因为我们要对多次迭代取平均。

在每次迭代结束时，更新公式为：

这里 eps_1.k_n 是一个向量，存储了本次迭代中每个动作被选择的次数。这个更新公式和我们之前见过的增量平均公式完全相同。假设前 i 次迭代中动作 a 的平均选择次数是 \bar{N}_i(a)，第 i+1 次迭代中动作 a 被选择了 N_{i+1}(a) 次，那么新的平均选择次数是：

经过所有迭代后，eps_1_selection[a] 就表示在一次典型的实验中，动作 a 期望被选择多少次。

确定性奖励设置的作用

练习2使用 mu='sequence' 来生成老虎机，这会创建一个平均奖励从 0 到 k-1 线性增加的设置。具体来说，手臂 0 的期望奖励是 0，手臂 1 的期望奖励是 1，依此类推，手臂 k-1 的期望奖励是 k-1。对于 k=10，手臂 9 是明确的最优手臂，期望奖励为 9。

这种确定性设置与练习1中的随机设置形成对比。在随机设置下，每次迭代的最优手臂位置都可能不同，有时在位置 3，有时在位置 7。这使得结果难以解释：如果我们发现某个策略经常选择手臂 5，我们无法判断这是因为策略有偏好手臂 5 的倾向，还是因为在这些迭代中手臂 5 恰好是最优的。

使用确定性设置后，所有迭代中最优手臂都是手臂 9。如果一个策略经常选择手臂 9，我们可以明确地说它成功找到了最优手臂；如果它经常选择手臂 3，我们可以明确地说它陷入了次优解。这种清晰性使得策略行为的分析变得简单直接。

此外，sequence设置创造了一个最优手臂明显优于其他手臂的情况。手臂 9 的期望奖励是 9，而其他所有手臂的平均期望奖励是 \bar{q} = \frac{0+1+\cdots+8}{9} = 4。最优手臂的优势达到 9 - 4 = 5，这是一个很大的差距。这种设置能够清楚地展示探索的价值：如果策略能够找到手臂 9，收益会显著高于随机选择或者陷入次优手臂。

Sequence模式下的性能对比

纯贪婪策略（\varepsilon = 0）的最终平均奖励是 4.6357，这个值非常接近除最优手臂外其他手臂的平均期望奖励 4.0。这说明贪婪策略几乎完全没有找到最优手臂 9，而是在次优手臂之间徘徊。具体来看，贪婪策略在初期会依次尝试各个手臂来初始化估计值。由于奖励有随机性，某个次优手臂（比如手臂 7 或 8）可能在第一次尝试时给出了较高的奖励，贪婪策略会认定它是最优的并持续选择它。即使手臂 9 的真实期望奖励更高，由于贪婪策略不再探索，它永远不会被发现。从曲线形态看，贪婪策略快速上升到约 4.6 后完全停滞，呈现出一条几乎水平的直线。

低探索策略（\varepsilon = 0.01）的最终平均奖励是 6.7223，这比贪婪策略高出约 45\%。这个提升来自于策略有更大概率找到最优手臂 9。虽然探索率只有 1\%，但在 1000 个情节中仍有约 10 次机会探索到手臂 9。一旦手臂 9 被采样几次，它的估计值 Q_n(9) 会迅速上升并超过其他手臂，随后的开发阶段就会主要选择它。但 1\% 的探索率意味着发现最优手臂需要较长时间，从曲线看，低探索策略在整个 1000 个情节中持续缓慢上升，说明它还在学习过程中，尚未完全收敛。

高探索策略（\varepsilon = 0.1）的最终平均奖励是 8.2920，这是三种策略中最高的，接近理论最优值 9。损失仅约 8\%，这个损失主要来自于 10\% 时间的随机探索。如果策略已经准确识别了手臂 9 是最优的，那么理论上的长期平均奖励应该是：

实际获得的 8.292 略低于这个理论值，说明策略并非 100\% 确定手臂 9 是最优的，仍有小概率在开发阶段选择其他手臂。

最优手臂选择率的深入分析

动作选择率的数据更直接地揭示了策略行为。手臂 9（最优手臂）的选择次数统计如下：

贪婪策略选择手臂 9 仅 92.0 次，占总情节数的 9.2\%。这个比例极低，说明贪婪策略几乎从未找到最优手臂。92 次选择可能大部分来自初始化阶段对所有手臂的尝试，之后就再也没有选择过手臂 9。

低探索策略选择手臂 9 共 350.04 次，占 35.0\%。这是一个中等水平的选择率。在 1000 个情节中，探索阶段约有 10 次机会，每次有 1/10 的概率选中手臂 9，期望只有 1 次。但这 1 次足以让智能体发现手臂 9 的高期望奖励，随后的开发阶段就会开始选择它。350 次意味着约 35\% 的时间智能体认为手臂 9 是最优的。剩余 65\% 的时间选择了其他手臂，这部分既包括探索阶段的随机选择，也包括开发阶段因估计不准确而选择的次优手臂。

高探索策略选择手臂 9 共 810.88 次，占 81.1\%。这是一个极高的选择率，说明高探索策略以超过 80\% 的时间在利用最优手臂。具体分析这 81.1\%：其中 10\% 的时间是探索阶段，此时每个手臂被选择的概率是 1/10，手臂 9 在探索阶段被选择的期望次数是 1000 \times 0.1 \times 0.1 = 10 次。剩余的约 801 次都来自开发阶段，这意味着在 90\% 的开发时间中，智能体选择的是手臂 9。计算比例：801 / (1000 \times 0.9) = 89\%。也就是说，在应该开发的情况下，有 89\% 的时间智能体正确地选择了手臂 9，只有 11\% 的时间因为估计误差选择了其他手臂。这个 89\% 的准确率已经非常高了。

对比三个策略的选择率，我们发现一个清晰的规律：探索率越高，找到最优手臂的概率越高。贪婪策略的 9.2\% 几乎等于随机猜中的概率（1/10 = 10\%），说明它完全没有学习能力。低探索策略的 35\% 是随机的 3.5 倍，有一定学习能力但不充分。高探索策略的 81\% 是随机的 8 倍以上，展现了强大的学习能力。

Random模式与Sequence模式的对比

将sequence模式的结果与练习1中random模式的结果对比，我们可以得出关于探索价值的更深层次结论。

在random模式中，手臂的期望奖励从标准正态分布中随机抽取。假设最优手臂的期望奖励是 q^*(a^*)，所有手臂的平均期望奖励是 \bar{q} = \frac{1}{k}\sum_{a=1}^{k} q^*(a)。由于是从 \mathcal{N}(0,1) 中抽取，\bar{q} 的期望值接近 0。最优手臂相对于平均水平的优势大约是 q^*(a^*) - \bar{q} \approx 0.5。这个优势不大，因为即使是最优手臂，它的期望奖励也只是标准正态分布的一个样本，不会偏离均值太多。在这种情况下，练习1的结果显示高探索策略（\varepsilon = 0.1）的最终平均奖励是 1.3006，贪婪策略是 0.9968，相对提升约 30\%。

在sequence模式中，最优手臂（手臂 9）的期望奖励是 9，所有手臂的平均期望奖励是 4，优势达到 9 - 4 = 5。这个优势是random模式的 10 倍。在这种情况下，高探索策略的最终平均奖励是 8.2920，贪婪策略是 4.6357，相对提升约 79\%。

这个对比说明了一个重要原则：探索的价值与最优动作的优势成正比。当最优手臂明显优于其他手臂时，找到它带来的收益巨大，此时探索的重要性凸显，值得花费大量资源去寻找最优手臂。当所有手臂的价值都差不多时，找到最优手臂的额外收益有限，此时过度探索反而会浪费在随机选择上的成本，不如尽快开发一个还不错的手臂。

从公式角度看，\varepsilon-贪婪策略的长期平均奖励是：

练习3：衰减 \varepsilon-贪婪策略

固定探索率的问题

标准 \varepsilon-贪婪策略存在一个根本性缺陷。无论智能体学习到了什么程度，无论它是否已经准确识别了最优手臂，探索始终以固定的概率 \varepsilon 发生。这意味着即使在第 1000 个情节，智能体已经非常确信手臂 9 是最优的（通过数百次采样验证），它仍然会以 10\% 的概率随机选择其他明显次优的手臂。

这种持续的探索在早期是有益的，因为智能体需要信息来学习各手臂的价值。但在后期就变成了纯粹的浪费，因为智能体已经掌握了充分的知识，继续探索只会降低平均奖励。理想的策略应该在初期大量探索以快速学习，然后逐渐减少探索转向开发，最终几乎完全开发最优手臂。

衰减策略的定义

其中 n 是情节编号，\beta \in (0, 1] 控制衰减速率。性质：\varepsilon_0 = 1（初始完全探索），\varepsilon_n \to 0（最终接近贪婪）。

要从 \varepsilon = 1 降到目标值 \varepsilon_{\text{target}} 所需情节数：

• \beta 越大，衰减越快

累积探索次数对比（前1000个情节）

衰减策略的总探索量取决于 \beta。慢衰减（\beta=0.01）探索最多，快衰减（\beta=1.0）探索最少。

图中展示了 \varepsilon_n 随情节数 n 的衰减曲线，三条曲线分别对应 \beta = 0.01（蓝色）、\beta = 0.1（橙色）和 \beta = 1.0（绿色）。

蓝色曲线（\beta = 0.01）衰减最慢。它从 \varepsilon_0 = 1 开始，缓慢下降，在第 100 个情节时仍有 \varepsilon_{100} = 0.5 的探索率。这意味着前 100 个情节中，平均有一半的时间在探索。曲线呈现出一个平缓的双曲线形状，到第 1000 个情节时 \varepsilon_{1000} = 0.0909 \approx 0.1，探索率仍然不低。

橙色曲线（\beta = 0.1）衰减速度中等。在第 10 个情节时 \varepsilon_{10} = 0.5，意味着前期迅速从纯探索转向平衡状态。第 50 个情节时 \varepsilon_{50} = 0.1667，第 100 个情节时 \varepsilon_{100} = 0.0909 \approx 0.1。这种中等速度的衰减在很多问题中都是合理的选择，它在前期提供了充分的探索，在后期又能有效地开发。

绿色曲线（\beta = 1.0）衰减最快。它几乎是一个阶跃函数：在前 10 个情节内从 1 骤降到 \varepsilon_{10} = 0.0909 \approx 0.1，然后迅速趋近于零。到第 50 个情节时 \varepsilon_{50} = 0.0196 \approx 0.02，已经非常接近纯贪婪。这种快衰减策略假设问题相对简单，可以很快学会，适合于手臂差异明显且情节数有限的场景。

固定与衰减策略的全面性能对比

实验在sequence模式下运行了 1000 个情节，对 6 种策略进行了系统比较。

早期（ep100）：Decay \beta=0.1 和 \beta=1.0 学习最快，因为初期探索率接近1。Fixed \varepsilon=0.01 最慢，因为探索太少。

中期（ep500）：Decay \beta=0.1 持续领先。Fixed \varepsilon=0.1 追赶上来。Decay \beta=1.0 增速放缓（探索已经很少）。

最终（ep1000）：Decay \beta=0.1 最优。

练习4：乐观初始化的贪婪策略

核心思想的深层理解

通过给所有手臂的估计值 Q_0(a) 设置一个高于实际期望奖励的初始值，即使使用纯贪婪策略（\varepsilon = 0），智能体也会被迫探索。因为当智能体选择某个手臂后获得的真实奖励通常低于乐观初始值，该手臂的估计值会下降，导致其他未被充分尝试的手臂看起来更好，从而被选择。

初始化值选择的数学推导

Init=5.0的情况：初始时所有手臂估计值都是5.0。策略会随机选一个手臂（因为都一样），假设选了手臂1，获得奖励约1.0，更新后 Q_1(1) = \frac{5+1}{2} = 3.0。接下来会选择估计值最高的手臂，还是那些未被尝试的手臂（仍是5.0）。假设选了手臂5，获得约5.0，更新后 Q_1(5) = \frac{5+5}{2} = 5.0，估计值几乎不变。再选一个，比如手臂9，获得约9.0，更新后 Q_1(9) = \frac{5+9}{2} = 7.0。

此时的估计值排序：Q(9)=7.0 > Q(5)=5.0 > Q(1)=3.0。贪婪策略会一直选手臂9，它的估计值会逐渐收敛到真实值9.0。但问题是：手臂8、7、6可能还没被尝试，它们的估计值仍是5.0。当手臂9的估计值稳定在9.0后，贪婪策略永远不会再尝试那些估计值只有5.0的手臂。这就导致了次优的探索：某些实际不错的手臂（如手臂8，真实期望8.0）被忽略了，因为初始值5.0太低，无法吸引智能体的注意。

Init=10.0的情况：初始时所有手臂估计值都是10.0。第一次随机选手臂1，获得约1.0，更新后 Q_1(1) = \frac{10+1}{2} = 5.5。第二次选择时，其他手臂仍是10.0，所以会选另一个未尝试的，比如手臂2，获得约2.0，更新后 Q_1(2) = \frac{10+2}{2} = 6.0。这个过程会持续，因为每次选择一个手臂后，它的估计值都会降到10.0以下，而未尝试的手臂仍保持10.0，所以会被优先选择。

只有当所有手臂都被尝试过至少一次后，策略才会开始重复选择估计值最高的那个。此时手臂9的估计值约为 \frac{10+9}{2} = 9.5，是最高的，会被反复选择。随着对手臂9采样次数的增加，它的估计值会收敛到9.0。而其他手臂因为已经被尝试过并"失望"了，估计值都低于9.0，不会再被选择。这样就实现了完整的探索加准确的开发。

关键差异在于：10.0保证了所有手臂都被访问，因为任何手臂第一次被选后估计值都会降到10.0以下；而5.0只是比部分手臂的真实值高，无法保证所有手臂被访问。数学上，最优初始值应满足：

只有这样，第一轮遍历所有手臂后，最优手臂的估计值才会是最高的。

Init=15.0效率低虽然它也能保证探索所有手臂，但初始值过高导致需要更多次采样才能让估计值回落到合理水平。手臂9第一次被选获得9.0，估计值变为 \frac{15+9}{2} = 12.0，仍然很高。第二次获得9.0，变为 \frac{15+9+9}{3} = 11.0。需要大约5次采样才能降到9.5附近。

性能表现的因果分析

从曲线形态看，Optimistic Init在约100个情节后就曲线几乎水平。这说明策略已经完全收敛：所有手臂都被充分采样，最优手臂被识别，之后只是不断重复选择它。而Decay β=0.1的曲线持续到500个情节才趋于平稳，说明它花了更长时间才完成学习。这5倍的收敛时间差异，正是有目的探索（乐观初始化）和随机探索（衰减策略）的本质区别。

实践中的应用考量

乐观初始化的最大限制是需要先验知识。在实际问题中，我们如何获得这个先验？一个策略是先用少量样本做预实验。比如用100个情节运行Fixed ε=0.1策略，观察获得的最大奖励 r_{\max}，然后设置 Q_0 = r_{\max} \times 1.2。这个1.2倍的系数给了一定的乐观空间，同时又不会过于离谱。

另一个问题是非平稳环境。如果手臂的期望奖励会随时间变化（比如在推荐系统中用户兴趣会变化），乐观初始化会失效。因为初期的探索完成后，策略会锁定在当时的最优手臂上，即使后来最优手臂改变了，也不会再探索。这种情况下，衰减策略更robust，因为它始终保持微小的探索概率，能够检测到环境的变化。

从计算成本看，乐观初始化是最便宜的。它使用纯贪婪策略，不需要生成随机数，不需要计算 \varepsilon_n 的衰减值，每步只需要一个 \arg\max 操作。在大规模系统中（比如有10000个手臂的推荐系统），这个计算优势会更明显。

综合来看，乐观初始化适合的场景是：平稳环境、有先验知识或能做预实验、追求极致性能、对探索效率要求高。如果这些条件不满足，衰减策略是更安全的选择，虽然性能略低但适应性更强。

练习5：上置信界（UCB）策略

UCB策略的核心思想

\varepsilon-贪婪策略在探索阶段完全随机地选择手臂，这存在效率问题。一个已经被尝试多次且平均奖励明显低于其他手臂的手臂，继续探索它的价值很小。理想的探索应该是有针对性的：优先探索那些我们了解较少、但有可能是最优的手臂。

UCB策略通过量化对每个手臂价值估计的不确定性来实现智能探索。在情节 n+1，选择动作为：

这个选择准则包含两部分。第一部分 Q_n(a) 是利用项，代表我们当前对手臂 a 价值的最佳估计。第二部分 c\sqrt{\frac{\log n}{N_n(a)}} 是探索奖励，量化了这个估计的不确定性。参数 c > 0 控制探索的激进程度。

UCB策略的哲学是"乐观面对不确定性"。对于那些被选择次数少、估计不确定性大的手臂，策略给予额外的"信任分"，假设它们可能比当前估计值更好。这样，即使某个手臂当前的估计值 Q_n(a) 不是最高的，如果它的不确定性足够大，总分 Q_n(a) + c\sqrt{\frac{\log n}{N_n(a)}} 仍可能是最高的，从而被选择。

不确定性项的演化规律

不确定性项 U_n(a) = c\sqrt{\frac{\log n}{N_n(a)}} 同时依赖于总情节数 n 和该手臂的选择次数 N_n(a)。分析这两个因素的影响能够揭示UCB策略如何平衡探索和开发。

随总情节数 n 的变化

假设手臂 a 的选择次数 N_n(a) 固定不变，不确定性项与 \sqrt{\log n} 成正比。对数函数 \log n 随 n 单调递增，但增长速度越来越慢。其导数 \frac{d}{dn}\log n = \frac{1}{n} 趋于零，这意味着当 n 变大时，\log n 每增加一个单位需要的 n 增量越来越大。进一步，\sqrt{\log n} 的增长更加缓慢，其导数 \frac{1}{2n\sqrt{\log n}} 以 \frac{1}{n} 的速度衰减。

这种缓慢增长确保了被忽视的手臂不会被永久遗忘。即使某个手臂在初期因为运气不好获得了较低的奖励，长期未被选择后，随着 n 的增长，它的探索奖励会缓慢积累，最终大到足以让策略重新考虑它。这是UCB相比 \varepsilon-贪婪的关键优势：探索不是随机的，而是针对那些可能被低估的手臂。

随选择次数 N_n(a) 的变化

固定总情节数 n，不确定性项与 \frac{1}{\sqrt{N_n(a)}} 成反比。

当手臂 a 被选择的次数增加时，U_n(a) 按平方根速率递减。

导数小于0 说明是严格单调递减的，且速度随 N_n(a) 增加而放缓。当 N_n(a) \to \infty 时，U_n(a) \to 0。

这个衰减规律有深刻的统计学含义。根据中心极限定理，样本均值 Q_n(a) 的标准误差正比于 \frac{1}{\sqrt{N_n(a)}}。UCB的不确定性项正是对这个标准误差的体现：采样越多，估计越准确，不确定性越小。

随着某个臂被选择的次数增加，我们对该臂的真实价值估计越来越准确，不确定性下降。根据课堂笔记中的统计理论，估计值的标准误差为：

UCB策略中的不确定性项\frac{1}{\sqrt{N_n(a)}}正是对这个标准误差的反映。当我们多次采样某个臂后，对其价值的估计更加可靠，因此降低其探索优先级是合理的。

两因素的交互作用

在实际运行中，n和N_n(a)都在变化。对于任意臂a，不确定性项的演化取决于这两者的相对速度：

情形1：臂a被频繁选择

如果臂a被频繁选择，那么N_n(a)的增长速度接近n的增长速度（因为N_n(a) \approx \alpha n，其中\alpha是选择比例）。此时：

由于\frac{\log n}{n} \to 0，该臂的探索奖励快速衰减到零。这意味着如果一个臂表现好且被频繁选择，其不确定性快速降低，策略会持续利用它。

情形2：臂a长期未被选择

如果臂a长期未被选择，N_n(a)保持较小且几乎不变，而n持续增长。此时：

探索奖励缓慢但持续增加，最终会使得：

此时臂a会被重新选择。这确保了没有臂会被永久忽视，即使是初期表现不佳的臂，也有机会在后期被重新评估。

这种动态平衡使得UCB具有自适应性。在初期所有手臂的不确定性 U_n(a) 都很大，策略广泛探索；在中期表现好的手臂被多次选择，不确定性下降，策略逐渐聚焦；在后期最优手臂的不确定性接近零，策略主要利用，但仍会偶尔检查次优手臂以防止早期的误判。

统计学基础：置信界理论

UCB策略的不确定性项来源于统计学中的置信界概念。根据Hoeffding不等式，对于独立同分布的随机变量，样本均值偏离真实均值的概率可以被界定:

这意味着以高概率（至少1 - \frac{2}{n^4}），真实值q^*(a)位于置信区间：

UCB策略选择这个置信区间的上界作为决策依据。这是一种乐观策略：它假设每个手臂的真实价值接近其可能的最好情况。如果某个手臂真的很优秀但因为采样不足而被低估，它的上置信界仍然会很高，确保它有机会被重新选择。一旦被多次采样，如果它确实不如预期，置信区间会收窄，上界下降，不再被选择。这种机制保证了策略既不会错过潜在的好手臂，也不会在确认某手臂不好后继续浪费资源在它身上。

UCB策略的实验性能

从1000个情节的最终性能看，UCB策略在所有参数下都达到了接近最优的水平。UCB c=1.0 以8.9454的平均奖励排名第二，仅次于Optimistic Init=10.0的8.9512，选择最优手臂的比例达到99.39%。其他UCB变体（c=0.5, 2.0）的性能也在8.89到8.92之间，都显著优于固定探索策略。

这些结果验证了UCB的理论优势。通过智能地分配探索资源，UCB能够快速识别最优手臂并持续利用它。参数 c 的选择影响探索的激进程度，但在合理范围内（0.1到2.0），性能都很稳定。c=1.0 通常是一个平衡的选择，既提供了足够的探索以避免过早收敛，又不会因过度探索而浪费太多资源。

收敛速度对比

收敛速度分析将平均奖励达到8.0作为阈值。UCB策略展现出极快的收敛速度：UCB c=0.5 和 c=1.0 都在第49到51个情节就达到了这个阈值。这个速度远快于固定探索策略，Fixed \varepsilon=0.1 需要467个情节才达到8.0。UCB的收敛速度甚至超过了乐观初始化策略（Optimistic Init=10.0需要50个情节），与之基本持平。

这种快速收敛源于UCB的定向探索机制。\varepsilon-贪婪在探索时随机选择，可能反复尝试已经确认为次优的手臂；UCB则优先探索那些不确定性大的手臂，避免了无效探索。当某个手臂被确认为次优后（通过多次采样），它的不确定性下降，不会再被频繁选择，资源集中在真正有希望的手臂上。

参数 c 的影响

参数 c 控制探索的强度。从实验结果看，c 在0.1到2.0的范围内，最终性能都很接近（8.84到8.95），说明UCB对参数选择不敏感。但 c 的大小仍会影响学习过程的细节。

较小的 c（如0.1）意味着不确定性项的权重较低，策略更倾向于利用当前估计最优的手臂。这可能加快收敛速度，但也增加了过早收敛到次优手臂的风险。从表格看，UCB c=0.1 的收敛速度是51个情节，与 c=1.0 的51个情节基本相同，说明在sequence这种简单问题上，即使很小的探索也足够。

较大的 c（如2.0）给予不确定性项更高的权重，策略更倾向于探索。这会稍微延缓收敛（UCB c=2.0 需要58个情节达到8.0），但在更复杂的问题中可能更安全。极端情况下，如果 c \to \infty，UCB会退化为"总是选择被尝试次数最少的手臂"的策略，完全忽视估计值信息。

UCB策略的理论性质

UCB不仅在实践中表现优秀，还有严格的理论保证。在多臂老虎机问题中，一个策略的性能通常用遗憾（regret）来衡量，定义为选择最优手臂能获得的总奖励与实际获得的总奖励之差。UCB策略的遗憾是对数级别的，即经过 T 个情节后，期望遗憾为 O(\log T)。这是渐近最优的，因为已经证明任何策略的遗憾下界都是 \Omega(\log T)。

相比之下，\varepsilon-贪婪策略（固定 \varepsilon）的遗憾是线性的，为 O(T)。这是因为策略永远保持固定的探索率，持续在次优手臂上浪费资源。衰减策略如果设计得当（比如 \varepsilon_n = \frac{1}{n}），也能达到对数遗憾，但在有限时间内的常数因子通常比UCB大。

这些理论结果解释了我们观察到的性能差异。UCB在长期运行中的优势会越来越明显，因为它的遗憾增长速度远低于固定探索策略。在1000个情节的实验中，这个差异已经很显著；如果运行10000或100000个情节，差异会更加巨大。