Cover Image

Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Singh, Rahul, Chandak, Siddharth, Moulines, Eric, Borkar, Vivek S., Bambos, Nicholas
Format:	Preprint
Published:	2026
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Concentration Bound for TD(0) with Function Approximation
by: Chandak, Siddharth, et al.
Published: (2023)

Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise
by: Chandak, Siddharth, et al.
Published: (2025)

High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise
by: Kar, Avik, et al.
Published: (2026)

Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis
by: Chandak, Siddharth, et al.
Published: (2026)

Policy Gradient Methods for Non-Markovian Reinforcement Learning
by: Kar, Avik, et al.
Published: (2026)

Learning to Control Unknown Strongly Monotone Games
by: Chandak, Siddharth, et al.
Published: (2024)

Last-Iterate Guarantees for Learning in Co-coercive Games
by: Chandak, Siddharth, et al.
Published: (2026)

Choose Your Battles: Distributed Learning Over Multiple Tug of War Games
by: Chandak, Siddharth, et al.
Published: (2025)

$O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation
by: Chandak, Siddharth
Published: (2025)

Reinforcement Learning in Non-Markovian Environments
by: Chandak, Siddharth, et al.
Published: (2022)

Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis
by: Chandak, Siddharth
Published: (2025)

Stochastic Approximation with Two Time Scales: The General Case
by: Borkar, Vivek S
Published: (2024)

An Actor-Critic Algorithm with Function Approximation for Risk Sensitive Cost Markov Decision Processes
by: Guin, Soumyajit, et al.
Published: (2025)

Optimal Control for Remote Patient Monitoring with Multidimensional Health States
by: Chandak, Siddharth, et al.
Published: (2025)

Tiered Service Architecture for Remote Patient Monitoring
by: Chandak, Siddharth, et al.
Published: (2024)

Stochastic approximation in non-markovian environments revisited
by: Borkar, Vivek Shripad
Published: (2026)

On Gaussian approximation for entropy-regularized Q-learning with function approximation
by: Rubtsov, Artemy, et al.
Published: (2026)

On Sampling with Approximate Transport Maps
by: Grenioux, Louis, et al.
Published: (2023)

The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning
by: Borkar, Vivek, et al.
Published: (2021)

An Asymptotic CVaR Measure of Risk for Markov Chains
by: Patel, Shivam, et al.
Published: (2024)

Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation
by: Levin, Ilya, et al.
Published: (2026)

Statistical inference for Linear Stochastic Approximation with Markovian Noise
by: Samsonov, Sergey, et al.
Published: (2025)

A theoretical basis for model collapse in recursive training
by: Borkar, Vivek Shripad
Published: (2025)

SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning
by: Mangold, Paul, et al.
Published: (2024)

Actor-Critic or Critic-Actor? A Tale of Two Time Scales
by: Bhatnagar, Shalabh, et al.
Published: (2022)

Regret Minimization via Saddle Point Optimization
by: Kirschner, Johannes, et al.
Published: (2024)

A dynamic view of some anomalous phenomena in SGD
by: Borkar, Vivek Shripad
Published: (2025)

Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents
by: Labbi, Safwan, et al.
Published: (2024)

Learning Time-Inhomogeneous Markov Dynamics in Financial Time Series via Neural Parameterization
by: Rovirosa, Jan, et al.
Published: (2026)

The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning
by: Block, Adam, et al.
Published: (2023)

Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning
by: Samsonov, Sergey, et al.
Published: (2024)

Markov Chain Variance Estimation: A Stochastic Approximation Approach
by: Agrawal, Shubhada, et al.
Published: (2024)

Learning the Model While Learning Q: Finite-Time Sample Complexity of Online SyncMBQ
by: Lim, Han-Dong, et al.
Published: (2024)

Asymptotic convexity of wide and shallow neural networks
by: Borkar, Vivek, et al.
Published: (2025)

Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds
by: Sattar, Yahya, et al.
Published: (2021)

Balanced Training of Energy-Based Models with Adaptive Flow Sampling
by: Grenioux, Louis, et al.
Published: (2023)

Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
by: Attias, Idan, et al.
Published: (2026)

Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processes
by: Moon, Sang Bin, et al.
Published: (2024)

Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation
by: Butyrin, Bogdan, et al.
Published: (2025)

Online Decision-Focused Learning
by: Capitaine, Aymeric, et al.
Published: (2025)