强化学习理论基础

2024-02-21 09:27:16

强化学习理论基础

强化学习理论基础

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[Gt​∣St​=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​+s′∈S∑​P(St+1​=s′∣St​=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​+γa∈A∑​π(a∣s)s′∈S∑​Pss′a​vπ​(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​+γs′∈S∑​Pss′a​a′∈A∑​π(a′∣s′)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)=a∈A∑​π(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[Gt​∣St​=s,At​=a]=Rsa​+γs′∈S∑​Pss′a​vπ​(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)=a∈A∑​π(s,a)(Rsa​+γs′∈S∑​Pss′a​vπ​(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​+γs′∈S∑​Pss′​a′∈A∑​π(a′∣s′)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)=πarg​maxvπ​(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)=πarg​maxQπ​(s,a)  for  any  state−action  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. π∗​(a∣s)={1,if  a=aarg​maxQ∗​(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)=πarg​maxvπ​(s)=πarg​maxa∈A∑​π(s,a)Qπ​(s,a)=πarg​maxQπ​(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)=a∈Amax​Rsa​+γs′∈S∑​Pss′a​v∗​(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​+γs′∈S∑​Pss′a​a′∈Amax​Q∗​(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)=amax​Rsa​+γs′∈S∑​Pss′a​v∗​(s′)
π ∗ ( s ) = m a x a Q ∗ ( s , a ) \pi_*(s)=\underset{a}{max}Q_*(s,a) π∗​(s)=amax​Q∗​(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+1​∣St​=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] Pss′a​=P[St+1​=s′∣St​=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)=a∈A∑​π(a∣s)(Rsa​+γs′∈S∑​Pss′a​vπ​(s′))

基于模型的预测

基于模型的预测也就是知道了下面两个条件：
（1） R s a R_s^a Rsa​
（2） P s s ′ a P_{ss'}^a Pss′a​

解线性方程

因为知道了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π​=a∈A∑​π(a∣s)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′π​=a∈A∑​π(a∣s)Pss′a​
那么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)=a∈A∑​π(a∣s)(Rsa​+γs′∈S∑​Pss′a​Vl​(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πu−Rπ−γPπv∣∣∞​=∣∣γPπ(u−v)∣∣∞​≤∣∣γPπ∣∣u−v∣∣∞​∣∣∞​≤γ∣∣u−v∣∣∞​
当 γ < 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=1N​Gt(i)​​=N(s)1​(Gt(N)​+i=1∑N−1​Gt(i)​)=N(s)1​(Gt(N)​+(N(s)−1)V(s))=V(s)+N(s)1​(Gt​−V(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)+α(Gt​−V(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 π，初始状态分布D，V(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 St​∼D
（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​+...+γ(n−1)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 max∣E[Gt(1)​]−vπ​(st​)∣=max∣Rt+1​+γvπ​(st+1​)−v(st​)∣=max∣Rt+1​+γv(st+1​)−(Rt+1​+γvπ​(st+1​))∣≤γ∣∣v−vπ​∣∣∞​
（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 max∣E[Gt(n)​]−vπ​(st​)∣≤γn∣∣v−vπ​∣∣∞​

使用机器学习中的方差-偏差分析：
（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∑∞​λn−1Gt(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 轨迹在T终止：Gt(λ)​=(1−λ)n=1∑T−t−1​λn−1Gt(n)​+λ(T−t+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)={γλEt−1​,st​​=sγλEt−1​+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' s←s′
问题：误差的求解是根据当前步得到的，但是更新的时候是将误差平坦到所有的状态，这时候需要对所有的状态更新，那么需要知道所有的状态，对于连续状态的问题涉及的状态是无穷的，这个问题的本质就是状态空间太大，状态空间太大的问题将通过价值函数逼近器的方法解决。
这里仍然是无模型的，无模型指的是不知道动作奖励函数和转移概率，并不是不知道所有的状态，注意区分。

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=0∑T​ΔVtTD​(S)=t=0∑T​ΔVt=0λ​(st​)I(S=st​)     任意的s∈SΔVtTD​(S)=αδt​Et​(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=1∑T−t−1​λn−1Gt(n)​+λT−t−1Gt​=−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=t∑T​(γλ)(k−t)δ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=0∑T​ΔVtλ​(st​)I(s=st​)=t=0∑T​αI(s=st​)k=t∑T​(γλ)k−tδ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=0∑t​(γλ)t−kI(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=0∑T​ΔVtTD​(s)=t=0∑T​αδt​k=0∑t​(γλ)t−kI(sk​=s)=t=0∑T​αk=t∑T​(γλ)t−kδk​I(sk​=s)=t=0∑T​αI(st​=s)k=t∑T​(γλ)t−kδ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​(γλ)t−k=∑t=kT​γt−k即当t=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=k∑T​δk​(γ)t−k=αδk​+γδk+1​+...+γT−kδT​=α[(Rk+1​+γVt​(sk+1​)−Vt​(sk​))+γ(Rk+2​+γVt​(sk+2​)−Vt​(sk+1​))+...+γT−k(RT+1​+0−VT​(sT​))]=α(Rk+1​+γRk+2​+...+γT−kRT​−Vt​(sk​))=α(Gk​−Vt​(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​+s′∈S∑​Pss′a​vπ​(s′))
Bellman最优方程是非线性方程，不能直接求解，但是其仍有动态规划的特点，因此也采用迭代的方式求解。
同样的，基于模型的控制我们仍然直到下面两个条件：
（1） R s a R_s^a Rsa​
（2） P s s ′ a P_{ss'}^a Pss′a​
基于模型的控制有两种方法：价值迭代和策略迭代

价值迭代

（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​+γs′∈A∑​Pss′a​vk​(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​+γs′∈S∑​Pss′a​v)
∣ [ τ ( 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)∣∣∞​=∣∣[amax​Rsa​+γs′∈S∑​Pss′a​u(s′)]−[amax​Rsa​+γs′∈S∑​Pss′a​v(s′)]∣∣∞​≤amax​∣∣γs′∈S∑​Pss′a​(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′)∣∣∞​≤γk∣∣v1​(s′)−u∗​(s′)∣∣∞​k→∞,vk​→v∗​
γ = 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)=a∈A∑​π(a∣s)(Rsa​+s′∈S∑​Pss′a​vπ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​+s′∈S∑​Pss′a​vπ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​+s′∈A∑​Pss′a​vπ​(s′))=amax​Qπ​(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,π′)=amax​Qπ​(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+1​∑​Pst​st+1​π′​vπ​(st+1​)≤R(st​,π′(st​))+γst+1​∑​Pst​st+1​π′​(R(st+1​,π′(st+1​))+γst+2​∑​Pst+1​st+2​π′​vπ​(st+2​))≤...≤E[Rt+1​+γRt+2​+...∣ak​=π′(sk​),k≥t]=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​+s′∈S∑​Pss′a​vπ∞​​(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(∣S∣2∣A∣)
策略迭代矩阵求逆为 O ( ∣ S ∣ 3 ) O(|S|^3) O(∣S∣3)，策略提升的代价为 O ( ∣ S ∣ 2 ∣ A ∣ ) O(|S|^2|A|) O(∣S∣2∣A∣)
（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)=argamax​Q(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)={argamax​Q(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)) 得到Gt​N(st​,at​)+=1Q(st​,at​)=Q(st​,at​)+N(st​,at​)1​(Gt​−Q(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
强化学习理论基础

上一篇：周金瑞11.9黄金行情预测，原油趋势分析及白银操作建议解套在线


下一篇：数据类型定义语句