統計学輪講（第２５回）

日時      2009年11月10日(火)    15時～15時50分
場所      経済学部新棟３階第３教室
講演者    本多 淳也 (情報理工M2)
演題      有界サポートモデル上の多腕バンディット問題における最適戦略

概要

多腕バンディット問題は強化学習における知識の探索と活用のジレンマを定式化した
もので，複数台のスロットマシンを選んでプレイするギャンブラーのモデルとして表
される．この問題では期待値最大でないマシンをプレイしてしまうことによる損失
(regret) の下限が存在する．この理論限界を達成する最適戦略は実際に知られては
いるものの，プレイ毎に複雑な計算を行う必要があるため，実用上は UCB 戦略など
が多く用いられてきた．そこで本発表では各マシンから得られる金額の確率分布が有
界なサポート上にある場合について従来のものとは異なる最適戦略を提案し，この戦
略が凸最適化の手法を用いることにより素早く計算可能なことを示す．また，この戦
略のもとでの regret が速やかに理論限界へと収束することをシミュレーションによ
り確認する．