跳转至

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

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

接下来，我们通过考察均值估计问题，来演示如何将一个非增量式(non-incremental)算法转换为增量式(incremental)算法。

Note

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

考虑一个取值于有限集合\(\mathcal{X}\)的随机变量\(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)\)中的近似是蒙特卡罗估计的基本思想，如第\(5\)章所介绍。我们知道，根据大数定律，当\(n\to\infty\)，\(\bar{x}\to\mathbb{E}[X]\)。

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

\[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}\)。可以验证

\[\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}\]

\((6.2)\)的优势在于，每次收到样本时，我们都能立即计算出平均值。这个平均值可以用来近似计算\(\bar{x}\)，进而近似计算\(\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}).\)。

此外，还可以考虑一种表达式更一般的算法：

\[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\)章中，我们将看到时序差分算法有类似(但更复杂)的表达式。

Note

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