以下は登場する数式を(なるべく)直感的に(厳密性をけっこう犠牲にして)解釈したもの。数式多め。簡単のため台は2個とします(K=2)。
- 補足1
収入をxとして、期待値がベストな台の収入の確率分布を、ベストでない適当な台iの収入の確率分布をとします。
このとき分布をもつベストな台があたかもベストでない台であるかのような振舞いを示す確率というのは漸近的に
で与えられるという理論があります(大偏差原理。Dは相互情報量で、分布から見た分布の「遠さ」を表す)。
さて現状で平均収入がベストだったのが台0だったとして、そのプレイ回数を、(理論的な)期待値をとします。また、もう一方の台1のプレイ回数を、期待値をとします(基本的には平均収入が多い台をプレイしていくため)。ここで「台1が実はベスト」ということの「確率」はどれくらいか?ということを考えてみます。
台1に比べて台0は十分試行回数が大きいため、台0は期待値と実際の平均収入がほとんど離れていない()と考えられます。したがって、このような「現状の平均収入と実際の期待値で順位が逆」ということが起きるとしたら、その原因は「台1の平均収入が真の期待値を偶然大きく下回った」ということになります。よって「台1が実はベスト」という確率を求めるためには、台1からの収入がたまたまを下回る確率がどれくらいか、ということを考えればよいことになります。
ここで上の理論が使え、台1が上のような振舞いを示す確率というのは
で与えられます。
以上をまとめると次のようになります
台0 | 台1 | ||
現状 | ベスト | × | |
プレイ数 | |||
ベストでない確率 | ほぼ1 |
この表より、ベストでない台をプレイした回数の期待値というのは
で与えられます。これを最小化するには第1項と第2項をバランスさせればよく、その結果出てくるのが
となり、これが「ベストでない台をプレイする回数」となります。ここでを微分することにより、「n回目にベストでない台をプレイする確率」が程度になると分かります。
- 補足2
UCBが目指すのが「台1の期待値が台0より大きい確率が以下」と判定されたときだけ実際に台0をプレイする(そうじゃない時は情報収集を優先して台1をプレイする)」というような判断基準であり、それを評価するために用いるのが信頼上限であることを上で説明しました。
ここで信頼上限というのは統計学の信頼区間みたいなものであり、ここでは実際に信頼区間を構成してみます。補足1同様に現状で平均収入がベストでない台1の平均収入を[tex:m_1(