この記事は何？
友達と強化学習の本を読む機会があり，毎週1章ずつ勉強しています．そこで学んだことをアウトプットしたものです．
今回は1章のまとめです．短い時間で書いているため，拙い部分も多くありますがご容赦下さい．
とりあえず公開して，更新していくことが大事だと考えています
1章 バンディット問題
1.1 機械学習の分類と強化学習
機械学習には以下の3つの分類があります．
- 教師あり学習: 入力と出力(正解ラベル)のペアデータを使って入力から出力への変換方法を学習する
- 教師なし学習: 正解ラベルのないデータを使い，データに潜む構造やパターンを見出す
- 強化学習: エージェントが環境と相互作用しながら集めたデータを使って高い報酬を得る方法を学習する
強化学習は教師あり学習，教師なし学習とも違う3つ目の分類で，
- 環境と相互作用しながら学習する
- 試行錯誤しながら学習する
という点がわかればいいと思っています．
1.2 バンディット問題
強化学習の中で最もシンプルな問題の一つであるバンディット問題について学習します．
1.2.1 バンディット問題とは
バンディットとは，スロットマシンの別称です．
バンディット(bandit)とは「盗賊」「山賊」という意味の単語ですが，スロットマシンにコインを入れると多くの場合コインを奪われることから，ギャンブラーの間で「1本腕の盗賊(one-armed bandit)」と呼ばれることになったそうです．面白いですね．
バンディット問題の設定を以下に示します．
- 当たる確率の異なる複数のスロットマシンがある
- プレイヤー(エージェント)は決められた回数(1000回など)スロットマシンをプレイし，得られるコインの枚数を最大化することを試みる.
- プレイヤーは，各スロットマシンの当たる確率を知らない
この問題では，各スロットマシンの当たる確率が環境，プレイヤーがエージェントです．
スロットマシンによって当たる確率が異なるため，エージェントは経験の中で当たりやすい「いいスロットマシン」を選んでプレイすることになります．
1.2.2 いいスロットマシンとは？
スロットマシンはランダム性があるため， 期待値の高いスロットマシンがいいスロットマシンです．
報酬の期待値を価値といいます．
特に，行動に対して得られる報酬の期待値を行動価値と言います．
1.2.3 数式で表す
$a, b$2つのスロットマシンがある場合を考える．
$A$: エージェントの行動．スロットマシン$a, b$のうちどちらかを選ぶことに対応し，aまたはbの2つをとる．
$R$: スロットマシンが吐き出したコインの枚数
$q(A)$: 行動$A$を取った時にエージェントが受け取る価値．この場合はスロットマシンからもらえるコインの期待値．
$$q(A) = \mathbb{E}[R|A]$$
バンディット問題をとくアルゴリズムを考えていきましょう．
1.3 バンディットアルゴリズム
実装はまだできてないのでとりあえずアルゴリズムだけ．実装はあとで更新します．
1.3.1 価値の評価
各スロットマシンをプレイした時，それまでに得られたコインの枚数の平均値を$Q$とします．$a,b$の2つのスロットマシンがあり，それぞれ$n$回ずつプレイした時
$$Q(a) = n回aをプレイして得られたコインの枚数の平均$$
$$Q(b) = n回bをプレイして得られたコインの枚数の平均$$
とします．この平均値は真の平均値ではありませんが，$n$が大きくなると信頼できる値になります．
1.3.2 平均値の実装
$Q_n$を$n$回の試行を行った後の行動価値とすると．
$$Q_n = \frac{(n-1)Q_{n-1} + R_n}{n} = Q_{n-1} + \frac{1}{n}(R_n - Q_{n-1})$$
整理して
$$Q_n = (1 - \frac{1}{n})Q_{n-1} + \frac{1}{n}R_n$$
すなわち，常に1つ前の行動価値と現在受け取った報酬だけわかれば行動価値は計算可能．すべての試行の結果を保存する必要はない．
1.3.3 プレイヤーの戦略
プレイヤー(エージェント)がどのような戦略を取るべきかを考えます．つまり，どうすれば価値が最大になるようなスロットマシンを見つけられるか，という戦略です．
まず考えつくのは，これまでにプレイした結果を元に一番いいスロットマシンを選ぶことです．具体的には，これまでの試行の中で最も価値の標本平均の大きいスロットマシンを選べばいいです．これをgreedyな行動といいます．
greedyな行動の問題点は，局所解に陥ったらそれ以降は最適化が進まないことです．
$a, b$の2つのスロットマシンがあり，1回ずつプレイして$a$の推定値が0，$b$の推定値が1だったとします．greedyな行動によれば，これ以降bしか選ばなくなります．でも，本当は$a$の方が期待値が高いかもしれません．
よって，一定の確率でgreedyでない行動をとることも必要になります．これは探索と呼ばれます．greedyな行動はこれまでの経験を活用するので活用と呼ばれます．
探索と活用を併用することで精度高くいいスロットマシンを推定できます．
1.4 バンディット問題の実装
省略．近日更新．
1.5 非定常問題
これまで扱ってきたバンディット問題は常にスロットマシンの期待値は一定でした．つまり，常に環境は一定です．これを定常問題といいます．
しかし現実には環境は常に移り変わります．例えば囲碁では，プレイヤーと相手が手を打つたびに盤上の環境は移り変わります．このように環境が変動する問題を非定常問題といいます．現実で扱う強化学習のもんだいのほとんどが非定常問題です．
ここからはこれをどのように解くか考えます．
1.5.1 非定常問題をとくために
定常問題では，標本平均を価値としていました．
$$Q_n = \frac{R_1 + R_2 + \cdots + R_n}{n}
\ = \frac{1}{n}R_1 + \frac{1}{n}R_2 + \cdots + \frac{1}{n}R_n$$
すなわち，すべての時刻の報酬は同じ重み$\frac{1}{n}$で評価されています．
これは常に状況が変動する定常問題では不適切です．なぜなら，時間とともに過去のデータの重要性は下がっていくからです．新しく得た報酬のデータの重要性が高くなるような価値のデザインが求められます．
ここで，重みを$\frac{1}{n}$の代わりに，固定値$\alpha (0 < \alpha < 1)$にすることを考えます．これは漸化式に含まれる重み$\frac{1}{n}$を固定値$\alpha$に置き換えることで実現可能です．
平均値の漸化式:
$$Q_n = Q_{n-1} + \frac{1}{n}(R_n -Q_{n-1}) $$
新しい漸化式
$$Q_n = Q_{n-1} + \alpha(R_n -Q_{n-1}) $$
これは指数平滑移動平均と呼ばれ，これを行うことで過去の報酬の重みが時間とともに減少します．
$$Q_n = \alpha R_n + \alpha (1-\alpha)R_{n-1} + \alpha (1-\alpha)^2R_{n-2} + \alpha (1-\alpha)^3R_{n-3} + (1-\alpha)^4Q_{n-4}$$