博文

【RL系列】Monte Carlo与TD算法的结合，n-step TD算法

已有 6653 次阅读 2018-8-11 11:02 |系统分类:科研笔记

强化学习中的Model-free问题主要的解决思路来源于统计方法。所谓统计方法又可分为Monte Carlo与TD算法。当学习任务可转化为episode task形式时，Monte Carlo与TD算法在实现上的不同主要体现在如何更新状态动作值函数。n-step TD算法则是由两种不同的值函数更新形式相结合所产生的，所以想要理解n-step TD算法，对Monte Carlo与TD进行透彻地的解析是十分有必要的。

Backup Diagram的区别

Monte Carlo方法：每个执行一个episode task，更新episode开始时的状态值函数。假设一个episode开始时的状态为$Start$，结束时的状态为$End$。如果将一个episode经过的状态写为状态集合$ State $，则每个episode可更新的状态值函数集合可以写为$V(State)$，用于更新状态值函数的$ \mathrm{Return} = R(End) $。所以对Monte Carlo来说，一个episode中状态集合的值函数更新更像是对多个状态独立地更新，在强化学习中，可以称其为non-bootstrap，这也应证了Monte Carlo方法最为重要的性质：每一个状态的估计都是独立的，不依赖于其它状态的! 所以为了尽可能保证每个状态都可以被更新到，才有了Exploring Start策略（什么是Exploring Start？可以阅读【RL系列】从蒙特卡罗方法正式引入强化学习）下面将通过Backup Diagram将MC方法的更新形式更加清晰的表现出来：

Monte Carlo

TD方法：在任意一个episode task执行过程中所遇到的每个状态都会被更新，且每个状态的更新都依赖于下一个状态的值函数与到达下一个状态所获得的奖励。因为是边执行episode边更新值函数，这种方法又被称为on-line learning。实际上，类似MC方法将执行好的episode的轨迹(trajectory)保存在下来，再依照TD方法更新也可以达到与on-line learning相同的效果，但很明显，这个方法是off-line learning，也就是说线下与线上学习并不是区分Monte Carlo与TD算法的依据。TD算法的值函数更新可用下图表示出来：

由上述示意图可以发现，TD方法的最后一步，也就是对状态$S_n$的值函数更新与Monte Carlo方法并无任何区别。对状态$ S_n $的更新依赖于$ R(End) $与$ V(End) $，但由于终止状态实际上不参与值函数更新过程，所以一般情况下都设$ V(End) = 0 $，这样一来，这最后一步就与Monte Carlo方法一致了。

定步长与不定步长，TD方法

定步长与不定步长的更新方法在Bandit问题里就曾讨论过，定步长实际上为Recency-Weighted Average，不定步长则是Incremental形式。通常来说，Monte Carlo Prediction采用的是不定步长的值函数更新，TD方法则采用的是定步长形式，但也不是固定的，可以互换使用。理论上来说，定步长与不定步长的通用形式可以写为：

$$ V_{n + 1}(S) = V_{n}(S) + \alpha(X - V_{n}(S)) $$

在这个式子中，$\alpha$通常小于1，若是常数不变则为定步长，若$ \alpha $是变量则为不定步长。不论定步长与不定步长，该式皆可表示为对随机变量$X$的均值估计，且该估计为无偏估计，也就是说当迭代次数无穷大时，这个估计的均值与期望$E[X]$是相同的。但是，$\alpha$越大估计值的方差就越大（特别注意，这是发生在当迭代次数较大进入收敛状态时），同时也存在着，$ \alpha $越小收敛速度越慢的情况，所以对于$ \alpha $的处理总是需要平衡收敛速度与均值方差。

Incremental Implementation作为不定步长的一种形式，可以说是比较好的平衡了收敛速度与均值方差之间的矛盾。对于Incremental形式来说，开始需要收敛速度时，$\alpha$很大，进入收敛状态后需要精确度时，$\alpha$又变的很小。但有时为了突出优化收敛速度，就必须要牺牲一定的精确度，最简单的方法就是提高$\alpha$的值，但需要估计的随机变量$X$的方差大小给这种方法带来了不确定性。若是$X$的方差$D[X]$较大，则估计均值的方差$D[V(S)]$会对$\alpha$值的增大非常敏感，这样一来不但收敛速度未得到很大改善反而精确度下降得厉害。（举例：均匀分布与0-1分布）

为了解决这个问题，我们可以人为的构造出与原有需要估计的随机变量$X$期望相同的新的随机变量$Y$，且希望随机变量$Y$的方差可以有所减小。在MC方法中，随机变量$X$就是终态的Reward（除终态外各状态Reward为0），而人为构造出的随机变量$Y$在TD中被描述为：

$$ Y = Rew(S') + V(S') $$

为什么MC方法中的随机变量$X$与TD方法中的随机变量$Y$的均值估计是等价的？我们使用一个简单例子来稍作计算（这里只考虑除终态Reward外其它Reward值为0的这种奖励设计，这样比较简单）。下图为一个以状态$S_1$为起点的马尔可夫决策模型，每一条之路可以表示为一个episode。

例子一：

假设共执行了N个episode，其中到达终态的episode个数分别为N1~N7。估计状态$S_1$的均值，先用Monte Carlo方法可以得出$V(S_1)$为：
$$ V(S_1) = \frac{\sum_{i}^{6} N_i R_i}{\sum_{i}^{6} N_i} $$

如果使用TD方法，对状态$S_1$的估计可以写为如下形式。假设episode经过状态$S_2$的次数为$K_1$，经过状态$S_3$的次数为$K_2$，其中$ K_1 = N_1 + N_2 + N_3 $与$K_2 = N_4 + N_5 + N_6$始终成立。

$$ V(S_1) = \frac{K_1 V(S_2) + K_2 V(S_3)}{K_1 + K_2} = \frac{\sum_{i}^{6} N_i R_i}{\sum_{i}^{6} N_i} $$

至于观察方差的变化，我们首先将通用的值函数更新方程做一个简单的化简：

$$ V_{n + 1}(S) = V_{n}(S) + \alpha(X - V_{n}(S)) = (1 - \alpha)V_{n}(S) + \alpha X $$

值函数$V(S)$的不确定性全部来源于后一项$ \alpha X $。首先看$\alpha$对估计值方差的影响，有公式$Var(cX + b) = c^2 Var(X)$所以当$\alpha$扩大$c$倍时，方差会变为原先的$c^2$倍。让我们再举个例子，看一看随机变量$X$本身对估计值方差的影响。

例子二：

如上图所示，终态只有End1与End2，让我们假设episode到达End1所获得的Reward为1，到达End2所获得的Reward为0。如按照MC方法更新，则值函数通用更新方程中的随机变量$X$即为终态时所获得的Reward，该随机变量$X$定然服从伯努利分布（0-1分布）。假设每一类episode发生的概率皆为1/6(共有6条支路，6类episode)，则随机变量$X$的概率分布可以写为：

$$ P(X = 1) = 0.5\\ P(X = 0) = 0.5 $$

依据方差计算公式，随机变量$X$的方差为：

$$ Var(X) = E[X^2] - (E[X])^2 = 0.25 $$

如果我们按照TD方法更新，则可先计算出$V(S_2) = \frac{1}{3}$，$V(S_3) = \frac{2}{3}$，则TD方法所构造的随机变量$Y$的概率分布可以写为如下形式，并依据方差公式计算$Var(Y)$：

$$ P(Y = \frac{1}{3}) = 0.5\\ P(Y = \frac{2}{3}) = 0.5 \\ Var(Y) = E[Y^2] - (E[Y])^2 = 0.0278$$

TD方法的估计均值误差是MC方法的1/10，这也就是TD方法通常可以在保持与MC方法相同的估计均值误差的前提下会以更快的速度收敛的原因（Random Walk问题就很好的应证了这一点，可以参考Sutton书的Figure 6.2与Figure 6.3）。但实际上这也并非是绝对的，MC方法的表现非常仰赖Reward设计与实际的环境，当终态数量很多时，Reward值之间比较接近时，MC方法的估计均值误差也不一定差。

n-step TD

对于上述的例子二，可将其episode前进的过程分为三个阶段或三层（如下图所示），所构造的待估计随机变量$Y = \{V(S_2), V(S_3) \}$，可以视为估计第一层而依赖于第二层的估计，这就是1-step TD。若构造的待估计随机变量为第三层估计的值函数，即$ Y = \{ V(S_4), V(S_5), V(S_6), V(S_7) \} $，也就是对第一层的估计依赖于第三层，而跳过了第二层（第二层的估计直接依赖于终态的Reward），这就是2-step TD。可以证明2-step TD的估计均值与1-step TD和MC方法完全一致，但均值估计误差却各不相同。