Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs

Abstract

This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\tilde{\mathcal{O}}(\sqrt{HSAT})$-minimax rate. The key technique in our analysis is a novel "clipped" regret decomposition which applies to a broad family of recent optimistic algorithms for episodic MDPs.

References in corpus (8)

• Empirical Bernstein Bounds and Sample Variance Penalization
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Exploration in Structured Reinforcement Learning
• Efficient Model-free Reinforcement Learning in Metric Spaces
• Policy Certificates: Towards Accountable Reinforcement Learning

Cited by in corpus (18)

• Learning Near Optimal Policies with Low Inherent Bellman Error
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
• $Q$-learning with Logarithmic Regret
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Reinforcement Learning with Feedback Graphs
• Confidence-Budget Matching for Sequential Budgeted Learning
• Provably Efficient Multi-Task Reinforcement Learning with Model Transfer
• Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation
• Can Q-Learning be Improved with Advice?