はじめに
- ベルマン方程式は図で考えると理解しやすいと思い、記事にしてみました
- もし内容でおかしな点にお気づきの方は、ご指摘いただけると幸いです
- 内容について不明点やもっと詳しく等あればお気軽にコメント欄にコメントください
- なぜかsafariだと数式の前後に変な改行が入るようなので、見にくい場合はchrome等でご覧ください
強化学習におけるベルマン方程式
強化学習においては、下記の式を指します
$$
V^{\pi}(s)=\sum_{a \in \mathcal{A}(s)} \pi(a \mid s) \sum_{s^{\prime} \in \mathcal{S}} P\left(s^{\prime} \mid s, a\right)\left(r\left(s, a, s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right) \label{a} \tag{1}
$$
なお、
$$
Q^{\pi}(s, a)=\sum_{s^{\prime} \in \mathcal{S}} P\left(s^{\prime} \mid s, a\right)\left(r\left(s, a, s^{\prime}\right)+\sum_{a^{\prime} \in \mathcal{A}\left(s^{\prime}\right)} \pi\left(a^{\prime} \mid s^{\prime}\right) \gamma Q^{\pi}\left(s^{\prime}, a^{\prime}\right)\right) \label{b} \tag{2}
$$
と表現されることも多いですが、こちらは
$$
V^{\pi}(s)=\sum_{a \in \mathcal{A}(s)} \pi(a \mid s) Q^{\pi}(s, a)
$$
という式に従って状態価値関数$V^{\pi}(s)$を行動価値関数$Q^{\pi}(s, a)$に置き換えているだけです。
これらは、$V^{\pi}(s)$ と $V^{\pi}(s')$ の漸化式、$Q^{\pi}(s,a)$ と$ Q^{\pi}(s',a')$ の漸化式として解釈できます（$s$ は $s_t$、$s'$ は $s_{t+1}$ として、$V^{\pi}(s_t)$ と $V^{\pi}(s_{t+1})$ の漸化式、$Q^{\pi}(s_t, a_t)$ と $Q^{\pi}(s_{t+1},a_{t+1})$ の漸化式、と書いた方がわかりやすいかもしれません）。
ベルマン方程式のありがたみは、価値関数を漸化式で表現できるというところにあります。この式を使用することで、逐次的な価値関数の更新が可能になり、効率的な学習ができるようになるのですが、ここでは詳細は割愛いたします（関連用語： TD法、ブートストラップ、など）
| 文字 | 意味 |
|---|---|
| $V^{\pi}(s)$ | 方策が${\pi}$であるときの,状態$s$の状態価値(※1) |
| $Q^{\pi}(s,a)$ | 方策が${\pi}$であるときの,状態$s$における行動$a$の行動価値(※2) |
| $A(s)$ | 状態$s$において選択可能な行動集合（状態$s$における全行動） |
| $\pi(a \mid s)$ | 状態$s$において行動$a$を選択する確率 |
| $S$ | 状態$s$において行動$a$を選択したときに生じうる状態集合 |
| $P\left(s^{\prime} \mid s, a\right)$ | 状態$s$で行動$a$を選択した場合に状態$s'$に推移する確率 |
| $r\left(s, a, s^{\prime}\right)$ | 状態$s$で行動$a$を選択して状態$s'$に推移したときに得られる即時報酬 |
| $\gamma$ | 報酬の割引率(0〜1)(※3) |
※1: 状態$s$を起点として、方策${\pi}$に従って行動した場合に得られる収益 (状態$s$以降に得られる累積報酬和) の期待値
※2: 状態$s$を起点として、行動$a$を選択して、その後は方策${\pi}$に従って行動した場合に得られる収益の期待値
※3: この値が小さいと、エージェントは直近の報酬を重視した行動をとるようになる
図を用いたベルマン方程式の理解
図で考えると分かりやすいです。
まずは、状態価値関数$V^{\pi}(s)$で表したベルマン方程式
$$
V^{\pi}(s)=\sum_{a \in \mathcal{A}(s)} \pi(a \mid s) \sum_{s^{\prime} \in \mathcal{S}} P\left(s^{\prime} \mid s, a\right)\left(r\left(s, a, s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right)
$$
を図にすると下図のようになります。
ここで、行動$a_1$を選択したときのパスに焦点を当てると、$r(s,a_1,s_{1}^{\prime})$ と $V^{\pi}\left(s_{1}^{\prime}\right)$ の関係は下図のようになり、行動$a_1$を選択したときの期待収益は、$r\left(s, a_{1}, s_{1}^{\prime}\right)+\gamma V^{\pi}\left(s_{1}^{\prime}\right)$ となります。
つまり、ベルマン方程式は、各パスの発生確率と、各パスを通った場合の期待収益を、かけて足し合わせることで、現在の状態$s$における期待収益$V^{\pi}\left(s\right)$を表現しているということになります。
なお、図において、行動$a_1$,$a_2$の先にさらに分岐があるのは、例えば「エージェントの行動」＝「大小二つのサイコロのどちらかを選ぶ」というような環境(タスク)の場合、エージェントがとれる行動は大きなサイコロを選ぶ($a_1$)か、小さなサイコロを選ぶ($a_2$)かまでで、そのサイコロを選んだ後にサイコロのどの面がでるかは確率的に決定される(複数の分岐がある)ためです。
これがもし、囲碁や将棋のように、選択した行動(例えば歩を前に動かす)がそのまま(ノイズなく)反映されるような環境の場合は、この行動$a_1$,$a_2$の先の分岐はありません($S$の要素数が1、$P\left(s^{\prime} \mid s, a\right)$の確率が1.0となる)。
次に、行動価値関数$Q^{\pi}(s,a)$で表したベルマン方程式
$$
Q^{\pi}(s, a)=\sum_{s^{\prime} \in \mathcal{S}} P\left(s^{\prime} \mid s, a\right)\left(r\left(s, a, s^{\prime}\right)+\sum_{a^{\prime} \in \mathcal{A}\left(s^{\prime}\right)} \pi\left(a^{\prime} \mid s^{\prime}\right) \gamma Q^{\pi}\left(s^{\prime}, a^{\prime}\right)\right)
$$
についても同様に図にすると、下図のようになります。
