あなたがカジノで3台のスロットマシン（腕=arm）の前に立っているとします。各マシンの当たりの確率は異なりますが、事前にはわかりません。限られた回数のプレイで獲得金額を最大化するには、どの戦略が最適でしょうか？
最初のうちは全てのマシンを均等に試して（探索）各マシンの当たり確率を推定し、次第に最も良いマシンを集中的にプレイする（活用）のが合理的です。しかし、探索にリソースを使いすぎれば活用の機会を逃し、活用に偏りすぎれば実は最良のマシンを見逃す可能性があります。
この探索と活用のトレードオフ（exploration-exploitation trade-off） を定量的に扱うのが多腕バンディット問題です。多腕バンディット問題は強化学習の最もシンプルな形であり（状態が1つ、行動の選択だけ）、探索と活用のトレードオフの本質を理解するための基盤です。
多腕バンディットの理論は以下のような実用的な場面で活用されています。
- A/Bテスト: Webサイトのデザインや広告の最適化
- 臨床試験: 新薬の最適な投与グループの割り当て
- 推薦システム: ユーザーに表示するコンテンツの選択
- ネットワーク最適化: 通信チャネルの動的な選択
本記事の内容
- 多腕バンディット問題の定式化とリグレットの概念
- ε-グリーディ法の分析
- UCB（Upper Confidence Bound）アルゴリズム
- Thompson Sampling（ベイズ的アプローチ）
- Pythonによる各アルゴリズムの比較実験
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
多腕バンディット問題の定式化
問題設定
多腕バンディット問題を正式に定式化しましょう。$K$ 本の腕（arm）を持つスロットマシンがあります。各腕 $i$ は未知の期待報酬 $\mu_i$ を持ちます。各タイムステップ $t = 1, 2, \ldots, T$ で、エージェントは1本の腕 $a_t \in \{1, \ldots, K\}$ を選び、報酬 $r_t$ を受け取ります。
報酬はその腕の分布からサンプリングされます。最も単純なベルヌーイバンディットでは、腕 $i$ を引くと確率 $\mu_i$ で報酬1、確率 $1 – \mu_i$ で報酬0が得られます。
ここで重要なのは、エージェントが観測できるのは「選んだ腕の報酬だけ」という点です。選ばなかった腕の報酬は観測できません。たとえばA/Bテストで広告Aを表示した場合、広告Bを表示していたらクリックされたかどうかは永遠にわかりません。この「反実仮想が観測できない」という性質が、バンディット問題を単純な最適化問題と異なるものにしています。
目標は、累積報酬 $\sum_{t=1}^T r_t$ を最大化することです。しかし、各腕の期待報酬 $\mu_i$ が未知であるため、最初から最適な行動をとることは不可能です。情報を集める（探索）ことと、集めた情報をもとに良い行動をとる（活用）ことのバランスが問題の本質になります。
リグレット
アルゴリズムの性能はリグレット（regret、後悔）で評価します。最適な腕 $a^* = \arg\max_i \mu_i$（期待報酬が最大の腕）を常に選んだ場合と比較した損失です。
$$ \begin{equation} R_T = T \mu^* – \sum_{t=1}^T \mu_{a_t} = \sum_{t=1}^T (\mu^* – \mu_{a_t}) \end{equation} $$
ここで $\mu^* = \max_i \mu_i$ は最適な腕の期待報酬です。
リグレット $R_T$ の式をもう少し丁寧に見てみましょう。$T\mu^*$ は「最初から最適な腕を知っていて常にそれを選んだ場合の期待累積報酬」です。$\sum_{t=1}^T \mu_{a_t}$ は「アルゴリズムが実際に選んだ腕の期待累積報酬」です。その差がリグレットですから、リグレットは「全知の神と比べてどれだけ損をしたか」を測る指標です。
リグレットは「最適な戦略を知っていた場合に比べて、どれだけ損をしたか」を測ります。良いアルゴリズムはリグレットの増加が遅い（$T$ に対して対数的 $O(\ln T)$）性質を持ちます。これは直感的に理解できます。良いアルゴリズムは時間が経つにつれて最適な腕を見つけ出し、ほとんどの場合その腕を選ぶようになるため、新たなリグレットの増加は非常に遅くなります。
リグレットの各ステップへの寄与は $\Delta_{a_t} = \mu^* – \mu_{a_t}$ です。最適な腕を選んだステップでは $\Delta_{a_t} = 0$ でリグレットは増えません。劣った腕 $i$ を選んだ回数を $N_i(T)$ と書けば、リグレットは
$$ R_T = \sum_{i: \mu_i < \mu^*} \Delta_i \cdot N_i(T) $$
と分解できます。つまり、サブオプティマリティギャップ $\Delta_i$ が大きい腕（明らかに劣った腕）の選択回数を減らすことが、リグレットの削減に直結します。
ライ・ロビンスの下界: 多腕バンディット問題には理論的な限界が存在します。どんなアルゴリズムでも、リグレットは
$$ R_T \geq \sum_{i: \mu_i < \mu^*} \frac{\Delta_i}{\text{KL}(\mu_i \| \mu^*)} \ln T $$
を下回ることはできません。ここで $\Delta_i = \mu^* – \mu_i$ はサブオプティマリティギャップ、$\text{KL}(\mu_i \| \mu^*)$ は腕 $i$ の報酬分布と最適な腕の報酬分布のKLダイバージェンスです。
この下界が意味しているのは、「最適な腕と劣った腕を統計的に区別するためには、劣った腕もある程度の回数を引かなければならない」ということです。KLダイバージェンスが小さい（分布が似ている）腕ほど区別が難しく、より多く探索する必要があるため、リグレットへの寄与が大きくなります。つまり、$O(\ln T)$ のリグレットは原理的に達成可能な最良のオーダーです。
リグレットの概念と理論的限界を理解したところで、次に具体的なアルゴリズムを見ていきましょう。まずは最もシンプルなε-グリーディ法から始めます。
ε-グリーディ法
アルゴリズム
ε-グリーディ法は最もシンプルなバンディットアルゴリズムです。確率 $\epsilon$ でランダムな腕を選び（探索）、確率 $1-\epsilon$ で現在の推定期待報酬が最大の腕を選びます（活用）。
各腕 $i$ の推定期待報酬 $\hat{\mu}_i$ は、これまでの観測報酬の平均で更新します。
$$ \hat{\mu}_i = \frac{1}{N_i} \sum_{t: a_t = i} r_t $$
$N_i$ は腕 $i$ が選ばれた回数です。実装上は、毎回全データから平均を再計算するのではなく、以下のインクリメンタル更新が効率的です。
$$ \hat{\mu}_i \leftarrow \hat{\mu}_i + \frac{1}{N_i}(r_t – \hat{\mu}_i) $$
新しい報酬 $r_t$ と現在の推定値 $\hat{\mu}_i$ との差（予測誤差）を、$1/N_i$ の割合で反映します。この更新式は、Q学習のTD更新と同じ構造をしています。
リグレット分析
固定の $\epsilon$ を使うε-グリーディ法のリグレットを分析してみましょう。各ステップでは確率 $\epsilon$ でランダムな腕を選びます。ランダムに選ぶとき、最適でない腕を選ぶ確率は $(K-1)/K$ です。したがって、最適でない腕を選ぶステップの期待数は $T \cdot \epsilon \cdot (K-1)/K$ のオーダーです。各ステップのリグレット寄与は $\Delta_i$ で上から抑えられるので、全体のリグレットは $O(\epsilon T)$ であり、$T$ に対して線形に増加します。
ここに $\epsilon$-グリーディ法の根本的なジレンマがあります。$\epsilon$ を大きくすれば探索が増えて最適な腕を早く見つけられますが、その分リグレットも大きくなります。$\epsilon$ を小さくすればリグレットの増加は抑えられますが、最初に選んだ腕がたまたま良かっただけで本当の最適腕を見逃す可能性が高まります。
$\epsilon$ を $1/t$ のように減衰させれば $O(\ln T)$ のリグレットが達成できますが、減衰スケジュールの設計は問題に依存します。また、減衰させても「探索がランダムで無駄を含む」という本質的な問題は残ります。最適な腕が $\mu^* = 0.9$ で、残りの腕が $\mu_i = 0.1$ であれば、数回引けば劣った腕だと分かるはずです。にもかかわらず、ε-グリーディ法はすべての腕を均等にランダム探索してしまいます。
より洗練された探索戦略——「どの腕の情報が不足しているか」を考慮して探索先を選ぶ——を提供するのがUCBアルゴリズムです。
UCB（Upper Confidence Bound）
楽観主義の原理
UCBは「不確実なものに対して楽観的に」（optimism in the face of uncertainty）という原理に基づきます。
この原理を転職活動のアナロジーで理解しましょう。今の職場（腕A）の満足度はよく分かっています。一方、求人情報だけ見た別の会社（腕B）の実際の満足度は不確実です。「不確実なものに楽観的に」という原理は、「よく知らない会社は、もしかしたら素晴らしいかもしれない」と楽観的に評価して面接に行ってみる（探索する）ことを推奨します。面接してみて期待外れなら、その不確実性は減少し、以降はその会社を楽観的に評価しなくなります。逆に期待通りなら、今後はその会社を選ぶようになります。
十分に試していない腕には不確実性が大きいため、その期待報酬の上側信頼限界は高くなります。UCBは各腕の推定期待報酬に「不確実性ボーナス」を加え、この上側信頼限界が最大の腕を選びます。
$$ \begin{equation} a_t = \arg\max_i \left[\hat{\mu}_i + c \sqrt{\frac{\ln t}{N_i}}\right] \end{equation} $$
$\hat{\mu}_i$ は腕 $i$ の推定期待報酬、$N_i$ は腕 $i$ が選ばれた回数、$c$ は探索パラメータ（通常 $c = \sqrt{2}$）です。
第2項 $c\sqrt{\ln t / N_i}$ が不確実性ボーナスです。この項の構造を詳しく見てみましょう。
- $N_i$ が小さい（あまり試していない）→ 分母が小さい → ボーナスが大きい → 探索される
- $N_i$ が大きい（十分に試した）→ 分母が大きい → ボーナスが小さい → $\hat{\mu}_i$ が支配的 → 活用される
- $t$ が増加 → 分子 $\ln t$ が緩やかに増加 → 長期間選ばれていない腕のボーナスが徐々に回復 → いずれ再探索される
$\sqrt{\ln t / N_i}$ という形が出てくるのは、ヘフディングの不等式に由来しています。$N_i$ 回の独立なサンプルから推定した平均 $\hat{\mu}_i$ が真の平均 $\mu_i$ から $\epsilon$ 以上ずれる確率は
$$ P(|\hat{\mu}_i – \mu_i| \geq \epsilon) \leq 2\exp(-2N_i \epsilon^2) $$
で抑えられます。信頼度 $1 – 2/t^{2c^2}$ で $\mu_i$ が含まれる区間の幅が $c\sqrt{\ln t / N_i}$ となるため、これが不確実性ボーナスの自然な形になるのです。
UCBのリグレット保証
UCB1（$c = \sqrt{2}$）のリグレットは以下の上界を持ちます。
$$ R_T \leq 8 \sum_{i: \mu_i < \mu^*} \frac{\ln T}{\Delta_i} + (1 + \frac{\pi^2}{3}) \sum_{i=1}^K \Delta_i $$
この式の第1項を読み解きましょう。$\ln T / \Delta_i$ は「ギャップ $\Delta_i$ が小さい腕ほど、最適腕と区別するために多くの探索が必要になる」ことを反映しています。$\Delta_i$ が小さい（最適腕に近い）腕は、多くのサンプルを集めなければ劣っていると確信できないためです。第1項は $O(\ln T)$ であり、ライ・ロビンスの下界のオーダーに一致します。第2項は $T$ に依存しない定数です。つまり、UCBは漸近的に最適なリグレットを達成するのです。
UCBの美しい点は、ε-グリーディのように「探索率 $\epsilon$ をどう設定するか」というハイパーパラメータの調整問題がないことです。不確実性ボーナスが自動的に探索と活用のバランスを取ってくれます。ただし、探索パラメータ $c$ の選択は必要で、$c$ が大きすぎると探索過多に、小さすぎると探索不足になります。
UCBが頻度論的なアプローチ（信頼区間に基づく探索）であるのに対し、次に紹介するThompson Samplingはベイズ的なアプローチで探索と活用のバランスを取ります。
Thompson Sampling
ベイズ的アプローチ
Thompson Sampling（トンプソンサンプリング）は、1933年にWilliam Thompsonが提案した、驚くほどシンプルかつ強力なアルゴリズムです。各腕の報酬分布に対するベイズ的な信念（事後分布）を維持し、その信念に比例して腕を選びます。
ベイズ的アプローチの核心は、「パラメータの点推定ではなく、パラメータの不確実性そのものを分布として管理する」ことです。UCBが「推定値 + 不確実性ボーナス」という形で不確実性を取り入れたのに対し、Thompson Samplingはパラメータの事後分布全体を使います。
ベルヌーイバンディットの場合、各腕 $i$ の成功確率 $\mu_i$ に対してBeta分布の事前分布を置きます。
$$ \mu_i \sim \text{Beta}(\alpha_i, \beta_i) $$
初期値は $\alpha_i = 1, \beta_i = 1$（一様分布）とします。Beta分布を事前分布に選ぶのは、ベルヌーイ分布の共役事前分布だからです。共役事前分布を使うと、データを観測した後の事後分布も同じ分布族（Beta分布）に属するため、パラメータの更新が $\alpha$ と $\beta$ の足し算だけで済みます。
各タイムステップで以下を実行します。
- 各腕 $i$ について、事後分布 $\text{Beta}(\alpha_i, \beta_i)$ からサンプル $\tilde{\mu}_i$ を抽出
- $\tilde{\mu}_i$ が最大の腕を選択: $a_t = \arg\max_i \tilde{\mu}_i$
- 報酬 $r_t$ を観測し、事後分布を更新 – 報酬1なら: $\alpha_{a_t} \leftarrow \alpha_{a_t} + 1$ – 報酬0なら: $\beta_{a_t} \leftarrow \beta_{a_t} + 1$
Thompson Samplingの直感
Thompson Samplingの直感は「自分の信念に比例して行動する」ことです。
不確実な腕（$\alpha_i + \beta_i$ が小さい）の事後分布は幅が広いため、サンプルされる値の範囲が大きくなります。偶然高い値がサンプルされれば選ばれ（探索）、低い値がサンプルされれば選ばれません。結果として、不確実な腕は「その不確実性に応じた頻度で」自動的に探索されます。
確実な腕（$\alpha_i + \beta_i$ が大きい）の事後分布は鋭いピークを持ち、サンプル値が真の期待報酬の近くに集中します。最良の腕は高い値が頻繁にサンプルされ、活用されます。
Thompson Samplingの探索メカニズムをもう少し定量的に見てみましょう。腕 $i$ が選ばれる確率は、その腕が最適である事後確率に一致します。
$$ P(a_t = i) = P\left(\tilde{\mu}_i = \max_j \tilde{\mu}_j\right) = \int \mathbf{1}\left[\mu_i = \max_j \mu_j\right] \prod_j p(\mu_j | \text{data}) \, d\mu_1 \cdots d\mu_K $$
この式は、各腕のパラメータを事後分布からサンプリングしたとき、腕 $i$ のサンプルが最大になる確率を表しています。つまり、Thompson Samplingは「各腕が最適である確率に比例して」その腕を選択するのです。これは確率マッチングとも呼ばれ、探索と活用の自然なバランスを実現します。
リグレットの保証
Thompson Samplingも $O(\ln T)$ のリグレット保証を持ちます。具体的には、Agrawal & Goyal（2012）によって以下のリグレット上界が証明されています。
$$ \mathbb{E}[R_T] \leq \sum_{i: \mu_i < \mu^*} \left(\frac{\Delta_i}{\text{KL}(\mu_i \| \mu^*)} + O(1)\right) \ln T $$
この上界はライ・ロビンスの下界の定数倍に一致しており、Thompson Samplingが漸近的に最適であることを示しています。
実験的にはUCBよりも優れた性能を示すことが多いです。その理由は、Thompson Samplingが「必要な分だけ探索する」効率的な探索を行うためです。UCBはすべての腕に同じ形の不確実性ボーナスを与えますが、Thompson Samplingは各腕の事後分布の形状（つまり、これまでの観測データが示す情報量）を正確に反映した探索を行います。
たとえば、腕Aで100回中50回成功（$\text{Beta}(51, 51)$）、腕Bで2回中1回成功（$\text{Beta}(2, 2)$）という状況を考えましょう。どちらも成功率の推定値は0.5ですが、腕Aの事後分布は鋭い（不確実性が小さい）のに対し、腕Bの事後分布は幅広い（不確実性が大きい）です。Thompson Samplingは腕Bから高い値をサンプリングする確率が高くなるため、自然と不確実な腕Bを優先的に探索します。
それでは、これまでに紹介した3つのアルゴリズムをPythonで実装し、性能を比較してみましょう。
Pythonによる比較実験
import numpy as np
import matplotlib.pyplot as plt
from scipy import stats
np.random.seed(42)
# --- バンディット環境 ---
class BernoulliBandit:
def __init__(self, probs):
self.probs = np.array(probs)
self.K = len(probs)
self.best_arm = np.argmax(probs)
self.best_prob = np.max(probs)
def pull(self, arm):
return float(np.random.random() < self.probs[arm])
# --- アルゴリズム ---
class EpsilonGreedy:
def __init__(self, K, epsilon=0.1):
self.K = K
self.epsilon = epsilon
self.counts = np.zeros(K)
self.values = np.zeros(K)
def select(self):
if np.random.random() < self.epsilon:
return np.random.randint(self.K)
return np.argmax(self.values)
def update(self, arm, reward):
self.counts[arm] += 1
n = self.counts[arm]
self.values[arm] += (reward - self.values[arm]) / n
class UCB:
def __init__(self, K, c=2.0):
self.K = K
self.c = c
self.counts = np.zeros(K)
self.values = np.zeros(K)
self.t = 0
def select(self):
self.t += 1
# 全ての腕を1回ずつ試す
for i in range(self.K):
if self.counts[i] == 0:
return i
ucb_values = self.values + self.c * np.sqrt(
np.log(self.t) / self.counts)
return np.argmax(ucb_values)
def update(self, arm, reward):
self.counts[arm] += 1
n = self.counts[arm]
self.values[arm] += (reward - self.values[arm]) / n
class ThompsonSampling:
def __init__(self, K):
self.K = K
self.alpha = np.ones(K)
self.beta = np.ones(K)
def select(self):
samples = np.random.beta(self.alpha, self.beta)
return np.argmax(samples)
def update(self, arm, reward):
if reward > 0:
self.alpha[arm] += 1
else:
self.beta[arm] += 1
# --- 実験 ---
bandit = BernoulliBandit([0.2, 0.5, 0.75, 0.6])
T = 5000
n_runs = 200
algorithms = {
'ε-Greedy (ε=0.1)': lambda: EpsilonGreedy(bandit.K, 0.1),
'ε-Greedy (ε=0.01)': lambda: EpsilonGreedy(bandit.K, 0.01),
'UCB (c=√2)': lambda: UCB(bandit.K, np.sqrt(2)),
'Thompson Sampling': lambda: ThompsonSampling(bandit.K),
}
results = {}
for name, algo_fn in algorithms.items():
all_regrets = np.zeros((n_runs, T))
for run in range(n_runs):
algo = algo_fn()
cum_regret = 0
for t in range(T):
arm = algo.select()
reward = bandit.pull(arm)
algo.update(arm, reward)
cum_regret += bandit.best_prob - bandit.probs[arm]
all_regrets[run, t] = cum_regret
results[name] = all_regrets
# --- 可視化 ---
fig, axes = plt.subplots(2, 2, figsize=(14, 10))
# (a) 累積リグレットの比較
ax = axes[0, 0]
colors = ['red', 'orange', 'blue', 'green']
for (name, regrets), color in zip(results.items(), colors):
mean_regret = regrets.mean(axis=0)
std_regret = regrets.std(axis=0)
ax.plot(mean_regret, label=name, color=color, linewidth=2)
ax.fill_between(range(T), mean_regret - std_regret,
mean_regret + std_regret, alpha=0.1, color=color)
ax.set_xlabel('Time step', fontsize=12)
ax.set_ylabel('Cumulative Regret', fontsize=12)
ax.set_title('Cumulative Regret Comparison', fontsize=13)
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)
# (b) 対数スケールでの比較
ax = axes[0, 1]
for (name, regrets), color in zip(results.items(), colors):
mean_regret = regrets.mean(axis=0)
ax.plot(mean_regret, label=name, color=color, linewidth=2)
ax.set_xscale('log')
ax.set_xlabel('Time step (log)', fontsize=12)
ax.set_ylabel('Cumulative Regret', fontsize=12)
ax.set_title('Regret (log scale)', fontsize=13)
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)
# (c) Thompson Samplingの事後分布の推移
ax = axes[1, 0]
ts = ThompsonSampling(bandit.K)
snapshots = [10, 50, 200, 1000]
x = np.linspace(0, 1, 200)
for t_snap in range(max(snapshots)):
arm = ts.select()
reward = bandit.pull(arm)
ts.update(arm, reward)
if (t_snap + 1) in snapshots:
for i in range(bandit.K):
pdf = stats.beta.pdf(x, ts.alpha[i], ts.beta[i])
if t_snap + 1 == snapshots[-1]:
ax.plot(x, pdf, linewidth=1.5,
label=f'Arm {i} (true={bandit.probs[i]:.2f})')
ax.axvline(bandit.probs[i], linestyle=':', alpha=0.3)
ax.set_xlabel('$\\mu$', fontsize=12)
ax.set_ylabel('Posterior density', fontsize=12)
ax.set_title(f'Thompson Sampling Posteriors (t={snapshots[-1]})',
fontsize=13)
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)
# (d) 各腕の選択比率
ax = axes[1, 1]
ts2 = ThompsonSampling(bandit.K)
arm_counts = np.zeros((T, bandit.K))
for t in range(T):
arm = ts2.select()
reward = bandit.pull(arm)
ts2.update(arm, reward)
arm_counts[t, arm] = 1
# 累積選択比率
cum_counts = np.cumsum(arm_counts, axis=0)
cum_ratios = cum_counts / (np.arange(1, T+1).reshape(-1, 1))
for i in range(bandit.K):
ax.plot(cum_ratios[:, i], linewidth=2,
label=f'Arm {i} ($\\mu$={bandit.probs[i]:.2f})')
ax.set_xlabel('Time step', fontsize=12)
ax.set_ylabel('Selection Ratio', fontsize=12)
ax.set_title('Arm Selection Ratios (Thompson Sampling)', fontsize=13)
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('bandit_comparison.png', dpi=150, bbox_inches='tight')
plt.show()
この比較実験から、各アルゴリズムの特性が明確に確認できます。
-
左上（累積リグレット）: Thompson SamplingとUCBがε-グリーディ法を大幅に上回っています。Thompson Samplingのリグレットは最も低く、UCBがそれに次ぎます。ε=0.1のε-グリーディは線形的にリグレットが増加し続けますが、UCBとThompson Samplingは対数的な増加にとどまっています
-
右上（対数スケール）: 対数スケールで見ると、UCBとThompson Samplingのリグレットがほぼ直線的に増加する（$O(\ln T)$）のに対し、ε-グリーディのリグレットは直線より速く増加する（$O(T)$）ことが確認できます
-
左下（事後分布）: Thompson Samplingが1000ステップ後に学習した各腕の事後分布です。最良の腕（$\mu = 0.75$）の事後分布は鋭いピークを持ち、真の値の近くに集中しています。劣った腕の事後分布は相対的に不確実ですが、真の値を中心に分布しています
-
右下（選択比率）: Thompson Samplingの各腕の選択比率の推移です。学習初期は全ての腕がほぼ均等に選ばれますが、時間が経つにつれて最良の腕（$\mu = 0.75$）の選択比率が1に近づいています。他の腕の選択比率は急速に減少しますが、完全にゼロにはならず、僅かな探索が続いています
実験設定について補足すると、4本の腕の真の成功確率は $[0.2, 0.5, 0.75, 0.6]$ です。最適な腕は3番目（$\mu^* = 0.75$）で、サブオプティマリティギャップは $\Delta = [0.55, 0.25, 0, 0.15]$ です。$\Delta$ が小さい腕（腕4の $\Delta = 0.15$）ほど最適腕と区別が難しいため、探索に多くのステップが必要になります。200回の独立した実験の平均と標準偏差を表示しているため、結果のばらつきも確認できます。
実用上の考慮事項
ここまで理論的な設定でのアルゴリズムを見てきましたが、実際のアプリケーションでバンディットアルゴリズムを使う際には、いくつかの追加的な考慮事項があります。
非定常バンディット
本記事で扱ったのは定常バンディット（各腕の期待報酬が時間とともに変化しない）ですが、現実の多くの場面では報酬分布が時間とともに変化します。たとえば、Webサイトのクリック率はユーザーの嗜好の変化、季節、トレンドなどにより変動します。
非定常環境では、古い観測よりも新しい観測を重視する必要があります。代表的なアプローチとして以下があります。
- スライディングウィンドウ: 直近 $W$ ステップの観測のみを使って推定値を更新する
- 指数的減衰: 推定値の更新に固定の学習率 $\alpha$ を使い、$\hat{\mu}_i \leftarrow \hat{\mu}_i + \alpha(r_t – \hat{\mu}_i)$ とする。$1/N_i$ の代わりに固定の $\alpha$ を使うことで、古い観測の影響が指数的に減衰する
- 変化検知: 報酬分布の変化を統計的検定で検知し、変化が検出されたらアルゴリズムをリセットする
文脈付きバンディット
標準的なバンディット問題では状態（文脈）を考慮しませんが、文脈付きバンディット（contextual bandit）は各タイムステップで文脈ベクトル $\bm{x}_t$ が与えられ、文脈に応じた最適な腕が異なる設定を扱います。
たとえばニュース推薦では、ユーザーの属性（年齢、地域、閲覧履歴）が文脈であり、表示する記事が腕に対応します。同じ記事でも、ユーザーによってクリック率が異なるため、文脈を考慮した選択が必要です。LinUCBやNeural Banditなどのアルゴリズムがこの設定に対応しています。
バンディットと強化学習の関係
多腕バンディット問題は、強化学習の「状態が1つだけ」の特殊ケースと見なせます。バンディット問題では行動の結果が即座に報酬として返されますが、強化学習ではある行動の影響が将来の状態と報酬に波及します（遅延報酬）。バンディット問題で培った探索と活用の概念は、DQNのε-グリーディ方策や、UCBに基づくモンテカルロ木探索（AlphaGoで使用）など、より複雑な強化学習手法の基盤になっています。
まとめ
本記事では、多腕バンディット問題の理論と主要なアルゴリズムについて解説しました。
- 多腕バンディットは探索と活用のトレードオフを扱う最もシンプルな強化学習問題
- リグレットはアルゴリズムの性能を測る指標であり、$O(\ln T)$ が達成可能な最良のオーダー
- ε-グリーディはシンプルだがリグレットが $O(T)$ で線形に増加する
- UCBは不確実性ボーナスにより楽観的に探索し、$O(\ln T)$ のリグレットを達成
- Thompson Samplingはベイズ的な事後分布からのサンプリングで探索し、$O(\ln T)$ のリグレットを達成
- 実験的にはThompson Samplingが最も優れた性能を示すことが多い
次のステップとして、以下の記事も参考にしてください。
- 探索と活用のトレードオフを理解する — 強化学習全般での探索手法
- ベイズ最適化の理論と実装 — バンディットの連続版
- モデルベース強化学習の基礎 — 環境モデルの学習