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

arXiv: https://arxiv.org/abs/2601.18907 · HTML: https://mlsanity.com/paper/2601.18907/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 12 of 12)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Deep Reinforcement Learning framework for Autonomous Driving](https://mlsanity.com/paper/1704.02532/) (2017)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [On the Convergence of SARSA with Linear Function Approximation](https://mlsanity.com/paper/2202.06828/) (2022)
- [Towards stability and optimality in stochastic gradient descent](https://mlsanity.com/paper/1505.02417/) (2015)
- [Implicit Updates for Average-Reward Temporal Difference Learning](https://mlsanity.com/paper/2510.06149/) (2025)
- [Stabilizing Temporal Difference Learning via Implicit Stochastic Recursion](https://mlsanity.com/paper/2505.01361/) (2025)

## 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.