# Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback

arXiv: https://arxiv.org/abs/2112.02856 · HTML: https://mlsanity.com/paper/2112.02856/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 89 references that are in the map.
- First posted on arXiv 6 Dec 2021.

## Builds on (most cited first, 25 of 25)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020)
- [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018)
- [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018)
- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [An Asynchronous Parallel Stochastic Coordinate Descent Algorithm](https://mlsanity.com/paper/1311.1873/) (2013)
- [Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games](https://mlsanity.com/paper/2002.09806/) (2020)
- [Multi-scale exploration of convex functions and bandit convex optimization](https://mlsanity.com/paper/1507.06580/) (2015)
- [An optimal algorithm for bandit convex optimization](https://mlsanity.com/paper/1603.04350/) (2016)
- [Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization](https://mlsanity.com/paper/1512.08122/) (2015)
- [Bandit Convex Optimization: sqrt{T} Regret in One Dimension](https://mlsanity.com/paper/1502.06398/) (2015)
- [Finite composite games: Equilibria and dynamics](https://mlsanity.com/paper/1503.07935/) (2015)
- [Learning with minimal information in continuous games](https://mlsanity.com/paper/1806.11506/) (2018)
- [Distributed stochastic optimization via matrix exponential learning](https://mlsanity.com/paper/1606.01190/) (2016)
- [A distributed block coordinate descent method for training l1 regularized linear classifiers](https://mlsanity.com/paper/1405.4544/) (2014)

## Built on by (most cited first, 15 of 15)

- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2604.16087/) (2026)
- [Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback](https://mlsanity.com/paper/2602.21436/) (2026)
- [Is Thompson Sampling Susceptible to Algorithmic Collusion?](https://mlsanity.com/paper/2405.17463/) (2024)
- [Multi-User Contextual Cascading Bandits for Personalized Recommendation](https://mlsanity.com/paper/2508.13981/) (2025)
- [Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis](https://mlsanity.com/paper/2603.19648/) (2026)
- [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026)
- [Decentralized Contextual Bandits with Network Adaptivity](https://mlsanity.com/paper/2508.13411/) (2025)
- [Risk-Averse Learning with Varying Risk Levels](https://mlsanity.com/paper/2512.22986/) (2025)
- [Nonparametric Learning and Earning with One-Point Feedback under Nonstationarity](https://mlsanity.com/paper/2605.21263/) (2026)
- [Learning under Opponent Unawareness in Linear-Quadratic Stochastic Games](https://mlsanity.com/paper/2608.08268/) (2026)
- [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026)
- [Decentralized Bandit Learning of Markov Perfect Equilibria](https://mlsanity.com/paper/2610.14333/) (2026)

## Abstract (arXiv)

We consider online no-regret learning in unknown games with bandit feedback, where each player can only observe its reward at each time -- determined by all players' current joint action -- rather than its gradient. We focus on the class of textitsmooth and strongly monotone games and study optimal no-regret learning therein. Leveraging self-concordant barrier functions, we first construct a new bandit learning algorithm and show that it achieves the single-agent optimal regret of tildeTheta(n√T) under smooth and strongly concave reward functions (n ≥ 1 is the problem dimension). We then show that if each player applies this no-regret learning algorithm in strongly monotone games, the joint action converges in the textitlast iterate to the unique Nash equilibrium at a rate of tildeTheta(nT-1/2). Prior to our work, the best-known convergence rate in the same class of games is tildeO(n2/3T-1/3) (achieved by a different algorithm), thus leaving open the problem of optimal no-regret learning algorithms (since the known lower bound is Omega(nT-1/2)). Our results thus settle this open problem and contribute to the broad landscape of bandit game-theoretical learning by identifying the first doubly optimal bandit learning algorithm, in that it achieves (up to log factors) both optimal regret in the single-agent learning and optimal last-iterate convergence rate in the multi-agent learning. We also present preliminary numerical results on several application problems to demonstrate the efficacy of our algorithm in terms of iteration count.