欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

4.蒙特卡洛(Monte-Carlo, MC)+时序差分(Temporal Difference, TD)

程序员文章站 2022-03-23 11:29:48
目录深度强化学习目录简介之前讲的PG算法和PPO算法,都是Policy-based的方法,接下来我们要讲Value-based的方法。之前说过了,P-B方法和V-B方法的区别在于前者训练的是策略本身(actor),而后者训练的是一种评判标准(critic)。critic能根据你输入的状态/动作,凭借策略π\piπ来输出对应的值函数。值函数有两种,一种是V(状态-值函数),一种是Q(状态-动作值函数),我们要讲的MC算法和TD算法是用来估计V值函数的。符号τ\tauτ:一轮游戏中的具体过程(tra...

目录

深度强化学习目录

简介

之前讲的PG算法和PPO算法,都是Policy-based的方法,接下来我们要讲Value-based的方法。之前说过了,P-B方法和V-B方法的区别在于前者训练的是策略本身(actor),而后者训练的是一种评判标准(critic)。critic能根据你输入的状态/动作,凭借策略π\pi来输出对应的值函数。值函数有两种,一种是V(状态-值函数),一种是Q(状态-动作值函数),我们要讲的MC算法和TD算法是用来估计V值函数的。

符号

  • τ\tau:一轮游戏中的具体过程(trajectory),τ={s1,a1,r1,s2,a2,r2,,sT,aT,rT}\tau=\{s_1,a_1,r_1,s_2,a_2,r_2,\ldots,s_T,a_T,r_T\},是状态-行为-奖赏的时间序列。
  • GtG_t:时间从t到结束的累积奖赏,由于t时刻的奖励是采取行动后t+1时刻才拥有的,所以GtG_t满足:Gt=rt+1+rt+2+G_t={r_{t+1}+r_{t+2}+\ldots}
  • Vπ(s)V_\pi(s):策略为π\pi的状态-值函数,即状态s下预计累计回报的期望值,满足:Vπ(s)=E[GtSt=s]V_\pi(s)=\mathbb{E}[G_t\vert S_t=s]
  • Qπ(s,a)Q_\pi(s,a):策略为π\pi的状态-动作值函数,即状态s下采取动作a预计累计回报的期望值,满足:Qπ(s,a)=E[GtSt=s,At=a]Q_\pi(s,a)=\mathbb{E}[G_t\vert S_t=s,A_t=a]

蒙特卡洛(Monte-Carlo, MC)算法

MC算法就是通过采样来估计分布的一种算法。在一场游戏中,先让策略π\pi去和环境进行交互获取数据,看到状态ss后计算整场游戏的累积奖赏GG,记录下这些数据后训练一个回归问题来拟合Vπ(s)V_\pi(s)。如下图所示:
4.蒙特卡洛(Monte-Carlo, MC)+时序差分(Temporal Difference, TD)
公式逼近为:Vπ(s)Vπ(s)+α(GtVπ(s))V_\pi(s)\leftarrow V_\pi(s)+\alpha(G_t-V_\pi(s))

其中α\alpha为学习率,越接近1学的越快。
显而易见,这样的训练需要大量的采样,并且每次update都需要一整轮的累积奖赏GtG_t,因此实际情况下我们用TD算法会比较多。

时序差分(Temporal Difference, TD)算法

在MC算法中,我们每次都要算整场游戏的总和GG。有的游戏很长,每次都要玩完游戏会花费很多时间。而TD算法只需要有st,at,rt,st+1,\ldots s_t,a_t,r_t,s_{t+1},\ldots这样的序列,就可以应用。
这是基于一个显见的递推公式:Vπ(st)=Vπ(st+1)+rtV_\pi(s_t)=V_\pi(s_{t+1})+r_t

有了这样一个递推公式,我们只需要记录每一步的即时奖励rtr_t,通过神经网络直接训练VπV_\pi函数,分别输入sts_tst+1s_{t+1},将两个结果相减,再将减后的结果与rtr_t进行回归拟合就行了。如下图所示:
4.蒙特卡洛(Monte-Carlo, MC)+时序差分(Temporal Difference, TD)
公式逼近为:Vπ(s)Vπ(s)+α(rt+1+Vπ(s)Vπ(s))V_\pi(s)\leftarrow V_\pi(s)+\alpha(r_{t+1}+ V_\pi(s')-V_\pi(s))

其中ss'是下一步的状态。

MC v.s. TD

MC的问题在于其方差过大。我们用MC算法回归估计的是累积奖赏GG,而累积奖赏是许多step的和,而游戏的每一步step的奖赏rr都有随机性,这份随机性也通过方差积累下来了。
而TD中的即时奖赏rr同样具有随机性,但是方差会小很多。TD的问题在于V的估计可能不准,那递归调用就会放大这份估计的误差。

例子

假设通过一个策略π\pi玩游戏,获得了以下8轮的τ\tau

  • sa,ra=0,sb,rb=0,Ends_a,r_a=0,s_b,r_b=0,End
  • sb,r=1,Ends_b,r=1,End
  • sb,r=1,Ends_b,r=1,End
  • sb,r=1,Ends_b,r=1,End
  • sb,r=1,Ends_b,r=1,End
  • sb,r=1,Ends_b,r=1,End
  • sb,r=1,Ends_b,r=1,End
  • sb,r=0,Ends_b,r=0,End

我们通过MC和TD算法分别估测a和b的状态值函数。
Monte-Carlo:Vπ(sa)=0Vπ(sb)=34V_\pi(s_a)=0\\V_\pi(s_b)=\frac{3}{4}
Temporal Difference:Vπ(sa)=Vπ(sb)=34V_\pi(s_a)=V_\pi(s_b)=\frac{3}{4}
如之前所说,MC算法就是采样状态s,然后计算其V值。我们发现在这8轮游戏中,a在第一轮出现一次,且一整轮的累积奖赏G1=ra+rb=0G_1=r_a+r_b=0,所以Vπ(sa)=E[Ga]=G1=0V_\pi(s_a)=\mathbb{E}[G_a]=G_1=0;而b在8轮中都出现过了,其中有六轮中累积奖赏G1,2,3,4,5,6=1G_{1,2,3,4,5,6}=1,两轮中累积奖赏G0,7=0G_{0,7}=0,所以Vπ(sb)=E[Gb]=18i=07Gi=34V_\pi(s_b)=\mathbb{E}[G_b]=\frac{1}{8}\sum_{i=0}^7 G_i=\frac{3}{4}
TD算法则是根据动作的即时奖赏来估计V值。在8轮中,状态sbs_b都是最后一个状态,所以对于每一轮都有Vπ(sb)=Vπ(End)+rV_\pi(s_b)=V_\pi(End)+r。而由定义易得Vπ(End)=0V_\pi(End)=0,所以Vπ(sb)=34V_\pi(s_b)=\frac{3}{4}。对于Vπ(sa)V_\pi(s_a),在第一轮中有Vπ(sa)=Vπ(sb)+raV_\pi(s_a)=V_\pi(s_b)+r_a,且ra=0r_a=0,所以Vπ(sa)=Vπ(sb)=34V_\pi(s_a)=V_\pi(s_b)=\frac{3}{4}

其他的critic

如果不估计VπV_\pi而是用动作-状态值函数QπQ_\pi,也是可以用MC和TD方法的,过程基本一致,不过Q函数接收的参数除了状态还有动作,因此需要更改一下公式。

总结

实际运用中用TD算法比较多。接下来讲Q-learning。

本文地址:https://blog.csdn.net/qq_39160779/article/details/107309495