以下の参考書を読み進めながらのメモです。
バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)
- 作者: 本多淳也,中村篤祥
- 出版社/メーカー: 講談社
- 発売日: 2016/08/25
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (1件) を見る
- バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ), 本多淳也・中村篤祥 (著), 講談社, 2016/8/24出版
バンディット問題とは
事前に用意された複数のアームの中から最良と思われるアームを逐次的に探していく問題。 アームを一回選択すると報酬を得ることができ、限られた回数の中で繰り返しアームの選択をする中でもらえる報酬を最大化することが目的になる。
報酬を最大にする過程には探索と活用のトレードオフが存在している。つまり、今最良とわかっているアームを選択し続けると未知のさらに良いアームを見つけることはできない。一方で、未知のアームばかり探し続けていると報酬を得られないままアームを引ける回数を使い切ってしまう。
K本のアームの中から一本ずつ選びながら規定回数だけアームを選択し、累積の報酬を最大にする問題をK腕バンディット問題と呼ぶ。この時、アームを選択する人はなんらかの方針にしたがって次に引くアームを選ぶ、この方針のことを方策（ポリシー）と呼ぶ。
K本のアームは、なんらかの分布に基づいて報酬をだしていて、この分布が常に固定か・アームを選択する人の方策にしたがって変化するかによって確率的バンディット・敵対的バンディットの二種類に分けることができる(バンディットの理論と応用, IBIS2011, 中村)。
方策の評価方法：リグレット
検索して上に出てくる「最善の選択肢を取り続けた場合」という言葉通り、毎回そのタイミングでの最良のアームを選択すると勝つことは絶対にできない。一本のアームをひき続けた時に得られる累積報酬の最大値を目標にして、それとの差分をリグレットと呼ぶ。つまり、あらかじめどのアームが期待報酬最大なのかを知っている状態の人に、何も知らない状態でどれくらい近づけるかが目標になる。敵対的バンディットの評価は疑リグレットと呼ぶ。
確率的バンディット
問題設定
- K本のアームから一本選んで報酬を得る、をn回行う
- それぞれのアームからの報酬は期待値が μ_{アームのインデックス} でありある分布の族（例えば全てベルヌーイ分布）になっているとする
- 累積報酬を最大化（リグレットを最小化）したい
標本分布と本当の分布の間の評価
観測した報酬の平均（標本平均）と本当の平均（母平均）の差の評価
- 中心極限定理
- チェルノフ・ヘフディング不等式[1]
良いアームを探す上で、過去のアームの報酬から得られた報酬の平均と実際の報酬平均がどれくらい離れているか、標本平均が期待値から大きく離れる確率（裾確率）を評価することは重要になる。
中心極限定理の場合、標本平均で母平均で近似するときの精度をよくするためには、精度に応じてサンプル数を巨大にする必要がある。チェルノフ・ヘフディング式の場合、分布の形によって指数項をさらに改善できる場合がある。
大偏差原理＝分布の収束先から低確率で発生する事象の確率の漸近的なふるまいを指数関数の形で評価する理論体系。サノフの定理から分布Pから得られたサンプルが分布Qから得られたかのように見える確率を評価できる。
方策
リグレット（期待報酬最大のアームを弾き続けた場合との差分が最小になる方策）が良い方策。
参考文献・資料
小宮山純平先生の人工知能学会誌での「私のブックマーク」
機械学習プロフェッショナルシリーズ資料
www.slideshare.net
その他参考文献
- [1] Michel Goemans, "18.310 lecture notes: Chernoff bounds, and some applications", 2015-2-21, http://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf
- [2] Po-Ning Chen, "Berry-Esseen Theorem", http://shannon.cm.nctu.edu.tw/prob/BEs08.pdf
- [3] Information and Coding Theory - Autumn 2014, https://ttic.uchicago.edu/~madhurt/courses/infotheory2014/
