关于TD-Learning算法的分析.doc

关于TD Learning算法的分析 导读：人工智能之机器学习主要有三大类：1）分类；2）回归；3）聚类。今天我们重点探讨一下TD Learning算法。 TD Learning时序差分学习结合了动态规划DP和蒙特卡洛MC方法，且兼具两种算法的优点，是强化学习的核心思想。 虽然蒙特卡罗MC方法仅在最终结果已知时才调整其估计值，但TD Learning时序差分学习调整预测以匹配后，更准确地预测最终结果之前的未来预测。 TD Learning算法概念：TD Learning（Temporal－Difference Learning） 时序差分学习指的是一类无模型的强化学习方法，它是从当前价值函数估计的自举过程中学习的。这些方法从环境中取样，如蒙特卡洛方法，并基于当前估计执行更新，如动态规划方法。 TD Learning算法本质：TD Learning（Temporal－DifferenceLearning）时序差分学习结合了动态规划和蒙特卡洛方法，是强化学习的核心思想。 时序差分不好理解。改为当时差分学习比较形象一些，表示通过当前的差分数据来学习。 蒙特卡洛MC方法是模拟（或者经历）一段序列或情节，在序列或情节结束后，根据序列或情节上各个状态的价值，来估计状态价值。TD Learning时序差分学习是模拟（或者经历）一段序列或情节，每行动一步（或者几步），根据新状态的价值，然后估计执行前的状态价值。可以认为蒙特卡洛MC方法是最大步数的TD Learning时序差分学习。 TD Learning算法描述：如果可以计算出策略价值（状态价值v（s），或者行动价值q（s，a）），就可以优化策略。 在蒙特卡洛方法中，计算策略的价值，需要完成一个情节，通过情节的目标价值Gt来计算状态的价值。其公式： MC公式：V（St）V（St）＋t t＝［Gt？V（St）］ 这里： t MC误差 MC学习步长 TD Learning公式：V（St）V（St）＋t t＝［Rt＋1＋V（St＋1）？V（St）］ 这里： t TD Learning误差 TD Learning步长 TD Learning报酬贴现率 TD Learning时间差分方法的目标为Rt＋1＋ V（St＋1），若V（St＋1） 采用真实值，则TD Learning时间差分方法估计也是无偏估计，然而在试验中V（St＋1） 用的也是估计值，因此TD Learning时间差分方法属于有偏估计。然而，跟蒙特卡罗MC方法相比，TD Learning时间差分方法只用到了一步随机状态和动作，因此TD Learning时间差分方法目标的随机性比蒙特卡罗MC方法中的Gt 要小，因此其方差也比蒙特卡罗MC方法的方差小。 TD Learning分类：1）策略状态价值v的时序差分学习方法（单步多步） 2）策略行动价值q的on－policy时序差分学习方法： Sarsa（单步多步） 3）策略行动价值q的off－policy时序差分学习方法： Q－learning（单步），Double Q－learning（单步） 4）策略行动价值q的off－policy时序差分学习方法（带importance sampling）： Sarsa（多步） 5）策略行动价值q的off－policy时序差分学习方法（不带importance sampling）： Tree Backup Algorithm（多步） 6）策略行动价值q的off－policy时序差分学习方法： Q（）（多步） TD Learning算法流程：1）单步TD Learning时序差分学习方法： IniTIalizeV（s） arbitrarily ？sS＋ Repeat（for each episode）： ？IniTIalize S ？Repeat （for each step of episode）： ？？ AacTIongiven by for S ？？Take acTIon A， observe R，S ？？V（S）V（S）＋［R＋V（S）？V（S）］ ？？ SS ？Until S is terminal 2）多步TD Learning时序差分学习方法： Input：the policy to be evaluated InitializeV（s） arbitrarily ？sS Parameters：step size （0，1］， a positive integer n Allstore and access operations （for St and Rt） can take their index mod n Repeat（for each episode）： ？Initialize and store S0terminal