过去一年我在反复调一套推荐策略的时候最大的挫败感来自环境不确定性流量平稳时算法怎么调都显得聪明一到活动流量涌进来规律全变模型追赶永远慢半拍。我一直盯着在线学习里的一个理想目标——Best-of-Both-WorldsBOBW也就是让同一个算法既能在随机环境拿到对数遗憾又能在对抗环境保持次线性遗憾。最近读到一篇 NIPS/NeurIPS 2025 论文标题非常直白Follow-the-Perturbed-Leader Nearly Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit。它说的是那个被很多人当成经典但不够强的 Follow-the-Perturbed-LeaderFTPL算法经过合适的设计居然能在 m-Set 半强盗semi-bandit问题下接近两全其美。这篇文章写给正在做组合决策、在线学习或者在实际系统里被非平稳流量折磨的朋友。我会把问题设定、FTPL 的核心机制、所谓Nearly到底损失在哪里以及我复现这类算法时踩过的坑一次性讲透。你可以把它当作一篇论文阅读笔记也可以当作一份带批判视角的入门指南。1. 先把问题说清楚m-Set半强盗到底在解什么1.1 从单臂选择到组合选择反馈却仍然细粒度经典多臂老虎机每轮只允许你选一个臂然后观测这个臂的奖励。m-Set 半强盗把动作空间变成所有大小为 m 的子集你每轮从 K 个基臂中选一个含 m 个基臂的集合然后观测这个集合里每一个基臂的反馈集合层面的收益通常视为所选基臂收益之和。用内容推荐来类比每轮给用户展示 m 个内容位用户是否点击是 item 级别的反馈广告系统里一次请求选 m 个广告位每个位置的曝光收益可以单独统计通信调度里选 m 个频段传数据每个频段的信道质量也是单独测量的。这些都是很自然的 semi-bandit 场景。半强盗的半指的是反馈粒度你看到了所选 m 个基臂的完整反馈但没选的那 K-m 个基臂完全不可见。这介于全信息所有 K 个臂都可见和经典强盗只看一个总和反馈之间。这个中间地带最有意思的地方在于动作空间巨大但反馈带结构算法可以在基臂层面做更新。1.2 动作空间坍缩的诱惑与陷阱很多人第一反应是既然只有 C(K, m) 个可能的子集那把每个子集当成一个独立超级臂不就行了理论上可以实际完全不行。K100、m5 时C(100,5) 已经接近 7500 万个动作。就算你只是维护一个权重向量每轮遍历所有动作都做不到更别提 EXP3 类型的算法还要对全部动作归一化、采样。semi-bandit 结构真正的价值在于如果集合收益是线性可加的那么最优集合必然是前 m 个最优基臂的组合。也就是说问题可以降维到 K 个基臂层面的优化而不是在组合空间里做优化。FTPL 之所以能扩展到这种场景正是因为它天然做的是基臂打分、取前 m 个这种操作。这里有一个容易忽略的陷阱线性可加性要求收益/损失在基臂层面是固定独立的。如果基臂之间存在强交互比如两个广告同时展示时互相压点击率问题就从半强盗变成了更难的组合在线学习FTPL 也不见得还能保持干净的遗憾界。所以读这篇论文时始终要记住它的前提是线性回报。1.3 为什么两全其美不是顺手就有的性质随机环境里最优算法应该逐渐锁定最优集合遗憾期望是 O(log T) 量级对抗环境里任何算法的遗憾都会被 Ω(√T) 限制住能达到 O(√T log T) 已经是好成绩。问题在于这两类目标需要的探索策略正好相反。随机环境希望探索量随时间衰减这样后期能越选越准对抗环境则要求一直保持一定的探索剂量否则对手可以在你锁定某个集合之后连续攻击它。一个固定参数的算法很难同时满足两种剂量需求。经典做法是设计一个环境检测器先判断现在是随机还是对抗再决定用哪套策略——但检测器本身有延迟切换瞬间往往就是最大的 regret 来源。BOBW 算法的真正评价标准是算法在不知道环境类型的前提下它的遗憾上界能否分别匹配两种环境各自的最优界。这比单环境调参好用要苛刻得多。所以当一个论文标题里出现 BOBW 时它不是在讲一个工程 trick而是在证明一个对两个动态过程同时成立的数学上界。2. FTPL是个老算法但它的结构被低估了2.1 算法主流程给历史损失加一点噪声再选前m个FTPL 的基本流程非常简单。假设我们用损失而不是收益每轮开始时维护每个基臂 i 的累积损失估计 L_{i, t-1}然后做四步独立采样一组扰动 ξ_i常见的是指数分布或伽马分布也有用高斯分布的变体。对每个基臂计算扰动后的分数S_i L_{i, t-1} ξ_i。选出分数最小的 m 个基臂作为本轮动作 A_t如果是最小化损失。观测 A_t 中每个基臂的真实损失更新累积损失 L_{i,t} L_{i,t-1} ℓ_{i,t}。给累积损失加噪声而不是给瞬时损失加噪声这是 FTPL 和 ε-greedy 式探索最本质的区别。ε-greedy 每轮独立地随机乱选扰动加在动作上FTPL 的扰动加在历史状态上决策本身仍然是确定性跟随最优只是最优的标准被噪声改写了。换个角度看扰动相当于给每个基臂一个信用浮动值。一个基臂累积损失稍微大一点但随机扰动给它一个大的负向浮动它仍可能被选中。m 越大这种随机化在组合层面造成的集中式探索越温和——你很少会选出一个和当前最优完全不相干的集合因为 m 个基臂同时被扰动抬上来的概率不高。对组合动作来说这比逐个动作做独立的随机探索要聪明得多。2.2 扰动在play两个角色探索和稳定如果说 FTLFollow-the-Leader不扰动是班里永远模仿上次考第一的同学那 FTPL 就是在每次考试前给每个同学的历史成绩单上偷偷加一点随机分。它有两个同时生效的效果。第一个效果是探索扰动让算法有机会选到历史次优但在当前噪声下分数更低的集合。扰动分布的方差越大探索强度越大。这一点大家都懂。第二个效果不那么明显扰动让决策边界变模糊从而让算法对历史损失的变化不那么敏感。当一个基臂的损失突然变大时FTL 会立刻把它踢出集合这种剧烈切换在对抗环境里很危险——对手可以通过构造损失序列来反复折腾你。FTPL 因为每个臂都有随机偏移只有损失差超过扰动幅度时才会导致集合切换而且切换发生在扰动较小的成员之间带有随机性对手不容易精确预测你的下一轮动作。从这个意义上说FTPL 的扰动既是探索剂也是缓冲垫。这就是为什么它能同时处理随机和对抗两种环境的雏形原因在随机环境下真实损失差稳定之后扰动只负责很少的额外探索在对抗环境下扰动提供的模糊性让算法不轻易被虚假历史带偏。2.3 稳定性-遗憾权衡FTPL分析里最重要的一课学过 FTPL 的人都知道它的遗憾分析几乎都建立在一个稳定性引理上。这个引理通常长这样如果某轮把累积损失只加一小段增量扰动后的最优集合没有发生剧烈变化那么你这一轮的后悔可以被限制在扰动幅度和损失变化量的某个函数之内。换句话说分析分两步走。稳定性项控制决策集合随历史变化而跳变的频率和幅度带来的后悔。偏差项控制扰动本身导致你总选到次优集合带来的额外后悔。扰动越大稳定性越好但偏差越大扰动越小偏差越小但稳定性变差。这正是 FTPL 的统一视角随机环境下最优集合稳定存在稳定性项会自然变小对抗环境下损失变化剧烈需要更大的扰动来压制稳定性项。算法本身不切换机制全靠扰动大小这个旋钮在两种模式间连续过渡。理解了这个权衡你就能理解为什么论文用 Nearly 这个定语。几乎所有 FTPL 的 BOBW 分析都会在随机界上多出一个来自扰动的额外项——扰动不能衰减到零否则对抗性不成立但扰动保持正数就永远存在着微小的随机探索损耗。这个损耗可以做到对数界里的低阶项或常数项但很难完全消除。3. 拆解Nearly Achieves遗憾界到底给了什么3.1 随机环境那一侧对数遗憾与额外因子随机环境下每个基臂的损失具有期望 μ_i最优基臂是期望最小的那一组。只要你做的是累积损失扰动然后选最小最终算法会以高概率把选择集中在最优集合附近。从传统 FTPL 分析角度来看随机环境里算法的遗憾大概长这样主要由误把次优集合当成最优的次数决定。每选一次次优集合损失的期望差距累加一次。随着 T 增大累积损失差不断拉开扰动被稀释选错概率指数下降最终遗憾是 O(log T / Δ_min) 量级其中 Δ_min 是最优集合和次优集合之间的期望损失差。但Nearly的代价通常藏在两处如果扰动方差设成一个正的常数为了兼顾对抗性那么随机环境下始终有一小撮轮次会出于扰动而选次优集合这在界上表现为一个不随 T 消失的常数项或者让对数项的常数变大。如果扰动方差随 T 衰减则随机界更干净但对抗界会变差因为它需要扰动保持足够大才能应对突然的损失跳变。论文的做法大概率是选择一种自适应扰动或者特殊分布让扰动大小依赖观测到的损失二阶矩从而在随机数据下自动收缩、在对抗数据下自动撑开。这样随机界勉强保住了对数级别但也因此付出了一些常数因子。标题里的 Nearly 实际上就是在坦白还不是常数意义上最优的 BOBW但已经是同数量级内最好的那档。3.2 对抗环境那一侧次线性遗憾与组合代价对抗环境里对手每轮可以任意选择损失向量甚至可以看着你的决策来构造下一轮损失。你可以想象一个恶意考官专挑你上次选中的集合来增加损失让你每次换都不对。FTPL 在对抗环境下的表现依赖一个关键事实因为决策含噪对手无法精确确定你下一步会选哪个集合只能对扰动后的最大概率集合做攻击。对抗遗憾界通常会包含 T 的 1/2 次方因子再乘上集合大小 m 和基臂数量 K 的一些根号项。直观理解m 越大每次决策牵涉的基臂越多损失的方差和对手可攻击面越大K 越大需要比较的候选越多决策不稳定性的风险越高。FTPL 这类算法在对抗环境里不会是最优常数但能保证 √T 量级。对于组合半强盗问题这已经是相当好的结果因为问题维度远比单臂老虎机复杂。论文在对抗侧的界如果能做到 O(m√(KT log K)) 或者相近量级那基本达到了不丢组合结构信息的理想状态。3.3 同一个统一框架怎么同时压住两个界BOBW 分析最迷人的地方在于你不需要先运行一个环境分类器而只需要在遗憾分解里写出一个同时包含随机性二阶矩和对抗性偏差的表达式。具体来说随机环境会让样本方差项很小各项中的方差/期望差距组合自动变成对数项对抗环境不保证方差小但可以用绝对值控制把界压到 √T。也就是说同一个界表达式因为环境不同而自动降落到不同的量级上。我在读这类论文时最关注的就是作者到底在哪个位置引入自适应的是扰动尺度随观测变化还是损失估计里的重要性权重随方差变化或者是分析中用到了某一类势函数。这篇文章按标题来看核心落在扰动机制本身——FTPL 的扰动天然构成一种连续的、指数族的形式让两种环境的界可以被同一组稳定性引理覆盖。这是它在结构上比检测器路线优雅的原因。4. 从读到懂让FTPL跨界的三个关键技术选择4.1 扰动尺度随数据的二阶矩自适应如果扰动尺度是固定的想同时拿随机界和对抗界非常困难。一种我见过的常见设计是扰动方差 λ_t 跟历史累积损失的波动幅度挂钩。你可以计算最近一段时间内损失向量的二阶矩估计方差涨了就加大扰动方差小了就减小扰动。这里的直觉是随机环境下损失波动小自然扰动被压低算法更接近锁定最优集合对抗环境下损失被人为制造出大波动扰动自动变大算法被迫多手准备。这种自适应和显式检测环境最大的不同是它没有二元切换而是连续调整。连续性的好处是边界处不会出现 abrupt 切换带来的瞬时后悔峰值。4.2 基臂级损失估计与截断m-Set 半强盗的反馈天然是基臂级的你选了哪个基臂就能看到它的损失。这个特性让损失估计变得简单——不需要像经典 bandit 那样构造复杂的 importance-weighted 估计。但为了在对抗环境下控制 variance一般需要用到重要性采样某个基臂 i 在当前决策集合中用 1/Pr(i∈A_t) 对观测损失进行加权得到无偏估计。这个权重可能非常大如果某个基臂很少被选中它的重要性权重会爆炸。所以必须配合截断操作比如把权重限制在某个阈值 W_max 内。截断会引入偏差但这个偏差通常可以被纳入 FTPL 稳定性引理里截断权重导致的估计偏差等价于在累积损失上多了一层扰动反而能与扰动分析合并处理。复现的时候要特别注意截断阈值的选择。阈值太大方差控制不住阈值太小低选择概率的基臂永远得不到有效的估计更新算法对它们的判断停留在先验。这个阈值在论文里一般和 m、K、T 的依赖关系写得很细抄代码时不能只抄数值要跟着理论式子一起缩放。4.3 不做显式切换连续内插比硬切换优雅传统 BOBW 思路有两种主流一是设计检测器判断当前环境是随机还是对抗然后调用对应的策略模块二是用时间窗滑动动态调整学习率。检测器路线的问题是检测需要样本而检测到对抗时往往已经在对抗开始后浪费了一批后悔更麻烦的是在边界处检测器输出不稳定策略反复横跳后悔就会叠加。FTPL 路线本质是鲁棒优化思路它并不试图知道现在处于什么环境而是构造一个在所有环境上都不会太差的策略。扰动尺度的自适应让人怀疑它也在做检测但它并不输出随机/对抗这个离散判断而是连续地改变探索强度。这避免了硬切换的边界问题。这种设计还带来一个额外好处可解释性和调试简单。你可以把每一轮的扰动方差画出来观察它如何跟随数据波动。某厂线上跑模型时如果只看策略切换日志经常一头雾水但画出扰动强度曲线一眼就能看出模型是不是感知到了流量异常。这在工程调优上是非常实用的性质。5. 复现和落地时容易踩的坑5.1 采样分布细节与数值溢出FTPL 最常用的扰动分布是指数分布或伽马分布。指数分布的无记忆性在数学分析里非常好用很多推导能出封闭形式。但实际编程时从指数分布采一个大数作为扰动再和累积损失相加很容易出现浮点问题。尤其当累积损失已经积累到几千而扰动只有个位数量级时扰动就完全被浮点精度吃掉了。我的建议是在一开始就把累积损失和扰动放在同一个尺度下设计可以定期做一次损失平移所有臂同时减去当前最小累积损失这样累积损失不会无限增长扰动始终有足够的相对精度。这一步理论上不改变算法行为因为所有臂同步平移不影响排序但数值稳定性提升非常明显。5.2 累积损失漂移时扰动尺度如何标定如果你直接把论文里的扰动参数搬到自己的数据上大概率会出事。因为论文的 λ 往往是一个依赖 K、m、T 的表达式T 在你的实验里可能只有论文的一个零头λ 也会差出几个数量级。正确的做法是按扰动幅度与相邻最优集合的期望损失差的比例来标定。你可以先跑几轮热身估计一下次优集合与最优集合之间的损失差分布然后让扰动方差落在该差距的 1/3 到 1 之间。这样既保证了对随机噪声的鲁棒性又不至于让探索完全淹没决策信号。我通常会在正式实验前做一个小的参数扫描而不是直接信任默认值。5.3 混合环境评测的陷阱与方法BOBW 论文的实验里最喜欢用先随机后对抗的拼接序列前半段数据 iid后半段数据被对手操纵。这种设计有它的合理性能直观看出算法切换能力。但复现时要注意切换时刻的选择会强烈影响平均遗憾曲线。如果你在随机段已经积累了足够大的损失差切换到对抗段后算法要花相当长时间才能忘掉原来的偏好如果随机段太短算法还没收敛就切换对抗遗憾会显得很大。建议你在不同切换点、不同 m/K 组合下分别跑并报告完整序列的平均遗憾和切换后 w 步内的亚线遗憾两个指标。只给一个总平均数看不出算法真实的切换能力。另外对抗序列的构造方式也对结果影响很大。经典做法是选择每轮让上轮算法最可能选择的集合损失变大也就是在线式对抗。自己实现时不要图省事写一个固定攻击序列那其实等于随机环境加噪声测不出对抗性。6. 跟两条经典BOBW路线对比一下6.1 邻域探索路线的取舍邻域探索neighborhood exploration思路是只在一个候选最优集合的邻域内做探索。随机环境下探索范围小损失可控对抗环境下即使当前候选被攻击邻域里还有足够多的次优集合可以顶上来。这种方法的优势是随机界的常数往往很漂亮因为它把探索限制在很小的集合内。劣势是实现复杂度高你要自己定义邻域的结构并且证明邻域足够覆盖所有可能的对抗攻击面。对于 m-Set 这种组合结构邻域定义要同时考虑替换哪个基臂、替换成哪些候选基臂细节非常多扩展一个新的动作空间限制就要重新设计。6.2 显式切换检测路线的取舍检测器路线的典型结构是一个随机性检验器比如检测损失均值是否稳定一个策略选择器。优势是概念清晰随机环境里可以放手使用非常激进的低探索算法遗憾界可以做到常数量级很优。劣势前面也说了检测滞后和边界振荡。更隐蔽的问题是检测器本身也消耗正则。你每多一个检测自由度就多一个可供对抗对手利用的维度——对手可以精准卡在检测器切换之前给你致命打击。理论上处理这种问题往往要加额外的随机化绕一圈又回到了类似 FTPL 的老路。6.3 一张小表总结三条路线路线是否需要显式检测随机环境界对抗环境界实现复杂度我的落地感受邻域探索否对数级常数较优√T 级需要精心设计邻域高理论干净但难推广显式检测切换是对数级可做到最优常数√T 级中调试直观边界头疼FTPL 自适应扰动否对数级带额外低阶项√T 级低工程友好解释性好从表格里能看出来FTPL 这条路线最大的卖点不是任何一个单独指标领先而是它在所有指标上都不瘸腿。尤其对想快速在内部系统里做实验的人来说算法简单本身就是一个巨大的优势——几行代码就能复现不用维护一整套检测器和策略切换状态机。7. 我读完后想继续做的几个方向这篇文章留下最让我在意的问题就是标题那个Nearly。如果能去掉这个 Nearly让随机界和对抗界同时达到常数最优那几乎就是组合半强盗 BOBW 的终局答案。我猜后续工作会集中在扰动分布的选择上某些重尾分布可能在稳定性引理里给出更紧的常数。另外高概率遗憾界而不是期望遗憾界目前在很多 BOBW 工作里都不够干净FTPL 这种基于独立扰动的结构恰好擅长做高概率分析这也是一个自然的延伸。从应用角度我更想做的是把 m-Set 的线性模型推广到带权重的凸组合动作比如推荐系统里每次给一个 item 分配不同的展示概率而不是硬性选 m 个。这个泛化需要重新推导稳定性引理中的凸对偶部分但 FTPL 的排序后取 top-m会变成向量内积 扰动后的 projection这在工程上也有现成的算子可以用。实际动手做个简单复现只需要几百行代码给我带来的感悟很朴素所谓算法创新很多时候是把一个老工具放在新的约束条件下重新审视。FTPL 从在线学习早期就存在但在 m-Set 半强盗的 BOBW 分析里它反而是最能打的。如果你的业务场景也是平稳期和波动期交替出现与其维护一堆检测器和切换逻辑不如先试试 FTPL 这种自带缓冲的算法——把扰动曲线画出来看看它是不是已经悄悄替你做完了环境感知。