强化学习中的算法-译 4 有限状态空间的时序差分学习

在这一节中,我们考虑估计一些马尔可夫奖励过程(MRP)下的价值函数 $V$ 的问题。价值预测问题以多种方式出现。估算某些未来事件的概率、某些事件发生前的预期时间或 MDP 中某些策略下的(动作-)价值函数都是价值预测问题。具体的应用有估计大型电网的故障概率(Frank等人[1],2008)或估计繁忙机场的航班离场滑行时间(Balakrishna等人[2],2008),这只是众多可能性中的两个。

由于一个状态的值被定义为过程从给定状态开始时随机返回的期望值,估计这个值的一个明显方法是计算从给定状态开始的多个独立实现的平均值。这就是所谓的 $\text{Monte-Carlo}$ 方法的一个实例。不幸的是,回报的方差可能很高,这意味着估计的质量会很差。另外,当以闭环方式与系统互动时(即在与系统互动时进行估计),可能无法将系统的状态重置为某个特定的状态。在这种情况下,应用 $\text{Monte-Carlo}$ 技术不可避免地引入一些额外的偏差。时序差分学习($\text{TD}$)(Sutton, 1984[3], 1988[4]),毫无疑问是强化学习中最重要的思想之一,是一种可以用来解决这些问题的方法。

有限状态空间的时序差分学习

$\text{TD}$ 学习的独特之处在于它使用了自举法(bootstrapping):预测在学习过程中被用作目标。在这一节中,我们首先介绍最基本的 $\text{TD}$ 算法,并解释自举是如何工作的。接下来,我们将 $\text{TD}$ 学习与(vanilla,原始)$\text{Monte-Carlo}$ 方法进行比较,并认同两者都有各自的优点。最后,我们提出了统一这两种方法的 $\text{TD}(\lambda)$ 算法。在这里,我们只考虑小的、有限的 MRP 的情况,当所有状态的估计值可以存储在计算机的主存储器中的数组或表格中时,这在强化学习文献中被称为表格的情况。当表格表示不可行的时候,把这里提出的想法扩展到大的状态空间,将在随后的章节中描述。

表格 $\text{TD}(0)$

固定某个有限的马尔可夫奖励过程 $\mathcal{M}$。我们希望在给定 $\mathcal{M}$ 的实现 $((X_t, R_{t+1}); t \geq 0)$ 的情况下估计 $\mathcal{M}$ 的价值函数 $V$。令 $V_t(x)$ 表示在时间 $t$ 上对状态 $x$ 的估计(例如,$V_0\equiv 0$)。在第 $t$ 步中,$\text{TD}(0)$ 执行以下计算:
$$
\begin{aligned}
\delta_{t+1} &= R_{t+1}+\gamma \hat{V}_t(X_{t+1}) - \hat{V}_t(X_t),\\
\hat{V}_{t+1}(x) &= \hat{V}_t(x)+\alpha_t\delta_{t+1}\Bbb{I}_{\lbrace X_t = x \rbrace},\\
x &\in \mathcal{X}
\end{aligned}
\tag{17}
$$
这里的步长序列 $(\alpha_ t ; t \geq 0)$由用户选择的(小的)非负数组成。算法 1 展示了这个算法的伪代码。

算法1 实现表格 $\text{TD}(0)$ 算法的函数。这个函数必须在每次转移后调用。

函数 $\text{TD0}(X,R,Y,V)$

输入:最后状态 $X$,下一状态 $Y$,与该转移相关的即时奖励 $R$,存储当前值估计的数组 $V$

  1. $\delta \leftarrow R+\gamma \cdot V[Y]-V[X]$
  2. $V[X]\leftarrow V[X]+\alpha \cdot\delta$
  3. $\textbf{return}\ V$

仔细检查更新方程可以发现,唯一改变的值是与 $X_t$ 相关的值,也就是刚刚访问过的状态(参见伪码第2行)。此外,当 $\alpha_t \leq 1$ 时,$X_t$ 的值被移向「目标」$R_{t+1} + \gamma \hat{V}_t(X_{t+1})$。由于目标取决于估计的价值函数,该算法使用了自举法(bootstrapping)。算法名称中的「时序差分(temporal difference)」一词来自于 $δ_{t+1}$ 被定义为对应于连续时间步骤的状态值之间的差异。特别是,$δ_{ t+1}$被称为时序差分误差(temporal difference error)。

正如强化学习中的许多其他算法一样,表格 $\text{TD}(0)$ 是一种随机逼近(stochastic approximation, SA)算法。很容易看出,如果它收敛,那么它必须收敛到一个函数 $\hat{V}$,使得 给定 $\hat{V}$ 得时序差分期望$$F\hat{V}(x) \stackrel{\text{def}}=\Bbb{E}[R_{t+1}+\gamma \hat{V}(X_t)-\hat{V}(X_{t+1})\mid X_t = x]$$对所有状态 $x$ 来说都为零,至少对所有被无限次采样的状态来说是如此。一个简单的计算表明,$F\hat{V} = T\hat{V} - \hat{V}$,其中 $T$ 是所考虑的 MRP 下 贝尔曼算子。根据事实 1,$F\hat{V} = 0$ 有一个唯一的解决方案,即价值函数 $V$。因此,如果 $\text{TD}(0)$ 收敛(而且所有的状态都被无限次采样),那么它必须收敛到 $V$。为了研究算法的收敛特性,为简单起见,假设 $(X_t; t\in \Bbb{N})$ 是一个平稳的、遍历的马尔可夫链。[5]此外,像以前一样用 $D$ 维向量来标识逼近的价值函数 $V_t$(例如,$\hat{V}_{t,i} = \hat{V}_t(x_i), i = 1, \dots , D$,其中 $D = \lvert X \rvert,X = \lbrace x_1,\dots, x_D\rbrace$)。然后,假设步长序列满足 Robbins-Monro(RM)条件 $$ \sum_{t=0}^\infty \alpha_t = \infty, \sum_{t=0}^\infty \alpha_t^2 \lt +\infty$$,序列 $(\hat{V}_t \in \Bbb{R}^D;t\in\Bbb{N})$ 会跟踪常微分方程(ODE)$$\dot{v}(t)=cF(v(t)), t \geq 0 \tag{18}$$的轨迹,其中 $c=1/D$ 且 $v(t)\in\Bbb{R}^D$ (如 Borkar, 1998[6])。借用(11)中使用的符号,上述 ODE 可以写为$$\dot{v}=r+(\gamma P-I)v$$。请注意,这是一个线性 ODE。由于 $\gamma P - I$ 的特征值都位于复平面的开放左半平面内,这个 ODE 是全局渐近平稳的。由此,利用 SA 的标准结果,可以得出 $V_t$ 几乎必然地收敛于 $V$。

考虑步长 由于我们将要讨论的许多算法都使用了步长,所以值得花一些时间来讨论它们的选择。一个满足上述条件的简单步长序列是 $\alpha_t = c/t,c \gt 0$。更一般地说,只要 $1/2 \lt \eta \leq 1$,任何形式的步长序列 $\alpha_t = ct^{-\eta},c \gt 0$ 都可以使用。在这些步长序列中,$\eta =1$ 给出了最小的步长。渐进地看,这种选择是最好的,但从算法的瞬时行为来看,选择 $\eta$ 接近 $1/2$ 会更好(因为这种选择的步长更大,因此算法会做更大的动作),甚至有可能做得比这更好。事实上,一种简单的方法——由 Polyak和Juditsky(1992)[7]提出的迭代平均法,被认为可以达到最好的渐进收敛率。然而,尽管它的理论属性很吸引人,但迭代平均法在实践中却很少使用。事实上,在实践中人们经常使用恒定的步长,这显然违反了 RM条件。这种选择是基于两个理由的:首先,算法经常被用于非平稳环境中(即,要评估的策略可能会改变);第二,这些算法通常只在小样本制度下使用(当使用恒定的步长时,参数会在分布上收敛。极限分布的方差将与选择的步长成正比)。在发展自动调整步长的方法方面也有很多工作要做,见(Sutton, 1992[8]; Schraudolph, 1999[9]; George and Powell, 2006[10])和其中的参考文献。然而,关于这些方法中哪一个是最好的,目前还没有定论。

只要稍作改动,该算法也可用于形式为 $((X_t , R_{t+1} , Y_{t+1}); t \geq 0)$ 的观察序列,其中 $(X_t ; t \geq 0)$ 是 $\mathcal{X}$ 上的遍历的马尔可夫链,$(Y_{t+1} , R_{t+1})\sim \mathcal{P}_ 0( \cdot \mid X_t)$。这一变化涉及到时序差分的定义: $$\delta_{t+1} = R_{t+1}+\gamma\hat{V}(Y_{t+1})-\hat{V}(X_t)$$。

那么,在没有额外条件的情况下,$V_t$ 仍然几乎必然地收敛于 MRP $(\mathcal{X},\mathcal{P}_0)$ 下的价值函数。特别是,状态 $(X_t ; t \geq 0)$ 的分布在这里并不起作用。

这很有趣,有多种原因。例如,如果样本是用模拟器生成的,我们就可以独立于 MRP 来控制状态 $(X_t; t\geq 0)$ 的分布。这对于平衡马尔可夫核 $\mathcal{P}$ 下的平稳分布中的任何不均衡性可能是有用的。另一个用途是学习 MDP 中的一些目标策略,同时遵循一些通常称为行为策略的其他策略。为简单起见,假设目标策略是确定性的。那么 $((X_t , R_{t+1} , Y_{ t+1}\ ), t \geq 0)$ 可以通过跳过所有由行为策略产生的轨迹中的状态-动作-奖励-下一个状态的四元组而得到,这些四元组中所采取的动作与目标策略在给定状态下所采取的行动不一致,而保留其余的(四元组)。这种技术可能允许人们在同一时间学习多种策略(更一般地说,学习多种长期预测问题)。当学习一个策略,同时遵循另一个策略时,被称为 离线策略学习(off-policy learning)。正因为如此,当 $Y_{t+1} \neq X_{t+1}$ 时,我们也将把基于三元组的学习 $((X_t , R_{t+1}, Y_{t+1} );t \geq 0)$ 称为离线策略学习。第三种技术性用途是当目标是将算法应用于一个情节性问题时。在这种情况下,三元组 $(X_t, R_{t+1}, Y_{t+1})$ 被如下选择:首先,$Y_{t+1}$ 从转移核 $\mathcal{P}(X,\cdot)$ 中取样。如果 $Y_{t+1}$ 不是终结状态,我们让 $X_{t+1} = Y_{t+1}$;否则,$X_{t+1} \sim \mathcal{P}_0(\cdot)$,其中 $\mathcal{P}_0$ 是用户选择的 $\mathcal{X}$ 上的分布。换句话说,当达到终结状态时,过程从初始状态分布 $\mathcal{P}_0$ 重新开始。从 $\mathcal{P}_0$ 重启到达到终结状态之间的时间段被称为一个情节(episode)(因此被称为情节性问题)。这种产生样本的方式应被称为从 $\mathcal{P}_0$ 重启的持续采样。
作为一个标准的线性SA方法,表格 $\text{TD}(0)$ 的收敛率将是通常的 $O(1/ \sqrt{t})$ 级(精确结果请参考Tadi´c(2004)[11]的论文和其中的参考文献)。然而,收敛率中的常数因子将在很大程度上受到步长大小序列的选择、核 $\mathcal{P}_0$ 的属性和 $\gamma$ 值的影响。

Every-visit $\text{Monte-Carlo}$

如前所述,我们也可以通过计算样本平均值来估计一个状态的值,这就产生了所谓的每次访问蒙特卡洛(every-visit Monte-Carlo方法。在这里,我们更精确地定义我们的意图,并将所产生的方法与 $\text{TD}(0)$ 进行比较。

为了确定这些想法,考虑某个情节性问题(否则,由于轨迹无限长,不可能无限地计算一个给定状态的回报)。令 这个问题下的 MRP 为 $\mathcal{M} = (\mathcal{X}, \mathcal{P}_0)$,$((X_ t , R_{t+1} , Y_{ t+1}\ ); t \geq 0)$ 由 $\mathcal{M}$ 中的持续采样产生,并从 $\mathcal{X}$ 上定义的某个分布 $\mathcal{P}_0$ 中重新开始。令 $(T_k ; k \geq 0)$ 是一个情节开始的时间序列(因此,对于每个 $k$,$X_{T_k}$ 是从 $\mathcal{P}_0$ 中取样的)。对于一个给定的时刻 $t$,令 $k(t)$ 是使得 $t\in[T_k, T_{k+1})$ 的唯一的情节索引。记从时刻 $t$ 开始到情节结束的回报为 $$\mathcal{R}_t = \sum_{s=t}^{T_{k(t)+1}-1}\gamma^{s-t}R_{s+1} \tag{19}$$。显然,$V(x) = \Bbb{E}\ [\mathcal{R}_t \mid X_t = x]$,对于任何状态 $x$,有 $\Bbb{P}(X_t= x)\gt0$。因此,更新估计值的一个明智的方法是使用 $$\hat{V}_{t+1}(x)=\hat{V}_t(x)+\alpha_t(\mathcal{R}_t-\hat{V}_t(x))\Bbb{I}_{\lbrace X_t=x \rbrace }, x \in \mathcal{X}$$。

算法 2 实现 every-visit $\text{Monte-Carlo}$ 算法的函数,用于估计情节性 MDP 的价值函数。这截程序必须在每一情节结束时调用,并在该情节期间收集状态-奖励序列。请注意,这里展示的算法具有情节长度上的线性的时间和空间复杂度。

函数 $\text{EveryVisitMC}(X_0, R_1, X_1, R_2,\dots,X_{T-1}, R_T,V)$

输入:时刻 $t$ 的状态 $X_t$,与第 $t$ 个转移相关的奖励 $R_{t+1}$,情节的长度 $T$,存储当前价值函数估计的数组 $V$

  1. $sum \leftarrow 0$
  2. $\textbf{for}\ t \leftarrow T-1 \ \textbf{downto}\ 0\ \textbf{do}$
  3. $\quad sum \leftarrow R_{t+1} +\gamma\cdot sum$
  4. $\quad target[X_t] \leftarrow sum$
  5. $\quad V[X_t]\leftarrow V[X_t]+\alpha\cdot(target[X_t]-V[X_t])$
  6. $\textbf{end for}$
  7. $\textbf{return}\ V$

像上面这种 $\text{Monte-Carlo}$ 方法,由于使用了多步预测值(参见公式(19)),所以被称为多步方法。这个更新模块的伪代码如算法 2 所示。

这个算法也是随机逼近的一个实例。因此,它的行为受 ODE $\dot{v}(t)=V-v(t)$ 的制约。由于这个 ODE 的唯一全局渐近平稳的均衡是 $V$,所以 $V_t$ 又几乎必然地收敛到 $V$。由于这两种算法实现了相同的目标,人们可能想知道哪种算法更好。

$ \text{TD}(0)$ 还是 $\text{Monte-Carlo}$?

首先,让我们考虑一个当 $\text{TD}(0)$ 收敛较快时的例子。考虑下图所示的未折扣的情节性 MRP。初始状态是 1 或 2。这个过程很可能从状态 1 开始,而从状态 2 开始的频率较低。现在考虑一下 $\text{TD}(0)在$ 状态 2 下的表现。当状态 2 被访问到第 $k$ 次时,平均来说,状态 3 已经被访问了 $10k$ 次。假设 $\alpha_ t = 1/(t + 1)$。在状态 3,$\text{TD}(0)$ 的更新减少到平均离开状态 3 时产生的伯努利奖励。在第 $k$ 次访问状态 2 时,$\text{Var}[\hat{V}_ t(3)]\approx \ 1/(10 k)$ (显然,$\Bbb{E}[\hat{V}_t(3)] = V (3) = 0.5$)。因此,状态 2 的更新目标将是对状态 2 的真实值的估计,精度随 $k$ 增加。$\text{Monte-Carlo}$ 方法忽略了对状态 3 值的估计,而直接使用伯努利奖赏。特别是,$\text{Var}[R_t \mid X_t = 2] = 0.25$,也就是说,目标的方差不随时间变化。在这个例子中,这使得 $\text{Monte-Carlo}$ 方法的收敛速度变慢,表明有时自举可能确实有帮助。

stateDiagram
    direction LR
        1 --> 3: 0
        note left of 1: P0(1) = 0.9
        2 --> 3: 0
        note left of 2: P0(2) = 0.1
        3 --> 4: R ~ Ber(0.5)
        4 --> 4: 0

一个情节性的马尔可夫奖励过程。在这个例子中,所有的转移都是确定性的。除了从状态 3 过渡到状态 4 时,奖励由参数为 0.5 的伯努利随机变量给出,其他的奖励为零。状态 4 是一个终结状态。当过程到达终结状态时,它被重置为从状态 1 或 2 开始。从状态 1 开始的概率是 0.9,而从状态 2 开始的概率是 0.1。

来看一个自举无用的例子。设想问题被改成与从状态 3 到状态 4 的转移相关的奖励被确定为等于 1。在这种情况下,$\text{Monte-Carlo}$ 方法变得更快,因为 $R_t = 1$ 是真实的目标值,而为了使状态 2 的值接近其真实值,$\text{TD}(0)$ 必须等到状态3的估计值变得接近其真实值。这就减慢了 $\text{TD}(0)$ 的收敛速度。事实上,我们可以想象一个更长的状态链,其中对于 $i\in\lbrace 1, \dots,N\rbrace$,状态 $i+1$ 跟随状态 $i$,唯一发生非零奖励的时间是从状态 $N-1$ 转移到状态 $N$。在这个例子中,$\text{Monte-Carlo}$ 方法的收敛率不受 $N$ 值的影响,而 $\text{TD}(0)$ 会随着 $N$ 的增加而变慢(非正式论证,见Sutton,1988[12];有精确收敛率的正式论证,见Beleznay等人,1999[13])。

$\text{TD}(\lambda)$:统一 $\text{Monte-Carlo}$ 和 $\text{TD}(0)$

前面的例子表明,蒙特卡洛和TD(0)都有各自的优点。有趣的是,有一种方法可以将这些方法统一起来。这是由所谓的 $\text{TD}(\lambda )$ 系列方法实现的(Sutton, 1984[3], 1988[4])。这里,$\lambda \in [0,1]$ 是一个参数,其允许人们在 $\text{Monte-Carlo}$ 和 $\text{TD}(0)$ 更新之间进行插值:$\lambda=0$ 给出 $\text{TD}(0)$(因此被称为 $\text{TD}(0)$),而 $\lambda=1$,即 $\text{TD}(1)$ 等同于 $\text{Monte-Carlo}$ 方法。实质上,给定某个 $λ>0$,$\text{TD}(\lambda )$ 更新中的目标由某个多步回报预测 $$\mathcal{R}_{t:k}=\sum_{s=t}^{t+k}\gamma^{s-t}R_{s+1}+\gamma^{k+1}\hat{V}_t(X_{t+k+1})$$的混合给出,其中混合系数为指数权重 $(1-\lambda)\lambda^ k, k\geq0$。 因此,对于 $\lambda\gt 0$, $\text{TD}(\lambda )$ 将是一个多步骤方法。该算法通过引入所谓的资格迹使其成为增量算法。
事实上,资格迹以用多种方式定义,因此 $\text{TD}(\lambda )$ 也相应地存在多种形式。带有所谓累积迹(accummulating traces)的 $\text{TD}(\lambda )$ 的更新规则如下:

$$\begin{aligned}\delta_{t+1}&=R_{t+1}+\gamma\hat{V}_t(X_{t+1})-\hat{V}_t(X_t),\\ z_{t+1}&=\Bbb{I}_{\lbrace x=X_t\rbrace}+\gamma\lambda z_t(x),\\ \hat{V}_{t+1}&=\hat{V}_t(x)+\alpha_t\delta_{t+1}z_{t+1}(x),\\ z_0(x)&=0,\\ x\in\mathcal{X}.\end{aligned}$$

这里 $z_t(x)$ 是状态 $x$ 的资格迹(eligibility trace)。这个名字的原理是 $z_t(x)$ 的值可以调节 $\text{TD}$ 误差对存储在状态 $x$ 的值的更新的影响。在该算法的另一个变体中,资格迹根据$$z_{t+1}(x)=\max(\Bbb{I}_{\lbrace x=X_t \rbrace},\gamma\lambda z_t(x)),x\in\mathcal{X}$$来更新。

这被称为置换迹(replacing trace)更新。在这些更新中,迹衰减参数(trace-decay parameter) $\lambda$ 控制着自举的数量:当 $\lambda=0$ 时,上述算法变得与 $\text{TD}(0)$ 相同(因为 $\lim_{\lambda\to 0+} (1-\lambda)\sum_{k\geq 0}\lambda^k\mathcal{R}_{t:k} = \mathcal{R}_{t:0} = R_{t+1} + \gamma\hat{V}_t(X_t+1)$)。当 $\lambda=1$ 时,我们得到 $\text{TD}(1)$ 算法,它与累积迹一起将模拟之前描述的情节性问题中的 every-visit $\text{Monte-Carlo}$ 算法。(为了精确的等价,我们需要假设价值更新只发生在轨迹的末端,在这之前的更新只是累积。然后,该公式会成立,因为从起始状态到终点状态的轨迹上的时序差分的折扣总和会伸缩,并给出沿轨迹的回报和起始状态的价值估计之间的差分。)置换迹和 $\lambda=1$ 对应于 $\text{Monte-Carlo}$ 算法的一个版本,其中一个状态只有在轨迹中第一次出现时才被更新。相应的算法被称为 首次访问蒙特卡洛(first-visit Monte-Carlo) 方法。First-visit $\text{Monte-Carlo}$与 $\text{TD}(1)$ 之间的正式对应关系,已知只在未折现的情况下成立(Singh 和 Sutton,1996[14])。

算法 3 使用置换迹实现表格 $\text{TD}(\lambda)$ 算法的函数,该函数必须在每次转移后调用。

函数 $\text{TDLambda}(X,R,Y,V,z)$

输入:最后状态 $X$,下一状态 $Y$,与该转移相关的即时奖励 $R$,存储当前值估计的数组 $V$,存储资格迹的数组 $z$

  1. $\delta \leftarrow R+\gamma \cdot V[Y]-V[x]$
  2. $\textbf{for all}\ x\in\mathcal{X}\ \textbf{do}$
  3. $\quad z[x] \leftarrow \gamma\cdot\lambda\cdot z[x]$
  4. $\quad \textbf{if}\ X=x\ \textbf{then}$
  5. $\quad\quad z[x] \leftarrow 1$
  6. $\quad \textbf{end if}$
  7. $\quad V[x]\leftarrow V[x]+\alpha\cdot\delta\cdot z[x]$
  8. $\textbf{end for}$
  9. $\textbf{return}\ (V,z)$

算法 3 给出了与置换迹的变体对应的伪代码。在实践中,$\lambda$ 的最佳值是通过试验和错误确定的。事实上,$\lambda$ 的值甚至可以在算法过程中改变,而不影响收敛性。这对其他广泛的可能的资格迹更新也是如此(关于精确的条件,见Bertsekas和Tsitsiklis,1996[15],第5.3.3和5.3.6节)。该算法的替换痕迹版本被认为在实践中表现更好(关于发生这种情况的一些例子,请参考Sutton和Barto,1998[16],第7.8节)。有人指出,当学习者对状态只有部分了解时,或者(在相关情况下)当函数逼近被用来逼近大状态空间中的值函数时,$\lambda\gt 0$ 是有帮助的——这是下一节的主题。

总之,$\text{TD}(\lambda)$ 允许人们在 MRP 中估计价值函数。它概括了 $\text{Monte-Carlo}$ 方法,可以用于非情节性问题,并允许自举。此外,通过适当地调整 $λ$,它的收敛速度明显快于 $\text{Monte-Carlo}$ 或 $\text{TD}(0)$。


  1. 1.Frank, J., Mannor, S., and Precup, D. (2008). Reinforcement learning in the presence of rare events. In Cohen et al. (2008), pages 336–343.
  2. 2.Balakrishna, P., Ganesan, R., Sherry, L., and Levy, B. (2008). Estimating taxi-out times with a reinforcement learning algorithm. In 27th IEEE/AIAA Digital Avionics Systems Conference, pages 3.D.3–1 – 3.D.3–12.
  3. 3.Sutton, R. S. (1984). Temporal Credit Assignment in Reinforcement Learning. PhD thesis, University of Massachusetts, Amherst, MA.
  4. 4.Sutton, R. S. (1988). Learning to predict by the method of temporal differences. Machine Learning, 3(1):9–44.
  5. 5.请记住,如果一个马尔可夫链 $(X_t; t\in \Bbb{N})$ 是不可还原的、无周期的和正循环的,它就是遍历的。实际上,这意味着大数法则对马尔可夫链的正则函数是成立的。
  6. 6.Borkar, V. S. (1998). Asynchronous stochastic approximations. SIAM J. Control and Optimization, 36(3):840–851.
  7. 7.Polyak, B. and Juditsky, A. (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30:838–855.
  8. 8.Sutton, R. S. (1992). Gain adaptation beats least squares. In Proceedings of the 7th Yale Workshop on Adaptive and Learning Systems, pages 161—166.
  9. 9.Schraudolph, N. (1999). Local gain adaptation in stochastic gradient descent. In Ninth International Conference on Artificial Neural Networks (ICANN 99), volume 2, pages 569–574.
  10. 10.George, A. P. and Powell, W. B. (2006). Adaptive stepsizes for recursive estimation with applications in approximate dynamic programming. Machine Learning, 65:167–198.
  11. 11.Tadi´c, V. B. (2004). On the almost sure rate of convergence of linear stochastic approximation algorithms. IEEE Transactions on Information Theory, 5(2):401–409.
  12. 12.Sutton, R. S. (1988). Learning to predict by the method of temporal differences. Machine Learning, 3(1):9–44.
  13. 13.Beleznay, F., Gr˝obler, T., and Szepesv´ari, C. (1999). Comparing value-function estimation algorithms in undiscounted problems. Technical Report TR-99-02, Mindmaker Ltd., Budapest 1121, Konkoly Th. M. u. 29-33, Hungary.
  14. 14.Singh, S. P. and Sutton, R. S. (1996). Reinforcement learning with replacing eligibility traces. Machine Learning, 32:123–158.
  15. 15.Bertsekas, D. P. and Tsitsiklis, J. N. (1996). Neuro-Dynamic Programming. Athena Scientific, Belmont, MA.
  16. 16.Sutton, R. S. and Barto, A. G. (1998). Reinforcement Learning: An Introduction. Bradford Book. MIT Press.