On the Hardness of Reinforcement Learning with Transition Look-Ahead

2025/10/22 by Corentin Pla, Hugo Richard, Pla, Corentin +7
Computer Science · #Reinforcement Learning in Robotics #AI-based Problem Solving and Planning #Artificial Intelligence in Games

paper · pdf · doi:10.48550/arxiv.2510.19372

Abstract

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.

Citations

• Efficiently Solving Discounted MDPs with Predictions on Transition Matrices
• Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
• Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions
• On Preemption and Learning in Stochastic Scheduling
• Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems
• On the Regret Analysis of Online LQR Control with Predictions
• Hitting the High Notes: Subset Selection for Maximizing Expected Order\n Statistics
• Algorithms with Predictions
• Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis
• On the Complexity of Value Iteration
• Is Q-learning Provably Efficient?
• Planning and Learning with Stochastic Action Sets
• Lower Bound On the Computational Complexity of Discounted Markov Decision Problems
• Learning from the Hindsight Plan -- Episodic MPC Improvement
• The Value Iteration Algorithm is Not Strongly Polynomial for Discounted Dynamic Programming
• Exponential Lower Bounds For Policy Iteration
• Complexity of finite-horizon Markov decision process problems
• On the Complexity of Solving Markov Decision Problems
• The Complexity of Markov Decision Processes
• Reinforcement Learning: An Introduction

Related

• Reinforcement Learning with Lookahead Information
• Planning and Learning with Adaptive Lookahead
• Explicit Explore-Exploit Algorithms in Continuous State Spaces
• Searching for Plannable Domains can Speed up Reinforcement Learning
• Assured RL: Reinforcement Learning with Almost Sure Constraints