[RL Notes] 时序差分的目标

Author: nex3z 2019-11-04

1. 半梯度下降

　　对于通用 SGD 方法

$$\begin{equation} \boldsymbol{\mathrm{w}}_{t+1} \doteq \boldsymbol{\mathrm{w}}_t + \alpha \big[U_t – \hat{v}(s, \boldsymbol{\mathrm{w}}_t)^2\big] \nabla \hat{v}(s, \boldsymbol{\mathrm{w}}_t) \tag{1} \end{equation}$$

如果 $U_t$ 是一个无偏估计，即满足对于任意的 $t$，有 $\mathbb{E}[U_t|S_t=s] = v_{\pi}(S_t)$，那么 $\boldsymbol{\mathrm{w}}$ 会收敛到局部最优。

　　如果使用将式 $(1)$ 中的 $U_t$ 替换为自举的目标，例如单步时序差分的目标，即

$$\begin{equation} U_{t} \doteq R_{t+1} + \gamma \hat{v}(S_{t+1}, \boldsymbol{\mathrm{w}}) \tag{2} \end{equation}$$

此时的目标会依赖于当前的价值估计 $\hat{v}(S_{t+1}, \boldsymbol{\mathrm{w}})$，当前的价值估计很可能不等于真实的价值，这就导致 $U_{t}$ 是有偏的，不能保证 $\boldsymbol{\mathrm{w}}$ 收敛到价值误差的局部最优。计算式 $(2)$ 对 $\boldsymbol{\mathrm{w}}$ 的梯度，可得

$$\begin{equation} \nabla \frac{1}{2} \big[U_t – \hat{v}(S_t, \boldsymbol{\mathrm{w}})\big]^2 = \big(U_t – \hat{v}(S_t, \boldsymbol{\mathrm{w}})\big) \big(\nabla U_t – \nabla \hat{v}(S_t, \boldsymbol{\mathrm{w}})\big) \tag{3} \end{equation}$$

注意由式 $(2)$ 可知 $U_t$ 依赖于 $\boldsymbol{\mathrm{w}}$，有

$$\begin{equation} \nabla U_t = \nabla \big(R_{t+1} + \gamma \hat{v}(S_{t+1}, \boldsymbol{\mathrm{w}})\big) = \gamma \nabla \hat{v}(S_{t+1}, \boldsymbol{\mathrm{w}}) \tag{4} \end{equation}$$

如果使用式 $(3)$ 进行“梯度下降”，则在对权重的优化过程中，只考虑了改变权重对估计的影响，而忽略了对目标的影响。由于只包含一部分梯度，这种方法称为半梯度（semi-gradient）方法。

　　虽然半梯度方法不能像梯度方法那样稳健地收敛，但它在多数情况下仍能可靠地收敛，而且由于时序差分目标相比收益的采样通常具有较小的方差，这使得它能更快收敛。

2. 半梯度 TD 算法

　　使用半梯度的 TD(0) 算法如下所示。

---

半梯度 TD(0)，用于估计 $\hat{v} \approx v_{\pi}$
输入：待评估的策略 $\pi$
输入：一个可微的函数 $\hat{v}: \mathcal{S}^+ \times \mathbb{R}^d \rightarrow \mathbb{R}$，满足 $\hat{v}(终止状态,\cdot) = 0$
算法参数：步长 $\alpha > 0$
对价值函数的权值 $\boldsymbol{\mathrm{w}} \in \mathbb{R}^d$ 进行任意的初始化（例如 $\boldsymbol{\mathrm{w}} = 0$）
对每一幕循环：
　　初始化 $S$
　　对该幕的每一步循环：
　　　　选取 $A \sim \pi(\cdot|S)$
　　　　采取动作 $A$，观察 $R, S’$
　　　　$\boldsymbol{\mathrm{w}} \leftarrow \boldsymbol{\mathrm{w}} + \alpha [R + \gamma \hat{v}(S’, \boldsymbol{\mathrm{w}}) – \hat{v}(S, \boldsymbol{\mathrm{w}})] \nabla \hat{v}(S, \boldsymbol{\mathrm{w}})$
　　　　$S \leftarrow S’$
　　直到 $S’$ 为终止状态

---