多臂老虎机问题

多臂老虎机问题（multi-armed bandit problem）研究有限反馈下的连续选择：每轮从若干选项中选一个，只观察所选项的奖励，并希望累计奖励尽可能高。这里的“臂”只是选项的名称，模型也可表示试验方案或服务策略。尝试不熟悉的选项可以获得信息，继续使用当前表现好的选项可以获取奖励，二者构成探索与利用的权衡。

本篇讨论有限个选项、平稳独立奖励的随机模型，并推导上置信界算法 UCB1。对抗环境、随时间变化的奖励和带上下文的选择属于不同模型，不能直接沿用这里的概率假设与误差界。

奖励、观察与比较基准

设共有 $K\ge 1$ 个臂。臂 i 的第 m 次奖励记为 $X_{i,m}\in [0,1]$，对每个臂奖励独立同分布，均值为未知的 ${\mu }_i$；不同臂的奖励序列也相互独立。算法在第 t 轮根据已有记录选 $I_t$，然后才看到该臂的下一次奖励，记本轮观察值为 $Y_t$。可想象各臂预先有一条尚未揭开的随机序列，每次选择就揭开其中一个新值。

记 ${\mu }_{\ast }=\underset{i}{max}{\mu }_i$、${\Delta }_i={\mu }_{\ast }-{\mu }_i\ge 0$，$N_i(T)$ 为前 T 轮选择臂 i 的次数。常用的伪遗憾为 $${\bar{R}}_T=\sum _{t=1}^T({\mu }_{\ast }-{\mu }_{I_t})=\sum _i{\Delta }_i{N}_i(T).$$ 它比较每次选择的均值与最佳固定臂的均值，不是与事后每轮都知道奖励的全知选择相比。它始终非负，但仍随算法得到的反馈而随机变化。

由于选择在本轮奖励揭开之前进行，所选臂的条件奖励均值是 ${\mu }_{I_t}$，所以 $$𝔼[{\bar{R}}_T]=T{\mu }_{\ast }-𝔼\left[\sum _{t=1}^T{Y}_t\right].$$ 一次实际运行的 $T{\mu }_{\ast }-\sum _t{Y}_t$ 可能因运气好而为负；不能把它与非负伪遗憾混作同一个量。

少量样本与乐观选择

假设两个臂 A、B 已各试一次，看到 A 返回一、B 返回零。只按样本均值选，就会继续选 A；但这两次结果没有证明 A 的真实均值更高。UCB1 在均值之外添加随观察次数缩小的探索项。

先各选每个臂一次。此后第 $t>K$ 轮，令 $N_i(t-1)$ 和 ${\hat{\mu }}_i(t-1)$ 表示该轮之前的次数和样本均值，选择使以下指数最大的臂： $$U_i(t)={\hat{\mu }}_i(t-1)+\sqrt{\frac{2\ln t}{N_i(t-1)}}.$$ 并列时可采用固定规则。第一项反映已经观察到的表现，第二项奖励较少尝试的选项。指数可能大于一，它是决策分数，不能解读成奖励概率。

沿着上面的教学反馈继续计算：第三轮两臂探索项相同，故选 A。若这次 A 返回零，第四轮 A 的均值为二分之一、次数二，B 的均值零、次数一，得 $$U_A(4)=\frac{1}{2}+\sqrt{\ln 4}\approx 1.6774,U_B(4)=\sqrt{2\ln 4}\approx \mathrm{1.6651.}$$ 第四轮仍选 A。若 A 又返回零，第五轮的两个指数变为 $$U_A(5)=\frac{1}{3}+\sqrt{\frac{2\ln 5}{3}}\approx 1.3692,U_B(5)=\sqrt{2\ln 5}\approx \mathrm{1.7941.}$$ 于是选择 B，尽管它的已观察均值仍较低。这条具体反馈路径说明探索项怎样改变下一步选择，不是对下一次随机奖励的预测。

比较的是完整指数。只比较样本均值，会作出不同的选择。

次优臂选择次数的界

UCB1 的对数级期望遗憾可由霍夫丁不等式解释。下面给出一个便于核算的界，常数不追求最紧。固定一个次优臂 i 和一个最优臂，令 $T\ge max\{K,2\}$、${\Delta }_i>0$。

先考虑预先固定的臂 j 的前 m 个奖励均值 ${\hat{\mu }}_{j,m}$。对 $r=\sqrt{2\ln t/m}$，霍夫丁不等式给出 $$Pr(|{\hat{\mu }}_{j,m}-{\mu }_j|>r)\le 2e^{-2m{r}^2}=2t^{-4}.$$ 算法的样本次数依赖过去反馈，不能把随机次数当作预先固定。解决办法是同时控制所有可能前缀：对 i 和最优臂、各自所有 $1\le m\le t$ 取联合界。这至多有 $2t$ 个事件，故任意一个置信条件失败的概率不超过 $4t^{-3}$。各事件之间不需要独立，联合界仍成立。

在这些条件都成立时，最优臂的指数至少为 ${\mu }_{\ast }$，次优臂的指数至多为 $${\mu }_i+2\sqrt{\frac{2\ln t}{N_i(t-1)}}.$$ 若其已有次数至少为 $$L_i=\lceil \frac{8\ln T}{{\Delta }_i^2}\rceil +1,$$ 则上式严格小于 ${\mu }_i+{\Delta }_i={\mu }_{\ast }$，不会再被选中。严格不等号来自额外的一，避免并列处理影响论证。

次数达到 $L_i$ 以前，这个臂至多被选 $L_i$ 次。之后若仍被选择，就必有本轮置信条件失败。因此逐轮取期望， $$𝔼[N_i(T)]\le L_i+\sum _{t=2}^{\mathrm{\infty }}4t^{-3}\le \lceil \frac{8\ln T}{{\Delta }_i^2}\rceil +3.$$ 最后一步用递减函数积分界 $\sum _{t=2}^{\mathrm{\infty }}{t}^{-3}\le {\int }_1^{\mathrm{\infty }}{x}^{-3}dx=1/2$。乘以各臂的均值差再相加，就得到期望伪遗憾的上界。原论文给出了经典的有限时间界；这里展开的前缀联合界说明适应性取样为什么没有使浓缩论证失效。

对固定正均值差，主项随 $\ln T$ 增长；差距越小，区分两臂需要的样本越多。这个结论是对随机运行取期望，不保证每一次运行都不超过该次数，也不是对任意奖励过程的保证。当界大于 T 时，还可取平凡界 $N_i(T)\le T$。

伯努利奖励的可运行实验

以下代码模拟奖励为零或一的环境。输入为非空概率序列、至少与臂数相同的整数轮数 T，以及随机种子。模拟器知道概率来生成反馈；选择指数的部分只使用观察到的累计奖励、次数和轮数。返回各臂次数、累计奖励、动作记录及伪遗憾，不改写输入。

Python 3

import math
import random

def simulate_ucb1(probabilities, rounds, seed=28):
    p = tuple(float(x) for x in probabilities)
    if not p or not all(math.isfinite(x) and 0 <= x <= 1 for x in p):
        raise ValueError("probabilities must be finite and in [0, 1]")
    k = len(p)
    if type(rounds) is not int or rounds < k:
        raise ValueError("rounds must be an integer at least k")
    rng = random.Random(seed)
    counts, totals, actions = [0] * k, [0] * k, []
    pseudo_regret = 0.0
    best_mean = max(p)
    for t in range(1, rounds + 1):
        if t <= k:
            chosen = t - 1
        else:
            chosen = max(range(k), key=lambda i:
                         totals[i] / counts[i]
                         + math.sqrt(2.0 * math.log(t) / counts[i]))
        reward = int(rng.random() < p[chosen])
        counts[chosen] += 1
        totals[chosen] += reward
        actions.append(chosen)
        pseudo_regret += best_mean - p[chosen]
    return counts, totals, actions, pseudo_regret

counts, totals, actions, regret = simulate_ucb1((0.4, 0.6), 600)
print(counts, totals, regret)

首次各试一次以后，各次数都为正，指数中的除法有定义。每轮只更新被选择的臂，次数总和始终等于已执行轮数；其样本均值由该臂实际观察值计算。扫描 K 个指数，时间为 $O(KT)$；保留动作记录时额外空间为 $O(K+T)$，若只需要最终统计可省去动作列表。

随机种子二十八的一次模拟。曲线是该次实验记录，不能代替期望界的证明。

这个实验中，每选一次 A，伪遗憾增加 $0.6-0.4=0.2$；选择 B 则不增加。因此返回的伪遗憾还应等于 $0.2N_A(600)$，可独立核对。作为边界变式，只有一个臂时每轮都选择它，伪遗憾严格为零；两臂均值相同时，无论动作怎样分配，伪遗憾也为零，算法却不知道它们恰好相等。

模型条件的作用

若奖励均值随时间改变，旧样本未必代表当前表现；若存在用户属性等上下文，同一臂的收益也可能随情境变化。此时需要不同的模型和学习规则。只观察被选择的臂，是本问题与每轮都能看到全部备选反馈的学习问题之间的关键差别。

这里的探索通过未来奖励回收信息成本，适合重复决策。一次性选择、只有可能状态而没有可学习反馈的问题，可使用极小极大遗憾等准则；它们的比较基准和信息结构都与本篇不同。