多腕強盗

確率論や機械学習では、マルチアームバンディット問題（Kアームバンディット問題^{[ 1 ]}またはNアームバンディット問題^{[ 2 ]}とも呼ばれる）は、スロットマシン（「ワンアームバンディット」とも呼ばれる）が並んだ場所で、どのマシンでプレイするか、各マシンで何回プレイするか、どの順番でプレイするか、現在のマシンを続けるか別のマシンを試すかを決めなければならないギャンブラーを想像して名付けられました。^{[ 3 ]}

より一般的には、これは意思決定者が複数の固定された選択肢（つまり、武器または行動）の中から繰り返し1つを選択する問題であり、各選択肢の特性は割り当ての時点では部分的にしかわかっておらず、時間の経過とともに理解が深まる可能性がある。バンディット問題の基本的な側面は、武器を選択しても、その武器や他の武器の特性には影響しないということである。^{[ 4 ]}

多腕バンディット問題の例としては、固定された限られたリソースを競合する（代替）選択肢間で繰り返し割り当てて後悔を最小限に抑えるタスクが挙げられる。^{[ 5 ] [ 6 ]}多腕バンディット問題の注目すべき代替設定には、「ベストアーム識別（BAI）」問題があり、これは有限ラウンドの終了までに最良の選択肢を特定することを目標としている。^{[ 7 ]}

マルチアームバンディット問題は、探索と活用のトレードオフのジレンマを典型的に示す、古典的な強化学習問題である。一般的な強化学習とは異なり、バンディット問題における選択された行動は、アーム間の報酬分配に影響を与えない。

多腕バンディット問題もまた、確率的スケジューリングという広いカテゴリーに分類される。

この問題では、各マシンは、そのマシン固有の 確率分布からランダムな報酬を提供しますが、その確率分布は事前にはわかりません。ギャンブラーの目的は、一連のレバー操作によって得られる報酬の合計を最大化することです。^{[ 5 ] [ 6 ]}ギャンブラーが各試行で直面する重要なトレードオフは、期待報酬が最も高いマシンの「活用」と、他のマシンの期待報酬に関するより多くの情報を得るための「探索」との間のトレードオフです。探索と活用のトレードオフは、機械学習でも直面します。実際には、マルチアームバンディットは、科学財団や製薬会社のような大規模組織での研究プロジェクトの管理などの問題をモデル化するために使用されてきました。^{[ 5 ] [ 6 ]}この問題の初期バージョンでは、ギャンブラーはマシンに関する初期知識を一切持たずに開始します。

1952年、ハーバート・ロビンスは、この問題の重要性を認識し、「実験の逐次設計のいくつかの側面」において、収束的な集団選択戦略を構築した。^{[ 8 ]}ジョン・C・ギティンスによって最初に発表されたギティンス指数という定理は、期待割引報酬を最大化するための最適な方針を示している。^{[ 9 ]}

多腕バンディット問題は、新しい知識の獲得（「探索」と呼ばれる）と既存の知識に基づく意思決定の最適化（「活用」と呼ばれる）を同時に試みるエージェントをモデル化したものです。エージェントは、考慮される期間における総価値を最大化するために、これらの相反するタスクのバランスを取ろうとします。バンディットモデルには、例えば以下のような多くの実用的な応用例があります。

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

これらの実例では、既に獲得した知識に基づいて報酬を最大化することと、知識をさらに増やすために新たな行動を試みることとのバランスを取ることが課題となります。これは機械学習における「活用と探索のトレードオフ」として知られています。

このモデルは、さまざまなプロジェクトへのリソースの動的な割り当てを制御するためにも使用されており、各可能性の難易度と報酬に関する不確実性を考慮して、どのプロジェクトに取り組むべきかという問いに答えています。^{[ 14 ]}

もともとは第二次世界大戦中に連合国の科学者によって検討されたが、非常に解決困難な問題であることが判明したため、ピーター・ウィットルによれば、ドイツの科学者にも時間を無駄にさせるために、この問題をドイツに投下することが提案されたという。 ^{[ 15 ]}

現在一般的に分析されているこの問題の定式化は、 1952年にハーバート・ロビンスによって行われた。

マルチアームバンディット（略称：バンディットまたはMAB）は、実数分布の集合と見なすことができる。${\displaystyle B=\{R_{1},\dots ,R_{K}\}}$各分配は、$\displaystyle K\in \mathbb {N} ^{+}}$レバー。${\displaystyle \mu _{1},\dots ,\mu _{K}}$これらの報酬分布に関連付けられた平均値をそれぞれとする。ギャンブラーはラウンドごとに1つのレバーを繰り返し操作し、それに関連する報酬を観察する。目的は、獲得した報酬の合計を最大化することである。${\displaystyle H}$は、プレイすべき残りのラウンド数です。バンディット問題は、形式的には1状態マルコフ決定過程と同等です。後悔${\displaystyle \rho }$後${\displaystyle T}$ラウンドとは、最適な戦略に関連付けられた報酬の合計と、収集された報酬の合計との期待される差として定義されます。

${\displaystyle \rho =T\mu ^{*}-\sum _{t=1}^{T}{\widehat {r}}_{t}}$、

どこ${\displaystyle \mu ^{*}}$最大報酬平均は、${\displaystyle \mu ^{*}=\max _{k}\{\mu _{k}\}}$、 そして$\displaystyle {\widehat {r}}_{t}}$ラウンドの報酬は${\displaystyle t}$。

後悔ゼロ戦略とは、1ラウンドあたりの平均後悔がゼロである戦略のことである。${\displaystyle \rho /T}$プレイされたラウンド数が無限大に近づくと、確率 1 でゼロに収束する傾向がある。^{[ 16 ]}直感的には、十分なラウンドがプレイされれば、ゼロ後悔戦略は (必ずしも一意ではない) 最適な戦略に収束することが保証される。

一般的な定式化としては、バイナリ多腕バンディットまたはベルヌーイ多腕バンディットがあり、確率で1の報酬が支払われます。${\displaystyle p}$それ以外の場合は報酬はゼロです。

多腕バンディットの別の定式化では、各腕が独立したマルコフマシンを表します。特定の腕がプレイされるたびに、そのマシンの状態はマルコフ状態進化確率に従って選択された新しい状態に進みます。報酬はマシンの現在の状態に応じて与えられます。「落ち着きのないバンディット問題」と呼ばれる一般化では、プレイされていない腕の状態も時間とともに変化する可能性があります。^{[ 17 ]}また、（どの腕をプレイするかについての）選択肢の数が時間とともに増加するシステムについても議論されています。^{[ 18 ]}

コンピュータ科学の研究者たちは、最悪のケースを想定してマルチアームバンディットを研究し、確率的^{[ 1 ]}と非確率的^{[ 19 ]}の両方のアームペイオフに対して、有限および無限（漸近的）の時間範囲で後悔を最小化するアルゴリズムを得ました。

以下に述べる研究における大きなブレークスルーは、最適な個体群選択戦略、すなわち（平均値が最も高い個体群への収束率が均一に最大となる）政策の構築であった。

マルチアームバンディットの有用な一般化として、コンテキストマルチアームバンディットがあります。各イテレーションで、エージェントは依然としてアームを選択する必要がありますが、過去にプレイしたアームの報酬とともに使用できるd次元の特徴ベクトル、つまりコンテキストベクトルも参照して、プレイするアームを選択します。時間の経過とともに、学習者の目標は、コンテキストベクトルと報酬が互いにどのように関連しているかについての十分な情報を収集し、特徴ベクトルを見て次にプレイする最適なアームを予測できるようにすることです。^{[ 39 ]}

制約付きコンテキストバンディット

実際には、各アクションで消費されるリソースには通常コストが伴い、クラウドソーシングや臨床試験などの多くのアプリケーションでは総コストは予算によって制限されます。制約付きコンテキストバンディット (CCB) は、マルチアームバンディット設定で時間と予算の両方の制約を考慮したモデルです。A. Badanidiyuru ら^{[ 52 ] は}、リソースフルコンテキストバンディットとも呼ばれる予算制約付きコンテキストバンディットを最初に研究し、${\displaystyle O({\sqrt {T}})}$後悔は実現可能である。しかし、彼らの研究は限られた数のポリシーに焦点を当てており、アルゴリズムは計算効率が悪い。

対数後悔を伴う単純なアルゴリズムが^{[ 53 ]で提案されている。}

• UCB-ALP アルゴリズム: UCB-ALP のフレームワークは右図に示されています。UCB-ALP は、UCB メソッドと適応型線形計画法 (ALP) アルゴリズムを組み合わせたシンプルなアルゴリズムで、実用システムに簡単に導入できます。これは、制約付きコンテキストバンディットで対数後悔を達成する方法を示した最初の研究です。^{[ 53 ]}は単一の予算制約と固定コストの特殊なケースに特化していますが、その結果は、より一般的な CCB 問題のアルゴリズムの設計と分析に光を当てています。

多腕バンディット問題の別の変種は、AuerとCesa-Bianchi（1998）によって最初に導入された敵対的バンディット問題と呼ばれています。この変種では、各反復で、エージェントが腕を選択し、同時に敵対者が各腕の報酬構造を選択します。これは、分布に関するすべての仮定を取り除くため、バンディット問題の最も強力な一般化の1つであり、敵対的バンディット問題の解は、より具体的なバンディット問題の一般化された解となります^{[ 54 ] 。}

パラメータ:実数${\displaystyle \gamma \in (0,1]}$初期化:${\displaystyle \omega _{i}(1)=1}$のために${\displaystyle i=1,...,K}$各t = 1, 2, ..., Tについて 1. セット$${\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}$$      ${\displaystyle i=1,...,K}$ 2. 描く${\displaystyle i_{t}}$確率に従ってランダムに${\displaystyle p_{1}(t),...,p_{K}(t)}$ 3. 報酬を受け取る${\displaystyle x_{i_{t}}(t)\in [0,1]}$ 4.${\displaystyle j=1,...,K}$セット：     ${\displaystyle {\hat {x}}_{j}(t)={\begin{cases}x_{j}(t)/p_{j}(t)&{\text{if }}j=i_{t}\\0,&{\text{otherwise}}\end{cases}}}$    ${\displaystyle \omega _{j}(t+1)=\omega _{j}(t)\exp(\gamma {\hat {x}}_{j}(t)/K)}$

パラメータ:実数${\displaystyle \eta }$初期化:${\displaystyle \forall i:R_{i}(1)=0}$各t = 1,2,...,Tについて 1. 各アームに対して指数分布からランダムノイズを生成する${\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}$ 2. アームを引く${\displaystyle I(t)}$:${\displaystyle I(t)=arg\max _{i}\{R_{i}(t)+Z_{i}(t)\}}$ 各アームにノイズを加え、最も高い値を持つアームを引っ張る 3. 値を更新する:${\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)}$ それ以外は変わらない

元の仕様および上記のバリアントでは、バンディット問題は離散的かつ有限の数のアームで指定され、多くの場合、変数で示されます。${\displaystyle K}$^{アグラワル（1995） [ 57 ]}によって導入された無限腕の場合、「腕」は連続変数であり、${\displaystyle K}$寸法。

このフレームワークは、非定常設定（すなわち、概念ドリフトが存在する場合）における多腕バンディット問題を指します。非定常設定では、腕の期待報酬は${\displaystyle k}$各タイムステップごとに変化する可能性があります${\displaystyle t\in {\mathcal {T}}}$:${\displaystyle \mu _{t-1}^{k}\neq \mu _{t}^{k}}$。 したがって、${\displaystyle \mu _{t}^{k}}$もはやアームに対する期待される（定常）報酬の全シーケンスを表していない${\displaystyle k}$。 その代わり、${\displaystyle \mu ^{k}}$は、アームに対する期待報酬のシーケンスを表します。${\displaystyle k}$定義される${\displaystyle \mu ^{k}=\{\mu _{t}^{k}\}_{t=1}^{T}}$[ ^{58 ]​}

動的オラクルは、非定常設定において他のポリシーと比較される最適なポリシーを表します。動的オラクルは、各ステップで期待報酬を最適化します。${\displaystyle t\in {\mathcal {T}}}$常に最良の腕を選択することで、期待される報酬は${\displaystyle \mu _{t}^{*}}$したがって、累積期待報酬は${\displaystyle {\mathcal {D}}(T)}$最終タイムステップにおける動的オラクルについて${\displaystyle T}$は次のように定義されます。

${\displaystyle {\mathcal {D}}(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}.}$

したがって、後悔${\displaystyle \rho ^{\pi }(T)}$政策のために${\displaystyle \pi }$は、${\displaystyle {\mathcal {D}}(T)}$およびステップでの累積期待報酬${\displaystyle T}$政策のために${\displaystyle \pi }$:

${\displaystyle \rho ^{\pi }(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right]={\mathcal {D}}(T)-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right].}$

ガリヴィエとムーリンは、プレイ中に基礎となるモデルが変化するバンディット問題に関して、最初の結果をいくつか導き出しました。このケースに対処するために、割引UCB ^{[ 59 ]}やスライディングウィンドウUCB ^{[ 60 ]}など、多くのアルゴリズムが提示されました。トンプソンサンプリングアルゴリズムに基づく同様のアプローチは、カヴェナギらが提案したf割引スライディングウィンドウトンプソンサンプリング（f-dsw TS）^{[ 61 ]}です。f-dsw TSアルゴリズムは、報酬履歴の割引係数とアーム関連のスライディングウィンドウを利用して、非定常環境における概念ドリフトを抑制します。ブルティーニらによる別の研究では、重み付き最小二乗トンプソンサンプリングアプローチ（WLS-TS）が導入され、既知および未知の非定常ケースの両方で有益であることが証明されています。^{[ 62 ]}

近年、この問題の様々なバリエーションが提案されている。

• 探索してからコミットするアルゴリズム
• ギティンス指数 ― バンディット問題を分析するための強力かつ汎用的な戦略。
• 貪欲アルゴリズム
• 最適な停止
• 探索理論
• 確率的スケジューリング

• Guha, S.; Munagala, K.; Shi, P. (2010)、「不安定なバンディット問題に対する近似アルゴリズム」、Journal of the ACM、58 : 1–50、arXiv : 0711.3861、doi : 10.1145/1870103.1870106、S2CID 1654066 
• Dayanik, S.; Powell, W.; Yamazaki, K. (2008)、「利用可能性制約付き割引バンディット問題に対するインデックスポリシー」、Advances in Applied Probability、40 (2): 377–400、doi : 10.1239/aap/1214950209。
• パウエル、ウォーレン B. (2007)、「第 10 章」、近似動的計画法: 次元の呪いの解決、ニューヨーク: ジョン・ワイリー・アンド・サンズ、ISBN 978-0-470-17155-4。
• Robbins, H. (1952)、「実験の逐次設計のいくつかの側面」、Bulletin of the American Mathematical Society、58 (5): 527–535、Bibcode : 1952BAMaS..58..527R、doi : 10.1090/S0002-9904-1952-09620-8。
• サットン、リチャード、バート、アンドリュー (1998)、強化学習、MIT Press、ISBN 978-0-262-19398-62013年12月11日にオリジナルからアーカイブされました。

• Allesiardo, Robin (2014)、「コンテキストバンディット問題のためのニューラルネットワーク委員会」、ニューラル情報処理 – 第21回国際会議、ICONIP 2014、マレーシア、2014年11月3日～6日、議事録、Lecture Notes in Computer Science、vol.  8834、Springer、pp. 374–381、arXiv : 1409.8191、doi : 10.1007/978-3-319-12637-1_47、ISBN  978-3-319-12636-4S2CID 14155718​ 。

• Weber, Richard (1992)、「多腕バンディット問題におけるギティンス指数について」、応用確率年報、2 (4): 1024–1033、doi : 10.1214/aoap/1177005588、JSTOR 2959678 。
• Katehakis, M. ; C. Derman (1986)、「臨床試験における最適な逐次割り当てルールの計算」、適応統計的手法と関連トピック、数理統計学研究所講義ノート - モノグラフシリーズ、第8巻、 29～  39ページ、doi : 10.1214/lnms/1215540286、ISBN  978-0-940600-09-6JSTOR 4355518。​ 
• Katehakis, Michael N. ; Veinott, Jr., Arthur F. (1987)、「多腕バンディット問題：分解と計算」、Mathematics of Operations Research、12 (2): 262–268、doi : 10.1287/moor.12.2.262、JSTOR 3689689、S2CID 656323  

• MABWiserは、コンテキストフリー、パラメトリック、ノンパラメトリックのコンテキストポリシーをサポートする、オープンソースのPythonによるバンディット戦略の実装であり、並列化機能とシミュレーション機能を内蔵しています。
• PyMaBanditsは、PythonとMatlabで実装されたバンディット戦略のオープンソースライブラリです。
• コンテキストフリーおよびコンテキスト依存のマルチアームドバンディットポリシーのシミュレーションと評価を容易にする、コンテキスト対応のオープンソースRパッケージ。
• bandit.sourceforge.net Banditプロジェクト、バンディット戦略のオープンソース実装。
• Banditlibは、C++で実装されたバンディット戦略のオープンソースライブラリです。
• レスリー・パック・ケルブリングとマイケル・L・リットマン（1996）。開発対探査：単一国家の事例。
• チュートリアル：バンディット入門：アルゴリズムと理論。パート1。パート2。
• ファインマンのレストラン問題は、活用と探索のトレードオフを示す古典的な例（既知の答えがある）である。
• バンディットアルゴリズムとABテストの比較
• S. Bubeck と N. Cesa-Bianchi による「山賊に関する調査」。
• コンテキスト型マルチアームバンディットに関する調査、コンテキスト型バンディットに関する調査/チュートリアル。
• マルチアームバンディット戦略に関するブログ記事（Pythonコード付き）。
• イプシロングリーディ法、トンプソンサンプリング法、および上限信頼区間探索／活用バランス戦略を説明する、アニメーション付きのインタラクティブなグラフ。