dynamic programming指已知MDP环境信息计算optimal policy的一系列算法。DP要求环境model，且需要大量计算，但它是理解其他算法的基础。DP的核心是利用value function来确定如何搜索policy。 满足Bellman optimality equations，DP便是将Bellman equations转化为估计value function的算法。

4.1 Policy Evaluation (Prediction)

首先思考计算任意 的value function ，称为policy evaluation in DP。 则value funtion存在且唯一。 考虑一系列 ，随意选择 ，用(4.4)来估计下一个： is a fixed point for this update。当 ， 。这种方法称为iterative policy evaluation。有两种方法进行更新：一种维护两个array来存储state value；一种用一个array，有更新则立刻使用，会converge快一些。一般使用第二种。注意什么时候停止。

4.2 Policy Improvement

得到了一个policy的value function，就可以更新policy。首先考虑deterministic policy（本章中方法皆可扩展到stochastic policy）。考虑在一个state 更新policy，选择action ，若 ，即选择 后继续按照 行动，得到的return大于 ，那么新的policy肯定比 好， 。同理推广到所有states， 。称为policy improvement theorem。当 ，满足Bellman optimality equation， 必然是

4.3 Policy Iteration

不断做policy evaluation和policy improvement，每一步都可以得到strictly better policy，最终可以得到optimal policy。这种方法称为policy iteration这种方法的速度越来越快（猜的，因为value function的变化越来越小）。通常很快就收敛了。

4.4 Value Iteration

一个policy iteration的缺点是，每次都要policy evaluation。我们不必每次都等value function收敛，如value iteration： value iteration在同样情况下也保证收敛到 。另一种理解value iteration的方法是，它只是将Bellam optimality equation转化为update rule。同样注意什么时候停止：value iteration每一步包含一步policy evaluation，一步policy improvement。通常一步policy improvement + 几步policy evaluation会收敛更快。

4.5 Asynchronous Dynamic Programming

之前讨论的DP方法，都需要将state重复扫。asynchronous DP用任意顺序，利用任何available的下一步数据。有的数据可能更新几次了，有的可能还没更新，有的利用out-of-date数据更新。需要保证不忽略states，但很flexible。in-place iterative methods。比如有一种就是一次只更新一个state，逐个更新。只要保证所有的都能更新无限次就ok。不扫state并不意味着计算量减很多，只是通过选择state来加速，选择更新顺序来让信息流动更迅捷。有了asyn DP，我们也可以让agent和环境交互时，实时更新state value，让算法关注和agent关系更近的states。

4.6 Generalized Policy Iteration

policy iteration，value iteration，asyn DP都是policy evaluation和policy improvement的各种结合，最终目标都是找到optimal value function和optimal policy。generalized policy iteration (GPI) 来表示policy evaluation和policy improvement的交互。大部分RL方法都可以用GPI表示，即有不同的policy和value function，用value funtion来更新policy，让value function更接近policy的true value funtion。当evaluation和improvement都稳定时，即converge了，得到optimal，满足Bellman equation。policy稳定表示它greedy了当前value function；value function稳定表示它是policy的value function。evaluation和improvement既compete也cooperate。每一个更新都会让另一个unstabilize，但是同时都趋近于goal。有的情况下GPI可以converge，有的不行。

4.7 Efficiency of Dynamic Programming

DP可能不适用于大问题，但其实挺efficient。找到optimal的时间和states actions数成polynomial，而且还能保证找到optimal，比把所有policies都试一次好很多，which is exponential time。DP方法受限于curse of dimensionality，即state数量随着state variable的增长呈exponential growth。policy iteration和value iteration用得都很广泛，很难说哪个更好。一般都比worst case要好很多，尤其是initial policy，value设置得好。state很多时，一般用asyn DP。

4.8 Summary

用一个estimate来更新estimate，称为bootstrapping。在RL里很常见。