2021

Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games

Bai, Yu, Jin, Chi, Wang, Huan et al.

Understand

Real world applications such as economics and policy making often involve solving multi-agent games with two unique features: (1) The agents are inherently asymmetric and partitioned into leaders and followers; (2) The agents have different reward functions, thus the game is general-sum.

The majority of existing results in this field focuses on either symmetric solution concepts (e.g.
Nash equilibrium) or zero-sum games.
It remains open how to learn the Stackelberg equilibrium -- an asymmetric analog of the Nash equilibrium -- in general-sum games efficiently from noisy samples.

Built on

Zur theorie der gesellschaftsspiele
J von Neumann · 1928
Earlier work this paper cites.
Non-cooperative games
John Nash · 1951
Earlier work this paper cites.
Stochastic games
Lloyd S Shapley · 1953
Earlier work this paper cites.
On the stackelberg strategy in nonzero-sum games
Marwaan Simaan and Jose B Cruz · 1973
Earlier work this paper cites.
The extragradient method for finding saddle points and other problems
GM Korpelevich · 1976
Earlier work this paper cites.
Cesari convergence of the gradient method of approximating saddle points of convex-concave functions
Arkadi S Nemirovski and David Berkovich Yudin · 1978
Earlier work this paper cites.
Constrained Markov decision processes , volume 7
Eitan Altman · 1999
Earlier work this paper cites.
Complexity of mechanism design
Vincent Conitzer and Tuomas Sandholm · 2002
Earlier work this paper cites.
Reward-free exploration for reinforcement learning
Original
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu · 2002
Earlier work this paper cites.
Convex optimization
Stephen P Boyd and Lieven Vandenberghe · 2004
Earlier work this paper cites.
Self-interested automated mechanism design and implications for optimal combinatorial auctions
Vincent Conitzer and Tuomas Sandholm · 2004
Earlier work this paper cites.
Prox-method with rate of convergence o (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems
Arkadi Nemirovski · 2004
Earlier work this paper cites.
Prediction, learning, and games
Nicolo Cesa-Bianchi and Gábor Lugosi · 2006
Earlier work this paper cites.
Computing the optimal strategy to commit to
Vincent Conitzer and Tuomas Sandholm · 2006
Earlier work this paper cites.
Methods for empirical game-theoretic analysis
Michael P Wellman · 2006
Earlier work this paper cites.
Learning payoff functions in infinite games
Yevgeniy Vorobeychik, Michael P Wellman, and Satinder Singh · 2007
Earlier work this paper cites.
Searching for approximate equilibria in empirical games
Patrick R Jordan, Yevgeniy Vorobeychik, and Michael P Wellman · 2008
Earlier work this paper cites.
Multiagent systems: Algorithmic, game-theoretic, and logical foundations
Yoav Shoham and Kevin Leyton-Brown · 2008
Earlier work this paper cites.

Similar

Learning and approximating the optimal strategy to commit to
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala · 2009
Cited alongside, same era.
Computing optimal strategies to commit to in extensive-form games
Joshua Letchford and Vincent Conitzer · 2010
Cited alongside, same era.
Algorithmic game theory
Tim Roughgarden · 2010
Cited alongside, same era.
Leadership games with convex strategy sets
Bernhard Von Stengel and Shmuel Zamir · 2010
Cited alongside, same era.
Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness
Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe · 2011
Cited alongside, same era.
Security and game theory: algorithms, deployed systems, lessons learned
Milind Tambe · 2011
Cited alongside, same era.
Optimization, learning, and games with predictable sequences
Original
Alexander Rakhlin and Karthik Sridharan · 2013
Cited alongside, same era.
Learning optimal commitment to overcome insecurity
Avrim Blum, Nika Haghtalab, and Ariel D Procaccia · 2014
Cited alongside, same era.
The sample complexity of revenue maximization
Richard Cole and Tim Roughgarden · 2014
Cited alongside, same era.
Learning in games: Robustness of fast convergence
Original
Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos · 2016
Cited alongside, same era.
Minimum-volume ellipsoids: Theory and algorithms
Michael J Todd · 2016
Cited alongside, same era.
Minimax regret bounds for reinforcement learning
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos · 2017
Cited alongside, same era.

Then

Computing stackelberg equilibria of large general-sum games
Avrim Blum, Nika Haghtalab, MohammadTaghi Hajiaghayi, and Saeed Seddighin · 2019
Later among the works it cites.
Optimal auctions through deep learning
Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath · 2019
Later among the works it cites.
Convergence of learning dynamics in stackelberg games
Original
Tanner Fiez, Benjamin Chasnov, and Lillian J Ratliff · 2019
Later among the works it cites.
Solving a class of non-convex min-max games using iterative first order methods
Original
Maher Nouiehed, Maziar Sanjabi, Jason D Lee, and Meisam Razaviyayn · 2019
Later among the works it cites.
Learning optimal strategies to commit to
Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo · 2019
Later among the works it cites.
High-dimensional statistics: A non-asymptotic viewpoint , volume 48
Martin J Wainwright · 2019
Later among the works it cites.
Provable self-play algorithms for competitive reinforcement learning
Yu Bai and Chi Jin · 2020
Later among the works it cites.
Near-optimal reinforcement learning with self-play
Original
Yu Bai, Chi Jin, and Tiancheng Yu · 2020
Later among the works it cites.
Bandit algorithms
Tor Lattimore and Csaba Szepesvári · 2020
Later among the works it cites.
Learning with good feature representations in bandits and in rl with a generative model
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz · 2020
Later among the works it cites.
A sharp analysis of model-based reinforcement learning with self-play
Original
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin · 2020
Later among the works it cites.
Learning probably approximately correct maximin strategies in simulation-based games with infinite strategy spaces
Alberto Marchesi, Francesco Trovò, and Nicola Gatti · 2020
Later among the works it cites.
Learning to play sequential games versus unknown opponents
Original
Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause · 2020
Later among the works it cites.
Stochastic stackelberg games
Original
Deepanshu Vasal · 2020
Later among the works it cites.
Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang · 2020
Later among the works it cites.
Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity
Original
Kaiqing Zhang, Sham M Kakade, Tamer Başar, and Lin F Yang · 2020
Later among the works it cites.
The ai economist: Improving equality and productivity with ai-driven tax policies
Original
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C Parkes, and Richard Socher · 2020
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…