深入理解强化学习——多臂赌博机：增量式实现

分类目录：《深入理解强化学习》总目录

至今我们讨论的动作—价值方法都把动作价值作为观测到的收益的样本均值来估计。下面我们探讨如何才能以一种高效的方式计算这些均值，尤其是如何保持常数级的内存需求和常数级的单时刻计算量。

为了简化标记，我们关心单个动作。令$R_i$表示这一动作被选择$i$次后获得的收益，$Q_n$表示被选择$n-1$次后它的估计的动作价值，现在可以简单地把它写为：
$$Q_n=\frac{R_1+R_2+\cdots +R_{n-1}}{n-1}$$

这种简明的实现需要维护所有收益的记录，然后在每次需要估计价值时进行计算。然而，由于已知的收益越来越多，内存和计算量会随着时间增长。每增加一次收益就需要更多的内存存储和更多的计算资源来对分子求和，但这确实不是必须的。为了计算每个新的收益，很容易设计增量式公式以小而恒定的计算来更新平均值。给定$Q_n$和第$n$次的收益$R_n$，所有$n$个收益的新的均值可以这样计算：
$$Q_{n+1}=Q_n+\frac{1}{n}[R_n-Q_n]$$

这个式子即使对$n=1$也有效，对任意$Q_1$，可以得到$Q_2=R_1$。对于每一个新的收益，这种实现只需要存储$Q_n$和$n$，并用上式进行少量计算即可。

上式的一般的形式是：
$$\text{新估计值}=\text{旧估计值}+\text{步长}\ast [\text{目标}-\text{旧估计值}]$$

表达式$\text{目标}-\text{旧估计值}$是估计值的误差。误差会随着向“目标"（Target）靠近的每一步而减小。虽然“目标"中可能充满噪声，但我们还是假定“目标”会告诉我们可行的前进方向。比如在上述例子中，目标就是第$n$次的收益。

值得注意的是，上述增量式方法中的“步长"（Stepsize）会随着时间而变化。处理动作$a$对应的第$n$个收益的方法用的“步长"是$\frac{1}{n}$。我们将“步长"记作$\alpha$，或者更普适地记作${\alpha }_t(a)$。

参考文献：
[1] 张伟楠, 沈键, 俞勇. 动手学强化学习[M]. 人民邮电出版社, 2022.
[2] Richard S. Sutton, Andrew G. Barto. 强化学习（第2版）[M]. 电子工业出版社, 2019
[3] Maxim Lapan. 深度强化学习实践（原书第2版）[M]. 北京华章图文信息有限公司, 2021
[4] 王琦, 杨毅远, 江季. Easy RL：强化学习教程 [M]. 人民邮电出版社, 2022