統計学輪講（第40回）

日時      2008年12月16日(火)    15時50分〜16時40分
場所      経済学部新棟３階第３教室
講演者    本多 淳也 (情報理工M1)
演題      多腕バンディット問題における諸戦略の評価

概要

強化学習においては，新たな情報を得るための探索(exploration)と現時点での
情報を最大限利用する活用(exploitation)のトレードオフが重要になる．
この問題をシンプルな形で表したのが多腕バンディット問題である．
これは複数台あるスロットマシンを選んでプレイするギャンブラーのモデルであ
り，有限回数のプレイで収入期待値の大きい台を選ぶ割合を最大化するような戦
略を考えるものである．
この問題において，最適でない台をプレイすることによる収入期待値の損失(
regret)は総プレイ数nに対してO(log n)より小さくできないことが知られている．
本発表ではAuerらが提案したUCB戦略について紹介する．UCBは小さい計算量でO(
log n)のregretを達成する戦略である．
また，古典的greedy戦略など他の戦略との比較をシミュレーションにより行う．