補足 - ソクラテスのチラシの裏だったもの

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

補足１

収入を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が実はベスト」ということの「確率」はどれくらいか？ということを考えてみます。
台１に比べて台０は十分試行回数が大きいため、台０は期待値と実際の平均収入がほとんど離れていない（ $m_0\approx E_0$ ）と考えられます。したがって、このような「現状の平均収入と実際の期待値で順位が逆」ということが起きるとしたら、その原因は「台１の平均収入が真の期待値を偶然大きく下回った」ということになります。よって「台１が実はベスト」という確率を求めるためには、台１からの収入 $m_1$ がたまたま $E_0$ を下回る確率がどれくらいか、ということを考えればよいことになります。
ここで上の理論が使え、台1が上のような振舞いを示す確率というのは
$\exp\left(n_1 D(p_0;p_1)\right)$
で与えられます。

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

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

この表より、ベストでない台をプレイした回数の期待値というのは
$n_0\exp\left(n_1D(p_0;p_1)\right)+n_1$
で与えられます。これを最小化するには第１項と第２項をバランスさせればよく、その結果出てくるのが
$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$ 程度になると分かります。

補足２

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