メインコンテンツへスキップ
見出し画像

Gymで強化学習⑰SARSA:実装編

    前回はTD学習法の理論について解説しました。今回は、オンポリシーでTD学習法を行うSARSAについて解説し実装します。

    まずは、SARSAをオンポリシーのTD学習法として導入してから実装を解説します。

    SARSAの仕組み

    前回はTD学習法で状態価値関数を更新する方法について解説しました。最終的には次のような更新式になりました。

    v(st)←v(st)+α[rt+γv(st+1)−v(st)]v(s_t) \leftarrow v(s_t) + \alpha \left[ r_t + \gamma v(s_{t+1}) - v(s_t) \right]

    TD学習法の特徴として次の2点が重要なポイントです。

    • 経験から学ぶので環境のモデル(状態遷移の確率)を必要としない。

    • ブートストラッピングを行うのでステップごとに学習ができる。

    上記の状態価値関数の更新式では、ポリシーについて触れていません。しかし、経験を集めるためには環境の中で探索を行う必要があります。TD学習法を利用するには、何らかのポリシーを使ってエージェントをコントロールする必要があります。

    それをオンポリシーで行うのがSARSAです。SARSAの名前の由来は、State - Action - Reward - State - Action から来ています。もっというとTD学習法で使う(st,at,rt,st+1,at+1)(s_t, a_t, r_t, s_{t+1}, a_{t+1})の頭文字からきています。

    オンポリシーなので行動を選択する挙動ポリシーと最適化の対象となるターゲットポリシーが同じです。よって、オンポリシーでTD学習法を行うSARSAは、下式を使って行動価値関数を更新していきます。

    q(st,at)←q(st,at)+α[rt+γq(st+1,at+1)−q(st,at) ]q(s_t, a_t) \leftarrow q(s_t, a_t) + \alpha \left[ r_t + \gamma q(s_{t+1}, a_{t+1}) - q(s_t, a_t)  \right]

    繰り返しますが、オンポリシーなので、次の状態st+1s_{t+1}における行動at+1a_{t+1}は行動を選択するポリシーが選ぶロジックに従います。

    あとは、状態価値関数の更新と同様に新しい予測値と古い予測値の差を計算しどのくらいの更新をするのかを決めます。

    もちろんSARSAは行動選択するためのポリシーとして学習するので行動価値関数を更新します。その際、新しい情報を取り入れた行動価値の予測値rt+γq(st+1,at+1)r_t + \gamma q(s_{t+1}, a_{t+1})と現状の行動価値の予測値q(st,at)q(s_t, a_t)との差を縮めるように行動価値関数を更新していきます。

    新しい情報による予測と現状の予測との差をTDエラーと呼びます。

    TD-error=rt+γq(st+1,at+1)−q(st,at)\text{TD-error} = r_t + \gamma q(s_{t+1}, a_{t+1}) - q(s_t, a_t)

    TDエラーが正の値ならば、新しい予測が以前の予測より大きくなっており、行動価値を増やす必要があります。また、TDエラーが負の値ならば、新しい予測が以前の予測より小さくなっているので、行動価値を減らす必要があります。

    q(st,at)←q(st,at)+α TD-errorq(s_t, a_t) \leftarrow q(s_t, a_t) + \alpha \ \text{TD-error}

    上記の更新式は、TDエラーを小さくする方向に新しい情報をステップサイズα\alphaによって少しずつ取り入れていると見ることができます。

    このような更新をなん度も重ねることで行動価値の予測が徐々に最適化されていくことになります。探索をしながらポリシーを改善していくために、いつものようにイプシロン・グリーディを使います。

    理論的な話は以上となります。

    SARSAの実装

    環境は凍った湖を使います。動的計画法やモンテカルロ法と比べるとかなりシンプルな実装になります。

    いつものようにエージェントから解説します。SarsaAgent は次のような構造になります。

    class SarsaAgent:
        def __init__(self, env, alpha, gamma, epsilon, epsilon_decay):
            self.env = env
            self.alpha = alpha
            self.gamma = gamma
            self.epsilon = epsilon
            self.epsilon_decay = epsilon_decay
    
            # 行動価値関数の初期化
            self.Q = np.zeros((env.observation_space.n, env.action_space.n))
    
        def reset(self, observation, info):
            self.state = observation
    
        def act(self):
            self.action = self._choose_action(self.state)
            return self.action
        
        def learn(self, observation, reward, terminated, truncated, info):
            ....

    __init__ はエージェントの初期化は、いつものイプシロン・グリーディの実装と同様です。行動価値関数は、2次元のNumPyオブジェクトであり、縦軸が状態、横軸が行動のインデックスになっています。

    reset は環境からの観測値の初期値を受け取ります。観測値はグリッド上の位置インデックスなのでそのまま状態として保存しておきます。

    act では、イプシロン・グリーディに従って行動を選びます。

    ここで self._choose_action なるメソッドを呼び出していますが、このファンクションはある状態(state)を渡すとイプシロン・グリーディに従って行動を返すようになっています。

        def _choose_action(self, state):
            if np.random.rand() < self.epsilon:
                action = np.random.choice(self.env.action_space.n)
            else:
                # 最大値の行動が複数ある場合はランダムに選択する
                max_q_value = np.max(self.Q[state])
                max_q_value_indices = np.nonzero(self.Q[state] == max_q_value)[0]
                action = np.random.choice(max_q_value_indices)
            return action

    イプシロン・グリーディでランダムな行動を選ぶか、さもなければ行動価値が最大になる行動を選びます。最大値の行動が複数ある場合は、その中からランダムに行動を選びます。これはモンテカルロ編でも同様でした。

    act では、self._choose_action に現状の状態(self.state)を渡すことで現在取る行動を取得しています。

    なお、このように self._choose_action を別のメソッドにした理由は次の learn でも使うからです。

    learn にはSARSAが行動価値関数を更新する実装があります。

        def learn(self, observation, reward, terminated, truncated, info):
            # SARSAによる行動価値関数の更新
            next_state = observation
    
            if terminated: 
                # エピソードが終了した場合は次の状態と行動は存在しない
                new_q_value = reward
            else:
                # オンポリシーなので、行動価値の更新でも同じポリシーを使う
                next_action = self._choose_action(next_state)
                new_q_value = reward + self.gamma * self.Q[next_state, next_action]
            
            # TDエラー
            td_error = new_q_value - self.Q[self.state, self.action]
            
            # 行動価値関数を更新する
            self.Q[self.state, self.action] += self.alpha * td_error
    
            # エピソード終了処理
            if terminated or truncated:
                # 行動価値関数を表示する
                print_q_table(self.Q)
                print(f'Epsilon: {self.epsilon:.2f}\n')
    
                # イプシロンを徐々に減らしていく
                self.epsilon *= self.epsilon_decay
    
            # 状態を更新する
            self.state = next_state

    ちょっと長いので分解して解説します。

    まず、行動の結果として受け取った状態を次の状態として、next_state に保存しておきます。

        def learn(self, observation, reward, terminated, truncated, info):
            # SARSAによる行動価値関数の更新
            next_state = observation

    エピソードが終了(terminated)した場合は、次の行動を考える必要がないので、行動価値の予測値は単純に受け取った報酬 reward になります。

            if terminated: 
                # エピソードが終了した場合は次の状態と行動は存在しない
                new_q_value = reward
            else:
                ...

    エピソードが終了していない場合(truncatedも含む)は、ブートストラッピングを利用して新しい情報を取り入れた行動価値の予測を行います。その際に次の状態 next_state に対する行動を選ぶのですが、オンポリシーなので実際の行動選択と同じ行動選択のロジックを使います。

    つまり、self._choose_action に次の状態 next_state を渡して、その状態での行動 next_action を選択します。イプシロン・グリーディなのでイプシロンが0に低減していないうちはランダムな行動選択も含まれます。

    この next_state と next_action を使えば、ブートストラッピングによって新しい行動価値の予測値を計算できます。

            if terminated: 
                # エピソードが終了した場合は次の状態と行動は存在しない
                new_q_value = reward
            else:
                # オンポリシーなので、行動価値の更新でも同じポリシーを使う
                next_action = self._choose_action(next_state)
                new_q_value = reward + self.gamma * self.Q[next_state, next_action]

    以上からTDエラーを計算し、行動価値関数を更新します。

            # TDエラー
            td_error = new_q_value - self.Q[self.state, self.action]
            
            # 行動価値関数を更新する
            self.Q[self.state, self.action] += self.alpha * td_error

    SARSAの実装の要はこれだけです。

    あとは、エピソードの終了時(terminated と truncated)にイプシロンを減らしていくなどの処理をします。

            # エピソード終了処理
            if terminated or truncated:
                # 行動価値関数を表示する
                print_q_table(self.Q)
                print(f'Epsilon: {self.epsilon:.2f}\n')
    
                # イプシロンを徐々に減らしていく
                self.epsilon *= self.epsilon_decay

    そして learn の最後に状態を更新しておきます。

            # 状態を更新する
            self.state = next_state

    ソースコードの実行

    ソースコード

    import argparse
    import gymnasium as gym
    import numpy as np
    
    
    class SarsaAgent:
        def __init__(self, env, alpha, gamma, epsilon, epsilon_decay):
            self.env = env
            self.alpha = alpha
            self.gamma = gamma
            self.epsilon = epsilon
            self.epsilon_decay = epsilon_decay
    
            # 行動価値関数の初期化
            self.Q = np.zeros((env.observation_space.n, env.action_space.n))
    
        def reset(self, observation, info):
            self.state = observation
    
        def act(self):
            self.action = self._choose_action(self.state)
            return self.action
        
        def _choose_action(self, state):
            if np.random.rand() < self.epsilon:
                action = np.random.choice(self.env.action_space.n)
            else:
                # 最大値の行動が複数ある場合はランダムに選択する
                max_q_value = np.max(self.Q[state])
                max_q_value_indices = np.nonzero(self.Q[state] == max_q_value)[0]
                action = np.random.choice(max_q_value_indices)
            return action
    
        def learn(self, observation, reward, terminated, truncated, info):
            # SARSAによる行動価値関数の更新
            next_state = observation
    
            if terminated: 
                # エピソードが終了した場合は次の状態と行動は存在しない
                new_q_value = reward
            else:
                # オンポリシーなので、行動価値の更新でも同じポリシーを使う
                next_action = self._choose_action(next_state)
                new_q_value = reward + self.gamma * self.Q[next_state, next_action]
            
            # TDエラー
            td_error = new_q_value - self.Q[self.state, self.action]
            
            # 行動価値関数を更新する
            self.Q[self.state, self.action] += self.alpha * td_error
    
            # エピソード終了処理
            if terminated or truncated:
                # 行動価値関数を表示する
                print_q_table(self.Q)
                print(f'Epsilon: {self.epsilon:.2f}\n')
    
                # イプシロンを徐々に減らしていく
                self.epsilon *= self.epsilon_decay
    
            # 状態を更新する
            self.state = next_state
                
    
    def print_q_table(Q):
        num_states, num_actions = Q.shape
    
        # 1行目:タイトル
        print("State |", end="")
        for action in range(num_actions):
            print(f"  Action {action} |", end="")
        print()
    
        # 2行目:区切り
        print("-" * (9 + num_actions * 12))
    
        # 3行目以降:状態と行動価値関数
        for state in range(num_states):
            print(f"{state:5} |", end="")
            for action in range(num_actions):
                print(f" {Q[state][action]:8.2f}  |", end="")
            print()
    
    
    def run_episodes(env, agent, max_episodes):
    
        # エピソードのループをmax_episodes回繰り返す
        for episode in range(max_episodes):
            print(f'エピソード: {episode+1}')
    
            # ゲーム環境を初期化してエージェントに初期観測値を渡す
            observation, info = env.reset()
            agent.reset(observation, info)
    
            # 1つのエピソードのループ
            while True:
                # エージェントの行動を決定
                action = agent.act()
    
                # 行動を実行すると、環境の状態が更新される
                observation, reward, terminated, truncated, info = env.step(action)
    
                # エージェントの学習
                agent.learn(observation, reward, terminated, truncated, info)
    
                # ゲームが終了したら、次のエピソードへ
                if terminated or truncated:
                    break
    
        # 環境を閉じる
        env.close()
    
    
    def main():
        # コマンドライン引数を取得
        parser = argparse.ArgumentParser()
        parser.add_argument("--map"          , type=str  , default="4x4")
        parser.add_argument("--slippery"     , action="store_true")
        parser.add_argument("--alpha"        , type=float, default=0.1)
        parser.add_argument("--gamma"        , type=float, default=0.9)
        parser.add_argument("--epsilon"      , type=float, default=1.0)
        parser.add_argument("--epsilon_decay", type=float, default=0.99)
        parser.add_argument("--max_episodes" , type=int  , default=1000)
        parser.add_argument("--no_render"    , action="store_true")
        args = parser.parse_args()
        args.render_mode = "human" if not args.no_render else None
        print(args)
    
        # 環境を作成
        env = gym.make('FrozenLake-v1',
                       map_name=args.map,
                       is_slippery=args.slippery,
                       render_mode=args.render_mode)
        
        # エージェントを作成
        agent = SarsaAgent(env,
                           alpha=args.alpha,
                           gamma=args.gamma,
                           epsilon=args.epsilon,
                           epsilon_decay=args.epsilon_decay)
    
        # エピソードを実行
        run_episodes(env, agent, max_episodes=args.max_episodes)
    
    
    if __name__ == "__main__":
        main()

    実行の仕方

    ソースコードを frozen_lake_sarsa.py といったファイルにセーブしておきます。

    Python環境は準備編で設定したのと同じです。

    なお、実行する際に幾つかのパラメータを指定できます。

    usage: frozen_lake_sarsa.py [-h] [--map MAP] [--slippery] [--alpha ALPHA]
                                [--gamma GAMMA] [--epsilon EPSILON] 
                                [--epsilon_decay EPSILON_DECAY]
                                [--max_episodes MAX_EPISODES] 
                                [--no_render]
    
    options:
      -h, --help            show this help message and exit
      --map MAP
      --slippery
      --alpha ALPHA
      --gamma GAMMA
      --epsilon EPSILON
      --epsilon_decay EPSILON_DECAY
      --max_episodes MAX_EPISODES
      --no_render

    例えば、以下のように実行すると is_slippery=True として環境が作成されます。

    python frozen_lake_sarsa.py --slippery

    画像なしで高速に実行したい場合は、次のように実行します。

    python frozen_lake_sarsa.py --no_render

    これでもコンソールに状態価値関数がエピソードごとに表示されるので更新される様子がわかります。

    実行結果

    モンテカルロ法の実装でも見たように、最初にゴールに到着するまでは行動価値関数は全てゼロのままです。なぜならゴールに到着するまでは報酬はゼロだからです。穴に落ちてもペナルティもありません。なので場合によってはかなり長い間ランダムな行動をしていることもあります。

    一旦ゴールに到着すると、ゴール付近の行動価値関数の値が更新されます。その後のエピソードでエージェントが再びその付近の状態を訪れることで少しずつ行動価値関数の更新が広がっていきます。

    以下の例では、エピソード32で初めてゴールに到着しました。

    エピソード: 32
    State |  Action 0 |  Action 1 |  Action 2 |  Action 3 |
    ---------------------------------------------------------
        0 |     0.00  |     0.00  |     0.00  |     0.00  |
        1 |     0.00  |     0.00  |     0.00  |     0.00  |
        2 |     0.00  |     0.00  |     0.00  |     0.00  |
        3 |     0.00  |     0.00  |     0.00  |     0.00  |
        4 |     0.00  |     0.00  |     0.00  |     0.00  |
        5 |     0.00  |     0.00  |     0.00  |     0.00  |
        6 |     0.00  |     0.00  |     0.00  |     0.00  |
        7 |     0.00  |     0.00  |     0.00  |     0.00  |
        8 |     0.00  |     0.00  |     0.00  |     0.00  |
        9 |     0.00  |     0.00  |     0.00  |     0.00  |
       10 |     0.00  |     0.00  |     0.00  |     0.00  |
       11 |     0.00  |     0.00  |     0.00  |     0.00  |
       12 |     0.00  |     0.00  |     0.00  |     0.00  |
       13 |     0.00  |     0.00  |     0.00  |     0.00  |
       14 |     0.00  |     0.00  |     0.10  |     0.00  |
       15 |     0.00  |     0.00  |     0.00  |     0.00  |

    この時、状態14から状態15のゴール地点へ右への移動(行動2)をしたので、報酬として1.0を受け取ります。つまり、行動価値関数のq(14,2)q(14, 2)の値が更新されています。

    画像

    ここでは古い予測値が0で新しい情報による予測値が1.0になるので差分は1.0となり、それに対してステップサイズ0.1を掛けた値である0.1がq(14,2)q(14, 2)の値となります。つまり、古い予測よりも少しだけ新しい情報による予測値に近づくことになります。

    まとめると、ゴールに初めて到着したことで、状態14で行動2(右への移動)を選択することに対する価値は0.1になりました。

    これを長く続けていくと行動価値関数は新しい情報を取り入れ続けて更新されていきます。以下はエピソード1000での行動価値関数です。

    エピソード: 1000
    State |  Action 0 |  Action 1 |  Action 2 |  Action 3 |
    ---------------------------------------------------------
        0 |     0.13  |     0.03  |     0.59  |     0.10  |
        1 |     0.18  |     0.00  |     0.66  |     0.16  |
        2 |     0.29  |     0.73  |     0.04  |     0.22  |
        3 |     0.24  |     0.00  |     0.00  |     0.00  |
        4 |     0.00  |     0.00  |     0.00  |     0.16  |
        5 |     0.00  |     0.00  |     0.00  |     0.00  |
        6 |     0.00  |     0.81  |     0.00  |     0.34  |
        7 |     0.00  |     0.00  |     0.00  |     0.00  |
        8 |     0.00  |     0.00  |     0.02  |     0.00  |
        9 |     0.00  |     0.00  |     0.35  |     0.00  |
       10 |     0.06  |     0.90  |     0.00  |     0.10  |
       11 |     0.00  |     0.00  |     0.00  |     0.00  |
       12 |     0.00  |     0.00  |     0.00  |     0.00  |
       13 |     0.00  |     0.00  |     0.09  |     0.00  |
       14 |     0.00  |     0.39  |     1.00  |     0.35  |
       15 |     0.00  |     0.00  |     0.00  |     0.00  |

    q(14,2)q(14, 2)の値が1.0になっているのが確認できます。ランダム性があるので毎回同じ結果になるとは限りませんが。

    次に、--slippery を指定して実行した場合に結果を表示します。長く探索を行うために次のような設定で実行しました。ステップサイズ(alpha)も調節して新しい情報を取り入れるスピードを少し遅くしました。

    python frozen_lake_sarsa.py --no_render --slippery \
                                --max_episodes 10000 --epsilon_decay 0.999 \
                                --alpha 0.05
    エピソード: 10000
    State |  Action 0 |  Action 1 |  Action 2 |  Action 3 |
    ---------------------------------------------------------
        0 |     0.06  |     0.05  |     0.04  |     0.04  |
        1 |     0.03  |     0.04  |     0.04  |     0.05  |
        2 |     0.05  |     0.05  |     0.06  |     0.04  |
        3 |     0.00  |     0.00  |     0.00  |     0.04  |
        4 |     0.09  |     0.06  |     0.06  |     0.04  |
        5 |     0.00  |     0.00  |     0.00  |     0.00  |
        6 |     0.10  |     0.05  |     0.06  |     0.02  |
        7 |     0.00  |     0.00  |     0.00  |     0.00  |
        8 |     0.07  |     0.08  |     0.09  |     0.16  |
        9 |     0.15  |     0.25  |     0.18  |     0.12  |
       10 |     0.30  |     0.19  |     0.17  |     0.09  |
       11 |     0.00  |     0.00  |     0.00  |     0.00  |
       12 |     0.00  |     0.00  |     0.00  |     0.00  |
       13 |     0.16  |     0.25  |     0.39  |     0.23  |
       14 |     0.35  |     0.67  |     0.42  |     0.41  |
       15 |     0.00  |     0.00  |     0.00  |     0.00  |

    これを見ると偶然に穴に落ちることがないように行動選択しているのがわかります。なお、行動価値の値はランダム性があり毎回異なります。

    次回は、TD学習をオフポリシーで実装するQ学習を解説します。

    (続く)

     
     
    「わかりやすく、具体的に」AIとサイエンスの情報を発信中

    あなたへのおすすめ