Lecture 3: Planning by Dynamic Programming

一、Introduction

（一）什么是动态规划（Dynamic Programming）

Dynamic：问题的动态顺序或时间成分
Programming：优化“程序”，即policy
我们认为问题是拥有某种时间或顺序方面的特性，也就是问题一步接一步地进行改变，我们尝试某些特殊的步骤来解决这些问题。
数学规划：线性规划或二次规划，它的含义就是像数学家一样，使用程序优化程序，它实质上指的就是一种policy。案例：从状态到动作的映射开始，然后你不断优化程序，以采取最优行为。

解决复杂问题的方法
通过将它们分解为子问题
- 解决子问题
- 结合解决子问题

（二）动态规划的要求

对于具有两个属性的问题，动态规划是一种非常通用的解决方案：

最优化结构

应用最优原理
最优解可以分解为子问题

最优化结构的含义是我们刻意将某些整体性问题分解为两个或多个子问题，在得到子问题的最优解后我们也就知道了整体问题的最优解。

重叠子问题

子问题重复出现多次
解决方案可以缓存和重用

我们不会对不满足以上两个条件的问题使用动态规划

马尔可夫决策过程同时满足这两个属性

贝尔曼方程提供递归分解
值函数存储和重用解决方案
缓存我们目前找到的MDP的最优值信息，通过value function可以找到任一状态出发的解决方法，可以找到最优的行动方式

（三）Planning by Dynamic Programming

动态规划假定您完全了解MDP
知道MDP的结构，MDP中的动态变化和奖励，完全了解环境的工作原理。
用于MDP中的计划
对于预测来说:
- Input:MDP $\left\langle S,A,P,R,\gamma\right\rangle$ and policy $\pi$
- or:MRP $\left\langle S,P^\pi,R^\pi,\gamma\right\rangle$
- Output:value function $v_\pi$
  在知道policy的情况下球的更多的奖励
或者对于control
- Input:MDP $\left\langle S,A,P,R,\gamma\right\rangle$
- Output:value function $v_\pi$
- and:最优policy $\pi_*$
  我们并不知道policy，我们想知道在所有的policy中选择哪一个才会在MDP中得到最多的奖励。

（四）动态规划的其他应用

动态规划用于解决许多其他问题，例如：

调度算法
字符串算法（如：序列比对）
图算法（如：最短路径算法）
图模型问题（如：Viterbi algorithm）‘
生物信息学（如：晶格模型）

二、Policy Evaluation

（一）Iterative Policy Evaluation

问题：评估给定的策略 $\pi$
解决方案：Bellman期望备份的迭代应用
$v_1\rightarrow v_2\rightarrow ...\rightarrow v_\pi$
使用同步备份
- 在每次迭代k + 1
- 对于所有状态 $s\in S$
- 从 $v_k(s')$ 更新 $v_{k+1}(s)$
- 其中 $s’$ 是 $s$ 的后继状态
稍后我们将讨论异步备份
讲座结束时将证明 $v_\pi$ 的收敛

使用贝尔曼方程来评估policy，解决control问题，你知道了MDP和policy，采取这个policy奖励会是多少。

$v_1$ 是一个向量，也就是MDP的value，从某个初始的value开始，一般初始取0（0表示我们没有在任何地方得到任何指令），接下来每一步都要用贝尔曼方程，向前看一步，就能找到一个新的value函数 $v_2$ ，迭代多次，得到真正的value函数。

（二）Iterative Policy Evaluation（2）

image.png

为了实现动态规划我们将会将这个方程转化为迭代更新操作。
我们在叶节点存储我们先前迭代的value，然后就可以求得下一次迭代的value。
将k迭代产生的值插入到叶节点，通过存储的这些值，我们就能计算出路径下一次迭代产生的一个新value

（三）Evaluating a Random Policy in the Small Gridworld

在小型网格世界中评估随机策略

没有折扣情况的MDP（ $\gamma=1$ ）
非终端状态 1,...,14
一个终端状态（以阴影正方形显示两次）
退出网格的动作保持状态不变
直到达到最终状态，奖励为-1
agent遵循统一的随机策略

image.png

（四）Iterative Policy Evaluation in Small Gridworld

image.png

-1.7如何得到？
应用公式

image.png

在本问题中，公式中,,,（因为执行一个action只能到达一个状态）
向北走：得到即时奖励-1，回到原地，加上上一步原地的value为-1，
向南走：得到即时奖励-1，到下个状态，加上上一步该状态的value为-1，
向西走：得到即时奖励-1，到下个状态，加上上一步该状态的value为0，
向东走：得到即时奖励-1，到下个状态，加上上一步该状态的value为-1，
将上述四项加到一块，

image.png

右边的policy是根据左边的value值，应用贪婪算法得到的，可以发现到最后policy是可以收敛的，因为k=3的时候policy就不再改变。

三、Policy Iteration

（一）如何改进policy

提供一个policy
- 评估policy $\pi$
- 应用贪婪的方法来改进policy $\pi$
在Small Gridworld中，改进策略是最佳的， $\pi'=\pi^*$
一般而言，需要进行更多迭代的改进/评估
但是，此策略迭代过程始终收敛于 $\pi^*$

无论你从哪里开始，无论你的value函数是什么、policy是什么，最终你总会得到最优的value函数和最优的policy。

示例：杰克的租车

States：两个地点，每个地点最多20辆车
Actions：一夜之间在各地点之间最多可移动5辆汽车
Reward：每辆租车$ 10（必须可以得到）
Transitions：汽车归还和请求是随机的
- 泊松分布，n个归还/请求，概率为 $\frac{\lambda^n}{n!}e^{-\lambda}$
- 第一个位置：平均请求数= 3，平均归还= 3
- 第二个位置：平均请求数= 4，平均归还= 2
  
  policy轮廓图，数字表示从一个位置往另一个位置移动几辆车
  
  首先是一个随机policy，然后用value function，然后用value function得到new policy，然后再用value function评估，然后得到更新的policy，然后再评估，最终得到最优policy。

（二）Policy Improvement

考虑一个确定性策略， $a =\pi(s)$
我们可以通过贪婪的方法改进这个策略
这就可以一步提高任何状态s的值

找到使得q的值最大的action，这个action比之前一个特定的action要好。
因此，它改善了价值函数， $v_\pi'(s)\geq v_\pi(s)$
如果改进停止
然后满足Bellman最优方程
因此对所有的 $s\in S$ , $v_\pi(s)=v_*(s)$
所以 $\pi$ 是最优policy

（三）Extensions to Policy Iteration

1、Modified Policy Iteration

修改的策略迭代
基本思想：提前停止迭代

policy评估需要收敛到 $v_\pi$ 吗？
还是应该引入停止条件
- 例如value function 的 $\varepsilon-convergence$
还是在k次迭代策略评估后停止？
例如，在小型网格世界中，k = 3足以实现最佳策略
为什么不每次迭代都更新策略？即在k = 1之后停止
- 这等效于值迭代（下一部分）

2、Generalised Policy Iteration

广义策略迭代

policy evaluation algorithm、policy improvement algorithm不再是固定的，可以用任意的算法

四、Value Iteration

（一）Value Iteration in MDPs

1、Principle of Optimality(最优原则)

任何最佳策略都可以细分为两个部分

最佳的第一个动作 $A_*$
紧随后继状态S'的最优策略

定理（Principle of Optimality）
一个策略 $\pi(a|s)$ 从状态s获得最佳值, $v_\pi(s)=v_*(s)$ ,当且仅当
从 $s$ 可到达的任意状态 $s'$
$\pi$ 从状态 $s'$ 获得最佳值， $v_\pi(s’)=v_*(s')$

2、Deterministic Value Iteration（确定性值迭代）

如果我们知道子问题 $v_*(s')$ 的解决方案
然后可以通过一步查找来找到解决方案 $v_*(s)$
价值迭代的思想是迭代地应用这些更新
直觉：从最终的奖励开始，然后倒退
仍适用于循环的，随机的MDP

3、Example: Shortest Path

应用此公式进行计算

每移动一步得到的奖励为-1，，
因为每个action只能到唯一一个后继状态，

-1=max{
向北：即时奖励-1，加上回到原地的上个状态value=0，相加为-1；
向南：即时奖励-1，加上到达的下个格子的上个状态value=0，相加为-1；
向西：即时奖励-1，加上到达的下个格子的上个状态value=0，相加为-1；
向东：即时奖励-1，加上到达的下个格子的上个状态value=0，相加为-1；}
-2=max{
向北：即时奖励-1，加上回到原地的上个状态value=-1，相加为-2；
向南：即时奖励-1，加上到达的下个格子的上个状态value=-1，相加为-2；
向西：即时奖励-1，加上到达的下个格子的上个状态value=-1，相加为-2；
向东：即时奖励-1，加上到达的下个格子的上个状态value=-1，相加为-2；}
-3=max{
向北：即时奖励-1，加上回到原地的上个状态value=-2，相加为-3；
向南：即时奖励-1，加上到达的下个格子的上个状态value=-2，相加为-3；
向西：即时奖励-1，加上到达的下个格子的上个状态value=-2，相加为-3；
向东：即时奖励-1，加上到达的下个格子的上个状态value=-2，相加为-3；}
-3=max{
向北：即时奖励-1，加上到达的下个格子的上个状态value=-5，相加为-6；
向南：即时奖励-1，加上回到原地的上个状态value=-5，相加为-6；
向西：即时奖励-1，加上到达的下个格子的上个状态value=-5，相加为-6；
向东：即时奖励-1，加上到达的下个格子的上个状态value=-5，相加为-6；}
-6=max{
向北：即时奖励-1，加上回到原地的上个状态value=-5，相加为-6；
向南：即时奖励-1，加上到达的下个格子的上个状态value=-2，相加为-6；
向西：即时奖励-1，加上回到原地的上个状态value=-5，相加为-6；
向东：即时奖励-1，加上到达的下个格子的上个状态value=-2，相加为-6；}

4、Value Iteration

问题：找到一个最优的policy $\pi$
方法：迭代应用贝尔曼最优备份（Bellman optimality backup）
$v_1\rightarrow v_2\rightarrow ... \rightarrow v_*$
用同步备份（synchronous backups）
- 在每个迭代 $k+1$
- 对于每个states $s\in S$
- 从 $v_k(s')$ 更新 $v_{k+1}(s)$
收敛到 $v_*$ 稍后将证明.
与policy Iteration 不同，这里没有明确的policy
中间值函数（value function）可能不符合任何policy

我们认为value function是对所有子问题的兑现方案，最优的value是来自 $s'$ ,有人告诉我们，我会从那个状态获得多少奖励，现在问题是我们该如何利用这些信息来构造一个先前那一步骤的最优value函数，我们需要做的是向前看一步，为了构造这棵树我们使用了贝尔曼最优方程。

我们来看看这棵树的树叶，树叶将他们存储起来，我们归纳的前提是：我们的最优解来自于我们的树叶，我们将这个存储起来我们最大化的所有的东西，那么在根处，我们就得到了最优值，value迭代的思想是不断地重复更新，从任意值开始，我们会很直观的找到答案，把这个存储起来，我们就得到了一个新的value函数，存储新的value函数得到更好的value函数。

5、Example of Value Iteration in Practice

http://www.cs.ubc.ca/~poole/demos/mdp/vi.html

6、Synchronous Dynamic Programming Algorithms（同步动态规划算法）

算法基于状态值函数 $v_\pi(s)$ 或 $v_*(s)$
对于m个动作和n个状态，每次迭代的复杂度 $O(mn^2)$
n种状态，每个状态可以执行m个action，每个action又可能有n个后继状态。
还可应用与action-value函数 $q_\pi(s,a)$ 或q_*(s,a)
每次迭代的复杂度 $O(m^2n^2)$
总共有mn个每个action-value对，后继有mn个action-value对，所以为 $m^2n^2$

五、Extension to Dynamic Programming

（一）Asynchronous Dynamic Programming

异步动态编程

到目前为止介绍的DP方法使用了同步备份
即所有状态都并行备份
异步DP以任何顺序分别备份状态
一般来说，你可以挑选任何state，并将该state进行备份。你可以立即行动，可以立即插入你的新的value函数，它会在底部进行备份，你并不需要等待全部状态更新完。你需要更新的是单一的状态，而不是整个状态空间。
对于每个选定状态，应用合适的备份
可以大大减少计算
如果继续选择所有状态，则保证收敛
不管你选择的顺序是怎么样的，只要你持续选择，那么你的算法都会收敛到最优value函数。

异步动态规划的三个简单思路：

In-place dynamic programming
Prioritised sweeping
Real-time dynamic programming
实时动态规划

1、In-Place Dynamic Programming

Synchronous value iteration存储值函数的两个副本
对于S中的所有s
In-place value iteration仅存储值函数的一个副本
对于S中的所有s

放弃了区分新的和旧的，将它进行扫描，然后无论我们的次序是什么，我们总是使用最新的版本，我们会即时更新我们的value函数，无论我们到了哪一种状态，我们将会使用的是最新的value，因为最新的value包含更多的信息，会更高效。
唯一的问题是你该如何安排state的次序，才能以最有效的方式进行计算。这表明知道问题的某些状态，你可以更加高效的进行计算。它就像一条长廊，我们扫描到了那个状态，即该状态是目标朝向了我们源方向，这说明迭代通过一次扫描所有的状态，我们就能找到最佳的解决方案。你不需要进行不同的扫描，因为你是从目标出开始的，你找到了目标的最优值，你回退一步，现在你插入的最新的value，然后再该状态再回退一步，插入最新value，再回退......。一直使用最新的估计来进行更新，这样会更加高效。加入你扫描到其他东西，那么你什么都不会得到。因此，排序真的很重要。

2、Prioritised Sweeping

思想：找到评估MDP状态重要性的标准。现在我们知道了你可以以任何顺序更新你的状态。我们应该首先更新哪些状态呢？
我们来组织一个优先级序列，来看看哪个状态相较于其他状态更好。我们会以某种顺序进行更新，依据就是state的重要性。

使用Bellman误差的幅度指导状态选择

我们的直觉告诉我们，改变最多的state，比如：更新之前该状态value是0，更新之后value状态为1000，这将会对之后的计算产生巨大的影响。
备份保存的Bellman误差最大的状态
每次备份后更新受影响状态的Bellman误差
需要了解逆向动态（先前状态）
通过组织优先级队列可以有效地实现

3、Real-Time Dynamic Programming

思想：选择那些agent真正访问过的state。我们并不是简单的扫描所有的东西，实际上是，在真实环境中运行一个agent，搜集真正的样本，使用来自某个轨迹的真正的样本。

想法：仅与agent相关的状态
运用agent的经验来指导状态的选择
在每个时间步 $S_t，A_t，R_{t + 1}$ 之后
备份状态 $S_t$

（二）Full-width and sample backups

1、Full-Width Backups

DP使用full-width备份
对于每个备份（同步或异步）
- 每个后继的状态和动作都被考虑
- 使用有关MDP转换和reward function的知识
DP对中等规模的问题（数百万个状态）有效
对于大问题，DP受到贝尔曼的维数诅咒
- 状态数 $n = |S|$ 随状态变量数呈指数增长
即使一次备份也可能太昂贵

2、Sample Backups

在随后的课程中，我们将考虑样本备份
使用sample rewards and sample transitions $\left\langle S,A,R,S'\right\rangle$
代替reward function $R$ 和transition dynamics $P$
Advantages:
- Model-free：无需MDP的先验知识
- 通过采样打破维数的诅咒
- 备份成本是恒定的，与 $n = |S|$ 无关

3、Approximate Dynamic Programming

近似value function
使用函数逼近器 $\widehat v(s,W)$
将动态规划应用于 $\widehat v(\cdot,W)$
例如:拟合值迭代在每个迭代k重复一次，
- Sample states $\widetilde S\subseteq S$
- 对于每个状态 $s\in\widetilde S$ ，使用Bellman最优方程估算目标值
  
  使用目标 $\{\left\langle s,{\widetilde v}_k(s)\right\rangle\}$ 训练下一个value function $\widehat v(\cdot,w_{k+1})$

六、Contraction Mapping

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,732评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,496评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,264评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,807评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,806评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,675评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,029评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,683评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 41,704评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,666评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,773评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,413评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,016评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,204评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,083评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,503评论 2赞 343

Lecture 3: Planning by Dynamic Programming

一、Introduction

（一） 什么是动态规划（Dynamic Programming）

（二）动态规划的要求

（三）Planning by Dynamic Programming

（四）动态规划的其他应用

二、Policy Evaluation

（一）Iterative Policy Evaluation

（二）Iterative Policy Evaluation（2）

（三）Evaluating a Random Policy in the Small Gridworld

（四）Iterative Policy Evaluation in Small Gridworld

三、Policy Iteration

（一）如何改进policy

示例：杰克的租车

（二）Policy Improvement

（三）Extensions to Policy Iteration

1、Modified Policy Iteration

2、Generalised Policy Iteration

四、Value Iteration

（一）Value Iteration in MDPs

1、Principle of Optimality(最优原则)

2、Deterministic Value Iteration（确定性值迭代）

3、Example: Shortest Path

4、Value Iteration

5、Example of Value Iteration in Practice

6、Synchronous Dynamic Programming Algorithms（同步动态规划算法）

五、Extension to Dynamic Programming

（一）Asynchronous Dynamic Programming

1、In-Place Dynamic Programming

2、Prioritised Sweeping

3、Real-Time Dynamic Programming

（二）Full-width and sample backups

1、Full-Width Backups

2、Sample Backups

3、Approximate Dynamic Programming

六、Contraction Mapping

推荐阅读更多精彩内容

（一）什么是动态规划（Dynamic Programming）