$Q$-learning with Logarithmic Regret

Abstract

This paper presents the first non-asymptotic result showing that a model-free algorithm can achieve a logarithmic cumulative regret for episodic tabular reinforcement learning if there exists a strictly positive sub-optimality gap in the optimal $Q$-function. We prove that the optimistic $Q$-learning studied in [Jin et al. 2018] enjoys a $\mathcal{O}\left(\frac{SA\cdot \mathrm{poly}\left(H\right)}{{\Delta }_{\min }}\log \left(SAT\right)\right)$ cumulative regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, $T$ is the total number of steps, and ${\Delta }_{\min }$ is the minimum sub-optimality gap. This bound matches the information theoretical lower bound in terms of $S,A,T$ up to a $\log \left(SA\right)$ factor. We further extend our analysis to the discounted setting and obtain a similar logarithmic cumulative regret bound.

arXiv commentAccepted by AISTATS 2021

References in corpus (18)

• 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
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Provably efficient RL with Rich Observations via Latent State Decoding
• On Lower Bounds for Regret in Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Exploration in Structured Reinforcement Learning
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• On Oracle-Efficient PAC RL with Rich Observations
• Regret Bounds for Discounted MDPs
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

Cited by in corpus (10)

• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Minimax Sample Complexity for Turn-based Stochastic Game
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge
• Gap-Dependent Bounds for Two-Player Markov Games