当前位置：首页 > news >正文

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

news 来源：原创 2025/7/26 8:55:34

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

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

2.4.1 Robbins-Monro算法

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

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

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

其中 $\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], \quad 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], \quad 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{aligned}\tilde{g}(v(s)) & =v_\pi\left(s_t\right)-\left[r_{t+1}+\gamma v_\pi\left(s_{t+1}\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)}_{g\left(v_\pi\left(s_t\right)\right)} \\ &+ \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)}_\eta . \end{aligned}$

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

$\begin{aligned}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{aligned}$

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

2.4.2.2 定义

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

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

$\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{aligned}& 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] \\\Longrightarrow & 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] \\\Longrightarrow & 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] \\\Longrightarrow & \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{aligned}$

因为 $\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}+\ldots$ 的样本。假设每个片段的长度是 $L$ 。假设每个状态有相同数量的动作，即 $|\mathcal{A}$ 。那么，按照软策略，一共有 $|\mathcal{A}|^L$ 种可能的片段。但是MC只使用部分片段来估计整体，所以估计方差较高.