Metraipolis › archive › dc_fc8d61fdc75d
Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead — arXiv:2609.11807
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.11807
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T05:55:26.988Z
- SHA-256 of the archived text
7dae0c036fe90814b1b39e91ace9a91e926d8bc39635f3304870ba11693f833a- Stable URL of this page
https://metraipolis.com/documento/dc_fc8d61fdc75d
How to cite
Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead — arXiv:2609.11807 — arXiv (en), https://arxiv.org/abs/2609.11807 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fc8d61fdc75d (Metraipolis archive dc_fc8d61fdc75d, sha256 7dae0c036fe90814b1b39e91ace9a91e926d8bc39635f3304870ba11693f833a)
BibTeX
@misc{dcfc8d61fdc75d,
title = {Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead — arXiv:2609.11807},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.11807},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fc8d61fdc75d; sha256 7dae0c036fe90814b1b39e91ace9a91e926d8bc39635f3304870ba11693f833a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11807. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-11 in cs.LG). Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG). Pagina del lavoro: https://arxiv.org/abs/2609.11807 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T05:44:25.107Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).