Research map / Reinforcement learning / Policy gradient and actor-critic
Regularized Q-Learning
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.
Proposes RegQ, a single time-scale Q-learning variant with linear function approximation that adds an L2 regularization term to the update, proving convergence via ODE analysis and switching-system comparison systems.
Problem
Q-learning with linear function approximation is unstable and can diverge under the deadly triad; existing convergent fixes rely on strong assumptions, target networks, or two time-scale updates.
Approach
Add an l2 regularization term -ηθ to the linear Q-learning update, making the associated switched linear system stable under a condition on η; this yields a regularized projected Bellman equation whose solution exists and is unique, and the stochastic iterates converge almost surely to it, without target networks.
Key results
- RegQ converges on the Baird seven-star and Tsitsiklis-Van Roy counterexamples where linear Q-learning diverges, and converges faster than two time-scale baselines (Carvalho et al. 2020, Maei et al. 2010) per the authors' experiments.
- Under the stated conditions (e.g., eta above the threshold in (15)), the paper proves the iterates converge almost surely to the unique solution of the regularized projected Bellman equation.
- Error bound ||X theta_eta - Q*||_inf <= ||Gamma_eta Q* - Q*||_inf / (1 - gamma||Gamma_eta||_inf) is derived, tight as eta goes to 0 and infinity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add an ℓ2 regularization term to linear Q-learning (RegQ) | Q-learning with linear function approximation · Tsitsiklis–Van Roy and Baird counterexamples | convergence | Helped |
| Use single-time-scale RegQ instead of the compared two-time-scale Q-learning algorithms | Linear Q-learning · Baird seven-star counterexample | convergence speed | Helped |
Surprising findings
- The regularized projected Bellman equation can have a solution when the standard projected Bellman equation does not (Appendix example).
Limitations
- Convergence requires the regularization coefficient to exceed a threshold (condition 15), which introduces bias in the fixed point and the error bound can be large.
- Requires orthogonal, non-negative feature matrix (Assumption 2.2), a strong restriction.
- Experiments limited to small classic counterexample environments.
Experimental setup
Datasets: Tsitsiklis and Van Roy (1996) counterexample Baird seven-star counterexample Mountain Car
Benchmarks: Baird seven-star counterexample Tsitsiklis and Van Roy counterexample Mountain Car
Metrics: convergence rate of parameter error
Baselines: Q-learning with linear function approximation Greedy-GQ Carvalho et al. (2020) two time-scale Q-learning
Builds on: Q-learning Lee and He (2020) switching system approach Borkar and Meyn ODE method Bharadwaj Diddigi et al. (2020) regularized TD
Closest papers by meaning
- Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set (ICML 2025 · similarity 0.89)
- A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation (NeurIPS 2024 · similarity 0.89)
- Diffusion-based Reinforcement Learning via Q-weighted Variational Policy Optimization (NeurIPS 2024 · similarity 0.87)
- ADDQ: Adaptive distributional double Q-learning (ICML 2025 · similarity 0.87)
- Adaptive $Q$-Network: On-the-fly Target Selection for Deep Reinforcement Learning (ICLR 2025 · similarity 0.87)
- Long-Horizon Q-Learning: Accurate Value Learning via n-Step Inequalities (NeurIPS 2026 · similarity 0.87)
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.