时序差分

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 算法就得出
$$\begin{array}{rlr}& v_{t+1}(s)=v_t(s_t)-{\alpha }_t(s_t)[v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]],& s=s_t\\ & v_{t+1}(s)=v_t(s_t),& s\ne s_t\end{array}$$
其中$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 算法
$$\begin{array}{rlr}& q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-\alpha (s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})]],& (s,a)=(s_t,a_t)\\ & q_{t+1}(s,a)=q_t(s_t,a_t),& \forall (s,a)\ne (s_t,a_t)\end{array}$$
再结合 policy improvement，在每一步更新后都用$ϵ-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})$。
$$\begin{array}{rlr}& q_{t+n}(s_t,a_t)=q_t(s_t,a_t)-\alpha (s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^n{q}_t(s_{t+n},a_{t+n})]],& (s,a)=(s_t,a_t)\\ & q_{t+n}(s,a)=q_t(s_t,a_t),& \forall (s,a)\ne (s_t,a_t)\end{array}$$

4 Q-learning

$q(s,a)=E[R_{t+1}+\gamma \underset{a}{\max }q(S_{t+1},a)|S=s_t,A=a_t]$（BOE）
$$\begin{array}{rlr}& q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-\alpha (s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma \underset{a}{\max }{q}_t(s_{t+1},a)]],& (s,a)=(s_t,a_t)\\ & & \\ & q_{t+1}(s,a)=q_t(s_t,a_t),& \forall (s,a)\ne (s_t,a_t)\end{array}$$
同时策略更新时，使用$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，而是使用$ma{x}_{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 充分探索。

5 代码链接

(GitHub)[https://github.com/wizard-lhx/rl-lesson-code]