Multi-Step Transition Lookahead を用いたほぼ最適な強化学習

複数ステップの遷移予測を可能にする強化学習（RL）の研究。エージェントは行動決定前に、任意の $\ell$ アクション系列後の状態を観察できる。このルックアヘッドは性能を大幅に向上させる可能性があるが、最適計画はNP困難であることが知られている。本研究では、この問題が割引率が1に非常に近い場合にハードであることを示し、問題の複雑性を分析する。

• 遷移ルックアヘッド付き強化学習における計画問題のNP困難性が証明された。
• 固定有理数割引率でも計画問題はNP困難であることが示された。
• 任意のルックアヘッド深度に対するランダム化多項式時間近似スキームを導入。
• 未知の遷移や確率的報酬に対しても、効率的な準最適計画と学習が可能になった。