【强化学习与最优控制】笔记（六）强化学习中的Decomposition

上一期笔记，忘记的小伙伴可以复习一下：

王源：【强化学习与最优控制】笔记（五）强化学习中值空间近似与策略空间近似概述

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

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

因为电子版的内容是一个草稿版本，其内容不是很强，所以也推荐大家来购买纸质版。本笔记对应教材中2.3节的内容，如需购买教材的童鞋请点击：

上一期的回顾：王源：【强化学习与最优控制】笔记（五）强化学习中值空间近似与策略空间近似概述

上一期我们笼统的讲了强化学习中值空间近似与策略空间近似。本次我们集中讲解值空间近似中一种常用的思路就是 Problem approximation (优化问题近似)。

我们这里主要介绍两种 Problem approximation (优化问题近似)的方法

1 Decomposition

(1) Optimization of One Subsystem at a Time

这个思想也非常简单了就是在每个stage里只是优化一个子问题，而其它的部分我们都不变。例如在stage k 我们需要决策的是 $u_k=(u^1_k,u^2_k,...,u^n_k)$ ，很显然对于复杂的问题而言 $u_k$ 是一个向量有多个元素构成其维数为 $n$ 。那么我们自然可以考虑在 stage k 的时候只选取 $u_k$ 的第一个分量 $u^1_k$ 作为变量，而把 $u^2_k,...,u^n_k$ 都视为常数。这样的话相当于我们在stage k 的时候仅仅做的是一个 subsytem 的优化问题，显然这可以降低计算量，尤其在 $n$ 比较的的时候。那么在 stage k+1 的时候我们又可以选择 $u^2_k$ 作为我们的决策变量，而把其它的部分都视为常数。以此类推，这样随着stage往前的推进，我们就可以更新不同的 $u_k$ 的分量。

这个思想其实类似于优化方法中的坐标下降法（coordinate descent）。坐标下降法的思想如下所示，对于如下优化问题

$\underset{x\in R^N}{\min}f\left( x \right)$ （1.1）

我们每次仅仅优化决策变量 $x$ 的一个分量，而保持其它分量不变，即

$x_{0}^{\left( k \right)}=\underset{x_0}{arg\min}f\left( x_0,x_{1}^{\left( k-1 \right)},x_{2}^{\left( k-1 \right)},...,x_{N}^{\left( k-1 \right)} \right)$ （1.2）

$x_{1}^{\left( k+1 \right)}=\underset{x_1}{arg\min}f\left( x_{0}^{\left( k \right)},x_1,x_{2}^{\left( k-1 \right)},...,x_{N}^{\left( k-1 \right)} \right)$ （1.3）

$x_{2}^{\left( k+1 \right)}=\underset{x_2}{arg\min}f\left( x_{0}^{\left( k \right)},x_{1}^{\left( k-1 \right)},x_2,...,x_{N}^{\left( k-1 \right)} \right)$ （1.4）

......

其中 $k$ 表示迭代次数， $x^k_i$ 表示第k次迭代时 $x$ 的第 $i$ 个分量。

(2) Constraint Decoupling by Lagrangian Relaxation

这里作为补充材料先简单介绍一下Lagrangian Relaxation的基本思想：

有如下优化问题

$\underset{x,y}{\min}c^Tx+d^Ty$

$A_1x=b_1$ (A1)

$A_2y=b_2$ (A2)

$A_3x+A_4y=b_3$ (A3)

决策变量有两大类 $x,y\in D$ ,约束（A1）和约束（A2）分别只和 $x,y$ 有关，而约束（A3）是一个linked/coupling constraints，它把 $x,y$ 两类变量耦合在了一起。

若采用Lagrangian relaxation 把约束（A3）松弛到目标函数得到松弛问题：

$\underset{x,y}{\min}c^Tx+d^Ty+\lambda^T(A_3x+A_4y-b_3)$

$A_1x=b_1$ (B1)

$A_2y=b_2$ (B2)

此时由于linked/coupling constraints 被处理掉了，因此在松弛问题中决策变量 $x,y$ 实现了解耦可以分为两个子问题分别对 $x,y$ 求优化

子问题1：

$\underset{x}{\min}c^Tx+\lambda^TA_3x$

$A_1x=b_1$

子问题2：

$\underset{y}{\min}d^Ty+\lambda^TA_4y$

$A_2y=b_2$

为了后边解释方便我这边直接列出其对偶问题：

对偶函数： $q\left( \lambda \right) =\underset{A_1x=b_1,A_2y=b_2}{\min}c^Tx+d^Ty+\lambda ^T\left( A_3x+A_4y-b_3 \right)$

对偶问题： $\underset{\lambda}{\max}q\left( \lambda \right)$

思考：为什么要用拉格朗日松弛？

1 拉格朗日松弛之后得到的问题下界要大于等于直接将0,1整数变量松弛为[0,1]连续变量的下界。一言以蔽之就是拉格朗松弛得到的解的质量要好。

2 采用拉格朗日松弛之后我们会得到拉格朗日乘子，拉格朗日乘子反应了对偶的信息，那么用这个这个对偶信息可以做很多很多事情（此处省略一万字）。

3 如果问题具有linked/coupling constraints那么采用拉格朗日松弛之后可以使得问题被分解，进而大大简化原问题。

到这里我们回到正题：如何把Lagrangian relaxation运用到我们对cost-to go function的近似中呢？我们知道一个动态系统经常有可能是由若干个子系统组成的，如下所示：

$u_k=\left( u_{k}^{1},...,u_{k}^{n} \right) \in U$ （1.5）

$x_{k+1}^{i}=f^i\left( x_{k}^{i},u_{k}^{i},w_{k}^{i} \right) ,\,\,\,\,i=1,...,n,\,\,k=0,1,...,$ （1.6）

其中 $x_k^i$ 表示在时刻 $k$ 第 $i$ 个子系统的状态， $u_k^i$ 表示在时刻 $k$ 第 $i$ 个子系统的控制量， $f^i$ 表示第 $i$ 个子系统的动态方程， $w_k^i$ 表示在时刻 $k$ 第 $i$ 个子系统的噪音。同样的时刻 $k$ 第 $i$ 个子系统的cost 可以表示为 $g^i(x^i_k,u^i_k,w^i_k)$

原来的优化问题为：

$J_{k}^{*}\left( x_k \right) = \underset{u_m,u_{m+1},...u_{N-1}}{\min}g_N\left( x_N \right) +\sum_{m=k}^{N-1}{g_m\left( x_m,u_m \right)}$ （1.7）

现在拆分成n个子系统后可以将上面的优化问题等价改写为：

$J_{k}^{*}\left( x_k \right) = \underset{u_m,u_{m+1},...u_{N-1}}{\min}g_N\left( x_N \right) +\sum_{m=k}^{N-1}{\sum_{i=1}^n{g_{m}^{i}\left( x_{m}^{i},u_{m}^{i} \right)}}$ （1.8）

如果说各个子系统之间没有互相耦合的约束，那么我们可以分别对每个子系统进行优化求解，这样可以大大降低计算量，但实际上这种假设过于理想，往往各个子系统之间存在着一些耦合约束，例如如下的约束形式就是一种耦合约束：

$J_{k}^{*}\left( x_k \right) = \underset{u_m,u_{m+1},...u_{N-1}}{\min}g_N\left( x_N \right) +\sum_{m=k}^{N-1}{\sum_{i=1}^n{g_{m}^{i}\left( x_{m}^{i},u_{m}^{i} \right)}} \\ s.t. \,\,\sum_{i=1}^n{c^iu_{m}^{i}}\le b,\,\,\,\, \forall k=k,k+1,...,N-1$ （1.9）

上面的约束和n个子系统的 $u^i_k$ 都有关，也就是说当我们调整其中任意一个 $u^i_m$ 的时候我们都需要看一下其它子系统的 $u_m^i$ 的值才行，否则就有可能导致该约束无法保证。

那么我们同样的采用 Lagrangian Relaxation 的方法来处理约束（1.9）这样的linked/coupling constraints约束，我们可以得到拉格朗日项为：

$\sum_{m=k}^{N-1}{\sum_{i=1}^n \lambda^i_m\left( {c^iu_{m}^{i}}-b \right) }$ （1.10）

原书中对于拉格朗日项的写法和我这里的写法略有不同，我这里是更加精细的一种写法，书中的写法是一种比较简单粗暴的写法，具体可见（page 75 式 2.16）。接下来我们将（1.10）拉格朗日项加入到（1.9）中可得

$\tilde{J}_{k}^{*}\left( x_k \right) =\underset{}{\min} g_N(x_N) +\sum_{m=k}^{N-1}{\sum_{i=1}^n{g_{m}^{i}\left( x_{m}^{i},u_{m}^{i} \right)}} + \sum_{m=k}^{N-1}{\sum_{i=1}^n \lambda^i_m\left( {c^iu_{m}^{i}}-b \right) }$ （1.11）

此时由于我们对耦合约束进行了处理，目标函数变成了可分的形式，我们就可以将上面的优化问题分解为n个子优化问题：

$\tilde{J}^{i}_{k}\left( x_k^i, \lambda^i_k \right) =\underset{}{\min} g_N(x_N) +\sum_{m=k}^{N-1}{{g_{m}^{i}\left( x_{m}^{i},u_{m}^{i} \right)}} + \sum_{m=k}^{N-1}{\lambda^i_m\left( {c^iu_{m}^{i}}-b \right) } ,\,\,\,\,\forall i=1,2,...,n$ （1.12）

实际上我们也可以认为该问题的等效cost为： $g^i\left( x_{m}^{i},u_{m}^{i} \right) +\lambda _{m}^{i}c^iu_{m}^{i}$

需要注意的是从式（1.9）通过Lagrangian Relaxation转化到式（1.11）这一步并不能保证是完全等价的，一般来说对于凸优化问题而言才能保证这么转化是完全等价的，而对于非凸优化问题而言就不容易保证这两者是完全等价的。所以在式（1.11）中我们采用了 $\tilde{J}_{k}^{*}$ 来表示是一种近似的Value function。到这里就完全回应了我们采用 Lagrangian Relaxation 来做 Value function的近似的主题。

更多关于 Lagrangian Relaxation 可参考

王源：拉格朗日松弛求解整数规划浅析（附Python代码实例）

2 Certainty Equivalent Control

Certainty Equivalent Control 的基本思想是将随机变量转化为确定变量，这样我们就可以求解确定性优化问题而不必求解随机优化问题，在一定程度上可以达到优化问题的简化的目的，如下所示是N-k的stage的随机优化问题

$\min E\left[ g_N\left( x_N \right) +\sum_{m=k}^{N-1}{g_m\left( x_m,u_m,w_m \right)} \right]$ (2.1)

其中的随机变量是 $w_m$ ，最直观的一个想法就是我们可以用随机变量的期望来代替随机变量本身，可以达到简化的目的

$\tilde{w}_m(x_m,u_m)=E\{w_m|x_m,u_m\}$ (2.2)

用上式替换（2.1）中的随机变量 $w_m$ 可得：

$\min \left[ g_N\left( x_N \right) +\sum_{m=k}^{N-1}{g_m\left( x_m,u_m,\tilde{w_m}(x_m,u_m) \right)} \right]$ (2.3)

这样就将随机优化的问题转化为了确定性优化的问题，可以降低计算量。

这里值得一提的是对于 $\tilde{w}_k(x_k,u_k)$ 的取法不止一种，可以采用期望，可以采用极大似然估计，也可以采用类似于卡尔曼滤波的方法等等，这块其实就是比较有学问的地方了，可以根据系统的不同特性进行设计的地方。

Certainty Equivalent Control with Heuristics 就不多说了和前面将过的用启发式方法来近似 cost-to go function(value function)的内容基本一致。

Partial Certainty Equivalent Control - Partially Observed States 其实是一个很好的话题，不过教材里的例子个人感觉不是特别好，所以这里就不展开讲了，比较感兴趣的童鞋可以关注一些关于卡尔曼滤波的内容，其实也都是可以非常好的能和强化学习的内容结合在一起的，Bertsekas在 page 81下面的注释部分也提到了卡尔曼滤波。

3 对强化学习求解组合优化问题的一点碎碎念

我个人感觉强化学习和传统的数学优化有很多可以结合的点进去，例如咱们本次笔记讲的 Optimization of One Subsystem at a Time 和 Lagrangian Relaxation 都是传统数学优化的基本思路和方法，这些基本思路和方法依然可以在强化学习的框架下发挥作用。

纯粹的Learning（机器学习方法）的方法和纯粹的Search（传统数学优化解整数规划/组合优化）的方法从理论发展来看目前都快走到头了，我个人觉得未来两者之间互相结合是一个不错的道路，而强化学习这个框架恰恰可以把这两者非常有机的融合在一起。

下一期笔记：

王源：【强化学习与最优控制】笔记（七） Rollout 与 Policy Improvement

【强化学习与最优控制】笔记（六）强化学习中的Decomposition

@王源

1 Decomposition

2 Certainty Equivalent Control

3 对强化学习求解组合优化问题的一点碎碎念

专栏：运筹学与控制论