ベルマン作用素の基本と性質

この記事上での定義
- ベルマン方程式再び
ベルマン作用素とその性質
- 2つのベルマン作用素
  - 定義
- 性質
まとめ

間違っていたら教えてください

この記事上での定義

・作用素 : 関数から関数への写像
・ $\mathbb{R}^{S} : S \longrightarrow \mathbb{R}$
・ $S$ : 状態集合
・ $A$ : 行動の集合
・ $g(s,a): S \times A \rightarrow \mathbb{R}$ : 状態 $s$ で行動 $a$ を取った時に手に入る報酬を与える関数.
・ $p_t(s'|s,a) : S \times A \times S \rightarrow [0,1]$ : 状態 $s$ で行動 $a$ を取った時に,状態 $s'$ に遷移する確率を与える関数.
・ $\pi(s,a) : S \times A \rightarrow [0,1]$ : 方策の事.状態 $s$ で行動 $a$ を取る確率を与える関数.

ベルマン方程式再び

定義だけ書きます.
ベルマン方程式 : $V^{\pi}(s) =\displaystyle{\sum_{a \in A} \pi(s,a)(g(s,a)+\gamma \sum_{s' \in S}p_t(s'|s,a)V^{\pi}(s'))}$
ベルマン最適方程式 : $V^*(s) = \displaystyle{\max_{a \in A}\{g(s,a) + \gamma \sum_{s' \in S}p_t(s'|s,a)V^*(s')\}}$

ベルマン作用素とその性質

定義 $\rightarrow$ 性質と証明 $\rightarrow$ の順番に書きます.

2つのベルマン作用素

MDP $M=\{S,A,p_{s_0},p_t,g\}$ に対してのお話である事に注意してください.

定義

ベルマン期待作用素 $B_{\pi}:\mathbb{R}^S \rightarrow \mathbb{R}^S$ は,
$(B_{\pi}V)(s) := \displaystyle{\sum_{a \in A}\pi(a|s)(g(s,a)+\gamma \sum_{s' \in S}p_t(s'|s,a)V(s')),\ \forall s \in S}$ と,

ベルマン最適作用素 $B_* : \mathbb{R}^S \rightarrow \mathbb{R}^S$ は,
$(B_*V)(s) := \displaystyle{ \max_{a \in A}\{ g(s,a) + \gamma \sum_{s' \in S}p_t(s'|s,a)V(s') \},\ \forall s \in S }$ と定義します.

ベルマン方程式たちとそっくりな見た目です.
この様に定義する嬉しい理由はこれらの作用素の持つ性質に有ります(まとめに書いてあります).

性質

1.単調性

$v(s) \leq v'(s),\ \ \forall s \in S$ がならば,
・ $(B^n_* v)(s) \leq (B^n_* v')(s),\ \ \forall s \in S,\forall n \in \mathbb{N}$ と,
・ $(B^n_{\pi} v)(s) \leq (B^n_{\pi} v')(s),\ \ \forall s \in S,\forall n \in \mathbb{N}$ が成立.

証明(上の式)

数学的帰納法を用いて成立を示す.
成立を示す式を①とする.
(1) $n = 0$ の時, $v(s) \leq v'(s),\ \ \forall s \in S$ は明らかに成立するので,①の成立が示された.

(2) $n = k (\neq 0), k \in \mathbb{N}_0$ の時の成立を仮定し, $n = k+1$ の時の成立を示す.

$p_t(s'|s,a) > 0$ より, $p_t(s'|s,a)(B^k_*v)(s') \leq p_t(s'|s,a)(B^k_*v')(s'),\ \ \forall s \in S$ の成立が言える.
ゆえに, $\gamma \geq 0$ である事を踏まえて,
$\displaystyle{ g(s,a) + \gamma \sum_{s' \in S}p_t(s'|s,a)(B^k_*v)(s') \leq g(s,a) + \gamma \sum_{s' \in S}p_t(s'|s,a)(B^k_*v')(s'),\ \ \forall s \in S }$
より,
$\displaystyle{ \max_{a \in A}\{g(s,a) + \gamma \sum_{s' \in S}p_t(s'|s,a)(B^k_*v)(s') \} \leq \max_{a \in A} \{g(s,a) + \gamma \sum_{s' \in S}p_t(s'|s,a)(B^k_*v')(s') \} }$ ,
つまり $(B^{k+1}_*v)(s) \leq (B^{k+1}_*v')(s),\ \ \forall s \in S$ が成立する.
以上より, $n=k+1$ でも成立.

以上から,数学的帰納法より,①の成立が示された.
下の式も全く同様に証明できる.

2.ベルマン作用素はバラせる.

関数 $v$ に定数 $b$ を加えた関数を $(v+b):\mathbb{R}^{S}$ と定義する.
任意の $s \in S,n \in \mathbb{N}_0$ に対して,
・ $(B^n_*(v+b))(s) = (B^n_*v)(s) + \gamma^n b$ ,
・ $(B^n_{\pi}(v+b))(s) = (B^n_{\pi}v)(s) + \gamma^n b$ が成立.

証明(上の式)

$(v+b)(s) = v(s) + b,\ \ \forall s \in S$ が成立する事に留意して,数学的帰納法を用いて示す.
成立を示したい式を①と置く.

(1) $n = 0$ の時,
$(v+b)(s) = v(s) + b$ より,明らかに①は成立する.

(2) $n = k$ の時の成立を仮定して, $n = k+1$ でも成立する事を示す.
$(B^k_*(v+b))(s) = (B^k_*v)(s) + \gamma^k b,\ \ \forall s \in S$ が成立するから,これの両辺に $B_*$ を適用して,
$(B^{k+1}_* (v+b))(s) = B_*(B^{k}_*v + \gamma^k b)(s) = (B^{k+1}_* v)(s) + \gamma^{k+1}b,\ \ \forall s \in S$ が成立する.
ゆえに, $n = k+1$ でも成立する.

以上より,数学的帰納法から,①の成立が示された.
下の式も全く同様に証明できる.

3.収束性

任意の有界の状態関数 $s : \mathbb{R}^S$ に対して,
(1) $V^*(s) = \lim_{k \rightarrow \infty}(B^k_{*}v)(s),\ \forall s \in S$
(2)非定常な方策系列 $\Pi':=\{\pi_0,\pi_1,...,\pi_{k-1}\} \in \Pi_k^M$ のベルマン期待作用素 $B^k_{\Pi' }$ について,
$\Pi := \{\Pi',\pi_k,\pi_{k+1},...\} \in \Pi_k^M$ に対して, $V^{\Pi}(s) = \displaystyle{ \lim_{k \rightarrow \infty}(B^k_{\Pi}v)(s),\ \ \forall s \in S}$ が成立.

証明:

(1)関数 $v$ は $V^*$ の有界関数なので,
$|V^*(s)-(s)| \leq b,\ \ \forall s \in S$ なる定数 $b \in \mathbb{R}$ が存在する.
よって, $V^*(s) - b \leq v(s) \leq V^*(s) + b$ が成立.

この両辺に $B_*$ を $k$ 回適用して,単調性より,
$B_*^k(V^*-b)(s) \leq (B_*^kv)(s) \leq B_*^k(V^*+b)(s),\ \ \forall s \in S$ ,さらに変形して,
$(B_{*}^{k}V^{*})(s)-\gamma ^{k}b \leq (B_{*}^{k}v)(s) \leq (B_{*}^{k}V^{*})(s)+\gamma ^{k}b$ が成立.

これに対して, $k \rightarrow \infty$ とすれば,はさみうちの原理より, $\displaystyle{ \lim_{k \rightarrow \infty}(B^k_*v)(s) = V^*(s) },\ \ \forall s \in S$ が成立.
以上から,示された.

(2)
$V^{\Pi}(s) = \mathbb{E}[ \sum_{t=0}^{k-1}\gamma^tg(S_t,A_t)|S_0 = s ] + \mathbb{E} [ \sum_{t=k}^{\infty}\gamma^t g(S_t,A_t)|S_0 = s ],\ \ \forall s \in S$ より,
$g(s,a)$ は有界なので, $|g(s,a)| \leq R_{\rm{max}},\ \forall s \in S,\forall a \in A$ なる $R_{\rm{max}}$ が存在するから,
$\displaystyle{ -\sum_{t=k}^{\infty}\gamma^t R_{\rm{max}} \leq V^{\Pi}(s) - \mathbb{E}[\sum_{t=0}^{k-1}\gamma^t g(S_t,A_t)|S_0 = s ] \leq \sum_{t=k}^{\infty}\gamma^t R_{\rm{max}},\ \ \forall s\in S}$ が成立.
ゆえに, $\displaystyle{ \frac{-\gamma^k R_{\rm{max}}}{1-\gamma} \leq V^{\Pi}(s) - \mathbb{E}[\sum_{t=0}^{k-1}\gamma^t g(S_t,A_t)|S_0 = s ] \leq \frac{\gamma^k R_{\rm{max}}}{1-\gamma},\ \ \forall s \in S }$ が成立.

また, $(B_{\Pi}^kv)(s)$ は式の意味から,
$\displaystyle{ (B_{\Pi}^kv)(s) = \mathbb{E}[\sum_{t=0}^{k-1}\gamma^t g(S_t,A_t) + \gamma^k v(S_k)|S_0 = s ] = \mathbb{E}[\sum_{t=0}^{k-1}\gamma^t g(S_t,A_t)|S_0 = s ] + \gamma^k \mathbb{E}[v(S_k)|S_0 = s] }$
$v$ は有界なので, $|v(s)| \leq V_{max},\ \ \forall s \in S$ なる定数 $V_{max} \in \mathbb{R}$ が存在.
ゆえに, $\displaystyle{ -\gamma^k V_{max} \leq (B_{\Pi}^kv)(s) - \mathbb{E}[\sum_{t=0}^{k-1}\gamma^t g(S_t,A_t)|S_0 = s ] \leq \gamma^k V_{max},\ \ \forall s \in S }$ が成立.

以上の2つを合わせて,
$\displaystyle{ - \gamma^k(V_{max} + \frac{R_{max}}{1-\gamma} ) \leq (B_{\Pi}^kv)(s) \leq \gamma^k (V_{max} + \frac{R_{max}}{1- \gamma } ) }$ が成立するから, $k \rightarrow \infty$ とすれば,
はさみうちの原理より(2)の成立が示された.

4.一意性

(1)ベルマン最適方程式の解になる関数 $v:\mathbb{R}^S$ は,
$(B_*v)(s) = v(s),\ \forall s \in S$ を満たし,この様になる $v$ は $V^*$ のみである.
(2)定常な方策 $\pi$ についてのベルマン期待方程式の解になる関数 $v : \mathbb{R}^S$ は,
$(B^{\pi}v)(s) = v(s),\ \forall s \in S$ を満たし,この様になる $v$ は $V^{\pi}$ のみである.

証明
(1)
$\exists s\in S,V_{*}(s)\neq v'(s)$ かつ $(B_{*}v')(s)=v'(s)$ を満たす $v':S\rightarrow \mathbb{R}$ の存在を仮定する.
この時, $B^*v'=v'$ より, $\displaystyle{ V^*(s) = \lim_{k \rightarrow \infty}(B_*^kv')(s) = v'(s),\ \forall s \in S}$ が成立.

これは仮定に矛盾する.ゆえに,示された.

(2):(1)と全く同じ様に示せる.
ちなみに, $\pi$ が定常方策でなければならないのは,
定常では無い時,同じ状態 $s$ であっても時間ステップによって $p_t(s'|s,a)$ が異なるからである.

5.縮小性

任意の有界関数 $v:S\rightarrow \mathbb{R},v':S\rightarrow \mathbb{R}$ と $k\in \mathbb{N_0},0 \leq \gamma < 1$ に対して,
(1)ベルマン最適作用素 $B_{*}$ について,
$\max_{s\in S}|(B_*^kv)(s)-(B_*^kv')(s)|\leq \gamma^{k}\max_{s\in S}|v(s)-v'(s)|$
が成立.
(2)任意の $\pi \in \Pi$ のベルマン最適作用素 $B_{\pi}$ について
$\max_{s\in S}|(B^k_{\pi}v)(s)-(B^k_{\pi}v')(s)| \leq \gamma^{k}\max_{s\in S}|v(s)-v'(s)|$
が成立.

証明
(1) $\alpha := \min_{s \in S}\{v(s) - v'(s)\},\ \beta := \max_{s \in S}\{v(s)-v'(s)\}$ と置く.
式の意味から, $v'(s) + \alpha \leq v(s) \leq v'(s) + \beta$ が成立する.
この両辺に $B_*$ を繰り返し適用して
$(B_*^kv')(s) + \gamma^k \alpha \leq (B_*^kv)(s) \leq (B_*^kv')(s) + \gamma^k \beta$ が成立.

ここで, $\epsilon := \max\{ |\alpha|,|\beta|\}$ とすると,
$(B_*^kv')(s) - \gamma^k \epsilon \leq (B_*^kv)(s) \leq (B_*^kv')(s) + \gamma^k \epsilon$ が成立.
ゆえに, $-\gamma^k \epsilon \leq (B_*^kv)(s) - (B_*^kv')(s) \leq \gamma^k \epsilon$ が成立する.