← 一覧へ
AI・データ
#멀티암드밴딧#탐험활용#톰슨샘플링#UCB#온라인학습
最終更新 · 2026-11-19

多腕バンディット(Multi-Armed Bandit)と探索・活用の最適配分

1. 概要

定義: 多腕バンディット(Multi-Armed Bandit, MAB)とは、報酬分布が未知の複数の選択肢(arm)の中から各時点で一つを選択してその結果(報酬)を観測する過程を繰り返しながら、探索(exploration、未知の選択肢の情報収集)と活用(exploitation、現時点で最良に見える選択肢の選択)の均衡を通じて累積報酬を最大化(=累積後悔を最小化)する逐次的意思決定(sequential decision making)の問題であり、かつアルゴリズム群である。

この名は、複数の腕(arm)を持つスロットマシン(one-armed bandit、片腕の盗賊)の前に立つ賭博師の状況に由来する。各腕は引くたびに異なる(しかし未知の)確率で賞金を与え、賭博師は限られた回数の中で、どの腕が良いかを知るために要する費用と、良いと判断された腕から賞金を得る利得との間で絶えず天秤にかける。この抽象化がデジタル時代に至って、広告クリエイティブの選択、推薦アルゴリズム、価格決定、臨床試験の患者割付など、「限られた機会の中で不確実な代替案から反復選択する」必要のあるほぼすべての問題の数学的骨格となった。

MABの本質は探索・活用のジレンマ(exploration-exploitation dilemma)である。活用のみを行えば初期の運の良い(あるいは運の悪い)観測に囚われ、実際にはより良い選択肢を永遠に見逃しかねず、探索のみを行えばすでに劣ると判明した選択肢に資源を浪費する。良いバンディットアルゴリズムは「十分に不確実な選択肢はより頻繁に試すが、証拠が蓄積して劣後が明らかになれば素早く損切りする」という原理を数学的に実装する。このとき性能の尺度は後悔(regret) — 各時点で常に最適選択肢を選んだときの期待報酬と、実際にアルゴリズムが得た報酬との累積差 — であり、良いアルゴリズムほど時間Tに対して後悔が緩やかに(理論的にO(log T))増加する。

登場背景と必要性

従来のA/Bテストはユーザを固定比率(例: 50:50)に分け、一定期間の最後まで劣後案にもトラフィックを流したうえで、終了時点に統計的に勝者を判定する。この方式は因果効果を明確に推定するには卓越するが、実験期間を通じて明らかに悪い案に半数のユーザを曝露する機会費用(実験後悔、experimentation regret)を避けられない。特にクリエイティブが数十・数百個であったり、トレンドが速くクリエイティブの寿命が短かったり(ニュース見出し、ファッション商品)、機会が希少な(臨床試験)状況では、「最後まで公平に分ける」固定実験は非効率である。

MABは実験しながら同時に学習結果を即座に配分に反映することで、この損失を減らす。良く見える選択肢に次第に多くのトラフィックを流すため、実験自体の累積損失が小さく、「最適案への収束」と「損失最小化」を同時に達成する。また選択肢を途中で追加・除去できるため、動的環境に柔軟である。このため推薦・広告・個人化のように代替案が多く速く変化する領域で、MABは固定A/Bテストを補完または代替する中核技法として定着した。

技術士の観点からの問題定義

論述答案でMABを「良いものをより頻繁に選ぶアルゴリズム」とだけ書けば失敗である。核心となる軸は、① 探索・活用のジレンマを後悔(regret)最小化として定式化する観点、② ε-greedy・UCB・トンプソンサンプリングの原理的差異と収束保証、③ 文脈(context)・非定常性(non-stationarity)・遅延報酬といった現実的制約への拡張、④ A/Bテストとの役割分担および統計的推論のトレードオフを、定量的・構造的に展開することである。

2. 全体構造と中核構成要素

MABは「選択 → 報酬観測 → 信念更新 → 次の選択」が連なる一つのオンライン学習ループである。下の構造図は、エージェントと環境の相互作用、そして探索・活用の方策がどこで作動するかを示す。

flowchart TD
  P["方策(Policy): 探索-活用均衡規則"] --> SEL["Arm選択(a_t)"]
  SEL --> ENV["環境(Environment): 報酬分布は未知"]
  ENV --> R["報酬観測(r_t)"]
  R --> UPD["推定更新(平均・不確実性)"]
  UPD --> P
  UPD --> REG["後悔(Regret)累積測定"]
  CTX["文脈(Context): ユーザ・時間特性"] -.-> P
  REG -.->|"性能評価"| EVAL["オフライン評価・IPS/DR"]

バンディット問題の構成要素は四つである。第一に選択肢集合(arms)は、広告クリエイティブ・推薦商品・UI変形のように、エージェントが選べる代替案である。第二に報酬(reward)は各選択の結果であり、クリック有無(ベルヌーイ)、滞在時間・売上(連続値)のように問題によって分布が異なる。第三に方策(policy)はこれまでの観測に基づき次の選択肢を決める規則であり、ここに探索・活用の戦略が織り込まれる。第四に後悔(regret)は性能指標で、事後的に判明した最適選択肢に対する損失の累積である。

A. 探索・活用のジレンマと後悔

探索・活用のジレンマはMABのすべてを貫く原理である。各選択肢には現時点までの推定平均報酬と、その推定の不確実性(標本が少ないほど大きい)がある。活用は推定平均が高い選択肢を、探索は不確実性が大きい(まだ試行が少ない)選択肢を好む。核心的洞察は「不確実性が大きい選択肢は実際には最良かもしれないため、その可能性を排除する前に数回さらに試す価値がある」ということである。

これを定量化したものが後悔である。選択肢iの期待報酬をμ_i、最適選択肢をμとすると、T回選択後の期待後悔はΣ(μ − μ_{a_t})と定義される。素朴なε-greedy(ε固定)は最後までε比率で任意の選択肢を選ぶため後悔が時間に線形(O(T))で増加するが、UCB・トンプソンサンプリングのように不確実性を精緻に扱うアルゴリズムは劣後選択肢を次第に選ばなくなり、後悔を対数(O(log T))に抑制する。例えばクリック率10%・5%の二つのクリエイティブを100万回露出するとき、固定50:50実験は劣後クリエイティブで約2万5千クリックを失うが、良いバンディットは数千クリックの損失で収束する。

B. 推定と信念更新

バンディットの心臓は、各選択肢に対する信念(belief)をデータで更新する過程である。最も単純には選択肢別の標本平均報酬を保持し、増分平均公式 Q ← Q + (r − Q)/n で各観測ごとにO(1)で更新する。非定常環境では過去を忘れるために固定学習率αで指数加重移動平均 Q ← Q + α(r − Q) を用いる。

より精緻な手法は、平均のみならず不確実性全体を分布として保持することである。ベルヌーイ報酬(クリック/非クリック)の場合、共役事前分布であるベータ(Beta)分布を各選択肢に置き、成功・失敗をα・βのパラメータに累積すれば事後分布が閉じた形で更新される。このように「点推定」ではなく「分布」を保持すれば、後述するトンプソンサンプリングのように不確実性を自然に探索に活用できる。

C. 文脈(Context)と評価の問題

現実では「どのクリエイティブが良いか」がユーザによって異なる。20代女性に良い広告と50代男性に良い広告が異なるということである。これを反映したものが文脈的バンディット(contextual bandit)で、各時点でユーザ・時間・機器の特性ベクトルx_tを受け取り、「この文脈における各選択肢の期待報酬」を線形モデル・ニューラルネットで推定し、その上に探索規則を載せる(LinUCB、ニューラルバンディットなど)。文脈のない古典的バンディットが「全体平均の最適案」を探すのに対し、文脈的バンディットは個人化された最適案を探す。

もう一つの難題はオフライン評価である。バンディットは選択しなかった選択肢の報酬を観測できない(反事実、counterfactual)ため、過去のログのみで新しい方策を評価しにくい。このために逆傾向重み付け(IPS, Inverse Propensity Scoring)・二重頑健(Doubly Robust)推定量が用いられ、ログを残す際に各選択の確率(propensity)を併せて記録してこそ、偏りのないオフライン評価が可能になる。この設計は実務でバンディットの信頼性を左右する核心的決定である。

3. 主要アルゴリズムと動作手順

代表的アルゴリズムは、探索をどのように注入するかで区別される。下のプロセス図は、一度の意思決定サイクルで三系統がどのように分岐するかを示す。

flowchart TD
  START["ラウンドt開始"] --> HOW{"探索注入方式"}
  HOW -->|"無作為混合"| EG["ε-greedy: 確率εで無作為、1-εで最善"]
  HOW -->|"楽観的ボーナス"| UCB["UCB: 平均+信頼上限ボーナス最大を選択"]
  HOW -->|"事後分布標本抽出"| TS["トンプソンサンプリング: 各arm事後分布から標本抽出し最大を選択"]
  EG --> ACT["選択実行、報酬観測"]
  UCB --> ACT
  TS --> ACT
  ACT --> UP["推定・事後分布更新"]
  UP --> START

A. ε-greedy — 最も単純な探索

ε-greedyは確率εで選択肢を無作為に選び(探索)、1−εで現在の推定平均が最も高い選択肢を選ぶ(活用)。実装が一行で済むほど単純で直観的なため、産業標準のベースラインとして広く使われる。ただし二つの弱点がある。第一に、εが固定であれば十分に学習された後も常にεだけ損失を出すため後悔が線形に増加する。これを緩和するために時間に応じてεを減らすε-減少(decay)変形を用いる。第二に、探索が「完全に無作為」であるため、明らかに悪い選択肢と有望な選択肢を同じく試す非効率がある。

それでもε-greedyが実務で絶えず使われる理由は頑健性と説明可能性である。分布の仮定がほぼなく、非定常環境でもεだけの探索が常に保証され環境変化を見逃さない。Netflixが初期のアートワーク(サムネイル)個人化にε-greedy系統を広範に適用して視聴参加を引き上げた事例のように、「完璧な最適性」より「運用の単純さと安定性」が重要な現場では依然として第一候補である。

B. UCB — 不確実性に対する楽観

UCB(Upper Confidence Bound)は「不確実性の前では楽観せよ(optimism in the face of uncertainty)」という原理を実装する。各選択肢について推定平均に信頼上限ボーナス(観測が少ないほど大きい値、例: √(2 ln t / n_i))を加えた値を計算し、この和が最も大きい選択肢を選択する。試行の少ない選択肢はボーナスが大きく自然に選ばれ、多く試行され不確実性が減ればボーナスが小さくなり平均のみで競う。すなわち探索が無作為ではなく「情報価値が大きい方へ方向性をもって」起こる。

UCBの強みは理論的後悔保証(O(log T))が証明される点と、無作為性なく決定論的に動作し再現・デバッグが容易な点である。弱点はボーナス項が報酬分布の仮定(有界性など)に敏感で、選択肢が数千・数万個と多かったり文脈が高次元であったりするとき計算・調整の負担が大きいことである。文脈拡張であるLinUCBは線形モデルの共分散で信頼区間を計算し、ニュース推薦などで広く使われた。

C. トンプソンサンプリング — 事後分布から標本抽出

トンプソンサンプリング(Thompson Sampling)はベイズ的手法で、各選択肢の報酬に対する事後分布から一つずつ標本を抽出し、その標本値が最も大きい選択肢を選択する。ベルヌーイ報酬であれば各選択肢のベータ事後分布から成功率を抽出して比較する形である。不確実性の大きい選択肢は事後分布が広く時折大きな値が抽出されるため探索され、証拠が蓄積して分布が狭まれば劣後選択肢が抽出される確率が急減する。探索・活用が確率的に自然に均衡する。

実務でトンプソンサンプリングは平均後悔が小さく、遅延報酬・バッチ更新に頑健で、実装が意外に簡単なため最も好まれるアルゴリズムの一つである。Google・Microsoftなどが広告・推薦システムに幅広く適用し、数百個のクリエイティブを同時に扱うコンテンツ最適化でUCBより安定的だという報告が多い。ただし報酬モデルの事前分布・尤度を定義せねばならないため、非定型報酬にはモデリングの労力が必要である。

D. アルゴリズムの比較

三系統の差異は「探索をどこから引き出すか」で分かれる。下の表は核心的特性を比較するが、数値そのものよりなぜそのような差が生じるかが重要である。ε-greedyの線形後悔は「固定比率の無思考な探索」から、UCB・トンプソンの対数後悔は「不確実性に比例した方向性のある探索」から生じる。

区分 ε-greedy UCB トンプソンサンプリング
探索方式 確率εで無作為 信頼上限ボーナス(決定論) 事後分布標本抽出(確率的)
後悔次数 O(T)(固定ε) / 改善可能 O(log T) O(log T)
分布の仮定 ほぼなし 有界性など必要 事前・尤度の定義が必要
遅延・バッチ報酬 頑健 やや脆弱 頑健
実装難易度 極めて低い 低い 中程度
説明可能性 高い 高い 中程度(確率的)

4. 比較と適用事例

A. A/Bテストとの関係 — 代替ではなく役割分担

MABとA/Bテストはしばしば対立構図で紹介されるが、実際には目的の異なる相補的な道具である。A/Bテストはトラフィックを固定比率で最後まで維持し、明確な因果効果と信頼区間を得ることが目的である。一方MABは実験中の損失(後悔)を減らし最適案へ速く収束することが目的であるため、トラフィックが勝者へ集中した瞬間、「劣後案の効果量を精密に推定する」能力は落ちる。すなわちMABでは「BがAより正確に何%良かった」を事後に信頼区間で述べにくい。

したがって実務の原則は明確である。学習が目的(正確な効果推定・意思決定の根拠確保)ならA/Bテスト、収益最適化が目的(損失最小化・速い配分)ならMABを用いる。クリエイティブの寿命が短かったり(見出し、プロモーションバナー)、代替案が数十個以上であればMABが、中核機能の長期効果を厳密に検証せねばならなければA/Bテストが適する。両者を結合し「初期にA/Bで候補を絞った後MABで配分最適化する」ハイブリッドも多い。

B. 産業適用事例

実際の適用は広範である。デジタル広告では数十個の広告クリエイティブのうちクリック率の高いクリエイティブへ露出を漸増させるのにトンプソンサンプリング・UCBが標準的に使われる。一日数億インプレッション規模で1%のCTR改善が莫大な売上に直結するため、「劣後クリエイティブの損切り速度」が即ち収益である。ニュース・コンテンツ推薦では、ポータルがLinUCB系統の文脈的バンディットでユーザ別の記事配置を最適化しクリック率を有意に高めた公開事例がある。

臨床試験では、患者を倫理的により効果的な治療群へ次第に多く割り付ける反応適応割付(response-adaptive randomization)にバンディットの着想が使われる。患者一人一人が希少で倫理的費用が大きいため、「実験後悔最小化」というMABの目的が生命に直結する。そのほか動的価格決定(複数の価格帯を探索しながら売上極大化)、推薦システムのコールドスタート(新規商品の露出配分)、ハイパーパラメータ探索などでバンディットが活用される。

国内でもe-コマース・OTT・ポータルの個人化領域でバンディット適用が拡散している。例えば商品詳細ページのバナー・クーポンのクリエイティブを数十種準備しておきバンディットで露出を最適化すれば、固定A/Bテストのように「一度に二三個ずつ数週間検証する」ボトルネックなく、クリエイティブ・プール全体を実時間で天秤にかけられる。特にプロモーション・シーズン商品のように寿命の短いクリエイティブはA/Bテストが統計的有意性を確保する頃にはすでにシーズンが終わってしまうため、「学習しながら直ちに配分する」バンディットの利点が際立つ。逆に決済フロー変更のように元に戻しにくく長期影響を厳密に検証せねばならない変更は依然として固定実験が安全である点で、組織は二つの道具の意思決定基準(変更の可逆性・クリエイティブ寿命・効果推定の必要性)を事前に合意しておくべきである。

5. 深化 — 文脈・非定常性・強化学習への拡張と最新動向

MABはより一般的な逐次意思決定へ拡張され、その境界で最新研究が活発である。第一に、文脈的バンディットから深層ニューラルネット基盤(neural bandit)への拡張である。線形の仮定を離れ複雑なユーザ・クリエイティブの相互作用を学習しつつ探索を維持するために、ドロップアウト・アンサンブル・ベイジアンニューラルネットで不確実性を近似する技法が使われる。ただしニューラルネットの過信(overconfidence)により探索が早期崩壊する危険を管理せねばならない。

第二に、非定常バンディット(non-stationary bandit)である。ユーザの嗜好・トレンドが時間とともに変化する現実では過去データを無限に信頼してはならない。スライディングウィンドウUCB、割引(discounted)UCB、変化点検知結合技法などが「過去を適切に忘れながら」環境変化を追跡する。これはモデルドリフト監視とも接する。

第三に、強化学習(RL)との関係である。バンディットは「状態(state)がない、あるいは選択が次の状態に影響しない」特殊なRLと見なせる。選択が環境状態を変え報酬が遅延して累積すれば完全なRL(MDP)となり、バンディットの探索・活用の原理(UCB・トンプソン)はRLの探索戦略としてそのまま継承される。近年はLLM基盤の推薦・対話最適化で応答候補の選択をバンディットとしてモデル化したり、RLHFの報酬モデル探索にバンディット理論を接合する流れも現れている。第四に、広告・推薦プラットフォームのオフライン方策評価(OPE)の高度化により、IPS・DR・スイッチ推定量を通じて「ライブトラフィックなしで」新しいバンディット方策を安全に事前検証するMLOpsの慣行が定着しつつある。

6. 考慮事項および示唆点

MAB導入を技術士の観点から設計・評価する際は、次を均衡よく考慮せねばならない。

  • 目的適合性(学習 vs 収益)の判断: バンディットは損失最小化に強いが効果量の精密推定には弱い。「根拠に基づく意思決定」が必要な戦略的変更はA/Bテストで、「運用最適化」はバンディットで分けつつ、両アプローチをハイブリッドで編むポートフォリオ戦略が望ましい。

  • 統計的推論とのトレードオフ: トラフィックが勝者へ集中して生じる適応的データ(adaptive data)のため、単純平均・標準誤差が偏る。事後分析にはIPS・二重頑健推定、信頼性補正が必要であり、選択確率(propensity)のロギングが前提となる。この設計を欠けば「最適化はされたが説明・検証は不可能な」ブラックボックスとなる。

  • 非定常性と遅延報酬の管理: 報酬が遅く到着したり(購買転換の遅延)分布が変われば、素朴なバンディットは誤った選択肢へ集中する。ウィンドウ・割引・バッチ更新、遅延報酬に頑健なトンプソンサンプリングの選択など、環境特性に合わせたアルゴリズム・周期の設計が必要である。

  • 公平性・安全・ガードレール: 収益のみを極大化するバンディットが特定集団を体系的に不利に扱ったり(公平性)、極端なクリエイティブへ集中してブランド・ユーザ体験を害しうる。最小露出保証(各選択肢への底トラフィック)、ガードレール指標の監視、探索上限の設定で安全装置を置くべきである。

  • 運用の複雑度と組織の能力: 文脈的・ニューラルバンディットは特徴量パイプライン・実時間推論・オフライン評価体系を要求する。ε-greedyのような単純な技法から始めて漸進的に高度化し、実験プラットフォーム・MLOps・監視と統合する成熟度ロードマップが成否を左右する。

参考資料


一言まとめ: 多腕バンディットは、報酬が不確実な複数の選択肢の間で探索と活用の均衡により累積後悔を最小化する逐次意思決定技法であり、ε-greedy・UCB・トンプソンサンプリングが代表的アルゴリズムで、損失を減らしつつ最適案へ速く収束せねばならない広告・推薦・価格・臨床の領域でA/Bテストを補完する。