6.1-启发示例:期望值估计

期望值估计问题已经在上一章讨论过一次。下面我们从另一个角度再次研究这个问题，并且介绍如何用“增量式”的方法解决这个问题。

Note

第一种非递增法是先收集所有样本，然后计算平均值。这种方法的缺点是，如果数据很多，我们可能需要等待很长时间才能收集到所有样本。第二种方法可可以克服这种问题，得到一次采样就更新一次，估计就会慢慢的变得准确。

考虑一个随机变量\(X\),它取值于有限集\(\mathcal{X}\)。我们的目标是估计期望值\(\mathbb{E}[X]\)。假设有一个独立同分布的样本序列\({x_i}_{i=1}^n\)。那么\(X\)的期望值可以通过这些样本的平均值来近似：

\[\mathbb{E}[X]\approx\bar{x}\doteq\frac{1}{n}\sum_{i=1}^nx_i.\tag{6.1}\]

\((6.1)\)就是是蒙特卡洛估计的基本思想，根据大数定律，当\(n\to\infty\)，\(\bar{x}\to\mathbb{E}[X]\)。

有两种方法可以用来计算\((6.1)\)中的\(\bar{x}\)。第一种非增量式 (non-incremental)是先收集所有样本，然后计算平均值。这种方法的缺点是，如果样本数量较多，我们可能需要等待很长时间才能收集到所有样本。第二种是增量式的 (incremental)。具体来说，令

\[w_{k+1}=\frac{1}{k}\sum_{i=1}^{k}x_{i},\quad k=1,2,\ldots\]

类似地

\[w_k=\frac{1}{k-1}\sum_{i=1}^{k-1}x_i,\quad k=2,3,\ldots\]

实际上，\(w_{k+1}\)可以用\(w_k\)表示为

\[w_{k+1}=\frac{1}{k}\sum_{i=1}^{k}x_{i}=\frac{1}{k}\left(\sum_{i=1}^{k-1}x_{i}+x_{k}\right)=\frac{1}{k}((k-1)w_{k}+x_{k})=w_{k}-\frac{1}{k}(w_{k}-x_{k}).\]

因此，我们得到了如下增量式算法：

\[w_{k+1}=w_{k}-\frac{1}{k}(w_{k}-x_{k}).\tag{6.2}\]

该算法可以以增量的方式计算均值\(\bar{x}\)

为了验证该算法，我们可以计算出\(k=1,2,\ldots\)次迭代的结果：

\[\begin{aligned}w_1&=x_1,\\w_2&=w_1-\frac{1}{1}(w_1-x_1)=x_1,\\w_3&=w_2-\frac{1}{2}(w_2-x_2)=x_1-\frac{1}{2}(x_1-x_2)=\frac{1}{2}(x_1+x_2),\\w_4&=w_3-\frac{1}{3}(w_3-x_3)=\frac{1}{3}(x_1+x_2+x_3),\\&\vdots\\w_{k+1}&=\frac{1}{k}\sum_{i=1}^kx_i.\end{aligned}\tag{6.3}\]

可以看出，由这个增量式算法得到的\(w_{k+1}\)确实是\(\{x_i\}_{i=1}^k\)的平均值。这里\(w_1=x_1\)是初始值。

算法\((6.2)\)的优势在于，每次接收到一个样本时，就能立即计算出平均值，进而近似计算\(\mathbb{E}[X]\)。值得注意的是，由于样本不足，近似值在开始时可能并不准确，随着样本数量的增加，估计准确率会逐步提高。此外，还可以定义\(w_{k+1}=\frac{1}{1+k} \sum_{i=1}^{k+1} x_i\)和\(w_k=\frac{1}{k} \sum_{i=1}^k x_i\)。在这种情况下，相应的迭代算法为\(w_{k+1}=w_{k}-\frac{1}{1+k}(w_{k}-x_{k+1}).\)。

最后，我们可以把\((6.2)\)推广到一个更一般化的算法：

\[w_{k+1}=w_k-\alpha_k(w_k-x_k).\tag{6.4}\]

除了系数\(1/k\)被\(\alpha_k>0\)取代之外，它与\((6.2)\)相同。由于没有给出\(\alpha_k\)的表达式，我们无法得到如\((6.3)\)所示的\(w_k\)的显式表达式。不过我们将在下一节证明，如果\({\alpha_k}\)满足一些温和条件 (mild conditions)的话，当\(k\to\infty\)时，\(w_k \rightarrow \mathbb{E}[X]\)。在第\(7\)章中，我们将看到时序差分算法与\((6.4)\)非常类似，这也是我们介绍该算法的主要原因。

Note

可以发现，我们在上章和本章中均利用期望值估计作为示例，这是因为强化学习中的许多量，都以期望值的方式定义，所以需要用数据去估计。

评论