からっぽのしょこ

読んだら書く！書いたら読む！同じ事は二度調べ(たく)ない

トップ > 攻略ノート > 3.5.1：ベルマン最適方程式の適用【ゼロつく4のノート】

3.5.1：ベルマン最適方程式の適用【ゼロつく4のノート】

攻略ノート 攻略ノート-ゼロつく4 強化学習 Python

はじめに

　『ゼロから作るDeep Learning 4 ――強化学習編』の独学時のまとめノートです。初学者の補助となるようにゼロつくシリーズの4巻の内容に解説を加えていきます。本と一緒に読んでください。

　この記事は、3.5.1節の内容です。ベルマン最適方程式の計算を確認します。

【前節の内容】

www.anarchive-beta.com

【他の記事一覧】

www.anarchive-beta.com

【この記事の内容】

3.5.1 ベルマン最適方程式の適用

　前節で導出した状態価値関数についてのベルマン最適方程式を使ってみます。ベルマン最適方程式については「3.4：ベルマン最適方程式【ゼロつく4のノート】 - からっぽのしょこ」を参照してください。

・問題設定の確認

　3.2.1項のときの2マスのグリッドワールド(図3-7)を考えます。問題設定の詳細については「3.2.1：状態価値関数のベルマン方程式の例【ゼロつく4のノート】 - からっぽのしょこ」を参照してください。

　状態価値関数のベルマン最適方程式は、次の式でした。

$$ v_{*}(s) = \max_a \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma v_{*}(s') \Bigr\} \tag{3.16} $$

　さらにこの例では、決定論的に状態が遷移するので、次の式になります。

$$ v_{*}(s) = \max_a \Bigl\{ r(s, a, s') + \gamma v_{*}(s') \Bigr\} \tag{3.18} $$


・状態価値関数の計算

　ベルマン最適方程式(3.18)の各項に具体的な数値を代入して、最適状態価値を計算します。

　割引率を$\gamma = 0.9$として、初期状態$s$がL1の場合を考えます。行動$a$がLeftのとき次の状態$s'$がL1、行動$a$がRightのとき次の状態$s'$がL2になるので、次のようになります。

$$ \begin{aligned} v_{*}(s = L1) &= \max_a \left\{ \begin{matrix} r(s = L1, a = \mathrm{Left}, s' = L1) + 0.9 v_{*}(s' = L1), \\ r(s = L1, a = \mathrm{Right}, s' = L2) + 0.9 v_{*}(s' = L2) \end{matrix} \right\} \\ &= \max_a \left\{ \begin{matrix} - 1 + 0.9 v_{*}(s' = L1), \\ 1 + 0.9 v_{*}(s' = L2) \end{matrix} \right\} \end{aligned} $$

　同様に、$s = L2$の場合を考えます。$a = \mathrm{Left}$のとき$s' = L1$、$a = \mathrm{Right}$のとき$s' = L2$なので、次のようになります。

$$ \begin{aligned} v_{*}(s = L2) &= \max_a \left\{ \begin{matrix} r(s = L2, a = \mathrm{Left}, s' = L1) + 0.9 v_{*}(s' = L1), \\ r(s = L2, a = \mathrm{Right}, s' = L2) + 0.9 v_{*}(s' = L2) \end{matrix} \right\} \\ &= \max_a \left\{ \begin{matrix} 0.9 v_{*}(s' = L1), \\ - 1 + 0.9 v_{*}(s' = L2) \end{matrix} \right\} \end{aligned} $$

　この連立方程式を解きます。え、どうやって解くの？

　とりあえず、全ての組み合わせを試すことにします。
　$v_{*}(L1)$の1つ目の式を整理すると

$$ \begin{align} & v_{*}(L1) = - 1 + 0.9 v_{*}(L1) \\ \Rightarrow & 0.1 v_{*}(L1) = - 1 \\ \Rightarrow & v_{*}(L1) = - 10 \tag{L1.1} \end{align} $$

となります。
　2つ目の式は

$$ \begin{align} & v_{*}(L1) = 1 + 0.9 v_{*}(L2) \\ \Rightarrow & v_{*}(L1) - 0.9 v_{*}(L2) = 1 \tag{L1.2} \end{align} $$

となります。

　同様に、$v_{*}(L2)$の1つ目の式を整理すると

$$ \begin{align} & v_{*}(L2) = 0.9 v_{*}(L1) \\ \Rightarrow & - 0.9 v_{*}(L1) + v_{*}(L2) = 0 \tag{L2.1} \end{align} $$

となります。
　2つ目の式は

$$ \begin{align} & v_{*}(L2) = - 1 + 0.9 v_{*}(L2) \\ \Rightarrow & 0.1 v_{*}(L2) = - 1 \\ \Rightarrow & v_{*}(L2) = - 10 \tag{L2.2} \end{align} $$

となります。

　それぞれの組み合わせで連立方程式を解きます。
　式(L1.1)と(L2.1)の場合は

$$ \begin{cases} v_{*}(L1) = - 10 &\quad (L1.1) \\ - 0.9 v_{*}(L1) + v_{*}(L2) = 0 &\quad (L2.1) \end{cases} $$

となるので、これを解くと

$$ \begin{cases} v_{*}(L1) = - 10 \\ v_{*}(L2) = - 9 \end{cases} $$

となります。

　式(L1.2)と(L2.1)の場合は

$$ \begin{cases} v_{*}(L1) - 0.9 v_{*}(L2) = 1 &\quad (L1.2) \\ - 0.9 v_{*}(L1) + v_{*}(L2) = 0 &\quad (L2.1) \end{cases} $$

となるので、これを解くと

$$ \begin{cases} v_{*}(L1) = 5.26316 \\ v_{*}(L2) = 4.73684 \end{cases} $$

となります。

　式(L1.1)と(L2.2)の場合は

$$ \begin{cases} v_{*}(L1) = - 10 &\quad (L1.1) \\ v_{*}(L2) = - 10 &\quad (L2.2) \\ \end{cases} $$

となります。

　式(L1.2)と(L2.2)の場合は

$$ \begin{cases} v_{*}(L1) - 0.9 v_{*}(L2) = 1 &\quad (L1.2) \\ v_{*}(L2) = - 10 &\quad (L2.2) \\ \end{cases} $$

となるので、これを解くと

$$ \begin{cases} v_{*}(L1) = - 8 \\ v_{*}(L2) = - 10 \end{cases} $$

となります。

　L1とL2それぞれの状態価値が最大となる組み合わせは、式(L1.2)と(L2.1)の場合でした。

$$ \begin{cases} v_{*}(L1) = 5.26316 \\ v_{*}(L2) = 4.73684 \end{cases} $$

　こうですか？分かりませんが、本の結果と一致したのでこれでよしとします。

・実験

　最後に、図3-7の設定に従って生成した報酬を使って収益を求めて、ベルマン最適方程式による状態価値関数の計算結果と比較します。(今後には影響しないので参考程度にしてください。)

　利用するライブラリを読み込みます。

# 利用するライブラリ
import numpy as np
import matplotlib.pyplot as plt


　繰り返し報酬を生成して、収益(累積割引報酬)を求めます。

# 試行回数(kの最大値)を指定
max_k = 100

# 割引率を指定
gamma = 0.9

# 状態の初期値を指定:(作図用)
S0 = 1

# 状態を初期化
s = S0

# 収益を初期化
G = 0

# 記録用のリストを初期化
trace_G = []

# 繰り返し試行
for k in range(max_k):
    # 現在の状態がL1の場合
    if s == 1:
        # 報酬を指定
        r_left, r_right = [-1.0, 1.0]
        
        # 最適(報酬が最大)な行動を選択
        a_idx = np.argmax([r_left, r_right])
        a = ['left', 'right'][a_idx]
        
        # 最適な行動による報酬を取得
        r = np.max([r_left, r_right])
        
        # 行動が左の場合:(壁にぶつかる場合)
        if a == 'left':
            # 何もしない
            pass
        
        # 行動が右の場合
        elif a == 'right':
            # 状態をL2に更新
            s = 2
    
    # 現在の状態がL2の場合
    elif s == 2:
         # 報酬を指定
        r_left, r_right = [0.0, -1.0]
        
        # 最適(報酬が最大)な行動を選択
        a_idx = np.argmax([r_left, r_right])
        a = ['left', 'right'][a_idx]
        
        # 最適な行動による報酬を取得
        r = np.max([r_left, r_right])
        
        # 行動が左の場合
        if a == 'left':
            # 状態をL1に更新
            s = 1
        
        # 行動が右の場合:(壁にぶつかる場合)
        elif a == 'right':
            # 何もしない
            pass
    
    # 収益を計算
    G += gamma**k * r
    
    # 値を記録
    trace_G.append(G)

# 最終結果を確認
print(G)

5.263018097900593

　現在の状態をsとします。エージェントのいるマスがL1であれば値が1、L2であれば2とします。
　エージェントの行動をaとします。左に行動する場合は値が'left'、右に行動する場合は'right'とします。

　状態sと行動aの値に応じて、if文で条件分けして処理します。
　報酬をr_left, r_rightとして値を指定します。r_left, r_rightの値が大きい方に行動する値(文字列)をaとします。また、r_left, r_rightの大きい方の値を取り出して報酬rとします。
　壁にぶつからずに移動できた場合は、sを更新(再代入)します。壁にぶつかる場合は、何もしないことをpassで明示していますが、これは最適な行動ではないため、そもそもこちらのケースは選択されません。

　最後に、割引率gammaを使って、報酬rを割り引いた値を収益Gに加算します。

　この処理をmax_k回繰り返します。

　収益の推移($k$と累積割引報酬の関係)をグラフで確認します。

# 真の最適状態価値を指定
true_v = 5.26

# x軸の値を作成
k_vals = np.arange(1, max_k+1)

# 実験結果を作図
plt.figure(figsize=(8, 6))
plt.plot(k_vals, trace_G, label='$G_t = \sum_k\ \gamma^k R_{t+k}$') # 収益の推移
plt.hlines(y=true_v, xmin=1, xmax=max_k+1, color='orange', linestyle='--', label='$v_{*}(s)$') # 真の状態価値
plt.xlabel('k')
plt.ylabel('value')
plt.suptitle('Bellman Optimality Equation', fontsize=20)
plt.title(
    '$v_{*}(L'+str(S0)+')='+str(true_v) + 
    ', V(L'+str(S0)+')='+str(np.round(trace_G[-1], 3)) + 
    ', \gamma='+str(gamma)+'$', 
    loc='left'
) # 状態価値関数の値
plt.grid()
plt.legend()
plt.show()

収益の推移

　収益(青色の実線)がベルマン最適方程式により求めた最適状態価値(オレンジ色の破線)に近付いていくのが分かります。3.2.1項でのベルマン方程式による状態価値の計算では確率的な処理を含みましたが、ベルマン最適方程式による計算では含みません。

　以上で、ベルマン最適方程式を確認しました。次項では、最適方策を確認します。

参考文献


おわりに

　ここでも行動価値関数の方のプログラムは省略です。
　で、maxが入った連立方程式はどうやって解けばいいんですか？これを解くのに動的計画法などが必要になるんですかね。

　投稿日前日に公開されたダンス動画をぜひ観て！

　ただでさえ良いのにシーズン7まで続いてくれてほんとありがたい企画です。

【次節の内容】

www.anarchive-beta.com