David silver 强化学习 Lecture 4

课程主页： https://www.davidsilver.uk/teaching/

这里回顾David silver 强化学习 Lecture 4的课程内容，这一讲简单介绍了不基于模型的预测。

介绍

上一讲介绍了如何通过DP进行规划，那里假设MDP已知；这一讲介绍不基于模型的预测，即对未知的MDP预测其价值函数。

蒙特卡洛学习

• 目标：通过策略$\pi$下的信息学习$v_\pi$

  $$S_{1}, A_{1}, R_{2}, \ldots, S_{k} \sim \pi$$

• 注意回报（return）是折扣奖励：

  $$G_{t}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1} R_{T}$$

• 回报价值函数是回报（return）的期望：

  $$v_{\pi}(s)=\mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right]$$

• 蒙特卡洛策略评估使用经验均值回报而非期望回报

具体方式如下：

• 为了评估状态$s$
• 在一幕（episode）中访问状态$s$的第一个（每一个）时间戳$t$
• 增加计数器$N(s) \leftarrow N(s)+1$
• 增加总回报$S(s) \leftarrow S(s)+G_{t}$
• 价值通过回报的均值估计$V(s) = S(s)/N(s)$
• 根据大数定律，随着$N(s)\to \infty$，$V(s) \rightarrow v_{\pi}(s)$

增量均值

序列$x_1,x_2,\ldots$的均值$\mu_1,\mu_2,\ldots$可以通过增量方式计算：

$$\begin{aligned} \mu_{k} &=\frac{1}{k} \sum_{j=1}^{k} x_{j} \\ &=\frac{1}{k}\left(x_{k}+\sum_{j=1}^{k-1} x_{j}\right) \\ &=\frac{1}{k}\left(x_{k}+(k-1) \mu_{k-1}\right) \\ &=\mu_{k-1}+\frac{1}{k}\left(x_{k}-\mu_{k-1}\right) \end{aligned}$$

增量MC更新

• 根据上述公式，可以通过增量方式更新$V(s)$

• 对于回报为$G_t$的状态$S_t$

  $$\begin{array}{l}{N\left(S_{t}\right) \leftarrow N\left(S_{t}\right)+1} \\ {V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\frac{1}{N\left(S_{t}\right)}\left(G_{t}-V\left(S_{t}\right)\right)}\end{array}$$

• 在非平稳问题中，跟踪连续平均值（即忘掉旧幕（episodes））可能很有用。

  $$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}-V\left(S_{t}\right)\right)$$

时序差分学习（Temporal-Difference Learning）

• TD方法可直接从经验中学习
• TD是不基于模型的：不需要了解MDP转移/奖励
• TD通过bootstrapping从不完整的幕中学习
• TD根据猜测更新猜测

MC and TD

• 目标：在策略$\pi$下根据经验在线学习$v_\pi$

• 增量MC

  • 根据实际回报$G_t $更新价值$V(S_t)$ $$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}-V\left(S_{t}\right)\right)$$

• 考虑最简单的时序差分算法：$TD(0)$

  • 通过估计回报$R_{t+1}+\gamma V\left(S_{t+1}\right)$更新$V(S_t)$

    $$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\right)$$

  • $R_{t+1}+\gamma V\left(S_{t+1}\right)$被称为TD目标

  • $\delta_{t}=R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)$被称为TD误差

MC vs TD的优劣势对比（1）

• TD在知道最终结果之前就可以学习
  • TD可以在每一步后在线学习
  • MC必须等到每一幕结束后知道回报的时刻
• TD可以在不知道最终结果的条件下学习
  • TD可以从不完全序列中学习
  • MC只能从完全序列中学习
  • TD可以在连续（非终止）环境中运行
  • MC只能在幕（终止）环境中运行

偏差/方差权衡

• 回报$G_{t}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1} R_{T}$是$v_\pi (S_t)$的无偏估计
• 真正的TD目标$R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right)$是$v_\pi (S_t)$的无偏估计
• TD目标$R_{t+1}+\gamma V\left(S_{t+1}\right)$是$v_\pi (S_t)$的有偏估计
• TD目标比回报的方差要小的多：
  • 因为回报依赖于很多随机动作，转移以及奖励
  • TD目标只依赖一个随机动作，转移以及奖励

MC vs TD的优劣势对比（2）

• MC有高方差，无偏
  • 很好的收敛性
  • 对初始值不敏感
  • 很好理解和使用
• TD有低方差，有偏
  • 通常比MC更高效
  • TD(0)收敛于$v_\pi(s)$
  • 对初始值更敏感

批量MC和TD

• MC和TD都收敛：$V(s)\to v_\pi(s)$随着经验$\to \infty$

• 但是对于有限经验的批处理解决方案呢？

  $$\begin{array}{c}{s_{1}^{1}, a_{1}^{1}, r_{2}^{1}, \ldots, s_{T_{1}}^{1}} \\ {\vdots} \\ {s_{1}^{K}, a_{1}^{K}, r_{2}^{K}, \ldots, s_{T_{K}}^{K}}\end{array}$$
  • 例如：重复对第$k\in [1,K]$幕采样
  • 对第$k$幕应用MC或$TD(0)$

MC vs TD的优劣势对比（3）

由TD的表达式，不难得到

• TD利用了马尔可夫性
  • 通常在马尔可夫环境下更高效
• MC没有利用马尔可夫性
  • 通常在非马尔可夫环境下更高效

对比

MC

$$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}-V\left(S_{t}\right)\right)$$

TD

$$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\right)$$

DP

$$V\left(S_{t}\right) \leftarrow \mathbb{E}_{\pi}\left[R_{t+1}+\gamma V\left(S_{t+1}\right)\right]$$

Bootstrapping和采样

• Bootstrapping：更新涉及估计
  • MC不使用Bootstrap
  • DP使用Bootstrap
  • TD使用Bootstrap
• 采样：
  • MC使用采样
  • DP不使用采样
  • TD使用采样

$TD(\lambda)$

假设$TD$查看未来的$n$步

$n$步回报

• 考虑如下$n$步回报：

  $$\begin{aligned} {n=1} &&(T D) &&G_{t}^{(1)}=R_{t+1}+\gamma V\left(S_{t+1}\right) \\ {n=2} && &&{G_{t}^{(2)}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} V\left(S_{t+2}\right)} \\ {\vdots} && &&{\vdots} \\ {n=\infty} && (M C) && G_{t}^{(\infty)}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1} R_{T}\end{aligned}$$

• 定义$n$步回报

  $$G_{t}^{(n)}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{n-1} R_{t+n}+\gamma^{n} V\left(S_{t+n}\right)$$

• $n$步时序差分学习

  $$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}^{(n)}-V\left(S_{t}\right)\right)$$

$\lambda$回报

接下来考虑对不同步数的回报做加权：

• $\lambda-$回报$G_t^\lambda $结合了所有$n$步回报$G_t^{(n)}$

• 使用权重$(1-\lambda) \lambda^{n-1}$

  $$G_{t}^{\lambda}=(1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t}^{(n)}$$

• $TD(\lambda)$的前向视角（Forward-view）

  $$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}^{\lambda}-V\left(S_{t}\right)\right)$$

$TD(\lambda)$的前向视角

• 通过$\lambda-$回报更新价值函数
• 通过对未来的前瞻性计算$G_t^{\lambda}$
• 像MC一样，只能根据完整的幕（episodes）计算

$TD(\lambda)$的反向视角

• 前向视角提供理论
• 反向提供了机制
• 从不完整的序列在线更新每一步

为了讨论反向视角，首先定义合格轨迹：

$$\begin{array}{l}{E_{0}(s)=0} \\ {E_{t}(s)=\gamma \lambda E_{t-1}(s)+\mathbf{1}\left(S_{t}=s\right)}\end{array}$$

• 保持每个状态$s$的合格轨迹$E_t(s)$

• 对每个状态$s$更新$V(s)$

• 更新项正比于TD-误差$\delta_t$和合格轨迹$E_t(s)$

  $$\begin{aligned} \delta_{t} &=R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right) \\ V(s) & \leftarrow V(s)+\alpha \delta_{t} E_{t}(s) \end{aligned}$$

$TD(\lambda)$和$TD(0)$

• 当$\lambda =0$，只有当前状态被更新

  $$\begin{aligned} E_{t}(s) &=\mathbf{1}\left(S_{t}=s\right) \\ V(s) & \leftarrow V(s)+\alpha \delta_{t} E_{t}(s) \end{aligned}$$

• 这等价于$TD(0)$更新

  $$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha \delta_{t}$$

$TD(1)$和MC

• 考虑在时间戳$k$一次访问$s$的一幕

• 考虑$TD(1)$的合格轨迹

  $$\begin{aligned} E_{t}(s) &=\gamma E_{t-1}(s)+\mathbf{1}\left(S_{t}=s\right) \\ &=\left\{\begin{array}{ll}{0} & {\text { if } t<k} \\ {\gamma^{t-k}} & {\text { if } t \geq k}\end{array}\right.\end{aligned}$$

• $TD(1)$更新在线累积误差

  $$\sum_{t=1}^{T-1} \alpha \delta_{t} E_{t}(s)=\alpha \sum_{t=k}^{T-1} \gamma^{t-k} \delta_{t}$$

• 在幕结束时，累计误差为

  $$\delta_{k}+\gamma \delta_{k+1}+\gamma^{2} \delta_{k+2}+\ldots+\gamma^{T-1-k} \delta_{T-1}$$

• 利用公式$ \delta_{t} =R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)$对其处理可得

  $$\begin{aligned} & \delta_{t}+\gamma \delta_{t+1}+\gamma^{2} \delta_{t+2}+\ldots+\gamma^{T-1-t} \delta_{T-1} \\=& R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right) \\+& \gamma R_{t+2}+\gamma^{2} V\left(S_{t+2}\right)-\gamma V\left(S_{t+1}\right) \\+& \gamma^{2} R_{t+3}+\gamma^{3} V\left(S_{t+3}\right)-\gamma^{2} V\left(S_{t+2}\right) \\+& \gamma^{T-1-t} R_{T}+\gamma^{T-t} V\left(S_{T}\right)-\gamma^{T-1-t} V\left(S_{T-1}\right) \\=& R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3 \cdots}+\gamma^{T-1-t} R_{T}-V\left(S_{t}\right) \\=& G_{t}-V\left(S_{t}\right) \end{aligned}$$

• 所以

  $$\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\left(S_{k}\right)\right)$$

更一般的，我们有如下定理：

定理

对于$TD(\lambda)$的前向视角和后向视角，所有更新的总和是相同的：

$$\sum_{t=1}^{T} \alpha \delta_{t} E_{t}(s)=\sum_{t=1}^{T} \alpha\left(G_{t}^{\lambda}-V\left(S_{t}\right)\right) \mathbf{1}\left(S_{t}=s\right)$$

总之，$TD(1)$几乎等价于MC

离线更新

离线更新

• 更新在一幕中累积
• 但在幕结束时批量应用

在线更新

• $TD(\lambda)$在每一幕的每一步中都进行更新
• $TD(\lambda)$的前向反向视角有所不同

总结