強化学習（Dynamic Programming）
GymのFrozen Lake環境で、Policy Iterationを使った強化学習を行います。
（学習内容の理解整理のため書いているので、様々な箇所で誤記や説明不足があると思います。）
はじめに
強化学習は、Agentが環境から得られるRewardを最大化するよう、自ら学習していく仕組みです。環境にはState、Rewardなどが与えられ、Agentはその環境でPolicy（方策）に基づきActionを選びます。
Gymでは、強化学習の教育目的に様々な環境が提供されています。
今回は、その一つのFrozen Lakeを利用しようと思います。
Markov Reward Process: MRP
まず、MRPによりValue function $${V(s)}$$を計算します。
$${V(s)}$$は、報酬$$r$$を$${\gamma}$$で割り引いた現在価値の期待値で表します。$${s}$$はStateの意味で、現在いる場所です。
$${V(s) = \mathbb{E}[r_0+\gamma r_1+\gamma^2r_2+\dots]}$$
この式を以下のように変形できます。
$${V(s) = r_0+\gamma \sum_{s' \in S}P(s'\mid s)V(s')}$$
s’は次のStateです。Pは現在のStateと次のStateの行列になります。
Pは、ｓがｓ’に移動する確率$${p(s'\mid s)}$$のN×Nの行列（以下）です。
ここでは、Agentの方策(policy)によらず勝手に移動してしまう環境とします。
$${P=\begin{pmatrix} p(s_0\mid s_0) & \dots & p(s_0\mid s_{N})\\\vdots & \ddots & \vdots\\p(s_{N}\mid s_0) & \dots & p(s_{N}\mid s_{N})\end{pmatrix}}$$
例えば、State番号5にいるときに、State番号6に行く確率が50%であれば、$${p(s_6 \mid s_5)=0.5}$$となります。
これらの情報から、すべての$${V(s)}$$を調べることができます。
例として、2X2の環境を考えます。報酬は$${r(s_3)=1}$$で、それ以外はゼロ。Pが以下の時、$${V(s)}$$を求めてみましょう。割引率$${\gamma}$$は0.9とします。
$${P=\begin{pmatrix} p(s_0\mid s_0)=0.5 & 0.25 & 0.25 & 0\\0.25 & 0.5 & 0 & 0.25\\0.25 & 0 & 0.5 & 0.25\\0 & 0.25 & 0.25 &p(s_3\mid s_3)=0.5\\ \end{pmatrix} }$$
$${V(s) = r_0+\gamma \sum_{s' \in S}P(s'\mid s)V(s')}$$を使います。
$${V(0)=r_0(=0)+\gamma\{p(s_0\mid s_0)(=0.5)*V(0)+ p(s_1\mid s_0)(=0.25)*V(1)+p(s_2\mid s_0)(=0.25)*V(2)\} \\V(1)=r_1(=0)+\gamma\{p(s_0\mid s_1)(=0.25)*V(0)+ p(s_1\mid s_1)(=0.5)*V(1)+p(s_3\mid s_1)(=0.25)*V(3)\}\\V(2)=r_2(=0)+\gamma\{p(s_0\mid s_2)(=0.25)*V(0)+ p(s_2\mid s_2)(=0.5)*V(2)+p(s_3\mid s_2)(=0.25)*V(3)\}\\V(3)=r3(=1)+\gamma\{p(s_1\mid s_3)(=0.25)*V(1)+ p(s_3\mid s_3)(=0.5)*V(3)+p(s_2\mid s_3)(=0.25)*V(2)\}}$$となり、これを解きます。
具体的な計算は、Vをゼロなどに初期化して、収束するまで繰り返します。
実際にpython3でやってみましょう。
P ={0: {0: [(0.25, 0, 0.0)],
1: [(0.25, 2, 0.0)],
2: [(0.25, 1, 0.0)],
3: [(0.25, 0, 0.0)]},
1: {0: [(0.25, 0, 0.0)],
1: [(0.25, 3, 1.0)],
2: [(0.25, 1, 0.0)],
3: [(0.25, 1, 0.0)]},
2: {0: [(0.25, 2, 0.0)],
1: [(0.25, 2, 0.0)],
2: [(0.25, 3, 1.0)],
3: [(0.25, 0, 0.0)]},
3: {0: [(0.25, 2, 0.0)],
1: [(0.25, 3, 1.0)],
2: [(0.25, 3, 1.0)],
3: [(0.25, 1, 0.0)]}}環境PとしてState（2X2なので左上、右上、左下、右下の順で、0, 1, 2, 3の4種類）Action(左、下、右、上の順で、0, 1, 2, 3の4種類)のディクショナリを用意します。State, Actionごとに、確率、次のState、Reward(0,1)を入れています。
これらの環境で、V(s)を求めてみましょう。
gamma = 0.9
value_function = np.zeros(4)
diff = 1
i = 0
while diff > 0:
old_value_function = value_function.copy()
for s in range(4):
rw = 0
fv = 0
for a in range(4):
p = P[s][a][0]
rw += p[0]*p[2]
fv += gamma*p[0]*value_function[p[1]]
value_function[s] = rw+fv
diff = np.max(np.abs(value_function - old_value_function))
i +=1
print(value_function,i)結果は、249回実行したら無事収束。V[0：左上]2.045、V[1：右上]2.5、V[2：左下]2.5、V[3：右下]2.95になりました。Reward=1のV(3)が2.95と一番高くなりました。
Markov Decision Process: MDP
MRPでV(s)の考え方が理解出来たら、続いてAgentにある方策(Policy)に基づきActionするようにしてみましょう。
Policyは$${\pi(s)=p(a\mid s) (\in \mathbb{R}^{A \times S})}$$で表します。あるs地点でaというアクションをとる確率を表します。Frozen Lakeでは、上下左右の4つの移動Actionがあります。
Value FunctionにPolicyを埋め込むと、
$${V^\pi(s)=r(s,\pi (s))+\gamma \sum_{a \in A}\sum_{s' \in S}p(a\mid s)P(s'\mid s,\pi(s))V^\pi(s')}$$
これを計算すれば、ある方策$${\pi}$$における$${V^\pi(s)}$$が出てきます。
Policy Iteration
MDPでは、Agentがとったある方策$${pi(s)=p(a\mid s)}$$の$${V^\pi(s)}$$を計算することができました。
次は、どのPolicyを取ればV(s)を最大にできるのか。Q関数を導入し、計算してみましょう。
Frozen Lake
Policy Iterationでは、GymのFroze Lakeをつかってみましょう。
Frozen Lakeは4×4の16個のStateを持ちます。Frozenというだけあって、一定の確率で滑ってしまいます。
環境Pを見てみましょう。
import gym
env = gym.make("FrozenLake-v1")
env.P{0: {0: [
(0.3333333333333333, 0, 0.0, False),
(0.3333333333333333, 0, 0.0, False),
(0.3333333333333333, 4, 0.0, False)],
1: [(0.3333333333333333, 0, 0.0, False),
(0.3333333333333333, 4, 0.0, False),
(0.3333333333333333, 1, 0.0, False)],
2: [(0.3333333333333333, 4, 0.0, False),
(0.3333333333333333, 1, 0.0, False),
(0.3333333333333333, 0, 0.0, False)],
3: [(0.3333333333333333, 1, 0.0, False),
(0.3333333333333333, 0, 0.0, False),
(0.3333333333333333, 0, 0.0, False)]},
1: {0: [(0.3333333333333333, 1, 0.0, False),
(0.3333333333333333, 0, 0.0, False),
(0.3333333333333333, 5, 0.0, True)] …..
上のデータは、State(0-15)にいるときAction(0-3：左下右上)を選んだ場合の、確率、次のState、Reward、終点か否か、のデータになります。
たとえば、1: {0: (0.3333333333333333, 5, 0.0, True)}}では、State(1)にいて、0（左に行く）というアクションを取った場合、33％の確率でState(5)に行ってしまい、Reward=0.0で図の落とし穴に落ちて終了(Terminate＝True)、という内容です。
Action方向が左の場合、左・下・上には33％の確率で移動してしまいますが、逆の右には行かないようです。
Policy Evaluation
AgentのPolicyに基づきV(s)を計算し、Policyを評価するステップです。
まずは、Policyを全て０（左へ進め）とし、そのV(s)を計算してみましょう。計算式は、
$${V^\pi(s) = \sum_a \pi(a\mid s) \left[ r(s,a)+\gamma\sum_{s'\in S} p(s'\mid s,\pi(s))V^\pi(s') \right]}$$です。
$${ \pi(a\mid s)}$$は確率変数ですが、まずはPolicyは100%指定の方向へ移動するようにします。一方、$${p(s'\mid s,\pi(s))}$$は確率変数で、Action通りStateが変わらりません。つるつる滑っているイメージです。
それでは、この$${V^\pi(s)}$$を求めてみましょう。
import numpy as np
gamma = 0.9
diff = 1
i = 0
value_function = np.zeros(env.observation_space.n)
policy = np.zeros(env.observation_space.n)空のValue FunctionとPolicyを準備しました。
def policy_evaluation(policy):
diff = 1
i = 0
while diff > 0:
old_value_function = value_function.copy()
for s in range(env.observation_space.n):
rw = 0
fv = 0
for p in env.P[s][policy[s]]:
rw += p[0]*p[2]
fv += gamma*p[0]*value_function[p[1]]
value_function[s] = rw+fv
diff = np.max(np.abs(value_function - old_value_function))
i +=1
return value_functionやり方は、MRPと同じです。Policyがすべてゼロ（左移動）なので、RewardがあるState(15)には至らず、V(s)もすべてゼロで収束しました。
Policy Improvement
次に、より多くのV(s)を得られるようなPolicyを探すPolicy Improvementを考えます。つまり、
$${\pi^*(s) = argmax_\pi V^\pi(s)}$$となる最適な$${\pi}$$を探します。
そのために、新しいState-action value functionとしてQ functionを定義します。
$${Q^\pi(s,a)=R(s,a)+\gamma\sum_{s' \in S}p(s'\mid s,a)V^\pi(s')}$$先ほどの
$${V^\pi(s) = \sum_a \pi(a\mid s) \left[ r(s,a)+\gamma\sum_{s'\in S} p(s'\mid s,\pi(s))V^\pi(s') \right]}$$との違いは、sとaが変数として与えられているところです。
あとは、現在のPolicy$${\pi_i}$$の$${Q^{\pi_i}(s,a)}$$が最大となるactionを新しいPolicy$${\pi_{i+1}}$$として更新していきます。
def policy_improvement(value_function):
q_function = np.zeros([env.action_space.n])
for s in range(env.observation_space.n):
rw = np.zeros(env.action_space.n)
fv = np.zeros(env.action_space.n)
for a in range(env.action_space.n):
for p in env.P[s][a]:
rw[a] += p[0]*p[2]
fv[a] += gamma*p[0]*value_function[p[1]]
q_function[a] = rw[a]+fv[a]
policy[s] = np.argmax(q_function)
return policyこのPolicy ImprovementとPolicy Evaluationを収束するまで繰り返せば、最適なPolicyが得られます。
old_value_function = np.ones(env.observation_space.n)
i = 0
while np.max(np.abs(value_function - old_value_function)) > 0:
old_value_function = value_function.copy()
policy = policy_improvement(value_function)
value_function = policy_evaluation(policy)
i += 1
print(policy,i)[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0] 1
[0 1 2 3 0 0 0 0 0 1 0 0 0 1 2 0] 2
[1 2 2 3 0 0 0 0 1 1 0 0 0 2 1 0] 3
[0 3 2 3 0 0 0 0 3 1 0 0 0 2 1 0] 4
[0 3 0 3 0 0 0 0 3 1 0 0 0 2 1 0] 5
[0 3 0 3 0 0 0 0 3 1 0 0 0 2 1 0] 6
6回のIterationで収束し、$$\pi^*(s)$$が得られました。Agentは試行錯誤の末、[左、上、左、上、左、左、左、左、上、下、左、左、左、右、下、左]を選んだようです。
環境があれば、試行錯誤を通じて、最もRewardの高いPolicyをAgentが選んでくれる強化学習アルゴリズムの例でした。