acceptodds
Under review as a conference paper at ICLR 2027

Self-Tuned Q-Learning and SARSA: Policy Control Without Worrying About Step-Size Calibration

Abstract

Q-learning and SARSA are foundational reinforcement learning algorithms whose practical success depends critically on step-size calibration: step-sizes that are too large cause numerical instability, while step-sizes that are too small yield slow progress. We propose self-tuned variants of both algorithms that recast the standard iterative updates as fixed-point equations, yielding a data-adaptive step-size adjustment. Our non-asymptotic analysis shows that the proposed methods remain stable over substantially broader step-size ranges. Under mild conditions, they admit arbitrarily large initial step sizes, greatly reducing the influence of initialization while matching the convergence rates of the standard algorithms. Empirical validation across environments with both discrete and continuous state spaces shows that self-tuned Q-learning and SARSA are markedly less sensitive to step-size selection, remaining stable at step-sizes that cause the standard methods to suffer numerical instability.

Primary area:
reinforcement learning
Keywords:
Q-learning, SARSA, Policy Control, Step size, Learning rate

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_bdnHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Self-Tuned Q-learning (ST-Q-learning) and Self-Tuned SARSA (ST-SARSA), which use an implicit/fixed-point update to transform the original step size into an adaptive effective step size related to the feature norm. The authors further derive finite-time error bounds for projected linear Q-learning and SARSA, and claim that the self-tuned variants allow arbitrarily large initial step sizes. Experiments cover tabular settings, linear function approximation, and simple deep Q-learning scenarios.

Critical strengths
  • The problem is clear and practically relevant. Step-size sensitivity is a practical issue in Q-learning/SARSA, while the proposed method only modifies the update rule without introducing complex additional modules, making the overall formulation relatively simple.
  • The paper not only provides a closed-form expression for the self-tuned update, but also gives finite-time analyses for both Q-learning and SARSA with a time-varying policy.
Critical weaknesses
  • The main experimental comparisons do not fully demonstrate the benefit of "self-tuning" itself. According to Proposition 3.1, the actual effective step size is β~t=βt1+βt∥ϕt∥2\tilde{\beta}_t=\frac{\beta_t}{1+\beta_t\|\phi_t\|^2}. For many tabular experiments using one-hot features, ∥ϕt∥2=1\|\phi_t\|^2=1, so this becomes β~t=βt/(1+βt)<1\tilde{\beta}_t=\beta_t/(1+\beta_t)<1. In other words, even when the nominal βt\beta_t is set to 100, 300, or larger, the actual update step size is automatically reduced below 1. The current experiments mainly compare ST methods with standard Q-learning/SARSA using the same nominal βt\beta_t, but do not include a matched baseline where the standard algorithms use the same transformed/effective step size. Therefore, part of the observed advantage in "large-step-size robustness" may directly result from this explicit step-size shrinkage.

  • Section 2 assumes r:S×A→[0,b]r:S\times A\rightarrow[0,b], i.e., non-negative rewards. However, Cliff Walking uses rewards of −100-100 and −1-1, and GridWorld also uses negative rewards. The paper does not clarify whether the theory actually only requires ∣r∣≤b|r|\le b, or whether reward shifting is applied in the experiments.

  • The deep extension directly replaces ∥ϕt∥2\|\phi_t\|^2 in the linear setting with ∥∇θQ∥2\|\nabla_\theta Q\|^2, but no corresponding theoretical derivation is provided.

  • There are still some basic issues in the references and presentation. For example, capitalization of journal and conference names is inconsistent in the bibliography, such as "nature," "Machine learning," "Springer nature," and "International conference on machine learning." The main text also contains unnatural citation rendering such as (Zou et al., 2019b;a). These issues do not affect the core results, but should be standardized in the final version.

Questions for authors

See Weaknesses.

Reviewer_BwfzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper present a self-tuned variant for the algorithms SARSA and Q-Learning. The Authors adopt implicit update schemes to reformulate the update rule of both approaches transforming their recursive update rule into a fixed-point equation. The Authors provide a non-asymptotic analysis showing a better stability under initially larger step-sizes w.r.t. the classic formulation for both the algorithms. Eventually, an experimental section shows over tabular and continuous setting the effectiveness of the self-tuning approaches.

Critical strengths
  • The method is a simple yet effective change to the update rule, with no extra hyperparameters and cost free.
Critical weaknesses
  • The experimental results are not convincing. In the discrete settings using one-hot feature ∣∣ϕ∣∣=1||\phi|| = 1, so the self-tuned methods are exactly the standard ones with step-size β/(1+β)<1\beta/(1 + \beta) < 1. In this case the results proposed only show tabular updates with step-size less than 1 which is known to work. In Fig. 4 instead, the results in almost every setting show no statistical evidence of ST methods performing better than classic ones, as all the shaded area (assumed to be confidence intervals) overlap. Same consideration are valid for MountainCar in Fig. 6.
Questions for authors
  • Can the Author elaborate more on the experimental results commented in the previous section?
  • Results on the deep q-learning looks promising, however the results proposed train for not enough interaction to be able to derive a decent policy. Can the Author provide additional results on this setting, especially adopting standard setup for the baseline step size (e.g., Adam)?
  • Can the Author explain where the condition of β0∈(0,1/ωq)\beta_0 \in (0, 1/ \omega_q) for Q-learning and β0∈(0,1/(2ωs))\beta_0 \in (0, 1/(2 \omega_s)) for SARSA used in the proof of Thm. 4.3 and 4.8? Do the Author think there might be the possibility to extended the bounds for any β0>0\beta_0 > 0? If so, what theoretical advantages the ST methods keep?
Reviewer_BfMROpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces self-tuned Q-learning and SARSA with an effective step size of βt/(1+βt∥ϕt∥2)\beta_t/(1+\beta_t\|\phi_t\|^2). It provides finite-time bounds for projected linear variants under decreasing step sizes and reports reduced sensitivity to large nominal step sizes across tabular, linear, and Atari RAM experiments.

Critical strengths

The update is simple to implement. The theoretical analysis and experiments address the practically relevant problem of step-size sensitivity.

Critical weaknesses

My main concern is algorithmic novelty. Normalized TD already scales updates by feature energy, as discussed by Bradtke and Barto (1996). More directly, Tamar et al. (2014), Implicit Temporal Differences, introduced the same implicit mechanism, yielding the same normalization factor when λ=0\lambda=0, and explicitly applied it to SARSA. These connections are not adequately discussed. The paper therefore needs to distinguish its new theoretical results from previously established update mechanisms.

Questions for authors

What is algorithmically new relative to normalized TD and implicit SARSA? Which finite-time results go beyond prior analyses, and what additional technical difficulties do they resolve?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.