補足

以下は登場する数式を(なるべく)直感的に(厳密性をけっこう犠牲にして)解釈したもの。数式多め。簡単のため台は2個とします(K=2)。

  • 補足1

収入をxとして、期待値がベストな台の収入の確率分布をp^*(x)、ベストでない適当な台iの収入の確率分布をp_i(x)とします。
このとき分布p^*をもつベストな台があたかもベストでない台p_i(x)であるかのような振舞いを示す確率というのは漸近的に
\exp\left(nD(p_i;p^*)\right)
で与えられるという理論があります(大偏差原理。Dは相互情報量で、分布p^*から見た分布p_iの「遠さ」を表す)。
さて現状で平均収入がベストだったのが台0だったとして、そのプレイ回数をn_0、(理論的な)期待値をE_0とします。また、もう一方の台1のプレイ回数をn_1、期待値をE_1とします(基本的には平均収入が多い台をプレイしていくためn_0\gg n_1)。ここで「台1が実はベスト」ということの「確率」はどれくらいか?ということを考えてみます。
台1に比べて台0は十分試行回数が大きいため、台0は期待値と実際の平均収入がほとんど離れていない(m_0\approx E_0)と考えられます。したがって、このような「現状の平均収入と実際の期待値で順位が逆」ということが起きるとしたら、その原因は「台1の平均収入が真の期待値を偶然大きく下回った」ということになります。よって「台1が実はベスト」という確率を求めるためには、台1からの収入m_1がたまたまE_0を下回る確率がどれくらいか、ということを考えればよいことになります。
ここで上の理論が使え、台1が上のような振舞いを示す確率というのは
\exp\left(n_1 D(p_0;p_1)\right)
で与えられます。

以上をまとめると次のようになります

台0 台1
現状 ベスト ×
プレイ数 n_0 \mbox{}\gg\mbox{} n_1
ベストでない確率 \exp\left(n_1D(p_0;p_1)\right) ほぼ1

この表より、ベストでない台をプレイした回数の期待値というのは
n_0\exp\left(n_1D(p_0;p_1)\right)+n_1
で与えられます。これを最小化するには第1項と第2項をバランスさせればよく、その結果出てくるのが
n_1=\frac 1 {D(p_0|p_1)} \log n_0\approx \frac 1 {D(p_0|p_1)} \log n
となり、これが「ベストでない台をプレイする回数」となります。ここで\log n微分することにより、「n回目にベストでない台をプレイする確率」が1/n程度になると分かります。

  • 補足2

UCBが目指すのが「台1の期待値が台0より大きい確率が\frac {1}{n}以下」と判定されたときだけ実際に台0をプレイする(そうじゃない時は情報収集を優先して台1をプレイする)」というような判断基準であり、それを評価するために用いるのが信頼上限であることを上で説明しました。
ここで信頼上限というのは統計学の信頼区間みたいなものであり、ここでは実際に信頼区間を構成してみます。補足1同様に現状で平均収入がベストでない台1の平均収入を[tex:m_1(

多腕バンディット問題とUCB解説

ホントは7月中には書く予定だったんですが遅くなってしまった。いちおう数学があんま分からなくても「補足」以外は読み物になってるつもり。
元ネタは
"Finite-time Analysis of the Multiarmed Bandit Probrem"
http://homes.dsi.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf
という論文。これはコンピューター囲碁とかで結構流行ってるらしい話で、僕が知ったのもkmo2さん経由でそっから。そのなかの証明を(厳密さを犠牲にして)直感的に理解できるように解釈しなおして研究室輪講で紹介したのが今回の話です。

多腕バンディット問題というのはスロットマシンをプレイするギャンブラーのモデルで、K個のマシンがある場合をK腕バンディット問題といいます。K個のマシンはそれぞれ設定が違って、1プレイの費用は同じですが、玉が出やすい台もあれば出にくい台もあります。ただし普通のスロの場合と違って「設定6よりいい台は存在しない」といった前提はありません。つまりもしかしたら設定7とか8が存在するかもしれない、ということです。
さてプレイヤーはK個のマシンを前にして、なるべく有限回のプレイで利益を最大にしたいと考えます。ここで生じるのは
・ある程度の回数をプレイしないとその台がヘボいかどうか分からない
・かといってヘボい台を何度もプレイしてると損
という問題で、この「今のところ効率は良くないけどもしかしたら実はベストかもしれない台」というのをどのくらいの頻度でプレイするか、というのがテーマになります。

さてさてこの問題はプレイ回数nが十分大きい場合には理論限界があり、「ベストでない台をプレイする回数は確率1で\mathrm{O}(\log n)以内に抑えることができる、逆にそれより小さく抑えることは不可能」というのが知られています(補足1)。ここで(\log n)/n\to 0なので、ほとんど全ての割合のプレイをベストの台で行うことが出来る、ということになります。このような理想的な台の選択を行った場合、n回目にベストでない台でプレイする確率は1/n程度となります。
一方で、この理論限界を達成する台の選択方法というのは複雑で実用的ではない(それと『漸近的に最適』ということしか示せない)、ということである程度シンプルな選択法「UCB」によって理論限界を達成した(ただし\log nの係数部はちょっと悪くなる)、というのがこの論文になります。

さて、台選びの方法として目指すのは上で述べた結果から「ベストでない台をプレイする確率を(ホントは0にしたいんだけど不可能だから)1/n程度に抑えたい」というものになります。
ここで補足1と同様にK=2とし、現状で台0のほうが台1に比べて平均収入が大きかったとします。そこで「台1の期待値が台0より大きい確率が\frac {1}{n}以下」と判定されたときだけ実際に台0をプレイする(そうじゃない時は情報収集を優先して台1をプレイする)ようにすれば、全体としてベストでない台をプレイする確率を1/n程度に抑えることができるだろう、というのがUCB(Upper Confidence Bound)の基本的な考え方となります。ここで「台1の期待値が台0より大きい確率」というのを計算するために用いているのがUpper Confidence Bound(無理やり訳すなら信頼上限とか)となります(補足2)。

上の思想を実現するため、UCBにおいては次の指標(以下小文字ucb)を台ごとに比較します。
台の番号をiとし、台iに関する現状の平均収入をm_i、台iをプレイした回数をn_i、台iの出玉の分散(バラツキ)に相当する量をV_iとして、台iのucb_iは次式となります。

ucb_i=m_i+\sqrt{\left(\frac{V_i}{n_i}\right)\log n}

プレイヤーは最初に全ての台を1回ずつプレイし、それ以降はその時点でucb_iが最大となった台iをプレイします。
さてさてUCBのキモはucbの2項目で、もしこれがなくてm_iだけだったら「今の次点で平均収入が最高の台をプレイする」という非常に安直な方法になります。しかし2項目の影響がプレイした回数が少ない(n_iが小さい)ほど大きく効いてくるので、「この台は今のところ割は良くない(m_iが小さい)けど試行回数がまだ少ないからもしかしたらいい台かもしれない」というようなことを考慮に入れたモデルになっているわけです。ここでV_iというのは問題のモデルによって様々な形があり、どれも「バラツキを大きめに見積もった」という値になっています。でもぶっちゃけ1とか定数でもいいです。
で、このUCBのもとで、ヘボな台をプレイしてしまう回数というのは理論限界と同じく\log nで抑えられる、ということを論文では長々と証明しています(補足2)。

さてさてUCBという話が流行ってるのはコンピューター囲碁の話。こっちの方面は全然知らないので半分予想で書いてるので怪しいところがあったら指摘してください。
囲碁ってのは今のところコンピューターが圧倒的に弱いゲーム(弱いアマチュアのレベル。オセロとかチェスはコンピューターの方が強くて将棋も最近はプロとそこそこ勝負になる)で、理由は
・単純に打てる手の組み合わせが将棋とかチェスより圧倒的に多い
・飛車角クイーンみたいな分かりやすい「大駒」みたいのがないので評価関数を立てにくい
というようなもの。そんなわけでコンピューター囲碁はかなり手探り感があるわけですが、そこで最近流行ってるのがゲーム木の探索にUCBを使おうというもの(あとモンテカルロ)。これは(たぶん)「深く読む手」というのをマシンとみなして、「n_i手目まで読んだ時点ではそこまで評価関数が良くないけどもう少し深く読んだら実はいい手かもしれない」みたいなことをやるんだと思います。たぶん。

さてUCBの日本のスロ(台が無数にたくさんあるけど設定は6まで)への応用についてですが、ぶっちゃけ僕はスロをやったことがないのでこれ以上深入りするとボロが出そうなのでよく分からんです。