强化学习第二讲

• 线性方程组的迭代解法(高斯-赛德尔迭代法)
• 基于模型的动态规划方法(策略迭代算法)

一、动态规划前置数学基础

1.雅克比(Jacobi)迭代法

不失一般性，用下述方程表示一般的线性方程组：

$AX=b \tag{2.1}$

雅克比迭代法假设系数矩阵的对角元素$a_{ii}\neq0\,$，以此构造迭代方程：

$\begin{cases} x_{1}=\frac{1}{a_{11}}\left(-a_{12}x_{2}-a_{13}x_{3}-\dots -a_{1n}x_{n}+b_{1}\right) \\ x_{2}=\frac{1}{a_{22}}\left(-a_{21}x_{1}-a_{23}x_{3}-\dots -a_{2n}x_{n}+b_{2}\right) \\ \qquad\qquad\qquad\qquad\quad\dots \\ x_{n}=\frac{1}{a_{nn}}\left(-a_{n1}x_{1}-a_{n3}x_{3}-\dots -a_{n,n-1}x_{n-1}+b_{n}\right)\tag{2.2} \end{cases}$

方程(2.2)写成矩阵的形式为

$X=-D^{-1}(L+U)X+D^{-1}b\tag{2.3}$

其中：

$D= \begin{bmatrix} a_{11}& & &\\ &a_{22}& & \\ & &\ddots& \\ & & & a_{nn} \end{bmatrix}, L=\begin{bmatrix} 0 & & & & \\ a_{21} & 0 & & & \\ a_{31} & a_{32} & 0 & & \\ \vdots & \vdots & & \ddots & \\ a_{n1} & a_{n2} & a_{n3}& \cdots & 0 \end{bmatrix},$

$U= \begin{bmatrix} 0 & & a_{21} & &\\ &a_{22}& & \\ & &\ddots& \\ & & & a_{nn} \end{bmatrix}$

若记$B=-D^{-1}(L+U)$，$d=D^{-1}b$，则迭代公式为

$X=BX+d\tag{2.4}$

在进行迭代计算时，(2.2)式变成

$\begin{cases} x_{1}^{(k+1)}=\frac{1}{a_{11}}\left(-a_{12}x_{2}^{(k)}-a_{13}x_{3}^{(k)}-\dots -a_{1n}x_{n}^{(k)}+b_{1}\right) \\ \\ x_{2}^{(k+1)}=\frac{1}{a_{22}}\left(-a_{21}x_{1}^{(k)}-a_{23}x_{3}^{(k)}-\dots -a_{2n}x_{n}^{(k)}+b_{2}\right) \\ \qquad\qquad\qquad\qquad\quad\dots \\ \\ x_{n}^{(k+1)}=\frac{1}{a_{nn}}\left(-a_{n1}x_{1}^{(k)}-a_{n3}x_{3}^{(k)}-\dots -a_{n,n-1}x_{n-1}^{(k)}+b_{n}\right)\tag{2.5} \end{cases}$

2.高斯-赛德尔(Gauss-Seidel)迭代法

从上述雅克比迭代式中可以看出，没有立即利用已算出来的$x_{1}^{(k+1)},x_{2}^{(k+1)},\cdots$等分量，而这些分量一般比$x_{1}^{(k)},x_{2}^{(k)},\cdots$更为精确。

所以高斯-赛德尔迭代法对其进行了优化，对(2.5)式中第二个方程，第一行式子算出来的$x_{1}^{(k+1)}$值立马投入后续方程里，直到第n个方程。即：

$\begin{cases} x_{1}^{(k+1)}=\frac{1}{a_{11}}\left(-a_{12}x_{2}^{(k)}-a_{13}x_{3}^{(k)}-\dots -a_{1n}x_{n}^{(k)}+b_{1}\right) \\ \\ x_{2}^{(k+1)}=\frac{1}{a_{22}}\left(-a_{21}x_{1}^{(k+1)}-a_{23}x_{3}^{(k)}-\dots -a_{2n}x_{n}^{(k)}+b_{2}\right) \\ \qquad\qquad\qquad\qquad\quad\dots \\ \\ x_{n}^{(k+1)}=\frac{1}{a_{nn}}\left(-a_{n1}x_{1}^{(k+1)}-a_{n3}x_{3}^{(k+1)}-\dots -a_{n,n-1}x_{n-1}^{(k+1)}+b_{n}\right)\tag{2.6} \end{cases}$

方程(2.6)式写成矩阵形式

$(D+L)X^{(k+1)}=-UX^{(k)}+b$

写成迭代方程为：

$X^{(k+1)}=GX^{(k)}+d_{1}\tag{2.7}$

其中$G=-(D+L)^{-1}U$，$d_{1}=(D+L)^{-1}b$

3.压缩映射证明策略评估的收敛性

略……(反正就是泛函分析数学证明收敛，也看不大懂，嗯，水了www)
可参考文章。

二、基于模型的动态规划方法(Model Based)

1、分类

在MDP框架中，根据状态转移概率P是否已知，可划分出基于模型的动态规划方法和基于无模型的强化学习方法。

两种类别都包括策略迭代算法，值迭代算法和策略搜索算法。

有模型与无模型预测和控制的方法
有模型(MDP):
预测：动态规划DP
控制：policy iteration; value iteration
无模型：
预测：MC;TD
控制：Sarsa;Q-learning

2.贝尔曼(Bellman)方程

• $Return$(回报)说的是把奖励进行折扣后所获得的收益，可定义为奖励的逐步叠加，如下式所示：

$G_{t}=R_{t+1}+\gamma{}R_{t+2}+\gamma{}^{2}R_{t+3}+\dots{}+\gamma{}^{T-t-1}R_{T}\tag{2.8}$

• 有了$return$之后，即可以定义一个状态的价值了，就是$state\ value\ function$。对于MRP，其被定义成是$return$的期望:

$\begin{aligned} v_{t}(s)&=E\left[G_{t}\mid{}s_{t}=s\right]\\ &=E\left[R_{t+1}+\gamma{}R_{t+2}+\dots{}+\gamma{}^{T-t-1}R_{T}\mid{}s_{t}=s\right]\\ &=E\left[R_{t+1}+\gamma{}G_{t+1}\mid{}s_{t}=s\right]\\ &=E\left[R_{t+1}+\gamma{}v(s_{t+1})\mid{}s_{t}=s\right]\\ &=R(s)+\gamma{}\sum_{s'\in{s}}P(s'\mid{}s)V(s')\tag{2.9} \end{aligned}$

上式即贝尔曼(Bellman)方程，在马尔科夫决策过程中表述为：

$v_{\pi{}}(s)=\sum_{a\in{}A}{\pi{}(a\mid{}s)\left(R_{s}^{a}+\gamma{}\sum_{s'\in{}S}{P_{ss'}^{a}v_{\pi{}}(s')}\right)}\tag{2.10}$

可以发现，状态s处的值函数$v_{\pi}(s)$可以利用后继状态的值函数$v_{\pi}(s')$来表述，即自举算法(bootstrapping)，于是乎我们可以用高斯-赛德尔迭代法来进行迭代计算，得到值函数并进行评估。

3.策略迭代算法

• 策略评估算法
  伪代码如下：

[1]输入:$\,$需要评估的策略$\,\pi{}\,$状态转移概率$P_{ss'}^{a}\,$和回报函数$R_{s}^{a}\,$,折扣因子$\gamma{}$
[2]初始化值函数：$v{}(s)=0$
[3]$\,Repeat\,k=0,1,\dots{}$
[4]$\quad{}for\ every\ s\ do$
[5]$\qquad{}\quad{}v_{k+1}(s)=\sum_{a\in{A}}{\pi{}(a\mid{}s)\left(R_{s}^{a}+\gamma{}\sum_{s'\in{S}}{P_{ss'}^{a}v_{k}(s')}\right)}$
[6]$\quad{}end\ for$
[7]$\,{}Until\enspace{}v_{k+1}=v_{k}$(精度控制)
[8]输出：$v(s)$

需要注意，每次迭代都需要对状态集进行一次遍历(扫描)一遍评估每个状态的值函数。

• 策略改善算法
  计算值函数的目的是利用值函数找到最优策略，可以自然的想到在已知当前策略的值函数时，在每个状态进行贪心改善当前策略，即：

$\pi_{l+1}(s)\in{\underset{a}{\argmax{}}q^{\pi{}_{l}}(s,a)}$

• 策略迭代算法
  策略迭代包括评估与改善两个步骤。在策略评估中，给定策略每个状态值函数，然后改善得到新策略。如此循环下去，最终得到最优策略，这是一个策略收敛的过程。伪代码如下：

[1]输入:$\,$状态转移概率$P_{ss'}^{a}\,$和回报函数$R_{s}^{a}$，折扣因子$\gamma{}$
[2]初始化值函数：$v(s)=0$，初始化策略$\pi{}_{0}$
[3]$\,Repeat\,l=0,1,\dots{}$
[4]$\quad{}find\ v^{\pi{}_{l}}$
[5]$\quad{}\pi_{l+1}(s)\in{\underset{a}{\argmax{}}q^{\pi{}_{l}}(s,a)}$
[6]$\,{}Until\enspace{}\pi{}_{l+1}=\pi{}_{l}$
[7]输出：$\pi{}^{*}=\pi{}_{l}$

• 由上可看出，值函数往往需要多次迭代，但事实上可以不用等到策略评估算法完全收敛。特别的，如果在评估一次后立马进行策略改善，则称为值函数迭代算法

4、值函数迭代算法

详情请听下回分解……

三、总结

• 总体有了大概的轮廓，比如说根据有无model采取不同的算法来获取最优策略，以及基于策略、值、或者演员-评论家方法进行值函数的计算和优化策略。
• 看到什么最优控制问题属于是一头懵了，有关DDP方法的一堆变分推导我只能otz，下次再写吧，顺带着把python示例也码出来，还算好理解。
• 不知道这个课咋考核啊，不会真要跑代码吧……