# Reinforcement Learning: day 6 Policy Gradient

## Framework for Reinforcement Learning
$$
State(at\ step=t):s^{(t)}=s\\
Action(at\ step=t):a^{(t)}=a\\
Reward(at\ step=t+1):r^{(t+1)}=r\\
State(at\ step=t+1):s^{(t+1)}=s'\\
Policy: \pi(a|s)\\
Transition\ Probability: P(s'|s,a)
$$
※Policy$:\pi$ とはある状態$s$でとる行動$a$の確率分布である。
※Transition Probability$:P$ とは状態$s$で行動$a$をとったときに状態$s'$に遷移する確率分布である。

### 状態価値関数
ある状態$s$に対して発生する方策$\pi$に従った時の将来的な報酬の期待値
$$
V^{\pi}(s)=\sum_a \pi(a|s) \sum_{s'}P(s'|s,a)\{r(s'|s,a)+\gamma V^{\pi}(s')\}\ \ \ Bellman方程式\\
※\gamma は割引率と呼ばれるハイパーパラメータ
$$
### 行動価値関数
ある状態$s$での行動$a$に対して発生する方策$\pi$に従った時の将来的な報酬の期待値
$$
Q^{\pi}(a|s)=\sum_{s'}P(s'|s,a)\{r(s'|s,a)+\gamma V^{\pi}(s')\}\\
V^{\pi}(s)=\sum_a \pi(a|s) Q^{\pi}(a|s)\\
Q^{\pi}(a|s)=\sum_{s'}P(s'|s,a)\{r(s'|s,a)+\gamma \sum_{a'} \pi(a'|s') Q^{\pi}(a'|s')\}\\
※a' は 状態s'でのAction
$$
### 参考
https://qiita.com/triwave33/items/8966890701169f8cad47

## Objectives of Reinforcement Learning

強化学習の目的は「**期待値を最大化する最適行動方策$\pi^*$の獲得**」と言える。

解きたい問題の環境が既知であることは稀である。
基本的にエージェントが環境に対して相互作用を繰り返して報酬や次の状態を観測する事を考えると、最適方策の獲得は、次の２通りの方法で学習できる。
- 行動価値関数の最適化
- 方策の最適化

今回は方策の最適化手法について紹介する。

## Policy Gradient (方策勾配法)
方策$\pi$が$\theta$のパラメータとなっている事を考える。
※イメージしやすいのは、NNで方策$\pi$が決まっている等

ある方策$\pi(\theta)$に従って次の状態行動履歴(step$=T$)が得られたとする。
$$
\tau=(s^{(0)},a^{(0)},s^{(1)},a^{(1)}, ..., s^{(T)},a^{(T)})
$$
ここで$\tau$が得られる確率は以下のように定義できる。
$$
p^{\pi}(\tau)=P(s^{(0)})\prod_{t=0}^{T}P(s^{(t+1)}|s^{(t)},a^{(t)})\pi(a^{(t)}|s^{(t)})
$$
この確率に対する適当な関数$f(\tau)$の期待値は以下のように書くとする。
$$
E_{\pi}[f(\tau)]=\sum_{\tau}p^{\pi}(\tau)f(\tau)
$$
ある方策$\pi(\theta)$に従って得られた状態行動履歴$\tau$での累積報酬$R(\tau)$の期待値$J(\theta)$を考える。
累積報酬とその期待値の定義は次のように書ける。
$$
R(\tau)\equiv \sum_{t=0}^{T}r(s^{(t)},a^{(t)})\\
J(\theta)\equiv E_{\pi}[R(\tau)]=\sum_{\tau}p^{\pi}(\tau)R(\tau)
$$
方策勾配法では、この期待値$J(\theta)$を最大化するような$\theta$の最適化を行う。
[証明](https://qiita.com/itok_msi/items/3c278e06cf2b0bb32f4e)は省くが、**方策勾配定理**を示す。
$$
\frac{\partial J(\theta)}{\partial \theta}=\sum_{t=0}^{T}Q^{\pi}(s^{(t)},a^{(t)})\frac{\partial}{\partial \theta}\log \pi(a^{(t)}|s^{(t)})
$$

## 方策勾配定理を使った最適方策の獲得

方策勾配定理を使って、NNを想定したパラメータ$\theta$の更新を行う。
その前に・・・
### NNの損失関数との対比
平均二乗誤差の場合のloss計算は
$$
L(\theta)=\frac{1}{2}(Predict(\theta)-Answer)^2\\
\frac{\partial L(\theta)}{\partial \theta}=(Predict(\theta)-Answer)\times \frac{\partial}{\partial \theta}Predict(\theta)\\
\theta\leftarrow \theta-\alpha\frac{\partial L(\theta)}{\partial \theta}
$$
パラメータ更新はLossを最小とするように更新するので、勾配の値に対してマイナスとなる。

### 方策勾配定理における行動価値関数Q

Q-Learning とは異なり、価値反復法による$Q(s,a)$の取得はできない。
※Q-Learning
$$
Q(s,a)\leftarrow Q(s,a)+\alpha(r+\gamma \max_{a'} Q(a',s'))
$$
なので、ざっくりと見積もったQ値を適当に与えてやるのが良い。
方策$\pi$に従ったあるエピソードを得られたとき、そのエピソード内のあるstep $t'$における$Q^{\pi}(s^{(t')},a^{(t')})$は次のように定義できる。
$$
Q^{\pi}(s^{(t')},a^{(t')})\equiv \sum_{t=t'}^{T}\gamma^{t-t'}r(s^{(t)},a^{(t)})
$$

### 迷路の例

すごく単純なマスの最善方策について考える。
状態：マス１〜４
行動：↑↓←→
報酬：マス４にたどり着いた時に+1. それ以外は0
初期状態：マス１
終了条件：マス４にたとり着いた時
方策初期値：NNの初期パラメータ$\theta_0$によって適当に決まる

初期方策$\pi(\theta)$に従って行動した結果、下記の状態行動履歴$\tau$を得たとする。
$$
\tau=(1,↑,3,↓,1,←,1,→,2,↑,4)\\\
※s,a,s,a,... のように記述
$$

上記のエピソードにおいては、5stepでエピソードが終了している。各step における$Q$は割引率$\gamma=0.95$とすると、次のように計算できる。
$$
step1:Q(1,↑)=0.95^0\times 0+...+0.95^4\times 1\\
step2:Q(3,↓)=0.95^0\times 0+...+0.95^3\times 1\\
step3:Q(1,←)=0.95^0\times 0+...+0.95^2\times 1\\
step4:Q(1,→)=0.95^0\times 0+0.95^1\times 1\\
step5:Q(2,↑)=0.95^0\times 1\\
$$

**方策勾配定理に沿うような**損失関数$L(\theta)$を計算する。
※$J(\theta)$は最大となるように計算したため、最小化の問題とするためマイナスを掛ける事に留意する。

$$
\frac{\partial L(\theta)}{\partial \theta}=-\frac{\partial J(\theta)}{\partial \theta}=-\sum_{t=0}^{T}Q^{\pi}(s^{(t)},a^{(t)})\frac{\partial}{\partial \theta}\log \pi(a^{(t)}|s^{(t)})\\
=-Q(1,↑)\frac{\partial}{\partial \theta}\log \pi(↑|1)-Q(3,↓)\frac{\partial}{\partial \theta}\log \pi(↓|3)-Q(1,←)\frac{\partial}{\partial \theta}\log \pi(←|1)\\
-Q(1,→)\frac{\partial}{\partial \theta}\log \pi(→|1)-Q(3,↑)\frac{\partial}{\partial \theta}\log \pi(↑|3)\\
L(\theta)=-J(\theta)=-Q(1,↑)\log \pi(↑|1)-Q(3,↓)\log \pi(↓|3)-Q(1,←)\log \pi(←|1)\\
-Q(1,→)\log \pi(→|1)-Q(3,↑)\log \pi(↑|3)\\
=-\sum_{t=0}^{T}Q^{\pi}(s^{(t)},a^{(t)})\log \pi(a^{(t)}|s^{(t)})
$$
この$L(\theta)$を計算すれば、後は優秀なpytorchなどが自動微分を計算してくれるので、back propagation を実行するだけ。