探索と活用：UCB・トンプソン抽出・多腕バンディット

多腕バンディットと後悔の定式化

スロットマシン（腕）が K 台あり、腕 i を引くと未知の分布から報酬が出ます。各腕の期待報酬を μ_i、最良腕の期待を μ* = max_i μ_i と書きます。あなたは合計 T 回引けますが、どの腕が当たりかは事前に分かりません。良い腕だと分かっている腕を引き続けたい（活用）が、まだ試していない腕に隠れた最良腕があるかもしれない（探索）。この緊張が強化学習の核にある探索と活用のトレードオフで、バンディットはそれを最も純粋な形に切り出した設定です。

性能は累積報酬そのものではなく、後悔(regret) で測ります。

R(T) = T·μ* - E[ Σ_{t=1..T} μ_{a_t} ]
     = Σ_i Δ_i · E[ N_i(T) ]
   Δ_i    : 最良腕とのギャップ μ* - μ_i
   N_i(T) : T回中に腕 i を引いた回数

後悔は「常に最良腕を引いていれば得られたはずの報酬」と「実際に得た報酬の期待」の差で、第2式が示すとおり各劣腕を引いた回数 N_i(T) にギャップ Δ_i を掛けて足したものです。つまりアルゴリズムの仕事は、劣腕を引く回数をいかに小さく抑えるかに尽きます。後悔が T に比例して増える（線形後悔）なら最良腕を一定割合で外し続けている証拠で、目標は後悔を T に対して劣線形、理想的には対数オーダーに抑えることです。

ε-greedyの限界

最も素朴な方策がε-greedyです。確率 1-ε で現在の推定平均が最大の腕を引き（活用）、確率 ε で一様ランダムに引きます（探索）。

確率 1-ε : argmax_i μ̂_i を引く（活用）
確率 ε   : 一様ランダムに引く（探索）
   μ̂_i : 腕 i の標本平均

ε を固定すると、探索分の ε の割合で劣腕を引き続けるため、後悔は T に比例して線形に増えてしまいます。ε を時間とともに 1/t 程度で減衰させれば対数後悔に近づけられますが、減衰スケジュールの調整が要り、何より探索が腕の不確実性を見ていないのが弱点です。十分試して当たりだと確信できた腕も、見込みのない腕も、探索時には一様に等確率で引く。この「無差別な探索」を、不確実性に応じて配分し直すのがUCBとトンプソン抽出です。なおQ学習とDQNでもεグリーディは探索の基本手段として登場しますが、そこでも同じ「無差別さ」が探索効率の課題になります。

UCB：楽観主義による信頼区間

UCB（Upper Confidence Bound） は「不確実性の前では楽観的に」という原理に立ちます。各腕について標本平均 μ̂_i だけでなく、その推定がどれだけ信頼できるかを表す信頼区間の上端を計算し、上端が最大の腕を引きます。

UCB_i(t) = μ̂_i + sqrt( 2·ln(t) / N_i(t) )
   左項 μ̂_i        : これまでの推定平均（活用の項）
   右項 sqrt(...)  : 信頼区間の幅（探索の項）

右の幅の項は、引いた回数 N_i(t) が少ない腕ほど大きくなり、時間 t が進むほど（ln t で）ゆっくり広がります。あまり引いていない腕は「実は良いかもしれない」と上端が持ち上がるので自然に選ばれ、引くほど幅が縮んで推定平均そのものに近づく。探索と活用が一つの式に同居しているのが要点です。

この幅が sqrt(ln t / N_i) の形を取る根拠がHoeffding不等式です。各報酬が [0,1] に収まる独立な確率変数なら、n 回の標本平均が真の平均から u 以上ずれる確率は次式で抑えられます。

P( |μ̂_i - μ_i| ≥ u ) ≤ 2·exp( -2·n·u² )

右辺を時刻ごとの許容失敗確率（おおむね t の負ベキ）に等しいと置いて u について解くと、ちょうど u ≈ sqrt(ln t / n) が出てきます。これがUCBの幅の正体で、係数の 2 はこの確率を十分小さく抑えるための余裕です。

トンプソン抽出：事後分布からのサンプリング

トンプソン抽出（Thompson sampling） は同じ問題をベイズの枠組みで解きます。各腕の未知パラメータ μ_i に事前分布を置き、観測した報酬でベイズ更新して事後分布を保ちます。腕を選ぶときは、各腕の事後分布から1標本を引き、その標本値が最大の腕を選びます。

ベルヌーイ報酬（当たり/外れ）の典型では、共役性からベータ分布が使えます。

事前    μ_i ~ Beta(1, 1)            # 一様
更新    当たりで α_i += 1、外れで β_i += 1
選択    各腕で θ_i ~ Beta(α_i, β_i) を1つサンプルし argmax_i θ_i を引く

この「事後から1標本引いて最大を選ぶ」操作が、探索と活用を確率的に両立させます。データが少なく事後分布が広い腕は、ときどき大きな θ_i をサンプルして選ばれる（探索）。データが溜まり事後が真値の周りに尖った腕は、サンプルがほぼ推定平均になり、良ければ高確率で選ばれ続ける（活用）。確率マッチング――「その腕が最良である事後確率に比例して引く」――が自然に実現され、これがトンプソン抽出の本質です。

両者は導出の哲学が正反対（楽観の決定論 対 事後のランダム化）ですが、どちらも劣腕の引数を ln T で抑え、同じ対数後悔オーダーに到達します。実務ではトンプソン抽出が実装の単純さと遅延フィードバックへの頑健さで好まれる場面が多い一方、UCBは挙動が決定的で解析・監視しやすい利点があります。

Lai-Robbins下界：対数後悔は最善

UCBもトンプソン抽出も対数後悔ですが、これは「たまたま良い」のではなく情報理論的に到達可能な限界に達していることが効きます。Lai と Robbins は、十分広いクラスの方策に対して、後悔がどんなに頑張っても次の下界を下回れないことを示しました。

liminf_{T→∞}  R(T) / ln T  ≥  Σ_{i: Δ_i>0}  Δ_i / KL(μ_i || μ*)
   KL(μ_i || μ*) : 腕 i の報酬分布と最良腕の報酬分布の
                   カルバック・ライブラー距離

直感はこうです。劣腕 i を「最良腕ではない」と統計的に確信するには、その腕を一定回数引いて報酬分布の違いを見分ける必要があります。二つの分布を見分ける難しさを測るのがKLダイバージェンスで、分布が似ている（KLが小さい）ほど見分けに多くの標本が要り、その腕を引く回数が増える。だから後悔の下界が 1/KL に比例して大きくなります。

重要なのは、この下界に係数まで含めて漸近的に達する方策（KL-UCBやトンプソン抽出）が存在することです。つまり対数後悔は妥協ではなくこの問題で原理的に到達できる最善であり、UCBとトンプソン抽出はその最善を、まったく異なる二つの道筋――頻度論の集中不等式とベイズの事後サンプリング――から実現していることになります。

まとめ

多腕バンディットは探索と活用のトレードオフを最も純粋に切り出した設定で、性能は後悔、すなわち劣腕の引数とギャップの積の総和で測ります。ε-greedyは不確実性を無視した一様探索のため線形後悔に陥りがちです。UCBはHoeffding不等式由来の信頼区間で楽観的に選び、トンプソン抽出は事後分布からのサンプリングで確率マッチングを行う。哲学は正反対ながら両者とも対数後悔を達成し、それがLai-Robbinsの下界で理論上の最善だと裏づけられます。各手法を「劣腕の引数をどう ln T で抑えているか」で読み解くと、設計思想が一貫して見えてきます。