《强化学习：原理与Python实现 》 —3.4　动态规划

3.4　动态规划

3.2.1节介绍的策略评估迭代算法和3.3节介绍的价值迭代算法都应用了动态规划这一方法。本节将介绍动态规划的思想，并且指出动态规划的缺点和可能的改进方法。

3.4.1　从动态规划看迭代算法

动态规划（Dynamic Programming，DP）是一种迭代求解方法，它的核心思想是：

将原问题分解成多个子问题，如果知道了子问题的解，就很容易知道原问题的解；

分解得到多个子问题中，有许多子问题是相同的，不需要重复计算。

求解Bellman期望方程和Bellman最优方程的迭代算法就实践了动态规划的思想。在第次迭代的过程中（），计算中的每一个值，都需要用到中所有的数值。但是，考虑到求解各个元素时使用了相同的数值，所以并不需要重复计算。从这个角度看，这样的迭代算法就使用了动态规划的思想。

在求解的过程中，和都是的估计值。用一个估计值来估计另外一个估计值的做法又称为自益（bootstrap）。动态规划迭代算法就运用了自益的思想。

在实际问题中，直接使用这样的动态规划常出现困难。原因在于，许多实际问题有着非常大的状态空间（例如AlphaGo面对的围棋问题的状态数约为种），仅仅扫描一遍所有状态都是不可能的事情。在一遍全面扫描中，很可能大多数时候都在做无意义的更新：例如某个状态所依赖的状态（即那些的状态）都还没被更新过。下一节将给出一些针对这个问题的改进。