計算上の障壁を打ち破る：低ランクMDPに対する証明可能に効率的なアクター・クリティック

要旨: 強化学習（RL）は、未知の環境との相互作用を通じてエージェントが最適な方策を学習する、逐次的意思決定のための基本的枠組みである。関数近似がある設定では、多くの既存のRLアルゴリズムが好ましいサンプル計算量を達成するが、しばしば計算的に扱いにくいオラクルに依存している。本論文では、低ランクのマルコフ決定過程（MDP）において、一般に採用されるRLオラクルの明確な階層を確立するために、計算の代理として教師あり学習を用いる。この階層は、教師あり学習が効率的に解けるならば、方策評価が最も計算効率の高いオラクルであることを示す。この観察に動機づけられて、我々は方策評価オラクルのみに依存する、新しい楽観的アクター・クリティックアルゴリズムを提案する。我々は、このアルゴリズムが低ランクMDPに対する既存のサンプル計算量の保証を上回ることを証明し、さらに従来研究で一般に仮定されてきた、計算コストの高い計画オラクルや最適化オラクルを回避する。さらに、理論結果をおおよそ低ランクのMDPへ拡張し、この設定が現実世界の幅広い環境のクラスを捉えることを示す。最後に、いくつかの標準的なGym環境に対する実験によって、理論結果の妥当性を検証する。