6.3-Dvoretzky定理
下面证明定理 6.1 从而证明 RM 算法的收敛性。为此，我们首先介绍一个重要的结果：Dvoretzky 定理 [31, 32]。这是随机近似领域的一个经典结果，该结果可以用来分析 RM 算法以及许多强化学习算法的收敛性。
值得提醒大家的是，本节有较多的数学内容。如果大家对随机近似的收敛分析感兴趣，推荐阅读本书；否则可以跳过这一节，并不会影响后续章节的学习。
Info
定理6.2. (Dvoretzky 定理). 考虑如下随机过程
其中\(\{\alpha_k\}_{k=1}^\infty\), \(\{\beta_k\}_{k=1}^\infty\), \(\{\eta_k\}_{k=1}^\infty\)是随机序列。对于所有\(k\)有\(\alpha_k\geq 0,\beta_k\geq 0\)。如果以下条件成立，那么\(\Delta_k\)将几乎必然收敛为零
(a) \(\sum_{k=1}^{\infty}\alpha_{k}=\infty,\sum_{k=1}^{\infty}\alpha_{k}^{2}<\infty,\)并且\(\sum_{k=1}^\infty\beta_k^2<\infty\)一致几乎必然成立;
(b) \(\mathbb{E}[\eta_k|\mathcal{H}_k]=0\)与\(\mathbb{E}[\eta_{k}^{2}|\mathcal{H}_{k}]\leq C\)几乎必然成立;
在这里\(\mathcal{H}_k=\{\Delta_k,\Delta_{k-1},...,\eta_{k-1},...,\alpha_{k-1},...,\beta_{k-1},...\}\)。
在介绍该定理的证明之前，我们首先要解释该定理中的一些条件。
-
在 RM 算法中，系数序列\(\{\alpha_k\}\)是确定性的。在Dvoretzky定理允许\(\{\alpha_k\},\{\beta_k\}\)可以是依赖于\(\mathcal{H}_k\)的随机变量。因此，在\(\alpha_k\)或\(\beta_k\)是\(\Delta_k\)的函数的情况下，该定理更为一般化。
-
Dvoretzky 定理的第一个条件涉及“一致几乎必然”（uniformly almost surely），这是因为当 \(\alpha_k\) 和 \(\beta_k\) 是随机变量时，其极限的定义必须是在随机意义上的。第二个条件也提到了“几乎必然”。这是因为 \(H_k\) 是随机变量，因此条件期望 \(E[\eta_k | H_k]\) 和 \(E[\eta_k^2 | H_k]\) 也是随机变量，其定义是在“几乎必然”意义上的。详情请参见附录 B。
-
定理 6.2 的表述与 [32] 略有不同：其第一个条件不要求 \(\sum_{k=1}^{\infty} \beta_k = \infty\)，这是因为当 \(\sum_{k=1}^{\infty} \beta_k < \infty\)，特别是在极端情况下 \(\beta_k = 0\) 时，序列仍然可以收敛。
6.3.1 Dvoretzky的证明¶
见Box\(6.3.1\)。
6.3.2 应用于期望值估计¶
虽然期望值估计算法\(w_{k+1}=w_k+\alpha_k(x_k-w_k)\)，我们已经在第\(6.2.2\)节使用RM定理分析了其收敛性，下面展示其收敛性也可以通过Dvoretzky定理直接证明。
证明. 令\(w^*=\mathbb{E}[X]\)。期望值估计算法\(w_{k+1}=w_k+\alpha_k(x_k-w_k)\)可以重写为
令\(\Delta=w-w^*\)，那么上式可以写成
由于\({x_k}\)是独立同分布的，我们有\(\mathbb{E}[\eta_k|\mathcal{H}_k] =\mathbb{E}[x_k-w^*|\mathcal{H}_k] = 0\)，且\(\mathbb{E}[\eta_{k}^{2}|\mathcal{H}_{k}]=\mathbb{E}[x_{k}^{2}|\mathcal{H}_{k}]-(w^{*})^{2}=\mathbb{E}[x_{k}^{2}]-(w^{*})^{2}\)是有界的(如果\(x_k\)的方差是有限的)。根据Dvoretzky定理，可知\(\Delta_k\)几乎必然收敛到零，因此\(w_k\)几乎必然收敛到\(w^∗ = \mathbb{E}[X]\)。
6.3.3 应用于证明罗宾斯-门罗定理¶
现在，我们可以用Dvoretzky定理来证明罗宾斯-门罗定理了。
对罗宾斯-门罗定理的证明. RM算法的目的是找到\(g(w) = 0\)的真实解。假设真实解是\(w∗\)，即\(g(w^∗) = 0\)，则RM算法的迭代公式为
在上式两边同减去\(w^*\)可得
根据中值定理[7,8]，可A得\(g(w_{k})-g(w^{*})=\nabla_{w}g(w_{k}^{\prime})(w_{k}-w^{*}),\)在这里\(w_k^\prime\in[w_k,w^*]\)。令\(\Delta_k= w_k-w^*\)，上面公式可变为
首先，RM 定理中的条件 \(c_1 \le \nabla_w g(w) \le c_2\) 表明 \(\nabla_w g(w)\) 是有界的。除此之外，由定理中的条件 \(\sum_{k=1}^{\infty} a_k = \infty\) 和 \(\sum_{k=1}^{\infty} a_k^2 < \infty\)，可得 \(\sum_{k=1}^{\infty} a_k = \infty\) 和 \(\sum_{k=1}^{\infty} a_k^2 < \infty\)。因此，Dvoretzky 定理中的条件都是满足的，进而可知 \(\Delta_k\) 几乎必然收敛到 0。
通过证明 RM 定理，我们知道 Dvoretzky 定理是一个更加一般化的定理。例如，虽然上面证明中的 \(\alpha_k\) 是一个依赖于 \(w_k\) 的随机序列，而并不是一个确定性序列，但是 Dvoretzky 定理仍然适用。
6.3.4 Dvoretzky定理的扩展¶
下面我们进一步推广 Dvoretzky 定理，从而得到一个能够处理多变量的更加强化的定理，可用于分析诸如 Q-learning 等随机优化算法的收敛性。
Info
定理6.3 设 \(\mathcal{S}\)为有限实数集。对于随机过程
对于所有 \(s \in \mathcal{S}\)，若以下条件满足，那么\(\Delta_k(s)\)几乎必然收敛于零：
(a) \(\sum_k \alpha_k(s) = \infty\), \(\sum_k \alpha^2_k(s) < \infty\),\(\sum_k \beta^2_k(s) < \infty\), 且\(\mathbb{E}[\beta_k(s)|\mathcal{H}_k] \leq \mathbb{E}[\alpha_k(s)|\mathcal{H}_k]\) 一致几乎必然成立
(b) \(\|\mathbb{E}[\eta_k(s)|\mathcal{H}_k]\|_\infty\leq\gamma\|\Delta_k\|_\infty\)，其中\(\gamma\in(0,1)\)
© \(\mathrm{var}[\eta_{k}(s)|\mathcal{H}_{k}]\leq C(1+\|\Delta_{k}(s)\|_{\infty})^{2}\),其中\(C\)是一个常数
此处，\(H_k = \{\Delta_k, \Delta_{k-1}, \dots, \eta_{k-1}, \dots, \alpha_{k-1}, \dots, \beta_{k-1}, \dots \}\)表示历史信息。术语 \(\|\cdot\|_\infty\)指代最大范数。
证明. 作为该定理的推广，其证明可基于 Dvoretzky定理完成。具体细节参见文献[32]，以下给出关于该定理的一些说明。
-
首先澄清定理中的一些符号。变量 \(s\) 可以被视为一个索引。在强化学习中，它可以是状态的索引。最大范数 \(\|\cdot\|_\infty\) 是定义在一个集合上的范数。例如，\(\|\eta_k(s)\|_\infty = \max_{s \in S} | \eta_k(s) | H_k|\), \(\| \Delta_k(s)\|_\infty = \max_{s \in S} |\Delta_k(s)|\)。这与我们熟悉的 \(L^\infty\) 范数类似但不完全相同。
-
该定理比 Dvoretzky 定理更一般化。首先，它通过使用最大范数 \(\|\cdot\|_\infty\) 可以处理多个变量，即证明多个变量对应的随机过程都收敛。这对于处理涉及多个状态的强化学习问题非常重要。此外，Dvoretzky 定理要求 \(E[\eta_k(s) | H_k] = 0\) 且 var[\(\eta_k(s)\)] = 0，而该定理仅要求期望值和方差由误差项 \(\Delta\) 控制。
-
值得注意的是，\(\Delta(s)\) 的收敛性要求定理中的条件对每个 \(s \in S\) 都是成立的。因此，在应用此定理证明强化学习算法的收敛性时，我们需要证明该定理中条件对每个状态（或动作-状态对）都是成立的。