Abstract
アクター・クリティック法は実運用において成功を収めているものの、その理論解析にはいくつかの限界があります。具体的には、既存の理論研究は、強い仮定によって探索問題を回避するか、あるいは複雑なアルゴリズム上の修正を伴う非現実的な手法を解析するかのいずれかです。さらに、線形MDPに対して解析されているアクター・クリティック法は、多くの場合、自然政策勾配（NPG）を用い、明示的なパラメータ付けなしに「暗黙的」な政策を構成します。このような政策はサンプル生成（サンプリング）が計算コストを要するため、環境との相互作用が非効率になります。そこで本研究では、有期限（finite-horizon）の線形MDPに焦点を当て、パラメトリックな対数線形政策を用いる楽観的（optimistic）アクター・クリティックの枠組みを提案します。具体的には、アクターには、扱いやすい\textit{logit-matching}回帰目的関数を導入します。クリティックについては、ラングジュバン・モンテカルロによる近似トンプソンサンプリングを用いて楽観的な価値推定を得ます。その結果得られるアルゴリズムが、オンポリシーおよびオフポリシーの設定においてそれぞれ\widetilde{\mathcal{O}}(\epsilon^{-4})および\widetilde{\mathcal{O}}(\epsilon^{-2})のサンプル複雑度を達成することを証明します。私たちの結果は、最先端のサンプル複雑度を達成する点で先行する理論研究と一致していますが、提案アルゴリズムは実運用との整合性がより高いものです。
