多腕バンディットとオンライン最適化｜マーケティングサイエンス

🎓 レベル：標準　|　重要度：A（必須）

📎 関連：第8章レコメンデーション目次　|　前提：A/Bテストの設計と分析

要点（BLUF）

多腕バンディットは、どの施策（広告クリエイティブ・推薦・価格）が良いか分からないまま、毎回1つ選んで報酬を観測し、累積報酬を最大化する逐次決定問題です。鍵は探索（explore：不確実な腕を試す）と活用（exploit：良いと分かった腕に寄せる）のトレードオフ。A/Bテストの設計と分析の A/B が固定割付（テスト中ずっと半々で、負け腕にもトラフィックを流し続ける）なのに対し、バンディットは良さそうな腕に配分を寄せながら学ぶ——だから学習中の機会損失（リグレット）を抑えられます。
損は累積リグレット $\text{Regret}(T)=T\mu^*-\sum_t\mu_{a_t}=\sum_k\Delta_k\,\mathbb{E}[n_k(T)]$ で測ります（ $\Delta_k$ ＝最良腕とのギャップ、 $n_k$ ＝腕 $k$ を引いた回数）。3戦略を実装します——ε-greedy（確率 $\varepsilon$ で無作為探索・ $1-\varepsilon$ で最良活用）、UCB1（ $\bar\mu_k+\sqrt{2\ln t/n_k}$ の上側信頼界で楽観的に選ぶ）、Thompson Sampling（各腕の Beta 事後から1標本引き最大の腕を選ぶ＝ベイズA/Bテストの事後を逐次に使う）。活用だけだと初期の誤評価で誤った腕に固定化し、探索だけ（＝A/B）だと損が線形に伸びます。
4本腕ベルヌーイ $\mu=[.10,.13,.16,.20]$ （最良＝腕3）・ $T=2000$ ・共通乱数で比べると、Thompson が最小リグレット $19.2$ ・最良腕 $80.5\%$ 、ε-greedy(0.1) も $26.2$ ・ $81.8\%$ と健闘、無作為は $102.0$ ・ $27.4\%$ で最悪。UCB1 は $71.0$ ・ $39.5\%$ で無作為には勝つものの、腕が近接（最良 $0.20$ と次点 $0.16$ の差は $0.04$ ）かつ地平が短い $T=2000$ では探索ボーナスが過大で腕2と腕3を分け合い収束途上——地平を伸ばせば最良腕へ収束し、劣線形リグレットの強みが効いてきます。戦略の優劣は地平に依存するので、自分の運用期間で評価してください。

1. 探索と活用：A/Bの固定割付からバンディットへ

A/Bテストの設計と分析では、トラフィックを $50:50$ で固定して一定期間流し、各腕の反応率を偏りなく推定して、勝った腕に切り替えました。これは「因果効果をきれいに測る」ためには理想的です。けれど、その間ずっと半分のトラフィックを負け腕に流し続けている——これが「学習のコスト」です。本当に最大化したいのが期間中の総コンバージョン（論文に載せる効果量ではなく）なら、証拠がたまるにつれて良い腕へ配分を寄せたい。これがバンディットの発想です。

舞台設定はこうです。 $K$ 本の腕（クリエイティブ案・推薦候補・価格水準）があり、1本引くと報酬（クリック／購入＝ $0/1$ ）が返る。各腕の真の報酬率 $\mu_k$ は未知。 $T$ 回の試行で累積報酬を最大化したい。ここに緊張があります——ある腕が良いと知るには引いてみる必要がある（探索）が、不確実な腕を引くたび、すでに良いと分かっている腕で稼げたはずの報酬を取りこぼす（活用の機会損失）。名前の由来は、当たりの分からないスロットマシン（＝片腕の盗賊 one-armed bandit）が何台も並んだ状況です。

flowchart LR
  subgraph AB["A/B テスト（固定割付・07-01）"]
    Aa["腕A：ずっと 50%"]
    Ab["腕B：ずっと 50%"]
  end
  subgraph MAB["多腕バンディット（適応配分）"]
    M1["腕を選ぶ"] --> M2["報酬を観測"] --> M3["推定を更新"]
    M3 --> M4{"探索と活用を両立"}
    M4 --> M1
  end
  AB -->|"負け腕にも流し続ける＝機会損失"| MAB

A/B は左の固定割付、バンディットは右の選ぶ→観測→更新を回し続けるループです。「どれだけ良い腕に寄せられたか」と「未知の腕をどれだけ取りこぼさず試せたか」を、毎ラウンド両立させるのが課題になります。

2. リグレットと3つの戦略（数式）

最大化したい累積報酬の代わりに、最小化したい機会損失を測るほうが見通しが良い。最良腕 $\mu^*=\max_k\mu_k$ だけを引き続けた理想と、実際に選んだ腕の期待報酬の差を累積リグレットと呼びます。

\text{Regret}(T)=\underbrace{T\mu^*}_{\text{最良腕だけの理想}}-\underbrace{\sum_{t=1}^{T}\mu_{a_t}}_{\text{実際に選んだ腕の期待報酬}}=\sum_{t=1}^{T}\bigl(\mu^*-\mu_{a_t}\bigr)

これは腕ごとに集計し直せて、ギャップ $\Delta_k=\mu^*-\mu_k$ と引いた回数 $n_k(T)$ の積の和になります。

\text{Regret}(T)=\sum_{k=1}^{K}\Delta_k\,\mathbb{E}\!\left[n_k(T)\right]

この式が全ての要です。リグレットは「ギャップの大きい（悪い）腕を、何回引いてしまったか」で決まる。だから二つの極端はどちらも損です。活用だけ（毎回いまの推定最良を引く）だと、序盤の偶然で悪い腕が良く見えるとそこに固定化し、悪い腕を $n_k\propto T$ 回引いてリグレットが線形に伸びる。探索だけ（A/B のように常に均等割付）だと $n_k\approx T/K$ で、 $\text{Regret}\approx\frac{T}{K}\sum_k\Delta_k$ とやはり線形。良い戦略は、データがたまるほど悪い腕を引く頻度を落とし、劣線形（対数的）リグレット $O\!\left(\sum_k\frac{\ln T}{\Delta_k}\right)$ を目指します。

ε-greedy は最も素朴な折衷です。経験的平均 $\hat\mu_k$ （その腕でこれまで得た報酬の平均）を持ち、

a_t= \begin{cases} \text{一様ランダムな腕} & \text{確率 }\varepsilon\\[4pt] \arg\max_k\hat\mu_k & \text{確率 }1-\varepsilon \end{cases}

で選びます。 $\varepsilon$ を固定すると、毎ラウンド確率 $\varepsilon$ で無作為に探索し続けるため、 $\frac{\varepsilon T}{K}\sum_k\Delta_k$ ぶんの線形の尾が残ります（ $\varepsilon_t\propto 1/t$ と減衰させれば対数リグレットに改善できます）。

UCB1 は「不確実なものは楽観的に評価する（optimism in the face of uncertainty）」原則です。

a_t=\arg\max_k\left(\hat\mu_k+\sqrt{\frac{2\ln t}{n_k}}\right)

加える項 $\sqrt{2\ln t/n_k}$ は、 $\mu_k$ の信頼区間の上側の幅（Hoeffding 不等式に由来）。引いた回数 $n_k$ が少ない腕ほど大きく（ $1/\sqrt{n_k}$ ）、自動的に探索が促され、よく引いた腕は幅が締まって実力勝負になる。 $\ln t$ はゆっくり増えるので、長く無視された腕もいつか再訪されます。理論上 $O(\sum_k\ln T/\Delta_k)$ の対数リグレットを達成します。

Thompson Sampling はベイズ的です。報酬がベルヌーイなら、腕 $k$ の反応率 $\mu_k$ の事後はベイズA/Bテストの Beta–二項共役そのもの—— $\text{Beta}(1,1)$ から始め、報酬 $r\in\{0,1\}$ を見るたび $\alpha_k\mathrel{+}=r,\ \beta_k\mathrel{+}=1-r$ と更新します。毎ラウンド、各腕の事後から1標本ずつ引いて、最大の腕を選ぶ。

\theta_k\sim\text{Beta}(\alpha_k,\beta_k)\quad(k=1,\dots,K),\qquad a_t=\arg\max_k\theta_k

これは確率マッチング——腕 $k$ は「事後のもとで $k$ が最良である確率」と等しい確率で選ばれます。不確実な腕は事後が広く、たまに高い標本を出して探索され、自信を持って良い腕はたいてい最大で活用される。探索と活用がサンプリング一発で自然に両立するのが美点で、これも対数リグレットを達成し、実務では最良のことが多い手法です。

3. 4戦略を走らせて比べる（コード）

真の報酬率を $\mu=[0.10,0.13,0.16,0.20]$ （最良＝腕3、 $\mu^*=0.20$ ）と決め、 $T=2000$ ラウンド回します。公平に比べるため共通乱数法を使います——rewards[t,k]＝「腕 $k$ をラウンド $t$ で引いたら出る $0/1$ 報酬」を1枚の表に先に作り、全戦略が同じ報酬実現を見るようにします。各戦略は毎ラウンド腕を選び、その腕の報酬だけを観測し、推定を更新します。sklearn は使わず、Thompson の事後標本は numpy の rng.beta で引きます。

import numpy as np
import pandas as pd

# 4本腕のベルヌーイ・バンディット。真の報酬率は腕3(=0.20)が最良。
rng = np.random.default_rng(0)
K = 4
mu = np.array([0.10, 0.13, 0.16, 0.20])   # 各腕の真の報酬率（学習者には未知）
T = 2000                                   # ラウンド数
best_arm = int(np.argmax(mu))              # 最良腕＝3
mu_star = mu[best_arm]                      # μ* = 0.20

# 共通の報酬表：全戦略が同じ報酬実現を見る（公平な比較＝共通乱数法）
# rewards[t, k] = 腕kをラウンドtで引いたときに出る0/1報酬
rewards = (rng.random((T, K)) < mu).astype(int)


def run_random(rewards, seed):
    g = np.random.default_rng(seed)
    T, K = rewards.shape
    arms = np.empty(T, dtype=int)
    for t in range(T):
        arms[t] = g.integers(K)            # 毎回ランダムに腕を選ぶ
    return arms, rewards[np.arange(T), arms]


def run_epsilon_greedy(rewards, eps, seed):
    g = np.random.default_rng(seed)
    T, K = rewards.shape
    counts = np.zeros(K)
    values = np.zeros(K)                   # 各腕の経験的な平均報酬
    arms = np.empty(T, dtype=int)
    rew = np.empty(T, dtype=int)
    for t in range(T):
        if g.random() < eps:
            a = g.integers(K)              # 確率εで無作為に探索
        else:
            a = int(np.argmax(values))     # 確率1−εで最良腕を活用
        r = rewards[t, a]
        counts[a] += 1
        values[a] += (r - values[a]) / counts[a]   # 平均を逐次更新
        arms[t], rew[t] = a, r
    return arms, rew


def run_ucb1(rewards):
    T, K = rewards.shape
    counts = np.zeros(K)
    values = np.zeros(K)
    arms = np.empty(T, dtype=int)
    rew = np.empty(T, dtype=int)
    for t in range(T):
        if t < K:
            a = t                          # 最初のKラウンドは各腕を1回ずつ
        else:
            ucb = values + np.sqrt(2 * np.log(t) / counts)      # 上側信頼界
            a = int(np.argmax(ucb))        # 楽観的に最大の腕を選ぶ
        r = rewards[t, a]
        counts[a] += 1
        values[a] += (r - values[a]) / counts[a]
        arms[t], rew[t] = a, r
    return arms, rew


def run_thompson(rewards, seed):
    g = np.random.default_rng(seed)
    T, K = rewards.shape
    alpha = np.ones(K)                     # Beta(1,1) 事前
    beta = np.ones(K)
    arms = np.empty(T, dtype=int)
    rew = np.empty(T, dtype=int)
    for t in range(T):
        theta = g.beta(alpha, beta)        # 各腕のBeta事後から1標本ずつ
        a = int(np.argmax(theta))          # 最大の標本を持つ腕を選ぶ
        r = rewards[t, a]
        if r == 1:
            alpha[a] += 1                  # 成功→α、失敗→βを更新
        else:
            beta[a] += 1
        arms[t], rew[t] = a, r
    return arms, rew


strategies = {
    "無作為": run_random(rewards, seed=1),
    "ε-greedy(ε=0.1)": run_epsilon_greedy(rewards, 0.1, seed=2),
    "UCB1": run_ucb1(rewards),
    "Thompson": run_thompson(rewards, seed=3),
}

rows = []
for name, (arms, rew) in strategies.items():
    final_regret = mu_star * T - mu[arms].sum()    # Tμ* − Σμ_{a_t}
    best_frac = np.mean(arms == best_arm)          # 最良腕(腕3)を選んだ割合
    total_reward = int(rew.sum())                  # 実現した累積報酬
    rows.append((name, final_regret, best_frac, total_reward))

df = pd.DataFrame(rows, columns=["戦略", "最終累積リグレット", "最良腕(腕3)選択割合", "累積報酬"])
print(f"4本腕ベルヌーイ μ={[0.10, 0.13, 0.16, 0.20]}  最良腕=腕{best_arm}(μ*={mu_star})  T={T}")
print(df.to_string(index=False, formatters={
    "最終累積リグレット": "{:.1f}".format,
    "最良腕(腕3)選択割合": "{:.1%}".format,
}))

出力：

4本腕ベルヌーイ μ=[0.1, 0.13, 0.16, 0.2]  最良腕=腕3(μ*=0.2)  T=2000
             戦略 最終累積リグレット 最良腕(腕3)選択割合  累積報酬
            無作為     102.0       27.4%   304
ε-greedy(ε=0.1)      26.2       81.8%   382
           UCB1      71.0       39.5%   341
       Thompson      19.2       80.5%   384

出力の意味：基準の無作為は4本を均等（各 $\approx25\%$ ）に引くだけで、リグレット $102.0$ ・最良腕 $27.4\%$ と最悪——学習しない戦略の損です。Thompson が最小リグレット $19.2$ ・累積報酬 $384$ で最良。ε-greedy(0.1) も $26.2$ ・最良腕 $81.8\%$ と健闘します。一方 UCB1 は $71.0$ ・最良腕 $39.5\%$ で、無作為には明確に勝つものの、Thompson・ε-greedy にはこの地平では及びません。

ここで $\S2$ の分解 $\text{Regret}=\sum_k\Delta_k n_k$ （ギャップ $\Delta=[0.10,0.07,0.04,0]$ ）が効きます。非最良の手をどの腕に費やしたかで損が決まる、という話です。Thompson は外した手を安い近接腕（腕2、ギャップ $0.04$ ）に集中させ（腕2を $15\%$ 、腕0/1 はほぼ引かない）、 $0.019{\times}.10+0.021{\times}.07+0.153{\times}.04\approx0.0095/\text{回}$ 、 $\times2000\approx19$ に収まる。ところが ε-greedy は最良腕割合こそ $81.8\%$ と高いのに、序盤にギャップの大きい腕1（ $0.07$ ）へ一時的に活用が固定し、そこを $13\%$ 引いてしまった——これが高くつき $26$ になります。「最良腕を当てた割合」が高くても、外した手が高ギャップ腕なら損は大きい。UCB1 は腕2（ $0.04$ ）を $35\%$ ・腕3 を $39\%$ と分け合ったまま終わっており、 $0.349{\times}.04$ だけで $28$ ぶんの損が積まれています。なぜ UCB1 がこうなるかは、図のあとで詰めます。

累積リグレットの時系列（4戦略）と、各戦略がどの腕を何割引いたかを1枚にします（このブロックはデータ生成から各戦略までを内部で再実行し、上と同じ値を描きます）。

import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib

# データ生成と4戦略の実行をこのブロック内で再現（ブロック単体で動く）。
rng = np.random.default_rng(0)
K, T = 4, 2000
mu = np.array([0.10, 0.13, 0.16, 0.20])
best_arm, mu_star = int(np.argmax(mu)), mu.max()
rewards = (rng.random((T, K)) < mu).astype(int)


def run(policy, seed=0):
    g = np.random.default_rng(seed)
    counts = np.zeros(K); values = np.zeros(K)
    alpha = np.ones(K); beta = np.ones(K)
    arms = np.empty(T, dtype=int)
    for t in range(T):
        if policy == "random":
            a = g.integers(K)
        elif policy == "egreedy":
            a = g.integers(K) if g.random() < 0.1 else int(np.argmax(values))
        elif policy == "ucb1":
            a = t if t < K else int(np.argmax(values + np.sqrt(2 * np.log(t) / counts)))
        else:  # thompson
            a = int(np.argmax(g.beta(alpha, beta)))
        r = rewards[t, a]
        counts[a] += 1; values[a] += (r - values[a]) / counts[a]
        if r == 1: alpha[a] += 1
        else: beta[a] += 1
        arms[t] = a
    return arms


runs = {
    "無作為": run("random", seed=1),
    "ε-greedy(ε=0.1)": run("egreedy", seed=2),
    "UCB1": run("ucb1"),
    "Thompson": run("thompson", seed=3),
}
colors = {"無作為": "C7", "ε-greedy(ε=0.1)": "C0", "UCB1": "C1", "Thompson": "C3"}

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(11.5, 4.4))

# 左：累積リグレットの時系列（寝ているほど良い）
ts = np.arange(1, T + 1)
for name, arms in runs.items():
    cum_regret = np.cumsum(mu_star - mu[arms])
    ax1.plot(ts, cum_regret, color=colors[name], lw=2, label=name)
ax1.set_xlabel("ラウンド t"); ax1.set_ylabel("累積リグレット")
ax1.set_title("累積リグレットの推移（寝ているほど良い）")
ax1.legend(loc="upper left", fontsize=9); ax1.grid(alpha=0.3)

# 右：各戦略の腕選択割合（積み上げ。最良腕＝腕3が上に伸びるほど良い）
names = list(runs.keys())
arm_colors = ["#cccccc", "#9ecae1", "#fdae6b", "#e6550d"]  # 腕3を強調
fracs = np.array([[np.mean(runs[nm] == k) for nm in names] for k in range(K)])
bottom = np.zeros(len(names))
for k in range(K):
    lbl = f"腕{k}" + ("（最良）" if k == best_arm else "")
    ax2.bar(names, fracs[k], bottom=bottom, color=arm_colors[k], label=lbl,
            edgecolor="white", width=0.6)
    bottom += fracs[k]
for j, nm in enumerate(names):                 # 最良腕の割合を上に注記
    ax2.text(j, 1.02, f"{np.mean(runs[nm] == best_arm):.0%}", ha="center", fontsize=9)
ax2.set_ylim(0, 1.12); ax2.set_ylabel("腕の選択割合")
ax2.set_title("各戦略の腕選択割合（上の数字＝最良腕の割合）")
ax2.legend(loc="lower center", ncol=4, fontsize=8, bbox_to_anchor=(0.5, -0.28))
plt.setp(ax2.get_xticklabels(), fontsize=9)

fig.suptitle("多腕バンディット：探索と活用のトレードオフ（μ=[.10,.13,.16,.20]・T=2000）")
fig.tight_layout()
plt.show()

左のリグレット曲線が物語です。無作為（灰）は直線——毎ラウンド一定の損を積む線形リグレット。Thompson（赤）は最も早く寝て最下層を走ります。ε-greedy（青）は序盤に立ち上がったあとほぼ平らになり（固定 $\varepsilon$ の線形の尾でわずかに上り続ける）、UCB1（橙）はその中間を、まだ寝きらずに上昇し続けます。右の積み上げ棒は各戦略の腕配分で、無作為はほぼ四等分、ε-greedy と Thompson は最良腕（濃橙）が $8$ 割超、UCB1 だけは腕2（薄橙）と腕3がほぼ半々——「まだ最良を選びきれていない」ことが目で見えます。

なぜ UCB1 がこの設定で振るわないかは、バグではなく原理です。最良腕（ $0.20$ ）と次点の腕2（ $0.16$ ）のギャップは $0.04$ しかありません。UCB1 がこの2本を見分けるには信頼界の幅 $\sqrt{2\ln t/n}$ をギャップの半分 $0.02$ 未満に縮める必要があり、 $n>2\ln(2000)/0.02^2\approx3.8\times10^4$ 回—— $T=2000$ では到底足りないのです。だから UCB1 は腕2と腕3を引き分けたまま終わります。実際、地平を $T=20000,\,100000$ と伸ばすと最良腕割合は $68\%,\,88\%$ へ上がり、リグレットは $71\to360\to685$ と対数的にしか増えません（＝最良腕に収束していく）。固定 $\varepsilon$ の ε-greedy が線形の尾を持つのに対し UCB1 は劣線形なので、十分大きな地平では UCB1 が優位になります（ただしギャップが小さい本設定では交差はさらに先で、Thompson はどの地平でも最小）。戦略の優劣は地平とギャップに依存する——短期キャンペーンと恒常運用で答えが変わる、という実務的に重要な教訓がここにあります。

⚠️ よくある誤解

探索と活用は両方とも、片方だけだと損：活用だけ（毎回いまの推定最良）だと、序盤の偶然で悪い腕が良く見えるとそこに固定化し、誤った腕を引き続けてリグレットが線形に伸びます。探索だけ（常に均等割付）は A/B と同じで、負け腕を一定割合で引き続けるためやはり損が線形。 $\text{Regret}=\sum_k\Delta_k n_k$ が示すとおり、良い戦略は証拠がたまるほど高ギャップ腕の $n_k$ を減らすことで劣線形を達成します。
ベンチマークは地平に依存する：本ノートで ε-greedy(0.1) が健闘したのは $T=2000$ が短いから。固定 $\varepsilon$ は線形の尾 $\frac{\varepsilon T}{K}\sum_k\Delta_k$ を残すので、 $T$ が大きいと劣線形の UCB1・Thompson に抜かれます（本設定では Thompson は全地平で ε-greedy を下回り、UCB1 は近接腕ゆえ交差が遠い）。逆に UCB1 が今回伸び悩んだのは近接腕＋短地平で $\sqrt{2\ln t/n}$ が過大だったため（バグではない）。「どの戦略が一番か」は自分の運用期間で測る——汎用の勝者を一つ覚えしないこと。
A/B とバンディットは目的が違う：A/Bテストの設計と分析の A/B は因果効果の厳密で不偏な推定が目的で、均等割付・固定期間だからこそ各腕の効果量をきれいに測れます。バンディットは累積報酬の最大化が目的で、適応配分のぶん推定にバイアスが乗ります（良い腕ばかり多く観測する・序盤の不運で早々に切った腕の評価が歪む＝winner’s curse）。厳密な効果量がほしいなら A/B、稼ぎながら学びたいならバンディット。両者は排他ではなく、A/B で効果を確かめてからバンディットで配分、という併用も普通です。
非定常だと過去を引きずる：本ノートは $\mu_k$ が時間で変わらない定常を仮定しました。実際の反応率は季節・在庫・飽きで動くことが多く、累積カウント（全履歴の平均）は古い情報を引きずって追従が遅れます。報酬率が変化するなら、割引（古い観測を指数的に軽く）やスライディング窓（直近のみ使う）で「忘れる」仕組みを足します（discounted UCB・減衰 Thompson など）。
文脈付きバンディットがレコメンド/価格に直結：本ノートは全ユーザー共通の腕を選びましたが、実務ではユーザーの特徴 $x$ で腕を出し分けたい（この人にはこのクリエイティブ／この価格）。これが文脈付きバンディット（contextual bandit）で、各腕の報酬を $x$ の関数としてモデル化します（LinUCB・文脈付き Thompson など）。協調フィルタリング（近傍法・行列分解）の「薦めて反応を見て更新する」オンライン最適化や価格戦略（価格差別・バンドル・心理価格）の動的価格は、まさにこの文脈付きの枠組みに乗ります。バンディットを強化学習の一場面として一般化する理論や文脈付きの手法は、機械学習テキストの守備範囲です。本ノートは重複させず、探索と活用を回しながら稼ぐという骨格に絞りました。

要点（BLUF）

1. 探索と活用：A/Bの固定割付からバンディットへ

2. リグレットと3つの戦略（数式）

3. 4戦略を走らせて比べる（コード）

⚠️ よくある誤解

関連ノート