多腕強盗

確率論と機械学習において、多腕バンディット問題（K- [ ^1]またはN-腕バンディット問題^[2]と呼ばれることもある）は、意思決定者が複数の固定された選択肢（つまり、腕または行動）から1つを反復的に選択する問題であり、各選択肢の特性は割り当て時点では部分的にしかわかっておらず、時間の経過とともに理解が深まる可能性がある。バンディット問題の基本的な側面は、腕を選択しても、その腕または他の腕の特性には影響しないという点である。^[3]

多腕バンディット問題の例としては、競合する（代替）選択肢の間で、後悔を最小化するように、固定された限られたリソースセットを反復的に割り当てるというタスクがあります。^{[4] [5]}多腕バンディット問題の注目すべき代替設定には、「最良のアームの識別」問題があり、その目標は有限数のラウンドの終わりまでに最適な選択肢を特定することです。^[6]

多腕バンディット問題は、探索と活用のトレードオフのジレンマを例示する古典的な強化学習問題です。一般的な強化学習とは対照的に、バンディット問題で選択されたアクションは、アームの報酬分配に影響を与えません。この名前は、スロットマシンの列（「片腕バンディット」と呼ばれることもあります）にいるギャンブラーを想像することに由来しています。ギャンブラーは、どのマシンでプレイするか、各マシンを何回プレイするか、どの順番でプレイするか、現在のマシンを続けるか、別のマシンを試すかを決定する必要があります。^[7]多腕バンディット問題は、確率的スケジューリングの広いカテゴリにも分類されます。

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

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

多腕バンディット問題は、新しい知識の獲得 (「探索」と呼ばれる) と既存の知識に基づく決定の最適化 (「活用」と呼ばれる) を同時に試みるエージェントをモデル化します。エージェントは、検討対象の期間にわたって合計価値を最大化するために、これらの競合するタスクのバランスを取ろうとします。バンディット モデルには、次のような多くの実用的なアプリケーションがあります。

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

これらの実際の例では、問題はすでに獲得した知識に基づく報酬の最大化と、知識をさらに増やすための新しいアクションの試行とのバランスを取る必要があります。これは、機械学習における活用と探索のトレードオフとして知られています。

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

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

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

多腕バンディット（略してバンディットまたは MAB）は、実分布 のセットとして考えることができます。各分布は、レバーの 1 つによって提供される報酬に関連付けられています。これらの報酬分布に関連付けられた平均値を とします。ギャンブラーは、ラウンドごとに 1 つのレバーを繰り返しプレイし、関連付けられた報酬を観察します。目的は、収集された報酬の合計を最大化することです。地平線は、プレイされる残りのラウンドの数です。バンディット問題は、形式的には 1 状態マルコフ決定プロセスに相当します。ラウンド後の後悔は、最適な戦略に関連付けられた報酬の合計と収集された報酬の合計との予想される差として定義されます。 ${\displaystyle B=\{R_{1},\dots ,R_{K}\}}$${\displaystyle K\in \mathbb {N} ^{+}}$${\displaystyle \mu _{1},\dots ,\mu _{K}}$${\displaystyle H}$ ${\displaystyle \rho}$${\displaystyle T}$

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

ここで、は最大報酬平均、 はラウンドtにおける報酬です。 ${\displaystyle \mu^{*}}$${\displaystyle \mu ^{*}=\max _{k}\{\mu _{k}\}}$${\displaystyle {\widehat {r}}_{t}}$

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

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

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

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

マルチアームバンディットにおける古典的な後悔最小化問題の重要なバリエーションは、純粋探索としても知られるベストアーム識別（BAI） ^[20]です。この問題は、臨床試験、適応ルーティング、推奨システム、A/Bテストなど、さまざまなアプリケーションで重要です。

BAI では、最も高い期待報酬を持つアームを特定することが目的です。この設定のアルゴリズムは、次のように記述される サンプリング ルール、決定ルール、および停止ルールによって特徴付けられます。

1. サンプリングルール：各時間ステップにおける一連のアクション${\displaystyle (a_{t})_{t\geq 1}}$
2. 停止ルール:サンプルの収集を停止するタイミングを示す (ランダムな) 停止時間です。${\displaystyle \tau}$
3. 決定ルール：これまでに収集されたデータに基づいて最適なアームを推測します${\displaystyle {\hat {a}}_{\tau}}$${\displaystyle \tau}$

BAI には主に 2 つの設定があります。

固定予算設定:時間範囲が与えられた場合、エラーの確率を最小限に抑えながら、期待される報酬が最も高いアームを特定することが目的です。 ${\displaystyle T\geq 1}$${\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}$${\displaystyle \delta}$

固定信頼度設定:信頼レベルが与えられた場合、目的は、可能な限り少ない試行回数とエラーの確率で、最も高い期待報酬を持つアームを特定することです。 ${\displaystyle \delta \in (0,1)}$${\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}$${\displaystyle \mathbb {P} ({\hat {a}}_{\tau }\neq a^{\star })\leq \delta }$

たとえば、決定ルール を使用すると、 を使用できます。ここで、 はマシン番号 1です(それぞれ異なる変数を使用できます)、 はレバーを引こうとする各試行の量です。ここで、 は各試行の合計として識別します。(...) 必要に応じて、そこから定量的確率として比率、合計、または平均を取得し、各スロットの定式化をサンプリングできます。 ${\displaystyle m_{1}}$${\displaystyle m}$${\displaystyle 1}$${\displaystyle \int \sum m_{1},m_{2},(...)=M}$${\displaystyle M}$${\displaystyle m_{1}+m_{2}}$

また、 を実行することもできます。ここで、 は各固有のマシン スロットに等しく、はレバーがトリガーされるたびに得られる金額、の合計、は所有している合計利用可能額、 はに対する相対値で、は からの各利益または損失の合計として減算されます( と定義される 100 ドルがあり、が に等しい利益 が に等しい損失 であるとします。そこから、独自の特定のルールを使用して に追加する正または負の結果が得られます)。 は、費やしてもよい最大額として計算されます。この構造は、を で制限したり、 を で制限したり できる前述の複数の代数式の組み合わせを使用して表現できます。${\displaystyle \int \sum _{k\propto _{i}}^{N}-(n_{j})}$${\displaystyle m1+m2}$${\displaystyle x,y}$${\displaystyle N}$${\displaystyle (m1_{x},_{y})+(m2_{x},_{y})(...)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle N}$${\displaystyle N=n(n_{a},b),(n1_{a},b),(n2_{a},b)}$${\displaystyle n_{j}}$${\displaystyle a,b}$${\displaystyle n}$${\displaystyle a}$${\displaystyle b}$${\displaystyle N}$${\displaystyle i}$${\displaystyle T}$

大きな進歩は、以下に説明する研究における最適な集団選択戦略、またはポリシー（平均が最も高い集団への均一な最大収束率を持つもの）の構築でした。

論文「漸近的に効率的な適応的割り当て規則」において、Lai と Robbins ^[21]は (1952 年の Robbins に遡る Robbins とその同僚の論文に続いて)、集団報酬分布が 1 パラメータ指数族である場合に (平均が最も高い集団に) 最も速い収束率を持つ収束的集団選択ポリシーを構築しました。その後、KatehakisとRobbins ^[22]では、既知の分散を持つ正規集団の場合のポリシーの簡略化と主な証明が示されました。次の注目すべき進歩は、Burnetas とKatehakisによる 論文「逐次割り当て問題に対する最適適応ポリシー」^[23]で達成されました。この論文では、各集団からの結果の分布が未知のパラメータのベクトルに依存する場合を含む、より一般的な条件下で、一様に最大収束率を持つインデックス ベースのポリシーが構築されました。 Burnetas と Katehakis (1996) は、結果の分布が任意の (つまり、非パラメトリックな) 離散単変量分布に従うという重要なケースに対しても明示的な解を提供しました。

その後、「マルコフ決定過程の最適適応政策」^[24]で、 Burnetas と Katehakis は、部分情報下でのマルコフ決定過程のはるかに大規模なモデルを研究しました。このモデルでは、遷移法則および/または期待される 1 期間の報酬が未知のパラメータに依存する可能性があります。この研究で、著者らは、有限状態行動空間と遷移法則の既約性という十分な仮定の下で、期待される有限期間の報酬全体に対して一様に最大収束率特性を持つ適応政策のクラスの明示的な形式を構築しました。これらの政策の主な特徴は、各状態と期間での行動の選択が、推定平均報酬最適方程式の右辺のインフレーションであるインデックスに基づいていることです。これらのインフレーションは、最近、Tewari と Bartlett、^[25]、 Ortner ^[26]、 Filippi、Cappé、および Garivier、^[27]、および Honda と Takemura ^{[28]の研究で楽観的アプローチと呼ばれています。}

ベルヌーイ多腕バンディットについては、ピラースキら^[29]が論文「ベルヌーイバンディットの最適ポリシー: 計算とアルゴリズム ゲージ」で、動的計画法を使用して完全に最適なソリューション (漸近的ではない) を導き出す計算方法を研究しました。^[29]インデックス スキーム、ルックアップ テーブル、その他の手法により、この研究では、時間範囲とアーム数が過度に大きくならない限り、ベルヌーイバンディットに実際に適用可能な最適ソリューションを提供しました。ピラースキら^[30]は後にこの研究を「遅延報酬ベルヌーイバンディット: 最適ポリシーと予測メタアルゴリズム PARDI」^[30]で拡張し、決定後すぐに報酬が明らかにならず、遅延される可能性がある場合にベルヌーイバンディットの最適ポリシーを決定する方法を作成しました。この方法は、まだ明らかにされていない報酬結果の期待値を計算し、報酬が明らかになったときに事後確率を更新します。

マルチアームバンディット課題の最適解^[31]を使用して動物の選択の価値を導き出すと、扁桃体と腹側線条体のニューロンの活動がこれらのポリシーから導き出された価値をエンコードし、動物が探索的選択と搾取的選択のどちらを行うかを解読するために使用できます。さらに、最適なポリシーは、代替戦略 (以下で説明) よりも動物の選択行動をよりよく予測します。これは、マルチアームバンディット問題の最適解が、計算量が多いにもかかわらず、生物学的に妥当であることを示唆しています。^[32]

バンディット問題に近似的な解決策を提供する戦略は数多く存在し、以下に詳述する 4 つの大まかなカテゴリに分類できます。

半均一戦略は、バンディット問題を近似的に解決するために発見された最も初期の（そして最も単純な）戦略です。これらの戦略に共通するのは、（均一に）ランダムなアクションが取られる場合を除いて、常に（以前の観察に基づいて） 最良のレバーを引くという貪欲な動作です。

• イプシロン貪欲戦略：^[33]試行の一定割合に対して最適なレバーが選択され、一定割合に対してはレバーがランダムに（均一な確率で）選択される。典型的なパラメータ値は であるが、これは状況や好みによって大きく変化する可能性がある。${\displaystyle 1-\epsilon }$${\displaystyle \epsilon }$${\displaystyle \epsilon =0.1}$
• イプシロン優先戦略^{[引用が必要]} : 純粋な探索フェーズの後に純粋な利用フェーズが続きます。試行全体のうち、探索フェーズは試行を占め、利用フェーズは試行を占めます。探索フェーズでは、レバーがランダムに選択されます (均一な確率で)。利用フェーズでは、常に最適なレバーが選択されます。${\displaystyle N}$${\displaystyle \epsilon N}$${\displaystyle (1-\epsilon )N}$
• イプシロン減少戦略^[要出典] : イプシロン貪欲戦略に似ていますが、実験が進むにつれて の値が減少するため、開始時には非常に探索的な行動が起こり、終了時には非常に搾取的な行動が起こります。${\displaystyle \epsilon }$
• 価値の差に基づく適応型イプシロン貪欲戦略 (VDBE) : イプシロン減少戦略に似ていますが、イプシロンは手動調整ではなく学習の進行に基づいて減少します (Tokic、2010)。^[34]価値推定値の変動が大きいと、イプシロンは高くなります (探索は高く、利用は低くなります)。変動が小さいと、イプシロンは低くなります (探索は低く、利用は高くなります)。探索アクションの場合は、ソフトマックス重み付けアクション選択によってさらに改善できます(Tokic & Palm、2011)。 ^[35]
• ベイジアンアンサンブルに基づく適応型イプシロン貪欲戦略 (Epsilon-BMC) : VBDE に似た、単調収束保証を備えた強化学習用の適応型イプシロン適応戦略。このフレームワークでは、イプシロンパラメータは、貪欲エージェント (学習した報酬を完全に信頼する) と均一学習エージェント (学習した報酬を信頼しない) を重み付けする事後分布の期待値と見なされます。この事後分布は、観測された報酬の正規性を仮定して、適切なベータ分布を使用して近似されます。イプシロンが急速に減少する可能性のあるリスクに対処するために、学習した報酬の分散の不確実性もモデル化され、正規ガンマモデルを使用して更新されます。 (Gimelfarb ら、2019)。^[36]

確率マッチング戦略は、特定のレバーを引く回数が、そのレバーが最適である実際の確率と一致するべきであるという考えを反映しています。確率マッチング戦略は、トンプソンサンプリングまたはベイジアンバンディット^{[37] [38]}としても知られており、各選択肢の平均値を事後分布からサンプリングできる場合は、驚くほど簡単に実装できます。

確率マッチング戦略は、いわゆる文脈バンディット問題に対する解決策も認める。^[37]

価格設定戦略は、各レバーの価格を設定します。例えば、POKERアルゴリズム^[16]で示されているように、価格は期待報酬と、追加の知識を通じて得られる将来の追加報酬の見積もりの​​合計になります。最も高い価格のレバーが常に引かれます。

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

コンテキスト バンディット問題に近似的な解決策を提供する戦略は多数存在し、以下に詳述する 2 つの大まかなカテゴリに分類できます。

• LinUCB （信頼上限）アルゴリズム：著者らは、行動の期待報酬とそのコンテキストの間に線形依存関係があると仮定し、線形予測子のセットを使用して表現空間をモデル化します。^{[40] [41]}
• LinRel（線形連想強化学習）アルゴリズム：LinUCBに似ていますが、リッジ回帰ではなく特異値分解を利用して信頼度の推定値を取得します。^{[42] [43]}

• UCBogramアルゴリズム: 非線形報酬関数は、ノンパラメトリック回帰におけるリグレッソグラムと呼ばれる区分定数推定器を使用して推定される。次に、各定数部分にUCBが適用される。コンテキスト空間の分割の連続的な改良は、スケジュールされるか、適応的に選択される。^{[44] [45] [46]}
• 一般化線形アルゴリズム：報酬の分配は線形バンディットの拡張である一般化線形モデルに従います。^{[47] [48] [49] [50]}
• KernelUCBアルゴリズム：効率的な実装と有限時間解析を備えた、linearUCBのカーネル化された非線形バージョン。^[51]
• バンディットフォレストアルゴリズム：ランダムフォレストを構築し、コンテキストと報酬の結合分布を知った上で構築されたランダムフォレストに基づいて分析する。^[52]
• オラクルベースのアルゴリズム：このアルゴリズムは文脈バンディット問題を一連の教師あり学習問題に縮小し、報酬関数に対する典型的な実現可能性の仮定に依存しません。^[53]

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

対数的後悔を伴う単純なアルゴリズムが提案されている: ^[55]

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

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

敵対的バンディットの例としてよく考えられるのは、反復囚人のジレンマです。この例では、各敵には引っ張るアームが 2 つあります。敵は否認するか自白することができます。標準的な確率的バンディット アルゴリズムは、このような反復ではうまく機能しません。たとえば、敵が最初の 100 ラウンドでは協力し、次の 200 ラウンドでは裏切り、その後の 300 ラウンドでは協力するなどの場合、UCB などのアルゴリズムはこれらの変化に迅速に対応できません。これは、ある時点以降、探索を制限して搾取に集中するために、最適でないアームが引っ張られることはほとんどないためです。環境が変化すると、アルゴリズムは適応できないか、変化を検出できない可能性があります。

EXP3 は、敵対的多腕バンディットの一般的なアルゴリズムであり、この設定で Auer ら [2002b] によって提案され分析されました。最近、このアルゴリズムの確率的設定でのパフォーマンスに対する関心が高まっています。これは、サイド情報を含む確率的多腕バンディット [Seldin ら、2011] や、混合確率的敵対的設定での多腕バンディット [Bubeck と Slivkins、2012] への新しい応用によるものです。この論文では、確率的設定での EXP3 アルゴリズムのパフォーマンスの実証的評価と改善された分析、および確率的環境で「対数的」な後悔を実現できる EXP3 アルゴリズムの修正が紹介されました。

 パラメータ:実数${\displaystyle \gamma \in (0,1]}$
 
  初期化:${\displaystyle \omega _{i}(1)=1}$${\displaystyle i=1,...,K}$
 
 各t = 1, 2, ..., Tについて
  1. 設定
  2.確率に従ってランダムに抽選
  3. 報酬を受け取る
  4.設定の場合:
      ${\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}$       ${\displaystyle i=1,...,K}$${\displaystyle i_{t}}$${\displaystyle p_{1}(t),...,p_{K}(t)}$${\displaystyle x_{i_{t}}(t)\in [0,1]}$${\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)}$

Exp3 は、確率でアームをランダムに選択します。より高い重み (exploit) を持つアームを優先し、確率で均一にランダムに探索することを選択します。報酬を受け取った後、重みが更新されます。指数関数的な成長により、優れたアームの重みが大幅に増加します。 ${\displaystyle (1-\gamma )}$${\displaystyle \gamma }$

Exp3アルゴリズムの（外部）後悔は最大で ${\displaystyle O({\sqrt {KTlog(K)}})}$

 パラメータ:実数${\displaystyle \eta }$
 
 初期化: ${\displaystyle \forall i:R_{i}(1)=0}$
 
 各t = 1,2,...,Tについて
  1. 各アームに指数分布からランダムノイズを生成します
  2. アームを引っ張ります:${\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}$${\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)}$
     残りは同じまま

私たちは、これまでで最高のパフォーマンスを示したと思われるアームを追跡し、それに指数関数的ノイズを加えて探索を行います。^[58]

元の仕様と上記のバリエーションでは、バンディット問題は離散的で有限個のアームで指定され、多くの場合変数 で示されます。Agrawal (1995) によって導入された無限アームの場合、^[59]では、 「アーム」は次元の連続変数です。 ${\displaystyle K}$${\displaystyle K}$

このフレームワークは、非定常設定（すなわち、概念ドリフトが存在する）における多腕バンディット問題を指す。非定常設定では、腕の期待報酬は各タイムステップで変化する可能性があると想定される。したがって、は腕の期待報酬（定常報酬）のシーケンス全体を表さなくなる。代わりに、は腕の期待報酬のシーケンスを表し、次のように定義される。^[60]${\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}}$

動的オラクルとは、非定常設定で他のポリシーと比較される最適なポリシーを表します。動的オラクルは、期待報酬が である最適なアームを常に選択することで、各ステップでの期待報酬を最適化します。したがって、最終時間ステップでの動的オラクルの累積期待報酬は次のように定義されます。 ${\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 ^[61]やスライディングウィンドウUCB ^[62]など、いくつかのアルゴリズムが発表されました。トンプソンサンプリングアルゴリズムに基づく同様のアプローチは、Cavenaghiらによって提案されたf-割引スライディングウィンドウトンプソンサンプリング (f-dsw TS) ^[63]です。f-dsw TSアルゴリズムは、報酬履歴の割引係数とアーム関連のスライディングウィンドウを利用して、非定常環境での概念ドリフトを対比します。Burtiniらによる別の研究では、加重最小二乗トンプソンサンプリングアプローチ (WLS-TS) が導入されており、これは既知および未知の非定常ケースの両方で有益であることが証明されています。^[64]

近年、この問題のさまざまなバリエーションが提案されています。

決闘盗賊の変種は、相対的フィードバックの探索対搾取のトレードオフをモデル化するために、Yue et al. (2012) ^[65]によって導入されました。この変種では、ギャンブラーは同時に 2 つのレバーを引くことができますが、どちらのレバーが最高の報酬をもたらしたかを示すバイナリ フィードバックしか得られません。この問題の難しさは、ギャンブラーが自分の行動の報酬を直接観察する方法がないことに起因します。この問題に対する最も初期のアルゴリズムは、InterleaveFiltering、^[65]、 Beat-The-Mean です。^{[66]決闘盗賊の相対的フィードバックは}、投票パラドックス にもつながります。解決策は、コンドルセ勝者を基準にすることです。^[67]

最近では、研究者らは伝統的なMABからデュエルバンディットまでアルゴリズムを一般化している：相対的上側信頼限界（RUCB）^[68]、相対的指数重み付け（REX3）^[69] 、コープランド信頼限界（CCB）^[70] 、相対的最小経験的発散（RMED）^[71]、およびダブルトンプソンサンプリング（DTS）^{[72] 。}

複数のバンディットが協力して知識を共有し、パフォーマンスを最適化するアプローチは、2013 年に「A Gang of Bandits」^[73]で始まりました。これは、異なるバンディット問題間の類似性グラフを利用して知識を共有するアルゴリズムです。類似性グラフの必要性は、2014 年に CLUB アルゴリズムの研究によってなくなりました。^[74]この研究に続いて、他の数人の研究者がバンディット フィードバック下で複数のモデルを同時に学習するアルゴリズムを作成しました。たとえば、COFIBA は Li、Karatzoglou、Gentile (SIGIR 2016) によって導入されました。^[75]ここでは、古典的な協調フィルタリングとコンテンツ ベース フィルタリングの方法が、トレーニング データを与えられた静的な推奨モデルを学習しようとします。

組み合わせ多腕バンディット（CMAB）問題^{[76] [77] [78]}は、エージェントが選択する単一の離散変数ではなく、一連の変数の値を選択する必要がある場合に発生します。各変数が離散的であると仮定すると、反復ごとの可能な選択肢の数は変数の数に対して指数関数的になります。文献では、変数がバイナリである設定^[77]から、各変数が任意の値のセットを取ることができるより一般的な設定まで、いくつかのCMAB設定が研究されています。^[78]

• Gittins インデックス – バンディット問題を分析するための強力で一般的な戦略。
• 貪欲アルゴリズム
• 最適な停止
• 検索理論
• 確率的スケジューリング

Scholia には、Multi-armed banditのトピックプロファイルがあります。

• 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)、「可用性制約のある割引バンディット問題に対するインデックスポリシー」、応用確率論の進歩、40 (2): 377–400、doi : 10.1239/aap/1214950209。
• パウエル、ウォーレン B. (2007)、「第 10 章」、近似動的プログラミング: 次元の呪いを解く、ニューヨーク: John Wiley and Sons、ISBN 978-0-470-17155-4。
• ロビンズ、H. (1952)、「実験の逐次設計のいくつかの側面」、アメリカ数学会報、58 (5): 527–535、doi : 10.1090/S0002-9904-1952-09620-8。
• サットン、リチャード; バルト、アンドリュー (1998)、強化学習、MIT プレス、ISBN 978-0-262-19398-6、2013-12-11にオリジナルからアーカイブ。

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

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