RL In Markov Games With Independent Function Approximation: Improved Sample Complexity Bound Under The Local Access Model
2024 · Junyi Fan, Yuxuan Han, Jialin Zeng, et al.
Abstract
Efficiently learning equilibria with large state and action spaces in general-sum Markov games while overcoming the curse of multi-agency is a challenging problem. Recent works have attempted to solve this problem by employing independent linear function classes to approximate the marginal \(Q\)-value for each agent. However, existing sample complexity bounds under such a framework have a suboptimal dependency on the desired accuracy \(\epsilon\) or the action space. In this work, we introduce a new algorithm, Lin-Confident-FTRL, for learning coarse correlated equilibria (CCE) with local access to the simulator, i.e., one can interact with the underlying environment on the visited states. Up to a logarithmic dependence on the size of the state space, Lin-Confident-FTRL learns \(\epsilon\)-CCE with a provable optimal accuracy bound \(O(\epsilon^\{-2\})\) and gets rids of the linear dependency on the action space, while scaling polynomially with relevant problem parameters (such as the n
Authors
(none)
Tags
Stats
Related papers
- Breaking The Curse Of Multiagents In A Large State Space: RL In Markov Games With Independent Linear Function Approximation (2023)0.00
- Distributionally Robust Online Markov Game With Linear Function Approximation (2025)0.00
- Minimax-optimal Multi-agent RL In Markov Games With A Generative Model (2022)2.26
- Refined Sample Complexity For Markov Games With Independent Linear Function Approximation (2024)0.00
- Minimax-optimal Multi-agent Robust Reinforcement Learning (2024)0.00
- Breaking The Curse Of Multiagency: Provably Efficient Decentralized Multi-agent RL With Function Approximation (2023)0.00
- Strategically Robust Multi-agent Reinforcement Learning With Linear Function Approximation (2026)0.00
- Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games (2025)0.00