探索智能体预判未来状态对强化学习的影响，发现两步以上预判会导致计算难题。
On the Hardness of Reinforcement Learning with Transition Look-Ahead
- 用线性规划解决一步预判的最优决策问题
- 两步及以上预判时问题变为NP难，计算成本激增
- 为预判能力在强化学习中的应用划定可计算边界
我们研究了具有转移预判能力的强化学习（RL），即智能体在做出行动前可预知执行任意ℓ个动作后将到达的状态。尽管此类预测信息能显著提升性能，但我们的研究表明，要最优利用该信息可能带来极高的计算代价。具体而言，当ℓ=1（一步预判）时，可通过一种新颖的线性规划方法在多项式时间内求解最优规划；而当ℓ≥2时，问题变为NP难。本研究精确划分了转移预判强化学习中可处理与不可处理的边界。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。