強化学習（森村）を読んで、価値反復法と縮小写像の関係が面白かったのでフォーカスしてまとめてみた。
ベルマン作用素と価値反復法
（前提となるマルコフ決定過程や方策などの概念の説明は割愛）
強化学習におけるゴールの一つは、次の（最適）ベルマン方程式を満たす最適価値関数$V^{*}$を求めることである。
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$を
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$に対し、ベルマン作用素を繰り返し適用することによって、最適価値関数を求めることができる。
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)$が存在して
||F(x) - F(y)|| \leq \mu||x - y|| \quad (\forall x,y \in X)
を満たすとき、$F$を縮小写像という。
直感的には、任意の2点間の距離がある一定のレートでどんどん近づいていくような「縮んでいく世界」を表現したものが、この縮小写像である。このような世界の上で成り立つ原理を表したのが次の定理である。
定理（縮小写像の原理2）
$X \subseteq \mathbb{R}^n$を閉集合、$F: X \rightarrow X$を縮小写像とする。
- $F(\bar{x}) = \bar{x}$となるような$\bar{x}$（これを不動点と呼ぶ）が$X$の中にただ一つ存在する。
- 任意の$x \in X$に対し、$F^{n}(x) \rightarrow \bar{x} \ (n \rightarrow \infty)$が成り立つ。
この定理はつまり、「縮んでいく世界」の中には唯一の動かない点が存在し、世界の全てはその点に向かって縮んでいくことを主張している。
加えて、縮小写像の定義に立ち戻ると、直ちに次の性質が成り立つことがいえる。
||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)|$で入れる。実は、適当な手続きを踏むと
||Bv - Bv'|| \leq \gamma ||v - v'|| \quad (v, v' \in \mathbb{R}^{|\mathcal{S}|})
すなわち、ベルマン作用素$B$が縮小写像であることが言える。
証明
\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}
したがって、縮小写像の原理から、次のことが保証される。
- 任意の価値関数$v$を初期値とした価値反復法により、最適価値関数が求まる
- 反復を通して、現在の価値関数と最適価値関数$V^{*}$との誤差は、割引率$\gamma$に従って指数的に減少する
- ベルマン方程式を満たす最適価値関数$V^{*}$は存在し、ただ一つである
以上の話はベルマン最適方程式だけでなく期待方程式、価値関数だけでなく行動価値関数についても同様に成り立つ。
このように、縮小写像を通してみることで、強化学習の基礎原理を見通しよく統一的に理解できる。
参考資料
- 強化学習（森村）
- https://towardsdatascience.com/mathematical-analysis-of-reinforcement-learning-bellman-equation-ac9f0954e19f
- 東京大学工学部計数工学科 基礎数理 講義資料