Value Learning Technique

价值学习技巧

经验回放

为了更好地学习 Q 值，可以加入经验回放缓冲区，将交互数据 $(s,\ a,\ r,\ s')$ 存储在缓冲区并在训练时进行随机采样得到一个批次的训练样本用于训练，既能够使样本满足独立假设，又可以提高样本利用效率。为了平衡常见样本和少见样本的学习，可以在经验回放的基础上加入非均匀抽样，抽样的概率满足：

$p_{i} \propto |\delta_{i}| + \epsilon \quad i \in \{ 1,\ 2,\ \cdots,\ b \}$

其中 $\delta_{i}$ 为样本 $(s_{i},\ a_{i},\ r_{i},\ s'_{i})$ 的 TD 误差，常数 $\epsilon$ 为很小的正数，防止抽样概率为 0。调整抽样概率的同时也应该设置不同的学习率，为了抵消掉由抽样概率差异带来的预测偏差，可以设置学习率为：

$\alpha_{i} = \frac{\alpha}{(bp_{i})^{\beta}}$

其中 $\alpha$ 为总体学习率，$\beta \in (0,\ 1)$ 为超参数。使用这种优先经验回放的方式可以增加少见样本的利用效率。但是经验回放方法只适用于异策略算法（目标策略不同于行为策略，行为策略的经验可以重复用于目标策略的训练），对于同策略算法则不能使用过时的目标策略收集到的经验。

非均匀高估问题

假设在 Q-Learning 中最终估计得到的动作价值 $q(s,\ a) = q^{\star}(s,\ a) + \epsilon$，其中 $\epsilon(s,\ a)$ 为相互之间独立的均值为零的随机噪声。这种估计虽然是无偏的 $\mathcal{E}_{\epsilon} q(s,\ a) = q^{\star}(s,\ a)$，但是最大动作价值的期望则会产生高估：

$\mathcal{E}_{\epsilon} \max_{a} q(s,\ a) \ge \max_{a} q^{\star}(s,\ a)$

以上不等式的证明如下：给定一组独立且期望相同的随机变量 $X_{1},\ X_{2},\ \cdots,\ X_{n}$，定义随机变量函数 $\phi(\boldsymbol{x})$：

$\phi(\boldsymbol{x}) = \max \{ x_{1} + c_{1},\ x_{2} + c_{2},\ \cdots,\ x_{n} + c_{n} \}$

其中 $c_{i}$ 为常数，考虑 $\forall\ \boldsymbol{x}_{1},\ \boldsymbol{x}_{2} \in \mathbb{R}^{n}$，$\phi(\boldsymbol{x})$ 满足：

$\begin{aligned} \phi(\lambda \boldsymbol{x}_{1} + (1 - \lambda) \boldsymbol{x}_{2}) &= \max_{i} \Big( \lambda x_{i}^{(1)} + (1 - \lambda) x_{i}^{(2)} + c_{i} \Big) = \max_{i} \Big( \lambda (x_{i}^{(1)} + c_{i}) + (1 - \lambda) (x_{i}^{(2)} + c_{i}) \Big) \\[5mm] &\le \lambda \max_{i} (x_{i}^{(1)} + c_{i}) + (1 - \lambda) \max_{j} (x_{j}^{(2)} + c_{j}) = \lambda \phi(\boldsymbol{x}_{1}) + (1 - \lambda) \phi(\boldsymbol{x}_{2}) \end{aligned}$

因此 $\phi(\boldsymbol{x})$ 为凸函数，因此通过 Jasen 不等式可得

$\mathcal{E}_{\boldsymbol{x}} \phi(\boldsymbol{x}) \ge \phi(\mathcal{E}_{\boldsymbol{x}} \boldsymbol{x}) = \max_{i} (\mathcal{E} x_{i} + c_{i}) = \mu_{x} + \max_{i} c_{i}$

利用这一结论可以证明 Q 值的高估现象

$\mathcal{E}_{\epsilon} \max_{a} q(s,\ a) = \max_{a} \Big( q^{\star}(s,\ a) + \epsilon(s,\ a) \Big) \ge \mu_{\epsilon} + \max_{a} q^{\star}(s,\ a) = \max_{a} q^{\star}(s,\ a)$

而在 Q-Learning 的自举学习会导致最大化操作的高估偏差的传播和积累，即：

1. 假设在某一步训练中 $q(s_{t + 1},\ a_{t + 1})$ 高（低）估了真实的 $q^{\star}(s_{t + 1},\ a_{t + 1})$
2. TD 目标 $g_{t}^{(1)} = r_{t + 1} + \max_{a} q(s_{t + 1},\ a)$ 高（低）估了真实的 $q^{\star}(s_{t},\ a_{t})$
3. 被更新的 $q(s_{t},\ a_{t}) \leftarrow q(s_{t},\ a_{t}) + \alpha \Big( g_{t}^{(1)} - q(s_{t},\ a_{t}) \Big)$ 高（低）估了真实的 $q^{\star}(s_{t},\ a_{t})$

因此自举的学习方式会导致最大化操作的高估偏差的传播和积累。同时由于不同的状态价值对 $(s,\ a)$ 出现的频率不同，因此会产生非均匀的高估，导致最终恢复出的策略不可靠。

算法	选择	求值	自举偏差传播问题	最大化高估问题
Q-Learning	$\hat{a} = \argmax_{a} q(s_{t + 1},\ a)$	$g_{t}^{(1)} = q(s_{t + 1},\ \hat{a})$	$\surd$	$\surd$
Target Q	$\hat{a} = \argmax_{a} \tilde{q}(s_{t + 1},\ a)$	$g_{t}^{(1)} = \tilde {q}(s_{t + 1},\ \hat{a})$	$\times$	$\surd$
Double Q	$\hat{a} = \argmax_{a} q(s_{t + 1},\ a)$	$g_{t}^{(1)} = \tilde {q}(s_{t + 1},\ \hat{a})$	$\times$	$\times$

Target Q

考虑到原始的 Q-Learning 算法存在由自举带来的偏差，以及 Q 表（网络）的更新带来的目标的不稳定性，可以加入额外的一个目标 Q 表 $\tilde{q}(s,\ a)$ 或 Q 网络 $\tilde{q}_{w^{-}}(s,\ a)$ 用于计算 TD 目标，从而切断自举：

$g_{t}^{(1)} = q(s_{t},\ a_{t}) - \Big( r_{t + 1} + \max_{a} \tilde{q}(s_{t + 1},\ a) \Big)$

并且目标 Q 表（网络）$\tilde{q}(s,\ a)$ 的值（参数）会间隔若干步与训练 Q 表（网络）$q(s,\ a)$ 进行同步，以此提高算法稳定性。同时在同步时可以采用软更新，例如目标网络参数 $w^{-}$ 的同步方式可以设置为：

$w^{-} \leftarrow \tau w^{-} + (1 - \tau) w \quad \tau \in (0,\ 1)$

Double Q

由于 Q-Learning 算法中训练时的最大化操作会产生对 Q 值的过高估计问题。Double Q 同时利用目标 Q 表（网络） $q$ 和训练 Q 表（网络） $\tilde{q}$ 来估计最优策略的动作价值 $\max_{a} q^{\star}(s,\ a)$，具体的优化目标为：

$r_{t + 1} + \gamma \tilde{q} \Big( s_{t + 1},\ \argmax_{a} q(s_{t + 1},\ a) \Big)$

与 Q-Learning 的区别在于 $\hat{a} = \argmax_{a} q(s_{t + 1},\ a) \ne \argmax_{a} \tilde{q}(s_{t + 1},\ a)$，其他算法逻辑则保持一致。由于 $\tilde{q} \Big( s_{t + 1},\ \argmax_{a} q(s_{t + 1},\ a) \Big) \le \max_{a} \tilde{q}(s_{t + 1},\ a)$，因此可以缓解 Q 值高估问题。