CS5446 7. Temporal-difference learning

Notes for CS5446 Reinforcement Learning.

TD learning of state values

• TD 算法解决的问题：
  • 给定一个策略，然后估算这个策略的 state value。
  • 本质在没有 model 的情况下，依赖数据，incrementally 算这个策略的 bellman equation
• 不能做什么：
  • 计算 action value
  • 搜索 optimal policy

TD 算法需要 data/ experience 来学习。一个 experience 是一个 tuple 的集合：

它表示对于给定策略 $\pi$ ，生成的一系列数据（一个 episode）。TD 算法就是拿数据来估计 state value。

• $v_{t}(s_t)$ 表示在 t 时刻，对于状态空间中任意一个状态 s 我有一个状态值 v(s) 来估计最佳策略 $v_{\pi}(s)$ 的值。$s_t$ 表示在t时刻访问到的那个状态。
• 第一个式子表示，在 t 时刻时，在状态 s_t ，我有了一些采样数据，然后根据这些数据，和上述公式，我来更新这个状态对应的 state value，然后可以得到 t+1 时刻的新的 state value。
• TD target 就是 $v_t$ 希望被修改成的样子，给定了一个方向。
• TD error 就是我们的优化目标，TD error 为0时，代表我们估计的 state value 和 TD target 一致。

和贝尔曼方程的关系

上面我们给出了 TD learning 的公式，以及它的含义。接下来我们来看一下它和 bellman equation 的关系。

我们有贝尔曼期望方程：

如果针对这个期望方程，我们通过 RM 算法来进行求解，就可以得到 TD 算法。还记得 RM 算法吗？RM 算法是对于一个问题 $g(w) = 0$ 进行求解。

我们的目标是求解 $v_{\pi}(s)$ 因此 $g(w) = v_{\pi}(s) - \mathbb{E}[R + \gamma v_{\pi}(S') | S = s]$ 这里的 w 就是 $v(s)$ 。 解出来这个方程就可以解出来 v(s) 的值了。

根据 RM 算法，我们对 R 和 S 都有一系列采样 r 和 s, 代入 RM 算法我们有：

• 对红色的部分，即在策略 $\pi$ 下，我们要对从状态 s 得到 r 跳到 s’ 这个过程进行反复采样
  • 而对于我们上面给出的 TD 算法，则是对一个 trajectory 进行采样
  • 对此，我们的做法是，我们仍然只对一个 trajectory 进行采样，对于已经采样到的 tuple 我们进行 state value 的更新，没有采样到的不更新（就是上面的式子 2）
• 对于蓝色的部分，这个式子要求我们需要知道 $s'_k$ 的真实状态值 $v_{\pi}(s'_k)$ .
  • 对此我们的处理是直接把它替换成对它的估计值 $v_k(s'_k)$

和 MC 的关系

TD learning of action-values: SARSA

SARSA 是以 TD learning 为基础的，因此它也是需要 data/ experience 来学习的。一个 experience 是一个 tuple 的集合：

它表示对于给定策略 $\pi$ ，生成的一系列数据（一个 episode）。SARSA 算法就是拿数据来估计 action value。

• $s_t$ 表示在t时刻访问到的那个状态
• $a_t$ 表示在t时刻访问到的那个 action。
• $q_{t}(s_t, a_t)$ 表示在 t 时刻，对于状态 s_t 和 action a_t 我有一个 action value q(s,a) 来估计最佳策略 $q_{\pi}(s,a)$ 的值。
• 第二个式子表示，对于其他的状态和 action，我们不进行更新。
• SARSA 的名字来源是 experience 的数据tuple的首字母。

这样有了 TD learning 来解决 policy evaluation 的问题，和 SARSA 来解决 policy improvement 的问题，我们就可以得到一个完整的 SARSA 算法:

1. 初始化：初始化 q(s,a) 的值 (通常是 0)，和状态 s 、动作 a
2. 执行策略 $\pi$ : 在环境中执行动作a, 然后我们可以采样到 reward r 和 下一个状态 s'
3. 策略评估：根据当前策略我们会有一个动作 a’， 执行 a’ 后 我们可以对 q(s,a) 进行更新
4. 策略改进：根据新的 q(s,a) 值，我们更新策略 $\pi$ 。注意这里我们使用 $\epsilon$ -greedy 策略来选择动作 a’。
5. 重复 2-4 步骤，直到收敛

example

一个典型的利用SARSA来解决 grid world 问题的例子是：从某个状态出发，找到一条路径到达目标状态。 这个问题和之前的问题不一样的点在于，之前的问题通常是让你找最优的策略。

这一点很重要，你需要非常注意问题是找一个路径，还是找一个最优的策略。

$n$ -step SARSA 与 MC

我们提到了 SARSA 和 MC 的关系，即 SARSA 是 incremental 版本的 MC。它和 MC 最核心的区别是，MC 需要等一个 episode 结束才能更新。而 SARSA 可以每一步都进行更新。

那如果我们在一个 trajectory 中，等 n 步再进行更新，会怎么样呢？这就是 $n$ -step SARSA 的思路。

n 越大 variance 越大，bias 越小。 n 越小 variance 越小，bias 越大。初始结果影响越大。

Q-learning

Q-learning 是通过迭代的方式用来求解 optimal action-value 的。

它和 SARSA 的公式很像，但是它不依赖于策略 $\pi$ ，而是直接选择最大的 action value。它在数学上求解的是一个贝尔曼最优方程。

properties

Q-learning 是一个 off-policy 的算法。那么如何判断一个算法是否支持 off-policy 呢？

1. 确认这个算法在解决一个什么样的数学问题
2. 确认这个算法需要的输入参数

比如对于 SARSA 它要求我们对 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$ 其中 $a_{t+1}$ 是根据策略 $\pi$ 选择的。它的 target policy 和 behavior policy 是同一个。因此它是一个 on-policy 的算法.

比如对于 MC，它需要一个完整的 trajectory 才能进行更新。同样对于 q value 的更新我们也是根据某个策略进行的，因此它也是一个 on-policy 的算法。

但是对于 Q-learning，我们不需要知道策略 $\pi$ ，因为求解bellman optimal equation 时是不涉及任何具体策略的。对于数据的观测，Q-learning 需要 $(s_t, a_t, r_{t+1}, s_{t+1})$ 。因此它是一个 off-policy 的算法。

pseudo code

对于 on policy 版本，和 SARSA 很类似：

1. 初始化：初始化 q(s,a) 的值 (通常是 0)，和状态 s 、动作 a
2. 执行策略 $\pi$ : 在环境中执行动作a, 然后我们可以采样到 reward r 和 下一个状态 s'
3. 策略评估：无需选择下一个动作， 根据 $max(q(s',a))$ 来更新 action value
4. 策略改进：根据新的 q(s,a) 值，我们更新策略 $\pi$ 。注意这里我们使用 $\epsilon$ -greedy 策略来选择动作 a’。
5. 重复 2-4 步骤，直到收敛

对于 off policy 版本，和 Q-learning 很类似：

1. 初始化：初始化 q(s,a) 的值 (通常是 0)，和状态 s 、动作 a
2. 执行策略 $\pi_b$ : 在环境中执行动作a, 然后我们可以采样到 reward r 和 下一个状态 s'
3. 策略评估：无需选择下一个动作， 根据 $max(q(s',a))$ 来更新 action value
4. 目标策略改进：根据新的 q(s,a) 值，我们使用 greedy 更新策略 $\pi_t$ 。对于目标策略，我们不需要探索。
5. 重复 2-4 步骤，直到收敛

TD 算法的统一视角

本节中介绍的算法都可以用一个公式概括:

其中 $\bar{q}_t$ 表示 TD Target, 根据取值的不同有如下变种:

同理, 他们所解决的数学问题也可以统一表达: