# Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 42 references that are in the map.
- First posted on arXiv 28 Nov 2022.

## Builds on (most cited first, 26 of 26)

- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [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)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policies](https://mlsanity.com/paper/2004.13332/) (2020)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach](https://mlsanity.com/paper/2202.00063/) (2022)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [Stackelberg Actor-Critic: Game-Theoretic Reinforcement Learning Algorithms](https://mlsanity.com/paper/2109.12286/) (2021)
- [Reinforcement Learning with Dynamic Boltzmann Softmax Updates](https://mlsanity.com/paper/1903.05926/) (2019)
- [Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure](https://mlsanity.com/paper/2111.00781/) (2021)
- [Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions](https://mlsanity.com/paper/2010.11450/) (2020)

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

- [Decentralized Online Learning in General-Sum Stackelberg Games](https://mlsanity.com/paper/2405.03158/) (2024)

## Abstract (arXiv)

We consider a multi-agent episodic MDP setup where an agent (leader) takes action at each step of the episode followed by another agent (follower). The state evolution and rewards depend on the joint action pair of the leader and the follower. Such type of interactions can find applications in many domains such as smart grids, mechanism design, security, and policymaking. We are interested in how to learn policies for both the players with provable performance guarantee under a bandit feedback setting. We focus on a setup where both the leader and followers are em non-myopic, i.e., they both seek to maximize their rewards over the entire episode and consider a linear MDP which can model continuous state-space which is very common in many RL applications. We propose a em model-free RL algorithm and show that tildeO(√d3H3T) regret bounds can be achieved for both the leader and the follower, where d is the dimension of the feature mapping, H is the length of the episode, and T is the total number of steps under the bandit feedback information setup. Thus, our result holds even when the number of states becomes infinite. The algorithm relies on em novel adaptation of the LSVI-UCB algorithm. Specifically, we replace the standard greedy policy (as the best response) with the soft-max policy for both the leader and the follower. This turns out to be key in establishing uniform concentration bound for the value functions. To the best of our knowledge, this is the first sub-linear regret bound guarantee for the Markov games with non-myopic followers with function approximation.