A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies
Proceedings of the ACM on Measurement and Analysis of Computing Systems · 29.05.2026 · 10 (2) · 1-43
DOI: 10.1145/3805624 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Measurement and Analysis of Computing Systems, online erschienen am 29.05.2026. Verfasst von Phalguni Nanda und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 73 Literaturangaben.
Abstract (Originalsprache)
In this work, we present the first finite-time analysis of Q-learning with time-varying learning policies (i.e., on-policy sampling) for discounted Markov decision processes under minimal assumptions, requiring only the existence of a policy that induces an irreducible Markov chain over the state space. We establish a last-iterate convergence rate for E[||Q k - Q * || ∞ 2 ], which implies a sample complexity of order O(1/ξ 2 ) for achieving E[||Q k - Q * || ∞ ]\le ξ. This rate matches that of off-policy Q-learning, but with a worse dependence on exploration-related parameters. We also derive an explicit finite-time rate for E[||Q π k - Q * || ∞ 2 ], where π k denotes the learning policy at iteration k . Together, these results highlight the exploration--exploitation trade-off in on-policy Q-learning. While exploration is weaker than in off-policy methods, on-policy learning enjoys an exploitation advantage since the learning policy itself converges to an optimal one. Numerical experiments corroborate our theoretical findings. From a technical perspective, the combination of rapidly time-varying learning policies, which induce time-inhomogeneous Markovian noise, and minimal exploration assumptions presents significant analytical challenges. To address these challenges, we develop a Poisson-equation-based decomposition of the Markovian noise associated with a lazy transition matrix, separating it into a martingale-difference term and residual terms. We then control the residual terms through a sensitivity analysis of the Poisson equation solution with respect to both the Q-function estimate and the learning policy. These techniques may facilitate the analysis of other reinforcement learning algorithms with rapidly time-varying learning policies, such as single-timescale actor--critic methods and learning-in-games algorithms.
Zitieren
APA
Nanda, P., & Chen, Z. (2026). A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 10(2), 1-43. https://doi.org/10.1145/3805624
Vancouver
Nanda P, Chen Z. A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2026;10(2):1-43. doi:10.1145/3805624
BibTeX
@article{Nanda2026,
author = {Nanda, Phalguni and Chen, Zaiwei},
title = {A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies},
journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
year = {2026},
volume = {10},
number = {2},
pages = {1--43},
doi = {10.1145/3805624}
}
EUVIMED