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

By Ruosong Wang, Simon Shaolei Du, Lin F. Yang, Sham M. Kakade. 2020

53 citations recorded by the source corpus.

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 $\varepsilon$ 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 $\varepsilon$-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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Mehdi Abbana Bennani
2. Ruosong Wang
3. Masashi Sugiyama
4. Lin F. Yang
5. Artur Dubrawski
6. Yichong Xu
7. Aarti Singh
8. Amos J. Storkey

In Computer Networks and Communications

1. Lin F. Yang
2. Ruosong Wang
3. Masashi Sugiyama

In Management Science and Operations Research

1. Ruosong Wang
2. Lin F. Yang
3. Artur Dubrawski
4. Yichong Xu
5. Aarti Singh
6. Masashi Sugiyama
7. Sham M. Kakade

Citations in the corpus

• Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent (2020, background): “These works have unlocked the analysis of several properties of Deep Neural Networks, in the context of various applications, such as Transfer Learning (Liu et al., 2019), Noisy Supervision (Hu et al., 2019), Reinforcement Learning (Wang et al., 2020) ...”
• Preference-based Reinforcement Learning with Finite-Time Guarantees (2020, background): “Very recently, Wang et al. [26] show an upper bound of , showing that the optimal H dependence might be linear.”