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

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

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

これまでの3回で、割引収益、状態価値関数、行動価値関数を学びました。今回は、それらを組み合わせた「ベルマン期待方程式」を取り上げます。

ベルマン期待方程式は、強化学習の数式の中でも特に重要な式です。次回のベルマン最適方程式、第6回のTD誤差、第7回のSARSA、第8回のQ学習は、すべてこの式を変形したものです。式は長く見えますが、第1回から第3回で学んだ部品の組み合わせなので、部品ごとに覚えれば必ず書けるようになります。

この記事のゴール

  • ベルマン期待方程式(状態価値の形)を、何も見ずに書けるようになる
  • 式の中にある2つの分かれ道(π と p)の意味を説明できるようになる
  • 第1回の再帰形から、ベルマン期待方程式が導かれる流れを説明できるようになる
  • 簡単な例で、ベルマン期待方程式を使って状態価値を計算できるようになる

これまでの復習

今回の式で使う部品を確認します。

第1回の割引収益の再帰形です。

G_t = R_{t+1} + \gamma G_{t+1}

覚え方は「じいさんは、ある我慢じいさん」でした。

第2回の状態価値関数です。

V^{\pi}(s) = \mathbb{E}_{\pi}[G_t \mid S_t = s]

覚え方は「価値(V)はパイ次第、イーパイでジーを平均、縦棒の右はスタート地点」でした。

第3回の状態価値と行動価値の関係式です。

V^{\pi}(s) = \sum_{a} \pi(a \mid s) Q^{\pi}(s, a)

覚え方は「ブイ(V)サインで、パイキュー(サンキュー)」でした。

ベルマン期待方程式の式

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

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

新しく登場する記号は次のとおりです。

記号読み方意味
s'エス・ダッシュ次の状態。行動した後に移る状態
rアール行動した結果としてもらえる報酬
p(s', r \mid s, a)ピー状態 s で行動 a を選んだとき、次の状態 s' に移って報酬 r をもらう確率
\sum_{s', r}シグマ起こりうるすべての「次の状態と報酬の組み合わせ」について足す

p は環境の遷移確率と呼ばれます。方策 π が「エージェントがどう行動するか」のルールだったのに対して、p は「環境がどう反応するか」のルールです。

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

「今の状態の価値は、方策 π で行動を選び、環境 p で次の状態と報酬が決まったときの、すぐもらえる報酬と次の状態の価値(割り引いたもの)の合計の平均に等しい」

もっと短く言うと、「今の価値 = 平均して(すぐの報酬 + γ × 次の価値)」です。

期待値で書いた形

同じ内容を、期待値の記号を使って短く書くこともできます。

V^{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma V^{\pi}(S_{t+1}) \mid S_t = s]

試験では、どちらの形でも出題されます。まずは短い期待値の形で意味をつかみ、その後に長い Σ の形を覚えると効率的です。

式の意味:今の価値は、一歩先の価値で決まる

ベルマン期待方程式が伝えていることは、「今の状態の価値は、一歩先の状態の価値を使って表せる」ということです。

山登りで考えてみます。ある休憩所から山頂までの「残りの楽しみ」を知りたいとします。すべての道のりを最後まで計算しなくても、次の休憩所までの楽しみと、次の休憩所から山頂までの残りの楽しみが分かれば、今の休憩所の残りの楽しみが分かります。

  • すぐもらえる報酬 r:次の休憩所までの楽しみ
  • 次の状態の価値 V^{\pi}(s'):次の休憩所から山頂までの残りの楽しみ
  • 割引率 γ:先の楽しみを少し割り引く

将来のすべての報酬を一度に考える代わりに、「一歩先」だけを見て価値を計算できるのが、ベルマン期待方程式の便利な点です。

第1回の再帰形から導く

ベルマン期待方程式は、第1回の再帰形の両辺の平均を取ると導けます。

  1. 第1回の再帰形:G_t = R_{t+1} + \gamma G_{t+1}
  2. 第2回の定義により、左辺の G の平均は状態価値 V になる
  3. 右辺の G_{t+1} の平均は、次の状態の価値 V^{\pi}(S_{t+1}) になる
  4. その結果、V^{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma V^{\pi}(S_{t+1}) \mid S_t = s] が得られる

つまり、ベルマン期待方程式は「じいさんは、ある我慢じいさん」を平均したものです。じいさん(G)を平均するとブイ(V)になるので、「ブイは、ある我慢ブイ」と言い換えられます。

練習問題1

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

  • ア:今の状態の価値は、直後の報酬だけで決まる
  • イ:今の状態の価値は、最も良い行動を選んだときの価値に等しい
  • ウ:今の状態の価値は、直後の報酬と次の状態の価値の割引和の平均に等しい
  • エ:今の状態の価値は、終端状態の価値と常に等しくなる

練習問題1の解答と解説

正解はウです。

ベルマン期待方程式は、「今の価値 = 平均して(すぐの報酬 + γ × 次の価値)」という関係を表します。

  • アは誤りです。直後の報酬だけでなく、割り引いた次の状態の価値も含みます。
  • イは誤りです。最も良い行動を選ぶ(max を取る)のは、次回学ぶベルマン最適方程式です。期待方程式では、方策 π の確率で平均します。
  • エは誤りです。終端状態の価値は 0 ですが、ほかの状態の価値が常に 0 になるわけではありません。

2つの分かれ道で式を読む

長い Σ の形を覚えるために、式を「2つの分かれ道」として読み解きます。

状態 s から一歩進むとき、結果は2回枝分かれします。

  1. 1回目の分かれ道:エージェントが行動 a を選ぶ。どの行動を選ぶかは方策 π で決まる
  2. 2回目の分かれ道:環境が次の状態 s' と報酬 r を決める。どうなるかは遷移確率 p で決まる
  3. 分かれ道の先:すぐの報酬と、割り引いた次の状態の価値を足す

式の各部分は、この3つに順番に対応しています。

式の部分対応する内容誰が決めるか
\sum_{a} \pi(a \mid s)1回目の分かれ道(行動の選択)エージェント(方策)
\sum_{s', r} p(s', r \mid s, a)2回目の分かれ道(次の状態と報酬)環境
[r + \gamma V^{\pi}(s')]分かれ道の先の値報酬と次の価値

強化学習の教科書では、この分かれ道を「バックアップ線図」と呼ばれる木の形の図で表します。白い丸(状態)から黒い丸(行動)に分かれ、黒い丸からさらに白い丸(次の状態)に分かれる図です。紙に自分で描いてみると、式の構造がよく分かります。

語呂合わせ1:パイで分かれて、ピーで分かれて、ある我慢ブイ

式を左から順に、次のように唱えます。

「パイで分かれて、ピーで分かれて、ある我慢ブイ」

  • パイで分かれて:\sum_{a} \pi(a \mid s)
  • ピーで分かれて:\sum_{s', r} p(s', r \mid s, a)
  • ある我慢ブイ:[r + \gamma V^{\pi}(s')]

「自分で選んで、環境に任せて、ある我慢ブイ」と言い換えても構いません。1回目は自分(エージェント)の選択、2回目は環境の反応です。

語呂合わせ2:ダッシュで次の状態へダッシュ

s' の右上の記号(')は、日本語ではダッシュと読みます(英語ではプライム)。ダッシュの付いた s は「次の状態」を表します。

覚え方は「ダッシュ(')で次の状態へダッシュ」です。

次の状態へ走って移るイメージを持つと、「ダッシュ付きは次の時刻のもの」と思い出せます。後の回で登場する a' も、「次の状態で選ぶ行動」という意味です。

語呂合わせ3:原因は縦棒の右、結果は縦棒の左

遷移確率 p(s', r \mid s, a) は、文字の順番を間違えやすい記号です。

第2回と第3回で、「縦棒の右には、分かっている前提が書かれる」と学びました。遷移確率では、今の状態 s と選んだ行動 a が分かっている前提(原因)です。その結果として、次の状態 s' と報酬 r が決まります。

覚え方は「原因は縦棒の右、結果は縦棒の左」です。

  • 縦棒の右(原因):s、a(今の状態と、選んだ行動)
  • 縦棒の左(結果):s'、r(次の状態と、もらえる報酬)

練習問題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^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s', r} p(s, a \mid s', r) [r + \gamma V^{\pi}(s')]
  • ウ:V^{\pi}(s) = \sum_{a} \pi(s \mid a) \sum_{s', r} p(s', r \mid s, a) [r + \gamma V^{\pi}(s')]
  • エ:V^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) [\gamma r + V^{\pi}(s')]

練習問題2の解答と解説

正解はアです。

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

  • イは誤りです。遷移確率の縦棒の左右が逆になっています。原因(s、a)は縦棒の右です。
  • ウは誤りです。方策の縦棒の左右が逆になっています。状態を見てから行動するので、縦棒の右は状態 s です。
  • エは誤りです。割引率 γ を掛ける位置が違います。割り引くのは次の状態の価値で、すぐもらえる報酬 r は割り引きません。

行動価値を使って2段階で覚える

長い式を一度に覚えるのが難しい場合は、第3回の行動価値を使って2段階に分けると覚えやすくなります。

1段階目は、第3回の関係式です。

V^{\pi}(s) = \sum_{a} \pi(a \mid s) Q^{\pi}(s, a)

2段階目は、行動価値を「環境の分かれ道」で表す式です。

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

2段階目の式を1段階目の Q に代入すると、ベルマン期待方程式になります。

  • 1段階目:パイで分かれる(ブイサインで、パイキュー)
  • 2段階目:ピーで分かれて、ある我慢ブイ

この分け方で覚えておくと、行動価値を主役にしたベルマン期待方程式も書けるようになります。2段階目の V に、1段階目の式(次の状態での V)を代入すると、次の式になります。

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^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s'} P(s' \mid s, a) [R(s, a, s') + \gamma V^{\pi}(s')]

P(s' \mid s, a) は次の状態に移る確率、R(s, a, s') はそのときにもらえる報酬です。見た目は違いますが、「パイで分かれて、ピーで分かれて、ある我慢ブイ」という構造は同じです。試験では、構造に注目して読み取りましょう。

練習問題3

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

  • 確率 0.6 で状態 x に移り、報酬 2 をもらう。V^{\pi}(x) = 10
  • 確率 0.4 で状態 y に移り、報酬 0 をもらう。V^{\pi}(y) = 5

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

  • ア:7.2
  • イ:9.2
  • ウ:11.0
  • エ:8.4

練習問題3の解答と解説

正解はエです。

2段階目の式「ピーで分かれて、ある我慢ブイ」を使います。

  • 状態 x に移る場合:2 + 0.9 × 10 = 11
  • 状態 y に移る場合:0 + 0.9 × 5 = 4.5

これを遷移確率で平均します。

Q^{\pi}(s, a) = 0.6 \times 11 + 0.4 \times 4.5 = 6.6 + 1.8 = 8.4

  • アの7.2は、報酬 r を足し忘れて 0.6 × 9 + 0.4 × 4.5 と計算した値です。
  • イの9.2は、割引率を掛け忘れて 0.6 × (2 + 10) + 0.4 × (0 + 5) と計算した値です。
  • ウの11.0は、確率で平均せずに、状態 x に移る場合だけを考えた値です。

各場合を「報酬 + γ × 次の価値」で計算してから、確率で平均する手順を守りましょう。

計算例で確かめる

計算例1:一本道の場合

次のような一本道を考えます。割引率は γ = 0.9 です。

  • 状態 A から必ず状態 B に移り、報酬 0 をもらう
  • 状態 B から必ず終端状態に移り、報酬 10 をもらう
  • 終端状態の価値は 0

行動も遷移も1通りしかないので、π も p もすべて確率1です。ベルマン期待方程式は「ある我慢ブイ」の部分だけになります。

ゴールに近い状態 B から計算します。

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

次に状態 A を計算します。

V^{\pi}(A) = 0 + 0.9 \times 10 = 9

ゴールから逆向きに、一歩ずつ価値が伝わっていく様子が分かります。この「後ろから価値を伝える」考え方が、ベルマン方程式を使った計算の基本です。

計算例2:2つの分かれ道がある場合

状態 s で、方策 π は2つの行動を次の確率で選ぶとします。割引率は γ = 0.5 です。

行動 a_1(確率 0.5)を選んだ場合:

  • 必ず状態 x に移り、報酬 4 をもらう。V^{\pi}(x) = 8

行動 a_2(確率 0.5)を選んだ場合:

  • 確率 0.5 で状態 x に移り、報酬 0 をもらう
  • 確率 0.5 で状態 y に移り、報酬 2 をもらう。V^{\pi}(y) = 0

まず、行動ごとに「ピーで分かれて、ある我慢ブイ」を計算します。

  • 行動 a_1:4 + 0.5 × 8 = 8
  • 行動 a_2:0.5 × (0 + 0.5 × 8) + 0.5 × (2 + 0.5 × 0) = 0.5 × 4 + 0.5 × 2 = 3

次に、「パイで分かれて」の部分を計算します。

V^{\pi}(s) = 0.5 \times 8 + 0.5 \times 3 = 4 + 1.5 = 5.5

内側(環境の分かれ道)から外側(行動の分かれ道)へ順に計算すると、計算ミスを防げます。

計算例3:状態がお互いに行き来する場合

計算例1では、ゴールから逆向きに計算できました。しかし、状態どうしが行き来する場合は、そう簡単にはいきません。

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

  • 状態 A から必ず状態 B に移り、報酬 3 をもらう
  • 状態 B からは、確率 0.5 で状態 A に戻って報酬 0、確率 0.5 で終端状態に移って報酬 2 をもらう

ベルマン期待方程式を、状態ごとに立てます。

V(A) = 3 + 0.5 V(B)

V(B) = 0.5 \times (0 + 0.5 V(A)) + 0.5 \times (2 + 0.5 \times 0) = 0.25 V(A) + 1

V(A) の式に V(B) が、V(B) の式に V(A) が入っているので、連立方程式として解きます。2つ目の式を1つ目の式に代入します。

V(A) = 3 + 0.5 (0.25 V(A) + 1) = 3.5 + 0.125 V(A)

両辺から 0.125V(A) を引くと、0.875V(A) = 3.5 となり、V(A) = 4 です。

これを2つ目の式に代入すると、V(B) = 0.25 × 4 + 1 = 2 です。

検算として、1つ目の式に戻すと 3 + 0.5 × 2 = 4 となり、正しいことが確認できます。

計算例4:繰り返し計算で近づける

計算例3のような連立方程式は、状態の数が増えると解くのが大変になります。そこで実際には、すべての価値を 0 から始め、ベルマン期待方程式を何度も当てはめて値を更新する方法を使います。この方法を反復方策評価と呼びます。

計算例3で試してみます。右辺には、1つ前の回の値を使います。

回数V(A) の計算V(A)V(B) の計算V(B)
0回目初期値0初期値0
1回目3 + 0.5 × 030.25 × 0 + 11
2回目3 + 0.5 × 13.50.25 × 3 + 11.75
3回目3 + 0.5 × 1.753.8750.25 × 3.5 + 11.875

回数を重ねるごとに、V(A) は 4 に、V(B) は 2 に近づいていきます。連立方程式を解かなくても、ベルマン期待方程式を繰り返し使うだけで、正しい価値にたどり着けます。

この「ベルマン方程式を繰り返して価値を求める」考え方は、動的計画法と呼ばれる手法の中心です。第6回のTD学習やQ学習も、同じ考え方を経験データで行う手法と言えます。

練習問題4

一本道の環境で、状態 A から必ず状態 B に移って報酬 1 をもらい、状態 B から必ず終端状態に移って報酬 4 をもらうとします。割引率 γ = 0.5 のとき、V^{\pi}(A) を求めてください。

練習問題4の解答と解説

答えは3です。

ゴールに近い状態 B から計算します。

  • V(B) = 4 + 0.5 × 0 = 4
  • V(A) = 1 + 0.5 × 4 = 1 + 2 = 3

「ある我慢ブイ」を、ゴールから逆向きに当てはめていくのがコツです。

練習問題5

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

  • ア:方策 π による行動の選択と、遷移確率 p による環境の反応の2回の分岐を含む
  • イ:割引率 γ は、すぐにもらえる報酬 r ではなく、次の状態の価値に掛かる
  • ウ:第1回の割引収益の再帰形の両辺について、期待値を取ると導くことができる
  • エ:環境の遷移確率 p が分からなくても、この式だけで価値を正確に計算できる

練習問題5の解答と解説

正解はエです。

この式で価値を計算するには、遷移確率 p が分かっている必要があります。p が分からない場合は、実際に行動して得た経験から価値を推定する方法が必要になります。第2回で紹介したモンテカルロ法や、第6回で学ぶTD学習がその方法です。

  • アは正しい説明です。「パイで分かれて、ピーで分かれて」の2回の分岐があります。
  • イは正しい説明です。「ある我慢ブイ」のとおり、我慢(γ)はブイ(次の価値)に掛かります。
  • ウは正しい説明です。「じいさんは、ある我慢じいさん」を平均すると「ブイは、ある我慢ブイ」になります。

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

つまずきやすい点正しい理解
γ を報酬 r にも掛けてしまうγ が掛かるのは次の状態の価値だけ。ある我慢ブイ
遷移確率の縦棒の左右を逆にする原因(s、a)は縦棒の右、結果(s'、r)は縦棒の左
方策の縦棒の左右を逆にする状態を見てから行動する。だから縦棒の右は状態 s
右辺の V にダッシュを付け忘れる右辺は次の状態の価値なので V^{\pi}(s')
期待方程式で max を取ってしまう期待方程式は π で平均する。max を取るのは最適方程式
計算の順番が分からなくなる内側(環境の分かれ道)から外側(行動の分かれ道)の順に計算する

白紙に書いて確認しよう

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

  1. ベルマン期待方程式(期待値を使った短い形)
  2. ベルマン期待方程式(Σ を使った長い形)
  3. 行動価値を環境の分かれ道で表す式(2段階目の式)
  4. 計算例3の連立方程式と、その答え

長い形を書くときは、「パイで分かれて、ピーで分かれて、ある我慢ブイ」と唱えながら、左から順に書いていきましょう。書き終えたら、π と p の縦棒の左右、γ の位置、ダッシュの付け忘れの3点を確認してください。

まとめ

  • ベルマン期待方程式は、「今の価値 = 平均して(すぐの報酬 + γ × 次の価値)」という関係を表します
  • 第1回の再帰形を平均したものです。じいさんを平均すると、ブイは、ある我慢ブイになります
  • 長い形は「パイで分かれて、ピーで分かれて、ある我慢ブイ」の順に書きます
  • ダッシュ(')で次の状態へダッシュ。原因は縦棒の右、結果は縦棒の左です
  • 状態価値と行動価値の2段階に分けると、どちらの形のベルマン期待方程式も書けます
  • 状態どうしが行き来する場合は、連立方程式か繰り返し計算で価値を求めます

次回は、ベルマン期待方程式の「パイで分かれて」の部分を「一番良い行動を選ぶ」に置き換えた「ベルマン最適方程式」を取り上げます。今回の式との違いはわずかですが、試験ではその違いが繰り返し問われます。今回の式を白紙に書ける状態にしてから読み進めてください。

投稿者プロフィール

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

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