Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information

• URL: http://arxiv.org/abs/2101.04667v2
• Date: Thu, 4 Feb 2021 14:45:34 GMT
• Title: Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information
• Authors: Angeliki Giannou, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos
• Abstract summary: We examine the Nash equilibrium convergence properties of no-regret learning in general N-player games. We establish a comprehensive equivalence between the stability of a Nash equilibrium and its support. It provides a clear refinement criterion for the prediction of the day-to-day behavior of no-regret learning in games.
• Score: 32.384868685390906
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we examine the Nash equilibrium convergence properties of no-regret learning in general N-player games. For concreteness, we focus on the archetypal follow the regularized leader (FTRL) family of algorithms, and we consider the full spectrum of uncertainty that the players may encounter - from noisy, oracle-based feedback, to bandit, payoff-based information. In this general context, we establish a comprehensive equivalence between the stability of a Nash equilibrium and its support: a Nash equilibrium is stable and attracting with arbitrarily high probability if and only if it is strict (i.e., each equilibrium strategy has a unique best response). This equivalence extends existing continuous-time versions of the folk theorem of evolutionary game theory to a bona fide algorithmic learning setting, and it provides a clear refinement criterion for the prediction of the day-to-day behavior of no-regret learning in games

Related papers

• The Power of Perturbation under Sampling in Solving Extensive-Form Games [56.013335390600524]
  This paper investigates how perturbation does and does not improve the Follow-the-Regularized-Leader (FTRL) algorithm in imperfect-information extensive-form games. Perturbing the expected payoffs guarantees that the FTRL dynamics reach an approximate equilibrium. We show that in the last-iterate sense, the FTRL consistently outperforms the non-samplinged FTRL.
  arXiv  Detail & Related papers  (2025-01-28T00:29:38Z)
• Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions [11.793922711718645]
  We address payoff-based decentralized learning in infinite-horizon zero-sum Markov games. In this setting, each player makes decisions based solely on received rewards, without observing the opponent's strategy or actions nor sharing information. By establishing novel properties of the value and policy updates induced by the Tsallis entropy regularizer, we prove finite-time convergence to an approximate Nash equilibrium.
  arXiv  Detail & Related papers  (2023-12-13T09:31:30Z)
• The equivalence of dynamic and strategic stability under regularized learning in games [33.74394172275373]
  We examine the long-run behavior of regularized, no-regret learning in finite games. We obtain an equivalence between strategic and dynamic stability. We show that methods based on entropic regularization converge at a geometric rate.
  arXiv  Detail & Related papers  (2023-11-04T14:07:33Z)
• Nash Equilibria and Pitfalls of Adversarial Training in Adversarial Robustness Games [51.90475640044073]
  We study adversarial training as an alternating best-response strategy in a 2-player zero-sum game. On the other hand, a unique pure Nash equilibrium of the game exists and is provably robust.
  arXiv  Detail & Related papers  (2022-10-23T03:21:01Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• On the Nash equilibrium of moment-matching GANs for stationary Gaussian processes [2.25477613430341]
  We show that the existence of consistent Nash equilibrium depends crucially on the choice of the discriminator family. We further study the local stability and global convergence of gradient descent-ascent methods towards consistent equilibrium.
  arXiv  Detail & Related papers  (2022-03-14T14:30:23Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  We propose a general meta learning approach to computing approximate Nash equilibrium for finite $n$-player normal-form games. Unlike existing solutions that approximate or learn a Nash equilibrium from scratch for each of the games, our meta solver directly constructs a mapping from a game utility matrix to a joint strategy profile.
  arXiv  Detail & Related papers  (2021-08-17T07:06:46Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
  arXiv  Detail & Related papers  (2021-02-23T05:11:07Z)
• On Information Asymmetry in Competitive Multi-Agent Reinforcement Learning: Convergence and Optimality [78.76529463321374]
  We study the system of interacting non-cooperative two Q-learning agents. We show that this information asymmetry can lead to a stable outcome of population learning.
  arXiv  Detail & Related papers  (2020-10-21T11:19:53Z)
• 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)

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.