2023.7.4 ゼロから作るDL4 動的計画法

反復方策評価（Iterative Policy Evaluation）

方策反復法 （Policy Iteration） : 方策改善定理、評価と改善を繰り返す

動的計画法：ボトムアップ、トップダウン（メモ化）

強化学習の主要なタスク：方策評価、方策制御、

ブートストラッピング、

共通部分

filename: common.py

code:python

import numpy as np

from collections import defaultdict

class GridWorld:

def __init__(self):

self.action_meaning = {

0: 'UP',

1: 'DOWN',

2: 'LEFT',

3: 'RIGHT'

}

self.reward_map = np.array(

)

self.goal_state = (0, 3)

self.wall_state = (1, 1)

self.start_state = (2, 0)

self.agent_state = self.start_state

def render_v(self):

pass

@property

def height(self):

return len(self.reward_map)

@property

def width(self):

@property

def shape(self):

return self.reward_map.shape

def actions(self):

return self.action_space

def states(self):

for h in range(self.height):

for w in range(self.width):

yield (h, w)

def next_state(self, state, action):

ny, nx = next_state

if nx < 0 or nx >= self.width or ny < 0 or ny >= self.height:

next_state = state

elif next_state == self.wall_state:

next_state = state

return next_state

def reward(self, state, action, next_state):

############################################

def eval_onestep(pi, V, env, gamma=0.9):

for state in env.states(): # 全state一巡

if state == env.goal_state:

continue # ゴールにおける方策は不要なので以下略

# 例：{0: 0.25, 1: 0.25, 2: 0.25, 3: 0.25}

new_V = 0

for action, action_prob in action_probs.items():

# action は行動 0, 1, 2, 3

# action_prob は各行動に対応する確率、総和は1

next_state = env.next_state(state, action) # 行動を獲得

# DPらしく全方向に向かって「次のstate」を求めている

r = env.reward(state, action, next_state)

# 全方向に移動した場合の、報酬を求めている

# 着目グリッドの価値関数を生成する、周囲のグリッドから確率の重

# pi(s'|s,a)*(r + \gamma*V(s'))

return V

def policy_eval(pi, V, env, gamma, threshold=0.001):

count = 0

while True:

count += 1

old_V = V.copy()

V = eval_onestep(pi, V, env, gamma)

delta = 0

for state in V.keys():

if delta < t:

delta = t

if delta < threshold:

break

print('policy_eval:', count)

return V

def argmax(d):

max_value = max(d.values())

max_key = 0

for key, value in d.items():

if value == max_value:

max_key = key

return max_key

def greedy_policy(V, env, gamma):

pi = {}

# 全ての状態に対して、各状態についての行動を2重ループで走査

# 状態の走査

for state in env.states():

action_values = {}

# 行動の走査

for action in env.actions():

# actionは 0, 1, 2, 3

# s'は全行動に対してチェックされる

next_state = env.next_state(state, action)

# そんで、s, a, s'からrを得る

r = env.reward(state, action, next_state)

# 状態価値関数は r + \gamma*V(s')

# sについて、a = 0, 1, 2, 3に対して価値が与えられる

# 最大の価値を有するアクションを決定

max_action = argmax(action_values)

action_probs = {0:0, 1:0, 2:0, 3:0}

# 最大のアクションだけを選択するように、確率1とする。

# そのような方策を pi に格納

return pi

反復方策評価

理解できると単純なことがわかる。

ダイクストラなどの経路探索法との違いを

filename: dp1_hanouku_housaku.py

code:python

'''

反復方策評価アルゴリム

* 各グリッドの状態価値関数を求める

* ボトムアップ方式のDP

'''

import numpy as np

import matplotlib.pyplot as plt

from collections import defaultdict

import common

env = common.GridWorld()

V = defaultdict(lambda: np.random.randn())

pi = defaultdict(lambda: {0:0.25, 1:0.25, 2:0.25, 3:0.25})

# 各方向ランダムに移動すると考えると確率は1/4なので

gamma = 0.9

threshold = 0.001

V = common.policy_eval(pi, V, env, gamma, threshold)

tmp = np.ndarray(env.reward_map.shape)

for k, v in V.items():

plt.imshow(tmp)

plt.show()

print(tmp)

方策反復法

filename: dp02_housaku_hanpuku.py

1. 方策 pi および状態価値関数 V(s) の初期値をそれぞれ以下のように設定する

4方向に対してランダムに移動する方策 pi(s) = {0:0.25, 1:0.25, 2:0.25, 3:0.25}

V(s) = 0

2. policy_eval を実行し、状態価値関数値を更新する。

$ V'(s) = \sum_{a, s'}\pi (a|s) p (s'|s, a) \{r(s,a,s') + \gamma V(s')\}

3. 更新された V(s) を用いて greedy な方策 pi を求める。

4. pi が更新されなくなるまで STEP 2 からの処理を繰り返す'

code:python

'''

import numpy as np

import matplotlib.pyplot as plt

from collections import defaultdict

import common

env = common.GridWorld()

pi = defaultdict(lambda: {0:0.25, 1:0.25, 2:0.25, 3:0.25})

V = defaultdict(lambda: 0)

gamma = 0.9

threshold = 0.0001

count = 0

while True:

count += 1

print('main:', count, end=' ')

V = common.policy_eval(pi, V, env, gamma, threshold)

new_pi = common.greedy_policy(V, env, gamma)

if new_pi == pi:

break

pi = new_pi

#

tmp = np.ndarray(env.reward_map.shape)

print(tmp)

for k, v in V.items():

plt.imshow(tmp)

plt.show()

tmp_pi = np.ndarray(env.reward_map.shape, dtype=object)

direct = {0:'^', 1:'v', 2:'<', 3:'>'}

for k, v in pi.items():

print(k, v)

print(tmp_pi)