Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon

Abstract

Episodic reinforcement learning and contextual bandits are two widely studied sequential decision-making problems. Episodic reinforcement learning generalizes contextual bandits and is often perceived to be more difficult due to long planning horizon and unknown state-dependent transitions. The current paper shows that the long planning horizon and the unknown state-dependent transitions (at most) pose little additional difficulty on sample complexity. We consider the episodic reinforcement learning with $S$ states, $A$ actions, planning horizon $H$, total reward bounded by $1$, and the agent plays for $K$ episodes. We propose a new algorithm, \textbf{M}onotonic \textbf{V}alue \textbf{P}ropagation (MVP), which relies on a new Bernstein-type bonus. Compared to existing bonus constructions, the new bonus is tighter since it is based on a well-designed monotonic value function. In particular, the \emph{constants} in the bonus should be subtly setting to ensure optimism and monotonicity. We show MVP enjoys an $O\left(\left(\sqrt{SAK} + S^2A\right) \poly\log \left(SAHK\right)\right)$ regret, approaching the $\Omega \left(\sqrt{SAK}\right)$ lower bound of \emph{contextual bandits} up to logarithmic terms. Notably, this result 1) \emph{exponentially} improves the state-of-the-art polynomial-time algorithms by Dann et al. [2019] and Zanette et al. [2019] in terms of the dependency on $H$, and 2) \emph{exponentially} improves the running time in [Wang et al. 2020] and significantly improves the dependency on $S$, $A$ and $K$ in sample complexity.

References in corpus (5)

• Empirical Bernstein Bounds and Sample Variance Penalization
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• On Lower Bounds for Regret in Reinforcement Learning
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?

Cited by in corpus (20)

• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• UCB Momentum Q-learning: Correcting the bias without forgetting
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Nearly Horizon-Free Offline Reinforcement Learning
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Minimax Regret for Stochastic Shortest Path
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Confidence-Budget Matching for Sequential Budgeted Learning
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
• Learning to Stop with Surprisingly Few Samples
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP