在对手动作可见的博弈中,实现快速收敛的最优学习算法。
Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions
- 通过估计对偶障碍正则化博弈,稀疏更新策略以加速收敛。
- 在高概率下达到 t^(-1/2) 的最后迭代收敛速率,优于原有 t^(-1/3) 上限。
- 适用于偏好学习等需观察对手动作的实际场景,提升学习效率。
在仅有损失反馈的二人零和博弈中,前人证明平均迭代收敛可达 t^(-1/2) 率,但最后迭代收敛受限于期望下的 t^(-1/3) 与高概率下的 t^(-1/4)。然而,在许多实际场景(如偏好学习)中,玩家不仅获得自身损失,还可观测对手动作。本文回答该问题:额外信息能否加快最后迭代收敛?我们给出肯定答案,提出一种高效算法,在高概率下实现 t^(-1/2) 的最后迭代收敛,其核心是通过求解估计的对偶障碍正则化博弈来稀疏更新策略。我们识别出标准单玩家多臂赌博机分析无法直接推广至博弈的原因,并发展新分析框架克服障碍。实验表明,本算法显著优于基线与不利用对手动作反馈的方法。此外,结果也改进了具有反对称博弈矩阵的对决赌博机(dueling bandits)情形。
原文摘要 · Abstract (English)
Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. (2025) show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal t^(-1/2) rate after t rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than t^(-1/3) in expectation or t^(-1/4) with high probability. However, in many practical settings, such as preference learning, the players observe not only their loss but also the opponent's action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that t^(-1/2) last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits, the single-player case, from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。