David Silver强化学习公开课自学笔记——Lec4不基于模型的预测

本笔记摘自知乎博主旺财的搬砖历险记和叶强，仅用于自学

1.Introduction

（1）概述

• 上节：使用动态规划解决已知模型（转移矩阵 P和奖励函数 R）的MDP问题
  • 通过动态规划来评估一个给定的策略，通过不断迭代最终得到最优价值函数
    • 值迭代
    • 策略迭代
• 本节：模型预测——模型未知，评估MDP问题的值函数
  • 在给定的策略同时不清楚MDP细节的情况下，估计Agent会得到怎样的最终奖励
• 下节：模型控制——模型未知，优化MDP问题的值函数
  • 利用本节的方法来进行控制进而找出最优策略，最大化Agent的奖励

（2）本节内容引入

模型未知时，不能用贝尔曼方程 v π ( s ) = ∑ a ∈ A π ( a ∣ s ) ( R s a + γ ∑ s ′ ∈ S P S S ′ a v π ( s ′ ) ) v_\pi(s)=\sum_{a\in \mathcal{A}}\pi(a\vert s)(\mathcal{R}_s^a+\gamma\sum_{s^\prime\in S}\mathcal{P}_{SS^\prime}^av\pi(s^\prime)) vπ​(s)=∑a∈A​π(a∣s)(Rsa​+γ∑s′∈S​PSS′a​vπ(s′))来求解得到最优策略，因为不知道状态转移概率

💗解决方案：引入蒙特卡洛方法

• 为了从环境中学习，需要让agent与环境交互，得到一些样本，本质上相当于从概率分布 R s a \mathcal{R}_s^a Rsa​和 P S S ′ a \mathcal{P}_{SS^\prime}^a PSS′a​中采样
• 然后通过这些样本来进行策略评估和策略迭代，从而得到最终策略

（3）动态规划与无模型学习的对比

	无模型学习	动态规划
环境模型	环境模型未知	环境模型已知
是否需要交互	需要与环境交互，有交互成本	不需要直接交互，利用环境模型推导
备份	样本备份	全宽备份
备份方式	异步备份	同步备份和异步备份
是否需要探索	需要充分探索	不需要探索
策略	行为策略和目标策略	一个策略

2.蒙特卡洛强化学习方法 Monte-Carlo Reinforcement Learning

（1）MC方法简介

1)蒙特卡洛方法

当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解

2)RL使用MC的原因

马尔科夫决策过程（MDP）是通过5元组 $⟨\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ⟩$来做决策的。模型已知时（5元组已知），很容易获得奖赏最大化。但是，无法在现实世界同时知道这个5元组。
虽然不知道状态转移概率 $\mathcal{P}$，但是这个概率真实存在。可以直接尝试，不断采样，然后会得到奖赏，通过奖赏来评估值函数。这与蒙特卡罗方法的思想一致。尝试很多次，最后估计的 V 值就会很接近真实 V 值。

3)蒙特卡洛强化学习方法

是一种不基于模型（Model Free）的方法，指在不清楚MDP状态转移概率和即时奖励的情况下，直接从完整的Episode来学习状态价值，通常情况下某状态的价值等于在多个Episode中以该状态算得到的所有Return的平均

• MC直接从Episode的经验中学习
• MC不基于模型
• MC必须从完整的Episode中学习：没有bootstrapping
• MC使用的方法是：value = mean return
• MC只能应用于episodic MDPs：所有的Episode都必须终止
• Return不是针对于Episode的，而是针对于Episode的某一个状态，是从这个状态开始经历完Episode时得到的有衰减的即时奖励的总和。从一个Episode中，我们可以得到该Episode内所有状态的收获。当一个状态在Episode内出现多次，该状态的收获有不同的计算方法：first visit和every visit

💗注💗：Episode理解

• 每条Episode都是一条从起始状态到结束状态的经历。
• 要得到的是某个状态$s$的平均收获，所以episode必须经过该状态$s$才能用于计算
• 完整的Episode不要求起始状态一定是某一个特定的状态，但是要求个体最终进入环境认可的某一个终止状态
• 理论上完整的状态序列越多，结果越准确
• 完整的Episode包含：状态的转移、使用的行为序列、中间状态的即时奖励、终止状态的即时奖励

（2）MC Policy Evaluation

1)定义

🧡MC的目标

• 在给定策略$\pi$下，从一系列的完整Episode经历 S 1 , A 1 , R 2 , … , S t , A t , R t + 1 , … , S T ∼ π S_1,A_1,R_2,\ldots,S_t,A_t,R_{t+1},\ldots,S_T\sim \pi S1​,A1​,R2​,…,St​,At​,Rt+1​,…,ST​∼π中学习得到该策略下的状态价值函数 v π v_\pi vπ​
  🧡以前的计算方法
• 回报Return是所有折扣Reward的和： G t = R t + 1 + γ R t + 2 + … + γ T − 1 R T G_t=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1}R_T Gt​=Rt+1​+γRt+2​+…+γT−1RT​
  • 注： R t R_t Rt​指的是任何状态得到的即时奖励
    • 很多时候即时奖励只出现在episode结束状态时，但有时在中间状态也可能有即时奖励
• 值函数是期望回报： v π ( s ) = E [ G t ∣ S t = s ] v_\pi(s)=\mathbb{E}[G_t\vert S_t=s] vπ​(s)=E[Gt​∣St​=s]
  🧡MC策略评估使用经验平均回报来代替期望回报

2)计算Return的两种方法

a)首次访问蒙特卡洛策略评估 First-Visit Monte-Carlo Policy Evaluation

给定一个策略，使用一系列完整Episode评估某一个状态 $s$ 时，对于每一个Episode，仅当该状态 $s$ ==第一次==出现的时间 $t$ 列入计算：

• 状态出现的次数更新：$N(s)\leftarrow N(s)+1$
• 总收获值更新： S ( s ) ← S ( s ) + G t S(s)\leftarrow S(s)+G_t S(s)←S(s)+Gt​
• 状态$s$的价值更新：$V(s)=S(s)/N(s)$
• 值函数：当$N\to \infty$时， V ( s ) → v π ( s ) V(s)\rightarrow v_\pi(s) V(s)→vπ​(s)

b)每次访问蒙特卡洛策略评估 Every-Visit Monte-Carlo Policy Evaluation

给定一个策略，使用一系列完整Episode评估某一个状态s时，对于每一个Episode，状态s==每次==出现在状态转移链时，计算的具体公式与上面的一样，但具体意义不一样

• 每次状态出现，次数都会更新：$N(s)\leftarrow N(s)+1$
• 每次状态出现，总收获值都会更新： S ( s ) ← S ( s ) + G t S(s)\leftarrow S(s)+G_t S(s)←S(s)+Gt​
• 状态$s$的价值更新：$V(s)=S(s)/N(s)$
• 值函数：当$N\to \infty$时， V ( s ) → v π ( s ) V(s)\rightarrow v_\pi(s) V(s)→vπ​(s)

3)累进更新平均值 Incremental Mean

🧡引入

• 使用MC求解平均收获时，需要计算平均值，通常计算平均值要预先存储所有的数据，最后使用总和除以此次数➡引入更简单使用的方法Incremental Mean

🧡方法

• 在计算平均收获时不需要存储所有既往收获，而是每得到一次收获，就计算其平均收获

序列 x 1 , x 2 , … x_1,x_2,\ldots x1​,x2​,…的均值 μ 1 , μ 2 , … \mu_1,\mu_2,\ldots μ1​,μ2​,…可以累进计算： μ k = 1 k ∑ j = 1 k x j = 1 k ( x k + ∑ j = 1 k − 1 x j ) = 1 k ( x k + ( k − 1 ) μ k − 1 ) = μ k − 1 + 1 k ( x k − μ ( k − 1 ) ) \mu_k=\frac{1}{k}\sum_{j=1}^kx_j=\frac{1}{k}(x_k+\sum_{j=1}^{k-1}x_j)=\frac{1}{k}(x_k+(k-1)\mu_{k-1})=\mu_{k-1}+\frac{1}{k}(x_k-\mu(k-1)) μk​=k1​j=1∑k​xj​=k1​(xk​+j=1∑k−1​xj​)=k1​(xk​+(k−1)μk−1​)=μk−1​+k1​(xk​−μ(k−1))

• 在处理非静态问题时，使用这个方法跟踪一个实时更新的平均值是非常有用的，可以扔掉那些已经计算过的Episode信息

静态问题：MDP是不变的，比如转移矩阵，比如奖励函数
非静态问题：随着时间的推移，MDP中的某些参数将会发生改变

🧡蒙特卡洛累进更新 Incremental Monte-Carlo Updates

• 对于一系列的完整Episode（ S 1 , A 1 , R 2 , … , S T S_1,A_1,R_2,\ldots,S_T S1​,A1​,R2​,…,ST​）里的每一个状态 S t S_t St​，有一个收获 G t G_t Gt​：
  N ( S t ) ← N ( S t ) + 1 N(S_t)\leftarrow N(S_t)+1 N(St​)←N(St​)+1 V ( S t ) ← V ( S t ) + 1 N ( S t ) ( G t − V ( S t ) ) V(S_t) \leftarrow V(S_t)+\frac{1}{N(S_t)}(G_t-V(S_t)) V(St​)←V(St​)+N(St​)1​(Gt​−V(St​))
  🧡增量式MC
• 忘掉计数值 N ( S t ) N(S_t) N(St​)，而换为我们想要的类似于学习速率的参数，该参数的选择关乎算法的收敛性： V ( S t ) ← V ( S t ) + α ( G t − V ( S t ) ) V(S_t) \leftarrow V(S_t)+\alpha (G_t-V(S_t)) V(St​)←V(St​)+α(Gt​−V(St​))
  ♥注意♥：MC方法只能用于Episodic MDP，也即所有的Episode都要终止。不然我们算不了 G t G_t Gt​，因为 G t G_t Gt​是从 $t$ 时刻开始，对整个Episode的奖励进行累加的，显然，这种方法计算量会比较大，所以，引出了时间差分方法。

3.时序差分学习 Temporal-Difference Learning

（1）特点

• 和蒙特卡洛学习一样，它也从Episode学习，不需要了解模型本身
• 但它可以学习不完整的Episode，通过合理的引导（bootstrapping）
  • 先估计某状态在该状态序列完整后可能得到的收获
  • 在此基础上利用前文所述的累进更新平均值的方法得到该状态的价值
  • 通过不断的采样来持续更新这个价值
• TD通过bootstrapping猜测Episode的结果，同时持续更新这个猜测

（2）定义

🧡目标

• 通过策略$\pi$下的经验在线学习 v π v_\pi vπ​

🧡每次蒙特卡洛累进更新Incremental every-visit Monte-Carlo

• 使用所有的实际收获 G t G_t Gt​来更新价值 V ( S t ) V(S_t) V(St​) V ( S t ) ← V ( S t ) + α ( G t − V ( S t ) ) V(S_t) \leftarrow V(S_t)+\alpha (G_t-V(S_t)) V(St​)←V(St​)+α(Gt​−V(St​))

🧡简单的时序差分学习算法TD(0)
在TD学习中，算法在估计某一个状态的收获时，用的是离开该状态的即时奖励 R t + 1 R_{t+1} Rt+1​与下一时刻状态 S t + 1 S_{t+1} St+1​的预估状态价值 V ( S t + 1 ) V(S_{t+1}) V(St+1​)乘以衰减系数$\gamma$组成： V ( S t ) ← V ( S t ) + α ( R t + 1 + γ V ( S t + 1 ) − V ( S t ) ) V(S_t) \leftarrow V(S_t)+\alpha (R_{t+1}+\gamma V(S_{t+1})-V(S_t)) V(St​)←V(St​)+α(Rt+1​+γV(St+1​)−V(St​))

• TD目标值TD target： R t + 1 + γ V ( S t + 1 ) R_{t+1}+\gamma V(S_{t+1}) Rt+1​+γV(St+1​)
• TD误差TD error： δ 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​)

🧡引导bootstrapping

• 指用TD目标值代替收获 G t G_t Gt​ 的过程

🧡比较
显然，MC每次更新都需要等到agent到达终点之后再更新；而对于TD来说，agent每走一步它都可以更新一次，不需要等到到达终点之后才进行更新

（3）DP和TD对比

🧡DP利用了贝尔曼方程去解强化学习问题 V ( s ) ← E [ R + γ V ( S ′ ) ∣ s ] V(s)\leftarrow \mathbb{E}[R+\gamma V(S^\prime )\vert s] V(s)←E[R+γV(S′)∣s]
🧡TD也利用了贝尔曼方程，但是做了以下几点改动：

• 全宽备份→样本备份：$s\to S$
• 去掉了期望符号： V ( s ) ← R + γ V ( S ′ ) V(s)\leftarrow R+\gamma V(S^\prime ) V(s)←R+γV(S′)
• 增加了学习率： V ( s ) ← V ( s ) + α ( R + γ V ( S ′ ) − V ( S ) ) V(s)\leftarrow V(s)+\alpha(R+\gamma V(S^\prime )-V(S)) V(s)←V(s)+α(R+γV(S′)−V(S))

♥注意♥：

• agent跟智能体发生交互，采样到哪个状态就更新哪个状态
• 求期望有两种方法：
  • 利用概率密度函数加权求和➡DP
  • 利用采样去估计➡MC、TD

（4）MC和TD对比

1)优劣势方面

🧡TD可以在知道结果之前学习；MC只能在等到最后结果才能学习
🧡TD可以在没有最后结果时候学习，可以在持续进行的环境中学习；MC只能从有终止状态的完整序列中学习
🧡TD算法有奖励值和状态转移作为更新的驱动力；MC算法只有奖励值作为更新的驱动力

2)方差与均方差方面

🧡实际收获 G t G_t Gt​

• G t = R t + 1 + γ R t + 2 + … + γ T − 1 R T G_t=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1}R_T Gt​=Rt+1​+γRt+2​+…+γT−1RT​是基于某一策略状态价值 v π ( S t ) v_\pi(S_t) vπ​(St​)的无偏估计 unbiased estimate

🧡TD目标值 R t + 1 + γ V ( S t + 1 ) R_{t+1}+\gamma V(S_{t+1}) Rt+1​+γV(St+1​)

• 是基于下一状态预估价值计算的当前预估收获，是当前状态实际价值 v π ( S t ) v_\pi(S_t) vπ​(St​)的有偏估计 biased estimate

🧡真实TD目标值 R t + 1 + γ v π ( S t + 1 ) R_{t+1}+\gamma v_\pi(S_{t+1}) Rt+1​+γvπ​(St+1​)

• 是基于下一状态实际价值计算对当前状态实际价值 v π ( S t ) v_\pi(S_t) vπ​(St​)的无偏估计 unbiased estimate

假设$X$是一个随机变量，若 E { [ X − E ( X ) ] 2 } E\{[X-E(X)]^2\} E{[X−E(X)]2}存在，则：
💡 E { [ X − E ( X ) ] 2 } E\{[X-E(X)]^2\} E{[X−E(X)]2}为$X$的方差，记为$D(X)$或$Var(X)$，即 D ( X ) = V a r ( X ) = E { [ X − E ( X ) ] 2 } D(X)=Var(X)=E\{[X-E(X)]^2\} D(X)=Var(X)=E{[X−E(X)]2}
💡 D ( X ) \sqrt{D(X)} D(X) ​为$X$的均方差或均方差，记为$\sigma (X)$

🧡在监督学习中，偏差/方差有另外的意义：欠拟合和过拟合

• 偏差大：欠拟合，预测值和样本之间的差大
• 方差大：过拟合，样本值之间的方差大，学出的模型适用性差。方差大意味着样本置信度较差
• 不同机器学习会在欠拟合和过拟合之间做权衡：trade-off

🧡比较

MC	TD
零偏差（bias）	有一些偏差
收敛性较好（即使采用函数逼近）	表格法下TD(0)收敛到 v π ( s ) v_\pi(s) vπ​(s)，函数逼近时不一定
高方差	低方差
对初始值不敏感	对初始值更敏感（用到了贝尔曼方程）
简单、容易理解和使用	通常比MC更高效
随着样本数量的增加，方差逐渐减小，趋近于0	随着样本数量的增加，偏差逐渐减少，趋近于0

3)实际意义方面

TD能比MC更快速灵活的更新状态的价值估计，这在某些情况下有着非常重要的实际意义。我们给驾车返家制定一个目标，要求安全平稳的返回家中。假如有一次你在驾车回家的路上突然碰到险情：对面开过来一辆车感觉要和你迎面相撞，严重的话甚至会威胁生命，不过由于最后双方驾驶员都采取了紧急措施没有让险情实际发生，最后平安到家。如果是使用蒙特卡罗学习，路上发生的这一险情可能引发的极大负值奖励将不会被考虑，你不会更新在碰到此类险情时的状态的价值；但是在TD学习时，碰到这样的险情过后，你会立即大幅调低这个状态的价值，并在今后再次碰到类似情况时采取其它行为，例如降低速度等来让自身处在一个价值较高的状态中，尽可能避免发生意外事件的发生。

4)Markov性质方面

TD算法使用了MDP问题的Markov属性，在Markov 环境下更有效
MC算法并不利用Markov属性，通常在非Markov环境下更有效
[[Lec4_无模型预测#2)确定性等价估计 Certainty Equivalence estimate]]

（5）示例

1)驾车返家

David Silver 增强学习补充——驾车返家 Driving Home Example - 知乎 (zhihu.com)

2)随机行走

🧡已知条件

• 状态空间：如上图A、B、C、D、E为中间状态，C同时作为起始状态。灰色方格表示终止状态；
• 行为空间：除终止状态外，任一状态可以选择向左、向右两个行为之一；
• 即时奖励：右侧的终止状态得到即时奖励为1，左侧终止状态得到的即时奖励为0，在其他状态间转化得到的即时奖励是0；
• 状态转移：100%按行为进行状态转移，进入终止状态即终止；
• 衰减系数：1；
• 给定的策略：随机选择向左、向右两个行为。

🧡问题：
对这个MDP问题进行预测，也就是评估随机行走这个策略的价值，也就是计算该策略下每个状态的价值，也就是确定该MDP问题的状态价值函数。

🧡求解：
下图是使用TD算法得到的结果。横坐标显示的是状态，纵坐标是各状态的价值估计，一共5条折线，数字表明的是实际经历的episode数量，true value所指的那根折线反映的是各状态的实际价值。第0次时，各状态的价值被初始化为0.5，经过1次、10次、100次后得到的值函数越来越接近实际状态值函数。

🧡比较MC和TD算法的效率
横坐标是经历的episode数量，纵坐标是计算得到的状态函数和实际状态函数下各状态价值的均方差。黑色是MC算法在不同step-size下的学习曲线，灰色的曲线使用TD算法。可以看出TD较MC更高效。此图还可以看出当==step-size（参数$\alpha$）不是非常小的情况下，TD有可能得不到最终的实际价值，将会在某一区间震荡==。

3)AB

现有两个状态(A和B)，MDP未知，衰减系数为1，不涉及策略和行为，只涉及状态转换和即时奖励，衰减系数为1。现有如下表所示8个完整Episode的经验及对应的即时奖励，其中除了第1个Episode有状态转移外，其余7个均只有一个状态

a)MC算法

🧡公式 V ( S t ) ← V ( S t ) + 1 N ( S t ) ( G t − V ( S t ) ) V(S_t) \leftarrow V(S_t)+\frac{1}{N(S_t)}(G_t-V(S_t)) V(St​)←V(St​)+N(St​)1​(Gt​−V(St​)) G t = R t + 1 + γ R t + 2 + … + γ T − 1 R T G_t=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1}R_T Gt​=Rt+1​+γRt+2​+…+γT−1RT​
🧡A的价值
只有第一个序列中包含状态A，因此A价值仅能通过第一个序列来计算。
因此 V ( A ) = V ( A ) + 1 1 ( G 1 − V ( A ) ) = G 1 = 0 V(A)=V(A)+\frac{1}{1}(G_1-V(A))=G_1=0 V(A)=V(A)+11​(G1​−V(A))=G1​=0

🧡B的价值
第一次： V ( B ) = V ( B ) + 1 1 ( G 1 − V ( B ) ) = G 1 = 0 V(B)=V(B)+\frac{1}{1}(G_1-V(B))=G_1=0 V(B)=V(B)+11​(G1​−V(B))=G1​=0
第二次： V ( B ) = V ( B ) + 1 2 ( G 2 − V ( B ) ) = 1 2 G 2 − 1 2 V ( B ) = 1 2 V(B)=V(B)+\frac{1}{2}(G_2-V(B))=\frac{1}{2}G_2-\frac{1}{2}V(B)=\frac{1}{2} V(B)=V(B)+21​(G2​−V(B))=21​G2​−21​V(B)=21​
第三次： V ( B ) = V ( B ) + 1 3 ( G 3 − V ( B ) ) = 1 3 G 3 + 2 3 V ( B ) = 2 3 V(B)=V(B)+\frac{1}{3}(G_3-V(B))=\frac{1}{3}G_3+\frac{2}{3}V(B)=\frac{2}{3} V(B)=V(B)+31​(G3​−V(B))=31​G3​+32​V(B)=32​
第四次： V ( B ) = V ( B ) + 1 4 ( G 4 − V ( B ) ) = 1 4 G 4 + 3 4 V ( B ) = 3 4 V(B)=V(B)+\frac{1}{4}(G_4-V(B))=\frac{1}{4}G_4+\frac{3}{4}V(B)=\frac{3}{4} V(B)=V(B)+41​(G4​−V(B))=41​G4​+43​V(B)=43​
第五次： V ( B ) = V ( B ) + 1 5 ( G 5 − V ( B ) ) = 1 5 G 5 + 4 5 V ( B ) = 4 5 V(B)=V(B)+\frac{1}{5}(G_5-V(B))=\frac{1}{5}G_5+\frac{4}{5}V(B)=\frac{4}{5} V(B)=V(B)+51​(G5​−V(B))=51​G5​+54​V(B)=54​
第六次： V ( B ) = V ( B ) + 1 6 ( G 6 − V ( B ) ) = 1 6 G 6 + 5 6 V ( B ) = 5 6 V(B)=V(B)+\frac{1}{6}(G_6-V(B))=\frac{1}{6}G_6+\frac{5}{6}V(B)=\frac{5}{6} V(B)=V(B)+61​(G6​−V(B))=61​G6​+65​V(B)=65​
第七次： V ( B ) = V ( B ) + 1 7 ( G 7 − V ( B ) ) = 1 7 G 7 + 6 7 V ( B ) = 6 7 V(B)=V(B)+\frac{1}{7}(G_7-V(B))=\frac{1}{7}G_7+\frac{6}{7}V(B)=\frac{6}{7} V(B)=V(B)+71​(G7​−V(B))=71​G7​+76​V(B)=76​
第八次： V ( B ) = V ( B ) + 1 8 ( G 8 − V ( B ) ) = 1 8 G 8 + 7 8 V ( B ) = 7 8 V(B)=V(B)+\frac{1}{8}(G_8-V(B))=\frac{1}{8}G_8+\frac{7}{8}V(B)=\frac{7}{8} V(B)=V(B)+81​(G8​−V(B))=81​G8​+87​V(B)=87​

🧡总结
在使用MC算法时，A和B的价值分别为0和 7 8 \frac{7}{8} 87​

b)TD算法

🧡分析
TD算法试图利用现有的episode经验构建一个MDP（如下图），由于只存在一个episode使得状态A有后继状态B，因此状态A的价值是通过状态B的价值来计算的，同时经验表明A到B的转移概率是100%，且A状态的即时奖励是0，并且没有衰减，因此A的状态价值等于B的状态价值。

🧡计算
看成一个MDP，求状态价值函数： V ( A ) = π ( a ∣ A ) [ R A a + γ P A B a V ( B ) ] = 1 × ( 0 + 1 × 1 × V ( B ) ) = V ( B ) V(A)=\pi(a\vert A)[R_A^a+\gamma P_{AB}^aV(B)]=1\times(0+1\times1\times V(B))=V(B) V(A)=π(a∣A)[RAa​+γPABa​V(B)]=1×(0+1×1×V(B))=V(B) V ( B ) = π ( b 1 ∣ B ) [ R B b 1 + γ P B B ′ b 1 V ( B ′ ) ] + π ( b 2 ∣ B ) [ R B b 2 + γ P B B ′ b 2 V ( B ′ ) ] = 0.75 × ( 1 + 1 × 1 × 0 ) + 0.25 × ( 0 + 1 × 1 × 0 ) = 0.75 V(B)=\pi(b1\vert B)[R_B^{b1}+\gamma P_{BB^\prime}^{b1}V(B^\prime)]+ \pi(b2\vert B)[R_B^{b2}+\gamma P_{BB^\prime}^{b2}V(B^\prime)]=0.75\times(1+1\times1\times 0)+0.25\times(0+1\times1\times 0)=0.75 V(B)=π(b1∣B)[RBb1​+γPBB′b1​V(B′)]+π(b2∣B)[RBb2​+γPBB′b2​V(B′)]=0.75×(1+1×1×0)+0.25×(0+1×1×0)=0.75
注意：这里由动作b1和b2到达的 B ′ B^\prime B′为终止状态，因此 V ( B ′ ) = 0 V(B^\prime)=0 V(B′)=0

🧡总结
在使用TD算法时，A和B的价值均为 6 8 \frac{6}{8} 86​

（6）Batch MC and TD

1)问题引入

🧡求解的值函数

• 经验趋于无穷，即无数次试验后，MC和 TD(0) 所估计得到的值函数都将收敛到策略对应的真实值函数（理想情况）

🧡问题

• 实际中我们不可能达到无穷经验，那如果我们利用有限的经验来对值函数进行估计将得到什么样的结果？

🧡以示例3为由说明
对于 K 个Episode：

重复对这K个Episode采样，对于某一次采样得到的样本k应用于MC和TD(0) ，得到什么结论？

根据示例3，应用MC算法，由于需要完整的Episode,因此仅Episode1可以用来计算A的状态价值，很明显是0；同时B的价值是6/8。应用TD算法时，TD算法试图利用现有的Episode经验构建一个MDP（如下图），由于存在一个Episode使得状态A有后继状态B，因此状态A的价值是通过状态B的价值来计算的，同时经验表明A到B的转移概率是100%，且A状态的即时奖励是0，并且没有衰减，因此A的状态价值等于B的状态价值

2)确定性等价估计 Certainty Equivalence estimate

a)MC算法

MC算法试图收敛至一个能够最小化状态价值与实际收获的均方差的解决方案，该均方差为： ∑ k = 1 K ∑ t = 1 T k ( G t k − V ( S t k ) ) 2 \sum_{k=1}^K\sum_{t=1}^{T_k}(G_t^k-V(S_t^k))^2 k=1∑K​t=1∑Tk​​(Gtk​−V(Stk​))2
式中， $k$ 表示的是Episode序号， $K$ 为总的Episode数量，$t$ 为一个Episode内状态序号（第1,2,3…个状态等）， T k T_k Tk​ 表示的是第 $k$ 个Episode总的状态数， G t k G_t^k Gtk​表示第 $k$ 个Episode里$t$ 时刻状态 S t S_t St​ 获得的最终收获， V ( S t k ) V(S_t^k) V(Stk​) 表示的是第 $k$ 个episode里算法估计的 $t$ 时刻状态 S t S_t St​ 的价值。

b)TD算法

TD算法收敛到一个根据已有经验构建的最大可能的Markov模型的状态价值。

• TD算法将首先根据已有经验估计状态间的转移概率： P ^ s , s ′ a = 1 N ( s , a ) ∑ k = 1 K ∑ t = 1 T k 1 ( s t k , a t k , s t + 1 k = s , a , s ′ ) \hat{\mathcal{P}}_{s,s^\prime}^a=\frac{1}{N(s,a)}\sum_{k=1}^K\sum_{t=1}^{T_k}\textbf{1}(s_t^k,a_t^k,s_{t+1}^k=s,a,s^\prime) P^s,s′a​=N(s,a)1​k=1∑K​t=1∑Tk​​1(stk​,atk​,st+1k​=s,a,s′)
• 并同时估计某一个状态的即时奖励： R ^ s a = 1 N ( s , a ) ∑ k = 1 K ∑ t = 1 T k 1 ( s t k , a t k = s , a ) \hat{\mathcal{R}}_s^a=\frac{1}{N(s,a)}\sum_{k=1}^K\sum_{t=1}^{T_k}\textbf{1}(s_t^k,a_t^k=s,a) R^sa​=N(s,a)1​k=1∑K​t=1∑Tk​​1(stk​,atk​=s,a)
• 最后计算该MDP的状态函数

💗注意💗：
$\text{1}(\dots )$是一个条件判断式，满足括号里的条件则该值为1，否则为0

（7）小结

MC学习算法、TD学习算法和DP算法都可以用来计算状态价值。

1)本质区别

• MC和TD是不依赖模型
  • MC学习需要完整的状态序列来更新状态价值
  • TD学习则不需要完整的状态序列
• DP算法则是基于模型的计算状态价值的方法
  • 它通过计算一个状态 S 所有可能的转移状态 S′ 及其转移概率以及对应的即时奖励来计算这个状态 S 的价值。

2)是否Bootstrap

• MC学习并不使用引导数据，它使用实际产生的奖励值来计算状态价值
• TD和DP则都是用后续状态的预估价值作为引导数据来计算当前状态的价值

3)是否采样

• MC和TD不依赖模型，使用的都是个体与环境实际交互产生的采样状态序列来计算状态价值的
• DP则依赖状态转移概率矩阵和奖励函数，全宽度计算状态价值，没有采样之说

4)应用

🧡使用单个采样，同时不经历完整的状态序列更新价值的算法➡TD学习
🧡使用单个采样，但依赖完整状态序列的算法➡MC学习
🧡考虑全宽度采样，但对每一个采样经历只考虑后续一个状态时的算法➡DP学习
🧡既考虑所有状态转移的可能性，同时又依赖完整状态序列的算法➡穷举法（exhausive search）

💗注意💗：

• DP利用的是整个MDP问题的模型，也就是状态转移概率，虽然它并不实际利用样本，但是它利用了整个模型的规律，因此认为是Full Width的
• 图中是从两个维度解释四种算法的区别：采样深度和广度。
  

4.TD($\lambda$)，$\lambda \in [0,1]$

（1）介绍

• 先前所介绍的TD算法实际上都是TD(0)算法
  • TD(0)表示采样1步，在当前状态下往前多看1步，利用 R t + 1 R_{t+1} Rt+1​和 V ( S t + 1 ) V(S_{t+1}) V(St+1​)来估计 V ( S t ) V(S_{t}) V(St​)
• MC算法则是相当于把当前时刻 t 到无穷的所有的奖励都加起来了
• 如果介于两者之间的target，比如在当前状态下往前多看2步更新状态价值会怎样？
• 这就引入了n-step的概念。

（2）n-step预测

🧡n-step预测指从状态序列的当前状态 S t S_t St​开始往序列终止状态方向观察至状态 S t + n − 1 S_{t+n-1} St+n−1​，使用这 n 个状态产生的即时奖励 ( R t + 1 , R t + 2 , . . . , R t + n R_{t+1},R_{t+2},...,R_{t+n} Rt+1​,Rt+2​,...,Rt+n​) 以及状态 S t + n S_{t+n} St+n​的预估价值来计算当前状态 S t S_t St​ 的价值。
🧡这里，TD target 也由2部分组成，已走的步数使用确定的即时reward，剩下的使用估计的状态价值替代。

图中，空心大圆圈表示状态，实心小圆圈表示行为

（3）n-Step Return

1)分析

对于n-Step的回报，$n=1,2,\dots ,\infty$

• n = 1 , G t ( 1 ) = R t + 1 + γ V ( S t + 1 ) → T D o r T D ( 0 ) n=1,\ G_t^{(1)}=R_{t+1}+\gamma V(S_{t+1})\ \rightarrow \ TD\ or\ TD(0) n=1, Gt(1)​=Rt+1​+γV(St+1​) → TD or TD(0)
• n = 2 , G t ( 2 ) = R t + 1 + γ R t + 2 + γ 2 V ( S t + 2 ) n=2,\ G_t^{(2)}=R_{t+1}+\gamma R_{t+2}+\gamma^2 V(S_{t+2}) n=2, Gt(2)​=Rt+1​+γRt+2​+γ2V(St+2​)
• n = ∞ , G t ( ∞ ) = R t + 1 + γ R t + 2 + … + γ n R T → M C n=\infty,\ G_t^{(\infty)}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^n R_T\ \rightarrow \ MC n=∞, Gt(∞)​=Rt+1​+γRt+2​+…+γnRT​ → MC

💗注意💗：$n=2$时不写成TD(2)

2)定义

• n-Step Return： 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}+\ldots+\gamma^{n-1}R_{t+n}+\gamma^n V(S_{t+n}) Gt(n)​=Rt+1​+γRt+2​+…+γn−1Rt+n​+γnV(St+n​)
• n-Step TD学习的状态价值函数： V ( S t ) ← V ( S t ) + α ( G t ( n ) − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha(G_t^{(n)}-V(S_t)) V(St​)←V(St​)+α(Gt(n)​−V(St​))
  

💡问题：
n取值多少时效果最好？

3)举例——大规模随机行走

💌研究了使用多个不同步数预测联合不同步长(step-size，公式里的系数α）时，分别在在线和离线状态时状态函数均方差的差别。

• 所有研究使用了10个Episode：
  • 离线是在经历所有10个Episode后进行状态价值更新
  • 在线则至多经历一个Episode就更新依次状态价值
    

图中结果表明：

• 离线和在线之间曲线的形态差别不明显
• 从步数上来看，步数越长，越接近MC算法，均方差越大

🧡对于这个大规模随机行走示例，在线计算比较好的步数是3-5步，离线计算比较好的是6-8步。但是不同的问题其对应的比较高效的步数不是一成不变的。因此选择多少步数作为一个较优的计算参数也是一个问题。

（4）n-Step 回报值平均

🧡不同的n下的 n 步回报值效果不同，我们可以在不同的n上求n步回报的平均值，也可以构成一个有效的回报值。

• 比如，平均2-step回报和4-step回报： 1 2 G ( 2 ) + 1 2 G ( 4 ) \frac{1}{2}G^{(2)}+\frac{1}{2}G^{(4)} 21​G(2)+21​G(4)，这个回报值混合了两种信息

🧡能不能有效地混合所有的n步回报值?

• 引入一个新的参数$\lambda$，可以做到在不增加计算复杂度的情况下综合考虑所有步数的预测——$\lambda$ predict和$\lambda$ return

1)$\lambda$ return

🧡 $\lambda$ return G t λ G_t^\lambda Gtλ​ 综合考虑了从 1 到 ∞ 的所有步收获，它给其中的任意一个n-步收获施加一定的权重 ( 1 − λ ) λ n − 1 (1-\lambda)\lambda^{n-1} (1−λ)λn−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)​
其中， 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}+\ldots+\gamma^{n-1}R_{t+n}+\gamma^n V(S_{t+n}) Gt(n)​=Rt+1​+γRt+2​+…+γn−1Rt+n​+γnV(St+n​)

2)$\lambda$ predict

🧡对应的$\lambda$ predict V ( S t ) V(S_t) V(St​)写成： V ( S t ) ← V ( S t ) + α ( G t ( λ ) − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha(G_t^{(\lambda)}-V(S_t)) V(St​)←V(St​)+α(Gt(λ)​−V(St​))
🧡对比n-step TD： V ( S t ) ← V ( S t ) + α ( G t ( n ) − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha(G_t^{(n)}-V(S_t)) V(St​)←V(St​)+α(Gt(n)​−V(St​))
🧡对比TD(0)： V ( S t ) ← V ( S t ) + α ( R t + 1 + γ V ( S t + 1 ) − V ( S t ) ) V(S_t) \leftarrow V(S_t)+ \alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t)) V(St​)←V(St​)+α(Rt+1​+γV(St+1​)−V(St​))
💗注意💗：

• $\lambda =0$时退化成TD(0)
• $\lambda =1$时退化成MC
• 最后一列，$T$为终止状态的时刻步数，$t$为当前状态的时刻步数
• 所有的权重加起来为1
  

3)$TD(\lambda )$ 对于权重分配的图解

🧡例如：

• 对于 n=3 的 3-Step 收获，赋予其在 $\lambda$ 收获中的权重如左侧阴影部分面积
• 对于终止状态的T-步收获，T以后的所有阴影部分面积
• 所有节段面积之和为1
• 这种几何级数的设计也考虑了算法实现的计算方便性

🧡意义：

• $TD(\lambda )$的设计使得episode中，后一个状态的状态价值与之前所有状态的状态价值有关
• 即一个状态价值参与决定了后续所有状态的状态价值
• 但是每个状态的价值对于后续状态价值的影响权重是不同的

（5）前向认识$TD(\lambda )$

🧡问题：
引入了$\lambda$之后，会发现要更新一个状态的状态价值，必须要走完整个Episode获得每一个状态的即时奖励以及最终状态获得的即时奖励。这和MC算法的要求一样，因此$TD(\lambda )$算法有着和MC方法一样的劣势。

🧡比较

• $TD(\lambda )$更新： V ( S t ) ← V ( S t ) + α ( G t ( λ ) − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha(G_t^{(\lambda)}-V(S_t)) V(St​)←V(St​)+α(Gt(λ)​−V(St​)) 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)​ 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}+\ldots+\gamma^{n-1}R_{t+n}+\gamma^n V(S_{t+n}) Gt(n)​=Rt+1​+γRt+2​+…+γn−1Rt+n​+γnV(St+n​)
• MC更新： V ( S t ) ← V ( S t ) + α ( G t − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha(G_t-V(S_t)) V(St​)←V(St​)+α(Gt​−V(St​))

🧡前向$TD(\lambda )$求解大规模随机行走问题：

（6）后向认识$TD(\lambda )$

1)示例

🧡问题：
老鼠在连续接受了3次响铃和1次亮灯信号后遭到了电击，那么在分析遭电击的原因时，到底是响铃的因素较重要还是亮灯的因素更重要呢？

2)频率启发与就近启发

🧡定义：
频率启发 Frequency heuristic：将原因归因于出现频率最高的状态
就近启发 Recency heuristic：将原因归因于较近的几次状态
🧡效用追踪
给每一个状态引入一个数值：效用追踪（Eligibility Traces, ES，也有翻译成“资质追踪”，这是同一个概念从两个不同的角度理解得到的不同翻译），可以结合上述两个启发。

• 定义： E 0 ( s ) = 0 E_0(s)=0 E0​(s)=0 E t ( s ) = γ λ E t − 1 ( s ) + 1 ( S t = s ) E_t(s)=\gamma\lambda E_{t-1}(s)+\textbf{1}(S_t=s) Et​(s)=γλEt−1​(s)+1(St​=s)
• E t ( s ) E_t(s) Et​(s)的可能曲线：
  • 该图横坐标是时间，横坐标下有竖线的位置代表当前进入了状态 s ，纵坐标是效用追踪值 E
  • 可以看出当某一状态连续出现，E值会在一定衰减的基础上有一个单位数值的提高，此时将增加该状态对于最终收获贡献的比重，因而在更新该状态价值的时候可以较多地考虑最终收获的影响
  • 同时如果该状态距离最终状态较远，则其对最终收获的贡献越小，在更新该状态时也不需要太多的考虑最终收获
• 解释：
  • 效用追踪其实是一个信度分配问题（Credit Assignment）
  • 比如，下围棋输了，是中间下的哪一步的责任？或者说，每一步对于输掉比赛这个结果分别承担多少责任，这是一个信度分配问题
  • 小鼠电击，按照频率启发，是灯泡的问题，按照就近启发，是电击的问题
  • 更合理的想法是，二者都有影响，因此需要为这两件事分配权重，如果某个事件s发生，s对应的效用追踪值+1，如果某一段时间事件s未发生，则按照某个衰减因子进行衰减，即 E t ( s ) E_t(s) Et​(s)的定义
• E t ( s ) E_t(s) Et​(s)的相关说明
  • E t ( s ) E_t(s) Et​(s)不需要等到完整的Episode结束再计算，每经过一个时刻就更新
  • E t ( s ) E_t(s) Et​(s)值有饱和现象，瞬时最高上限是 E m a x = 1 1 − γ λ E_{max}=\frac{1}{1-\gamma \lambda} Emax​=1−γλ1​
  • 可以把 E t ( s ) E_t(s) Et​(s)想象成神经元参数，反映了神经元对某一刺激的敏感性和适应性：神经元接受刺激时有反馈，持续刺激时反馈强，一段时间不刺激神经元静息，但无论怎样增加刺激频率，神经元都有一个最大的饱和反馈

3)后向认识$TD(\lambda )$

🧡根据效用追踪更新状态价值

• 每个状态$s$都保存一个效用追踪，即每一个状态都有一个E值，E值随时间发生变化
• 可以将效用追踪理解为一个权重，状态$s$被访问的时间离现在越久，被访问的次数越少，对于值函数的影响越小 δ 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​) V ( s ) ← V ( s ) + α δ t E t ( s ) V(s)\leftarrow V(s)+\alpha \delta_t E_t(s) V(s)←V(s)+αδt​Et​(s) E t ( s ) = γ λ E t − 1 ( s ) + 1 ( S t = s ) E_t(s)=\gamma\lambda E_{t-1}(s)+\textbf{1}(S_t=s) Et​(s)=γλEt−1​(s)+1(St​=s)

🧡解释
有个人坐在状态流上，手里拿着话筒，面朝着已经经历过的状态获得当前回报并利用下一个状态的值函数得到TD偏差之后，此人会向已经经历过的状态喊话告诉这些已经经历过的状态处的值函数需要利用当前时刻的TD偏差进行更新。此时过往的每个状态值函数更新的大小应该跟距离当前状态的步数有关

4)前向和后向$TD(\lambda )$的关系

通过一系列的说明前向视角和后向视角的$TD(\lambda )$ 等价

a)前向和后向$TD(\lambda )$

🧡 前向视角 V ( S t ) ← V ( S t ) + α ( G t ( λ ) − V ( S t ) ) V(S_t)\leftarrow V(S_t)+\alpha(G_t^{(\lambda)}-V(S_t)) V(St​)←V(St​)+α(Gt(λ)​−V(St​)) 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)​
🧡后向视角→使用效用追踪 V ( s ) ← V ( s ) + α δ t E t ( s ) V(s)\leftarrow V(s)+\alpha \delta_t E_t(s) V(s)←V(s)+αδt​Et​(s)
其中， δ 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​) E t ( s ) = γ λ E t − 1 ( s ) + 1 ( S t = s ) E_t(s)=\gamma\lambda E_{t-1}(s)+\textbf{1}(S_t=s) Et​(s)=γλEt−1​(s)+1(St​=s)

b)$TD(0)$（后向视角）——$TD(\lambda )$和$TD(0)$

• $\lambda =0$时，只有当前状态得到更新
  • $\gamma \lambda =0$，在效用追踪公式 E t ( s ) = γ λ E t − 1 ( s ) + 1 ( S t = s ) E_t(s)=\gamma\lambda E_{t-1}(s)+\textbf{1}(S_t=s) Et​(s)=γλEt−1​(s)+1(St​=s)里，相当于每时每刻过去的贡献都被衰减完毕，效用追踪只记录脉冲信号 E t ( s ) = 1 ( S t = s ) E_t(s)=\textbf{1}(S_t=s) Et​(s)=1(St​=s)
  • 此时 V ( s ) ← V ( s ) + α δ t E t ( s ) V(s)\leftarrow V(s)+\alpha \delta_tE_t(s) V(s)←V(s)+αδt​Et​(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​
• 可以看到带有效用追踪的后向$TD(\lambda )$等同于$TD(0)$算法

c)对状态的总的更新量——$TD(\lambda )$和MC

🧡对状态$s$的总更新量：

• $TD(\lambda )$前向视角： ∑ t = 1 T α δ t E t ( s ) = ∑ t = 1 T α ( G t λ − V ( S t ) ) 1 ( S t = s ) \sum_{t=1}^T\alpha \delta_tE_t(s)=\sum_{t=1}^T\alpha (G_t^\lambda -V(S_t))\textbf{1}(S_t=s) ∑t=1T​αδt​Et​(s)=∑t=1T​α(Gtλ​−V(St​))1(St​=s)
• $TD(\lambda )$后向视角： ∑ t = 1 T α δ t E t ( s ) \sum_{t=1}^T\alpha \delta_tE_t(s) ∑t=1T​αδt​Et​(s)

💗注意💗：离线更新的前向和后向视角相同： ∑ t = 1 T α δ t E t ( s ) = ∑ t = 1 T α ( G t λ − V ( S t ) ) 1 ( S t = s ) \sum_{t=1}^T\alpha \delta_tE_t(s)=\sum_{t=1}^T\alpha (G_t^\lambda -V(S_t))\textbf{1}(S_t=s) ∑t=1T​αδt​Et​(s)=∑t=1T​α(Gtλ​−V(St​))1(St​=s)

d)前向和后向的累积误差

🧡假设条件：

• 在某个Episode中，状态$s$在$k$时刻被访问了一次，则$\lambda =1$时

🧡后向视角下的误差

• 根据公式 E t ( s ) = γ λ E t − 1 ( s ) + 1 ( S t = s ) E_t(s)=\gamma\lambda E_{t-1}(s)+\textbf{1}(S_t=s) Et​(s)=γλEt−1​(s)+1(St​=s)，效用追踪化简为：

• 在线更新过程中，不断累积误差 ∑ t = 1 T α δ t E t ( s ) \sum_{t=1}^T\alpha \delta_tE_t(s) ∑t=1T​αδt​Et​(s)可以化简为： ∑ t = 1 T α δ t E t ( s ) = α ( G k − V ( S k ) ) \sum_{t=1}^T\alpha \delta_tE_t(s)=\alpha (G_k-V(S_k)) t=1∑T​αδt​Et​(s)=α(Gk​−V(Sk​))

  • （证明如[[Lec4_无模型预测#（1）后向的TD(1)累积的误差]]）
  • 这里 G k G_k Gk​相当于蒙特卡洛的回报值， V ( S k ) V(S_k) V(Sk​)为当前状态值函数， G k − V ( S k ) G_k-V(S_k) Gk​−V(Sk​)相当于MC的更新量

• 因此，可以看出$\lambda =1$时，TD误差之和会缩小为MC误差，TD(1)粗略看与每次访问的MC算法等同

  • $TD(1)$为在线误差累计，每步更新
  • 如果 $TD(1)$ 也等到片段结束后离线更新，那么 TD(1) 就是 MC

🧡前向视角下的误差

• 已知公式 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)​ 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}+\ldots+\gamma^{n-1}R_{t+n}+\gamma^n V(S_{t+n}) Gt(n)​=Rt+1​+γRt+2​+…+γn−1Rt+n​+γnV(St+n​)
• 化简误差可得： G t λ − V ( S t ) = δ t + γ λ δ t + 1 + ( γ λ ) 2 δ t + 2 + … G_t^\lambda -V(S_t)=\delta_t+\gamma\lambda \delta_{t+1}+(\gamma\lambda)^2 \delta_{t+2}+\ldots Gtλ​−V(St​)=δt​+γλδt+1​+(γλ)2δt+2​+…
  • 证明如[[Lec4_无模型预测#（2）前向的$TD(lambda)$累积的误差]]

🧡证明前向和后向视角下的误差相等
这里不取特例$\lambda =1$，因此效用追踪

从后向视角的$TD(\lambda )$累积误差入手

5)两种视角下等价性

🧡离线更新

• 在整个片段里累计更新误差
• 在片段结束后统一更新
• 离线更新下，前向视角和后向视角等价
  🧡在线更新
• 在片段的每一步更新
• 此时前向视角和后向视角有一点不同
• 可以通过对资格迹进行一些修正，使两者完全等价
  

5.证明

（1）后向的$TD(1)$累积的误差

💗注意💗：

• 化简的最后一步，因为 S T S_T ST​是最后一个状态，因此 V ( S T ) V(S_{T}) V(ST​)一般为0，从而 γ T − k V ( S T ) \gamma^{T-k} V(S_{T}) γT−kV(ST​)一项为0，直接省去

（2）前向的$TD(\lambda )$累积的误差

已知公式 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)​ 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}+\ldots+\gamma^{n-1}R_{t+n}+\gamma^n V(S_{t+n}) Gt(n)​=Rt+1​+γRt+2​+…+γn−1Rt+n​+γnV(St+n​)
因此，累计误差：
G t λ − V ( S t ) = − V ( S t ) + ( 1 − λ ) λ 0 ( G t ( 1 ) ) + ( 1 − λ ) λ 1 ( G t ( 2 ) ) + ( 1 − λ ) λ 2 ( G t ( 3 ) ) + ( 1 − λ ) λ 3 ( G t ( 4 ) ) + … G_t^\lambda -V(S_t) = -V(S_t)+(1-\lambda)\lambda^{0}(G_t^{(1)})+(1-\lambda)\lambda^{1}(G_t^{(2)})+(1-\lambda)\lambda^{2}(G_t^{(3)})+(1-\lambda)\lambda^{3}(G_t^{(4)})+\ldots Gtλ​−V(St​)=−V(St​)+(1−λ)λ0(Gt(1)​)+(1−λ)λ1(Gt(2)​)+(1−λ)λ2(Gt(3)​)+(1−λ)λ3(Gt(4)​)+…

• 这里
  

• 因此可以化简
  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！