On the Hardness of Reinforcement Learning with Transition Look-Ahead
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915895898537984 |
|---|---|
| author | Pla, Corentin Richard, Hugo Abeille, Marc Merlis, Nadav Perchet, Vianney |
| author_facet | Pla, Corentin Richard, Hugo Abeille, Marc Merlis, Nadav Perchet, Vianney |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19372 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Hardness of Reinforcement Learning with Transition Look-Ahead Pla, Corentin Richard, Hugo Abeille, Marc Merlis, Nadav Perchet, Vianney Machine Learning 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. |
| title | On the Hardness of Reinforcement Learning with Transition Look-Ahead |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2510.19372 |