Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs

Abstract

We study the reinforcement learning problem for discounted Markov Decision Processes (MDPs) under the tabular setting. We propose a model-based algorithm named UCBVI-$\gamma$, which is based on the \emph{optimism in the face of uncertainty principle} and the Bernstein-type bonus. We show that UCBVI-$\gamma$ achieves an $\tilde{O}(\sqrt{SAT}/(1-\gamma {)}^{1.5})$ regret, where $S$ is the number of states, $A$ is the number of actions, $\gamma$ is the discount factor and $T$ is the number of steps. In addition, we construct a class of hard MDPs and show that for any algorithm, the expected regret is at least $\tilde{\Omega }(\sqrt{SAT}/(1-\gamma {)}^{1.5})$. Our upper bound matches the minimax lower bound up to logarithmic factors, which suggests that UCBVI-$\gamma$ is nearly minimax optimal for discounted MDPs.

33 pages, 1 figure, 1 table. In NeurIPS 2021

References in corpus (9)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• On Lower Bounds for Regret in Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Variance-reduced $Q$-learning is minimax optimal
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity
• Regret Bounds for Discounted MDPs

Cited by in corpus (3)

• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Regret Bounds for Discounted MDPs