Minimax Regret Bounds for Reinforcement Learning

Abstract

We consider the problem of provably optimal exploration in reinforcement learning for finite horizon MDPs. We show that an optimistic modification to value iteration achieves a regret bound of $\tilde{O}(\sqrt{HSAT}+H^2{S}^{2}A+H\sqrt{T})$ where $H$ is the time horizon, $S$ the number of states, $A$ the number of actions and $T$ the number of time-steps. This result improves over the best previous known bound $\tilde{O}(HS\sqrt{AT})$ achieved by the UCRL2 algorithm of Jaksch et al., 2010. The key significance of our new results is that when $T\ge H^3{S}^{3}A$ and $SA\ge H$, it leads to a regret of $\tilde{O}(\sqrt{HSAT})$ that matches the established lower bound of $\Omega (\sqrt{HSAT})$ up to a logarithmic factor. Our analysis contains two key insights. We use careful application of concentration inequalities to the optimal value function as a whole, rather than to the transitions probabilities (to improve scaling in $S$), and we define Bernstein-based "exploration bonuses" that use the empirical variance of the estimated values at the next states (to improve scaling in $H$).

References in corpus (2)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning

Cited by in corpus (30)

• Noisy Networks for Exploration
• Deep Reinforcement Learning: An Overview
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Is Pessimism Provably Efficient for Offline RL?
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Learning to Control in Metric Space with Optimal Regret
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• Geometric Entropic Exploration
• RL for Latent MDPs: Regret Guarantees and a Lower Bound
• Preference-based Reinforcement Learning with Finite-Time Guarantees
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function
• Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning
• Locally Persistent Exploration in Continuous Control Tasks with Sparse Rewards
• Active Reinforcement Learning with Monte-Carlo Tree Search
• Reinforcement Learning with Feedback Graphs
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation
• The Effect of Q-function Reuse on the Total Regret of Tabular, Model-Free, Reinforcement Learning
• Confidence-Budget Matching for Sequential Budgeted Learning
• Minimax Adaptive Control for a Finite Set of Linear Systems
• Can Q-Learning be Improved with Advice?
• Concurrent Training Improves the Performance of Behavioral Cloning from Observation
• Near-optimal Bayesian Solution For Unknown Discrete Markov Decision Process