記事を読む前に
強化学習を用いた迷路探索part1では、強化学習を用いずに行ける方向に同確率で、ランダムに迷路を探索するアルゴリズムを作成しました。
本partでは、方策勾配法を用いて迷路を探索します。
方策勾配法とは
方策とは、物事を達成するための手立てのことです。
また、勾配法とは、最適化問題において、関数の勾配に関する情報を解の探索に用いるアルゴリズムの総称(wikipedia引用)
方策勾配法は、方策をパラメータを持った関数として定義し、方策の価値が最大となるパラメータを勾配法を用いて求める方法である。
パラメータθを持つ方策$π_θ$の価値を$J(θ)$とします。方策の価値の勾配を$∇_θJ(θ)$、学習率をαとすると、パラメータの更新式は次式のようになる。
$$θ_new = θ+ η∇_θJ(θ)$$
$∇_θJ(θ)$は以下の式で求めれます。
$$∇_θJ(θ) = 𝔼_π[∇_θlnπ_θ(a|s)Q^π_θ(s, a)]$$
これを方策勾配定理と呼びます。
s：状態
a：行動
Q：Q値
θ：方策πのパラメータ
また、本記事では、方策を求める際に、softmax関数を使用する。
ソフトマックス関数とは
ソフトマックス関数（ソフトマックスかんすう、softmax function）は、ロジスティック関数を多次元に拡張したもの。ネットワークの出力を確率分布に変換することができるので、ニューラルネットワークの最後の活性化関数としてよく用いられる。
wikipedia
数式
$$ y = \frac {e^{x_i}}{\sum_{k=1}^ne^{x_k}}$$
グラフ
迷路探索Pythonで実装
本記事で扱う迷路図を以下に記す。また、この迷路図はpart1で実装済みなので本記事では割愛します。
各座標における条件
# [上 右 下 左]
theta_0 = np.array([[np.nan, 1, 1, np.nan], #S0
[np.nan, np.nan, np.nan, 1], #S1
[np.nan, np.nan, 1, np.nan], #S2
[1, 1, 1, np.nan], #S3
[np.nan, 1, np.nan, 1], #S4
[1, np.nan, np.nan, 1], #S5
[1, 1, np.nan, np.nan], #S6
[np.nan, 1, np.nan, 1], #S7
])進める場合は1、進めない場合はnp.nanとする。
条件に基づき各方向へ進める確率を算出
def softmax_convert_into_pi_from_theta(theta):
beta = 1.0
[m, n] = theta.shape
# 進む方向の確率を保持する変数piを作成
pi = np.zeros((m, n))
exp_theta = np.exp(beta * theta)
# S0~S7までの1行ずつソフトマックス関数に適応する
for i in range(0, m):
pi[i, :] = exp_theta[i, :] / np.nansum(exp_theta[i, :])
pi = np.nan_to_num(pi) # 欠損地を0に置換
return pi
pi = softmax_convert_into_pi_from_theta(theta_0)
print(pi)実行結果
[[0. 0.5 0.5 0. ]
[0. 0. 0. 1. ]
[0. 0. 1. 0. ]
[0.33333333 0.33333333 0.33333333 0. ]
[0. 0.5 0. 0.5 ]
[0.5 0. 0. 0.5 ]
[0.5 0.5 0. 0. ]
[0. 0.5 0. 0.5 ]]方策$π_θ(s,a)$に従って、行動させる関数を定義
あくまで、方策に従って行動するので、以下のコードで学習しているわけではないです。
def get_action_and_next_s(pi, s):
direction = ["up", "right", "down", "left"]
next_direction = np.random.choice(direction, p = pi[s, :]) # 次の行動をランダムで選ぶ
# 選んだ行動に応じて次のマスへ進む
if next_direction == "up":
action = 0
s_next = s - 3
elif next_direction == "right":
action = 1
s_next = s + 1
elif next_direction == "down":
action = 2
s_next = s + 3
elif next_direction == "left":
action = 3
s_next = s - 1
return [action, s_next]ゴールまでのプロセスを表示する関数の定義&表示
def goal_maze_state_action(pi):
s = 0
state_action_history = [[0, np.nan]]
while (1):
[action, next_s] = get_action_and_next_s(pi, s)
state_action_history[-1][1] = action
state_action_history.append([next_s, np.nan])
if next_s == 8:
break
else:
s = next_s
return state_action_historystate_action_history = goal_maze_state_action(pi)
print(state_action_history)
print("迷路を解くのにかかったステップ数は" + str(len(state_action_history) - 1) + "です")実行結果
#[今いる場所, 進む方向]
[[0, 1], [1, 3], [0, 1], [1, 3], [0, 1], [1, 3], [0, 2], [3, 1], [4, 3], [3, 0], [0, 1], [1, 3], [0, 2], [3, 0], [0, 2], [3, 0], [0, 1], [1, 3], [0, 1], [1, 3], [0, 2], [3, 0], [0, 1], [1, 3], [0, 2], [3, 2], [6, 1], [7, 3], [6, 1], [7, 1], [8, nan]]
迷路を解くのにかかったステップ数は30です方策勾配法に従って方策を更新
方策勾配法とはで触れた数式に従い$θ_new$の更新を行う関数を定義する
def updata_theta(theta, pi, state_action_history):
eta = 0.1 # 学習率
T = len(state_action_history)
[m, n] = theta.shape
delta_theta = theta.copy()
for i in range(0, m):
for j in range(0, n):
if not(np.isnan(theta[i, j])):
SA_i = [SA for SA in state_action_history if SA == i]
SA_ij = [SA for SA in state_action_history if SA == [i, j]]
N_i = len(SA_i)
N_ij = len(SA_ij)
delta_theta[i, j] = (N_ij - pi[i, j] + N_i) / T
new_theta = theta + eta * delta_theta
return new_thetanew_theta = updata_theta(theta_0, pi, state_action_history)
pi = softmax_convert_into_pi_from_theta(new_theta)
print(pi)実行結果
[[0. 0.5016129 0.4983871 0. ]
[0. 0. 0. 1. ]
[0. 0. 1. 0. ]
[0.33548733 0.33225634 0.33225634 0. ]
[0. 0.49919355 0. 0.50080645]
[0.5 0. 0. 0.5 ]
[0.4983871 0.5016129 0. 0. ]
[0. 0.5 0. 0.5 ]]何をしているか簡単に説明すると、スタート位置からゴールまでの道順を記憶しておいて、各座標における条件の確率を更新しているということになります。
要は、ランダムで進む場所を選んでいたとはいえ、よく進んだ方向がゴールに近いんじゃないか！ってことでその方向の確率を上げとこうって話です。
学習によりゴールまでの道のりを最適化
さて、あとは今までのコードを組み合わせて学習を行い、ゴールまでのプロセスの最適解を算出します
stop_epsilon = 10**-4
theta = theta_0 # 各座標における初期値条件
pi = pi_0 # 各座標における初期確率
is_continue = True
count = 1
# いわゆる学習
while is_continue:
state_action_history = goal_maze_state_action(probability) # ゴールまでの道のりを記録
new_theta = updata_theta(theta, pi, state_action_history) # 方策の更新
new_pi = softmax_convert_into_pi_from_theta(new_theta) # 確率を更新
print(np.sum(np.abs(new_pi - pi))) # 前回の確率と更新した確率を比較
print("迷路を解くのにかかったステップ数は" + str(len(state_action_history) - 1) + "です。")
if np.sum(np.abs(new_pi - pi)) < stop_epsilon: # 更新の変化がstop_epsilon以下になったら終了
is_continue = False
else: # 終わるまで繰り返す
theta = new_theta
pi = new_pi実行結果
........
0.00010013600373691596
迷路を解くのにかかったステップ数は4です。
9.989463211836427e-05
迷路を解くのにかかったステップ数は4です。
# 終了最終的な方策
np.set_printoptions(precision = 3, suppress = True) # 有効数字の設定
print(pi)[[0. 0.016 0.984 0. ]
[0. 0. 0. 1. ]
[0. 0. 1. 0. ]
[0.01 0.01 0.98 0. ]
[0. 0.5 0. 0.5 ]
[0.499 0. 0. 0.501]
[0.011 0.989 0. 0. ]
[0. 0.979 0. 0.021]]ゴールまでの道のり
from matplotlib import animation
from IPython.display import HTML
def init():
line.set_data([], [])
return (line, )
def animate(i):
state = state_action_history[i][0]
x = (state % 3) + 0.5
y = 2.5 - int(state / 3)
line.set_data(x, y)
return (line,)
anim = animation.FuncAnimation(fig, animate, init_func=init, frames = len(state_action_history), interval=200, repeat=False)
HTML(anim.to_jshtml())実行結果
以上で本記事は終わりです。
Part3では価値反復法についての説明をします。
コメント