Deep Q-Learning 系列论文漫谈(三) 错综复杂的误差(上)-投影误差

误差来源

前一章我们比较概要的了解了作者所采取的两个措施：TargetNet和Experience Replay，并且从直观上解释了他们的作用，加上了一点我个人的理解。

在逐渐了解这两项措施的过程中，我们很自然的引出了和函数近似相关的一个问题，就是deadly triad，恰好DQN同时满足了这三个条件，因此，DQN表现出的不稳定和误差，与这三个条件有什么关系呢？这个问题也许很难回答，我们可以更加具体一些，DQN的误差来源有哪些？作者做的措施是怎样削弱这些误差的？

我个人将DQN的误差分为以下几类：

• 函数近似误差:由Function Approx引起的投影误差。
• 过拟合
• 采样分布漂移
• 采样误差
• Target moving
• 最大化偏差(Maximization Bias)

这是一个比较大的主题，将会分成上下两个章节，本章主要讨论和分析由函数近似引起的投影误差。

Linear Value Function Geometry

首先我们需要对Function Approximation带来的误差有个直观的了解，函数近似和自助法是“死亡三条件”中相对重要的两个，《RL book 2018》第11.4节，sutton用线性近似函数详细分析了函数近似带来的误差，我们可以跟随他的脚步简单建立一些概念。

投影算子(Projection operator)

乍一看很复杂，其实我们只需搞懂几个概念即可。为了简单起见，使用线性基函数做分析。我们假设状态空间${\cal S}=\{s_1,s_2,s_3\}$，也就是总共有三种状态。并且假设近似函数为线性基函数，参数为${\bf w}=(w_1,w_2)^{\top}$。

在策略$\pi$固定的情况下，真实的Value Function记为 $v_{\pi}:{\cal S} \rightarrow {\Bbb R}$

假设有2个特征基函数记为 $\phi_{0},\phi_{1}:{\cal S} \rightarrow {\Bbb R}$

那么可以将函数近似Value Function $v_w$ 写出来 : $v_w(s)=\sum{w_i*\phi_i(s)}$

然后在三维空间$\Bbb R^3$中用一个向量表示真实值函数: $v_\pi=[v_\pi(s_1),v_\pi(s_2),v_\pi(s_3)]$

同样的，我们也可以用一个向量表示近似值函数: $v_w=[v_w(s_1),v_w(s_2),v_w(s_3)]$

将这个三维空间记为$\cal V$，里面每一个点(向量)表示一个值函数。

然后我们再定义一个二维空间 $\Phi$，在这个空间中，我们的近似值函数又可以被定义为：$v_w=[w_1,w_2]$，它是也是这个二维空间中的一个点。这说明 $\Phi$ 是 $\cal V$ 的一个子空间。也就是如上面那张图中所示一样。

然后我们使用投影算子 $\Pi$ 将$\cal V$上的向量投影到子空间$\Phi$上:

$$\Pi v \stackrel{\text{def}}{=} v_w \ \ {\rm while} \ \ w=\arg\min_{w \in \Phi }||v-v_w||_{\mu}^2$$

这里的 $\mu_{\pi}$ 是在策略 $\pi$ 固定情况下，状态的概率密度函数。
定义距离：

$$d(v_1,v_2)=||v_1-v_2||_{\mu}^2=\sum_i^n(v_1(s_i)-v_2(s_i))^2 \cdot \mu_{\pi}(s_i)$$

它其实就是一个加权的欧式距离。在定义了这个距离之后，我们就能用投影算子 $\Pi$ 将空间 $\cal V$ 中任意一点给投影到平面 $\Phi$ 上。

投影算子也可以这样解释：在平面 $\Phi$ 上找到一个点 $\Pi v$，它与 $\cal V$ 中点 $v$ 的距离最近。

Bellman 算子(Bellman operator)

根据强化学习中关于值函数贝尔曼方程的定义:

$$\begin{aligned} v_\pi(s) \ \dot{=}& \ {\Bbb E}[G_t|S_t=s] \\ =&\ {\Bbb E}[R_{t+1}+\gamma G_{t+1}|S_t=s] \end{aligned}$$

我们可以直接写出Bellman算子$B_\pi$:

$$(B_\pi v)(s) \ \dot{=} \sum_a \pi(a|s) \sum_{s',r}{p(s',r|s,a)}[r+\gamma v(s')]$$

真实值函数 $v_\pi$ 是算子 $B_\pi$ 的唯一不动点(即 $B_\pi v_\pi=v_\pi$ 也就是值函数贝尔曼方程的定义)

那么可以定义近似值函数的贝尔曼误差(Bellman error):

$$\overline{\delta}_w=B_\pi v_w-v_w$$

特别要注意的是，TD误差 $\delta_w$ 和 Bellman误差 $\overline{\delta}_w$ 之间的关系。

TD误差为:

$$\delta_w(s,a,s')= r(s,a,s')+ \gamma v_w(s')-v_w(s)$$

Bellman误差为:

$$\overline{\delta}_w(s)= \Bbb E_{a\sim \pi ,s'\sim p(s'|s,a)}[\delta_w(s)]$$

可以看出，Bellman算子的作用就是将某个值函数$v$展开成时间差分的形式(TD)的期望，而且展开会存在Bellman误差，当且仅当$v=v_\pi$时，Bellman误差为0。

注：上面$r$和$r(s,a,s’)$是回报在不同已知变量下的不同形式，包括$r(s,a)$它们都来自于MDP模型函数$p(r,s’|a,s)$。见《RLbook2018》P49。

投影误差

Bellman算子给我们提供了一个思路，要想得到真实值函数，我们可以迭代地减小$v_w$的Bellman误差，直至为0。如果我们在表格型解决方案中使用这个思路，很正确，但是在函数近似问题中，却是行不通的。

下面来解释为什么行不通。

这张《RLbook2018》中的图可以解决我们这一章所有问题:

 

换个角度看，Bellman算子将一个点$v_w$转换为另一个点$v_w’=B_\pi v_w$，然后它们的差$(B_\pi v_w-v_w)$就是Bellman error vector(BE)。

图中我们初始近似值函数点$v_w$在$\Phi$平面上，第一次使用Bellman算子，产生的新的点$B_\pi v_w$“极有可能”离开$\Phi$平面，因为Bellman算子作用范围是整个值函数空间$\cal V$。

当$B_\pi v_w$不在$\Phi$上时，我们就不可能让Bellman error vector（BE）=0，因为$v_w$是不可能离开$\Phi$平面的。只能退而求其次，找到$B_\pi v_w$离$\Phi$最近的点，也就是使用投影算子将其投影到$\Phi$上，得到新的点 $\Pi B_\pi v_w$。如图中所示，新的点是在$\Phi$上的，我们可以使用梯度下降法更新参数$(w_1,w_2)$让$v_w$移动到$\Pi B_\pi v_w$。这个过程实际上是在最小化投影Bellman误差(projected Bellman error)PBE。

我们可以在图上看见，如果$v$可以离开$\Phi$平面，反复迭代使用Bellman算子，并每次都能使Bellman误差等于0，那么有理论可以保证最后一定收敛到不动点，即真实值函数$v_\pi$，也就是上面那一段连续的灰色箭头所指的路径。

$v_w$不能离开$\Phi$平面时，我们每次最小化的误差是PBE，就是让$v_w$移动到$B_\pi v_w$的投影点上。下一次迭代从$\Pi B_\pi v_w$出发，继续使用Bellman算子，然后再投影到$\Phi$上。下面的灰色箭头就是近似值函数$v_w$的迭代路径。和之前一样我们可以进一步定义均方PBE,使用状态的分布函数进行加权:

$${\rm \overline{PBE}}( {\bf w})=||\Pi \overline{\delta}_w||^2_\mu$$

每次迭代都让PBE为0向量，也就是让均方PBE=0，最终$v_w$也会收敛到一不动点$\rm w_{TD}$。

注：$\rm w_{TD}$是TD不动点，是最小化PBE得到的，并不是最小化TDE得到的。

真实值函数$v_\pi$也可以投影到$\Phi$上，得到$\Phi$平面上离真实值函数最近的点$\Pi v_\pi$。他们之间的误差叫做Value Error(VE)，这是理论上$v_w$能到达的离$v_\pi$最近的点，注意，是理论上，最小化PBE得到的$\rm w_{TD}$很有可能与它不相等。

$${\rm \overline{VE}}( {\bf w})=||\Pi v_\pi-v_\pi ||^2_\mu$$

总结

好了，到此为止，我们已经初步了解了函数近似所带来的误差，和投影算子密切相关，我可以统称为投影误差。为了下一章中的投影误差分析，我们这里做了很多铺垫，下一章主要会结合论文讨论其他误差。

最后强调两个概念:

1. 我们DQN每次迭代最小化的是PBE，如果能够收敛，最后会收敛到定点$\rm w_{TD}$，这个点很有可能不是$\Phi$上的最优点$\Pi v_\pi$。

2. $\Pi v_\pi$是指的$v_\pi$离平面$\Phi$最近一点。它和$v_\pi$之间存在误差VE，而且VE很有可能不为0，除非$v_\pi$刚好在平面上。

图上的其他内容大家可以自己详细阅读那一章节，这里就不赘述了。

可以参考的资料

[1] Stanford University:Value Function Geometry and Gradient TD

[2] A Tutorial on Linear Function Approximators for Dynamic Programming and Reinforcement Learning

 
 
 
 

由于没听老婆劝，执意回湖北后，恰好碰见新冠肺炎爆发，被封在省内。十几天没出门，人也发霉了。截止今日全国已经有一万七千多人被感染，疫情发展速度之快让我们都措手不及，一线的医务工作者和志愿者们你们辛苦了！相信一切都会好起来，我和老婆以前在武汉上大学，对这座城市感情很深，等到风平浪静，一定要再去樱花大道走一走。