Skip to Main content Skip to Navigation
Conference papers

Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium

Yu-Guan Hsieh 1 Kimon Antonakopoulos 2 Panayotis Mertikopoulos 2, 3 
1 DAO - Données, Apprentissage et Optimisation
LJK - Laboratoire Jean Kuntzmann
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : In game-theoretic learning, several agents are simultaneously following their individual interests, so the environment is non-stationary from each player's perspective. In this context, the performance of a learning algorithm is often measured by its regret. However, no-regret algorithms are not created equal in terms of game-theoretic guarantees: depending on how they are tuned, some of them may drive the system to an equilibrium, while others could produce cyclic, chaotic, or otherwise divergent trajectories. To account for this, we propose a range of no-regret policies based on optimistic mirror descent, with the following desirable properties: i) they do not require any prior tuning or knowledge of the game; ii) they all achieve O(√ T) regret against arbitrary, adversarial opponents; and iii) they converge to the best response against convergent opponents. Also, if employed by all players, then iv) they guarantee O(1) social regret; while v) the induced sequence of play converges to Nash equilibrium with O(1) individual regret in all variationally stable games (a class of games that includes all monotone and convex-concave zero-sum games).
Document type :
Conference papers
Complete list of metadata
Contributor : Panayotis Mertikopoulos Connect in order to contact the contributor
Submitted on : Monday, September 13, 2021 - 12:29:17 PM
Last modification on : Wednesday, July 6, 2022 - 4:23:07 AM


Files produced by the author(s)


  • HAL Id : hal-03342410, version 1


Yu-Guan Hsieh, Kimon Antonakopoulos, Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. COLT 2021 - the 34th Annual Conference on Learning Theory, Aug 2021, Boulder, United States. pp.1-34. ⟨hal-03342410⟩



Record views


Files downloads