[2510.19372] On the Hardness of Reinforcement Learning with Transition Look-Ahead

Statistics > Machine Learning arXiv:2510.19372 (stat) [Submitted on 22 Oct 2025 (v1), last revised 28 Mar 2026 (this version, v2)] Title:On the Hardness of Reinforcement Learning with Transition Look-Ahead Authors:Corentin Pla, Hugo Richard, Marc Abeille, Nadav Merlis, Vianney Perchet View a PDF of the paper titled On the Hardness of Reinforcement Learning with Transition Look-Ahead, by Corentin Pla and 4 other authors View PDF HTML (experimental) 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. Subjects: Machine Learning (stat.ML); Machine Learning (cs.LG) Cite as: arXiv:2510.19372 [stat.ML]   (or arXiv:2510.19372v2 [stat.ML] for this version)   https://doi.org/10.48550/arXiv.2510.19372 Focus to learn more arXiv-issued DOI via DataCite Submission h...