UCB 算法

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

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

自适应样本数的严谨点 ​

$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以可靠选出最高均值臂为目标，研究纯探索的停止规则与样本复杂度。的最优停止算法。

将每个次优臂的期望拉取次数乘以 ${\mathrm{\Delta }}_i$ 并求和，得到 $O(\sum _i(\log T)/{\mathrm{\Delta }}_i)$ 的实例依赖伪遗憾。该式说明 gap 大的臂会很快被排除，真正昂贵的是与最优臂难分的近邻。

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