提出一种高效无耦合算法，实现双线性鞍点问题的稳定收敛。
Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback
- 基于实验设计与FTRL框架，设计带几何适配正则的无耦合算法。
- 在仅获随机反馈下，以$ ilde{O}(T^{-1/4})$速率收敛至纳什均衡。
- 适用于需低计算开销的在线学习场景，如大规模博弈建模。
本文研究双线性鞍点问题中学习算法的最后迭代收敛性，该概念能刻画学习动态的日常行为。我们关注玩家从紧凸集选择动作且仅接收带子反馈的挑战性设定。主要贡献是设计了一种无耦合学习算法，可高概率保证最后迭代收敛至纳什均衡。我们建立了$ ilde{O}(T^{-1/4})$的收敛速率，包含问题参数的多项式因子。关键的是，所提算法计算高效，仅需对玩家动作集使用高效的线性优化预言机。该算法通过结合实验设计与经典跟随正则化领导者（FTRL）框架，并采用针对各学习者动作集几何结构精心设计的正则化函数获得。
原文摘要 · Abstract (English)
In this paper, we study last-iterate convergence of learning algorithms in bilinear saddle-point problems, a preferable notion of convergence that captures the day-to-day behavior of learning dynamics. We focus on the challenging setting where players select actions from compact convex sets and receive only bandit feedback. Our main contribution is the design of an uncoupled learning algorithm that guarantees last-iterate convergence to the Nash equilibrium with high probability. We establish a convergence rate of $\tilde{O}(T^{-1/4})$ up to polynomial factors in problem parameters. Crucially, our proposed algorithm is computationally efficient, requiring only an efficient linear optimization oracle over the players' compact action sets. The algorithm is obtained by combining techniques from experimental design and the classic Follow-The-Regularized-Leader (FTRL) framework, with a carefully chosen regularizer function tailored to the geometry of the action set of each learner.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。