mlsanityData to 14 Oct 2026

On the Hardness of Reinforcement Learning with Transition Look-Ahead

arXiv 2510.19372 ↗First posted 22 Oct 2025stat.ML cs.LGcited by 4

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

16 of 33 references.

References · 16

  1. 2018Is Q-learning Provably Efficient?cited by 487
  2. 2020Algorithms with Predictionscited by 153
  3. 2019Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysiscited by 40
  4. 2013On the Complexity of Solving Markov Decision Problemscited by 31
  5. 2021Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systemscited by 25
  6. 2021On the Regret Analysis of Online LQR Control with Predictionscited by 22
  7. 2016Learning from the Hindsight Plan -- Episodic MPC Improvementcited by 16
  8. 2018Planning and Learning with Stochastic Action Setscited by 9
  9. 2018On the Complexity of Value Iterationcited by 8
  10. 2023Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictionscited by 8
  11. 2022On Preemption and Learning in Stochastic Schedulingcited by 6
  12. 2013The Value Iteration Algorithm is Not Strongly Polynomial for Discounted Dynamic Programmingcited by 4
4 more
  1. 2020Hitting the High Notes: Subset Selection for Maximizing Expected Order Statisticscited by 4
  2. 2025Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Searchcited by 4
  3. 2017Lower Bound On the Computational Complexity of Discounted Markov Decision Problemscited by 3
  4. 2025Efficiently Solving Discounted MDPs with Predictions on Transition Matricescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Minimax PAC Bounds for Learning in Exogenous Contextual MDPscited by 1
  2. 2026Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batchingcited by 0
  3. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholdingcited by 0
  4. 2026Near-Optimal Reinforcement Learning with Multi-Step Transition Lookaheadcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Reinforcement Learning with Lookahead Information
  2. 2025Computational Hardness of Reinforcement Learning with Partial qπ-Realizability
  3. 2026Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality
  4. 2026Learning from the Near Future: Temporal Self-Distillation for RLVR
  5. 2025Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead
  6. 2026Average-Reward Policy Identification from a Single Continuing Trajectory
  7. 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach
  8. 2024A General Control-Theoretic Approach for Reinforcement Learning: Theory and Algorithms