该书由清华大学李升波教授撰写的，主要面向工业控制领域的研究者和工程师，曾获得2024年度Springer中国新发展奖（China New Development Awards）。全书按照原理剖析、主流算法、典型示例的架构，系统地介绍了用于动态系统决策与控制的强化学习方法。全书共分为11章，内容涵盖了强化学习的基本概念、蒙特卡洛法、时序差分法、动态规划法、函数近似法、策略梯度法、近似动态规划、状态约束的处理和深度强化学习等知识点。书籍及源代码下载网站：书籍及代码链接点这里。

另外，由于本部分篇幅较长，因此分成三篇博客发表。其它博客的地址参考我的系列博客的地址汇总。

书籍链接：Reinforcement Learning for Sequential Decision and Optimal Control

本篇博客对应于原书的第九章，主要讲述了带有约束的强化学习。在实际的场景中，我们往往会遇到很多约束条件，包括对于输入的约束和对于状态的约束。对于输入的约束相对而言比较容易处理，而更困难的是对于状态的约束。主要有三种方法来处理状态约束：(1) 使用罚函数来惩罚打破约束的行为；(2) 使用基于对偶理论的拉格朗日乘子法来确定原问题的下界；(3) 使用feasible descent direction方法来找到一个既满足约束又能使目标函数下降的方向。

可以看出，处理带约束的强化学习问题与static optimization问题是类似的，但是前者因为带有约束而产生了保持每步学得的策略的递归可行性的难题。递归可行性被破坏通常是由于过于严格的状态约束。另一个困难是要在学得策略的同时确定可行域，而这两个问题是紧密耦合在一起的。因此本章中提出了一种新的学习架构——Actor-Critic-Scenery（ACS）架构，其中的Actor和Critic作用不变，而Scenery则负责确定可行域。

那么，对于这种带有hard state constraints的强化学习问题，应该在哪里训练呢？有两种常用的方法：(1) 先offline的在仿真环境中训练，然后再作为一个最优控制器部署在真实环境中；(2) 直接在真实环境中训练并部署。

9.1 处理动作约束的方法

总的来说，有两种方法可以来处理动作约束：

• saturated policy function：saturation函数用于将一个未加限制的策略函数的输出约束到一定范围内。
• penalized utility function：向utility function中加入一个惩罚项，用于惩罚超出约束范围的动作。外点罚函数和内点罚函数都可以用来实现上述功能。

9.1.1 Saturated Policy Function

什么是saturation函数呢？其实，举个例子就知道了。一个在深度学习中使用的很广泛的激活函数Sigmoid函数就是一个saturation函数。其函数图像如下所示：

从上述图像也可以看出为什么我们把这类函数称为saturation函数了。因为在自变量趋于$+\infty$或$-\infty$时，函数值会趋近于一个常数而不会发散。

我们通常应用saturation函数的方式如下：
$$u=\varphi (\pi (x;\theta ))$$ 这里的$\pi (x;\theta )$是我们原始的无限制的策略函数，而$\varphi$就是saturation函数。注意，这里的saturation函数是一个逐元素的函数，也就是说，它把输入的向量$\mathbf{x}$的每一个元素都约束到一个范围内。

下面，我们来看看一些常见的saturation函数：

• Sigmoid函数：
  $$\varphi (z)=\frac{1}{1+\exp (-z)}$$
• Tanh函数（双曲正切函数）：
  $$\varphi (z)=\tanh (z)=\frac{e^z-e^{-z}}{e^z+e^{-z}}$$
• 反正切函数：
  $$\varphi (z)=\arctan (z)$$
• Softsign函数：
  $$\varphi (z)=\frac{z}{1+|z|}$$

加上saturation函数之后，我们需要使用链式法则来计算梯度：
$$\frac{\partial u}{\partial \theta }=\frac{\partial \varphi (\pi )}{\partial \pi }\cdot \frac{\partial \pi }{\partial \theta }$$

Saturation函数的上述使用的一个典型例子就是在神经网络中的激活函数。这样就可以把输出压缩到一个有限的范围中（比如要输出一个概率值的时候）。但是，这样的saturation函数有一个缺点，就是在自变量的值很大或者很小的时候会出现梯度接近于0的现象，这样趋近于0的梯度再加上网络层数一深，就会导致梯度消失的问题。使用以0为中心的激活函数（比如tanH）可以缓解这个问题。

9.1.2 Penalized Utility Function

罚函数（penalty function）是一种广泛使用的可以把有约束问题转化为无约束问题的方法。罚函数主要分为两大类：外点罚函数和内点罚函数。下面分别介绍。

• 外点罚函数：
  • 特点：惩罚项只在输出的动作违反约束的时候才会生效。
  • 得到的策略是否一定满足约束，又是否一定最优：通常不是，会有一点小的违反约束。这样我们得到的输出并不能严格的遵守约束，适合那些允许轻微违反约束的问题。
  • 对于初始点有无要求：无
• 内点罚函数：
  • 特点：当输出的动作在接近约束边界（此时还未违反约束）时会趋向于无穷大。
  • 得到的策略是否一定满足约束，又是否一定最优：一定满足约束，但通常会比真正的有约束最优策略略差一点。
  • 对于初始点有无要求：有，需要在可行域内。

下面我们来介绍一下一种可以用于RL的内点罚函数法：在utility function中加入一个惩罚项：
$$l_{\mathrm{mod}}(x,u)=l(x,u)+\rho \cdot \phi (u)$$ 这里的$\phi (u)$是一种给内点罚函数，而$\rho$是一个惩罚系数。这里，我们给出$\phi (u)$的一个具体实例（这个例子可以把saturation函数和内点罚函数联系起来）：
$$\phi (u)={\int }_0^u\left({\varphi }^{-1}(v)-{\rho }^{-1}\frac{\partial l(x,v)}{\partial v}\right)\mathrm{d}v$$ 这里的$\varphi$是一个element-wise的saturation函数，把输入从$(-\infty ,+\infty )$映射到$[-1,1]$。${\varphi }^{-1}$是$\varphi$的反函数，因此它能把$[-1,1]$映射回$(-\infty ,+\infty )$。这样定义的$\phi (u)$在输入的动作$u$趋于边界1或者-1（即马上就要违反约束的时候），就会趋向于无穷大。接下来我们来推导最优的策略。

首先，根据稳态时的最优性条件，我们有：
$$\frac{\partial V^{\ast }(x)}{\partial u}=0,\mathrm{when}u=u^{\ast }$$ 那么，再结合引入的惩罚项的Bellman方程：
V ∗ ( x ) = min ⁡ u { l m o d ( x , u ) + V ∗ ( x ′ ) } V^{*}(x)=\min_{u}\{l_{\mathrm{mod}}(x,u)+V^{*}(x')\} V∗(x)=umin​{lmod​(x,u)+V∗(x′)} 那么，我们有：
$$\begin{array}{rl}\frac{\partial (l_{\mathrm{mod}}+V^{\ast }(x^{\prime }))}{\partial u}& =\frac{\partial (l(x,u)+\rho \cdot ({\int }_0^u\left({\varphi }^{-1}(v)-{\rho }^{-1}\frac{\partial l(x,v)}{\partial v}\right)\mathrm{d}v)+V^{\ast }(x^{\prime }))}{\partial u}\\ & =\frac{\partial l(x,u)}{\partial u}+\rho \cdot \left({\varphi }^{-1}(u)-{\rho }^{-1}\frac{\partial l(x,u)}{\partial u}\right)+\frac{\partial x^{\prime }}{\partial u}\frac{\partial V^{\ast }(x^{\prime })}{\partial x^{\prime }}\\ & =\rho {\varphi }^{-1}(u)+\frac{\partial f^{\mathrm{T}}}{\partial u}\frac{\partial V^{\ast }(x^{\prime })}{\partial x^{\prime }}\\ & =0\end{array}$$ 那么我们可以解得：
$$u^{\ast }=\varphi \left(-\frac{1}{\rho }\frac{\partial f^{\mathrm{T}}}{\partial u}\frac{\partial V^{\ast }(x^{\prime })}{\partial x^{\prime }}\right).$$ 可以看出，我们最终输出的策略被saturation函数约束在了$[-1,1]$之间。在这个例子中，我们将内点罚函数和saturation函数联系起来，从内点罚函数的推导入手，最后得到的最优策略的形式却是一个saturation函数。

9.2 状态约束和可行性的关系

本节我们先来讨论一下状态约束和可行性的关系，至于具体怎么在RL中处理状态约束，我们将会在下面几节中详细介绍。

与我们刚才说过的对于动作的约束相比，对于状态的约束之所以更加难以处理是因为它与不可行现象深度耦合在一起。状态约束可能来自于对于安全的考虑、物理规则的约束、系统performance的限制等。在任何可行的策略被找到之前，我们需要先回答两个问题：（1）怎么在原来的最优控制问题（OCP）的建模中加上状态约束；（2）怎么设计一个带有约束的RL算法。

我们先来看看第一个问题。它看似简单，但是其内在的困难在于我们在建模时需要从real-time的约束转化到virtual-time的约束。而对应的virtual-time的约束建模方法又不唯一，如果我们选择了不合适的建模方式，那么无论采取何种优化技巧都无法得到一个可行的策略。早期的关于带有约束的OCP的建模可以追溯到MPC（尽管没有被明确的指出）。在MPC中，我们可以通过只在prediction-horizon中的某些步施加约束而令其它步不受约束的方式来处理约束。另一个例子是Control Barrier Function（CBF）。CBF通常只需要去处理一些预测步，因此能降低在long-horizon限制中的计算复杂度。

接下来我们来看看第二个问题。怎么在完成建模之后把状态的限制纳入到RL的学习算法中去。现在主要有三种方法：

• 罚函数法
• 拉格朗日乘子法：这种方法通过使用对偶的上升更新方法来求解一个minimax优化问题。
• feasible descent direction法

大部分现实世界中的决策或者控制问题都是持续不断的（continuing），那么它们的状态限制也应该从当前状态一直持续到无穷远的未来都被满足。不失一般性，我们可以这样表述real-time域中的状态约束：
$$h(x_{t+i})\le 0,i=1,2,\dots ,\infty ,$$ 其中$h(\cdot )\in \mathbb{R}$是一个标量函数。可能大家会疑惑，在工程实际中，很多的状态约束是向量函数而不是标量函数，为什么我们这里要把$h(\cdot )$定义为一个标量函数呢？一方面，十一位内直接处理向量函数会带来很多计算上的负担，好比说在很多时候我们都需要求导，这时候如果$h(\cdot )$是一个向量函数，那么求一次导可能就得到了一个矩阵，再求导可能就得到了哟个张量，这样问题的计算复杂度会急剧上升。另一方面，我们也有很多手段把向量函数转化为标量函数，比如使用求和或者取最值的操作。接下来，我们来引入一个新的概念：Risk Signal，它被定义如下：
$$c_t=h(x_t)$$ 可以这样理解，risk signal与标量的限制函数$h(\cdot )$的关系就与reward signal与utility function的关系一样。Risk signal是一个标量，它表示了一个状态与限制的边界距离多远。限制函数与risk signal构成了一个risk-aware系统，这与reward signal与utility function构成了一个reward系统是类似的。其实很多的代悦书的RL/ADP问题就是通过简单地把risk signal加入到reward signal中来处理状态约束的。这种思路可以极大地降低算法design的复杂度，但是其实仔细想想，这种相对naive的做法并不能保证约束一定会被满足。在这种情况下，因为要在optimal control（以reward signal反映）和约束满足（以risk signal反映）之间做权衡，因此总会看到一定程度的performance loss。另外还需要说明的是，约束函数$h(\cdot )$并不一定是一个已知量。如果这里的约束函数未知，那么就要求risk signal必须是可以观测的，并且我们需要通过不断地与环境交互来获得risk signal的信息。另一方面，如果约束函数已知（有显式解析形式），那么我们可以直接使用观察到的状态和动作来获得risk signal，这样有助于提升算法的效率和训练的稳定性。

9.2.1 从两个域的角度理解状态约束

对于带有状态约束的OCP问题，常见的解决问题的方法，比如变分法和庞特里亚金最小值原理都不再适用。而MPC虽然可以用，但是它的online计算的特性有天然制约了其解决复杂问题的能力。因此，一个offline训练、online应用的RL算法就成了不二选择。

为了说明怎么训这样的一个RL策略，我们需要使用在第八单元的博客中提到的Receding Horizon Control（RHC）的两个时间域的概念。我们需要在virtual-time域中训练策略，并在real-time域中应用策略。事实上这是我们处理带有限制的RL/ADP问题时总是采用的方法。在virtual-time域中，通常这样定义约束：
$$h(x_{i|t})\le 0,i=1,2,...,\infty$$ 注意到这个式子与我们刚刚提到的real-time域中的约束的定义$h(x_{t+i})\le 0,i=1,2,...,\infty$的区别。那里的t+i表示在real-time域中的第i+t个时间步，而这里的i|t表示在virtual-time域中，从实际时间t开始的第i个时间点。在继续下去之前，我们需要指出一个有意思的观察：式子$h(x_{i|t})\le 0$中的约束并不一定需要在virtual-time中每个时间步都被满足。因此，virtual-time域中的约束和real-time域中的约束也不一定是一样的，这种可分离性在为我们在virtual-time域中构建OCP问题时提供了很大的灵活性。下面我们就来介绍一种用的最多的构建OCP问题的方法。

与MPC相似，这里我们在虚拟时间域中训练得到的策略预测出的最有动作序列中只有第一个动作会被真正在real-time域中执行。而执行之后引起的状态转移到的下一个状态（在虚拟时间域中是$x_{1|t}$，在实际时间域中是$x_{t+1}$）也必须满足状态限制：
$$h(x_{1|t})=h(x_{t+1})\le 0$$ 这也被称做Simplest Constraint。至于虚拟时间域中剩下的状态$x_{i|t}i=2.3....\infty$是否满足$h(x_{i|t})\le 0.i=2.3....\infty$并不重要。如下图所示：

那么，我们可以这样构建OCP：
$$\begin{array}{c}\underset{u}{\min }V(x)=\sum _{i=0}^{N-1}l(x_{i|t},u_{i|t}),\\ \text{s.t.}\\ x_{i+1|t}=f(x_{i|t},u_{i|t}),\\ h(x_{1|t})\le 0,\end{array}$$ 其中，初始状态$$x\stackrel{\mathrm{def}}{=}{x}_{0|t}=x_t$$并注意这里的环境模型$f(\cdot )$被假定是完美的，即在虚拟时间域和实际时间域中都是一样的。根据N是否等于$\infty$，可以将上述问题进一步细分为finite-horizon问题和infinite-horizon问题。上述这种在虚拟时间域中构建OCP的方法是最广为使用的，因为simplest constraint的存在，在满足约束的情况下计算量被压缩到了最小，也能够使得学到的策略最接近此约束下的真实策略（因为不必要的额外条件施加的最少）。

9.2.2 关于不可行和可行的定义与讨论

在上面我们讲了simplest constraint之后，可能大家就会以为这是一个绝佳的选择，就应该使用这种方式来在虚拟时间域中构建OCP问题。但是这种方法在实际中用到的却很少？这是为什么呢？为了回答这个问题，需要先来讨论一下什么是可行的和不可行的。

定义1：不可行（Infeasible）：
我们使用不可行（infeasible）来描述一个定义在virtual-time域中的定义的OCP问题没有满足virtual-time域中的约束的可行解。

为了下面更好的说明不可行的现象是怎样发生的，我们可以定义如下集合：
X C s t r = d e f { x ∣ h ( x ) ≤ 0 } \mathrm{X}_{\mathrm{Cstr}}\stackrel{\mathrm{def}}{=}\{x|h(x)\leq0\} XCstr​=def{x∣h(x)≤0} 集合${\mathrm{X}}_{\mathrm{Cstr}}$描述的时所有满足约束的状态的集合。现在我们可以来回答为什么simplest constraint在实际中用的很少了。因为这种约束只要去保证$x_{1|t}$满足约束就可以了，而不需要去保证$x_{i|t},i=2,3,...\infty$满足约束。换句话说，Simplest constraint只要求$x_{1|t}$在${\mathrm{X}}_{\mathrm{Cstr}}$中，而不要求$x_{i|t},i=2,3,...\infty$在${\mathrm{X}}_{\mathrm{Cstr}}$中。因此与其它在虚拟时间域中多步的约束相比，simplest constraint具有最差的保证长时间内feasibility的能力，很容易在之后的实际时间步求解virtual-time域时遇到找不到可行解的情况。而那些多步的约束能保证更多在virtual-time域中的状态点在${\mathrm{X}}_{\mathrm{Cstr}}$中。下面我们来看一个在虚拟时间域中使用4步constraint而遇到不可行的例子：

在上图中，我们可以看到，实际时间t时，实际的状态是$x_t$，它处于可行域之内，然后在时刻t的虚拟时间域中，它作为$x_{0|t}$。然后我们在虚拟时间域中向后预测了四步，得到了$x_{1|t},x_{2|t},x_{3|t},x_{4|t}$，他们都在可行域中，即$x_{1|t},...,x_{4|t}\in X_{\mathrm{Cstr}}$。然后我们选取此时在虚拟时间步中的第一个最优动作$u_{0|t}^{\ast }$作为控制器实际的动作$u_t$进行执行，此时实际状态转移到$x_{t+1}$。我们同样如法炮制，再让实际的状态转移到$x_{t+2}$。但是此时就发生了不可行问题，如上图所示，此时预测出的动作序列的最后一个超出了可行域，即$x_{1|t+2},x_{2|t+2},x_{3|t+2}\in X_{\mathrm{Cstr}}$，$x_{4|t+2}\notin X_{\mathrm{Cstr}}$。那么此时因为虚拟时间域中得不到可行解，因此也无法得到需要在实际时间域中要执行的动作，这时就会发生不可行的现象。从这里我们也可以看出，不可行现象的发生不是因为再实际时间域中我们没有可以采用的动作来转移到下一个满足约束的状态（实际上仍然可能有），只是我们再虚拟时间域中构建的OCP问题没有找到可行解。也就是说，并不是控制器没有可以采取的动作了，而是优化器找不到可行解了。

接下来我们来定性的分析一下状态约束和可行性的关系。对于在虚拟时间域中的OCP问题，如果我们把需要满足约束的horizon设置的越长，得到的策略的可行性就会越高。这是因为我们保证了long-term下满足约束。但是，增长horizon的代价是计算复杂度的增加以及策略最优性的降低。因此，需要恰当的在虚拟时间域中构建OCP问题来达到最优性和可行性的平衡。

实际上，不光是我们这里的讲到的带约束的RL/ADP问题，不可行（infeasible）的问题在很多的其它的带约束的最优控制问题里面页是一个由来已久的问题。比如在带约束的MPC中，就曾经提出了很多方法来处理这个问题，如horizon enlargement、约束松弛等。下面来简要介绍一下这两种方法：

• Horizon Enlargement：
  • 特点：通过增加horizon的长度来增加可行性。
  • 缺点：增加horizon的长度会增加计算复杂度，同时也会降低策略的最优性。
• 松弛约束：
  • 特点：通过将一些硬性的状态约束转化为soft constraints。
  • 缺点：
    • 很难确定哪些状态可以被松弛，要松弛的话又要松弛多少。
    • 某些状态由于实际的物理系统的约束是绝对不可以被松弛的。

上述的关于不可行的分析也为我们澄清一些长久以来finite-MPC中的模糊的看法提供了依据。广为人知，horizon很短的MPC问题往往难以保证闭环系统稳定性，只能采用一些stability conditions来修补，比如终止状态约束（terminal state constraints）和终止惩罚约束（terminal penalty constraints）。但是上述stable conditions的缺点和详尽的理论分析也一直未被讨论。其实上述的做法是基于RHC的可行性的假设，然而通过我们刚才的讨论可知这并不是恒成立的。实际情况是stablitity conditions只是通过增加更多的约束来达到效果的，但是这样自然会降低策略的最优性（因为约束多了）和可行性（因为增加了额外的约束，更容易违反了），如果增加的sta’bility conditions过于tight设置会找不到可行解。因此，在MPC中同通过上述tricks来解决闭环系统稳定性的做法不是free lunch，是以牺牲最优性和可行性为代价的。

9.2.3 Constraints的类型和可行性分析

Constraints的类型通常有两种：point-wise constraints和barrier constraints。它们的形式如下：

• Point-wise constraints：
  $$h(x_{i|t})\le 0,\forall i=1,2,\dots ,n$$ 这里的n表示需要施加的virtual-time域中的约束的个数。
• Barrier constraints：
  $$\left(h(x_{i+1|t})-h(x_{i|t})\right)+\lambda h(x_{i|t})\le 0,\forall i=1,2,\dots ,n$$

注意，读者需要记住，凡是带有约束的OCP都是定义在virtual-time域中的。但是，正如同大多数的文献都不去区分，在下面的叙述中我们也会使用$x_{t+i}$来表示$x_{i|t}$。

9.2.3.1 类型I: Point-wise constraints

Point-wise constraints描述了在虚拟时间域中每个时间步都需要满足的约束。首先，为了下面描述的清晰，我们需要先厘清两个记号N和n之间的区别。N表示在real-time域中的真实的预测horizon的长度（即真实时间域中cost function中求和的序列的长度），而n表示在虚拟时间域中的预测horizon的长度（在虚拟时间域中世家约束的不等式数量）。那么根据n域N之间的关系，可以对于point-wise constraints做出如下的分类：

• Short-horizon Point-wise Constraints（$n<N$）：
  易知，我们之前讲过的simplest constraint就是一种short-horizon point-wise constraints（$n=1$）。
• Full-horizon Point-wise Constraints（$n=N$）：
  根据N是否等于$\infty$，又可以将full-horizon point-wise constraints进一步细分：
  • Finite pointwise constraint (full-horizon)：
    $$h(x_{i|t})\le 0,\forall i=1,2,\dots ,N.$$
  • Infinite pointwise constraint (full-horizon)：
    $$h(x_{i|t})\le 0,\forall i=1,2,\dots ,\infty .$$

在下面的讨论中，我们主要讨论上述分类中的两种：$n=N=<\infty$和$n=N=\infty$。我们把前者称为finite-horizon OCP，把后者称为infinite-horizon OCP。注意到，这两种OCP都是full-horizon的。

下面我们来对于状态空间$\mathcal{S}$进一步划分。首先，我们之前已经定义了${\mathrm{X}}_{\mathrm{Cstr}}$，它表示了所有满足约束的状态的集合。但是，这个集合是否就是可行域呢（或者说，这个集合里的状态点是否全都是feasible的呢）？当然不是！因为在集合${\mathrm{X}}_{\mathrm{Cstr}}$只是说明满足约束，但是可行域中每个点的“可行”不仅意味着满足约束，还意味着以该状态点作为输入的虚拟时间中的OCP问题是有解的。因此，可行域是$X_{\mathrm{Cstr}}$的一个子集。我们可以进一步将可行域分为两类：

• Initially Feasible Region：

  定义2：Initially Feasible Region（IFR，$X_{Init}$）：
  初始可行域是这样一些状态构成的集合：这些状态本身是可行的（对应于OCP有解），但是从它们转移到的后续状态不一定是可行的。

• Endlessly Feasible Region：

  定义3：Endlessly Feasible Region（EFR，$X_{Edls}$）：
  永久可行域是这样一些状态构成的集合：这些状态本身是可行的（对应于OCP有解），并且存在一个策略，使得从这些初始状态转移到的后续状态也是可行的。

一个策略只有工作在EFR中才能被称为一个有用的策略并部署在真实环境中。

对于finite-horizon OCP问题，$X_{Init}$、$X_{Edls}$和$X_{Cstr}$之间的关系如下图所示：

上图中那个最大的正方形区域就是$X_{Cstr}$。它们之间的包含关系如下：
$${\mathrm{X}}_{\mathrm{Edls}}\subseteq {\mathrm{X}}_{\mathrm{Init}}\subseteq {\mathrm{X}}_{\mathrm{Cstr}}$$ 而对于infinite-horizon OCP问题，$X_{Init}$、$X_{Edls}$和$X_{Cstr}$之间的关系如下图所示：

它们之间的包含关系如下：
$${\mathrm{X}}_{\mathrm{Edls}}={\mathrm{X}}_{\mathrm{Init}}\subseteq {\mathrm{X}}_{\mathrm{Cstr}}$$ 这时EFR的等于IFR。这也很容易理解，因为此时我们的虚拟时间中的OCP问题是无限长的，只要输入的初始状态可行且OCP有解，那么必定能满足之后转移到的状态都是可行的（因为如果之后的状态不可行，那么无限长的OCP就没有解了）。因此，此时我们不区分IFR和EFR，将其简称为可行域（feasible region）。此时的可行域只由环境模型和约束决定，而与优化时采用的标准（criterion）无关。

我们的目标是找到最大的EFR，因为我们找到的EFR越大，可供算法工作在内的安全区域就越大。那么，大家可能会好奇哪种虚拟时间域中的约束可以带来最大的EFR呢？答案是full-horizon point-wise constraint。事实上，我们有如下的定理：

定理1：对于一个infinite-horizon OCP问题，full-horizon point-wise constraint相比于其它所有可行的虚拟时间域中的约束，具有最大的EFR。

证明参考原书第9.2.3.1节。实际应用中，我们在构建OCP时不一定使用full-horizon point-wise constraint，因此得到的也不一定是最大的EFR，而是它的一个子集。在下面的叙述中，我们规定使用$X_{\mathrm{Edls}}$来表示最大的EFR，而使用$X$来表示我们得到的EFR的一个子集。

其实IFR和EFR这个概念不是一个很新的概念。比如，在今天的MPC研究中，在一个MPC算法被应用之前，总是要计算它的EFR，因为RHC（Receding Horizon Control）的机制并不能保证算法的稳定性和递归可行性。再者，对于一个RL/ADP算法，它学得的策略只有工作在EFR中才是物理上有意义的。当控制一个处于不可行区域或者IFR区域的状态时，总是会导致不可行（infeasibility）的问题，并可能带来严重的安全问题。因此，一个有用的RL/ADP算法总是应该同时输出一个EFR以及一个在EFR之内的最优策略。还应该注意的是，一个EFR不止对应一种可行的策略，只不过这其中有一个是最优的策略（可以最小化我们的criterion）罢了。

9.2.3.2 类型II: Barrier constraints

在具体讲Barrier constraints之前，我们先来想想一个理想的定义在虚拟时间域中的约束应该具有什么特点。显然，我们希望这个约束在保证系统能够严格保证约束不被破坏的前提下拥有尽可能大的EFR（Endlessly Feasible Region）。我们刚才已经证明过了，full-horizon的point-wise的约束拥有最大的EFR，但是它的不等式太多了；而最开始说的simplest constraint只有一个不等式，但是它的EFR很小。我们希望在二者之间区的一个平衡，那么Barrier constraints就是一个很好的选择。

多步的Barrier constraints的形式如下：
$$\begin{gathered} B(x_{i|t},x_{i+1|t})\stackrel{\mathrm{def}}{=}\left(h\right(x_{i+1|t})-h(x_{i|t}\left)\right)+\lambda h(x_{i|t})\le 0 \\ \forall i=0,1,...,n-1, \end{gathered}$$ 这里的n是不等式约束的数量，通常我们选取时要使它远远小于N或者$\infty$。可以看出，上述一系列不等式拥有cascading的结构，我们可以推出根据上述不等式组，每个虚拟时间步上的约束函数$h(x_{i|t})$之间满足下述的收敛关系：
$$h(x_{i|t})\le (1-\lambda {)}^{i}h(x_{0|t})$$
那么，从上式自然易得，$\gamma$的选取对于约束强度的影响：

• $\lambda \in (-\infty ,0]$：此时收缩因子$(1-\gamma )$大于1，约束力还不如point-wise的约束强。
• $\lambda \in (0,1)$：此时收缩因子$(1-\gamma )$小于1，约束力比point-wise的约束更强。
• $\lambda =1$：退化为标准的point-wise约束。
• $\lambda \in (1,+\infty )$：物理上无意义。

对于相同的horizon长度（即虚拟时间域中的不等式数量），barrier约束的约束力通常比point-wise约束更强。换句话说，要实现相同强度的约束，barrier约束所需的不等式数量更少。正因为barrier约束的约束力更强，所以对于同一个初始状态，barrier约束比point-wise约束更有可能保证该状态的长期的recursive feasibility。因此，其EFR往往大于相同horizon长度的point-wise约束。如下图所示：

不过，太强的barrier约束也可能会极大的缩小EFR，因为此时很难保证在状态的转移中长期满足约束。而且这种EFR的扩大是以最优性的丧失为代价的。合理的一种设计是只限制下一个状态，这样既有助于降低计算负担又有助于保持良好的recursive feasibility。

9.2.4 以紧急刹车问题为例来说明状态约束与可行性的关系

紧急刹车问题就是要在前方有障碍物时自动采取制动刹车措施。下面来看一下这个问题的建模：

状态	$s=[d,v{]}^{\mathrm{T}}$
动作	加速度$a$
环境模型	$\left[\begin{array}{c}{d}_{t+1}\\ v_{t+1}\end{array}\right]=\left[\begin{array}{cc}1& -\Delta t\\ 0& 1\end{array}\right]\left[\begin{array}{c}{d}_t\\ v_t\end{array}\right]+\left[\begin{array}{c}0\\ \Delta t\end{array}\right]a_t$
Performance Index	${\min }_{\pi }J={\sum }_{i=0}^{N-1}{a}_{t+i}^2$
约束	a ∈ [ a B r k , 0 ] d t + i ≥ d safe , i = { 1 , 2 , ⋯   , ∞ } a\in[a_{\mathrm{Brk}},0]\\d_{t+i}\geq d_{\text{safe}},i=\{1,2,\cdots,\infty\} a∈[aBrk​,0]dt+i​≥dsafe​,i={1,2,⋯,∞}

上面的d和v分别表示车辆与前方障碍物的距离和速度，$\Delta t$表示采样时间间隔。Performance Index采用一个长为N的horizon中各个时刻的加速度的平方之和（表示能量）。约束有两类，第一类是加速度约束，其中$a_{\text{Brk}}$是制动的最大加速度；本处我们取为$-10m/s^2$。第二类是与障碍物的距离约束，其中$d_{\text{safe}}$是安全距离，本处我们取为0。

那么，根据我们之前的讲述，可以构建处两种不同的约束：

• Point-wise constraints：
  d i ∣ t ≥ d s a f e , i = { 1 , 2 , ⋯   , N } d_{i|t}\geq d_{\mathrm{safe}},i=\{1,2,\cdots,N\} di∣t​≥dsafe​,i={1,2,⋯,N}
• Barrier constraints：
  ( d i ∣ t − d i + 1 ∣ t ) + λ ( d s a f e − d i ∣ t ) ≤ 0 , i = { 1 , 2 , ⋯   , N } \left(d_{i|t}-d_{i+1|t}\right)+\lambda\big(d_{\mathrm{safe}}-d_{i|t}\big)\leq0,i=\{1,2,\cdots,N\} (di∣t​−di+1∣t​)+λ(dsafe​−di∣t​)≤0,i={1,2,⋯,N}

下面我们使用上面的两种约束结合MPC进行分析（为什么这里不用RL算法？因为这里我们此时重点是要阐明约束与可行的关系，使用的算法只要能够套进RHC的分析框架即可）。那么，因为我们此时的状态只有两维，所以我们可以将状态之间转移形成的轨迹在二维平面上画出来，如下图所示：

图中的垂直于横轴的那条虚线表示距离约束，而那条红色的曲线代表加速度约束（因为$v^2=2a\cdot d$，所以加速度约束可以表示为$d_{\min }=0.5\frac{v_0^2}{|a_{\mathrm{Brk}}|}$）。图的标题中的$N=5$表示预测的horizon的长度。而图中所有哪些靠右的实心点表示初始状态，之后的状态则使用空心点表示。而破坏约束的点使用$\times $来表示。下面所有的同类图中含义均与此处相同。

首先我们来关注point-wise constraints的情况。下面一组图首先展示了不同的horizon长度（这里的N既是虚拟时间域中的约束数量，又是真实时间中的cost function中求和的长度，即$n=N$）下的情况：

可以看出，随着horizon长度的增加，违反约束的轨迹越少。这里的道理很好理解，就是因为约束更加严格了，因此违反约束的可能性就越小。下图展示了不同horizon长度下不可行区域、初始可行区域（IFR）和永久可行区域（EFR）的情况：


可以看出，随着horizon长度的增加，EFR面积也不断增加。当N=20的时候，此时的EFR已经与理论上的最大EFR（无限长horizon的point-wise constraints下的EFR，即图中红线下面的区域）非常接近了。同时，从N不断增大的过程中，我们也发现了初始可行区域也不一直在发生变化，不是一成不变的。这是因为IFR的定义是该集合中的状态使得OCP有解，那么随着N的增大，求解每个OCP时需要处理的约束数量也在增加，因此更难满足约束，因此IFR也在不断变小。从变化趋势也可以看出，当$N\to \infty$时，IFR也与理论上的那个红线下面的区域重合了。

接下来我们来看barrier constraints的情况。这里barrier constraints的取为两步的情况。先来看看不同的$\lambda$下的情况：

可以看出，随着$\lambda$的减小，违反约束的轨迹越来越少，这说明barrier constraints的约束力越来越强。当$\lambda =0.1$的时候，约束效果就已经很好了。而当$\lambda =0.02$的时候，约束力太强导致了有些轨迹甚至在离垂直于横轴的那条灰色虚线还有一定距离的地方就停下了。下面展示了不同$\lambda$下的不可行区域、初始可行区域（IFR）和永久可行区域（EFR）的情况：

可以看出，随着$\lambda$的减小，EFR面积也不断增加。当$\lambda =0.1$的时候，此时的EFR已经与理论上的最大EFR很接近了。而当$\lambda$继续减小，此时的约束会越来越保守，可能导致EFR反而减小。

同时，可以看出，要达到同样的EFR近似于理论上最大的EFR，barrier constraints所需要的约束数量要远远小于point-wise constraints（2步对20步）。这也说明了barrier constraints的具有更强的约束力的特点。

9.2.5 带约束的RL/ADP算法的分类

正如之前所说，主要有三种方法来处理带约束的最优化问题（OCP问题）：

• 罚函数法：将一个惩罚项加入cost function中，来惩罚违背约束的状态。
• 拉格朗日乘子法：这种方法使用对偶理论来确定原始问题的下界。根据Slater条件，这样可以得到一个最优解。
• Feasible Descent Direction（FDD）法：在FDD方法中，更新的方向既可行又可以保证下降，并且原始的带约束的OCP问题被转化为了一系列的局部的凸优化问题。

与不带约束的RL/ADP问题相似，带约束的RL/ADP问题也可以分为两种方法：Direct Method（带约束的策略梯度）和Indirect Method（带约束的策略迭代和带约束的值迭代）。Direct RL/ADP方法中，带约束的OCP问题被转化为一个带约束的优化问题，最优解使用随机梯度下降来得到；而Indirect RL/ADP方法中，通过求解带约束的贝尔曼方程（通常同时是最优性的充分和必要条件）的解，来作为最优策略。

下表展示了带约束的RL/ADP算法的分类，其中黑色小圆圈表示对应的算法存在，而白色小圆圈表示对应的算法不存在，“#”表示会在下面的章节中讨论的算法。

9.2.5.1 对于带约束的OCP问题的Direct RL/ADP方法

不失一般性，考虑之前说过的full-horizon point-wise constraints的情况。我们可以将带有状态约束的OCP问题表示为：
$$\begin{array}{c}\underset{u}{\min }V(x)=\sum _{i=0}^{\infty }l(x_{t+i},u_{t+i}),\\ s.t.\\ x_{t+i+1}=f(x_{t+i},u_{t+i}),\\ x\stackrel{\mathrm{def}}{=}{x}_t\\ \text{with the full-horizon pointwise constraint:}\\ h(x_{t+i})\le 0,i=1,2,...,\infty ,\end{array}$$ 注意，这里的full-horizon问题的horizon取得是$\infty$。另外，为了与其他的经典的文献里面的记号对齐，这里约束采用的记号看似（写成）定义在实际时间域中的，但需要牢记于心的是所有的约束都是定义在虚拟时间域中的。

前面介绍过的罚函数法、拉格朗日乘子法和FDD法都可以用来解决上述的带约束的OCP问题对应的RL/ADP问题。PDO（Primal-Dual Optimization）算法是一种前沿的拉格朗日乘子法类的方法。它使用对偶上升技术来进行策略更新。TRPO算法可以被看做一种带约束的model-free的强化学习算法。它使用二阶椭圆形的约束来限制策略更新的步长。局部的线性化允许TRPO算法使用一个共轭的梯度算子来更有效率的计算梯度。而CPO算法则是TRPO算法的一个扩展，它能保证每次策略更新不会违反约束。

9.2.5.2 对于带约束的OCP问题的Indirect RL/ADP方法

实际上，处理带约束的OCP问题的Indirect RL/ADP方法比不带约束的版本历史更长。罚函数法可以追溯到上世纪七十年代的risk-sensitive MDP。这类方法把约束作为奖励信号的一部分。由此也可以引出一系列risk-sensitive的TD算法，比如risk-sensitive Q-learning和risk-sensitive TD(0)。而为了应用拉格朗日或者FDD方法，需要使用一个一个带约束的actor和一个不带约束的critic来求解带约束的贝尔曼方程。带约束的actor需要去求解一个带约束的优化问题，而不管是拉格朗日乘子法还是FDD法，都可以在初始状态可行的条件下递归的保证后续状态的可行性。下面我们来看看怎么构建一个带约束的贝尔曼方程。

定义4：可行的策略（Feasible Policy：
对于一个给定的区域$X\in X_{\mathrm{Edls}}$，我们称一个策略在这个区域内是可行的，如果对于任意的初始状态$x_0\in X$，它后续转移到的状态$x_1,x_2,\cdots ,x_{\infty }\in \mathrm{X}$。

无论何时一个策略被称为是可行的，我们都必须事先指定它所工作的区域。那么当然，最完美的工作区域就是最大的endless feasible region：$X_{\mathrm{Edls}}$。但这个最大的EFR不总是可以的，因此它的一些特殊的子集也可以被作为工作区域。换句话说，一个可行的策略要么被定义在$X_{\mathrm{Edls}}$上，要么被定义在$X_{\mathrm{Edls}}$的一个特殊的子集$X$上。这里的特殊指的是任何从$X$中开始的状态都可以保证后续的状态都待在$X$中。

带约束的Indirect RL/ADP方法的构建依赖于下面的贝尔曼方程：
V ∗ ( x ) = min ⁡ u { l ( x , u ) + V ∗ ( x ′ ) } , s.t. x ′ = f ( x , u ) , with one- step constraint: x ′ ∈ X E d l s . \begin{aligned}V^*(x)&=\min_u\{l(x,u)+V^*(x^{\prime})\},\\ &\text{s.t.}\\x^{\prime}&=f(x,u),\\ \text{with one-}&\text{step constraint:}\\x^{\prime}&\in\mathrm{X}_{\mathrm{Edls}}.\end{aligned} V∗(x)x′with one-x′​=umin​{l(x,u)+V∗(x′)},s.t.=f(x,u),step constraint:∈XEdls​.​ 可以看出，在带约束的贝尔曼方程中，约束只表现为一步的形式，即要求下一步转移到的状态$x^{\prime }$停留在$X_{\mathrm{Edls}}$中。为了保证递归可行性（recursive feasibility，即对于Policy Iteration来说，所有中间策略都是“可行”的），下一个状态$x^{\prime }$必须定义在一个特殊的EFR中。我们自然会想，最好的选择就是$X_{\mathrm{Edls}}$，它提供了关于约束的最明显信息。因此，我们在上面的带约束的贝尔曼方程中确实也是这样选的，这样可以最大化最终得到的策略的工作区域。可能大家会疑惑，为什么不能选最原始的$x^{\prime }\in X_{\mathrm{Cstr}}$（即$h(x^{\prime })\le 0$）呢？因为这样选似乎不用提前计算任何EFR，算法的设计也会更显得简单。其实，这样选也是可以的，只不过这样是隐式的寻找一个满足约束的策略。我们可以使用贝尔曼方程的机制来解释一下为什么这样选也是可行的。本质上来说，带约束的贝尔曼方程中的one-step约束表明了带约束的优化问题在哪些区域内是数学上可行的（可行换句话说就是状态值函数在定义的区域内是有限值）。因此选择$x^{\prime }\in X_{\mathrm{Cstr}}$也可以，因为这样在优化过程中那些违反约束的点会被排除在外。最终随着优化过程中对于带约束的环境动力学的探索，可行区域可以被确定下来。选择$x^{\prime }\in X_{\mathrm{Cstr}}$的坏处是这样没有显式的考虑到约束，需要进行大量的计算。关于选择$x^{\prime }\in X_{\mathrm{Edls}}$还是$x^{\prime }\in X_{\mathrm{Cstr}}$的一个简单图示如下：

从上图中，可以看出，如果选择$x^{\prime }\in X_{\mathrm{Edls}}$，那么每次转移也都是在这样一个可行区域中进行转移，不会超出这个区域，探索到不可行的状态；而如果选择$x^{\prime }\in X_{\mathrm{Cstr}}$，，每次趋势会探索到一些不可行的状态（红色的点）。

下一个问题是怎么设计一个迭代算法来求解带约束的贝尔曼方程的解。我们可以选择带约束的策略迭代，那么关键问题就是怎么处理单步约束。一种看法是我们可以把约束看成是环境动力学的一部分。由此也可以知道，可行的约束应该具有马尔科夫性质（每个约束只与当前的状态，上一个状态以及动作有关），这样才能被视为马尔科夫性质的一部分。如果没有约束被违反，带约束的策略迭代就与不带约束的版本没有任何区别。因此，在EFR中，带约束的贝尔曼方程的解就是原始的OCP问题的最优解；而在EFR之外，讨论贝尔曼方程的解是没有意义的，因为在未来某个时间点约束总会被为违反。

现在，让我们来讨论一下怎么设计一个带约束的策略迭代算法。按之前的讨论，算法应该包含两部分：（1）PEV（Policy Evaluation）：即critic的更新。（2）PIM（Policy Improvement）：即actor的更新。在PEV阶段，因为当前的策略是可行的，所以不需要考虑约束，所以说PEC阶段与无约束的版本的PEV阶段是一样的，self-consistency条件不变：
$$V^k(x)=l(x,{\pi }_k)+V^k(x^{\prime }).$$在PIM阶段，则必须考虑约束，以便找到一个更好且可行的策略，否则在下一次迭代中self-consistency条件就会被破坏，因为此时状态值函数超出工作区域就不会有意义了。因此，PIM过程应该是下面这样的带约束优化问题：
π k + 1 ( x ) = arg ⁡ min ⁡ u { l ( x , u ) + V k ( x ′ ) } , with x ′ = f ( x , u ) , x ′ ∈ X E d l s . \pi_{k+1}(x)=\arg\min_u\{l(x,u)+V^k(x^{\prime})\},\\\text{with}\\x^{\prime}=f(x,u),\\x^{\prime}\in\mathrm{X}_{\mathrm{Edls}}. πk+1​(x)=argumin​{l(x,u)+Vk(x′)},withx′=f(x,u),x′∈XEdls​. 可以看出上述的优化目标说明，对于每一个状态$x$，都要找到一个u使得它的状态值函数最小（使用贝尔曼方程表示的）。通过限制$x^{\prime }$在$X_{\mathrm{Edls}}$中，可以保证每次都能是策略在保持可行的条件下变得更好。为了证明我们可以不断地重复应用PEV和PIM，我们需要证明策略${\pi }_k$在
$X_{\mathrm{Edls}}$中是递归可行的（即每次通过${\pi }_k$求得的${\pi }_{k+1}$是可行的）。那么关键是证明${\pi }_{k+1}$总是存在于$X_{\mathrm{Edls}}$中。简单证明如下：

定理2：对于一个带约束的策略迭代算法，如果初始策略${\pi }_0$是可行的，那么对于任意的$k$，${\pi }_{k+1}$都是可行的，只要它之前的策略${\pi }_k$是可行的。

证明：首先，如果${\pi }_k$是可行的，那么$V^k(x)$在$X_{\mathrm{Edls}}$中是有限值。那么因为$V^k(x)$是有限值，那么每次PIM时构建的优化问题都是有有意义的。那么如果从这个优化问题求得的${\pi }_{k+1}$是非平凡的，那么它必然是可行的。而如果它是平凡的，那么至少可以选择${\pi }_{k+1}={\pi }_k$。因此，总存在一个可行的${\pi }_{k+1}$在$X_{\mathrm{Edls}}$中。证毕。

除了递归可行性，收敛性也是一个重要的性质。在EFR中时，证明收敛性是比较容易的，可以像证明无约束的版本一样，主要分为两个部分：（1）值函数值不断下降；（2）最终可以收敛到最优值。这里就不再赘述了。另外值得指出的是，关于EFR和递归可行性的概念在一些MPC的文献中也被提到，只不过用的名词不一样而已。详情可参考Borreli在2017年的书（详见本文章对应的《Reinforcement Learning for Sequential Decision and Optimal Control》的参考文献[9-7]）。