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

Gymで強化学習⑮モンテカルロ法:実装編

    前回はオン・オフポリシーについて解説しました。今回は実際にモンテカルロ法のエージェントを使って凍った湖の環境を解決します。

    エージェントの全体像

    いつものようにエージェントはいくつかのメソッドを実装することで実行できるようになります。あとで環境を走らせるコードを掲載しますが、基本的に以前に実装したものと同じでエージェントからアクションを受け取り環境に適用することで報酬をエージェントが受け取るという過程を繰り返します。

    イプシロン・グリーディ

    実装するモンテカルロ法のエージェントではイプシロン・グリーディを使って経験を貯めていきます。以下は、エージェントの全体像を要点だけに絞って示したものです。

    class MonteCarloAgent:
        def __init__(self, env, method, gamma, epsilon, epsilon_decay):
            self.env = env
            ...
            self.epsilon = epsilon
            ...
    
            # モンテカルロ法による行動価値関数の計算
            self.Q = np.zeros((env.observation_space.n, env.action_space.n))
            ...
    
        def reset(self, observation, info):
            self.state = observation
            self.samples = []
    
        def act(self):
            if np.random.rand() < self.epsilon:
                self.action = np.random.choice(self.env.action_space.n)
            else:
                # 最大値の行動を返す
                self.action = np.argmax(self.Q[self.state])
            return self.action
    
        def learn(self, observation, reward, terminated, truncated, info):
            # エピソードの行動と観測値を記録する
            self.samples.append((self.state, self.action, reward))
            ...

    これを土台に改良を重ねてさまざまなモンテカルロ法(オンポリシー、オフポリシー、逐一訪問、初回訪問)に対応していきますが、まずは基本的な仕組みを解説します。

    今回も凍った湖の環境を使います。

    画像
    https://gymnasium.farama.org/environments/toy_text/frozen_lake/

    凍った湖の環境では観測値(observation)は凍った湖における位置を示す整数です。4x4 の地図ならば0から15の値になります。

    画像
    4x4の地図

    この観測値によって得る報酬とエピソードが終了するかどうかが決まるので観測値をそのまま状態として使います。

    エージェントの初期化の部分では環境オブジェクトやその他もろもろの引数を受け取ります。

        def __init__(self, env, method, gamma, epsilon, epsilon_decay):
            self.env = env
            ...
            self.epsilon = epsilon
            self.epsilon_decay = epsilon_decay
    
            # モンテカルロ法による行動価値関数の計算
            self.Q = np.zeros((env.observation_space.n, env.action_space.n))
            ...

    詳細は後に回しますが、イプシロン(ϵ\epsilon)の値や行動価値関数QQなど必要なものをここでメンバー変数として設定します。

        def reset(self, observation, info):
            self.state = observation
            self.samples = []

    reset はエピソード開始時に呼ばれます。ここでは最初の観測値を受け取ります。また、経験から得たサンプルデータを収納するためのリストを self.samples として定義しています。このリストに状態、行動、報酬を時系列に沿って貯めていきます。

        def act(self):
            if np.random.rand() < self.epsilon:
                self.action = np.random.choice(self.env.action_space.n)
            else:
                # 最大値の行動を返す
                self.action = np.argmax(self.Q[self.state])
            return self.action

    act はエピソードのループで繰り返し呼ばれます。その都度、エージェントが選択した行動を返します。

    イプシロン・グリーディのイプシロンの意味は、0から1までの数を一つランダムに生成して、イプシロン(ϵ\epsilon)より小さかったら、ランダムな行動を選択することで探索(exploration)を行います。

                 self.action = np.random.choice(self.env.action_space.n)

    なお、self.env.action_space.n は可能な行動の数を返します。この環境では0から3までの四つの行動が可能で、それぞれ左(0)、下(1)、右(2)、上(3)となっています。よって0から3までの数値をランダムに選んでいます。

    ランダムな行動を選ばない場合には、搾取(exploitation)を行います。つまり、最大の行動価値(Q値)を返す行動を選択します。

    初期化のところで見たように、self.Qは行動価値関数をNumPyの2次元配列で表現しています。

            # モンテカルロ法による行動価値関数の計算
            self.Q = np.zeros((env.observation_space.n, env.action_space.n))

    よってself.Q[state][action]で状態と行動を指定するとその状態における指定された行動価値を返します。また、self.Q[state] のように状態だけを指定すると四つの行動に対する価値をリストとして返します。

    Q[状態] => [左へ移動する価値、下へ移動する価値、右へ移動する価値、上へ移動する価値]

    なので以下の文は最大の行動価値のインデックス(0から3)を返します。

                # 最大値の行動を返す
                self.action = np.argmax(self.Q[self.state])

    実は、この最大値を返す行動を選ぶ際に厄介な問題ありあとでコードを修正します。今のところはここでグリーディ(欲張り)になり搾取を行うとだけ覚えておいてください。

    act が返した行動が環境において実行されると報酬と次の観測値が返されます。これがエージェントの learn に渡されます。

        def learn(self, observation, reward, terminated, truncated, info):
            # エピソードの行動と観測値を記録する
            self.samples.append((self.state, self.action, reward))
            ...

    こうして得た状態、行動、報酬をサンプルのリストに追加します。このようにしてエピソードからの経験を集めていきます。

    この経験を使って行動価値関数Qを更新します。それはエピソードの終了時に行われます。

        def learn(self, observation, reward, terminated, truncated, info):
            # エピソードの行動と観測値を記録する
            self.samples.append((self.state, self.action, reward))
    
            # エピソードが終了(terminated)。truncatedは無視する
            if terminated:
                # 行動価値関数を更新する
                self.method(self.Q, self.S, self.C, self.samples, self.gamma, self.epsilon)
    
                ...
            ...

    この際、エピソードの終了を terminated がTrueかどうかで判断します。ここでは truncated は無視します。truncated がTrueでもエピソードは終了なのですが、エージェントが穴に落ちるとかゴールに到着する場合は terminated はTrueになりますが、truncated はTrueにはなりません。

    truncated がTrueになるのは、エージェントがぐるぐる堂々巡りをしていたり、いつまでも壁に向かって移動を試み続けているような場合です。つまり、強制終了になるときです。よって、本当の意味でのエピソードの終了(ゴールに到着とか穴に落ちるとか)ではなく生涯報酬を計算することができないので無視します。

        def learn(self, observation, reward, terminated, truncated, info):
            ...
    
            # エピソードが終了(terminated)。truncatedは無視する
            if terminated:
                # 行動価値関数を更新する
                self.method(self.Q, self.S, self.C, self.samples, self.gamma, self.epsilon)
    

    行動価値関数Qの更新のために self.method を呼び出しています。ここでの処理の目的は、さまざまなモンテカルロ法(オンポリシー、オフポリシー、逐一訪問、初回訪問)に対応した手法で行動価値関数を更新することです。各手法の実装の詳細については後述します。

    また、以下に見るようにエピソードの終了後にイプシロンを低減させます。

        def learn(self, observation, reward, terminated, truncated, info):
            ...
    
            # エピソードが終了(terminated)。truncatedは無視する
            if terminated:
                ...
    
                # イプシロンを徐々に減らしていく
                self.epsilon *= self.epsilon_decay
    
            # 状態を更新する
            self.state = observation

    epsilon_decay はイプシロンをエピソードごと低減される割合を設定しています。例えば、epsilon_decay = 0.99 だったら毎エピソード後にイプシロンを1%減らすことになります。

    最後に、新しい観測値を状態へと更新して次のステップへ備えます。以上がイプシロン・グリーディを使ったエージェントの全体像です。

    次に、self.method の中身を各手法の実装に対して解説していきます。

    オンポリシー

    オンポリシーでは経験から状態、行動、報酬のサンプルを集めるポリシーと最適化されるポリシーが同じです。よってオフポリシーよりも実装が簡単なので最初に解説します。

    逐一訪問モンテカルロ法

    逐一訪問は初回訪問より簡単なのでこちらから実装します。

    # オンポリシー、逐一訪問モンテカルロ法
    # (イプシロンは使わない)
    def on_policy_every_visit_mc(Q, S, C, samples, gamma, epsilon):
        g = 0
        for state, action, reward in reversed(samples):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g
    
            # この状態・行動のペアに対する価値の総和と回数を更新する
            S[state][action] += g
            C[state][action] += 1.0
    
            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]

    逐一訪問モンテカルロ法のエージェントでは、self.method が on_policy_every_visit_mc を参照しています。その引数として S, C などが渡されています。実はこれらはエージェントの初期化で設定されています。

    class MonteCarloAgent:
        def __init__(self, env, method, gamma, epsilon, epsilon_decay):
            self.env = env
            self.method = method
            ...
    
            # モンテカルロ法による行動価値関数の計算
            self.Q = np.zeros((env.observation_space.n, env.action_space.n))
    
            # 各状態における行動の価値を計算するための変数(総和と回数)
            self.S = np.zeros((env.observation_space.n, env.action_space.n))
            self.C = np.zeros((env.observation_space.n, env.action_space.n))

    SとCは両方とも行動価値関数Qと同じ状態と行動の2次元配列になっています。S[state][action]はある状態 state からある行動 action を選んだ時の生涯報酬の総和を収納しています。C[state][action]はその状態を訪れた回数を記憶しています。

    よって、S[state][action]をC[state][action]で割れば、その状態 state からある行動 action を選んだ時の生涯報酬の平均を計算できます。

    S[state][action] / C[state][action]

    なお、エージェントの初期化のところでは、割引率γ\gammaとして gamma も引数として渡されています。

    class MonteCarloAgent:
        def __init__(self, env, method, gamma, epsilon, epsilon_decay):
            self.env = env
            self.method = method
            self.gamma = gamma
            ...

    それが逐一訪問モンテカルロ法の実装である on_policy_every_visit_mc で使われています。

    # オンポリシー、逐一訪問モンテカルロ法
    # (イプシロンは使わない)
    def on_policy_every_visit_mc(Q, S, C, samples, gamma, epsilon):
        g = 0
        for state, action, reward in reversed(samples):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g
    
            # この状態・行動のペアに対する価値の総和と回数を更新する
            S[state][action] += g
            C[state][action] += 1.0
    
            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]

    この関数はエピソードが終了(terminated)した時に呼ばれます。samples には state, action, reward がリストに収納されています。これを後ろから順番に処理していきます。

        g = 0
        for state, action, reward in reversed(samples):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g

    この部分は、生涯報酬の値を最後のステップから最初のステップへと逆順序で計算しています。例えば、ゴールに到着してエピソードが終わった場合、reward = 1.0 です。あとは常に reward = 0.0 です。よって、割引率を 0.9 とすると計算は次のようになります。

    最後から1番目:g = 1.0
    最後から2番目:g = 0 + 0.9 * 1.0 = 0.9
    最後から3番目:g = 0 + 0.9 * 0.9 = 0.81
    …

    このように計算した生涯報酬 g を訪れた状態と行動に対して S に追加(足し算)します。また、訪れた回数を C に記録します。

            # この状態・行動のペアに対する価値の総和と回数を更新する
            S[state][action] += g
            C[state][action] += 1.0

    あとは、行動価値関数Qを更新します。ここでは生涯報酬の総和を訪れた回数で割り算しています。

            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]

    実装としてはこれだけです。イプシロン・グリーディで、いろいろな状態でいろいろな行動を経験できれば行動価値関数Qの値も収束していきます。

    ただし、実際にこのままエージェントを実行すると、思ったように探索が進みません。なぜなら、ゴール地点に行くまでには複数の偶然が重なる必要があるからです。実際、250回以上のエピソードを行って初めてゴール到着が生じるなど普通に起こります。早い時は50回ぐらいでゴールを経験することもあります。それこそランダムです。

    さらに、もう一つもっと重大な問題があります。

    気づいた方もいるかもしれませんが、エージェントの初期化では行動価値はすべてゼロに設定されており優劣がありません。つまりあらゆる状態においてすべての行動の価値がゼロになっています。その場合、下記の文はつねに最初のインデックスである0を行動として返します。

                # 最大値の行動を返す
                self.action = np.argmax(self.Q[self.state])

    つまり、搾取の行動としてエージェントは左への移動ばかりを選ぶことになります。よって、左への移動が不必要に多く選ばれることになります。

    ある状態において、最大の行動価値に優劣がない場合は、搾取であっても決定論的ではなくランダムに行動を選ぶことによって探索をする機会が増えます。よって行動価値が最大になる行動が複数ある場合は、その中からランダムに選ぶようにします。

            # ある状態における行動価値の最大値
            max_q_value = np.max(self.Q[self.state])
    
            # 最大値の行動のインデックスを集める
            max_q_value_indices = []
            for i, q_value in enumerate(self.Q[self.state]):
                if q_value == max_q_value:
                    max_q_value_indices.append(i)
    
            # 最大値の行動のリストからランダムに選択する
            self.action = np.random.choice(max_q_value_indices)

    これでも良いのですが、もう少しコンパクトにしたコードは以下のようになります。やっていることは同じです。

            # 最大値の行動が複数ある場合はランダムに選択する
            max_q_value = np.max(self.Q[self.state])
            max_q_value_indices = np.nonzero(self.Q[self.state] == max_q_value)[0]
            self.action = np.random.choice(max_q_value_indices)

    いずれにせよ、最大値の行動のリストが作られます。そこに複数の値があればランダムに選択されますし、一つだけなら決定論的に決めているのと同じです。

    なお、理論的なことを言うと逐一訪問は偏った平均を計算することになる可能性があります。それは一つのエピソード内で同じ状態と行動のペアを複数回経験した時に両方を計算に含めるからです。最適なポリシーであればそんなことは起きない(slipperry=Falseならば)ので好ましくないサンプルを含んでいることになります。

    ただし、実際には行動価値関数Qが収束しイプシロンが低減するに従って無駄な行動も少なくなり問題はありません。また、サンプルをたくさん集められるという意味では初回訪問モンテカルロ法よりも収束が早くなる可能性もあります。

    理論上は初回訪問モンテカルロ法の方が平均値に偏りが起きにくいことにはなるのでそちらも実装してみます。

    初回訪問モンテカルロ法

    初回訪問モンテカルロ法の実装は、逐一訪問モンテカルロ法に数行の修正を加えるだけです。

    # オンポリシー、初回訪問モンテカルロ法
    def on_policy_first_visit_mc(Q, S, C, samples, gamma, epsilon): # イプシロンは使わない
        # 各状態・行動のペアに対する初回訪問のステップ数を記録する
        first_visited_state_actions = {}
        for rstep, (state, action, reward) in enumerate(reversed(samples)):
            first_visited_state_actions[(state, action)] = rstep
    
        g = 0
        for rstep, (state, action, reward) in enumerate(reversed(samples)):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g
    
            # 初回訪問でなければ、その時点での価値を計算しない
            if first_visited_state_actions[(state, action)] != rstep:
                continue
    
            # この状態・行動のペアに対する価値の総和と回数を更新する
            S[state][action] += g
            C[state][action] += 1.0
    
            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]

    違いは初回訪問のチェックがあるかどうかになります。そのためにどの状態行動を最初に訪れたのかを記録するディクショナリを作成します。

        # 各状態・行動のペアに対する初回訪問のステップ数を記録する
        first_visited_state_actions = {}
        for rstep, (state, action, reward) in enumerate(reversed(samples)):
            first_visited_state_actions[(state, action)] = rstep

    後ろから辿ってディクショナリの更新しているので最終的には初回訪問の記録が残ります。

    なお、rstep (reverse step)と呼んでいるのは、逆からのステップという意味です。それ以外に深い意味はありません。

    そして、初回訪問でない状態行動に関してはスキップします。

            # 初回訪問でなければ、その時点での価値を計算しない
            if first_visited_state_actions[(state, action)] != rstep:
                continue

    初回訪問のための実装の変更は以上になります。

    逐一訪問モンテカルロ法と同様で、一旦ゴール到着の経験をすれば徐々に行動価値関数Qが収束していきます。

    オフポリシー

    オフポリシーでは経験から状態、行動、報酬のサンプルを集める挙動ポリシーと最適化されるターゲットポリシーが異なります。

    挙動ポリシーは探索が目的なので、ここではイプシロン・グリーディを使います。よって、オンポリシーと同じコードを再利用することができます。

    ターゲット・ポリシーでは行動価値関数Qから最大値を与える行動を選ぶのですが、前述したように複数の行動が最大値を与える場合はランダムに選びます。つまり、エージェントのコード自体はオンポリシーと同じものを使います。self.method が指す関数の実装だけが異なるわけです。

    逐一訪問モンテカルロ法

    前回の記事で重点サンプリングの手法を解説しました。その際、挙動ポリシーとターゲットポリシーによる行動選択の確率の比を計算して生涯報酬に掛け合わせることで挙動ポリシーの行動選択でサンプルを集めながらもターゲットポリシーの行動価値の期待値を計算できるようにしました。

    それを逐一訪問で実装したのが以下になります。

    # オフポリシー、逐一訪問モンテカルロ法
    def off_policy_every_visit_mc(Q, S, C, samples, gamma, epsilon):
        g = 0
        W = 1
        for state, action, reward in reversed(samples):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g
    
            # この状態・行動のペアに対する価値の総和と回数を更新する
            # Wは重点サンプリング比率
            S[state][action] += W * g
            C[state][action] += 1.0
    
            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]
    
            # ターゲットポリシーに従って行動を選択するので
            # ターゲットポリシーと挙動ポリシーの行動が異なれば終了
            max_indices = np.nonzero(Q[state] == Q[state].max())[0]
            if action not in max_indices:
                break
    
            # 重点サンプリング比率を更新する。
            # ターゲットポリシーでも収束し始めるまでは複数の最大値を持つ行動を
            # 等確率で選択することを考慮する。
            num_max_actions = len(max_indices)
            target_prob = 1 / num_max_actions
            behavior_prob = (1 - epsilon) / num_max_actions + epsilon / len(Q[state])
            W *= target_prob / behavior_prob

    Wは重点サンプリングで使う挙動ポリシーとターゲットポリシーによる行動選択の確率の比(重点サンプリング比率)です。

        W = 1

    これをエピソードのステップを後ろから追うごとに更新しならが生涯報酬の総和を更新していきます。生涯報酬 g に W を掛け合わせています。

            # この状態・行動のペアに対する価値の総和と回数を更新する
            # Wは重点サンプリング比率
            S[state][action] += W * g
            C[state][action] += 1.0

    そのあとは以前同様に平均を計算します。

            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]

    この後にWの値も更新するのですが、挙動ポリシーによる行動がターゲットポリシーが取り得る行動である時のみに更新します。

            # ターゲットポリシーに従って行動を選択するので
            # ターゲットポリシーと挙動ポリシーの行動が異なれば終了
            max_indices = np.nonzero(Q[state] == Q[state].max())[0]
            if action not in max_indices:
                break

    なぜなら、ターゲットポリシーが取り得ない行動の確率はゼロなのでWもゼロになりそれ以前の行動はサンプルとしての意味がないからです。ターゲットポリシーは最大値の行動しか選ばないので、挙動ポリシーの行動がその中に含まれているかのチェックをここで行なっています。

    もしOKであれば、重点サンプリング比率を更新します。

            # 重点サンプリング比率を更新する。
            # ターゲットポリシーでも収束し始めるまでは複数の最大値を持つ行動を
            # 等確率で選択することを考慮する。
            num_max_actions = len(max_indices)
            target_prob = 1 / num_max_actions
            behavior_prob = (1 - epsilon) / num_max_actions + epsilon / len(Q[state])
            W *= target_prob / behavior_prob

    ターゲットが行動を選ぶ確率は、最大値を与える行動の数で決まります。4つあれば4分の1(25%)の確率で一つの行動を選びます。最適化が進めば一つの行動が100%の確率で選ばれる決定論的な行動選択になります。

    挙動ポリシーに関してはターゲットポリシーが選ぶような行動を選ぶのは、イプシロン・グリーディの探索でランダムな行動を選ぶ確率と搾取の際に最大値を与える行動からランダムに選ぶ確率の和になります。

    探索でランダムな行動を選ぶ確率は次になります。

    epsilon / len(Q[state])

    ちなみに len(Q[state]) は常に4なのですが、ここではQ[state]が返す行動価値のリストの長さとして一般的な形で計算しています。

    また、搾取の際に最大値を与える行動からランダムに選ぶ確率はターゲットポリシーと同様に次になります。

    (1 - epsilon) / num_max_actions

    以上で、オフポリシーの逐一訪問モンテカルロ法の実装になります。が、一つ問題があります。

    状態行動の回数を更新するところでC[state][action]に1を足しています。

            # この状態・行動のペアに対する価値の総和と回数を更新する
            # Wは重点サンプリング比率
            S[state][action] += W * g
            C[state][action] += 1.0

    実は、これは通常重点サンプリング(Ordinary Importance Sampling、OIS)といって、理論的には正しいです。

    例えば、状態価値を通常サンプリングで計算する数式は次のようになります。

    V(s)≐∑t∈T(s)ρt:T−1gt∣T(s)∣V(s) \doteq \dfrac{ \sum\limits_{t \in \Tau(s)} \rho_{t:T-1} g_t }{ | \Tau(s) | }

    T(s)\Tau(s)は状態ssを訪れたすべてのステップを返します。ρt:T−1\rho_{t:T-1}はステップ t から終了ステップTまでの重点サンプリング比率です。| \Tau(s) |は状態ssが訪問された数です。

    この手法だと重点サンプリング比率が大きくなりがちで行動価値関数Qの値が実際の生涯報酬の何十倍になったりしてうまく収束しなかったり、長い時間がかかったりします。

    なので、実際には加重平均を使った使った加重重点サンプリング(Weighted Importance Sampling、WIS)が使われます。数式で書くと次になります。

    V(s)≐∑t∈T(s)ρt:T−1gt∑t∈T(s)ρt:T−1V(s) \doteq \dfrac{ \sum\limits_{t \in \Tau(s)} \rho_{t:T-1} g_t }{ \sum\limits_{t \in \Tau(s)} \rho_{t:T-1} }

    重点サンプリング比率を掛けた総和を重点サンプリング比率の総和で割っているので価値の値が大きくなることを防げます。

    コードの書き換えは1をWに変えるだけです。

            # この状態・行動のペアに対する価値の総和と回数を更新する
            # Wは重点サンプリング比率
            S[state][action] += W * g
            C[state][action] += W

    これで生涯報酬の値が大きくなりすぎることがなくなり、収束しやすくなります。

    参考までに、以下の図はRichard SuttonによるReinforcement Learning An Introductionからの引用です。ブラックジャック(カードゲーム)における状態価値の予測エラーがエピソードごとに減る度合いを表示しています。

    画像

    加重重点サンプリング(Weighted Importance Sampling、WIS)の方が通常重点サンプリング(Ordinary Importance Sampling、OIS)よりはやく収束するのがわかります。

    初回訪問モンテカルロ法

    オフポリシーの初回訪問モンテカルロ法はオフポリシーの逐一訪問モンテカルロ法に初回訪問のチェックを加えたものです。オンポリシーの時と全く同様で初回訪問のチェックが入ります。

    # オフポリシー、初回訪問モンテカルロ法
    def off_policy_first_visit_mc(Q, S, C, samples, gamma, epsilon):
        # 各状態・行動のペアに対する初回訪問のステップ数を記録する
        first_visited_state_actions = {}
        for rstep, (state, action, reward) in enumerate(reversed(samples)):
            first_visited_state_actions[(state, action)] = rstep
        
        g = 0
        W = 1
        for rstep, (state, action, reward) in enumerated(reversed(samples)):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g
    
            # 初回訪問でなければ、その時点での価値を計算しない
            if first_visited_state_actions[(state, action)] != rstep:
                continue
    
            # この状態・行動のペアに対する価値の総和と回数を更新する
            # Wは重点サンプリング比率
            S[state][action] += W * g
            C[state][action] += W
    
            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]
    
            # ターゲットポリシーに従って行動を選択するので
            # ターゲットポリシーと挙動ポリシーの行動が異なれば終了
            max_indices = np.nonzero(Q[state] == Q[state].max())[0]
            if action not in max_indices:
                break
    
            # 重点サンプリング比率を更新する。
            # ターゲットポリシーでも収束し始めるまでは複数の最大値を持つ行動を
            # 等確率で選択することを考慮する。
            num_max_actions = len(max_indices)
            target_prob = 1 / num_max_actions
            behavior_prob = (1 - epsilon) / num_max_actions + epsilon / len(Q[state])
            W *= target_prob / behavior_prob

    呼び出す関数の指定

    呼び出す関数に関してはコマンドライン引数の値を使って作った関数名を実際の関数に eval しているだけです。

        # 文字列を関数に変換
        policy = "off" if args.off else "on"
        visits = "first" if args.first else "every"
        method = eval(policy + "_policy_" + visits + "_visit_mc")

    以下にソースコードを掲載位してあるので main の中身を見て確認してください。

    ソースコードの実行

    ソースコード

    import argparse
    import gymnasium as gym
    import numpy as np
    
    
    class MonteCarloAgent:
        def __init__(self, env, method, gamma, epsilon, epsilon_decay):
            self.env = env
            self.method = method
            self.gamma = gamma
            self.epsilon = epsilon
            self.epsilon_decay = epsilon_decay
    
            # モンテカルロ法による行動価値関数の計算
            self.Q = np.zeros((env.observation_space.n, env.action_space.n))
    
            # 各状態における行動の価値を計算するための変数(総和と回数)
            self.S = np.zeros((env.observation_space.n, env.action_space.n))
            self.C = np.zeros((env.observation_space.n, env.action_space.n))
    
        def reset(self, observation, info):
            self.state = observation
            self.samples = []
    
        def act(self):
            if np.random.rand() < self.epsilon:
                self.action = np.random.choice(self.env.action_space.n)
            else:
                # これだと一番最初に見つけた最大値を返すだけ
                #self.action = np.argmax(self.Q[self.state])
    
                # 最大値の行動が複数ある場合はランダムに選択する
                max_q_value = np.max(self.Q[self.state])
                max_q_value_indices = np.nonzero(self.Q[self.state] == max_q_value)[0]
                self.action = np.random.choice(max_q_value_indices)
    
            return self.action
    
        def learn(self, observation, reward, terminated, truncated, info):
            # エピソードの行動と観測値を記録する
            self.samples.append((self.state, self.action, reward))
    
            # エピソードが終了(terminated)。truncatedは無視する
            if terminated:
                # 行動価値関数を更新する
                self.method(self.Q, self.S, self.C, self.samples, self.gamma, self.epsilon)
    
                # 行動価値関数を表示する
                print_q_table(self.Q)
                print(f'Epsilon: {self.epsilon:.2f}\n')
    
                # イプシロンを徐々に減らしていく
                self.epsilon *= self.epsilon_decay
    
            # 状態を更新する
            self.state = observation
    
    
    # オンポリシー、初回訪問モンテカルロ法
    def on_policy_first_visit_mc(Q, S, C, samples, gamma, epsilon): # イプシロンは使わない
        # 各状態・行動のペアに対する初回訪問のステップ数を記録する
        first_visited_state_actions = {}
        for rstep, (state, action, reward) in enumerate(reversed(samples)):
            first_visited_state_actions[(state, action)] = rstep
    
        g = 0
        for rstep, (state, action, reward) in enumerated(reversed(samples)):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g
    
            # 初回訪問でなければ、その時点での価値を計算しない
            if first_visited_state_actions[(state, action)] != rstep:
                continue
    
            # この状態・行動のペアに対する価値の総和と回数を更新する
            S[state][action] += g
            C[state][action] += 1.0
    
            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]
    
    
    # オンポリシー、逐一訪問モンテカルロ法
    def on_policy_every_visit_mc(Q, S, C, samples, gamma, epsilon): # イプシロンは使わない
        g = 0
        for state, action, reward in reversed(samples):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g
    
            # この状態・行動のペアに対する価値の総和と回数を更新する
            S[state][action] += g
            C[state][action] += 1.0
    
            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]
    
    
    # オフポリシー、初回訪問モンテカルロ法
    def off_policy_first_visit_mc(Q, S, C, samples, gamma, epsilon):
        # 各状態・行動のペアに対する初回訪問のステップ数を記録する
        first_visited_state_actions = {}
        for rstep, (state, action, reward) in enumerate(reversed(samples)):
            first_visited_state_actions[(state, action)] = rstep
        
        g = 0
        W = 1
        for rstep, (state, action, reward) in enumerated(reversed(samples)):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g
    
            # 初回訪問でなければ、その時点での価値を計算しない
            if first_visited_state_actions[(state, action)] != rstep:
                continue
    
            # この状態・行動のペアに対する価値の総和と回数を更新する
            # Wは重点サンプリング比率
            S[state][action] += W * g
            C[state][action] += W
            #C[state][action] += 1.0
    
            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]
    
            # ターゲットポリシーに従って行動を選択するので
            # ターゲットポリシーと挙動ポリシーの行動が異なれば終了
            max_indices = np.nonzero(Q[state] == Q[state].max())[0]
            if action not in max_indices:
                break
    
            # 重点サンプリング比率を更新する。
            # ターゲットポリシーでも収束し始めるまでは複数の最大値を持つ行動を
            # 等確率で選択することを考慮する。
            num_max_actions = len(max_indices)
            target_prob = 1 / num_max_actions
            behavior_prob = (1 - epsilon) / num_max_actions + epsilon / len(Q[state])
            W *= target_prob / behavior_prob
    
    
    # オフポリシー、逐一訪問モンテカルロ法
    def off_policy_every_visit_mc(Q, S, C, samples, gamma, epsilon):
        g = 0
        W = 1
        for state, action, reward in reversed(samples):
            # この状態・行動のペアに対する価値を計算する
            g = reward + gamma * g
    
            # この状態・行動のペアに対する価値の総和と回数を更新する
            # Wは重点サンプリング比率
            S[state][action] += W * g
            #C[state][action] += 1.0
            C[state][action] += W
    
            # この状態・行動のペアに対する価値の平均を計算する
            Q[state][action] = S[state][action] / C[state][action]
    
            # ターゲットポリシーに従って行動を選択するので
            # ターゲットポリシーと挙動ポリシーの行動が異なれば終了
            max_indices = np.nonzero(Q[state] == Q[state].max())[0]
            if action not in max_indices:
                break
    
            # 重点サンプリング比率を更新する。
            # ターゲットポリシーでも収束し始めるまでは複数の最大値を持つ行動を
            # 等確率で選択することを考慮する。
            num_max_actions = len(max_indices)
            target_prob = 1 / num_max_actions
            behavior_prob = (1 - epsilon) / num_max_actions + epsilon / len(Q[state])
            W *= target_prob / behavior_prob
    
    
    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}')
    
            # ゲーム環境を初期化してエージェントに初期観測値を渡す
            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("--off"          , action="store_true")
        parser.add_argument("--first"        , action="store_true")
        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("--render_mode"  , type=str  , default="human")
        args = parser.parse_args()
        print(args)
    
        # 環境を作成
        env = gym.make('FrozenLake-v1',
                       map_name=args.map,
                       is_slippery=args.slippery,
                       render_mode=args.render_mode)
        
        # 文字列を関数に変換
        policy = "off" if args.off else "on"
        visits = "first" if args.first else "every"
        method = eval(policy + "_policy_" + visits + "_visit_mc")
    
        # エージェントを作成
        agent = MonteCarloAgent(env,
                                method,
                                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_mc.py といったファイルにセーブしておきます。

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

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

    usage: frozen_lake_mc.py [-h] [--map MAP] [--slippery] [--off] [--first]
                             [--gamma GAMMA] [--epsilon EPSILON] 
                             [--epsilon_decay EPSILON_DECAY]
                             [--max_episodes MAX_EPISODES]
    
    options:
      -h, --help            show this help message and exit
      --map MAP
      --slippery
      --off
      --first
      --gamma GAMMA
      --epsilon EPSILON
      --epsilon_decay EPSILON_DECAY
      --max_episodes MAX_EPISODES

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

    python frozen_lake_mc.py --slippery

    オフポリシーは次のように指定します。指定しないとオンポリシーになります。

    python frozen_lake_mc.py --off

    初回訪問モンテカルロ法は次のように指定します。指定しなけらば逐一訪問になります。

    python frozen_lake_mc.py --first

    組み合わせてオフポリシーの初回訪問にしたければ次のように指定します。

    python frozen_lake_mc.py --off --first

    デフォルトではオンポリシーの逐一訪問モンテカルロ法が使われます。

    その他、割引率(--gamma)、イプシロン(--epsilon)、イプシロン逓減率(--epsilon_decay)などの指定ができます。さらに、氷が滑る(--slippery)の指定もできます。

    結果だけを見たい時は画像なしにするとスピードが速くなります。

    python frozen_lake_mc.py --render_mode ""

    いろいろと組みわあせて試してください。

    実行結果

    このコードでは行動価値関数の値をエピソードごとにコンソールに出力しています。

    実際に実行してみると最初にゴールに到着するまでは、行動価値関数の値は全てゼロのままです。なぜならゴールに到着するまでは報酬はゼロだからです。穴に落ちてもペナルティもありません。

    なので、穴に落ちて終了したら報酬を-1にするとか変更したくなりますが、できるだけ環境に対する知識を手作業で取り入れないように注意を払って何もいじっていません。

    例えば、オンポリシーの逐一訪問を試したときには258回目のエピソードで初めてゴール到着のサンプルが生じました。そこからは徐々に収束し始めて最後のエピソードでは次のような結果となりました。

    State |  Action 0 |  Action 1 |  Action 2 |  Action 3 |
    ---------------------------------------------------------
        0 |     0.02  |     0.45  |     0.02  |     0.07  |
        1 |     0.04  |     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.57  |     0.00  |     0.02  |
        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.06  |     0.00  |     0.69  |     0.00  |
        9 |     0.07  |     0.80  |     0.15  |     0.00  |
       10 |     0.16  |     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.17  |     0.89  |     0.18  |
       14 |     0.38  |     0.36  |     1.00  |     0.00  |
       15 |     0.00  |     0.00  |     0.00  |     0.00  |

    まず状態0で行動1(下)が最大値なので下にある状態4に移動します。そこでも行動1(下)が最大値なのでさらに下にある状態8に移動します。そこでは行動2(左)が最大値なので左にある状態9に移動します。このように辿っていくと最終的に状態15へと到着するポリシーとなっています。

    また、オフポリシー初回訪問では次のような結果が出ました。

    State |  Action 0 |  Action 1 |  Action 2 |  Action 3 |
    ---------------------------------------------------------
        0 |     0.06  |     0.08  |     0.55  |     0.11  |
        1 |     0.15  |     0.00  |     0.64  |     0.12  |
        2 |     0.13  |     0.72  |     0.00  |     0.24  |
        3 |     0.13  |     0.00  |     0.24  |     0.17  |
        4 |     0.00  |     0.00  |     0.00  |     0.19  |
        5 |     0.00  |     0.00  |     0.00  |     0.00  |
        6 |     0.00  |     0.81  |     0.00  |     0.38  |
        7 |     0.00  |     0.00  |     0.00  |     0.00  |
        8 |     0.00  |     0.00  |     0.00  |     0.00  |
        9 |     0.00  |     0.00  |     0.54  |     0.00  |
       10 |     0.46  |     0.90  |     0.00  |     0.64  |
       11 |     0.00  |     0.00  |     0.00  |     0.00  |
       12 |     0.00  |     0.00  |     0.00  |     0.00  |
       13 |     0.00  |     0.00  |     0.90  |     0.00  |
       14 |     0.73  |     0.90  |     1.00  |     0.81  |
       15 |     0.00  |     0.00  |     0.00  |     0.00  |

    このポリシーでは状態1から右へ移動するようになっています。状態と行動を辿っていくと最終的にはゴールに到着するポリシーになっています。

    氷が滑る設定にすると動的計画法で得たのと同様に穴を裂けながらなんとかゴールを目指すポリシーが生じますが、動的計画法のように完璧なものにはなかなかなりませんでした。

    かなり長いこと探索を続ける必要があるのでこんな設定で実験しました。

    python frozen_lake_mc.py --slippery --epsilon_decay 0.99999 \
                             --max_episodes 200000 --render_mode ""

    結果は以下のようになり、なかなか良いのではないでしょうか。

    State |  Action 0 |  Action 1 |  Action 2 |  Action 3 |
    ---------------------------------------------------------
        0 |     0.03  |     0.02  |     0.02  |     0.02  |
        1 |     0.01  |     0.01  |     0.01  |     0.03  |
        2 |     0.04  |     0.02  |     0.03  |     0.02  |
        3 |     0.01  |     0.01  |     0.01  |     0.02  |
        4 |     0.05  |     0.03  |     0.03  |     0.02  |
        5 |     0.00  |     0.00  |     0.00  |     0.00  |
        6 |     0.06  |     0.06  |     0.08  |     0.01  |
        7 |     0.00  |     0.00  |     0.00  |     0.00  |
        8 |     0.03  |     0.06  |     0.05  |     0.09  |
        9 |     0.10  |     0.18  |     0.13  |     0.08  |
       10 |     0.24  |     0.20  |     0.18  |     0.06  |
       11 |     0.00  |     0.00  |     0.00  |     0.00  |
       12 |     0.00  |     0.00  |     0.00  |     0.00  |
       13 |     0.12  |     0.25  |     0.31  |     0.20  |
       14 |     0.31  |     0.60  |     0.56  |     0.48  |
       15 |     0.00  |     0.00  |     0.00  |     0.00  |

    ただし、状態10で右に行こうとすると穴に落ちる可能性があるなど問題点もあります。

    結局どれがいいの?

    答えはもちろん環境やポリシーでどのように探索をしたいのかによります。また、報酬構造にも大きく影響されるでしょう。

    挙動ポリシーとターゲットポリシーを別々にしたいならオフポリシーにする必要があります。そうでなければオンポリシーの方が実装が簡単です。

    重要なのは、モンテカルロのそれぞれの手法が理解できることの方でしょう。オンポリシーとオフポリシーについては今後のエージェントでも登場するので概念を理解しておくと良いと思います。

    それでは、次回はTD学習法について解説します。

    (続く)


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

    あなたへのおすすめ