集合収束から点ごとの収束へ：適応ステップサイズを用いた平均報酬Q学習の有限時間保証

Abstract: 本研究は、非同期実装を伴う平均報酬 Q-learning における最後の反復（last-iterate）収束のための初めての有限時間（finite-time）解析を提示する。ここで検討するアルゴリズムの重要な特徴は、各状態-行動ペアに対する局所クロックとして機能する適応ステップサイズ（adaptive stepsizes）の使用である。我々は、適切な仮定の下で、この Q-learning アルゴリズムによって生成される反復が、平均二乗の意味で、スパン半ノルム（span seminorm）における最適 Q 関数へ収束することを、収束速度が ilde{mathcal{O}}(1/k) であることを示す。さらに、アルゴリズムにセンタリング（centering）ステップを追加することで、同じく収束速度 ilde{mathcal{O}}(1/k) で、中心化された最適 Q 関数に対する点ごとの平均二乗収束も確立する。これらの結果を証明するために、適応ステップサイズが必要であることを示す。すなわち、それらがない場合には、アルゴリズムは正しい目標に収束しない。加えて、適応ステップサイズは、非同期更新の影響を打ち消す一種の暗黙の重要度サンプリング（implicit importance sampling）として解釈できる。技術的には、適応ステップサイズを用いることで、各 Q-learning の更新がサンプル履歴全体に依存するようになり、強い相関が生じ、アルゴリズムは非マルコフの確率近似（SA）スキームとなる。我々のこの課題を克服するためのアプローチは、(1) 非マルコフ SA を時間非一様（time-inhomogeneous）なマルコフ的な再定式化によって言い換えること、ならびに (2) ほとんど確実な（almost-sure）時間変動する上界、条件付けの議論、マルコフ連鎖の集中（concentration）不等式を組み合わせて、適応ステップサイズと反復の間の強い相関を断ち切ることである。本研究で開発された手法は、適応ステップサイズを用いる一般的な SA アルゴリズムの解析に広く適用できる可能性が高い。