On the Hardness of Reinforcement Learning with Transition Look-Ahead

Corentin Pla; Hugo Richard; Marc Abeille; Nadav Merlis; Vianney Perchet

stat.MLOct 22, 2025

On the Hardness of Reinforcement Learning with Transition Look-Ahead

Authors: Corentin Pla, Hugo Richard, Marc Abeille, Nadav Merlis, Vianney Perchet

Organizations: CREST, ENSAE · Criteo AI Lab · FairPlay Joint Team · Technion

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 $\ell$ 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 ( $\ell=1$ ) can be solved in polynomial time through a novel linear programming formulation. In contrast, for $\ell \geq 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.

Figures & tables

Figure 1: Hardness of

2

- DVDP . At time

t=0

, the agent is at the root state

s_{0}

and observes, through depth-

2

look-ahead, the candidate vertex states that would become available after playing go and then one of the selector actions

\textsf{pick}_{1},\dots,\textsf{pick}_{k}

. At

s_{0}

, it may either play wait to remain in

s_{0}

and obtain a fresh look-ahead, or play go to transition to

s_{1}

. Once in

s_{1}

, the agent chooses among the currently revealed candidates; if it then moves to a vertex state

s_{v}

, the subsequent payoff is governed by the random variable

X_{v}

. Thus, if the agent commits at time

\tau

, the value of the revealed look-ahead is of the form

\mathbb{E}[\max_{v\in S_{V}(\xi_{\tau})}X_{v}]

. Optimizing the time at which the agent commits at

s_{0}

is then shown to be essentially as hard as the stochastic subset-selection problem underlying the reduction of Mehta et al. (2020) .

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,742 papers

Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
Sep 10, 2026Corentin Pla, Hugo Richard, Marc Abeille +1Reinforcement Learning Approximation Algorithms
CREST, ENSAE · Criteo AI Lab FairPlay Joint Team
Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching
Jan 15, 2026Nadav MerlisReinforcement Learning Regret Minimization in RL
The Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology, Israel
Reinforcement Learning with Multi-Step Transition Predictions: A Bellman Theory
Oct 23, 2026Chenbei Lu, Zaiwei Chen, Tongxin Li +2Reinforcement Learning Model-Based RL
Duffield College of Engineering, Cornell University · Edwardson School of Industrial Engineering, Purdue University · School of Data Science, The Chinese University of Hong Kong (Shenzhen) +2

Sep 10, 2026J/K move · Enter open · S save

Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet

CREST, ENSAE · Criteo AI Lab FairPlay Joint Team

Reinforcement Learning Approximation Algorithms Model-Based RL

Open paper AskPDF 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. Although look-ahead can substantially improve achievable performance, [1] showed that optimal planning with multi-step transition look-ahead is NP-hard. However, this hardness was established using a discount factor close to one. It was therefore unknown whether the problem remains hard for every discount factor, and whether near-optimal planning can nevertheless be performed efficiently. We resolve both questions. First, we show that for every fixed discount factor, exact planning remains NP-hard. Second, we introduce a randomized polynomial-time approximation scheme for every fixed look-ahead depth. Third, we extend our approach to account for unknown transitions. We empirically validate the soundness of our results on the wind-farm storage-control benchmark of [2], showing that our approach, optimally accounting for -step look-ahead information, offers substantially better performance than existing algorithms. [1] Corentin Pla, Hugo Richard, Marc Abeille, Nadav Merlis, Vianney Perchet : On the Hardness of Reinforcement Learning with Transition Look-Ahead [2] Chenbei Lu, Zaiwei Chen, Tongxin Li, Chenye Wu, Adam Wierman : Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach

Abstract

Reinforcement Learning

Explore similar work

Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching

Reinforcement Learning with Multi-Step Transition Predictions: A Bellman Theory