技术摘要：具有对手动作反馈的零和博弈的近最优最后迭代收敛

问题陈述

本文研究了在带宽反馈（bandit feedback）下双人零和博弈的学习问题，其中玩家仅观察到每轮中特定动作对产生的带噪声的损失/奖励，而非其混合策略的完整梯度。本工作的一个关键区别在于假设玩家除了观察到自身的损失外，还能观察到对手的动作。

主要目标是实现到纳什均衡的最后迭代收敛（last-iterate convergence），即随着轮次 $t \to \infty$，对偶间隙 $DGap(x_t, y_t) \to 0$。这与平均迭代收敛（时间平均策略的收敛）或随机迭代收敛不同，且比后者更强。

先前的研究在没有对手动作反馈的情况下，确立了平均迭代收敛与最后迭代收敛之间的严格分离：

• 平均迭代收敛：最优速率为 $O(t^{-1/2})$。
• 最后迭代收敛（无对手动作）：期望中的最优速率限制为 $O(t^{-1/3})$，高概率下的最优速率限制为 $O(t^{-1/4})$。

本文提出的核心问题是：观察对手动作这一额外信息是否能够实现更快的最后迭代收敛，特别是能否弥合差距，达到最优的 $O(t^{-1/2})$ 速率。

方法论

算法：PMO-LB

作者提出了带对数屏障正则化的分阶段极小极大优化算法（Phased Minimax Optimization with Log-Barrier Regularization, PMO-LB）。该算法在长度倍增的时段（epochs）中运行（从 $2^{s-1}$ 到 $2^s - 1$）。

1. 估计：在每个时段 $s$ 内，玩家收集数据以计算博弈矩阵 $A$ 的经验估计量 $\hat{A}_s$。
2. 策略更新：在每个时段开始时，玩家通过求解一个估计的对数屏障正则化博弈来计算新的混合策略对 $(x_s, y_s)$。收益函数定义为：
   $$\Phi_s(x, y) \triangleq x^\top \hat{A}_s y + \gamma_s \sum_{i=1}^d \log \frac{1}{x_i} - \gamma_s \sum_{j=1}^d \log \frac{1}{y_j}$$
   其中 $\gamma_s$ 是随时段衰减的学习率。
3. 执行：玩家在时段持续期间从 $(x_s, y_s)$ 中采样动作。
4. 独立性：尽管博弈具有耦合性质，但该算法是解耦的；每个玩家仅利用观察到的对手动作和自身的损失即可独立计算其策略。

分析方法

本文指出，带宽文献中的标准技术（包括硬消除和软消除）即使在有对手动作反馈的情况下，也无法推广到博弈问题。

• 硬消除：失效的原因在于，估计纯策略对 $(e_i, e_j)$ 的对偶间隙需要执行其他潜在的“糟糕”策略以寻找最佳响应，这与在每一轮都保持低遗憾的目标相悖。
• 标准软消除（FALCON 风格）：现有分析依赖于“低遗憾 - 低方差”属性，即动作估计的方差由其遗憾控制。作者表明，这一属性对于博弈而言是不够的，因为估计策略对的对偶间隙需要执行那些自身可能具有高对偶间隙的策略。

为了克服这一困难，作者基于乘性稳定性（multiplicative stability）开发了一种新颖的分析方法。

• 他们证明，连续的策略 $x_s$ 和 $x_{s-1}$（$y$ 同理）在高概率下是乘性接近的（即 $x_{s,i} \leq \alpha x_{s-1,i}$）。
• 这种稳定性由对数屏障正则化实现，它防止概率质量过快集中在部分动作上，从而控制了损失估计量的方差。
• 该分析建立了一种“低对偶间隙 - 低方差”属性，结合乘性稳定性，使得无需算法显式执行糟糕策略即可界定真实的对偶间隙。

主要贡献

1. 最优最后迭代收敛：本文证明，在具有对手动作反馈的情况下，可以实现高概率下的 $O(t^{-1/2})$ 最后迭代收敛。这匹配了平均迭代收敛的最优速率，有效地在此设定下弥合了两种收敛概念之间的差距。
2. 算法效率：所提出的算法计算高效，在 $t$ 轮后仅需 $\log t$ 次更新（求解鞍点优化问题）。
3. 理论新颖性：该工作指出了将单人带宽分析推广到多人博弈时的根本障碍。它引入了一种新的分析框架，依赖于连续策略间的乘性稳定性，这与以往基于遗憾的分析不同。
4. 决斗带宽（Dueling Bandits）的改进：作为博弈矩阵为斜对称矩阵（即决斗带宽）的特例，该结果为这一设定提供了首个最后迭代收敛保证，优于仅提供遗憾界限的先前工作。

结果

理论保证

定理 4.1：对于任意固定的 $\delta \in (0, 1)$，采用特定学习率调度的算法 2 保证以至少 $1-\delta$ 的概率：
$$DGap(x_t, y_t) = O\left( \frac{d^2 \sqrt{\log(d \log t / \delta)}}{\sqrt{t}} \right)$$
对所有 $t \geq 1$ 成立。这代表了 $t^{-1/2}$ 的收敛速率。

实验验证

作者在安全博弈基准（规模分别为 $61 \times 21$ 和 $39 \times 35$）上评估了 PMO-LB，并与五个基线进行了对比：

• 没有对手动作反馈的先前方法（Cai 等人 [2023, 2025]，Fiegel 等人 [2025, 2026]）。
• 一个利用对手动作但将经验最佳策略与均匀探索混合的朴素基线（算法 3）。

发现：

• PMO-LB 始终优于所有基线。
• 经验收敛斜率与理论预测相符：
  • PMO-LB：$\approx -0.5$（匹配 $t^{-1/2}$）。
  • 朴素基线：$\approx -0.25$（匹配 $t^{-1/4}$）。
  • 先前方法（无对手动作）：斜率范围从 $-0.175$到$-0.301$（匹配$t^{-1/8}$到$t^{-1/3}$）。

意义与主张

本文声称解决了一个长期存在的开放性问题，即对手动作信息对最后迭代收敛的影响。通过证明 $t^{-1/2}$ 的收敛是可以实现的，该工作表明，在带宽反馈设定中，最后迭代收敛这条“更艰难的路径”并非本质上比平均迭代收敛更慢，前提是对手的动作是可观测的。

作者强调，他们的贡献主要是理论和算法层面的。他们指出，虽然界限中的 $d^2$ 依赖关系可能并非最优，但 $t^{-1/2}$ 的速率在维度因子范围内是最优的。该工作还强调，其分析技术（通过对数屏障正则化实现的乘性稳定性）可能对单人带宽问题具有独立的兴趣，为现有的基于遗憾的分析提供了一种替代方案。

本文得出结论：观察对手动作从根本上缓解了实现最后迭代收敛所需的探索 - 利用张力，使得算法能够避免先前认为在带宽反馈设定中不可避免的缓慢速率。