【強化学習】第3回 - モンテカルロ(MC)法とTD(0)学習、TD(λ)学習について解説

# はじめに
前回は**遷移確率 $P$ や報酬 $R$ が既知の場合に状態価値関数を計算する方法**について扱いました。しかし実際に強化学習を行う際は、むしろ**遷移確率や報酬は未知である場合が多い**です。第3回である本稿では、モデルが未知の場合に適用できるアルゴリズムとして「**モンテカルロ法」と「TD(0)学習**」「TD(λ)学習」の3つを紹介します。なお、強化学習には**Sutton & Barto**によるバイブル的な参考書["**Reinforcement Learning: An Introduction**"](http://incompleteideas.net/book/the-book.html)があり、この記事もここに書かれている内容を元に作成しています。すべて英語ですが、参考にしてください。

前回 ▶ [【強化学習】第2回 - ベルマン方程式と方策反復法(PI)、価値反復法(VI)について解説](https://qiita.com/inoz/items/f69d523058a1fe543ee8)
次回 ▶ [【強化学習】第4回 - SARSAとQ学習について解説](https://qiita.com/inoz/items/5e27dbd7eb34fd68fdee)

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/67895a00-94df-6668-ed17-2e410c2e45d0.png">

# モデルフリーにおける方策評価
**モデルフリー**とは、**モデルの情報を使用しない**ということです。すなわち、モデルフリーな学習は具体的な遷移確率 $P$ や報酬 $R$ が未知の際にも適用することができます。まずはモデルフリーな状況下における状態価値関数 $V^{\pi}(s)$ を評価する手法について見ていきましょう。モデルフリーな状況下において方策を改善する手法については第4回で扱います。

## モンテカルロ法
<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/7212042a-1cfa-861d-dbc3-d3c28fc1defc.jpeg">

第2回でも述べたように、最適な方策を求めるためには、**方策の良さ**を知る必要があります。**モデルの完全な情報が手元にない状態**において、**ある方策に従った際の各状態の将来的な報酬の見込み $V^{\pi}(s)$ を推測する方法**について考えてみましょう。

具体的なモデルの情報が未知であっても、**環境内で行動を重ねることでモデルの情報を推測することは可能**です。モデルに従ったエピソードをいくつか用意した上で、それらの**エピソードから得られる平均値を各状態の価値関数としましょう**、というのがモンテカルロ法の発想です。Monte-Carloの頭文字を取ってMC法とも呼ばれます。

モンテカルロ法は、**各状態がマルコフ的でない場合でも適用できます**。一方でアルゴリズムの性質上、**各エピソードのHorizon(長さ)は必ず有限**である必要があります。本質的な差はありませんが、モンテカルロ法には**初回訪問モンテカルロ法**と**逐一訪問モンテカルロ法**の2種類があります。順に見ていきましょう。

#### 初回訪問モンテカルロ法
モンテカルロ法という手法を用いて状態価値関数を評価する方法を説明します。ゴールは、方策 $\pi$ に従った行動の結果として得られた1つ以上のエピソードから、**$\pi$ に従ったときの各状態における将来的な報酬の見込み $V^{\pi}(s)$ を推測すること**です。マルコフ決定過程のモデル $M$ において、$r_t$ を時刻 $t$ における報酬、$\gamma$を割引率とすると、**時刻 $t$ からの将来的な報酬の見込み $G_t$ と状態価値関数 $V^{\pi}(s)$** はそれぞれ以下の式で定義されました。

$$
\begin{align}
&G_t=r_t+\gamma r_{t+1}+\gamma^2 r_{t+2}+\cdots\\\\
&V^{\pi}(s)=\mathbb{E}\[G_t\\,|\\,s_t=s\]
\end{align}
$$

初回訪問モンテカルロ法における**状態価値関数の評価**は、以下の流れで行います。方策 $\pi$ に従った結果として得られたエピソード$i=s_{i,1},\\,a_{i,1},\\,r_{i,1},\\,s_{i,2},\\,a_{i,2},\\,r_{i,2},\\,\cdots,\\,s_{i,n}$の集合を $I$ とします。

1. $\forall s\in S$ について $N(s)=0,\\,G(s)=0$ と初期化する。
2. $\forall i\in I$ について、以下の処理を行う。
    1. エピソード $i$ の中で訪問される任意の状態 $s$ について、以下の処理を行う。
        1. エピソード $i$ の中で初めて $s$ を訪問する時刻 $t$ を選ぶ。
        2. $G_{i,t}=r_{i,t}+\gamma r_{i,t+1}+\gamma^2 r_{i,t+2}+\cdots$を計算する。
        3. $N(s)=N(s)+1$ とする。
        4. $G(s)=G(s)+G_{i,t}$ とする。 
        5. $V^{\pi}(s)=G(s)\\,/\\,N(s)$ とする。

$N(s)$ は用意したエピソードの集合の中で、**状態 $s$ を訪問したエピソードが何個あるのかを表すカウンター**です。また、$G(s)$ は**各エピソードの中で初めて状態 $s$ が訪問されたときに計算した $G_{i,t}$ の合計**です。$N(s)$ と $G(s)$ を用いて各状態 $s$ における未来の報酬の平均値を計算し、それを状態 $s$ の価値関数の値とします。

第2回に引き続き、火星探索ロボットに登場してもらいます。ロボットは時刻が $1$ 経過するごとに必ず左右のどちらかへ移動し、その場に留まることはありません。**状態が$s_1$ のときに報酬1、状態が $s_5$ のときに報酬5**をそれぞれ手にし、それ以外の状態における報酬は0です。割引率 $\gamma$ は $\gamma=0.5$ としましょう。
<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/740429b8-6dbb-609f-e4ac-8642bd27e01b.png">

ロボットは状態1から状態5までをある一定の方策 $\pi$ に従って動き回ります。方策 $\pi$ に従った結果、1つ目のエピソードとして、「**$s_3$→$s_4$→$s_3$→$s_4$→$s_5$」というエピソード $i$ が得られた**とします。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/2ef5966d-8583-aa85-57c2-0c953b67ad41.gif">

このエピソードを用いて**モンテカルロ法による方策評価**を行いましょう。このエピソードの中で訪問する状態は $s_3,\\,s_4,\\,s_5$ですので、これらについて順に考えてみます。

まず、$s_3$ を初めて訪問する時刻は $t=1$ です。したがって、$G_{i,1}$ を計算します。

$$
\begin{align}
G_{i,1}&=r_{i,1}+\gamma r_{i,2}+\gamma^2 r_{i,3}+\gamma^3 r_{i,4}+\gamma^4 r_{i,5}\\\\
&=0+0+0+0+(0.5)^4\cdot5\\\\
&=5/16\\\\
&=0.3125
\end{align}
$$

これにより
$$
\begin{align}
N(s_3)&=0+1=1,\\\\
G(s_3)&=0+0.3125=0.3125
\end{align}
$$
とそれぞれ更新できます。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/18b3c40a-0fa4-7f14-75e1-4e011576697b.png">

$s_4$ を初めて訪問するのは時刻 $2$ なので、$s_4$ についても同様に考えると

$$
\begin{align}
G_{i,2}&=r_{i,2}+\gamma r_{i,3}+\gamma^2 r_{i,4}+\gamma^3 r_{i,5}\\\\
&=0+0+0+(0.5)^3\cdot5\\\\
&=5/8\\\\
&=0.625
\end{align}
$$

となり、$N(s_4)$ と $G(s_4)$ は下表のように更新できます。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/36cffbe1-3d1f-0f5a-7574-d2363be7157b.png">

最後に $s_5$ については、初めて訪問する時刻が $5$ であるため、


$$
\begin{align}
G_{i,5}&=r_{i,5}\\\\
&=5
\end{align}
$$

となり、このエピソード $i$ からは最終的に下表が完成します。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/c9a8d717-6d62-7755-6b9a-f3cca559cc10.png">

さらにまた他のエピソードを用いて同様の更新を繰り返すことで、状態価値関数 $V^{\pi}(s)$ を求めます。

モンテカルロ法で行動価値関数を求める際[^1]は、以上のような手順で計算を行います。初回訪問モンテカルロ法は**偏り(bias)が全く無い**というメリットがある一方で、**得られる方策の分散(variance)は大きい**です。言い換えると、正確な値を得るためには大量のエピソードをサンプリングする必要があります。このため、エピソードを得るのが難しい場合やエピソードのサンプリングの値段が高く付くような場合、試行錯誤による結果が重大な場合[^2]には実用的ではありません。

#### 逐一訪問モンテカルロ法
**初回訪問モンテカルロ法**は、それぞれの状態 $s$ を初めて訪問するときのみ $G_{i,t}$ を計算し、$G(s)$ と $N(s)$ を更新しました。初回訪問時のみだけでなく、**すべての訪問において $G(s)$ と $N(s)$ を更新しよう**というのが**逐一モンテカルロ法**の発想です。このほかは初回訪問モンテカルロ法と全く変わりません。

1. $\forall s\in S$ について $N(s)=0,\\,G(s)=0$ と初期化する。
2. $\forall i\in I$ について、以下の処理を行う。
    1. エピソード内のすべての時刻 $t$ について以下の処理を行う。
        1. エピソード $i$ 内の時刻 $t$ における状態を $s$ とする。
        2. $G_{i,t}=r_{i,t}+\gamma r_{i,t+1}+\gamma^2 r_{i,t+2}+\cdots$を計算する。
        3. $N(s)=N(s)+1$ とする。
        4. $G(s)=G(s)+G_{i,t}$ とする。 
        5. $V^{\pi}(s)=G(s)\\,/\\,N(s)$ とする。


逐一訪問モンテカルロ法は一つのエピソード内で複数回訪問した状態についても $N(s)$ と $G(s)$ の更新を繰り返します。そのため初回訪問モンテカルロ法と比較すると **$N(s)$ が大きくなり、$V^{\pi}(s)$ の精度は向上**します。とはいえ、今から紹介するTD学習と比較すると**まだまだ正確な値を得るためには大量のエピソードを必要とする手法**です。

## TD学習
モンテカルロ法は方策の偏りを抑えられる一方、状態価値関数を得るためには膨大なデータが必要だという問題点がありました。

**TD学習**は、モデルの情報が未知な状況において、**状態価値関数や行動価値関数をエピソードが終了するよりも前に更新していく手法の総称**です。TD学習は一般に、方策に偏りが生じるものの、モンテカルロ法よりも**分散が小さくなり素早く最適な方策に近づける**という特徴があります。

TD学習の代表的な手法としては、**TD(0)学習**や**TD(λ)学習**、**SARSA、Q学習**といったものが挙げられます。記事のボリューム的に今回はTD(0)学習とTD(λ)学習のみを取り上げ、SARSAとQ学習については次回扱います。なお"TD"とは、"Temporal Difference"の頭文字を取ったものです。

### TD(0)学習
TD学習の中でも最もシンプルな**TD(0)学習**では、以下のステップで方策評価を行います。ゴールは**ある方策 $\pi$ のもとでの状態価値関数 $V^{\pi}(s)$ を各状態に対して求めること**です。方策 $\pi$ に従った結果として得られたエピソードを1つ以上用意して、それらの集合を $I$ とします。

1. $\forall s\in S$ について $V^{\pi}(s)=0$ と初期化する。$\alpha\in\[0,\\,1]$ を決める。
2. $\forall i\in I$ について、以下の処理を行う。
    1. エピソード $i$ 内のすべての時刻 $t$ について、以下の処理を行う。
        1. 遷移を表すタプル $(s_t,\\,a_t,\\,r_t,\\,s_{t+1})$ をエピソード $i$ の中から取る。
        2. $V^{\pi}(s_t)=V^{\pi}(s_t)+\alpha(\[r_t+\gamma V^{\pi}(s_{t+1})\]-V^{\pi}(s_t))$ と更新する。

2.1.2の更新式の意味が少し取りにくいですが、この式を(1)とすると**式(1)は以下の式(2)に変形できます。**
$$
\begin{align}
V^{\pi}(s_t)&=V^{\pi}(s_t)+\alpha(\[r_t+\gamma V^{\pi}(s_{t+1})\]-V^{\pi}(s_t))\tag{1}\\\\
V^{\pi}(s_t)&=(1-\alpha)V^{\pi}(s_t)+\alpha(\[r_t+\gamma V^{\pi}(s_{t+1})\])\tag{2}
\end{align}
$$
「もともと保持していた $V^{\pi}(s_t)$ の値」と、「遷移後の状態が保持していた $V^{\pi}(s_{t+1})$ の値と実際に得られた報酬から予測できる $V^{\pi}(s_t)$ の値」の**重み付き平均を次なる $V^{\pi}(s_t)$ として採用**しているわけです。

なお、このときの更新差分である
$$
\delta_t=r_t+\gamma V^{\pi}(s_{t+1})-V^{\pi}(s_t)
$$
のことを、**TD誤差**と呼びます。

モンテカルロ法ではエピソードの終点までの報酬を考慮したのに対し、**TD(0)法では次の状態までの報酬のみを考慮**しています。3つの状態を遷移するエピソードが与えられたとき、状態を$s$、行動を $a$ と表せば、2つの手法の違いは以下の図のように表現できます。オレンジ色の背景の部分がモンテカルロ法における状態価値関数の更新で考慮する範囲、黄色の背景の部分がTD(0)法における状態価値関数の更新で考慮する範囲です。
<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/0d142b86-722e-b0f1-7af1-9e84dc06fdd9.png">
**モンテカルロ法が終点まで考慮**しているのに対し、**TD(0)法は次に遷移する状態までのみを考慮**していることがポイントです。なお、どちらの手法もエピソードに沿って価値関数を更新するため、エピソードの中で遷移しなかった部分については考慮していません。

### TD(λ)学習
TD(0)学習では直後に遷移する状態のみを更新に用いましたが、エピソードがその後も続くのであれば**直後よりも後にある遷移の情報も考慮したほうが効率良く学習できそう**です。**TD(λ)学習**はこのような発想に基づいた、エピソードの終点まで考慮するモンテカルロ法と直後の遷移のみを考慮するTD(0)学習の中間を取った方法です。

まずは、$G_t$ を拡張した $G^{(n)}_t$ を以下で定義します。

$$
\begin{align}
G^{(1)}\_t&=R_{t+1}+\gamma V(s_{t+1})\\\\
G^{(2)}\_t&=R_{t+1}+\gamma R_{t+2} +\gamma^2 V(s_{t+2})\\\\
G^{(n)}\_t&=R_{t+1}+\gamma R_{t+2} +\gamma^2  R_{t+3}+\cdots+\gamma^{n-1} R_{t+n}+\gamma^n V(s_{t+n})
\end{align}
$$

ここで、**TD(0)学習における以下の更新式を改良**することを考えます。
$$
\begin{align}
V^{\pi}(s_t)&=V^{\pi}(s_t)+\alpha(\[r_t+\gamma V^{\pi}(s_{t+1})\]-V^{\pi}(s_t))\\\\
\end{align}
$$
上の更新式は直後の遷移しか考えていませんが、先程導入した $G^{(n)}_t$ を用いれば、例えば

$$
\begin{align}
V^{\pi}(s_t)&=V^{\pi}(s_t)+\alpha(G^{(2)}_t-V^{\pi}(s_t))\\\\
V^{\pi}(s_t)&=V^{\pi}(s_t)+\alpha(G^{(4)}_t-V^{\pi}(s_t))\\\\
V^{\pi}(s_t)&=V^{\pi}(s_t)+\alpha(G^{(4)}_t-V^{\pi}(s_t))\tag{3}
\end{align}
$$
といったように改良できそうですね[^3]。一方で、最も上手く学習ができるような **$n$ を選ぶのは簡単ではありません**。そこで、すべての $n$ に渡って **$G^{(n)}_t$ の加重平均を取った値 $G^{\lambda}_t$ を更新に用いましょう**、というのがTD(λ)のアイディアです。$\lambda\in\[0,\\,1]$ に対して $G^{\lambda}_t$ は以下のように定義されます。

$$
G^{\lambda}\_t=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G^{(n)}_t
$$

これを用いて、TD(0)の更新式を

$$
V^{\pi}(s_t)=V^{\pi}(s_t)+\alpha(G^{\lambda}_t-V^{\pi}(s_t))
$$

と改善したのが**TD(λ)学習**です。$G^{\lambda}_t$ の計算時に $n$ が無限まで足し算しているので、モンテカルロ法と同様に**エピソードは有限**である必要があります。$\sum$ の係数に $1-\lambda$ がついているのは、$G^{n}_t$ の係数の総和を $1$ にするためです。

また、このような更新手法は「**ある状態よりもあとの状態を更新に利用する**」ことから、**Foward View TD**と呼ばれます。対になる概念として**Backward View TD**が存在しますが、こちらの解説は本稿では省略します。

# おわりに
**モンテカルロ法と、TD(0)学習、TD(λ)学習**について扱いました。特にTD(λ)学習の更新式は一見複雑ですが、**TD(0)学習の自然な改良**となっていることが分かれば飲み込みやすいと思います。今回は、モデルフリーの状況で状態価値を推定する方法について扱いました。次回は同じ状況下で方策を改善する手法として、モンテカルロ法を用いた方法や**SARSA**、**Q学習**について扱う予定です。

## 訳出について
専門用語は以下のように訳出しています。機械学習分野はしっかりとした和訳が確立されていないものも多いので、そのようなものは英語のままにしました。
|日本語|英語|
|---|---|
|初回訪問モンテカルロ法 |First-Visit Monte Carlo |
|逐一訪問モンテカルロ法 |Every-Visit Monte Carlo |
|偏り |bias |
|分散 |variance |
|TD誤差 |TD error |

## 参考文献
1. Sutton & Barto, "Reinforcement Learning: An Introduction", http://incompleteideas.net/book/the-book.html （最終閲覧: 2022/11/07）
2. sconeman, "強化学習理論の基礎2", https://qiita.com/sconeman/items/b1aacfa924e52102e9d612 （最終閲覧: 2022/11/07）
3. Wikipedia, "強化学習", https://ja.wikipedia.org/wiki/%E5%BC%B7%E5%8C%96%E5%AD%A6%E7%BF%92 （最終閲覧: 2022/11/07）
3. (画像素材) Unsplash, https://unsplash.com/ （最終閲覧: 2022/11/07）

なお、内容の説明にはLeibniz Universität HannoverのMarius Lindauer先生の講義を参考にしています。

[^1]: モンテカルロ法を用いて方策を改善する方法は第4回で紹介します。
[^2]: 火星探査は難しそうですね。他にも、患者へ薬を投与する時の状態観察に強化学習を適用する場合なども、モンテカルロ法の適用は難しいでしょう。
[^3]: (3)式のように改良すればモンテカルロ法です。