mlsanityData to 14 Oct 2026

Implicit Q-Learning and SARSA: Liberating Policy Control from Step-Size Calibration

arXiv 2601.18907 ↗First posted 26 Jan 2026stat.ML cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Q-learning and SARSA are foundational reinforcement learning algorithms whose practical success depends critically on step-size calibration. Step-sizes that are too large can cause numerical instability, while step-sizes that are too small can lead to slow progress. We propose implicit variants of Q-learning and SARSA that reformulate their iterative updates as fixed-point equations. This yields an adaptive step-size adjustment that scales inversely with feature norms, providing automatic regularization without manual tuning. Our non-asymptotic analyses demonstrate that implicit methods maintain stability over significantly broader step-size ranges. Under favorable conditions, it permits arbitrarily large step-sizes while achieving comparable convergence rates. Empirical validation across benchmark environments spanning discrete and continuous state spaces shows that implicit Q-learning and SARSA exhibit substantially reduced sensitivity to step-size selection, achieving stable performance with step-sizes that would cause standard methods to fail.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 12 of its 39 references that are in the map. First posted on arXiv 26 Jan 2026.

Builds on

12 of 39 references.

Closest ancestors · 3

Same direction, newest first

  1. 2025Implicit Updates for Average-Reward Temporal Difference Learning7 Oct
  2. 2025Stabilizing Temporal Difference Learning via Implicit Stochastic Recursion2 May
  3. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation25 Jan

Other references · 9

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  3. 2017Deep Reinforcement Learning framework for Autonomous Drivingcited by 225
  4. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  5. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  6. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  7. 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
  8. 2022On the Convergence of SARSA with Linear Function Approximationcited by 15
  9. 2015Towards stability and optimality in stochastic gradient descentcited by 11

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Long-Horizon Q-Learning: Accurate Value Learning via n-Step Inequalities
  2. 2025Is Q-learning an Ill-posed Problem?
  3. 2023Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning
  4. 2026SCQ: Stabilizing Conservative Q-Learning with Sigmoid-Bounded Entropy
  5. 2025Behavior-Adaptive Q-Learning: A Unifying Framework for Offline-to-Online RL
  6. 2024Decision-Centered Abstractions via Orthogonal Estimation of Difference-of-Q Functions
  7. 2026Scalable Reinforcement Learning via Adaptive Batch Scaling
  8. 2023Offline Reinforcement Learning with On-Policy Q-Function Regularization