线性Bandit新突破：IAFTRL实现随机与对抗环境双优

线性bandit问题的核心挑战之一，是设计一种算法能同时在对抗环境和随机环境中表现最优——即所谓“两全其美”（best-of-both-worlds, BOBW）。近期一篇论文提出了IAFTRL（information-acquisition follow-the-regularized-leader），宣称这是首个纯FTRL框架下达到该目标的算法，一举解决了此前多个工作留下的开放问题。

为什么BOBW在线性Bandit中如此困难？

在有限动作集的线性bandit中，对抗环境要求算法保证 $\tilde{O}(\sqrt{T})$ 的遗憾，而随机环境则期望 $O(\log T)$ 级别的遗憾。传统上，这两类保证需要截然不同的算法设计：对抗算法通常基于FTRL或镜像下降，随机算法则依赖乐观估计或置信区间。BOBW的目标是让同一个算法自动适应环境，无需预先知道环境类型。

此前，针对有限动作集，已有工作（如Lee et al. 2021、Kong & Zhou 2023、Ito et al. 2023、Zhao et al. 2025）在特定条件下取得了进展，但始终未能给出一个纯FTRL框架下、在随机环境中达到实例依赖最优遗憾的BOBW算法。IAFTRL填补了这一空白。

线性bandit（Linear Bandit） 是多臂bandit问题的重要推广：每一轮算法从动作集 $\mathcal{A} \subset \mathbb{R}^d$ 中选择一个动作 $a_t$，观测到的奖励为 $r_t = \langle a_t, \theta^* \rangle + \eta_t$，其中 $\theta^$ 是未知参数向量，$\eta_t$ 是噪声。与有限臂bandit（每个臂独立）不同，线性bandit中动作之间存在线性结构关联，算法需要利用这种结构从部分反馈中推断 $\theta^$。这种设定广泛用于推荐系统、临床试验和广告投放等场景。线性bandit的难点在于：动作集可能连续或巨大，算法只能观测到所选动作的奖励（bandit反馈），因而需要精心设计探索策略来估计 $\theta^$。对抗环境和随机环境的区别在于奖励生成机制：随机环境中 $\eta_t$ 是零均值噪声且 $\theta^$ 固定；对抗环境中奖励可能由对手自适应地选择，甚至依赖历史。BOBW要求算法在两类环境中都接近最优，这对探索与利用的平衡提出了更高要求。

IAFTRL的核心思路：信息获取与正则化博弈

IAFTRL的全称是information-acquisition follow-the-regularized-leader。它延续了FTRL框架，但在正则化项的设计中显式融入了“信息获取复杂度”（information-acquisition complexity，记作 $\cstar$）。这个量刻画了线性bandit中实例依赖的最优性——直观上，它衡量了在给定动作集和未知参数下，获取足够信息以区分最优动作所需的成本。

算法通过动态调整正则化强度，使得在随机环境中遗憾以 $\tilde{O}(\cstar \log T)$ 增长，而在对抗环境中仍保持 $\tilde{O}(\sqrt{T})$ 的保证。关键在于，正则化项的设计同时兼顾了信息获取的几何结构与对损坏（corruption）的鲁棒性，这正是标题中“信息获取、损坏与几何的相互作用”所指。

FTRL（Follow-The-Regularized-Leader） 是在线学习中的经典框架：每一轮，算法选择使累积线性损失加上正则化项最小的决策，即 $x_{t+1} = \arg\min_x \left{ \sum_{s=1}^t \langle \ell_s, x \rangle + R_t(x) \right}$，其中 $R_t$ 是正则化项。FTRL的统一性使其成为设计BOBW算法的自然选择，因为通过调整正则化项可以灵活控制算法的稳定性与适应性。在bandit反馈下，损失梯度无法直接观测，通常需要使用重要性加权估计（如逆概率加权）来构造无偏梯度估计。IAFTRL的创新在于将信息获取复杂度融入正则化项的设计，使得正则化强度随实例的“信息获取难度”自适应变化：在信息获取容易的实例上使用更强的正则化以加速收敛，在困难实例上则放松正则化以保持探索。这种设计需要精细分析正则化项的几何性质（如强凸性、自和谐性）与信息获取复杂度之间的关系，从而在随机和对抗环境中同时获得最优遗憾界。

理论保证与开放问题的解决

论文证明了IAFTRL在随机环境下的遗憾上界为 $\tilde{O}(\cstar \log T)$ 型，其中 $\cstar$ 为信息获取复杂度。这一界是实例依赖最优的，意味着对于“简单”实例（信息获取容易），遗憾更小；对于“困难”实例，遗憾相应增大。同时，在对抗环境中，算法保证 $\tilde{O}(\sqrt{T})$ 遗憾，与纯对抗算法的最优界同阶。

这一结果直接解答了Lee et al. (2021)、Kong & Zhou (2023)、Ito et al. (2023) 以及Zhao et al. (2025) 中提出的开放问题：是否存在纯FTRL的BOBW算法能达到实例依赖最优的随机遗憾。IAFTRL给出了肯定答案。

几何与损坏：算法鲁棒性的来源

标题中“几何”与“损坏”并非修饰词。线性bandit的动作集具有几何结构（如多面体、球面），而FTRL的正则化项需要与这种几何相容，才能保证遗憾界不因动作集形状而恶化。此外，算法还需应对“损坏”（corruption）——即随机环境中的部分观测被恶意篡改。IAFTRL通过信息获取复杂度的自适应调整，在损坏存在时仍能维持接近最优的遗憾。

据论文所述，IAFTRL是首个在纯FTRL框架下同时处理信息获取、损坏和几何结构的BOBW算法。其分析融合了FTRL的稳定性与信息获取的实例依赖下界，为后续研究提供了新工具。

信息获取复杂度（information-acquisition complexity，$\cstar$） 是刻画线性bandit实例依赖最优遗憾的关键量。直观上，它衡量了在给定动作集和未知参数下，为区分最优动作所需的最少信息量。形式化地，$\cstar$ 通常与动作集的几何结构（如最优动作与次优动作之间的间隙）以及参数估计的方差有关。在随机线性bandit中，实例依赖最优遗憾下界通常可表示为 $\Omega(\cstar \log T)$ 的形式，其中 $\cstar$ 反映了问题的“难度”：如果最优动作很容易被识别（间隙大、动作集几何良好），则 $\cstar$ 较小；反之则较大。IAFTRL通过将 $\cstar$ 融入正则化项，使算法能够自动适应实例难度，从而在随机环境中达到 $\tilde{O}(\cstar \log T)$ 的遗憾上界。这一界与已知下界匹配（至对数因子），因此是实例依赖最优的。理解 $\cstar$ 需要一些线性代数和凸几何的背景，但核心思想是：它量化了“学习未知参数以找到最优动作”所需付出的统计代价。

对Bandit学习者的意义

对于关注在线学习与bandit算法的研究者和工程师，IAFTRL的价值在于它统一了两种看似矛盾的目标。实际应用中，环境往往在随机与对抗之间摇摆（例如推荐系统中的用户行为），BOBW算法能自动适应而不需要手动切换。IAFTRL的纯FTRL结构也意味着它易于实现和扩展，可能推动BOBW思想在更复杂模型（如上下文bandit、强化学习）中的落地。

当然，论文目前聚焦于有限动作集的线性bandit，向无限动作集或非线性模型的推广仍是开放方向。但就有限动作集而言，IAFTRL已经迈出了关键一步。

损坏（corruption） 在在线学习文献中通常指随机环境中的一部分观测被恶意篡改或受到对抗性干扰。具体到bandit设定，每轮奖励可能以一定概率被对手修改，或者存在一个总预算约束的对抗性扰动。损坏模型是连接纯随机环境和纯对抗环境的桥梁：当损坏量为零时，环境是纯随机的；当损坏量足够大时，环境可视为对抗的。BOBW算法若能在损坏存在时仍保持接近最优的遗憾，则说明其鲁棒性更强。IAFTRL通过信息获取复杂度的自适应调整来应对损坏：在检测到异常观测时，算法会调整正则化强度以降低对损坏数据的敏感度。理论分析表明，即使存在一定程度的损坏，IAFTRL的遗憾仍能保持在 $\tilde{O}(\cstar \log T + \sqrt{C T})$ 量级，其中 $C$ 是损坏总量。这一结果统一了随机和对抗设定，并提供了损坏与遗憾之间的平滑权衡。