表形式（タブラー）マルコフ決定過程における政策同定のための最適事後サンプリング

arXiv stat.ML / 2026/5/6

💬 オピニオンDeveloper Stack & InfrastructureIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、有界な有限ホライズンのエピソード型タブラーMDPにおける$(
03b5,
03b4)$-PAC政策同定を扱い、サンプル複雑度などの統計面と計算効率の両方に焦点を当てています。
既存手法は概ね有限時間保証を与えるものの、計算コストが高く実装しづらいこと、さらに$
log(1/
03b4)$への依存が最適でないため、理論・実用の両面で課題があると指摘しています。
著者らは、事後サンプリングにオンライン学習を組み合わせ、MDP内の探索を導くことで、best-policy identificationのためのランダム化かつ計算効率の良いアルゴリズムを提案します。
提案手法は、事後の収縮（posterior contraction）レートも含めてサンプル複雑度の漸近的最適性を満たし、1エピソードあたりの計算量は$O(S^2AH)$です。
MOCAやPEDELといった先行手法と比べて、漸近領域でも保証が意味を保ち、$
log(1/
03b4)$に関する不利な多項式依存を避ける点が特徴で、タブラーMDPでの効率的な政策同定に向けた理論的洞察と実用的手段を提供することを目指しています。

要旨: 有限ホライゾンのエピソード型マルコフ決定過程における $(\varepsilon, \delta)$ -PAC 方策同定問題を研究します。既存のアプローチは近似設定（ $\varepsilon>0$ ）に対して有限時間保証を提供しますが、高い計算コストを伴うため実装が難しく、また $log(1/\delta)$ に関する依存が不最適であるという問題があります。我々は、MDP における探索を導くためのオンライン学習アルゴリズムと、事後サンプリングを組み合わせた、最良方策同定のための確率的かつ計算効率の高い手法を提案します。本手法は、サンプル複雑性において、事後収縮率の観点でも漸近的最適性を達成し、標準的なモデルベース手法と同様に、1 エピソードあたり $O(S^2AH)$ で動作します。MOCA や PEDEL のような先行アルゴリズムとは異なり、我々の保証は漸近領域においても意味のあるものとなっており、 $log(1/\delta)$ に対する不最適な多項式依存を回避します。本研究の結果は、理論的な洞察と、表形式（tabular）MDP における効率的な方策同定のための実用的なツールの両方を提供します。