0、为什么免模型学习？
在已知的MDP中，可以使用DP来计算求解RL
但是在未知MDP中，没有转移函数，不能直接求解，此时MDP未知，需要使用采样方法，也就是本课中的Model-Free方法
PS：课程中迭代的值是值函数；周志华老师的西瓜书中迭代的是状态值函数；课程中迭代的是状态-动作值函数
1、蒙特卡洛方法
直接通过采样求和（v(s) = S(s)/n(s)，其中S(s) = S(s) + G(t)，G(t)=r(t+1)+r(t+2)+...）
1.1、蒙特卡洛增量计算方法(v(s) = v(s) + a*(G(t)))
2、TD算法
自举:从原样本自身的数据抽样得到新的样本的统计量(参考:http://blog.csdn.net/omenglishuixiang1234/article/details/50281249)
2.1、思想
用样本值函数均值代替值函数期望
2.2、计算公式
1) 全量计算: N(s)<-N(s)+1; S(s)<-S(s)+G(t); V(s)<-S(s)/N(s) V(s)=S(s)/N(s)
2) 增量计算: N(s)<-N(s)+1; V(St)<-V(St) + (Gt - V(St)) / N(St); V(St)<-V(St) + lambda * (Gt - V(St))
3、TD(0)
3.1、计算公式
V(St)=V(St)+lambda * (R(t+1) + lambda2 * V(St+1)- V(St))
其中: R(t+1) + lambda2 * V(St+1) 称为TD target；R(t+1) + lambda2 * V(St+1) - V(St) 称作TD error；
注意:这里的下一个状态并非和上一个状态相同
3.2、优势
TD不需要知道完整序列，随时都可以学习；MC相反
3.3、偏差/方差分析
True TD target是值函数的无偏估计；采样的TD target是有偏估计
TD算法方差低，因为它只依赖一个动作就更新
4、MC和TD的比较
MC高方差, 无偏; 对初始值不敏感; 容易理解和使用; 在函数逼近(用函数逼近值函数，而不是backup值函数)时好使???
TD低方差, 有偏;对初始值敏感; 在函数逼近时不好使???
AB Example说明MC/TD的结果可能不一致
MC向着最小二乘收敛；TD向MDP的最大似然收敛
TD探索马尔科夫性，在马尔科夫环境更有效；MC不探索马尔科夫性，在非马尔科夫环境更有效
5、DP/MC/TD的比较
从是否自举和backup数考虑
1)只使用sample backup值，自举，是TD
2)只使用sample backup值，不自举，是MC
3)使用full backup值，自举，是DP
4)使用full backup值，不自举，是穷举搜索
6、TD(lambda):TD和MC的融合
6.1、TD(n)
TD(0)是n=1，向前看一步；TD(infinite)是看到结束，相当于MC
6.2、定义
TD(lambda)是TD(0)/TD(1)/TD(2)……的等比加权(几何加权:无记忆, 适合高效计算)组合; 这样TD算法会更加鲁棒
6.3、后向算法
优势: 前向算法需要完整的样本, 和MC一样
信用分配: 频次分配/近邻分配
基于资格迹的TD(lambda)算法:V(s)=V(s) + td-error*Et(S)，其中Et(S)是资格迹(E0(s)=0; Et+1(S) = r*lambda*E(S) + 1(St=s))
资格迹表征了一个状态在时间和频次上的可信度！！！！
前向更新和后向更新是一致的
Question：
MC在函数逼近时好使;TD在函数逼近时不好使，这是什么意思???
TD(lambda)的后向算法形式上和TD(lambda)有区别，如何等价???
(课程中只说了lambda为0/1时, 是相等的, 然后就得到了结论95:00-95:09前后, PPT中有证明，哈哈哈)
如果发现文中有问题，敬请联系作者批评指正，真诚欢迎您的指教，谢谢！
微信: legelsr0808
邮箱: legelsr0808@163.com