强化学习之时序差分法

首页摘要：

时序差分法和蒙特卡洛法都是不用基于模型的方法，但是蒙特卡洛需要完整的序列才能使用，而时序差分法正是用来克服这个不足的。时序差分法的在线（on-policy）版是SARSA算法、离线（off-policy）版是Q-learning算法，不同的策略改进方式产生了这个差别。

时间差分法

从蒙特卡洛法我们知道，动作价值函数通过采样再取平均来更新：

$$G_{t}=r_{t+1}+\gamma r_{t+2}+ \gamma^{2}r_{t+3}+...+\gamma^{T-1}r_{t+T}\\ N(S_{t})=N(S_{t})+1\\ \begin{equation} \begin{split} v(S_{t})&=v(S_{t})+\frac{1}{N(S_{t})}(G_{t}-V(S_{t}))\\ &=v(S_{t})+\alpha (G_{t}-v(S_{t})) \end{split} \end{equation}\\ q(S_{t},A_{t})=q(S_{t},A_{t})+\alpha (G_{t}-q(S_{t},A_{t}))$$

根据回报的表达式可知：

$$G_{t}=r_{t}+\gamma v(S_{t+1})$$

所以蒙特卡洛计算状态价值以及动作价值函数的公式可以改写成：

$$G_{t}=r_{t+1}+\gamma v(S_{t+1})\\ v(S_{t})=v(S_{t})+\alpha (r_{t}+\gamma v(S_{t+1})-v(S_{t}))\\ q(S_{t},A_{t})=q(S_{t},A_{t})+\alpha (r_{t}+\gamma q(S_{t+1},A_{t+1})-q(S_{t},A_{t}))$$

其中的 $\alpha$ 是设置的迭代超参数，因为时序差分法是在持续进行环境中学习，不会等到运行结束再采样完整的序列，最后一个公式之所以可以把$G_{t}=r_{t}+\gamma v(S_{t+1})$改写成$G_{t}=r_{t}+\gamma q(S_{t+1},A_{t+1})$，是因为动作价值函数是确定动作之后的价值函数，而价值函数是多个可能动作下的动作价值函数的期望。

前面所述回报是用向前一步来代替，但是也可以用 $n$ 步来代替：

$$G_{t}=r_{t+1}+\gamma r_{t+1}+\gamma ^{2} r_{t+2}+...+\gamma ^{n-1} r_{t+n}+\gamma ^{n} v(S_{t+n})$$

当 $n$ 趋于无穷时，时序差分法相当于蒙特卡洛法。因此确定这个步数是一个需要考虑的问题，但是为了从理解原理起见，这里只介绍一步前向回报。

在蒙特卡洛法中，我们用了在线（on-policy）策略来进行强化学习。对于时序差分法来说，在线版本是SARSA算法，离线版本是Q-learning。在线是指选择动作和更新动作值函数都是基于同一个$\epsilon -greedy$ 贪婪策略，而离线是指选择动作采用$\epsilon -greedy$贪婪策略，更新动作值函数使用$max$贪婪策略。算法具体细节见以下两节。

SARSA

SARSA算法迭代时，基于$\epsilon -greedy$ 贪婪策略在状态 $s$ 时选择动作 $a$ ，获得实时回报 $r$ 并转到状态 $s’$，进一步根据$\epsilon -greedy$ 贪婪策略采取动作 $a’$ ，这个时候就可以更新动作值函数：

$$\begin{equation} \begin{split} q(s,a)&=q(s,a)+\alpha (G_{t}-q(s,a))\\ &=q(s,a)+\alpha (r+\gamma q(s',a')-q(s,a)) \end{split} \end{equation}$$

具体算法流程如下：

输入:迭代轮数 $T$、状态集 $S$ 、动作集 $A$ 、即时回报 $r$ 、衰减因子 $\gamma$ 、探索率 $\epsilon$ ；

输出:所有的状态和动作对应的价值 $q$ ；

1.随机初始化所有的状态和动作对应的价值 $q$ ；

2.for $i$ to $T$ ，进行迭代

（1）初始化 $s$ 为当前状态序列的第一个状态。设置 $a$ 为$\epsilon -greedy$ 贪婪策略在状态 $s$ 下选择的动作

（2）在状态 $s$ 下执行动作 $a$ ，转到状态 $s’$ 并获得回报 $r$

（3）利用$\epsilon -greedy$ 贪婪策略在状态 $s’$ 下得到选择的动作 $a’$

（4）更新动作价值函数：

$$q(s,a)=q(s,a)+\alpha (r+\gamma q(s',a')-q(s,a))$$

（5）$s=s’,a=a’$

（6）如果 $s$ 是终止状态，当前轮迭代完毕，否则转到步骤(2)

这里有一个要注意的是，步长 $\alpha$ 一般需要随着迭代的进行逐渐变小，这样才能保证动作价值函数可以收敛。当动作价值函数收敛时，我们的 $\epsilon -greedy$ 贪婪策略也就收敛了。

Q-learning.

Q-learning算法迭代时，基于$\epsilon -greedy$贪婪策略在状态 $s$ 时选择动作 $a$ ，获得实时回报 $r$ 并转到状态 $s’$，和SARSA算法不同的是进一步根据$max$贪婪策略采取动作 $ a’$ ，这个时候就可以更新动作值函数：

$$\begin{equation} \begin{split} q(s,a)&=q(s,a)+\alpha (G_{t}-q(s,a))\\ &=q(s,a)+\alpha (r+\gamma q(s',a')-q(s,a)) \end{split} \end{equation}$$

具体算法流程如下：

输入:迭代轮数 $T$、状态集 $S$ 、动作集 $A$ 、即时回报 $r$ 、衰减因子 $\gamma$ 、探索率 $\epsilon$ ；

输出:所有的状态和动作对应的价值 $q$ ；

1.随机初始化所有的状态和动作对应的价值 $q$ ；

2.for $i$ to $T$ ，进行迭代

（1）初始化 $s$ 为当前状态序列的第一个状态。对于终止状态其 $q$ 值初始化为0。设置 $a$ 为$\epsilon -greedy$ 贪婪策略在状态 $s$ 下选择的动作

（2）在状态 $s$ 下根据 $\epsilon -greedy$ 贪婪策略执行动作 $a$ ，转到状态 $s’$ 并获得回报 $r$

（3）利用$max$贪婪策略在状态 $s’$ 下得到选择的动作 $a’$

（4）更新动作价值函数：

$$q(s,a)=q(s,a)+\alpha (r+\gamma q(s',a')-q(s,a))$$

（5）$s=s’$

（6）如果 $s$ 是终止状态，当前轮迭代完毕，否则转到步骤(2)

这里有一个要注意的是，步长 $\alpha$ 一般需要随着迭代的进行逐渐变小，这样才能保证动作价值函数可以收敛。当动作价值函数收敛时，我们的 $\epsilon -greedy$ 贪婪策略也就收敛了。

结语

在实际应用中两种方法各有优劣，具体来说，存在以下几个区别：

1. Q-learning在更新动作价值时采用的是贪婪策略，而SARSA采用的是 $\epsilon -greedy$ 贪婪策略，导致前者收敛速度更快，但是这也导致前者更加激进，容易掉入“最优陷阱”（实际上或许最优性还不如后者）；
2. 一个就是Q-Learning直接学习最优策略，但是最优策略会依赖于训练中产生的一系列数据，所以受样本数据的影响较大，因此受到训练数据方差的影响很大，甚至会影响Q函数的收敛。Q-learning的深度强化学习版Deep Q-Learning也有这个问题。

因此，在模拟环境中一般使用Q-learning（试错机会多），实际生产环境用SARSA（保守操作更好）。但是这两种方法只适合状态和动作都比较少的环境，因为如果状态和动作很多的话，会导致Q值表非常大以至于内存不足，此外还容易造成维数灾。针对这个问题，近几年兴起的深度学习在一定程度上解决了这个问题，在未来的学习中，我将结合深度学习来进行介绍。