Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium

2021/04/26 by Yu-Guan Hsieh, Kimon Antonakopoulos, Hsieh, Yu-Guan +3 · 6 citations
Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2104.12761

openalex publication_date 2021/04/26 · openalex created_date 2021/05/10 · openalex updated_date 2026/07/28

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).

Citations

• Fast Convergence of Regularized Learning in Games
• Learning in games with continuous action sets and unknown payoff functions
• A Variational Inequality Perspective on Generative Adversarial Networks
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• On the robustness of learning in games with stochastically perturbed\n payoff observations
• On the convergence of single-call stochastic extra-gradient methods
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• Adaptive extra-gradient methods for min-max optimization and games

Cited by

• Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies
• Robust equilibria in continuous games: From strategic to dynamic robustness
• Multi-agent learning under uncertainty: Recurrence vs. concentration
• Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
• Grouped Satisficing Paths in Pure Strategy Games: a Topological Perspective
• Last-Iterate Convergence in Adaptive Regret Minimization for Approximate Extensive-Form Perfect Equilibrium

Related

• No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation
• No-regret Learning in Cournot Games
• Is Learning in Games Good for the Learners?
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games
• Pointwise Convergence in Games with Conflicting Interest