あなたが新しい街に引っ越してきたとします。昼食のレストランを選ぶとき、2つの戦略があります。
- 活用（Exploitation）: これまで行った中で一番美味しかったレストランに毎日行く
- 探索（Exploration）: まだ行ったことのないレストランを試す
活用だけでは、もっと美味しいレストランを見つける機会を逃します。探索だけでは、既に知っている美味しいレストランの恩恵を受けられません。この探索と活用のトレードオフ（exploration-exploitation trade-off）は、強化学習の最も根本的なジレンマです。活用だけに偏れば「局所最適」にはまり、探索だけに偏れば「永遠に試すだけ」で成果が得られません。このバランスをいかに取るかが、強化学習アルゴリズムの性能を左右する決定的な要因となります。
このジレンマは単にレストラン選びだけの問題ではありません。ウェブ広告の配信（どの広告を表示するか）、臨床試験のデザイン（どの治療法を試すか）、ロボットの行動計画（未知の環境でどう動くか）、さらには就職活動（もっと良い会社があるかもしれないが、今の内定先で十分か）など、不確かさのもとでの意思決定全般に現れます。
探索と活用のトレードオフを理解すると、以下のような場面で活用できます。
- 強化学習: 効率的な方策の学習
- A/Bテスト: 限られたサンプルでの最適な変種の特定
- ハイパーパラメータ最適化: 探索空間の効率的なカバー
- 推薦システム: ユーザーの好みの学習と既知の好みの活用
本記事の内容
- 探索と活用のトレードオフの形式的な定義
- 後悔（regret）の理論
- epsilon-greedy, ボルツマン探索, UCB, Thompson Sampling
- 深層強化学習における探索手法
- Pythonでの比較実験
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 多腕バンディット問題 — 探索と活用の基礎的なモデル
- DQNの理論と実装 — 深層強化学習の基礎
形式的な定義
多腕バンディット問題との関係
探索と活用のトレードオフを数学的に分析するには、問題を単純化して本質だけを取り出す必要があります。そのための理想的なモデルが多腕バンディット問題です。名前の由来はカジノのスロットマシン（one-armed bandit: 片腕の強盗）で、複数のスロットマシンの中からどれを引くかという意思決定問題を指します。$K$ 本のアーム（選択肢）があり、各アーム $a$ を引くと未知の分布 $P_a$ から報酬 $r$ が得られます。プレイヤーは各スロットマシンの当たりやすさを知りません。$T$ 回の試行で累積報酬を最大化することが目標です。
最適な戦略は、最も報酬期待値が高いアーム $a^* = \arg\max_a \mu_a$（$\mu_a = \mathbb{E}[r|a]$）を毎回引くことです。しかし、各アームの $\mu_a$ は未知なので、最適アームを特定するために探索が必要です。
多腕バンディット問題は「状態が1つしかない」強化学習の特殊ケースと見なすこともできます。状態遷移がないため問題の構造が単純ですが、探索と活用のトレードオフの本質は完全に保持されています。この単純さのおかげで、各探索戦略の理論的な性質を厳密に分析できるのです。
後悔（Regret）
探索戦略の良し悪しを測る指標として、後悔（regret）を定義します。後悔は、「もし最初から最適なアームがわかっていたら得られたであろう報酬」と「実際に得られた報酬」の差です。
$$ \begin{equation} \text{Regret}(T) = T \cdot \mu^* – \sum_{t=1}^{T} \mu_{a_t} \end{equation} $$
ここで $\mu^* = \max_a \mu_a$ は最適アームの期待報酬、$a_t$ は時刻 $t$ で選択したアームです。
良い探索戦略は、後悔の増加を遅くします。理論的には、
- 最悪の場合: 後悔は $O(T)$（線形に増加 = 何も学習していない）
- 下界: $\Omega(\sqrt{KT})$（Lai & Robbins, 1985）— どんな戦略でもこれ以下にはできない
- UCBの上界: $O(\sqrt{KT \log T})$ — ほぼ最適
後悔が $o(T)$（$T$ より遅く増加）する戦略は、長期的に最適アームを見つけていることを意味します。
後悔の概念は非常に重要です。単に「累積報酬が高い」だけでは良い戦略かどうか判断できません。なぜなら、報酬の絶対値は問題の設定に依存するからです。後悔は「最適戦略と比べてどれだけ損をしたか」を測るので、問題の設定に依存しない公正な評価基準となります。後悔が0に近いほど、「もし最初から最適アームを知っていた場合」に近い性能を達成していることを意味します。
各探索戦略が後悔にどう影響するかを見ていきましょう。
epsilon-greedy
アルゴリズム
epsilon-greedyは最もシンプルかつ広く使われている探索戦略です。レストランのアナロジーに戻ると、「サイコロを振って1が出たら新しいレストランに行き、それ以外なら一番美味しかったレストランに行く」という戦略に相当します。確率 $\epsilon$ でランダムに探索し、確率 $1 – \epsilon$ で現在の推定が最良のアームを活用します。
$$ a_t = \begin{cases} \text{uniform random from } \{1, \ldots, K\} & \text{with probability } \epsilon \\ \arg\max_a \hat{\mu}_a & \text{with probability } 1 – \epsilon \end{cases} $$
ここで $\hat{\mu}_a$ はアーム $a$ の報酬の標本平均です。$\epsilon = 0.1$ なら10%の確率でランダムに行動し、90%の確率で今の推定に基づいて最良の行動を取ります。
$\epsilon$ の値が大きいほど探索が多く、小さいほど活用が多くなります。$\epsilon = 0$ は完全な貪欲方策（一切探索しない）、$\epsilon = 1$ は完全なランダム方策（一切活用しない）に対応します。
後悔の分析
固定 $\epsilon$ の場合、後悔は $O(\epsilon T)$ で線形に増加します。なぜなら、$\epsilon T$ 回のランダム選択で最適でないアームを引くからです。これは致命的な問題です。試行回数 $T$ を増やしても、後悔が線形に増え続けるということは、エージェントが「いつまでも無駄な探索を続けている」ことを意味します。これは、十分な情報が集まった後も盲目的に探索し続けるepsilon-greedyの構造的な限界です。
減衰epsilon-greedy
$\epsilon$ を時間とともに減衰させることで、初期は多く探索し、徐々に活用に移行します。
$$ \epsilon_t = \min\left(1, \frac{c K}{d^2 t}\right) $$
ここで $c$ は定数、$d = \min_{a \neq a^*}(\mu^* – \mu_a)$ は最適アームと次善アームの差です。適切な減衰により、後悔を $O(\log T)$ に改善できます。
しかし $d$ は未知であり、実用では $\epsilon_t = 1/\sqrt{t}$ 等のヒューリスティックが使われます。
epsilon-greedyの最大の利点は実装の容易さと直感的なわかりやすさです。そのため、多くの強化学習の教科書やチュートリアルで最初に紹介されます。しかし、探索時にアームの推定値を一切考慮しない「完全ランダム」な探索は明らかに非効率です。例えば、推定報酬が明らかに低いアームにも等確率で探索してしまいます。この欠点を改善したのが、次に紹介するボルツマン探索です。
ボルツマン探索（Softmax探索）
アルゴリズム
ボルツマン探索（Softmax探索とも呼ばれます）は、統計力学のボルツマン分布に着想を得た手法です。温度の高い系では分子がさまざまなエネルギー状態をとるように、高い温度パラメータのもとでは多様な行動を取り、温度が低くなるにつれてエネルギーの低い（報酬の高い）状態に集中していきます。
各アームの推定報酬に基づくソフトマックス分布から確率的にアームを選択します。
$$ \begin{equation} P(a_t = a) = \frac{\exp(\hat{\mu}_a / \tau)}{\sum_{a’} \exp(\hat{\mu}_{a’} / \tau)} \end{equation} $$
温度 $\tau > 0$ が探索と活用のバランスを制御します。
- $\tau \to 0$: 最良アームに確率が集中（貪欲 = 活用のみ）
- $\tau \to \infty$: 一様分布に近づく（完全な探索）
温度パラメータの名前は統計力学に由来します。低温では物質の原子は最もエネルギーの低い状態に落ち着き、高温では多様な状態を取ります。同様に、低い $\tau$ ではエージェントは最も報酬の高い行動に集中し、高い $\tau$ では多様な行動を試みます。実用では $\tau$ を時間とともに減衰させる（焼きなまし法のように徐々に冷やす）ことで、初期の探索から後期の活用への移行を実現できます。
epsilon-greedyとの比較
ボルツマン探索の利点は、アームの推定値に基づいて探索を行うことです。epsilon-greedyは探索時に完全にランダムですが、ボルツマン探索は推定値が低いアームを選ぶ確率が低くなります。
例えば、3つのアームの推定報酬が $\hat{\mu}_1 = 5, \hat{\mu}_2 = 3, \hat{\mu}_3 = 1$ のとき
- epsilon-greedy（探索時）: 各アームを等確率で選択
- ボルツマン探索: $\hat{\mu}_1$ のアームが最も高い確率で選ばれ、$\hat{\mu}_3$ は低い確率。推定報酬の差に応じて選択確率が連続的に変化します
この「情報に基づく探索」は、次に紹介するUCBでさらに洗練されます。ただし、ボルツマン探索にも弱点があります。温度パラメータ $\tau$ の選択が難しく、推定値のスケールに依存するため、問題ごとに適切な $\tau$ を探す必要があります。また、推定が不正確な序盤では、たまたま高い推定値を持つ最適でないアームに偏ってしまう可能性もあります。
UCB（Upper Confidence Bound）
アルゴリズム
UCBは「不確かなものには楽観的に対処せよ」（optimism in the face of uncertainty）という原理に基づいた手法です。確率的な探索（epsilon-greedyやボルツマン探索）とは異なり、UCBは決定論的にアームを選択します。各アームの推定値に「不確かさボーナス」を加えた「楽観的な推定値」（信頼上界）を計算し、最も楽観的なアームを選択します。
$$ \begin{equation} a_t = \arg\max_a \left[\hat{\mu}_a + \sqrt{\frac{2 \ln t}{N_a(t)}}\right] \end{equation} $$
ここで $N_a(t)$ は時刻 $t$ までにアーム $a$ を引いた回数です。第1項 $\hat{\mu}_a$ が活用を、第2項 $\sqrt{2\ln t / N_a(t)}$ が探索を担当しており、この2つの合計が最大のアームを決定論的に選びます。
直感
UCBの考え方は「楽観主義（optimism in the face of uncertainty）」です。
- $\hat{\mu}_a$: アーム $a$ の現在の推定値（活用項）
- $\sqrt{2 \ln t / N_a(t)}$: 信頼区間の幅（探索項）
たくさん引いたアーム（$N_a$ が大きい）は信頼区間が狭く、推定が正確です。あまり引いていないアーム（$N_a$ が小さい）は信頼区間が広く、「もしかしたら良いかもしれない」という楽観的な見積もりが大きくなります。
具体的な数値例で考えてみましょう。アームAは100回引いて平均報酬0.5、アームBは3回引いて平均報酬0.4とします。$t = 103$ のとき、UCB値はアームAが $0.5 + \sqrt{2\ln 103 / 100} \approx 0.80$、アームBが $0.4 + \sqrt{2\ln 103 / 3} \approx 2.15$ となります。アームBは推定報酬が低いにもかかわらずUCB値が圧倒的に高いため、UCBは「まだ十分に試していないアームB」を優先的に探索します。
この仕組みにより、UCBは以下の自然な行動をとります: 1. あまり試していないアームを積極的に探索する（信頼区間が広いため） 2. 推定値が高いアームを活用する（$\hat{\mu}_a$ が大きいため） 3. 十分に探索した結果、推定値が低いアームを避ける（信頼区間が狭く、楽観値も低いため）
後悔の保証
Auer et al.（2002）は、UCB1の後悔が
$$ \text{Regret}(T) \leq 8 \sum_{a: \mu_a < \mu^*} \frac{\ln T}{\Delta_a} + (1 + \frac{\pi^2}{3}) \sum_{a: \mu_a < \mu^*} \Delta_a $$
を満たすことを証明しました。ここで $\Delta_a = \mu^* – \mu_a$ です。後悔が $O(\log T)$ で増加し、これはLai & Robbinsの下界にほぼ一致します。
この結果の意味を直感的に理解しましょう。$O(\log T)$ の後悔とは、試行回数を10倍にしても後悔は $\log 10 \approx 2.3$ 倍しか増えないということです。つまり、長く試行するほど「ほぼ最適なアーム」を選び続けることになります。UCBの探索項 $\sqrt{2 \ln t / N_a(t)}$ が自然に「不確かなアームを優先的に探索し、十分探索したアームは活用に回す」というバランスを実現しているのです。
UCBは理論的に強力ですが、頻度主義的なアプローチです。次に紹介するThompson Samplingは、ベイズ統計の枠組みで同等以上の性能を達成する手法です。
Thompson Sampling
アルゴリズム
Thompson Sampling（Thompson, 1933）は、驚くほど古い歴史を持つ手法です。1933年に提案されながら、長年にわたって理論的な分析が進まず、注目されませんでした。しかし2010年代以降の研究で、UCBと同等以上の理論的保証を持つことが示され、再評価されています。
Thompson Samplingは、各アームの報酬分布に対する事後分布からサンプリングして行動を決定するベイズ的手法です。
ベルヌーイバンディット（報酬が0か1）の場合:
- 各アーム $a$ の事前分布を $\text{Beta}(\alpha_a, \beta_a)$ とする（初期: $\alpha_a = \beta_a = 1$、一様分布に相当）
- 各アームの事後分布からサンプルを引く: $\theta_a \sim \text{Beta}(\alpha_a, \beta_a)$
- 最もサンプル値が高いアームを選ぶ: $a_t = \arg\max_a \theta_a$（「一番当たりが出そう」なアームを選ぶ）
- 報酬 $r_t$ を観測し、事後分布を更新: – $r_t = 1$ なら $\alpha_{a_t} \leftarrow \alpha_{a_t} + 1$ – $r_t = 0$ なら $\beta_{a_t} \leftarrow \beta_{a_t} + 1$
UCBとの比較
Thompson Samplingの美しさは、探索と活用のバランスが自動的に調整される点にあります。UCBは信頼区間の上界を使って「楽観的に」行動しますが、Thompson Samplingは事後分布からの確率的なサンプリングで自然に探索と活用のバランスを取ります。
- 不確かなアーム: 事後分布が広い（分散が大きい）ため、たまに高いサンプル値が出る → 自然に探索が促進される
- よく知られたアーム: 事後分布が狭い（分散が小さい）ため、真の値付近のサンプルが安定して出る → 正確な活用が行われる
- 真に良いアーム: データが集まるにつれて事後分布の平均が高くなり、選択される確率が増える → 活用に移行する
理論的にはUCBとThompson Samplingは同じオーダーの後悔を達成しますが、実験的にはThompson Samplingの方がわずかに優れることが多いです。Thompson Samplingが実験的に強い理由の1つは、事後分布の「形状」を活用している点にあります。UCBは信頼区間の上端のみを見ますが、Thompson Samplingは分布全体からサンプリングするため、より豊かな不確かさの情報を活用しています。
ここまではバンディット問題という比較的単純な設定での探索手法を見てきました。しかし、実際の深層強化学習では状態空間・行動空間が高次元であり、上記の手法をそのまま適用するのは困難です。次に、深層強化学習特有の探索手法を見ていきましょう。
深層強化学習での探索
epsilon-greedyの限界
バンディット問題では上記の手法が有効ですが、深層強化学習（DQN等）の高次元の状態空間・行動空間では、epsilon-greedyのランダム探索は非効率です。
例えば100次元の連続行動空間で、ランダムな行動が有意義な状態遷移を引き起こす確率は非常に低くなります。ロボットの関節を制御する場面を想像してみてください。10個の関節の角度をそれぞれランダムに動かしても、意味のある動作（例えばコップを掴む）は偶然には生まれません。高次元空間での「ランダム」は、人間が想像するよりもはるかに非効率なのです。この問題を解決するために、ネットワークの構造自体に探索のメカニズムを組み込む手法が提案されています。
Noisy Networks
Fortunato et al.（2018）は、ニューラルネットワークの重みにパラメトリックなノイズを追加するNoisyNetを提案しました。
$$ y = (\bm{W} + \sigma_w \odot \bm{\epsilon}_w) \bm{x} + (\bm{b} + \sigma_b \odot \bm{\epsilon}_b) $$
ノイズのパラメータ $\sigma_w, \sigma_b$ は学習によって自動的に調整されます。探索が不要になった次元ではノイズが小さくなり、探索が必要な次元ではノイズが大きく残ります。
NoisyNetの重要な利点は、epsilon-greedyのように「探索か活用か」を二者択一で切り替えるのではなく、行動空間のどの次元でどの程度の探索が必要かを学習データから自動的に判断する点です。これにより、状態に依存した適応的な探索が可能になります。
内発的動機づけ
前の記事でも触れましたが、好奇心に基づく内発的報酬は深層強化学習の探索に有効です。
$$ R_t = R_t^{\text{ext}} + \beta R_t^{\text{int}} $$
外部報酬 $R^{\text{ext}}$ がスパースでも、内発的報酬 $R^{\text{int}}$ が探索を駆動します。
内発的動機づけは人間の心理学から着想を得た手法です。子供が「なぜ？」と繰り返し質問するように、「まだよくわからないこと」に対する好奇心が自然に探索を促進します。代表的な手法としては、予測誤差に基づくICM（Intrinsic Curiosity Module）やRND（Random Network Distillation）があり、Montezuma’s Revengeのようなスパース報酬のゲームで大幅な性能向上が報告されています。
ここまでで理論的な背景を一通り学びました。次に、これらの探索戦略をPythonで実装し、実験で比較してみましょう。
Pythonでの比較実験
4つの探索戦略の比較
ここでは10本のアーム（$K=10$）を持つバンディット問題で、epsilon-greedy（$\epsilon=0.1$ と $\epsilon=0.01$）、UCB、ボルツマン探索、Thompson Samplingの5つの戦略を比較します。各アームの真の報酬は標準正規分布からサンプリングし、200回の試行を平均化して信頼性の高い結果を得ます。
import numpy as np
import matplotlib.pyplot as plt
class BanditEnv:
"""多腕バンディット環境"""
def __init__(self, k=10):
self.k = k
self.means = np.random.randn(k)
self.optimal = np.argmax(self.means)
def pull(self, arm):
return self.means[arm] + np.random.randn()
def run_epsilon_greedy(env, T, epsilon):
"""epsilon-greedy"""
Q = np.zeros(env.k)
N = np.zeros(env.k)
rewards = np.zeros(T)
optimal_actions = np.zeros(T)
for t in range(T):
if np.random.rand() < epsilon:
a = np.random.randint(env.k)
else:
a = np.argmax(Q)
r = env.pull(a)
N[a] += 1
Q[a] += (r - Q[a]) / N[a]
rewards[t] = r
optimal_actions[t] = (a == env.optimal)
return rewards, optimal_actions
def run_ucb(env, T, c=2.0):
"""UCB1"""
Q = np.zeros(env.k)
N = np.zeros(env.k)
rewards = np.zeros(T)
optimal_actions = np.zeros(T)
for t in range(T):
if t < env.k:
a = t # 各アームを1回ずつ
else:
ucb_values = Q + c * np.sqrt(np.log(t) / (N + 1e-10))
a = np.argmax(ucb_values)
r = env.pull(a)
N[a] += 1
Q[a] += (r - Q[a]) / N[a]
rewards[t] = r
optimal_actions[t] = (a == env.optimal)
return rewards, optimal_actions
def run_boltzmann(env, T, tau=1.0):
"""ボルツマン探索"""
Q = np.zeros(env.k)
N = np.zeros(env.k)
rewards = np.zeros(T)
optimal_actions = np.zeros(T)
for t in range(T):
exp_q = np.exp(Q / max(tau, 0.01))
probs = exp_q / exp_q.sum()
a = np.random.choice(env.k, p=probs)
r = env.pull(a)
N[a] += 1
Q[a] += (r - Q[a]) / N[a]
rewards[t] = r
optimal_actions[t] = (a == env.optimal)
return rewards, optimal_actions
def run_thompson(env, T):
"""Thompson Sampling（正規分布版）"""
mu = np.zeros(env.k)
sigma = np.ones(env.k) * 10.0
N = np.zeros(env.k)
rewards = np.zeros(T)
optimal_actions = np.zeros(T)
for t in range(T):
samples = np.random.randn(env.k) * sigma + mu
a = np.argmax(samples)
r = env.pull(a)
N[a] += 1
mu[a] += (r - mu[a]) / N[a]
sigma[a] = 1.0 / np.sqrt(N[a] + 1)
rewards[t] = r
optimal_actions[t] = (a == env.optimal)
return rewards, optimal_actions
# 複数回の試行で平均化
n_runs = 200
T = 1000
k = 10
all_rewards = {name: np.zeros((n_runs, T)) for name in
["eps-greedy(0.1)", "eps-greedy(0.01)", "UCB(c=2)",
"Boltzmann(tau=0.5)", "Thompson"]}
all_optimal = {name: np.zeros((n_runs, T)) for name in all_rewards}
for run in range(n_runs):
env = BanditEnv(k)
np.random.seed(run)
r, o = run_epsilon_greedy(env, T, 0.1)
all_rewards["eps-greedy(0.1)"][run] = r
all_optimal["eps-greedy(0.1)"][run] = o
r, o = run_epsilon_greedy(env, T, 0.01)
all_rewards["eps-greedy(0.01)"][run] = r
all_optimal["eps-greedy(0.01)"][run] = o
r, o = run_ucb(env, T, c=2.0)
all_rewards["UCB(c=2)"][run] = r
all_optimal["UCB(c=2)"][run] = o
r, o = run_boltzmann(env, T, tau=0.5)
all_rewards["Boltzmann(tau=0.5)"][run] = r
all_optimal["Boltzmann(tau=0.5)"][run] = o
r, o = run_thompson(env, T)
all_rewards["Thompson"][run] = r
all_optimal["Thompson"][run] = o
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
colors = ["#e41a1c", "#ff7f00", "#377eb8", "#4daf4a", "#984ea3"]
names = list(all_rewards.keys())
# (a) 平均報酬
ax = axes[0]
for name, color in zip(names, colors):
mean_reward = all_rewards[name].mean(axis=0)
ax.plot(mean_reward, color=color, linewidth=1, alpha=0.8, label=name)
ax.set_xlabel("Step", fontsize=12)
ax.set_ylabel("Average Reward", fontsize=12)
ax.set_title("Average Reward over Time", fontsize=13)
ax.legend(fontsize=9, loc="lower right")
ax.grid(True, alpha=0.3)
# (b) 最適行動の選択率
ax = axes[1]
for name, color in zip(names, colors):
opt_rate = all_optimal[name].mean(axis=0)
# 移動平均
window = 20
opt_smooth = np.convolve(opt_rate, np.ones(window)/window, mode='valid')
ax.plot(opt_smooth, color=color, linewidth=1.5, alpha=0.8, label=name)
ax.set_xlabel("Step", fontsize=12)
ax.set_ylabel("Optimal Action Rate", fontsize=12)
ax.set_title("Optimal Action Selection Rate", fontsize=13)
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)
# (c) 累積後悔
ax = axes[2]
for name, color in zip(names, colors):
mean_reward = all_rewards[name].mean(axis=0)
# 後悔 = 最適報酬 - 実際の報酬
regret = np.cumsum(np.max(all_rewards[name].mean(axis=0)) - mean_reward)
ax.plot(regret, color=color, linewidth=1.5, alpha=0.8, label=name)
ax.set_xlabel("Step", fontsize=12)
ax.set_ylabel("Cumulative Regret", fontsize=12)
ax.set_title("Cumulative Regret", fontsize=13)
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig("exploration_exploitation.png", dpi=150, bbox_inches="tight")
plt.show()
このグラフから、各探索戦略の特性が明確に読み取れます。
-
左図（平均報酬）: Thompson SamplingとUCBが最も速く高い報酬に到達し、epsilon-greedy(0.1)は長期的にも探索の「コスト」が残っています。epsilon-greedy(0.01)は初期の探索が少なく立ち上がりが遅いですが、長期的には活用が多いため報酬が安定します
-
中央図（最適行動選択率）: Thompson SamplingとUCBが最も速く最適行動の選択率を上げています。epsilon-greedy(0.1)は上限が約90%（10%はランダム探索）で頭打ちになる一方、UCBとThompson Samplingは探索が自動的に減衰するため、選択率が高くなり続けます
-
右図（累積後悔）: epsilon-greedy(0.1)の後悔は線形に増加（一定の探索コスト）しているのに対し、UCBとThompson Samplingの後悔の増加は対数的に遅くなっています。これは理論的な保証と一致しており、UCBとThompson Samplingが長期的に最適に近い行動を学習していることを示しています
実験結果をまとめると、探索戦略の選択は問題の性質やドメインに依存しますが、理論的保証と実験性能の両面でThompson SamplingとUCBが推奨されることがわかります。epsilon-greedyはベースラインや初期の実験に有用ですが、本番環境で高い性能を求めるのであれば、不確かさの構造を積極的に活用する手法を選ぶべきです。
まとめ
本記事では、探索と活用のトレードオフの理論と実装について解説しました。
- 探索と活用のトレードオフは強化学習の根本的なジレンマであり、後悔（regret）で定量的に評価される
- epsilon-greedyは最もシンプルで実装が容易だが、固定epsilonでは後悔が線形に増加する。減衰epsilonで対数オーダーに改善可能
- UCBは信頼上界に基づく楽観主義で、$O(\log T)$ の後悔を保証する
- Thompson Samplingはベイズ的なアプローチで、事後分布からの確率的なサンプリングにより自然に探索と活用のバランスを取り、実験的にはUCBを上回ることが多い
- 深層強化学習ではNoisyNetや内発的動機づけがepsilon-greedyの限界を補う
探索と活用のトレードオフは、強化学習に限らず、不確かさのもとでの意思決定全般に関わる普遍的なテーマです。本記事で学んだ理論は、A/Bテストの最適な停止条件の決定、ハイパーパラメータ探索の効率化、推薦システムの「コールドスタート問題」の解決など、幅広い場面で応用できます。
次のステップとして、以下の記事も参考にしてください。
- 多腕バンディット問題 — UCBとThompson Samplingの詳細
- 報酬設計の理論と実践 — 報酬関数の設計原則
- DQNの理論と実装 — 深層強化学習での探索