  Deep reinforcement learning (RL) works impressively in some environments and
fails catastrophically in others. Ideally, RL theory should be able to provide
an understanding of why this is, i.e. bounds predictive of practical
performance. Unfortunately, current theory does not quite have this ability. We
compare standard deep RL algorithms to prior sample complexity bounds by
introducing a new dataset, BRIDGE. It consists of 155 deterministic MDPs from
common deep RL benchmarks, along with their corresponding tabular
representations, which enables us to exactly compute instance-dependent bounds.
We choose to focus on deterministic environments because they share many
interesting properties of stochastic environments, but are easier to analyze.
Using BRIDGE, we find that prior bounds do not correlate well with when deep RL
succeeds vs. fails, but discover a surprising property that does. When actions
with the highest Q-values under the random policy also have the highest
Q-values under the optimal policy (i.e. when it is optimal to be greedy on the
random policy's Q function), deep RL tends to succeed; when they don't, deep RL
tends to fail. We generalize this property into a new complexity measure of an
MDP that we call the effective horizon, which roughly corresponds to how many
steps of lookahead search would be needed in that MDP in order to identify the
next optimal action, when leaf nodes are evaluated with random rollouts. Using
BRIDGE, we show that the effective horizon-based bounds are more closely
reflective of the empirical performance of PPO and DQN than prior sample
complexity bounds across four metrics. We also find that, unlike existing
bounds, the effective horizon can predict the effects of using reward shaping
or a pre-trained exploration policy. Our code and data are available at
https://github.com/cassidylaidlaw/effective-horizon
