マルコフ決定過程における方策テスティング（Policy Testing）

概要: 静的サンプリングを伴う生成モデルの下で、固定信頼度（fixed-confidence）設定における割引マルコフ決定過程（MDP）における方策テスティング問題を研究します。目標は、サンプル数を最小化しつつ、与えられた方策の価値が所定の閾値を超えるかどうかを判断することです。まず、妥当なアルゴリズムが満たさなければならない、事例依存の下界を導出します。この下界は、非凸制約を伴う最適化問題として定式化されることによって特徴づけられます。この定式化に導かれて、新しいアルゴリズムを提案します。この設計パラダイムは、最良腕の識別（best-arm identification）のような純粋探索（pure exploration）問題では一般的ですが、MDPで生じる非凸制約が大きな困難を引き起こします。これに対処するために、目的関数と制約の役割を入れ替えることで、下界問題を再定式化し、非凸な目的関数を持つ一方で凸な制約を持つ別の問題を得ます。この再定式化は、新たに構築した逆向きMDP（reversed MDP）における方策最適化タスクとして解釈できることを認めます。さらに、グローバルなKL制約が、積の形のボックス（product-box）に関するサブ問題の族へと厳密に分解できることを示します。これらのサブ問題は、射影付き方策勾配によって解かれ、外側の予算探索（outer budget search）によって結合されます。方策テスティングにとどまらず、この再定式化および逆向きMDPという観点は、方策評価や最良方策の識別を含む、MDPにおける他の純粋探索タスクへの拡張も示唆します。