敵対的バンディット
概要
プレイヤーの方策(policy)を知っている敵対者が報酬を決める場合を想定する プレイヤーの方策を知っている神のような能力をもつ敵対者が報酬を選ぶと仮定し、その最悪の場合でもうまくいく方策を考える
敵対者はプレイヤーのアーム選択方策を知った上で報酬を最小化しようとするため、プレイヤーがランダム性を持たない決定的な方策を用いる場合にはプレイヤーの選択アームを敵対者は事前に知ることが可能
したがって、選択アームに報酬の最小値を常に設定することが可能で、プレイヤーに勝ち目はない
そこでプレイヤーは確率的な方策を用いるしかない
ただし、敵対者はプレイヤーの実際の選択アームを知る前に各アームの報酬を決めるとする
敵対的バンディットで扱う報酬モデルは確率的バンディットを含んでいて、報酬の確率的な構造が未知である場合も扱うことができるのが利点
一方プレイヤーがより広い報酬モデルを考慮しなければならないため、保証可能な性能は確率的バンディットより劣る
敵対者のタイプ
プレイヤーの過去の選択に依存せず報酬を決める
プレイヤーの過去の選択に依存して次の報酬を決める
こちらのほうが難しい