マルチアームバンディット問題とは

マルチアームバンディット問題は、限られた試行回数の中で、報酬が得られる確率が未知である複数の選択肢（スロットマシンのアーム）から一つを選び続ける際、過去の経験に基づいて最も期待値が高いと思われる選択肢を選ぶこと（活用）と、まだ十分に試していない選択肢の情報を集めること（探索）のバランスを最適化し、得られる報酬の合計を最大化することを目指す意思決定の枠組みのことです。

これは、強化学習における最も基本的な問題設定の一つであり、ウェブサイトのABテストの効率化や広告配信、臨床試験などの実社会における動的な最適化に広く応用されています。

探索と活用のトレードオフ

マルチアームバンディット問題の本質は、探索（Exploration）と活用（Exploitation）のトレードオフをどのように解決するかという点にあります。

1. 探索（Exploration）

より優れた選択肢を見つけるために、現在の知識では最善とは限らないアームを試す行為です。短期的には損失を生む可能性がありますが、長期的に最大の報酬を得るための情報を収集する役割を担います。

2. 活用（Exploitation）

これまでの試行結果から、現時点で最も高い報酬が期待できるアームを選択する行為です。短期的には確実に報酬を得られますが、実は他にさらに優れたアームが存在していた場合、その機会を逃し続けることになります。

代表的なアルゴリズム

この問題に対し、総報酬を最大化（あるいは後悔と呼ばれる損失を最小化）するために考案された主なアルゴリズムを解説します。

1. ε-greedy法（イプシロン・グリーディ法）

最も単純かつ強力な手法の一つです。あらかじめ設定した確率 ε（例：0.1）の割合でランダムに探索を行い、残りの 1-ε の割合で現時点の最善策を選択します。

2. UCB策（Upper Confidence Bound策）

各アームの期待値だけでなく、試行回数の少なさからくる不確実性（不確かさ）を考慮する手法です。期待値に「自信のなさ」を表す項を加えた上限値を算出し、その値が最大のアームを選択します。

ここで、$\bar{X}_a$ はアーム $a$ の平均報酬、$t$ は全試行回数、$n_a$ はアーム $a$ を選択した回数を示します。試行回数が少ないアームほど第2項が大きくなり、優先的に探索される仕組みです。

3. トンプソン抽出（Thompson Sampling）

各アームの報酬確率を確率分布（ベイズ統計）として推定し、その分布からサンプリングされた値が最大のアームを選択する手法です。実務において非常に高いパフォーマンスを発揮することが知られています。

実社会における応用事例

マルチアームバンディット問題の考え方は、従来の静的なテスト手法を置き換える形で普及しています。

1. ウェブサイトのABテストの最適化

従来のABテストでは、一定期間テストを行い、その後勝者を固定します。しかし、バンディットアルゴリズムを用いることで、テスト中であっても有望なデザインへのトラフィック配分を動的に増やし、テストに伴う機会損失を最小限に抑えることが可能です。

2. 広告配信システム

クリック率（CTR）が未知の新しい広告と、実績のある既存の広告を適切に混ぜて配信し、全体のクリック数を最大化するために利用されます。

3. レコメンデーションエンジン

ユーザーが好む可能性が高いコンテンツを提示しつつ、新しいジャンルの興味を掘り起こすための探索を自動的に行います。

評価指標：リグレット（後悔）

マルチアームバンディットアルゴリズムの性能は、リグレット（Regret）という指標で評価されます。リグレットは、理想的な（すべてを知っている）意思決定者が得られたであろう報酬と、実際に選択したアルゴリズムが得た報酬の差を指します。

優れたアルゴリズムは、試行回数 $T$ が増えるにつれて、このリグレットの増加率を対数オーダー（$\ln T$）に抑えることが理論的に証明されています。

関連用語

お問い合わせ

システム開発・アプリ開発に関するご相談がございましたら、APPSWINGBYまでお気軽にご連絡ください。