## 定義 多腕バンディット問題(Multi-Armed Bandit Problem)とは、得られる報酬の期待値(母平均)が異なる複数のアーム(選択肢。語源はスロットマシンのレバー)の中から、試行を重ねながらどのアームを選択すれば累計報酬を最大化できるかを解く問題である。各アームの報酬は固有の確率分布に従って生成されると仮定し、試行(あるアームを選択して報酬を得る行為)を通じて得られる標本から、母平均を確率密度関数(事後分布)として推定する。標本平均は試行回数が増えるほど母平均に収束する(大数の法則)が、試行回数が少ないと標本平均は母平均から大きく外れうるため、単純に標本平均が最大のアームを選び続ける戦略は最適ではない。この問題を解く鍵は、母平均が不確かなアームを試す「探索」と、母平均が大きいと見込まれるアームを選ぶ「活用」のバランスを取ることにあり、これを[[探索と活用のトレードオフ]]と呼ぶ。理論的な性能評価には、最適なアームを選ばなかったことによる機会損失であるRegretの最小化が用いられる。(Source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] §11.1) コンテキスト(文脈。ユーザーの年齢・職業・行動履歴等)に応じて最適なアームを選ぶ拡張を文脈付き多腕バンディット(Contextual Multi-Armed Bandit)と呼ぶ。 ## 代表的な方策 母平均の不確実性を評価値に取り込む方法として、以下の方策がある。 - **Bayesian-UCB**: 各アームの母平均の事後分布(ベルヌーイ試行ではベータ分布)における信用区間の上限(例: 95パーセンタイル値)を評価値とし、楽観的に評価する。決定的なアルゴリズム。 - **UCB1(Upper Confidence Bound version 1)**: 標本平均に「全アームを引いた回数の対数をそのアームを引いた回数で割った項の平方根」を加えた値を評価値とする。理論的な性能証明を持つが、アーム間の母平均の差が小さいと収束に長い時間がかかりうる。決定的なアルゴリズム。 - **Softmax法**: 標本平均をアームの選択確率に変換する(温度パラメータで確率分布の鋭さを制御)。温度を徐々に下げるアニーリング(焼きなまし)を併用できる。確率的なアルゴリズム。 - **Thompson Sampling(TS)法**: あるアームの事後分布から乱数を1つ生成し、その乱数が最大のアームを選択する。調整パラメータがほとんどないにもかかわらず経験的に良好な性能を示し、近年は理論的な性能証明もなされている。確率的なアルゴリズム。 Bayesian-UCB・UCB1は試行のたびに即座に報酬が返ることを前提とする決定的で逐次的なアルゴリズムであり、バッチ処理や並列化、報酬観測に遅延がある実環境には向かない。Softmax法・TS法のような確率的アルゴリズムはこの制約を持たない。文脈付き多腕バンディットは、ブートストラップ法で複数の回帰予測器を学習し、予測値の分散を不確実性の推定として使うことで、点推定しかできない回帰モデルにもTS法を適用できる。(Source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] §11.4-§11.9) ### モデル選択への応用(『機械学習システムデザイン』9章) 9章はバンディットアルゴリズムを、実運用中の複数モデルのうちどれを本番採用すべきかを判断する実環境でのテスト手法として位置づける。A/Bテストがステートレス(各モデルの現時点のパフォーマンスを知らなくてもトラフィックを振り分けられる)であるのに対し、バンディットはステートフルであり、モデルにリクエストを振り分ける前にすべてのモデルの現状のパフォーマンスを計算しておく必要があるとする。適用には、(1) モデルがオンライン予測できること、(2) 予測の良し悪しに関するフィードバックが得られること、(3) フィードバックを収集し各モデルの現時点のパフォーマンスに基づいてトラフィックを振り分ける仕組みがあること、の3条件が要る。ε-グリーディ法(一定確率で最高パフォーマンスのモデルへ、残りをランダムに振り分ける)、トンプソンサンプリング、UCB(不確かなときは楽観的にの原理に基づき上限信頼限界が最も高いものを選ぶ)を代表的な探索アルゴリズムとして挙げる。Google の Greg Rafferty による実験では、A/B テストで95%の信頼区間を得るには63万個超のサンプルが必要だったのに対し、トンプソンサンプリングは1万2千個未満のサンプルで他のモデルより5%優れたモデルを導き出せた。ただしバンディットはペイオフの計算・追跡が必要なためA/Bテストより実装難易度が高く、一部の大手テック企業を除けば広くは普及していないとする。(Source: [[@2023__OReillyJapan__機械学習システムデザイン - Chapter 9 実現場での継続学習とテスト]] §9.2.5) 9章はさらに、モデル評価のバンディット(各モデルのペイアウトを決定する)と区別して、文脈バンディット(contextual bandit)を「各アクション(表示する商品や広告)のペイアウトを決定する探索戦略」と定義する。これは1,000個の商品をお勧めするレコメンドシステムであれば1,000本の多腕バンディット問題(ベスト10の腕を選ぶ)とみなせ、表示されなかった商品はフィードバックが得られない「部分的フィードバック(バンディットフィードバック)」問題として扱われる。文脈バンディットはワンショットな強化学習問題とも呼ばれ、Twitter・Googleの報告ではモデルのパフォーマンスを大幅に向上させることが分かっているが、探索戦略がモデルアーキテクチャーに依存するためユースケース間での汎用性が乏しいとされる。(Source: [[@2023__OReillyJapan__機械学習システムデザイン - Chapter 9 実現場での継続学習とテスト]] §9.2.5.1) ## 横断的知見 - **9章の「文脈バンディット」は、本ページの別名(alias)にある「文脈付き多腕バンディット」と同じ日本語表記でありながら、11章とは異なる対象を指す**: 11章由来の定義(既出、コンテキストに応じて最適なアームを選ぶ拡張)は、あくまで多腕バンディットの一般化としての「文脈付き」であり、アーム(モデル・選択肢)そのものの選択にコンテキストを使う。これに対し9章§9.2.5.1が定義する文脈バンディットは、モデル評価のバンディット(どのモデルを採用するか)とは意図的に区別し、「各アクション(表示する商品や広告)のペイアウトを決定する探索戦略」を指す——アームに相当するのが「モデル」ではなく「アクション(表示する商品)」である点が異なる。9章自身も「モデルを評価するバンディットのことを文脈バンディットと呼ぶ人もいるが、混乱を招かないよう本書ではアクションのペイアウトを決定する探索戦略のことを指して文脈バンディットと呼ぶ」と明示的に注記しており、同じ用語が文献によって異なる対象を指しうることを著者自身が認識している。11章・9章のいずれの意味で使われているかは、文脈(アームが「モデル」か「表示コンテンツ」か)で判別する必要がある。(Source: [[@2023__OReillyJapan__機械学習システムデザイン - Chapter 9 実現場での継続学習とテスト]] §9.2.5.1, [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] §11.1) - **9章のGoogle実験(A/Bテスト63万サンプル対トンプソンサンプリング1万2千サンプル未満)は、11章がA/Bテストをバンディットの「探索と活用が時間的に完全に分離された静的な2段階の割当方式」と位置づける理論的主張([[A-Bテスト]]参照)に、具体的な定量データを与える**: [[A-Bテスト]]が集約する11章の横断的知見は、A/Bテストがバンディットの特殊ケースであり、動的割当への一般化がバンディットであると理論的に位置づけるが、具体的にどの程度データ効率が改善するかの数値までは示さない。9章§9.2.5のGoogle Greg Raffertyの実験(A/Bテスト63万サンプル超 対 トンプソンサンプリング1万2千未満で5%優れたモデルを検出)は、この理論的な一般化が実務でもたらす効果を50倍以上のサンプル効率として定量化しており、11章の理論と9章の実測値が相互に補強し合う。(Source: [[@2023__OReillyJapan__機械学習システムデザイン - Chapter 9 実現場での継続学習とテスト]] §9.2.5, [[A-Bテスト]]) - **9章が明示するε-グリーディ法は、11章が意図的に解説を省いた探索戦略であり、両ソースの記述範囲は互いに補完する**: 11章は脚注でε-greedy法の解説を意図的に省いたと明記する(既出、未解決の問い参照)。9章§9.2.5のコラム「バンディットアルゴリズム」はこれと対照的に、ε-グリーディ法を「最もシンプルな探索アルゴリズム」として具体的な数値例(ε=0.9なら90%の時間は最高パフォーマンスのモデルへ、残り10%はランダムに振り分ける)つきで解説しており、11章が空白にした部分を9章が埋める形になっている。ただし9章もトンプソンサンプリング・UCBを「最も一般的な探索アルゴリズム」と位置づけており、ε-グリーディ法自体を主要な選択肢として推奨しているわけではない。(Source: [[@2023__OReillyJapan__機械学習システムデザイン - Chapter 9 実現場での継続学習とテスト]] §9.2.5, [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] §11.1) 当初(11章・12章の2ソースのみ)は本書内の既存concept 3件との接続にとどまっていたが、以下のとおり9章の追加により他書との横断的知見も蓄積した。[[学習問題設定の分類]]は「訓練データが網羅的かサンプリングか」「ワンショットか逐次的か」「フィードバックが教師的か評価的か」という3軸で多腕バンディット問題(バンデッド問題)を「サンプリング・ワンショット・評価的」に分類し、[[強化学習]](サンプリング・逐次的・評価的)との違いをワンショット/逐次的の軸のみに切り分けていた。本ページはこのワンショット性が持つ意味を、Bayesian-UCB・UCB1・Softmax法・TS法という具体的なアルゴリズムの水準で裏づける。すなわち、多腕バンディットのアーム選択は各試行が独立(前の試行が次の試行の状態遷移を引き起こさない)であるため、事後分布の更新だけを状態として扱えばよく、強化学習で必要になる状態遷移のモデル化(価値関数・方策のブートストラップ更新)を必要としない。この対比は今後、強化学習側の具体的手法(SARSA・Q学習等)とバンディットの方策とを同じ粒度で突き合わせる際に精査する。また[[A-Bテスト]]・[[Uplift Modeling]]は、いずれも本概念のバンディット・文脈付きバンディットの特殊ケース(100%ランダム配信からある時点で最適なアームへ全配信を切り替える方策)と位置づけられており、この関係は[[探索と活用のトレードオフ]]の横断的知見で扱う。 - **オンライン広告配信の教科書(12章)は、11章の理論的なバンディット問題を「Logged Bandit Feedback」という具体名を持つ実運用上のバイアス問題として裏づける**: 11章はバンディットアルゴリズムを人工的な設定(スロットマシンのアーム選択)として一般論で扱うのに対し、12章§12.4.1はこの構造がそのまま広告配信ログの学習データに現れることを示す。広告配信システムが実際に選んだ広告(アクション)に対するオーディエンスのレスポンスしか観測できず、選ばれた回数の多い広告ほどログに多く出現し、逆に選ばれなかった広告は評価データが不足する。12章はこの設定で生成されるデータを指してLogged Bandit Feedbackという用語を与え、対処法として(1) 出現頻度を傾向スコアとして使う学習時のバイアス補正、(2) 選択回数が少なすぎるアクションを意図的に選ぶ探索方策、の2つを挙げる。11章が抽象的に論じた「探索を怠ると準最適解に固定化するリスク」(→[[探索と活用のトレードオフ]])が、12章では「学習データに出現しないアクションを永遠に正しく評価できない」という具体的な機械学習パイプライン上の帰結として再登場しており、理論と実運用のギャップを橋渡しする対応関係にある。(Source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] §11.1, [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 12 オンライン広告における機械学習]] §12.4.1) ## 未解決の問い - 12章のLogged Bandit Feedback対処法(傾向スコア補正/意図的な未知アクション選択)は、11章のBayesian-UCB・UCB1・Softmax法・TS法のどれと直接対応するのか、あるいはこれらのアルゴリズムとは独立にログ収集段階で講じる別レイヤーの対処なのかは、両ソースとも明示していない。 - 本ソースは決定的アルゴリズム(Bayesian-UCB・UCB1)と確率的アルゴリズム(Softmax法・TS法)を実環境適性で対比するが、両者の理論的なRegret上界がどう異なるかは数式・証明を意図的に省いているため触れられていない。 - 文脈付き多腕バンディットのブートストラップ法による実装は、ベース学習器に決定木を用いた場合の例のみを扱う。GBDTやxgboostのような勾配ブースティング系アルゴリズムをベースにした場合の性能・計算コストの違いは、本ソースでは名前が挙がるのみで検証されていない。 - 報酬到着が遅延する環境での「報酬待ちの試行を無視する/報酬ゼロとして扱う/期待値最大のアームの事後分布を仮に割り当てる」という3つの対処法のどれを選ぶべきかの判断基準(遅延時間の分布・アーム数・報酬の疎密等)は明示されていない。 - ε-greedy法は本書では意図的に解説が省かれている(脚注)が、9章§9.2.5はε=0.9の具体例つきで解説している(既出)。UCB系・Softmax法・TS法とε-greedy法の性能比較(理論的なRegretの違い)は両ソースいずれの範囲外であり、[[強化学習]]・[[好奇心駆動学習]]の探索戦略との統一的な比較が今後の課題になる。 - 9章§9.2.5.1が指摘する「文脈バンディットの探索戦略はモデルアーキテクチャー(決定木かニューラルネットワークか)に依存するためユースケース間の汎用性が乏しい」という制約は、11章のブートストラップ法による文脈付き多腕バンディットの実装(決定木ベースのみ検証、既出)と、具体的にどう対応するか。両ソースを突き合わせても、汎用性の乏しさが11章の実装のどの部分に起因するかは特定できない。 ## 関連 - source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] / [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 12 オンライン広告における機械学習]](Logged Bandit Feedbackという実運用上の具体例) / [[@2023__OReillyJapan__機械学習システムデザイン - Chapter 9 実現場での継続学習とテスト]](モデル選択への応用、文脈バンディットの別定義、ε-グリーディ法の解説、Google実験の定量データ) - concept: [[探索と活用のトレードオフ]](本概念の中核をなす設計原理) / [[強化学習]](多腕バンディットが属する上位の問題設定) / [[学習問題設定の分類]](多腕バンディットを3軸で位置づける分類枠組み) / [[A-Bテスト]] / [[Uplift Modeling]](いずれも本概念の特殊ケースとみなせる) / [[CTR予測]](Logged Bandit Feedbackの具体的な発生源) / [[リアルタイム入札]] / [[継続的トレーニング]](継続的に更新されるモデル群からバンディットで最適なものを選ぶ関係) ## 出典 - 有賀康顕・中山心太・西林孝, 『仕事ではじめる機械学習 第2版』, オライリー・ジャパン, 2021, 第11章, 第12章, §12.4.1. - [[@2023__OReillyJapan__機械学習システムデザイン - Chapter 9 実現場での継続学習とテスト]] — Chip Huyen 著, 江川崇・平山順一 訳, 『機械学習システムデザイン』, オライリー・ジャパン, 2023, 9章, §9.2.5, §9.2.5.1.