時間変化する方策を用いるQ学習に対する最小仮定の解析

Abstract

本研究では、割引マルコフ決定過程に対し、時間変化する学習方策（すなわちオンポリシー・サンプリング）を用いるQ-learningの最初の有限時間解析を提示する。最小限の仮定のもとで行い、必要とするのは、状態空間上で既約なマルコフ連鎖を誘導する方策の存在のみである。 ablaまでの収束率について、 ablaの下での最後の反復の収束率を確立する：すなわち ablaを示し、 abla abla を達成するためのサンプル複雑性が ablaのオーダー abla abla abla となることを意味する。これはオフポリシーQ-learningのレートと一致するが、探索に関連するパラメータへの依存はより悪い。また、有限時間における abla abla の収束率も導出する。ここで abla は反復 k における学習方策であり、オンポリシーQ-learningにおける探索と活用（エクスプロイト）のトレードオフを明確にする。オンポリシー学習では探索はオフポリシー手法よりも弱い一方で、学習方策が最適な方策へ収束することで活用の優位性を得られる。我々の理論は数値実験によって裏付けられる。技術的には、急速に時間変化する学習方策は時間非一様なマルコフ雑音を誘発し、最小限の探索のもとでは解析上の大きな困難を生む。これに対処するため、怠惰な遷移行列に基づくポアソン方程式にもとづく分解を開発し、そのマルコフ雑音をマルチンゲール差分項と残差項に分離する。残差は、ポアソン方程式の解に対するQ関数推定と学習方策の両方に関する感度分析によって制御する。これらの技法は、シングルタイムスケールのアクタークリティック手法や学習-in-ゲームアルゴリズムのような、時間変化する方策を持つ他のRLアルゴリズムにも拡張されうる。