強化学習を用いた迷路探索part2

プログラミング

記事を読む前に

強化学習を用いた迷路探索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_history
state_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_theta
new_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では価値反復法についての説明をします。

コメント

タイトルとURLをコピーしました