E資格対策・強化学習の重要数式の覚え方(5)ベルマン最適方程式を語呂合わせと計算例で確実に覚える

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

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

前回は、方策 π に従ったときの価値を表す「ベルマン期待方程式」を学びました。今回は、最も良い方策に従ったときの価値を表す「ベルマン最適方程式」を取り上げます。

ベルマン最適方程式は、前回の式のごく一部を書き換えただけの式です。しかし、試験ではその「ごく一部」の違いが繰り返し問われます。また、第8回のQ学習と第9回のDQNは、この式をもとに作られています。前回の式と見比べながら、違いを確実に押さえていきましょう。

この記事のゴール

  • ベルマン最適方程式(状態価値の形と行動価値の形)を、何も見ずに書けるようになる
  • ベルマン期待方程式との違いを説明できるようになる
  • max を置く位置が、状態価値の形と行動価値の形で違う理由を説明できるようになる
  • 簡単な例で、最適な価値と最適な行動を計算できるようになる

第4回の復習

前回のベルマン期待方程式を確認します。

V^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) [r + \gamma V^{\pi}(s')]

覚え方は「パイで分かれて、ピーで分かれて、ある我慢ブイ」でした。

  • パイで分かれて:エージェントが方策 π で行動を選ぶ
  • ピーで分かれて:環境が遷移確率 p で次の状態と報酬を決める
  • ある我慢ブイ:すぐの報酬と、割り引いた次の状態の価値を足す

また、第3回では次の2つの関係も学びました。

  • 方策 π に従うとき:V^{\pi}(s) = \sum_{a} \pi(a \mid s) Q^{\pi}(s, a)(平均)
  • 最適な場合:V^{*}(s) = \max_{a} Q^{*}(s, a)(最大)

今回の内容は、この「平均」と「最大」の違いをベルマン方程式に当てはめたものです。

ベルマン最適方程式の式

今回覚える式は、状態価値の形と行動価値の形の2つです。

状態価値の形:

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

行動価値の形:

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

記号の意味は、これまでに学んだものと同じです。

記号意味
V^{*}(s)最適状態価値。最も良い方策に従ったときの状態 s の価値
Q^{*}(s, a)最適行動価値。状態 s で行動 a を選び、その後は最も良い方策に従ったときの価値
\max_{a}すべての行動 a の中で、最大の値を選ぶ
\max_{a'}次の状態 s' で選べるすべての行動 a' の中で、最大の値を選ぶ

状態価値の形を日本語にすると、次のようになります。

「最適な状態価値は、行動ごとに(すぐの報酬 + γ × 次の状態の最適な価値)の平均を求め、その中で最も大きいものに等しい」

ベルマン期待方程式との違い

2つの式を並べてみます。

期待方程式:

V^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) [r + \gamma V^{\pi}(s')]

最適方程式:

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

違いは次の2か所だけです。

違い期待方程式最適方程式
行動の分かれ道\sum_{a} \pi(a \mid s)(方策の確率で平均)\max_{a}(最も良い行動を選ぶ)
価値の記号右肩が π右肩が *(アスタリスク)

遷移確率 p の部分と、「ある我慢ブイ」の部分は変わりません。

練習問題1

ベルマン期待方程式とベルマン最適方程式の違いとして、最も適切なものを選んでください。

  • ア:最適方程式では、遷移確率 p による平均が max に置き換わる
  • イ:最適方程式では、方策 π による平均が max に置き換わる
  • ウ:最適方程式では、割引率 γ が常に1として扱われる
  • エ:最適方程式では、すぐにもらえる報酬 r が式から消える

練習問題1の解答と解説

正解はイです。

期待方程式の「パイで分かれて」の部分が、最適方程式では「最も良い行動を選ぶ(max)」に置き換わります。

  • アは誤りです。遷移確率 p による平均は、最適方程式でもそのまま残ります。理由は次の語呂合わせで説明します。
  • ウは誤りです。割引率 γ の扱いは期待方程式と同じです。
  • エは誤りです。「ある我慢ブイ」の部分はそのまま残るので、報酬 r も式に含まれます。

語呂合わせで覚える

語呂合わせ1:期待はパイ、最適はマックス

前回の語呂合わせの「パイ」を「マックス」に入れ替えるだけで、最適方程式の状態価値の形になります。

  • 期待方程式:パイで分かれて、ピーで分かれて、ある我慢ブイ
  • 最適方程式:マックスで選んで、ピーで分かれて、ある我慢ブイ

覚え方は「期待はパイ、最適はマックス」です。

方策 π に従うときは、行動を確率で選ぶので「平均」を取ります。最適な場合は、一番良い行動だけを選ぶので「最大」を取ります。第3回で学んだ「方策 π に従うときは平均、最適な場合は最大」と同じ考え方です。

語呂合わせ2:選べるところはマックス、選べないところは平均

試験で特によく問われるのが、「なぜ遷移確率 p の部分は max にならないのか」という点です。

その理由は、次の2つの分かれ道の性質の違いにあります。

  • 行動の分かれ道:エージェント自身が選べる。だから一番良いものを選べる(max)
  • 環境の分かれ道:エージェントには選べない。環境が確率で決める(平均)

サイコロを振るゲームで考えてみます。「サイコロを振るか、振らないか」は自分で選べますが、「どの目が出るか」は自分では選べません。どんなに最適な行動を取っても、出る目は運に任せるしかないため、平均で評価するしかないのです。

覚え方は「選べるところはマックス、選べないところは平均」です。

この語呂合わせを覚えておけば、max を遷移確率 p の外側(行動の分かれ道)に置くことを迷わずに書けます。

練習問題2

ベルマン最適方程式(状態価値の形)として正しいものを選んでください。

  • ア:V^{*}(s) = \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) [r + \gamma V^{*}(s')]
  • イ:V^{*}(s) = \max_{s', r} \sum_{a} p(s', r \mid s, a) [r + \gamma V^{*}(s')]
  • ウ:V^{*}(s) = \max_{a} \sum_{s', r} p(s', r \mid s, a) [\gamma r + V^{*}(s')]
  • エ:V^{*}(s) = \max_{a} \sum_{s', r} p(s', r \mid s, a) [r + \gamma V^{*}(s')]

練習問題2の解答と解説

正解はエです。

「マックスで選んで、ピーで分かれて、ある我慢ブイ」の順に並んでいます。

  • アは誤りです。行動の分かれ道が方策 π による平均のままです。最適方程式では max を取ります。
  • イは誤りです。max を取る対象が、次の状態と報酬になっています。環境の分かれ道は選べないので、max ではなく平均を取ります。
  • ウは誤りです。割引率 γ が報酬 r に掛かっています。割り引くのは次の状態の価値です。

行動価値の形を覚える

語呂合わせ3:ブイは外でマックス、キューは中でマックス

2つの形を比べると、max を置く位置が違います。

状態価値の形(max が式の外側、先頭にある):

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

行動価値の形(max が式の内側、かっこの中にある):

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

覚え方は「ブイは外でマックス、キューは中でマックス」です。

位置が違う理由は、それぞれの関数が「どこから始まるか」にあります。

  • 状態価値 V^{*}(s):今の状態 s から始まるので、最初に「今の行動」を選ぶ必要がある。だから max が先頭(外側)に来る
  • 行動価値 Q^{*}(s, a):今の行動 a はすでに決まっている。そのため、今の行動を選ぶ必要はなく、次の状態 s' で「次の行動 a'」を選ぶところで max を取る。だから max が内側に来る

第3回で学んだ「Qは場所と一手」のとおり、Q は最初の一手がすでに決まっています。最初の一手を選ばなくてよい分、max は一歩先の行動に移ります。

語呂合わせ4:ピーで分かれて、ある我慢、次のマックスキュー

前回、行動価値の形のベルマン期待方程式を「ピーで分かれて、ある我慢、次のパイキュー」と覚えました。最適方程式では「パイ」が「マックス」に変わります。

覚え方は「ピーで分かれて、ある我慢、次のマックスキュー」です。

かっこの中の \max_{a'} Q^{*}(s', a') には、a にも s にもダッシュが付いています。「次の状態で、次の行動を選ぶ」ので、両方にダッシュが付くことを確認しましょう。前回の「ダッシュ(')で次の状態へダッシュ」のとおりです。

Q学習とのつながり

行動価値の形のかっこの中は、次のようになっています。

r + \gamma \max_{a'} Q^{*}(s', a')

この形は、第8回で学ぶQ学習の更新式と、第9回で学ぶDQNの損失関数に、そのまま登場します。Q学習は、遷移確率 p が分からなくても、実際の経験を使ってこの式を満たすように Q の値を少しずつ近づけていく手法です。

「マックスキュー」の部分が書ければ、Q学習とDQNの式の半分は書けたことになります。

練習問題3

状態 s で行動 a を選んだとき、環境は次のように反応するとします。割引率は γ = 0.5 です。

  • 確率 0.5 で状態 x に移り、報酬 1 をもらう。状態 x での最適行動価値は、行動 b_1 が 4、行動 b_2 が 8
  • 確率 0.5 で状態 y に移り、報酬 2 をもらう。状態 y での最適行動価値は、行動 b_1 が 6、行動 b_2 が 2

最適行動価値 Q^{*}(s, a) の値を選んでください。

  • ア:4.0
  • イ:8.5
  • ウ:5.0
  • エ:5.5

練習問題3の解答と解説

正解はウです。

「ピーで分かれて、ある我慢、次のマックスキュー」を使います。まず、次の状態ごとに、最大の行動価値を選びます。

  • 状態 x:4 と 8 のうち最大は 8
  • 状態 y:6 と 2 のうち最大は 6

次に、場合ごとに「すぐの報酬 + γ × 次のマックスキュー」を計算します。

  • 状態 x に移る場合:1 + 0.5 × 8 = 5
  • 状態 y に移る場合:2 + 0.5 × 6 = 5

最後に、遷移確率で平均します。

Q^{*}(s, a) = 0.5 \times 5 + 0.5 \times 5 = 5

  • アの4.0は、max ではなく平均を取った値です。状態 x の平均 6、状態 y の平均 4 を使うと、0.5 × (1 + 3) + 0.5 × (2 + 2) = 4 になります。
  • イの8.5は、割引率を掛け忘れた値です。0.5 × (1 + 8) + 0.5 × (2 + 6) = 8.5 になります。
  • エの5.5は、状態 y でも状態 x の最大値 8 を使ってしまった値です。0.5 × (1 + 4) + 0.5 × (2 + 4) = 5.5 になります。max は、移った先の状態ごとに取ることに注意してください。

計算例で確かめる

計算例1:近道か遠回りか

次の環境を考えます。割引率は γ = 0.9 です。

  • 状態 A で「左」を選ぶ:すぐに終端状態に移り、報酬 1 をもらう
  • 状態 A で「右」を選ぶ:状態 B に移り、報酬 0 をもらう
  • 状態 B では行動は1つだけ:終端状態に移り、報酬 10 をもらう

ゴールに近い状態 B から計算します。状態 B では行動が1つしかないので、max を取る必要はありません。

V^{*}(B) = 10 + 0.9 \times 0 = 10

次に、状態 A での行動ごとの最適行動価値を計算します。

  • 左:Q^{*}(A, left) = 1 + 0.9 \times 0 = 1
  • 右:Q^{*}(A, right) = 0 + 0.9 \times 10 = 9

最後に、状態 A の最適状態価値は、2つのうち大きい方です。

V^{*}(A) = \max(1, 9) = 9

最適な行動は「右」です。すぐにもらえる報酬は「左」の方が大きいものの、将来まで考えると「右」の方が得になります。目先の報酬にとらわれず、将来を見通して行動を選べるのが、ベルマン最適方程式の考え方です。

計算例2:割引率を変えると最適な行動が変わる

計算例1と同じ環境で、割引率を γ = 0.05 に変えてみます。

  • 左:1 + 0.05 × 0 = 1
  • 右:0 + 0.05 × 10 = 0.5

今度は「左」の方が大きくなり、最適な行動が入れ替わりました。第1回の「γ は我慢」のとおり、我慢できない(γ が小さい)エージェントは、目先の報酬を選びます。

割引率 γ左の価値右の価値最適な行動
0.919右
0.0510.5左

練習問題4

次の環境を考えます。割引率は γ = 0.5 です。

  • 状態 A で「左」を選ぶ:すぐに終端状態に移り、報酬 2 をもらう
  • 状態 A で「右」を選ぶ:状態 B に移り、報酬 1 をもらう
  • 状態 B では行動は1つだけ:終端状態に移り、報酬 6 をもらう

最適状態価値 V^{*}(A) と、状態 A での最適な行動を答えてください。

練習問題4の解答と解説

最適状態価値は 4、最適な行動は「右」です。

  • 状態 B の価値:6 + 0.5 × 0 = 6
  • 状態 A で左を選ぶ場合:2 + 0.5 × 0 = 2
  • 状態 A で右を選ぶ場合:1 + 0.5 × 6 = 4

2つのうち大きい方を選ぶので、V^{*}(A) = \max(2, 4) = 4 です。値を聞かれたら max、行動を聞かれたら argmax で答えます。

計算例3:繰り返し計算で最適な価値を求める(価値反復法)

ベルマン期待方程式は、連立方程式として解くことができました。しかし、ベルマン最適方程式には max が含まれるため、普通の連立一次方程式としては解けません。そこで、ベルマン最適方程式を繰り返し当てはめて、値を更新していく方法を使います。この方法を価値反復法と呼びます。

次の環境で試してみます。割引率は γ = 0.9 です。

  • 状態 A で「とどまる」を選ぶ:報酬 1 をもらい、状態 A にとどまる
  • 状態 A で「去る」を選ぶ:報酬 5 をもらい、終端状態に移る

ベルマン最適方程式は次のようになります。

V^{*}(A) = \max(1 + 0.9 V^{*}(A), 5)

価値を 0 から始めて、右辺に1つ前の値を入れて計算します。

回数「とどまる」の値「去る」の値V(A)
0回目--0
1回目1 + 0.9 × 0 = 155
2回目1 + 0.9 × 5 = 5.555.5
3回目1 + 0.9 × 5.5 = 5.9555.95
4回目1 + 0.9 × 5.95 = 6.35556.355

1回目は「去る」が最適に見えますが、2回目以降は「とどまる」の方が大きくなります。計算を続けると、V(A) は 10 に近づいていきます。

この 10 という値は、第1回の計算例で学んだ「報酬が毎回1で永遠に続く場合の収益 1 ÷ (1 − γ)」と同じです。1 ÷ (1 − 0.9) = 10 となり、すぐに 5 をもらって終わるよりも、1 を永遠にもらい続ける方が得だと分かります。

このように、価値反復法では、繰り返すうちに最適な行動が見えてきます。最初の数回の結果だけで判断しないことが大切です。

練習問題5

ベルマン最適方程式について、適切でないものを選んでください。

  • ア:max を含むため、普通の連立一次方程式として簡単に解ける
  • イ:Q学習の更新式には、r + γ max Q の形がそのまま登場する
  • ウ:遷移確率 p による平均は、最適方程式でもそのまま残る
  • エ:最適状態価値は、最適行動価値の行動についての最大値に等しい

練習問題5の解答と解説

正解はアです。

ベルマン最適方程式は max を含むため、ベルマン期待方程式のように普通の連立一次方程式として解くことはできません。そのため、価値反復法のような繰り返し計算や、Q学習のような経験から学ぶ方法を使います。

  • イは正しい説明です。行動価値の形のかっこの中が、Q学習の目標値になります。
  • ウは正しい説明です。選べないところは平均です。
  • エは正しい説明です。第3回で学んだ V^{*}(s) = \max_{a} Q^{*}(s, a) の関係です。

期待方程式と最適方程式のまとめ表

4つの式を1つの表に整理します。試験直前の確認に使ってください。

種類式語呂合わせ
期待方程式(V)V^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) [r + \gamma V^{\pi}(s')]パイで分かれて、ピーで分かれて、ある我慢ブイ
期待方程式(Q)Q^{\pi}(s, a) = \sum_{s', r} p(s', r \mid s, a) [r + \gamma \sum_{a'} \pi(a' \mid s') Q^{\pi}(s', a')]ピーで分かれて、ある我慢、次のパイキュー
最適方程式(V)V^{*}(s) = \max_{a} \sum_{s', r} p(s', r \mid s, a) [r + \gamma V^{*}(s')]マックスで選んで、ピーで分かれて、ある我慢ブイ
最適方程式(Q)Q^{*}(s, a) = \sum_{s', r} p(s', r \mid s, a) [r + \gamma \max_{a'} Q^{*}(s', a')]ピーで分かれて、ある我慢、次のマックスキュー

表を見ると、次の3つの規則があることが分かります。

  1. 期待方程式の「パイ」を「マックス」に変えると、最適方程式になる
  2. 遷移確率 p の部分は、4つの式すべてで同じ(選べないところは平均)
  3. V の式は行動の分かれ道が外側、Q の式は内側にある(ブイは外でマックス、キューは中でマックス)

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

つまずきやすい点正しい理解
遷移確率 p の部分も max にしてしまう選べるところはマックス、選べないところは平均
Q の式で、max を先頭に置いてしまうブイは外でマックス、キューは中でマックス
\max_{a'} のダッシュを付け忘れる次の状態で選ぶ行動なので、a にもダッシュが付く
右肩を π のままにしてしまう最適な価値なので、右肩は *(星が付いたら一番星)
連立方程式で解こうとしてしまうmax を含むので、価値反復法などの繰り返し計算で解く
目先の報酬が大きい行動を最適と判断するすぐの報酬と、割り引いた将来の価値の合計で比べる

白紙に書いて確認しよう

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

  1. ベルマン最適方程式(状態価値の形)
  2. ベルマン最適方程式(行動価値の形)
  3. 期待方程式と最適方程式の違い(一言で)
  4. 計算例1の V^{*}(A) と、最適な行動

さらに余裕があれば、上のまとめ表の4つの式をすべて書いてみましょう。4つが書ければ、ベルマン方程式に関する穴埋め問題には十分に対応できます。

まとめ

  • ベルマン最適方程式は、最も良い方策に従ったときの価値を表す式です
  • 期待方程式の「パイで分かれて」を「マックスで選んで」に変えると、最適方程式になります。期待はパイ、最適はマックスです
  • 選べるところはマックス、選べないところは平均。遷移確率 p の部分は max になりません
  • ブイは外でマックス、キューは中でマックス。行動価値の形は「ピーで分かれて、ある我慢、次のマックスキュー」です
  • max を含むため、連立方程式ではなく、価値反復法などの繰り返し計算で解きます
  • 行動価値の形のかっこの中は、Q学習とDQNの目標値として登場します

次回は、遷移確率 p が分からない場合に、実際の経験から価値を学ぶための「TD誤差」を取り上げます。今回までのベルマン方程式の「ある我慢ブイ」の部分が、そのまま主役になります。ここまでの5つの式を白紙に書ける状態にしてから読み進めてください。

投稿者プロフィール

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

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