Computer Science > Machine Learning
Title:Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
Abstract:The Robbins-Siegmund theorem establishes the convergence of stochastic processes that are almost supermartingales and is one of the most commonly used approaches for analyzing stochastic iterative algorithms in stochastic approximation and reinforcement learning (RL). However, its original form has a significant limitation as it requires the zero-order term to be summable. In many important RL applications, this summable condition, however, cannot be met. This limitation motivates us to extend the Robbins-Siegmund theorem for almost supermartingales where the zero-order term is not summable, but only square-summable. In particular, we introduce a novel and mild assumption on the increments of the stochastic processes. This together with the square-summable condition enables an almost sure convergence to a bounded set. Additionally, we further provide almost sure convergence rates, high probability concentration bounds, and $L^p$ convergence rates. We then apply the new results to stochastic approximation and RL. Notably, we obtain the first almost sure convergence rate, the first high probability concentration bound, and the first $L^p$ convergence rate for $Q$-learning with linear function approximation.
| Subjects: | Machine Learning (cs.LG) ; Optimization and Control (math.OC) |
|---|---|
| Cite as: | arXiv:2509.26442 [cs.LG] |
| (or arXiv:2509.26442v3 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2509.26442 arXiv-issued DOI via DataCite |
Submission history
Access Paper:
- HTML (experimental)
Additional Features
- Audio Summary
Current browse context:
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bookmark
Bibliographic and Citation Tools
Code, Data and Media Associated with this Article
Demos
Recommenders and Search Tools
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.