【强化学习与最优控制】笔记（一）确定性问题的动态规划

0 写在前面的

最近在学动态规划和强化学习，主要采用的教材是这本书，Bertsekas D P. Reinforcement learning and optimal control[M]. Belmont, MA: Athena Scientific, 2019. 这本书是最新出的目前网上能找到的只有一个草稿版本，需要电子版的同学可以在如下链接的公众号回复"强化学习2021“即可获得教材电子版：

Dimitri P. Bertsekas 强化学习2021版教材和视频课程推荐

教材纸质版在京东有卖的，建议大家将笔记和教材结合起来看效果更佳。

写笔记并不是说照着教材抄一遍就完事了，主要是笔记有三个优势，1是笔记梳理的思路更加精炼，会更加突出核心思想，比自己单纯看书要快也更能抓住重点，2是教材中有一些比较困难的地方，主要是涉及到理论证明的地方，我们会用自己的语言去进一步的诠释，辅助大家把一些证明跳步和背后隐含的内容挖出来，3是适当配点code增强实操的感受，理论配合实践相辅相成方能融会贯通。

我个人本科是control的背景，对optimal control和经典的数学优化的各种programming比较熟悉一点，对动态规划和强化学习自己也是初学者。开始更新这个笔记主要也是督促自己自学，输出倒逼输入，希望感兴趣的小伙伴关注支持。我会把书中的1-2节作为一篇笔记文章来组织，本篇文章对应书中的 1.1. Deterministic Dynamic Programming

1 离散时间动态系统（确定性问题）

离散时间动态系统形式如下：

$x_{k+1}=f_k(x_k,u_k) \quad (1.1)\\$ 其中 $k$ 是时间索引， $x_k$ 表示时间步 $k$ 系统的状态也被称为状态变量(state variable)， $u_k$ 表示时间步 $k$ 的控制量或者决策变量 (control variable or decision variable)，一般来说 $u_k$ 要满足一定的约束表示为 $u_k∈U_k(x_k)$ $f_k$ 是一个关于 $(x_k,u_k)$ 的函数，它描述了系统的动态特性， $N$ 是总的时间步数目，我们这里暂时只讨论 $N$ 是有限的情况。如果 $N$ 是无穷的话情况就会复杂很多，在我们不特殊强调的情况下都默认先考虑有限的情况。整个离散时间动态系统（确定性）如下图所示：关于离散时间动态系统（确定性）要注意两点： 1. 如果知道系统初始状态 $x_0$ ，系统动态特性 $f_k$ ，还有控制量序列 ${u_0,u_1,...u_k}$ ，就可以根据式（1.1）计算出 $1$ 到 $k+1$ 的状态变量 ${x_1,x_2,...x_{k+1}}$ ; 2. 虽然我们在之前为了方便起见会把 $k$ 定义为时间步或者时间索引，但是实际上 $k$ 的含义并不一定只能是时间。在上面的图1.1中用了stage $k$ 来表示实际上是更加准确的一种方式，只要是有先后顺序了一个动态过程就可以用多个stage来表示，例如把微分方程离散之后所构成的离散时间动态系统，例如组合优化问题中的序列决策，例如最短路问题中需要决定先走哪个节点再到哪个节点的顺序等等，例如也可以表示优化算法迭代到第 $k$ 步等等; 下面在离散时间动态系统的基础上我们引入 cost function，在动态系统的变化过程中我们总是有所期望的，例如燃烧燃料最小，例如车辆行驶距离最短，例如服务等待时间最小等等。这些我们统一采用 $g_k(x_k,u_k)$ 来表示在时间 $k$ 的 cost function，对于给定初始状态 $x_0$ 和控制序列 ${u_0,u_1,...u_{N−1}}$ ，可得总的cost function值 $J(x_0;u_0,...u_{N-1})=g_N(x_N)+\sum_{k=0}^{N-1}{g_k(x_k,u_k)}\\$

虽然这个总的cost function看似顺理成章就得到了，其实之所以能写成上面这样已经是隐含了一个重要的假设条件，就是每个时间步的 cost function 之间必须是 additive，从优化的角度来说就是优化问题是可分的。

如果不懂优化问题也没关系，简单来说就是 $g_k$ 要满足一些性质，如果取这样的话就不行了 $g_k=x_{k}x_{k−1}+x_{k−1}+u_k$ ，因为 $g_k$ 不但和 $x_k,u_k$ 有关还和 $x_{k−1}$ 有关，那么我们就不能把整体的 cost function 写成每个时刻的 cost function 相加的形式，即式（1.2）中的求和形式。

这里我们为什么要强调这个性质，因为在动态规划算法中最优性原理最核心的一步中就需要这个性质才能使得一切都成立，否则动态规划最基本的思想就不复存在了。

有式（1.2）可以定义出优化问题

$J\left( x_0 \right) =\underset{u_k\in U_k\left( x_k \right) ,k=0,...,N-1}{\min}J\left( x_0;u_0,...,u_{N-1} \right) \quad (1.3) \\$ 注意该优化问题是关于 $x_0$ 的函数实例1：图中最短路问题，如下图所示 ![](https://s3.bmp.ovh/imgs/2022/10/19/93e27275424296ef.png) 式中 $x_k$ 就表示在 stage $k$ 所处的节点， $u_k$ 表示在 stage $k$ 去到 stage $k+1$ 选择哪条边，同时初始状态和终止状态都是给定的， $g(x_k,u_k)$ 就可以定义为从 stage $k$ 到stage $k+1$ 经过的边的长度，易知总的cost就是要让经过的路径最短。这样我们就可以把一个最短路问题建模成一个离散时间动态系统的最优控制问题。那么对于任意一个权值非负的无环图2个节点之间的最短路问题都可以转化为一个离散时间动态系统的最优控制问题，关于这个的证明将在后边再详细介绍。 ### 2 动态规划算法我们先讨论动态规划的一个基本性质就是 Principle of optimality，然后给出动态规划算法的迭代表达式，最后提一点从动态规划到强化学习的一个直观解释。 #### 2.1 Principle of optimality 给定 $x_0$ 为初始状态，若 ${u_0^∗,...,u_{N−1}^∗}$ 是最优的控制序列，通过系统动态方程（1.1）可以得到相对应的最优状态序列 ${x_0^∗,...,x_{N−1}^∗}$ ，考虑如下的子问题，该子问题从时刻 $k$ 开始到 $N$ 结束，对于该子问题总的目标函数为 $\underset{u_k,...u_{N-1}}{\min}g_k\left( x_{k}^{*},u_k \right) +\sum_{m=k+1}^{N-1}{g_m\left( x_m,u_m \right)}+g_N\left( x_N \right) \\$

其中 $u_m\in U_m(x_m), m=k,...,N-1$ 。那么可知序列 ${u_k^∗,...,u_{N−1}^∗}$ 是上面所述子问题的最优解之一。

简单来说就是原问题的最优解拿出来一个子序列依然是子问题的最优解，当然要注意的是这个子问题不是随便取的，而是要从stage $k$ 到 $N$ 的子问题，也就是说终点stage一定要一样，起点可以随便选择只要不跑出范围就行。英文中就叫做 tail subproblem，如下图所示

这里只说一下这个定理的证明思路：如果 ${u_k^∗,...,u_{N−1}^∗}$ 不是子问题的最优解，那么该子问题至少还存在另外一个最优解 $\{{u}_k',...,{u}_{N-1}'\}$ ，那么返回来看原问题容易得到 $\{u_0^*,...,u_{k-1}^*,{u}_k',...,{u}_{N-1}'\}$ 会比原问题最优解 $\{{u}_0^*,...,{u}_{N-1}^*\}$ 还要好，这就产生了矛盾。关于这个问题的证明和直观解释知乎上也有很多这里就不详细再展开讨论了。

Principle of optimality 告诉我们当你要求解从stage 0 到 N，这么大的一个问题的时候可以先从小规模问题入手就是tail subproblem，因为tail subproblem的规模要比原问题要小，从而达到对问题分而治之的目的。刷过数据结构的童鞋对这个思想应该是非常熟悉的了。在做好了一系列铺垫之后就要正式提出我们的主角动态规划算法了。

2.2 动态规划算法求解确定性有限时间问题

再强调一下我们这里的动态规划算法是针对确定性有限时间问题的，带有随机性的会在下一节讲到，无限时间分析起来比较麻烦，将会放到最后来介绍。上一个小节我们讲了tail subproblem 那么所有的tail subproblem的最优值函数序列如下

$J^*_N(x_N),J^*_{N-1}(x_{N-1}),...,J^*_0(x_0) \\$

其定义如下所示：

$J_k^*\left( x_k \right) =\underset{u_k\in U_k\left( x_k \right) ,m=k,...,N-1}{\min}J\left( x_k;u_k,...,u_{N-1} \right) \quad (2.2) \\$ $J\left( x_k;u_k,...,u_{N-1} \right) = g_N(x_N)+\sum_{m=k}^{N-1}{g_m(x_m,u_m)} \quad (2.3) \\$

$J_k^∗(x_k)$ 表示从stage $k$ 开始到stage N结束一共包含 $N-k$ 个stage的tail subproblem的最优目标函数值。

由此给出确定性有限时间问题的动态规划算法如下

对于 $k=N$ 有

$J_{N}^{*}\left( x_N \right) =g_N\left( x_N \right) ,\,\,\,\,for\ all\ x_N \\$

对于 $k=0,...,N−1$ 有

$J_{k}^{*}\left( x_k \right) =\underset{u_k\in U_k\left( x_k \right)}{\min}\left[ g_k\left( x_k,u_k \right) +J_{k+1}^{*}\left( f_k\left( x_k,u_k \right) \right) \right] ,\,\,\,\,for\ all\ x_k \quad (2.5) \\$

下面我们来证明一下这个结论：

首先对于 $k=N$ 的情况是显然有 $J_N^∗(x_N)=g_N(x_N) ,\,\,\,\,for\ all\ x_N$ 成立

对于 $k=0,...,N−1$ 有

$J_{k}^{*}\left( x_k \right) =\underset{u_k\in U_k\left( x_k \right) ,m=k,...,N-1}{\min}\left[ g_N\left( x_N \right) +\sum_{m=k}^{N-1}{g_m\left( x_m,u_m \right)} \right] \quad (2.6) \\$ $= \underset{u_k\in U_k\left( x_k \right)}{\min}\left[ g_k\left( x_k,u_k \right) +\underset{u_m\in U_m\left( x_m \right) ,m=k+1,...,N-1}{\min}\left[ g_N\left( x_N \right) +\sum_{m=k+1}^{N-1}{g_m\left( x_m,u_m \right)} \right] \right] \quad (2.7) \\$ $=\underset{u_k\in U_k\left( x_k \right)}{\min}\left[ g_k\left( x_k,u_k \right) +J_{k+1}^{*}\left( f_k\left( x_k,u_k \right) \right) \right] \quad (2.8) \\$

从（2.6）-（2.8）在教科书上就直接过来了，我们需要注意的是式（2.7）是 min 套 min，可不要看成分别min了，里边那个min的问题就是对应到tail problem，而且这个tail problem的初始状态是 xk ，而 xk 还被嵌套在外边一层的min中，根据前面的Principle of optimality就可以得到从（2.6）到（2.7）。从（2.7）到（2.8）就是把定义套了一下而已。

分析式（2.8）可知，该优化问题的目标函数由两部分构成，第一部分 $g_k(x_k,u_k)$ 叫做immediately cost，第二部分 $J_{k+1}^∗(f_k(x_k,u_k))$ 代表未来的花费，被叫做 cost-to-go function。如果说我们在做决策的时候每次只考虑 immediately cost，而不考虑未来的cost的话那就意味着这是一种贪婪的策略。可以清楚的看到 $J_k^∗$ 是一个关于 $x_k$ 的函数，如果 $x_k$ 是离散的话，那我们在第 $k$ 步就需要把所有可能取到的 $x_{k+1}$ 穷举出来计算出与之相对的 $J_k^∗$ 。在这里不难看出这个计算量是非常之大的，对于小规模问题还可以，而对于大规模问题则难以直接套用进来。那么在下一小节将初步探讨一下如何通过对 $J_k^∗$ 的近似来降低计算量的问题。

在得到所有的 $J_k^∗$ 之后，我们对如下问题求解就可得到最优的控制序列 ${u_0^∗,u_1^∗,⋯,u_{N−1}^∗}$

$u_{0}^{*}\in \text{argmin} \left[ g_0\left( x_0,u_0 \right) +J_{1}^{*}\left( f_0\left( x_0,u_0 \right) \right) \right] \quad (2.9) \\$

由此易知

$x_{1}^{*}=f_0\left( x_0,u_{0}^{*} \right) \quad (2.10) \\$

同理对于 $k=1,2,...,N−1$

$u_{k}^{*}\in \text{argmin} \left[ g_k\left( x_k,u_k \right) +J_{k+1}^{*}\left( f_k\left( x_k,u_k \right) \right) \right] \quad (2.11) \\$

由此易知 $x_{k+1}^∗=f_k(x_k,u_k^∗) \quad (2.12)\\$

2.3 Value Space的近似

在强化学习中我们也经常把 cost-to-go function $J_k^∗$ 称之为 value function，尤其在强化学习领域中我们一般更习惯称之为 value function，之后我们会不加区分的使用 cost-to-go function 和 value function 它们的含义是一样的。

接上文动态规划的最大的问题在于 $J_k^∗$ 计算量太大了，在大规模问题上我们要想办法降低计算量。在当前时刻做决策我们既要考虑immediately cost: $g_k(x_k,u_k)$ ，也要考虑cost-to-go function: $J_{k+1}^∗(f_k(x_k,u_k))$ ，但是从直观的角度来看，对于未来的考虑可以不必那么精确。例如今天你做一件事情对明天会产生显著的影响但是对10年后的影响就比较小，基于这样的一个直观感受在一定程度上可以对cost-to-go function 进行近似。也就是用 $\tilde{J}_k$ 近似 $J_k^∗$ ，那么我们就可以将式（2.9）-（2.12）替换成如下形式：

$\tilde{u}_0\in \arg\min \left[ g_0\left( x_0,u_0 \right) +\tilde{J}_{1}^{*}\left( f_0\left( x_0,u_0 \right) \right) \right] \quad (2.13) \\$

在上式中我们采用 $\tilde{J}_k$ 近似 $J_k^∗$ ，这就是 Approximation Dynamic Programming 的一种形式。也是我们后边要讲到的 Value-based Reinforcement Learning 的基本思路。至于怎么来得到近似后的 $\tilde{J}_k$ 那么这其实就是一个监督学习的问题可以采用神经网络来进行近似。

由此易知 $\tilde{x}_1=f_0(x_0,\tilde{u}_0) \quad (2.14)$

同理对于 $k=1,2,...,N−1$

$\tilde{u}_k\in \text{argmin} \left[ g_k\left( \tilde{x}_k,u_k \right) +\tilde{J}_{k+1}^{*}\left( f_k\left(\widetilde {x}_k,u_k \right) \right) \right] \quad (2.15) \\$