木構造MDPにおける方策をバンディットアームとして扱うオンライン学習

arXiv cs.AI / 2026/5/7

📰 ニュースIdeas & Deep AnalysisModels & Research

共有:

要点

この論文は、有限ホライズンのTree MDP（T-MDP）に対するオンライン学習を、PAC（サンプル効率）と後悔最小化（regret）という2つの設定で扱います。
方策をバンディットのアームとして見なすことで、T-MDPに標準的なバンディット手法（LUCBとUCB）を適用できることを示します。
主な課題は、方策数が状態数に対して指数的に増える点ですが、著者らは方策間で共有されるデータに基づく信頼度境界の設計を提案します。
方策共有データを活用することで、バンディットアルゴリズムを多項式メモリと1ステップ当たりの多項式計算で実装でき、サンプル効率と後悔の両方に対して実例依存の上界を与えます。
実験では、提案手法が秘匿情報ゲームの一連のベンチマークにおいて既存手法より一貫して優れることが示されます。

note

note

note

note

note