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

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

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

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

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

上の思想を実現するため、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}

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

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

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