TD算法

  • TD算法
  1. 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对网络参数做梯度下降优化。
  2. 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版本:

      • 同上,使用神经网络近似最优动作价值。
  3. 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})\);
上一篇:【NOIP普及】排座椅


下一篇:表格属性及合并