KL-UCB

从平方根半径到分布几何 ​

Hoeffding 型 UCB 把均值不确定性写成对称半径

$${\hat{\mu }}_i+\sqrt{c\log t/N_i(t)}.$$

对 Bernoulli 奖励，接近 $0$ 或 $1$ 的经验均值具有明显非对称的可行范围，平方根半径没有使用这一分布结构。KL-UCB 不直接给均值加半径，而问：哪些候选均值 $q$ 与观测经验均值在 Bernoulli 相对熵下仍相容？

记

$$\mathrm{kl}(p\Vert q)=p\log \frac{p}{q}+(1-p)\log \frac{1-p}{1-q}.$$

它是 Bernoulli$(p)$ 到 Bernoulli$(q)$ 的KL 散度公理库KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。，方向由“观测经验参数 $p$、候选真实参数 $q$”决定。

算法 ​

先将每个臂至少拉取一次。第 $t$ 轮前，臂 $i$ 已拉取 $N_i(t-1)$ 次，经验均值为 ${\hat{\mu }}_i(t-1)$。定义指数

$$U_i(t)=sup\{q\in [{\hat{\mu }}_i(t-1),1]:N_i(t-1)\mathrm{kl}({\hat{\mu }}_i(t-1)\Vert q)\le f(t)\},$$

其中常用 $f(t)=\log t+c\log \log t$。选择 $U_i(t)$ 最大的臂。

对固定 $p$，$q\mapsto \mathrm{kl}(p\Vert q)$ 在 $q\ge p$ 上单调增加，因此指数可用区间 $[p,1]$ 上的二分搜索求解。若 $p=1$，上端点就是 $1$；实现应直接处理边界，避免计算 $0\log 0$ 产生数值错误。

为什么这是乐观原则 ​

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

局部展开

$$\mathrm{kl}(p\Vert p+u)\approx \frac{u^2}{2p(1-p)}$$

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

遗憾保证 ​

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

$$\underset{T\to \mathrm{\infty }}{lim sup}\frac{\mathbb{E}{N}_i(T)}{\log T}\le \frac{1}{\mathrm{kl}({\mu }_i\Vert {\mu }_{\ast })}.$$

因此期望遗憾满足

$$\underset{T\to \mathrm{\infty }}{lim sup}\frac{\mathbb{E}{R}_T}{\log T}\le \sum _{i:{\mu }_i<{\mu }_{\ast }}\frac{{\mu }_{\ast }-{\mu }_i}{\mathrm{kl}({\mu }_i\Vert {\mu }_{\ast })}.$$

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

分析中的两个坏事件 ​

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

$$N_i(t)\mathrm{kl}({\hat{\mu }}_i(t)\Vert {\mu }_{\ast })\le f(t),$$

只有在臂 $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 分配问题。

参考资料

• Aurélien Garivier and Olivier Cappé, “The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond,” COLT, 2011.
• Tze Leung Lai and Herbert Robbins, “Asymptotically Efficient Adaptive Allocation Rules,” Advances in Applied Mathematics, 1985.
• Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, KL-based index chapters.