##記事の内容

強化学習によって、迷路を解く。
####どんな人に向いている記事か？
・強化学習の基礎、用語はなんとなくわかったから、実際に何かを実装したい

こんな人向けに、今回は迷路を強化学習で解いてみます。強化学習の柱である**「方策」**が実際にどう変化しているのかチェックしているので、注目してみてください。強化学習の各概念の定義と紹介は、この記事ではふわっとしたものにとどめています。

####強化学習入門のハードルの高さ
機械学習への入門は、どんどん手軽になってきています。しかし、強化学習の勉強はややハードルが高いです。
なぜでしょうか？
それは、気軽に実装しにくいからです。強化学習では、環境を構築してあげる必要があります。今回の例でいうならば「迷路」です。
他にも、あるゲームを強化学習させるならゲームの環境構築からスタートしなければなりません。
環境から実装しなければならないという点が難しい理由です。そして、個々の環境に合わせて強化学習のロジック設計も調整してあげる必要があります。
強化学習の本質である理論の部分に集中する前に、コーディングにおいて考えなければならない箇所がたくさん生じてしまいます。

ですので、入門者の方は、自分が今どの部分を勉強しようとしているのか意識してみてください。
今回の記事では、環境が迷路、強化学習の本質である学習アルゴリズムはQ学習です。

####今回解く迷路
自分で想定してみた迷路は次の通りです。この迷路に強化学習でアプローチします。

##「方策」設定フェーズ
強化学習を勉強すると出てくる単語が「方策」です。方策は、エージェントがどのように動くべきか書いてあるルールのようなものです。もちろん、エージェントは最初どのように動けばいいのかわかりません。学習した方策をもっていないからです。どのように行動するのが目標達成のために最適なのか学習するのが強化学習といってもいいでしょう。つまり、最適な方策を作ること、これが強化学習の目標です。目標達成のための最適な戦略、これが方策だとイメージするといいかもしれません。

「パラメータθに従い、状態sの時に行動aをとる」というように、方策は定義されます。最初は、適当な方策を定義しておきます。
今回は解く迷路に合わせて、表形式表現の方策にします。そのために、まずはパラメータを定義します。

# 初期の方策を決定するパラメータtheta_0を設定
# 行は状態0～14、列は移動方向↑、→、↓、←を表す　
# np.nanは移動できない方向のこと
theta_0 = np.array([[np.nan, 1, np.nan, np.nan],  # 0 
                    [np.nan, 1, np.nan,1],  # 1
                    [np.nan, 1, 1, 1],  # 2
                    [np.nan,np.nan,1,1],  # 3
                    
                    [np.nan, 1, 1, np.nan],  # 4
                    [np.nan, np.nan, 1, 1],  # s5
                    [1,1,1,np.nan],  # s6
                    [1, np.nan, np.nan,1],  #7
                    
                    [1,1,1,np.nan], #8
                    [1,1, np.nan,1], #9
                    [1, np.nan, np.nan, 1], #10
                    [np.nan,np.nan,1,np.nan], #11
                    
                    [1,1,np.nan,np.nan], #12
                    [np.nan,1,np.nan,1], #13
                    [np.nan,1,np.nan,1], #14
                    ])

このパラメータをもとに、状態sのときに行動aをとることを表現する方策を作ります。ある行動をとるべきだということをあらわすために、確率に帰着させます。
「最適な行動＝その行動をとる確率が大きい」
と表現するわけです。

パラメータをもとに初期の方策を確率で表現してみましょう。

# 方策パラメータtheta_0を方策piに変換する

def simple_convert_into_pi_from_theta(theta): #単純に割合を求める

    [m, n] = theta.shape  # thetaの行列サイズを取得
    pi = np.zeros((m, n))
    for i in range(0, m):
        pi[i, :] = theta[i, :] / np.nansum(theta[i, :])  # 割合の計算

    pi = np.nan_to_num(pi)  # nanを0に変換

    return pi

# 行動方策pi_0を求める
pi_0 = simple_convert_into_pi_from_theta(theta_0)

pi_0の中身を見てみると、初期の方策が確認できます。ちゃんと確率になっていますね。

[[0.         1.         0.         0.        ]
 [0.         0.5        0.         0.5       ]
 [0.         0.33333333 0.33333333 0.33333333]
 [0.         0.         0.5        0.5       ]
 [0.         0.5        0.5        0.        ]
 [0.         0.         0.5        0.5       ]
 [0.33333333 0.33333333 0.33333333 0.        ]
 [0.5        0.         0.         0.5       ]
 [0.33333333 0.33333333 0.33333333 0.        ]
 [0.33333333 0.33333333 0.         0.33333333]
 [0.5        0.         0.         0.5       ]
 [0.         0.         1.         0.        ]
 [0.5        0.5        0.         0.        ]
 [0.         0.5        0.         0.5       ]
 [0.         0.5        0.         0.5       ]]

現在では、適当な方策になっています。学習することによって、目標達成のための最適な行動をとる確率を求めていくのが強化学習です。学習し終わったあとの方策の変化に注目してみてください。

##学習フェーズ　報酬と行動価値関数
今回は価値反復法を使います。ゴールから逆算して、ゴール以外の位置にも価値をつける方法です。

行動価値・・・ゴールにつながるような行動をすれば報酬をもらえる
というイメージです。

それでは、さきほど設定した初期の方策をもとに価値関数を準備します。

#初期の適当な行動価値関数を表形式表現で設定
#行が状態s、列が行動a

[a, b] = theta_0.shape  # 行と列の数をa, bに格納
Q = np.random.rand(a, b) * theta_0 * 0.1
# *theta0をすることで要素ごとに掛け算をし、Qの壁方向の値がnanになる

実際に価値関数の中身を確認します。Q学習で更新した後に、どのように変化するのかチェックしてみてください。


[[       nan 0.01795809        nan        nan]
 [       nan 0.0859586         nan 0.07551988]
 [       nan 0.00700877 0.09546995 0.07051601]
 [       nan        nan 0.08008534 0.02308839]
 [       nan 0.00508086 0.06546547        nan]
 [       nan        nan 0.01404905 0.09351654]
 [0.05976642 0.04505335 0.02963649        nan]
 [0.06548684        nan        nan 0.02702707]
 [0.0574676  0.09419638 0.04148861        nan]
 [0.0442088  0.0435865         nan 0.02932538]
 [0.05559397        nan        nan 0.0017236 ]
 [       nan        nan 0.0967847         nan]
 [0.01776322 0.0497807         nan        nan]
 [       nan 0.09162495        nan 0.03189324]
 [       nan 0.05184677        nan 0.03070013]]

###ε-greegy法で方策を設定
行動価値関数を方策に反映させたい。しかし、今は初期状態で適当な値です。そこで、ある確率εでランダムに行動し、残りの1-εの確率で行動価値Qが最大になる行動を選ぶようにする。この方法が、ε-greegy法です。

自分が解きたい迷路に合わせて、行動と状態を定義するのに注意します。迷路の図をイメージしながらコードを見てみてください。

# ε-greedy法を実装

def get_action(s, Q, epsilon, pi_0):
    direction = ["up", "right", "down", "left"]

    # 行動を決める
    if np.random.rand() < epsilon:
        # εの確率でランダムに動く
        next_direction = np.random.choice(direction, p=pi_0[s, :])
    else:
        # Qの最大値の行動を採用する
        next_direction = direction[np.nanargmax(Q[s, :])]

    # 行動をindexに
    if next_direction == "up":
        action = 0
    elif next_direction == "right":
        action = 1
    elif next_direction == "down":
        action = 2
    elif next_direction == "left":
        action = 3

    return action


def get_s_next(s, a, Q, epsilon, pi_0):
    direction = ["up", "right", "down", "left"]
    next_direction = direction[a]  # 行動aの方向

    # 行動から次の状態を決める
    if next_direction == "up":
        s_next = s - 4  # 上に移動するときは状態の数字が3小さくなる
    elif next_direction == "right":
        s_next = s + 1  # 右に移動するときは状態の数字が1大きくなる
    elif next_direction == "down":
        s_next = s + 4  # 下に移動するときは状態の数字が3大きくなる
    elif next_direction == "left":
        s_next = s - 1  # 左に移動するときは状態の数字が1小さくなる

    return s_next

##Q学習の実装　Sarsaとの違いに注意
行動価値関数Qをどうやって更新するか？今回は、Q学習で行います。

$$Q(s, a) ← Q(s, a) + \alpha[r' + \gamma , max_{a'} Q(s', a') - Q(s, a)]　$$
式のイメージは次のようなものです。

Q(前の状態、行動)= (1 - 学習率) × Q(前の状態、行動) + 学習率 × (報酬 + 割引率 × 今の状態で一番大きいQ)

####Q学習とSarsa法との違いはなにか？
ここで私自身、混乱したポイントがあります。それは、強化学習の核である学習アルゴリズムのSarsa法とQ学習の違いが分かりにくいという点です。
Sarsaは方策に依存する方法、Q学習は方策に依存しない方法と説明されます。しかし、コードをみればわかるとおり、Q学習でも方策に従って行動を決めています。
どういうことなのでしょうか？

それは、Q学習の更新式のなかに登場する行動選択と、実際にエージェントがとる行動は同じではないということです。Q学習の更新式では、「今の状態で一番大きいQ」＝行動選択を常に利用します。しかし、これと実際の行動選択とは別です。実際にエージェントが動く次の行動を選択することは、Q学習でQを更新する前に、更新前のQに依存した方策により決定されます。

つまり、実際に次にとる行動とは独立にQは更新されます。
だから、Q学習は方策オフ型と呼ばれます。
この混乱は、「方策」という概念の理解の曖昧さのせいでしょうか。
方策を、**「エージェントが実際に行動する方向の決め方」**であるとイメージしなおした方がいいかもしれません。

一方、Q学習とは異なり、Sarsa法では「エージェントが実際に行動する方向」に依存してQを更新します。

Q学習とSarsa法の本質的な違いをつかめたでしょうか？

# Q学習による行動価値関数Qの更新

def Q_learning(s, a, r, s_next, Q, eta, gamma):#Sarsaと違い「次の行動」を更新に使用しない⇒方策に依存しない

    if s_next == 15:  # ゴールした場合
        Q[s, a] = Q[s, a] + eta * (r - Q[s, a]) #今が最終状態のときは、「今の状態で一番大きいQ」はゼロ

    else:  #更新式
        Q[s, a] = Q[s, a] + eta * (r + gamma * np.nanmax(Q[s_next,: ]) - Q[s, a])

    return Q

それでは実際に、Q学習で迷路を解いていきましょう。

# Q学習で迷路を解く関数の定義、状態と行動の履歴および更新したQを出力

def goal_maze_ret_s_a_Q(Q, epsilon, eta, gamma, pi):
    s = 0  # スタート地点
    a = a_next = get_action(s, Q, epsilon, pi)  # 初期の行動
    s_a_history = [[0, np.nan]]  # エージェントの移動を記録するリスト

    while (1):  # ゴールするまでループ
        a = a_next  # 行動更新

        s_a_history[-1][1] = a
        # 現在の状態（つまり一番最後なのでindex=-1）に行動を代入

        s_next = get_s_next(s, a, Q, epsilon, pi)
        # 次の状態を格納

        s_a_history.append([s_next, np.nan])
        # 次の状態を代入。行動はまだ分からないのでnanにしておく

        # 報酬を与え,　次の行動を求めます
        if s_next == 15:
            r = 1  # ゴールにたどり着いたなら報酬を与える
            a_next = np.nan
        else:
            r = 0
            a_next = get_action(s_next, Q, epsilon, pi)
            # 次の行動a_nextを求めます。

        # 価値関数を更新
        Q = Q_learning(s, a, r, s_next, Q, eta, gamma)

        # 終了判定
        if s_next == 15:  # ゴール地点なら終了
            break
        else:
            s = s_next
            

    return [s_a_history, Q]

# Q学習で迷路を解く

eta = 0.1  # 学習率
gamma = 0.9  # 時間割引率
epsilon = 0.5  # ε-greedy法の初期値
is_continue = True
episode = 1


while is_continue:  # is_continueがFalseになるまで繰り返す
    print("エピソード:" + str(episode))

    # ε-greedyの値を少しずつ小さくする
    epsilon = epsilon / 2

    # Q学習で迷路を解き、移動した履歴と更新したQを求める
    [s_a_history, Q] = goal_maze_ret_s_a_Q(Q, epsilon, eta, gamma, pi_0)

    print("迷路を解くのにかかったステップ数は" + str(len(s_a_history) - 1) + "です")

    # 100エピソード繰り返す
    episode = episode + 1
    if episode > 100:
        break

##方策の変化は？
それでは、学習させた後の方策を見てみましょう。今回でいうならば、学習した価値関数の値になります。価値が最大な方向にエージェントが行動するのが、この迷路を解く最適な方法だとわかったのです。

「教師あり学習」「教師なし学習」とも違う「強化学習」のイメージをつかめたでしょうか？

[[       nan 0.22308601        nan        nan]
 [       nan 0.30086234        nan 0.01772575]
 [       nan 0.02956487 0.38606621 0.02953981]
 [       nan        nan 0.02881941 0.02880064]
 [       nan 0.03886425 0.03883072        nan]
 [       nan        nan 0.03966321 0.0399114 ]
 [0.03077404 0.03101214 0.4733773         nan]
 [0.02834202        nan        nan 0.02623401]
 [0.03791642 0.03758315 0.72375069        nan]
 [0.02955659 0.03319108        nan 0.64172525]
 [0.03742338        nan        nan 0.55891861]
 [       nan        nan 0.03311604        nan]
 [0.03882683 0.80856136        nan        nan]
 [       nan 0.89973738        nan 0.03944373]
 [       nan 0.99997608        nan 0.0795919 ]]

##参考文献
今回のコードのおおよそは、次の本を参考にしています。初心者でも学べるいい本です。
つくりながら学ぶ! 深層強化学習 ~PyTorchによる実践プログラミング~

Q学習の基本的な流れは、こちらがわかりやすくておすすめ。
Q学習_Q-Learning(Vol.12)

Q学習とSarsa法の違いについてはこちらがおすすめ。
今さら聞けない強化学習（10）: SarsaとQ学習の違い

強化学習の基本と本質をつかむためには次の記事がおすすめ。「価値」とはどのように定義されるのか。
【強化学習の本質入門】「価値」ってなに？「将来に対する平均」ってなに？