随机逼近稳态收敛新理论：最优速率O(√α)高斯逼近，还搞定Q学习！
Steady-State Convergence of Stochastic Approximation
📖 AI 总结
本文研究常步长随机逼近（SA）的稳态收敛（SSC）问题，即当步长趋近于零时，缩放后平稳分布的极限行为。现有SSC理论依赖独立同分布或加性噪声假设，并要求均值算子全局可微，且给出的收敛速率并非最优。作者针对由马尔可夫乘性噪声驱动的收缩型SA，建立了一个统一理论框架，同时覆盖均值算子局部可微与局部不可微两种情形。其核心方法是多步普适性框架，通过逐步将原始随机递归约化为可处理的辅助动力学，同时保持稳态极限不变。在不动点处局部二次线性化条件下，作者以Wasserstein-2距离获得了最优速率O(√α)的高斯近似，并进一步给出原始迭代的有限时间高斯近似。在局部不可微情形下，作者证明主导阶渐近偏差可达√α量级，与光滑情形下的α阶偏差形成鲜明对比。该理论被应用于马尔可夫线性SA和异步Q学习，二者均未被此前结果覆盖；作者还提出一种无需预知局部光滑性状态的Q学习偏差缩减方案，并通过数值实验验证。
🔑 关键词速览
| 随机逼近 (Stochastic Approximation, SA) | 一种用于求解寻根或优化问题的迭代算法，利用带噪声的观测逐步逼近目标解。 |
| 稳态收敛 (Steady-State Convergence, SSC) | 研究当步长趋于零时，固定步长随机逼近算法所收敛到的平稳分布的极限行为。 |
| 马尔可夫乘性噪声 (Markovian Multiplicative Noise) | 噪声项不仅具有马尔可夫依赖性，而且其幅度与当前状态相乘，而非简单相加。 |
| Wasserstein-2距离 | 一种衡量两个概率分布之间差异的度量，基于最优传输理论，对分布的形状和位置敏感。 |
| 异步Q学习 (Asynchronous Q-learning) | 一种强化学习算法，用于在未知环境中学习最优动作价值函数，其更新异步进行，不要求所有状态-动作对同时更新。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅