はじめに
前回までに強化学習を行う上で基礎的な知識となる、状態価値（$V^\pi(s）$および行動価値（$Q^\pi(s,a)$）を定義し、反復法による状態価値関数の推定を行いました。
今さら聞けない強化学習（1）：状態価値関数とBellman方程式
今さら聞けない強化学習（2）：状態価値関数の実装
今さら聞けない強化学習（3）：行動価値関数とBellman方程式
今さら聞けない強化学習（4）：行動価値関数の実装
今さら聞けない強化学習（5）：状態価値関数近似と方策評価
今回は、いよいよ価値関数から最適な方策を決定します。これで記事も一区切りです。
コードはgithubに公開しています。
最適方策
下図をもとに最適方策と価値関数の関係を説明します。
ある状態$s$が与えられた時、取り得る行動（黒丸）が4つに分岐しています。これらのどれが一番良い行動なのかを決めるのがこの章の目的です。
行動aをとった結果は、状態遷移確率$P^a_{ss'}$を経て、報酬$R^a_{ss'}$および次の状態の価値関数$V^\pi(s)$で表されます。それならば、なるべく多い報酬と次の状態の価値を持つものを最適な行動とするのが自然です。
すなわち、灰色で囲んだ黒丸以下のユニット$\sum_{s'}P^a_{ss'}[R^a_{ss'} + \gamma V^\pi(s')]$が最も高い行動が状態$s$での最適な方策$\pi’(s)$になります。
$$ \pi'(s) = arg\ max_a \sum_{s'}P^a_{ss'}[R^a_{ss'} + \gamma V^\pi(s')]$$
ただし、$arg\ max_a(x)$は、xが最大となるようなaを返す関数です。数式よりも図でイメージで理解した方が早いですね。
注
ここでは、最適な関数を決定論的な関数としています。つまり最適な関数なので、確率的な方策のように「$a_1$が90%, $a_2$が5%...」とするのではなく、「最適な関数は$a_1$」と断言しています。ただし、確率的な方策にも、今回の議論を当てはめることができます。（Sutton本 P.102にその記述があります。）
方策改善
ここまで学んできたことを整理しましょう。
- ある方策$\pi$があった時に、
- その方策に従ったときの状態の価値を求める （反復方策評価） ←前回の記事
- その状態での最適な方策(改善方策$\pi'$)を求める （方策改善） ←今回
改善された方策$\pi'$に従って新しい状態の価値を求めれば、それをもとにさらに方策を改善していくことができます。1-3のステップを次々と繰り返すことで、最適な状態と方策を求めることができます。
ここで、2のことを反復方策評価（Iterative policy evaluation）、3のことを方策改善(Policy improvement)といいます。2は状態価値を計算しているので価値評価なのかと思わなくもないのですが、「そのような状態を生み出す方策を評価するから」と覚えるようにします。1-3のステップを繰り返すことを方策反復と呼びます。
2自体が反復処理になっているので、それを反復する方策反復は反復の入れ子構造になっていることに注意します。。
方策反復
方策反復（前章の1-3の処理）のアルゴリズムを以下に示します。
1.初期化
すべての$s \in S$に対して$V(s) \in R$と$\pi(s) \in A(s)$ を任意に設定する
2.方策評価
$\Delta < \theta$（正の小さな値）になるまで繰り返し：
$\Delta \leftarrow 0 $
各$s \in S$について：
$v \leftarrow V(s) $
$V(s) \leftarrow \sum_{s'} P_{ss'}^{\pi(s)}[R_{ss'}^{\pi(s)} + \gamma V(s')]$
$\Delta \leftarrow max(\Delta, |v-V(s)|)$
3.方策改善
$policyStable \leftarrow true $
各 $s \in S$について：
$b \leftarrow \pi(s)$
$\pi(s) \leftarrow arg max_a \sum_{s'}P_{ss'}^a[R_{ss'}^a + \gamma V(s')]$
もし$b \neq \pi(s)$ならば，$policyStable \leftarrow false$
もしpolicyStableならは，終了；それ以外は，2から繰り返す
結果
方策反復を用いて得られた最適方策を示します。問題設定は過去の記事を参照してください。
Aにいるとどの行動をとっても10点なので、Aの最適行動（右）に意味はありません。Bも同様です。
Aに到達するようにうまく矢印が流れていますね。
一番右上のマスは下にいったほうがAに到達するのでそちらの方が最適な行動な気がするのですが、なぜ左なのかがよくわからないですね。（長く移動することによる罰則はないので）
反復終了の閾値が高かったのかもしれません。
実装
用いた実装を載せておきます。コードはgithubに公開しています。
N = 1000
GAMMA = 0.9
ACTIONS = ['right', 'up', 'left', 'down']
num_row = 5
num_col = 5
# 1.初期化
# Vの初期化
V = np.zeros((num_row, num_col))
# piの初期化
pi = np.random.randint(0,4,(5,5)) # 決定的な方策
V_trend = np.zeros((N, num_row, num_col))
pi_trend = np.zeros((N, num_row, num_col))
entire_count=0
policy_stable = False
while(policy_stable == False):
# 2.方策評価
print('entire count %d: ' % entire_count)
count = 0
while(True):
delta = 0
# 状態空間をスキャン
for i in range(num_row):
for j in range(num_col):
#print("delta %f" % delta)
v = V[i,j]
# 方策に従い行動を決定
action = ACTIONS[pi[i,j]]
agent.set_pos([i,j])
s = agent.get_pos()
# 行動を実行し次の状態に遷移
agent.move(action)
s_dash = agent.get_pos()
tmp = (agent.reward(s,action) + GAMMA * V[s_dash[0], s_dash[1]])
V[i,j] = tmp
delta = max(delta, abs(v - V[i,j]))
count += 1
if delta < 1.E-5:
break
V_trend[entire_count, :,:] = V
# 3.方策改善
b = pi.copy()
# 状態空間をスキャン
for i in range(num_row):
for j in range(num_col):
tmp = np.zeros(len(ACTIONS))
# 最適な行動を決定するため取り得る行動についてスキャン
for index, action in enumerate(ACTIONS):
agent.set_pos([i,j])
s = agent.get_pos()
# 行動を実行、次の状態に遷移
agent.move(action)
s_dash = agent.get_pos()
tmp[index] = agent.reward(s,action) + GAMMA*V[s_dash[0], s_dash[1]]
# 最適な行動を決定
pi[i,j] = np.argmax(tmp)
pi_trend[:entire_count,:,:] = pi
if(np.all(b==pi)):
policy_stable=True
print("policy_stable")
break
entire_count += 1
実装の方策反復に関する部分を抜粋しています。アルゴリズムにしたがって単純に実装してます。
終わりに
今回で、価値関数および最適方策に関する記事は一段落です。全6回とかなり長きに渡って書いてしまいました。
ただ、価値関数と状態遷移に対する基礎理解ができれば、これに続くモンテカルロ法やQ学習への理解がすんなりいくと思っています。実際に、文章に書くことにより、自分の中で不明だった点や要点が明確になってきました。そういった箇所は文章中で太字にしたり、図を用いてイメージで理解できるように心がけました。
引き続き、強化学習の基礎理論を進めていきたいと思います。次はモンテカルロ法を解説する予定です。Deepまでは遠い。。