Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?

Abstract

Learning to plan for long horizons is a central challenge in episodic reinforcement learning problems. A fundamental question is to understand how the difficulty of the problem scales as the horizon increases. Here the natural measure of sample complexity is a normalized one: we are interested in the number of episodes it takes to provably discover a policy whose value is $\epsilon$ near to that of the optimal value, where the value is measured by the normalized cumulative reward in each episode. In a COLT 2018 open problem, Jiang and Agarwal conjectured that, for tabular, episodic reinforcement learning problems, there exists a sample complexity lower bound which exhibits a polynomial dependence on the horizon -- a conjecture which is consistent with all known sample complexity upper bounds. This work refutes this conjecture, proving that tabular, episodic reinforcement learning is possible with a sample complexity that scales only logarithmically with the planning horizon. In other words, when the values are appropriately normalized (to lie in the unit interval), this results shows that long horizon RL is no more difficult than short horizon RL, at least in a minimax sense. Our analysis introduces two ideas: (i) the construction of an $\epsilon$-net for optimal policies whose log-covering number scales only logarithmically with the planning horizon, and (ii) the Online Trajectory Synthesis algorithm, which adaptively evaluates all policies in a given policy class using sample complexity that scales with the log-covering number of the given policy class. Both may be of independent interest.

References in corpus (6)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• On Lower Bounds for Regret in Reinforcement Learning
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• PAC Reinforcement Learning without Real-World Feedback

Cited by in corpus (5)

• Model-Based Reinforcement Learning with Value-Targeted Regression
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning