E資格対策・強化学習の重要数式の覚え方(8)Q学習の更新式を語呂合わせと計算例で確実に覚える

こんにちは。ゆうせいです。

E資格の強化学習で出題される重要数式を、1つずつ覚えていくシリーズの第8回です。

前回は、次の状態で実際に選んだ行動を使って行動価値を学ぶ「SARSA」を学びました。今回は、強化学習の手法の中で最もよく知られている「Q学習」を取り上げます。

Q学習の更新式は、SARSAの更新式と1か所しか違いません。しかし、その1か所の違いによって、SARSAは「方策オン型」、Q学習は「方策オフ型」という別の性格を持つ手法になります。E資格では、この違いが繰り返し問われます。また、次回学ぶDQNは、Q学習をニューラルネットワークで行う手法です。

この記事のゴール

  • Q学習の更新式を、何も見ずに書けるようになる
  • SARSAの更新式との違いを説明できるようになる
  • 「方策オフ型」の意味を説明できるようになる
  • Q学習の更新を手計算できるようになる

これまでの復習

前回学んだSARSAの更新式を確認します。

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]

覚え方は次のとおりでした。

  • サルサは5ステップで踊る。エス、エー、アール、エス、エー
  • ブイをキューに、次は実際の一手
  • サルサは有言実行(方策オン型)

また、第5回で学んだベルマン最適方程式(行動価値の形)も確認しておきます。

Q^{*}(s, a) = \sum_{s', r} p(s', r \mid s, a) [r + \gamma \max_{a'} Q^{*}(s', a')]

覚え方は「ピーで分かれて、ある我慢、次のマックスキュー」でした。今回のQ学習は、このかっこの中の部分を目標値として使います。

Q学習の更新式

今回覚える式は次のとおりです。

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t)]

SARSAの更新式と並べてみます。

SARSA:

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]

Q学習:

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t)]

違いは、目標値の中の「次の Q 値」の部分だけです。

部分SARSAQ学習
目標値の次の Q 値Q(S_{t+1}, A_{t+1})\max_{a'} Q(S_{t+1}, a')
意味次の状態で実際に選んだ行動の Q 値次の状態で Q 値が最大になる行動の Q 値
方策の分類方策オン型方策オフ型

Q学習のTD誤差だけを取り出すと、次のようになります。

\delta_t = R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t)

式全体を日本語にすると、次のようになります。

「今の状態で選んだ行動の Q 値を、すぐもらえた報酬と、次の状態で一番良い行動を選んだときの Q 値(割り引いたもの)の合計に、ある程度だけ近づける」

式の意味:次は最善を尽くすと仮定して答え合わせ

Q学習の目標値は、「次の状態では、必ず一番良い行動を選ぶ」と仮定したときの見積もりです。

将棋の練習で考えてみます。対局中、ときどき新しい戦法を試すために、わざと普段と違う手を指すとします。

  • SARSA:「次も、ときどき変わった手を指すかもしれない」という自分のくせを含めて、今の手の良さを評価する
  • Q学習:「次からは最善の手を指す」と仮定して、今の手の良さを評価する

Q学習は、実際の自分の行動にとらわれず、「最善を尽くした場合の価値」を学習します。そのため、繰り返し学習すると、Q 値は第5回で学んだ最適行動価値 Q^{*} に近づいていきます。

練習問題1

Q学習の更新式として正しいものを選んでください。

  • ア:Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]
  • イ:Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t)]
  • ウ:Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_{a'} Q(S_t, a') - Q(S_t, A_t)]
  • エ:Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [\gamma R_{t+1} + \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t)]

練習問題1の解答と解説

正解はイです。

目標値に、次の状態での Q 値の最大値 \max_{a'} Q(S_{t+1}, a') を使っています。

  • アは誤りです。次の状態で実際に選んだ行動の Q 値を使っているので、SARSAの更新式です。
  • ウは誤りです。max を取る Q 値の状態が、次の状態ではなく今の状態 S_t になっています。
  • エは誤りです。割引率 γ が報酬に掛かっています。γ が掛かるのは次の状態の Q 値です。

語呂合わせで覚える

語呂合わせ1:Q(キュー)学習は究極(きゅうきょく)の一手

Q学習の目標値には、次の状態で選べる行動の中で最も良い一手、つまり「究極の一手」の Q 値が入ります。

覚え方は「キュー学習は、究極(きゅうきょく)の一手で答え合わせ」です。

SARSAの語呂合わせ「次は実際の一手」と対にして覚えると、2つの手法の違いがはっきりします。

  • SARSA:次は実際の一手
  • Q学習:次は究極の一手

語呂合わせ2:次のマックスキュー

Q学習の目標値 R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') は、第5回のベルマン最適方程式のかっこの中とまったく同じ形です。

覚え方は「Q学習は、ある我慢、次のマックスキュー」です。

ベルマン最適方程式には、遷移確率 p による平均(ピーで分かれて)が含まれていました。Q学習では、遷移確率が分からない代わりに、実際に経験した1回分の結果を使います。そして、学習率 α で少しずつ更新を重ねることで、平均を取ったのと同じ効果を得ます。

式環境の分かれ道の扱い目標の形
ベルマン最適方程式遷移確率 p で平均する(ピーで分かれて)ある我慢、次のマックスキュー
Q学習実際の経験1回分を使い、α で少しずつ平均するある我慢、次のマックスキュー

語呂合わせ3:大文字は実際、小文字は候補

Q学習の式では、max の中の行動が小文字の a' になっています。SARSAでは大文字の A_{t+1} でした。

  • 大文字の A_{t+1}:次の状態で実際に選んだ1つの行動
  • 小文字の a':次の状態で選べるすべての行動の候補

Q学習では、実際に選んだ行動ではなく、すべての候補の中から Q 値が最大のものを探すので、小文字の a' を使います。第2回で学んだ「大文字は箱、小文字は箱に入る中身」の考え方を発展させて、「大文字は実際、小文字は候補」と覚えましょう。

語呂合わせ4:オフ型は、行動と学習が離れている

Q学習は「方策オフ型」の手法に分類されます。

方策オフ型とは、「実際に行動するときに使う方策(行動方策)」と「価値を学習している方策(ターゲット方策)」が異なっていてもよい手法のことです。

Q学習では、2つの方策が次のように分かれています。

方策の種類Q学習での中身役割
行動方策ε-greedy 法など実際に行動を選ぶ。探索のためにランダムな行動も選ぶ
ターゲット方策常に Q 値が最大の行動を選ぶ方策(greedy 方策)学習の目標になる。max の部分に対応する

実際にはときどきランダムな行動を試しながら、学習の目標は「常に最善の行動を選ぶ方策」の価値になっています。行動している方策と、学習している方策が切り離されている(オフになっている)ので、方策オフ型と呼びます。

覚え方は「オフ型は、行動と学習が離れている。キュー学習は、口では最善、足では冒険」です。

前回の「サルサは有言実行」と対にして覚えましょう。SARSAは学習に使った行動をそのまま実行しますが、Q学習は学習では最善の行動を仮定しつつ、実際の行動では探索も行います。

練習問題2

方策オフ型の手法の説明として、最も適切なものを選んでください。

  • ア:行動を選ぶ方策と、学習する方策が常に同じである手法
  • イ:行動価値ではなく、状態価値だけを学習する手法である
  • ウ:環境の遷移確率を事前に知っている必要がある手法である
  • エ:行動を選ぶ方策と、学習する方策が異なっていてもよい手法

練習問題2の解答と解説

正解はエです。

方策オフ型では、実際に行動を選ぶ方策(行動方策)と、価値を学習する方策(ターゲット方策)が異なっていても構いません。

  • アは誤りです。2つの方策が常に同じなのは、方策オン型の説明です。SARSAが該当します。
  • イは誤りです。方策オン型かオフ型かは、学習する対象が状態価値か行動価値かとは関係ありません。Q学習は行動価値を学習します。
  • ウは誤りです。Q学習はTD学習の一種なので、遷移確率を知らなくても経験から学習できます。

Q学習の手順

Q学習の学習は、次の手順で進みます。

  1. 状態 S_t で、ε-greedy 法などを使って行動 A_t を選ぶ
  2. 行動 A_t を実行し、報酬 R_{t+1} と次の状態 S_{t+1} を観測する
  3. 次の状態 S_{t+1} での Q 値の最大値を使って、Q(S_t, A_t) を更新する
  4. 次の状態を今の状態にして、手順1に戻る

SARSAの手順と比べると、「次の行動を選んでから更新する」という手順がなくなっています。Q学習の更新に必要なのは、状態、行動、報酬、次の状態の4つだけです。次の行動は、更新の後に改めて選びます。

手法更新に必要な要素要素の数
SARSAS_t、A_t、R_{t+1}、S_{t+1}、A_{t+1}5つ
Q学習S_t、A_t、R_{t+1}、S_{t+1}4つ

覚え方は「サルサは5ステップ、キュー学習は4ステップ」です。

次の行動が更新に必要ないことは、方策オフ型であることの表れでもあります。実際にどの行動を選んだかに関係なく更新できるので、過去に別の方策で集めた経験データを使って学習することもできます。この性質は、次回学ぶDQNの「経験再生」で活かされます。

計算例で確かめる

計算例1:基本の更新

次の状況を考えます。

  • 今の Q 値:Q(S_t, A_t) = 2
  • すぐもらえた報酬:R_{t+1} = 1
  • 次の状態での Q 値:行動 a_1 が 4、行動 a_2 が -2
  • 割引率 γ = 0.9、学習率 α = 0.1

まず、次の状態での Q 値の最大値を求めます。4 と -2 のうち、最大は 4 です。

次に、TD誤差を計算します。

\delta_t = 1 + 0.9 \times 4 - 2 = 1 + 3.6 - 2 = 2.6

最後に、Q 値を更新します。

Q(S_t, A_t) \leftarrow 2 + 0.1 \times 2.6 = 2.26

計算例2:次の行動がランダムに選ばれても結果は変わらない

前回のSARSAの計算例2では、次の行動としてたまたま a_2 が選ばれると、更新後の Q 値が 1.72 に下がりました。

Q学習では、次に実際にどの行動を選ぶかは更新に関係しません。常に最大値の 4 を使うので、次に a_1 を選んでも a_2 を選んでも、更新後の Q 値は 2.26 になります。

次に実際に選んだ行動SARSAの更新後Q学習の更新後
a_1(Q 値 4)2.262.26
a_2(Q 値 -2)1.722.26

Q学習は、探索のために悪い行動を選んでしまっても、その影響を受けずに「最善を尽くした場合の価値」を学習します。これが方策オフ型の特徴です。

練習問題3

次の状況で、Q学習による更新後の Q(S_t, A_t) の値を選んでください。

  • 今の Q 値:Q(S_t, A_t) = 3
  • すぐもらえた報酬:R_{t+1} = 2
  • 次の状態で実際に選んだ行動の Q 値:6
  • 次の状態での Q 値の最大値:14
  • 割引率 γ = 0.5、学習率 α = 0.5
  • ア:6.0
  • イ:4.0
  • ウ:9.5
  • エ:9.0

練習問題3の解答と解説

正解はアです。

Q学習では、次の状態での Q 値の最大値 14 を使います。

\delta_t = 2 + 0.5 \times 14 - 3 = 2 + 7 - 3 = 6

Q(S_t, A_t) \leftarrow 3 + 0.5 \times 6 = 3 + 3 = 6

  • イの4.0は、実際に選んだ行動の Q 値 6 を使った値です。これは前回のSARSAの練習問題3の答えです。
  • ウの9.5は、割引率を掛け忘れた値です。δ = 2 + 14 − 3 = 13 となり、3 + 0.5 × 13 = 9.5 となります。
  • エの9.0は、学習率を掛け忘れた値です。3 + 6 = 9 となり、ズレを全部反映しています。

前回のSARSAの練習問題3とまったく同じ数値です。2つの答えを見比べると、使う Q 値の違いがよく分かります。

計算例3:Qテーブルが更新されていく様子

次の一本道を考えます。

  • 状態 s_1 で「右」を選ぶと、状態 s_2 に移り、報酬 0 をもらう
  • 状態 s_2 で「右」を選ぶと、終端状態に移り、報酬 10 をもらう
  • 割引率 γ = 0.9、学習率 α = 0.5
  • Qテーブルの値は、すべて 0 から始める

1回目のエピソードです。

  • Q(s_1, right) の更新:次の状態 s_2 での最大値は 0 なので、0 + 0.5 × (0 + 0.9 × 0 − 0) = 0
  • Q(s_2, right) の更新:次は終端状態なので、0 + 0.5 × (10 − 0) = 5

2回目のエピソードです。

  • Q(s_1, right) の更新:次の状態 s_2 での最大値は 5 なので、0 + 0.5 × (0 + 0.9 × 5 − 0) = 2.25
  • Q(s_2, right) の更新:5 + 0.5 × (10 − 5) = 7.5
エピソードQ(s_1, right)Q(s_2, right)
開始時00
1回目の後05
2回目の後2.257.5
本当の最適値910

第6回のTD学習と同じく、ゴールの報酬がバケツリレーのように後ろから前へ伝わっていきます。回数を重ねると、Q 値は本当の最適行動価値に近づいていきます。

練習問題4

次の状態が終端状態であるとします。今の Q 値が 2、すぐもらえた報酬が 6、学習率 α = 0.25 のとき、Q学習による更新後の Q 値を求めてください。

練習問題4の解答と解説

答えは3です。

次の状態が終端状態のときは、その後に選べる行動がないので、max の部分は 0 として計算します。

  • TD誤差:δ = 6 + γ × 0 − 2 = 4
  • 更新後:Q = 2 + 0.25 × 4 = 3

Q学習の性格と注意点

崖歩きでは最短の道を学習する

前回紹介した「崖歩き」の問題では、Q学習は崖のそばを通る最短の道を学習します。「次は必ず最善の行動を取る」と仮定しているため、探索中のランダムな一歩で崖に落ちる危険を考慮しないからです。

学習した Q 値に従って、探索をやめて最善の行動だけを取るようになれば、最短の道を安全に進めます。一方、学習中も ε-greedy 法で探索を続けていると、ときどき崖に落ちてしまいます。

覚え方は「サルサは慎重派、キュー学習は理想派」です。

Q 値を大きく見積もりすぎることがある

Q学習の目標値には max が含まれています。学習の途中の Q 値には誤差があるため、たまたま大きめに見積もられた値が max で選ばれやすくなります。その結果、Q 値が本当の値よりも大きく見積もられる傾向があります。この現象を過大評価と呼びます。

たとえば、本当はどの行動の価値も 0 なのに、誤差によって Q 値が 1、-1、0.5 と推定されていたとします。max を取ると 1 が選ばれるので、目標値は本当の値 0 よりも大きくなってしまいます。

この問題を和らげるために考えられたのが、Double Q学習や、次回紹介する Double DQN です。

最適な行動価値に収束する

Q学習は、すべての状態と行動の組み合わせを十分な回数試し、学習率を適切に小さくしていくなどの条件を満たせば、最適行動価値 Q^{*} に収束することが知られています。方策オフ型なので、探索のためにランダムな行動を混ぜていても、最適な価値を学習できるのが大きな利点です。

練習問題5

Q学習について、適切でないものを選んでください。

  • ア:目標値には、次の状態での Q 値の最大値を使う
  • イ:行動は ε-greedy 法で選びながら、最適な Q を学習できる
  • ウ:更新には、次の状態で実際に選んだ行動が必ず必要になる
  • エ:最大値を取るため、Q 値を大きく見積もりすぎることがある

練習問題5の解答と解説

正解はウです。

Q学習の更新に必要なのは、状態、行動、報酬、次の状態の4つです。次の状態で実際に選んだ行動は使いません。次の行動が必要になるのは、前回学んだSARSAです。

  • アは正しい説明です。「キュー学習は、究極の一手で答え合わせ」のとおりです。
  • イは正しい説明です。方策オフ型なので、探索しながらでも最適な Q を学習できます。
  • エは正しい説明です。max による過大評価の問題です。

SARSAとQ学習の比較まとめ

試験直前の確認用に、2つの手法を1つの表にまとめます。

項目SARSAQ学習
目標値R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a')
次の Q 値実際の一手究極の一手
方策の分類方策オン型(有言実行)方策オフ型(口では最善、足では冒険)
更新に必要な要素5つ(5ステップ)4つ(4ステップ)
学習する価値探索を含む実際の方策の価値最適な方策の価値
崖歩きで学習する道安全な道(慎重派)最短の道(理想派)
関連するベルマン方程式ベルマン期待方程式ベルマン最適方程式

初学者がつまずきやすい点

つまずきやすい点正しい理解
目標値に実際に選んだ行動の Q 値を使うQ学習は次の状態での Q 値の最大値を使う。究極の一手
max の中を今の状態 S_t にするmax を取るのは次の状態 S_{t+1} での Q 値
max の中の行動を大文字で書くすべての候補から選ぶので小文字の a'。大文字は実際、小文字は候補
方策オン型とオフ型を逆に覚えるサルサは有言実行(オン)、キュー学習は口では最善、足では冒険(オフ)
Q学習では探索しなくてよいと考える行動方策では ε-greedy 法などで探索し、学習の目標だけを最善にする
終端状態でも max を計算しようとする終端状態の後に行動はないので、max の部分は 0

白紙に書いて確認しよう

記事を読み終えたら、何も見ずに次の5つを紙に書いてみてください。

  1. Q学習の更新式
  2. Q学習のTD誤差
  3. SARSAの更新式(Q学習との違いを確認するため)
  4. 方策オン型と方策オフ型の違い(一言ずつ)
  5. Q学習の目標値と、ベルマン最適方程式のかっこの中が同じ形であること

書き終えたら、max の位置、max の中が次の状態になっているか、max の中の行動が小文字のダッシュ付きになっているかの3点を確認してください。

まとめ

  • Q学習は、次の状態での Q 値の最大値を目標値に使って、行動価値を学習する手法です
  • SARSAの「次は実際の一手」を「次は究極の一手」に変えると、Q学習の更新式になります
  • 目標値は、ベルマン最適方程式と同じ「ある我慢、次のマックスキュー」の形です
  • max の中の行動は小文字の a' です。大文字は実際、小文字は候補です
  • 行動方策と学習する方策が分かれている方策オフ型です。口では最善、足では冒険です
  • 更新に必要な要素は4つです。サルサは5ステップ、キュー学習は4ステップです
  • max を使うため、Q 値を過大評価しやすいという注意点があります

次回は、Q学習の Q テーブルをニューラルネットワークに置き換えた「DQN(Deep Q-Network)」の損失関数を取り上げます。今回の目標値「ある我慢、次のマックスキュー」が、そのまま損失関数の中に登場します。今回の更新式を白紙に書ける状態にしてから読み進めてください。

投稿者プロフィール

山崎講師
山崎講師代表取締役
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
海外放浪の末、2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します!
この記事に間違い等ありましたらぜひお知らせください。

学生時代は趣味と実益を兼ねてリゾートバイトにいそしむ。長野県白馬村に始まり、志賀高原でのスキーインストラクター、沖縄石垣島、北海道トマム。高じてオーストラリアのゴールドコーストでツアーガイドなど。現在は野菜作りにはまっている。