からっぽのしょこ

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

3.2.1:状態価値関数のベルマン方程式の例【ゼロつく4のノート】

はじめに

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

 この記事は、3.2.1節の内容です。状態価値関数についてのベルマン方程式の計算を確認します。

【前節の内容】

www.anarchive-beta.com

【他の記事一覧】

www.anarchive-beta.com

【この記事の内容】

3.2.1 状態価値関数のベルマン方程式の例

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

・問題設定の確認

 まずは、環境とエージェントの設定を確認します。簡単な例として、2マスのグリッドワールド(図3-7)を考えます。

 状態価値関数についてのベルマン方程式は、次の式でした。

$$ v_{\pi}(s) = \sum_a \pi(a | s) \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma v_{\pi}(s') \Bigr\} \tag{3.7} $$

 実際にこの計算をするために、環境とエージェントを定義します。

 エージェントがいるマスを状態$s$で表します。$s$は、L1かL2の値を取ります。これを$s \in \{L1, L2\}$で表します。
 エージェントの行動を$a$で表します。エージェントは、左(Left)または右(Right)に行動します。これを$a \in \{\mathrm{Left}, \mathrm{Right}\}$で表します。
 エージェントが行動すると、エージェントがいるマスが変わります(状態が遷移します)。ただし、「L1マスから左」または「L2マスから右」に行動しようとすると、壁にぶつかりエージェントは移動しません(状態はそのままです)。行動後のマス(次の状態)を$s'$で表します。2つのマス自体は変わらないので、$s' \in \{L1, L2\}$です。マスの移動がない場合も状態が遷移すると表現します。

 よって、ベルマン方程式は、次のようになります。

$$ v_{\pi}(s) = \sum_{a \in \{\mathrm{Left}, \mathrm{Right}\}} \pi(a | s) \sum_{s' \in \{L1, L2\}} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma v_{\pi}(s') \Bigr\} $$

 続いて、確率的方策・状態遷移確率・報酬関数の設定を確認していきます。

・確率論的方策の設定

 エージェントは等確率でランダムに行動することとします。

 LeftかRightが等確率で決まるので、状態$s$がL1のとき(エージェントがL1マスにいるとき)の方策を、次の式で表します。

$$ \begin{aligned} p(a = \mathrm{Left} | s = L1) &= 0.5 \\ p(a = \mathrm{Right} | s = L1) &= 0.5 \end{aligned} $$

 状態$s$がL2の場合も同様です。

$$ \begin{aligned} p(a = \mathrm{Left} | s = L2) &= 0.5 \\ p(a = \mathrm{Right} | s = L2) &= 0.5 \end{aligned} $$

 各ノードから枝分かれするエッジの確率の和が1になります。(この例では分岐しませんが)状態遷移確率についても同様です。

・状態遷移確率の設定

 状態は決定論的に遷移することとします。つまり、元の状態と行動から1つの状態に決まります。

 元の状態$s$がL1で行動$a$がLeftのとき(L1マスから左に行動するとき)の遷移確率を、次の式で表します。

$$ \begin{aligned} p(s' = L1 | s = L1, a = \mathrm{Left}) &= 1 \\ p(s' = L2 | s = L1, a = \mathrm{Left}) &= 0 \end{aligned} $$

 L1マスから左に行動すると、常に壁にぶつかりL1マスのままであることを確率1で、L2マスに移動しないことを確率0で表しています。

 行動$a$がRightのとき(L1マスから右に行動するとき)の遷移確率は、次のように表します。

$$ \begin{aligned} p(s' = L1 | s = L1, a = \mathrm{Right}) &= 0 \\ p(s' = L2 | s = L1, a = \mathrm{Right}) &= 1 \end{aligned} $$

 常にL2マスに移動することを確率1で、L1マスのままにならないことを確率0で表します。

 元の状態がL2の場合も同様です。

$$ \begin{aligned} p(s' = L1 | s = L2, a = \mathrm{Left}) &= 1 \\ p(s' = L2 | s = L2, a = \mathrm{Left}) &= 0 \\ p(s' = L1 | s = L2, a = \mathrm{Right}) &= 0 \\ p(s' = L2 | s = L2, a = \mathrm{Right}) &= 1 \end{aligned} $$


・報酬関数の設定

 状態がL1からL2に遷移する(L1マスからL2マスに移動する)とき、リンゴが得られるので、報酬を1とします。L2からL1に遷移する場合は、何も起きないので、報酬は0です。また、壁にぶつかり状態が遷移しないとき、報酬を-1とします。

 それぞれ次の式で表します。

$$ \begin{aligned} r(s = L1, a = \mathrm{Left}, s' = L1) &= -1 \\ r(s = L1, a = \mathrm{Right}, s' = L2) &= 1 \\ r(s = L2, a = \mathrm{Left}, s' = L1) &= 0 \\ r(s = L2, a = \mathrm{Right}, s' = L2) &= -1 \end{aligned} $$


・状態価値関数の計算

 問題設定を確認できたので、状態価値関数を計算します。

・L1の状態価値

 初期状態$s$がL1の場合を考えます。

$$ v_{\pi}(s = L1) = \sum_{a \in \{\mathrm{Left}, \mathrm{Right}\}} \pi(a | s = L1) \sum_{s' \in \{L1, L2\}} p(s' | s = L1, a) \Bigl\{ r(s = L1, a, s') + \gamma v_{\pi}(s') \Bigr\} $$

 次の状態$s'$に関する総和$\sum_{s'}$を展開します。

$$ \begin{aligned} v_{\pi}(s = L1) &= \sum_{a \in \{\mathrm{Left}, \mathrm{Right}\}} \pi(a | s = L1) \Bigl[ p(s' = L1 | s = L1, a) \Bigl\{ r(s = L1, a, s' = L1) + \gamma v_{\pi}(s' = L1) \Bigr\} \Bigr. \\ &\qquad \qquad \qquad \Bigl. + p(s' = L2 | s = L1, a) \Bigl\{ r(s = L1, a, s' = L2) + \gamma v_{\pi}(s' = L2) \Bigr\} \Bigr] \end{aligned} $$

 $s' = L1$の場合と$s' = L2$の場合の和を求めます。

 さらに、行動$a$に関する総和$\sum_a$を展開します。

$$ \begin{aligned} v_{\pi}(s = L1) &= \pi(a = \mathrm{Left} | s = L1) \Bigl[ p(s' = L1 | s = L1, a = \mathrm{Left}) \Bigl\{ r(s = L1, a = \mathrm{Left}, s' = L1) + \gamma v_{\pi}(s' = L1) \Bigr\} \Bigr. \\ &\qquad \qquad \qquad \Bigl. + p(s' = L2 | s = L1, a = \mathrm{Left}) \Bigl\{ r(s = L1, a = \mathrm{Left}, s' = L2) + \gamma v_{\pi}(s' = L2) \Bigr\} \Bigr] \\ &\quad + \pi(a = \mathrm{Right} | s = L1) \Bigl[ p(s' = L1 | s = L1, a = \mathrm{Right}) \Bigl\{ r(s = L1, a = \mathrm{Right}, s' = L1) + \gamma v_{\pi}(s' = L1) \Bigr\} \Bigr. \\ &\qquad \qquad \qquad \Bigl. + p(s' = L2 | s = L1, a = \mathrm{Right}) \Bigl\{ r(s = L1, a = \mathrm{Right}, s' = L2) + \gamma v_{\pi}(s' = L2) \Bigr\} \Bigr] \end{aligned} $$

 $a = \mathrm{Left}$の場合と$a = \mathrm{Right}$の場合の和を求めます。

 状態遷移確率$p(s' | s, a)$に具体的な値を代入します。

$$ \begin{aligned} v_{\pi}(s = L1) &= \pi(a = \mathrm{Left} | s = L1) \Bigl[ 1 \Bigl\{ r(s = L1, a = \mathrm{Left}, s' = L1) + \gamma v_{\pi}(s' = L1) \Bigr\} \Bigr. \\ &\qquad \qquad \qquad \Bigl. + 0 \Bigl\{ r(s = L1, a = \mathrm{Left}, s' = L2) + \gamma v_{\pi}(s' = L2) \Bigr\} \Bigr] \\ &\quad + \pi(a = \mathrm{Right} | s = L1) \Bigl[ 0 \Bigl\{ r(s = L1, a = \mathrm{Right}, s' = L1) + \gamma v_{\pi}(s' = L1) \Bigr\} \Bigr. \\ &\qquad \qquad \qquad \Bigl. + 1 \Bigl\{ r(s = L1, a = \mathrm{Right}, s' = L2) + \gamma v_{\pi}(s' = L2) \Bigr\} \Bigr] \\ &= \pi(a = \mathrm{Left} | s = L1) \Bigl\{ r(s = L1, a = \mathrm{Left}, s' = L1) + \gamma v_{\pi}(s' = L1) \Bigr\} \\ &\quad + \pi(a = \mathrm{Right} | s = L1) \Bigl\{ r(s = L1, a = \mathrm{Right}, s' = L2) + \gamma v_{\pi}(s' = L2) \Bigr\} \end{aligned} $$

 決定論的に遷移するので、それぞれ1つの項のみが1でそれ以外の項は0になります。そのため、確率が1の項を取り出せば、$s'$についての総和の計算が不要なことが分かります。

 確率的方策$\pi(a | s)$と報酬関数$r(s, a, s')$にも具体的な値を代入します。

$$ v_{\pi}(s = L1) = 0.5 \Bigl\{ - 1 + \gamma v_{\pi}(s' = L1) \Bigr\} + 0.5 \Bigl\{ 1 + \gamma v_{\pi}(s' = L2) \Bigr\} $$

 割引率を$\gamma = 0.9$とします。

$$ \begin{aligned} v_{\pi}(s = L1) &= 0.5 \Bigl\{ - 1 + 0.9 v_{\pi}(s' = L1) \Bigr\} + 0.5 \Bigl\{ 1 + 0.9 v_{\pi}(s' = L2) \Bigr\} \\ &= 0.45 v_{\pi}(s' = L1) + 0.45 v_{\pi}(s' = L2) \end{aligned} $$

 左辺の項を右辺に移項し(て、さらに左辺と右辺を入れ替え)ます。

$$ - 0.55 v_{\pi}(s' = L1) + 0.45 v_{\pi}(s' = L2) = 0 \tag{3.9} $$


・L2の状態価値

 続いて、初期状態$s$がL2の場合を考えます。状態遷移確率と$s'$の総和の計算が不要なことを確認したので、省略した次の式で計算します。

$$ v_{\pi}(s = L2) = \sum_{a \in \{\mathrm{Left}, \mathrm{Right}\}} \pi(a | s = L2) \Bigl\{ r(s = L2, a, s') + \gamma v_{\pi}(s') \Bigr\} $$

 先ほどと同様に、$\sum_{a \in \{\mathrm{Left}, \mathrm{Right}\}}$を展開して、具体的な値を代入して、式を整理します。

$$ \begin{aligned} v_{\pi}(s = L2) &= \pi(a = \mathrm{Left} | s = L2) \Bigl\{ r(s = L2, a = \mathrm{Left}, s' = L1) + 0.9 v_{\pi}(s' = L1) \Bigr\} \\ &\quad + \pi(a = \mathrm{Right} | s = L2) \Bigl\{ r(s = L2, a = \mathrm{Right}, s' = L2) + 0.9 v_{\pi}(s' = L2) \Bigr\} \\ &= 0.5 \Bigl\{ 0 + 0.9 v_{\pi}(s' = L1) \Bigr\} + 0.5 \Bigl\{ -1 + 0.9 v_{\pi}(s' = L2) \Bigr\} \\ &= 0.45 v_{\pi}(s' = L1) + 0.45 v_{\pi}(s' = L2) - 0.5 \end{aligned} $$

 状態価値関数の項を左辺に定数項を右辺に移項し(て、両辺に-1を掛け)ます。

$$ 0.45 v_{\pi}(s' = L1) - 0.55 v_{\pi}(s' = L2) = 0.5 $$


・連立方程式を解く

 2つのベルマン方程式をまとめます。

$$ \begin{cases} - 0.55 v_{\pi}(L1) + 0.45 v_{\pi}(L2) &= 0 \\ 0.45 v_{\pi}(L1) - 0.55 v_{\pi}(L2) &= 0.5 \end{cases} $$

 連立方程式を解きます。

$$ \begin{cases} v_{\pi}(L1) &= - 2.25 \\ v_{\pi}(L2) &= - 2.75 \end{cases} $$

 以上で、L1とL2それぞれの状態価値が求まりました。方策$\pi(a | s)$を取るときの状態L1の価値が-2.25だと分かりました。これを言い換えると、L1マスからスタートして、ランダムに行動を取り続けた場合、-2.25の報酬が見込まれることが分かりました。

・実験

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

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

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


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

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

# 割引率を指定
gamma = 0.9

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

# 状態を初期化
s = S0

# 左に行動する確率を指定
p_left = 0.5

# 確率的方策を作成
p_a = [p_left, 1.0-p_left]

# 収益を初期化
G = 0

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

# 繰り返し試行
for k in range(max_k):
    # ランダムに行動を決定
    a = np.random.choice(['left', 'right'], size=1, p=p_a).item()
    
    # 現在の状態がL1の場合
    if s == 1:
        # 行動が左の場合(壁にぶつかる場合)
        if a == 'left':
            # 報酬を指定
            r = -1.0
        
        # 行動が右の場合
        elif a == 'right':
            # 状態をL2に更新
            s = 2
            
            # 報酬を指定
            r = 1.0
    
    # 現在の状態がL2の場合
    elif s == 2:
        # 行動が左の場合
        if a == 'left':
            # 状態をL1に更新
            s = 1
            
            # 報酬を指定
            r = 0.0
        
        # 行動が右の場合(壁にぶつかる場合)
        elif a == 'right':
            # 報酬を指定
            r = -1.0
    
    # 収益を計算
    G += gamma**k * r
    
    # 値を記録
    trace_G.append(G)

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

 現在の状態をsとします。エージェントのいるマスがL1であれば値が1、L2であれば2とします。
 エージェントの行動をaとします。左に移動する場合は値が'left'、右に移動する場合は'right'とします。確率的方策p_aに従いnp.random.choice()でランダムに値(行動)を生成します。

 状態sと行動aの値に応じて、if文で条件分けして処理します。
 壁にぶつからずに移動できた場合はsを更新(再代入)します。
 それぞれの設定に従い報酬rを得ます。

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

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

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

# 真の状態価値を指定
v_s = -2.25

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

# 実験結果を作図
plt.figure(figsize=(8, 6))
plt.plot(k_vals, trace_G, label='$G_t$') # 収益の推移
plt.hlines(y=v_s, xmin=1, xmax=max_k+1, color='orange', linestyle='--', label='v(s)') # 真の状態価値
plt.xlabel('k')
plt.ylabel('value')
plt.suptitle('$G_t = \sum_k\ \gamma^k R_{t+k}$', fontsize=20)
plt.title('$S_t=L'+str(S0) + ', p(a | s)='+str(p_a) + ', \gamma='+str(gamma)+'$', loc='left') # 実験の設定
plt.grid()
plt.legend()
plt.show()

収益のグラフ

 この結果にはランダムな処理を含むので、処理の度に結果が変わります。

 そこで1.4節や1.5節のときと同様に、繰り返し実験を行い平均を求めます。

# 実験回数を指定
runs = 200

# 1実験当たりの試行回数を指定
max_k = 100

# 割引率を指定
gamma = 0.9

# 状態の初期値を指定
S0 = 1

# 左に行動する確率を指定
p_left = 0.5

# 確率的方策を作成
p_a = [p_left, 1.0-p_left]

# 記録用の配列を初期化
all_trace_G = np.zeros((runs, max_k))

# 繰り返し実験
for run in range(runs):
    # 状態を初期化
    s = S0

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

    # 繰り返し試行
    for k in range(max_k):
        # ランダムに行動を決定
        a = np.random.choice(['left', 'right'], size=1, p=p_a).item()

        # 現在の状態がL1の場合
        if s == 1:
            # 行動が左の場合(壁にぶつかる場合)
            if a == 'left':
                r = -1.0

            # 行動が右の場合
            elif a == 'right':
                # 状態をL2に更新
                s = 2
                r = 1.0

        # 現在の状態がL2の場合
        elif s == 2:
            # 行動が左の場合
            if a == 'left':
                # 状態をL1に更新
                s = 1
                r = 0.0

            # 行動が右の場合(壁にぶつかる場合)
            elif a == 'right':
                r = -1.0

        # 収益を計算
        G += gamma**k * r
        trace_G.append(G)
    
    # 実験結果を記録
    all_trace_G[run] = trace_G
    print('run', run+1, ': G =', G)

# 試行ごとに平均を計算
avg_trace_G = np.average(all_trace_G, axis=0)
run 1 : G = -4.980591362864736
run 2 : G = -2.2730124813649515
run 3 : G = -1.7988888846519528
(省略)
run 199 : G = -0.6050262486652901
run 200 : G = 2.4734957011806085

 1回の実験における収益の推移をtrace_Gに格納します。1回の実験が終わる度に、状態sと収益G、記録用のリストtrace_Gを初期化する必要があります。
 また、全ての実験の収益の推移をall_trace_Gに格納します。all_trace_Gの各行が各実験、各列が各将来時刻に対応します。
 最後に、all_trace_Gを時刻ごとに(列ごとに)平均をとりavg_trace_Gとします。avg_trace_Gが推移の平均になります。

 全ての実験の推移と平均推移をグラフで確認します。

# 真の状態価値を指定
true_v = -2.25

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

# 実験結果を作図
plt.figure(figsize=(8, 6))
for run in range(runs):
    plt.plot(k_vals, all_trace_G[run], alpha=0.1) # 実験結果
plt.plot(k_vals, avg_trace_G, color='red', label='V(s)') # 実験結果の平均
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('State-Value Function', fontsize=20)
plt.title(
    '$v(L'+str(S0)+')='+str(true_v) + 
    ', V(L'+str(S0)+')='+str(np.round(avg_trace_G[-1], 3)) + 
    ', \gamma='+str(gamma)+'$', 
    loc='left'
) # 状態価値関数の値
plt.grid()
plt.legend()
plt.show()

収益の標本平均のグラフ

 収益の標本平均(赤色の実線)がベルマン方程式により求めた状態価値(オレンジ色の破線)に近付いていくのが分かります。

 以上で、状態価値関数のベルマン方程式を確認できました。次節では、行動価値関数のベルマン方程式を確認します。

参考文献


おわりに

 面倒だけど手を動かすと理解が深まりますね?

 投稿日前日に公開された新MVをどうぞ♪


【次節の内容】

www.anarchive-beta.com