MDP最优控制问题转化为可求解的线性规划

本文是对 CS287-FA19 Advanced Robotics at UC Berkeley 课程
Lecture 3 Solving Continuous MDPs with Discretization 的个人解读
欢迎交流~

本文内容是关于上面这一页板书的理解

问题背景

一个(离散) MDP，包含：

• 状态集合：$S$
• 动作集合：$A$
• 转移概率：$T(s,a,s^{\prime })=P(st+1=s^{\prime }|st=s,at=a)$
• 即时奖励：$R(s,a,s^{\prime })或R(s,a)$
• 折扣因子：$\gamma \in [0,1]$
• 初始状态分布：${\mu }_0(s)=P(s_0=s)$

目标是最大化期望的累积折扣奖励：
$$\underset{\pi }{\max }\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^{t}R(s_t,a_t,s_{t+1})\right]\text{ 其中 }{a}_t\sim \pi (\cdot |s_t).$$

如何将求解最优策略的问题写成一个带有线性约束的优化问题❓

1. 占用测度$\lambda (s,a)$的定义

在无限视域、带有折扣的设定下，定义占用测度(也称为折扣访问频率)为

$$\lambda (s,a)=\sum _{t=0}^{\infty }{\gamma }^{t}P(s_t=s,a_t=a),$$

即在策略$\pi$下，带有折扣${\gamma }^t$考虑了从$t=0$到无穷远将来时刻，“访问”到$(s,a)$的"总权重"(概率累加并乘以折扣)。可以把它理解为：

• ${\gamma }^t$ 折扣因子相当于"越往后越不重要”。
• $P(s_t=s,a_t=a)$ 是第 $t$ 步处在状态 $s$ 并采取动作 $a$ 的概率。

在最优解中，这个${\lambda }^{\ast }(s,a)$会告诉我们在无限时间内 (带折扣权重)"总共"访问$(s,a)$的度量。

2 将期望的累积奖励写成对$\lambda (s,a)$的求和

原先的目标:
${\sum }_{t=0}^{\infty }{\gamma }^t\mathbb{E}[R(s_t,a_t,s_{t+1})]$.
现在把期望拆分到每个 $(s,a)$ 上，
因为“某状态-动作”出现的概率正是 $P(s_t=s,a_t=a)$。

1. 把时刻 t 的概率分量汇总到 $\lambda (s,a)$:
   ${\sum }_{t=0}^{\infty }{\gamma }^{t}P(s_t=s,a_t=a)=\lambda (s,a).$
2. 期望奖励的关键：当“状态为 s、动作为 a”发生后，下一步到达 $s_{t+1}$ 的分布是由转移概率 $T(s,a,s^{\prime })$ 给定，因此
   $\mathbb{E}[R(s_t,a_t,s_{t+1})|s_t=s,a_t=a]={\sum }_{s^{\prime }}T(s,a,s^{\prime })R(s,a,s^{\prime }).$
3. 因此：若考虑所有$(s,a)$的访问，期望总奖励可写成
   ${\sum }_{s,a}{\sum }_{t=0}^{\infty }{\gamma }^{t}P(s_t=s,a_t=a)\times \mathbb{E}[R(s,a,s_{t+1})|s,a].$
   将上面期望替换成 ${\sum }_{s^{\prime }}T(s,a,s^{\prime })R(s,a,s^{\prime })$, 就得到
   ${\sum }_{s,a}({\sum }_{t=0}^{\infty }{\gamma }^{t}P(s_t=s,a_t=a)){\sum }_{s^{\prime }}T(s,a,s^{\prime })R(s,a,s^{\prime }).$
   注意中间那一大括号正好是我们定义的 $\lambda (s,a)$。于是变成
   ${\sum }_{s,a,s^{\prime }}\lambda (s,a)T(s,a,s^{\prime })R(s,a,s^{\prime }).$
   这就是所谓的三重求和形式（对$s,a,s^{\prime }$的求和）。
4. 故，最大化的目标可以改写为
   ${\max }_{\lambda (\cdot ,\cdot )}{\sum }_{s,a,s^{\prime }}\lambda (s,a)T(s,a,s^{\prime })R(s,a,s^{\prime }).$

这样转化的含义是：如果你知道了“在策略$\pi$下折扣访问$(s,a)$的量是多少，就能直接算出这个策略对累积奖励的贡献，从而把“找最优策略”转换为“找一组$\lambda \ast (s,a)$使这个和最大”。

线性规划等价

首先回顾线性规划的定义和要求，
线性规划(LP)通常的标准要素包括：

1. 决策变量：我们要在它上面做最优决策；
2. 目标函数：对决策变量的线性组合进行最大化或最小化；
3. 约束：对决策变量的线性约束（包括不等式/等式）；
4. 非负性

对照我们的占用测度表达：

决策变量与目标函数

• 决策变量：$\lambda (s,a)$。
• 目标函数：
$$\sum _{s,a,s^{\prime }}\lambda (s,a)T(s,a,s^{\prime })R(s,a,s^{\prime })$$
这对 $\lambda$ 来说是一个线性项，因为对每个 $(s,a),\lambda (s,a)$ 只是被一个常数(${\sum }_{s^{\prime }}T(s,a,s^{\prime })R(s,a,s^{\prime })$)乘了一下再加和起来。

约束项

流量平衡约束
在无限时域、折扣设定下，流量平衡约束常写作：

$$\forall s^{\prime }:\sum _{a^{\prime }}\lambda (s^{\prime },a^{\prime })={\mu }_0(s^{\prime })+\gamma \sum _{s,a}\lambda (s,a)T(s,a,s^{\prime }).$$

含义是：
(左侧)下一个时刻带折扣访问到状态$s^{\prime }$的总量"，等于
(右侧)初始就处于$s^{\prime }$的量 + 从上一时刻各状态动作转移到 s’ 的量(再乘以折扣$\lambda$)"。

在某种意义上，它像一个“流量守恒”：

• 左边：在状态 s’ 上的占用总和（对所有动作 a’ 求和，得到“访问状态 s’ 的折扣频率”）。
• 右边：初始分布 ${\mu }_0(s^{\prime })$ + 从前一轮“状态 - 动作 $(s,a)$”里以概率 $T(s,a,s^{\prime })$ 跳到$s^{\prime }$的折扣流量。

• 线性规划约束：
$$\sum _{a^{\prime }}\lambda (s^{\prime },a^{\prime })-\gamma \sum _{s,a}\lambda (s,a)T(s,a,s^{\prime })={\mu }_0(s^{\prime }),$$
是一个标准的线性等式约束（$\lambda$ 仅以一次幂出现，与 $\lambda (s,a)$ 成线性关系）。

• 非负性约束：$\lambda (s,a)\ge 0$。

小结

所有这些都满足“线性规划”的结构：

1. 目标是 ${\mathbf{c}}^{\top }\mathbf{x}$ 形式；
2. 约束是 $A\mathbf{x}=\mathbf{b}$ 或 $A\mathbf{x}\le \mathbf{b}$ 之类的线性关系；
3. 非负性 ($\mathbf{x}\ge 0$) 。

因此，把 MDP（在折扣条件下）最优策略问题转化为“占用测度形式的 LP”，是完全符合线性规划的要求的。

从最优解${\lambda }^{\ast }$得到最优策略

如果想取一个确定性策略(板书中直接记成${\Pi }^{\ast }(s)=\arg {\max }_a\lambda (s,a)$),那就等价于选使${\lambda }^{\ast }(s,a)$最大的动作$a$。