「そろそろ攻めるか」を勘で決めない。UCBとThompson samplingをε-greedyと競走させた
前回のε-greedyは、「10%の確率でランダムに冒険する」というシンプルな仕組みで探索と活用のバランスを取った。でも実装しながらずっと気になっていたことがある。探索するかどうかを、なぜサイコロで決めるのか。 今どれくらい迷っているか——つまり不確実性そのもの——を測って、それに応じて探索すればいいのではないか。
それをやるのが、バンディット問題の2大定番、UCBとThompson samplingだ。今回はこの2つを実装して、前回と同じ10本腕バンディット(各腕の真の期待報酬は正規分布から生成、未知)でε-greedyと競走させた。
2つの「不確実性の使い方」
UCB (Upper Confidence Bound) は楽観主義者だ。各腕の推定値に「その腕をあまり引いていないなら大きくなるボーナス」を上乗せし、合計が最大の腕を選ぶ。
a = np.argmax(q_est + c * np.sqrt(np.log(t + 1) / n)) # n: 各腕を引いた回数「よく知らない相手のことは、良い方に想像しておく」。試していない腕はボーナスが大きいから自然に選ばれ、試すほどボーナスが縮んで実力勝負になる。
Thompson sampling は空想家だ。各腕の期待報酬について事後分布(信念)を持ち、毎回その信念から乱数で1つの世界をサンプルして、その空想の世界でベストな腕を選ぶ。
post_mean = (n * q_est) / (1 + n) # 事後平均 (事前 N(0,1))
post_var = 1 / (1 + n) # 事後分散
a = np.argmax(rng.normal(post_mean, np.sqrt(post_var)))自信のない腕は信念の幅が広いので、たまに「もしかしたら最強かも」という空想を引き当てて選ばれる。自信がつくにつれ空想は現実に収束する。どちらも「探索率」というパラメータを勘で決める必要がなく、探索が不確実性から自動的に導かれるのが共通点だ。
競走結果: 後悔の伸び方が違う
1000回の独立試行で、累積後悔(最適腕との期待報酬差の積み上げ)を平均した。
2000ステップでの累積後悔は ε-greedy 395 / UCB 185 / Thompson 79。差は歴然だが、注目したいのは絶対値より曲線の形だ。
- ε-greedyの後悔は直線で伸び続ける。 最適腕がとっくに分かっていても、永遠に10%はサイコロを振り続けるからだ。探索が「成長しない」
- UCBとThompsonは対数的に寝ていく。 学ぶほど探索が減り、後悔の追加分がゼロに近づく
- ただし序盤250ステップまでは、UCBはε-greedyより後悔が大きい。UCBは全部の腕を義務的に一通り試すコストを先払いするからで、「賢い方法は序盤から常に得」ではない
中身を見る: 縮むヒゲと、尖る信念
UCBの「推定値+ボーナス」がどう動くかをスナップショットで見る。
最終的に最適腕は2000回中1884回引かれ、そのヒゲ(不確実性)はほぼ消える。一方で見込みの薄い腕のヒゲは長いまま残る——「よく知らないから、まだ夢を見る余地がある」状態が、そのまま可視化される。
Thompsonの信念の進化はアニメーションが分かりやすい。
最適腕の信念だけがぐんぐん尖り、真の値(点線)に吸い付いていく。面白いのはダメな腕の信念は幅広いまま放置されることだ。「アイツの実力を正確に知る」こと自体には価値がなく、「自分の選択に関係あるところだけ詳しくなる」。無駄のない学び方をする。
手を動かして意外だったこと
一番の発見は、ε-greedyの敗因が「探索が下手」ではなく**「探索をやめられない」**ことだった点だ。序盤の立ち上がりでは3者に大差はない。差がつくのは、UCBとThompsonが「もう分かったから」と探索を畳んでいく中盤以降で、ε-greedyだけが機械的に10%の冒険を続けてジリジリ後悔を積む。前回「εの値は結果に効く」と学んだが、本当の問題はεの値ではなく、εが時間とともに変わらないことだったわけだ。
もう1つはUCBの序盤コスト。全腕を律儀に試すぶん、最初の250ステップはε-greedyより成績が悪い。短期決戦ならサイコロの方がマシな場面もある——「どの時間軸で評価するか」で優劣が入れ替わるのは、手法比較のいつもの罠だ。
人の意思決定に翻訳すると、UCBは「未知の選択肢には楽観ボーナスを上乗せして試す」、Thompsonは「自分の中の確信度から未来を1つ空想して、その世界の最善手を打つ」。共通するのは、迷いの量を測って、迷いに比例して冒険することだ。新しい環境では大胆に、勝手が分かってきたら着実に。探索の割合そのものが経験とともに成長していく。いつまでも同じ割合でサイコロを振っているとしたら、それは慎重なのではなく、たぶん自分の確信度を測っていないだけなのだ。
まとめ
- 前回のε-greedyと同じ10本腕ガウスバンディットで、UCB(c=2)とThompson sampling(正規事後)を実装して競走させた
- 累積後悔@2000ステップ(1000試行平均): ε-greedy 395 / UCB 185 / Thompson 79。最適腕選択率は0.83 / 0.90 / 0.94
- ε-greedyの後悔は直線で伸び続ける(探索率が固定のため)。UCB/Thompsonは不確実性の減少に伴い探索が自動で減り、後悔が対数的に頭打ちになる
- ただしUCBは全腕を試す先行投資のため、序盤250ステップまではε-greedyより後悔が大きい——評価する時間軸で優劣は入れ替わる
- UCBは「引いていない腕のボーナス(ヒゲ)」が、Thompsonは「信念分布の幅」が探索を駆動する。どちらも最適腕の周辺だけ詳しくなり、ダメな腕の不確実性は放置される——学びのリソース配分として合理的
