多腕バンディット問題(たわんばんでぃっともんだい、Multi-armed bandit problem)は、確率論機械学習において、一定の限られた資源のセットを競合する選択肢間で、期待利得を最大化するように配分しなければならない問題。それぞれの選択肢の特性が、配分時には一部しか分かっておらず、時間が経過したり選択肢に資源が配分されることで理解できる可能性がある[1][2]。これは、探索(exploration)と活用(exploitation)のトレードオフのジレンマを例証する古典的な強化学習の問題である。この名前は、スロットマシン(単腕バンディットとも呼ばれる)の列で、どのマシンをプレイするか、各マシンを何回プレイするか、どの順番でプレイするか、現在のマシンを続けるか別のマシンを試すかを決めなければならないギャンブラーを想像することに由来している[3]。多腕バンディット問題も、広義の確率的スケジューリングに分類される。

ラスベガスのスロットマシン

経験的動機

編集
 
結果を最大化するために、これらの研究部門間で特定の予算をどのように配分すべきか?

多腕バンディット問題は、新しい知識の取得(探索 exploration)と既存の知識に基づいた意思決定の最適化(活用 exploitation)を同時に試みるエージェントをモデル化したものである。エージェントは、これらの競合するタスクのバランスをとりながら、考慮される期間中の総価値を最大化しようとする。以下のような例がある。

  • 患者の損失を最小限に抑えながら、さまざまな実験的治療の効果を調査する臨床試験[1] [4]
  • ネットワークの遅延を最小化するための適応的なルーティングの取り組み
  • 金融ポートフォリオの設計[5][6]

このような実用例では、すでに獲得した知識に基づく報酬の最大化と、さらに知識を増やすための新しい行動の思考とのバランスが問題となる。これは、機械学習における探索 exploration と活用 exploitation のトレードオフとして知られる。

このモデルは、さまざまなプロジェクトへのリソースの動的な配分を制御するために使用されており、それぞれの可能性の難易度と報酬に関する不確実性がある場合、どのプロジェクトに取り組むかという問題に答えている[7]

第二次世界大戦で連合国の科学者によって検討されたが、それはあまりに難解なため、ピーター・ホイットルによれば、ドイツの科学者も時間を浪費できるようにと、この問題をドイツに投下することが提案されたのだという[8]

現在一般的に分析されているのは、1952年にハーバート・ロビンスによって定式されたバージョンである。

多腕バンディットモデル

編集

多腕バンディット(略称:バンディットまたは MAB)は、確率分布   の集合と見做すことができる。各確率分布は、  個のレバーのそれぞれによって配分される報酬に関連する。  を報酬分布の平均値とする。ギャンブラーは各ラウンドに1つのレバーを操作し、報酬を観察する。収集された報酬の合計を最大化することが目的である。地平線   は残りのラウンド数である。バンディット問題は、形式的には1状態のマルコフ決定過程と同等である。  ラウンド後の後悔   は、最適な戦略による報酬の合計と収集された報酬の合計との間の差の期待値として定義される。

 

ここで、最大報酬平均    を満たす。  はラウンド t の報酬である。

ゼロ後悔戦略とは、ラウンドごとの平均後悔が   が確率 1 でゼロになる戦略である[9]。直感的には、十分なラウンドがプレイされれば、後悔ゼロの戦略は最適な戦略に収束することが保証される。

関連項目

編集

脚注

編集
  1. ^ a b John C. Gittins (1989), Multi-armed bandit allocation indices, Wiley-Interscience Series in Systems and Optimization., Chichester: John Wiley & Sons, Ltd., ISBN 978-0-471-92059-5 
  2. ^ Don Berry; Fristedt, Bert (1985), Bandit problems: Sequential allocation of experiments, Monographs on Statistics and Applied Probability, London: Chapman & Hall, ISBN 978-0-412-24810-8 
  3. ^ Weber, Richard (1992), “On the Gittins index for multiarmed bandits”, Annals of Applied Probability 2 (4): 1024-1033, doi:10.1214/aoap/1177005588, JSTOR 2959678, https://jstor.org/stable/2959678 
  4. ^ Press, William H. (2009), “Bandit solutions provide unified ethical models for randomized clinical trials and comparative effectiveness research”, Proceedings of the National Academy of Sciences 106 (52): 22387-22392, Bibcode2009PNAS..10622387P, doi:10.1073/pnas.0912378106, PMC 2793317, PMID 20018711, http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pmcentrez&artid=2793317. 
  5. ^ Brochu, Eric; Hoffman, Matthew W.; de Freitas, Nando (2010-09), Portfolio Allocation for Bayesian Optimization, arXiv:1009.5419, Bibcode2010arXiv1009.5419B 
  6. ^ Shen, Weiwei; Wang, Jun; Jiang, Yu-Gang; Zha, Hongyuan (2015), “Portfolio Choices with Orthogonal Bandit Learning”, Proceedings of International Joint Conferences on Artificial Intelligence (IJCAI2015), http://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/viewPDFInterstitial/10972/10798 
  7. ^ Farias, Vivek F; Ritesh, Madan (2011), “The irrevocable multiarmed bandit problem”, Operations Research 59 (2): 383-399, doi:10.1287/opre.1100.0891 
  8. ^ Peter Whittle (1979), “Discussion of Dr Gittins' paper”, Journal of the Royal Statistical Society, Series B 41 (2): 148-177, doi:10.1111/j.2517-6161.1979.tb01069.x 
  9. ^ Vermorel, Joannes; Mohri, Mehryar (2005), Multi-armed bandit algorithms and empirical evaluation, In European Conference on Machine Learning, Springer, pp. 437-448, http://bandit.sourceforge.net/Vermorel2005poker.pdf 

参考文献

編集

外部リンク

編集