动态规划基础

Bellman's Principle

针对某系统、某初始状态、某奖励/损失函数和时间窗口，解一条最优的控制序列，把其中某段截取出来，将截取段的开头作为初始状态，重新解一条最优的控制序列，一定和原来的相同。

一句话，全局最优必然包含局部最优。

贝尔曼原理隐含了“系统具有马尔可夫性”和“系统的奖励/损失可累加”这两个假设。

一、若系统不具有马尔可夫性，则从初始状态到中间状态的历史，会影响系统在中间状态时做出的决策，这可能导致后续最优序列，与直接从中间状态开始的最优序列不一致。

[!NOTE] 马尔可夫性 系统当前状态包含了决定未来的所有必要信息，状态转移概率和即时奖励/损失仅与当前状态、动作（控制输入）有关，与历史信息无关。

二、若系统的奖励/损失不可累加，必须完成一次完整的控制/决策流程才可算出，那么局部序列和全局序列的关系就很复杂，无法推出贝尔曼原理。

动态规划

基于贝尔曼原理，我们从轨迹终点往回推，只要每一步都是最优，那整条轨迹就是最优的。

举个例子，我们定义最优代价函数（cost-to-go）\(V_{k}(\mathbf{x})\) 编码了从 \(k\) 时刻，状态 \(\mathbf{x}\) 开始进行最优控制到终点的总代价。

以LTI 系统的 LQR 问题为例，在最后时刻 \(N\) 的最优代价函数是

\[V_{N}(\mathbf{x}) = \frac{1}{2}\mathbf{x}^{\top}Q\mathbf{x} = \frac{1}{2}\mathbf{x}^{\top}P\mathbf{x}\]

在上一时刻的最优代价函数是

\[V_{N-1}(\mathbf{x}) = \min_{\mathbf{u}}\frac{1}{2}\mathbf{x}_{N-1}^{\top}Q\mathbf{x}_{N-1}+\frac{1}{2}\mathbf{u}_{N-1}^{\top}R\mathbf{u}_{N-1}+V_{N}(A\mathbf{x}_{N-1}+B\mathbf{u}_{N-1})\]

最优的 \(\mathbf{u}_{N-1}\) 是以上函数关于 \(\mathbf{u}\) 的梯度为 0 的解：

\[\begin{aligned} &\nabla \left[\mathbf{u}_{N-1}^{\top}R\mathbf{u}_{N-1}+(A\mathbf{x}_{N-1}+B\mathbf{u}_{N-1})^{\top}P(A\mathbf{x}_{N-1}+B\mathbf{u}_{N-1})\right]\\ &= R\mathbf{u}_{N-1} + B^{\top}P(A\mathbf{x}_{N-1}+B\mathbf{u}_{N-1}) = 0\\ \mathbf{u}_{N-1} &= -\left(R+B^{\top}PB\right)^{-1}B^{\top}PA\mathbf{x}_{N-1} \end{aligned}\]

这里的 \(\left(R+B^{\top}PB\right)^{-1}B^{\top}PA\) 就是 Riccati 递归法里推出来的负反馈增益系数 \(K\) ！

---

以上就是动态规划的基本流程，我们概括一下：

首先，将终端代价 \(l_{N}(\mathbf{x})\) 赋值给 \(V_{N}(\mathbf{x})\) ，然后按照以下式子反向递推：

\[V_{k-1}(\mathbf{x}) = \min_{\mathbf{u}}\left[l(\mathbf{x},\mathbf{u})+V_{k}(f(\mathbf{x},\mathbf{u}))\right]\]

这里的 \(l(\mathbf{x},\mathbf{u})\) 是状态代价+阶段代价，\(f\) 是状态转移函数。

我们知道了最优代价函数之后，就可以解出每个时刻的最优控制输入了：

\[\mathbf{u}_{k}(\mathbf{x}) = \arg\min_{\mathbf{u}\in\mathcal{U}}\left[l(\mathbf{x},\mathbf{u})+V_{k+1}(f(\mathbf{x},\mathbf{u}))\right]\]

从强化学习的视角看，\(l(\mathbf{x},\mathbf{u})\) 就是状态动作的奖励函数 \(r(s,a)\) ，\(V_k\) 就是状态价值函数，两者相加就是动作价值函数 \(Q^{\pi}(s,a)\) .

在强化学习中，我们一般不用状态价值的贝尔曼期望方程，而是用动作价值的贝尔曼期望方程。这是因为我们要避免在建模时引入模型先验知识 \(f\) ，尽可能做到 model-free .

The curse

动态规划方法只在简单低维问题可行，对于非线性、高维问题，基本上我们无法写出一个代价函数的形式，就算能写出来，大概率也是非凸的优化问题，难以优化。