强化学习——时序差分方法（七）

时序差分

1 时序差分计算 state value（Temporal difference learning）

$v_t(s_t) = E[R_{t+1}+\gamma v_t(S_{t+1})|S_t = s_t]$（BE），根据 RM 算法就得出

其中$r_{t+1},s_{t+1}$是$R_{t+1},S_{t+1}$的抽样值，$v_t(s_t)$是 state value 当前估计值，$[r_{t+1} + \gamma v_t(s_{t+1})]$作为state value 的一个采样，称为 TD target，而预估值与实际值的差$v_t(s_t) - [r_{t+1} + \gamma v_t(s_{t+1})]$称为 TD error。
而这个算法由于需要两个不同时刻的采样${s_t,r_{t+1},s_{t+1}}$所以称为时序差分。

2 on-line 和 off-line 更新

对比 MC 的方法，TD 算法只需要在每次获得${s_t,r_{t+1},s_{t+1}}$就可以进行值更新称为在线（on line）的方式。而 MC 算法需要完成一个完整的 episode 才进行 action value 的更新，称为离线（off line）更新。off-line 的好处是可以处理不间断的任务，同时提高计算效率。

3 时序差分更新 action value

3.1 Sarsa algorithm

该算法需要${s_t,a_t,r_{t+1},s_{t+1},a_{t+1}}$采样，所以算法名字就是这几个采样的缩写。
$q(s,a) = E[R_{t+1} + \gamma q(S_{t+1},A_{t+1})| S=s_t,A = a_t]$（BE）
根据 RM 算法

再结合 policy improvement，在每一步更新后都用$\epsilon-greedy$更新当前状态策略。

3.2 n-step Sarsa algorithm

在 Sarsa 基础上由于$q(s,a) = E[R_{t+1} + \gamma q(S_{t+1},A_{t+1})| S=s_t,A = a_t] = E[R_{t+1} + \gamma R_{t+2}+ \cdots +\gamma^n q(S_{t+n},A_{t+n})| S=s_t,A = a_t]$。TD target 换成$r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^n q_t(s_{t+n},a_{t+n})$。

4 Q-learning

$q(s,a) = E[R_{t+1} + \gamma \displaystyle \max_a q(S_{t+1},a)| S=s_t,A = a_t]$（BOE）

同时策略更新时，使用$greedy$策略进行更新。

4.1 on-policy 和 off-policy

Q-learning 相比 Sarsa 除了数学上求解的方程从 BE 变成 BOE，重要的是，它可以以 off-policy 方式进行更新策略。
policy 分为两类，一类是用来生成数据的（behavior policy），一类是需要更新的策略（target policy）。
Sarsa 类的算法在更新 action value 时使用的生成数据的策略和进行 policy improvement 时使用的是一个策略，所以它是 on-policy 的。
而 Q-learning 可以使用两个不同的策略，生成数据时使用$\pi_b$，更新策略时使用的另一个$\pi_T$。之所以可以这样做，是因为它更新 action value 时，完全不依赖于 behavior policy，而是使用$max_a q(S_{t+1},a)$来直接选出最优值。Sarsa 在更新策略时依赖于 behavior policy，因为更新的策略又依赖于更新的 action value，$q(S_{t+1},A_{t+1})$是需要 behavior policy 获得$A_{t+1}$的。
off-policy 的好处可以使用一个探索性强的策略作为 behavior policy 充分探索。