No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
- URL: http://arxiv.org/abs/2004.00603v5
- Date: Fri, 2 Sep 2022 16:09:00 GMT
- Title: No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
- Authors: Andrea Celli, Alberto Marchesi, Gabriele Farina, Nicola Gatti
- Abstract summary: 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.
- Score: 76.78447814623665
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The existence of simple, uncoupled no-regret dynamics that converge to
correlated equilibria in normal-form games is a celebrated result in the theory
of multi-agent systems. Specifically, it has been known for more than 20 years
that when all players seek to minimize their internal regret in a repeated
normal-form game, the empirical frequency of play converges to a normal-form
correlated equilibrium. Extensive-form (that is, tree-form) games generalize
normal-form games by modeling both sequential and simultaneous moves, as well
as private information. Because of the sequential nature and presence of
partial information in the game, extensive-form correlation has significantly
different properties than the normal-form counterpart, many of which are still
open research directions. Extensive-form correlated equilibrium (EFCE) has been
proposed as the natural extensive-form counterpart to normal-form correlated
equilibrium. However, it was currently unknown whether EFCE emerges as the
result of uncoupled agent dynamics. In this paper, we give the first uncoupled
no-regret dynamics that converge to the set of EFCEs in $n$-player general-sum
extensive-form games with perfect recall. First, we introduce a notion of
trigger regret in extensive-form games, which extends that of internal regret
in normal-form games. When each player has low trigger regret, the empirical
frequency of play is close to an EFCE. Then, we give an efficient
no-trigger-regret algorithm. 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 at each decision point.
Related papers
- 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) - Learning in Multi-Player Stochastic Games [1.0878040851638]
We consider the problem of simultaneous learning in games with many players in the finite-horizon setting.
While the typical target solution for a game is a Nash equilibrium, this is intractable with many players.
We turn to a different target: algorithms which generate an equilibrium when they are used by all players.
arXiv Detail & Related papers (2022-10-25T19:02:03Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games.
We introduce a new algorithm for computing optimal equilibria in all three notions.
arXiv Detail & Related papers (2022-03-14T15:21:18Z) - 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) - Model-Free Online Learning in Unknown Sequential Decision Making
Problems and Games [114.90723492840499]
In large two-player zero-sum imperfect-information games, modern extensions of counterfactual regret minimization (CFR) are currently the practical state of the art for computing a Nash equilibrium.
We formalize an online learning setting in which the strategy space is not known to the agent.
We give an efficient algorithm that achieves $O(T3/4)$ regret with high probability for that setting, even when the agent faces an adversarial environment.
arXiv Detail & Related papers (2021-03-08T04:03:24Z) - 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) - Polynomial-Time Computation of Optimal Correlated Equilibria in
Two-Player Extensive-Form Games with Public Chance Moves and Beyond [107.14897720357631]
We show that an optimal correlated equilibrium can be computed in time in two-player games with public chance moves.
This results in the biggest positive complexity result surrounding extensive-form correlation in more than a decade.
arXiv Detail & Related papers (2020-09-09T14:51:58Z)
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.