下文采用**随机逼近 / 强化学习收敛理论中的 Dvoretzky theorem**，即 Aryeh Dvoretzky 关于 stochastic approximation 的收敛定理；这不是凸几何中“高维凸体近似欧氏球”的 Dvoretzky theorem。Dvoretzky 1956 年论文题为 _On Stochastic Approximation_；近年的形式化证明工作也明确指出，该定理蕴含 Robbins–Monro、Kiefer–Wolfowitz 等经典随机逼近算法的收敛性。([Project Euclid](https://projecteuclid.org/proceedings/berkeley-symposium-on-mathematical-statistics-and-probability/Proceedings-of-the-Third-Berkeley-Symposium-on-Mathematical-Statistics-and/Chapter/On-Stochastic-Approximation/bsmsp/1200501645?utm_source=chatgpt.com "On Stochastic Approximation")) --- # 1. 四个概念的逻辑关系 四者可以按如下层次理解： $$ \boxed{ \text{contraction mapping} \Rightarrow \text{Banach fixed-point theorem} \Rightarrow \text{Robbins--Monro stochastic approximation} \Rightarrow \text{Dvoretzky stochastic approximation theorem} } $$ 含义分别是： $$ \text{contraction mapping} $$ 是一种**映射性质**：距离被严格缩小； [ $$ \text{Banach fixed-point theorem} $$ ] 说明：在完备度量空间中，收缩映射有唯一不动点，并且反复迭代收敛； [ $$ \text{Robbins--Monro theorem} $$ ] 说明：如果无法精确计算函数，只能观测有噪声样本，也可以用递减步长逼近方程根； [ $$ \text{Dvoretzky theorem} $$ ] 给出更一般的随机递推收敛框架，Robbins–Monro、Kiefer–Wolfowitz、许多 stochastic approximation 和强化学习收敛证明都可作为其特例或推论。([Columbia University](https://www.columbia.edu/~ww2040/8100F16/RM51.pdf?utm_source=chatgpt.com "A Stochastic Approximation Method")) --- # 2. Contraction mapping：收缩映射 设 ($(X,d)$) 是度量空间。映射 [ $$ T:X\to X $$ ] 称为 **contraction mapping**，如果存在常数 [ $$ 0\le \alpha<1 $$ ] 使得对任意 ($x,y\in X$)，都有 [ $$ \boxed{ d(Tx,Ty)\le \alpha d(x,y). } $$ ] 其中 ($\alpha$) 称为 contraction modulus。 这比一般 Lipschitz continuity 更强。若只满足 [ $$ d(Tx,Ty)\le d(x,y), $$ ] 即 ($\alpha=1$)，则只是 non-expansive mapping，不足以保证唯一不动点或迭代收敛。 收缩映射的本质是： [ $$ \boxed{ T\text{ 每作用一次，任意两点之间的距离最多缩小为原来的 }\alpha\text{ 倍。} } $$ ] 因此如果存在不动点 $x^*$，即 [ $$ x^*=Tx^*, $$ ] 那么迭代 $$ x_{n+1}=Tx_n $$ 会使误差满足： $$ d(x_{n+1},x^* ) = d(Tx_n,Tx^* ) \le \alpha d(x_n,x^* ). $$ 递推得到： $$ \boxed{ d(x_n,x^*)\le \alpha^n d(x_0,x^* ). } $$ 这说明误差按几何速度衰减。 --- # 3. Banach fixed-point theorem ## 3.1 定理陈述 设 ($(X,d)$) 是非空完备度量空间，($T:X\to X$) 是 contraction mapping，即存在 [ $$ 0\le \alpha<1 $$ ] 使得： [ $$ d(Tx,Ty)\le \alpha d(x,y), \qquad \forall x,y\in X. $$ ] 则： 1. 存在唯一 ($x^* \in X$)，满足 $$ x^*=Tx^*. $$ 2. 对任意初始点 ($x_0\in X$)，由 $$ x_{n+1}=Tx_n $$ 定义的序列收敛到 ($x^*$)。 3. 误差界为： $$ \boxed{ d(x_n,x^*)\le \frac{\alpha^n}{1-\alpha}d(x_1,x_0). } $$ Banach fixed-point theorem 的标准表述正是：完备度量空间上的 contraction 有唯一 fixed point，Picard iteration 从任意初始点收敛，并且有显式误差界。([Michael Loss's Home Page](https://loss.math.gatech.edu/16FALLTEA/NOTES/2completemetricspaces.pdf?utm_source=chatgpt.com "complete metric spaces and the contraction mapping")) --- ## 3.2 唯一性证明 假设存在两个不动点： $$ x^*=Tx^*, \qquad y^*=Ty^*. $$ 则： $$ d(x^*,y^*) = d(Tx^*,Ty^*) \le \alpha d(x^*,y^*). $$ 移项： $$ (1-\alpha)d(x^*,y^*)\le 0. $$ 因为： $$ 1-\alpha>0, \qquad d(x^*,y^*)\ge 0, $$ 只能有： [ $$ d(x^*,y^*)=0. $$ ] 由度量的正定性： [ $$ x^*=y^*. $$ ] 所以不动点唯一。 --- ## 3.3 存在性证明 取任意初始点： [ $$ x_0\in X. $$ ] 定义 Picard iteration： [ $$ x_{n+1}=Tx_n. $$ ] 先证明相邻项距离指数衰减： [ $$ \begin{aligned} d(x_{n+1},x_n) &= d(Tx_n,Tx_{n-1}) \\ &\le \alpha d(x_n,x_{n-1}). \end{aligned} $$ ] 递推得到： [ $$ d(x_{n+1},x_n) \le \alpha^n d(x_1,x_0). $$ ] 对任意 (m>n)，由三角不等式： [ $$ \begin{aligned} d(x_m,x_n) &\le d(x_m,x_{m-1}) + d(x_{m-1},x_{m-2}) +\cdots+ d(x_{n+1},x_n) \\ &\le \left( \alpha^{m-1} + \alpha^{m-2} + \cdots + \alpha^n \right)d(x_1,x_0) \\ &= \alpha^n \left( 1+\alpha+\cdots+\alpha^{m-n-1} \right)d(x_1,x_0) \\ &\le \frac{\alpha^n}{1-\alpha}d(x_1,x_0). \end{aligned} $$ ] 因为： [ $$ \alpha^n\to 0, $$ ] 所以对任意 ($\varepsilon>0$)，存在 ($N$)，当 ($m>n\ge N$) 时： [ $$ d(x_m,x_n)<\varepsilon. $$ ] 因此 ($\{x_n\}$) 是 Cauchy sequence。 由于 (X) 完备，存在 ($x^*\in X$)，使得： [ $$ x_n\to x^*. $$ ] 又因为 contraction mapping 必连续： [ $$ d(Tx_n,Tx^* )\le \alpha d(x_n,x^*)\to 0, $$ ] 所以： [ $$ Tx_n\to Tx^*. $$ ] 但： [ $$ x_{n+1}=Tx_n. $$ ] 且： [ $$ x_{n+1}\to x^*. $$ ] 因此极限唯一，得到： [ $$ x^*=Tx^*. $$ ] 所以不动点存在。 --- ## 3.4 误差界证明 由前面得到： [ $$ d(x_m,x_n) \le \frac{\alpha^n}{1-\alpha}d(x_1,x_0). $$ ] 令： [ $$ m\to\infty, $$ ] 因为： [ $$ x_m\to x^*, $$ ] 得到： [ $$ \boxed{ d(x^*,x_n) \le \frac{\alpha^n}{1-\alpha}d(x_1,x_0). } $$ ] 这就是 Banach theorem 的构造性意义：不仅证明存在唯一解，还给出收敛算法与误差上界。 --- # 4. Bellman operator 是 contraction 的典型例子 固定策略 ($\pi$) 下，Bellman operator 为： $$ (T^\pi v)(s) = r_\pi(s) + \gamma\sum_{s'}P_\pi(s'|s)v(s'). $$ 对任意两个价值函数 $(u,v)$，有： $$ \begin{aligned} |(T^\pi u)(s)-(T^\pi v)(s)| &= \left| \gamma \sum_{s'}P_\pi(s'|s) \bigl(u(s')-v(s')\bigr) \right| \\ &\le \gamma \sum_{s'}P_\pi(s'|s) |u(s')-v(s')| \\ &\le \gamma |u-v|_\infty \sum_{s'}P_\pi(s'|s) \\ &= \gamma |u-v|_\infty. \end{aligned} $$ 对所有 ($s$) 取 supremum： $$ \boxed{ |T^\pi u-T^\pi v|_\infty \le \gamma|u-v|_\infty. } $$ 当： [ $$ 0\le \gamma<1 $$ ] 时，($T^\pi$) 是 $\gamma$-contraction。 由 Banach theorem，Bellman 方程： [ $$ v=T^\pi v $$ ] 存在唯一解 ($v^\pi$)，并且 value iteration： [ $$ v_{k+1}=T^\pi v_k $$ ] 收敛到 ($v^\pi$)。Dvoretzky 随机逼近形式化证明论文也以 Bellman optimality operator 为强化学习中的 contraction 例子，说明 fixed-point iteration 与 stochastic approximation 的联系。([arXiv](https://arxiv.org/pdf/2202.05959?utm_source=chatgpt.com "Formalization of a Stochastic Approximation Theorem")) --- # 5. Robbins–Monro 定理与随机逼近 ## 5.1 Robbins–Monro 原问题 设存在未知函数： [ $$ M(x)=\mathbb E[Y(x)]. $$ ] 目标是求： [ $$ M(\theta)=a. $$ ] 等价地定义： [ $$ h(x)=M(x)-a, $$ ] 要求解： [ $$ h(\theta)=0. $$ ] 困难在于 ($M(x)$) 不能直接计算。给定 ($x_n$)，只能观测随机样本 ($Y_n$)，满足： [ $$ \mathbb E[Y_n\mid x_n]=M(x_n). $$ ] Robbins 和 Monro 1951 年论文提出的 stochastic approximation method 正是为了解决这种“回归函数未知，只能通过带噪声实验观测求根”的问题。([Columbia University](https://www.columbia.edu/~ww2040/8100F16/RM51.pdf?utm_source=chatgpt.com "A Stochastic Approximation Method")) --- ## 5.2 Robbins–Monro 更新 Robbins–Monro 递推为： # [ $$ \boxed{ x_{n+1} = x_n-a_n(Y_n-a). } $$ ] 因为： # [ $$ Y_n-a = M(x_n)-a+\xi_{n+1} = h(x_n)+\xi_{n+1}, $$ ] 其中： [ $$ \xi_{n+1}=Y_n-M(x_n) $$ ] 满足： [ $$ \mathbb E[\xi_{n+1}\mid\mathcal F_n]=0. $$ ] 于是递推可写为： # [ $$ \boxed{ x_{n+1} = x_n-a_n\bigl(h(x_n)+\xi_{n+1}\bigr). } $$ ] 这就是确定性求根迭代： [ $$ x_{n+1}=x_n-a_nh(x_n) $$ ] 的带噪声版本。 --- ## 5.3 步长条件 经典 Robbins–Monro 步长条件为： [ $$ \boxed{ a_n>0, \qquad \sum_{n=1}^{\infty}a_n=\infty, \qquad \sum_{n=1}^{\infty}a_n^2<\infty. } $$ ] 第一条： [ $$ \sum_n a_n=\infty $$ ] 表示总学习量不能有限，否则可能在到达根之前停止移动。 第二条： [ $$ \sum_n a_n^2<\infty $$ ] 表示噪声累计方差可控。 典型例子： [ $$ a_n=\frac1n. $$ ] 因为： [ $$ \sum_n\frac1n=\infty, \qquad \sum_n\frac1{n^2}<\infty. $$ ] Robbins–Monro 原文中即使用这类递减正步长条件来保证随机逼近序列收敛。([Columbia University](https://www.columbia.edu/~ww2040/8100F16/RM51.pdf?utm_source=chatgpt.com "A Stochastic Approximation Method")) --- # 6. Robbins–Monro 收敛定理：一种常用充分条件 下面给出一维 almost sure convergence 的常用版本。原始 Robbins–Monro 论文的表述主要是概率收敛；现代随机逼近理论通常在更强条件下给出几乎必然收敛。 设： # [ $$ x_{n+1} = x_n-a_n\bigl(h(x_n)+\xi_{n+1}\bigr). $$ ] 假设： 1. ($\theta$) 是唯一根： [ $$ h(\theta)=0. $$ ] 2. 稳定性条件成立： [ $$ (x-\theta)h(x)>0, \qquad x\ne\theta. $$ ] 直观含义是：如果 ($x>\theta$)，则 ($h(x)>0$)，更新会把 ($x$) 向左推；如果 ($x<\theta$)，则 ($h(x)<0$)，更新会把 ($x$) 向右推。 3. 噪声为 martingale difference： [ $$ \mathbb E[\xi_{n+1}\mid \mathcal F_n]=0. $$ ] 4. 条件二阶矩有界： [ $$ \mathbb E[\xi_{n+1}^2\mid\mathcal F_n]\le C(1+|x_n-\theta|^2). $$ ] 5. 步长满足： [ $$ \sum_n a_n=\infty, \qquad \sum_n a_n^2<\infty. $$ ] 6. 迭代序列有界，或通过投影 / Lyapunov 条件保证有界。 则： [ $$ \boxed{ x_n\to \theta \quad \text{almost surely}. } $$ ] --- ## 6.1 Robbins–Monro 证明 令误差： [ $$ e_n=x_n-\theta. $$ ] 由于 ($h(\theta)=0$)，递推为： $$ e_{n+1} = e_n-a_nh(x_n)-a_n\xi_{n+1}. $$ 考虑平方误差： $$ \begin{aligned} e_{n+1}^2 &= \left( e_n-a_nh(x_n)-a_n\xi_{n+1} \right)^2 \\ &= e_n^2 -2a_ne_nh(x_n) -2a_ne_n\xi_{n+1} +a_n^2\bigl(h(x_n)+\xi_{n+1}\bigr)^2. \end{aligned} $$ 对 ($\mathcal F_n$) 条件取期望。由于： [ $$ \mathbb E[\xi_{n+1}\mid\mathcal F_n]=0, $$ ] 有： # [ $$ \mathbb E[e_n\xi_{n+1}\mid\mathcal F_n] = e_n\mathbb E[\xi_{n+1}\mid\mathcal F_n]=0 $$ ] 因此： [ $$ \begin{aligned} \mathbb E[e_{n+1}^2\mid\mathcal F_n] &= e_n^2 -2a_ne_nh(x_n) +a_n^2\mathbb E[(h(x_n)+\xi_{n+1})^2\mid\mathcal F_n]. \end{aligned} $$ ] 在有界性和二阶矩条件下，存在常数 ($C'$)，使得： [ $$ \mathbb E[(h(x_n)+\xi_{n+1})^2\mid\mathcal F_n]\le C'. $$ ] 所以： [ $$ \boxed{ \mathbb E[e_{n+1}^2\mid\mathcal F_n] \le e_n^2 -2a_ne_nh(x_n) +C'a_n^2. } $$ ] 由于稳定性条件： [ $$ e_nh(x_n)\ge 0, $$ ] 得到： [ $$ \mathbb E[e_{n+1}^2\mid\mathcal F_n] \le e_n^2+C'a_n^2. $$ ] 因为： [ $$ \sum_n a_n^2<\infty, $$ ] 由非负 almost-supermartingale 收敛定理可得： [ $$ e_n^2 $$ ] 几乎必然收敛，并且： [ $$ \sum_n a_ne_nh(x_n)<\infty. $$ ] 现在证明极限只能为 0。 反设： [ $$ e_n^2\to L>0. $$ ] 则存在 ($\varepsilon>0$)，使得充分大 (n) 时： [ $$ |e_n|\ge \varepsilon. $$ ] 由于迭代有界，且 ($h$) 满足稳定性条件，在集合 [ $$ {x: |x-\theta|\ge \varepsilon,\ |x|\le B} $$ ] 上有： [ $$ (x-\theta)h(x)\ge c_\varepsilon>0. $$ ] 于是充分大 ($n$) 时： [ $$ e_nh(x_n)\ge c_\varepsilon. $$ ] 因此： $$ \sum_n a_ne_nh(x_n) \ge c_\varepsilon\sum_n a_n = \infty. $$ 这与： [ $$ \sum_n a_ne_nh(x_n)<\infty $$ ] 矛盾。 所以： [ $$ L=0. $$ ] 即： [ $$ e_n^2\to0, $$ ] 从而： [ $$ \boxed{ x_n\to\theta \quad \text{almost surely}. } $$ ] 这就是 Robbins–Monro 收敛证明的核心机制：负漂移项 [ $$ -2a_ne_nh(x_n) $$ ] 持续把误差拉向 0，而噪声项通过 [ $$ \sum a_n^2<\infty $$ ] 被压制。 --- # 7. Banach 与 Robbins–Monro 的关系 Banach 处理确定性 fixed-point iteration： [ $$ x_{n+1}=T(x_n). $$ ] Robbins–Monro 处理 noisy root-finding： [ $$ x_{n+1}=x_n-a_n(h(x_n)+\xi_{n+1}). $$ ] 如果要求解不动点： [ $$ x=T(x), $$ ] 可定义： [ $$ h(x)=x-T(x). $$ ] 则不动点问题等价于求根： [ $$ h(x)=0. $$ ] 若只能观测 ($T(x)$) 的带噪声估计： [ $$ \widehat T(x), \qquad \mathbb E[\widehat T(x)\mid x]=T(x), $$ ] 则可使用随机递推： $$ x_{n+1} = x_n+a_n\bigl(\widehat T(x_n)-x_n\bigr). $$ 这就是 noisy fixed-point iteration。 强化学习中的 Q-learning、TD learning 都可放入类似框架：Bellman operator 给出 deterministic target，采样 transition 给出 noisy Bellman target。Jaakkola、Jordan、Singh 的经典工作正是通过 stochastic approximation 理论建立 TD($(\lambda)$) 与 Q-learning 等动态规划型学习算法的收敛性。([NeurIPS Proceedings](https://proceedings.neurips.cc/paper/1993/file/5807a685d1a9ab3b599035bc566ce2b9-Paper.pdf?utm_source=chatgpt.com "Convergence of Stochastic Iterative Dynamic Programming ...")) --- # 8. Dvoretzky’s stochastic approximation theorem ## 8.1 定理定位 Dvoretzky 定理可以看成 Robbins–Monro 的抽象推广。它不局限于： [ $$ x_{n+1}=x_n-a_n(Y_n-a), $$ ] 而允许更一般的随机递推： # [ $$ X_{n+1} = T_n(X_1,\dots,X_n)+W_n. $$ ] 其中： - ($T_n$) 是依赖历史的确定性 / 可测主项； - ($W_n$) 是 martingale difference 噪声； - 目标是证明 ($X_n\to x^*$) almost surely。 Vajjha 等人的形式化证明论文说明，Dvoretzky 1956 年的随机逼近定理是一个一般收敛定理，能够推出 Robbins–Monro 与 Kiefer–Wolfowitz 等经典算法的收敛性。([arXiv](https://arxiv.org/pdf/2202.05959?utm_source=chatgpt.com "Formalization of a Stochastic Approximation Theorem")) --- ## 8.2 Dvoretzky 定理的一种常用形式 设 ($\{\mathcal F_n\}$) 是 filtration，($X_n$) 是 $\mathcal F_n$-measurable 随机变量。递推： # [ $$ \boxed{ X_{n+1} = T_n(X_1,\dots,X_n)+W_n. } $$ ] 目标点为： [ $$ x^*. $$ ] 假设： ### 噪声条件 [ $$ \boxed{ \mathbb E[W_n\mid\mathcal F_n]=0. } $$ ] 即 ($W_n$) 是 martingale difference。 并且： [ $$ \boxed{ \sum_{n=1}^\infty \mathbb E[W_n^2]<\infty. } $$ ] ### 确定性主项的收缩式条件 存在非负数列： [ $$ \alpha_n,\beta_n,\gamma_n\ge 0 $$ ] 满足： [ $$ \alpha_n\to0, $$ ] [ $$ \sum_n\beta_n<\infty, $$ ] [ $$ \sum_n\gamma_n=\infty. $$ ] 并且对所有历史路径，有： $$ |T_n(X_1,\dots,X_n)-x^*| \le \max \left\{ \alpha_n, (1+\beta_n)|X_n-x^* |-\gamma_n \right\}. $$ 则： $$ \boxed{ X_n\to x^* \quad \text{almost surely}. } $$ 该形式体现了 Dvoretzky 定理的核心结构：主项有持续向目标点收缩的漂移，允许可和的小扩张 ($\beta_n$)，允许趋零的误差地板 ($\alpha_n$)，并允许平方可和的 martingale 噪声。相关形式与完整形式化证明可见 Vajjha 等人的 Coq formalization 工作。([arXiv](https://arxiv.org/pdf/2202.05959?utm_source=chatgpt.com "Formalization of a Stochastic Approximation Theorem")) --- # 9. Dvoretzky 定理的证明思路 Dvoretzky 原定理的完整证明涉及测度论、martingale 收敛和随机序列控制。下面给出核心证明骨架。 令误差： $$ Z_n=|X_n-x^* |. $$ 递推给出： $$ X_{n+1}-x^* = T_n(X_1,\dots,X_n)-x^* + W_n. $$ 因此： [ $$ Z_{n+1} \le |T_n-x^* |+|W_n|. $$ ] 由主项条件： [ $$ |T_n-x^* | \le \max \left\{ \alpha_n, (1+\beta_n)Z_n-\gamma_n \right\}. $$ ] 所以： [ $$ Z_{n+1} \le \max \left\{ \alpha_n, (1+\beta_n)Z_n-\gamma_n \right\} + |W_n|. $$ ] 若暂时忽略噪声 (W_n)，则有确定性递推： [ $$ Z_{n+1} \le \max \left\{ \alpha_n, (1+\beta_n)Z_n-\gamma_n \right\}. $$ ] 由于： [ $$ \alpha_n\to0, $$ ] 误差地板消失； 由于： [ $$ \sum_n\beta_n<\infty, $$ ] 临时扩张总量有限； 由于： [ $$ \sum_n\gamma_n=\infty, $$ ] 朝目标的累计收缩无限大。 因此，确定性递推会迫使： [ $$ Z_n\to0. $$ ] 加入噪声后，关键是： $$ \mathbb E[W_n\mid\mathcal F_n]=0, \qquad \sum_n\mathbb E[W_n^2]<\infty. $$ 这说明噪声没有条件偏差，并且总二阶能量有限。由 martingale convergence 相关引理可得，噪声不会无限累积破坏收敛。Vajjha 等人的证明将这一部分形式化为 martingale 收敛、Borel–Cantelli 型控制以及一个确定性序列引理的组合。([arXiv](https://arxiv.org/pdf/2202.05959?utm_source=chatgpt.com "Formalization of a Stochastic Approximation Theorem")) 因此得到： [ $$ \boxed{ Z_n=|X_n-x^*|\to0 \quad\text{almost surely}. } $$ ] 也就是： [ $$ \boxed{ X_n\to x^* \quad\text{almost surely}. } $$ ] --- # 10. Robbins–Monro 是 Dvoretzky 的特例 Robbins–Monro 递推： # [ $$ x_{n+1} = x_n-a_n(h(x_n)+\xi_{n+1}) $$ ] 可以写为： # [ $$ x_{n+1} = \underbrace{x_n-a_nh(x_n)}_{T_n} + \underbrace{(-a_n\xi_{n+1})}_{W_n}. $$ ] 其中： [ $$ \mathbb E[\xi_{n+1}\mid\mathcal F_n]=0 $$ ] 推出： [ $$ \mathbb E[W_n\mid\mathcal F_n]=0. $$ ] 如果： [ $$ \mathbb E[\xi_{n+1}^2\mid\mathcal F_n]\le C $$ ] 且： [ $$ \sum_n a_n^2<\infty, $$ ] 则： # [ $$ \sum_n\mathbb E[W_n^2] = \sum_n a_n^2\mathbb E[\xi_{n+1}^2] \le C\sum_n a_n^2 <\infty. $$ ] 稳定性条件： [ $$ (x-\theta)h(x)>0 $$ ] 保证确定性主项： [ $$ T_n=x_n-a_nh(x_n) $$ ] 朝 (\theta) 产生负漂移。步长条件： [ $$ \sum_n a_n=\infty $$ ] 对应 Dvoretzky 条件中的累计收缩无限大。 所以 Robbins–Monro 可视为 Dvoretzky 定理的具体求根版本： [ $$ \boxed{ \text{Robbins--Monro 是具体算法；Dvoretzky theorem 是一般随机逼近收敛工具。} } $$ ] --- # 11. Dvoretzky 型定理在强化学习中的常用收缩版本 强化学习中常出现如下 noisy contraction recursion： # [ $$ \Delta_{t+1} = (1-\alpha_t)\Delta_t + \alpha_t F_t. $$ ] 其中 (\Delta_t) 是当前误差，例如： [ $$ \Delta_t=Q_t-Q^*. $$ ] 假设： [ $$ |\mathbb E[F_t\mid\mathcal F_t]| \le \gamma|\Delta_t|+c_t, \qquad 0\le\gamma<1, \qquad c_t\to0. $$ ] 并且： [ $$ \operatorname{Var}(F_t\mid\mathcal F_t) \le C(1+|\Delta_t|^2). $$ ] 步长满足： [ $$ \sum_t\alpha_t=\infty, \qquad \sum_t\alpha_t^2<\infty. $$ ] 则在适当有界性条件下： [ $$ \boxed{ \Delta_t\to0 \quad \text{almost surely}. } $$ ] 这类结论正是把 contraction mapping 与 stochastic approximation 结合起来。Jaakkola、Jordan、Singh 的随机迭代动态规划收敛定理用于证明 TD((\lambda)) 和 Q-learning 等算法的收敛性，核心就是 noisy dynamic programming update 在期望上具有 contraction-type drift。([NeurIPS Proceedings](https://proceedings.neurips.cc/paper/1993/file/5807a685d1a9ab3b599035bc566ce2b9-Paper.pdf?utm_source=chatgpt.com "Convergence of Stochastic Iterative Dynamic Programming ...")) --- ## 11.1 简化证明 设： $$ Z_t=|\Delta_t|^2. $$ 递推： $$ \Delta_{t+1} = (1-\alpha_t)\Delta_t+\alpha_tF_t. $$ 展开平方： $$ \begin{aligned} |\Delta_{t+1}|^2 &= |(1-\alpha_t)\Delta_t+\alpha_tF_t|^2 \\ &= (1-\alpha_t)^2|\Delta_t|^2 + 2\alpha_t(1-\alpha_t)\langle \Delta_t,F_t\rangle + \alpha_t^2|F_t|^2. \end{aligned} $$ 取条件期望。若期望漂移满足收缩性质，则可得到形如： $$ \mathbb E[Z_{t+1}\mid\mathcal F_t] \le \left( 1-c\alpha_t+C\alpha_t^2 \right)Z_t + C\alpha_t^2 + o(\alpha_t), $$ 其中： [ $$ c>0. $$ ] 由于： [ $$ \sum_t\alpha_t=\infty, \qquad \sum_t\alpha_t^2<\infty, $$ ] 应用 supermartingale convergence lemma 得到： [ $$ Z_t $$ ] 几乎必然收敛，并且： [ $$ \sum_t\alpha_tZ_t<\infty. $$ ] 若极限 (Z_\infty>0)，则由于： [ $$ \sum_t\alpha_t=\infty, $$ ] 会导致： [ $$ \sum_t\alpha_tZ_t=\infty, $$ ] 矛盾。因此： [ $$ Z_\infty=0. $$ ] 所以： [ $$ \boxed{ \Delta_t\to0 \quad \text{almost surely}. } $$ ] 这正是 noisy contraction fixed-point iteration 的基本证明模式：确定性 contraction 提供负漂移，Robbins–Monro 步长压制噪声，Dvoretzky 型定理保证几乎必然收敛。 --- # 12. 四者在强化学习中的统一解释 以 Bellman optimality operator 为例： $$ (T^*Q)(s,a)= \mathbb E \left[ R_{t+1} + \gamma\max_{a'}Q(S_{t+1},a') \mid S_t=s,A_t=a \right]. $$ 在 sup norm 下： [ \boxed{ |T^*Q-T^*Q'|_\infty \le \gamma|Q-Q'|_\infty. } ] 所以 (T^*) 是 contraction。 由 Banach theorem： $$ Q^*=T^*Q^* $$ 存在唯一解，并且确定性 value iteration： [ $$ Q_{k+1}=T^*Q_k $$ ] 收敛到 (Q^*)。 Q-learning 的实际更新使用采样 Bellman target： $$ Q_{t+1}(S_t,A_t) = Q_t(S_t,A_t) + \alpha_t \left[ R_{t+1} + \gamma\max_{a'}Q_t(S_{t+1},a') Q_t(S_t,A_t) \right]. $$ 这是： [ $$ Q_{t+1}=Q_t+\alpha_t(\widehat T_tQ_t-Q_t) $$ ] 的随机版本，其中： $$ \mathbb E[\widehat T_tQ_t\mid\mathcal F_t]=T^*Q_t. $$ ] 因此： [ $$ \boxed{ \text{Banach theorem 处理无噪声 Bellman iteration；Robbins--Monro / Dvoretzky 处理采样噪声下的 Bellman iteration。} } $$ ] --- # 13. 总结 **Contraction mapping**： $$ \boxed{ d(Tx,Ty)\le\alpha d(x,y),\quad \alpha<1. } $$ 含义：映射每次作用都会缩小距离。 **Banach fixed-point theorem**： [ $$ \boxed{ \text{完备度量空间上的 contraction 有唯一不动点，且 }x_{n+1}=Tx_n\text{ 收敛到该点。} } $$ ] 证明核心：相邻迭代距离几何衰减，序列为 Cauchy；完备性给出极限；连续性给出 fixed point；收缩性给出唯一性。 **Robbins–Monro 定理**： $$ \boxed{ x_{n+1}=x_n-a_n(h(x_n)+\xi_{n+1}) } $$ 在稳定根、martingale difference noise、二阶矩有界和步长条件 [ $$ \sum a_n=\infty, \qquad \sum a_n^2<\infty $$ ] 下收敛到根。证明核心是平方误差的负漂移： [ $$ -2a_n(x_n-\theta)h(x_n) $$ ] 压倒平方可和噪声项。 **Dvoretzky stochastic approximation theorem**： $$ \boxed{ X_{n+1}=T_n(X_1,\dots,X_n)+W_n } $$ 在主项持续向目标点收缩、噪声为 martingale difference 且平方可和时，得到： $$ X_n\to x^* \quad\text{almost surely}. $$ 其作用是提供比 Robbins–Monro 更抽象的一般随机逼近收敛框架。 最终关系可以写成： $$ \boxed{ \text{Banach fixed-point theorem} = \text{确定性收缩迭代收敛理论。} } $$ $$ \boxed{ \text{Robbins--Monro} = \text{带无偏噪声的求根迭代收敛理论。} } $$ $$ \boxed{ \text{Dvoretzky theorem} = \text{更一般的随机递推几乎必然收敛理论。} } $$ $$ \boxed{ \text{强化学习中的 TD/Q-learning 收敛证明，通常正是 contraction mapping + stochastic approximation 的结合。} } $$ ] --- 下面默认把 **Dvoretzky’s theorem** 解释为**随机逼近理论中的 Dvoretzky 定理**，即 Aryeh Dvoretzky 1956 年 _On Stochastic Approximation_ 中的收敛定理；不是凸几何中关于高维凸体截面的 Dvoretzky theorem。随机逼近版本的 Dvoretzky theorem 是 Robbins–Monro、Kiefer–Wolfowitz，以及许多强化学习随机迭代收敛证明的抽象基础。Vajjha 等人的形式化证明论文明确说明，他们形式化的是 Dvoretzky 1956 年关于 stochastic approximation 的结果，并给出了 regular Dvoretzky theorem 的完整假设形式。([arXiv](https://arxiv.org/pdf/2202.05959 "Formalization of a Stochastic Approximation Theorem")) --- # 0. 四个概念的总关系 四者可以按如下逻辑理解： $$ \boxed{ \text{contraction mapping} \Rightarrow \text{Banach fixed-point theorem} \Rightarrow \text{noisy fixed-point iteration} \Rightarrow \text{Robbins--Monro / Dvoretzky stochastic approximation} } $$ 更具体地： [ $$ \text{contraction mapping} $$ ] 是一种映射性质； [ $$ \text{Banach fixed-point theorem} $$ ] 说明这种映射有唯一不动点，并且反复迭代收敛； [ $$ \text{Robbins--Monro} $$ ] 把“确定性求根”推广到“只能看到有噪声样本”的情形； [ $$ \text{Dvoretzky theorem} $$ ] 把 Robbins–Monro 这类随机逼近进一步抽象为一般随机递推的几乎必然收敛定理。Vajjha 等人也指出，Dvoretzky 允许下一步估计由完整历史和当前样本共同决定，而 Robbins–Monro 是其中一个特殊情形。([arXiv](https://arxiv.org/pdf/2202.05959 "Formalization of a Stochastic Approximation Theorem")) --- # 1. Contraction mapping：收缩映射 ## 1.1 定义 设 ($(X,d)$) 是度量空间。映射 $$ T:X\to X $$ 称为 **contraction mapping**，如果存在常数 [ $$ 0\le c<1 $$ ] 使得对所有 ($x,y\in X$)，都有 [ $$ \boxed{ d(Tx,Ty)\le c,d(x,y). } $$ ] 其中 (c) 称为 contraction modulus。 这个条件比一般 Lipschitz 连续更强。若只满足 [ $$ d(Tx,Ty)\le d(x,y), $$ ] 也就是 ($c=1$)，则只能称为 non-expansive mapping，不足以保证唯一不动点或迭代收敛。Banach 定理的教材材料也明确要求存在 ($K<1$)，而不是 ($K=1$)。 --- ## 1.2 不动点 点 ($x^*\in X$) 称为 ($T$) 的 fixed point，如果 $$ \boxed{ Tx^*=x^* } $$ 求解很多方程都可以转化为求不动点。例如： [ $$ x=f(x) $$ ] 本身就是不动点问题。强化学习中的 Bellman 方程： [ $$ v=T^\pi v $$ ] 也是不动点方程。 --- ## 1.3 收缩映射的基本误差性质 若 ($x^*$) 是不动点，则： $$ x^* =Tx^* . $$ 对迭代 [ $$ x_{n+1}=Tx_n, $$ ] 有： [ $$ \begin{aligned} d(x_{n+1},x^*) &= d(Tx_n,Tx^*) \\ &\le c,d(x_n,x^*). \end{aligned} $$ ] 递推得到： [ $$ \boxed{ d(x_n,x^*)\le c^n d(x_0,x^*). } $$ ] 因此只要不动点存在，收缩映射迭代会以几何速度逼近该不动点。 但是，存在性和唯一性还需要额外条件：空间必须是**完备度量空间**。这正是 Banach fixed-point theorem 的内容。 --- # 2. Banach fixed-point theorem ## 2.1 定理陈述 设 ($(X,d)$) 是非空完备度量空间，($T:X\to X$) 是 contraction mapping，即存在 ($0\le c<1$)，使得： [ $$ d(Tx,Ty)\le c,d(x,y), \qquad \forall x,y\in X. $$ ] 则： 1. 存在唯一 ($x^*\in X$)，满足 [ $$ Tx^*=x^*. $$ ] 2. 对任意初始点 ($x_0\in X$)，迭代 [ $$ x_{n+1}=Tx_n $$ ] 收敛到 ($x^*$)。 3. 有误差界： [ $$ \boxed{ d(x_n,x^*)\le \frac{c^n}{1-c}d(x_1,x_0). } $$ ] Banach 定理的标准表述正是：完备度量空间上的 contraction 有唯一 fixed point，并且迭代过程给出构造性近似和误差界。 --- ## 2.2 唯一性证明 假设存在两个不动点： [ $$ x^*=Tx^*, \qquad y^*=Ty^*. $$ ] 由 contraction 性质： # [ $$ d(x^*,y^*) = d(Tx^*,Ty^*) \le c,d(x^*,y^*). $$ ] 移项： [ $$ (1-c)d(x^*,y^*)\le 0. $$ ] 由于： [ $$ 1-c>0, \qquad d(x^*,y^*)\ge 0, $$ ] 只能有： [ $$ d(x^*,y^*)=0. $$ ] 由度量正定性： [ $$ x^*=y^*. $$ ] 所以不动点唯一。 --- ## 2.3 存在性证明 任取 ($x_0\in X$)，定义： [ $$ x_{n+1}=Tx_n. $$ ] 先证明 ($\{x_n\}$) 是 **Cauchy sequence**。 由 contraction 性质： [ $$ \begin{aligned} d(x_{n+1},x_n) &= d(Tx_n,Tx_{n-1}) \\ &\le cd(x_n,x_{n-1}). \end{aligned} $$ ] 递推： [ $$ d(x_{n+1},x_n) \le c^n d(x_1,x_0). $$ ] 对 ($m>n$)，由三角不等式： [ $$ \begin{aligned} d(x_m,x_n) &\le d(x_m,x_{m-1}) + d(x_{m-1},x_{m-2}) +\cdots+ d(x_{n+1},x_n) \\ &\le \left(c^{m-1}+c^{m-2}+\cdots+c^n\right)d(x_1,x_0) \\ &= c^n(1+c+\cdots+c^{m-n-1})d(x_1,x_0) \\ &\le \frac{c^n}{1-c}d(x_1,x_0). \end{aligned} $$ ] 因为 ($0\le c<1$)，所以： [ $$ \frac{c^n}{1-c}d(x_1,x_0)\to0. $$ ] 因此对任意 ($\varepsilon>0$)，存在 ($N$)，当 ($m>n\ge N$) 时： [ $$ d(x_m,x_n)<\varepsilon. $$ ] 所以 ($\{x_n\}$) 是 **Cauchy sequence**。 由于 ($X$) 完备，存在 ($x^*\in X$)，使得： [ $$ x_n\to x^*. $$ ] 接下来证明 ($x^*$) 是不动点。由于 ($T$) 是 contraction，必连续： [ $$ d(Tx_n,Tx^*)\le c,d(x_n,x^*)\to0. $$ ] 所以： [ $$ Tx_n\to Tx^*. $$ ] 但： [ $$ x_{n+1}=Tx_n. $$ ] 又因为 ($x_{n+1}\to x^*$)，极限唯一，所以： [ $$ Tx^*=x^*. $$ ] 因此不动点存在。 --- ## 2.4 误差界证明 前面已经得到： $$ d(x_m,x_n) \le \frac{c^n}{1-c}d(x_1,x_0). $$ 令 ($m\to\infty$)，由于 $x_m\to x^*$，得到： $$ \boxed{ d(x^*,x_n) \le \frac{c^n}{1-c}d(x_1,x_0). } $$ 也可得到 posterior bound： $$ \boxed{ d(x_n,x^*) \le \frac{c}{1-c}d(x_{n-1},x_n). } $$ 教材材料也给出这两个误差估计：prior estimate 和 posterior estimate。 --- # 3. Bellman operator 作为 contraction mapping 固定策略 ($\pi$) 下，Bellman operator 为： $$ (T^\pi v)(s) = r_\pi(s) + \gamma\sum_{s'}P_\pi(s'|s)v(s'). $$ 对任意 $(u,v)$，有： $$ \begin{aligned} |(T^\pi u)(s)-(T^\pi v)(s)| &= \left| \gamma\sum_{s'}P_\pi(s'|s)(u(s')-v(s')) \right| \\ &\le \gamma\sum_{s'}P_\pi(s'|s)|u(s')-v(s')| \\ &\le \gamma|u-v|_\infty \sum_{s'}P_\pi(s'|s) \\ &= \gamma|u-v|_\infty. \end{aligned} $$ 对所有 ($s$) 取最大： $$ \boxed{ |T^\pi u-T^\pi v|_\infty \le \gamma|u-v|_\infty. } $$ 因此，当 [ $$ 0\le\gamma<1 $$ ] 时，($T^\pi$) 是 $\gamma-contraction$。 由 Banach fixed-point theorem，Bellman 方程 [ $$ v=T^\pi v $$ ] 有唯一解 ($v^\pi$)，且迭代 [ $$ v_{k+1}=T^\pi v_k $$ ] 收敛到 ($v^\pi$)。 这就是动态规划与强化学习中 Bellman 收敛理论的数学底座：Bellman operator 的 contraction 性质给出唯一 fixed point 和确定性 value iteration 的收敛。 --- # 4. Robbins–Monro 定理 ## 4.1 原问题 Robbins–Monro stochastic approximation 的原问题是：有未知函数 [ $$ M(x)=\mathbb E[Y(x)], $$ ] 目标是求解： [ $$ M(\theta)=a. $$ ] 即： [ $$ h(\theta)=0, \qquad h(x):=M(x)-a. $$ ] 困难在于 ($M(x)$) 不能直接计算。给定 ($x_n$)，只能观测随机变量 ($Y_n$)，满足： [ $$ \mathbb E[Y_n\mid x_n]=M(x_n). $$ ] Robbins 和 Monro 原文正是设 ($M(x)$) 为某实验响应在 level $x$ 处的期望，($M$) 未知，目标是通过 sequential experiments 找到 ($M(x)=a$) 的解。([Columbia University](https://www.columbia.edu/~ww2040/8100F16/RM51.pdf "A Stochastic Approximation Method")) --- ## 4.2 Robbins–Monro 递推 Robbins–Monro 更新为： [ $$ \boxed{ x_{n+1}=x_n-a_n(Y_n-a). } $$ ] 令： [ $$ \xi_{n+1}=Y_n-M(x_n). $$ ] 则： [ $$ \mathbb E[\xi_{n+1}\mid\mathcal F_n]=0. $$ ] 又因为： [ $$ Y_n-a=M(x_n)-a+\xi_{n+1}=h(x_n)+\xi_{n+1}, $$ ] 所以递推可写为： [ $$ \boxed{ x_{n+1}=x_n-a_n\bigl(h(x_n)+\xi_{n+1}\bigr). } $$ ] 这就是确定性求根迭代 [ $$ x_{n+1}=x_n-a_nh(x_n) $$ ] 的带噪声版本。 原文中也给出递推形式 ($x_{n+1}-x_n=a_n(a-Y_n)$)，并讨论 ($Y_n$) 的条件分布由当前 ($x_n$) 决定。([Columbia University](https://www.columbia.edu/~ww2040/8100F16/RM51.pdf "A Stochastic Approximation Method")) --- ## 4.3 步长条件 经典步长条件为： [ $$ \boxed{ a_n>0, \qquad \sum_{n=1}^\infty a_n=\infty, \qquad \sum_{n=1}^\infty a_n^2<\infty. } $$ ] 含义： [ $$ \sum a_n=\infty $$ ] 保证总修正量足够大，不会过早停止； [ $$ \sum a_n^2<\infty $$ ] 保证噪声的累计方差有限。 原始 Robbins–Monro 论文使用类似 ($a_n$) 的平方和有限以及 ($a_n$) 总和发散的条件；后续随机逼近文献通常把这写为 ($a_n\to0,\sum a_n=\infty,\sum a_n^2<\infty$)。Vajjha 等人的论文也概括了 Robbins–Monro 对学习率序列的三个条件，并说明 ($a_n=1/(n+1)$) 满足这些条件。([Columbia University](https://www.columbia.edu/~ww2040/8100F16/RM51.pdf "A Stochastic Approximation Method")) --- ## 4.4 一个常用的一维 almost sure 收敛定理 下面给出比原始 Robbins–Monro 更适合现代随机逼近分析的一维充分条件版本。 设： # [ $$ x_{n+1} = x_n-a_n(h(x_n)+\xi_{n+1}). $$ ] 假设： 1. 唯一根： [ $$ h(\theta)=0. $$ ] 2. 强单调稳定性： [ $$ \boxed{ (x-\theta)h(x)\ge \mu (x-\theta)^2, \qquad \mu>0. } $$ ] 3. 增长有界： [ $$ \boxed{ |h(x)|\le L|x-\theta|. } $$ ] 4. 噪声为 martingale difference： [ $$ \boxed{ \mathbb E[\xi_{n+1}\mid\mathcal F_n]=0. } $$ ] 5. 条件二阶矩有界： [ $$ \boxed{ \mathbb E[\xi_{n+1}^2\mid\mathcal F_n]\le \sigma^2+C(x_n-\theta)^2. } $$ ] 6. 步长满足： [ $$ \sum_n a_n=\infty, \qquad \sum_n a_n^2<\infty. $$ ] 则： [ $$ \boxed{ x_n\to\theta \quad\text{almost surely}. } $$ ] --- ## 4.5 Robbins–Monro 收敛证明 令误差： [ $$ e_n=x_n-\theta. $$ ] 由于 ($h(\theta)=0$)，递推为： # [ $$ e_{n+1} = e_n-a_nh(x_n)-a_n\xi_{n+1}. $$ ] 考虑平方误差： [ $$ \begin{aligned} e_{n+1}^2 &= \left(e_n-a_nh(x_n)-a_n\xi_{n+1}\right)^2 \\ &= e_n^2 -2a_ne_nh(x_n) -2a_ne_n\xi_{n+1} +a_n^2(h(x_n)+\xi_{n+1})^2. \end{aligned} $$ ] 对 ($\mathcal F_n$) 条件取期望。因为： [ $$ \mathbb E[\xi_{n+1}\mid\mathcal F_n]=0, $$ ] 所以： [ $$ \mathbb E[e_n\xi_{n+1}\mid\mathcal F_n]=0. $$ ] 于是： [ $$ \begin{aligned} \mathbb E[e_{n+1}^2\mid\mathcal F_n] &= e_n^2 -2a_ne_nh(x_n) +a_n^2\mathbb E[(h(x_n)+\xi_{n+1})^2\mid\mathcal F_n]. \end{aligned} $$ ] 由强单调性： $$ e_nh(x_n) = (x_n-\theta)h(x_n) \ge \mu e_n^2. $$ 又由增长条件和噪声二阶矩条件，存在常数 (K_1,K_2)，使得： [ $$ \mathbb E[(h(x_n)+\xi_{n+1})^2\mid\mathcal F_n] \le K_1 e_n^2+K_2. $$ ] 因此： [ $$ \begin{aligned} \mathbb E[e_{n+1}^2\mid\mathcal F_n] &\le e_n^2 -2\mu a_ne_n^2 +a_n^2(K_1e_n^2+K_2) \\ &= (1-2\mu a_n+K_1a_n^2)e_n^2 + K_2a_n^2. \end{aligned} $$ ] 因为 ($a_n\to0$)，存在 ($N$)，当 ($n\ge N$) 时： [ $$ K_1a_n^2\le \mu a_n. $$ ] 于是： $$ \mathbb E[e_{n+1}^2\mid\mathcal F_n] \le (1-\mu a_n)e_n^2+K_2a_n^2. $$ 令： [ $$ Z_n=e_n^2. $$ ] 得到： [ $$ \boxed{ \mathbb E[Z_{n+1}\mid\mathcal F_n] \le (1-\mu a_n)Z_n+K_2a_n^2. } $$ ] 使用 Robbins–Siegmund almost-supermartingale lemma，可得： 1. ($Z_n$) 几乎必然收敛； 2. ($\sum_n a_n Z_n<\infty$)。 由于： [ $$ \sum_n a_n=\infty, $$ ] 若 ($Z_n\to Z_\infty>0$)，则充分大 ($n$) 后 ($Z_n\ge Z_\infty/2$)，从而： [ $$ \sum_n a_nZ_n=\infty, $$ ] 矛盾。因此： [ $$ Z_\infty=0. $$ ] 所以： [ $$ e_n^2\to0, $$ ] 即： [ $$ \boxed{ x_n\to\theta \quad\text{almost surely}. } $$ ] 这个证明展示了 Robbins–Monro 的核心数学机制： 负漂移项 [ $$ -2a_ne_nh(x_n) $$ ] 持续降低误差；噪声项通过 [ $$ \sum a_n^2<\infty $$ ] 被控制。 --- # 5. Dvoretzky’s stochastic approximation theorem ## 5.1 定理定位 Dvoretzky theorem 是更抽象的随机逼近定理。Robbins–Monro 的递推只依赖上一点 ($x_n$) 和当前样本 ($Y_n$)，而 Dvoretzky 允许下一步由整个历史 ($x_1,\dots,x_n$) 决定。Vajjha 等人概括 Dvoretzky 的一般化：($x_{n+1}$) 可以由完整历史和当前样本共同决定，并可写作 ($x_{n+1}=T_n(x_1,\dots,x_n)+W_n$)，其中噪声满足条件期望为 0。([arXiv](https://arxiv.org/pdf/2202.05959 "Formalization of a Stochastic Approximation Theorem")) --- ## 5.2 Regular Dvoretzky theorem：定理陈述 设： [ $$ (\Omega,\mathcal F,\mathbb P) $$ ] 是概率空间， [ $$ \mathcal F_1\subseteq \mathcal F_2\subseteq\cdots $$ ] 是 filtration。 令 ($X_n$) 是 $\mathcal F_n$-measurable 的实值随机变量。递推为： [ $$ \boxed{ X_{n+1}=T_n(X_1,\dots,X_n)+W_n. } $$ ] 其中 ($W_n$) 是 $\mathcal F_{n+1}$-measurable，并满足： [ $$ \boxed{ \mathbb E[W_n\mid\mathcal F_n]=0. } $$ ] 以及： [ $$ \boxed{ \sum_{n=1}^{\infty}\mathbb E[W_n^2]<\infty. } $$ ] 存在非负数列： [ $$ \alpha_n,\beta_n,\gamma_n\ge0 $$ ] 满足： [ $$ \alpha_n\to0, $$ ] [ $$ \sum_n\beta_n<\infty, $$ ] [ $$ \sum_n\gamma_n=\infty. $$ ] 并且存在 ($x^*\in\mathbb R$)，使得对所有 ($n$) 和所有历史 ($x_1,\dots,x_n$)： $$ \boxed{ |T_n(x_1,\dots,x_n)-x^*| \le \max\left\{ \alpha_n,, (1+\beta_n)|x_n-x^*|-\gamma_n \right\}. } $$ 则： $$ \boxed{ X_n\to x^* \quad\text{almost surely}. } $$ ] 这就是 Vajjha 等人列出的 regular Dvoretzky theorem 的核心假设与结论。([arXiv](https://arxiv.org/pdf/2202.05959 "Formalization of a Stochastic Approximation Theorem")) --- ## 5.3 条件含义 ### 5.3.1 ($W_n$) 是无偏噪声 [ $$ \mathbb E[W_n\mid\mathcal F_n]=0. $$ ] 表示在给定历史后，噪声无系统偏差。 --- ### 5.3.2 噪声平方能量有限 [ $$ \sum_n \mathbb E[W_n^2]<\infty. $$ ] 这保证噪声不会无限积累。若 ($W_n=a_n\xi_{n+1}$)，且 ($\xi_{n+1}$) 条件二阶矩有界，则该条件由 [ $$ \sum_n a_n^2<\infty $$ ] 保证。 --- ### 5.3.3 ($\alpha_n\to0$) ($\alpha_n$) 是允许的误差地板，最终必须消失。 --- ### 5.3.4 ($\sum\beta_n<\infty$) ($\beta_n$) 表示允许的临时扩张： [ $$ (1+\beta_n)|x_n-x^*|. $$ ] 总扩张必须有限。 --- ### 5.3.5 ($\sum\gamma_n=\infty$) ($\gamma_n$) 表示朝 ($x^*$) 的收缩量。累计收缩必须无限大。 --- # 6. Dvoretzky theorem 的证明结构 完整原始证明较长。下面给出 regular scalar 版本的严谨证明主链。证明依赖两个标准引理：martingale noise 控制引理和确定性收缩序列引理；Dvoretzky 证明文献也说明 Derman–Sacks 简化证明使用条件 Kolmogorov 定律、Chebyshev inequality、Borel–Cantelli lemma，以及 ($\alpha_n,\beta_n,\gamma_n$) 的 bounding-series 操作。([arXiv](https://arxiv.org/pdf/2202.05959 "Formalization of a Stochastic Approximation Theorem")) --- ## 6.1 引理一：平方可和 martingale difference 的收敛控制 设： [ $$ \mathbb E[W_n\mid\mathcal F_n]=0, \qquad \sum_n\mathbb E[W_n^2]<\infty. $$ ] 定义 martingale： [ $$ M_N=\sum_{n=1}^N W_n. $$ ] 则： [ $$ M_N $$ ] 在 ($L^2$) 中 Cauchy，并且几乎必然收敛。 证明： 当 (m>n) 时， [ $$ M_m-M_n=\sum_{k=n+1}^m W_k. $$ ] 由于 ($W_k$) 是 martingale difference，交叉项期望为 0： [ $$ \mathbb E[W_iW_j]=0,\qquad i\ne j. $$ ] 因此： # [ $$ \mathbb E[(M_m-M_n)^2] = \sum_{k=n+1}^m\mathbb E[W_k^2]. $$ ] 由于： [ $$ \sum_k\mathbb E[W_k^2]<\infty, $$ ] 尾和趋于 0，所以 ($M_N$) 在 ($L^2$) 中 Cauchy。 由 martingale convergence theorem，($M_N$) 几乎必然收敛。于是噪声累计和不会破坏收敛趋势。 --- ## 6.2 引理二：确定性 Dvoretzky 型收缩序列 设非负序列 ($z_n$) 满足： $$ z_{n+1} \le \max\left\{ \alpha_n, (1+\beta_n)z_n-\gamma_n \right\} +\varepsilon_n, $$ 其中： [ $$ \alpha_n\to0, \qquad \sum_n\beta_n<\infty, \qquad \sum_n\gamma_n=\infty, \qquad \varepsilon_n\to0 $$ ] 并且扰动由平方可和 martingale 控制，使得其长期累计影响有限，则： [ $$ z_n\to0. $$ ] 证明思想如下。 若 ($z_n$) 不趋于 0，则存在 ($\eta>0$) 和无穷多个 ($n$)，使得： [ $$ z_n\ge \eta. $$ ] 由于： [ $$ \alpha_n\to0, \qquad \varepsilon_n\to0, $$ ] 充分大 ($n$) 时： [ $$ \alpha_n<\eta/4, \qquad |\varepsilon_n|<\eta/4. $$ ] 当 ($z_n\ge \eta$) 且充分大时，主递推的第二项主导： [ $$ z_{n+1} \lesssim (1+\beta_n)z_n-\gamma_n+\varepsilon_n. $$ ] ($\sum\beta_n<\infty$) 表示扩张总量有限，而 ($\sum\gamma_n=\infty$) 表示负漂移累计无限大。因此若误差长期保持在 ($\eta$) 以上，累计负漂移会超过所有有限扩张与噪声扰动，导致 ($z_n$) 最终变成负数。这与 ($z_n\ge0$) 矛盾。 因此： [ $$ z_n\to0. $$ ] 该引理本质上是 Dvoretzky bounding-series 证明的确定性核心。 --- ## 6.3 Dvoretzky theorem 证明 令： [ $$ Z_n=|X_n-x^*|. $$ ] 递推为： # [ $$ X_{n+1}-x^* = T_n(X_1,\dots,X_n)-x^* + W_n. $$ ] 因此： [ $$ Z_{n+1} \le |T_n(X_1,\dots,X_n)-x^*| + |W_n|. $$ ] 由 Dvoretzky 条件： [ $$ |T_n(X_1,\dots,X_n)-x^*| \le \max\left\{ \alpha_n, (1+\beta_n)Z_n-\gamma_n \right\}. $$ ] 所以： [ $$ Z_{n+1} \le \max\left\{ \alpha_n, (1+\beta_n)Z_n-\gamma_n \right\} + |W_n|. $$ ] 由引理一，martingale difference noise 的累计影响被控制；由引理二，确定性递推在 ($\alpha_n\to0$)、($\sum\beta_n<\infty$)、($\sum\gamma_n=\infty$) 条件下只能收敛到 0。因此： [ $$ Z_n\to0 \quad\text{almost surely}. $$ ] 也就是： [ $$ \boxed{ X_n\to x^* \quad\text{almost surely}. } $$ ] 这就是 regular Dvoretzky theorem 的收敛机制。 --- # 7. Robbins–Monro 是 Dvoretzky 的特例 Robbins–Monro 递推： $$ x_{n+1} = x_n-a_n(h(x_n)+\xi_{n+1}) $$ ] 可写成： # [ $$ x_{n+1} = \underbrace{x_n-a_nh(x_n)}_{T_n(x_1,\dots,x_n)} + \underbrace{(-a_n\xi_{n+1})}_{W_n}. $$ ] 于是： [ $$ T_n(x_1,\dots,x_n)=x_n-a_nh(x_n). $$ ] 如果： [ $$ \mathbb E[\xi_{n+1}\mid\mathcal F_n]=0, $$ ] 则： [ $$ \mathbb E[W_n\mid\mathcal F_n]=0. $$ ] 如果： [ $$ \mathbb E[\xi_{n+1}^2\mid\mathcal F_n]\le C, \qquad \sum_n a_n^2<\infty, $$ ] 则： # [ $$ \sum_n\mathbb E[W_n^2] = \sum_n a_n^2\mathbb E[\xi_{n+1}^2] \le C\sum_n a_n^2 <\infty. $$ ] 若 (h) 对根 (\theta) 具有稳定性，即： [ $$ (x-\theta)h(x)>0, \qquad x\ne\theta, $$ ] 则确定性部分： [ $$ x_n-a_nh(x_n) $$ ] 会把 ($x_n$) 朝 ($\theta$) 拉回。通过构造相应的 ($\alpha_n,\beta_n,\gamma_n$)，即可验证 Dvoretzky 条件。 Vajjha 等人也明确写出 Robbins–Monro 过程是 Dvoretzky 过程的 specialization，并给出对应关系： $$ T(x_1,\dots,x_n)=x_n+a_n(b-M(x_n)), \qquad W_n=a_n(M(x_n)-Y_n). $$ ([arXiv](https://arxiv.org/pdf/2202.05959 "Formalization of a Stochastic Approximation Theorem")) 因此： $$ \boxed{ \text{Robbins--Monro 是具体随机求根算法；Dvoretzky theorem 是覆盖它的抽象收敛定理。} } $$ --- # 8. 与强化学习收敛证明的关系 强化学习中的 Bellman update 通常形如： # [ $$ Q_{t+1} = Q_t+\alpha_t(\widehat T_tQ_t-Q_t), $$ ] 其中 ($\widehat T_tQ_t$) 是**采样 Bellman target**。 条件期望满足： $$ \mathbb E[\widehat T_tQ_t\mid\mathcal F_t] = TQ_t. $$ 如果 (T) 是 contraction，例如 Bellman optimality operator 在 ($|\cdot|_\infty$) 下为 $\gamma$-contraction，则确定性迭代： [ $$ Q_{k+1}=TQ_k $$ ] 由 Banach theorem 收敛。 带采样噪声的递推则需要 Robbins–Monro / Dvoretzky / stochastic approximation 工具处理。Jaakkola、Jordan、Singh 的经典论文把 DP-based learning algorithms 与 stochastic approximation 关联，并建立能覆盖 TD($(\lambda)$) 和 Q-learning 的收敛定理。([NeurIPS Proceedings](https://proceedings.neurips.cc/paper/1993/file/5807a685d1a9ab3b599035bc566ce2b9-Paper.pdf "Convergence of Stochastic Iterative Dynamic Programming Algorithms")) 因此 RL 收敛证明的典型结构是： $$ \boxed{ \text{Bellman operator 是 contraction} + \text{采样噪声是 martingale difference} + \text{学习率满足 Robbins--Monro 条件} \Rightarrow \text{随机迭代收敛。} } $$ --- # 9. 最终总结 ## 9.1 Contraction mapping [ $$ \boxed{ d(Tx,Ty)\le c,d(x,y),\qquad c<1. } $$ ] 含义：映射 (T) 严格缩小任意两点距离。 --- ## 9.2 Banach fixed-point theorem 若 ($T$) 是完备度量空间上的 contraction，则： [ $$ \boxed{ \exists!\ x^*:Tx^*=x^* } $$ ] 且： [ $$ \boxed{ x_{n+1}=Tx_n\to x^*. } $$ ] 证明核心： 1. contraction 使相邻距离几何衰减； 2. 迭代序列 Cauchy； 3. 完备性给出极限； 4. 连续性给出 fixed point； 5. contraction 给出唯一性。 --- ## 9.3 Robbins–Monro 随机求根递推： [ $$ \boxed{ x_{n+1}=x_n-a_n(h(x_n)+\xi_{n+1}). } $$ ] 其中： [ $$ \mathbb E[\xi_{n+1}\mid\mathcal F_n]=0. $$ ] 在稳定性、二阶矩控制和步长条件 [ $$ \sum_n a_n=\infty, \qquad \sum_n a_n^2<\infty $$ ] 下： [ $$ \boxed{ x_n\to\theta. } $$ ] 证明核心是**平方误差负漂移**： [ $$ -2a_n(x_n-\theta)h(x_n) $$ ] 压倒平方可和噪声。 --- ## 9.4 Dvoretzky theorem 一般随机递推： [ $$ \boxed{ X_{n+1}=T_n(X_1,\dots,X_n)+W_n. } $$ ] 若： [ $$ \mathbb E[W_n\mid\mathcal F_n]=0, \qquad \sum_n\mathbb E[W_n^2]<\infty, $$ ] 并且主项满足： [ $$ |T_n-x^*| \le \max{\alpha_n,(1+\beta_n)|X_n-x^*|-\gamma_n}, $$ ] 其中： [ $$ \alpha_n\to0, \qquad \sum_n\beta_n<\infty, \qquad \sum_n\gamma_n=\infty, $$ ] 则： [ $$ \boxed{ X_n\to x^* \quad\text{almost surely}. } $$ ] 证明核心： 1. ($T_n$) 提供持续收缩漂移； 2. ($\beta_n$) 的扩张总量有限； 3. ($\alpha_n$) 的误差地板趋零； 4. ($W_n$) 是平方可和 martingale difference 噪声； 5. 因此误差只能收敛到 0。 --- 一句话概括： $$ \boxed{ \text{Banach 定理解决无噪声收缩不动点迭代；Robbins--Monro 解决有噪声的求根；Dvoretzky 定理给出更一般的随机递推几乎必然收敛框架。} } $$