这一节，我们先介绍强化学习中，当马尔科夫决策过程可以利用元组 (S,A,P,r,γ) 来描述，且转移概率 P 已知(称为基于模型强化学习），该类强化学习的优化问题可以通过动态规划算法进行解决。

   

4.1. 什么是动态规划

Richard Bellman在20世纪50年代提出的动态规划（dynamic programming）概念，这是一种强大的算法设计技术——将问题分解成多个小问题，存储它们的解，通过将其结合在一起，最终得到原始问题的解决方案。

了解更多相关知识请参考动态规划_百度百科 (baidu.com)

4.2.动态规划为什么可以求解基于模型强化学习

根据第二节(2.强化学习如何建模序贯决策问题 - 知乎 (zhihu.com))部分，介绍的状态值函数与状态-行为值函数的贝尔曼⽅程，最优值函数和状态行为值函数满足下述方程：

      从4.1部分介绍的动态规划基础知识可以知道，如果想利⽤动态规划解决的问题需要满⾜两个条件：⼀是整个优化问题可以分解为多个⼦优化问题；⼆是⼦优化问题的解可以被存储和重复利⽤。

     从第二节(2.强化学习如何建模序贯决策问题 - 知乎 (zhihu.com))回忆下述图和值函数的迭代计算公式，状态 s 处的值函数 υπ(s) ，可以看成后继状态的值函数 υπ(s′) 的表示。另外，动态规划的第二个条件较容易满足。因此，该类强化学习，可以通过动态规划求解。

4.3.如何利用动态规划求解基于模型强化学习

     对于求解上式(4.2)方程， ，Pssa，γ 和 Rsa 都是已知数， π(a|s) 为要评估的策略是指定的，也是已知值。方程中唯一的未知数是值函数，该方程，变成求解值函数的线性方程组，如何求解呢？

4.3.1. 线性方程组的迭代求解法

      用方程表示一般的线性方程组： AX=b    （4.3）

      线性方程组的数值求解包括直接法（如高斯消元法、矩阵三角分解法、平方根法、追赶法等）和迭代解法。策略评估中采用线性方程组的迭代解法。

       所谓迭代解法是根据(4.3)式设计一个迭代公式，任取初始值 X(0) ，将其导入到设计的迭代公式中，得到 X(1) ，再将代入迭代公式中得到 X(2) ，如此循环最终得到收敛的 X 。常用的迭代方法有：

方法一：雅可比(Jacobi)迭代法

       方法二：高斯-赛德尔迭代法

4.3.2. 基于动态规划的基于模型强化学习迭代算法设计思路

      此处，我们使用高斯-赛德尔迭代算法进行求解(4.2)。

思考题：上述迭代公式，能够获得线性方程组(4.2)的解吗？答案请参考4.3.5解内容

基本问题1：策略评估算法。给定⼀个策略π，如何计算在策略π下的值函数？

基本问题2：策略改善算法。如何利⽤值函数进⾏策略改善，从⽽得到最优策略？

    ⼀个很⾃然的⽅法是当已知当前策略的值函数时，在每个状态采⽤贪婪策略对当前策略进⾏改善

4.3.3.基于模型强化学习迭代算法——策略迭代算法

      策略迭代算法包括策略评估和策略改善两个步骤。在策略评估中，给定策略，通过数值迭代算法不断计算该策略下每个状态的值函数。利用该值函数和贪婪策略得到新的策略。

      从策略迭代的伪代码我们看到，进⾏策略改善之前需要得到收敛的值函数。值函数的收敛往往需要很多次迭代(如下图所示)，现在问题是进⾏策略改善之前⼀定要等到策略值函数收敛吗？

答案:不⼀定要等到策略评估算法完全收敛。

如果我们在评估一次之后就进行策略改善，则称为值函数迭代算法(接下来要介绍的算法)。

4.3.4.基于模型强化学习迭代算法——值迭代算法

      值函数迭代算法的伪代码如下：

4.3.5.高斯-赛德尔迭代的策略评估算法会收敛吗？

   首先介绍一个数学概念：压缩映射(contraction mapping)。

   定义：设 X 是度量空间，其度量用 ρ 表示。映射 T:X→X ,若存在a, 0≤a<1 使得 ρ(Tx,Ty)≤aρ(x,y),∀x,y∈X , 则称 T 是 X 上的一个压缩映射。

   定理1：完备度量空间上的压缩映射具有唯一的不动点。

   定理1，也可以解释为，从度量空间任何一点出发，只要满足压缩映射，压缩映射的序列必定会收敛到唯一的不动点。因此，证明一个迭代序列是不是收敛，只需证明该序列所对应的映射是不是压缩映射。

在回答策略评估算法是否收敛的证明中

4.4.思考

思考1：基于模型的策略迭代算法，优化变量(迭代策略)收敛性吗？

思考2：基于模型的值函数迭代算法，优化变量(迭代策略)收敛性吗？