エントロピー正則化されたマルコフ決定過程およびゲームにおける計画

要旨: 本稿では、環境の生成モデルが与えられたもとで、エントロピー正則化されたマルコフ決定過程および2人ゲームにおける価値関数を推定するための新しい計画アルゴリズムであるSmoothCruiserを提案する。SmoothCruiserは、正則化によって促進されるベルマン作用素の滑らかさを利用することで、所望の精度εに対して問題非依存のサンプル複雑度がO~(1/epsilon^4)のオーダーで達成されることを示す。これに対し、正則化されない設定では、最悪の場合に保証された多項式サンプル複雑度を持つ既知のアルゴリズムは存在しない。