ダブル・オラクル効率を用いた政策最適化とオフライン推定のためのモデルベース強化学習

要旨: 大規模な環境における強化学習（RL）は、多くの場合、深刻な計算上のボトルネックに悩まされます。従来の後悔（regret）最小化アルゴリズムでは、計画および統計的推定のオラクルへの、繰り返しでコストの高い呼び出しが必要となるためです。近年、オフラインのオラクル効率的アルゴリズムが研究されてきましたが、その計算複雑性は通常、状態空間と行動空間の濃度（cardinality）に比例してスケールし、大規模または連続的な環境では実行不可能になります。本論文では、log-barrier（対数バリア）とlog-determinant（対数行列式）正則化の観点から、オフラインのオラクル効率的なエピソード型RLを調べることで、この根本的な制限に取り組みます。具体的には、表形式マルコフ決定過程（MDP）に対して、Tが既知の場合に、オフラインの統計的推定オラクルと計画オラクルの両方への呼び出しを合わせてO(H
log\log T)回だけで済み、さらに後悔の上界が最適な
tilde{O}(
sqrt{T})を達成する新しいアルゴリズムを提案します。また、Tが未知の場合には呼び出し回数がO(H
log T)回になります。重要なのは、このオラクル複雑性が、状態空間と行動空間の大きさに完全に依存しない点です。この厳密な独立性により、計画オラクルの複雑性が大幅に低減され、既存のオフライン・オラクル効率的アルゴリズム（Qian et al., 2024）に比べて実質的な改善となります。さらに、本枠組みの汎用性を示すため、無限の状態空間と任意の行動空間を持つ線形MDPへアルゴリズムを一般化します。一般化したアプローチが、有意義な（sub-linear）部分線形の後悔を達成できることを証明します。結果として、本研究は、無限の状態空間と行動空間を持つMDPを解くことが可能な、最初の「二重オラクル効率的（すなわち、統計的推定と方策最適化の両方に対して効率的）」な後悔最小化アルゴリズムを提供し、計算上の実行可能性の限界を大きく押し広げます。