Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 26 of its 42 references that are in the map. First posted on arXiv 28 Nov 2022.
Builds on
26 of 42 references.
References · 26
- 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
- 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
- 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
- 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
- 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
- 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
- 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
- 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
- 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
- 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
- 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
- 2020The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policiescited by 75
14 more
- 2017Online Reinforcement Learning in Stochastic Gamescited by 67
- 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
- 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
- 2015The Sample Complexity of Revenue Maximizationcited by 48
- 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
- 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
- 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
- 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
- 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
- 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
- 2021Stackelberg Actor-Critic: Game-Theoretic Reinforcement Learning Algorithmscited by 18
- 2019Reinforcement Learning with Dynamic Boltzmann Softmax Updatescited by 14
- 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
- 2020Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functionscited by 10
Built on by
Citing papers per year: 2024: 1.
1 paper.