model-based to model-free前文中所说的value iteration和policy iteration均需要知道模型的参数但在一些情况中我们可能无法准确得知模型参数那么我们应该如何来进行估计呢我们可以利用大数定理来进行估计。iid同分布独立采样通过进行多次采样我们可以将采样所得样本均值近似为当前模型的期望将采样所得样本的方差的近似为当前模型的方差除于N。MC basic理解该算法的关键在于如何将策略迭代转变到model-free策略迭代分为两步策略评估和策略优化从逐项展开式可以看出关键点在action-value上PIa|s)是有我们来给值的。对action-value我们有两种不同表示方法我们可以基于数据用第二种方式来计算action-value。、基本流程如下从某一sa对开始采取一定策略生成一个episode这个episode的return就是gsa而gsa是Gt的一个采样假设我们有一定量的episode我们可以通过大数定理得到action-value。MC Basic算法描述当价值函数尚未收敛时遍历所有的s和a收集一定数量的episode并将其平均return作为sa的action-value最后通过贪心策略更新。MC Basic只在理论上有意义在实际中并不使用因为其的计算效率过低需要等待average return计算完成后才能进行下一步。例题第一步policy evaluation在这道题中有9个state*5种行动action45个state-action pairs。因为该题中策略是确定的因此一个episode能够满足该题如果策略是不确定的那么需要无限次的episode至少多次才能满足。这里列出qs1a1第二步policy improvement和前文所述一致通过贪心策略更新。MC Exploring StartsVisitstate-action对每次在episode中出现将其称为对该state-action对的一次访问。MC Basic所用的方法是initial-visit method对上图中的这条数据只用在(s1,a2后的return作为(s1,a2的action-value没用充分利用这条数据。Date-efficient methods有两种1.frist visit method只用第一次visit的return作为action-value的估计2.every visit method每一次对state-value对的visit所得的return都作为action-value的估计这样就充分的利用了数据MC-based RL的policy update也有两种方法第一种是收集该sa对的episodes并用其平均return来更新该方法问题在于等待时间过长第二种是用单个episode来更新我们可以提高策略episode by episode有些人可能会忧虑第二种方法是否会导致一些问题事实上第二种方法的思路如同前文所述的截断策略迭代一样在一些需要迭代的地方截断在后面通过迭代次数来弥补。伪代码要注意的是这里的计算不是顺着episode进行的而是从后往前计算的这样只需要计算γgrt1能够减少计算量。探索起点的设置在理论上只有当所有的state-action被充分发掘我们才能找到最优策略但实际上这是很难做到的。同时我们需要思考我们一个episode有多长如果episode过短那么该state可能无法找到最优策略如果episode过长又会增加计算量为了解决该问题我们可以使用soft policy。MC ε-greedy policy这就是所使用的soft policy给除最优策略以外的策略一定被选概率使用这种策略能够有效平衡探索的广度和深度。当ε等于0该策略就和greedy policy一样有深度但牺牲了广度。当ε等于1它变成了均匀分布有广度但牺牲深度。将ε-greedy policy嵌入MC-based RL算法中只需要将策略更新的policy由greedy改为ε-greedy即可。一个episode能否遍历所有的state-action pairs当ε1时有最强的广度每个state-action pairs都被多次访问。当ε减小state-action pairs的访问次数减少广度减少。在该例中ε越大state value越小这是因为它更有可能采取会受到惩罚的行动。summary
