Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds

Abstract

Strong worst-case performance bounds for episodic reinforcement learning exist but fortunately in practice RL algorithms perform much better than such bounds would predict. Algorithms and theory that provide strong problem-dependent bounds could help illuminate the key features of what makes a RL problem hard and reduce the barrier to using RL algorithms in practice. As a step towards this we derive an algorithm for finite horizon discrete MDPs and associated analysis that both yields state-of-the art worst-case regret bounds in the dominant terms and yields substantially tighter bounds if the RL environment has small environmental norm, which is a function of the variance of the next-state value functions. An important benefit of our algorithmic is that it does not require apriori knowledge of a bound on the environmental norm. As a result of our analysis, we also help address an open learning theory question~\cite{jiang2018open} about episodic MDPs with a constant upper-bound on the sum of rewards, providing a regret bound with no $H$-dependence in the leading term that scales a polynomial function of the number of episodes.

Bug fixes

References in corpus (6)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• On Lower Bounds for Regret in Reinforcement Learning
• Model-based Reinforcement Learning and the Eluder Dimension
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• Problem Dependent Reinforcement Learning Bounds Which Can Identify Bandit Structure in MDPs

Cited by in corpus (39)

• MOPO: Model-based Offline Policy Optimization
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Reward-Free Exploration for Reinforcement Learning
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Corruption-robust exploration in episodic reinforcement learning
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Adaptive Discretization in Online Reinforcement Learning
• Task-agnostic Exploration in Reinforcement Learning
• Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
• UCB Momentum Q-learning: Correcting the bias without forgetting
• Adaptive Discretization for Model-Based Reinforcement Learning
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• 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
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• Near-optimal Regret Bounds for Stochastic Shortest Path
• Dueling RL: Reinforcement Learning with Trajectory Preferences
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge
• Reinforcement Learning with Feedback Graphs
• Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation
• Improved Exploration in Factored Average-Reward MDPs
• Confidence-Budget Matching for Sequential Budgeted Learning
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation
• Can Q-Learning be Improved with Advice?
• Ranking Policy Gradient
• Online Selection of Diverse Committees
• Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation