バンディット問題の歴史
1980年代から1990年代にかけて、エージェントがとる行動に依存して報酬と次の状態が決まるマルコフ決定過程において状態ごとの最適行動を学習する強化学習(reinforcement learning)の研究でも、探索と知識利用のトレードオフを解決して無限時間区間の幾何割引された累積報酬を最大化する方策について議論が行われた アーム選択指標が既存のものより単純かつ直感的なため様々な応用が行われるようになった
敵対的バンディットの研究はアウアー、チェザビアンキ、フロイント、シャピレらによる1995年の論文が始まりとされている
Hedgeアルゴリズムをバンディット問題に適応させたExp3方策を提案
HedgeアルゴリズムはK個の選択肢の各々に対し、過去の損失に応じた確率を割り当てるアルゴリズム
https://gyazo.com/c183e55c2a34267d522e0292be93e7d9