两个问题
- 预测(prediction)
- 控制(control)
预测就是给定一个策略，我们要根据贝尔曼最优方程求解最优价值函数。
控制则是求解出最优策略和最优价值函数。
预测问题的解决
显然预测问题更好解决，所以我们先讨论预测问题的解决。
解决方法
基本思想就是迭代。由于策略已经给定，我们将贝尔曼方程改写成矩阵形式，有
记迭代轮数为$k$,基本想法就是用上一轮的状态价值函数结合(1)式算出当前轮的状态价值函数。即
直到状态价值函数收敛，我们就能得到给定策略$\pi$对应的状态价值函数。
证明
证明上述迭代可以收敛到我们给定$\pi$对应的$\mathcal{V}^{\pi}$不是那么显然的，下面开始一波推导。
这个的证明需要用到压缩映射定理，介绍这个定理前先看几个定义。
距离
距离这个概念在数学分析中学到过，定义一个$d$为距离，如果满足以下3个条件：
- (非负性) $d(x,y) \geq 0且d(x,y)=0 \Leftrightarrow x=y$
- (对称性) $d(x,y)=d(y,x)$
- (三角不等式) $d(x,y) \leq d(x,z)+d(z,y)$
我们平时空间中算的欧几里得距离，绝对值距离等等都是这个定义基础之上的。在一个空间上定义了某种距离则称这个空间为该种距离的空间。
cauchy序列
记${x_n}$是距离空间$X$中的点列，对于$\forall \varepsilon >0,\exists 自然数 N，当\forall $m$,$n$>N时，有|x_m-x_n|<\varepsilon$,称${x_n}$是距离空间$X$中的cauchy序列。
如图，cauchy序列直观上理解就是$N$很大时任意两点之间距离很小。注意cauchy序列的定义是依赖于距离的。
完备空间
如果一个空间中的任何柯西序列都收敛在该空间之内，则称该空间为完备空间。
实数是完备空间，有理数则不是。因为$\sqrt{2}$的有限位小数逼近$\sqrt{2}$。
压缩映射定理
理解了上述几个定义，我们可以讨论压缩映射定理了。首先我们先看一下什么叫压缩映射。
压缩映射
对于一个完备空间$\langle M,d \rangle$,一个连续映射函数$f:M \to M$,如果存在实数$k \in [0,1)$,使得对于任意$x,y \in M$，有 ,则称$f$是该完备空间上的一个压缩映射。
压缩映射定理
对于一个完备空间$\langle M,d \rangle$,一个映射函数$f:M \to M$，$f$是它的一个压缩映射函数，则有：
- 在该空间中存在唯一的点$x_{*}$满足$f(x_{*})=x_{*}$
- 对该空间中的任意点$x$，有$\lim\limits_{n \to \infty}f^n(x)=x_*$。其中$f^n(x)=f(f^{n-1}(x))$
压缩映射定理的证明
首先证明第2条。
对于任意$x,y \in M$,由距离和压缩映射的定义，
由(3):
对于任意$x \in M$, 任意自然数$P,Q$，结合(4)有
由(5)，我们知道${f^n(x)}$是cauchy数列，而且由完备空间知，该数列是收敛的。
记$\lim\limits_{n \to \infty}f^n(x)=x_{*}$。下面我们欲证第1条，分两步。首先证明$f(x_{*})=x_{*}$。
结合$f$定义的连续性，有
下面再证明$x_{*}$的唯一性即可。不失一般性，反证法。假设有$y_{*}$满足同样的性质，则 $$d(x_*,y_*)=d(f(x_*),f(y_*))\leq k \cdot d(x_*,y_*)<d(x_*,y_*)$$
矛盾！至此我们证明完毕。
迭代收敛正确性的证明
记
则我们每一轮的状态函数值就是数列${\mathcal{T}^k(\mathcal{V}^{\pi})}$。下面我们要说明$\mathcal{T}$是个压缩映射。首先需要定义一个距离，这里我们采用无穷范数。矩阵的无穷级数是行和的绝对值的最大值，而向量的无穷级数则是单个元素的绝对值的最大值。
对于$u,v$任意两个状态值函数，我们有
$$d(\mathcal{T}(u),\mathcal{T}(v))=||\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi}u-\mathcal{R}^{\pi}-\gamma \mathcal{P}^{\pi}v||_{\infty}=||\gamma \mathcal{P}^{\pi}(u-v)||_{\infty}\\ \leq \gamma||\mathcal{P}_{\pi}||_{\infty}\cdot ||u-v||_{\infty} \tag{7}$$
考虑到$\mathcal{P}_{\pi}$是个状态转移概率分布，所以有
$$||\mathcal{P}_{\pi}||_{\infty}= 1 \tag{8}$$
由(7)和(8):
所以$\mathcal{T}$在无穷范数的距离和状态函数值空间下是压缩映射，由压缩映射定理，我们的迭代$\mathcal{T}^k$最终会收敛，再结合(1)，我们知道会收敛到$\mathcal{V}^{\pi}$。
证毕！
控制问题的解决
控制问题主要有两种解决方式，分别成为策略迭代和值迭代，下面我们分别讨论。
策略迭代
基本想法就是先给定一个策略$\pi$,然后我们根据上面提出的预测问题的迭代方法求出$\mathcal{V}^{\pi}$,此时一个自然的想法就是更新$\pi$至$\pi^{‘}$,确保$\mathcal{V}^{\pi^{‘}}\geq \mathcal{V}^{\pi}$。
更新策略如下：
对任意状态$s$,
我们要说明，对任意状态$s$，下列式子成立:
$$v_{\pi}(s)=\sum_{a \in A} \pi(a|s) \cdot q_{\pi}(s,a) \tag{9}$$ $$q_{\pi}(s,a)=r_s^a+\gamma \sum_{s' \in S}P(s_{t+1}=s'|s_t=s,a_t=a)\cdot v_{\pi}(s') \tag{10 }$$
结合(9)和(10)，有
最后一步是由定义得来，如下：
每个期望展开计算恰好和上面的式子对应，所以上式右边是$v_{\pi^{‘}}(s)$。
总结一下策略迭代就是先给定一个策略，然后先根据该策略迭代得到该策略对应的状态价值函数，然后根据该状态价值函数更新策略再继续上述过程。我们知道加入折扣因子后，$v_{\pi}(s)$是有上界的(因为即时奖励已经由环境给定)，单调递增有上界的无穷数列必收敛。所以最终我们能得到$v_*(s)$。
值迭代
首先我们回顾以下最优贝尔曼方程：
值迭代的基本思想就是不断根据(11)迭代$v$,然后收敛到$v_{*}$。具体证明我们后面再推导。我们根据$v_*$就可以根据(12)计算出$q_{*}$函数。然后根据$q_{*}$函数我们就能得到$\pi_{*}$。
首先定义几个记号，$\mathcal{R}^a$和$\mathcal{P}^a$。
$\mathcal{R}^a$：一个$|S|*1$的向量，表示动作$a$每个状态值的奖励。
$\mathcal{P}^a$:一个$|S|*|S|$的矩阵，表示给定动作$a$状态$s$到$s'$的状态转移概率。
将(11)表示为矩阵形式,然后和策略迭代一样，定义： 只要说明$\mathcal{T}$是个压缩映射，就得证了。此处我们依然采用无穷范数定义为我们的距离。
我们先证明一个引理：
$f$和$g$是$\mathbb{R}^d \to \mathbb{R}$上的映射，则有：
$$|\max\limits_xf(x)-\max\limits_xg(x)| \leq \max\limits_x|f(x)-g(x)| \tag{13}$$
反证法：
记$x_0=argmax_x[f(x)],x_1=argmax_x[g(x)]$。
由对称性，不妨假设$f(x_0)>g(x_1)$。有$f(x_0)>g(x_1)\geq g(x_0)$
$$f(x_0)-g(x_1)>\max\limits_x|f(x)-g(x)|$$
$$g(x_1)<f(x_0)-\max\limits_x|f(x)-g(x)|\leq f(x_0)-|f(x_0)-g(x_0)|=g(x_0)$$
矛盾！
还有一个显然的性质就是一个向量的无穷范数等于这个向量每一项取绝对值后的无穷范数。
下面证明$\mathcal{T}$是个压缩映射。
对于任意两个$u$和$v$,有
$$d(\mathcal{T}(u),\mathcal{T}(v))=||\max\limits_{a \in A}(\mathcal{R}^a+\gamma \mathcal{P}^a \mathcal{u})-\max\limits_{a \in A}(\mathcal{R}^a+\gamma \mathcal{P}^a \mathcal{v})||_{\infty} \tag{14}$$
注意(14)中的$\max$是指对向量的每一项计算时候的操作，而且我们知道对每一项取绝对值后向量的无穷范数不变，所以我们对每一项的计算取绝对值后应用引理放大(先取绝对值再将每项放大显然能保证向量的无穷范数不减):
记$abs(v)$表示对向量$v$的每一项做取绝对值操作。
$$d(\mathcal{T}(u),\mathcal{T}(v)) \leq ||\max\limits_{a \in A}abs(\mathcal{R}^a+\gamma \mathcal{P}^a \mathcal{u}-\mathcal{R}^a-\gamma \mathcal{P}^a \mathcal{v})||_{\infty}\\ =\gamma ||\max\limits_{a \in A}abs(\mathcal{P}^a(u-v))||_{\infty} \tag{15}$$
我们知道对于任意的$a \in A$,有：
$$\mathcal{P}^a的行和=1且\mathcal{P}^a是转换概率\tag{16}$$
结合$\max$是相对于向量的每一项操作，所以$\max\limits_{a \in A}abs(\mathcal{P}^a(u-v))$这个向量的每一项都非负并且$\leq abs(u-v)$向量中每一项的最大值。
结合(15): 得证！
总结
策略迭代和值迭代都能解决控制问题，但不同之处是策略迭代要求每个策略都要计算出收敛的状态价值函数，而值迭代函数相当于就计算了一次状态价值函数就更新策略了。一般来讲，值迭代更容易收敛，因为很多时候状态值函数不用收敛更新的策略和状态价值函数收敛后更新的策略是相同的。
我们知道$\mathcal{P}^{\pi}$是由环境的动力学决定的，一般情况下这个动力学规律我们是没办法直接获取的。能获取这些的我们就称为基于模型的学习。后续我们会讨论这些未知的学习方法，称为不依赖模型对的学习。
参考链接
http://chercheurs.lille.inria.fr/~ghavamza/RL-EC-Lille/Lecture4-b.pdf
https://cs.uwaterloo.ca/~ppoupart/teaching/cs886-spring13/slides/cs886-module6-value-iteration.pdf
