SARSA算法：

• SARSA名字由来：SARSA每次用一个五元组来更新动作价值表（Q表）：\((s_t,a_t,r_t,s_{t+1},a_{t+1})\)，SARSA的每一个字母对应元组里的一个元素。
• 表格版本。状态和动作都是有限的，以状态为行，动作为列建表，表中的每个元素表示动作价值\(Q_\pi(s,a)\)：
  1. 观测到一个状态转移：\((s_t,a_t,r_t,s_{t+1})\)；
  2. 依据策略函数抽样一个动作\(a_{t+1}\)；
  3. TD target：\(y_t = r_t + \gamma \cdot Q(s_{t+1},a_{t+1})\)；
  4. TD error：\(\delta_t = Q(s_t,a_t) - y_t\)；
  5. 更新表格：\(Q_\pi(s_t,a_t) \leftarrow Q_\pi(s_t,a_t) - \lambda \delta_t\)。
• 神经网络版本。状态空间非常大，用神经网络\(q(s,a;w)\)来近似动作价值函数\(Q_\pi(s,a)\)。
  1. 神经网络的输入是状态，输出是n维向量，向量每个元素表示某一个动作的价值。（与actor-critic中的critic一致）
  2. 与上同求得TD target；
  3. 使用TD target与网络输出的均方误差作为loss对网络参数做梯度下降优化。

Q-learning（DQN)：

• Q-learning用来学习最优动作价值函数\(Q^*(s,a)\)。（SARSA学习的是\(Q_\pi(s,a)\)）

  • Q-learning的TD target：\(y_t = t_t + \mathop {max}\limits_a Q^*(s_{t+1},a)\)；（SARSA没有对动作价值函数求最大化）

  • 表格版本：

    • 表格中行代表状态，列代表动作，值代表动作价值。
    1. 观测到四元组transition\((s_t,a_t,r_t,s_{t+1})\)；
    2. TD target：\(y_t = r_t + \gamma \cdot \mathop {max}\limits_ a Q^*(s_{t+1},a)\)；（表格中对应行中最大的值）
    3. TD error：\(\delta_t = Q^*(s_t,a_t) - y_t\)；
    4. 更新：\(Q^*(s_t,a_t) \leftarrow Q^*(s_t,a_t) + \lambda \delta_t\)；

• DQN版本：

  • 同上，使用神经网络近似最优动作价值。

Multi-step TD

• 标准TD算法使用一步真实奖励来优化，multi-step使用多个多步奖励进行优化。
• multi-step target for sarsa：\(y_t = \sum_{i=0}^{m - 1} \gamma^i r_{t+1} + \gamma^m Q(s_{t+m,a_{t+m}})\)；
• multi-step target for Q-learning：\(y_t = \sum_{i=0}^{m - 1} \gamma^i r_{t+1} + \gamma^m Q^*(s_{t+m,a})\)；