强化学习（二）SARSA和Q-learning

综述

在使用时序差分方法求强化学习的控制问题时，我们得到了下式：

$$q_{\pi}(s,a)=q_{\pi}(s,a)+\alpha(R(s,a)+\gamma q_{\pi}(s',a')-q_{\pi}(s,a))$$

同时我们得到一个$\epsilon$策略：

$$\pi(a|s)=\begin{cases} 1-\epsilon+\frac{\epsilon}{m},a=arg\max_a q(s,a)\\ \frac{\epsilon}{m},else \end{cases}$$

SARAR和Q-learning两种强化学习方法都是基于这个式子和这个策略的，但是这两个算法在状态$s’$采用动作$a’$时所使用的策略不同。

SARAR

SARSA是一种在线的学习方法。什么是在线学习呢，就是一边选择策略一边学习，对于假想的动作是真正执行了的。SARAR的学习过程是这样的：
(1) 已知一个状态$s$和动作$a$，得到一个状态$s’$
(2) 使用$\epsilon$策略分布采样一个动作$a’$
(3) 利用$q_{\pi}(s’,a’)$更新$q_{\pi}(s,a)$
(4) $s \leftarrow s’$，$a\leftarrow a’$
在对弈游戏中，SARAR可以看作是代理使用$\epsilon$策略而无法控制对方的策略。

Q-learning

Q-learning是一种离线的学习方法。什么是离线学习呢，就是学习与策略选择是分开的，更新策略时假想的动作不一定真正执行，而是到了新状态重新选择一个动作。离线学习的方法可以对历史数据重复学习，不只学习自己的策略，也学习别人的策略。Q-learning的学习过程是这样的：
(1) 已知一个状态$s$
(2) 从$\epsilon$策略中采样一个动作$a$
(3) 从$s$和$a$，得到$s’$
(4) 从另一个策略采样$a’$，这个策略可以是$\epsilon$策略也可以是最大策略也可以是其他策略，Q-learning一般是最大策略
(5) 利用$q_{\pi}(s’,a’)$更新$q_{\pi}(s,a)$
(6) $s\leftarrow s’$
在对弈游戏中，Q-learning可以看作是代理使用$\epsilon$策略，同时模拟对手使用另一个策略。

其他

上述两种方法都是单步更新参数的，即不需要蒙特卡洛采样出一条路径，只需要蒙特卡洛采样出下一个状态即可更新参数。还有一种路径更新参数的方法，就是蒙特卡洛采样出一条路径，然后利用这条路径去更新参数。我们都知道：

$$q_{\pi}(s,a)=q_{\pi}(s,a)+\alpha(R(s,a)+\gamma q_{\pi}(s',a')-q_{\pi}(s,a))=q_{\pi}(s,a)+\alpha(U(s,a)-q_{\pi}(s,a))$$

其中$U(s,a)$是状态$s$采取动作$a$时的期望收益，在单步更新中我们使用$R(s,a)+\gamma q_{\pi}(s’,a’)$去近似。这里的$U(s,a)$还可以是通过采样多条完整的路径计算平均收益去近似，然后利用随机梯度的思想，每次只采样一条路径去近似，得到：

$$q_{\pi}(s_t,a_t)=q_{\pi}(s_t,a_t)+\alpha(R_t(\tau)-q_{\pi}(s_t,a_t))$$

其中$\tau$表示采样的路径，$R_t(\tau)$表示将$t$时刻看作是开始时刻的收益。