2021

Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?

Zhong, Han, Yang, Zhuoran, Wang, Zhaoran et al.

Understand

We study multi-player general-sum Markov games with one of the players designated as the leader and the other players regarded as followers.

In particular, we focus on the class of games where the followers are myopic, i.e., they aim to maximize their instantaneous rewards.
For such a game, our goal is to find a Stackelberg-Nash equilibrium (SNE), which is a policy pair $(\pi^*, \nu^*)$ such that (i) $\pi^*$ is the optimal policy for the leader when the followers always play their best response, and (ii) $\nu^*$ is the best response policy of the followers, which is a Nash equilibrium of the followers' game induced by $\pi^*$.
We develop sample-efficient reinforcement learning (RL) algorithms for solving for an SNE in both online and offline settings.

Built on

Convergence of learning dynamics in Stackelberg games
Original
Fiez, T · 1906
Earlier work this paper cites.
Feature-based q-learning for two-player stochastic games
Original
Jia, Z · 1906
Earlier work this paper cites.
Stabilizing off-policy Q-learning via bootstrapping error reduction
Original
Kumar, A · 1906
Earlier work this paper cites.
Way off-policy batch deep reinforcement learning of implicit human preferences in dialog
Original
Jaques, N · 1907
Earlier work this paper cites.
A review of cooperative multi-agent deep reinforcement learning
Original
OroojlooyJadid, A · 1908
Earlier work this paper cites.
Solving rubik’s cube with a robot hand
Original
Akkaya, I · 1910
Earlier work this paper cites.
Behavior regularized offline reinforcement learning
Original
Wu, Y · 1911
Earlier work this paper cites.
Multi-agent reinforcement learning: A selective overview of theories and algorithms
Original
Zhang, K · 1911
Earlier work this paper cites.
Stochastic games
Shapley, L. S · 1953
Earlier work this paper cites.
On the Stackelberg strategy in nonzero-sum games
Simaan, M · 1973
Earlier work this paper cites.
Stackelberg strategies and incentives in multiperson deterministic decision problems
Zheng, Y.-P · 1984
Earlier work this paper cites.
Sequential Stackelberg equilibria in two-person games
Breton, M · 1988
Earlier work this paper cites.
Q-learning
Watkins, C. J · 1992
Earlier work this paper cites.
Markov games as a framework for multi-agent reinforcement learning
Littman, M. L · 1994
Earlier work this paper cites.
Neuro-dynamic programming
Bertsekas, D. P · 1996
Earlier work this paper cites.
Dynamic Noncooperative Game Theory
Başar, T · 1998
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
Sutton, R. S · 1999
Earlier work this paper cites.
Friend-or-foe Q-learning in general-sum games
Littman, M. L · 2001
Earlier work this paper cites.
Complexity of mechanism design
Conitzer, V · 2002
Earlier work this paper cites.
Optimistic policy optimization with bandit feedback
Original
Efroni, Y · 2002
Earlier work this paper cites.
Keep doing what worked: Behavioral modelling priors for offline reinforcement learning
Original
Siegel, N. Y · 2002
Earlier work this paper cites.
Correlated Q-learning
Greenwald, A · 2003
Earlier work this paper cites.
Nash q-learning for general-sum stochastic games
Hu, J · 2003
Earlier work this paper cites.
Q ⋆ {Q}^{\star} -approximation schemes for batch reinforcement learning: A theoretical comparison
Original
Xie, T · 2003
Earlier work this paper cites.
Stackelberg scheduling strategies
Roughgarden, T · 2004
Earlier work this paper cites.
The AI economist: Improving equality and productivity with AI-driven tax policies
Original
Zheng, S · 2004
Earlier work this paper cites.
Design of incentive compatible mechanisms for Stackelberg problems
Garg, D · 2005
Earlier work this paper cites.
Morel: Model-based offline reinforcement learning
Original
Kidambi, R · 2005
Earlier work this paper cites.
Mopo: Model-based offline policy optimization
Original
Yu, T · 2005
Earlier work this paper cites.
Near-optimal reinforcement learning with self-play
Original
Bai, Y · 2006
Earlier work this paper cites.
Computing the optimal strategy to commit to
Conitzer, V · 2006
Earlier work this paper cites.
Conservative q-learning for offline reinforcement learning
Original
Kumar, A · 2006
Earlier work this paper cites.
Accelerating online reinforcement learning with offline datasets
Original
Nair, A · 2006
Earlier work this paper cites.
Critic regularized regression
Original
Wang, Z · 2006
Earlier work this paper cites.
Fitted Q-iteration in continuous action-space MDPs
Antos, A · 2007
Earlier work this paper cites.
A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic
Original
Hong, M · 2007
Earlier work this paper cites.
Provably good batch reinforcement learning without great exploration
Original
Liu, Y · 2007
Earlier work this paper cites.

Similar

Model-based multi-agent rl in zero-sum Markov games with near-optimal sample complexity
Original
Zhang, K · 2007
Cited alongside, same era.
Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path
Antos, A · 2008
Cited alongside, same era.
A comprehensive survey of multiagent reinforcement learning
Busoniu, L · 2008
Cited alongside, same era.
Stochastic linear optimization under bandit feedback
Dani, V · 2008
Cited alongside, same era.
Finite-time bounds for fitted value iteration
Munos, R · 2008
Cited alongside, same era.
The importance of pessimism in fixed-dataset policy optimization
Original
Buckman, J · 2009
Cited alongside, same era.
Learning and approximating the optimal strategy to commit to
Letchford, J · 2009
Cited alongside, same era.
Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon
Original
Zhang, Z · 2009
Cited alongside, same era.
Error propagation for approximate policy and value iteration
Farahmand, A. M · 2010
Cited alongside, same era.
A sharp analysis of model-based reinforcement learning with self-play
Original
Liu, Q · 2010
Cited alongside, same era.
Provably efficient online agnostic learning in Markov games
Original
Tian, Y · 2010
Cited alongside, same era.
Leadership games with convex strategy sets
Von Stengel, B · 2010
Cited alongside, same era.

Then

Online reinforcement learning in stochastic games
Original
Wei, C.-Y · 2017
Later among the works it cites.
Approximation methods for bilevel programming
Original
Ghadimi, S · 2018
Later among the works it cites.
Is multiagent deep reinforcement learning the answer or the question? a brief survey
Hernandez-Leal, P · 2018
Later among the works it cites.
Is Q-learning provably efficient?
Original
Jin, C · 2018
Later among the works it cites.
Breaking the curse of horizon: Infinite-horizon off-policy estimation
Original
Liu, Q · 2018
Later among the works it cites.
A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play
Silver, D · 2018
Later among the works it cites.
Reinforcement Learning: An Introduction
Sutton, R. S · 2018
Later among the works it cites.
Solving the rubik’s cube with deep reinforcement learning and search
Agostinelli, F · 2019
Later among the works it cites.
On the value iteration method for dynamic strong Stackelberg equilibria
Bucarey, V · 2019
Later among the works it cites.
Information-theoretic considerations in batch reinforcement learning
Chen, J · 2019
Later among the works it cites.
Off-policy deep reinforcement learning without exploration
Fujimoto, S · 2019
Later among the works it cites.
A survey and critique of multiagent deep reinforcement learning
Hernandez-Leal, P · 2019
Later among the works it cites.
Safe policy improvement with baseline bootstrapping
Laroche, R · 2019
Later among the works it cites.
Learning optimal strategies to commit to
Peng, B · 2019
Later among the works it cites.
Sample-optimal parametric Q-learning using linearly additive features
Yang, L · 2019
Later among the works it cites.
Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds
Zanette, A · 2019
Later among the works it cites.
Model-based reinforcement learning with a generative model is minimax optimal
Agarwal, A · 2020
Later among the works it cites.
Model-based reinforcement learning with value-targeted regression
Ayoub, A · 2020
Later among the works it cites.
Provable self-play algorithms for competitive reinforcement learning
Bai, Y · 2020
Later among the works it cites.
Provably efficient exploration in policy optimization
Cai, Q · 2020
Later among the works it cites.
Computing a pessimistic Stackelberg equilibrium with multiple followers: The mixed-pure case
Coniglio, S · 2020
Later among the works it cites.
A theoretical analysis of deep Q-learning
Fan, J · 2020
Later among the works it cites.
Bandit Algorithms
Lattimore, T · 2020
Later among the works it cites.
A game theoretic framework for model based reinforcement learning
Rajeswaran, A · 2020
Later among the works it cites.
Adaptive incentive design
Ratliff, L. J · 2020
Later among the works it cites.
Solving discounted stochastic two-player games with near-optimal time and sample complexity
Sidford, A · 2020
Later among the works it cites.
Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium
Xie, Q · 2020
Later among the works it cites.
Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound
Yang, L · 2020
Later among the works it cites.
Sample-efficient learning of Stackelberg equilibria in general-sum games
Original
Bai, Y · 2021
Closest in time.
Independent policy gradient methods for competitive reinforcement learning
Original
Daskalakis, C · 2021
Closest in time.
V-learning–a simple, efficient, decentralized algorithm for multiagent rl
Original
Jin, C · 2021
Closest in time.
Dynamic Stackelberg duopoly with sticky prices and a myopic follower
Kańska, K · 2021
Closest in time.
Provably efficient reinforcement learning in decentralized general-sum Markov games
Original
Mao, W · 2021
Closest in time.
Bridging offline reinforcement learning and imitation learning: A tale of pessimism
Original
Rashidinejad, P · 2021
Closest in time.
When can we learn general-sum Markov games with a large number of players sample-efficiently?
Original
Song, Z · 2021
Closest in time.
Provably efficient policy gradient methods for two-player zero-sum Markov games
Original
Zhao, Y · 2021
Closest in time.

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…