signed

QiShunwang

“诚信为本、客户至上”

强化学习理论基础

2021/5/14 22:49:28   来源:

强化学习理论基础

强化学习理论基础

1、贝尔曼方程 & 贝尔曼期望方程

(1)Bellman方程

在MRP中,为了衡量一个状态未来得期望回报,引入了价值函数 v ( s ) v(s) v(s)的概念,其计算方式为:
v ( s ) = E [ G t ∣ S t = s ]                              = E [ R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . ∣ S t = s ]                              = E [ R t + 1 + γ ( R t + 2 + R t + 3 + . . . ) ∣ S t = s ]                              = E [ R t + 1 + γ v ( S t + 1 = s ′ ) ∣ S t = s ]                              = R t + 1 + ∑ s ′ ∈ S P ( S t + 1 = s ′ ∣ S t = s ) v ( s ′ ) v(s)=E[G_t|S_t=s]\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = E[R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...|S_t=s]\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~=E[R_{t+1}+\gamma(R_{t+2}+R_{t+3}+...)|S_t=s]\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~=E[R_{t+1}+\gamma v_(S_{t+1}=s')|S_t=s]\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~=R_{t+1}+\sum_{s'\in S}P(S_{t+1}=s'|S_t=s)v(s') v(s)=E[GtSt=s]                            =E[Rt+1+γRt+2+γ2Rt+3+...St=s]                            =E[Rt+1+γ(Rt+2+Rt+3+...)St=s]                            =E[Rt+1+γv(St+1=s)St=s]                            =Rt+1+sSP(St+1=sSt=s)v(s)
Bellman方程这里并没有涉及策略的概念。

(2)Bellman期望方程

Bellman期望方程在MDP中引入的,这时有策略的概念,Bellman期望方程包括价值函数的期望方程的行为价值函数的期望方程,Bellman期望方程的获得可以从两个角度来看:
角度一:从Bellman方程看角度看,就是将策略的概率引入,类似的可以得到:
v π ( s ) = R s a + γ ∑ a ∈ A π ( a ∣ s ) ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) v_{\pi}(s)=R_{s}^a+\gamma \sum_{a\in A}\pi (a|s)\sum_{s'\in S}P_{ss'}^av_\pi (s') vπ(s)=Rsa+γaAπ(as)sSPssavπ(s)
Q π ( s , a ) = R s a + γ ∑ s ′ ∈ S P s s ′ a ∑ a ′ ∈ A π ( a ′ ∣ s ′ ) Q ( s ′ , a ′ ) Q_\pi (s,a)=R_{s}^a+\gamma\sum_{s'\in S}P_{ss'}^a\sum_{a'\in A}\pi(a'|s') Q(s',a') Qπ(s,a)=Rsa+γsSPssaaAπ(as)Q(s,a)

角度二:利用行为价值函数,过程为:
a、引入行为价值函数 Q π ( s , a ) Q_\pi (s,a) Qπ(s,a)
b、得到价值函数与行为价值函数之间的关系:
v π ( s ) = ∑ a ∈ A π ( s , a ) Q π ( s , a ) v_{\pi}(s)=\sum_{a\in A}\pi (s,a)Q_{\pi}(s,a) vπ(s)=aAπ(s,a)Qπ(s,a)
c、推导行为价值函数的递推式子:
Q π ( s , a ) = E [ G t ∣ S t = s , A t = a ] = R s a + γ ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) Q_{\pi}(s,a)=E[G_t |S_t=s,A_t=a]\\=R_s^a+\gamma \sum_{s'\in S}P_{ss'}^av_{\pi}(s') Qπ(s,a)=E[GtSt=s,At=a]=Rsa+γsSPssavπ(s)
d、b与c互相带入就得到Bellman期望方程:
价值函数的Bellman期望方程:
v π ( s ) = ∑ a ∈ A π ( s , a ) ( R s a + γ ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) ) v_\pi (s)=\sum_{a\in A}\pi(s,a)(R_s^a+\gamma\sum_{s'\in S}P_{ss'}^av_\pi (s')) vπ(s)=aAπ(s,a)(Rsa+γsSPssavπ(s))
行为价值函数的Bellman期望方程:
Q π ( s , a ) = R s a + γ ∑ s ′ ∈ S P s s ′ ∑ a ′ ∈ A π ( a ′ ∣ s ′ ) Q π ( a ′ . s ′ ) Q_\pi (s,a)=R_s^a+\gamma\sum_{s'\in S}P_{ss'}\sum_{a'\in A}\pi(a'|s')Q_\pi (a'.s') Qπ(s,a)=Rsa+γsSPssaAπ(as)Qπ(a.s)

过程来看,行为价值函数的引入似乎是为了推导出价值函数的Bellman期望方程,但是在后续的相关算法中其回发挥很大的作用。

2、贝尔曼最优方程

最优价值函数: v ∗ ( s ) = a r g π m a x v π ( s )    f o r    a n y    s t a t e s v_*(s)=\underset{\pi}{arg}maxv_\pi (s)~~for~~any~~states v(s)=πargmaxvπ(s)  for  any  states
最优行为价值函数: Q ∗ ( s , a ) = a r g π m a x Q π ( s , a )    f o r    a n y    s t a t e − a c t i o n    p a i r s Q_*(s,a)=\underset{\pi}{arg}maxQ_\pi(s,a)~~for~~any~~state-action~~pairs Q(s,a)=πargmaxQπ(s,a)  for  any  stateaction  pairs
确定型最优策略:
π ∗ ( a ∣ s ) = { 1 , i f    a = a r g a m a x Q ∗ ( s , a ) 0 , e l s e \pi_*(a|s)=\left\{\begin{array}{l}1,if~~a=\underset{a}{arg}maxQ_*(s,a)\\0,else \end{array}\right. π(as)={1,if  a=aargmaxQ(s,a)0,else
则对于最优策略下的价值函数:
v ∗ ( s ) = a r g π m a x v π ( s ) = a r g π m a x ∑ a ∈ A π ( s , a ) Q π ( s , a ) = a r g π m a x Q π ( s , a ) = Q ∗ ( s , a ) v_*(s)=\underset{\pi}{arg}maxv_{\pi}(s)\\=\underset{\pi}{arg}max\sum_{a\in A}\pi(s,a)Q_\pi (s,a)\\=\underset{\pi}{arg}maxQ_\pi(s,a)\\=Q_*(s,a) v(s)=πargmaxvπ(s)=πargmaxaAπ(s,a)Qπ(s,a)=πargmaxQπ(s,a)=Q(s,a)
即在确定型最优策略下,价值函数与行为价值函数的值相同,此时,价值函数与行为价值函数的Bellman期望方程形式相同,称为Bellman最优方程:
v ∗ ( s ) = m a x a ∈ A R s a + γ ∑ s ′ ∈ S P s s ′ a v ∗ ( s ′ ) v_*(s)=\underset{a\in A}{max}R_s^a+\gamma\sum_{s'\in S}P_{ss'}^av_*(s') v(s)=aAmaxRsa+γsSPssav(s)
Q ∗ ( s , a ) = R s a + γ ∑ s ′ ∈ S P s s ′ a m a x a ′ ∈ A Q ∗ ( s ′ , a ′ ) Q_*(s,a)=R_s^a+\gamma\sum_{s'\in S}P_{ss'}^a\underset{a'\in A}{max}Q_*(s',a') Q(s,a)=Rsa+γsSPssaaAmaxQ(s,a)

因此,根据Bellman最优方程,获得最优策略的方法为:
求解Bellman最优方程,最优策略 π ∗ \pi_* π:
π ∗ ( s ) = m a x a R s a + γ ∑ s ′ ∈ S P s s ′ a v ∗ ( s ′ ) \pi_*(s)=\underset{a}{max}R_s^a+\gamma\sum_{s'\in S}P_{ss'}^av_*(s') π(s)=amaxRsa+γsSPssav(s)
π ∗ ( s ) = m a x a Q ∗ ( s , a ) \pi_*(s)=\underset{a}{max}Q_*(s,a) π(s)=amaxQ(s,a)
从上面的式子可以看出,如果求得行为价值函数,那么就可以比较快得到最优策略,所以很多时候都是直接求解行为价值函数得到最优策略。
很多时候强化学习都是形式化为MDP,因此求解强化学习问题其实就是求解Bellman最优方程。

3、预测与控制

MDP中涉及的两类基本的问题是控制和预测,控制即找到最优策略,预测即评估当前给定策略的好坏。
控制即求解Bellman最优方程,Bellman最优方程中有非线性的算子max,所以Bellman方程并不是线性方程。
预测问题即求解Bellman期望方程,其是线性方程,有解析解,但是只适用于小规模问题。
预测和控制问题根据是否知道模型分为基于模型的预测(控制)以及无模型的预测(控制)。
基于模型至少要知道下列两个条件:
(1) R s a = E [ R t + 1 ∣ S t = s , A t = a ] R_{s}^a=E[R_{t+1}|S_t=s,A_t=a] Rsa=E[Rt+1St=s,At=a]
(2) P s s ′ a = P [ S t + 1 = s ′ ∣ S t = s , A t = a ] P_{ss'}^a=P[S_{t+1}=s'|S_t=s,A_t=a] Pssa=P[St+1=sSt=s,At=a]

(1)预测问题:求解Bellman期望方程

预测问题就求解Bellman期望方程:
v π ( s ) = ∑ a ∈ A π ( a ∣ s ) ( R s a + γ ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) ) v_\pi(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma \sum_{s'\in{S}}P_{ss'}^av_\pi(s')) vπ(s)=aAπ(as)(Rsa+γsSPssavπ(s))

基于模型的预测

基于模型的预测也就是知道了下面两个条件:
(1) R s a R_s^a Rsa
(2) P s s ′ a P_{ss'}^a Pssa

解线性方程

因为知道了Bellman期望方程的所有条件,并且Bellman期望方程是线性的,所以可以直接得到其解析解。
首先:(1) R s π = ∑ a ∈ A π ( a ∣ s ) R s a R_s^{\pi}=\sum_{a\in A}\pi(a|s)R_s^a Rsπ=aAπ(as)Rsa
(2) P s s ′ π = ∑ a ∈ A π ( a ∣ s ) P s s ′ a P_{ss'}^\pi=\sum_{a\in A}\pi(a|s)P_{ss'}^a Pssπ=aAπ(as)Pssa
那么Bellman期望方程就可以写为:
V π = R π + γ P π V π ⇒ V π = ( I − γ P π ) − 1 R π V_\pi=R_\pi+\gamma P_\pi V_\pi\Rightarrow V_\pi=(I-\gamma P_\pi)^{-1}R_\pi Vπ=Rπ+γPπVπVπ=(IγPπ)1Rπ
缺点:
(1)矩阵求逆,复杂度为 O ( S 3 ) O(S^3) O(S3),计算量大
(2)当矩阵洗漱的时候结果不一定准确
但是Bellman期望方程满足动态规划的条件:
(1)原问题包含子问题
(2)子问题重复出现
因此使用动态规划的方法求解Bellman方程,动态规划的本质就是迭代进行。

动态规划

(1)初始化一个价值函数 V 1 V_1 V1
(2)进行迭代:
V l + 1 ( s ) = ∑ a ∈ A π ( a ∣ s ) ( R s a + γ ∑ s ′ ∈ S P s s ′ a V l ( s ) ) V_{l+1}(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma\sum_{s'\in S}P_{ss'}^aV_{l}(s)) Vl+1(s)=aAπ(as)(Rsa+γsSPssaVl(s))
收敛道真实函数 V π V_\pi Vπ

收敛性证明:
Bellman期望算子 τ π ( v ) = R π + γ P π v \tau^\pi(v)=R^\pi+\gamma P^\pi v τπ(v)=Rπ+γPπv
∣ τ π ( u ) − τ π ( v ) ∣ ≤ ∣ ∣ τ π ( u ) − τ π ( v ) ∣ ∣ ∞ = ∣ ∣ R π + γ P π u − R π − γ P π v ∣ ∣ ∞ = ∣ ∣ γ P π ( u − v ) ∣ ∣ ∞ ≤ ∣ ∣ γ P π ∣ ∣ u − v ∣ ∣ ∞ ∣ ∣ ∞ ≤ γ ∣ ∣ u − v ∣ ∣ ∞ |\tau^\pi(u)-\tau^\pi(v)|\leq||\tau^\pi(u)-\tau^\pi(v)||_\infty\\=||R^\pi+\gamma P^\pi u-R^\pi-\gamma P^\pi v||_\infty \\=||\gamma P^\pi(u-v)||_\infty\\\leq||\gamma P^\pi||u-v||_\infty||_\infty\\\leq\gamma||u-v||_\infty τπ(u)τπ(v)τπ(u)τπ(v)=Rπ+γPπuRπγPπv=γPπ(uv)γPπuvγuv
γ < 1 \gamma<1 γ<1时Bellman期望算子是收缩的,那么经过迭代会收敛到真实的 V π V_\pi Vπ。( γ = 1 \gamma=1 γ=1时的收敛证明用其他方法,参考PPT lecture3的15页)

无模型的预测

动态规划求解预测问题的局限:对模型的依赖
(1)要么是MDP问题的模型已知
(2)要么智能体对环境建模
很多情况下是不知道模型的,所以需要找到不基于模型的方法。

蒙特卡洛方法(MC)

MC是从价值函数的本质定义出发,即 V ( s ) = E [ G t ] V(s)=E[G_t] V(s)=E[Gt]使用观测轨迹的回报的均值估计回报的期望。

1、MC的特点:

(1)无模型:不需要MDP的奖励函数和状态转移概率
(2)根据完整的轨迹:无自举

2、MC的基本思想:

使用观测的均值回报代替回报的期望,即价值函数

3、MC的要求:

所有的轨迹都能到达终止状态或者轨迹足够长。

4、MC方法的过程:

(1)初始版本:
a、评估状态s,在一次轨迹中首次经过s时: N ( s ) = N ( s ) + 1 N(s)=N(s)+1 N(s)=N(s)+1
S ( s ) = S ( s ) + G t S(s)=S(s)+G_t S(s)=S(s)+Gt(这里需要 G t G_t Gt,只有完整轨迹之后才可以得到,这也就是为什么MC需要完整的轨迹)

b、估计价值函数为 V ( s ) = S ( s ) N ( s ) V(s)=\frac{S(s)}{N(s)} V(s)=N(s)S(s)
总结:需要完整的轨迹,使用回报的均值估计回报的期望
(2)改进之增量版本
S ( s ) = ∑ i = 1 N G t ( i ) N ( s ) = 1 N ( s ) ( G t ( N ) + ∑ i = 1 N − 1 G t ( i ) ) = 1 N ( s ) ( G t ( N ) + ( N ( s ) − 1 ) V ( s ) ) = V ( s ) + 1 N ( s ) ( G t − V ( s ) ) S(s)=\frac{\sum_{i=1}^N G_{t(i)}}{N(s)}\\=\frac{1}{N(s)}(G_{t(N)}+\sum_{i=1}^{N-1}G_{t(i)})\\ =\frac{1}{N(s)}(G_{t(N)}+(N(s)-1)V(s))\\=V(s)+\frac{1}{N(s)}(G_t-V(s)) S(s)=N(s)i=1NGt(i)=N(s)1(Gt(N)+i=1N1Gt(i))=N(s)1(Gt(N)+(N(s)1)V(s))=V(s)+N(s)1(GtV(s))
随着采样轨迹数量的增加, N ( s ) → 0 N(s)\rightarrow0 N(s)0,那么学习的后期,观测量对结果的影响不大,但是如果环境时动态的、不断变化的,更希望时能够随时跟踪当前不断变化的均值:使用固定的学习率 α \alpha α
V ( s ) = V ( s ) + α ( G t − V ( s ) ) V(s)=V(s)+\alpha(G_t-V(s)) V(s)=V(s)+α(GtV(s))

时间差分

价值函数的另一个定义是Bellmman期望方程: V π ( s ) = E [ R t + 1 + γ V π ( S t + 11 ) ] V_\pi(s)=E[R_{t+1}+\gamma V_\pi(S_{t+11})] Vπ(s)=E[Rt+1+γVπ(St+11)]

1、TD特点

(1)根据非完整的轨迹学习,借助自举法
(2)根据一个猜测值更新另一个猜测值

2、TD的本质思想

类似MC,使用回报的均值估计期望,最后更新变为在当前基础上加上学习率 ∗ * 差值。所以类似的,TD是根据Bellman方程进行估计,也有期望,那么类似MC,也是使用到了差值,在当前的基础上+学习率 ∗ * 差值,差值的获得根据Bellman方程
当前已经有一个猜测值,期望减少和真实值之间的误差,由猜测值得到的值作为其对真实值更精确的估计。

3、TD算法

时间差分,根据考虑的时间步数的不同,可以分为 T D ( 0 ) TD(0) TD(0) T D ( λ ) TD(\lambda) TD(λ)算法。
这里的TD算法是进行预测,如果是进行估计那就是叫(Srasa,sarsa(lambda))

TD(0)
1、算法过程

(1)给定策略 π , 初 始 状 态 分 布 D , V ( S ) = 0 , α , t = 0 \pi,初始状态分布D,V(S)=0,\alpha,t=0 πDV(S)=0,α,t=0
(2)如果 S t = S t e r m i n a l S_t=S_{terminal} St=Sterminal或者 s t s_t st没有初始化,那么初始化: S t ∼ D S_t\sim D StD
(3)采样动作: a t ∼ π a_t\sim \pi atπ
执行 a t a_t at观测得到 R t + 1 R_{t+1} Rt+1 S t + 1 S_{t+1} St+1.
(4)根据 ( S t , R t + 1 , S t + 1 ) (S_t,R_{t+1},S_{t+1}) (St,Rt+1,St+1)更新: V ( S t ) = V ( S t ) + α ( R t + 1 + γ V ( S t + 1 ) − V ( S t ) ) t = t + 1 V(S_t)=V(S_{t})+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t))\\t=t+1 V(St)=V(St)+α(Rt+1+γV(St+1)V(St))t=t+1
回到(2)。

PS:TD目标: R t + 1 + γ V ( s t + 1 ) R_{t+1}+\gamma V(s_{t+1}) Rt+1+γV(st+1)
TD误差: δ t = R t + 1 + γ V ( S t + 1 ) − V ( S t ) \delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t) δt=Rt+1+γV(St+1)V(St)

2、 α \alpha α的选取

(1) α \alpha α小,学习慢,曲线平滑
(2) α \alpha α大,学习快,震荡明显,且可能越过真实值,一直震荡

TD( λ \lambda λ)
1、n步回报

MC是无穷步回报,TD是一步回报,将两者结合,在TD学习中增加回报的计算步数。
G t ( n ) = R t + 1 + γ R t + 2 + . . . + γ ( n − 1 ) R t + n + γ n v ( S t + n ) G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+...+\gamma^{(n-1)}R_{t+n}+\gamma^nv(S_{t+n}) Gt(n)=Rt+1+γRt+2+...+γ(n1)Rt+n+γnv(St+n)
n步回报时间差分学习:
v ( S t ) = v ( S t ) + α ( G t ( n ) − v ( S t ) ) v(S_t)=v(S_t)+\alpha (G_t^{(n)}-v(S_t)) v(St)=v(St)+α(Gt(n)v(St))

TD与n步回报误差比较:
(1)TD(一步回报误差),使用一步期望估计价值函数,即代替回报的期望: m a x ∣ E [ G t ( 1 ) ] − v π ( s t ) ∣ = m a x ∣ R t + 1 + γ v π ( s t + 1 ) − v ( s t ) ∣ = m a x ∣ R t + 1 + γ v ( s t + 1 ) − ( R t + 1 + γ v π ( s t + 1 ) ) ∣ ≤ γ ∣ ∣ v − v π ∣ ∣ ∞ max|E[G_t^{(1)}]-v_\pi(s_t)|=max|R_{t+1}+\gamma v_\pi(s_{t+1})-v(s_t)|\\=max|R_{t+1}+\gamma v(s_{t+1})-(R_{t+1}+\gamma v_\pi(s_{t+1}))|\\\leq\gamma||v-v_\pi||_\infty maxE[Gt(1)]vπ(st)=maxRt+1+γvπ(st+1)v(st)=maxRt+1+γv(st+1)(Rt+1+γvπ(st+1))γvvπ
(2)n步回报:
m a x ∣ E [ G t ( n ) ] − v π ( s t ) ∣ ≤ γ n ∣ ∣ v − v π ∣ ∣ ∞ max|E[G_t^{(n)}]-v_\pi(s_t)|\leq\gamma^n||v-v_\pi||_\infty maxE[Gt(n)]vπ(st)γnvvπ

使用机器学习中的方差-偏差分析:
(1)n大,价值估计准确性高,偏差小,但是随着采样数据的增加,方差大
(2)n小,价值估计准确性低,偏差大,但是采样数据少,方差小

那么n应该怎样取值?
均值化n步回报

2、 λ \lambda λ回报

将所有n步回报整合在一起,系数为 ( 1 − λ ) λ (1-\lambda)\lambda (1λ)λ: 无 穷 步 轨 迹 : G t ( λ ) = ( 1 − λ ) ∑ n = 1 ∞ λ n − 1 G t ( n ) 无穷步轨迹:G_t^{(\lambda)}=(1-\lambda)\sum_{n=1}^\infty\lambda^{n-1}G_t^{(n)} Gt(λ)=(1λ)n=1λn1Gt(n)
轨 迹 在 T 终 止 : G t ( λ ) = ( 1 − λ ) ∑ n = 1 T − t − 1 λ n − 1 G t ( n ) + λ ( T − t + 1 ) G t 轨迹在T终止:G_t^{(\lambda)}=(1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{n-1}G_t^{(n)}+\lambda^{(T-t+1)}G_t TGt(λ)=(1λ)n=1Tt1λn1Gt(n)+λ(Tt+1)Gt

3、前向 T D ( λ ) TD(\lambda) TD(λ)

v ( S t ) = v ( S t ) + α ( G t ( λ ) − v ( S t ) ) v(S_t)=v(S_t)+\alpha(G_t^{(\lambda)}-v(S_t)) v(St)=v(St)+α(Gt(λ)v(St))

好处:之前n步回报的缺点是方差增大,但是这里随着n的增加,其权重不断减小,因此既利用了长步数估计的精度,又降低了高方差的影响

前向:对每个访问的状态,都是从其开始往前看所有未来的奖励,并结合这些奖励来更新价值函数。
特点:
(1)更新价值函数向 λ \lambda λ-回报逼近
(2)需要未来时刻的观测计算 G t ( λ ) G_t^{(\lambda)} Gt(λ)
(3)与MC一样要求完整的轨迹
(4)离线学习

4、资格迹

反映了被观测的次数和频率,结合了历史和现在
E t ( s ) = { γ λ E t − 1 , s t ≠ s γ λ E t − 1 + 1 , s t = s E_t(s)=\left\{\begin{array}{l}\gamma \lambda E_{t-1},s_t\neq s\\\gamma\lambda E_ {t-1}+1,s_t=s \end{array}\right. Et(s)={γλEt1,st=sγλEt1+1,st=s

5、后向 T D ( λ ) TD(\lambda) TD(λ)

使用TD估计价值函数,误差由过程中的状态共同导致,资格迹表征了每个状态对误差的贡献,如何权分误差:使用资格迹。
(1)、任意初始化 V ( s ) V(s) V(s)
(2)、每个episode重复(3)(4)
(3)、E(S)=0
(4)、对episode的每一步:
a、 a ∼ π a\sim\pi aπ,执行动作 观测奖励r和下一个状态s’
b、 δ = r + γ v ( s ′ ) − v ( s ) , E ( s ) = E ( s ) + 1 \delta=r+\gamma v(s')-v(s),E(s)=E(s)+1 δ=r+γv(s)v(s),E(s)=E(s)+1
c、对所有的状态分摊误差: V ( S ) = V ( S ) + α δ E ( S ) V(S)=V(S)+\alpha\delta E(S) V(S)=V(S)+αδE(S)
E ( S ) = γ λ E ( S ) E(S)=\gamma\lambda E(S) E(S)=γλE(S)
d、 s ← s ′ s\leftarrow s' ss
问题:误差的求解是根据当前步得到的,但是更新的时候是将误差平坦到所有的状态,这时候需要对所有的状态更新,那么需要知道所有的状态,对于连续状态的问题涉及的状态是无穷的,这个问题的本质就是状态空间太大,状态空间太大的问题将通过价值函数逼近器的方法解决。
这里仍然是无模型的,无模型指的是不知道动作奖励函数和转移概率,并不是不知道所有的状态,注意区分。

6、前向和后向 T D ( λ ) TD(\lambda) TD(λ)

定理:当使用离线更新时,后向和前向 T D ( λ ) TD(\lambda) TD(λ)在同一轨迹上的更新量时相同的:
∑ t = 0 T Δ V t T D ( S ) = ∑ t = 0 T Δ V t = 0 λ ( s t ) I ( S = s t )       任 意 的 s ∈ S Δ V t T D ( S ) = α δ t E t ( S ) Δ V t λ ( s t ) = α ( G t λ − V t ( s t ) ) \sum_{t=0}^T\Delta V_t^{TD}(S)=\sum_{t=0}^T\Delta V_{t=0}^\lambda(s_t)I(S=s_t)~~~~~任意的s\in S \\ \Delta V_t^{TD}(S)=\alpha\delta_tE_t(S) \\ \Delta V_t^\lambda (s_t)=\alpha(G_t^\lambda-V_t(s_t)) t=0TΔVtTD(S)=t=0TΔVt=0λ(st)I(S=st)     sSΔVtTD(S)=αδtEt(S)ΔVtλ(st)=α(GtλVt(st))
向前:轨迹中每遇到一次进行一次更新
向后:每一步都进行一次更新

前向 T D ( λ ) TD(\lambda) TD(λ),每遇到一次进行更新,那么一次更新为:
1 α Δ V t λ ( s t ) = G t λ − V t ( s t ) = − V t ( s t ) + ( 1 − λ ) ∑ n = 1 T − t − 1 λ n − 1 G t ( n ) + λ T − t − 1 G t = − V t ( s t ) + ( 1 − λ ) λ 0 ( R t + 1 + γ V t ( s t + 1 )     + ( 1 − λ ) λ 1 ( R t + 1 + γ R t + 2 + γ 2 V t ( s t + 2 )     + ( 1 − λ ) λ 2 ( R t + 1 + γ R t + 2 + γ 2 R t + 3 + γ 3 V t ( s t + 3 )       + . . . . . . . . = − V t ( s t ) + R t + 1 + γ λ R t + 2 + ( γ λ ) 2 R t + 3 + . . . . + + ( 1 − λ ) λ 0 γ V t ( s t + 1 ) + ( 1 − λ ) λ 1 γ 2 V t ( s t + 2 ) + . . . . = − V t ( s t ) + R t + 1 + γ λ R t + 2 + ( γ λ ) 2 R t + 3 + . . . . + ( γ λ ) 0 ( V t ( s t + 1 ) − γ λ V t ( s t + 1 ) + ( γ λ ) 1 ( V t ( s t + 2 ) − γ λ V t ( s t + 2 ) ) + . . . = ( γ λ ) 0 ( R t + 1 + V t ( s t + 1 ) − γ λ V t ( s t + 1 ) ) + ( γ λ ) 1 ( R t + 2 + V t ( s t + 2 ) − γ λ V t ( s t + 2 ) ) + . . . . = ∑ k = t T ( γ λ ) ( k − t ) δ k \frac{1}{\alpha}\Delta V_t^\lambda(s_t)=G_t^\lambda-V_t(s_t)\\=-V_t(s_t)+(1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{n-1}G_t^{(n)}+\lambda^{T-t-1}G_t\\=-V_t(s_t)+(1-\lambda)\lambda^0(R_{t+1}+\gamma V_{t}(s_{t+1})\\~~~+(1-\lambda)\lambda^1(R_{t+1}+\gamma R_{t+2}+\gamma^2V_t(s_{t+2})\\~~~+(1-\lambda)\lambda^2(R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\gamma^3V_t(s_{t+3})\\~~~~~+........\\=-V_t(s_t)+R_{t+1}+\gamma\lambda R_{t+2}+(\gamma\lambda)^2R_{t+3}+....+\\+(1-\lambda)\lambda^0\gamma V_t(s_{t+1})+(1-\lambda)\lambda^1\gamma^2 V_t(s_{t+2})+....\\=-V_t(s_t)+R_{t+1}+\gamma\lambda R_{t+2}+(\gamma\lambda)^2R_{t+3}+....+\\ (\gamma\lambda)^0(V_t(s_{t+1})-\gamma\lambda V_t(s_{t+1})+(\gamma\lambda)^1(V_t(s_{t+2})-\gamma\lambda V_t(s_{t+2}))+...\\=(\gamma\lambda)^0(R_{t+1}+V_t(s_{t+1})-\gamma\lambda V_t(s_{t+1}))+\\(\gamma\lambda)^1(R_{t+2}+V_t(s_{t+2})-\gamma\lambda V_t(s_{t+2}))+....\\=\sum_{k=t}^T(\gamma\lambda)^{(k-t)}\delta_k α1ΔVtλ(st)=GtλVt(st)=Vt(st)+(1λ)n=1Tt1λn1Gt(n)+λTt1Gt=Vt(st)+(1λ)λ0(Rt+1+γVt(st+1)   +(1λ)λ1(Rt+1+γRt+2+γ2Vt(st+2)   +(1λ)λ2(Rt+1+γRt+2+γ2Rt+3+γ3Vt(st+3)     +........=Vt(st)+Rt+1+γλRt+2+(γλ)2Rt+3+....++(1λ)λ0γVt(st+1)+(1λ)λ1γ2Vt(st+2)+....=Vt(st)+Rt+1+γλRt+2+(γλ)2Rt+3+....+(γλ)0(Vt(st+1)γλVt(st+1)+(γλ)1(Vt(st+2)γλVt(st+2))+...=(γλ)0(Rt+1+Vt(st+1)γλVt(st+1))+(γλ)1(Rt+2+Vt(st+2)γλVt(st+2))+....=k=tT(γλ)(kt)δk
则:
∑ t = 0 T Δ V t λ ( s t ) I ( s = s t ) = ∑ t = 0 T α I ( s = s t ) ∑ k = t T ( γ λ ) k − t δ k \sum_{t=0}^T\Delta V_t^\lambda(s_t)I(s=s_t)=\sum_{t=0}^T\alpha I(s=s_t)\sum_{k=t}^T(\gamma\lambda)^{k-t}\delta_k t=0TΔVtλ(st)I(s=st)=t=0TαI(s=st)k=tT(γλ)ktδk

后向 T D ( λ ) TD(\lambda) TD(λ),每一步都要进行一次更新:
首先,完整轨迹上的资格迹等于:
E t ( s ) = ∑ k = 0 t ( γ λ ) t − k I ( s k = s ) , 即 k 时 第 一 次 出 现 E_t(s)=\sum_{k=0}^t(\gamma\lambda)^{t-k}I(s_k=s),即k时第一次出现 Et(s)=k=0t(γλ)tkI(sk=s)k
那么后向的更新量:
∑ t = 0 T Δ V t T D ( s ) = ∑ t = 0 T α δ t ∑ k = 0 t ( γ λ ) t − k I ( s k = s ) = ∑ t = 0 T α ∑ k = t T ( γ λ ) t − k δ k I ( s k = s ) = ∑ t = 0 T α I ( s t = s ) ∑ k = t T ( γ λ ) t − k δ k ( 首 次 出 现 有 了 资 格 迹 之 后 才 在 之 后 的 每 一 步 都 进 行 更 新 ) \sum_{t=0}^T\Delta V_t^{TD}(s)=\sum_{t=0}^T\alpha\delta_t\sum_{k=0}^t(\gamma\lambda)^{t-k}I(s_k=s)\\=\sum_{t=0}^T\alpha\sum_{k=t}^T(\gamma\lambda)^{t-k}\delta_kI(s_k=s)\\=\sum_{t=0}^T\alpha I(s_t=s)\sum_{k=t}^T(\gamma\lambda)^{t-k}\delta_k \\(首次出现有了资格迹之后才在之后的每一步都进行更新) t=0TΔVtTD(s)=t=0Tαδtk=0t(γλ)tkI(sk=s)=t=0Tαk=tT(γλ)tkδkI(sk=s)=t=0TαI(st=s)k=tT(γλ)tkδk

因此,离线的时候前向和后向是等价的。
总结:

前向提供理论依据
后向给出算法实现
在离线更新时两者等价
但实际应用时往往使用在线的后向 T D ( λ ) TD(\lambda) TD(λ):在线学习、每一时刻更新、可以适用轨迹中的一小段,非完整轨迹

7、TD(0) & MC & TD( λ \lambda λ)

使用后向的角度进行关系寻找

λ = 0 \lambda=0 λ=0

资格迹: E t ( s ) = { 0 , S t ≠ s 1 , S t = s E_t(s)=\left\{\begin{array}{l}0,S_t\neq s\\1,S_t=s\end{array}\right. Et(s)={0,St=s1,St=s
更新量: Δ V t T D ( s ) = { 0 , S t ≠ s α δ t , S t = s \Delta V_t^{TD}(s)=\left\{\begin{array}{l}0,S_t\neq s\\\alpha\delta_t,S_t=s\end{array}\right. ΔVtTD(s)={0,St=sαδt,St=s
等同于TD(0): v ( s t ) ← v ( s t ) + α δ t v(s_t)\leftarrow v(s_t)+\alpha\delta_t v(st)v(st)+αδt

λ = 1 \lambda=1 λ=1

资格迹的累积: E t ( s ) = ∑ k = t T ( γ λ ) t − k = ∑ t = k T γ t − k 即 当 t = k 的 时 候 第 一 次 遇 到 该 状 态 , 此 后 的 每 一 步 才 对 误 差 进 行 摊 分 E_t(s)=\sum_{k=t}^T(\gamma\lambda)^{t-k}=\sum_{t=k}^T\gamma^{t-k}即当\\t=k \\的时候第一次遇到该状态,此后的每一步才对误差进行摊分 Et(s)=k=tT(γλ)tk=t=kTγtkt=k
那么假设离散更新,在整条轨迹上的更新量: Δ V t T D ( s ) = α ∑ t = k T δ k ( γ ) t − k = α δ k + γ δ k + 1 + . . . + γ T − k δ T = α [ ( R k + 1 + γ V t ( s k + 1 ) − V t ( s k ) ) + γ ( R k + 2 + γ V t ( s k + 2 ) − V t ( s k + 1 ) ) + . . . + γ T − k ( R T + 1 + 0 − V T ( s T ) ) ] = α ( R k + 1 + γ R k + 2 + . . . + γ T − k R T − V t ( s k ) ) = α ( G k − V t ( s k ) ) \Delta V_t^{TD}(s)=\alpha\sum_{t=k}^T\delta_k(\gamma)^{t-k}\\=\alpha\delta_k+\gamma\delta_{k+1}+...+\gamma^{T-k}\delta_T\\=\alpha[(R_{k+1}+\gamma V_t(s_{k+1})-V_t(s_k))+\\\gamma (R_{k+2}+\gamma V_t(s_{k+2})-V_t(s_{k+1}))+...\\+\gamma^{T-k}(R_{T+1}+0-V_T(s_T))]\\=\alpha(R_{k+1}+\gamma R_{k+2}+...+\gamma^{T-k}R_T-V_t(s_k))\\=\alpha(G_k-V_t(s_k)) ΔVtTD(s)=αt=kTδk(γ)tk=αδk+γδk+1+...+γTkδT=α[(Rk+1+γVt(sk+1)Vt(sk))+γ(Rk+2+γVt(sk+2)Vt(sk+1))+...+γTk(RT+1+0VT(sT))]=α(Rk+1+γRk+2+...+γTkRTVt(sk))=α(GkVt(sk))

所以离线TD(1)方法在同一个轨迹对某一状态的累计更新量等于该状态的MC更新。
但是实际上往往使用在线TD(1)方法,这是因为:
在线,增量式,学习效率高,对于MC要求整条轨迹结束后再更新。

总结与比较
1、MC & TD(0)

MC(采样):
(1)需要完整的轨迹

(2)零偏差,高方差

(3)好的收敛性,即使是使用逼近器也能保证收敛

(4)与价值函数初始值无关

(5)原理简单,使用方便

(6)MC对应最小二乘,没有利用马尔可夫性,不需要直到后续的状态,在非马尔可夫环境下同样有效

TD(0)(自举):
(1)不需要完整的轨迹,单步更新

(2)有偏差,低方差

(3)TD(0)能够收敛,但是与逼近器结合后没有收敛保证

(4)受价值函数初始值影响

(5)TD收敛结果对应最大似然马尔可夫模型,利用了马尔可夫性,需要直到后续状态,在马尔可夫环境下更加有效

2、 MC/TD/DP
自举

更新时包含一个猜测量:TD,DP

采样

使用采样的数据计算期望:TD,MC

(2)控制问题:求解Bellman最优方程

基于模型的控制

控制问题求解的是Bellman最优方程:
V ∗ ( s ) = m a x a ( R s a + ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) ) V_*(s)=\underset{a}{max}(R_s^a+\sum_{s'\in S}P_{ss'}^av_\pi(s')) V(s)=amax(Rsa+sSPssavπ(s))
Bellman最优方程是非线性方程,不能直接求解,但是其仍有动态规划的特点,因此也采用迭代的方式求解。
同样的,基于模型的控制我们仍然直到下面两个条件:
(1) R s a R_s^a Rsa
(2) P s s ′ a P_{ss'}^a Pssa
基于模型的控制有两种方法:价值迭代和策略迭代

价值迭代

(1)、初始化一个函数 V 1 V_1 V1
(2)、根据已知的价值函数 V k V_k Vk更新一个新的函数:
v k + 1 ( s ) = m a x a ( R s a + γ ∑ s ′ ∈ A P s s ′ a v k ( s ) ) k = k + 1 v_{k+1}(s)=\underset{a}{max}(R_s^a+\gamma\sum_{s'\in A}P_{ss'}^av_{k}(s))\\k=k+1 vk+1(s)=amax(Rsa+γsAPssavk(s))k=k+1
(3)、重复(2)直到收敛或者误差达到一定的范围
收敛性证明:
首先定义价值迭代算子 τ ( v ) = m a x a ( R s a + γ ∑ s ′ ∈ S P s s ′ a v ) \tau(v)=\underset{a}{max}(R_s^a+\gamma \sum_{s'\in S}P_{ss'}^av) τ(v)=amax(Rsa+γsSPssav)
∣ [ τ ( u ) ] ( s ) − [ τ ( v ) ] ( s ) ∣ ≤ ∣ ∣ [ τ ( u ) ] ( s ) − [ τ ( v ) ] ( s ) ∣ ∣ ∞ = ∣ ∣ [ m a x a R s a + γ ∑ s ′ ∈ S P s s ′ a u ( s ′ ) ] − [ m a x a R s a + γ ∑ s ′ ∈ S P s s ′ a v ( s ′ ) ] ∣ ∣ ∞ ≤ m a x a ∣ ∣ γ ∑ s ′ ∈ S P s s ′ a ( u ( s ′ ) − v ( s ′ ) ) ∣ ∣ ∞ ≤ γ ∣ ∣ u ( s ′ ) − v ( s ′ ) ∣ ∣ ∞ |[\tau(u)](s)-[\tau(v)](s)|\leq||[\tau(u)](s)-[\tau(v)](s)||_\infty\\=||[\underset{a}{max}R_s^a+\gamma \sum_{s'\in S}P_{ss'}^au(s')]-[\underset{a}{max}R_s^a+\gamma\sum_{s'\in S}P_{ss'}^av(s')]||_\infty\\\le\underset{a}{max}||\gamma\sum_{s'\in S}P_{ss'}^a(u(s')-v(s'))||_\infty\\\leq\gamma||u(s')-v(s')||_\infty [τ(u)](s)[τ(v)](s)[τ(u)](s)[τ(v)](s)=[amaxRsa+γsSPssau(s)][amaxRsa+γsSPssav(s)]amaxγsSPssa(u(s)v(s))γu(s)v(s)
因此,当 γ < 1 \gamma<1 γ<1的时候价值迭代算子 τ \tau τ就是收缩算子,则:
∣ ∣ v k + 1 ( s ) − v ∗ ( s ) ∣ ∣ ∞ = ∣ ∣ [ τ ( v k + 1 ) ] ( s ) − [ τ ( v ∗ ) ] ( s ) ∣ ∣ ∞ ≤ γ ∣ ∣ v k ( s ′ ) − v ∗ ( s ′ ) ∣ ∣ ∞ ≤ γ k ∣ ∣ v 1 ( s ′ ) − u ∗ ( s ′ ) ∣ ∣ ∞ k → ∞ , v k → v ∗ ||v_{k+1}(s)-v_*(s)||_\infty=||[\tau(v_{k+1})](s)-[\tau(v_*)](s)||_\infty\\\leq\gamma||v_k(s')-v_*(s')||_\infty\\\leq\gamma^k||v_1(s')-u_*(s')||_\infty\\k\rightarrow\infty,v_k\rightarrow v_* vk+1(s)v(s)=[τ(vk+1)](s)[τ(v)](s)γvk(s)v(s)γkv1(s)u(s)k,vkv
γ = 1 \gamma=1 γ=1的收敛性证明见PPT lecture3 page15

策略迭代

(1)给定一个初始策略 π 1 , k = 1 \pi_1,k=1 π1,k=1
(2)策略评估:对当前的策略使用Bellman期望方程计算价值函数:
v π k ( s ) = ∑ a ∈ A π ( a ∣ s ) ( R s a + ∑ s ′ ∈ S P s s ′ a v π k ( s ′ ) ) v_{\pi k}(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\sum_{s'\in S}P_{ss'}^av_{\pi k}(s')) vπk(s)=aAπ(as)(Rsa+sSPssavπk(s))
(3)策略提升:根据计算得到的价值函数进行贪心策略提升:
π k + 1 ( s ) = m a x a ( R s a + ∑ s ′ ∈ S P s s ′ a v π k ( s ′ ) ) k = k + 1 \pi_{k+1}(s)=\underset{a}{max}(R_s^a+\sum_{s'\in S}P_{ss'}^av_{\pi k}(s'))\\k=k+1 πk+1(s)=amax(Rsa+sSPssavπk(s))k=k+1
(4)收敛则停止,或者达到一定的精度停止。

收敛性证明:
注意点:上述的策略提升的时候,只是进行了一步提升,先证明不断一步提升可以收敛到最优策略。
a、考虑确定性策略 s = π ( s ) s=\pi(s) s=π(s)
b、从已知的策略进行贪心提升(一步提升):
π ′ ( s ) = m a x a ( R s a + ∑ s ′ ∈ A P s s ′ a v π ( s ′ ) ) = m a x a Q π ( s , a ) \pi'(s)=\underset{a}{max}(R_s^a+\sum_{s'\in A}P_{ss'}^av_\pi(s'))\\=\underset{a}{max}Q_\pi(s,a) π(s)=amax(Rsa+sAPssavπ(s))=amaxQπ(s,a)
c、上述过程提升了s的一步期望:
Q π ( s , π ′ ) = m a x a Q π ( s , a ) ≥ Q π ( s , π ( s ) ) = v π ( s ) Q_\pi(s,\pi')=\underset{a}{max}Q_\pi(s,a)\\\ge Q_\pi(s,\pi(s))=v_\pi(s) Qπ(s,π)=amaxQπ(s,a)Qπ(s,π(s))=vπ(s)
d、 v π ( s ) ≤ Q π ( s t , π ′ ( s t ) ) = E [ R t + 1 + γ v π ( s t + 1 ) ∣ a t = π ′ ( s t ) , a k = π ( s k ) , k > t ] = R ( s t , π ′ ( s t ) ) + γ ∑ s t + 1 P s t s t + 1 π ′ v π ( s t + 1 ) ≤ R ( s t , π ′ ( s t ) ) + γ ∑ s t + 1 P s t s t + 1 π ′ ( R ( s t + 1 , π ′ ( s t + 1 ) ) + γ ∑ s t + 2 P s t + 1 s t + 2 π ′ v π ( s t + 2 ) ) ≤ . . . ≤ E [ R t + 1 + γ R t + 2 + . . . ∣ a k = π ′ ( s k ) , k ≥ t ] = v π ′ ( s t ) v_\pi(s)\le Q_\pi(s_t,\pi'(s_t))\\=E[R_{t+1}+\gamma v_\pi(s_{t+1})|a_t=\pi'(s_t),a_k=\pi(s_k),k>t]\\=R(s_t,\pi'(s_t))+\gamma\sum_{s_{t+1}}P_{s_ts_{t+1}}^{\pi'}v_\pi(s_{t+1})\\\leq R(s_t,\pi'(s_t))+\gamma \sum_{s_{t+1}}P_{s_ts_{t+1}}^{\pi'}(R(s_{t+1},\pi'(s_{t+1}))+\\\gamma \sum_{s_{t+2}}P_{s_{t+1}s_{t+2}}^{\pi'}v_\pi(s_{t+2}))\\\leq...\\\leq E[R_{t+1}+\gamma R_{t+2}+...|a_k=\pi'(s_k),k\ge t]\\=v_{\pi'}(s_t) vπ(s)Qπ(st,π(st))=E[Rt+1+γvπ(st+1)at=π(st),ak=π(sk),k>t]=R(st,π(st))+γst+1Pstst+1πvπ(st+1)R(st,π(st))+γst+1Pstst+1π(R(st+1,π(st+1))+γst+2Pst+1st+2πvπ(st+2))...E[Rt+1+γRt+2+...ak=π(sk),kt]=vπ(st)
e、即提升了策略价值函数,这里讨论的是确定性策略,对随机性策略仍然成立。不断提升,最终收敛到价值函数值最大的 v ∗ v_* v
f、 π ∞ ( s ) = m a x a ( R s a + ∑ s ′ ∈ S P s s ′ a v π ∞ ( s ′ ) ) \pi_\infty(s)=\underset{a}{max}(R_s^a+\sum_{s'\in S}P_{ss'}^av_{\pi_\infty}(s')) π(s)=amax(Rsa+sSPssavπ(s))
满足Bellman最优方程,所以:
v π ∞ = v ∗ , π ∞ = π ∗ v_{\pi\infty}=v_*,\pi_{\infty}=\pi_* vπ=v,π=π

总结

(1)价值迭代基于Bellman最优方程,策略迭代即使用了Bellman最优方程(策略提升),也使用了Bellman期望方程(策略评估)。
(2)价值迭代收敛之后得到最优策略,但是中间过程不产生策略;
策略迭代每次迭代开始时给定一个策略,结束时产生一个新的策略。
(3)价值迭代涉及赋值操作,计算量小, O ( ∣ S ∣ 2 ∣ A ∣ ) O(|S|^2|A|) O(S2A)
策略迭代矩阵求逆为 O ( ∣ S ∣ 3 ) O(|S|^3) O(S3),策略提升的代价为 O ( ∣ S ∣ 2 ∣ A ∣ ) O(|S|^2|A|) O(S2A)
(4)价值迭代通常迭代次数多
策略迭代通常迭代次数少

无模型的控制

控制即找到最优的策略,价值迭代需要基于模型的信息,所以从策略迭代的方法入手,看是否能在无模型的条件下解决控制问题。
策略迭代分为策略评估和策略提升。
策略评估即求解Bellman期望方程,即可以使用无模型的预测方法:MC和TD进行策略评估。
策略提升即求解Bellman最优方程,仍然需要模型的信息,基于行为价值函数的策略提升是无模型的:
π ′ ( s ) = a r g m a x a Q ( s , a ) \pi'(s)=arg\underset{a}{max}Q(s,a) π(s)=argamaxQ(s,a)
问题:
单纯使用贪心策略,可能会导致陷入局部最优,因此要进行探索。
(1)在线学习需要具有探索性的策略
(2)保证获得尽可能全面的模型观测数据
最简单的探索策略: ϵ − g r e e d y \epsilon-greedy ϵgreedy
π ( s ) = ϵ − g r e e d y ( Q ) ( s ) = { a r g m a x a Q ( s , a )   w i t h   p r o b a b i l i t y   ϵ / m + 1 − ϵ r a n d o m   a   w i t h   p r o b a b i l i t y   ϵ / m \pi(s)=\epsilon-greedy(Q)(s)\\=\left\{\begin{array}{l}arg\underset{a}{max}Q(s,a)~with~probability~\epsilon/m+1-\epsilon\\random~a~with~probability~\epsilon/m\end{array}\right. π(s)=ϵgreedy(Q)(s)={argamaxQ(s,a) with probability ϵ/m+1ϵrandom a with probability ϵ/m

1、MC+行为-价值函数提升
(1)单轨迹评估策略

MC对一个策略的价值评估需要多条轨迹,能否每次策略评估的时候只使用一条轨迹:
GLIE(无限探索下的极限贪心):当对状态行为对访问无数多次的时候,其会收敛到贪心策略。
当MC中的贪心探索的概率随着训练次数的增加趋近0,那么相当于已经对问题的状态有了比较全的探索,即访问了无数次,所以满足了GLIE,会收敛到贪心策略。
所以MC策略控制中要求探索的概率随着探索次数的增加趋近0

(2)MC控制学习

a、初始化 Q ( S , A ) , N ( S , A ) = 0 , ϵ = 1 , k = 1 Q(S,A),N(S,A)=0,\epsilon=1,k=1 Q(S,A),N(S,A)=0,ϵ=1,k=1
b、 π k = ϵ − g r e e d y ( Q ) \pi_k=\epsilon-greedy(Q) πk=ϵgreedy(Q)
c、使用 π k \pi_k πk得到第k个轨迹,时间为0到T,t=0,1,2,…T:
如果 ( s t , a t ) (s_t,a_t) (st,at)是轨迹上首次访问,那么计算(策略评估):
得 到 G t N ( s t , a t ) + = 1 Q ( s t , a t ) = Q ( s t , a t ) + 1 N ( s t , a t ) ( G t − Q ( s t , a t ) ) 得到G_t\\N(s_t,a_t)+=1\\Q(s_t,a_t)=Q(s_t,a_t)+\frac{1}{N(s_t,a_t)}(G_t-Q(s_t,a_t)) GtN(st,at)+=1Q(st,at)=Q(st,at)+N(st,at)1(GtQ(st,at))
d、 k = k + 1 , ϵ = 1 k π k = ϵ − g r e e d y ( Q ) k = k+1,\epsilon=\frac{1}{k}\\\pi_k=\epsilon-greedy(Q) k=k+1,ϵ=k1πk=ϵgreedy(Q)策略提升

3、定理

GLIE MC控制是收敛到最优动作-价值函数的。

但是实际算法运行的时候, ϵ \epsilon ϵ更多使用的是一个固定的常值,保证新观测的数据对更新的有效性:时间差分+策略提升。

2、TD+行为-价值函数提升

to be continued
在这里插入图片描述