多臂老虎机Multi-Armed BanditMAB这个名字听着挺唬人底子却是一个朴素到不能再朴素的场景赌场大厅里摆着一排老虎机每台机器中奖的概率你事先一无所知兜里的硬币就那么几枚怎么安排拉杆顺序才能让最后的收益尽量高。UCB1Upper Confidence Bound, version 1就是解决这类问题最经典、最干净的一个算法公式短到能写在一张便利贴上背后却压着 Hoeffding 不等式和一套相当漂亮的遗憾界证明。如果你正在做推荐系统冷启动、广告素材轮换、A/B 测试的流量分配或者在做超参搜索、临床试验分组甚至只是想给游戏 AI 写一个会自己试错的决策模块UCB1 基本都绕不开。它的好处是几乎零调参——显式超参数只有一个常数系数剩下的全靠数据自己算。我从遗憾的定义开始把 UCB1 的公式从头推一遍然后手写一份能直接跑的 Python 实现跑仿真看它比 ε-贪心好多少最后聊聊实际落地时踩过的那些坑。1. 先把问题框清楚老虎机到底在优化什么1.1 赌场原型与探索-利用的两难先把符号定下来。假设有 K 根臂老虎机第 i 根臂每次被拉动会以一个未知的固定分布吐出一个奖励记它的期望是 μ_i。整个过程跑 T 轮每一轮你只能选一根臂拉完看到本次的实际奖励 r。目标很直白让这 T 轮的奖励总和尽量大。难点在于两件事同时发生。一是你不知道 μ_i 是多少只能靠拉出来的样本去估计二是你的估计本身要靠拉杆来获得而拉杆又消耗了本该花在已知好臂上的预算。这就是所谓的探索-利用困境exploration-exploitation tradeoff。拿推荐场景打比方你手里有 200 条候选内容第一天只能给用户推一条推完看到用户点没点。你想知道哪条最受欢迎就必须每条都试但用户的时间是有限的全拿去试短期点击率就崩了。你要在多试和少试之间找一个动态平衡点。这个平衡点不是拍脑袋定的它有一个数学上的最优节奏而 UCB1 给的就是一个足够接近这个节奏、实现还特别简单的方案。值得注意的是老虎机问题和普通的监督学习有个本质区别你拿到的数据不是随机分配的而是被你的策略挑出来的。这意味着你收集到的样本天然带偏越到后期越集中在少数几根好臂上对这种偏置的估计必须靠额外的机制来纠正。UCB1 的 bonus 项本质上就是那个纠正机制。1.2 别盯着单次收益盯遗憾评价一个 bandit 策略业界不太看总收益而看遗憾Regret。定义很直接假如你从第一轮就知道哪根臂最好并且一直拉它能得到的总收益是 T·μ*其中 μ* max_i μ_i实际策略只拿到 Σ μ_{a_t}两者之差就是累积遗憾R(T) T·μ* − Σ_{t1}^{T} μ_{a_t}为什么用遗憾而不用总收益因为总收益的绝对值和具体问题绑定得太死——一个 μ* 0.9 的问题和一个 μ* 0.05 的问题收益数字差几十倍没法横向比较算法。遗憾把最优解当作基准线扣掉剩下的部分纯粹反映你的策略有多浪费这才是算法本身的能力。遗憾还可以拆成两块。如果第 t 轮选了臂 i这一轮的即时遗憾是 μ* − μ_i记 Δ_i μ* − μ_i叫做这根臂的间隙gap。累积遗憾就是 Σ Δ_{a_t}。你希望这个量增长得越慢越好。如果策略是次优的它会以线性速度增长也就是平均每轮都亏一个固定量如果策略是好的遗憾只会以对数甚至更慢的速度增长摊到每轮上趋近于零。这个线性还是对数的区别在工程上不是学术问题。T 100 万次曝光对数增长的遗憾可能只有几千线性增长的遗憾就是几十万直接对应真金白银的转化损失。所以看一个 bandit 算法值不值得用第一眼就该看它的遗憾是 O(ln T) 还是 O(T)。1.3 贪心和 ε-贪心为什么不够好最直接的想法是纯贪心每一轮都选当前平均收益最高的臂。这个策略的问题太致命了——只要某根臂运气好前几次拉出来几个高奖励它的均值就会短暂飙高然后被无限拉下去永远没有翻身的机会。哪怕它其实是全场最差的臂只要样本量够小它就能把自己伪装成最优解。这种早期随机性导致的锁死现象是贪心策略的经典翻车方式。稍微改一下就是 ε-贪心以 1−ε 的概率选当前最优臂以 ε 的概率随机挑一根。它能逃出锁死但引入了新的浪费——那 ε 的探索是盲目的均匀撒在所有臂上包括早已确认很差的那些。你已经知道第 7 根臂成功率只有 2%却还要按固定比例继续给它流量这就是纯粹的浪费。更麻烦的是 ε 怎么定。ε 设大了长期遗憾下不来设小了早期探索不够、锁死风险还在。有人用 ε 随时间衰减比如 ε_t 1/t效果会好很多但衰减曲线又成了一个需要自己调的超参。我在早期做广告轮换时就吃过这个亏为了保守把 ε 定在 0.1跑了一个月后发现大约 10% 的曝光永远浪费在垫底素材上白扔的量相当可观。UCB1 的思路是彻底换一个角度不再固定探索预算而是让探索量由不确定性自动决定。一根臂没被拉过几次它的不确定性就大bonus 就高自然会被优先探索拉得多了bonus 缩小探索自动退火。整个过程不需要你手调衰减率bonus 的数值直接从置信区间的宽度算出来。2. UCB1 公式是怎么推出来的2.1 乐观主义给不确定的东西加成UCB 的核心哲学叫面对不确定性时保持乐观optimism in the face of uncertainty。具体做法是对每根臂不算它的平均收益而算它的最乐观可能收益——也就是在统计意义上真实均值最高可能有多高。然后挑这个乐观值最大的那根去拉。这个逻辑其实很好理解。一根已经拉了几千次的臂它的均值很稳乐观值和均值几乎一样一根只拉过两次的臂均值可能很低但样本太少真实均值完全可能高得多所以它的乐观值可以很高。于是算法会自然地把有潜力的新人和稳定的老人放在同一个尺度上比较谁的乐观值大谁上。这个乐观值的学名就叫上置信界Upper Confidence Bound。它等于样本均值加上一个置信半径均值是当前最好的猜测半径是我可能猜错了多少的量化。半径越大说明越不确定就越值得再试一次。2.2 Hoeffding 不等式把均值有多可信量化要让半径有数学依据得用一个工具Hoeffding 不等式。先做归一化假设奖励取值落在 [0, 1] 区间内不是的话自己缩放后面会讲。设臂 i 的真实均值为 μ_i已经独立拉了 n_i 次观测到的样本均值为\hat μ_i (1/n_i) · Σ_{s1}^{n_i} r_sHoeffding 不等式告诉我们样本均值高出真实均值超过 ε 的概率有个上界P(\hat μ_i − μ_i ≥ ε) ≤ exp(−2 n_i ε²)这个式子值得多看一眼。它说的是样本量 n_i 越大样本均值偏离真值的概率衰减得越快而且是按 e 的负二次方衰减非常快。它不要求奖励服从正态分布只要求有界且独立同分布这比中心极限定理的适用范围宽得多——伯努利奖励、均匀奖励、有界连续奖励都能用这一点在工程上特别重要因为线上的点击奖励就是个 0/1 伯努利变量。现在把这个不等式反过来用。我不想问给定 ε 求概率我想问给定一个我很小的犯错概率 δε 该取多大。令 exp(−2 n_i ε²) δ两边取对数2 n_i ε² ln(1/δ)ε sqrt( ln(1/δ) / (2 n_i) )这就是置信半径的雏形。你可以看到它的结构分母是拉杆次数 n_i次数越多半径越小分子是对数形式的置信水平你想要越高的把握半径就要放得越宽。2.3 从置信半径到 UCB1 的完整推导剩下唯一的问题是 δ 取多少。δ 不能是常数因为整个 T 轮里你会做 T 次判断如果每次犯错的概率都是固定的 δ累积起来的总犯错概率会随 T 线性膨胀遗憾分析就做不出来了。正确做法是让 δ 随轮数 t 一起衰减并且衰减得足够快使得对 t 求和后是个收敛的级数。Auer 等人在 2002 年那篇经典论文里取的方案是 δ_t t^{−4}。为什么是四次方因为要对所有轮次做并集界union bound需要 Σ_{t1}^{∞} t^{−4} 收敛。这个级数的极限是 π⁴/90 ≈ 1.0823是个很小的常数所以整个过程中至少出现一次覆盖失败的总概率被牢牢压在常数级别遗憾的每一块都能加起来。把 δ t^{−4} 代回半径公式注意 ln(1/δ) ln(t⁴) 4 ln tε sqrt( 4 ln t / (2 n_i) ) sqrt( 2 ln t / n_i )于是臂 i 的上置信界就是UCB_i(t) \hat μ_i sqrt( 2 ln t / n_i )每一轮算完所有臂的这个值选最大的那根a_t argmax_i [ \hat μ_i sqrt( 2 ln t / n_i ) ]这就是 UCB1 的完整公式。没有别的了。整个推导里用到的假设只有三条奖励有界在 [0,1]、各轮奖励独立同分布、臂之间相互独立。三条假设在绝大多数业务场景里都是成立的。顺手补一个历史背景Agrawal 在 1995 年提出的早期 UCB 指数里含有一项需要用动态规划算出来的复杂积分工程上根本没法实时算。Auer 团队用上面这个 sqrt(2 ln t / n) 把它替换掉了指数变成闭式可算这才是 UCB1 真正流行起来的原因。1这个编号来源于它是那篇论文里提出的 UCB 家族中最简单的第一个版本后面还有 UCB2 和 UCB-Tuned。2.4 系数 2 的来历以及改它会发生什么经常有人问那个 2 能不能换成别的。能但你要清楚换掉的是什么。系数 2 完全来自 ln(t⁴)/2 2 ln t。如果你把 δ 从 t^{−4} 改成 t^{−α}半径就变成 sqrt(α ln t / (2 n_i))α 越大半径越大、探索越激进、遗憾上界里的常数也越大。工程代码里通常把它写成一个显式的系数 cbonus 项写成 c·sqrt(2 ln t / n_i)。c 1 是理论值实际调参时在 0.5 到 2 之间试都算合理。调 c 的直觉是这样的如果你的奖励噪声特别大或者奖励分布偏离假设比较严重比如重尾理论半径偏窄可以适当把 c 调大一点多给探索一些空间如果你的奖励很干净、臂之间的差距又很大喜欢快速收敛把 c 调小一点能更快锁定最优臂。不过说实话UCB1 对 c 的敏感度远低于 ε-贪心对 ε 的敏感度我见过很多线上系统就直接用 c 1 没动过效果也够用。注意把 c 调到 0.1 以下时UCB1 实际上退化成了近似贪心策略早期锁死的风险会回来。这不是理论问题是我在压测里亲眼见过的事——c 太小的配置在高噪声环境下前 200 轮就锁死在一根次优臂上之后再也爬不出来。2.5 遗憾上界为什么它值得信赖光有公式不够得知道它有多好。Auer 等人证明的 UCB1 期望遗憾上界大致是E[R(T)] ≤ 8 · Σ_{i: Δ_i0} (ln T / Δ_i) C · Σ_{i: Δ_i0} Δ_i其中 C 是个由收敛级数产生的常数约 4.29 量级。第一项是对数主项第二项是与 T 无关的常数项。把它粗略化简一下就是 O(K · ln T / Δ_min)其中 Δ_min 是最小的那个非零间隙。这个结论有两层含义。第一遗憾随 T 只按对数增长这是 bandit 算法能做到的好结果因为 Lai-Robbins 下界证明了任何一致好的策略遗憾至少是 Ω(ln T)所以 UCB1 在 T 的量级意义上是达到了最优的。第二它对 Δ_min 非常敏感——如果两根臂几乎一样好间隙趋近于零遗憾上界会被放大得很厉害。这不是 UCB1 的缺陷而是问题本身的性质两根几乎一样好的臂你很难区分多花一些代价是必然的。不过也要公平地说UCB1 的常数偏松。Lai-Robbins 下界里最优系数是 1/KL(μ_i, μ*)用 KL 散度度量的UCB1 的分母是 Δ_i²对于伯努利分布来说比 KL 大所以高估了所需样本量。这个差距就是后面 UCB-V、KL-UCB 这些改进版本的动机所在。3. 手写一份能跑的 UCB13.1 接口与数据结构怎么定真要把 UCB1 写成代码需要维护的状态其实非常少每根臂只需要两个数字被拉的次数 counts[i] 和奖励的累加和 sums[i]。均值不单独存用的时候现算这样能避免浮点累积误差——如果你每轮都按 \hat μ ← \hat μ (r − \hat μ)/n 增量更新跑个几百万轮下来误差是能被看见的。每轮决策分两个阶段。第一阶段是冷启动只要还有臂没被拉过就按顺序把没拉过的臂各拉一次。这一步是必须的因为 sqrt(2 ln t / n_i) 在 n_i 0 时除零而且从统计上看不给每根臂至少一个样本你连它属于哪个数量级都不知道谈不上比较。第二阶段才是正常的指数计算和 argmax。有些实现会把冷启动那一步写成初始化时给每根臂的 counts 填 1、sums 填一个乐观初值这也行但我不太推荐。原因是它的行为等价于给每根臂加了一个人为的先验而这个先验的强度你在后面调参时很容易忘掉出问题不好排查。老老实实写个冷启动分支逻辑清楚得多。3.2 完整实现代码下面这份实现只有二十来行我把它写成了一个独立的类方便你直接贴到 notebook 里跑。import numpy as np class UCB1: 奖励需归一化到 [0, 1]。c 是探索系数理论值取 1。 def __init__(self, n_arms, c1.0): self.n_arms int(n_arms) self.c float(c) self.counts np.zeros(self.n_arms, dtypenp.int64) self.sums np.zeros(self.n_arms, dtypenp.float64) property def total(self): return int(self.counts.sum()) def select(self): # 阶段一未被拉过的臂各拉一次顺便避免除零 unseen np.flatnonzero(self.counts 0) if unseen.size 0: return int(unseen[0]) # 阶段二算上置信界取最大 avg self.sums / self.counts bonus self.c * np.sqrt(2.0 * np.log(self.total) / self.counts) return int(np.argmax(avg bonus)) def update(self, arm, reward): self.counts[arm] 1 self.sums[arm] reward这段代码里有两个细节容易写错。一个是np.log(self.total)t 用的是全局总轮数而不是该臂的次数这个很关键——如果误写成 log(counts[i])bonus 的结构就完全变了会退化成一种奇怪的自适应采样。另一个是avg bonus里 avg 必须是浮点如果你的 sums 用了 int 类型除出来会被截断这个坑我在 C 版本里踩过。3.3 仿真跑起来把参数拧一拧光看代码没有手感得跑个数。下面这段仿真是我最常用的验证模板造一组伯努利臂跑 T 轮统计累积遗憾用多组随机种子取平均消除单次波动。def run_ucb1(probs, T, seed, c1.0): rng np.random.default_rng(seed) K len(probs) best max(probs) policy UCB1(K, cc) cum_regret 0.0 for _ in range(T): arm policy.select() reward 1.0 if rng.random() probs[arm] else 0.0 policy.update(arm, reward) cum_regret best - probs[arm] return cum_regret, policy.counts probs [0.15, 0.25, 0.35, 0.45, 0.55, 0.65] T 20000 regrets, all_counts [], [] for s in range(50): reg, cnt run_ucb1(probs, T, seeds) regrets.append(reg) all_counts.append(cnt) print(平均累积遗憾:, np.mean(regrets)) print(各臂平均拉杆次数:, np.mean(all_counts, axis0).round(0))跑完之后你应该会看到两个现象。第一个是各臂的拉杆次数极度不均衡——最优那根臂0.65大概会吃掉一万五千次以上最差那根0.15可能只有几十次。这个分布形态就是 UCB1 该有的样子一旦某根臂被确认很差它的 counts 涨得极慢bonus 也就涨不起来从此基本被冷藏。第二个是累积遗憾的绝对数值会落在几百的量级而不是上千——理论上是几千但那个上界包含了一个宽松的 8 倍常数实际表现通常好得多。再做一组对比实验把 T 从 2000 拉到 20000你会看到遗憾只增加了大约一倍出头ln 20000 / ln 2000 ≈ 9.90 / 7.60 ≈ 1.30而不是增加十倍。这个对数级的增长曲线是判断一个 bandit 实现有没有写错的最直接证据。如果你改完代码发现遗憾随 T 线性增长那基本可以确定 bonus 项写错了或者 counts 的更新逻辑有问题。3.4 和 ε-贪心、Thompson 采样横向比一比单看 UCB1 没意思得有参照物。我在同一组臂、同一批随机种子上跑了三个策略把结果整理成了下面这张表。策略关键机制累积遗憾相对量级需要调的超参确定性纯贪心永远选当前均值最高高且波动极大无是ε-贪心ε0.1固定比例随机探索中等约为 UCB1 的 2 至 3 倍ε否ε-衰减ε_t 1/t较低接近 UCB1衰减曲线否UCB1均值 置信半径低c通常取 1是Thompson 采样从后验采样后取最大通常略优于 UCB1先验参数否表里的相对量级是我多次跑下来得到的经验排序不同参数下具体数值会变但大方向很稳。有几点值得展开说。ε-贪心最大的问题是它的探索是无记忆的。跑了十万轮之后它仍然会以 10% 的概率去拉那根成功率 0.15 的臂这 10% 的浪费是永久性的、不会随经验减少的。而 UCB1 的 bonus 会随着 counts 增长持续缩小探索是自动退火的跑得越久浪费越少。这就是对数遗憾和线性遗憾在实测里的直观差别。Thompson 采样在伯努利奖励下经常能压 UCB1 一头因为它是贝叶斯方法用了完整的后验分布而不只是一个二阶矩的界。但它需要你指定先验Beta(a, b)先验选得不合适早期会跑偏而且它本质上是随机策略同样的输入跑两次结果不一样线上排查问题时这一点挺烦人的。UCB1 的确定性在工程上是个被低估的优点你能精确复现任何一次决策。提示做 A/B 对比实验时务必让三个策略共用同一组随机种子生成的奖励序列。不然你看到的差异里混进了噪声很容易得出错误结论。我早期对比时忘了这事结论反复横跳了好几次。4. 落地踩坑与排查手册4.1 冷启动、奖励尺度与非平稳奖励尺度是第一杀手。UCB1 的推导建立在奖励落在 [0,1] 的前提上。如果你直接把 GMV、停留时长、点击转化金额这种原始数值塞进去均值可能落在几千的区间而 bonus 项里的 sqrt(2 ln t / n) 最大也就几两者的量纲差了三个数量级bonus 完全被均值淹没算法直接退化成纯贪心。正确的处理方式有两种把奖励除以一个上界 R 归一化到 [0,1]或者把 bonus 整体乘以 R 保持量纲一致。哪种都行关键是不能忘。我在一个电商项目里见过有人直接把客单价塞进去跑了两周发现策略一直只推一个爆款排查半天才发现是这个量纲问题。非平稳环境要加窗口。UCB1 的 \hat μ_i 是对全部历史求的平均counts 也是累积的。一旦环境变了——比如某条素材的热度随季节过去了——老数据会拖住均值而 counts 又很大导致 bonus 很小算法几乎没有动力去重新验证。表现就是反应迟钝眼看着效果掉下去也不调整。解决办法是把累积统计换成滑动窗口只统计最近 w 次或者指数加权衰减这就是 Sliding-Window UCB 和 Discounted UCB 的动机。窗口长度 w 怎么定我的经验是取你业务里环境显著变化的时间尺度的两三倍比如素材热度大概三天一轮w 就取一周左右的曝光量。大规模臂数的冷启动成本。UCB1 要求每根臂至少拉一次臂数 K 大的时候这一步很贵。如果 K 是几百无所谓如果 K 是几百万条候选商品先全试一遍根本不可能。这种场景有两条路一是给 counts 设虚拟初值把冷启动软化成先验二是先做一层粗粒度聚类在簇级别跑 bandit簇内再用别的逻辑挑。后者是工业界最常见的做法树的每一层跑一个小规模的 UCB整体复杂度从 O(K) 降到 O(log K)。4.2 常见问题速查表下面这张表是我和同事们在排查时实际用过的按症状查比从头读代码快得多。症状最可能的原因排查动作策略长期只拉一根臂其余几乎不碰bonus 被均值淹没量纲不一致检查奖励是否归一化试把 c 放大到 1 以上观察行为变化遗憾随轮数线性增长bonus 计算错误或 counts 未正确更新打印每轮的 avg 和 bonus确认 bonus 随 total 缓慢上升、随 counts 下降前期锁死在次优臂上c 过小或冷启动阶段被人为缩短把 c 调回 1确认每根臂都拿到了至少一次初始拉杆环境变化后长期不调整累积统计导致对新数据不敏感换成滑动窗口或指数衰减统计相同输入两次运行结果不同你在 update 里加了随机化或臂间均值打平时 argmax 不稳定检查是否有随机成分打平时用固定的 tie-break 规则线上效果远差于离线仿真反馈延迟counts 更新滞后于决策引入影子计数把决策与更新解耦成异步流水线后期完全不再探索业务侧用了很小的 c或 log 项被截断确认 log 用的是全局轮数而不是该臂次数第五条特别值得说。UCB1 的 argmax 在两根臂完全打平时numpy 会返回下标较小的那个。这在仿真里无所谓但在线上意味着流量会系统性地偏向编号靠前的臂久而久之形成一种隐蔽的不公平。如果你的臂对应不同的内容创作者这就是个业务问题而不只是技术问题。显式加一个随机 tie-break 更稳妥。4.3 几条不太写在文档里的心得先跑离线回放再上在线。线上流量是有成本的拿真实用户去验证一个还没调好的算法风险太大。我的做法是先用历史日志做离线评估——每天的曝光日志里每条臂都有被曝光和被点击的记录用这些数据构造一个如果当时选别的臂会怎样的反事实估计IPS 加权是常见做法先把 c 的取值范围缩到一个窄区间再拿去线上小流量试。日志里一定要记 bonus。出问题时最想知道的就是这个决策当时的置信半径是多少。把 avg、bonus、total、counts 一起打点到日志里排查效率能提高一个数量级。很多团队只记了最终选了哪根事后完全无法复现推理过程只能靠猜。注意反馈延迟带来的 counts 滞后。在推荐场景里点击可能在曝光后几分钟甚至几小时才回来。如果决策时读到的是还没更新的 counts你会在短时间内反复选同一根臂——因为它的 counts 迟迟不涨bonus 一直很高。这是线上 UCB1 最容易出现的隐性 bug表现是某个时段流量异常集中。解决办法是决策和计数分成两条路径决策读影子计数计数在反馈回来后异步写入。别用 UCB1 去解决它不擅长的问题。如果臂数固定但候选池每天在变如果奖励不是独立同分布而是有时间相关性如果用户之间有强差异需要个性化UCB1 都不是合适的选择。这些情况下该上的是上下文老虎机或者干脆回到常规的监督学习排序模型把探索交给一个轻量的随机扰动去做。5. UCB 家族的其他成员与适用边界5.1 UCB-V、KL-UCB、滑动窗口 UCB标准 UCB1 只用了样本均值和样本量完全忽略了一个信息奖励的方差。如果一根臂的奖励波动极小比如稳定在 0.5 附近另一根波动极大一会儿 0 一会儿 1均值也是 0.5UCB1 会给它们完全相同的 bonus但显然第一根的不确定性更低真正需要的探索更少。UCB-V 通过把经验方差带进置信半径修正了这一点它的 bonus 形式大致是 sqrt(2 σ̂² ln t / n) 加上一个随 n 衰减的修正项。奖励方差差异大的场景下UCB-V 能明显省下探索预算。KL-UCB 走的是另一条路不用 Hoeffding 的二次型界而用 Chernoff 界导出基于 KL 散度的置信区间。这在伯努利奖励下特别合适因为伯努利的 KL 散度有闭式表达。它的理论性质更好渐近常数能逼近 Lai-Robbins 下界实测在臂数多、间隙小的场景里优势比较明显。滑动窗口 UCB 和折扣 UCB 是针对非平稳环境的两个变体。前者只保留最近 w 轮的观测后者给历史观测加指数衰减权重。两者本质上是同一个思路的两种实现选择哪个主要看你的数据结构——用队列维护窗口容易但更新成本 O(w)用衰减因子是 O(1) 更新但要额外存一个权重和。5.2 上下文来了怎么办LinUCB 与 GP-UCB纯粹的 UCB1 是无上下文的它对所有用户群体给同一个答案。真实的推荐和广告场景里同一个臂对不同用户的收益天差地别这时候需要上下文老虎机。LinUCB 是最常被拿来用的一个。它假设收益是特征向量的线性函数μ xᵀθ把标量的均值和方差换成线性回归的估计和协方差UCB_i xᵀθ̂_i α · sqrt( xᵀ A_i^{−1} x )这里的 A_i 是臂 i 的特征二阶矩矩阵α 就是 UCB1 里那个 c 的角色。结构上完全是同一个思想——线性预测加一个不确定性的加成只是不确定性从标量变成了由特征空间几何形状决定的量。实践中 LinUCB 的 α 通常要调因为它同时承担了置信水平和模型正则化的双重角色不再有理论值可以直接用。GP-UCB 则是把线性假设换成高斯过程适合特征维度低、需要平滑性假设的场景。贝叶斯优化里那套 GP-UCB 采集函数本质上和这里是同一个东西只是名字换了。5.3 什么时候不该用 UCB1最后说说边界。UCB1 有几个明确不适用的情况。第一臂的数量极大且动态变化。前面说过冷启动成本的问题百万级候选池上用 UCB1 需要额外做分层。第二奖励不满足有界独立同分布。特别是奖励之间存在强时间相关性的时候比如某类内容的整体热度在上升Hoeffding 的独立性假设不成立bonus 的理论保证就失效了。这不是说不能用而是说你要知道理论保证没了得靠滑动窗口这类工程手段兜底。第三延迟反馈非常长的场景。如果一次转化的反馈需要一周才能确定UCB1 的 counts 更新会严重滞后于决策节奏整个算法的收敛速度被反馈链路卡死。这种情况更适合用短期信号的代理指标比如点击代替成交先跑起来。第四需要严格可解释性和审计的场景。UCB1 本身是确定性的、可复现的这点是加分项但它的探索行为在业务侧看起来会很反直觉——明明某条素材数据最差算法还在给它流量。如果业务方难以接受这种解释你可能需要准备一套话术把为了长期收益正在付出的探索成本讲清楚或者把探索额度做成显式的预算池让它变得可见可控。我在实际项目里最常用的一套组合是全局层用 UCB1 做粗粒度的资源分配保证探索量自适应用户层用轻量的上下文模型做个性化排序探索交给 UCB1 输出的臂级权重来控制。这套分层结构的好处是两层的职责很清晰出了问题容易定位是哪一层的问题而且 UCB1 那层几乎不需要维护跑几年都不会出什么状况。如果你也想上手建议就从那份二十行的实现开始先在一个小的流量池里跑通全流程把日志打全再考虑往上下文方向扩展。 UCB1算法：多臂老虎机探索-利用、遗憾界与Python实战
多臂老虎机Multi-Armed BanditMAB这个名字听着挺唬人底子却是一个朴素到不能再朴素的场景赌场大厅里摆着一排老虎机每台机器中奖的概率你事先一无所知兜里的硬币就那么几枚怎么安排拉杆顺序才能让最后的收益尽量高。UCB1Upper Confidence Bound, version 1就是解决这类问题最经典、最干净的一个算法公式短到能写在一张便利贴上背后却压着 Hoeffding 不等式和一套相当漂亮的遗憾界证明。如果你正在做推荐系统冷启动、广告素材轮换、A/B 测试的流量分配或者在做超参搜索、临床试验分组甚至只是想给游戏 AI 写一个会自己试错的决策模块UCB1 基本都绕不开。它的好处是几乎零调参——显式超参数只有一个常数系数剩下的全靠数据自己算。我从遗憾的定义开始把 UCB1 的公式从头推一遍然后手写一份能直接跑的 Python 实现跑仿真看它比 ε-贪心好多少最后聊聊实际落地时踩过的那些坑。1. 先把问题框清楚老虎机到底在优化什么1.1 赌场原型与探索-利用的两难先把符号定下来。假设有 K 根臂老虎机第 i 根臂每次被拉动会以一个未知的固定分布吐出一个奖励记它的期望是 μ_i。整个过程跑 T 轮每一轮你只能选一根臂拉完看到本次的实际奖励 r。目标很直白让这 T 轮的奖励总和尽量大。难点在于两件事同时发生。一是你不知道 μ_i 是多少只能靠拉出来的样本去估计二是你的估计本身要靠拉杆来获得而拉杆又消耗了本该花在已知好臂上的预算。这就是所谓的探索-利用困境exploration-exploitation tradeoff。拿推荐场景打比方你手里有 200 条候选内容第一天只能给用户推一条推完看到用户点没点。你想知道哪条最受欢迎就必须每条都试但用户的时间是有限的全拿去试短期点击率就崩了。你要在多试和少试之间找一个动态平衡点。这个平衡点不是拍脑袋定的它有一个数学上的最优节奏而 UCB1 给的就是一个足够接近这个节奏、实现还特别简单的方案。值得注意的是老虎机问题和普通的监督学习有个本质区别你拿到的数据不是随机分配的而是被你的策略挑出来的。这意味着你收集到的样本天然带偏越到后期越集中在少数几根好臂上对这种偏置的估计必须靠额外的机制来纠正。UCB1 的 bonus 项本质上就是那个纠正机制。1.2 别盯着单次收益盯遗憾评价一个 bandit 策略业界不太看总收益而看遗憾Regret。定义很直接假如你从第一轮就知道哪根臂最好并且一直拉它能得到的总收益是 T·μ*其中 μ* max_i μ_i实际策略只拿到 Σ μ_{a_t}两者之差就是累积遗憾R(T) T·μ* − Σ_{t1}^{T} μ_{a_t}为什么用遗憾而不用总收益因为总收益的绝对值和具体问题绑定得太死——一个 μ* 0.9 的问题和一个 μ* 0.05 的问题收益数字差几十倍没法横向比较算法。遗憾把最优解当作基准线扣掉剩下的部分纯粹反映你的策略有多浪费这才是算法本身的能力。遗憾还可以拆成两块。如果第 t 轮选了臂 i这一轮的即时遗憾是 μ* − μ_i记 Δ_i μ* − μ_i叫做这根臂的间隙gap。累积遗憾就是 Σ Δ_{a_t}。你希望这个量增长得越慢越好。如果策略是次优的它会以线性速度增长也就是平均每轮都亏一个固定量如果策略是好的遗憾只会以对数甚至更慢的速度增长摊到每轮上趋近于零。这个线性还是对数的区别在工程上不是学术问题。T 100 万次曝光对数增长的遗憾可能只有几千线性增长的遗憾就是几十万直接对应真金白银的转化损失。所以看一个 bandit 算法值不值得用第一眼就该看它的遗憾是 O(ln T) 还是 O(T)。1.3 贪心和 ε-贪心为什么不够好最直接的想法是纯贪心每一轮都选当前平均收益最高的臂。这个策略的问题太致命了——只要某根臂运气好前几次拉出来几个高奖励它的均值就会短暂飙高然后被无限拉下去永远没有翻身的机会。哪怕它其实是全场最差的臂只要样本量够小它就能把自己伪装成最优解。这种早期随机性导致的锁死现象是贪心策略的经典翻车方式。稍微改一下就是 ε-贪心以 1−ε 的概率选当前最优臂以 ε 的概率随机挑一根。它能逃出锁死但引入了新的浪费——那 ε 的探索是盲目的均匀撒在所有臂上包括早已确认很差的那些。你已经知道第 7 根臂成功率只有 2%却还要按固定比例继续给它流量这就是纯粹的浪费。更麻烦的是 ε 怎么定。ε 设大了长期遗憾下不来设小了早期探索不够、锁死风险还在。有人用 ε 随时间衰减比如 ε_t 1/t效果会好很多但衰减曲线又成了一个需要自己调的超参。我在早期做广告轮换时就吃过这个亏为了保守把 ε 定在 0.1跑了一个月后发现大约 10% 的曝光永远浪费在垫底素材上白扔的量相当可观。UCB1 的思路是彻底换一个角度不再固定探索预算而是让探索量由不确定性自动决定。一根臂没被拉过几次它的不确定性就大bonus 就高自然会被优先探索拉得多了bonus 缩小探索自动退火。整个过程不需要你手调衰减率bonus 的数值直接从置信区间的宽度算出来。2. UCB1 公式是怎么推出来的2.1 乐观主义给不确定的东西加成UCB 的核心哲学叫面对不确定性时保持乐观optimism in the face of uncertainty。具体做法是对每根臂不算它的平均收益而算它的最乐观可能收益——也就是在统计意义上真实均值最高可能有多高。然后挑这个乐观值最大的那根去拉。这个逻辑其实很好理解。一根已经拉了几千次的臂它的均值很稳乐观值和均值几乎一样一根只拉过两次的臂均值可能很低但样本太少真实均值完全可能高得多所以它的乐观值可以很高。于是算法会自然地把有潜力的新人和稳定的老人放在同一个尺度上比较谁的乐观值大谁上。这个乐观值的学名就叫上置信界Upper Confidence Bound。它等于样本均值加上一个置信半径均值是当前最好的猜测半径是我可能猜错了多少的量化。半径越大说明越不确定就越值得再试一次。2.2 Hoeffding 不等式把均值有多可信量化要让半径有数学依据得用一个工具Hoeffding 不等式。先做归一化假设奖励取值落在 [0, 1] 区间内不是的话自己缩放后面会讲。设臂 i 的真实均值为 μ_i已经独立拉了 n_i 次观测到的样本均值为\hat μ_i (1/n_i) · Σ_{s1}^{n_i} r_sHoeffding 不等式告诉我们样本均值高出真实均值超过 ε 的概率有个上界P(\hat μ_i − μ_i ≥ ε) ≤ exp(−2 n_i ε²)这个式子值得多看一眼。它说的是样本量 n_i 越大样本均值偏离真值的概率衰减得越快而且是按 e 的负二次方衰减非常快。它不要求奖励服从正态分布只要求有界且独立同分布这比中心极限定理的适用范围宽得多——伯努利奖励、均匀奖励、有界连续奖励都能用这一点在工程上特别重要因为线上的点击奖励就是个 0/1 伯努利变量。现在把这个不等式反过来用。我不想问给定 ε 求概率我想问给定一个我很小的犯错概率 δε 该取多大。令 exp(−2 n_i ε²) δ两边取对数2 n_i ε² ln(1/δ)ε sqrt( ln(1/δ) / (2 n_i) )这就是置信半径的雏形。你可以看到它的结构分母是拉杆次数 n_i次数越多半径越小分子是对数形式的置信水平你想要越高的把握半径就要放得越宽。2.3 从置信半径到 UCB1 的完整推导剩下唯一的问题是 δ 取多少。δ 不能是常数因为整个 T 轮里你会做 T 次判断如果每次犯错的概率都是固定的 δ累积起来的总犯错概率会随 T 线性膨胀遗憾分析就做不出来了。正确做法是让 δ 随轮数 t 一起衰减并且衰减得足够快使得对 t 求和后是个收敛的级数。Auer 等人在 2002 年那篇经典论文里取的方案是 δ_t t^{−4}。为什么是四次方因为要对所有轮次做并集界union bound需要 Σ_{t1}^{∞} t^{−4} 收敛。这个级数的极限是 π⁴/90 ≈ 1.0823是个很小的常数所以整个过程中至少出现一次覆盖失败的总概率被牢牢压在常数级别遗憾的每一块都能加起来。把 δ t^{−4} 代回半径公式注意 ln(1/δ) ln(t⁴) 4 ln tε sqrt( 4 ln t / (2 n_i) ) sqrt( 2 ln t / n_i )于是臂 i 的上置信界就是UCB_i(t) \hat μ_i sqrt( 2 ln t / n_i )每一轮算完所有臂的这个值选最大的那根a_t argmax_i [ \hat μ_i sqrt( 2 ln t / n_i ) ]这就是 UCB1 的完整公式。没有别的了。整个推导里用到的假设只有三条奖励有界在 [0,1]、各轮奖励独立同分布、臂之间相互独立。三条假设在绝大多数业务场景里都是成立的。顺手补一个历史背景Agrawal 在 1995 年提出的早期 UCB 指数里含有一项需要用动态规划算出来的复杂积分工程上根本没法实时算。Auer 团队用上面这个 sqrt(2 ln t / n) 把它替换掉了指数变成闭式可算这才是 UCB1 真正流行起来的原因。1这个编号来源于它是那篇论文里提出的 UCB 家族中最简单的第一个版本后面还有 UCB2 和 UCB-Tuned。2.4 系数 2 的来历以及改它会发生什么经常有人问那个 2 能不能换成别的。能但你要清楚换掉的是什么。系数 2 完全来自 ln(t⁴)/2 2 ln t。如果你把 δ 从 t^{−4} 改成 t^{−α}半径就变成 sqrt(α ln t / (2 n_i))α 越大半径越大、探索越激进、遗憾上界里的常数也越大。工程代码里通常把它写成一个显式的系数 cbonus 项写成 c·sqrt(2 ln t / n_i)。c 1 是理论值实际调参时在 0.5 到 2 之间试都算合理。调 c 的直觉是这样的如果你的奖励噪声特别大或者奖励分布偏离假设比较严重比如重尾理论半径偏窄可以适当把 c 调大一点多给探索一些空间如果你的奖励很干净、臂之间的差距又很大喜欢快速收敛把 c 调小一点能更快锁定最优臂。不过说实话UCB1 对 c 的敏感度远低于 ε-贪心对 ε 的敏感度我见过很多线上系统就直接用 c 1 没动过效果也够用。注意把 c 调到 0.1 以下时UCB1 实际上退化成了近似贪心策略早期锁死的风险会回来。这不是理论问题是我在压测里亲眼见过的事——c 太小的配置在高噪声环境下前 200 轮就锁死在一根次优臂上之后再也爬不出来。2.5 遗憾上界为什么它值得信赖光有公式不够得知道它有多好。Auer 等人证明的 UCB1 期望遗憾上界大致是E[R(T)] ≤ 8 · Σ_{i: Δ_i0} (ln T / Δ_i) C · Σ_{i: Δ_i0} Δ_i其中 C 是个由收敛级数产生的常数约 4.29 量级。第一项是对数主项第二项是与 T 无关的常数项。把它粗略化简一下就是 O(K · ln T / Δ_min)其中 Δ_min 是最小的那个非零间隙。这个结论有两层含义。第一遗憾随 T 只按对数增长这是 bandit 算法能做到的好结果因为 Lai-Robbins 下界证明了任何一致好的策略遗憾至少是 Ω(ln T)所以 UCB1 在 T 的量级意义上是达到了最优的。第二它对 Δ_min 非常敏感——如果两根臂几乎一样好间隙趋近于零遗憾上界会被放大得很厉害。这不是 UCB1 的缺陷而是问题本身的性质两根几乎一样好的臂你很难区分多花一些代价是必然的。不过也要公平地说UCB1 的常数偏松。Lai-Robbins 下界里最优系数是 1/KL(μ_i, μ*)用 KL 散度度量的UCB1 的分母是 Δ_i²对于伯努利分布来说比 KL 大所以高估了所需样本量。这个差距就是后面 UCB-V、KL-UCB 这些改进版本的动机所在。3. 手写一份能跑的 UCB13.1 接口与数据结构怎么定真要把 UCB1 写成代码需要维护的状态其实非常少每根臂只需要两个数字被拉的次数 counts[i] 和奖励的累加和 sums[i]。均值不单独存用的时候现算这样能避免浮点累积误差——如果你每轮都按 \hat μ ← \hat μ (r − \hat μ)/n 增量更新跑个几百万轮下来误差是能被看见的。每轮决策分两个阶段。第一阶段是冷启动只要还有臂没被拉过就按顺序把没拉过的臂各拉一次。这一步是必须的因为 sqrt(2 ln t / n_i) 在 n_i 0 时除零而且从统计上看不给每根臂至少一个样本你连它属于哪个数量级都不知道谈不上比较。第二阶段才是正常的指数计算和 argmax。有些实现会把冷启动那一步写成初始化时给每根臂的 counts 填 1、sums 填一个乐观初值这也行但我不太推荐。原因是它的行为等价于给每根臂加了一个人为的先验而这个先验的强度你在后面调参时很容易忘掉出问题不好排查。老老实实写个冷启动分支逻辑清楚得多。3.2 完整实现代码下面这份实现只有二十来行我把它写成了一个独立的类方便你直接贴到 notebook 里跑。import numpy as np class UCB1: 奖励需归一化到 [0, 1]。c 是探索系数理论值取 1。 def __init__(self, n_arms, c1.0): self.n_arms int(n_arms) self.c float(c) self.counts np.zeros(self.n_arms, dtypenp.int64) self.sums np.zeros(self.n_arms, dtypenp.float64) property def total(self): return int(self.counts.sum()) def select(self): # 阶段一未被拉过的臂各拉一次顺便避免除零 unseen np.flatnonzero(self.counts 0) if unseen.size 0: return int(unseen[0]) # 阶段二算上置信界取最大 avg self.sums / self.counts bonus self.c * np.sqrt(2.0 * np.log(self.total) / self.counts) return int(np.argmax(avg bonus)) def update(self, arm, reward): self.counts[arm] 1 self.sums[arm] reward这段代码里有两个细节容易写错。一个是np.log(self.total)t 用的是全局总轮数而不是该臂的次数这个很关键——如果误写成 log(counts[i])bonus 的结构就完全变了会退化成一种奇怪的自适应采样。另一个是avg bonus里 avg 必须是浮点如果你的 sums 用了 int 类型除出来会被截断这个坑我在 C 版本里踩过。3.3 仿真跑起来把参数拧一拧光看代码没有手感得跑个数。下面这段仿真是我最常用的验证模板造一组伯努利臂跑 T 轮统计累积遗憾用多组随机种子取平均消除单次波动。def run_ucb1(probs, T, seed, c1.0): rng np.random.default_rng(seed) K len(probs) best max(probs) policy UCB1(K, cc) cum_regret 0.0 for _ in range(T): arm policy.select() reward 1.0 if rng.random() probs[arm] else 0.0 policy.update(arm, reward) cum_regret best - probs[arm] return cum_regret, policy.counts probs [0.15, 0.25, 0.35, 0.45, 0.55, 0.65] T 20000 regrets, all_counts [], [] for s in range(50): reg, cnt run_ucb1(probs, T, seeds) regrets.append(reg) all_counts.append(cnt) print(平均累积遗憾:, np.mean(regrets)) print(各臂平均拉杆次数:, np.mean(all_counts, axis0).round(0))跑完之后你应该会看到两个现象。第一个是各臂的拉杆次数极度不均衡——最优那根臂0.65大概会吃掉一万五千次以上最差那根0.15可能只有几十次。这个分布形态就是 UCB1 该有的样子一旦某根臂被确认很差它的 counts 涨得极慢bonus 也就涨不起来从此基本被冷藏。第二个是累积遗憾的绝对数值会落在几百的量级而不是上千——理论上是几千但那个上界包含了一个宽松的 8 倍常数实际表现通常好得多。再做一组对比实验把 T 从 2000 拉到 20000你会看到遗憾只增加了大约一倍出头ln 20000 / ln 2000 ≈ 9.90 / 7.60 ≈ 1.30而不是增加十倍。这个对数级的增长曲线是判断一个 bandit 实现有没有写错的最直接证据。如果你改完代码发现遗憾随 T 线性增长那基本可以确定 bonus 项写错了或者 counts 的更新逻辑有问题。3.4 和 ε-贪心、Thompson 采样横向比一比单看 UCB1 没意思得有参照物。我在同一组臂、同一批随机种子上跑了三个策略把结果整理成了下面这张表。策略关键机制累积遗憾相对量级需要调的超参确定性纯贪心永远选当前均值最高高且波动极大无是ε-贪心ε0.1固定比例随机探索中等约为 UCB1 的 2 至 3 倍ε否ε-衰减ε_t 1/t较低接近 UCB1衰减曲线否UCB1均值 置信半径低c通常取 1是Thompson 采样从后验采样后取最大通常略优于 UCB1先验参数否表里的相对量级是我多次跑下来得到的经验排序不同参数下具体数值会变但大方向很稳。有几点值得展开说。ε-贪心最大的问题是它的探索是无记忆的。跑了十万轮之后它仍然会以 10% 的概率去拉那根成功率 0.15 的臂这 10% 的浪费是永久性的、不会随经验减少的。而 UCB1 的 bonus 会随着 counts 增长持续缩小探索是自动退火的跑得越久浪费越少。这就是对数遗憾和线性遗憾在实测里的直观差别。Thompson 采样在伯努利奖励下经常能压 UCB1 一头因为它是贝叶斯方法用了完整的后验分布而不只是一个二阶矩的界。但它需要你指定先验Beta(a, b)先验选得不合适早期会跑偏而且它本质上是随机策略同样的输入跑两次结果不一样线上排查问题时这一点挺烦人的。UCB1 的确定性在工程上是个被低估的优点你能精确复现任何一次决策。提示做 A/B 对比实验时务必让三个策略共用同一组随机种子生成的奖励序列。不然你看到的差异里混进了噪声很容易得出错误结论。我早期对比时忘了这事结论反复横跳了好几次。4. 落地踩坑与排查手册4.1 冷启动、奖励尺度与非平稳奖励尺度是第一杀手。UCB1 的推导建立在奖励落在 [0,1] 的前提上。如果你直接把 GMV、停留时长、点击转化金额这种原始数值塞进去均值可能落在几千的区间而 bonus 项里的 sqrt(2 ln t / n) 最大也就几两者的量纲差了三个数量级bonus 完全被均值淹没算法直接退化成纯贪心。正确的处理方式有两种把奖励除以一个上界 R 归一化到 [0,1]或者把 bonus 整体乘以 R 保持量纲一致。哪种都行关键是不能忘。我在一个电商项目里见过有人直接把客单价塞进去跑了两周发现策略一直只推一个爆款排查半天才发现是这个量纲问题。非平稳环境要加窗口。UCB1 的 \hat μ_i 是对全部历史求的平均counts 也是累积的。一旦环境变了——比如某条素材的热度随季节过去了——老数据会拖住均值而 counts 又很大导致 bonus 很小算法几乎没有动力去重新验证。表现就是反应迟钝眼看着效果掉下去也不调整。解决办法是把累积统计换成滑动窗口只统计最近 w 次或者指数加权衰减这就是 Sliding-Window UCB 和 Discounted UCB 的动机。窗口长度 w 怎么定我的经验是取你业务里环境显著变化的时间尺度的两三倍比如素材热度大概三天一轮w 就取一周左右的曝光量。大规模臂数的冷启动成本。UCB1 要求每根臂至少拉一次臂数 K 大的时候这一步很贵。如果 K 是几百无所谓如果 K 是几百万条候选商品先全试一遍根本不可能。这种场景有两条路一是给 counts 设虚拟初值把冷启动软化成先验二是先做一层粗粒度聚类在簇级别跑 bandit簇内再用别的逻辑挑。后者是工业界最常见的做法树的每一层跑一个小规模的 UCB整体复杂度从 O(K) 降到 O(log K)。4.2 常见问题速查表下面这张表是我和同事们在排查时实际用过的按症状查比从头读代码快得多。症状最可能的原因排查动作策略长期只拉一根臂其余几乎不碰bonus 被均值淹没量纲不一致检查奖励是否归一化试把 c 放大到 1 以上观察行为变化遗憾随轮数线性增长bonus 计算错误或 counts 未正确更新打印每轮的 avg 和 bonus确认 bonus 随 total 缓慢上升、随 counts 下降前期锁死在次优臂上c 过小或冷启动阶段被人为缩短把 c 调回 1确认每根臂都拿到了至少一次初始拉杆环境变化后长期不调整累积统计导致对新数据不敏感换成滑动窗口或指数衰减统计相同输入两次运行结果不同你在 update 里加了随机化或臂间均值打平时 argmax 不稳定检查是否有随机成分打平时用固定的 tie-break 规则线上效果远差于离线仿真反馈延迟counts 更新滞后于决策引入影子计数把决策与更新解耦成异步流水线后期完全不再探索业务侧用了很小的 c或 log 项被截断确认 log 用的是全局轮数而不是该臂次数第五条特别值得说。UCB1 的 argmax 在两根臂完全打平时numpy 会返回下标较小的那个。这在仿真里无所谓但在线上意味着流量会系统性地偏向编号靠前的臂久而久之形成一种隐蔽的不公平。如果你的臂对应不同的内容创作者这就是个业务问题而不只是技术问题。显式加一个随机 tie-break 更稳妥。4.3 几条不太写在文档里的心得先跑离线回放再上在线。线上流量是有成本的拿真实用户去验证一个还没调好的算法风险太大。我的做法是先用历史日志做离线评估——每天的曝光日志里每条臂都有被曝光和被点击的记录用这些数据构造一个如果当时选别的臂会怎样的反事实估计IPS 加权是常见做法先把 c 的取值范围缩到一个窄区间再拿去线上小流量试。日志里一定要记 bonus。出问题时最想知道的就是这个决策当时的置信半径是多少。把 avg、bonus、total、counts 一起打点到日志里排查效率能提高一个数量级。很多团队只记了最终选了哪根事后完全无法复现推理过程只能靠猜。注意反馈延迟带来的 counts 滞后。在推荐场景里点击可能在曝光后几分钟甚至几小时才回来。如果决策时读到的是还没更新的 counts你会在短时间内反复选同一根臂——因为它的 counts 迟迟不涨bonus 一直很高。这是线上 UCB1 最容易出现的隐性 bug表现是某个时段流量异常集中。解决办法是决策和计数分成两条路径决策读影子计数计数在反馈回来后异步写入。别用 UCB1 去解决它不擅长的问题。如果臂数固定但候选池每天在变如果奖励不是独立同分布而是有时间相关性如果用户之间有强差异需要个性化UCB1 都不是合适的选择。这些情况下该上的是上下文老虎机或者干脆回到常规的监督学习排序模型把探索交给一个轻量的随机扰动去做。5. UCB 家族的其他成员与适用边界5.1 UCB-V、KL-UCB、滑动窗口 UCB标准 UCB1 只用了样本均值和样本量完全忽略了一个信息奖励的方差。如果一根臂的奖励波动极小比如稳定在 0.5 附近另一根波动极大一会儿 0 一会儿 1均值也是 0.5UCB1 会给它们完全相同的 bonus但显然第一根的不确定性更低真正需要的探索更少。UCB-V 通过把经验方差带进置信半径修正了这一点它的 bonus 形式大致是 sqrt(2 σ̂² ln t / n) 加上一个随 n 衰减的修正项。奖励方差差异大的场景下UCB-V 能明显省下探索预算。KL-UCB 走的是另一条路不用 Hoeffding 的二次型界而用 Chernoff 界导出基于 KL 散度的置信区间。这在伯努利奖励下特别合适因为伯努利的 KL 散度有闭式表达。它的理论性质更好渐近常数能逼近 Lai-Robbins 下界实测在臂数多、间隙小的场景里优势比较明显。滑动窗口 UCB 和折扣 UCB 是针对非平稳环境的两个变体。前者只保留最近 w 轮的观测后者给历史观测加指数衰减权重。两者本质上是同一个思路的两种实现选择哪个主要看你的数据结构——用队列维护窗口容易但更新成本 O(w)用衰减因子是 O(1) 更新但要额外存一个权重和。5.2 上下文来了怎么办LinUCB 与 GP-UCB纯粹的 UCB1 是无上下文的它对所有用户群体给同一个答案。真实的推荐和广告场景里同一个臂对不同用户的收益天差地别这时候需要上下文老虎机。LinUCB 是最常被拿来用的一个。它假设收益是特征向量的线性函数μ xᵀθ把标量的均值和方差换成线性回归的估计和协方差UCB_i xᵀθ̂_i α · sqrt( xᵀ A_i^{−1} x )这里的 A_i 是臂 i 的特征二阶矩矩阵α 就是 UCB1 里那个 c 的角色。结构上完全是同一个思想——线性预测加一个不确定性的加成只是不确定性从标量变成了由特征空间几何形状决定的量。实践中 LinUCB 的 α 通常要调因为它同时承担了置信水平和模型正则化的双重角色不再有理论值可以直接用。GP-UCB 则是把线性假设换成高斯过程适合特征维度低、需要平滑性假设的场景。贝叶斯优化里那套 GP-UCB 采集函数本质上和这里是同一个东西只是名字换了。5.3 什么时候不该用 UCB1最后说说边界。UCB1 有几个明确不适用的情况。第一臂的数量极大且动态变化。前面说过冷启动成本的问题百万级候选池上用 UCB1 需要额外做分层。第二奖励不满足有界独立同分布。特别是奖励之间存在强时间相关性的时候比如某类内容的整体热度在上升Hoeffding 的独立性假设不成立bonus 的理论保证就失效了。这不是说不能用而是说你要知道理论保证没了得靠滑动窗口这类工程手段兜底。第三延迟反馈非常长的场景。如果一次转化的反馈需要一周才能确定UCB1 的 counts 更新会严重滞后于决策节奏整个算法的收敛速度被反馈链路卡死。这种情况更适合用短期信号的代理指标比如点击代替成交先跑起来。第四需要严格可解释性和审计的场景。UCB1 本身是确定性的、可复现的这点是加分项但它的探索行为在业务侧看起来会很反直觉——明明某条素材数据最差算法还在给它流量。如果业务方难以接受这种解释你可能需要准备一套话术把为了长期收益正在付出的探索成本讲清楚或者把探索额度做成显式的预算池让它变得可见可控。我在实际项目里最常用的一套组合是全局层用 UCB1 做粗粒度的资源分配保证探索量自适应用户层用轻量的上下文模型做个性化排序探索交给 UCB1 输出的臂级权重来控制。这套分层结构的好处是两层的职责很清晰出了问题容易定位是哪一层的问题而且 UCB1 那层几乎不需要维护跑几年都不会出什么状况。如果你也想上手建议就从那份二十行的实现开始先在一个小的流量池里跑通全流程把日志打全再考虑往上下文方向扩展。