ベイズA/Bテストとバンディット：Thompson Samplingで後悔を最小化する

はじめに

A/Bテストは、勝者が決まるまで、負けている案にも均等にトラフィックを流し続けます。差が明らかになるまでの間、機会損失は積み上がります。トラフィックが貴重だったり、試したい施策が多かったりする場面では、この「決めるまでの損」が無視できません。

今回、真の転換率が0.03・0.05・0.08の3施策を題材に、固定割当A/B・ε-greedy・UCB1・Thompson Samplingを3000試行ずつ回して累積後悔（regret）を比べました。最も低かったのはThompson Samplingで累積後悔17.7、最良の施策を選べた割合は84%で、固定割当A/Bは24.8、ε-greedyは30.5でした。意外だったのは素のUCB1で、転換率が小さい領域では探索しすぎて59.9と最も悪い結果でした。この記事では、後悔という評価軸でオンライン意思決定を測り、なぜThompson Samplingが軽くて強いのかを実装で確かめます。

対象読者:

• Webの施策評価・レコメンド・価格最適化に関わる方
• ベイズ更新の基礎があり、探索と活用のトレードオフを定量的に見たい方
• A/Bテストの機会損失を減らしたいと考えている方

記事のポイント:

• 後悔（regret）という評価軸でオンライン意思決定を測ります
• ε-greedy・UCB1・Thompson Samplingの違いを理解します
• Thompson Samplingが固定割当A/Bより累積後悔を抑える様子を確認します

---

問題設定：マルチアームドバンディット

複数の施策（アーム）があり、それぞれの真の報酬率は未知です。引くたびに確率的な報酬が返ります。目的は累積報酬の最大化で、これは累積後悔の最小化と同じことです。後悔は、毎回最適なアームを引いていれば得られた報酬と、実際に選んだアームの報酬との差の総和で定義します。

$$\mathrm{regret}(T) = \sum_{t=1}^{T} \left( \mu^\star - \mu_{a_t} \right)$$

$\mu^\star$ は最適アームの報酬率、$\mu_{a_t}$ は時刻 $t$ に選んだアームの報酬率です。良い戦略ほど後悔の増え方が緩やかになります。理想は、序盤に少し探ってすぐ最良に集中し、後悔を対数オーダーに抑えることです。

代表的な戦略

ε-greedyは、確率 $\varepsilon$ でランダムに探索し、それ以外は現時点の最良を引きます。単純ですが、$\varepsilon$ を固定する限りランダム探索を延々と続けるため、後悔は線形に増え続けます。

UCB1は、各アームの推定報酬に不確実性の上乗せ $\sqrt{2\ln t / n_a}$ を足し、その和が最大のアームを選びます。まだ引いていないアームを楽観的に評価して探索を促す、頻度論的な信頼区間ベースの手法です。

Thompson Samplingは、各アームの報酬率の事後分布からサンプルを1つ引き、その値が最大のアームを選びます。ベルヌーイ報酬ならBeta分布が共役なので、成功で $\alpha$、失敗で $\beta$ を足すだけで事後が更新できます。実装も数行で済みます。

def thompson(rng):
    a = np.ones(K); b = np.ones(K)          # Beta(1,1) からスタート
    for t in range(T):
        arm = int(np.argmax(rng.beta(a, b)))  # 各アームの事後からサンプルし最大を選ぶ
        r = pull(arm, rng)
        a[arm] += r; b[arm] += 1 - r          # ベイズ更新

サンプリングという確率的な選択そのものが、探索と活用を自然に混ぜてくれます。事後が不確実なアームはサンプルが大きく振れて時々選ばれ（探索）、良いと確信したアームは高い値を出して多く選ばれます（活用）。

ベイズA/Bテストとの関係

固定割当A/Bは、一定期間すべてのアームに均等配分してから勝者に切り替える、探索フェーズと活用フェーズの二段構えです。探索の間はどのアームも同じ確率で引くので、悪いアームにも決まった割合のトラフィックが流れ続けます。バンディットは探索と活用を連続的に混ぜることで、この実験中の機会損失を削ります。加えて、事後分布から「AがBに勝つ確率 $P(A>B)$」を直接読める点も、ベイズ的な扱いの実務的な利点です。

シミュレーションで比べる

転換率0.03・0.05・0.08の3アームで、各戦略を3000試行、200シードで平均しました。固定割当A/Bは最初の30%を均等探索に充て、その後は経験的な最良アームに切り替えます。乱数シードは42に固定しました。

累積後悔の推移を見ると、戦略の性格がそのまま曲線に出ます。

最良アームを引けた割合も並べておきます。固定割当A/Bは探索中ずっと33%（均等配分）に張り付き、切り替え時点で跳ね上がります。Thompsonは最も速く最良アームへ集中していきます。

3000試行後の結果は次のとおりです。

戦略	累積後悔	最良アーム選択率
Thompson	17.7	84.1%
固定割当A/B	24.8	78.6%
ε-greedy	30.5	76.5%
UCB1	59.9	49.1%

Thompson Samplingの事後分布を1回分の実行で見ると、最良アーム（真値0.08）に2686回を集中させて分布が鋭く尖り、他の2つは百数十回しか引かず広いまま残っています。無駄な探索に労力を割いていません。

戦略をどう選ぶか

Thompson Samplingは、累積後悔でも最良アーム選択率でも最も良い結果でした。後悔曲線が寝てくる（増え方が緩む）のは、最良アームへ早く集中できている証拠です。固定割当A/Bの曲線には、探索終了時点（試行900）で傾きが折れる明確な折り目が見えます。ここまでは均等探索で後悔を線形に積み、以後は最良に切り替えて増加が止まります。この折り目の面積が、二段構えが払っている探索コストそのものです。

素のUCB1が最も悪かった点は、実務で知っておく価値があります。UCB1の探索ボーナス $\sqrt{2\ln t/n_a}$ は報酬が0から1のスケールを想定して設計されています。ところが今回の転換率は0.03から0.08と極端に小さく、ボーナス項が報酬の信号を完全に覆い隠してしまいます。結果、UCB1はいつまでも全アームをほぼ均等に引き続けます。転換率やクリック率のように報酬が小さい問題では、UCB1の探索定数の調整（あるいはKL-UCBのような報酬スケールに適応する変種）が要ります。既定のまま使うと、A/Bより悪くなりかねません。Thompson Samplingが報酬スケールに自動で適応するのと対照的です。この点は別記事で掘り下げ、探索定数を調整すればUCBがThompsonにほぼ追いつくことを確かめています。

ε-greedyは固定割当A/Bより後悔が大きい結果でした。$\varepsilon=0.1$ を最後まで維持するため、良いアームが分かった後も1割の探索を続けて機会損失を出し続けます。探索率を徐々に下げる工夫（減衰ε）で改善はしますが、いずれにせよ手で調整するパラメータが増えます。

適用範囲には前提があります。ここでの評価は報酬率が時間で変わらない定常環境を前提にしています。実際のWebではトレンドやCTRの変動があり、非定常なら割引やスライディングウィンドウで古い情報を忘れる仕組みがいります。報酬が遅れて届く、バッチで更新する、文脈（ユーザー属性）で最適が変わるといった拡張もそれぞれ別の設計を要します。それでも、まず試すべき既定としてThompson Samplingは、実装の軽さと性能の両面で有力な選択肢になります。

まとめ

オンラインの施策評価は、探索と活用のトレードオフ問題として捉えると見通しがよくなります。今回の3アームでは、Thompson Samplingが累積後悔17.7と固定割当A/Bの24.8を明確に下回り、実装もBeta分布の更新数行で済みました。一方、素のUCB1は報酬スケールが小さい設定で探索過多に陥り、既定値のままでは危ういことも分かりました。手元の施策評価にバンディットを入れるなら、まずThompson Samplingを定常環境で試し、報酬が非定常なら忘却の仕組みを、文脈依存なら文脈付きバンディットを検討する、という順で広げていくとよいでしょう。