acceptodds
Under review as a conference paper at ICLR 2027

Randomized Learning-Rate -Learning for Continuing Discounted MDPs

Abstract

Randomized learning-rate -learning achieves tractable, gap-independent regret in episodic finite-horizon MDPs and often outperforms optimistic-bonus -learning, but its guarantees rely on a terminal boundary that ends the Bellman recursion. Removing this boundary leads to continuing discounted control, for which no such guarantee is known. We propose a discounted randomized -learning algorithm (D-RandQ), whose analysis lifts stage-wise reuse counting to a global interaction-time occurrence representation: each target is aligned with its successor occurrence, stage-ending self-loops and boundary visits are charged separately, and the recursion closes through a reuse operator with bounded column sum. Combined with adaptive-update concentration and Dirichlet anti-concentration, this yields a finite-sample, high-probability, gap-independent action-gap bound, hence, to our knowledge, the first finite-sample, gap-independent sublinear regret guarantee for randomized learning-rate -learning in continuing discounted MDPs. Empirically, under a documented disjoint calibration protocol, D-RandQ attains lower cumulative action gaps and higher realized rewards than -SlowSwitch-Adv and UCBVI- on Maze-25, and a large separation on the reported Chain-50 runs at the same transferred operating point.

Primary area:
reinforcement learning
Keywords:
Q-Learning, Randomized Exploration, Continuing Discounted MDPs

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_RofZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes D-RandQ, a randomized learning-rate Q-learning algorithm for continuing discounted MDPs. Building on RandomizedQ (Wang et al., 2026), the algorithm combines fast and slow Q-learning ensembles with a new stage schedule and mixing rule. The main technical contribution is an occurrence-time analysis that handles the absence of a terminal Bellman boundary and controls error propagation through self-loops and stage transitions. The authors establish a high-probability regret bound of Oγ(T/log⁡T)O_\gamma(T/\sqrt{\log T}) for fixed problem parameters. Experiments on Maze-25 and Chain-50 show improvements over Q-SlowSwitch-Adv and UCBVI-γ\gamma under the reported parameter settings.

Critical strengths
  1. To the best of my knowledge, this is the first work establishing a gap-independent sublinear regret guarantee for randomized learning-rate Q-learning in continuing discounted MDPs.

  2. The paper develops a new occurrence-time representation to handle the absence of a terminal Bellman boundary. The analysis carefully handles repeated error propagation, self-loops, and stage-boundary dependencies, allowing the regret recursion to close.

Critical weaknesses
  1. Weak regret rate and lack of a tightness argument. The paper establishes an Oγ(T/log⁡T)O_\gamma(T/\sqrt{\log T}) regret bound, which is barely sublinear. Both randomized learning-rate Q-learning in episodic MDPs and existing continuing discounted RL algorithms achieve O~(T)\widetilde O(\sqrt T)-type rates. Corollary 1 converts the result to Liu–Su γ\gamma-regret, allowing comparison with the O~(T)\widetilde O(\sqrt T) guarantees summarized in Table 3. However, no lower bound or tightness argument is provided to explain whether the slower rate is inherent to the algorithm or a limitation of the analysis.

  2. Limited algorithmic novelty and theoretical justification. D-RandQ largely inherits the randomized learning-rate mechanism and fast/slow ensemble architecture of RandomizedQ (Wang et al., 2026), while introducing a new stage schedule and mixing rule and adapting the targets to the discounted setting. Thus, the main contribution is primarily analytical. Moreover, the proof treats the fast bootstrap as a bounded perturbation, while the leading regret term arises from the fast–slow mixture drift. The analysis therefore does not establish a theoretical benefit from the fast component.

  3. Unclear empirical benefit of learning-rate randomization. Replacing the Beta learning rates with their conditional means produces no statistically significant performance difference on either benchmark, with all four paired confidence intervals including zero. Since identically initialized heads remain identical under this replacement, the deterministic variant is effectively a single-head method. Thus, the experiments do not demonstrate a clear benefit from randomization or ensemble diversity.

  4. Large gap between theoretical and practical parameters. On Maze-25, the certified ensemble size is J=761J=761, compared with 1616 in practice. The certified slow prior n0♭=⌈c0κ♭ℓ⌉≈2×107n_0^\flat=\lceil c_0\kappa^\flat\ell\rceil\approx2\times10^7 is also much larger than the practical value 18221822 and the interaction budget T=2×106T=2\times10^6. Moreover, substituting the Maze-25 instance parameters into Theorem 1 yields a bound no better than the trivial HγTH_\gamma T upper bound, even with the unspecified constant C=1C=1. This raises concerns about the practical relevance of the theoretical guarantee.

Questions for authors

Questions

  1. The leading regret term arises from the fast–slow mixture, while the fast bootstrap is treated as a bounded perturbation. With η≡0\eta\equiv0 (Slow-only), these terms appear to disappear from (45)–(47), potentially yielding a O~γ(T)\widetilde O_\gamma(\sqrt T) regret bound. Does the analysis support this conclusion? If so, why does it certify a better rate for the empirically worse variant? If not, which step fails?

  2. Randomization is used through Dirichlet anti-concentration (Lemma 6) to establish slow-ensemble optimism (Lemma 9), requiring multiple heads and large constants. Could a deterministic single-head variant with an explicit optimism bonus achieve similar guarantees? What theoretical advantage does randomization provide, especially given the similar empirical performance of D-RandQ-mean?

  3. For Maze-25 (S=625S=625, A=4A=4, γ=0.99\gamma=0.99, δ=0.05\delta=0.05), what is the smallest TT for which the nontrivial branch of (7) improves upon HγTH_\gamma T, even with C=1C=1? Could the authors also evaluate the fully certified configuration (J=761J=761, κ♭=8ℓ\kappa^\flat=8\ell, n0♭n_0^\flat from (5), U=2HγU=2H_\gamma) to assess the practical relevance of the guarantee?

  4. Could the authors report the number of slow commits, the fraction of steps with uncommitted actions at the current state, and how often the fast–slow mixture changes the greedy action relative to the committed slow table alone? This would help clarify the contribution of the fast component to the empirical results.

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

The paper designs a new algorithm for discounted reward Q learning with randomized learning rate. The algorithm incorporates previous design for episodic Q learning with randomized learning rate and carefully chooses the length of each episode. The analysis authors provide does not require environment reset which is interesting. However the provided T/log⁡TT/\log T rate is worse than the general T\sqrt{T} rate in literature with the same regret definition. In numerical comparison, the authors only showed better performance than a limited amount of baselines.

Critical strengths

The authors provided a new analysis that can analyze the regret of randomized Q learning in infinite horizon discounted reward where the environment can not be reset.

Critical weaknesses

1, The regret rate is worse than the T\sqrt{T} rate achievable by other algorithms for discounted reward RL. Further, the authors did not discuss why randomized learning rate is more favorable than optimism.

2, The authors did not compare with some baselines they cited like Zamir et al., 2026. Together with the worse regret rate, this raised the question whether the proposed algorithm achieves better empirical performance overall.

Questions for authors

1, Can the authors provide empirical comparison with Zamir et al., 2026?

2, Can the authors provide a tighter regret bound or indicate why T\sqrt{T} rate is hard for randomized learning rate?

3, Can the authors provide discussion between choosing a randomized learning rate and choosing optimism?

Reviewer_Q6vBOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes adaptation of the work of Wang et al. (2026) on fast-slow randomized Q-learning to the discounted setting, using the discounted regret definition of Liu and Su (2020). The authors proved the corresponding regret bound and launched the algorithm on several benchmarks, showing the competitive performance.

Critical strengths

None

Critical weaknesses

My main concern is a positioning of this paper against existing works of Ji & Li, (2023) as a work which extended a more complex version of Q-learning into the discounted setting, work of Dong et al. (2020), and the work of Wang et al. (2026) which main algorithmic design was taken. The paper do not discuss any challenges and difficulties in the analysis and the difference between them in the main text, making it extremely difficult to judge the novelty of the work. The second main concern is poor writing, which make it very difficult to understand the existing parts.

Dong, Kefan, et al. "Q-learning with UCB exploration is sample efficient for infinite-horizon MDP." ICLR 2020 (2020).

Questions for authors
  • What is the main technical difficulty of adaptation of the analysis to the discounted setting?
  • I did not understand the following sentence in the related work, which seems to claim the novel part of the analsys: "our targets are frozen before the current beta draws, so randomized-rate errors expand with deterministic mean-weight backward coefficients and are controlled by conditional-MGF and stopped calendar-time martingales" and, I believe, the corresponding statement is Lemma 5. How is it fundamentally different from the later analysis of Tiapkin et al. (2023, Proposition 7 of their Arxiv V2), except the direct MGF manipulations instead of applying Rosenthal inequality?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.