## 定義 探索と活用のトレードオフとは、評価的フィードバックしか得られない意思決定問題([[多腕バンディット]]・[[強化学習]])において、まだ試していない/情報の少ない選択肢を試す「探索(exploration)」と、現時点で最も良いとわかっている選択肢を選ぶ「活用(exploitation)」との間で、どちらを優先するかを決めなければならないという構造的なジレンマである。探索を怠ると、真に最良の選択肢を見逃したまま準最適な選択肢を選び続けるリスクがある一方、活用を怠ると、既知の情報から得られるはずの報酬を取りこぼす。バンディットアルゴリズムの文脈では、探索は「試行回数が少なく母平均が不確かなアームを選択すること」、活用は「複数のアームのなかで母平均が大きいであろうものを選択すること」として定義される。(Source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] §11.1) [[教師あり学習]]と異なり、[[強化学習]]・[[多腕バンディット]]では訓練データが受動的に与えられず、自分が行動してはじめて観測が得られる(能動的なデータ取得)ため、今の情報で報酬を最大化するか、新しい行動を試して情報を得るかというこのジレンマを解く必要が生じる。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.4) ## 具体的な解法(バンディットアルゴリズムの水準) このトレードオフを解く方策として、以下の系統がある。 - **信用区間の上限を評価値にする(楽観的な評価)**: Bayesian-UCB・UCB1は、母平均の不確実性(信用区間の幅)を評価値に加算・反映させることで、不確実なアームを楽観的に評価し自動的に探索させる。試行回数が増え不確実性が減ると、評価値は自然と標本平均に収束し活用へ移行する。 - **選択確率を連続的に変化させる**: Softmax法は標本平均を選択確率に変換し、温度パラメータ(アニーリングで漸減させる)によって探索寄り(高温)から活用寄り(低温)への移行速度を制御する。 - **事後分布から乱数を引く**: Thompson Sampling法は、各アームの事後分布から乱数を1回生成し最大のものを選ぶことで、不確実性の大きいアームほど極端な値を引きやすくなり、結果として探索と活用が自動的にバランスする。 (Source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] §11.2-§11.6) ## 横断的知見 - **バンディットの解法は「不確実性の明示的な定量化」を軸にするのに対し、[[強化学習]]の教科書(第4章)はε-greedy法という単純な確率的解法にとどまり、好奇心駆動学習は「予測誤差」という代理指標を使う**: 本ページが積み増したBayesian-UCB・UCB1・TS法は、いずれも母平均の事後分布(信用区間・分散)という統計的な不確実性を直接評価値に組み込む。これに対し『ディープラーニングを支える技術〈2〉』第4章のε-greedy法は、確率εでランダムなアームを選び残りの確率で最良のアームを選ぶだけであり、不確実性の大きさそのものは評価値に反映されない(どのアームも一律の確率でしか探索されない)。[[好奇心駆動学習]]が導入する内発的報酬(予測誤差・新規性ベース)は、両者の中間に位置する第三の系統であり、「状態遷移の予測が難しい」という間接指標を通じて不確実性を近似する。3つの系統(信用区間ベース/一様ランダムベース/予測誤差ベース)が独立に発展しているが、いずれも「探索対象をどう優先順位付けするか」という同一問題の異なる解であることが、この2冊の教科書の対比から見える。(Source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] §11.2-§11.6, [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.9) - **決定的な探索(UCB系)は逐次性を前提とし、確率的な探索(Softmax・TS)はバッチ処理・並列化と両立する**: 本章が明示するBayesian-UCB/UCB1とSoftmax/TSの対比(§11.6, §11.9.1)は、バンディットという最も単純な逐次的意思決定問題においてすら「決定的な最適化」と「システム実装上の制約(遅延・並列化)」が衝突しうることを示す。この制約は、[[エージェント型強化学習]]がロールアウト生成の並列化・非同期パイプラインを主要な設計問題として扱う([[エージェント型強化学習]]の横断的知見にある「非同期デカップリング」原則)ことと構造的に対応する。バンディットの1試行=1決定という最小単位ですら並列化との衝突が生じるという事実は、より複雑なマルチターンのエージェント型RLで非同期実行が必須になる理由の最小限の説明を与える。(Source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] §11.6, §11.9.1, [[エージェント型強化学習]]) ## 未解決の問い - Bayesian-UCB・UCB1の「不確実性の明示的定量化」と好奇心駆動学習の「予測誤差による近似」は、理論的にどの程度等価か。状態空間が離散で小さいバンディット問題では前者が計算可能だが、状態空間が高次元・連続なRL環境では後者しか計算可能でない、という計算量の違いに起因する使い分けなのか、精査が必要。 - ε-greedy法(強化学習第4章で標準的に使われる)は、本ソース(ch11)では意図的に解説が省かれている。ε-greedy法をBayesian-UCB・UCB1・Softmax・TSと同一の人工データで比較した場合、性能はどう位置づけられるか。 - 探索と活用のトレードオフの「正しい」バランスは問題設定(Regret最小化かベイズ最適か)によって変わりうるが、本ページが扱う各アルゴリズムがどの最適化基準のもとで導出されているかは、本ソースが数式・証明を意図的に省いているため厳密には確認できていない。 ## 関連 - source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 11 バンディットアルゴリズムによる強化学習入門]] / [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] - concept: [[多腕バンディット]](本概念を解くための具体的な問題設定とアルゴリズム) / [[強化学習]](より一般的な逐次的意思決定問題としての上位概念) / [[好奇心駆動学習]](予測誤差ベースの探索戦略) / [[A-Bテスト]] / [[Uplift Modeling]](探索と活用のトレードオフを固定割当/動的割当という形で扱う応用) ## 出典 - 有賀康顕・中山心太・西林孝, 『仕事ではじめる機械学習 第2版』, オライリー・ジャパン, 2021, 第11章, §11.1-§11.6, §11.9.1. - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, 第2章, §2.4.