多腕バンディット問題というのは、ギャンブラーがスロットマシンで金儲けを狙う場合に、
$k$台ある性能の異なるマシンの中から$n$回($n>> k$)プレイする中で各マシンの報酬の期待値を推定し、それに応じて各台のプレイ回数を報酬ができるだけ大きくなるように決める問題です。仮定としては各マシンの報酬がある確率分布の集合に属すること、またその集合（例えばベルヌーイ分布、または正規分布であること）は既知であることです。応用例はギャンブルの他にいくつもあるそうです。
直感的には、期待値の一番高いマシンをできるだけ多くプレイし、その他のマシンはプレイしないことが理想となります。
ここで報酬を大きくするために、regretと呼ばれる’損失量’を小さくしたいのですが、最適戦略では各々のマシンを少なくとも$O(\log n)$回プレイすることが必要であることが知られています。この理論限界を達成する戦略をとれば、一番良いマシンを$n-O(k\log n)$回プレイできることになります。これを漸近的に達成するアルゴリズムを開発、解析することが多腕バンディット問題の目標となります。$\log n$の係数部はKL divergence を期待値制約のもとで最小化した量を用いてあらわされますが、これは分布$F$が期待値$\mu$以上の分布とどれくらい紛らわしくないかを表す指標で、これが小さい場合マシンは相対的にプレイされやすくなります。
発表ではまず先行研究の紹介と比較をしていただきました。既に提案されているUCB(Upper Confidence Bound)戦略と本多さんと竹村彰通先生が2010年に提案されたDMED(Deterministic Minimum Empirical Divergence)戦略、また近年再発見されたThompson samplingの3手法について計算量、性能（相対的に$O(\log n)$の項がどの程度小さくなるか）と解析の容易さの基準から比較しています。確率分布の変数（期待値、分散など）の数が$m$個の場合を$m$パラメータ問題と呼びます。確率分布の集合やコンパクト性、またパラメータの個数に応じても問題の難しさが変わるようです。
DMED戦略では、大まかには理論限界よりも少ない回数をプレイした台を探し、それがあればそれを次に選び、なければ現在の期待値の予想値が最大のものを選びます。UCBよりも計算が速い場合が多く、解析が容易（なため難しい確率分布モデルへも理論が拡張できる）ことが特長です。
確率分布を変えたときに漸近最適性の解析法や証明が異なり、特に個人的に興味深かったのは、一番自然に頭に浮かぶ正規分布の2パラメータ問題（期待値と分散が未知）については、複数パラメータで非コンパクトなこともあり解析が非常に難しいとされてきたことです。
regretを大きくしてしまう意味で問題となるのが、実際は期待値の大きいマシンが偶然期待値が小さいものと判断されてしまい、結果的になかなかそのマシンがプレイされないために期待値最大のマシンの推定を間違えている状態が続く状況です。発表後半ではこのような状況が起こる確率とそれから抜けるための待ち時間などを大偏差原理という理論を用いて評価することで解析を進め、この結果DMED戦略がコンパクト分布に対し漸近最適であること、更に非コンパクトな半有界サポートモデルでも同じ戦略で漸近最適であることを示されました。
実際の発表では、幸か不幸か導入部から山のように質問があり、スライド12枚目で2時間が経過する状況になりました。スライド後半では、なぜ正規分布の解析が難しいのかなども説明していただく予定だったようですが、結果的に数理的な内容は詳しい話をしていただく時間がありませんでした。質問の内容は多様でしたが特に、確率分布が時間定常でない場合はどうなるか、またDMEDとUCBの直感的違いなどについて議論になりました。
0 件のコメント:
コメントを投稿