David silver强化学习课程第三课 动态规划
第三课 动态规划
本章主要讲了利用动态规划解决MDP的预测和控制两个问题。策略评估用来解决预测问题，策略迭代和值迭代用来解决控制问题，这都是建立在已知完整信息的MDP问题当中。
1 动态规划简介
动态：指的是该问题的时间序贯部分
规划：指的是去优化一个策略
那么哪些问题可以用动态规划求解呢？需要满足两个特性：
- 最优子结构：求解问题可以分解为求解若干个子问题，子问题最优解构成了问题的最优解
- 重叠子问题：子问题重复出现多次，可以缓存并重用子问题的解
MDP恰好满足以上两个特性，贝尔曼方程给出了问题的迭代子问题；值函数可以存储并重用。动态规划用来求解已知全部信息的MDP问题，也就是第一课提到的Planning。动态规划可以用来解决预测和控制两个问题：
预测：
控制：
2 迭代策略评估
策略评估就是评价一个策略π的好坏，具体是通过值函数表现出来，也就是说我们需要计算策略π下的状态值函数或状态动作值函数。迭代策略评估用来解决预测问题。
迭代的使用贝尔曼期望方程进行backup，这里的backup有人翻译成反向更新，有人翻译成回溯，个人觉得回溯更准确一些。
同步backup算法（使用t时刻的v(s‘)更新t+1时刻的v(s)，这里是对某一时刻的所有s的值函数进行更新并备份)：
本节后面会讨论异步backup
具体更新公式如下这里对于某个策略π，进行多次backup后状态值将收敛，最终得到的值才评价了策略π的好坏：
3 策略迭代
如何改善提略
在预测问题中，我们利用迭代策略评估评价了某个策略的好坏程度。那么我们如何改进已知的策略，使得状态值函数更大，最终获得最优状态值函数？
在这里，课程提到通过对于old policy的值函数采用贪婪法(greedy)即可得到改进的策略:
首先利用迭代策略评估计算状态值函数，接着为每个状态选取使状态值函数最大的动作，也就是选取该状态下q(s,a)最大的那个a（这里采取状态动作值更好理解）。反复利用这两个步骤，π‘将会收敛到π*。
下面证明为什么采取贪婪策略后π’优于π：
贪婪选取的策略总是优于之前的策略的，这一点可以通过状态值看出来：选取q(s,a)最大的那个动作带来的v(s)值总是大于等于原来v(s)的期望值的。不断地进行迭代策略评估和贪婪策略改善，策略会不断改善直到上述式子变成等号，根据贝尔曼最优方程，说明策略已经是最优策略。
策略迭代：基于贝尔曼期望方程，反复的进行策略评估和策略改善(greedy)，最终收敛到最优策略。策略迭代用于解决控制问题。
策略评估会消耗大量的时间，每一次策略评估都需要收敛到vπ吗？例如课程给的例子，随机策略的第三次迭代和第10次迭代产生的状态值函数得到的贪婪策略是一样的，如图：
有时候不需要持续迭代至最有价值函数，可以设置一些条件提前终止迭代，比如设定一个Ɛ，比较两次迭代的价值函数平方差；直接设置迭代次数；以及每迭代一次更新一次策略等。
4 价值迭代
最优原则
一个最优策略可以被分为两部分：
- 从状态s到下一个状态s’采取了最优行为A*
- 在状态s’时遵循一个最优策略。
一个策略使状态s获得最优价值，当且仅当对于从状态s可以到达的任何状态s’，该策略能够使得状态s’的价值是最优价值：
价值迭代：利用贝尔曼最优方程进行backup，不断更新状态值，直至收敛。
同步backup：
更新公式：
策略迭代和价值迭代的区别：
- 策略迭代中策略评估步骤一般需要进行n次迭代得到vπ，交叉策略提升进行k次，得到π*；而价值迭代需要迭代k次得到v*，进而得到*。
- 策略迭代有显示的策略（贪婪策略）,价值迭代没有显示的策略。
- 策略迭代利用贝尔曼期望方程和贪婪策略，价值迭代利用贝尔曼最优方程进行迭代。
5 同步动态规划总结
上面所讲的方法都是适用于同步动态规划，也就是说每个时刻利用上一时刻的状态值函数更新本时刻的所有状态的值函数，包括状态值函数和状态动作值函数。使用状态价值函数或行为价值函数两种价值迭代的算法时间复杂度都较大。一种改进方案是使用异步动态规划，其他的方法放弃使用动态规划，随后的几讲中将详细讲解其他方法。
6 动态规划扩展
异步动态规划
同步动态规划中所有的状态一起进行backup，而异步动态规划则是将所有states独立进行backup，并且是以任意顺序。异步动态规划可以减少计算量，不过如果想要收敛，则需要满足一个条件：所有状态都需要能够持续被选择，或者说，在任一时刻，任何状态都有可能被选中。异步动态规划主要有三个简单的方式：
-
原位动态规划（In-place dynamic programming）
同步值迭代存储值函数的两个副本，而in-place值迭代存储值函数的一个副本，也就是说在backup时，有用到vk也有用到vk+1,更新方式如下：
-
重要状态优先更新（Prioritised sweeping）
对那些重要的状态优先更新，使用Bellman error：
来确定哪些状态是比较重要的。Bellman error 反映的是当前的状态价值与更新后的状态价值差的绝对值。Bellman error越大，越有必要优先更新。对那些Bellman error较大的状态进行备份。这种算法使用优先级队列能够较得到有效的实现。
-
实时动态规划（Real-time dynamic programming）
实时动态规划的思想是只有代理现在关注的状态会被更新。与当前无关的状态暂时不被更新。有些状态虽然理论上存在，但在现实中几乎不会出现。比如在时间步St，At，Rt+1，仅仅backup状态St：
采样backup
动态规划使用的是full-width backups，所有继承的状态和动作都被考虑到，因此在面对大型的问题时，会出现贝尔曼维度灾难。为了解决这一问题，可以用sample backup代替full-width backups。有三个优点：
- model-free：不需要知道MDP的全部信息
- 避免维度灾难
- 计算开销是常数，与状态数无关
近似动态规划
7 收缩映射定理
课程没有仔细讲这块内容，但是参考其他博主的博客了解到这个定理用来证明策略迭代、值迭代的收敛性。可以参考https://www.leiphone.com/news/202001/y5nyxtWsNUrm37a9.html，用数学理论证明了对于任何有限的MDP，都存在一个最佳策略π*，满足其他所有可能的策略π都不会比这个策略更好。
参考资料：https://blog.****.net/u013745804/article/details/78196834
https://zhuanlan.zhihu.com/p/55788587