Gap-Dependent Bounds for Two-Player Markov Games

Abstract

As one of the most popular methods in the field of reinforcement learning, Q-learning has received increasing attention. Recently, there have been more theoretical works on the regret bound of algorithms that belong to the Q-learning class in different settings. In this paper, we analyze the cumulative regret when conducting Nash Q-learning algorithm on 2-player turn-based stochastic Markov games (2-TBSG), and propose the very first gap dependent logarithmic upper bounds in the episodic tabular setting. This bound matches the theoretical lower bound only up to a logarithmic term. Furthermore, we extend the conclusion to the discounted game setting with infinite horizon and propose a similar gap dependent logarithmic regret bound. Also, under the linear MDP assumption, we obtain another logarithmic regret for 2-TBSG, in both centralized and independent settings.

arXiv comment34 pages

References in corpus (20)

• Playing Atari with Deep Reinforcement Learning
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• On Lower Bounds for Regret in Reinforcement Learning
• Variance-reduced $Q$-learning is minimax optimal
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• $Q$-learning with Logarithmic Regret
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Regret Bounds for Discounted MDPs