mlsanityData to 7 Oct 2026

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

arXiv 2112.13521 ↗First posted 27 Dec 2021cs.LG cs.GT stat.MLcited by 24

Not on the map. Why?

Abstract (arXiv)

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 (π^*, nu^*) such that (i) π^* 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 π^*. We develop sample-efficient reinforcement learning (RL) algorithms for solving for an SNE in both online and offline settings. Our algorithms are optimistic and pessimistic variants of least-squares value iteration, and they are readily able to incorporate function approximation tools in the setting of large state spaces. Furthermore, for the case with linear function approximation, we prove that our algorithms achieve sublinear regret and suboptimality under online and offline setups respectively. To the best of our knowledge, we establish the first provably efficient RL algorithms for solving for SNEs in general-sum Markov games with myopic followers.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). Builds on 48 of its 101 references that are in the map. First posted on arXiv 27 Dec 2021.

Builds on

48 of 101 references.

References · 48

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  2. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 833
  3. 2019Solving Rubik's Cube with a Robot Handcited by 699
  4. 2019Behavior Regularized Offline Reinforcement Learningcited by 654
  5. 2020AWAC: Accelerating Online Reinforcement Learning with Offline Datasetscited by 647
  6. 2020MOReL : Model-Based Offline Reinforcement Learningcited by 582
  7. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  8. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  9. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 361
  10. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  11. 2019Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialogcited by 283
  12. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
36 more
  1. 2020Critic Regularized Regressioncited by 269
  2. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  3. 2018Approximation Methods for Bilevel Programmingcited by 231
  4. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2018A Survey and Critique of Multiagent Deep Reinforcement Learningcited by 173
  10. 2019A Review of Cooperative Multi-Agent Deep Reinforcement Learningcited by 147
  11. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  12. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  13. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  14. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  15. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  16. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  17. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  18. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  19. 2020The Importance of Pessimism in Fixed-Dataset Policy Optimizationcited by 99
  20. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  21. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  22. 2020The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policiescited by 75
  23. 2020A Game Theoretic Framework for Model Based Reinforcement Learningcited by 72
  24. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  25. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  26. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  27. 2014Complexity of Mechanism Designcited by 33
  28. 2019Convergence of Learning Dynamics in Stackelberg Gamescited by 28
  29. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  30. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparisoncited by 22
  31. 2020Minimax Sample Complexity for Turn-based Stochastic Gamecited by 13
  32. 2020Online Learning in Unknown Markov Gamescited by 9
  33. 2018Adaptive Incentive Designcited by 6
  34. 2016Caching Incentive Design in Wireless D2D Networks: A Stackelberg Game Approachcited by 3
  35. 2017Methods for finding leader--follower equilibria with multiple followerscited by 3
  36. 2014Incentive Mechanism Design for Heterogeneous Peer-to-Peer Networks: A Stackelberg Game Approachcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 9; 2023: 7; 2024: 5; 2025: 2; 2026: 1.

24 papers.

Sort:

By area:

  1. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  2. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  3. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  4. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  5. 2022Performative Reinforcement Learningcited by 25
  6. 2023Online Learning in Stackelberg Games with an Omniscient Followercited by 15
  7. 2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 13
  8. 2022Oracles & Followers: Stackelberg Equilibria in Deep Multi-Agent Reinforcement Learningcited by 12
  9. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  10. 2024Performative Reinforcement Learning with Linear Markov Decision Processcited by 8
  11. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  12. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
12 more
  1. 2025On Corruption-Robustness in Performative Reinforcement Learningcited by 6
  2. 2023Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraintscited by 5
  3. 2022Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximationcited by 1
  4. 2022Function Approximation for Solving Stackelberg Equilibrium in Large Perfect Information Gamescited by 1
  5. 2023Differentiable Arbitrating in Zero-sum Markov Gamescited by 1
  6. 2024Learning Optimal Tax Design in Nonatomic Congestion Gamescited by 1
  7. 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescited by 1
  8. 2022Offline Reinforcement Learning for Human-Guided Human-Machine Interaction with Private Informationcited by 0
  9. 2023Decentralized Online Bandit Optimization on Directed Graphs with Regret Boundscited by 0
  10. 2024ReLExS: Reinforcement Learning Explanations for Stackelberg No-Regret Learnerscited by 0
  11. 2025The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportabilitycited by 0
  12. 2026Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Gamescited by 0