この記事では、先読みを伴う強化学習（RL）について考察しています。エージェントが行動を選択する前に、$ ext{l}$ アクションのシーケンスを実行した場合に訪れる状態を観察することができる場合、予測情報はパフォーマンスを大幅に向上させる可能性があります。しかし、この情報を最適に活用するためには、相当な計算コストがかかることが示されています。具体的には、1ステップ先読みの場合（$ ext{l}=1$）、最適計画が多項式時間内に解決できることを新しい線形計画法の定式化を通じて証明します。一方で、$ ext{l} ext{≥} 2$の場合、この問題はNP困難であることが示されています。本研究は、先読みを用いた強化学習における計画問題の扱いやすいケースと扱いにくいケースとの明確な境界を delineateしています。