Abstract
Learning to plan for long horizons is a central challenge in episodicreinforcement learning problems. A fundamental question is to understand howthe difficulty of the problem scales as the horizon increases. Here the naturalmeasure of sample complexity is a normalized one: we are interested in thenumber of episodes it takes to provably discover a policy whose value is$\varepsilon$ near to that of the optimal value, where the value is measured bythe normalized cumulative reward in each episode. In a COLT 2018 open problem,Jiang and Agarwal conjectured that, for tabular, episodic reinforcementlearning problems, there exists a sample complexity lower bound which exhibitsa polynomial dependence on the horizon -- a conjecture which is consistent withall known sample complexity upper bounds. This work refutes this conjecture,proving that tabular, episodic reinforcement learning is possible with a samplecomplexity that scales only logarithmically with the planning horizon. In otherwords, when the values are appropriately normalized (to lie in the unitinterval), this results shows that long horizon RL is no more difficult thanshort horizon RL, at least in a minimax sense. Our analysis introduces twoideas: (i) the construction of an $\varepsilon$-net for optimal policies whoselog-covering number scales only logarithmically with the planning horizon, and(ii) the Online Trajectory Synthesis algorithm, which adaptively evaluates allpolicies in a given policy class using sample complexity that scales with thelog-covering number of the given policy class. Both may be of independentinterest.