Related papers: Learning in nonatomic games, Part I: Finite action spaces and population games

Learning in nonatomic games, Part I: Finite action spaces and population games

URL: http://arxiv.org/abs/2107.01595v1
Date: Sun, 4 Jul 2021 11:20:45 GMT
Title: Learning in nonatomic games, Part I: Finite action spaces and population games
Authors: Saeed Hadikhanloo and Rida Laraki and Panayotis Mertikopoulos and Sylvain Sorin
Abstract summary: We examine the long-run behavior of a wide range of dynamics for learning in nonatomic games, in both discrete and continuous time. We focus exclusively on games with finite action spaces; nonatomic games with continuous action spaces are treated in detail in Part II of this paper.
Score: 22.812059396480656
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We examine the long-run behavior of a wide range of dynamics for learning in nonatomic games, in both discrete and continuous time. The class of dynamics under consideration includes fictitious play and its regularized variants, the best-reply dynamics (again, possibly regularized), as well as the dynamics of dual averaging / "follow the regularized leader" (which themselves include as special cases the replicator dynamics and Friedman's projection dynamics). Our analysis concerns both the actual trajectory of play and its time-average, and we cover potential and monotone games, as well as games with an evolutionarily stable state (global or otherwise). We focus exclusively on games with finite action spaces; nonatomic games with continuous action spaces are treated in detail in Part II of this paper.

Related papers

Logit-Q Dynamics for Efficient Learning in Stochastic Teams [1.3927943269211591]
We present a new family of logit-Q dynamics for efficient learning in games. We show that the logit-Q dynamics presented reach (near) efficient equilibrium in teams with unknown dynamics.
arXiv Detail & Related papers (2023-02-20T07:07:25Z)
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)
Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
arXiv Detail & Related papers (2022-11-29T05:16:41Z)
Online Learning in Periodic Zero-Sum Games [27.510231246176033]
We show that Poincar'e recurrence provably generalizes despite the complex, non-autonomous nature of these dynamical systems.
arXiv Detail & Related papers (2021-11-05T10:36:16Z)
From Motor Control to Team Play in Simulated Humanoid Football [56.86144022071756]
We train teams of physically simulated humanoid avatars to play football in a realistic virtual environment. In a sequence of stages, players first learn to control a fully articulated body to perform realistic, human-like movements. They then acquire mid-level football skills such as dribbling and shooting. Finally, they develop awareness of others and play as a team, bridging the gap between low-level motor control at a timescale of milliseconds.
arXiv Detail & Related papers (2021-05-25T20:17:10Z)
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)
Follow-the-Regularized-Leader Routes to Chaos in Routing Games [23.497377573947382]
We study the emergence of chaotic behavior of Follow-the-Regularized Leader (FoReL) dynamics in games. We show the existence of novel non-standard phenomena such as the coexistence of stable Nash equilibria and chaos in the same game. Although FoReL dynamics can be strange and non-equilibrating, we prove that the time average still converges to an exact equilibrium for any choice of learning rate and any scale of costs.
arXiv Detail & Related papers (2021-02-16T06:40:31Z)
Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
We present volume analyses of Multiplicative Weights Updates (MWU) and Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as coordination games. We show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. We also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed: OMWU expands volume exponentially fast, whereas MWU contracts.
arXiv Detail & Related papers (2020-05-28T13:47:09Z)
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.