# Bridging RL Theory and Practice with the Effective Horizon

arXiv: https://arxiv.org/abs/2304.09853 · HTML: https://mlsanity.com/paper/2304.09853/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 22 references that are in the map.
- First posted on arXiv 19 Apr 2023.

## Builds on (most cited first, 8 of 8)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning](https://mlsanity.com/paper/1810.08272/) (2018)
- [Offline RL Without Off-Policy Evaluation](https://mlsanity.com/paper/2106.08909/) (2021)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [State Entropy Maximization with Random Encoders for Efficient Exploration](https://mlsanity.com/paper/2102.09430/) (2021)
- [StarCraft Micromanagement with Reinforcement Learning and Curriculum Transfer Learning](https://mlsanity.com/paper/1804.00810/) (2018)

## Built on by (most cited first, 30 of 31)

- [Cognitive Architectures for Language Agents](https://mlsanity.com/paper/2309.02427/) (2023)
- [Is Value Learning Really the Main Bottleneck in Offline RL?](https://mlsanity.com/paper/2406.09329/) (2024)
- [All Roads Lead to Likelihood: The Value of Reinforcement Learning in Fine-Tuning](https://mlsanity.com/paper/2503.01067/) (2025)
- [Horizon Reduction Makes RL Scalable](https://mlsanity.com/paper/2506.04168/) (2025)
- [A Dense Reward View on Aligning Text-to-Image Diffusion with Preference](https://mlsanity.com/paper/2402.08265/) (2024)
- [Correlated Proxies: A New Definition and Improved Mitigation for Reward Hacking](https://mlsanity.com/paper/2403.03185/) (2024)
- [Dissecting Deep RL with High Update Ratios: Combatting Value Divergence](https://mlsanity.com/paper/2403.05996/) (2024)
- [Rapidly Adapting Policies to the Real World via Simulation-Guided Fine-Tuning](https://mlsanity.com/paper/2502.02705/) (2025)
- [Segmenting Text and Learning Their Rewards for Improved RLHF in Language Model](https://mlsanity.com/paper/2501.02790/) (2025)
- [Do Transformer World Models Give Better Policy Gradients?](https://mlsanity.com/paper/2402.05290/) (2024)
- [EvIL: Evolution Strategies for Generalisable Imitation Learning](https://mlsanity.com/paper/2406.11905/) (2024)
- [Understanding the Challenges in Iterative Generative Optimization with LLMs](https://mlsanity.com/paper/2603.23994/) (2026)
- [Can we hop in general? A discussion of benchmark selection and design using the Hopper environment](https://mlsanity.com/paper/2410.08870/) (2024)
- [Random Policy Evaluation Uncovers Policies of Generative Flow Networks](https://mlsanity.com/paper/2406.02213/) (2024)
- [Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions](https://mlsanity.com/paper/2601.15353/) (2026)
- [Executable Agentic Memory for GUI Agent](https://mlsanity.com/paper/2605.12294/) (2026)
- [Autonomous Option Invention for Continual Hierarchical Reinforcement Learning and Planning](https://mlsanity.com/paper/2412.16395/) (2024)
- [The Effective Horizon Explains Deep RL Performance in Stochastic Environments](https://mlsanity.com/paper/2312.08369/) (2023)
- [Toward Computationally Efficient Inverse Reinforcement Learning via Reward Shaping](https://mlsanity.com/paper/2312.09983/) (2023)
- [DeLF: Designing Learning Environments with Foundation Models](https://mlsanity.com/paper/2401.08936/) (2024)
- [Online Joint Fine-tuning of Multi-Agent Flows](https://mlsanity.com/paper/2406.04516/) (2024)
- [Minimax Optimal Reinforcement Learning with Quasi-Optimism](https://mlsanity.com/paper/2503.00810/) (2025)
- [Iterative Option Discovery for Planning, by Planning](https://mlsanity.com/paper/2310.01569/) (2023)
- [On shallow planning under partial observability](https://mlsanity.com/paper/2407.15820/) (2024)
- [On the Limits of Tabular Hardness Metrics for Deep RL: A Study with the Pharos Benchmark](https://mlsanity.com/paper/2509.17092/) (2025)
- [On the Effective Horizon of Inverse Reinforcement Learning](https://mlsanity.com/paper/2307.06541/) (2023)
- [Smaller Batches, Bigger Gains? Investigating the Impact of Batch Sizes on Reinforcement Learning Based Real-World Production Scheduling](https://mlsanity.com/paper/2406.02294/) (2024)
- [Is there Value in Reinforcement Learning?](https://mlsanity.com/paper/2505.04822/) (2025)
- [Incoherence in Goal-Conditioned Autoregressive Models](https://mlsanity.com/paper/2510.06545/) (2025)
- [Context-Sensitive Abstractions for Reinforcement Learning with Parameterized Actions](https://mlsanity.com/paper/2512.20831/) (2025)

## Abstract (arXiv)

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