Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

preprint2026arXivOpen access

Abstract

Establishing almost sure convergence rates for stochastic approximation and reinforcement learning under Markovian noise is a fundamental theoretical challenge. We make progress towards this challenge for a class of stochastic approximation algorithms whose expected updates are contractive, a setting that arises in many reinforcement learning algorithms such as QQ-learning and linear temporal difference learning. Specifically, for a power-law learning rate O(n−η)O(n^{-η}) with η∈(1/2,1)η\in (1/2, 1), we obtain an almost sure convergence rate arbitrarily close to o(n1−2η)o(n^{1 - 2η}). For a harmonic learning rate O(n−1)O(n^{-1}), we obtain an almost sure convergence rate arbitrarily close to o(n−1)o(n^{-1}), which we argue is a strong result because it is close to the optimal rate O(n−1log⁡log⁡n)O(n^{-1}\log\log n) given by the law of the iterated logarithm (for a special case of i.i.d. noise). Key to our analysis is a novel Lyapunov drift construction that applies a Poisson-equation based correction for Markovian noise to the well-established Moreau-envelope smoothing for the contractive mapping.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.