TD Value Learning

基于时序差分的价值学习

在策略评估时可以通过时序差分方法估计 $v_{\pi}(s)$。但是在环境模型未知时无法通过评估的 $v_{\pi}(s)$ 进行策略提升（转移概率和奖励函数未知，无法计算 $q_{\pi}(s,\ a)$），因此可以利用时序差分方法直接估计 $q_{\pi}(s,\ a)$ 并进行策略提升，最终学习到最优动作价值 $q^{\star}(s,\ a)$，通过最优动作价值可以恢复出最优策略 $\pi^{\star}$。

SARSA

单步 SARSA

SARSA 算法通过时序差分和单步转移 $(s_{t},\ a_{t},\ r_{t + 1},\ s_{t + 1},\ a_{t + 1})$ 来直接对 $q_{\pi}(s,\ a)$ 进行估计：

$q(s_{t},\ a_{t}) = q(s_{t},\ a_{t}) + \alpha \Big[ \underset{\delta_{t}^{(1)}}{\underbrace{r_{t + 1} + \gamma q(s_{t + 1},\ a_{t + 1}) - q(s_{t},\ a_{t})}} \Big]$

事实上对策略进行提升不需要基于完全估计的动作价值，在策略评估不完全的情况下即可进行贪婪的策略提升 $\pi(s) \leftarrow \pi^{+}(s) \in \argmax_{a} q_{\pi}(s,\ a)$，SARSA 等算法交替地进行环境交互、策略评估和策略提升。

同时为了更加准确地估计动作价值，需要在序列中获得不同的状态价值对 $(s,\ a)$。为了避免贪婪策略无法访问某些状态价值对，可以改进为 $\epsilon$-greedy 策略，即有 $\epsilon$ 的概率在动作空间中进行随机采样：

$\pi^{+}(a \mid s) = \left\{ \begin{matrix} \dfrac{\epsilon}{|\mathcal{A}|} + (1 - \epsilon) & a \in \argmax_{a} q(s,\ a) \\[5mm] \dfrac{\epsilon}{|\mathcal{A}|} & a \notin \argmax_{a} q(s,\ a) \end{matrix} \right.$

需要注意的是，SARSA 算法中的 $s_{t}$ 为给定的状态，$a_{t}$ 基于 $s_{t}$ 采用行为策略采样得到，执行后 $r_{t + 1}$ 和 $s_{t + 1}$ 从环境中采样得到，而用于更新 $q$ 值的 $a_{t + 1}$ 的目标策略与行为策略相同，这种算法被称为同策略算法。

多步 SARSA

类似地，基于多步 TD 方法可以平衡估计的偏差和方差，加速 SARSA 算法的收敛速度，其更新方式为：

$q(s_{t},\ a_{t}) = q(s_{t},\ a_{t}) + \alpha \Big[ \underset{\delta_{t}^{(k)}}{\underbrace{r_{t + 1} + \gamma r_{t + 2} + \cdots + \gamma^{k} q(s_{t + k},\ a_{t + k}) - q(s_{t},\ a_{t})}} \Big]$

SARSA(λ)

类似地，基于 TD(λ) 方法可以得到 SARSA(λ) 算法，其中资格迹需要变为 $e(s,\ a)$ 的形式，更新方式为：

$e_{t + 1}(s,\ a) \leftarrow \gamma \lambda e_{t}(s,\ a) + \boldsymbol{1}(s = s_{t + 1},\ a = a_{t + 1})$

每个时间步上 $q(s,\ a)$ 的更新方式为 $q(s,\ a) \leftarrow q(s,\ a) + \alpha \delta_{t} e_{t}(s,\ a)$。

Q-Learning

单步 Q-Learning

与 SARSA 不同的是，Q-Learning 的时序差分更新方式为：

$q(s_{t},\ a_{t}) \leftarrow q(s_{t},\ a_{t}) + \alpha \Big[ \underset{\delta_{t}^{(1)}}{\underbrace{r_{t + 1} + \gamma \max_{a} q(s_{t + 1},\ a) - q(s_{t},\ a_{t})}} \Big] = q(s_{t},\ a_{t}) + \alpha \Big[ r_{t + 1} + \gamma q(s_{t + 1},\ \hat{a}) - q(s_{t},\ a_{t}) \Big]$

其中，$s_{t}$ 为给定的状态，$a_{t}$ 基于 $s_{t}$ 通过行为策略采样得到，执行后 $r_{t + 1}$ 和 $s_{t + 1}$ 从环境中采样得到，而用于更新 $q$ 值的 $\hat{a}$ 的目标策略（$\argmax_{a} q(s_{t + 1},\ a)$）则不同于行为策略，这种算法被称为异策略算法。

多步 Q-Learning

类似地，基于多步 TD 方法得到多步 Q-Learning 算法，其更新方式为：

$q(s_{t},\ a_{t}) \leftarrow q(s_{t},\ a_{t}) + \alpha \Big[ \underset{\delta_{t}^{(k)}}{\underbrace{r_{t + 1} + \gamma r_{t + 2} + \cdots + \gamma^{k} \max_{a} q(s_{t + k},\ a) - q(s_{t},\ a_{t})}} \Big]$

Q(λ)

由于 Q-Learning 为异策略算法，在目标策略采样的 $\hat{a}$ 不同于得到 $s_{t + 1}$ 后行为策略采样的 $a_{t + 1}$ 时需要对资格迹 $e(s,\ a)$ 进行重置操作（置零），具体的更新方式为：

$e_{t + 1}(s,\ a) = \Big[ \gamma \lambda e_{t}(s,\ a) + \boldsymbol{1}(s = s_{t + 1},\ a = \hat{a}) \Big] \cdot \mathbb{I}(a_{t + 1} = \hat{a})$

每个时间步上 $q(s,\ a)$ 的更新方式为 $q(s,\ a) \leftarrow q(s,\ a) + \alpha \delta_{t} e_{t}(s,\ a)$。