Model-free prediction
Estimate the value function of an unknown MDP

简介

上一节讲到的动态规划算法(【强化学习】04 ——动态规划算法
)要求马尔可夫决策过程是已知的，即要求与智能体交互的环境是完全已知的（例如迷宫或者给定规则的网格世界）。在此条件下，智能体其实并不需要和环境真正交互来采样数据，直接用动态规划算法就可以解出最优价值或策略。

这类已经给定一个MDP模型（即，状态转移${\mathcal{P}}_{s{s}^{\prime }}^a$和奖励函数${\mathcal{R}}_s$明确给定） 的算法可以称为基于模型的强化学习。基于模型来计算最优价值函数和学习最优的策略。

但这在大部分场景下并不现实，机器学习的主要方法都是在数据分布未知的情况下针对具体的数据点来对模型做出更新的。对于大部分强化学习现实场景（例如电子游戏或者一些复杂物理环境），其马尔可夫决策过程的状态转移概率是无法写出来的，也就无法直接进行动态规划。在这种情况下，智能体只能和环境进行交互，通过采样到的数据来学习，这类学习方法统称为无模型的强化学习（model-free reinforcement learning）。

蒙特卡洛算法

蒙特卡洛算法（Monte-Carlo method）和时序差分算法（temporal difference，TD）就是典型的无模型的强化学习。在【强化学习】03 ——马尔可夫决策过程中已经对MC有过介绍。这里再做几点补充与总结。

$$\begin{array}{rlr}& \text{思路:}& V(S_t)\simeq \frac{1}{N}\sum _{i=1}^N{G}_t^{(i)}\\ & \text{增量式实现:}& V(S_t)\leftarrow V(S_t)+\alpha (G_t-V(S_t))\end{array}$$

• 蒙特卡洛方法：直接从经验片段进行学习

• 蒙特卡洛是模型无关的：未知马尔可夫决策过程的状态转移/奖励

• 蒙特卡洛从完整的片段中进行学习：没有使用bootstrapping的方法

• 蒙特卡洛采用最简单的思想：值（value）= 平均累计奖励（mean return）

• 注意：只能将蒙特卡洛方法应用于有限长度的马尔可夫决策过程中

  • 即，所有的片段都有终止状态

• 蒙特卡洛策略评估使用经验均值累计奖励而不是期望累计奖励

  • 值函数（value function）是期望累计奖励

• first-visit MC

  • 对于一个episode，只计算一次状态$s$的回报，之后再出现状态$s$，则不去计算。
  • 参考伪代码

• every-visit MC

  • 在状态$s$每一次出现时计算它的回报

时序差分方法

时序差分是一种用来估计一个策略的价值函数的方法，它结合了蒙特卡洛和动态规划算法的思想。时序差分方法和蒙特卡洛的相似之处在于可以从样本数据中学习，不需要事先知道环境；和动态规划的相似之处在于根据贝尔曼方程的思想，利用后续状态的价值估计来更新当前状态的价值估计。回顾一下蒙特卡洛方法对价值函数的增量更新方式：$$V(s_t)\leftarrow V(s_t)+\alpha [G_t-V(s_t)]$$
其中$\alpha$为对价值估计更新的步长，可以是个常量，因此也可以将上述方式称为constant-$\alpha$ MC。蒙特卡洛方法必须要等整个序列结束之后才能计算得到这一次的回报$G_t$，而时序差分方法只需要当前步结束即可进行计算。具体来说，时序差分算法用当前获得的奖励$R_{t+1}$加上下一个状态的价值估计$V(S_{t+1})$来作为在当前状态会获得的回报，即：$$\begin{array}{r}V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]\end{array}$$上述这种TD方法称为$TD(0)$，或者说是一步TD算法，之后还会介绍$TD（\lambda ）$算法，或者称为n-step 的TD算法。$R_{t+1}+\gamma V(S_{t+1})$被称为时序差分目标（TD Target）$R_{t+1}+\gamma V(S_{t+1})-V(S_t)$被称为时序差分误差（ TD error）,时序差分算法将时序差分误差与步长的乘积作为状态价值的更新量。。下面是TD(0)的算法伪代码：
可以用$R_{t+1}+\gamma V(S_{t+1})$代替$G_t$的原因是：$$\begin{array}{rl}{V}_{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t|S_t=s]\\ & ={\mathbb{E}}_{\pi }[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma \sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+2}|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma V_{\pi }(S_{t+1})|S_t=s]\end{array}$$因此蒙特卡洛方法将上式第一行作为更新的目标，而时序差分算法将上式最后一行作为更新的目标。于是，在用策略和环境交互时，每采样一步，我们就可以用时序差分算法来更新状态价值估计。

Example1

每天下班开车回家时，你都试图预测回家需要多长时间。当你离开办公室时，你会注意时间、一周中的哪一天、天气以及其他任何可能相关的事情。假设这个星期五你正好在6点离开，你估计需要30分钟才能到家。当你到达你的车时，已经是6:05了，你注意到天开始下雨了。雨天交通通常较慢，所以你重新估计从那时起需要35分钟，总共需要40分钟。15分钟后，你顺利地完成了高速公路部分的旅程。当你从一条二级公路上下来时，你把总的旅行时间估计减少到35分钟。不幸的是，在这一点上，你被一辆慢车挡住了，而这条路太窄，无法超车。你最终不得不跟着卡车，直到你在6:40转弯到你住的街道。三分钟后你就到家了。因此，状态、时间和预测的序列如下：

下图是MC和TD算法基于上述问题的对比。可以看到蒙特卡洛是等待片段结束，估计总的时间；而TD则是依据下一步进行估计。

MC和TD的对比

时序差分：能够在知道最后结果之前进行学习
• 时序差分能够在每一步之后进行在线学习
• 蒙特卡洛必须等待片段结束，直到累计奖励已知

时序差分：能够无需最后结果地进行学习
• 时序差分能够从不完整的序列中学习
• 蒙特卡洛只能从完整序列中学习
• 时序差分在连续（无终止的）环境下工作
• 蒙特卡洛只能在片段化的（有终止的）环境下工作

偏差（Bias）/方差（Variance）的权衡

• 累计奖励$\begin{array}{r}{G}_t=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{T-1}{R}_T\end{array}$是$V_{\pi }(S_t)$的无偏估计

• 时序差分真实目标$R_{t+1}+\gamma V_{\pi }(S_{t+1})$是对$V_{\pi }(S_t)$的无偏估计

• 时序差分目标$R_{t+1}+\gamma V(S_{t+1})$是对$V_{\pi }(S_t)$的有偏估计

• 时序差分目标具有比累计奖励更低的方差
  • 累计奖励——取决于多步随机动作，多步状态转移和多步奖励，多步随机可能带来更多的不确定性。
  • 时序差分目标——取决于单步随机动作，单步状态转移和单步奖励

MC：$V(s_t)\leftarrow V(s_t)+\alpha [G_t-V(s_t)]$	TD：$\begin{array}{r}V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]\end{array}$
蒙特卡洛具有高方差，无偏差	时序差分具有低方差，有偏差
• 良好的收敛性质	• 通常比蒙特卡洛更加高效
• 使用函数近似时依然如此	• 时序差分最终收敛到$V_{\pi }(S_t)$
• 对初始值不敏感	• 但使用函数近似并不总是如此
• 易于理解和使用	• 比蒙特卡洛对初始值更加敏

Example2 Random Walk

在这个例子中，我们将TD（0）和constant-αMC应用于以下马尔可夫奖励过程，对它们的预测能力进行了比较：

在这个MRP中，所有的情节都以中心状态C开始，然后每个步骤都向左或向右移动一个状态，概率相等。情节要么在最左边终止，要么在最右边终止。当情节在右侧终止时，发生+1的奖励；所有其他奖励都是零。例如，一个典型的情节可能包括以下状态和奖励序列：C，0，B，0，C，0，D，0，E，1。由于此任务是未打折的，因此每个状态的真实值是从该状态开始终止于右侧的概率。因此，中心状态的真实值为$V_{\pi }(C)$=0.5。状态A到E的真实值是1/6、2/6、3/6、4/6和5/6。

可以看到随着采样次数的增多，或越来越接近真实值。

从图中可以看出，MC比TD的收敛速度要慢上许多，同时MC的均方根误差要比TD大上不少。

Example3 AB

从上面的例子中我们知道，当$Episodes\to \infty$时，MC和TD都可以使得$V(s)$收敛到$V_{\pi }(s)$。接下来，我们将会讨论有限个Episodes的问题：用有限个Episodes反复训练MC和TD。

以下面的双状态AB例子为例，一共8个Episode。依据这些数据，求解出$V(A),V(B)$

很容易知道$V(B)=0.75$,但对于$V(A)$的求解，MC和TD会给出两种不同的答案。

• MC收敛于具有最小均方根误差的解
  • 会对已有的经验求取最小均方根误差
  • $\begin{array}{r}\sum _{k=1}^K\sum _{t=1}^{T_k}{\left(G_t^k-V(s_t^k)\right)}^2\end{array}$
  • 因此，对于MC,$V(A)=0$
• TD(0)收敛于极大似然马尔可夫模型的解
  • 
  • 基于MDP$⟨S,A,\hat{P},\hat{R},\gamma ⟩$去拟合数据
  • $\begin{array}{rl}{\hat{\mathcal{P}}}_{s,s^{\prime }}^a& =\frac{1}{N(s,a)}\sum _{k=1}^k\sum _{t=1}^{T_k}1(s_t^k,a_t^k,s_{t+1}^k=s,a,s^{\prime })\\ {\hat{\mathcal{R}}}_s^a& =\frac{1}{N(s,a)}\sum _{k=1}^k\sum _{t=1}^{T_k}1(s_t^k,a_t^k=s,a)r_t^k\end{array}$
  • 因此，对于TD,$V(A)=0.75$
• TD利用Markov特性
  • 通常在马尔可夫环境中更有效
• MC不利用Markov属性
  • 通常在非马尔可夫环境中更有效

反向传播(backup)

Monte-Carlo Backup

MC的反向传播需要通过不断地采样，最终抵达终点时，结束采样并计算$G_t$

Temporal-Difference Backup

而TD只需进行一步

Dynamic Programming Backup

动态规划同样是一步，但是是对下一步的所有可能的状态作估计。

下图是DP、枚举法、MC以及TD四种算法的比较。

Bootstrapping and Sampling

Bootstrapping:update involves an estimate	Sampling:update samples an expectation
MC does not bootstrap	MC samples
DP bootstraps	DP does not sample
TD bootstraps	TD samples

多步时序查分学习

除了往前探一步，我们还可以往前探$n$步。

定义𝑛步累计奖励：
$$G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+...+{\gamma }^{n-1}{R}_{t+n}+{\gamma }^{n}V(S_{t+n})$$
因此，𝑛步时序差分学习为：
$$V(S_t)\leftarrow V(S_t)+\alpha \left(G_t^{(n)}-V(S_t)\right)$$

伪代码如下：

Example4 Large Random Walk Example

对于多步时序查分，可以从下图中看到，当$n\to \infty$时，平均均方根误差越大，符合MC方差大的特性。同时，不同的$n$所产生的效果也不同，最佳点（平均均方根误差最小的点处，即极小值点处）的选择也不尽相同，对于一个问题，可能$n=4$时比较好，但对于另一个问题，则是$n=2$比较好。因此我们需要考虑一种能够兼顾所有$n$的算法，以增强鲁棒性。

Forward-view TD(λ)

举个例子：

我们可以对$n=2$和$n=4$的累计奖励进行平均：$\frac{1}{2}{G}^{(2)}+\frac{1}{2}{G}^{(4)}$，以此来进行平衡。同样地，我们可以扩展到所有的步长：
这个算法被称为λ-return算法。该算法组合了所有的$G_t^{(n)}$，并且赋上了相应的权值$(1-\lambda ){\lambda }^{n-1}$,累计奖励为：$$G_t^{\lambda }=(1-\lambda )\sum _{n=1}^{\infty }{\lambda }^{n-1}{G}_t^{(n)}$$
因此，TD(λ)为$$V(S_t)\leftarrow V(S_t)+\alpha \left(G_t^{\lambda }-V(S_t)\right)$$

以上讲述的算法为Forward-view TD(λ)：

• 基于λ-return更新价值函数
• Forward-view looks into the future to compute $G_t^{\lambda }$
• 不过对于这种算法(Forward-view TD(λ))，也是和MC一样需要从完整的片段中进行学习。

Backward View TD(λ)

此部分不完整

Backward View TD(λ)是另一种算法，无需从完整的片段中进行学习。

• Forward view provides theory
• Backward view provides mechanism
• Update online, every step, from incomplete sequences

Eligibility Traces

例子：如图所示，响三声铃铛再亮了一个灯泡，之后发生触电，那么是什么行为导致触电的呢？bell or light？

基于此，有两种启发式算法：

• Frequency heuristic: 按频率进行启发
• Recency heuristic: 按离得最近的进行启发
• 而Eligibility Traces则综合了以上两种启发方式：$$\begin{array}{rl}& E_0(s)=0\\ & E_t(s)=\gamma \lambda E_{t-1}(s)+1(S_t=s)\end{array}$$当访问一个节点时，会使得Eligibility Trace增加，而不访问时，则会随时间衰退。
  

基于Eligibility Traces，我们可以得到Backward View TD(λ)：

• Keep an eligibility trace for every state s
• Update value $V(s)$for every state s
• In proportion to TD-error ${\delta }_t$ and eligibility trace $E_t(s)$。（下面这个TD-error是1-step的）
  $$\begin{array}{rl}{\delta }_t& =R_{t+1}+\gamma V(S_{t+1})-V(S_t)\\ V(s)& \leftarrow V(s)+\alpha {\delta }_t{E}_t(s)\end{array}$$
  

当$\lambda =0$时，只有当前状态被更新$$\begin{array}{rl}& E_t(s)=1(S_t=s)\\ & V(s)\leftarrow V(s)+\alpha {\delta }_t{E}_t(s)\end{array}$$也就等效于TD(0)

当$\lambda =1$时，需要用到整个episode，同时可以进行离线更新。对于其中一个episode，TD(1) 的累计更新方式与MC基本相同。

对于一个episode，从时间$k$处的$s$开始，

• TD(1) eligibility trace会随着时间打折扣$$\begin{array}{c}{E}_t(s)=\gamma E_{t-1}(s)+1(S_t=s)\\ =\{\begin{array}{ll}0& \mathrm{if}t<k\\ {\gamma }^{t-k}& \mathrm{if}t\ge k\end{array}\end{array}$$
• TD(1)在线更新累计误差$$\sum _{t=1}^{T-1}\alpha {\delta }_t{E}_t(s)=\alpha \sum _{t=k}^{T-1}{\gamma }^{t-k}{\delta }_t=\alpha \left(G_k-V(S_k)\right)$$
• 在episode的最后，累计所有的error$${\delta }_k+\gamma {\delta }_{k+1}+{\gamma }^2{\delta }_{k+2}+...+{\gamma }^{T-1-k}{\delta }_{T-1}$$$$\begin{array}{rl}& {\delta }_t+\gamma {\delta }_{t+1}+{\gamma }^2{\delta }_{t+2}+...+{\gamma }^{T-1-t}{\delta }_{T-1}\\ & =R_{t+1}+\gamma V(S_{t+1})-V(S_t)\\ & +\gamma R_{t+2}+{\gamma }^{2}V(S_{t+2})-\gamma V(S_{t+1})\\ & +{\gamma }^2{R}_{t+3}+{\gamma }^{3}V(S_{t+3})-{\gamma }^{2}V(S_{t+2})\\ & +{\gamma }^{T-1-t}{R}_T+{\gamma }^{T-t}V(S_T)-{\gamma }^{T-1-t}V(S_{T-1})\\ & \dots \\ & =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}...+{\gamma }^{T-1-t}{R}_T-V(S_t)\\ & =G_t-V(S_t)\end{array}$$
• TD（1）大致相当于every-visit Monte-Carlo
• error是在线累积的，循序渐进
• 如果价值函数仅在episode结束时离线更新
• 那么总更新与MC完全相同

总结

参考

[1] 伯禹AI
[2] https://www.deepmind.com/learning-resources/introduction-to-reinforcement-learning-with-david-silver
[3] 动手学强化学习
[4] Reinforcement Learning