强化学习导论 | 第六章 时序差分方法

前面讲到的动态规划方法和蒙特卡洛方法都可以用来计算价值函数。动态规划方法是model-based的，需要知道状态的转换概率，某个状态的价值是根据其后续的状态价值计算的；蒙特卡洛方法是model-free的，不需要知道状态的转换概率，某个状态的价值是根据从该状态开始到轨迹结束的折扣奖励来计算的。本章的时序差分方法是对动态规划方法和蒙特卡洛方法的结合，跟蒙特卡洛方法一样，也是根据经验来学习，而不需要知道状态的转换概率，跟动态规划方法类似的，价值的更新不需要等到完成的轨迹走完，而是根据已获得的奖励和后续状态的估计奖励来计算。

时序差分法 Temporal-Difference Learning，简称TD
蒙特卡洛方法 Monte Carlo Methods, 简称MC

1. TD预测

TD和MC一样，都是从经验中学习，回想MC方法在计算状态价值时的迭代公式：
$V(S_t) = V(S_t) + \frac{1}{N(S_t)}(G_t - V(S_t))$V(St​)=V(St​)+N(St​)1​(Gt​−V(St​))

在MC方法中，$G_t$Gt​的计算公式为：
$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{T-1} R_{T}$Gt​=Rt+1​+γRt+2​+γ2Rt+3​+⋯+γT−1RT​

即在一个完成的轨迹结束之后，更新该轨迹中出现的所有状态的价值。

但在TD方法中，不再等到轨迹结束之后更新价值，而是走一步就可以更新。当前时刻$t$t的奖励$G_t$Gt​可以表示为：
$G_t = R_{t+1} + \gamma V(S_{t+1})$Gt​=Rt+1​+γV(St+1​)

上式表示，时刻$t$t的状态$S_t$St​得到的奖励等于做某个动作得到的即时奖励$R_{t+1}$Rt+1​以及下一个状态的估计价值乘以折扣因子的和。这里的$G_t$Gt​我们成为目标价值。

所以，TD中，价值更新式为：
$V(S_t) = V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$V(St​)=V(St​)+α[Rt+1​+γV(St+1​)−V(St​)]

其中的$\alpha$α表示每次从目标价值和估计价值的差距中学习多少来更新$V(S_t)$V(St​)。

这种方法称为TD(0)，也叫做one-step TD，即走一步就更新价值。

下面给出TD(0)的更新价值的代码描述：

上面的代码对于输入的策略$\pi$π进行评估，即得到各个状态的价值。算法具体步骤为：初始化价值$V(s)$V(s)和更新步长$\alpha$α。在一个episode中，初始化所在状态$S$S，根据策略选择一个动作$A$A，执行该动作，得到即使奖励$R$R和下一个状态$S'$S′，然后利用上面讲到的更新公式，更新状态$S$S的价值。接着对下一个状态$S'$S′执行相同的操作。直至达到终止状态，再进行下一个episode。

这里称TD方法是bootstrapping(利用后继状态的值函数估计当前值函数)的，像DP一样。

TD methods combine the sampling of MC with the bootstrapping of DP.

2. 例子：MC和TD的区别

假设我们有以下8个轨迹序列：
$A, 0, B, 0 \quad \quad \quad \quad B, 1 \\ B, 1 \quad \quad \quad \quad \quad \quad B, 1\\ B, 1 \quad \quad \quad \quad \quad \quad B, 1\\ B, 1\quad \quad \quad \quad \quad \quad B, 0$A,0,B,0B,1B,1B,1B,1B,1B,1B,0

我们分别利用MC和TD方法计算状态$A$A和状态$B$B的价值。设折扣因子$\gamma$γ =1。

MC方法：
包含状态$A$A的轨迹序列只有一个，所以$A$A的价值就是该轨迹的折扣奖励。
$V(A) = R_A + \gamma * R_B = 0 + 1*0 = 0$V(A)=RA​+γ∗RB​=0+1∗0=0

包含状态$B$B的轨迹序列有8个，且$B$B都是终止状态，所以$V(B)$V(B)应该是各个$R_B$RB​的平均值。
$V(B) = \frac{6*1 + 2 * 0}{8} = \frac{3}4{}$V(B)=86∗1+2∗0​=43​

TD方法：
对于状态$B$B，因为它没有后续状态，所以它的价值就等于各个即时奖励的平均值。
$V(B) = \frac{6*1 + 2 * 0}{8} = \frac{3}4{}$V(B)=86∗1+2∗0​=43​

但对于状态$A$A，它的后续状态为$B$B，所以价值计算为：
$V(A) = R_{A} + \gamma * V(B) = 0 + 1 * \frac{3}{4} = \frac{3}{4}$V(A)=RA​+γ∗V(B)=0+1∗43​=43​

从上面两个方法的计算过程，我们可以知道MC和TD的区别：

• MC是在一个轨迹序列结束之后才更新其中的状态价值；TD(0)是从某状态走一步就可以直接更新该状态的价值。所以TD(0)可以在没有最终结果的时候进行学习。
• TD是根据即时奖励和后续状态的估计价值作为目标价值的，所以这个估计是有偏的。而MC使用的是真实的奖励，是无偏估计。
• TD估计的方差一般要比MC小很多。因为TD的目标价值计算涉及到的中间状态少，变化幅度不大。而MC需要一条完整的轨迹序列，中间会经理众多随机态，方差较大。

3. Sarsa: On-policy TD 控制

On-policy控制是采样轨迹和我们要评估的策略是一样的。这里我们学习的不是状态价值函数，而是动作价值函数，即$Q(s, a)$Q(s,a)。更新该值的方法跟更新状态价值$V(s)$V(s)的方式一致：
$Q(S_t, A_t) = Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]$Q(St​,At​)=Q(St​,At​)+α[Rt+1​+γQ(St+1​,At+1​)−Q(St​,At​)]

每个转换对应的是一个五元组：$(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$(St​,At​,Rt+1​,St+1​,At+1​)，这也是sarsa名字的由来。

有了更新公式，我们就可以得到sarsa算法的伪代码描述。

可以看出，上面的代码描述与第一节中给出的更新状态价值函数的代码基本一致，只有将状态价值的更新变为了动作价值函数的更新。得到了每个状态下执行每个动作的价值，我们就可以很容易的确定策略了。

on-policy体现在采样的策略为$\epsilon$ϵ-greedy，更新价值函数的时候使用的策略也是$\epsilon$ϵ-greedy。

4. Q-learning: Off-policy TD 控制

off-policy控制是指我们使用两个策略，一个策略用来采样轨迹，称为“行为策略”，另一个策略用于更新价值函数，称为“目标策略”。

采样策略一般更具探索性，比如：$\epsilon$ϵ-greedy。目标策略一般采取贪心策略。

基于此，我们可以得到Q-learning算法中动作价值函数的更新公式：
$Q(S_t, A_t) = Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a)- Q(S_t, A_t)]$Q(St​,At​)=Q(St​,At​)+α[Rt+1​+γamax​Q(St+1​,a)−Q(St​,At​)]

公式中的目标价值表示为$R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a)$Rt+1​+γmaxa​Q(St+1​,a)，指即时奖励和下一个状态下所有动作价值中的最大价值的和。这里就说明更新价值函数时采用的是贪心策略。

由此，我们可以得到Q-learning的伪代码描述：

off-policy体现在：采样策略为$\epsilon$ϵ-greedy，更新价值函数时采样的贪心策略。

5. 总结

本章主要讲了TD(0)方法用于评估策略的思想，即使用即时奖励和后续状态的价值估计来评估当前状态的价值。在策略控制中，主要是估计动作价值函数，以此来确定最优策略。并且，根据on-policy和off-policy的区别，提出了两个对应的算法sarsa和q-learning。这两个算法思想一致，只有在更新动作价值函数时有不同。