MLエンジニアへの道 #39

この記事では、強化学習における動的計画法アプローチについて紹介します。

前回の2つの記事では、マルコフ決定過程（MDP）と強化学習のためのGymnasiumについて紹介しました。問題の理解ができたところで、その解決方法について議論を始めることができます。この記事では、強化学習における動的計画法（DP）アプローチについて解説します。これは、今後議論する他の手法を理解するための重要な基礎となります。

(動的計画法についてよく分からないという場合、C++プログラマへの道 #19 - 動的計画法を読むことをお勧めします。)

動的計画法

前回の記事では、価値関数の再帰的構造を明らかにしたベルマン方程式について説明しました。これは、MDPが環境を完全にモデル化している場合、DPがこの再帰的関係を活用してMDPを解決できることを示唆しています。ただし、莫大な計算コストが伴います。現実には、完全なモデルという前提と高い計算コストがあるため、DPアプローチは実用的ではありません。しかし、理論的には非常に重要です。なぜなら、強化学習へのすべてのアプローチは、より少ない計算でDPと同じ効果を得ようとする試みとして解釈できるからです。

この文脈におけるDPアプローチの本質は、近似された価値に基づいてポリシーを改善し続け、それらがベルマン最適方程式によって与えられる価値に収束し、もはや改善されなくなるまで続けることです。全体のプロセスは ポリシー反復 と呼ばれ、価値を近似する ポリシー評価 と、これらの近似された価値に基づいてポリシーを改善する ポリシー改善 を繰り返し行います。

ポリシー評価

まず、現在のポリシーに基づいて改善を行うために、そのポリシーの価値関数を近似する必要があります。ここでのアルゴリズムである反復的ポリシー評価は、ベルマン方程式を更新規則として反復的に適用し、すべての状態の価値の近似を得ます。以下は、 $k$ ステップから $(k+1)$ ステップへの近似を改善するために使用される更新規則です。

v_{k+1}(s) = \sum_a \pi(a | s) \sum_{s',r} p(s', r | s, a)[r + \gamma v_k(s')]

初期状態として、すべての状態 $s$ に対して $v_0(s) = 0$ を設定し、その後、上記の更新規則を適用して期待値を徐々に計算していきます。（このプロセスは、ベルマン-フォードアルゴリズムが最小コストの経路を見つけるために推定値を徐々に更新していく方法に似ています。） $k$ が $\infty$ に近づくにつれて、各状態の影響がすべての他の状態に伝播していくため、実際の価値への収束が保証されます。収束は早期に発生する可能性があり、その場合は早期に終了してポリシー改善に移ることができます。以下は、前回の記事で設定したFrozenLakeEnvironmentに対するポリシー評価アルゴリズムのコードです。

## 座標とIDの変換
def num_to_coord(s):
  return [s // 4, s % 4]
 
def coord_to_num(coord):
  return coord[0] * 4 + coord[1]
 
  
## いかなる状態からでも行動できる
def transition_model(env, state, action):
  # エージェントが停止している場合、同じ状態を維持し報酬ゼロで返す
  if state == 15:
    return [[1, state, 0, True]]
  if state in [5, 7, 11, 12]:
    return [[1, state, 0, True]]
 
  # その他の場合、エージェントを所定の位置に配置し、動かす
  state = num_to_coord(state)
  env._agent_location = state
  direction = env._action_to_direction[action]
 
  env._agent_location = np.clip(
      env._agent_location + direction, 0, 3
  )
  success = np.array_equal(env._agent_location, env._target_location)
  fail = any([np.array_equal(env._agent_location, location) for location in env._hole_locations])
  terminated = any([success, fail])
  reward = 1 if success else 0
  observation = env._agent_location
  observation = coord_to_num(observation)
 
  # 行動の確率が非決定的な場合、[prob, observation, reward, terminated]がそれぞれの行動ごとに返される
  return [[1, observation, reward, terminated]]
 
## ポリシー評価
def policy_evaluation(env, policy, gamma=1, theta=1e-8, draw=False):
    V = np.zeros(16)
    while True:
        delta = 0 # 価値の変化
        for s in range(16):
            Vs = 0 # 状態の価値
            for a, action_prob in enumerate(policy[s]):
                for prob, next_state, reward, done in transition_model(env, s, a):
                    Vs += action_prob * prob * (reward + gamma * V[next_state]) # 更新規則
            delta = max(delta, np.abs(V[s]-Vs)) # マイナスな変化は0にする
            V[s] = Vs # 更新
        if draw: plot(V,policy,draw_vals=True)
        if delta < theta: # 価値の変化がthetaよりも小さい場合終了
            break
    return V
 
env = FrozenLakeEnvironment()
policy = np.ones([16, 4]) / 4 # ランダムに行動を選ぶポリシーからスタート
V = policy_evaluation(env, policy, draw=True)
# 結果の価値評価
# array([0.01393977, 0.01163091, 0.02095297, 0.01047648, 0.01624865,
#        0.        , 0.04075153, 0.        , 0.03480619, 0.08816993,
#        0.14205316, 0.        , 0.        , 0.17582037, 0.43929118,
#        0.        ])

すべての状態に更新規則を適用する必要があるため、まず任意の状態から行動を実行できるようにするtransition_modelを設定する必要があります。ポリシー評価を適用した後、現在のポリシーの下でのすべての状態の価値の近似であるVを使用して、ポリシーを改善することができます。

ポリシー改善

価値推定に基づいてポリシーを改善し、新しいポリシーが以前のポリシーより悪化しないことを保証する方法は、次の状態の価値を最大化する行動を選択する、つまり貪欲ポリシーを構築することです。これは状態-行動価値関数 $q_{\pi}(s, a)$ を使用して、数学的に以下のように表現できます。

\pi'(s) = \argmax_a q_{\pi}(s, a) \\ = \argmax_a \sum_{s', r} p(s', r | s, a)[r + \gamma v_{\pi}(s')]

現在のポリシーの下での価値関数が正確に推定されているため、新しい貪欲ポリシーが悪化しないことを保証できます。以下のように、コードでポリシー改善を実現できます。

## QをVから行ごとに作成
def q_from_v(env, V, s, gamma=1):
    q = np.zeros(4) # sに対応するQの行
    for a in range(4):
        for prob, next_state, reward, done in transition_model(env, s, a):
            q[a] += prob * (reward + gamma * V[next_state]) # ベルマン方程式
    return q
 
## ポリシー改善
def policy_improvement(env, V, gamma=1):
    policy = np.zeros([16, 4]) / 4 ## 新しいポリシー
    for s in range(16):
        q = q_from_v(env, V, s, gamma)
 
        # deterministic policy, will always choose an action (not capture the distribution)
        # policy[s][np.argmax(q)] = 1
 
        # 価値を最大化できる行動が複数の場合、それらの行動に均等に遷移確率を振り分ける
        best_a = np.argwhere(q==np.max(q)).flatten()
        policy[s] = np.sum([np.eye(4)[i] for i in best_a], axis=0)/len(best_a)
 
    return policy
 
new_policy = policy_improvement(env, V)
# ポリシー改善結果
# array([[0.  , 0.  , 1.  , 0.  ],
#        [0.  , 0.  , 0.  , 1.  ],
#        [0.  , 0.  , 1.  , 0.  ],
#        [0.  , 1.  , 0.  , 0.  ],
#        [0.  , 0.  , 1.  , 0.  ],
#        :
#        [0.25, 0.25, 0.25, 0.25],
#        [0.25, 0.25, 0.25, 0.25],
#        [0.  , 0.  , 0.  , 1.  ],
#        [0.  , 0.  , 0.  , 1.  ],
#        [0.25, 0.25, 0.25, 0.25]])

ここまでで、ポリシーの価値を近似する方法と、それに基づいてポリシーを改善する方法を確立しました。目標は、ベルマン最適方程式に対応する最適ポリシーに到達することです。そのために、価値が収束するまでこのポリシー評価と改善のサイクルを繰り返し実行するだけです。以下は、ポリシー反復の実装コードです。

def policy_iteration(env, gamma=1, theta=1e-8):
    policy = np.ones([16, 4]) / 4
    while True:
 
        # ポリシー評価
        V = policy_evaluation(env, policy, gamma, theta)
 
        # ポリシー改善
        new_policy = policy_improvement(env, V)
 
        if np.max(abs(policy_evaluation(env, policy) - policy_evaluation(env, new_policy))) < theta*1e2:
           break
 
        policy = copy.copy(new_policy)
    return policy, V
 
policy, V = policy_iteration(env)

完全なモデルと無制限の計算リソースという前提の下で、ポリシー反復を使用してMDPを解くことができます。

価値反復

ポリシー反復アプローチの問題点は、ポリシー評価における反復回数に制限がないことです。単純なケースでは、このアプローチで非常に早く収束に達することができますが、 価値反復 と呼ばれるプロセスでは、ポリシー評価で1回の反復だけを行っても収束を保証できます。価値反復法は、更新規則にベルマン方程式の代わりにベルマン最適方程式を使用し、実質的にポリシー評価と改善を組み合わせたものとしても考えることができます。

v_{k+1}(s) = \argmax_a \sum_{s',r} p(s', r | s, a)[r + \gamma v_k(s')]

最適ポリシーはどのみち最も高い価値を持つ状態に移動するための行動を選択するため、最も価値のある状態のみで価値を更新することは直感的に理にかなっています。以下は価値反復の実装コードを示しています。

def value_iteration(env, gamma=1, theta=1e-8):
    V = np.zeros(16)
    # ベルマン最適方程式を用いたポリシー評価とポリシー改善の組み合わせ
    while True:
        delta = 0
        for s in range(16):
            v_s = V[s]
            q_s = q_from_v(env, V, s, gamma)
            V[s] = max(q_s) # 状態行動価値の最大
            delta = max(delta, abs(V[s] - v_s))
        if delta < theta: break
    # 最後に最適なポリシーを得る
    policy = policy_improvement(env, V, gamma)
    return policy, V
 
policy, V = value_iteration(env)

価値反復における反復回数は、1回の反復あたりの価値推定の変化が小さくなるため増加する可能性があり、ポリシー評価の反復をいくつか追加することで、より早い収束につながる可能性があります。ただし、どのアプローチも最終的には最適ポリシーに収束します。

結論

この記事では、MDP（マルコフ決定過程）を解決するための動的計画法アプローチ、ポリシー反復、そして価値反復について説明しました。このアプローチは、後続の状態から状態の推定値を更新するためのメモ化の使用によって特徴付けられ、具体的には ブートストラッピング と呼ばれます。完全なモデルを前提としないものでも、多くのアプローチがブートストラッピング技法を使用しています。次の記事では、ブートストラッピングを使用せず完全なモデルを前提とするアプローチについて説明し、その次の記事では、ブートストラッピングを使用するが完全なモデルを前提としないアプローチについて説明します。

リソース

cwkx. 2022. Reinforcement Learning 4: Dynamic programming. YouTube.
Sutton, S. R. & Barto, G. A. 2015. Reinforcement Learning: An Introduction. Stanford.