UCB 算法

UCB 把不确定性下的乐观原则理路不确定性下的乐观原则Optimism under uncertainty · Optimism in the face of uncertainty在仍与数据相容的模型中按最好可能价值行动，以探索消除不确定性。写成一个可比较指数：经验均值表示已经观测到的收益，置信半径表示仍未排除的上升空间。常拉的臂半径收缩，少拉的臂仍可能显得最好，于是探索与利用在每轮由同一条上界共同决定。

次优臂只有在估计发生罕见偏差，或它的半径仍大到足以覆盖 gap 时才会被选中。前两类事件的概率可求和，后一类在样本数达到 $O((\log T)/{\mathrm{\Delta }}_i^2)$ 后消失，这正是拉取界的结构来源。

一轮实际选择 ​

设第 $101$ 轮开始前，三个臂的拉取次数为 $(80,15,5)$，合计恰为此前的 $100$ 轮；经验均值为 $(0.7,0.5,0.2)$。代入本页公式：

算法选择第三臂：它的已观测收益最低，但仅有五次观测，尚未排除的上升空间最大。指数可以大于奖励上限 $1$，因为它是用于排序的置信上界，并非奖励预测值；本页算法按公式直接比较，不截断这些数。

若这次收到奖励 $0$，第三臂次数变为 $6$，奖励总和仍为 $5\times 0.2=1$，新均值为 $1/6$。下一轮用 $t=102$ 和更新后的次数重新计算指数，其他两臂的经验均值保持不变。

自适应样本数的严谨点 ​

$N_i(t)$ 由过去奖励决定，不能把它当作预先固定样本量无条件套 Hoeffding。常见处理是先为每个确定的臂内样本数 $n$ 建立事件，再对 $i,t,n$ 使用并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，或使用置信序列理路置信序列Confidence sequence · Anytime-valid confidence sequence · 时间一致置信序列一列随数据更新的随机置信集合，以规定概率在所有时间同时覆盖同一个固定参数目标。先控制每个臂内所有样本数的覆盖，再分配跨臂错误预算。这样在随机时刻读取经验均值仍有保证。

边界 ​

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

拉取界还能帮助理解探索预算：一个臂与最优均值的差距缩小一半，标准分析中为排除它所需的观测数就约增为四倍。因此预算主要花在难以区分的近邻上；这也解释了为何只看经验均值接近，并不足以宣布某个臂已经获胜。

UCB 是一族算法而非单一公式。方差感知、KL-UCB、线性 UCB 与置信序列版本会改变半径和证明事件；迁移时应从奖励范围、尾部模型和自适应覆盖要求重新推导，不应只替换根号中的常数。