技术摘要：通过混沌迭代与简单随机博弈计算学习函数的固定点

1. 问题陈述

本文解决了计算 $d$ 维函数 $f: X \to X$（在非负实数集 $\mathbb{R}^d_+$ 上）的最小固定点 ($\mu f$) 的问题，其中 $f$ 并非精确已知，而是仅通过一系列近似序列 $(f_n)$ 可获取。这种情况经常出现在定量系统（如马尔可夫决策过程 MDP 和简单随机博弈 SSG）中，其中转移概率和奖励需要通过采样进行估计。

一个主要的挑战在于，最小固定点算子不一定是连续的；因此，近似函数的最小固定点序列 $(\mu f_n)$ 并不总是收敛于 $\mu f$。此外，以往的工作（特别是 [4]）依赖于 Mann-Kleene 方案，该方案假设：

1. 向量的所有分量在每个迭代步骤中都会更新。
2. 学习率序列 $(\alpha_n)$ 收敛到一个大于 0 的值（通常为 1）。
3. 近似序列 $(f_n)$ 进行“正常”收敛（即 $\sum \|f - f_n\| < \infty$），这一条件通常需要人为地加速采样过程。

这些约束使得该方法在处理高维系统（其中全量更新在计算上是不可行的）时显得不切实际，并限制了其在模型无关强化学习算法（如 Q-learning）中的适用性，因为在这些算法中，学习率必须收敛到 0 以处理随机噪声。

2. 方法论

作者通过推广**阻尼 Mann 迭代（dampened Mann iteration）**方案来克服这些限制。标准迭代定义为：
$$x_{n+1} = (1 - \beta_n) \cdot (x_n + \alpha_n \cdot (f_n(x_n) - x_n))$$
其中 $\alpha_n$ 是学习率，$\beta_n$ 是阻尼因子。

本文引入了三个关键的推广：

A. 非收敛及消失的学习率

作者放宽了 $\alpha_n \to 1$（或 $\alpha > 0$）的要求。他们定义了一种进展方案（progressing scheme），其中满足 $\lim_{n \to \infty} \beta_n / \alpha_n = 0$。这使得：

• $\alpha_n$ 可以收敛到 0（这对于模型无关强化学习的收敛至关重要）。
• $\alpha_n$ 可以不收敛（例如随机选择）。
• 阻尼因子 $\beta_n$ 仍能满足 $\sum \beta_n = \infty$ 且 $\lim \beta_n = 0$。

这种放宽使得对近似条件的约束从 $\sum \|f - f_n\| < \infty$ 弱化为 $\sum \alpha_n \|f - f_n\| < \infty$。当 $\alpha_n \to 0$ 时，这一条件更容易满足。

B. 广义（向量）参数与混沌迭代

参数 $\alpha_n$ 和 $\beta_n$ 从标量推广到了 $[0, 1]^d$ 中的向量。这实现了混沌迭代（chaotic iteration），即在第 $n$ 步仅更新一部分分量 $I_n \subseteq \{1, \dots, d\}$：
$$x_{n+1}(i) = \begin{cases} (1 - \beta_n(i)) \cdot (x_n(i) + \alpha_n(i) \cdot (f_n(x_n) - x_n)(i)) & \text{若 } i \in I_n \\ x_n(i) & \text{若 } i \notin I_n \end{cases}$$
为了确保在这种异步设置下的收敛性，作者引入了一种广义进展方案。这要求阻尼因子在所有维度上“公平地”递减：必须存在一系列时间步，使得在任意两个步骤之间，每个分量至少被更新一次，并且这些间隔内的最小阻尼因子之和发散至无穷大。

C. 近似函数的收敛证明

本文为单调且非扩张（1-Lipschitz）的序列 $(f_n)$ 建立了收敛性证明。

• 精确情况： 如果 $f$ 是已知的，进展广义方案会收敛到 $\mu f$。
• 近似情况： 如果 $\lim_{n \to \infty} \mu(\sup_{k \ge n} f_k) = \mu f$，则保证收敛。当 $(f_n)$ 单调收敛于 $f$，或者极限函数 $f$ 是一个 Picard 算子（具有唯一固定点且迭代收敛于该点）时，此条件成立。

3. 核心贡献与结果

1. 阻尼 Mann 迭代的推广： 作者证明了阻尼 Mann 迭代可以在学习率收敛到 0 或不收敛，以及使用支持混沌更新的向量值参数的情况下工作。
2. 在简单随机博弈（SSGs）中的应用： 本文展示了阻尼 Mann 迭代可以直接应用于 SSGs。以往的工作需要通过“加速”采样来强制实现正常收敛（这非常昂贵），而本方法可以使用标准的采样序列。这是通过证明在采样条件下，最小固定点算子对于 SSGs 是连续的来实现的。
3. 扩展至行为度量： 研究结果意味着阻尼 Mann 迭代可用于在近似设置下计算行为度量（例如概率双模拟距离），为对转移概率微小扰动敏感的方法提供了一个鲁棒的替代方案。
4. 数值实验： 作者在 50 个随机生成的 SSG 上进行了实验。
   • 学习率： 他们将消失型（$\alpha_n = 1/n^\epsilon$）和随机型（$\alpha_n \sim U[0,1]$）学习率方案与标准的松弛 Mann-Kleene 方案进行了比较。结果显示出相似的收敛速度，表明在无故障采样场景下，消失型速率并不会阻碍收敛。
   • 混沌迭代： 他们测试了每次仅随机选择一个状态进行更新的混沌变体。结果表明，混沌迭代产生的收敛速度与全量更新（在按计算量归一化后）相当，同时允许获得中间结果并可能降低内存占用。

4. 意义与主张

本文声称，其推广对于弥合理论固定点迭代与实际强化学习算法之间的鸿沟至关重要：

• 模型无关强化学习： 通过允许 $\alpha_n \to 0$，该理论现在可以与 Q-learning 等算法对齐，在这些算法中，更新取决于当前的样本而非估计的概率。
• 可扩展性： 通过引入混沌迭代，该方法变得适用于全量向量更新不可行的超高维系统。
• 鲁棒性： 对 $(f_n)$ 收敛条件的放宽，允许使用标准采样策略，而无需使用计算昂贵的“加速”机制来强制实现正常收敛。
• SSG 可解性： 这项工作解决了一个开放性问题，即阻尼 Mann 迭代是否能“开箱即用”地应用于 SSG，证明了它不需要以往方法所受限制的特定结构假设（如幂收缩性）。

作者保持了谦逊的语气，指出虽然采用随机分量选择的混沌迭代不会增加收敛速度的成本，但基于访问频率等启发式信息进行分量选择的方法可以进一步提高效率，这是他们计划探索的方向。同样，他们建议未来的工作可以将这些结果应用于典型于随机逼近理论中的极限平均收敛场景。