Provably Efficient Model-free RL In Leader-follower MDP With Linear Function Approximation

Abstract

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 \(\tilde\{\mathcal\{O\}\}(\sqrt\{d^3H^3T\})\) regret bounds can be achieved for both the leader and the follower, where \(d\) is the dimension of the feature mapping, \(H\

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyghosh2022provably

Related papers

• Reward-free Model-based Reinforcement Learning With Linear Function Approximation (2021)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Distributionally Robust Online Markov Game With Linear Function Approximation (2025)0.00
• Online Learning In Mdps With Linear Function Approximation And Bandit Feedback (2020)0.00
• Model-based Reinforcement Learning With Multinomial Logistic Function Approximation (2022)2.26
• Improved Regret For Efficient Online Reinforcement Learning With Linear Function Approximation (2023)0.00
• Provably Efficient Reinforcement Learning With Linear Function Approximation (2019)11.76
• Nonstationary Reinforcement Learning With Linear Function Approximation (2020)0.00