On the Hardness of Reinforcement Learning with Transition Look-Ahead

Corentin Pla, Hugo Richard, Marc Abeille, Nadav Merlis, Vianney Perchet
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:55-63, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-pla26a, title = { On the Hardness of Reinforcement Learning with Transition Look-Ahead }, author = {Pla, Corentin and Richard, Hugo and Abeille, Marc and Merlis, Nadav and Perchet, Vianney}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {55--63}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/pla26a/pla26a.pdf}, url = {https://proceedings.mlr.press/v300/pla26a.html}, 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. } }
Endnote
%0 Conference Paper %T On the Hardness of Reinforcement Learning with Transition Look-Ahead %A Corentin Pla %A Hugo Richard %A Marc Abeille %A Nadav Merlis %A Vianney Perchet %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-pla26a %I PMLR %P 55--63 %U https://proceedings.mlr.press/v300/pla26a.html %V 300 %X 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.
APA
Pla, C., Richard, H., Abeille, M., Merlis, N. & Perchet, V.. (2026). On the Hardness of Reinforcement Learning with Transition Look-Ahead . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:55-63 Available from https://proceedings.mlr.press/v300/pla26a.html.

Related Material