バンディット問題

エージェントが行動することで、環境から報酬を貰える。その報酬を最大化する。

エージェント（行動）→環境

エージェント←（報酬）環境

例えば、複数のスロットマシン（多腕バンディット）があり、どれかのスロットマシンを選んで回し、それを複数回試行した獲得コイン（報酬）を最大化する

どのスロットマシンを選ぶかは獲得コイン枚数とその確率を使った期待値（行動価値）をベースに考える

式で表すと以下になる。

$q(A) = E[R|A]$

q ：行動価値

A：行動

R：報酬

E：期待値

実際にはエージェントは各スロットの期待値がわからないので推定していく必要がある

行動の回数をn

報酬をR1、R2、R3、、、、、Rn

行動価値の推定値（期待値）をQｎ

とすると、

$Qn = \frac{R1 + R2 +・・・+Rn}{n}$

となるが、この式だとnが大きくなるに連れて計算リソースが大きくなる

これをいい感じに変形すると、

$Qn = Q_{n-1} + \frac1n(R_{n} - Q_{n-1})$

となり、

実際にプレイした結果をもとに一番良いスロットマシンを選ぶことを「greedyな行動」、「活用」という

スロットマシンの価値を精度良く推定するために様々なスロットマシンを試すことを「探索」という

バンディット問題では「活用」と「探索」のバランスをとる必要がある

「活用」と「探索」のバランスをとるアルゴリズムで基本的なものがε-greedy法

ε = 0.1(10%)の確率で「探索」を行い、それ以外は（1 - εの確率で）活用するという手法。

スロットの確率が試行ごとに変化するような非定常化問題を考える

非定常化問題では、環境が時間とともに変化するので過去の報酬の重要性は時間とともに低くする必要がある（最近の報酬ほど価値が高い）

行動価値 $Q_n$を更新するときのステップをα(0 < α < 1)とすることで、過去の報酬が指数関数的に低下する

$Q_n = Q_{n-1} + α(R_n - Q_{n-1})$

なぜそうなるのか。まず式を展開する

$Q_n = Q_{n-1} + α(R_n - Q_{n-1})$

$= αR_n + Q_{n-1} - αQ_{n-1}$

$= αR_n + (1 - α)Q_{n-1}$

ここでnを一つ繰り下げると以下になる

$Q_{n-1} = αR_{n-1} + (1 - α)Q_{n-2}$

展開した$Q_n$の式に上記を代入すると

$Q_n = αR_n + (1 - α)\{αR_{n-1} + (1 - α)Q_{n-2}\}$

$= αR_n + α(1 - α)R_{n-1}+(1 - α)^2Q_{n-2}$

となるので過去の報酬ほど指数関数的に小さくなる