Function Approximation for Solving Stackelberg Equilibrium in Large
Perfect Information Games
- URL: http://arxiv.org/abs/2212.14431v2
- Date: Sun, 2 Apr 2023 01:22:02 GMT
- Title: Function Approximation for Solving Stackelberg Equilibrium in Large
Perfect Information Games
- Authors: Chun Kai Ling, J. Zico Kolter, Fei Fang
- Abstract summary: We propose learning the textitEnforceable Payoff Frontier (EPF) -- a generalization of the state value function for general-sum games.
This is the first method that applies FA to the Stackelberg setting, allowing us to scale to much larger games.
- Score: 115.77438739169155
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Function approximation (FA) has been a critical component in solving large
zero-sum games. Yet, little attention has been given towards FA in solving
\textit{general-sum} extensive-form games, despite them being widely regarded
as being computationally more challenging than their fully competitive or
cooperative counterparts. A key challenge is that for many equilibria in
general-sum games, no simple analogue to the state value function used in
Markov Decision Processes and zero-sum games exists. In this paper, we propose
learning the \textit{Enforceable Payoff Frontier} (EPF) -- a generalization of
the state value function for general-sum games. We approximate the optimal
\textit{Stackelberg extensive-form correlated equilibrium} by representing EPFs
with neural networks and training them by using appropriate backup operations
and loss functions. This is the first method that applies FA to the Stackelberg
setting, allowing us to scale to much larger games while still enjoying
performance guarantees based on FA error. Additionally, our proposed method
guarantees incentive compatibility and is easy to evaluate without having to
depend on self-play or approximate best-response oracles.
Related papers
- Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
We study offline multi-agent reinforcement learning (RL) in Markov games.
We provide the first framework for sample-efficient offline learning in Markov games.
arXiv Detail & Related papers (2023-02-06T05:22:27Z) - Safe Subgame Resolving for Extensive Form Correlated Equilibrium [47.155175336085364]
Correlated Equilibrium is a solution concept that is more general than Nash Equilibrium (NE) and can lead to better social welfare.
We apply textitsubgame resolving, a technique extremely successful in finding NE in zero-sum games to solving general-sum EFCEs.
Subgame resolving refines a correlation plan in an textitonline manner: instead of solving for the full game upfront, it only solves for strategies in subgames that are reached in actual play.
arXiv Detail & Related papers (2022-12-29T14:20:48Z) - Learning in Mean Field Games: A Survey [44.154293801251505]
Mean Field Games (MFGs) rely on a mean-field approximation to allow the number of players to grow to infinity.
Recent literature on Reinforcement Learning methods to learnlibria and social optima in MFGs.
We present a general framework for classical iterative methods to solve MFGs in an exact way.
arXiv Detail & Related papers (2022-05-25T17:49:37Z) - FL Games: A federated learning framework for distribution shifts [71.98708418753786]
Federated learning aims to train predictive models for data that is distributed across clients, under the orchestration of a server.
We propose FL Games, a game-theoretic framework for federated learning for learning causal features that are invariant across clients.
arXiv Detail & Related papers (2022-05-23T07:51:45Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games:
Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [99.00383370823839]
We study the problem of finding optimal correlated equilibria of various sorts.
We introduce the correlation DAG, a representation of the space of correlated strategies whose size is dependent on the specific solution concept.
We also introduce two new benchmark games: a trick-taking game that emulates the endgame phase of the card game bridge, and a ride-sharing game.
arXiv Detail & Related papers (2022-03-14T15:21:18Z) - On the Complexity of Computing Markov Perfect Equilibrium in General-Sum
Stochastic Games [18.48133964089095]
Games (SGs) lay the foundation for the study of multi-agent reinforcement learning (MARL) and sequential agent interactions.
We derive an approximate Perfect Equilibrium (MPE) in a finite-state SGs Game within the exponential precision of textbfPPAD-complete.
Our results indicate that finding an MPE in SGs is highly unlikely to be textbfNP-hard unless textbfNP=textbfco-NP.
arXiv Detail & Related papers (2021-09-04T05:47:59Z) - Better Regularization for Sequential Decision Spaces: Fast Convergence
Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
We study the application of iterative first-order methods to the problem of computing equilibria of large-scale two-player extensive-form games.
By instantiating first-order methods with our regularizers, we develop the first accelerated first-order methods for computing correlated equilibra and ex-ante coordinated team equilibria.
arXiv Detail & Related papers (2021-05-27T06:10:24Z) - 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)
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.