強化学習（森村）を読んで、価値反復法と縮小写像の関係が面白かったのでフォーカスしてまとめてみた。

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

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

強化学習におけるゴールの一つは、次の（最適）ベルマン方程式を満たす最適価値関数$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$は割引率を表す¹。ベルマン作用素$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点間の距離がある一定のレートでどんどん近づいていくような「縮んでいく世界」を表現したものが、この縮小写像である。このような世界の上で成り立つ原理を表したのが次の定理である。

定理（縮小写像の原理²）

$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^{*}$は存在し、ただ一つである

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

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

参考資料

簡単のため状態空間と行動空間は有限とする。また、実際には環境$p_{T}(s'|s, a)$は未知であり、探索を通して推定する対象となるが、便宜上既知とする（このような設定をプランニングという）。 ↩
Banachの不動点定理とも呼ぶ。実は、この定理は完備距離空間というより広い対象に一般化できる。 ↩