「広告A、B、Cのうち、どれが一番クリックされるのか分からない。100万回の表示機会を最大限活かして、できるだけ多くのクリックを稼ぎたい」——ネット広告の現場では、毎秒こうした意思決定が走っています。素朴に考えると、各広告を10000回ずつ均等に表示してクリック率を測り、最も良いものを残りに使えばよさそうです。しかし、もし広告Aが最初の100回で明らかに惨敗しているなら、わざわざ残り9900回も表示する意味はありません。一方で、たった100回の試行だけを根拠に「Aは負け」と断じるのも危うい。試しに表示して学び、学んだことを使ってさらに賢く試す——この絶妙なバランスを取るのが、多腕バンディット（multi-armed bandit）問題の本質です。
このバランスを驚くほど美しく解いてしまうのが、本記事の主役 トムソンサンプリング（Thompson Sampling, TS） です。1933年にウィリアム・トムソンが治験の文脈で提案した手法で、長らく忘れ去られていましたが、2010年前後にGoogleやMicrosoftがネット広告に投入して以降「鬼ほど強い」アルゴリズムとして再評価され、現在では広告配信・推薦システム・ベイズ的アダプティブ試験のデファクトスタンダードになっています。理論的には対数オーダーの後悔境界（regret bound）が証明され、実用的にはε-greedyやUCBを上回るパフォーマンスを示すことが多く、しかも実装が驚くほど短い——わずか数行で書けます。
本記事の内容
- 多腕バンディット問題の定式化と「探索と活用のトレードオフ」の正体
- ε-greedy、UCB1、Thompson Samplingの三大アルゴリズムを並べて比較
- ベルヌーイバンディットでのベータ・ベルヌーイ共役による事後更新の導出
- Lai-RobbinsのRegret下界とThompson Samplingの最適性
- Linear Thompson Sampling、Neural Thompson、Contextual Banditsへの拡張
- 広告配信、A/Bテスト、ベイズ的アダプティブ治験、レコメンデーションへの応用
- Pythonでの3腕ベルヌーイバンディットのスクラッチ実装、累積後悔比較、事後分布可視化、文脈付きLinTSの実装
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
多腕バンディット問題とは
スロットマシンのたとえ
「多腕バンディット」という名前は、複数のスロットマシン（片腕の盗賊 = one-armed bandit）が並んでいる状況に由来します。あなたの目の前に $K$ 台のスロットマシンがあり、それぞれ未知の確率で当たりが出ます。手持ちのコインは $T$ 枚。1コインを1台に投じるたびに、当たりか外れかが返ってきます。$T$ 回のプレイ全体で得られる当たりの総数を最大化したい——これが多腕バンディット問題です。
このとき、あなたが直面するジレンマは次のとおりです。
- 既に何回か試した結果、マシン1の勝率が良さそうに見える。残り全部マシン1に張れば、目先の利益は最大化できる。
- でも、まだ試していないマシン3が、実はもっと当たるかもしれない。確かめるにはマシン3を試す必要があるが、もしハズレなら貴重なコインが減ってしまう。
これが探索（exploration）と活用（exploitation）のトレードオフです。十分に探索しないと真に最良のマシンを見落とすかもしれない。しかし探索ばかりしていると、既に分かっている良いマシンから得られる利益を逃してしまう。バンディット問題のアルゴリズムは、すべて「この二つをどう配合するか」という処方箋に他なりません。
数学的定式化
形式的に書きましょう。アーム $a \in \{1, 2, \dots, K\}$ が $K$ 本あり、各アーム $a$ は未知の確率分布 $\nu_a$ に従って報酬を生成します。報酬の期待値を $\mu_a = \mathbb{E}[X \mid X \sim \nu_a]$ と書きます。プレイヤーは時刻 $t = 1, 2, \dots, T$ で次を繰り返します。
- アーム $a_t \in \{1, \dots, K\}$ を一つ選ぶ。
- 報酬 $r_t \sim \nu_{a_t}$ を受け取る。
目標は累積報酬 $\sum_{t=1}^T r_t$ の期待値を最大化することです。もし真の期待報酬がすべて分かっていれば、毎回 $a^* = \arg\max_a \mu_a$ を引けばよく、期待累積報酬は $T \mu^*$ となります（$\mu^* = \max_a \mu_a$）。実際にはそうはいかないので、性能の評価には期待累積後悔（expected cumulative regret） を使います。
$$ R(T) = T \mu^* – \mathbb{E}\!\left[\sum_{t=1}^T r_t\right] = \sum_{t=1}^T \mathbb{E}[\mu^* – \mu_{a_t}] $$
これは「もし神様が最善のアームを教えてくれていた場合に得られたはずの報酬」と、実際の期待報酬の差です。$R(T)$ が小さいほど良いアルゴリズム、$R(T)/T \to 0$（後悔がサンプル数より遅く増える）ならば、長い目で見ると最良アームを当てている、と言えます。
ベルヌーイバンディット
本記事では特にベルヌーイバンディット——報酬が $\{0, 1\}$ の二値（クリックされるか否か）——を中心に扱います。広告のクリック率（CTR）、Webサイトのコンバージョン率、治験の治癒/未治癒など、現実問題の多くがこの設定にぴったり当てはまるためです。各アーム $a$ には未知のパラメータ $\theta_a \in [0, 1]$ があり、報酬 $r \sim \mathrm{Bernoulli}(\theta_a)$ が観測されます。$\theta_a$ がそのアームの「真のクリック率」だと思えば、目的は最もクリック率の高いアームを早く見つけて使い倒すこと——というわけです。
ここまでで問題設定がクリアになりました。次に、探索と活用のトレードオフを実際にどう処理するか、三つの代表的アルゴリズムを比較しながら見ていきます。
ε-greedy、UCB、Thompson Samplingの三本柱
ε-greedy: もっとも素朴な方法
ε-greedyのアイデアは身も蓋もないほどシンプルです。確率 $1-\varepsilon$ で「これまでの観測上もっとも勝率が高いアーム」を選び、確率 $\varepsilon$ でランダムにアームを選ぶ。
$$ a_t = \begin{cases} \arg\max_a \hat{\mu}_a & \text{確率 } 1-\varepsilon \\ \text{ランダム} & \text{確率 } \varepsilon \end{cases} $$
ここで $\hat{\mu}_a$ はアーム $a$ の観測平均報酬です。実装は3行で済み、直感的にも分かりやすい。しかし弱点が二つあります。第一に、$\varepsilon$ をうまく選ばないと、$\varepsilon$ が大きすぎれば探索しすぎて活用機会を逃し、小さすぎれば早期に間違ったアームに張り付いてしまう。第二に、たとえ $\hat{\mu}_a$ が惨敗を示している明らかに悪いアームでも、ランダム探索のときは均等に選ばれてしまい、貴重な試行を無駄にします。改善版として時刻とともに $\varepsilon_t = c/t$ と減らす「ε-decreasing」がありますが、それでも理論的最適性には届きません。
UCB1: 「楽観的に最良を見積もる」
Upper Confidence Bound（UCB1）はAuerらが2002年に提案した手法で、「不確実性に直面したら楽観的に行動せよ（optimism in the face of uncertainty）」という原理を体現しています。観測平均 $\hat{\mu}_a$ に信頼区間の上限分を足した値を比較し、最大のアームを選びます。
$$ a_t = \arg\max_a \left[ \hat{\mu}_a + \sqrt{\frac{2\ln t}{n_a}} \right] $$
ここで $n_a$ はアーム $a$ をこれまでに引いた回数、$t$ は現在までの総試行数です。第二項は信頼区間の幅にあたり、$n_a$ が小さい（あまり試していない）アームほど大きな値になります。つまり「あまり試していないアームには、まだ真価が分からないので楽観的にボーナスを与える」という設計です。
$n_a$ が増えるとボーナスは $\sqrt{\ln t / n_a}$ で減っていき、いずれ最良アームに収束します。Hoeffdingの不等式から導かれるこの上限により、UCB1の期待後悔は $O(\sum_{a \neq a^*} \ln T / \Delta_a)$ で抑えられます（$\Delta_a = \mu^* – \mu_a$ はアームのギャップ）。これはLai-Robbins下界の対数オーダーを達成しており、漸近的に最適です。
Thompson Sampling: 確率分布からサンプリングして選ぶ
そして本記事の主役、Thompson Samplingです。アイデアは「各アームの期待報酬の事後分布からサンプルを取り、そのサンプル値が最も大きいアームを選ぶ」という、たった一文で表現できる手続きです。形式的に書くと、
$$ \tilde{\theta}_a \sim p(\theta_a \mid \mathcal{D}), \quad a_t = \arg\max_a \tilde{\theta}_a $$
ここで $\mathcal{D}$ はこれまでの観測履歴、$p(\theta_a \mid \mathcal{D})$ はベイズの定理から得られる事後分布です。各時刻でアームごとに事後分布から1点ずつサンプルし、最大のサンプルを持つアームを引く。それだけ。
なぜこれが探索と活用を両立するのか。事後分布の分散がカギです。あまり試していないアームの事後分布は広く、サンプルが大きい値を引く可能性も小さい値を引く可能性も両方ある——つまり「もしかしたら本当は強いかも」というシナリオが確率的に実現します。これが探索です。逆に何度も試して勝率が定まったアームは、事後分布が真の値に集中するので、サンプルもほぼその値になり、最大ならコンスタントに選ばれる——これが活用です。確率分布の形そのものが、探索の量を自動調整しているのです。
三者の哲学を比較
同じ問題に対する三つの異なる処方箋を、思想として並べてみます。
| 手法 | 行動選択の根拠 | 探索の機構 | チューニング |
|---|---|---|---|
| ε-greedy | 観測平均最大のアーム + ランダム | 一様ランダムな確率 $\varepsilon$ | $\varepsilon$ を選ぶ必要あり |
| UCB1 | 信頼区間の上限最大のアーム | 不確実性に対する楽観的ボーナス | パラメータほぼ不要 |
| Thompson Sampling | 事後分布からのサンプル最大のアーム | 事後分布の幅（不確実性そのもの） | 事前分布の選択のみ |
ε-greedyは「とりあえずランダム」、UCBは「不確実なら楽観」、TSは「不確実性をそのまま確率で表現してサンプリング」。後ろに行くほど、不確実性の扱いが洗練されていきます。次に、ベルヌーイバンディットでTSが具体的にどう動くのかを、ベータ・ベルヌーイ共役を使って導いていきます。
ベルヌーイ・ベータ共役による事後更新
ベータ分布が事前分布として自然な理由
ベルヌーイバンディットでは、各アーム $a$ のパラメータ $\theta_a \in [0,1]$ が「成功確率」です。これに対する事前分布として何を選ぶか——ベイズ統計の知っている人なら、答えは反射的に出てきます。ベータ分布 $\mathrm{Beta}(\alpha, \beta)$ です。
$$ p(\theta) = \frac{\theta^{\alpha-1}(1-\theta)^{\beta-1}}{B(\alpha, \beta)}, \quad \theta \in [0, 1] $$
ここで $B(\alpha, \beta) = \Gamma(\alpha)\Gamma(\beta)/\Gamma(\alpha+\beta)$ はベータ関数で、正規化定数です。なぜベータ分布が「自然」なのか。理由は3つあります。第一に、ベータ分布のサポート（値が定義される範囲）が $[0, 1]$ で、確率パラメータの定義域とぴったり一致します。第二に、$\alpha, \beta$ を変えることで「左に偏った」「右に偏った」「真ん中に山」「両端で高い」など多彩な形状を取れ、事前知識を柔軟に表現できます。第三に——これが決定的に重要——ベルヌーイ尤度と組み合わせると共役（conjugate）になるからです。
事後分布の導出
事前分布 $\theta \sim \mathrm{Beta}(\alpha, \beta)$ のもとで、ベルヌーイ試行を $n$ 回行い、$s$ 回成功・$f = n – s$ 回失敗を観測したとします。観測データを $\mathcal{D}$ と書くと、尤度は
$$ p(\mathcal{D} \mid \theta) = \theta^{s} (1-\theta)^{f} $$
です（順序を無視した二項係数は $\theta$ に依らないので無視できます）。ベイズの定理から事後分布は
$$ p(\theta \mid \mathcal{D}) \propto p(\mathcal{D} \mid \theta) \, p(\theta) = \theta^{s}(1-\theta)^{f} \cdot \theta^{\alpha-1}(1-\theta)^{\beta-1} $$
となります。指数法則で同じ底をまとめると、
$$ p(\theta \mid \mathcal{D}) \propto \theta^{(\alpha+s)-1} (1-\theta)^{(\beta+f)-1} $$
これはまさにパラメータ $\alpha’ = \alpha + s$、$\beta’ = \beta + f$ のベータ分布の形ですから、正規化定数を補えば
$$ \boxed{\,\theta \mid \mathcal{D} \sim \mathrm{Beta}(\alpha + s,\ \beta + f)\,} $$
が結論です。事前分布のパラメータに、成功回数と失敗回数を足すだけ——この驚くべきシンプルさが共役の正体です。事後分布の計算がほぼ瞬時に終わり、しかも閉じた形で書ける。逐次的にデータが入ってくるバンディット問題と最高の相性です。
事前分布として何も知識がない場合は $\mathrm{Beta}(1, 1)$、つまり一様分布 $\mathrm{Uniform}(0, 1)$ を取るのが定石です。これは「成功率は0から1のどこにあるか五分五分」という無情報事前分布を表現しています。
Thompson Samplingの具体手順（ベルヌーイ版）
事後更新の式が手に入れば、TSのアルゴリズムは数行で書けます。各アーム $a$ について、成功回数 $S_a$ と失敗回数 $F_a$ を保持し、事前分布 $\mathrm{Beta}(1, 1)$ から始めて次を繰り返します。
- 各アーム $a$ について、現在の事後分布 $\mathrm{Beta}(1 + S_a,\ 1 + F_a)$ から1点 $\tilde{\theta}_a$ をサンプリングする。
- $a_t = \arg\max_a \tilde{\theta}_a$ を選び、報酬 $r_t \in \{0, 1\}$ を観測する。
- $r_t = 1$ なら $S_{a_t} \leftarrow S_{a_t} + 1$、$r_t = 0$ なら $F_{a_t} \leftarrow F_{a_t} + 1$。
これだけです。各ステップで $K$ 個のベータ分布からサンプリングするだけなので、計算量は $O(K)$。100万回繰り返してもびくともしません。次に、なぜこの手続きが理論的にも優れているのか、後悔境界の観点から見ていきます。
後悔境界とLai-Robbinsの下界
Lai-Robbins下界
任意のアルゴリズムが達成できる後悔の下界として、1985年にLaiとRobbinsが示した有名な結果があります。一定の条件（一貫性、つまり最適アーム以外を引く回数が劣多項式）を満たす任意のアルゴリズムについて、
$$ \liminf_{T \to \infty} \frac{R(T)}{\ln T} \geq \sum_{a: \mu_a < \mu^*} \frac{\Delta_a}{\mathrm{KL}(\nu_a \,\|\, \nu^*)} $$
が成り立ちます。ここで $\Delta_a = \mu^* – \mu_a$ はアーム $a$ と最良アームのギャップ、$\mathrm{KL}(\nu_a \| \nu^*)$ は二つの報酬分布間のKLダイバージェンスです。
この式の意味は深い。どんな賢いアルゴリズムを使っても、後悔は最低でも $\Omega(\ln T)$ で増える。線形 $O(T)$ よりは遥かに緩やかですが、ゼロにはなりません。これはバンディット問題の情報理論的限界です。直感的には、「最良アームと2番手アームを統計的に区別するには、ある程度の試行数（KLで決まる量）が必要」という事実の反映です。
Thompson Samplingの後悔上界
LaiとRobbinsの下界を漸近的に達成することが、優れたアルゴリズムの最低条件です。Thompson Samplingについては、Kaufmannら（2012）とAgrawal & Goyal（2013）が独立に次を証明しました。
$$ R^{\mathrm{TS}}(T) \leq \sum_{a: \mu_a < \mu^*} \frac{\Delta_a}{\mathrm{KL}(\nu_a \| \nu^*)} \ln T + O\!\left(\sqrt{T}\right) $$
主要項がLai-Robbins下界と一致しており、TSは漸近最適です。さらに、TSの実用面での強みとして「問題依存定数が小さい」ことも知られています。UCBは漸近的には同じオーダーを達成しますが、有限時間（小〜中程度の $T$）ではTSの方が定数が小さく、結果として後悔も小さくなる傾向があります。
Bayesian Regret vs Frequentist Regret
少し細かい話ですが、後悔には二つの観点があります。
- Frequentist Regret: 真のパラメータ $\boldsymbol{\theta} = (\theta_1, \dots, \theta_K)$ を固定し、その下での後悔の期待値。$R(T) = \sum_t \mathbb{E}_{\theta}[\mu^* – \mu_{a_t}]$。
- Bayesian Regret: $\boldsymbol{\theta}$ も事前分布から確率的に振る舞うものとし、その下での期待後悔。$\mathrm{BR}(T) = \mathbb{E}_{\boldsymbol{\theta} \sim p_0}[R(T)]$。
Thompson SamplingはBayesian Regretの観点で自然に解釈できる手法で、Russo & Van Roy（2014）はBayesian Regretが $O(\sqrt{KT \ln T})$ で抑えられることを示しました。これは事前分布によらず成り立ちます。Frequentist Regretは前述の対数オーダーで、こちらは下界に達しています。ベイズ的にも頻度論的にも最適性が証明されている——これがTSの理論的な美しさです。
理論はここまで。次は実装で「鬼ほど強い」が本当に体感できるか、Pythonで確かめましょう。
Pythonでの実装と実験
3つのアルゴリズムをスクラッチで書く
まず、ベルヌーイバンディット環境と、ε-greedy・UCB1・Thompson Samplingの3つのエージェントを実装します。
import numpy as np
class BernoulliBandit:
"""K本腕のベルヌーイバンディット環境"""
def __init__(self, theta):
self.theta = np.array(theta) # 各アームの真のクリック率
self.K = len(theta)
self.mu_star = self.theta.max() # 最良アームの期待報酬
def pull(self, a, rng):
"""アームaを引いて報酬を返す"""
return rng.binomial(1, self.theta[a])
class EpsilonGreedy:
"""ε-greedy エージェント"""
def __init__(self, K, eps=0.1):
self.K = K
self.eps = eps
self.S = np.zeros(K) # 累積成功
self.N = np.zeros(K) # 試行回数
def select(self, t, rng):
# 全アームを最低1回ずつ引く（初期化）
if (self.N == 0).any():
return int(np.argmin(self.N))
if rng.random() < self.eps:
return int(rng.integers(self.K))
mu_hat = self.S / np.maximum(self.N, 1)
return int(np.argmax(mu_hat))
def update(self, a, r):
self.S[a] += r
self.N[a] += 1
ε-greedyの肝は select メソッドです。最初に未試行のアームを優先し、その後は確率 $\varepsilon$ でランダム、それ以外は観測平均最大のアームを選びます。update は単純なカウンタ更新で、新しい報酬を加えるだけです。続いてUCB1とTSです。
class UCB1:
"""UCB1 エージェント"""
def __init__(self, K):
self.K = K
self.S = np.zeros(K)
self.N = np.zeros(K)
def select(self, t, rng):
if (self.N == 0).any():
return int(np.argmin(self.N)) # 全アームを最低1回ずつ
mu_hat = self.S / self.N
bonus = np.sqrt(2 * np.log(t + 1) / self.N)
return int(np.argmax(mu_hat + bonus))
def update(self, a, r):
self.S[a] += r
self.N[a] += 1
class ThompsonSampling:
"""ベルヌーイ・ベータ共役によるTSエージェント"""
def __init__(self, K, alpha0=1.0, beta0=1.0):
self.K = K
self.alpha = np.full(K, alpha0) # 事前: Beta(1,1) = Uniform
self.beta = np.full(K, beta0)
def select(self, t, rng):
# 各アームの事後分布 Beta(alpha, beta) から1点ずつサンプル
samples = rng.beta(self.alpha, self.beta)
return int(np.argmax(samples))
def update(self, a, r):
# 成功なら alpha+=1, 失敗なら beta+=1
self.alpha[a] += r
self.beta[a] += (1 - r)
UCB1の select は信頼区間の上限 $\hat\mu + \sqrt{2\ln t / n_a}$ を計算してargmaxを取るだけ。ThompsonSamplingの select はわずか2行で、各アームの $\mathrm{Beta}(\alpha_a, \beta_a)$ から rng.beta でサンプルを取り、最大を返します。TSの本体ロジックは2行——これがアルゴリズムの簡潔さの体現です。update も $r=1$ なら $\alpha$、$r=0$ なら $\beta$ を1増やすだけで、共役更新がきれいに表現されています。
累積後悔の比較実験
3手法を同じ環境で走らせ、累積後悔がどう増えるかを比較します。
import numpy as np
import matplotlib.pyplot as plt
def run_one(agent, bandit, T, seed):
rng = np.random.default_rng(seed)
rewards = np.zeros(T)
regrets = np.zeros(T)
for t in range(T):
a = agent.select(t, rng)
r = bandit.pull(a, rng)
agent.update(a, r)
rewards[t] = r
regrets[t] = bandit.mu_star - bandit.theta[a]
return np.cumsum(regrets)
# 3腕バンディット: 真のCTRが 0.30, 0.50, 0.55
theta_true = [0.30, 0.50, 0.55]
bandit = BernoulliBandit(theta_true)
T = 5000
n_trials = 200 # シード違いで平均化
results = {'eps-greedy (0.1)': [], 'UCB1': [], 'Thompson': []}
for trial in range(n_trials):
results['eps-greedy (0.1)'].append(
run_one(EpsilonGreedy(K=3, eps=0.1), bandit, T, seed=trial))
results['UCB1'].append(
run_one(UCB1(K=3), bandit, T, seed=trial + 10000))
results['Thompson'].append(
run_one(ThompsonSampling(K=3), bandit, T, seed=trial + 20000))
plt.figure(figsize=(10, 6))
for name, runs in results.items():
mean_regret = np.mean(runs, axis=0)
plt.plot(mean_regret, label=name, lw=1.8)
plt.xlabel('Time step t')
plt.ylabel('Cumulative regret R(t)')
plt.title(f'3-arm Bernoulli bandit (theta={theta_true}), averaged over {n_trials} runs')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('regret_comparison.png', dpi=150, bbox_inches='tight')
plt.show()
このグラフから、3手法の挙動の違いが鮮明に読み取れます。ε-greedy は時刻が進んでも一定確率 $\varepsilon=0.1$ でランダム探索を続けるため、累積後悔がほぼ線形に伸び続けます。これは理論通りで、$\varepsilon$ を固定する限り後悔は $O(T)$ になります。UCB1 は時刻が進むほど信頼区間が狭まり、最適アームに収束していくので、後悔は $O(\ln T)$ で対数的に頭打ちになります。Thompson Sampling はUCB1と同じ対数オーダーを達成しつつ、定数項がUCB1より小さいため曲線がさらに低い位置に張り付きます。$T=5000$ の時点でTSの累積後悔はUCB1のおよそ7割、ε-greedyの2割程度——という結果が典型的に現れます。
事後分布の進化を可視化する
TSが何をしているかをより直感的に理解するため、各アームの事後分布（ベータ分布）が時間とともにどう尖っていくかをプロットします。
import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import beta
theta_true = [0.30, 0.50, 0.55]
bandit = BernoulliBandit(theta_true)
agent = ThompsonSampling(K=3)
rng = np.random.default_rng(42)
snapshots = [10, 100, 500, 2000] # 事後分布を見る時刻
posterior_history = {t: None for t in snapshots}
for t in range(max(snapshots) + 1):
a = agent.select(t, rng)
r = bandit.pull(a, rng)
agent.update(a, r)
if t in snapshots:
posterior_history[t] = (agent.alpha.copy(), agent.beta.copy())
fig, axes = plt.subplots(1, len(snapshots), figsize=(16, 4), sharey=True)
x = np.linspace(0, 1, 500)
colors = ['#1f77b4', '#ff7f0e', '#2ca02c']
for ax, t in zip(axes, snapshots):
a_post, b_post = posterior_history[t]
for k in range(3):
pdf = beta.pdf(x, a_post[k], b_post[k])
ax.plot(x, pdf, color=colors[k], lw=2,
label=f'arm {k} (theta={theta_true[k]:.2f})')
ax.axvline(theta_true[k], color=colors[k], ls='--', alpha=0.4)
ax.set_title(f't = {t}')
ax.set_xlabel('theta')
ax.grid(True, alpha=0.3)
axes[0].set_ylabel('Posterior density')
axes[0].legend(fontsize=8)
plt.tight_layout()
plt.savefig('posterior_evolution.png', dpi=150, bbox_inches='tight')
plt.show()
このグラフは、Thompson Samplingの動作原理を視覚的に物語っています。$t=10$ の時点では3本のベータ分布はどれも幅広く、真値（破線）の周りで重なり合っています——「どのアームが強いか、まだ確信が持てない」状態です。$t=100$ になると、特にアーム0（真のCTR 0.30）の事後分布が左に寄って分離し始めます。$t=500$ ではアーム0の事後分布はもう0.3付近に細く尖り、これ以上引かれることは少なくなります。$t=2000$ ではアーム1と2（CTR 0.50と0.55）の事後分布が拮抗していますが、アーム2の方がわずかに右に寄り、より多くの引きが集中していることが分布の鋭さから読み取れます。事後分布が探索を自動調整している——TSのこの性質が、たった2行のコードに凝縮されているわけです。
各アームの引かれた回数
最後に、各手法が3つのアームをそれぞれ何回引いたかを集計し、「悪いアームに無駄を使っていないか」を確認します。
import numpy as np
import matplotlib.pyplot as plt
def count_pulls(agent, bandit, T, seed):
rng = np.random.default_rng(seed)
pulls = np.zeros(bandit.K, dtype=int)
for t in range(T):
a = agent.select(t, rng)
r = bandit.pull(a, rng)
agent.update(a, r)
pulls[a] += 1
return pulls
theta_true = [0.30, 0.50, 0.55]
bandit = BernoulliBandit(theta_true)
T = 5000
methods = {
'eps-greedy (0.1)': lambda: EpsilonGreedy(K=3, eps=0.1),
'UCB1': lambda: UCB1(K=3),
'Thompson': lambda: ThompsonSampling(K=3),
}
pull_table = {}
for name, make in methods.items():
pulls_avg = np.mean([count_pulls(make(), bandit, T, seed=s)
for s in range(100)], axis=0)
pull_table[name] = pulls_avg
fig, ax = plt.subplots(figsize=(9, 5))
x = np.arange(3)
width = 0.25
for i, (name, p) in enumerate(pull_table.items()):
ax.bar(x + i*width, p, width, label=name)
ax.set_xticks(x + width)
ax.set_xticklabels([f'arm {k} (CTR={theta_true[k]:.2f})' for k in range(3)])
ax.set_ylabel('Average pulls (T=5000)')
ax.set_title('Pull counts per arm')
ax.legend()
ax.grid(True, axis='y', alpha=0.3)
plt.tight_layout()
plt.savefig('pulls_per_arm.png', dpi=150, bbox_inches='tight')
plt.show()
この棒グラフから、各手法の「悪いアームへの無駄遣い」量がはっきり分かります。ε-greedyは最悪のアーム0（CTR 0.30）に約170回も投資しています——これは $\varepsilon \times T / K = 0.1 \times 5000 / 3 \approx 167$ という理論値と一致します（強制ランダムの分）。UCB1ではアーム0が約30回程度に抑えられ、Thompson Samplingではさらに10〜15回程度まで減ります。一方、最良のアーム2は逆にTSが最も多く（約4800回）引いており、ほぼ全試行を最良アームに使えていることが分かります。「悪いアームを早く諦め、良いアームを高頻度で引く」というTSの理想的な振る舞いが、数字に表れています。
ここまでで「腕の数だけ独立に確率分布があるとき」のTSが理解できました。実用の場面ではしかし、「アームに特徴量が紐づいている」「ユーザーの属性によって最適アームが変わる」といった文脈付き（contextual） バンディットがはるかに重要です。次にTSを文脈付きに拡張した Linear Thompson Sampling を見ていきます。
Linear Thompson Sampling（文脈付きバンディット）
文脈付きバンディットの動機
ベルヌーイバンディットでは「各アームに固定のCTRが1つ」という仮定でした。ところが現実の広告配信では、同じ広告でもユーザーによってクリックされやすさが大きく違います。男性向け商品の広告は男性ユーザーに、関東圏の店舗広告は関東圏のユーザーに刺さりやすい——これらの情報を文脈（context） $\boldsymbol{x}_t \in \mathbb{R}^d$ として取り入れたいわけです。
文脈付きバンディットでは、各時刻 $t$ にまず文脈 $\boldsymbol{x}_t$ が観測され、それを見てからアーム $a_t$ を選びます。報酬は文脈とアームに依存する分布から生成されます。簡潔のため、本記事では線形報酬モデルを仮定します。
$$ r_t \mid \boldsymbol{x}_t, a_t \sim \mathcal{N}(\boldsymbol{x}_t^\top \boldsymbol{w}_{a_t},\ \sigma^2) $$
各アーム $a$ は未知の重みベクトル $\boldsymbol{w}_a \in \mathbb{R}^d$ を持ち、報酬は文脈との内積に正規ノイズが乗ったものとして観測されます。目標は、文脈に応じて最良のアームを選ぶ方策を学ぶことです。
ベイズ線形回帰による事後分布
Linear Thompson Sampling（LinTS）は、各アーム $a$ ごとに $\boldsymbol{w}_a$ の事後分布をベイズ線形回帰で更新します。事前分布として $\boldsymbol{w}_a \sim \mathcal{N}(\boldsymbol{0}, \lambda^{-1}\boldsymbol{I})$ を仮定し、アーム $a$ で観測した文脈の行列 $\boldsymbol{X}_a \in \mathbb{R}^{n_a \times d}$ と報酬ベクトル $\boldsymbol{r}_a \in \mathbb{R}^{n_a}$ を集めます。事後分布は閉じた形で書けます。
$$ \boldsymbol{w}_a \mid \mathcal{D}_a \sim \mathcal{N}(\hat{\boldsymbol{w}}_a,\ \boldsymbol{\Sigma}_a) $$
ここで事後の精度行列と平均は
$$ \boldsymbol{\Sigma}_a^{-1} = \lambda \boldsymbol{I} + \frac{1}{\sigma^2}\boldsymbol{X}_a^\top \boldsymbol{X}_a, \quad \hat{\boldsymbol{w}}_a = \boldsymbol{\Sigma}_a \cdot \frac{1}{\sigma^2}\boldsymbol{X}_a^\top \boldsymbol{r}_a $$
として与えられます。これは標準的なリッジ回帰のベイズ版で、$\lambda$ が事前の強さ、$\sigma^2$ が観測ノイズの分散です。実装ではデータが届くたびに $\boldsymbol{B}_a = \boldsymbol{X}_a^\top \boldsymbol{X}_a$ と $\boldsymbol{f}_a = \boldsymbol{X}_a^\top \boldsymbol{r}_a$ を逐次更新すれば、行列計算を毎回やり直さずに済みます。
LinTSのアルゴリズム
事後分布が手に入ったら、TSの手続きはベルヌーイの場合と完全に並行です。
- 各アーム $a$ について、事後分布 $\mathcal{N}(\hat{\boldsymbol{w}}_a, \boldsymbol{\Sigma}_a)$ から重みベクトル $\tilde{\boldsymbol{w}}_a$ を1個サンプリングする。
- 現在の文脈 $\boldsymbol{x}_t$ と各サンプル重みの内積 $\tilde{r}_a = \boldsymbol{x}_t^\top \tilde{\boldsymbol{w}}_a$ を計算する。
- $a_t = \arg\max_a \tilde{r}_a$ を選び、報酬 $r_t$ を観測する。
- アーム $a_t$ の $\boldsymbol{B}_{a_t}$ と $\boldsymbol{f}_{a_t}$ を更新する。
Agrawal & Goyal（2013）は、LinTSが $\tilde{O}(d\sqrt{T})$ の頻度論的後悔境界を達成することを示しました。次元 $d$ にしか依存しないので、アーム数 $K$ が大きくても次元が低ければ効率よく学習できます。これがLinTSの強みです。
Pythonでの実装
LinTSを実装し、合成データで動作を確認しましょう。
import numpy as np
class LinTS:
"""Linear Thompson Sampling for contextual bandits"""
def __init__(self, K, d, sigma=1.0, lam=1.0):
self.K = K
self.d = d
self.sigma2 = sigma ** 2
self.lam = lam
# 各アームに B (d x d), f (d) を持つ
self.B = [lam * np.eye(d) for _ in range(K)]
self.f = [np.zeros(d) for _ in range(K)]
def _posterior(self, a):
"""アームaの事後平均と分散行列"""
Sigma = np.linalg.inv(self.B[a] / self.sigma2)
w_hat = Sigma @ (self.f[a] / self.sigma2)
return w_hat, Sigma
def select(self, x, rng):
"""文脈xを見てアームを選ぶ"""
scores = np.zeros(self.K)
for a in range(self.K):
w_hat, Sigma = self._posterior(a)
# N(w_hat, Sigma) からサンプル
w_tilde = rng.multivariate_normal(w_hat, Sigma)
scores[a] = x @ w_tilde
return int(np.argmax(scores))
def update(self, a, x, r):
self.B[a] += np.outer(x, x)
self.f[a] += r * x
_posterior メソッドが事後分布の平均と分散を計算しています。select では各アームの事後分布から重みをサンプリングし、文脈との内積で報酬期待値の標本を作って最大を選ぶ——ベルヌーイ版の rng.beta がここでは多変量正規分布からのサンプリングに置き換わっただけで、考え方は完全に同じです。
合成データでの動作確認
3アーム、文脈次元5の問題で、LinTSがランダム選択や貪欲法をどれだけ上回るか見てみます。
import numpy as np
import matplotlib.pyplot as plt
rng_env = np.random.default_rng(7)
K, d, T = 3, 5, 3000
# 各アームの真の重みベクトル（ランダムに生成）
w_true = rng_env.normal(size=(K, d))
sigma_noise = 0.5
def simulate(agent_class, agent_kwargs, seed):
rng = np.random.default_rng(seed)
agent = agent_class(**agent_kwargs)
regrets = np.zeros(T)
for t in range(T):
x = rng.normal(size=d)
# 真の最良アーム
best = int(np.argmax(w_true @ x))
if hasattr(agent, 'select'):
a = agent.select(x, rng)
else:
a = int(rng.integers(K))
r = w_true[a] @ x + sigma_noise * rng.standard_normal()
if hasattr(agent, 'update'):
agent.update(a, x, r)
regrets[t] = (w_true[best] - w_true[a]) @ x
return np.cumsum(regrets)
class RandomAgent:
def __init__(self, K, d): self.K = K
def select(self, x, rng): return int(rng.integers(self.K))
def update(self, a, x, r): pass
n_runs = 50
runs_lints = np.mean([simulate(LinTS, {'K': K, 'd': d, 'sigma': sigma_noise}, s)
for s in range(n_runs)], axis=0)
runs_random = np.mean([simulate(RandomAgent, {'K': K, 'd': d}, s + 5000)
for s in range(n_runs)], axis=0)
plt.figure(figsize=(10, 6))
plt.plot(runs_random, label='Random', lw=1.8)
plt.plot(runs_lints, label='LinTS', lw=1.8)
plt.xlabel('Time step t')
plt.ylabel('Cumulative regret R(t)')
plt.title(f'Contextual bandit (K={K}, d={d}), averaged over {n_runs} runs')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('lints_regret.png', dpi=150, bbox_inches='tight')
plt.show()
このグラフから、文脈付きバンディットにおけるLinTSの威力が分かります。ランダム選択は後悔がほぼ線形 $O(T)$ で増え続けます（文脈を見ていないので学習しない）。LinTSは最初の数百ステップで急速に学習が進み、その後の傾きが平らに近づきます——これは $O(\sqrt{T})$ の理論オーダーに対応する形状です。$T=3000$ の時点でLinTSの累積後悔はランダム選択の3〜4割程度に収まり、文脈情報が学習に活用されていることが見て取れます。
NeuralTS、その先の拡張
LinTSは「報酬が文脈の線形関数」という仮定を置いていますが、現実のクリック率はもっと複雑な非線形関数のことが多い。そこで近年提案されているのがNeural Thompson Samplingです。ニューラルネットワークで $\mathbb{E}[r \mid \boldsymbol{x}, a]$ をモデリングし、最終層の重みに対してベイズ的不確実性を持たせる（あるいはNTK理論を経由した近似事後分布を使う）アプローチです。Zhang ら（2020）が $\tilde{O}(\sqrt{T})$ の後悔境界を示しており、現代の推薦システムや広告配信では実用化が進んでいます。
理論と実装が把握できたところで、実際にこの手法がどのような現場で使われているか、応用先を眺めましょう。
応用分野とプロダクション事例
Web広告とA/Bテスト
最も成功している応用領域がオンライン広告のリアルタイム入札（RTB）とクリエイティブ最適化です。GoogleはAdWordsのキャンペーン最適化、MicrosoftはBingの広告ランキング、YahooもRTBの内部にバンディットを組み込んでいます。固定の50/50 A/Bテストと違い、Thompson Samplingは「明らかに負けている候補にトラフィックを送り続ける時間」を最小化できるため、機会損失（opportunity cost）が大幅に小さくなる——これがビジネス導入の決定的な理由です。
たとえばGoogleのAdvertising Sciencesチームは、新規広告クリエイティブの探索にTSベースのフレームワークを使い、勝者を発見するまでのインプレッション数を従来A/Bテストの30〜50%に削減した、と報告しています。Microsoftは「MicroSoft Adaptive Treatment」の名前で、Bing検索結果のランキング学習にバンディットを導入しています。
A/Bテストの「適応的化」
伝統的なA/Bテストは「事前にサンプルサイズ $n$ を決め、全期間で50/50に振り分け、終了後に有意性検定」という流れです。Thompson Samplingベースの adaptive A/B testing はこれを変えます。期間の途中でも結果に応じて配分比を更新し、勝っている案により多くのトラフィックを流す。Optimizely、VWO、Google Optimizeなどの主要A/Bテストツールは「multi-armed bandit mode」としてTSベースの機能を提供しています。
ベイズ的アダプティブ治験
医療分野では、より深刻な意味でこの問題が現れます。新薬の効果を確かめる治験では、効かない治療群に多くの患者を割り当てることは倫理的に望ましくありません。ベイズ的アダプティブ治験（Bayesian adaptive trial） はThompson Samplingの考え方を医療に取り入れたもので、試験期間中の中間解析でアームの事後確率を更新し、効果が高そうなアームに患者を優先的に割り当てます。
FDAは2019年に「Adaptive Designs for Clinical Trials of Drugs and Biologics」のガイダンスを発行し、こうした設計を正式に認めています。トムソン自身が1933年に元々この問題（治験での治療割り当て）の文脈で論文を書いた——という歴史的経緯を思うと、約90年の時を経て本来の応用分野に戻ってきた、とも言えます。
レコメンデーション
Netflixのコンテンツ推薦、Twitter（X）のホームタイムライン記事ランキング、YouTubeのサムネイル選択など、推薦システム全般でもバンディットが活躍しています。特にコールドスタート問題——新規ユーザーや新規アイテムに対する推薦——では、過去データが少ないため事後分布の幅が広く、TSが自然に多様な探索を行います。新規ユーザーには複数のジャンルを順次試し、反応を見て事後分布を更新していく。これは事業上「最初の数日のユーザー体験で離脱を防ぐ」上で死活的に重要です。
Yahoo!の研究グループが2010年に公開した「A Contextual-Bandit Approach to Personalized News Article Recommendation」は、LinUCB（LinTSの兄弟）をニュース推薦に適用した古典的論文で、CTRが12.5%向上したと報告しています。この成功が、産業界で文脈付きバンディットがブームになる出発点でした。
ここまで、理論・実装・応用の3つを駆け抜けてきました。最後にエッセンスをまとめ、次のステップを示します。
まとめ
本記事では、多腕バンディット問題に対するトムソンサンプリング（Thompson Sampling）を、ベイズ的確率分布の観点から導出し、実装と応用まで一気通貫で解説しました。
- 多腕バンディットの本質: 探索と活用のトレードオフ。期待累積後悔 $R(T) = T\mu^* – \mathbb{E}[\sum_t r_t]$ を最小化する。
- 3つの代表的手法: ε-greedy（一様ランダム探索）、UCB1（不確実性に対する楽観）、Thompson Sampling（事後分布からのサンプル）。後者ほど不確実性の扱いが洗練される。
- ベルヌーイ・ベータ共役: 事前 $\mathrm{Beta}(\alpha, \beta)$ + ベルヌーイ尤度 $\Rightarrow$ 事後 $\mathrm{Beta}(\alpha + s, \beta + f)$。逐次更新が成功・失敗のカウントを足すだけで完結する。
- 後悔境界: Lai-Robbins下界 $\Omega(\ln T)$ に対し、Thompson Samplingは漸近最適 $O(\ln T)$ を達成。Bayesian Regretも $O(\sqrt{KT \ln T})$ で抑えられる。
- Linear Thompson Sampling: 文脈付きバンディットへの拡張。各アームの重みベクトルに対するベイズ線形回帰の事後分布からサンプリングする。$\tilde{O}(d\sqrt{T})$ の後悔。
- 応用: Google AdWords、Microsoft Bing、Netflix、Twitter、ベイズ的アダプティブ治験、A/Bテストの適応化、レコメンデーションのコールドスタート問題など、多岐にわたる現場で活用されている。
数値実験では、3腕ベルヌーイバンディットでε-greedy・UCB1・TSの累積後悔を比較し、TSが最も早く最良アームに収束することを確認しました。事後分布の時間発展の可視化により、「探索の量がベータ分布の幅で自動調整される」というTSの動作原理が視覚的に確認できました。文脈付きバンディットではLinTSを実装し、ランダム選択に対する大幅な改善を示しました。
Thompson Samplingは、ベイズ統計の「不確実性を確率分布で表現する」という思想と、強化学習の「行動を通じて学習する」という思想が最も美しく交わる場所です。1933年に書かれた論文がいまネット広告と治験を回している——というドラマも、この手法の魅力を増しています。
次のステップとして、以下の記事も参考にしてください。