縮小写像の原理から見た強化学習

[強化学習（森村）](https://www.kspub.co.jp/book/detail/5155912.html)を読んで、価値反復法と縮小写像の関係が面白かったのでフォーカスしてまとめてみた。

## ベルマン作用素と価値反復法

（前提となるマルコフ決定過程や方策などの概念の説明は割愛）

強化学習におけるゴールの一つは、次の（最適）ベルマン方程式を満たす最適価値関数$V^{*}$を求めることである。

```math
V^{*}(s) = \max_{a \in \mathcal{A}} \left\{ g(s, a) + \gamma \sum_{s' \in \mathcal{S}} p_{T}(s'|s, a)V^{*}(s') \right\} \quad (s \in \mathcal{S})
```

ここで、$s \in \mathcal{S}$は状態、$a \in \mathcal{A}$は行動、$g(s, a)$は報酬関数、$p_{T}(s'|s, a)$は状態遷移確率関数、$\gamma$は割引率を表す[^1]。ベルマン作用素$B: v \mapsto v$を
[^1]: 簡単のため状態空間と行動空間は有限とする。また、実際には環境$p_{T}(s'|s, a)$は未知であり、探索を通して推定する対象となるが、便宜上既知とする（このような設定をプランニングという）。

```math
Bv(s):= \max_{a \in \mathcal{A}} \left\{ g(s, a) + \gamma \sum_{s' \in \mathcal{S}} p_{T}(s'|s, a) v(s') \right\} \quad (s \in \mathcal{S})
```

で定義すると、ベルマン方程式は$Bv = v$とシンプルに書くことができる。

最適価値関数を求めるアプローチの一つに、価値反復法がある。価値反復法では、適当な価値関数の初期値$v$に対し、ベルマン作用素を繰り返し適用することによって、最適価値関数を求めることができる。

```math
B^n v(s) \xrightarrow{n\to\infty} V^{*}(s) \quad (s \in \mathcal{S})
```

価値反復法を理解するにあたり、素朴に次のような疑問が湧いてくる。

- なぜベルマン作用素を繰り返し適用することで最適価値関数$V^{*}$を求めることができるのか
- どれくらい反復すれば最適価値関数$V^{*}$に収束してくれるのか
- そもそもベルマン方程式の解となる最適価値関数$V^{*}$の存在性、唯一性はいえるのか

これらの疑問に対する答えは「ベルマン作用素が縮小写像だから」という事実に集約される。

## 縮小写像の原理

翻って縮小写像について説明する。$X \subseteq \mathbb{R}^n$のノルムを$||\cdot||$とする。

**定義（縮小写像）**

写像$F: X \rightarrow X$について、ある$\mu \ (0 \leq \mu < 1)$が存在して

```math
||F(x) - F(y)|| \leq \mu||x - y|| \quad (\forall x,y \in X)
```

を満たすとき、$F$を縮小写像という。

直感的には、任意の2点間の距離がある一定のレートでどんどん近づいていくような「縮んでいく世界」を表現したものが、この縮小写像である。このような世界の上で成り立つ原理を表したのが次の定理である。

**定理（縮小写像の原理[^2]）**
[^2]: Banachの不動点定理とも呼ぶ。実は、この定理は完備距離空間というより広い対象に一般化できる。

$X \subseteq \mathbb{R}^n$を閉集合、$F: X \rightarrow X$を縮小写像とする。

1. $F(\bar{x}) = \bar{x}$となるような$\bar{x}$（これを不動点と呼ぶ）が$X$の中にただ一つ存在する。
2. 任意の$x \in X$に対し、$F^{n}(x) \rightarrow \bar{x} \ (n \rightarrow \infty)$が成り立つ。

この定理はつまり、「縮んでいく世界」の中には唯一の動かない点が存在し、世界の全てはその点に向かって縮んでいくことを主張している。

加えて、縮小写像の定義に立ち戻ると、直ちに次の性質が成り立つことがいえる。

```math
||F^{n}(x) - \bar{x}|| \leq \mu^n||x - \bar{x}|| \quad (\forall x \in X)
```

これより、任意の$x$は縮小の強さを表す$\mu$に依存した指数的なレートで不動点$\bar{x}$に近づいていくことがわかる。

## 縮小写像の原理から見た強化学習

以上を踏まえた上で、強化学習の文脈に戻る。

価値関数$v$を$\mathbb{R}^{|\mathcal{S}|}$上の$|\mathcal{S}|$次元のベクトルと見なし、ノルムを$||v|| = \max_{s \in \mathcal{S}}|v(s)|$で入れる。実は、適当な手続きを踏むと

```math
||Bv - Bv'|| \leq \gamma ||v - v'|| \quad (v, v' \in \mathbb{R}^{|\mathcal{S}|})
```

すなわち、ベルマン作用素$B$が縮小写像であることが言える。

<details>
<summary>証明</summary>
<div>

```math
\begin{align}
||Bv - Bv'|| &= \max_{s \in \mathcal{S}} \left| \max_{a \in \mathcal{A}} \left\{ g(s, a) + \gamma \sum_{s' \in \mathcal{S}} p_{T}(s'|s, a) v(s') \right\} - \max_{a \in \mathcal{A}} \left\{ g(s, a) + \gamma \sum_{s' \in \mathcal{S}} p_{T}(s'|s, a) v'(s') \right\} \right| \\
&\leq \max_{s \in \mathcal{S}} \left| \max_{a \in \mathcal{A}} \left\{   \left(g(s, a) + \gamma \sum_{s' \in \mathcal{S}} p_{T}(s'|s, a) v(s') \right) - \left(g(s, a) + \gamma \sum_{s' \in \mathcal{S}} p_{T}(s'|s, a) v'(s') \right) \right\} \right| \\
&= \max_{s \in \mathcal{S}} \left| \max_{a \in \mathcal{A}} \gamma \sum_{s' \in \mathcal{S}} p_{T}(s'|s, a) \left(v(s') - v'(s') \right) \right| \\
&\leq \max_{s \in \mathcal{S}} \left|\max_{a \in \mathcal{A}} \gamma \sum_{s' \in \mathcal{S}} p_{T}(s'|s, a) ||v - v'|| \right| \\
&= \gamma ||v - v'||
\end{align}
```
</div>
</details>
    

したがって、縮小写像の原理から、次のことが保証される。

- 任意の価値関数$v$を初期値とした価値反復法により、最適価値関数が求まる
- 反復を通して、現在の価値関数と最適価値関数$V^{*}$との誤差は、割引率$\gamma$に従って指数的に減少する
- ベルマン方程式を満たす最適価値関数$V^{*}$は存在し、ただ一つである

以上の話はベルマン最適方程式だけでなく期待方程式、価値関数だけでなく行動価値関数についても同様に成り立つ。

このように、縮小写像を通してみることで、強化学習の基礎原理を見通しよく統一的に理解できる。

## 参考資料

- [強化学習（森村）](https://www.kspub.co.jp/book/detail/5155912.html)
- https://towardsdatascience.com/mathematical-analysis-of-reinforcement-learning-bellman-equation-ac9f0954e19f
- [東京大学工学部計数工学科 基礎数理 講義資料](http://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-kisosuri/contraction071210.pdf)