多腕バンディット問題

多腕バンディット問題（たわんばんでぃっともんだい、Multi-armed bandit problem）は、確率論と機械学習において、一定の限られた資源のセットを競合する選択肢間で、期待利得を最大化するように配分しなければならない問題。それぞれの選択肢の特性が、配分時には一部しか分かっておらず、時間が経過したり選択肢に資源が配分されることで理解できる可能性がある。これは、探索(exploration)と活用(exploitation)のトレードオフのジレンマを例証する古典的な強化学習の問題である。この名前は、スロットマシン（単腕バンディットとも呼ばれる）の列で、どのマシンをプレイするか、各マシンを何回プレイするか、どの順番でプレイするか、現在のマシンを続けるか別のマシンを試すかを決めなければならないギャンブラーを想像することに由来している。多腕バンディット問題も、広義の確率的スケジューリングに分類される。
経験的動機.
多腕バンディット問題は、新しい知識の取得（探索 exploration）と既存の知識に基づいた意思決定の最適化（活用 exploitation）を同時に試みるエージェントをモデル化したものである。エージェントは、これらの競合するタスクのバランスをとりながら、考慮される期間中の総価値を最大化しようとする。以下のような例がある。
このような実用例では、すでに獲得した知識に基づく報酬の最大化と、さらに知識を増やすための新しい行動の思考とのバランスが問題となる。これは、機械学習における探索 exploration と活用 exploitation のトレードオフとして知られる。
このモデルは、さまざまなプロジェクトへのリソースの動的な配分を制御するために使用されており、それぞれの可能性の難易度と報酬に関する不確実性がある場合、どのプロジェクトに取り組むかという問題に答えている。
第二次世界大戦で連合国の科学者によって検討されたが、それはあまりに難解なため、ピーター・ホイットルによれば、ドイツの科学者も時間を浪費できるようにと、この問題をドイツに投下することが提案されたのだという。
現在一般的に分析されているのは、1952年にハーバート・ロビンスによって定式されたバージョンである。
多腕バンディットモデル.
多腕バンディット（略称：バンディットまたは MAB）は、確率分布 formula_1 の集合と見做すことができる。各確率分布は、formula_2 個のレバーのそれぞれによって配分される報酬に関連する。formula_3 を報酬分布の平均値とする。ギャンブラーは各ラウンドに1つのレバーを操作し、報酬を観察する。収集された報酬の合計を最大化することが目的である。地平線 formula_4 は残りのラウンド数である。バンディット問題は、形式的には1状態のマルコフ決定過程と同等である。formula_5 ラウンド後の後悔 formula_6 は、最適な戦略による報酬の合計と収集された報酬の合計との間の差の期待値として定義される。
ここで、最大報酬平均 formula_8 は formula_9 を満たす。formula_10 はラウンド "t" の報酬である。
ゼロ後悔戦略とは、ラウンドごとの平均後悔が formula_11 が確率 1 でゼロになる戦略である。直感的には、十分なラウンドがプレイされれば、後悔ゼロの戦略は最適な戦略に収束することが保証される。