acceptodds
Under review as a conference paper at ICLR 2027

Replicable Linear Bandits with UCB based Exploration

Abstract

We study replicable algorithms for stochastic linear bandits with optimism-based exploration. A bandit algorithm is -replicable if two executions using shared internal randomness but independent reward realizations produce the same action sequence with probability at least . For linear bandits with infinitely many actions, existing replicable algorithms are elimination-based and rely on discretizing the action space, leading to suboptimal dependence on the dimension and on . We first introduce RepRidge, a replicable ridge regression estimator that satisfies a self-normalized confidence bound whose radius is inflated by a factor of . We believe this estimator is of independent interest. Building on it, we design RepLinUCB, a replicable optimistic algorithm that combines determinant-triggered batching with RepRidge, and show that its regret is . This improves the state-of-the-art by a factor of and gives the first linear bandit algorithm with optimal dependence on for large action sets. Because our approach does not rely on action-space discretization, it also applies to time-varying action sets, which existing results could not handle. Finally, we extend our approach to generalized linear bandits via a replicable penalized GLM estimator, RepGLM, and a corresponding optimistic algorithm, RepGLMUCB. In synthetic experiments, RepLinUCB achieves substantially lower regret than existing elimination-based algorithms.

Primary area:
learning theory
Keywords:
Replicability, Bandits

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_qeP5OpenReview ↗
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 1−ρ1-\rho. 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 O~(d3T/ρ)\widetilde O(d^3\sqrt T/\rho), improving the previous O~(d4T/ρ2)\widetilde O(d^4\sqrt T/\rho^2) 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
  1. Meaningful improvement in replicable bandit guarantees. The claimed improvement from O~(d4T/ρ2)\widetilde O(d^4\sqrt T/\rho^2) to O~(d3T/ρ)\widetilde O(d^3\sqrt T/\rho) improves both dimension and replicability dependence, achieving the optimal dependence on ρ\rho.

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

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 ρ\rho-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\mathcal A_t 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 ε\varepsilon. RepRidge rounds the whitened estimate Vn1/2θ^nV_n^{1/2}\hat\theta_n on a grid whose width is set by the current radius βn(δ)\beta_n(\delta), so the rounding error takes the shape of the confidence ellipsoid. Rounding in the original coordinates would inflate the VnV_n-norm radius by κ(Vn)\sqrt{\kappa(V_n)}, which is large under optimistic exploration, where VtV_t 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\ell_2 accuracy around that minimizer (which they denote θ∗\theta^*; 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+dρ−2δ)\lVert\tilde\theta_n-\theta^\star\rVert_{V_n}\le\beta_n(\delta)\big(1+\tfrac{d}{\rho-2\delta}\big) at every nn, with no sample-size threshold. This is what the optimistic index ⟨a,θ~b⟩+β~b∥a∥Vtb−1\langle a,\tilde\theta_b\rangle+\tilde\beta_b\lVert a\rVert_{V_{t_b}^{-1}} requires. An ℓ2\ell_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))N=\Omega\big((B+Y)^2d^3\log(1/\delta)/(\lambda^2\varepsilon^2(\rho-2\delta)^2)\big) samples for ℓ2\ell_2 accuracy ε\varepsilon. The two can be compared directly under a core-set design with uniform prediction error ε\varepsilon. There, their Theorem 3.2 needs O~(d3k2∥θ⋆∥4/(ε6ρ2))\tilde O\big(d^3k^2\|\theta^\star\|^4/(\varepsilon^6\rho^2)\big) samples, where kk is the number of core points. Since the core points must span Rd\mathbb R^d, which our Assumption 3.2 also requires, k≥dk\ge d, so this is at least of order d5/(ε6ρ2)d^5/(\varepsilon^6\rho^2). Our Proposition 3.1 needs O~(d3(d+log⁡(1/δ))/(ε2ρ2))\tilde O\big(d^3(d+\log(1/\delta))/(\varepsilon^2\rho^2)\big): a factor dd better in the dimension, and ε−2\varepsilon^{-2} instead of ε−6\varepsilon^{-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 ρ\rho-replicable VnV_n-norm ellipsoid around θ⋆\theta^\star at every nn 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/ρ)\tilde O(d^3\sqrt T/\rho), optimal in ρ\rho and TT, 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\ell_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 dd-dimensional estimate, their rounding bound would give an inflation factor of 1+d3/2/(ρ−2δ)1+d^{3/2}/(\rho-2\delta) instead of our 1+d/(ρ−2δ)1+d/(\rho-2\delta). 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.

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.

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

The paper studies the problem of replicable learning in linear bandits. The goal is to design a no-regret algorithm that produces the same sequence of actions in two different executions on the same stochastic instance, with high probability. While previous works assume a finite number of actions or perform some discretization, this paper works directly with continuous (and possibly time-varying) action sets.

The authors provide a new replicable estimator for the unknown parameter. Then, they exploit this estimator to develop a replicable algorithm based on determinant-triggered batching. The algorithm attains O(d3/ρT)O(d^3/\rho \sqrt{T}) regret, where ρ\rho is the replicability parameter, matching a known lower bound in both ρ\rho and TT and improving upon previous works by a factor of O(d/ρ)O(d/\rho). These techniques are also extended to replicable generalized linear bandits.

Critical strengths

The paper provides interesting results. It provides the first replicable algorithm for linear bandits that directly works with continuous action sets. Furthermore, it can be employed in contextual linear bandits (i.e., linear bandits with time-varying action sets), and it matches a known lower bound in the parameter ρ\rho.

From a technical point of view, the authors propose an elegant solution to develop a suitable replicable ridge estimator. The classical technique by Impagliazzo et al. (2022) cannot be directly applied to linear settings, since the natural confidence set is an ellipsoid. The authors circumvent this problem by working in whitened coordinates, where the confidence set becomes a ball. The classical technique is extended to multidimensional settings and applied to these coordinates.

Critical weaknesses

While the new estimator requires a novel idea, the rest of the paper seems to follow standard techniques. The learning algorithm employs determinant-triggered batching (see, e.g., Abbasi-Yadkori et al., 2011) with the replicable estimator in place of the standard one.

Questions for authors
  • Are there any significant technical challenges in combining determinant-triggered batching with the replicable estimator?
3 comments

We thank the reviewer for their positive assessment and for recognizing the contributions of our paper. We address their question below.

Combining RepRidge with determinant-triggered batching requires a trajectory-level coupling argument that jointly controls the estimates, selected actions, and batch boundaries. This guarantee does not follow by substituting RepRidge into the standard batching analysis.

  • The common design and batch schedule must themselves be established. RepRidge (Theorem 3.1) guarantees agreement when the two runs share the same design. In a bandit, however, the design consists of actions selected using earlier estimates. Thus, the whitening transformations, rounding widths, and determinant-triggered update times can differ across runs. Moreover, conditioning on an adaptively realized design or batch grid does not justify applying the fixed-design guarantee, since these quantities depend on past reward noise.

  • We resolve this dependence by analyzing the first action disagreement. We first establish that the batch in effect at any round, and its start time, are determined by the preceding actions alone. At the first disagreement, the two runs therefore have a common batch start, design matrix, and confidence radius. Their batch-start estimates must differ: equal estimates and deterministic tie-breaking would produce the same action. Exact agreement matters here because nearby estimates need not select identical actions from a continuous action set.

    Writing Mb\mathcal M_b for agreement up to a common batch start and AbA_b for disagreement of the batch estimates, we prove

    \le 2\delta_b+(\rho_b-2\delta_b)=\rho_b.$$ This combines unconditional, time-uniform concentration, which remains valid at random batch starts (Lemma E.1), with a rounding argument conditional on the information determining both runs before their batch-$b$ calls (Lemma E.3). The fresh shared seed $v_b$ remains independent of that information; on $\mathcal M_b$, the widths coincide, so both runs use the same shift $\alpha_bv_b$.
  • The determinant bound controls the accumulated replication cost. The first-disagreement argument reduces trajectory failure to a union over at most B=O(dlog⁡T)B=O(d\log T) batch updates, independently of the number of actions and allowing time-varying action sets. Allocating ρb=ρ/B\rho_b=\rho/B therefore gives ρ\rho-replicability of the entire action sequence, while the confidence-radius inflation scales as dB/ρdB/\rho.

We have made this coupling argument explicit in Appendix E and highlight it in Remark 4.3.

We hope this clarifies why combining RepRidge with determinant-triggered batching is not plug-and-play, and we would be glad to answer further questions.

Dear Reviewer,

Thank you again for your review and your positive assessment of our paper.

You asked whether combining determinant-triggered batching with the replicable estimator raises significant technical challenges. We hope our response above shows that it does. The combination needs a trajectory-level coupling argument, based on the first action disagreement, which does not follow from the standard batching analysis. We have made this argument explicit in Appendix E and highlighted it in Remark 4.3.

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,
The Authors

I thank the authors for their response. I agree that replicablility does not follow from the standard determinant-triggered batching analysis, which proves only the regret bound. However, it does not seem a significant challenge. Looking at the proof of Lemma E.3, steps 1, 2 and 4 are straightforward, while step 3 is essentially the same argument used to prove the replicability of RepRidge. Overall, the four steps of the proof adapt the idea employed by Esfandiari et al. (2023a) in their analysis.

Reviewer_uYvFOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a replicable linear bandit algorithm that choose the same actions across repeated runs despite observing different reward noise. The proposed RepLinUCB algorithm combines randomized rounding of regression estimates with infrequent updates, and extends the approach to generalized linear bandits. The authors present theoretical guarantees and experiments (in a very limited setting) showing lower regret than an earlier replicable baseline.

I lean toward a weak reject. The idea is promising, but the paper is hard to follow and does not feel sufficiently self-contained and well-organized.

Parts of the mathematical exposition also look somewhat LLM-generated, particularly the lengthy expansions of routine calculations, although this is only a stylistic impression and not evidence of authorship.

Critical strengths

I like the idea of rounding in the geometry of the confidence ellipsoid.

The fixed-design estimator argument looks sound, and the ability to handle shared, time-varying action sets is a useful contribution.

The GLM extension also gives the approach some breadth.

Critical weaknesses

The introduction and the embedded related-work discussion is hard to follow. Some terms are defined in this section, others are defined later on, some (like C_{ME}) are not defined explicitly. It also seems that related-work should address Eaton et al.’s replicable ridge regression and Komiyama et al.’s finite-action linear-bandit result. 

The experiments are somewhat limited and narrow. They use one low-dimensional, very low-noise setting. I think that the experimental setting should be extended. Additionally, reporting empirical agreement of (0.80) at a target of (0.80) does not establish that the underlying replicability requirement is met. I would like to see per-instance agreement rates and clarification of whether the tuned parameters preserve the theoretical guarantee.

Parts of the mathematical exposition also look somewhat LLM-generated to me, particularly the repeated, lengthy expansions of routine calculations. This is a stylistic impression. Shortening these repetitions and giving more attention to the delicate conditioning and parameter assumptions would make the paper easier to read.

Questions for authors

My main concern is the comparison with earlier elimination methods. Starting from the older estimator’s sample complexity, a standard geometric-accuracy elimination schedule seems capable of achieving (1/\rho) regret dependence already for fixed action sets. What prevents this argument from going through?

Why the experimental setting is so limited?

7 comments

We thank the reviewer for the careful reading and for the positive comments: that rounding in the geometry of the confidence ellipsoid is a promising idea, that the fixed-design estimator argument looks sound, that handling shared, time-varying action sets is a useful contribution, and that the GLM extension gives the approach breadth. We next address their concerns below.


1. Comparison with prior work: W1 (second part), Q1

  • Comparison with Eaton et al. (2026). Their replicable ridge regression assumes independently drawn data, rounds the estimate coordinate by coordinate in the original parameter space, and gives an ℓ2\ell_2 error bound around the population regularized minimizer once a sample-size threshold is met. RepRidge differs in three ways:

    • It makes no distributional assumption, and it stays ρ\rho-replicable under adaptively chosen designs shared across runs (Lemma E.3). This is the bandit setting with time-varying At\mathcal A_t.
    • It rounds the whitened estimate Vn1/2θ^nV_n^{1/2}\hat\theta_n, so the rounding error takes the shape of the confidence ellipsoid. Rounding in the original coordinates would inflate the VnV_n-norm radius by κ(Vn)\sqrt{\kappa(V_n)}.
    • It returns a VnV_n-norm ellipsoid around θ⋆\theta^\star at every nn, which is what the optimistic index of RepLinUCB requires.

     

    Where the two are directly comparable (a core-set design with uniform prediction error ε\varepsilon), their Theorem 3.2 needs at least order d5/(ε6ρ2)d^5/(\varepsilon^6\rho^2) samples. Our Proposition 3.1 needs d4/(ε2ρ2)d^4/(\varepsilon^2\rho^2). None of our main results (Theorem 3.1 with Lemma E.3, and Theorems 4.1 and 5.1) follows from their construction. We added a comparison with Eaton et al. as Remark 3.1 in Section 3.1, and a detailed discussion in Appendix A. A full comparison is in our response to Reviewer qeP5.

     

  • Comparison with Komiyama et al. (2026). Their replicable linear elimination algorithm is stated for a fixed set of KK actions. Its regret grows linearly in KK because the replicability budget is split across per-arm elimination decisions. It does not cover the infinite time-varying action sets of the standard linear bandit setting of Abbasi-Yadkori et al. (2011), which we study in Theorems 4.1 and 5.1. We now discuss it in the related-work section and in Table 1.

     

  • Elimination with a geometric-accuracy schedule (Q1). Our main results (Theorems 4.1 and 5.1) are for the standard linear bandit setting of Abbasi-Yadkori et al. (2011), in which the action set At\mathcal A_t may change every round. The reviewer's argument relies on a fixed action set in two places, and neither carries over to this setting:

    1. Estimator. The replicable least-squares estimator of Esfandiari et al. (Lemma 9) pulls each action of a fixed core set many times. With changing At\mathcal A_t, a core action is generally no longer available, and a given action may appear only once.
    2. Schedule. An elimination schedule makes O(log⁡T)O(\log T) policy updates. Ruan et al. (STOC 2021, Theorem 8) show that, when the action sets are fixed in advance by an adversary, as in our setting, Ω(dlog⁡T/log⁡(dlog⁡T))\Omega(d\log T/\log(d\log T)) policy switches are needed for any T\sqrt T-type regret. This holds even with two actions per round, and for any algorithm, replicable or not. RepLinUCB's determinant-triggered batching uses O(dlog⁡T)O(d\log T) updates.

For a single fixed action set, a geometric-accuracy schedule would improve the ρ\rho-dependence of Esfandiari et al. (Theorem 10). Their Algorithm 4 ties each batch's accuracy to a geometric grid in time and then multiplies the batch length by the replicability blow-up, so the blow-up enters the regret linearly. Fixing the accuracy of each phase instead (phased elimination with ϵp=2−p\epsilon_p=2^{-p}; Lattimore and Szepesvári, 2020, Ch. 22) places it under a square root. However, even for fixed action sets, elimination differs from RepLinUCB in several respects:

  • Computation. The algorithm of Esfandiari et al. for infinite action sets discretizes with a 1/T1/T-net and runs in time polynomial in TdT^d. RepLinUCB only needs the LinUCB maximization over At\mathcal A_t.
  • Data reuse. Phased elimination estimates from each phase's fresh samples only. RepRidge's guarantee holds for adaptively collected data, so RepLinUCB uses all past data at every batch start.
  • Empirical behavior. RepLinUCB attains 5.8×5.8\times lower regret than elimination at ρ=0.2\rho=0.2, and lower regret at every ρ∈[0.05,0.5]\rho\in[0.05,0.5] we tested.
  • Extensions. Many extensions of linear bandits are built on optimistic confidence sets: bandits with knapsacks (Agrawal and Devanur, 2016), conservative bandits (Kazerouni et al., 2017), safe bandits (Amani et al., 2019), and non-stationary bandits (Cheung et al., 2019; Russac et al., 2019). Bollini et al. (2026) note that elimination-based replicable algorithms do not readily extend to constrained settings, and they point to non-stationary settings as another case that favors optimism. Since RepRidge provides a replicable confidence ellipsoid, such constructions can in principle be made replicable by substituting it for their confidence set, as RepGLMUCB does for generalized linear bandits.

 

To our knowledge, RepLinUCB and RepGLMUCB are the first replicable algorithms for linear and generalized linear bandits with time-varying action sets and with regret optimal in TT and ρ\rho. This is the setting of most linear bandit applications (e.g., Li et al., 2010) and of replicability-motivated ones such as digital health (Zhang et al., 2025), where each patient arrives with new features.


2. Experiments: W2, Q2

  • Scope. Our main contributions are theoretical, and the paper is submitted under the learning theory primary area. Replicability has so far been studied mainly from a theoretical perspective: the replicable bandit papers of Esfandiari et al. (2023), Ahmadi et al. (2025) and Bollini et al. (2026) contain no experiments, and Komiyama et al. (2026) report a single simulation at T=104T=10^4. Nevertheless, we have substantially extended our experiments in the new Appendix G of the update paper, in two directions. Here we summarize these experiments; for full details see the updated paper.

     

  • Theoretical parameters and per-instance replicability. In Figure 1, all algorithms are tuned on held-out instances subject to agreement at least 1−ρ1-\rho, as is standard for bandit algorithms (e.g., Zhou et al., 2020; Ding et al., 2022) and as Komiyama et al. (2026) do for replicable ones; the 0.800.80 is the agreement of the tuned configuration. To ensure that the theoretical guarantee applies, we also ran RepLinUCB and Elimination (Esfandiari et al., Theorem 10) with exactly the hyperparameters prescribed by their theorems, on 50 instances with 2,000 pairs of runs each, ρ∈{0.1,…,0.5}\rho\in\{0.1,\dots,0.5\}, and T=1012T=10^{12} . We check replicability on each instance separately, using a one-sided 95% Clopper–Pearson lower bound on its agreement. In the setting of Figure 1, both algorithms are ρ\rho-replicable on all 50 instances for every ρ\rho, with agreement far above 1−ρ1-\rho, and RepLinUCB has lower regret on every instance, by a factor of at least 6.76.7 in the mean (Table A).

     

    Table A. Setting of Figure 1 (d=5d=5, σ=10−3\sigma=10^{-3}, T=1012T=10^{12}). Regret: mean ± one standard error over the 50 instances, in units of 10610^6. Ratio: Elimination's mean regret divided by RepLinUCB's. Min. agreement: smallest per-instance agreement over the 50 instances. ρ\rho-replicable: number of instances whose one-sided 95% Clopper–Pearson lower bound on agreement is at least 1−ρ1-\rho.

    ρ\rhoRegret, RepLinUCB (×106\times10^6)Regret, Elim. (×106\times10^6)RatioMin. agreement, RepLinUCBMin. agreement, Elim.ρ\rho-replicable, RepLinUCBρ\rho-replicable, Elim.
    0.17.6 ± 1.250.3 ± 8.76.70.99450.999550/5050/50
    0.21.57 ± 0.2717.2 ± 6.810.90.98850.999550/5050/50
    0.30.66 ± 0.1210.7 ± 6.116.30.98550.999050/5050/50
    0.40.361 ± 0.0648.4 ± 5.823.30.98150.998050/5050/50
    0.50.227 ± 0.0417.2 ± 5.531.70.97900.998050/5050/50

     

  • Ablation over the dimension and the noise level. With the same theoretical parameters and protocol, we vary d∈{2,5,10,15,20}d\in\{2,5,10,15,20\} with σ=10−3\sigma=10^{-3} (Table B), and σ∈{10−3,0.01,0.05,0.1,0.5,1}\sigma\in\{10^{-3},0.01,0.05,0.1,0.5,1\} with d=5d=5 (Table C). In all 10 settings and for every ρ\rho, both algorithms are ρ\rho-replicable on all 50 instances; the smallest per-instance agreement of RepLinUCB over all settings is 0.9380.938 (σ=1\sigma=1, ρ=0.5\rho=0.5, where the requirement is 0.50.5). RepLinUCB has lower mean regret than Elimination in every setting and for every ρ\rho.

     

    Table B. Varying the dimension dd (σ=10−3\sigma=10^{-3}, T=1012T=10^{12}). Regret: mean ± one standard error over the 50 instances, in units of 10610^6. Ratio: Elimination's mean regret divided by RepLinUCB's. Min. agreement: smallest per-instance agreement over the 50 instances. In every row, both algorithms are ρ\rho-replicable on all 50 instances: the one-sided 95% Clopper–Pearson lower bound on each instance's agreement is at least 1−ρ1-\rho.

    ddρ\rhoRegret, RepLinUCB (×106\times10^6)Regret, Elim. (×106\times10^6)RatioMin. agreement, RepLinUCBMin. agreement, Elim.
    50.17.6 ± 1.250.3 ± 8.76.70.99450.9995
    0.21.57 ± 0.2717.2 ± 6.810.90.98850.9995
    0.30.66 ± 0.1210.7 ± 6.116.30.98550.9990
    0.40.361 ± 0.0648.4 ± 5.823.30.98150.9980
    0.50.227 ± 0.0417.2 ± 5.531.70.97900.9980
    100.1185 ± 18498 ± 382.70.99300.9995
    0.241.3 ± 5.0161 ± 363.90.98900.9995
    0.317.8 ± 2.497 ± 385.40.98350.9995
    0.49.9 ± 1.475 ± 387.50.98250.9990
    0.56.31 ± 0.9264 ± 3910.10.97400.9990
    150.11260 ± 711836 ± 891.50.99350.9995
    0.2276 ± 20510 ± 361.80.98750.9995
    0.3120 ± 10231 ± 171.90.98500.9995
    0.467.6 ± 6.4139 ± 132.00.98000.9995
    0.543.4 ± 4.590.3 ± 9.02.10.97900.9990
    200.16151 ± 3167099 ± 2981.20.99301.0000
    0.21378 ± 872090 ± 1321.50.98950.9995
    0.3594 ± 401070 ± 941.80.98450.9995
    0.4329 ± 23665 ± 742.00.98250.9990
    0.5209 ± 15425 ± 472.00.97800.9990

     

    Table C. Varying the noise level σ\sigma (d=5d=5, T=1012T=10^{12}). Regret: mean ± one standard error over the 50 instances, in units of 10610^6. Ratio: Elimination's mean regret divided by RepLinUCB's. Min. agreement: smallest per-instance agreement over the 50 instances. In every row, both algorithms are ρ\rho-replicable on all 50 instances: the one-sided 95% Clopper–Pearson lower bound on each instance's agreement is at least 1−ρ1-\rho.

    σ\sigmaρ\rhoRegret, RepLinUCB (×106\times10^6)Regret, Elim. (×106\times10^6)RatioMin. agreement, RepLinUCBMin. agreement, Elim.
    0.0010.17.6 ± 1.250.3 ± 8.76.70.99450.9995
    0.21.57 ± 0.2717.2 ± 6.810.90.98850.9995
    0.30.66 ± 0.1210.7 ± 6.116.30.98550.9990
    0.40.361 ± 0.0648.4 ± 5.823.30.98150.9980
    0.50.227 ± 0.0417.2 ± 5.531.70.97900.9980
    0.010.1358 ± 32381 ± 521.10.99050.9975
    0.286 ± 10124 ± 291.40.98450.9960
    0.338.3 ± 5.271 ± 241.80.97800.9950
    0.421.7 ± 3.148 ± 212.20.97300.9940
    0.514.0 ± 2.134 ± 162.40.96800.9935
    0.050.14122 ± 1925601 ± 3111.40.98850.9945
    0.21092 ± 711671 ± 1141.50.98100.9915
    0.3519 ± 42854 ± 771.60.97100.9885
    0.4306 ± 28559 ± 691.80.96700.9820
    0.5203 ± 21366 ± 501.80.95750.9820
    0.10.110839 ± 37517184 ± 6741.60.99100.9950
    0.23078 ± 1545333 ± 2741.70.98000.9925
    0.31492 ± 902784 ± 1731.90.96900.9875
    0.4894 ± 621769 ± 1372.00.95900.9825
    0.5602 ± 471158 ± 921.90.95400.9785
    0.50.173454 ± 1293158446 ± 21492.20.98550.9950
    0.226645 ± 55260268 ± 9812.30.97400.9925
    0.314437 ± 43636334 ± 9012.50.96350.9845
    0.49197 ± 33925774 ± 9762.80.95250.9835
    0.56446 ± 26916740 ± 6172.60.94100.9770
    10.1143518 ± 3317305819 ± 36792.10.98600.9950
    0.258589 ± 950135940 ± 14432.30.97300.9915
    0.333664 ± 60292908 ± 14622.80.95950.9815
    0.422381 ± 51672559 ± 16433.20.94950.9820
    0.516179 ± 45947280 ± 10232.90.93800.9815

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.