ICLR paper links deep RL success to 'effective horizon'

The paper argues that many stochastic Markov decision processes "can be solved by performing only a few steps of value iteration on the random policy's Q function and then acting greedily," which the authors — Cassidy Laidlaw, Banghua Zhu, Stuart Russell and Anca Dragan — use to explain why deep RL algorithms often perform well in practice despite relying on random exploration and expressive neural networks.

The ICLR 2024 spotlight paper introduces SQIRL, an algorithm that iteratively learns a near-optimal policy by collecting random-exploration rollouts and then running a limited number of fitted-Q iteration steps over them. From it, the authors derive instance-dependent sample-complexity bounds that are "exponential only in an 'effective horizon' of lookahead and on the complexity of the class used for function approximation," rather than the full problem horizon.

Empirically, they report that "SQIRL performance strongly correlates with PPO and DQN performance in a variety of stochastic environments," which they offer as evidence the theoretical framework is predictive of what practitioners actually see. Code and data are posted at github.com/cassidylaidlaw/effective-horizon.