多腕バンディット問題は、時にはK腕またはN腕バンディット問題とも呼ばれ、確率論と機械学習における基礎的な概念である。これは、しばしば「片腕バンディット」と呼ばれる一列のスロットマシンに直面したギャンブラーにちなんで名付けられたもので、そのギャンブラーはどのマシンをプレイするか、各マシンを何回プレイするか、どの順序でプレイするかを決定し、同時に現在のマシンに固執するか別のマシンを試すかを決定しなければならない。より一般的には、各選択肢の特性が割り当て時点では部分的にしか知られておらず、時間の経過とともによりよく理解される可能性がある場合に、腕または行動として知られるいくつかの固定された選択肢のうちの1つを反復的に選択する意思決定者を記述する。重要な側面は、腕を選択してもその腕や他の腕の特性に影響を与えないことであり、これは行動が将来の状態や報酬分布を変える可能性があるより広範な強化学習問題と区別される。
この問題は、機械学習における中心的なジレンマである探索と活用のトレードオフを例示している。ギャンブラーは、既知の期待利得が最も高いマシンの「活用」と、他のマシンに関するより多くの情報を収集するための「探索」のバランスを取らなければならない。目的は、一連のレバー操作を通じて得られる総報酬を最大化することである。このトレードオフは、臨床試験、適応型ネットワークルーティング、金融ポートフォリオ設計、研究組織におけるリソース割り当てなど、多くの実用的な応用に見られる。
多腕バンディット問題は、もともと第二次世界大戦中に連合国の科学者によって検討されたが、それは非常に扱いにくいものであったため、ピーター・ウィットルによれば、ドイツの科学者もそれに時間を浪費できるように、ドイツ上空に投下することが提案された。現在一般的に分析されているバージョンは、1952年にハーバート・ロビンスによって定式化され、彼は論文「逐次実験計画のいくつかの側面」において収束する集団選択戦略を構築した。注目すべき理論的結果は、ジョン・C・ギッティンズによって最初に発表されたギッティンズ指数であり、これは期待される割引報酬を最大化するための最適な政策を提供する。
正式なモデル
多腕バンディットは、実分布の集合 \(B = \{R_1, \dots, R_K\}\) としてモデル化でき、各分布は \(K\) 個のレバーのうちの1つによって提供される報酬に関連付けられ、ここで \(K \in \mathbb{N}^+\) である。\(\mu_1, \dots, \mu_K\) をこれらの報酬分布の平均値とする。ギャンブラーは各ラウンドで1つのレバーを反復的にプレイし、関連する報酬を観察し、残りのラウンド数であるホライズン \(H\) にわたって収集された報酬の合計を最大化することを目標とする。バンディット問題は、正式には1状態マルコフ決定過程と同等である。
リグレットは \(\rho\) と表記され、最適な戦略の報酬合計と \(T\) ラウンド後に収集された報酬との間の期待差を測定する。これは \(\rho = T\mu^ - \sum_{t=1}^T \hat{r}_t\) として定義され、ここで \(\mu^\) は最大の報酬平均であり、\(\hat{r}_t\) はラウンド \(t\) で得られた報酬である。リグレットの最小化は、バンディットアルゴリズムにおける主要な目的である。
探索と活用
探索と活用のトレードオフは、多腕バンディット問題における中核的な課題である。活用は、現在の知識に基づいて推定報酬が最も高い腕を選択することを含み、一方で探索は、その潜在的な報酬に関する不確実性を減らすために他の腕を試すことを含む。効果的な戦略は、長期的な累積報酬を最大化するために、これらの競合する目的のバランスを取らなければならない。このトレードオフはバンディットに固有のものではなく、Machine learning全体、特にReinforcement learningやArtificial intelligenceシステムに見られ、既知の戦略を使用することと新しい戦略を発見することの間で決定を下さなければならない。
実際には、多腕バンディットは、科学財団や製薬会社のような大規模組織における研究プロジェクトの管理などの問題をモデル化するために使用されてきた。例えば、研究マネージャーはどのプロジェクトに資金を提供するかを決定しなければならず、既知の可能性を持つプロジェクトの活用と、新しい不確実なアイデアの探索のバランスを取る。このモデルはまた、ネットワーク遅延を最小化するための適応型ルーティングや、資産の選択が同様のトレードオフを含む金融ポートフォリオ設計にも適用されている。
アルゴリズムと戦略
多腕バンディット問題に対処するために、いくつかのアルゴリズムが開発されてきた。最も初期のものの1つはイプシロン・グリーディ戦略であり、エージェントは確率 \(\epsilon\) でランダムな腕を選択し（探索）、それ以外の場合は推定報酬が最も高い腕を選択する（活用）。もう1つの人気のあるアプローチは、上限信頼境界（UCB）アルゴリズムであり、これは平均報酬とその推定の不確実性の両方に基づいて腕を選択し、原理的な方法で探索と活用のバランスを効果的に取る。トンプソンサンプリングはベイズ法であり、各腕の報酬に対する事後分布を維持し、これらの分布からサンプリングしてどの腕をプレイするかを決定する。
ジョン・C・ギッティンズによって導入されたギッティンズ指数は、特定のバンディット設定において期待される割引報酬を最大化するための最適な政策を提供する。これは各腕の状態に基づいて指数を割り当て、最適な戦略は最も高い指数を持つ腕をプレイすることである。この結果は、オペレーションズリサーチと経済学に影響を与えてきた。
応用と実証的証拠
多腕バンディットの枠組みには、多くの実用的な応用がある。臨床試験では、患者を異なる治療に割り当てるために使用でき、患者の損失を最小化しながら治療効果に関する情報を収集する。適応型ルーティングでは、ネットワークパスを動的に選択することで遅延を最小化するのに役立つ。金融ポートフォリオ設計では、競合する投資オプション間でのリソースの割り当てを導く。
2024年の研究では、カジノのギャンブル記録を使用して、未知のオッズを持つスロットマシン間でのプレイヤーの繰り返しの選択を大規模な多腕バンディット問題として扱った。この研究では、より経験豊富なプレイヤーは、より良いオッズを持つマシンを選択する傾向があり、時間の経過とともにマシンの選択においてより大きな一貫性を示し、これは学習とよりよく知られたオプションのより大きな活用と一致するパターンであることがわかった。この実証的証拠は、バンディットモデルの現実世界の意思決定への関連性を支持している。
このモデルはまた、異なるプロジェクトへのリソースの動的な割り当てを制御するためにも使用されており、難易度と報酬に関する不確実性を考慮してどのプロジェクトに取り組むべきかという質問に答える。この応用は、組織が限られたリソースを競合するイニシアチブ間でどのように割り当てるかを決定しなければならない研究開発において特に重要である。
強化学習との関係
多腕バンディット問題は、探索と活用のトレードオフを例示する古典的なReinforcement learning問題である。しかし、選択された行動が腕の報酬分布に影響を与えないため、一般的な強化学習よりも単純である。対照的に、一般的な強化学習では、行動が環境の状態を変え、将来の報酬に影響を与える可能性がある。この区別により、バンディットは探索と活用のジレンマを研究するための扱いやすい出発点となり、バンディットのために開発された多くのアルゴリズムが、より複雑な強化学習設定に拡張されている。
この問題はまた、異なる行動の結果に関する不確実性の下で決定を下さなければならない確率的スケジューリングの広範なカテゴリーに該当する。この関連性は、オペレーションズリサーチからArtificial intelligenceまで、さまざまな領域にわたるバンディットモデルの広範な適用可能性を強調している。
要約すると、多腕バンディット問題は、不確実性の下での意思決定のための基本的なモデルであり、深い理論的ルーツと広範な実用的関連性を持つ。その研究は、Machine learningおよびそれ以降の研究に情報を提供し続ける洗練されたアルゴリズムと洞察を生み出してきた。