终于我们开始系统进入RL的部分。如本系列一开始所说的，我个人的观点是把Dynamic Programming（DP，动态规划）模型作为理解RL算法的基础，因为我们总可以把RL算法看作近似动态规划（approximate dynamic programming, ADP）的算法。因此，本篇文章我们就先来介绍一下DP模型。内容主要来自经过我调整的之前的一个知乎回答：

什么是动态规划（Dynamic Programming）？动态规划的意义是什么？​www.zhihu.com

参考的主要就是Dimitri P. Bertsekas的书籍^[1]前两章。

一、定义：两个集合

本节我们定义为了准确描述动态规划模型必不可少的5个符号。

考虑

那么我们现在定义了两组集合和一组函数。我们记无穷序列

坚持住，接下来就是定义最后最关键的符号了！我们把函数

在定义了这些符号后，抽象动态规划便主要是考虑如下两组递推映射

也就是说，

二、抽象动态规划模型

一般来说，一个动态规划问题会有

对不熟悉上边算子"连乘"记号的，实际上这个N个算子“连乘”可以分解成

也就是说，实际上我们是先对

当

即为原来成本函数的极限。动态规划模型的目标便是要找到一组最好的策略

在合理的条件下，这个问题等价于一个求不动点问题：

即问题变成了求

也就是说，抽象的来看，动态规划需要解决的问题就是计算由5个符号定义的，这个等式的解！

三、两个重要性质：单调性与压缩性

本节我们介绍常见动态规划模型需要满足的两个重要性质，也即前一段末尾所说的“合理的条件”。只有满足了这两个条件，我们的动态规划模型才可以化为上述唯一确定的基于Bellman's equation的不动点求解问题。

先说单调性（Monotonicity）：

也就是说算子

再说压缩性（Contraction）：

假设

也就是说

不过这个压缩性的话可能就不如前面那个单调性，没什么特别直观的道理。然而如果你认同“折旧”（discount）的会计概念，比如未来的单位成本相比今天的单位成本要按照日期以固定比例

好那么有没有什么直观的解释为什么我们的动态规划模型最好要满足这两个性质呢？

回忆：Bellman's equation的本质便是寻找

四、马尔可夫决策过程（Markov Decision Process）

上面的讨论其实完全没有涉及具有实际意义的问题，因此如果你觉得太抽象了，本节便讨论如何将MDP用抽象动态规划的框架写出来。那么因为是MDP，我们有所谓的离散时间状态转移方程：

也就是说，如果时间k的时候我们处于状态

注意这里我们使用了折旧系数

也就是说我们考虑的两个算子定义为

如果你已经接触过动态规划/强化学习的文献，这可能就会是你更加熟悉的递推方程（在RL模型中，绝大部分都是用这里的infinite horizon discounted MDP来建模的）。

容易验证，

---

五、Value Iteration算法：一些分析

Value Iteration（VI）算法是最常见的求解DP和RL的算法之一（另一个是Policy Iteration及其变种）。这个算法非常简单，找到一个起始的值函数

我们在上图中画出VI算法收敛的图示，注意

最后我们考虑近似VI算法的理论性质。即我们无法精确求出

那么我们的近似VI算法就可以得到一个序列

那么利用三角不等式和算子

令

我们注意到利用抽象动态规划模型的算子写法分析VI算法的收敛速率变得无比简单！至于实际问题中我们应该如何近似值函数，我们下次文章再重点讨论。

参考

1. ^Bertsekas, D. P. (2018). Abstract dynamic programming. Athena Scientific.