Research map / Optimization / Nonconvex and smooth optimization
Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that linear Q-learning with an adaptive-temperature epsilon-softmax behavior policy has an explicit L2 convergence rate to a bounded set, and derives an L2 rate for tabular Q-learning using a pseudo-contraction of the weighted Bellman optimality operator.
Problem
Linear Q-learning is widely believed to diverge; prior guarantees of boundedness are asymptotic (almost sure) and rely on algorithmic modifications or strong assumptions on features or behavior policy. The paper asks for a nonasymptotic L2 convergence rate for unmodified linear Q-learning.
Approach
Uses an epsilon-softmax behavior policy whose temperature shrinks as ||w|| grows (kappa_w = kappa_0/||w||), giving Lipschitz continuity of the expected update, and analyzes a general stochastic approximation with single-timescale fast-changing Markovian noise via a Moreau-envelope Lyapunov function; for tabular Q-learning, shows the weighted Bellman optimality operator is a pseudo-contraction in t
Key results
- Theorem gives E[||w_t||^2] bounded by a decaying term plus a constant B_3 for epsilon_alpha=1, and an exponentially decaying term plus B_6 for epsilon_alpha in (0,1).
- Tabular Q-learning with epsilon-softmax behavior policy obtains E[||q_t - q*||_inf^2] rate with a ln(t)/t^min(1,B2 alpha) term.
- On Baird's counterexample (gamma=0.99, alpha=0.1, 10 runs, 1500 iterations) unmodified linear Q-learning weights remain stably bounded.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an ε-softmax behavior policy with adaptive temperature | Unmodified linear Q-learning · Linear Q-learning | expected squared L2 weight norm | Helped |
| Use an ε-softmax behavior policy | Tabular Q-learning · Tabular Q-learning | expected squared infinity-norm error to q* | Helped |
| Use the weighted Bellman optimality operator's pseudo-contraction property | Tabular Q-learning analysis · Tabular Q-learning | convergence to q* | Helped |
Limitations
- Bounded set rather than convergence to optimal Q-function for linear Q-learning.
- Requires sufficiently small epsilon and sufficiently large kappa_0 and t_0 (constants not explicit).
- Experiments limited to a single toy benchmark (Baird's counterexample).
Experimental setup
Datasets: Baird's counterexample
Benchmarks: Baird's counterexample
Metrics: squared L2 norm of weights
Baselines: Meyn (2024) Lim and Lee (2024) Chen et al. (2023) linear SARSA bounded-set analysis
Builds on: Melo et al. (2008) linear Q-learning analysis Meyn (2024) boundedness of linear Q-learning Moreau envelope smooth norm construction (Chen et al.)
Closest papers by meaning
- A new convergent variant of Q-learning with linear function approximation (NeurIPS 2020 · similarity 0.90)
- Sharp asymptotic theory for Q-learning with \texttt{LD2Z} learning rate and its generalization (ICLR 2026 · similarity 0.89)
- Regularized Q-Learning (NeurIPS 2024 · similarity 0.89)
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift (NeurIPS 2026 · similarity 0.89)
- Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability (NeurIPS 2025 · similarity 0.88)
- A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.