机器学习算法之TD Learning算法

机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心,是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域,它主要使用归纳、综合而不是演绎。人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。今天我们重点探讨一下TD Learning算法。 ^_^

 
TD Learning时序差分学习结合了动态规划DP和蒙特卡洛MC(请参见人工智能(31))方法,且兼具两种算法的优点,是强化学习的核心思想。
  
虽然蒙特卡罗MC方法仅在最终结果已知时才调整其估计值,但TD Learning时序差分学习调整预测以匹配后,更准确地预测最终结果之前的未来预测。
机器学习算法之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算法
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 ?s∈S+
 
  Repeat(for each episode):
 
  ?Initialize S
 
  ?Repeat (for each step of episode):
 
  ?? A←actiongiven by π for S
 
  ??Take action A, observe R,S′
 
  ??V(S)←V(S)+α[R+γV(S′)?V(S)]
 
  ?? S←S′
 
  ?Until S is terminal
机器学习算法之TD Learning算法