6.3-Dvoretzky定理
6.3 Dvoretzky定理¶
到目前为止，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\)的函数的情况下，该定理更为有用。
-
第一个条件是 "几乎必然一致"。这是因为\(\alpha_k\)和\(\beta_k\)可能是随机变量，因此它们的极限定义必须在随机情况下。第二个条件也表述为"几乎必然"。这是因为\(\mathcal{H}k\)是一个随机变量序列，而不是具体的值。因此，\(\mathbb{E}[\eta_{k}|\mathcal{H}_{k}]\)和\(\mathbb{E}[\eta_{k}^{2}|\mathcal{H}_{k}]\)都是随机变量。在这种情况下，条件期望的定义是以“几乎必然”的意义给出的(附录 \(B\))。
-
定理\(6.2\)的陈述与[32]略有不同，因为定理\(6.2\)的第一个条件中并不要求\(\sum_{k=1}^{\infty}\beta_{k}=\infty\)。当\(\sum_{k=1}^{\infty}\beta_{k}<\infty\)时，特别是当\(\beta_k = 0\)对所有\(k\)成立时，该序列仍然可以收敛。
6.3.1 Dvoretzky的证明¶
见Box\(6.3.1\)。
6.3.2 应用于期望值估计¶
虽然均值估计算法\(w_{k+1}=w_k+\alpha_k(x_k-w_k)\)已经通过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算法的迭代公式为
这时我们有
根据中值定理[7,8]，可得\(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^*\)，上面公式可变为
注意到在假设条件下\(\nabla_w g(w)\)有界，即 \(0 < c_1 \leq \nabla_w g(w) \leq c_2\)。根据假设 \(\sum_{k=1}^\infty a_k = \infty\)且 \(\sum_{k=1}^\infty a_k^2 < \infty\)，可知 \(\sum_{k=1}^\infty \alpha_k = \infty\)且 \(\sum_{k=1}^\infty \alpha_k^2 < \infty\)。因此，Dvoretzky定理的所有条件均被满足，故 \(\Delta_k\)几乎必然收敛于零。
RM定理的证明展现了Dvoretzky定理的强大能力。特别地，证明中的\(\alpha_k\)是一个依赖于\(w_k\)的随机序列，而非确定性序列。在此情形下，Dvoretzky定理依然适用。
6.3.4 Dvoretzky定理的扩展¶
接下来，我们将Dvoretzky定理推广至一个能处理多变量的更一般形式。该广义定理由[32]提出，可用于分析\(Q\)学习等随机迭代算法的收敛性。
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\)定义于集合之上，其与向量的 \(L^\infty\)范数概念相似但存在差异。具体而言：\(\mathbb{E}[\eta_k(s)|\mathcal{H}_k] \|_\infty \doteq \max_{s \in \mathcal{S}} | \mathbb{E}[\eta_k(s)|\mathcal{H}_k] |\)以及\(\| \Delta_k(s) \|_\infty = \max_{s \in \mathcal{S}} | \Delta_k(s) |\)
-
该定理比Dvoretzky定理更具普适性。首先，由于采用了最大范数运算，它能处理多变量情形，这对存在多重状态的强化学习问题至关重要；其次，Dvoretzky定理要求 \(\mathbb{E}[\eta_k(s)|\mathcal{H}_k] =0\)且 \(\text{var}[\eta_k(s)|\mathcal{H}_k] \leq C\)，而本定理仅需期望与方差被误差 \(\Delta_k\)界定。
-
需注意，\(\Delta(s)\)对所有 \(s \in \mathcal{S}\)的收敛性要求条件在每一 \(s \in \mathcal{S}\)上均成立。因此，在应用该定理证明强化学习算法收敛性时，需证明这些条件对每个状态(或状态-动作对)均成立。