Continuous-time convergence rates in potential and monotone games
From MaRDI portal
Publication:5081641
DOI10.1137/20M1381873zbMATH Open1492.91036arXiv2011.10682OpenAlexW3106705281MaRDI QIDQ5081641FDOQ5081641
Authors: Bolin Gao, Lacra Pavel 
Publication date: 17 June 2022
Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)
Abstract: In this paper, we provide exponential rates of convergence to the interior Nash equilibrium for continuous-time dual-space game dynamics such as mirror descent (MD) and actor-critic (AC). We perform our analysis in -player continuous concave games that satisfy certain monotonicity assumptions while possibly also admitting potential functions. In the first part of this paper, we provide a novel relative characterization of monotone games and show that MD and its discounted version converge with in relatively strongly and relatively hypo-monotone games, respectively. In the second part of this paper, we specialize our results to games that admit a relatively strongly concave potential and show AC converges with . These rates extend their known convergence conditions. Simulations are performed which empirically back up our results.
Full work available at URL: https://arxiv.org/abs/2011.10682
Recommendations
- On the rate of convergence of continuous-time fictitious play
- On best-response dynamics in potential games
- Generalized mirror descents with non-convex potential functions in atomic congestion games: continuous time and discrete time
- Continuous time learning algorithms in optimization and game theory
- The rate of convergence of continuous fictitious play
Cites Work
- Machine learning. A probabilistic perspective
- First-order methods in optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Title not available (Why is that?)
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- Higher order game dynamics
- Title not available (Why is that?)
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- Nash Equilibrium Seeking in Noncooperative Games
- Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria
- Saddle-point dynamics: conditions for asymptotic stability of saddle points
- Hedging under uncertainty: regret minimization meets exponentially fast convergence
- On best-response dynamics in potential games
- Information geometry and its applications
- Cycles in adversarial regularized learning
- Relatively smooth convex optimization by first-order methods, and applications
- Optimization methods for large-scale machine learning
- Learning in games via reinforcement and regularization
- Penalty-regulated dynamics and robust learning procedures in games
- Convergent multiple-timescales reinforcement learning algorithms in normal form games
- Distributed Nash Equilibrium Seeking by a Consensus Based Approach
- Mixed-Strategy Learning With Continuous Action Sets
- Convergence rate of \(\mathcal{O}(1/k)\) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems
- The approximate duality gap technique: a unified theory of first-order methods
- A Passivity-Based Approach to Nash Equilibrium Seeking Over Networks
- Continuous-Time Discounted Mirror Descent Dynamics in Monotone Concave Games
- On Passivity, Reinforcement Learning, and Higher Order Learning in Multiagent Finite Games
Cited In (2)
Uses Software
This page was built for publication: Continuous-time convergence rates in potential and monotone games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5081641)
