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

arXiv: https://arxiv.org/abs/2112.13521 · HTML: https://mlsanity.com/paper/2112.13521/

## Key facts

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

## Builds on (most cited first, 30 of 48)

- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction](https://mlsanity.com/paper/1906.00949/) (2019)
- [Solving Rubik's Cube with a Robot Hand](https://mlsanity.com/paper/1910.07113/) (2019)
- [AWAC: Accelerating Online Reinforcement Learning with Offline Datasets](https://mlsanity.com/paper/2006.09359/) (2020)
- [Behavior Regularized Offline Reinforcement Learning](https://mlsanity.com/paper/1911.11361/) (2019)
- [MOReL : Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2005.05951/) (2020)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialog](https://mlsanity.com/paper/1907.00456/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Critic Regularized Regression](https://mlsanity.com/paper/2006.15134/) (2020)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [A Survey and Critique of Multiagent Deep Reinforcement Learning](https://mlsanity.com/paper/1810.05587/) (2018)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [A Review of Cooperative Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1908.03963/) (2019)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)

## Built on by (most cited first, 24 of 24)

- [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2308.02585/) (2023)
- [Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus](https://mlsanity.com/paper/2206.00159/) (2022)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023)
- [Performative Reinforcement Learning in Gradually Shifting Environments](https://mlsanity.com/paper/2402.09838/) (2024)
- [Oracles & Followers: Stackelberg Equilibria in Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2210.11942/) (2022)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [Performative Reinforcement Learning with Linear Markov Decision Process](https://mlsanity.com/paper/2411.05234/) (2024)
- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [A General Framework for Sequential Decision-Making under Adaptivity Constraints](https://mlsanity.com/paper/2306.14468/) (2023)
- [On Corruption-Robustness in Performative Reinforcement Learning](https://mlsanity.com/paper/2505.05609/) (2025)
- [Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints](https://mlsanity.com/paper/2301.10230/) (2023)
- [Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation](https://mlsanity.com/paper/2211.15792/) (2022)
- [Function Approximation for Solving Stackelberg Equilibrium in Large Perfect Information Games](https://mlsanity.com/paper/2212.14431/) (2022)
- [Differentiable Arbitrating in Zero-sum Markov Games](https://mlsanity.com/paper/2302.10058/) (2023)
- [Learning Optimal Tax Design in Nonatomic Congestion Games](https://mlsanity.com/paper/2402.07437/) (2024)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)
- [Offline Reinforcement Learning for Human-Guided Human-Machine Interaction with Private Information](https://mlsanity.com/paper/2212.12167/) (2022)
- [Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds](https://mlsanity.com/paper/2301.11802/) (2023)
- [ReLExS: Reinforcement Learning Explanations for Stackelberg No-Regret Learners](https://mlsanity.com/paper/2408.14086/) (2024)
- [The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability](https://mlsanity.com/paper/2506.09940/) (2025)
- [Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Games](https://mlsanity.com/paper/2604.04394/) (2026)

## 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.