【强化学习入门笔记】 2.4 时序差分算法

本系列为学习赵世钰老师的《强化学习的数学原理》所作的学习笔记.

本节我们将介绍强化学习中的蒙特卡洛方法.

2.4.1 Robbins-Monro算法

Robbins-Monro算法是一种随机近似方法，通过迭代的方式求解非线性方程。

假设我们要求解: $g(w)=0$, 但是我们没有$g(w)$的具体函数形式, 只有它的观测数据:

$$\begin{array}{rl}\tilde{g}(w,\eta )& =g(w)+\eta ,\end{array}$$

其中$\eta$是观测误差, 那么我们可以利用观测数据, 迭代式的逼近$g(w)$的根:

$$w_{k+1}=w_k-a_k\tilde{g}\left(w_k,{\eta }_k\right),$$

其中$a_k$是一个大于0的参数, 迭代过程如下图, 这种方法就是Robbins-Monro算法. 它的收敛性证明可以前往书中查看.

2.4.2 TD learning 时序差分算法

2.4.2.1 推导

时序差分算法用来计算给定策略$\pi$和其状态$s$的状态值期望$v_{\pi }(s)$, 即贝尔曼公式:

$$v_{\pi }(s)=\mathbb{E}\left[R_{t+1}+\gamma G_{t+1}\mid S_t=s\right],s\in \mathcal{S}$$

因为$t+1$的discounted return实际上就是其状态值的期望:

$$\mathbb{E}\left[G_{t+1}\mid S_t=s\right]=\sum _a\pi (a\mid s)\sum _{s^{\prime }}p\left(s^{\prime }\mid s,a\right)v_{\pi }\left(s^{\prime }\right)=\mathbb{E}\left[v_{\pi }\left(S_{t+1}\right)\mid S_t=s\right]$$

因此贝尔曼公式也可以写作, 也叫做贝尔曼期望公式:

$$v_{\pi }(s)=\mathbb{E}\left[R_{t+1}+\gamma v_{\pi }\left(S_{t+1}\right)\mid S_t=s\right],s\in \mathcal{S}.$$

TD算法就是利用RM算法迭代求解贝尔曼公式, 首先我们定义求解目标:

$$g\left(v_{\pi }\left(s_t\right)\right)\doteq v_{\pi }\left(s_t\right)-\mathbb{E}\left[R_{t+1}+\gamma v_{\pi }\left(S_{t+1}\right)\mid S_t=s_t\right]=0$$

接着我们写出它的采样$\tilde{g}(v(s))$:

$$\begin{array}{rl}\tilde{g}(v(s))& =v_{\pi }\left(s_t\right)-\left[r_{t+1}+\gamma v_{\pi }\left(s_{t+1}\right)\right]\\ & =\underset{g\left(v_{\pi }\left(s_t\right)\right)}{\underbrace{\left(v_{\pi }\left(s_t\right)-\mathbb{E}\left[R_{t+1}+\gamma v_{\pi }\left(S_{t+1}\right)\mid S_t=s_t\right]\right)}}\\ & +\underset{\eta }{\underbrace{\left(\mathbb{E}\left[R_{t+1}+\gamma v_{\pi }\left(S_{t+1}\right)\mid S_t=s_t\right]-\left[r_{t+1}+\gamma v_{\pi }\left(s_{t+1}\right)\right]\right)}}.\end{array}$$

然后根据RM算法, 写出更新方程:

$$\begin{array}{rl}{v}_{t+1}\left(s_t\right)& =v_t\left(s_t\right)-{\alpha }_t\left(s_t\right)\tilde{g}\left(v_t\left(s_t\right)\right)\\ & =v_t\left(s_t\right)-{\alpha }_t\left(s_t\right)\left(v_t\left(s_t\right)-\left[r_{t+1}+\gamma v_{\pi }\left(s_{t+1}\right)\right]\right)\end{array}$$

实际上, 上式就是TD learning算法更新公式

2.4.2.2 定义

假设我们基于一个策略$\pi$, 按时间步顺序生成了一组状态和奖励: $\left(s_0,r_1,s_1,\dots ,s_t,r_{t+1},s_{t+1},\dots \right)$, 用下式更新$v_{t+1}$, 就是时序差分算法:

$$\underset{\text{new estimate }}{\underbrace{v_{t+1}\left(s_t\right)}}=\underset{\text{current estimate }}{\underbrace{v_t\left(s_t\right)}}-{\alpha }_t\left(s_t\right)[\stackrel{\text{TD error }{\delta }_t}{\overbrace{v_t\left(s_t\right)-(\underset{\text{TD target }{\bar{v}}_t}{\underbrace{r_{t+1}+\gamma v_t\left(s_{t+1}\right)}})}}],$$

• ${\bar{v}}_t$是TD target, 代表$v_t$更新的目标
• ${\delta }_t$是TD error, 代表$v_t$更新的目标与$v_t$之间的误差

我们可以简写成如下形式, 显然这符合Robbins-Monro算法的形式:

$$v_{t+1}\left(s_t\right)=v_t\left(s_t\right)-{\alpha }_t\left(s_t\right)\left[v_t\left(s_t\right)-{\bar{v}}_t\right]$$

2.4.2.3 TD target 和 TD error

为了理解为什么${\bar{v}}_t$是更新的目标, 并做推导:

$$\begin{array}{rl}& v_{t+1}\left(s_t\right)=v_t\left(s_t\right)-{\alpha }_t\left(s_t\right)\left[v_t\left(s_t\right)-{\bar{v}}_t\right]\\ ⟹& v_{t+1}\left(s_t\right)-{\bar{v}}_t=v_t\left(s_t\right)-{\bar{v}}_t-{\alpha }_t\left(s_t\right)\left[v_t\left(s_t\right)-{\bar{v}}_t\right]\\ ⟹& v_{t+1}\left(s_t\right)-{\bar{v}}_t=\left[1-{\alpha }_t\left(s_t\right)\right]\left[v_t\left(s_t\right)-{\bar{v}}_t\right]\\ ⟹& \left|v_{t+1}\left(s_t\right)-{\bar{v}}_t\right|=\left|1-{\alpha }_t\left(s_t\right)\right|\left|v_t\left(s_t\right)-{\bar{v}}_t\right|\end{array}$$

因为${\alpha }_t\left(s_t\right)$是一个小的正数, 因此$0<1-{\alpha }_t\left(s_t\right)<1$, 所以:

$$\left|v_{t+1}\left(s_t\right)-{\bar{v}}_t\right|<\left|v_t\left(s_t\right)-{\bar{v}}_t\right|.$$

这说明了: $v_{t+1}$比$v_t$离${\bar{v}}_t$更近, 代表这算法是在朝着目标${\bar{v}}_t$迭代更新$v_t$.

那么${\delta }_t$代表误差就很容易理解了, 当${\delta }_t=0$时, 代表$v_t$已经达到了目标.

2.4.3 TD learning 和 MC learning对比

2.4.3.1 在线/离线

• TD learning: 是在线算法, 每迭代一步(从$k$到$k+1$)就可以在线更新;
• MC learning: 是离线算法, 也就是它必须等到episode采样结束, 才能更新

2.4.3.2 持续任务/片段任务

• TD learning: 可以处理持续和片段任务, 因为它是在线更新的, 所以不需要等到采样完整结束;
• MC learning: 只能处理持续和片段任务,因为它必须要等到此案有完整结束才能更新

2.4.3.3 Bootstrapping

• TD learning: Bootstrapping, 它在初始猜测策略的基础上, 不需要完整的episode就能更新策略; 但是相应的, 差的初始猜测会让他更难接近最优解.
• MC learning: none Bootstrapping, 它不需要初始猜测, 可以直接估计状态/动作值.

2.4.3.4 估计方差

• TD learning: 估计方差小, 因为它涉及的随机变量较少, 只需要一步的数据;
• MC learning: 估计方差大, 因为涉及许多随机变量。例如，要估计$q_{\pi }\left(s_t,a_t\right)$，我们需要$R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots$的样本。假设每个片段的长度是$L$。假设每个状态有相同数量的动作，即$|\mathcal{A}$。那么，按照软策略，一共有$|\mathcal{A}{|}^L$种可能的片段。但是MC只使用部分片段来估计整体，所以估计方差较高.