Digital Reactor
統計・確率

UCBはThompson Samplingに追いつけるか：報酬スケールと探索定数を検証する

UCBはThompson Samplingに追いつけるか：報酬スケールと探索定数を検証する

はじめに

前回、バンディットの比較記事で、素のUCB1が最下位という結果が出ました。転換率0.03〜0.08という小さな報酬では、UCB1の探索ボーナスが大きすぎて延々と探索を続け、Thompson Samplingの2.8倍もの後悔を積みました。この結果は「UCBはダメな手法だ」という印象を与えかねません。しかしそれは、UCBを不利な設定で使っただけではないか。UCBが有利になるはずの条件を整えれば、本当にThompsonに追いつくのかを検証します。

仮説はこうです。UCB1のボーナス 2ln⁡t/n\sqrt{2\ln t / n} は、報酬が0から1のスケールにあることを前提に係数2が決められています。報酬が小さいと、このボーナスが信号を覆い隠して過剰に探索します。ならば、(1) 報酬を0.5付近のスケールにする、(2) 探索定数を下げる、(3) 報酬スケールに適応するKL-UCBを使う、のいずれかで差は縮むはずです。結論を先に言うと、探索定数を2から0.1へ下げるだけで、小報酬での後悔は41.6から16.6へ落ち、Thompsonの14.9にほぼ並びました。UCB1の惨敗は、手法の欠陥ではなく既定パラメータの問題でした。

対象読者:

  • バンディットアルゴリズムを実務で使う、あるいは選定する立場の方
  • UCBとThompson Samplingの使い分けを判断したい方
  • 「既定パラメータのまま使う」ことのリスクを具体例で押さえたい方

記事のポイント:

  • UCB1が小報酬で不利になる理由（探索ボーナスのスケール前提）を確かめます
  • 報酬スケール・探索定数・KL-UCBの3条件で、UCBがどこまで追いつくかを測ります
  • 自動で適応する手法と、調整を要する手法の実務的な違いを整理します

仮説：なぜUCB1は負けたのか

UCB1は各アームの推定報酬に 2ln⁡t/na\sqrt{2\ln t / n_a} というボーナスを足し、その和が最大のアームを選びます。このボーナスは、報酬が0から1に分布することを念頭に、係数を2として導かれています。ところが転換率が0.05のような小さい報酬では、報酬の差（信号）は0.01〜0.03のオーダーなのに、ボーナスは0.1以上になることも珍しくありません。信号がボーナスに埋もれ、UCB1はいつまでも全アームをほぼ均等に引き続けます。

だとすれば、条件を変えれば結果は変わるはずです。報酬スケールを上げる、探索定数を下げる、あるいは報酬スケールに合わせて探索量を決めるKL-UCBを使う。この3つを順に検証します。実験はいずれもベルヌーイ報酬、2000試行、120シードの平均です。乱数シードは42に固定しました。

検証1：報酬スケール

まず報酬スケールの影響を見ます。2本のアームの差を0.05に固定したまま、ベースの報酬率を0.03から0.45へ動かし、UCB1とKL-UCBの後悔をThompson比で測ります。

報酬スケールに対する後悔（Thompson比）

UCB1のThompson比は、報酬率0.03で4.1倍だったものが、0.45では1.9倍まで下がりました。スケールを上げるとUCB1の不利は確かに縮みます。ただし、どこまで上げても1.0（Thompsonと同等）には届きませんでした。スケールは効くものの、それだけでは追いつけないということです。

検証2：探索定数のチューニング

次が本命です。UCBのボーナスを c ln⁡t/n\sqrt{c\,\ln t / n} と一般化し、定数 cc を動かします。UCB1の既定は c=2c=2 です。

def ucb_c(rates, rng, c=2.0):
    n = np.zeros(K); s = np.zeros(K)
    for t in range(T):
        arm = t if t < K else int(np.argmax(s / n + np.sqrt(c * np.log(t + 1) / n)))
        r = pull(rates[arm], rng); n[arm] += 1; s[arm] += r

小報酬の設定（0.03/0.05/0.08）で cc を振ると、後悔は cc とともに単調に減りました。

探索定数 c累積後悔
2.0（既定）41.6
1.037.3
0.531.5
0.2524.4
0.116.6

既定の c=2c=2 で41.6だった後悔が、c=0.1c=0.1 では16.6まで落ちました。Thompsonの14.9にほぼ並ぶ水準です。前回UCB1が惨敗した原因の大半は、この過大な既定定数にありました。

探索定数とThompson・KL-UCBの比較

検証3：KL-UCB

探索定数を手で調整する代わりに、報酬スケールに自動で適応する方法もあります。KL-UCBは、各アームの経験平均 p^\hat{p} から、ベルヌーイのKLダイバージェンス d(p^,q)d(\hat{p}, q) を使って上側信頼限界を決めます。

indexa=max⁡{q≥p^a:na d(p^a,q)≤ln⁡t+3ln⁡ln⁡t}\text{index}_a = \max\left\{ q \geq \hat{p}_a : n_a\, d(\hat{p}_a, q) \leq \ln t + 3\ln\ln t \right\}

報酬が小さいと p^\hat{p} 付近のKLの曲がり方が急になり、信頼限界が自動的に狭まります。つまり報酬スケールに応じて探索量が調整されます。小報酬の設定で、KL-UCBの後悔は24.6でした。既定のUCB1（41.6）よりはるかに良く、Thompson（14.9）には届かないものの、手で定数を調整せずにここまで来ます。

UCBをどう使うべきか

小報酬の設定での4手法をまとめます。

小報酬設定での4手法の後悔

UCB1の惨敗は手法の欠陥ではなく、設定の問題でした。探索定数を下げるだけで後悔は41.6から16.6へ、Thompsonの14.9にほぼ並びます。前回の記事で「UCB1が最下位」と出たのは、報酬スケールに対して既定の c=2c=2 が過大だったからです。UCBそのものが弱いわけではありません。

ただし、追いついても追い越してはいません。今回のベルヌーイの設定では、最良に調整したUCBでもThompsonをわずかに上回れませんでした。報酬スケールを上げても、KL-UCBを使っても、Thompson比は1.0を割りませんでした。確率的バンディットの平均後悔で、Thompson Samplingは非常に強い基準線です。

実務で効くのは「調整が要るかどうか」です。最良の探索定数はスケールに依存し、それを知るには報酬の見当が要ります。一方、Thompson SamplingとKL-UCBは報酬スケールに自動で適応し、調整なしで安定して良い成績を出します。UCBを既定の c=2c=2 のまま新しい問題に投げるのは危険で、少なくとも報酬スケールに合わせて cc を見直すか、KL-UCBのような適応版を使うべきです。逆に言えば、UCBには決定的で再現性が高く、事前分布を要さないという別の利点があるので、それらが重要な場面では、きちんと調整したUCBは正当な選択肢になります。

ひとつ差し引くべき点があります。ここでの c=0.1c=0.1 は同じ問題で後から選んだ、いわば理想的な調整です。実運用では事前に最適な cc は分からないので、報酬スケールからの見積もりや、初期データでの調整が要ります。また今回は定常なベルヌーイ報酬に限った比較で、非定常環境や連続報酬、文脈付きの設定では順位が変わりえます。

まとめ

UCBが有利になる条件を整えれば、Thompson Samplingにほぼ追いつきます。探索定数を既定の2から0.1へ下げるだけで、小報酬での後悔は41.6から16.6へ落ち、Thompsonの14.9に肉薄しました。前回の「UCB1が最下位」という結果は、手法の優劣ではなく既定パラメータの不一致が原因でした。ただし追い越すには至らず、しかも最良の定数は問題に依存します。新しい問題にバンディットを入れるなら、まず自動で適応するThompsonかKL-UCBを基準線に置き、UCBを使うなら報酬スケールに合わせて探索定数を必ず見直す、という順で進めるのが安全です。

関連記事

← 技術ブログ一覧へ