【强化学习与最优控制】笔记（十）无限时间动态规划和随机最短路问题

上一期笔记，忘记的童鞋可以复习一下：

王源：【强化学习与最优控制】笔记（九）值函数，Q函数和策略空间的近似

需要教材电子版的同学可以从如下链接中获取电子版的草稿版本：

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

本笔记对应教材中第4章4.1-4.3的内容。由于电子版的内容不是很全，所以也推荐大家来购买纸质版，需购买教材的童鞋请点击：

从本章开始我们研究的问题从有限时间到无限时间问题。

1 Overview

无限时间问题（Infinite horizon）和有限时间问题（finite horizon）主要的区别有2点：

1 无限时间问题考虑的是无穷多 stage 的问题。

2 无限时间问题里的系统是稳态的，也就是说动态系统方程，每个阶段的 cost 还有噪音的分布等并不会随着时间变化。

对 Infinite 问题的分析要比 finite 问题困难一点，因为涉及到无限就需要分析收敛性，需要极限等数学工具。另一方面 Infinite 问题很多时候会得到比 finite 问题更加漂亮的结论。需要注意的是绝大多数书中内容是对有限数量state和有限数量action的分析。

Infinite 问题中的 cost function:

$J_{\pi}\left( x_0 \right) =\underset{N\rightarrow \infty}{\lim}\underset{w_0,w_1,...}{E}\left\{ \sum_{k=0}^{N-1}{\alpha^k g\left( x_k,\mu _k\left( x_k \right) ,w_k \right)} \right\}$ (1.1)

其中 $x_0$ 表示初始状态， $\pi =\left\{ \mu _0,\mu _1,... \right\}$ 表示 policy， $\alpha \in [0,1]$ 表示系数。

我们不妨对比一下 finite 问题中的 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)}$ (1.2)

Infinite 问题和 finite 问题的 cost function 的区别在于：1 infinite 是有极限运算的，而 finite 是有限项求和；2 infinite 问题中多了 $\alpha$ 系数，这个系数也被称之为 discount 系数。第一点很好理解，第二点多了一个 $\alpha$ 系数，一般情况下我们会让 $0<\alpha <1$ ，它有两层含义：1是对于距离我当前时间步 $k$ 越远的时刻，那么其对整体 cost 的值的影响会减小，所以就通过这个系数来体现，因为随着 $k$ 增大 $\alpha^k$ 会变小。2是在收敛性证明方面有了这个 $\alpha$ 系数才会让整个 cost 的值不会趋于无穷，也就是无需额外条件就可以保证了收敛性。

在本章会研究两类问题：一类是 stochastic shortest path problem ，一类是 discounted problem。在理论上可以证明这两类问题实际上是等价的。

依据DP算法给出 Infinite 问题不含 discount 系数的递推表达式为：

$J_{k+1}\left( x \right) =\underset{u\in U\left( x \right)}{\min}\underset{w}{E}\left\{ g\left( x,u,w \right) +J_k\left( f\left( x,u,w \right) \right) \right\} ,\,\,\,\,k=0,1,...,$ (1.3)

和 finite 问题不同在于我们的 stage 有无穷多个，所以大致我们可以推测出如下的结论：

(a) $J^*\left( x \right) =\underset{N\rightarrow \infty}{\lim}J_N\left( x \right)$ (1.4)

其中 $J^*\left( x \right)$ 是最优的 Value function 的值

(b) $J^*\left( x \right) =\underset{u\in U\left( x \right)}{\min}\underset{w}{E}\left\{ g\left( x,u,w \right) +J^*\left( x,u,w\right) \right\} ,\,\,\,\,k=0,1,...,$ (1.5)

对式（3）两边取极限，可以得到上式。上式是对任意状态都满足的，所以每有一个状态就有一个与之对应的方程。这个方程也被称之为 Bellman's equation

(c) 若 $\mu(x)$ 是式（5）的最优解，同时最优解的 policy $\{\mu,\mu,...,\}$ 被称之为 stationary。值得注意的是这里最优的policy和初始状态是没有任何关系的，这点直观上也很好去理解就是对于 infinite 问题而言极限的前有限项都不会影响最终极限收敛的值。这个性质实际上是 infinite比较好也比较重要的性质。

2 Stochastic shortest path problems

本小节我们先考虑没有discount系数的问题，下一小节再讨论含 discount 系数的问题。

如下图所示就是一个 Stochastic shortest path problem （SSP）

其中 $p_{ij}(u)$ 表示从状态 $i$ 转移到状态 $j$ 的概率。可以看到图中有一个终止状态点，当系统进入这个状态之后就会停止其 stage cost 为 0，用公式表达为：

$p_{tt}\left( u \right) =1,\,\,\,\,g\left( t,u,u \right) =0,\ for\ all\ u\in U\left( t \right)$ (2.1)

根据式（1.5）可以写出 SSP 的 Bellman's equation

$J^*\left( i \right) =\underset{u\in U\left( i \right)}{\min}\left[ p_{it}\left( u \right) g\left( i,u,t \right) +\sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +J^*\left( j \right) \right)} \right]$ (2.2)

上式实际上就是把式（1.5）中的期望值按照定义写出来之后的得到的。

根据式（1.3）可以得到 Value function 的迭代公式

$J_{k+1}\left( i \right) =\underset{u\in U\left( i \right)}{\min}\left[ p_{it}\left( u \right) g\left( i,u,t \right) +\sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +J_k\left( j \right) \right)} \right]$ (2.3)

同理，上式实际上就是把式（1.3）中的期望值按照定义写出来之后的得到的。

式（2.2）由三项构成：

(a） $p_{it}\left( u \right) g\left( i,u,t \right)$ 从状态 $i$ 到终止状态 $t$ 的 cost的期望

(b) $\sum_{j=1}^n{p_{ij}\left( u \right) g\left( i,u,j \right)}$ 从状态 $i$ 到非终止状态 $j$ 的 cost的期望

之前我们讨论过的确定性的最短路的问题可以看做是SSP问题的一种特殊情况，即令 $p_{ij}(u)=1$ 那么 SSP 问题就等价为一个确定性的最短路问题了。

在SSP中一般会有如下假设：

存在一个整数 $m$ 对于任意 policy 和任意初始状态，使得经过 $m$ 个stage到达终止状态 $t$ 的概率严格大于0，用如下式表示：

$\rho _{\pi}=\underset{i=1,...,n}{\max}P\left\{ x_m\ne t|x_0=i,\pi \right\} <1$ (2.4)

对于所有初始状态和policy 不到达终止状态 $t$ 的概率为：

$\rho =\underset{\pi}{\max}\rho _{\pi}<1$ (2.5)

基于以上假设我们得到一个重要的推论：随着stage的变大，不到达终止状态的概率将会收敛到 0。

证明：由定义易知：

$P\left\{ x_{2m}\ne t|x_0=i,\pi \right\} =P\left\{ x_{2m}\ne t| x_{m}=t,x_0=i,\pi \right\} P\{x_m = t |x_0=i, \pi \}+ \\ P\left\{ x_{2m}\ne t| x_{m}\ne t,x_0=i,\pi \right\}P\{x_m \ne t |x_0=i, \pi \}$ (2.6)

等式右端第一项是等于0的，因为 $x_m=t$ 表明在stage $t$ 的时候已经到达终止状态了，则在 $m$ 以后的状态都停留在终止状态，因此是不会出现 $x_{2m} \ne t$ 的情况的。

式（2.6）去掉右边第一项由此可得：

$P\left\{ x_{2m}\ne t|x_0=i,\pi \right\} =P\left\{ x_{2m}\ne t| x_{m}\ne t,x_0=i,\pi \right\}P\{x_m \ne t |x_0=i, \pi \}$ （2.7）

由式（2.5）和（2.7）易知：

$P\left\{ x_{2m}\ne t|x_0=i,\pi \right\} =P\left\{ x_{2m}\ne t| x_{m}\ne t,x_0=i,\pi \right\}P\{x_m \ne t |x_0=i, \pi \} \leq \rho^2$ （2.8）

由归纳法进一步可得：

$P\left\{ x_{km}\ne t|x_0=i,\pi \right\} \leq \rho^k, i=1,2,..,n$ （2.9）

所有随着 $k$ 增大，不到达终止状态的概率将会收敛到 0。

QED.

基于以上条件，我们可以得到SSP问题的2个性质（教材上有4个性质，我这里只列出前2个，因为后2个很简单）：

性质1：设最优的cost为 $J^*(i)$ 对所有的状态 $i$ 都是有界的。对于任意的初始值 $J_0(1),...,J_0(n)$ ，通过如下值迭代算法

产生的数列 $\{J_k(i)\}$ 收敛到 $J^*(i)$ 对于所有的 $i=1,...,n$

性质2：最优值函数 $J^*=\left( J^*\left( 1 \right) ,...,J^*\left( n \right) \right)$ 是 Bellman's equation

关于上面两个性质的证明在教材212页有详细过程，我就不照抄过来了。在证明中最核心的思想就是压缩映射，理解了这一点就非常容易理解上面2个性质了。如果我们把式（2.10）DP算法的迭代操作看做是一个映射 $T$ 的话，每次从stage k到k+1的计算相当于是对 Value function 做映射 $T$ 的操作。

$(TJ)(i) =\underset{u\in U\left( i \right)}{\min}\left[ p_{it}\left( u \right) g\left( i,u,t \right) +\sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +J\left( j \right) \right)} \right]$ (2.11)

而这个映射 $T$ 实际上是一个压缩映射（压缩映射的概念来自泛函分析在收敛性证明解存在性证明中经常会用到），大家只需要知道压缩映射有如下性质：

$\lVert TJ-TJ' \rVert \le \rho \lVert J-J' \rVert$ (2.12)

这里的 norm 是 infinity norm

由此可以推出：

$\lVert J_k-J^* \rVert \le \rho^k \lVert J_0-J^* \rVert$ (2.13)

$J_k$ 就表示经过 $k$ 次压缩映射 $T$ 之后的 Value function

3 Discounted problem

相似的，可以写出带有discount系数的Bellman's equation：

$J^*\left( i \right) =\underset{u\in U\left( i \right)}{\min}\left[ \sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +\alpha J^*\left( j \right) \right)} \right]$ (3.1)

相似的，可以写出带有discount系数的DP迭代公式：

$J_{k+1}\left( i \right) =\underset{u\in U\left( i \right)}{\min}\left[ \sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +\alpha J_k\left( j \right) \right)} \right]$ (3.2)

对比一下没有discount系数的SSP问题式（2.2）（2.3）我们可以发现上式中除了在Value function 上多加了一个 discount 系数 $\alpha$ 之外还去掉了终止状态那一项。

实际上通过如下图所示就可以得到 discount 问题和没有discount问题的等价转化

通过上图不难看出discount的意义相当于是加了一个cost为0的终止状态，并且其他状态到终止状态的概率为 $1-\alpha$

那么有了这个等价转化，上面关于没有discount的性质和结论也都适用于带有discount的问题。在此就不再赘述了。

王源：【强化学习与最优控制】笔记（十一）无限时间动态规划分布式值迭代和策略迭代

【强化学习与最优控制】笔记（十）无限时间动态规划和随机最短路问题

@王源

1 Overview

2 Stochastic shortest path problems

3 Discounted problem

专栏：运筹学与控制论