No-regret learning in harmonic games: Extrapolation in the face of conflicting interests

• URL: http://arxiv.org/abs/2412.20203v1
• Date: Sat, 28 Dec 2024 16:28:13 GMT
• Title: No-regret learning in harmonic games: Extrapolation in the face of conflicting interests
• Authors: Davide Legacci, Panayotis Mertikopoulos, Christos H. Papadimitriou, Georgios Piliouras, Bary S. R. Pradelski,
• Abstract summary: We show that learning converges to a Nash equilibrium from any initial condition, and all players are guaranteed at most O(1) regret. Results provide an in-depth understanding of no-regret learning in harmonic games.
• Score: 45.94247914236653
• License:
• Abstract: The long-run behavior of multi-agent learning - and, in particular, no-regret learning - is relatively well-understood in potential games, where players have aligned interests. By contrast, in harmonic games - the strategic counterpart of potential games, where players have conflicting interests - very little is known outside the narrow subclass of 2-player zero-sum games with a fully-mixed equilibrium. Our paper seeks to partially fill this gap by focusing on the full class of (generalized) harmonic games and examining the convergence properties of follow-the-regularized-leader (FTRL), the most widely studied class of no-regret learning schemes. As a first result, we show that the continuous-time dynamics of FTRL are Poincar\'e recurrent, that is, they return arbitrarily close to their starting point infinitely often, and hence fail to converge. In discrete time, the standard, "vanilla" implementation of FTRL may lead to even worse outcomes, eventually trapping the players in a perpetual cycle of best-responses. However, if FTRL is augmented with a suitable extrapolation step - which includes as special cases the optimistic and mirror-prox variants of FTRL - we show that learning converges to a Nash equilibrium from any initial condition, and all players are guaranteed at most O(1) regret. These results provide an in-depth understanding of no-regret learning in harmonic games, nesting prior work on 2-player zero-sum games, and showing at a high level that harmonic games are the canonical complement of potential games, not only from a strategic, but also from a dynamic viewpoint.

Related papers

• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game. Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
  arXiv  Detail & Related papers  (2024-01-10T12:56:24Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium [33.9962699667578]
  No-regret algorithms are not created equal in terms of game-theoretic guarantees. We propose a range of no-regret policies based on optimistic mirror descent.
  arXiv  Detail & Related papers  (2021-04-26T17:52:29Z)
• Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [65.64512759706271]
  We study the existence of simple, uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games. We introduce a notion of trigger regret in extensive-form games, which extends that of internal regret in normal-form games. We give an efficient no-regret algorithm which guarantees with high probability that trigger regrets grow sublinearly in the number of iterations.
  arXiv  Detail & Related papers  (2021-04-04T02:26:26Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  We look at algorithms that ensure strong performance in hindsight relative to what could have been achieved with modified behavior. We develop and advocate for this hindsight framing of learning in general sequential decision-making settings. We present examples illustrating the distinct strengths and weaknesses of each type of equilibrium in the literature.
  arXiv  Detail & Related papers  (2020-12-10T18:30:21Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  We study the dynamics of "follow-the-regularized-leader" (FTRL) We show that any Nash equilibrium which is not strict cannot be stable and attracting under FTRL. This result has significant implications for predicting the outcome of a learning process.
  arXiv  Detail & Related papers  (2020-10-19T13:49:06Z)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
  We give the first uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games. We introduce a notion of trigger regret in extensive-form games, which extends that of internal regret in normal-form games. Our algorithm decomposes trigger regret into local subproblems at each decision point for the player, and constructs a global strategy of the player from the local solutions.
  arXiv  Detail & Related papers  (2020-04-01T17:39:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.