TD算法

5 min
2201 words
Categories: 强化学习 机器学习
Tags: TD学习，sarsa，Q Learning

sarsa

TD目标

  • 折扣回报： $U_t = R_t + \gamma U_{t+1}$
  • 动作价值： $$ \begin{aligned} Q_\pi (s_t,a_t) &= E[U_t|s_t,a_t] \ &= E [R_t + \gamma U_{t+1} | s_t,a_t] \ &= E [R_t] + \gamma E [U_{t+1} | s_t,a_t] \ &= E [R_t] + \gamma E [Q_\pi (S_{t+1},A_{t+1}) | s_t,a_t] \ &= E [R_t + \gamma Q_\pi (S_{t+1},A_{t+1})] \end{aligned} $$
  • TD目标： 对「动作价值」进行蒙特卡洛近似，得 $y_t = r_t + \gamma Q_\pi (s_{t+1},a_{t+1})$

表格形式

形式：利用一个表格来记录 $Q _\pi(s,a)$，行为状态 $s$，列为动作 $a$。

算法：

  1. 根据状态 $s_{t+1}$，通过策略函数 $\pi (a|s)$ 预测下一个动作 $a_{t+1}$
  2. TD目标：$y_t = r_t + \gamma Q_\pi (s_{t+1},a_{t+1})$
  3. TD误差：$\delta_t = Q_\pi (s_t,a_t) - y_t$
  4. 更新 $Q_\pi$：$Q_\pi(s_t,a_t) = Q_\pi(s_t,a_t) - \alpha \delta_t$

Sarsa($\lambda$)

Sarsa 表格的问题

  • 问题：

    1. 角色可能在前进的轨迹上转圈（在某几个状态上来回切换）

  • 解决思路：

    1. 对轨迹上的每个状态进行「标记」，标记值越大的状态，说明该状态对找到宝藏的贡献越大，尽量避免没必要的转圈

Sarsa($\lambda$) 的实现

  • 状态个数： 利用多少个状态对 $Q_{\pi}$ 进行更新，这里的取值范围为 1 ~ n（n：表示一回合结束时，轨迹所包含状态的个数），但是由于我们不会真的一回合才进行更新，所以并不知道一回合会有多少状态。因此，可以将状态个数映射到 [0,1]，0：表示1个状态；1：表示n个状态，而我们用于Sarsa更新，使用的状态个数为 $\lambda \in [0,1]$，所以该算法就称之为 Sarsa($\lambda$)

  • 状态标记：

    1. 每个状态被经过一次，将会被标记，标记会随时间衰减
    2. 当一个状态被多次经过时，对于标记值的处理方式有两种
      • 标记值直接叠加
      • 标记值限幅

  • 算法流程：每一轮游戏的开始前，都会将轨迹表归零，$E = 0$

    1. 根据状态 $s_{t+1}$，通过策略函数 $\pi (a|s)$ 预测下一个动作 $a_{t+1}$
    2. TD目标：$y_t = r_t + \gamma Q_\pi (s_{t+1},a_{t+1})$
    3. TD误差：$\delta_t = Q_\pi (s_t,a_t) - y_t$
    4. 更新的轨迹表$E$：
      • 方式一：$E(s_t,a_t) = E(s_t,a_t) + 1$
      • 方式二：$E(s_t,:) = 0; \ E(s_t,a_t) = 1$
    5. 实现 $E$ 全表中标记值的衰减：$E = \gamma \lambda E$

  • Sarsa($\lambda$) 案例

Sarsa($\lambda$) 解释

  • e4时刻的$Q_\pi$ 更新：

    在e4时刻，对于 $Q(e4)$ 的TD误差为

    $$ \delta_{q4} = Q(e4) - r_4 - \gamma Q(e5) $$

    并对 $Q(e4)$ 进行修正

    $$ Q(e4)’ = Q(e4) - \alpha \delta_{q4} $$

    在e3时刻，对于 $Q(e3)$ 的TD误差为

    $$ \delta_{q3} = Q(e3) - r_3 - \gamma Q(e4) $$

    在e3时，我们并不知道Q(e4)具有误差的情况下，对$Q(e3)$进行了修正

    $$ Q(e3)’ = Q(e3) - \alpha \delta_{q3} $$

    在e4时刻，我们得到了更准确的 $Q(e4)’$ ，回代修正 $Q(e3)$

    $$ \begin{aligned} \delta_{q3}’ &= Q(e3) - r_3 - \gamma Q(e4)’ \ &= Q(e3) - r_3 - \gamma [ Q(e4) - \alpha \delta_{q4} ] \ &= Q(e3) - r_3 - \gamma Q(e4) + \gamma \alpha \delta_{q4} \ &= \delta_{q3} + \gamma \delta_{q4} \end{aligned} $$

    重新对$Q(e3)$进行修正

    $$ \begin{aligned} Q(e3)’’ &= Q(e3) - \alpha \delta_{q3}’ \ &= Q(e3) - \alpha \delta_{q3} - \alpha\gamma \delta_{q4} \ &= Q(e3)’ - \alpha \delta_{q4} \gamma \end{aligned} $$

    最终得到的公式就与计算流程的更新公式所对应：

    $$ \begin{aligned} Q(e3)’’ &= Q(e3)’ - \alpha \delta_{q4} \gamma \ Q_\pi &= Q_\pi - \alpha \delta_t E \end{aligned} $$

    其他状态同理，就是一层一层的套娃下去。

  • $Q_\pi$ 更新： 对于上述的 Sarsa($\lambda$) 算法，并非是一轮游戏结束后，才对 $Q_\pi$ 表进更新。从算法的计算流程可以看出 $Q_\pi$ 表在每一次动作后，都会更新一次，也就是说，角色每转移一次状态，就会停下来，对之前的轨迹进行一次回顾，修正之前所经历的状态到当前状态 $s_t$ 的关联性。

  • 状态个数： 在e4时刻，对于轨迹状态e1的动作价值 $Q_\pi$ 更新，涉及的状态就有e2 - e4；对于轨迹状态e2而言，就是e3 - e4

  • $\lambda$ 实现状态个数控制：

    • $\lambda = 0$：这就导致一下次状态的开始，$E=0$，然后轨迹表只有当前状态才有记录：$E(s_t,a_t) = 1$，因此 $Q_\pi = Q_\pi - \alpha \delta_t E$ 实际只更新了当前状态的 $Q_\pi(s_t,a_t)$。
    • $\lambda = 1$：$Q_\pi = Q_\pi - \alpha \delta_t E$ 更新了 从回合开始状态 $s_0$ 到当前状态 $s_t$ 对应的所有 $Q_\pi$值
    • $\lambda \in (0,1)$：由于 $E = \gamma \lambda E$ 的反复迭代，实现了轨迹标记值的衰减，离当前状态越近的状态，其标记值越大，例如到达e4时刻时， e4 = 1；e3 = 0.8；e2 = 0.64，时间越靠前，e 值就越小，对e值再乘以一个倍数值 $\lambda$，就可以将原来当前时刻的e值变得更小，几乎就等于0了，这样就实现了类似于 $\lambda = 0$ 时，状态的 $Q_\pi$ 不更新。即 $\lambda$ 使得比较旧的 $Q_{pi}$ 不再参与到更新，也就控制了「状态个数」

神经网络形式

思路： 利用神经网络 $q(s,a;w)$ 来近似动作价值函数 $Q_\pi(s,a)$。 输入为状态，输出为各个动作对应的价值

算法：

  1. 根据状态 $s_{t+1}$，通过策略函数 $\pi (a|s)$ 预测下一个动作 $a_{t+1}$
  2. TD目标：$y_t = r_t + \gamma q (s_{t+1},a_{t+1};w)$
  3. TD误差：$\delta_t = q (s_t,a_t;w) - y_t$
  4. 损失函数：$L=\frac{1}{2} \delta_t^2$
  5. 更新系数：$w = w - \alpha \delta_t \frac{\partial q(s_t,a_t;w)}{\partial w}$

Q Learning

TD目标

  • 最优动作价值： $$ \begin{aligned} Q_\pi (s_t,a_t) &= E [R_t + \gamma Q_\pi (S_{t+1},A_{t+1})] \ Q^* (s_t,a_t) &= E [R_t + \gamma Q^* (S_{t+1},A_{t+1})] \ &= E [R_t + \gamma \max\limits_a Q^* (S_{t+1},a)] \end{aligned} $$
  • TD目标： 对「最优动作价值」进行蒙特卡洛近似，得 $y_t = r_t + \gamma \max\limits_a Q^* (s_{t+1},a)$

表格形式

形式：利用一个表格来记录 $Q^*(s,a)$，行为状态 $s$，列为动作 $a$。

  1. TD目标：$y_t = r_t + \gamma \max\limits_a Q^* (s_{t+1},a)$
  2. TD误差：$\delta_t = Q^*(s_t,a_t) - y_t$
  3. 更新 $Q_\pi$：$Q^(s_t,a_t) = Q^(s_t,a_t) - \alpha \delta_t$

神经网络形式

思路： 利用神经网络 $Q(s,a;w)$ 来近似动作价值函数 $Q^*(s,a)$。

算法：

  1. TD目标：$y_t = r_t + \gamma \max\limits_a Q (s_{t+1},a;w)$
  2. TD误差：$\delta_t = Q(s_t,a_t;w) - y_t$
  3. 损失函数：$L=\frac{1}{2} \delta_t^2$
  4. 更新系数：$w = w - \alpha \delta_t \frac{\partial q(s_t,a_t;w)}{\partial w}$

[!note|style:flat]

  • sarsa： 近似的是「价值函数 $Q_\pi(s,a)$」
  • Q Learning： 近似的是「最优价值函数 $Q^*(s,a)$」
  • 神经网络版的 Q Learning 就是 DQN 算法

multi-step TD

  • 思路： 之前的算法都是利用一次 $r$ 进行算法更新，还可以采用多次 $r$ 来更新算法。

  • multi-step TD 目标： 利用多次 $r$ 构造的TD目标

  • 回报展开： $$ \begin{aligned} U_t &= R_t + \gamma U_{t+1} \ &= R_t + \gamma R_{t+1} + \gamma^2 U_{t+2} \ &= R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \gamma^3 U_{t+3} \ &= \sum\limits_{i=0}^{m-1}\gamma^i R_{t+i} + \gamma^m U_{t+m} \end{aligned} $$

  • sarsa multi-step TD 目标: $$ y_t = \sum\limits_{i=0}^{m-1}\gamma^i r_{t+i} + \gamma^m Q_\pi(s_{t+m},a_{t+m}) $$

  • sarsa multi-step TD 目标: $$ y_t = \sum\limits_{i=0}^{m-1}\gamma^i r_{t+i} + \gamma^m \max\limits_a Q^*(s_{t+m},a) $$

License

Author: 海拉鲁的三角

Link: http://localhost:1313/artificial_intelligence/posts/reinforcementlearning/td_learning/

License: MIT

只要学不死，就往死里学