2.4 增量法实现

到目前为止我们所讨论的动作价值方法，都是利用观察奖励的样本均值来估计动作价值，现在我们开始考虑如何基于高效计算的原则计算这些均值，也就是说利用确定的内存和单步运算速度来实现高效运算。

为了简化符号表示，我们考虑单一动作。此处我们使用R{i}表示该动作执行第i次时获得的奖励，使用Q{n}表示该动作被选择执行{n-1}次后的动作价值估计，记为：

  Q_n=\frac{R_1+R_2+\cdots+R_{n-1}}{n-1}.

根据上述公式，我们需要记录该动作的全部n次奖励值，并在需要价值估计值时利用该公式计算，然而，如果采取这种计算方式，那么随着时间的增长，观察到的奖励数将不断增加，从而将导致内存和计算的消耗不断增长，每一个新增加的奖励值都需要额外的内存存储，额外的加和计算消耗。

就像你可能疑惑的那样，该公式不必如此使用，我们很容易就可以从上述公式中分离出增量部分，计算增量部分可以在很小的计算消耗下更新价值。已知Q{n}和第n的奖励R{n}，可得新的增量式价值表达式：

\begin{align} Q{n+1}&=\frac{1}{n}\sum{i=1}^{n}R_{i}\

                     &=\frac{1}{n}\left(R_{n}+\sum_{i=1}^{n-1}R_{i}\right)\\

                   & =\frac{1}{n}\left(R_{n}+(n-1)\frac{1}{n-1}\sum_{i=1}^{n-1}R_{i}\right)\\

                    & =\frac{1}{n}\left(R_{n}+(n-1)Q_n\right)\\

                     &=\frac{1}{n}\left(R_{n}+nQ_n-Q_n\right)\\

                     &=Q_n+\frac{1}{n}\left[R_n-Q_n\right],  \hfill {(2.3)}

\end{align}

当n=1时，对于任意Q_1可得Q_2=R_1。在使用这种增量式计算方法时只需要存储Q_n和n，并且每次仅需很小的计算量。下文将提出完整的老虎机问题算法伪代码，该算法使用增量是样本均值计算方法和\varepsilon-贪婪动作选择策略，假设dandit（a）函数采取动作并返回对应的奖励。

一个简单的老虎机算法

初始化，for\ a=1\ to\ k:\ Q(a)\gets0\ N(a)\gets0\ 永久循环：\ A\gets\left{ \begin{aligned} &argmax_aQ(a) &概率为1-\varepsilon (随机打破连接) \ &一个随机动作 &概率为\varepsilon \end{aligned} \right.\ R\gets bandit(A)\ N(A)\gets N(A)+1\ Q(A)\gets Q(A)+\frac{1}{N(A)}[R-Q(A)]

更新规则(2.3)是本书中经常出现的一种更新规则，其一般形式为：

  NewEstimate\gets OldEstimate\ +\ StepSize\big[Target-OldEstimate\big].(2.4)

\big[Target-OldEstimate\big]表达式表示了误差的估计，该误差通过向“目标”趋近来减小,目标假定代表了一个合适的移动方向，尽管可能是有噪声的。在上面的例子中目标是第n个奖励。

值得注意的是，上面增量方法中使用的步长参数（StepSize）会随着时间步的进行而发生变化，在计算动作a的第n个奖励时，步长参数将设为\frac{1}{n}，在本书中我们用\alpha，或者更一般的\alpha_t(a)，表示步长参数，偶尔在表示\alpha_t(a)=\frac{1}{n}时，也会采用非正式的简写\alpha=\frac{1}{n}，这种表示隐含了n对于动作的依赖，就像我们在本节中使用的那样。