MLエンジニアへの道 #41 - 時間差分学習

MLRL

Last Edited: 2/16/2025

この記事では、強化学習における時間差分学習について紹介します。

ML

これまで、MDPを解き近似するための2つのアプローチ、動的計画法とモンテカルロ法について説明してきました。 この記事では、これらの前述のアプローチの長所を組み合わせた手法である 時間差分学習 について説明します。

時間差分 (TD)

モンテカルロ法は、完全なモデルの前提を必要としないことで、DPの最大の問題を解決しました。 しかし、この手法はエピソードからの収益の平均を取り、状態行動価値を更新するため、 エピソードが完了した後でしか学習できません。大規模な環境では、エピソードの完了に時間がかかることが多く、反復が遅くなります。そこで、実際の収益を使用する代わりに、DPで行われる ように、ブートストラッピングを行い、次の状態の推定状態行動価値を使用して現在の状態行動価値を更新することができます。 これにより、完全なエピソードの完了を必要とせず、各時間ステップで価値を更新できる時間差分学習を確立することができます。

Q(s,a)=Q(s,a)+α[R+γQ(s′,a′)−Q(s,a)] Q(s, a) = Q(s, a) + \alpha[R + \gamma Q(s', a') - Q(s, a)]

上記は時間差分学習の更新規則を示しています。この更新規則は、α\alphaが単純平均または重み付き平均を取るための除数に対応し、 Q(s′,a′)Q(s', a')の代わりにGGが使用されるモンテカルロ法で使用される規則と非常に似ています。（前回の実装ではγ\gammaは1でした。） 次の状態と行動s′s'とa′a'は、目標ポリシーと同じ場合もあれば異なる場合もある行動ポリシーによって決定されます。 角括弧内の項は 時間差分誤差 であり、任意の学習率α\alphaを掛け経験から現在の状態行動価値を修正します。 時間差分学習は、反復が∞\inftyに近づくにつれて最適なポリシーに収束することが保証されています。

SARSA：オンポリシーTD制御

SARSA（State-Action-Reward-State-Action）は、同じ行動ポリシーと目標ポリシーを使用するオンポリシーTD制御です。 十分な探索を可能にするために、オンポリシーモンテカルロ法と同様にϵ\epsilon-貪欲ポリシーを使用します。 以下のコード実装はFrozenLakeEnvironmentにおけるSARSAを示しています。

def SARSA(env, num_episodes, epsilon, alpha=0.001, gamma=1):
  Q = np.zeros([16, 4])
 
  for episode in range(num_episodes):
      state, _ = env.reset()
      done = False
      if np.random.rand() > epsilon:
          action = np.argmax(Q[coord_to_num(state), :])
      else:
          action = env.action_space.sample()
 
      while not done:
          new_state, reward, done, _, _ = env.step(action)
          # epsilon-greedy for next action
          if np.random.rand() > epsilon:
            next_action = np.argmax(Q[coord_to_num(new_state), :])
          else:
            next_action = env.action_space.sample()
          TD = reward + gamma * Q[coord_to_num(new_state), next_action] - Q[coord_to_num(state), action]
          Q[coord_to_num(state), action] += alpha * TD
          state = new_state
          action = next_action
 
      if episode % 1000 == 0 and episode != 0:
        print(f"episode: {episode}/{num_episodes}")
 
  print(f"episode: {episode}/{num_episodes}")
 
  env.close()
 
  return Q
 
Q = SARSA(env, 100000, 0.4)

このアルゴリズムは、次の行動によって計算される時間差分誤差を使用する点を除いて、 モンテカルロ法で使用されるものと非常に似ています。価値反復と同様に、エピソードの完了を待つのではなく、 毎時間ステップで状態行動価値を更新します。 オンポリシーアルゴリズムであるため、 次の行動は同じϵ\epsilon-貪欲ポリシーによって決定されます。上記のコードを実行することで、 更新されたQによって決定されるポリシーが最適なϵ\epsilon-貪欲ポリシーになることを確認できます。

Q学習：オフポリシーTD制御

オフポリシーモンテカルロ制御法の問題は、重要度サンプリング比がゼロになるため、最初の非貪欲行動の後のエピソードの末尾からしか学習できないことです。 しかし、Q学習またはオフポリシーTD制御は、重要度サンプリング比の代わりに任意のα\alphaを使用し、 各ステップから学習するため、この問題を持ちません。以下のコード実装はFrozenLakeEnvironmentにおけるQ学習を示しています。

def Q_Learning(env, num_episodes, epsilon, alpha=0.001, gamma=1):
  Q = np.zeros([16, 4])
 
  for episode in range(num_episodes):
      state, _ = env.reset()
      done = False
 
      while not done:
          # epsilon greedy behavior policy
          if np.random.rand() > epsilon:
            action = np.argmax(Q[coord_to_num(state), :])
          else:
            action = env.action_space.sample()
          new_state, reward, done, _, _ = env.step(action)
          next_action = np.argmax(Q[coord_to_num(new_state), :]) # greedy target policy
          TD = reward + gamma * Q[coord_to_num(new_state), next_action] - Q[coord_to_num(state), action]
          Q[coord_to_num(state), action] += alpha * TD
          state = new_state
 
      if episode % 1000 == 0 and episode != 0:
        print(f"episode: {episode}/{num_episodes}")
 
  print(f"episode: {episode}/{num_episodes}")
 
  env.close()
 
  return Q
 
Q = Q_Learning(env, 100000, 0.4)

SARSAとの唯一の違いは、TDを計算するためのnext_actionの選択に貪欲な目標ポリシーを使用することです。 上記のコードを実行することで、更新されたQによって決定されるポリシーが最適な貪欲ポリシーになることを確認できます。 SARSAよりも信頼性高く滑らかに最適なポリシーに収束でき、 目標ポリシーがϵ\epsilon-ソフトポリシーである必要がないため、 強化学習における最も重要なブレークスルーの1つとしてしばしば見なされています。

適格度トレース

上記で説明した時間差分学習は、1ステップTDまたは TD(0) と呼ばれる特別なタイプのTDで、 前のステップのみを参照します。一方で価値反復のように1ステップだけを見るかわりに、 複数のステップを待ち、状態、行動、報酬などの関連情報を適格度トレースに保存し、 その適格度トレースに基づいて価値を更新することができます。適格度トレースを追加したTD学習は TD(λ\lambda) と呼ばれ、 1回の反復でより多くのステップを使用して価値を更新でき、場合によっては最適ポリシーへの収束をより速くすることができます。

TD(λ\lambda)は2つの方法で解釈できます。理論的な観点からは、TD(λ\lambda)は1回の反復でより多くのステップを組み込むという点で、 TD(0)とモンテカルロ法のスペクトラムの間に位置すると言えます。これは、TD(0)やモンテカルロ法よりも多くまたは少ないステップを予見するアプローチとして捉えるため、 通常 前方視点 と呼ばれます。もう一つの機械的な観点では、TD(λ\lambda)はトレースを振り返り、トレース内の状態行動ペアの価値を更新すると捉えられます。 これは 後方視点 と呼ばれます。練習として、後方視点に基づいてFrozenLakeEnvironmentのためのTD(λ\lambda)を用いたSARSAとQ学習を実装してみることをお勧めします。

結論

この記事では、DPにおけるブートストラッピングとモンテカルロ法における環境との相互作用を組み合わせた時間差分学習を紹介しました。 また、オンポリシーTD制御（SARSA）とオフポリシーTD制御（Q学習）について、それらの実装とともに説明しました。 次の記事では、ついに強化学習の文脈でどのように深層学習の力を活用できるかについて掘り下げていきます。

リソース

TOPに戻る↑