# On the Hardness of Reinforcement Learning with Transition Look-Ahead

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 22 Oct 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [On the Complexity of Solving Markov Decision Problems](https://mlsanity.com/paper/1302.4971/) (2013)
- [Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems](https://mlsanity.com/paper/2106.10497/) (2021)
- [On the Regret Analysis of Online LQR Control with Predictions](https://mlsanity.com/paper/2102.01309/) (2021)
- [Learning from the Hindsight Plan -- Episodic MPC Improvement](https://mlsanity.com/paper/1609.09001/) (2016)
- [Planning and Learning with Stochastic Action Sets](https://mlsanity.com/paper/1805.02363/) (2018)
- [On the Complexity of Value Iteration](https://mlsanity.com/paper/1807.04920/) (2018)
- [Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions](https://mlsanity.com/paper/2307.10524/) (2023)
- [On Preemption and Learning in Stochastic Scheduling](https://mlsanity.com/paper/2205.15695/) (2022)
- [The Value Iteration Algorithm is Not Strongly Polynomial for Discounted Dynamic Programming](https://mlsanity.com/paper/1312.6832/) (2013)
- [Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics](https://mlsanity.com/paper/2012.07935/) (2020)
- [Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search](https://mlsanity.com/paper/2502.05720/) (2025)
- [Lower Bound On the Computational Complexity of Discounted Markov Decision Problems](https://mlsanity.com/paper/1705.07312/) (2017)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)

## Built on by (most cited first, 4 of 4)

- [Minimax PAC Bounds for Learning in Exogenous Contextual MDPs](https://mlsanity.com/paper/2606.25170/) (2026)
- [Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching](https://mlsanity.com/paper/2601.10418/) (2026)
- [Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding](https://mlsanity.com/paper/2602.00781/) (2026)
- [Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead](https://mlsanity.com/paper/2609.11807/) (2026)

## Abstract (arXiv)

We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of ℓ actions before deciding its course of action. While such predictive information can drastically improve the achievable performance, we show that using this information optimally comes at a potentially prohibitive computational cost. Specifically, we prove that optimal planning with one-step look-ahead (ℓ=1) can be solved in polynomial time through a novel linear programming formulation. In contrast, for ℓ ≥ 2, the problem becomes NP-hard. Our results delineate a precise boundary between tractable and intractable cases for the problem of planning with transition look-ahead in reinforcement learning.