多臂老虎机 UCB 算法的置信上界推导与后悔界

1. 定义多臂老虎机问题

明确 问题设定：你有 K 个老虎机（臂），每个臂 i 有一个未知的奖励分布，均值为 μ_i。你每次选择拉一个臂，获得一个奖励。目标是在 T 轮后最大化累计奖励，或者说最小化累计遗憾（后悔）。

形式化 后悔（Regret）定义为：
$$R_T = T \cdot \mu^* - \sum_{t=1}^T r_t$$
其中 μ* 是最优臂的均值，r_t 是第 t 轮获得的奖励。

理解 你无法直接知道哪个臂最好，所以需要“探索-利用”的平衡策略。UCB（Upper Confidence Bound）是一种经典方法：它给每个臂一个乐观的估计（置信上界），然后每次选择置信上界最大的臂。

2. 置信上界（UCB）的推导

引入 Hoeffding 不等式（一种概率工具）：对于独立同分布的随机变量 X₁,...,Xₙ，取值范围在 [0,1]，样本均值 X̄ 满足
$$P(\bar{X} - \mu \ge \epsilon) \le e^{-2n\epsilon^2}$$
同理对另一侧也成立。

写出 我们想构造一个上界，使得真实均值 μ_i 以高概率不超过某个值。设目前臂 i 被拉了 n_i 次，样本均值为 X̄_i。我们希望找到一个 U_i 使得
$$P(\mu_i > \overline{X}_i + U_i) \le \delta$$
其中 δ 是允许的失败概率（通常取 δ = 1/t 或 1/t^2 等）。

应用 Hoeffding 不等式：
令 ε = U_i，则有
$$P(\overline{X}_i + U_i < \mu_i) = P(\overline{X}_i - \mu_i < -U_i) \le e^{-2n_i U_i^2}$$
我们想让右边 ≤ δ，即
$$e^{-2n_i U_i^2} \le \delta \quad\Rightarrow\quad -2n_i U_i^2 \le \ln \delta \quad\Rightarrow\quad U_i \ge \sqrt{\frac{\ln(1/\delta)}{2n_i}}$$
通常取 δ = 1/t^2（或 1/t），使得随时间递减。假设在时刻 t，我们使用 δ = 1/t^2（这样所有臂的置信界可以同步），那么
$$U_i(t) = \sqrt{\frac{2\ln t}{n_i(t)}}$$
注意：这里是 2 ln t 源于 ln(1/(1/t^2)) = 2 ln t。这是常见形式。

得到 UCB 指标公式：
$$\text{UCB}_i(t) = \overline{X}_i(t) + \sqrt{\frac{2\ln t}{n_i(t)}}$$
每一轮 t，计算 每个臂的 UCB_i，然后选择 最大值的臂去拉。

3. 推导遗憾上界（后悔界）

目标 证明 UCB 算法的期望累计遗憾 E[R_T] 上界为 O(√(KT ln T)) 量级。这里给出一个简化推导。

分解 后悔可以分解为每个次优臂被选择的次数与它和最优臂均值差值的乘积。设最优臂为 a*，均值 μ*；每个次优臂 i 的差距 Δ_i = μ* - μ_i > 0。那么
$$R_T = \sum_{i: Δ_i > 0} Δ_i \cdot N_i(T)$$
其中 N_i(T) 是臂 i 在前 T 轮中被选的次数。我们需要上界 E[N_i(T)]。

关键 臂 i 被选，只可能因为它的 UCB 超过了最优臂 a* 的 UCB 或其真实均值。我们分析一个次优臂被选次数不会太多。

构造 事件：“臂 i 在时刻 t 被选” 意味着 UCB_i(t) ≥ UCB_*(t)。利用定义，可以推出该事件发生时，至少下面三个条件之一成立：

1. 最优臂的样本均值 underestimate（低于真实值太多）
2. 臂 i 的样本均值 overestimate（高于真实值太多）
3. 臂 i 的 UCB 正常但被选中（极少数情况）

利用 Hoeffding 不等式，我们可以给出每个臂被选次数的上界（详细推导较为繁琐，这里只给出结论）。大致思路是：对于固定的 s（某个整数），臂 i 被选的次数超过某个阈值后，其置信区间会变得很窄，从而它超过最优臂的概率极小。

结果 最终可以得到：
$$E[N_i(T)] \le \frac{8\ln T}{Δ_i^2} + 1 + \frac{\pi^2}{3}$$
求和得到总期望后悔：
$$E[R_T] \le \sum_{i: Δ_i>0} \left( \frac{8\ln T}{Δ_i} + Δ_i + \frac{\pi^2}{3}Δ_i \right)$$
如果所有差距 Δ_i 都很小（例如最小差距为 Δ_min），则上界大约是 O((K\ln T)/Δ_min)。进一步，如果不知道差距，可以用更精细的分析得到 O(√(KT\ln T)) 形式（利用 AM-GM 不等式）。

简化 最常用的后悔上界形式：
$$E[R_T] \le O\left(\sqrt{KT\ln T}\right)$$
这是对 UCB 算法（特别是 UCB1）的经典结论。

4. 总结推导步骤（实践指南）

准备 需要的基本工具：Hoeffding 不等式，期望线性性质，以及一些代数放缩。

1. 写出 目标后悔分解式
   $$R_T = \sum_{i=1}^K Δ_i N_i(T)$$

2. 固定 一个次优臂 i，计算 它在 T 轮中被选次数的期望上界。

   • 定义 一个阈值 u = ⌈(8\ln T)/Δ_i^2⌉。
   • 考虑 第 s 次被选（s > u）时，需要满足 UCB_i(t) ≥ UCB_*(t)。
   • 利用 概率不等式（Hoeffding 加 union bound）得到每个 s 发生的概率 ≤ 2/t^2。
   • 求和 所有 s > u 的概率，得到 ≤ π^2/3。
   • 因此 E[N_i(T)] ≤ u + 1 + π^2/3。

3. 代入 后悔分解，整理 得到：
   $$E[R_T] \le \sum_i \left( \frac{8\ln T}{Δ_i} + (1+\frac{\pi^2}{3})Δ_i \right)$$

4. 进一步 如果对 Δ_i 一无所知，可以放缩：用最大值 Δ_max = 1（假设奖励在 [0,1]），并利用柯西不等式或 Jensen 得到 O(√(KT\ln T))。更紧的界需要更精细的常数。

最终 你就获得了 UCB 算法后悔界的核心推导思路。

5. 代码模拟验证（可选）

虽然文章纯文字，但可以给出伪代码思路供读者自己实现。注意 代码块格式。

import math

def ucb1(K, T, reward_function):
    counts = [0] * K
    values = [0.0] * K
    total_regret = 0.0
    for t in range(1, T+1):
        # 每个臂至少拉一次
        if t <= K:
            arm = t-1
        else:
            ucb = [values[i] + math.sqrt(2*math.log(t)/counts[i]) for i in range(K)]
            arm = max(range(K), key=lambda i: ucb[i])
        reward = reward_function(arm)
        counts[arm] += 1
        values[arm] += (reward - values[arm]) / counts[arm]
        # 记录后悔（假设已知最优均值 mu_star）
        total_regret += mu_star - reward
    return total_regret

解释：reward_function(arm) 返回该臂的奖励，需事先定义。上述代码体现了 UCB 选择逻辑。

结束 你已经完成了从问题定义、置信上界推导到后悔界上界的完整过程。直接动手实现并观察累计遗憾的增长曲线即可验证理论。