你的位置：首页 > 读后感 > 文章正文

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

时间: 2021-11-13 16:36:48 | 作者：skydownacai | 来源: 喜蛋文章网 | 编辑: admin | 阅读: 109次

为什么要在知乎上分享笔记

由于本人研究生阶段最终选择了强化学习方向,因此研一上学期的主要目标就是读透强化学习相关教材。按照导师的推荐,首先选择了Dimitri P. Bertsekas 写的《Reinforcement Learning and Optimal Control》这本书。同时决定在知乎上每隔一段时间分享自己写好的读书笔记, 一来是强化自己的记忆,逐个检查笔记中是否有错误的地方，二来是分享出来希望同更多朋友交流，这样才知道自己对问题的理解是否正确。因此也十分欢迎各位朋友指正我笔记中的错误。

本次笔记为涉及该书Chapter 1 Exact Dynamic Programming 的全部内容,下面开始正文。

一. 确定性动态规划 Deterministic Dynamic Programming

这是全书的第一节的内容。因此在进入前, 我们首先要了解一些最基本的概念。下面用大白话来阐述。

什么是DP(动态规划)? 动态规划实际上就是在一个离散时间的动态系统上求解最优序列决策的过程。这样的动态系统通常会产生状态序列，这时需要你根据产生的状态做出对应的控制，或者制定策略(policy),从而达到我们的总收益或者平均收益最大,或者成本最小之类的目标。什么是"精准"动态规划? 在后续的内容中我们会看到, 求解动态规划的最优控制, 通常会把执行某个控制u带来的成本分解为: immediate cost

（当前时刻成本）+ future cost

(未来成本)。在某些问题中我们的

是能够精准求出来的，这时计算

的精确值并求解最优控制的过程称为精准动态规划(Exact Dynamic Programming)。相反,我们选择估计

的近似值

并基于此求解最优控制的过程成为近似动态规划(Approximate Dynamic Programming)。什么是"确定性"动态规划? 与确定性动态规划(Deterministic Dynamic Programming) 相对应的是随机动态规划(Stochastic Dynamic Programming)。在问题的模型上,两者的区别在于：对于每个时点

,动态系统产生状态

后, 此时你执行控制 u_k

后，动态系统是否会产生一个随机扰动 w_k

影响下一个时点状态 $x_{k+1}$ 的产生。 (通常假设 w_k

的分布只依赖于

)。如果不产生随机扰动,就是确定性动态规划。如果产生，就是随机动态规划。什么是 "Infinite Horizon" DP 与 "Finite Horizon" DP？ 前者通常指无限步长(阶段)的DP问题,后者指有限步长(阶段)的DP问题。

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

1.问题建模

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

(i)定义时点k的状态变量 $x_kin mathcal{X}_k ,k=0,1,...,N$ 。 $mathcal{X}_k$ 又称为时点k的状态空间(state space)。

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

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

$x_{k+1}=f_k(x_k,u_k), qquad k=0,1,...,N-1$

其中: $f_kleft( x_k,cdot right) : mathrm{U}_{mathrm{k}}left( x_k right) rightarrow mathcal{X}_{k+1}$ 为时点k的状态转移方程。

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

(v)给定初试状态 $x_0in mathcal{X}_0$ , 对应整个 stage的总损失为 $Jleft( x_0;u_0,...,u_{N-1} right)$ ,并且是每个时点损失的叠加:

$Jleft( x_0;u_0,...,u_{N-1} right) =sum_{k=0}^{N-1}{g_kleft( x_k,u_k right)}+underset{text{终止状态的损失}}{underbrace{g_Nleft( x_N right) }}$

2. 问题目标

从我们的建模来看,在给定损失函数与状态转移方程后,控制序列 ${u_0,u_1,...,u_{N-1}}$ 唯一决定了状态序列 ${x_1,...,x_{N-1}}$ 与总损失 $Jleft( x_0;u_0,...,u_{N-1} right)$ 。因此我们的目标便是求解最优控制序列使得总损失最小,即:

$(u_{0}^{*},...,u_{N-1}^{*})inunderset{begin{array}{c} u_kin mathrm{U}_kleft( x_k right) 0le kle N-1 end{array}}{mathrm{arg}min},,Jleft( x_0;u_0,...,u_{N-1} right)$

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

$J^*left( x_0 right) =Jleft( x_0;u_{0}^{*},...,u_{N-1}^{*} right) ,quad x_0in mathcal{X}_0$

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

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

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

Tail problem at time :设时点k的状态为 x_k

后, 求控制序列 ${ u_k,u_{k+1},...,u_{N-1} }$ 使得尾部总损失 $J_kleft( x_k;u_k,u_{k+1},...,u_{N-1} right) =sum_{j=k}^{N-1}{g_jleft( x_j,u_j right)}+g_Nleft( x_N right)$ 最小。我们称 J_k

为cost-to-go function

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

$J_{k}^{*}left( x_k right) =underset{begin{array}{c} u_jin mathrm{U}_jleft( x_j right) kle jle N-1 end{array}}{min},,J_kleft( x_k;u_k,...,u_{N-1} right)$

那么最优性原则是说:

Princple of Optimality：若 ${u_{0}^{*},...,u_{N-1}^{*}}$ 是初始状态为 x_0

下的最优控制序列, 控制序列对应产生的状态序列为 ${ x_0,x_{1}^{*},....,x_{N}^{*} }$ 。那么对于任意的时点

, 尾控制序列 ${ u_{k}^{*},...,u_{N-1}^{*} }$ 是时点

状态为

时的尾部问题的最优控制序列,即: $J_{k}^{*}left( x_{k}^{*} right) =J_kleft( x_{k}^{*};u_{k}^{*},...,u_{N-1}^{*} right)$

proof:

对于其他任意一个时点k状态为 x_k^* 的尾部控制序列 ${ tilde{u}_k,...,tilde{u}_{N-1} }$ ,对应产生的状态序列定义为 ${ tilde{x}_k,...,tilde{x}_{N-1} }$ 。

由于 ${ u_{0}^{*},...,u_{N-1}^{*} }$ 是最优控制序列, 从而 ${ u_{0}^{*},...,u_{k-1}^{*},tilde{u}_k,...,tilde{u}_{N-1}}$ 是N-stage的次优控制序列。因此：

$Jleft( u_{0}^{*},...,u_{N-1}^{*} right) le Jleft( u_{0}^{*},...,u_{k-1}^{*},tilde{u}_k,...,tilde{u}_{N-1} right)$

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

$Jleft( u_{0}^{*},...,u_{N-1}^{*} right) -Jleft( u_{0}^{*},...,u_{k-1}^{*},tilde{u}_k,...,tilde{u}_{N-1} right)$

$=left( sum_{k=0}^{N-1}{g_kleft( x_{k}^{*},u_{k}^{*} right)}+g_Nleft( x_{N}^{*} right) right) -left( sum_{j=0}^{k-1}{g_jleft( x_{j}^{*},u_{j}^{*} right)}+g_kleft( x_{k}^{*},tilde{u}_k right) +sum_{j=k+1}^{N-1}{g_jleft( tilde{x}_j,tilde{u}_j right)}+g_Nleft( tilde{x}_N right) right)$

$=left( sum_{j=k}^{N-1}{g_jleft( x_{j}^{*},u_{j}^{*} right) +g_Nleft( x_{N}^{*} right)} right) -left( g_kleft( x_{k}^{*},tilde{u}_k right) +sum_{j=k+1}^{N-1}{g_jleft( tilde{x}_j,tilde{u}_j right)}+g_Nleft( tilde{x}_N right) right)$

$=J_kleft( x_{k}^{*};u_{k}^{*},...,u_{N-1}^{*} right) -J_kleft( x_{k}^{*};tilde{u}_k,...,tilde{u}_{N-1} right) le 0$

$Rightarrow J_kleft( x_{k}^{*};u_{k}^{*},...,u_{N-1}^{*} right) le J_kleft( x_{k}^{*};tilde{u}_k,...,tilde{u}_{N-1} right)$

$Rightarrow J_kleft( x_{k}^{*};u_{k}^{*},...,u_{N-1}^{*} right) =J_{k}^{*}left( x_{k}^{*} right)$

得证

4. 问题求解算法

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

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

$J_kleft( x_k;u_k,...,u_{N-1} right)$

$=sum_{i=k}^{N-1}{g_ileft( x_i,u_i right)}+g_Nleft( x_N right)$

$=g_kleft( x_k,u_k right) +underset{tail,,problem,,at,,time,,k+1,x_{k+1}=f_kleft( x_k,u_k right)}{underbrace{left( sum_{i=k+1}^{N-1}{g_ileft( x_i,u_i right)}+g_Nleft( x_N right) right) }}$

$=underset{imediate,,cost}{underbrace{g_kleft( x_k,u_k right) }}+underset{future,,cost}{underbrace{J_{k+1}left( f_kleft( x_k,u_k right) ;u_{k+1},...,u_N right) }}$

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

$J_{k}^{*}left( x_k right) =underset{begin{array}{c} u_jin mathrm{U}_jleft( x_j right) kle jle N-1 end{array}}{min},,J_kleft( x_k;u_k,...,u_{N-1} right)$

$=underset{begin{array}{c} u_jin mathrm{U}_jleft( x_j right) kle jle N-1 end{array}}{min}left( g_kleft( x_k,u_k right) +J_{k+1}left( f_kleft( x_k,u_k right) ;u_{k+1},...,u_N right) right)$ $=underset{u_kin mathrm{U}_{mathrm{k}}left( x_k right)}{min}left{ g_kleft( x_k,u_k right) +underset{begin{array}{c} u_jin mathrm{U}_jleft( x_j right) k+1le jle N-1 end{array}}{min}J_{k+1}left( f_kleft( x_k,u_k right) ;u_{k+1},...,u_N right) right}$

$=underset{u_kin mathrm{U}_{mathrm{k}}left( x_k right)}{min}g_kleft( x_k,u_k right) +J_{k+1}^{*}left( f_kleft( x_k,u_k right) right)$

这个等式非常的美妙且关键，因为对于绝大部分问题而言 g_k,f_k 都是已知的。这意味着：一旦我们知道 $J_{k+1}^*$ 与我们就能求出 J_k^* ,因此我们可以从 J_N^*=g_N 开始,反向递推,直到求得 J^*_0=J^* 。这便是我们问题的最优值。

当我们知道了 $left{ J_{1}^{*},...,J_{N}^{*} right}$ 后,我们便可以正向决策求得最优控制序列,即：

$u_{0}^{*}inunderset{u_0in mathrm{U}_0left( x_0 right)}{mathrm{arg}min},,g_0left( x_0,u_0 right) +J_{1}^{*}left( f_0left( x_0,u_0 right) right)$

$x_{1}^{*}=f_0left( x_0,u_{0}^{*} right)$

$u_{i}^{*}inunderset{u_iin mathrm{U}_ileft( x_{i}^{*} right)}{mathrm{arg}min},,g_ileft( x_{i}^{*},u_i right) +J_{i+1}^{*}left( f_ileft( x_{i}^{*},u_{i}right) right) , i=1,...,N-1$

$x_{i+1}^{*}=f_ileft( x_{i}^{*},u_{i}^{*} right) , i=1,...,N-1$

以上便是我们的求解思路。但同样,为了构建 J_k^* ,实际上仍然需要计算 $|bigcup_{x_kin mathcal{X}_k}{mathrm{U}_kleft( x_k right)}|$ 次。因此构建 $left{ J_{1}^{*},...,J_{N}^{*} right}$ 的时间复杂度至少是 $Oleft( prod_k{|bigcup_{x_kin mathcal{X}_k}{mathrm{U}_kleft( x_k right)}|} right)$ 。这往往随着状态空间与控制空间增大而指数级增大。因此对于很多问题而言，我们不会去使用这种算法，因为算法时间消耗是难以接受的。因此往往使用值近似的思想,即通过某种手段求得 $tilde{J}_k$ 并基于此求得次优控制序列 ${ tilde{u}_0,...,tilde{u}_{N-1} }$ 。

5. Q-factor

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

$Q_{k}^{*}left( x_k,u_k right) =g_kleft( x_k,u_k right) +J_{k+1}^{*}left( f_kleft( x_k,u_k right) right)$

$u_{k}^{*}in mathrm{arg}min Q_{k}^{*}left( x_k,u_k right)$

又 $J_{k}^{*}left( x_k right) =underset{u_kin mathrm{U}_{mathrm{k}}left( x_k right)}{min}Q_{k}^{*}left( x_k,u_k right)$ ,故我们可以得到Q-facto递推式

$Q_{k}^{*}left( x_k,u_k right) =g_kleft( x_k,u_k right) +underset{u_{k+1}in mathrm{U}_{mathrm{k}}left( f_kleft( x_k,u_k right) right)}{min}Q_{k}^{*}left( x_k,u_k right)$

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

$tilde{u}_kin underset{u_kin mathrm{U}_{mathrm{k}}left( x_k right)}{min}tilde{Q}_kleft( x_k,u_k right)$

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

二. 随机动态规划 Stochastic Dynamic Programming

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

1.每个时点k多了一个随机扰动 w_k 影响状态转移与损失

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

$x_{k+1}=f_kleft( x_k,u_k,w_k right) in mathcal{X}_{k+1}$ 。

由这个递推式可以知道 x_k 实际上变成了由 $(w_0,...,w_{k-1})与(u_0,...,u_{k-1})$ 决定的随机变量。

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

cost,,at,,time,,k=g_kleft( x_k,u_k,w_k right) 。

因 w_k 是随机的,因此从 x_0 出发,状态序列 $left{ x_1,...,x_N right}$ 也是随机的。相较于确定性的动态规划,一个控制序列 ${u_0,...,u_{N-1}}$ 只会得到唯一的状态序列与总损失 J(x_0) 。但随着 w_k 的加入,一个控制序列可能会产生不同的状态序列，从而产生不同的总损失 J(x_0) 。因此我们不再求解最优的控制序列,而是求解最优的policy: $pi={mu_0,...,mu_{N-1}}$ 。其中:

$mu_k(x_k)in mathrm{U}_kleft( x_k right)$

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

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

$w_k|left( x_k,u_k right) sim mathbb{P}_kleft( cdot |x_k;u_k right)$

$left{ mathbb{P}_0,...,mathbb{P}_{N-1} right}$ 是否知道需要依赖具体的问题,这里我们把 x_k 理解为一个随机变量, u_k 是参数。

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

$J_{pi}left( x_0 right) =mathbb{E}_{w_0,...,w_{N-1}}left( sum_{k=0}^{N-1}{g_kleft( x_k,mu _kleft( x_k right) ,w_k right)}+g_Nleft( x_N right) right)$

(注意:尽管 x_k 是随机的,但它的随机性只来自于 ${w_0,...,w_{k-1}}$ ,因此我们期望式内的随机变量实际只有 ${w_0,...,w_{N-1}}$ )

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

那么最优损失便定义为: $J^*left( x_0 right) =underset{pi sim Pi}{min},,J_{pi}left( x_0 right)$ 。

一旦我们固定了时点k状态 x_k 的取值,那么时点k之前的随机扰动 ${w_0,...,w_{k-1}}$ 不会对未来产生影响。因为他们只是影响时点k之前的损失与 x_k 的取值,但后者被我们固定住了。因此,同确定性规划动态规划类似,我们可以在每个时点 ,状态为 x_k 时定义尾部问题的最小损失:

$J_{k}^{*}left( x_k right) =underset{mu _k,...,mu _{N-1}}{min }mathbb{E}_{w_k,...,w_{N-1}}left( sum_{j=k}^{N-1}{g_jleft( x_j,mu _jleft( x_j right) ,w_j right)}+g_Nleft( x_N right) |x_k right)$

事实上,再期望形式上+总损失是每步叠加的假设下,我们可以看到 $J_{k}^*$ 的递推式在随机规划中仍然存在,只需利用重期望分解即可:

J_k^*(x_k)

$=underset{mu _k,...,mu _{N-1}}{min }mathbb{E}_{w_k,...,w_{N-1}}left( sum_{j=k}^{N-1}{g_jleft( x_j,mu _jleft( x_j right) ,w_j right)}+g_Nleft( x_N right) |x_k right)$

$=underset{mu _k,...,mu _{N-1}}{min }mathbb{E}_{w_k}left( mathbb{E}_{w_{k+1},...,w_{N-1}}left( g_kleft( x_{k,}mu _k(x_k),w_k right) +sum_{j=k+1}^{N-1}{g_jleft( x_j,mu _jleft( x_j right) ,w_j right)}+g_Nleft( x_N right) |x_k,w_k right) |x_k right)$

$=underset{mu _k,...,mu _{N-1}}{min }mathbb{E}_{w_k}left( g_kleft( x_{k,}mu _k(x_k),w_k right) +mathbb{E}_{w_{k+1},...,w_{N-1}}left( sum_{j=k+1}^{N-1}{g_jleft( x_j,mu _jleft( x_j right) ,w_j right)}+g_Nleft( x_N right) |x_{k+1} right) |x_k right)$

$=underset{mu _k,...,mu _{N-1}}{min }mathbb{E}_{w_k}left( g_kleft( x_{k,}mu _k(x_k),w_k right) +J_{k+1}left( f_kleft( x_k,mu _kleft( x_k right) ,w_k right) ;mu _{k+1},...,mu _{N-1} right) |x_k right)$

$=underset{mu _k}{min } mathbb{E}_{w_k}left( g_kleft( x_{k,}mu _k(x_k),w_k right) +J_{k+1}^{*}left( f_kleft( x_k,mu _kleft( x_k right) ,w_k right) right) |x_k right)$

这表明,随机动态规划与确定性动态规划具有一样的backward递推关系,因此我们可以同样定义Q-factor:

$Q_{k}^{*}left( x_k,u_k right) =mathbb{E}_{w_k}left( g_kleft( x_{k,}u_k,w_k right) +J_{k+1}^{*}left( f_kleft( x_k,u_k,w_k right) right) |x_k right)$

即状态 x_k 下执行 u_k 后的最小尾部问题损失，从而:

$J_{k}^{*}left( x_k right) =underset{u_kin mathrm{U}_kleft( x_k right)}{min }Q_{k}^{*}left( x_k,u_k right)$

$Q_{k}^{*}left( x_k,u_k right) =mathbb{E}_{w_k}left( g_kleft( x_{k,}u_k,w_k right) +underset{u_{k+1}in mathrm{U}_{k+1}left( f_kleft( x_k,u_k,w_k right) right)}{min }Q_{k+1}^{*}left( f_kleft( x_k,u_k,w_k right) ,u_{k+1} right) |x_k right)$

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

(i) 从 $J_{N}^{*}left( x_n right) =g_Nleft( x_n right)$ 出发,backward递推,求解函数序列 $left{ J_{0}^{*},...,J_{N}^{*} right}$

(ii) 正向决策: $mu _{k}^{*}left( x_k right) =underset{u_kin mathrm{U}_kleft( x_k right)}{mathrm{arg}min}Q_{k}^{*}left( x_k,u_k right)$

此时 $pi ^*=left{ mu _{0}^{*},...,mu _{N-1}^{*} right}$ 是问题的最优策略。

三. 一些变种问题与思想

1.状态空间 $mathcal{X}_k$ 的构造技巧:

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

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

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

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

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

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

2. uncontrollable state components

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

→ 观测 x_k

→ 产生 $y_ksim mathbb{P}_kleft( cdot |x_k right)$ 得到完整状态 (x_k,y_k)

→ 根据策略生成控制变量 u_k=mu_k(x_k,y_k)

→ 产生随机扰动 w_k

→ 状态转移至 $x_{k+1}$

俄罗斯方块游戏便是这样一个例子。我们可以定义 x_k

为当前游戏的棋盘。

是下一个要降落的方块的形状。显然 y_k

只依赖于

,不受

影响。并且观测到

后才是真正的状态

，组成了下一步决策的全部信息。

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

$x_{k+1}=f_kleft( x_k,y_k,u_k,w_k right)$

cost at time k =g_k(x_k,y_k,u_k,w_k)

(x_k,y_k) 下的最优cost-to-go function:

$J_{k}^{*}left( x_k,y_k right) =underset{mu _k}{min},,mathbb{E}_{w_k,y_{k+1}}left( g_kleft( x_{k,}y_{k,}mu _k(x_k,y_k),w_k right) +J_{k+1}^{*}left( f_kleft( x_k,y_k,mu _kleft( x_k,y_k right) ,w_k right) ,y_{k+1} right) |x_k,y_k right)$

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

$hat{J}_kleft( x_k right) =mathbb{E}_{y_k}left( J_{k}^{*}left( x_k,y_k right) |x_k right)$

$=mathbb{E}_{y_k}left{ underset{mu _k}{min},,mathbb{E}_{w_k,y_{k+1}}left( g_kleft( x_{k,}y_{k,}mu _k(x_k,y_k),w_k right) +J_{k+1}^{*}left( f_kleft( x_k,y_k,mu _k(x_k,y_k),w_k right) ,y_{k+1} right) |x_k,y_k right) |x_k right}$

$=mathbb{E}_{y_k}left{ underset{mu _k}{min},,mathbb{E}_{w_k}left( g_kleft( x_{k,}y_{k,}mu _k(x_k,y_k),w_k right) +mathbb{E}_{y_{k+1}}left( J_{k+1}^{*}left( x_{k+1},y_{k+1} right) |x_{k+1} right) right) |x_k right}$

$=mathbb{E}_{y_k}left{ underset{mu _k}{min},,mathbb{E}_{w_k}left( g_kleft( x_{k,}y_{k,}mu _k(x_k,y_k),w_k right) +hat{J}_{k+1}left( f_kleft( x_k,y_k,mu _k(x_k,y_k),w_k right) right) right) |x_k right}$

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

3. belief state 与 partial state information

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

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

$x_ksim mathbb{P}_kleft( cdot |x_0,....,x_{k-1};u_0,...,u_{k-1} right)$

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

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

$mathbb{P}_kleft( cdot |x_0,....,x_{k-1};u_0,...,u_{k-1} right) =mathbb{P}left( cdot |theta _k right)$

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

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

文章地址: http://www.xdqxjxc.cn/duhougan/128629.html

文章标签：动态规划强化学习 (Reinforcement Learning) 读书笔记

[《Reinforcement Learning and Optimal Control》读书笔记 (一): CH1. 精准动态规划 Exact Dynamic Programming] 相关文章推荐：

2023-11-24 11:00:14写好读书笔记对写作有哪些帮助
2023-11-09 01:01:18读书笔记的摘要和主要内容概述的区别
2023-10-30 19:00:44读书笔记对于阅读的重要性体现在哪里
2023-10-18 13:00:23用平板做读书笔记，推荐哪个软件
2023-09-20 11:00:39读书笔记就是摘抄句子吗
2023-08-29 17:01:33写读书笔记可以抄正在学的课文吗
2023-08-03 11:01:44你对读书笔记或者日记这种手写文字有怎样的认知是不是和我一样有一种戒不掉的隐你知道为什么么
2023-07-14 19:00:23如何写读书笔记，
2023-06-30 23:00:14如何教三年级学生学会写读书笔记
2023-06-29 12:01:30怎样引导孩子写读书笔记的感悟思考

最新读后感

热门读后感

Top

全站搜索

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

为什么要在知乎上分享笔记

一. 确定性动态规划 Deterministic Dynamic Programming

1.问题建模

2. 问题目标

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

4. 问题求解算法

5. Q-factor

二. 随机动态规划 Stochastic Dynamic Programming

三. 一些变种问题与思想

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

2. uncontrollable state components

3. belief state 与 partial state information

[《Reinforcement Learning and Optimal Control》读书笔记 (一): CH1. 精准动态规划 Exact Dynamic Programming] 相关文章推荐：

1.状态空间 $mathcal{X}_k$ 的构造技巧: