在本章中，我们将考虑我们用于估计价值函数和发现最优政策的第一种学习方法。 与前一章不同，这里我们不假设完整的环境知识。 蒙特卡罗方法只需要经验 - 样本序列的状态，动作，以及与环境的实际或模拟交互。
蒙特卡洛和核心思想是随机模拟然后取平均，下面是V函数的first-visit蒙特卡洛求解方法
对于无模型的问题，求解V函数是不能得到策略的，所以需要求解q(s,a)，但是蒙克卡罗有一个很严重的问题：有时候不是所有的s,a对都会出现，这是一个探索问题。
参考通用策略迭代模型，我们可以像DP一样迭代更新求解
如果假设数据集是探索开始的并且是无限的，可以保证迭代的收敛
那么我们有什么办法去掉探索开始这个不太实际的假设吗？有两种方法可用：on-policy和off-policy。off-policy改进策略的时候用的不是当前策略产生的数据，Monte Carlo ES是on-policy的方法，改进策略的数据是当前策略产生的。
首先我们考虑ε-soft policy下的Monte Carlo ES，假设不是数据探索开始的，在改进策略一环中可以用ε-soft促进探索。
下面简单证明该算法会使价值变大
所有的策略学习方法都面临一个困境：既要使得策略为最优策略，又要对环境进行探索。上面的ε-soft Monte Carlo ES实际上是一种折衷的方法，还有一种方法是：学习两个策略，一个为最优策略(target policy)，另一个为探索策略用于生成行为(behavior policy)。
对于MDP问题下式成立
得到重要性采样比例
因为p可以消去，所以我们无需知道MDP状态转移概率
所以我们可以用并未策略b采样估计目标策略的价值函数
5.5式为ordinary importance sampling，特点是无偏差，方差大；5.6式为weighted importance sampling，特点是偏差大，方差小。简单的理解为：5.6的采样中，如果有一个采样比例特别大，就会使得V(s)严重偏离期望；5.5的采样中，假设只采样一次，消去元过后，则统计出来的结果不是目标策略的V(s)的期望。
下面的实验展示了5.5的方差太大而导致始终无法收敛
下面讨论off-policy蒙特卡洛算法的增量实现：
算法描述
异策略算法的优势是目标策略可以是确定性的，而行为策略是尽可能采样到每一个动作的。
off-policy蒙特卡洛策略学习
这个算法有一个潜在的问题是喜欢从事件的尾部学习，当尾部是贪心的则会导致学习很慢。
下面讨论ordinary off-policy减小方差的方法：如果给定一个100长度序列且回报衰减r=0，理论上只需要计算一步得到重要性采样比例，而实际上我们用100长度的序列来计算，这就极大的增加了方差。所以有一种思想是把衰减r视为序列终止的概率，于是可以得到一个新的回报计算公式：
新的采样公式
还有另一种思路减小方差：
展开第一项发现只有第一个因子和对应回报是相关联的，对于第k项由类似的结论
所以我们应该把5.11式改为
这个idea被称为per-decision version ofweightedimportance sampling
网友评论