Multi-armed bandit 問題で理解する強化学習の概念
Multi-armed bandit 問題はSutton先生の "Reinforcement learning An introduction"で紹介される最初の問題である。
強化学習がどのような問題で有効的なのかを理解するのに適している。
問題の説明
Multi-armed bandit ( N-armed bandit ) では以下のシナリオを想像する：
カジノでスロットマシーンがN個並んでいる。私たちの勇気あるギャンブラー、太郎は今日で１０００回スロットを回す意気込みでカジノに来ている。
このN個のスロットで取れる行為はレバーを引くことだけである。異なるスロットのレバーを引く行為を と示せる。
問題の目的は１０００回スロットを遊んだ場合に報酬を最大にすること。
ここで太郎はN個のうちのスロットからどれを回すかを選ばなければならない。ここで大事となってくるのは各スロットの期待報酬が未知であること。
ただしを遊んでいくうちにそれぞれのスロットの期待報酬に関しての情報が得られていく。その情報を用いて太郎は自分の行動パターンを変更していく。
問題の特徴
・探索で最大の期待報酬のスロットを見つけたい
・上記の情報を用いて総合報酬を最大化したい
ここで探索と知識利用のジレッマ（exploration exploitation dilemma）が発生する。
・知識利用は現在のベストだと思ってる行為を選ぶこと。
・探索はすべての行為からランダムに選んで実行する。そしてその結果を用いて環境をより正確に評価する。（この問題の場合、各スロットの期待報酬に関しての情報を得る）
・試行の回数が限られているのでジレッマになる：
探索をしすぎると
各スロットの期待報酬を高い確率で実際値に近づけることができる。なので高い確率でもっとも期待報酬の高いスロットを選ぶことができる。ただし探索の回数が多いのでベストだと思っているスロットと異なるスロットを遊んで損をする。
知識利用をしすぎると
頻繁な探索で損をしないが、各スロットの期待報酬のサンプルが少ないためもっとも高い報酬だと判断しているスロットが実際そうではない確率が高くなる。
強化学習アプローチ
Action-value法
可能な行為がそれぞれどれぐらいの報酬をもたらすかを評価できればベストな行為を選ぶことができる。行為の期待報酬を
と示す。（Q関数）
一番単純な方法は今までの試行の結果を見てそれぞれの行為の平均報酬を測る
行為をk回行って観察された報酬が
だった場合
の期待報酬を以下とする：
アルゴリズム
知識利用をするには現在の Q関数で最大の行為を選ぶただし、
最初の試行ではQ関数は実際の期待報酬を示しておらずランダムに行為を選ぶのと等価である。試行を重ねていくうちにQ関数は実際の期待報酬の測定がより的確となっていく。
ε-greedy
各試行で：
ε の確率で:
探索を行う (ランダムに行為を選択)
1-ε の確率で
知識利用する,
（Q関数の最大値となる行為を行う）
得られた結果の報酬を用いてQ関数を更新する
実行してみると
epsilon = 0.1 , 0.01
2000個の10-armed banditタスクの平均。1タスクのステップは1000回
探索回数が少ない場合(epsilon = 0.01)：
・期待報酬が最大のスロットを見つけるのにステップの回数が多い
・この例ではベストのスロットを見つけると同時に1000回のステップがほぼ終わってしまう（知識利用するステップが少ない）
探索回数が多い場合(epsilon = 0.1)：
・期待報酬の最大のスロットは早い段階で見つかる
・しかし見つかった後でも1割の確率で探索を行うのでベストではないスロットを選んでしまう
