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

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$ 的增加以指数形式递减:距离越近的收益权重越大,距离越远的收益权重越小。