4.6 广义策略迭代

策略迭代包括两个同时进行的相互作用的流程，是策略评估和策略改进，两个流程交替进行，并且可以不必一次评估对应一次改进，可以每两次策略改进之间执行一次策略评估迭代，只要两个流程持续更新所有状态，那么最后的结果通常是相同的，均会收敛到最优价值函数和一个最优策略。
广义策略迭代(GPI) 指代策略评估和策略改进相互作用的一般思路，与流程的粒度和其他细节无关。几乎所有的强化学习方法都可以被描述为GPI，策略总是基于特定的价值函数进行改进，价值函数也始终会向对应特定策略的真实价值函数收敛。价值函数只有在与当前策略一致时才稳定，并且策略只有在对当前价值函数是贪心策略时才稳定。两者的同时稳定意味着贝尔曼最优方程成立，策略和价值函数都是最优的。

4.7 动态规划的效率

1. DP算法不太适合于大规模问题，但是和其他解决MDP方法相比，实际效率很高。
2. DP算法可以保证在多项式时间内找到一个最优策略。
3. DP算法有时会因为维数灾难而缺乏实用性，但是状态集合太大大多是因为问题本身的困难，而不是DP作为解法带来的。
4. 对于有很大状态空间的问题，采用异步DP算法及GPI的一些变种，可能比同步方法更快找到好的甚至更优的策略。

4.8 本章小结

本章主要介绍了利用动态规划解决有限马尔科夫决策过程的基本思想和算法。
需要掌握的一些概念：

1. 策略评估、策略改进、策略迭代、价值迭代。
2. 与贝尔曼方程相关的期望更新，及其回溯图。
3. 广义策略迭代GPI。
4. 异步DP算法。
5. 自举法：对当前状态的更新都依赖于对后继状态的估计。

5.1 蒙特卡洛预测

蒙特卡洛方法中不需要完备的环境知识，仅仅需要经验，即从环境交互中得到的状态、动作、收益的序列。这时的模型只需要模拟生成状态转移的一些样本，而不需要像DP算法一样生成所有转移的概率分布。
MC方法通过平均样本的回报来解决强化学习问题，是逐幕进行更新的，也就是价值估计和策略改进是在整个幕结束才进行，而不是每一步都在线更新。
MC算法采样并平均每一个“状态-动作”二元组的回报，其与赌博机算法的主要区别是，每一个状态都类似于一个不同的赌博机算法，并且这些赌博机问题是相关联的，即某个状态采取动作之后的回报取决于同一幕中后来的状态中采取的动作。
假设在给定策略$\pi$下途径状态s的多幕数据，想估计策略$\pi$下状态s的价值函数$v_\pi(s)$，在给定的一幕中，每次状态s的出现称为对s的一次访问，在每一幕中，状态s可能被多次访问。
首次访问型MC算法用s的所有首次访问的回报的平均值估计$v_\pi(s)$
每次访问型MC算法用s的所有访问的回报的平均值估计$v_\pi(s)$
两者算法的主要区别就是是否需要检查状态$S_t$在当前幕已经出现过。
首次访问型MC算法中的每个回报值都是对$v_\pi(s)$的一个独立同分布的估计，且方差有限，根据大数定理，这一平均值的序列会收敛到它们的期望值，每次平均都是一个无偏估计，且标准差会不断衰减。
每次访问型MC算法也会二阶收敛到$v_\pi(s)$。

首次访问型MC算法如上图所示，需要判断$S_t$是否已经出现过，并使用回报的平均值来更新状态值函数。
MC算法只需利用若干幕采样序列就能计算的特性是一个巨大的优势，即使已知整个环境的状态特性也是如此。

图左为MC方法的回溯图，根为一个状态节点，然后往下是某幕样本序列已知到终止状态为止的完整轨迹，包含该幕中的全部状态转移。
而图右是DP的回溯图，其显示了所有可能的转移，而MC算法只显示在当前幕中采样的那些转移。
并且DP回溯图只包含一步转移，而MC算法包含这一幕结束为止的所有转移。
MC的一个重要特点：对每个状态的估计是独立的。对一个状态的估计完全不依赖于对其他状态的估计，这与DP完全不同。也就是MC算法不使用自荐法。

5.2 动作价值的蒙特卡洛估计

如果无法得到环境的模型，那么计算动作价值函数，也就是“状态-动作”二元组的价值，比计算状态价值函数更加有用。
在有模型的情况下，单靠价值函数就可以确定一个策略，只需要简单向前看一步，选取特定的动作，贪心使得当前收益与后继状态的价值函数之和最大即可。
但在没有模型的情况下，必须显式地确定每一个动作的价值函数才能确定一个策略，也就是不能通过环境模型来向前看一步的话，只能显式知道当前状态的每个动作的价值，才能贪心得到策略。
动作价值函数的策略评估问题的目标就是估计$q_\pi(s,a)$，跟5.1中类似，只不过转化成用“状态-动作”二元组得到的回报的平均值作为价值函数的估计。这里唯一复杂一些的是某一些“状态-动作”二元组可能永远不会被访问到，如果$\pi$是一个确定的策略，那么遵循$\pi$意味着每一个状态中只会观测到一个动作的回报，为了比较所有动作的选择好坏，需要顾及在一个状态中可采取的所有动作的价值函数，而不仅仅是当前更偏好某个特定动作的价值函数。
也就是对应“试探”的问题，为了保持持续的试探，一种方法是将指定的二元组作为起点开始一幕采样，同时保证所有二元组都有非零的概率可以被选为起点，被称为“试探性出发”，一种方法是只考虑那些在每个状态下所有动作都有非零概率被选中的随机策略。