《Reinforcement Learning and Optimal Control》读书笔记 (一): 精准动态规划 Exact Dynamic Programming

在本书的第四章前,我们主要讨论Finite Horizon DP。这时我们通常使用 来指代总的步长数(或者称阶段数)

1.问题建模

一个 stage的确定性动态规划问题通常建模为以下形式:

(i)定义时点k的状态变量。 又称为时点k的状态空间(state space)。

(ii)定义时点k采取的控制变量 。 又称为时点k的控制空间(control space)。控制空间代表当前时点我们能采取的所有控制,这通常是随当时的状态变化的,因此记为而非 。

(iii)具有确定性的动态系统, 即控制后的状态转移方式是确定性的,不受随机扰动影响:

其中: 为时点k的状态转移方程。

(iv)每个时点k的损失函数是确定性的,不受随机扰动影响, 记为。其中终止状态的损失为 。损失函数 一般都是已知的。

(v)给定初试状态 , 对应整个 stage的总损失为 ,并且 是每个时点损失的叠加:

2. 问题目标

从我们的建模来看,在给定损失函数与状态转移方程后,控制序列 唯一决定了状态序列 与总损失 。因此我们的目标便是求解最优控制序列使得总损失 最小,即:

因此我们的最小总损失 满足:

3. 最优性原则(Princple of Optimality)

注意,在我们的问题建模中,总损失是每步损失的叠加。这个假设非常关键: 正是有了这个假设，我们才能把每一步控制的损失分解为当前损失+未来损失。从而有了的动态规划中的各种求解与近似算法。

为了进一步说明,我们首先来定义尾部问题(tail problem):

Tail problem at time :

同样,我们可以定义尾部问题的最小值:

那么最优性原则是说:

proof:

对于其他任意一个时点k状态为的尾部控制序列,对应产生的状态序列定义为 。

由于 是最优控制序列, 从而 是N-stage的次优控制序列。因此：

并且两个控制序列都会使得时点k的状态为 , 故LHS-RHS得:

得证

4. 问题求解算法

从我们的建模可以看出来, 从初始状态 出发,我们的控制过程类似于遍历一颗树。第k层的节点即为第k层的状态，而时点k的做出的控制 ,产生的状态转移类似于从第k层节点 到第k+1层节点 引出一条边,权重为 。因此控制序列产生的状态序列就是这棵以 为根节点,一共 层的树上的从根节点到叶子节点的一个路径。每个路径上的权重和即为我们的总损失 。求最优控制序列即是在这棵树上找到这样一个最短的加权路径。我们当然可以使用图遍历或者树遍历的算法(比如BFS,DFS)找到。但随着 的增大,与状态空间的增大,显然时间消耗是非常难以承受的。因此我们考虑换个思路。

基于我们的模型，我们注意下面这个事实:

注意到imediate cost与未来的决策没有任何关联。因此我们求解尾部问题的最优控制决策,可以先假设当前控制 给定，再求解最优的未来决策，这时再优化 ,即:

这个等式非常的美妙且关键，因为对于绝大部分问题而言 都是已知的。这意味着：一旦我们知道 与我们就能求出 ,因此我们可以从 开始,反向递推,直到求得 。这便是我们问题的最优值。

当我们知道了 后,我们便可以正向决策求得最优控制序列,即：

以上便是我们的求解思路。但同样,为了构建 ,实际上仍然需要计算 次。因此构建 的时间复杂度至少是 。这会随着状态空间与控制空间增大而快速增长。因此对于很多问题而言，我们不会去使用这种算法，因为算法时间消耗是难以接受的。因此往往使用值近似的思想,即通过某种手段求得 并基于此求得次优控制序列 。

5. Q-factor

上式的推导说明了,控制 产生的最小损失可以分解为 imediate cost 与 future cost最小值。我们将两者统一为Q-factor:

又 ,故我们可以得到Q-facto递推式

这样，我们求解最优控制序列可以直接通过解Q-factor得到。求解次优控制序列可以通过求解近似值得到:

在很多问题中,我们也是直接对Q-factor而不是 进行估计。

二. 随机动态规划 Stochastic Dynamic Programming

1.问题建模

相比于确定性动态规划,随机动态规划建模的不同主要侧重于以下几个方面:

(i) 每个时点k多了一个随机扰动 影响状态转移与损失

状态转移不仅与当前状态 和控制变量 ，还和随机变量 有关,即：

。

由这个递推式可以知道 实际上变成了由 决定的随机变量。

同样,时点k的损失也和 有关,即:

。

因 是随机的,因此从 出发,状态序列 也是随机的。相较于确定性的动态规划,一个控制序列 只会得到唯一的状态序列与总损失 。但随着 的加入,一个控制序列可能会产生不同的状态序列，从而产生不同的总损失 。因此我们不再求解最优的控制序列,而是求解最优的policy: 。其中:

即每当我们观测到 后, 就是我们对应的控制变量。(这里我们先不考虑是一个概率分布的情况。)

(ii). 假设 在 给定后的条件概率测度唯一确定。即:

是否知道需要依赖具体的问题,这里我们把 理解为一个随机变量, 是参数。

(iii). 给定初始状态 ,针对policy 的总损失定义在期望形式上，即：

(注意:尽管 是随机的,但它的随机性只来自于 ,因此我们期望式内的随机变量实际只有 )

2.问题求解

我们定义 所有可能的情况构成的集合为策略空间:

那么最优损失便定义为: 。

为方便后面论述与证明,我们定义时点k在状态 执行 与后续策略的损失为:

类似于确定性动态规划,我们可以定义Q-factor,即时点k在状态 执行 的最小当前与未来损失之和:

同样可以定义每个时点 ,状态为 时定义尾部问题的最小损失:

因此一旦我们得到 ,我们就能得到策略,其中:

使得每个时点k都选择当前与未来的期望损失最小的控制。这样定义出来 是真的是任意时点k的尾部问题的最优策略吗? 事实上,我们可以证明对于任意 :

proof:

假设k=m+1时,对于任意 有上式成立

当k=m时,对于任意 :

令

从而:

于是:

记期望内

容易知道:

于是:

又:

故:

因此 该命题对k=m成立

容易验证对k=N-1成立,于是对任意k=0,1,...,N-1成立,从而:

这就说明了策略是任意时点k的尾部问题的最优策略。

上面的证明过程,可以直接说明 与 的递推式在动态随机规划中仍然存在:

(i)

(ii)

从而随机规划问题的求解思想与确定性动态规划问题求解思想一致:

(i) 从 出发,backward递推,求解函数序列

(ii) 正向决策:

三. 一些变种问题和思想

1.状态空间的构造技巧:

一般而言,构造状态 需要遵循下面几个原则:

① 应当包含controller在时点k所知的所有信息

② 应当具有马尔科夫性,能够将过去与未来区分开。一旦我们知道了 ,我们未来的所有控制都只与 有关，而与之前的任何状态控制历史无关

(ps: 我觉得这两条才是最重要的。假设时点k的状态值为 ,若它不能代表stage k的全部信息,这本质上意味着存在隐变量 ，那么真实的状态值 。那么反复访问定义的状态时,其对应的真实状态值可能发生变化，从而得到不同的期望尾部损失）

③ 信息打包的方式可能有多种方式,但对controller来说,可能却是同等重要,或者为选择 所利用上的信息量相同。例如对 的选择来说, 与 为决策 提供的信息量是一致的，因为本来就只需要 的信息。对于这些情况，我们往往考虑能减少状态空间维度的方法来构造。

(ps: 减少状态空间的维度一般来讲是有意义的,但并不总是的。比如动态系统中存在某个数量 随时间变化。 是 在时点k前的所有测量,即: 。用 可以作为时点 k的状态。但一个更好的方式是，使用条件分布 作为状态,因为它可能包含了为决策 所需要的全部信息。 是有限维的，但 是无限维的。因此状态空间的构造要依据问题而定。这种利用条件分布作为状态的方法也称为belief state。)

2. uncontrollable state components

在实际问题中,状态中一些部分不受控制变量影响,并且是首先观测到了状态中的其他部分后再依据 取值而产生,我们把状态中的这些部分不我们称之为uncontrollable state components。那么时点k的完整状态为 。并且我们假设,当观测到 后, 服从条件概率测度 。从而stage k的整个流程如下:

→ 观测

→ 产生 得到完整状态

→ 根据策略生成控制变量

→ 产生随机扰动

→ 状态转移至

同其他DP问题的建模一样,我们可以定义状态转移方程,损失函数,cost-to-go function :

cost at time k

下的最优cost-to-go function:

注意,因为 分布只依赖于,我们可以对求期望缩小 的定义域:

这样 仍然具有递推关系式,因此同样可以利用反向递推正向决策的思想来求解包含uncontrollable state components的问题。但求解并做决策相比求解 做决策会明显缩小状态空间的大小,会带来计算开销上的降低。

3. belief state 与 partial state information

在很多时候,controller并不能获取到 的确切值(比如对 的测量有误差,或者成本难以接受)。很多时候我们也只能获得真实状态 的部分信息。这种情况就成为partial state information 或者 imperfect state information。

通常的做法是将这类问题reduced 到 belief state的问题,即:

它服从controller 获得所有历史observation下的某个条件概率分布。

求解belief state DP的一种做法是。考虑 的条件概率分布由某个参数 决定:

这时我们可以把参数 作为状态 取值。在很多case下,这个参数我们是能求得解析形式与递推关系的。从而能够解出DP问题。