Research map / Reinforcement learning / MDPs and planning
The Effective Horizon Explains Deep RL Performance in Stochastic Environments
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SQIRL, a model-free algorithm that explores randomly and runs a few steps of fitted Q-iteration on rollouts, with sample complexity exponential only in a stochastic effective horizon, and shows it correlates with PPO/DQN on sticky-action Bridge environments.
Problem
Existing RL theory relies on strategic exploration with limited function classes and minimax bounds, so it cannot explain why random exploration and neural-network function approximation work in deep RL, especially in stochastic environments.
Approach
Generalizes the deterministic GORP algorithm to stochastic MDPs by replacing rollout averaging with regression of the random policy's Q-function and backing up values with fitted Q-iteration, so sample complexity is exponential only in a stochastic effective horizon (k + log_A(1/Δ_k^2)).
Key results
- SQIRL solves more than two-thirds as many Bridge environments as PPO and nearly as many as DQN, while GORP barely solves any.
- In environments where both PPO and DQN solve, SQIRL matches them 85% of the time; when both fail, SQIRL never succeeds.
- SQIRL's sample complexity has higher Spearman correlation with PPO and DQN than they have with each other.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SQIRL instead of PPO or DQN | RL on sticky-action Bridge environments where PPO and DQN both converge · Sticky-action Bridge environments | success rate | Mixed |
| Use SQIRL instead of PPO and DQN | RL on full-length Atari games · Full-length Atari games | reward | Mixed |
Surprising findings
- More than half of sticky-action Bridge MDPs are approximately 1-QVI-solvable, so acting greedily on the random policy's Q-function is nearly optimal.
- GORP, designed for deterministic environments, barely solves any stochastic Bridge environments.
Limitations
- SQIRL requires more hyperparameter tuning than PPO or DQN and is not presented as a practical algorithm.
- SQIRL still fails in some environments where PPO or DQN succeed.
- Sample complexity is exponential in k and in the effective horizon, and the k-QVI-solvability condition may not hold in all environments.
Experimental setup
Datasets: Bridge Atari
Benchmarks: Bridge sticky-action environments Atari
Metrics: number of environments solved empirical sample complexity Spearman correlation median sample-complexity ratio
Baselines: PPO DQN GORP
Builds on: GORP fitted Q-iteration PPO DQN
Closest papers by meaning
- Stochastic Q-learning for Large Discrete Action Spaces (ICML 2024 · similarity 0.89)
- Random Latent Exploration for Deep Reinforcement Learning (ICML 2024 · similarity 0.88)
- Horizon Reduction Makes RL Scalable (NeurIPS 2025 · similarity 0.88)
- SRL: Scaling Distributed Reinforcement Learning to Over Ten Thousand Cores (ICLR 2024 · similarity 0.87)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.87)
- Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.