[RL Notes] 动作价值估计的增量更新

Author: nex3z 2019-10-12

1. 增量计算平均值

　　前文给出的估计动作价值的方法，需要保存所有历史数据，即历史上观测到的所有动作收益。这一计算实际上可以通过增量计算的方式更有效地进行。

　　考虑一个特定动作 $a$，记 $R_i$ 为这一动作被选择 $i$ 次后获得的收益，$Q_n$ 表示选择该动作 $n-1$ 次后对动作价值的估计，则

$$\begin{equation} Q_n \doteq \frac{R_1 + R_2 + \cdots + R_{n-1}}{n-1} = \frac{1}{n-1} \sum_{i=1}^{n-1}R_i \tag{1} \end{equation}$$

由上式可以进一步得到

$$\begin{align} Q_{n+1} &= \frac{1}{n} \sum_{i=1}^{n}R_i = \frac{1}{n} \bigg( R_n + \sum_{i=1}^{n-1}R_i \bigg) = \frac{1}{n} \bigg( R_n + (n-1) \frac{1}{n-1} \sum_{i=1}^{n-1}R_i \bigg) \\ &= \frac{1}{n} \big( R_n + (n-1)Q_n \big) = \frac{1}{n}(R_n + nQ_n – Q_n) \\ &= Q_n + \frac{1}{n}(R_n – Q_n) \tag{2} \end{align}$$

使用式 $(2)$，只需要保存 $Q_n$ 和 $n$，就可以计算得到 $Q_{n+1}$，同时计算量也比式 $(1)$ 少。

2. 一般形式

　　式 $(2)$ 可以写成一种更新估计值的一般形式

$$\begin{equation} 新估计值 \leftarrow 旧估计值 + 步长 \times (目标 – 旧估计值) \tag{3} \end{equation}$$

其中$(目标 – 旧估计值)$可以看成是估计的误差，$新估计值$在$旧估计值$的基础上，朝着$目标$的方向前进，使得误差随着向$目标$靠近的每一步而减小。

3. 增量更新

　　由式 $(3)$ 可以得到对动作价值估计的更新规则

$$\begin{equation} Q_{n+1} \doteq Q_n + \alpha_n(R_n – Q_n) \tag{4} \end{equation}$$

其中步长 $\alpha_n \in [0, 1]$，是 $n$ 的函数。当 $\alpha_n = \frac{1}{n}$ 时，式 $(4)$ 变为式 $(2)$，计算的是平均值。

4. 应对非平稳问题

　　在前文给出的 $k$ 臂赌博机问题中，每个动作的收益由所选动作决定的平稳概率分布产生。如果产生动作收益的概率不平稳，如赌博机某个拉杆在夏天的收益期望大于在冬天的收益期望，使用式 $(2)$ 计算平均值就难以体现这一变化。

　　估计非平稳赌博机问题动作价值的一个方法是在式 $(3)$ 中使用常数步长，即

$$\begin{equation} Q_{n+1} \doteq Q_n + \alpha(R_n – Q_n) \tag{5} \end{equation}$$

其中步长 $\alpha \in (0, 1]$ 是一个常数，此时

$$\begin{align} Q_{n+1} &= Q_n + \alpha(R_n – Q_n) \\ &= \alpha R_n + (1 – \alpha)Q_n = \alpha R_n + (1 – \alpha)[\alpha R_{n-1} + (1 – \alpha)Q_{n-1}] \\ &= \alpha R_n + (1 – \alpha) \alpha R_{n-1} + (1 – \alpha)^2 Q_{n-1} \\ &= \alpha R_n + (1 – \alpha) \alpha R_{n-1} + (1 – \alpha)^2 \alpha R_{n-2} + \cdots + (1 – \alpha)^{n-1} \alpha R_1 + (1 – \alpha)^n Q_1 \\ &= (1 – \alpha)^n Q_1 + \sum_{i=1}^n \alpha(1-\alpha)^{n-i}R_i \end{align}$$

可见此时 $Q_{n+1}$ 是对过去收益 $R_i$ 和初始估计 $Q_1$ 的加权平均，权重随间隔 $n-i$ 的增加以指数形式递减：距离越近的收益权重越大，距离越远的收益权重越小。