FTPL算法接近实现m-Set半强盗的Best-of-Both-Worlds

过去一年我在反复调一套推荐策略的时候，最大的挫败感来自环境不确定性：流量平稳时算法怎么调都显得聪明，一到活动流量涌进来，规律全变，模型追赶永远慢半拍。我一直盯着在线学习里的一个理想目标——Best-of-Both-Worlds（BOBW），也就是让同一个算法既能在随机环境拿到对数遗憾，又能在对抗环境保持次线性遗憾。最近读到一篇 NIPS/NeurIPS 2025 论文，标题非常直白：Follow-the-Perturbed-Leader Nearly Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit。它说的是：那个被很多人当成"经典但不够强"的 Follow-the-Perturbed-Leader（FTPL）算法，经过合适的设计，居然能在 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) 个可能的子集，那把每个子集当成一个独立"超级臂"不就行了？理论上可以，实际完全不行。K=100、m=5 时，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}，然后做四步：

1. 独立采样一组扰动 ξ_i（常见的是指数分布或伽马分布，也有用高斯分布的变体）。
2. 对每个基臂计算扰动后的分数：S_i = L_{i, t-1} + ξ_i。
3. 选出分数最小的 m 个基臂作为本轮动作 A_t（如果是最小化损失）。
4. 观测 A_t 中每个基臂的真实损失，更新累积损失 L_{i,t} = L_{i,t-1} + ℓ_{i,t}。

给累积损失加噪声而不是给瞬时损失加噪声，这是 FTPL 和 ε-greedy 式探索最本质的区别。ε-greedy 每轮独立地随机乱选，扰动加在动作上；FTPL 的扰动加在历史状态上，决策本身仍然是"确定性跟随最优"，只是最优的标准被噪声改写了。

换个角度看，扰动相当于给每个基臂一个"信用浮动值"。一个基臂累积损失稍微大一点，但随机扰动给它一个大的"负向浮动"，它仍可能被选中。m 越大，这种随机化在组合层面造成的"集中式探索"越温和——你很少会选出一个和当前最优完全不相干的集合，因为 m 个基臂同时被扰动抬上来的概率不高。对组合动作来说，这比逐个动作做独立的随机探索要聪明得多。

2.2 扰动在play两个角色：探索和稳定

如果说 FTL（Follow-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 一张小表总结三条路线

从表格里能看出来，FTPL 这条路线最大的卖点不是任何一个单独指标领先，而是它在所有指标上都不瘸腿。尤其对想快速在内部系统里做实验的人来说，算法简单本身就是一个巨大的优势——几行代码就能复现，不用维护一整套检测器和策略切换状态机。

7. 我读完后想继续做的几个方向

这篇文章留下最让我在意的问题就是标题那个"Nearly"。如果能去掉这个 Nearly，让随机界和对抗界同时达到常数最优，那几乎就是组合半强盗 BOBW 的终局答案。我猜后续工作会集中在扰动分布的选择上：某些重尾分布可能在稳定性引理里给出更紧的常数。另外，高概率遗憾界（而不是期望遗憾界）目前在很多 BOBW 工作里都不够干净，FTPL 这种基于独立扰动的结构恰好擅长做高概率分析，这也是一个自然的延伸。

从应用角度，我更想做的是把 m-Set 的线性模型推广到带权重的凸组合动作，比如推荐系统里每次给一个 item 分配不同的展示概率，而不是硬性选 m 个。这个泛化需要重新推导稳定性引理中的凸对偶部分，但 FTPL 的"排序后取 top-m"会变成"向量内积 + 扰动后的 projection"，这在工程上也有现成的算子可以用。

实际动手做个简单复现只需要几百行代码给我带来的感悟很朴素：所谓算法创新，很多时候是把一个老工具放在新的约束条件下重新审视。FTPL 从在线学习早期就存在，但在 m-Set 半强盗的 BOBW 分析里，它反而是最能打的。如果你的业务场景也是"平稳期和波动期交替出现"，与其维护一堆检测器和切换逻辑，不如先试试 FTPL 这种自带缓冲的算法——把扰动曲线画出来，看看它是不是已经悄悄替你做完了环境感知。