EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies

Phalguni Nanda, Zaiwei Chen

ACM SIGMETRICS Performance Evaluation Review · 20.07.2026 · 54 (1) · 213-215

DOI: 10.1145/3820171.3806884 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 27.07.2026. Verfasst von Phalguni Nanda und 1 weiteren Autor:innen. Die Arbeit nennt 12 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

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 * || ∞ ]≤ ξ. 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. 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. ACM SIGMETRICS Performance Evaluation Review, 54(1), 213-215. https://doi.org/10.1145/3820171.3806884

Vancouver

Nanda P, Chen Z. A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies. ACM SIGMETRICS Performance Evaluation Review. 2026;54(1):213-215. doi:10.1145/3820171.3806884

BibTeX
@article{Nanda2026,
  author = {Nanda, Phalguni and Chen, Zaiwei},
  title = {A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies},
  journal = {ACM SIGMETRICS Performance Evaluation Review},
  year = {2026},
  volume = {54},
  number = {1},
  pages = {213--215},
  doi = {10.1145/3820171.3806884}
}
Kostenlos starten →