强腐败对抗线性赌博机：CRW-FTRL实现近极小极大最优遗憾

对抗线性赌博机（adversarial linear bandits）是序贯决策中的经典模型，但当奖励观测被恶意篡改时，传统算法的理论保证会严重退化。一篇最新研究提出了CRW-FTRL算法，在强腐败模型下将遗憾上界提升至与无腐败最优速率同阶，并匹配了已知下界。

强腐败为何让经典算法失效

在强腐败设定中，自适应对手先选择奖励向量，而在看到学习者的动作后，强对手可以篡改每一轮的观测奖励，总篡改预算为已知常数 (C)。这种攻击模式直接击穿了对抗赌博机常用的重要性加权奖励估计：对手只需在采样概率极低的动作被选中的轮次注入腐败，每单位腐败就会被放大为采样概率的倒数倍。

这意味着，即使总腐败预算不大，算法也可能被少数关键轮次的扰动彻底误导。此前Liu等人给出的最佳上界为 (\tilde O(\sqrt{d^3T} + dC))，其主项比无腐败速率高出一个 (\sqrt{d}) 因子。能否达到 (\tilde O(d\sqrt{T} + dC)) 的遗憾，一直是该问题的开放点。

重要性加权估计是处理对抗赌博机反馈的常用技术：当算法以概率 (p_t(a)) 选择动作 (a) 并观测到奖励 (r_t(a)) 时，无偏估计器为 (\hat{r}_t(a) = r_t(a) \cdot \mathbb{I}{a_t = a} / p_t(a))。它让算法能够从仅有的被选动作反馈中无偏地估计所有动作的期望奖励，是FTRL、EXP3等算法的基石。然而，该估计器的方差与 (1/p_t(a)) 成正比，当某些动作被极低概率采样时，相应的估计会极度不稳定。在强腐败场景下，对手若精准地在这些低概率轮次注入误差，腐败量会被放大为原始值的 (1/p_t(a)) 倍，从而以很小的总预算造成巨大的累积偏差。因此，重要性加权估计在对抗恶意篡改时存在结构性脆弱性，需要从根本上重新设计估计器。

CRW-FTRL的核心设计

CRW-FTRL的全称是“半径加权跟随正则化领导者”（radius-weighted FTRL）。它没有沿用重要性加权，而是采用一种归一化核估计器来估计奖励，其对腐败的敏感度由每个动作的“半径”控制，而非采样概率的倒数。

这些半径具有非递减性质，并与采样分布一起通过一个单调对数行列式障碍问题联合求解。该设计的关键在于，正则化项中的负线性项能够同时抵消腐败偏差和每个比较器的估计误差。换句话说，算法把对抗腐败的鲁棒性编码进了正则化结构本身，而不是事后修补估计量。

跟随正则化领导者（FTRL） 是一类在线学习框架：每一轮，算法选择使“历史累积奖励估计减去正则化项”最大化的动作，即 (a_t = \arg\max_{a} \left( \sum_{s=1}^{t-1} \hat{r}_s(a) - R_t(a) \right))，其中 (\hat{r}_s) 是奖励估计，(R_t) 是正则化项。FTRL的遗憾分析通常将累积遗憾分解为估计误差项和正则化项，通过精心设计的正则化器（如对数行列式障碍函数）来控制算法的稳定性与探索。在腐败存在时，估计误差项会包含腐败带来的偏差，而正则化项的设计需要额外吸收这部分偏差。CRW-FTRL的贡献在于，它将半径权重融入正则化器，使得负线性项能够同时抵消腐败偏差和比较器的估计误差，从而在遗憾界中恢复无腐败的最优主项。

理论保证：匹配下界与无腐败速率

对于 (\mathbb{R}^d) 中的 (K) 个动作，CRW-FTRL以高概率对抗自适应对手取得 (\tilde O(\sqrt{dT\log K} + dC)) 的遗憾。这一上界的主项与已知最优的无腐败速率一致，腐败相关项 (dC) 则与 (\Omega(dC)) 下界在忽略对数因子后匹配。

将算法应用于一般紧致动作集的离散化，可得到 (\tilde O(d\sqrt{T} + dC)) 的遗憾，从而正式确定了强腐败下对抗线性赌博机的统计速率。从理论角度看，这解决了Liu等人遗留的开放问题，把主项的 (\sqrt{d}) 差距彻底消除。

在线学习中的下界用于刻画任何算法在给定问题类上所能达到的最优遗憾的极限。在无腐败的对抗线性赌博机中，已知的极小极大下界为 (\Omega(d\sqrt{T}))（忽略对数因子），而Liu等人在强腐败设定下证明了 (\Omega(dC)) 的腐败相关下界。CRW-FTRL的遗憾上界 (\tilde O(\sqrt{dT\log K} + dC)) 在忽略对数因子后与这两个下界均匹配，意味着它在统计上是速率最优的。特别地，腐败项 (dC) 与下界的匹配表明，算法对腐败的敏感度已经达到了信息论极限，无法再通过改进算法来降低腐败带来的额外代价。

方法启示与边界

这项工作传递出一个更普遍的信号：面对观测腐败，单纯依赖重要性加权的算法框架存在结构性缺陷，需要从估计器和正则化器两个层面同时重新设计。半径加权的思路提供了一种可复用的模板——用与动作相关的尺度参数替代全局的逆概率权重，从而限制单点腐败的放大效应。

需要说明的是，该结果目前建立在理论分析之上，实验验证和实际部署中的数值表现尚未在摘要中体现。此外，腐败预算 (C) 已知这一假设在实际场景中未必成立，如何在不完全知晓预算时保持近优遗憾，仍是值得关注的方向。