Research map / Learning theory and algorithms / Prediction and decision losses
Regularized Q-learning through Robust Averaging
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 2RA Q-learning, a tabular/linear Q-learning variant that replaces the max-expectation term with a distributionally robust closed-form estimator over N averaged Q-estimates, giving controllable estimation bias with convergence and AMSE guarantees.
Problem
Q-learning suffers from an uncontrollable estimation bias (overestimation in Watkins' Q-learning, underestimation in Double Q-learning), which can degrade policy quality.
Approach
Estimate the max-expected-value term with a distributionally robust estimator over a 2-Wasserstein ball around the empirical average of N Q-estimates; the closed form reduces to subtracting a sqrt(rho)*||phi||_2 penalty, so bias is tuned via rho and N at Watkins-level per-iteration cost.
Key results
- Theory: 2RA Q-learning converges almost surely to Q* for any N with rho_n -> 0, and with learning rate N-times Watkins' its AMSE equals Watkins' AMSE.
- On CartPole (1000 runs, N=8), 2RA's mean hit time is better than Double Q-learning, which beats Watkins and Maxmin by a significant margin.
- On LunarLander with neural networks, 2RA and Maxmin lead by only a small margin over other methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use 2RA instead of Watkins' Q-learning | Baird's Example · Baird's Example | early learning performance | Helped |
| Use 2RA instead of Watkins' Q-learning | Random Environment · Random Environment | early learning performance | Helped |
| Use 2RA instead of Double Q-learning | CartPole · CartPole | hit time | Helped |
| Use 2RA instead of Watkins' Q-learning | CartPole · CartPole | hit time | Helped |
| Use 2RA instead of Watkins' Q-learning | Baird's Example · Baird's Example | AMSE | No clear effect |
| Increase the initial regularization ρ (ablation) | 2RA Q-learning · Baird's Example | early convergence speed | Helped |
| Use excessively large ρ or decay it too slowly (ablation) | 2RA Q-learning · Baird's Example | late learning performance | Hurt |
| Increase the number of estimates N (ablation) | 2RA Q-learning · Baird's Example | standard error | Helped |
| Increase the number of estimates N (ablation) | 2RA Q-learning · Baird's Example | marginal standard-error reduction | Mixed |
| Increase the number of estimates N (ablation) | 2RA Q-learning · Estimation bias | estimation bias | Helped |
| Use the specified 2RA learning rate N times Watkins' learning rate | 2RA Q-learning · Tabular asymptotic analysis | AMSE | No clear effect |
| Use a neural-network Q-function approximation with 2RA | 2RA Q-learning · LunarLander | hit time | Mixed |
Surprising findings
- Environments that favor underestimation bias (where Double Q-learning does well) also tend to be where 2RA performs well, suggesting underestimation is beneficial in these tasks.
- Only Variance Reduced Q-learning outperformed 2RA in the Baird's example AMSE comparison.
Limitations
- Convergence and AMSE theory hold only in the tabular (or linear canonical-basis) setting; neural network experiments lack theoretical guarantees.
- Choosing N too large with N-times learning rate can cause numerical instability.
- Optimal bias level is environment-dependent and no rigorous rule for choosing rho and N is given.
Experimental setup
Datasets: Baird's example (synthetic MDP) random MDP environments (synthetic) CartPole LunarLander
Benchmarks: Baird's example random MDP environments CartPole LunarLander
Metrics: asymptotic mean-squared error mean squared error hit time (episodes to solve)
Baselines: Watkins' Q-learning Double Q-learning Maxmin Q-learning REDQ Variance Reduced Q-learning
Builds on: Double Q-learning Maxmin Q-learning Watkins' Q-learning Q(0)-learning REDQ
Closest papers by meaning
- Maxmin Q-learning: Controlling the Estimation Bias of Q-learning (ICLR 2020 · similarity 0.88)
- The Mean-Squared Error of Double Q-Learning (NeurIPS 2020 · similarity 0.87)
- On the Estimation Bias in Double Q-Learning (NeurIPS 2021 · similarity 0.86)
- ADDQ: Adaptive distributional double Q-learning (ICML 2025 · similarity 0.85)
- Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set (ICML 2025 · similarity 0.84)
- Regularized Q-Learning (NeurIPS 2024 · similarity 0.83)
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.