Minimax Sample Complexity for Turn-based Stochastic Game
arXiv:2011.14267
Abstract
The empirical success of Multi-agent reinforcement learning is encouraging, while few theoretical guarantees have been revealed. In this work, we prove that the plug-in solver approach, probably the most natural reinforcement learning algorithm, achieves minimax sample complexity for turn-based stochastic game (TBSG). Specifically, we plan in an empirical TBSG by utilizing a `simulator' that allows sampling from arbitrary state-action pair. We show that the empirical Nash equilibrium strategy is an approximate Nash equilibrium strategy in the true TBSG and give both problem-dependent and problem-independent bound. We develop absorbing TBSG and reward perturbation techniques to tackle the complex statistical dependence. The key idea is artificially introducing a suboptimality gap in TBSG and then the Nash equilibrium strategy lies in a finite set.
15 pages
References in corpus (9)
- Model-Based Reinforcement Learning for Atari
- Benchmarking Model-Based Reinforcement Learning
- Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
- Feature-Based Q-Learning for Two-Player Stochastic Games
- Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
- Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
- -learning with Logarithmic Regret
- Near-Optimal Reinforcement Learning with Self-Play
- Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?