- 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 for fixed problem parameters. Experiments on Maze-25 and Chain-50 show improvements over Q-SlowSwitch-Adv and UCBVI- under the reported parameter settings.
Critical strengths
-
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.
-
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
-
Weak regret rate and lack of a tightness argument. The paper establishes an regret bound, which is barely sublinear. Both randomized learning-rate Q-learning in episodic MDPs and existing continuing discounted RL algorithms achieve -type rates. Corollary 1 converts the result to Liu–Su -regret, allowing comparison with the 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.
-
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.
-
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.
-
Large gap between theoretical and practical parameters. On Maze-25, the certified ensemble size is , compared with in practice. The certified slow prior is also much larger than the practical value and the interaction budget . Moreover, substituting the Maze-25 instance parameters into Theorem 1 yields a bound no better than the trivial upper bound, even with the unspecified constant . This raises concerns about the practical relevance of the theoretical guarantee.
Questions for authors
Questions
-
The leading regret term arises from the fast–slow mixture, while the fast bootstrap is treated as a bounded perturbation. With (Slow-only), these terms appear to disappear from (45)–(47), potentially yielding a 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?
-
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?
-
For Maze-25 (, , , ), what is the smallest for which the nontrivial branch of (7) improves upon , even with ? Could the authors also evaluate the fully certified configuration (, , from (5), ) to assess the practical relevance of the guarantee?
-
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.