FTPL算法实现m-Set半带问题的Best-of-Both-Worlds遗憾保证

组合半带问题听起来像是纯粹的学术概念但只要你接触过线上广告选品、云资源调度、仓库分批拣货甚至短视频推荐里的候选集生成你就会觉得它离工程实践并不远。m-Set Semi-Bandit 的核心就是每轮从 (K) 个候选项里选 (m) 个然后只拿到被选中项的反馈。2025 年有一篇顶会投稿把目光重新拉回到 FTPLFollow-the-Perturbed-Leader这个朴素算法上证明了它在这个问题里可以做到 Best-of-Both-Worlds——随机环境下积累对数级别的遗憾对抗环境下把遗憾控制在平方根量级。这不只是理论上的漂亮话更关系到我们能不能用一个实现简单、不用反复调参的算法去应对真实系统里那些既稳定又随时可能突变的环境。1. 问题设定m-Set Semi-Bandit 到底在解决什么1.1 从多臂老虎机到组合半带多臂老虎机Multi-Armed Bandit大家应该不陌生有 (K) 个选项每轮选一个然后观察这个选项的收益目标是让累积收益尽量大。但很多真实场景比单臂选择复杂得多比如一次投放要选出 5 个广告位一个批次要挑拣 3 种商品一台服务器要同时跑几个任务。这种每轮必须选出一组动作的问题就进入了组合老虎机Combinatorial Bandit的范畴。m-Set Semi-Bandit 是组合带的一个经典变体每轮从 (K) 个基础臂中选出 (m) 个组成集合 (S_t \subseteq {1,\dots,K})其中 (|S_t| m)。环境给这 (K) 个臂各自产生一个收益向量 (g_t \in [0,1]^K)但智能体只能观察被选中集合内部那 (m) 个臂的收益选集外的收益对它完全不可见。这里有个容易被忽略的字眼Semi-Bandit。在纯 Bandit 设置里你选一个动作只拿到这个动作的收益在 Full-Information 设置里你能看到所有 (K) 个臂的收益。Semi-Bandit 介于两者之间——你拿到的是所选集合内每个臂的收益。就是这“多一点”的反馈让问题结构发生了变化你既不能只看整体收益来判断一组动作好不好也不需要用太粗糙的方式来估计未选臂。1.2 随机环境与对抗环境为什么要“两条腿走路”理论里通常把环境分成两大类。第一类是随机环境Stochastic Context。每个臂有一个固定的未知均值 (\mu_i)每轮收益独立地从分布中采样。这类环境下一个算法如果能持续选最优集合 (S^*)那么它的遗憾Regret应该只随轮次 (T) 对数增长也就是 (O(\log T))。第二类是对抗环境Adversarial Context。环境每轮可以故意和你作对收益向量根据你之前的动作来调整甚至可以和你对着干。这样的环境下不可能指望对数遗憾理论上更好的结果是平方根级别 (O(\sqrt{T}))因为你要对抗一个完全不讲道理的对手需要足够多的样本去摸清它的底细。现实系统往往两种状态都存在。搜索引擎的点击率分布可能一个月内基本稳定但一旦上线一个热点活动用户行为整体偏移之前那些固定均值就全失效了。做推荐系统的同学最清楚这种“环境突然翻脸”的痛。所以理论上追求一种算法在随机环境里不暴殄天物、在对抗环境里不崩盘这就是论文里说的 Best-of-Both-Worlds。1.3 这个工作要解决的核心矛盾难度在于很多算法在一个环境中表现出色换到另一个环境就判若两人。典型的贪心类算法随机环境下很稳一旦遇到对抗性输入就会被克制而一些为对抗设计而生的算法在随机环境下又往往因为过于保守而多付出对数甚至更糟的遗憾。m-Set Semi-Bandit 的难点还叠加了一个“组合爆炸”每轮可选的集合数量是 (\binom{K}{m})直接枚举最优集合不现实。所以理论上我们希望有这样的算法它足够简单不需要显式枚举所有组合它在随机环境下能快速锁定最优集合遗憾保持对数级别它同时能抵抗对抗扰动不被人为构造的序列牵着鼻子走它还最好能利用 Semi-Bandit 反馈而不是只当全信息或纯带问题去对待。FTPL 就是这样一个看起来极其简单的候选者。这篇工作的价值就是把这位“老选手”重新拉回到 m-Set Semi-Bandit 赛场并且给出了它在两种环境下都接近最优的遗憾界。2. FTPL 算法一个被低估的老实人2.1 从 Follow-the-Leader 到 Follow-the-Perturbed-LeaderFollow-the-LeaderFTL可能是所有在线决策算法里最直白的每轮把历史收益累加选历史累积收益最高的那组动作。在对手完全固定的情况下FTL 能很快收敛到最优解但在对抗环境下它有一个致命伤——只要对手稍微设置一点障碍累积收益的微小差距就会导致动作选择在几个候选集之间剧烈振荡遗憾迅速放大。解决办法是加扰动。Follow-the-Perturbed-Leader 在选动作前给每个臂的累积收益加上一个随机扰动 (Z_i)然后选出“历史收益 扰动”最大的 (m) 个臂。扰动的作用相当于给决策过程加了一层“模糊化”让近似的分数差距不再被严格放大。即使几个候选集合的历史累积收益非常接近算法也不会因为微小的分数差异就频繁切换动作。FTPL 的核心优势在于实现成本低。你不需要维护复杂的学习率调度不需要做凸优化甚至不需要知道 (m) 个臂组成的集合空间长什么样。每次决策只需要在 (K) 维向量上做一次排序取前 (m) 个计算开销很小。2.2 扰动分布的选择门道扰动分布不是随便选的。常见的选择包括拉普拉斯分布、Gumbel 分布、指数分布等。不同的扰动分布会直接影响遗憾界的常数和边界条件。比如在 m-Set 这个问题里一个直观的设计是给每个臂注入独立同分布的扰动。如果扰动服从拉普拉斯分布那么概率分析会相对顺手因为拉普拉斯分布的尾部是指数级衰减的这能保证“一个较差臂因为扰动而被选中的概率”足够小。如果扰动取值范围太小本质上等于还是 FTL如果太大决策会被噪声主导随机环境下很难收敛。论文里对扰动尺度的边界条件有明确的推导。简单说扰动要和累积收益在一个量级上配合扰动太小对抗博弈下无法避免 FTL 的病态振荡扰动太大随机环境下选择最优集的概率会被噪声稀释对数遗憾的系数就会变差。这个“中间地带”在哪正是理论分析要解决的核心问题。2.3 组合约束带来的麻烦很多人第一次看到 FTPL 会觉得这算法是不是过于简单了。其实把 FTPL 用到 m-Set Semi-Bandit 上有个隐藏难点由于组合约束你不能只对“集合收益”做线性累加因为每次最优集合是由多个臂共同组成的臂之间的收益在集合内部是加和关系但不同集合之间又是竞争关系。举个例子如果所有臂的累积分数都差不多扰动后任意 (m) 个臂都可能被选中此时一个表现很差的臂可能会长期搭着其他好臂的便车被选中。这对随机环境的遗憾是不利的。理论上要让这个概率可控就得给扰动尺度加足够大的“保护”而保护过头又会影响收敛速度。这篇工作的贡献之一就是找到了这个平衡点对应的分析框架。3. 理论结果与遗憾分析拆解3.1 随机环境下对数遗憾从哪里来如果你用 FTPL 在随机环境下跑最优集合 (S^*) 的累积期望收益是最大的。但因为没有先验知识算法需要在探索和利用之间做权衡。扰动在这里扮演的是“系统性探索”的角色。每个臂的累积收益其实会围绕它的真实均值产生波动而扰动让算法偶尔选中一些并非最优的集合。关键在于这种“偶尔”应该有多大如果每个劣质臂与最优集合中的臂之间存在一个收益差距 (\Delta)那么扰动导致它被选中的概率应当被压缩到某个与 (\Delta) 成反比的量级上。在随机环境下遗憾的典型上界表达通常长这样[ R_T \le O\left(\frac{m^2}{\Delta_{\min}} \log T\right) ]其中 (\Delta_{\min}) 表示最优集合与次优集合之间的最小收益差。这个界里的 (\log T) 来自经典探索-利用权衡每个非最优集合被选中的次数不会超过某个与 (\Delta) 成反比的对数量级。理论细节上通过调节扰动的方差参数可以使得非最优集被选中的期望次数被控制住。3.2 对抗环境下平方根遗憾如何平衡对抗环境下假设每个收益向量都由对手按某种策略产出你的累积遗憾要和“事后看全场表现最好的固定集合”做对比。这个场景下FTPL 的分析通常依赖一个经典工具让扰动尺度随时间变化或者把一个足够大的随机偏移加进累积分数里从而把决策序列和某个稳定分布联系起来。具体到 m-Set Semi-Bandit对抗遗憾界的常见形态是[ R_T \le O\left(m\sqrt{KT}\right) ]这意味着随着轮数增加单轮平均遗憾 (\frac{R_T}{T}) 会按照 (O(1/\sqrt{T})) 的速度收敛到零。这正是对抗环境里“能拿到的最好结果”的典型特征。更细的分析里还要考虑扰动分布族的矩条件、选择集合收益的线性结构以及 Semi-Bandit 反馈相对于 Full-Information 反馈的差异——你拿不到未选臂的信息所以只能通过自身已选集合内的样本来更新这会带来额外的方差项。3.3 “Nearly”到底近在哪里标题里特意写“Nearly Achieves”说明结果并不是完美的最优常数界。通常这种“接近”体现在两方面。一是界中可能会出现额外的因子比如从理论上最优的 (O(m\log T)) 变成了 (O(m^2\log T))或者对抗界里带上了一个额外的 (\sqrt{m}) 因子。这些多出来的多项式因子不会改变其在大 (T) 下的主要增长趋势但确实说明算法在“计算简单”和“理论最优”之间做了一部分取舍。二是在边界情形下比如当最小收益差 (\Delta_{\min}) 非常小或者对抗收益的移动速度很快时分析可能会出现对数因子损失。但总体来看跟只针对单一环境设计的算法相比FTPL 的优势在于全凭一个策略同时拿到了两个环境下的近乎最优保证。4. 实操从零复现一个 FTPL Semi-Bandit Demo4.1 模拟环境与算法骨架理论归理论我更习惯把算法跑起来看曲线。下面这段代码是我根据论文思路写的一个简化复现版本严格来说不是逐行对论文源码的搬运而是把核心逻辑还原出来。pythonimport numpy as npimport matplotlib.pyplot as pltclass SemiBanditEnv:definit(self, modestochastic, K20, m5, T50000):self.mode modeself.K Kself.m mself.t 0if mode stochastic: self.means np.random.rand(K) self.adv_rewards None else: # 对抗环境的简化生成每个臂的收益随轮次缓慢漂移 base np.random.rand(T, K) drift np.cumsum(np.random.randn(T, K) * 0.01, axis0) self.adv_rewards np.clip(base drift, 0.0, 1.0) def best_expected_reward(self): idx np.argsort(self.means)[-self.m:] return self.means[idx].sum() def best_fixed_action_regret(self): total self.adv_rewards.sum(axis0) best_idx np.argsort(total)[-self.m:] best_total total[best_idx].sum() return best_total def step(self, action): if self.mode stochastic: r np.random.binomial(1, self.means[self.t % len(self.means)]) if False else np.random.binomial(1, self.means) return r[action] else: r self.adv_rewards[self.t] self.t 1 return r[action]def fpl_semibandit(K, m, T, modestochastic, scale_base0.5):env SemiBanditEnv(mode, K, m, T)cum np.zeros(K)regret_curve []total_regret 0.0if mode stochastic: best_value env.best_expected_reward() else: best_fixed_total env.best_fixed_action_regret() played_total 0.0 played_counts np.zeros(K) for t in range(1, T 1): scale scale_base * np.sqrt(m / (t 1)) perturb np.random.laplace(scalescale, sizeK) scores cum perturb action np.argsort(scores)[-m:] rewards env.step(action) # Semi-Bandit 反馈只更新被选中臂的累积分数 cum[action] rewards if mode stochastic: instant_regret best_value - env.means[action].sum() total_regret instant_regret else: played_total rewards.sum() # 事后计算“最优固定集合”的收益比较麻烦这里用累积最优集合总收益来近似 # 因为每一轮都是全量生成的可以离线用已经生成的全部数据来做比较 cum_total env.adv_rewards[:t1].sum(axis0) best_idx np.argsort(cum_total)[-m:] best_total_t cum_total[best_idx].sum() total_regret best_total_t - played_total regret_curve.append(total_regret) return regret_curvemark stylebackground: #fff3cd;/mark 代码重点解释一下。cum 数组保存的是每个臂的累积观察收益这是 Semi-Bandit 反馈的核心只有被选中的 \(m\) 个臂的收益才被累加进去。每次决策时给 cum 加上一个拉普拉斯扰动再取前 \(m\) 个。 扰动尺度这里我用了 scale scale_base * sqrt(m / (t1))为了让他随着时间递减。理论里通常会给一个与时间 \(T\) 或轮次 \(t\) 相关的变化尺度具体哪个表达式最优取决于你更侧重随机还是对抗性能。实际复现时最好多试几组不同 decay 策略观察后悔曲线的形态。 mark stylebackground: #fff3cd;### 4.2 关键参数选择与验证方法/mark first \(K\) 和 \(m\) 的比例要拉开。一般建议 \(m \ll K\)比如 \(K20, m5\)。如果 \(m\) 接近 \(K\)那每次基本等于全选问题退化了看不出算法的行为差异。 second扰动尺度。扰动太小算法在对抗环境里的振荡抑制不够扰动太大随机环境下无法稳定收敛到较优集合。我的经验是先固定 mode 为 stochastic跑一组不同 scale_base 的对比选出随机场景后悔曲线最平滑的那个取值再用它去跑对抗场景看后悔是否仍然呈平方根增长。如果两边都能维持合适的增长曲线基本就认为这套参数是可用的。 third验证随机环境是否真的是 \(\log T\) 级别。可以画累计遗憾对轮次的曲线图横轴改成 \(\log T\)如果曲线接近一条直线或者斜率逐渐变平就说明对数遗憾的特征是存在的。验证对抗环境就用双对数图看累计遗憾和 \(T\) 的斜率是否接近 0.5。当然模拟轮次要足够长建议 \(T \ge 100000\)否则短期的随机波动会污染你对渐近趋势的判断。 mark stylebackground: #fff3cd;### 4.3 多个随机种子与方差控制/mark 一个常被忽略的问题是FTPL 本身带有随机扰动所以单次运行的后悔曲线会有较大噪音。我非常建议所有实验都至少跑 20 个不同随机种子取平均后悔曲线并画出标准差区间。否则你观察到的“对数趋势”可能只是某次运气好。 我自己跑下来发现方差的最大来源并不是收益采样本身而是扰动分布的尾部波动。拉普拉斯分布偶尔会生成一个特别大的扰动值导致这一轮选择了明显较差的集合。这在实际系统中也会发生你可以用 truncated 扰动或者在扰动尺度上增加一个上限阈值来缓解虽然这会略微影响理论界的证明但工程上通常值得。 mark stylebackground: #fff3cd;5. 常见问题与避坑心得/mark ### 5.1 半带反馈和全信息反馈的差异不能忽略 有些人会把 Semi-Bandit 简单当全信息来处理给所有臂都更新分数。这在 Full-Information 设置里没错但在 Semi-Bandit 里未选臂的收益是不可观察的你硬给未选臂随便填一个收益会直接污染累积分数导致后续决策被虚假信息带偏。 正确做法就是上面代码里写的cum[action] rewards。只更新本次被选中的臂。这样累积分数里的每一项都来自真实观察虽然有些臂的更新频率低但至少是无偏估计。 ### 5.2 对抗环境下事后比较最优固定集合时的小心机 论文里的对抗遗憾定义是最优固定集合的累计收益减去算法实际收益但“最优固定集合”本身需要知道全部轮次的收益才能算出来。实操时如果你用的模拟环境是预先生成全量收益的那可以在循环外直接算没必要在每一轮里重复计算。 像我的 demo 代码里在每轮都重新计算 best_idx 是方便演示实际大规模模拟中会拖累速度。更高效的方式是遍历完 \(T\) 轮之后一次性算最优固定集合的收益然后用算法每轮记录的实际收益累计值做差。两者结果完全一致但后者能省掉一轮重复的排序计算。 ### 5.3 运行时效率的真正瓶颈是排序不是扰动 FTPL 每次决策的核心是 np.argsort(scores)[-m:]复杂度 \(O(K\log K)\)。当 \(K\) 很大比如百万量级时每轮排序仍然压力不小。 一种工程上的优化是只在部分臂上做排序因为累积分数长期偏低的臂基本没可能通过一次有限大小的扰动跳到前 \(m\)。你可以维护一个“活跃候选集”每轮只对这个集合内的臂加扰动排序每隔一定轮次做一次全局刷新。这么做的代价是理论上需要额外论证“被淘汰的臂不会因为扰动被错误淘汰”但工程上换来的性能提升非常可观。 ### 5.4 这个算法后续还能怎么扩展 如果你手头的问题不只是选 \(m\) 个而是选集合后还要考虑集合内元素之间的关联效应比如推荐系统里一个列表的总体转化率不是各条推荐单独转化率的简单加总那 m-Set Semi-Bandit 的线性假设就不够用了。这时可以把模型从线性奖励扩展成子模奖励或者带交叉项的非线性奖励但 FTPL 的扰动分析就要重新设计边界会变得更紧。 另外如果反馈延迟高比如电商场景里点击反馈要等几小时甚至几天才回传那对 cum 的更新就不能实时做。常见的做法是把 FTPL 改造成 Mini-Batch 版本每隔一段时间统一用一批新反馈更新累积分数。这种改动会让理论上的扰动分析更复杂但至少能在工程上继续吃 FTPL 低成本的红利。 我个人做了不少实验后的体会是如果你面对的系统状态相对平稳只是偶尔有偏移FTPL 配一个合理的扰动衰减策略就已经很能打了。它在绝大多数轮次会表现得像贪心算法一样高效在环境突变时又不会像纯贪心那样彻底失控。最后再分享一个小技巧无论理论界推导得多漂亮落地前一定先画一张不同参数下的后悔曲线对比图观察斜率和方差——很多时候光看理论界的常数项会被误导实际跑出来的趋势才最有发言权。