Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
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. 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
Related
- Optimal Multi-Reward Reinforcement Learning
- Optimal Value Inference for Reinforcement Learning
- Optimal Transport Meets Reinforcement Learning: A Survey
- Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model
- Augmented Patient Preference Incorporated Reinforcement Learning (APP-RL) to Estimate the Optimal Dynamic Treatment Regime
BibTeX
@misc{pla2026nearoptimal,
title = {{Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead}},
author = {Corentin Pla and Hugo Richard and Marc Abeille and Vianney Perchet},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11807},
eprint = {2609.11807},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11807},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
AU - Corentin Pla
AU - Hugo Richard
AU - Marc Abeille
AU - Vianney Perchet
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.11807
UR - https://arxiv.org/abs/2609.11807
AB - 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
ER -