第四章：动态规划
动态规划是指一类在MDP下对环境有完全建模的计算最优策略的算法。经典的DP算法在强化学习中应用有限，不仅是因为需要对环境进行完全建模，而且还需要很多的计算资源。但是这个算法在理论上依然很重要。实际上，书中后面章节的所有算法都可以看成想要使用更少的计算资源而且不需要对环境完全建模的尽可能达到DP的效果的尝试。
一般我们假设环境是有限状态MDP。尽管动态规划也可以应用到连续状态和连续动作的场景中，但是我们一般会将状态和动作进行离散化，之后应用有限状态动态规划算法进行近似。第九章讲解这些算法。
DP或者说强化学习的核心思想是利用值函数来组织和结构化对策略的搜索。本章会介绍通过获得满足贝尔曼最优等式（下图）的值函数
或者
来很容易得出最优策略的算法。我们将会看到，DP算法会通过对类似下式的等式进行调整为赋值等式来对其值函数进行更新，最终进行优化和近似得到想要的值函数。
4.1 Policy Evaluation(Prediction)
首先我们考虑如何在策略
下计算状态值函数
。这个方法在DP中叫做policy evaluation，也叫作prediction problem。回忆一下第三章中值函数v的贝尔曼公式，下标表示遵从该策略，
表示该策略状态s采取a的概率。只要是满足
或者在策略下有一个结束状态，那么v的存在性和唯一性就能得到保证。
如果环境的状态转移分布是完全已知的，那么公式4.4就相当于对状态空间中的
个状态每个都有一个等式，同时也有这么多未知数，理论上可以直接解出结果。假如有一个值函数估计值的序列，
每个都代表从状态到一个实数的映射，那么根据贝尔曼等式我们可以得到如下连续递推估计的更新规则：
显然当
趋近于的时候等式收敛。这个算法叫做policy evaluation。为了更新对值函数的估计值，循环policy evaluation对于每个状态的操作都是一样的，使用下一状态的旧的v以及转移到下一状态得到反馈的期望得到本状态的一个新的估计值，并用其来替代旧的估计值。这种操作叫做expected update，因为使用的都是期望值而不是一个采样来更新状态函数。所有的值更新都可以很自然的使用一个等式或者一个backup diagram来展示其中的过程。
一般为了在计算机中完成这个算法，需要保有两个序列，一个是旧的状态值函数，一个是新的值函数。这样新的值函数才能够一直利用旧的值来进行迭代。但是这是不必要的，我们可以直接使用一个序列保有所有的值函数，因此有时新得到的状态值会立马被用到状态更新中。这样依然能够保证算法的收敛性，实际上经常会收敛得更快。一般我们讨论DP算法的时候用的都是这种inplace的形式。
以下是policy evaluation的算法伪代码：
练习4.1 -1 -15
练习4.2 -12 -20（和原来的状态13一样）
练习4.3 
4.2 Policy Improvement
计算值函数的目的是为了找出一个更好的策略。假设我们有一个确定性策略，想知道在某些特定的状态我们是否需要选择一个和
不一样的动作a。已知当前策略下选择该动作的值，但是进行调整选择别的动作是否会得到更好或更坏的结果呢？可以选择在状态s下选择动作a，之后再根据策略来进行选择动作，这样可以得到一个状态动作值函数：
最重要的判断方式就是判断这个值是否会大于值函数
。加入这个q更大，那么说明在状态s时选择动作a是一个比在状态s时根据策略进行选择的更好的策略。这是一个policy improvement theorem的泛化理论的一个特殊例子。加入有两个确定性策略和
，假如他们在每个状态
都满足 
那么就可以推出
。具体推导不贴了，在书上，一个简单的放缩。很自然地我们会想到，在每一个状态s时根据状态动作值函数
选择当前表现最好的动作a。也就是得到一个新的策略
这个新的贪心策略其它状态时都遵循策略，但是在当前状态s时根据进行一步搜索得到当前最优的动作a。这样构造使得新的策略与旧的策略能够满足policy improvement theorem的要求。这样在一个旧的策略基础上不断进行改进，使得新的策略在旧策略的值函数基础上得到一个贪心的结果，这个过程叫做policy improvement。
加入有一个新的贪心策略是和老策略一样好但是没有更好，也就是
，根据4.9又得出其满足如下方程：
但这个方程和贝尔曼最优等式是相同的，因此新策略和旧策略都等于最优策略
（贝尔曼最优等式有唯一解）。也就是说这个policy improvement 算法一定会不断改进算法直到其收敛至最优策略。
目前为止我们在本章讨论的都是确定性策略，对于随机策略有一个概率
来表示在状态s时采取动作a的概率。实际上这些思想可以很容易应用到随机性策略中。特别的是如果一个状态有好几个同样取得最大反馈的动作时，可以平均分配概率给这几个动作而不用随机取其中一个，只要是其它非最优动作分配的概率为0即可。
4.3 Policy Iteration
一旦一个策略被使用改进得到了一个新的策略那么就可以计算出新的值函数
。根据新的值函数又可以进行改进得到更好的策略
，如此循环往复直到达到最优策略。因为一个有限状态MDP只有有限数量的策略，因此这个过程一定会在有限步之内得到最优策略和最优值函数。这个方式叫做policy iteration。具体的算法如下表示，需要注意在进行新策略的policy evaluation的过程中初始v是使用的上一个旧策略的值函数，这样可以加速收敛。PI通常在几次迭代中就会收敛。
练习4.4 在3.中第一个if里加入判断q(s,oldaction) < q(s, )。只有两个条件同时成立才把policy-stable赋为false。
练习4.5 把v值的更新改为q值的更新。选择新策略时根据q的最大化。有点疑惑这样是否能够遍历所有状态动作对。
练习4.6 1.不用改 2. v值更新改为期望形式 3.策略更新改为最大化期望v
4.4 Value Iteration
policy Iteration的一个缺点在于每次进行policy evaluation的时候需要很多步迭代，而每步迭代都要遍历所有的状态s。policy evaluation的过程只会在最后才会收敛，但是我们也许不用等到其收敛才进行policy improvement，而同样也能够达到最终的收敛。其中一个最重要的例子就是每一次进行policy evaluation的遍历之后都进行一次policy improvement，这个算法叫做value Iteration。可以通过一个很简单的更新形式表示其更新过程，只要最优值存在那么这个算法也就可以保证收敛至最优：
另一种理解这个算法的形式是通过把贝尔曼最优等式直接改写为更新规则。同样需要提到的是，value Iteration的更新过程和policy evaluation是一样的，除了每次value Iteration进行了一次取最大值。另一种观察这种关系的方式是画出他们的backup diagrams，左边是policy evaluation 右边是value Iteration。
value Iteration具体的算法伪代码如下：
value Iteration实际上是在每一次遍历的过程中对每个状态都结合了policy evaluation和policy improvement。在每一次遍历policy improvement中间交替使用几次遍历policy evaluation通常会更快得到收敛效果。大体上说这类交替算法可以被看成是一个状态遍历的序列，其中几个是policy evaluation，跟着几个policy improvement。这些算法都会在discounted有限MDP中收敛至最优策略。
练习4.8 不太会
练习4.10 
4.5 Asynchronous Dynamic Programming
目前为止讲的几个DP算法的一个主要的缺陷是这些算法都需要遍历所有的状态空间。如果状态空间很大，那么一次遍历就可能过去很长时间而策略都得不到及时更新。异步DP算法主要是使用非系统性遍历所有状态空间的in-place DP算法。这些算法不关心每个状态值函数的更新顺序，某些状态的值可能比其它状态的值更新快好几倍。但是异步算法依然需要更新所有状态的值函数之后才能够达成正确的收敛，也就是不能忽略某些状态值函数的计算。但是异步DP算法能够灵活选择需要进行更新的状态。
可以将一些不同的更新方式灵活的用在不需要进行遍历操作的DP算法中。但是避免了遍历并不意味着减少了计算量 ，它只是意味着我们不需要在策略有改进之前陷入长时间的状态遍历中，也就是选择需要更新的状态来加速算法的运算过程。因为某些状态可能不需要像其它状态那样更新那么多次。
异步算法同样能够使得实时交互与计算过程之间的混合更加容易。我们可以在一个agent实时经历一个MDP过程的同事运行一个迭代DP算法，agent的经历可以用来决定算法需要更新哪些状态的值函数。同时DP算法中产生的最新值函数和策略也能够指引agent进行决策。这样能够重点关注哪些和agent最相关的那部分状态，这种重点关注是强化学习中不断出现的主题。
4.6 Generalized Policy Iteration
Policy iteratation又两个实时交互的过程组成，一个是让值函数与当前策略一致（policy evaluation），另一个是让策略在当前的值函数下保持最优（policy improvement）。在policy Iteration的过程中这两个过程交替进行，一个执行完才执行另一个，但这不是必要的。比如在value iteration中每次policy improvement之间只执行了一次policy evaluation。在异步DP算法中，评估和改进的过程在更细的粒度下交替。只要这两个过程都持续地更新状态，那么最终的结果都会一样，也就是达成最优值函数和最优策略。
我们使用generalized policy iteration（GPI）来表示让这两个过程进行交互的过程，而不关心它们具体的粒度和实现方式。基本上所有的强化学习算法都可以用GPI进行很好的描述。也就是，每个算法都含有独特的策略以及值函数，策略可以一直利用值函数进行改进，而值函数也被更新得符合当前策略，就像右图一样。
如果两个过程都稳定了，那么值函数和策略一定都达到了最优。因为只要当它们都互相一致而且满足了贝尔曼最优等式之后才有可能稳定，也就是保证了最优。
GPI中评估和改进的过程可以被看成是一直合作与竞争。竞争是说它们两个过程互相拉向相反的方向，因为让当前策略基于当前值函数最优一般意味着让值函数与新策略不一致。而让值函数与策略一致一般又会导致策略在更新完的值函数上不是最优。但是长期来看这两个过程互相作用最终达到了最优策略和最优值函数。这两个过程的每一个都是向着达成最优的目标前进，尽管他们前进的路线可能都不是直线。
4.7 Efficiency of Dynamic Programming
对于很大型的问题DP有可能不实用，但是相比于其它解MPD的方法，DP算法是非常有效的。如果忽略技术细节的话，那么DP算法最坏时间也会在状态数和动作数的多项式时间内找出最优解。假设状态数是n动作数是k，即使所有的策略量级是
DP算法依然可以在n和k的多项式时间内解决问题。在这个程度上，DP算法比那些直接搜索的算法快了指数倍。线性规划也可以解决MDP问题，有些情况下比DP更快。但是线性规划很快就会随着问题规模的上升变得不实用。对于大型问题只能使用DP算法。
DP有时候因为维度灾难被认为是不实用的。维度灾难是指随着状态变量的数量增长，状态数的增长往往呈指数级。但是这个问题是MDP问题本身的问题而不是DP算法的问题。相比于其他算法DP算法是很实用的。实际上DP算法可以使用如今的电脑解决有百万级别个状态的MDP问题。policy Iteration和 value Iteration都应用的很广泛，而且这两个很难分出哪个更好。通常这些算法比理论最差时间收敛得更快，特别是在有个合理的初始值的情况下。
对于有很大规模状态空间的问题，异步DP算法是常用的。即使遍历一次异步算法也需要为每个状态提供计算力和存储。对于某些问题，为他们提供计算力和存储空间是不现实的，但是这些问题依然可以通过计算迹相关的状态来解决。异步算法可以在这些情况下得到应用，而且比同步算法更快。
4.8 Summary
这一章我们讲述了动态规划解决MDP问题的基础知识和算法。policy evaluation是在给定policy的情况下迭代计算值函数。policy improvement 是给出策略和该策略值函数的情况下改进策略。把他们放在一起就得到了policy Iteration和value Iteration，这两个算法都可以得到MDP问题的最优策略和最优值函数，只要给出MDP环境的完全建模。
经典的DP算法基于遍历状态空间，对每个状态的值函数进行期望更新。当算法不再更新值和策略的时候达到最优。对于值函数和最优值函数这四个变量各有一个相应的贝尔曼等式和相应的期望更新公式。这些更新操作都可以使用backup diagrams来看到。
更深入的看DP算法或者说大部分强化学习算法，它们都可以归为GPI的范畴。GPI是一个泛化的关于逼近策略和逼近值函数的两个交互过程的框架。一个过程是在给出策略的情况下更新值函数。另一个过程是指在给出值函数的情况下进行策略的改进。尽管他们都互相改变了对方的算法基础，但是他们会共同找到最优的结果。一些情况GPI已经证明是收敛的，比如目前讲到的DP算法。但有些情况GPI还未证明收敛，但是也可以为我们更好理解问题提供思路。
在DP算法中也不是一定需要每次完全遍历状态空间，异步算法就是一种用任意顺序inplace更新状态值函数的想法，用的可能是过期的状态信息。最后，讲一下DP算法最有一个特性。所有的值更新都是基于下一个状态的值函数。也就是说状态值的估计是建立在另外的估计之上的。这种想法叫做bootstrapping。许多强化学习算法都用了这个想法，即使是那些不需要像DP一样要求对环境完全建模的算法。下一章会讲解不需要环境建模和bootstrap的算法。