KL-UCB

集合中的 $q$ 是尚未被数据排除的候选均值，取上端点表示在可信模型中选择最乐观的一个。样本少时约束右侧 $f(t)/N_i$ 大，指数接近 $1$，迫使算法探索；观测增加后，置信集合收缩到经验均值附近。

局部展开

显示半径会根据 Bernoulli 方差调整。但 KL-UCB 不只是把 UCB 平方根项里的方差替掉：远离局部区域时完整非对称散度决定置信边界，这正是渐近常数改进的来源。

遗憾保证 ​

设臂奖励独立 Bernoulli，最佳均值为 ${\mu }_{\ast }<1$，次优臂 $i$ 的均值为 ${\mu }_i<{\mu }_{\ast }$。KL-UCB 的分析给出

因此期望遗憾满足

这与 Lai–Robbins 型 change-of-measure 下界的常数匹配，因而在相应一致性条件下渐近最优。结论比较的是固定随机实例上的 $T\to \mathrm{\infty }$ 行为，不表示每个有限 $T$ 都优于 Hoeffding UCB。

分析中的两个坏事件 ​

次优臂被选择，通常因为最佳臂的指数异常低，或次优臂仍有一个高于 ${\mu }_{\ast }$ 的可行候选。第一类由最佳臂的 KL 自归一化集中控制；第二类意味着

只有在臂 $i$ 样本还少或经验均值异常高时成立。把两类事件求和，就得到每个次优臂约 $(\log T)/\mathrm{kl}({\mu }_i\Vert {\mu }_{\ast })$ 次拉取。

随机拉取次数依赖过去，不能把 $N_i(t)$ 当预先固定样本量后机械套 Hoeffding。严谨证明按第 $s$ 次拉取重索引观测，或使用适应过程的自归一化不等式。

边界与推广 ​

Bernoulli KL-UCB 的公式依赖奖励族。对有界但非 Bernoulli 奖励，Bernoulli KL 可通过极值性质给保守界；对指数族可使用相应分布 KL，得到参数族适配版本。若似然族错设，指数未必保持所需 coverage。

本页的 KL 方向是 $\mathrm{kl}({\mu }_i\Vert {\mu }_{\ast })$。交换方向会改变渐近常数，也不对应通过改变次优臂使其看似最优的下界代价。该算法控制累计遗憾，不等同于固定置信最佳臂识别中的 KL 分配问题。

KL-UCB 在 Bernoulli 实例上把次优臂拉取次数的首项常数压到 $1/\mathrm{kl}({\mu }_i\Vert {\mu }_{\ast })$，与 change-of-measure 下界匹配。优势来自完整分布几何，而不是在 Hoeffding 半径中替换一个经验方差。

指数族可用对应 KL 构造参数适配指数；一般有界奖励则可使用 Bernoulli 极值界获得保守保证。模型错设、重尾或非平稳奖励会破坏置信覆盖，需要更换集中工具与环境模型。