イントロ
こんにちは！Navy Researchです。
学生時代に（NNを用いない）強化学習を用いた研究をしており、下記書籍をバイブルとしていました。本シリーズでは、個人的なOutputの練習も兼ね、講談社発刊の森本哲郎著「強化学習」（以下、書籍とします）の内容に触れたいと思います。
著作権の兼ね合いもありますので、本シリーズでは、書籍に掲載されている図を作成する過程について解説していきます。書籍に掲載されている図は、基本的に導出の計算式やコードが添付されていません。本シリーズは、自分で図を作成してみることで、より理解を深めることをモチベーションとしています。
前提
イントロの通り、あまり深く書籍の内容について追従することは憚られます（※図によっては書籍が無くても内容を理解できるものもあります）。ですので、本書がお手元にあると、より理解しやすいかと思われます。
計算過程
本稿では、「図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)$$
これを解くと、
\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))$$
これを展開すると、
\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)$を代入します。
\begin{align}
V^\pi(1)&=\frac{5+0.2\gamma \frac{1}{1-\gamma}}{1-0.8\gamma}
\end{align}
これを整理すると、
\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のことを、「吸収状態」とも言います）。これより、価値関数は以下のように表せます。
\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}
ここでは、等比級数の和の公式を利用しています。さらに整理すると、
\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
- なし
この場合は単純ですね。等比級数の和の公式から、以下が導けます。
\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)$」を計算しておきます。
\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コードです。
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）