多腕バンディット問題
多腕バンディット問題は、新しい知識の取得(探索 exploration)と既存の知識に基づいた意思決定の最適化(活用 exploitation)を同時に試みるエージェントをモデル化したものである。エージェントは、これらの競合するタスクのバランスをとりながら、考慮される期間中の総価値を最大化しようとする。以下のような例がある。
患者の損失を最小限に抑えながら、さまざまな実験的治療の効果を調査する臨床試験
ネットワークの遅延を最小化するための適応的なルーティングの取り組み
金融ポートフォリオの設計
このような実用例では、すでに獲得した知識に基づく報酬の最大化と、さらに知識を増やすための新しい行動の思考とのバランスが問題となる。これは、機械学習における探索 exploration と活用 exploitation のトレードオフとして知られる。
このモデルは、さまざまなプロジェクトへのリソースの動的な配分を制御するために使用されており、それぞれの可能性の難易度と報酬に関する不確実性がある場合、どのプロジェクトに取り組むかという問題に答えている。
第二次世界大戦で連合国の科学者によって検討されたが、それはあまりに難解なため、ピーター・ホイットルによれば、ドイツの科学者も時間を浪費できるようにと、この問題をドイツに投下することが提案されたのだという。
現在一般的に分析されているのは、1952年にハーバート・ロビンスによって定式されたバージョンである。
T {\displaystyle T} ラウンド後の後悔 ρ {\displaystyle \rho } は、最適な戦略による報酬の合計と収集された報酬の合計との間の差の期待値として定義される。
ρ = T μ ∗ − ∑ t = 1 T r ^ t {\displaystyle \rho =T\mu ^{*}-\sum _{t=1}^{T}{\widehat {r}}_{t}}
ここで、最大報酬平均 μ ∗ {\displaystyle \mu ^{*}} は μ ∗ = max k { μ k } {\displaystyle \mu ^{*}=\max _{k}\{\mu _{k}\}} を満たす。 r ^ t {\displaystyle {\widehat {r}}_{t}} はラウンド t の報酬である。
ゼロ後悔戦略とは、ラウンドごとの平均後悔が ρ / T {\displaystyle \rho /T} が確率 1 でゼロになる戦略である。直感的には、十分なラウンドがプレイされれば、後悔ゼロの戦略は最適な戦略に収束することが保証される。