強化学習 （森本哲郎 著） 掲載図1.12の導出

# イントロ
こんにちは！Navy Researchです。
学生時代に（NNを用いない）強化学習を用いた研究をしており、下記書籍をバイブルとしていました。本シリーズでは、個人的なOutputの練習も兼ね、講談社発刊の森本哲郎著「強化学習」（以下、書籍とします）の内容に触れたいと思います。

著作権の兼ね合いもありますので、本シリーズでは、書籍に掲載されている図を**作成する過程**について解説していきます。書籍に掲載されている図は、基本的に導出の計算式やコードが添付されていません。本シリーズは、自分で図を作成してみることで、より理解を深めることをモチベーションとしています。

# 前提
イントロの通り、あまり深く書籍の内容について追従することは憚られます（※図によっては書籍が無くても内容を理解できるものもあります）。ですので、本書がお手元にあると、より理解しやすいかと思われます。

# 計算過程

![1_12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3806582/4ef1714e-52e3-ef43-cc60-3a629509b49d.png)

本稿では、「図1.12：価値関数の割引率γ依存性」を模した上図のような図を作成することを目標とします。

図1.12は、図1.11の状態遷移図に従ったマルコフ遷移過程に対して、初期状態$S=1$において方策$\pi^1$、$\pi^2$、$\pi^3$に従ったときの価値関数$V^{\pi}(1)$と割引率$\gamma$の関係を図にしたものです。方策$\pi^1$、$\pi^2$、$\pi^3$ごとに、それぞれ計算してみましょう！

## 方策1の場合

状態$S=1, 2$それぞれで考えます。

### 状態1

* 確率0.2で状態2に遷移し、報酬5を得る。
* 確率0.8で状態1に滞在し、報酬5を得る。

### 状態2 
* 確率1.0で状態2に滞在し、報酬1を得る。

これを基に、各状態の価値関数 $V^\pi$ を以下のように表現できます。

$V^\pi(2)$は簡単で、再帰式で表せます。

$$V^\pi(2)=1+\gamma V^\pi(2)$$

これを解くと、

```math
\begin{align}
V^\pi(2)-\gamma V^\pi(2)&=1 \\
V^\pi(2)(1-\gamma)&=1 \\
V^\pi(2)&=\frac{1}{1-\gamma}
\end{align}
```

と表せます。

$V^\pi(1)$は以下のように立式できます。

$$V^\pi(1)=0.2(5+\gamma V^\pi(2))+0.8(5+\gamma V^\pi(1))$$
​
これを展開すると、

```math
\begin{align}
V^\pi(1)&=5+0.2\gamma V^\pi(2)+0.8\gamma V^\pi(1) \\
V^\pi(1)(1-0.8\gamma)&=5+0.2\gamma V^\pi(2) \\
V^\pi(1)&=\frac{5+0.2\gamma V^\pi(2)}{1-0.8\gamma}
\end{align}
```

ここで、先ほど求めた$V^\pi(2)$を代入します。

```math
\begin{align}
V^\pi(1)&=\frac{5+0.2\gamma \frac{1}{1-\gamma}}{1-0.8\gamma}
\end{align}
```

これを整理すると、

```math
\begin{align}
V^\pi(1)&=\frac{5(1-\gamma)+0.2\gamma}{(1-\gamma)(1-0.8\gamma)} \\
V^\pi(1)&=\frac{5-4.8\gamma}{(1-\gamma)(1-0.8\gamma)} 
\end{align}
```

と導くことができます。

## 方策2の場合

状態$S=1, 2$それぞれで考えます。

### 状態1

* 確率1.0で状態2に遷移し、報酬10を得る。

### 状態2 
* なし

$\pi^2$は$\pi^1$よりも単純ですね。1ステップで状態2へ遷移し、そこからは永遠に状態2で滞在し続けます（※このような状態2のことを、「**吸収状態**」とも言います）。これより、価値関数は以下のように表せます。

```math
\begin{align}
V^\pi(1)&=1.0\times 10+\sum^\infty_{k=1}(\gamma ^k \times 1) \\
V^\pi(1)&=10+\frac{1}{1-\gamma}-1 
\end{align}
```

ここでは、等比級数の和の公式を利用しています。さらに整理すると、

```math
\begin{align}
V^\pi(1)&=9+\frac{1}{1-\gamma} \\
V^\pi(1)&=\frac{10-9\gamma}{1-\gamma}
\end{align}
```

と導くことができます。

## 方策3の場合

状態$S=1, 2$それぞれで考えます。

### 状態1

* 確率1.0で状態1に滞在し、報酬2を得る。

### 状態2 
* なし

この場合は単純ですね。等比級数の和の公式から、以下が導けます。

```math
\begin{align}
V^\pi(1)&=\sum^\infty_{k=0}(\gamma ^k \times 2) \\
V^\pi(1)&=\frac{2}{1-\gamma}
\end{align}
```

# 「図1.12：価値関数の割引率γ依存性」の作成

以上の計算より、図1.12の類似図を作成していきたいと思います。上部の計算過程から、図1.12の縦軸ラベルである「$(1-\gamma)V^\pi(1)$」を計算しておきます。

```math
\begin{align}
(1-\gamma)V^\pi(1)&=\frac{5-4.8\gamma}{1-0.8\gamma} \qquad 　(\pi_d(1)=a^1)\\
(1-\gamma)V^\pi(1)&=10-9\gamma \qquad \quad　(\pi_d(1)=a^2) \\
(1-\gamma)V^\pi(1)&=2 \qquad \qquad \qquad　(\pi_d(1)=a^3)
\end{align}
```

以上より、図1.12を構成する各式を立式することができました！以下が図を作成するPythonコードです。

```python:1_12.py
import numpy as np
import matplotlib.pyplot as plt

# s = [s1, s2]           : 状態集合
# a = [a1, ... , an]     : 行動集合
#     if S=1: n=3
#     if S=2: n=1
# prob                   : 状態遷移確率 (S×A×S)
# reward                 : 報酬関数 (S×A)
# gamma                  : 学習率γ
S = [1, 2]
A = [1, 2, 3]
prob = [[[0.8, 0.0, 1.0], [0.0, 0.0, 0.0]], [[0.2, 1.0, 0.0], [1.0, 0.0, 0.0]]]
reward = [[5, 10, 2], [1, 0, 0]]
gamma = np.linspace(0.5, 1.0, num = 100, retstep = False)

# 以下，(1-γ)V^π(1)を求める．
# a1のとき，V1, ... , a3のとき，V3, とする．

# π_d(1) = a1 のとき
def V1(x):
    return (reward[0][0] - 4.8 * x) / (reward[1][0] - prob[0][0][0] * x)

# π_d(1) = a2 のとき
def V2(x):
    return reward[0][1] - 9 * x

# π_d(1) = a3 のとき
def V3(x):
    return np.ones([int(len(gamma)), 1]) * reward[0][2]

# 結果をプロットする．
plt.figure(figsize=(20, 20))

plt.plot(gamma, V1(gamma), c = 'c', label = r'$\pi_d(1)=a^1$', linewidth=8)
plt.plot(gamma, V2(gamma), c = 'm', label = r'$\pi_d(1)=a^2$', linewidth=8)
plt.plot(gamma, V3(gamma), c = 'k', label = r'$\pi_d(1)=a^3$', linewidth=8)

plt.legend(fontsize=30)
plt.xlabel(r'$\gamma$', fontsize=30)
plt.ylabel(r'$(1-\gamma)V^{\pi}(1)$', fontsize=30)
plt.xlim([0.5, 1.0])
plt.ylim([0, 6])
plt.minorticks_on()
plt.grid(which="major", axis = "x", color="black", alpha=0.5)
plt.grid(which="minor", axis = "x", color="gray", linestyle=":")
plt.grid(which="major", axis = "y", color="black", alpha=0.5)
plt.tick_params(labelsize=25)

plt.show()
```

# 参考文献
+ 森本 哲郎 『機械学習プロフェショナルシリーズ 強化学習』 講談社 （[URL](https://www.amazon.co.jp/%E5%BC%B7%E5%8C%96%E5%AD%A6%E7%BF%92-%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E6%A3%AE%E6%9D%91-%E5%93%B2%E9%83%8E/dp/4065155916)）