バンディット問題
概要
選択肢の集合から1つの要素を選択し、その選択肢の報酬を得るという問題を繰り返す中で報酬の総和を最大化することを目指す逐次決定問題
どの選択肢が当たりやすいか否かは、実際に選択した結果からのみ得られるため、最も当たりやすい選択を探すためには情報の少ない選択を選ぶ探索(exploration)が必要 しかし探索ばかりだと利益が大きくならないので、それまでに最も当たりやすい選択を選ぶという知識利用(expolitation)を行う必要もある 複数回繰り返していく中で、それまで得た報酬をもとに次に引く選択肢を決定する戦略のことを方策(policy)と呼ぶ https://gyazo.com/28e532cf6273348b13f89ffd238d694c
バンディットの由来
1つのアームがついた古典的なスロットマシンをプレイヤーにお金を使わせる(お金を奪う)ことから1腕バンディット(one-armed bandit)と呼ぶことに由来
K台のスロットマシンから1台のスロットマシンを選んでアーム(選択肢)を引くことを繰り返して報酬の最大化を目指す問題を多腕バンディット問題(multi-arm-bandit)と呼ぶようになった
これを一般化したものをバンディット問題と総称
バンディットの種類
参考
本多 淳也, 中村 篤祥, 2016, 『バンディット問題の理論とアルゴリズム』