KL-UCB

形式陈述 ​

本页选择固定均值随机赌博机理路随机赌博机与伪遗憾Stochastic bandit · Pseudo-regret每个臂从固定分布独立取样时，以均值差和选择次数表达期望损失。的 Bernoulli 奖励族。KL-UCB 按乐观原则理路不确定性下的乐观原则Optimism under uncertainty · Optimism in the face of uncertainty在仍与数据相容的模型中按最好可能价值行动，以探索消除不确定性。选择置信集合上端点；与UCB1理路UCB 算法UCB1 · upper confidence bound algorithm在有界随机多臂赌博机中选择经验均值加置信半径最大的手臂。相比，它用适配 Bernoulli 族的相对熵集合代替分布无关平方根半径。

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

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

记

它是 Bernoulli$(p)$ 到 Bernoulli$(q)$ 的KL 散度理路KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。；本页所有对数均为自然对数，方向由“观测经验参数 $p$、候选真实参数 $q$”决定。零概率项按连续延拓解释；正概率除以零则给出无穷散度。

算法 ​

设 $K\ge 2$，先将每个臂拉取一次；若时域先结束，就停止初始化。之后 $t\ge K+1\ge 3$，臂 $i$ 已拉取 $N_i(t-1)$ 次，经验均值为 ${\hat{\mu }}_i(t-1)$。定义指数

本页固定 $f(t)=\log t+3\log \log t>0$，选择 $U_i(t)$ 最大的臂并预先固定平票规则。下述保证对应这个探索函数；不能任意改变系数后沿用同一证明。$K=1$ 时只需始终选择唯一臂。

对固定 $p$，$q\mapsto \mathrm{kl}(p\Vert q)$ 在 $q\ge p$ 上单调增加，因此指数可用区间 $[p,1]$ 上的二分搜索求解。若 $p=0$，指数恰为 $1-\exp (-f(t)/N_i)$；若 $p=1$，指数为 $1$。实现应直接处理边界，避免计算零概率项时产生数值错误。

若只要求指数所在区间宽度至多 $0<\epsilon <1$，每臂至多二分 $\lceil {\log }_2(1/\epsilon )\rceil$ 次，每次求一个 KL 值；直接实现每轮为全部 $K$ 个臂求指数，再作 $O(K)$ 次比较。计数、奖励和及指数共用 $O(K)$ 存储，选中臂的统计量更新只需常数次运算。这按实数基本运算与 KL 求值分别计费；对数计算、数值精度和奖励反馈的成本另计。下述定理使用精确上端点，有限精度选择规则的遗憾保证还需控制指数误差。