UCB 算法

模型与算法 ​

有 $K$ 个臂，臂 $i$ 的奖励独立同分布于 $[0,1]$，均值为 ${\mu }_i$。UCB1 先把每臂拉一次；此后在时刻 $t$ 选择

$$I_t\in \arg \underset{i}{max}\{{\hat{\mu }}_i(t-1)+\sqrt{\frac{2\log t}{N_i(t-1)}}\},$$

其中 $N_i(t-1)$ 是此前拉臂次数，${\hat{\mu }}_i$ 是对应奖励均值。平票规则可任意固定。指数中的常数与证明采用的置信事件必须配套；“UCB”还包括许多方差、自归一化或 KL 版本，本页只陈述 UCB1。

探索—利用图像 ​

经验均值代表已知收益，半径代表尚未排除的乐观空间。常拉的臂 $N_i$ 大，半径收缩；少拉的臂半径仍大，会被自动重新探索。算法不是先分出纯探索阶段再永久利用，而是在每轮用同一个上置信指标比较。

次优臂拉取界 ​

令 ${\mu }^{\ast }=\underset{i}{max}{\mu }_i$、${\mathrm{\Delta }}_i={\mu }^{\ast }-{\mu }_i>0$。若次优臂 $i$ 在已经拉取 $n$ 次后仍被选中，则至少发生以下之一：最优臂均值被低估、臂 $i$ 均值被高估，或其半径尚大到 $2\sqrt{2\log t/n}\ge {\mathrm{\Delta }}_i$。前两类由Hoeffding 不等式公理库Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。及对时间/臂的求和控制；后一项在 $n>8\log T/{\mathrm{\Delta }}_i^2$ 后不再可能。由此得到

$$\mathbb{E}{N}_i(T)\le \frac{8\log T}{{\mathrm{\Delta }}_i^2}+O(1),$$

以及伪遗憾

$${\overline{\mathrm{Reg}}}_T=\sum _{i:{\mathrm{\Delta }}_i>0}{\mathrm{\Delta }}_i\mathbb{E}{N}_i(T)=O\left(\sum _{i:{\mathrm{\Delta }}_i>0}\frac{\log T}{{\mathrm{\Delta }}_i}\right).$$

自适应样本数的严谨点 ​

$N_i(t)$ 由过去奖励决定，不能把它当作预先固定样本量无条件套 Hoeffding。常见处理是先为每个确定的臂内样本数 $n$ 建立事件，再对 $i,t,n$ 使用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，或使用适用于停止时间的置信序列。这样在随机时刻读取经验均值仍有保证。

边界 ​

${\mathrm{\Delta }}_i$ 很小时，上述 gap-dependent 界可能比 minimax $\sqrt{KT}$ 量级更差；它不是所有实例上的最佳表达。奖励范围未知、重尾、非平稳或对抗生成时，Hoeffding 半径失效，需要稳健均值或另一 bandit 模型。UCB1 控制累计 regret，也不是最佳臂识别公理库最佳臂识别best-arm identification · pure exploration以可靠选出最高均值臂为目标，研究纯探索的停止规则与样本复杂度。的最优停止算法。

参考资料

• Peter Auer, Nicolò Cesa-Bianchi, Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, 2002.
• Tor Lattimore, Csaba Szepesvári, Bandit Algorithms, Cambridge University Press, 2020.