- 「LQR」:线性二次调节
- 「DDP」:微分动态规划
- 「LQG」:线性二次高斯分布
1 有限范围 MDP
在上一章中我们介绍了马尔可夫决策过程,其中最优贝尔曼公式给出了最优值函数的求解方法:
根据最优值函数,我们还可以求解出最优策略:
在本章中,我们将对上一章的结论进行推广:
- 我们希望写出的方程对离散和连续情况均适用,即:
- 我们将假设奖励函数同时依赖于「状态和动作」,即
,这使得最优策略的计算公式变为:
- 不同于之前的无限范围,我们将假设 MDP 为「有限范围」,定义如下五元组:
其中
为时间范围。在这样的设定中,对于收益的定义将发生变化:
而不是:
折扣因子的存在本质上是为了保证无限和的奖励函数为有限值。假设奖励函数的上界为某一常数
,则收益为:
其为一个几何级数和(有限和),因为这里收益本身即为有限和,所以折扣因子也不再需要。
此外,在有限范围下,最优策略
将不稳定,随时间发生变化:
这种情况出现的原因从直观上可以理解为:我们希望基于处于环境中的位置与剩余的时间来采取不同的策略。
- 我们将使用基于时间的动态方法:
即状态转移概率随时间变化。奖励函数同样随时间变化
,这样的设定更加符合实际情况。结合之前的设定,有限范围 MDP 的通用公式如下:
注:上述方程与在状态中加入时间等价。
时间
的值函数(使用策略
)使用与之前相同的方式定义:
现在的问题是,如何在有限范围下找出「最优值函数」:
我们可以用「动态规划」的思想来求解这一问题:
- 在决策过程的最后,最优值函数为:
- 对于其他时间步
,如果已知下一个时间步的最优值函数
,则:
基于上述观察,可以用如下算法来求解最优值函数:
- 使用
式计算
- 对于
,使用
式基于
计算
实际上,我们可以将标准的值迭代看做上述算法的特例(不追踪时间),如果在标准设置下,运行值迭代
次,则可以得到最优值迭代的
估计(几何收敛)。我们还可以证明如下定理:
「定理」:令
定义贝尔曼更新以及
(上界)。如果
表示
时间步的值函数,则有:
可以看出,贝尔曼更新
是一个
收缩算子。
2 线性二次调节(LQR)
本节我们将介绍有限范围 MDP 下的一个特例:「LQR 模型」。通过该模型我们可以求得精确的解。该模型常用于机器人控制,很多问题经常将问题简化成该模型。
首先定义模型假设:
「假设一」:状态空间与动作空间连续:
「假设二」:线性转移函数(带噪声):
其中
为矩阵,
为某个高斯噪声(0 均值),之后我们会证明最优策略与噪声无关!
「假设三」:二次奖励函数:
其中
为正定矩阵,这意味着奖励函数一直为负。该奖励函数的特征表明我们希望状态接近原点(小范数),可以理解为模型希望维持稳定,避免过度的波动。
定义完假设后,下面介绍 LQR 算法的两个步骤:
「Step 1」:假定
未知,我们需要基于观察数据进行估计。
,使用值函数近似章节中的方法进行估计:
,使用高斯判别分析方法进行估计(极大似然)
「Step 2」:假定模型参数已知(给定或估计得出),我们可以使用动态规划算法来推导最优策略,即给定:
我们希望去计算
。使用第一节中提到的动态规划方法,我们有:
- 「初始化步骤」
对于最后一个时间步
:
- 「循环步骤」
令
,假定我们已知
。
「事实 1」:如果
是一个二次函数,那么
也是一个二次函数,即:
对于时间步
,我们有
以及
(根据初始化步骤中的结论)。
「事实 2」:我们可以证明最优策略是状态的线性函数。
知道了
就等同于知道了
和
,我们只需要解释如何基于
和
以及其他参数来计算
和
。根据最优值函数的定义以及模型假设,我们有:
上式可以优化为关于
的二次函数(过程省略o(╯□╰)o),我们可以解得最优动作
:
其中:
根据上式可以得出:最优策略与
线性相关。给定
我们可以求解
和
,得出「离散里卡蒂方程」:
「事实 3」:可以看到
不依赖于
和噪声
,这表明「最优策略也不依赖于噪声」!(但是
依赖于
,即
也依赖于
)
最后进行总结,LQR 算法的流程如下:
- 估计参数
(如果必要)
- 初始化
和
- 从
开始迭代更新
和
,使用离散里卡蒂方程(基于
和
)。只要存在能朝 0 状态前进的策略,收敛性就可以得到保障
- 求解最优策略
,注意因为最优策略不依赖于
,所以可以不更新
3 非线性动态下的 LQR
对于很多问题,即便其动态非线性,也可以化简为 LQR。例如,对于倒立摆问题,其状态间的转换关系为:
其中函数
取决于角度的余弦。我们的问题是:该系统能够线性化吗?
3.1 动态的线性化
假定在时间
,系统大部分时间都处于状态
,且选取的行为在
附近。对于倒立摆问题,如果我们达到了某种最优状态,就会满足:行为空间很小且和竖直方向的偏差不大。
我们可以使用「泰勒展开」来进行线性化。先考虑最简单的情况:状态为一维且转换函数
不依赖于动作,则我们可以写出:
对于更一般的情况,公式看上去基本一样,只是将简单的导数换成了梯度:
现在我们可以重写
式来得到如下线性关系:
其中
是某个常数,
是矩阵。我们可以通过将常数项合并到
中(增加一维)使得公式的形式与之前一致。
3.2 微分动态规划(DDP)
之前所说的方法适用于优化目标为保持在某个状态
附近,如倒立摆、无人驾驶(保持在路中间)等。而某些情况下,目标往往更加复杂。下面介绍一种方法,其适用于系统需要遵循某种轨迹(比如火箭)。该方法将轨迹离散化为离散的时间步,并创造中间目标来使用之前的方法。这种方法称为「微分动态规划」,其主要步骤如下:
「Step 1」:使用一个简单的控制器得到一条标称轨迹,作为对目标轨迹的估计:
「Step 2」:在每个轨迹点
执行线性化:
其中
表示当前的状态和动作。现在我们可以使用之前的方法,将上式重写为:
注意这里使用的是非平稳动态设定,即策略随时间发生变化。
类似地,我们可以通过二阶泰勒展开得到奖励函数
:
其中
表示
的海森矩阵项。上式可以重写为(使用之前所述的增加维度技巧):
如果想自己证明,注意下式:
「Step 3」:现在,我们已经将问题「严格」地重写为了 LQR 框架下的形式,可以使用 LQR 来找到最优策略
。
注意:如果 LQR 轨迹(下一步)与轨迹的线性近似偏离过多,可能会出现问题,需要通过调节奖励函数的形态来修正。
「Step 4」:现在我们得到了新的控制器(新策略
),我们将构建一个新的轨迹:
注意生成新轨迹时,我们使用真实的函数
而不是其线性估计来计算转换,即:
然后返回步骤 2,进行重复直到满足某些停止条件。
4 线性二次高斯分布(LQG)
目前为止,我们假设状态都是可以得到的,而在现实世界中,实际的观测值可能并不是真实的状态值(类似 HMM)。我们将使用「部分可观测 MDP」(POMDP)来解决这类问题。
POMDP 是一种包含额外观察层的 MDP。我们将引入一个新的变量
,其满足某种条件概率分布:
形式上看,一个有限范围 POMDP 由如下六元组给出:
在该框架下,一种通用的策略是先基于观测值
得到一个「置信状态」,然后 POMDP 的策略将置信状态映射为动作。
本节我们将对 LQR 进行拓展来求解 POMDP,假定我们观测到
(
),并满足:
其中
为压缩矩阵,
和
一样为高斯噪声;奖励函数保持不变,为状态(非观测值)和动作的函数;置信状态同样满足高斯分布。在上述设定下,具体的算法如下:
「Step 1」:基于观测值计算置信状态的高斯分布:
我们希望计算均值
和协方差
。我们将使用「卡尔曼滤波」算法来提升计算效率(之后介绍)。
「Step 2」:得到分布后,我们将使用均值
作为对
的最佳估计。
「Step 3」:选择动作
其中
来自常规的 LQR 算法。
直观上来看,因为
是
的噪声估计(相当于向 LQR 中添加更多噪声),而 LQR 是与噪声无关的,所以这个算法可以工作。
下面对第一步进行解释,这里我们假设状态与动作无关(
和
可以基于观察数据估计):
因为噪声是高斯分布,所以我们可以证明联合分布也为高斯分布:
使用高斯分布的边缘公式(参考因子分析章节),我们可以得到:
然而计算边缘分布的参数计算过于复杂,可能会达到
的复杂度。我们将使用「卡尔曼滤波」算法来更快捷地计算均值与方差,仅需要常数时间 t。算法分为两步,假定我们已知分布
:
不断迭代上述步骤,即可更新置信状态:
下面具体解释两个步骤:
「预测步」:假定我们已知分布:
则下一个状态的分布也为高斯分布:
其中:
「更新步」:给定
和
,我们可以证明:
其中:
矩阵
也称为「卡尔曼增益」:
从公式可以看出我们并不需要时间步 t 之前的观测值,仅需要之前的概率分布。
将上述过程结合起来,算法的整体过程如下:
- 运行前向传播来计算
,
和
- 运行反向传播(LQR 更新)来计算量
,
和
- 使用
来得到最优策略
5 思维导图