- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies stochastic linear bandits in which two executions with shared algorithmic randomness but independent reward realization must select the same action sequence with probability at least . It constructs RepRidge by applying randomized grid rounding to a ridge estimate. Combining this estimator with determinant-triggered batching yields RepLinUCB, with a claimed regret bound of , improving the previous guarantee. The approach extends to generalized linear bandits.
I lean toward acceptance because the improved bandit guarantee is a useful contribution. My recommendation depends on adequately distinguishing RepRidge from closely related work.
Critical strengths
-
Meaningful improvement in replicable bandit guarantees. The claimed improvement from to improves both dimension and replicability dependence, achieving the optimal dependence on .
-
A useful construction with broader applicability. The method directly produces a replicable parameter estimate with a confidence guarantee, avoiding action-space discretization and arm-wise reconstruction. Its compatibility with time-varying action sets and extension to generalized linear bandits strengthen its potential usefulness.
Critical weaknesses
Estimator-level novelty is insufficiently positioned. Eaton et al., Replicable Reinforcement Learning with Linear Function Approximation, already construct a replicable ridge estimator through randomized grid rounding (their Algorithm 2). This closely related work is not discussed. RepRidge uses different rounding coordinates and establishes a different confidence guarantee, but whitening, ridge confidence bounds, and randomized rounding are established ingredients. A direct comparison is necessary to establish the specific new contribution.
Questions for authors
How does RepRidge compare with Eaton et al.’s R-Ridge-Regression in its assumptions, design, confidence guarantees, and sample complexity? Which result here cannot be obtained directly from that earlier construction?
3 comments
Dear Reviewer,
Thank you again for your review and your positive assessment of our work.
You noted that your recommendation depends on adequately distinguishing RepRidge from a closely related work: Eaton et al. We hope our response above, detailing the differences, settles this. We have added the comparison to the paper as Remark 3.1 and in Appendix A.
If this resolves your concern, we would be grateful if you would consider updating your assessment. We are happy to answer any further questions before the discussion period ends.
Best regards,
Authors
The rebuttal addressed my main concern. I will keep my positive score.
We thank the reviewer for the positive assessment and for recognizing both the improved replicable bandit guarantee and the broader applicability of our construction. The reviewer's sole concern is how RepRidge relates to the replicable ridge regression of Eaton et al. Below, we answer each part of the question in turn, comparing assumptions, design, confidence guarantees, and sample complexity, and explain why none of our main results can be obtained from their construction.
1. Comparison with Eaton et al. (2026): W1, Q1
Assumptions. R-Ridge-Regression targets random designs: covariates are drawn independently from a sequence of distributions (their Theorem 3.1) or from a core set (their Theorem 3.2), and responses are bounded. RepRidge makes no distributional assumption. Its ellipsoid holds for adaptively chosen covariates (Assumption 3.1, Lemma E.1), and it is ρ-replicable whenever the design is shared by the two runs, including designs chosen adaptively as in RepLinUCB (Lemma E.3). This is the regime of RepLinUCB: the covariates are the learner's own actions, chosen from past rewards, and with time-varying At there is no underlying distribution.
Design. R-Ridge-Regression rounds the estimate coordinate by coordinate in the original parameter space, on a grid whose width is fixed in advance from the target accuracy ε. RepRidge rounds the whitened estimate Vn1/2θ^n on a grid whose width is set by the current radius βn(δ), so the rounding error takes the shape of the confidence ellipsoid. Rounding in the original coordinates would inflate the Vn-norm radius by κ(Vn), which is large under optimistic exploration, where Vt concentrates on a few directions. The two estimators are complementary. Theirs handles random designs that differ across runs, as in RL with random state visits, where they replicate the covariance separately. Ours handles adaptively chosen designs shared across runs.
Confidence guarantees. Their analysis compares each run's empirical minimizer with the population regularized minimizer, using strong convexity and uniform convergence. It gives ℓ2 accuracy around that minimizer (which they denote θ∗; it is not the true parameter), or a uniform prediction-error bound, once a sample-size threshold is met. RepRidge is a replicable counterpart of the self-normalized ellipsoid of Abbasi-Yadkori et al. (2011): ∥θ~n−θ⋆∥Vn≤βn(δ)(1+ρ−2δd) at every n, with no sample-size threshold. This is what the optimistic index ⟨a,θ~b⟩+β~b∥a∥Vtb−1 requires. An ℓ2 bound does not shrink along well-explored directions.
Sample complexity. Their Theorem 3.1 needs N=Ω((B+Y)2d3log(1/δ)/(λ2ε2(ρ−2δ)2)) samples for ℓ2 accuracy ε. The two can be compared directly under a core-set design with uniform prediction error ε. There, their Theorem 3.2 needs O~(d3k2∥θ⋆∥4/(ε6ρ2)) samples, where k is the number of core points. Since the core points must span Rd, which our Assumption 3.2 also requires, k≥d, so this is at least of order d5/(ε6ρ2). Our Proposition 3.1 needs O~(d3(d+log(1/δ))/(ε2ρ2)): a factor d better in the dimension, and ε−2 instead of ε−6.
Which results cannot be obtained from Eaton et al.'s construction. None of our main results. Theorem 3.1 with Lemma E.3 gives a ρ-replicable Vn-norm ellipsoid around θ⋆ at every n under adaptively chosen designs shared across runs, and Theorem F.1 with Lemma F.8 gives its GLM analogue. The bandit guarantees built on them, Theorem 4.1 (regret O~(d3T/ρ), optimal in ρ and T, with time-varying action sets) and Theorem 5.1, therefore cannot be obtained either. Each needs a self-normalized ellipsoid under an adaptive design, which a random-design ℓ2 guarantee does not provide. The only shared ingredient is the randomized grid rounding of Impagliazzo et al. (2022), which Eaton et al. also adapt (their Lemma 2.1). Applied as stated to a d-dimensional estimate, their rounding bound would give an inflation factor of 1+d3/2/(ρ−2δ) instead of our 1+d/(ρ−2δ). Under a core-set design, their Theorem 3.2 gives the same type of uniform prediction guarantee as our Proposition 3.1, but at the worse rate shown above.
We added a comparison with Eaton et al. as Remark 3.1 in Section 3.1, and a detailed discussion in Appendix A. We hope this clarifies the new contribution relative to Eaton et al., and we would be glad to answer any further questions the reviewer has.