acceptodds
Under review as a conference paper at ICLR 2027

The Price of Tail Safety in Heavy-tailed Bandits

Abstract

Traditional bandit algorithms focus on minimizing expected regret to achieve good average performance. However, low expected regret can mask tail risk—the possibility of exceptionally large regret on individual runs, which can be unacceptable in risk-sensitive applications. Under heavy-tailed rewards, extreme observations can distort reward estimates and lead to large regret. Additional exploration can make these estimates more reliable and reduce this risk, but at the cost of higher expected regret. We study this trade off under a known bound on the centered -th moment. Our target is pseudo-regret, which measures decision error: realized payoff shortfall also contains reward noise that can cause large losses even for an oracle. We establish matching upper and lower bounds relating a worst-case expected-regret budget to the pseudo-regret tail probability. For fixed and a fixed number of arms, a budget of order times the minimax regret scale yields a -fold improvement in the negative-log tail rate, up to constants. We therefore propose Budget-Calibrated Robust Racing (BCRR), a novel algorithm that jointly calibrates exploration and robust arm elimination to the expected-regret budget, attaining the optimal trade off between average performance and tail protection. Numerical experiments demonstrate the algorithm's effectiveness in controlling the risk of large decision errors.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Tail Safety, Bandits, Online Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_KADiOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper studies the tradeoff between worst-case expected pseudo-regret and pseudo-regret tail probabilities in heavy-tailed stochastic bandits with known moment parameters. It proposes a robust elimination algorithm and presents matching upper and lower bounds for fixed KK and ε\varepsilon over a specified threshold range.

Critical strengths
  • The paper addresses a meaningful question beyond expected-regret minimization: what tail protection is achievable under a prescribed worst-case expected-regret budget? Its matching minimax tail exponents for fixed KK and ε\varepsilon over the stated threshold range provide a useful finite-moment extension of existing regret-distribution results.
  • The proposed algorithm explicitly links the regret budget, elimination radius, and confidence level. Its analysis accounts for the sample-size requirements of robust estimation and achieves the tradeoff without an additional log⁡T\log T loss, providing a constructive counterpart to the lower bound.
Critical weaknesses

None

Questions for authors

Proposition 4 in Appendix E is conditional on Assumption 2. Is this assumption achievable over the stated class? Rare-contamination alternatives appear incompatible with its simultaneous coverage and adaptive-radius guarantees: the narrow interval required under a point mass at zero can miss the mean of an admissible heavy-tailed distribution producing the same all-zero sample with constant probability. This concern is confined to Appendix E and does not undermine the main known-parameter results.

3 comments

We thank the reviewer for the valuable feedback and for identifying this issue in the unknown-moment extension. We have checked your rare-contamination argument and agree that Assumption 2 in the original submission is not achievable over the full stated moment class when ϵmin⁡<1\epsilon_{\min}<1. Our main expectation–tail trade-off in Theorems 2–4 assumes known moment parameters and does not depend on Assumption 2.

Q1. Achievability of Assumption 2 in the original Appendix E

1. The rare-contamination argument gives a contradiction. The original Assumption 2 required a confidence interval computed without knowing the moment parameters (v,ϵ)(v,\epsilon), with guarantees for every ϵ∈[ϵmin⁡,1]\epsilon\in[\epsilon_{\min},1]; ϵmin⁡>0\epsilon_{\min}>0 is a known lower bound. Fix ϵ0∈[ϵmin⁡,1)\epsilon_0\in[\epsilon_{\min},1), write p=1+ϵ0p=1+\epsilon_0, and take K=2K=2, T=2nT=2n, v=1v=1, and ρ=log⁡n\rho=\log n. Compare

\qquad P_n=\left(1-\frac{1}{2n}\right)\delta_0 +\frac{1}{2n}\delta_{n^{1/p}},$$ where $\delta_b$ denotes a point mass at $b$. The second distribution has $$\mu_n=\frac12n^{-\epsilon_0/(1+\epsilon_0)}\in[0,1], \qquad \mathbb E_{P_n}|X-\mu_n|^{1+\epsilon_0}\le1.$$ For these choices of $(K,T,v,\rho)$, the original Assumption 2 required the probability of failing to cover the true mean to tend to zero uniformly over the stated moment class. Under $P_0$, its requirement at $\epsilon=1$ also gives coverage of zero and radius at most $w_n=C(\log n)^b/\sqrt n$ with probability tending to one, for fixed constants $C,b>0$. Since $\epsilon_0/(1+\epsilon_0)<1/2$, we have $\mu_n/w_n\to\infty$. Under $P_n$, the same all-zero sample occurs with probability $(1-1/(2n))^n\to e^{-1/2}$. Because the procedure does not use the true moment parameters, these identical data give the same interval, or the same distribution of intervals if randomized. For sufficiently large $n$, $\mu_n>2w_n$, so an interval containing zero with radius at most $w_n$ cannot contain $\mu_n$. The probability that the interval misses $\mu_n$ therefore stays bounded away from zero, contradicting the uniform coverage requirement. **2. We have removed the original unknown-moment extension, including Assumption 2 and Proposition 4.** The revised Appendix E now contains the construction and proofs of a new instance-dependent extension under known moment parameters, with Theorems 5–6 stated in Section 7. **Theorem 5** provides a gap-dependent expected-regret bound and a tail bound for each fixed instance. **Theorem 6** establishes the necessary growth of a general fixed-instance budget $f(T)$ and matching worst-case tail rates under simultaneous worst-case and fixed-instance expected-regret budgets. We have moved the original material from Section 7 to **Appendix D (Sections D.2–D.4)**. **3. The main results use known moment parameters and remain unaffected.** **Theorem 2 (Appendix B.4)** uses the explicit robust estimator in **Proposition 2** and the phase analysis; **Theorem 3 (Appendix B.5)** follows by integrating that tail bound; and **Theorem 4 (Appendix C.2)** uses the moment-constrained distributions in **Lemma 5** and the change-of-measure argument. The proofs of Theorems 2–4 do not use Assumption 2 or Proposition 4. We thank the reviewer again for helping us improve the rigor and clarity of the manuscript.

Thank you for the clarification and revision. Removing the original Assumption 2 and conditional Proposition 4 resolves my concern. I will update my soundness score from 2 to 3 and maintain my overall rating

We thank the reviewer for the careful evaluation and constructive feedback. Your comment helped us improve the rigor of the manuscript and clarify the scope of our results. We appreciate your reassessment and are pleased that the revision has resolved your concern.

Reviewer_Y9kqOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies regret tails of heavy tailed multi armed bandits, where the rewards are only assumed to have a bounded 1+ϵ1 + \epsilon moment instead of being subgaussian. They propose a phased elimination algorithm and prove a oneway concentration inequality for the regret, which matches the known optimal concentration for subgaussian rewards(when ϵ=1\epsilon = 1) up to log⁡K\sqrt{\log K} factor. They further prove a lower bound, showing the concentration achieved by the algorithm is optimal upto a logKlog K factor, and for observed regret an extra unavoidable polynomial term in TT. They also extend their results to unknown time horizon setting with doubling technique and do numerical experiments to showcase the regret tail behavior empirically.

Critical strengths
  • The paper studies an important problem in heavy tailed bandits, characterizing best achievable regret tails when the rewards themselves are heavytailed and they provide a tight worst-case characterization up to logarithmic factors
Critical weaknesses
  • the proposed algorithm is suboptimal even in terms of expected regret with an extra polylog K\text{polylog } K factor, whereas regret without log term is achievable [1], although this is pointed out in the paper.
  • The proofs are mostly extension of the subgaussian regime proofs in [2] but the paper fails to generalize the characterization to instance dependent tails present in [2] and [3].

[1] Wei, Lai, and Vaibhav Srivastava. "Minimax policy for heavy-tailed bandits." IEEE Control Systems Letters 5, no. 4 (2020): 1423-1428.

[2] Simchi-Levi, David, Zeyu Zheng, and Feng Zhu. "Regret distribution in stochastic bandits: Optimal trade-off between expectation and tail risk." arXiv preprint arXiv:2304.04341 (2023).

[3] Lee, Harin, and Min-hwan Oh. "Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning." arXiv preprint arXiv:2605.05102 (2026).

Questions for authors
  • The tail optimal algorithm for subgaussian MAB is a UCB type algorithm with modified exploration bonus terms. Some known algorithms that achieves log free (in K) expected regret in heavy tailed setting are robust variants of UCB([1]). Did the authors consider this, or other types of algorithms that are at least optimal in expected regret, and if so what was some technical challenges that prevented both nearly-optimal regret tails and log less optimal expected regret?
  • Similarly, the instance dependent characterization of expected regret is known for heavy tailed bandits, can the paper be generalized for instance dependent regret tails, or any blackbox instance dependent regret f(T)f(T)?

[1] Wei, Lai, and Vaibhav Srivastava. "Minimax policy for heavy-tailed bandits." IEEE Control Systems Letters 5, no. 4 (2020): 1423-1428.

7 comments

We thank the reviewer for the valuable feedback and questions on optimality and technical novelty. Our focus, as in [2], is the trade-off between expected regret and tail safety. We establish this trade-off under only a finite (1+ϵ)(1+\epsilon)-moment assumption.

Our technical novelty is to control the regret caused by robust-estimation errors within the expected-regret budget and construct reward distributions that give a matching lower bound under the moment constraint. The sub-Gaussian arguments in [2] do not directly establish this finite-moment trade-off.

We have extensively revised the manuscript to address your questions on instance-dependent regret tails and a general instance-dependent expected-regret bound f(T)f(T). Section 7 now presents two new theorems: Theorem 5 gives a gap-dependent expected-regret bound and a tail bound for each fixed instance; Theorem 6 gives a necessary condition on f(T)f(T) and matching worst-case tail bounds when both the worst-case and instance-dependent expected regret are constrained. The full construction and proofs are in Appendix E. We have moved the original material from Section 7 to Appendix D (Sections D.2–D.4).

Write p=1+ϵp=1+\epsilon, R=RT⋆=v1/pKϵ/pT1/pR=R_T^\star=v^{1/p}K^{\epsilon/p}T^{1/p}, and q=R/Kq=R/K. RegT\mathrm{Reg}_T denotes pseudo-regret.

W1. The logarithmic gap and the meaning of optimality

We acknowledge the remaining logarithmic gap in KK relative to the minimax expected-regret rate. The expected-regret bound in [2] also retains a logarithmic factor in KK. As in [2], our tail optimality concerns the dependence on TT for fixed KK.

1. The cited work [2] also retains a logarithmic gap in its expected-regret guarantee. Setting α=1/2\alpha=1/2 in Proposition 4.3 gives

=O(\sqrt{KT\log K}),$$ which retains a $\sqrt{\log K}$ factor relative to the log-free $O(\sqrt{KT})$ benchmark. **2. In [2], optimality refers to the dependence on $T$.** [Section 2.1, Remark 1](https://arxiv.org/html/2304.04341v2#S2.SS1) explicitly defines optimality through the dependence on $T$, without requiring sharp dependence on $K$. Corollaries 3.4 and 4.2 in [2] match the tail power exponents in $T$. **3. For fixed $K$, our upper and lower tail bounds also match in their dependence on $T$.** Theorems 2–4 prove this for a given expected-regret budget. For a direct comparison, choosing $\rho=(1+\log K)^{\epsilon/(1+\epsilon)}$ in Theorem 3 gives $$\sup_\nu\mathbb E_\nu[\mathrm{Reg}_T] \lesssim R(1+\log K)^{\epsilon/(1+\epsilon)}.$$ At $\epsilon=1$ and fixed $v$, our expected-regret bound has the same $K,T$ order as [2], under only finite variance. With this choice of $\rho$, the upper and lower tail bounds match at budget $B_T\asymp\rho R$ for $CB_T\le z\le cT$, whenever this interval is nonempty. The log-free $O(R)$ expected-regret bound in [1] does not by itself establish the optimal decay of the worst-case tail probability $\sup_\nu\Pr_\nu(\mathrm{Reg}_T>z)$ under an $O(R)$ expected-regret budget. In the Conclusion and Limitations, we list achieving a minimax-optimal expected-regret bound uniformly in $K$, while preserving tail safety, as future work.

W2. The finite-moment technical contribution

Our technical contribution is to prove how the expected-regret budget limits the probability of large regret under finite-moment rewards. We prove a regret-tail upper bound for BCRR and prove a lower bound with the same exponent for every policy satisfying the same budget, in the stated threshold range.

1. Upper-bound novelty: proving which estimation errors can cause large regret. [2]'s Theorem 4.1 proof uses exponential bounds on sample-mean deviations over a range of sample sizes. Our assumption E∣X−μ∣p≤v\mathbb E|X-\mu|^p\le v does not ensure these bounds, even when ϵ=1\epsilon=1. After replacing the sample mean with a robust estimate, we still need to prove which estimation errors can cause large regret and bound their total probability without exceeding the exploration budget.

With nn samples per active arm, we choose the confidence parameter u(n)u(n) so that the robust estimation radius equals Cϵρq/nC_\epsilon\rho q/n:

=C_\epsilon\rho q/n \quad\Longrightarrow\quad u(n)=\rho^{p/\epsilon}(T/(Kn))^{1/\epsilon}.$$ The robust concentration bound applies only at valid phases, where $1\le u(n)\le n/32$. The regret incurred before the first valid phase is included in $O(\rho R)$. Write $n_s$ for the number of samples per active arm at phase $s$. For $D\rho R\le y < T$, choose a phase $s_y$ with $n_{s_y}\asymp\rho qT/y$. Let $\mathcal G_s$ be the event that all estimates differ from their true means by at most the chosen radius at phase $s$, and let $\mathcal V_y$ denote the set of valid phases up to and including $s_y$. **We prove that regret above $C\rho R+y$ requires an inaccurate estimate at some phase in $\mathcal V_y$:** $$\\{\mathrm{Reg}_T > C\rho R+y\\} \subseteq \bigcup_{s\in\mathcal V_y}\mathcal G_s^c.$$ At phase $s_y$, $u(n_{s_y})\asymp\rho(y/R)^{1/\epsilon}$. At the earlier dyadic sample sizes, halving $n$ multiplies $u(n)$ by $2^{1/\epsilon}$. Summing the phase error probabilities gives $$\Pr(\mathrm{Reg}_T > C\rho R+y) \le\sum_{s\in\mathcal V_y}CKe^{-cu(n_s)} \lesssim K e^{-c'\rho(y/R)^{1/\epsilon}}.$$ This is the key step in **Theorem 2 (Appendix B.4)**, and the sum introduces no extra $\log T$ factor. **2. Lower-bound novelty: proving a matching lower bound under the moment constraint.** **For $\epsilon < 1$, the Gaussian reward distributions used in [2] are too easy to distinguish at small gaps to give a lower bound matching our upper bound.** In [2]'s [Theorem 3.1 proof](https://arxiv.org/html/2304.04341v2#A1), the Gaussian reward distributions have different means. Under our moment constraint, their common variance can be at most $O(v^{2/p})$. Even at this variance scale, their one-sample KL is $\asymp\Delta^2/v^{2/p}$. In a base instance with gap $\Delta$ for every suboptimal arm, choose the suboptimal arm $j$ with the fewest expected pulls. Let $N_j(T)$ be its pull count and $\mathbb E_0$ denote expectation on this instance. Averaging the budget over the $K-1$ suboptimal arms gives $\mathbb E_0N_j(T)\lesssim B_T/(K\Delta)$. The KL divergence between the distributions of all selected arms and observed rewards before and after changing arm $j$ is therefore bounded by $$D_{\mathrm G}\lesssim\frac{B_T\Delta}{K v^{2/p}}.$$ For a small normalized gap $\delta=\Delta/v^{1/p}$, the Gaussian KL scale $\delta^2$ is larger than $\delta^{p/\epsilon}$ because $p/\epsilon > 2$. A larger KL divergence gives a smaller probability lower bound through change of measure, so this Gaussian construction does not give the matching exponent. In **Lemma 5 (Appendix C.1)**, we choose the size $h\asymp(v/\Delta)^{1/\epsilon}$ and probability $\theta\asymp\Delta/h$ of rare, large rewards **to obtain the required mean gaps and KL divergence while satisfying the moment constraint.** The reward distributions $P_0,P_1,P_2$ have means $0,\Delta,2\Delta$, respectively, obey the centered $p$th-moment constraint, and satisfy $$\theta h\asymp\Delta,\qquad \theta h^p\lesssim v,\qquad \mathrm{KL}(P_0\Vert P_2)\lesssim\theta \asymp\frac{\Delta^{p/\epsilon}}{v^{1/\epsilon}}.$$ Under the same bound on $\mathbb E_0N_j(T)$, let $\mathbb P_0,\mathbb P_j$ denote the distributions of all selected arms and observed rewards before and after changing arm $j$ from $P_0$ to $P_2$. Then $$\mathrm{KL}(\mathbb P_0\Vert\mathbb P_j) \lesssim\frac{B_T}{K\Delta} \frac{\Delta^{p/\epsilon}}{v^{1/\epsilon}} =\frac{B_T}{R}\left(\frac{T\Delta}{R}\right)^{1/\epsilon}.$$ Setting $\Delta=4z/T$ and applying the binary KL inequality in **Lemma 4 (Appendix C.1)** gives the expected-regret-budget lower bound in **Theorem 4 (proof in Appendix C.2)**. With the budget and threshold range stated in W1, Theorem 4 matches the tail exponent in Theorem 2. **The instance-dependent extension is addressed in Q2.**

Q1. Can we modify Robust MOSS to obtain optimal regret tails and log-free expected regret?

We considered modifying Robust MOSS at the beginning of the project. The aim was to obtain matching regret tails while keeping its log-free worst-case expected-regret bound. Two difficulties arise.

1. BCRR's tail bound requires more exploration than Robust MOSS uses on some fixed instances. Robust MOSS achieves both log-free minimax expected regret and Oν(log⁡T)O_\nu(\log T) expected regret on fixed instances (Theorems 7–8 of [1]). In Theorem 7 (Appendix C.3), the fixed instances ν0,ν1\nu^0,\nu^1 differ only in arm 2: its distribution is P0P_0 (mean 00) under ν0\nu^0 and P2P_2 (mean 2Δ02\Delta_0) under ν1\nu^1; arm 1 has mean Δ0\Delta_0 in both. After constant rescaling, these reward distributions satisfy Robust MOSS's raw-moment assumption, so E0N2(T)=O(log⁡T)\mathbb E_0N_2(T)=O(\log T). Write P0,P1\mathbb P_0,\mathbb P_1 for the corresponding distributions of all selected arms and observed rewards. Then

=\mathbb E_0N_2(T)\\,\mathrm{KL}(P_0\Vert P_2) =O(\log T) \quad\Longrightarrow\quad \Pr_1(\mathrm{Reg}_T > \Delta_0T/4)\ge cT^{-C}.$$ For fixed $(K,v,\epsilon)$ and sufficiently large $T$, this polynomial lower bound prevents the original Robust MOSS algorithm from achieving BCRR's $\exp[-c'T^{1/p}]$ tail bound at threshold $\Delta_0T/4$ and a minimax-order expected-regret budget. Under a sublinear expected-regret budget on $\nu^0$, achieving BCRR's tail bound requires $\mathrm{KL}(\mathbb P_0\Vert\mathbb P_1)=\Omega(T^{1/p})$, hence $\mathbb E_0N_2(T)=\Omega(T^{1/p})$. **A modified Robust MOSS must therefore sample arm 2 more often on $\nu^0$.** **2. For modified Robust MOSS, we must prove both the tail bound and the log-free worst-case expected-regret bound.** **(a) Controlling estimation errors after changing the exploration bonus.** A fixed-sample robust concentration bound does not by itself bound regret over the full adaptive sampling process. W2 and the **proof of Theorem 2 (Appendix B.4)** explain how BCRR controls estimation errors and exploration costs. **(b) Preserving the log-free worst-case expectation bound after increasing exploration.** In our analysis of BCRR, the union bound over arms gives the factor $CK$ in the tail bound. Integrating this bound gives $$\mathbb E\mathrm{Reg}_T \lesssim R\bigl[\rho+\rho^{-\epsilon}(1+\log^\epsilon(CK))\bigr].$$ Removing the logarithmic factor in $K$ while preserving the tail bound remains open in our analysis. For fixed $K$, our upper and lower bounds already establish the trade-off between the expected-regret budget and tail safety, under the stated budget calibration and threshold range. **This trade-off under finite-moment rewards is the focus of our paper.**
Reviewer_51HVOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the trade-off between worst-case expected pseudo-regret and regret-tail probabilities in stochastic multi-armed bandits with a known bound on the centered 1+ε1+\varepsilon-th reward moment. It first separates decision-induced regret from realized payoff shortfall, showing that the latter retains an unavoidable polynomial reward-noise component even for an oracle.

The proposed Budget-Calibrated Robust Racing algorithm, BCRR, combines median-of-means estimation with phased elimination. Its elimination radius and confidence parameter are calibrated to an expected-regret allowance, and elimination is postponed until the sample size supports the required confidence. For fixed ε\varepsilon and K, the paper establishes matching upper and lower tail exponents under a budget of order ρRT⋆\rho R_T^\star, over a specified threshold range. Further results include quantile bounds, an unknown-horizon extension, and an incompatibility with logarithmic regret on every fixed separated instance. Experiments use synthetic Pareto rewards and resampled financial residuals.

Critical strengths

A meaningful finite-moment budget–tail characterization. The central contribution is the combination of an achievable tail bound with a converse applying to any policy satisfying the prescribed worst-case expected-regret budget. For fixed K and ε\varepsilon, their dependence on the budget multiplier and regret threshold matches up to constants within the stated range. This extends the expectation–tail trade-off studied by Simchi-Levi et al. to a weaker reward model. It also addresses a different objective from the fixed-instance asymptotic analysis of Panda and Agrawal. The contribution is therefore more substantial than an additional expected-regret bound for a robust bandit algorithm.

The policy design and scope of the guarantees are carefully connected. Matching the budget-based elimination radius to the finite-moment estimation radius yields an explicit confidence schedule and sample-size requirement. The proof accounts for exploration during invalid phases, while the oracle construction explains why the same tail guarantee cannot apply directly to realized payoff shortfall. The unknown-horizon extension and the instance-dependent efficiency barrier further clarify what the proposed protection does and does not provide.

Critical weaknesses

The gap between the theoretical calibration and the experimental policy is substantial. Algorithm 1 sets Aε=CεA_\varepsilon=C_\varepsilon from Proposition 2, whose explicit construction gives Cε=(16⋅18p−1)1/p,p=1+εC_\varepsilon=(16\cdot18^{p-1})^{1/p},\qquad p=1+\varepsilon. In the main experiment, ε=0.5\varepsilon=0.5, v=1, K=2, and T=1600, giving Aε≈16.64A_\varepsilon\approx16.64 and qT≈86.18q_T\approx86.18. With τ=2.2\tau=2.2 and ρ=1\rho=1, even at the largest phase size n=800, τaρ,T(800)≈3.94>1\tau a_{\rho,T}(800)\approx3.94>1. Since estimates are clipped to ([0,1]), no elimination can occur with these explicit constants; the threshold is still larger for (\rho=2,4). Algorithm 1 would consequently allocate 800 pulls to each arm and incur pseudo-regret (144) in this setting. The reported experiments instead use a radius multiplier of (0.08) and a modified validity multiplier. These choices are disclosed, but the paper does not establish what finite-sample protection survives this change. This does not invalidate the asymptotic-order theorem, but it substantially limits the experiments’ ability to validate the theoretically calibrated policy.

The empirical comparisons provide limited evidence of a practical advantage at comparable mean cost. Figure 2A appears to show substantially smaller 99% median-centered excess quantiles for MoM-UCB than for BCRR over overlapping mean-regret costs. The financial-residual comparison in Figure 3D also appears broadly comparable across methods. This is compatible with BCRR’s worst-case theorem, but deserves explicit discussion when assessing its practical benefit. Moreover, the supplementary comparisons largely use quantiles after subtracting each configuration’s own median. These are informative about dispersion but do not directly establish protection at a common absolute regret threshold. The 99% quantile comparison in Figure 2A uses 800 replications, leaving only about eight observations in the upper 1%, without reported uncertainty intervals. Consequently, the practical comparative conclusion remains less convincing than the theoretical contribution.

Questions for authors

Can you clarify the relationship between the implemented policy and Algorithm 1? Is the no-elimination calculation above correct for the explicit constants in Proposition 2? What guarantees, if any, apply to the experimental radius and validity multipliers? A direct comparison of the theoretical and practical calibrations would help establish the operational meaning of the proposed budget control.

1 comment

We thank the reviewer for the valuable feedback and the questions on calibration and empirical tail comparisons. We clarify which calibrations are covered by theory, compare tails at matched mean regret, and directly compare the theoretical and practical calibrations.

1. Response to Questions 1–3 and Weakness 1

We agree that the original experiments did not evaluate BCRR under its theoretical calibration. The implementation retained Algorithm 1's phased racing design but used empirical choices for the radius multiplier, validity condition, and MoM blocking that are not covered by our theoretical guarantees.

The reviewer's no-elimination calculation is correct. At T=1600T=1600, τaρ,T(800)≈3.94ρ>1\tau a_{\rho,T}(800)\approx3.94\rho>1, so the explicit constants give no elimination and regret 144144. To address this concern, we have modified the experiments in Section 8 to use the full theoretical calibration on two new instances, at T=50,000T=50{,}000 and T=100,000T=100{,}000.

2. Response to Weakness 2: Tail comparison at matched mean regret

In both settings, theoretically calibrated BCRR has lower observed tail probabilities at closely matched mean regret. Both settings use ρ=1\rho=1 and the explicit constant Aϵ=(16⋅18ϵ)1/(1+ϵ)A_\epsilon=(16\cdot18^\epsilon)^{1/(1+\epsilon)} from Proposition 2, without additional empirical radius scaling:

  • Setting 1: K=5K=5, T=50,000T=50{,}000, ϵ=1\epsilon=1.
  • Setting 2: K=10K=10, T=100,000T=100{,}000, ϵ=.98\epsilon=.98.

Rewards have centered Student-t3t_3 noise scaled to satisfy the moment bound v=1v=1. We tune the MoM-UCB and Mean-UCB multipliers on separate pilots to match unconditional mean regret, then evaluate on 30,00030{,}000 and 12,00012{,}000 fresh runs. The means (BCRR / MoM-UCB / Mean-UCB) are 4880.75/4881.83/4881.094880.75/4881.83/4881.09 and 9926.59/9926.53/9927.469926.59/9926.53/9927.46, respectively.

We report Pr⁡(R>xα)\Pr(R>x_\alpha), where RR is pseudo-regret and xαx_\alpha is MoM-UCB's empirical α\alpha-quantile. All three methods use the same absolute regret threshold at each reference level within a setting.

SettingMoM-UCB reference quantileBCRRMoM-UCBMean-UCB
190%4.36%10.00%6.22%
195%0.52%5.00%2.52%
199%0%1.00%0.33%
199.9%0%0.10%0.03%
290%4.53%10.00%7.06%
295%0.60%5.00%2.88%
299%0%1.00%0.38%
299.9%0%0.10%0.03%

At the 95% reference level, BCRR is less likely than MoM-UCB to have regret above the same threshold in both settings. The 95% simultaneous confidence intervals for this probability are [0%, 1.48%] for BCRR and [4.04%, 5.96%] for MoM-UCB in Setting 1. In Setting 2, they are [0%, 2.12%] for BCRR and [3.48%, 6.52%] for MoM-UCB. No BCRR run had regret above the 99% or 99.9% reference thresholds in either setting.

Regret was above the 95% reference threshold approximately 88–90% less often for BCRR than for MoM-UCB. Section 8 now reports these results and shows both survival curves in Figure 1; Appendix G gives the experimental configurations.

3. Direct comparison of the theoretical and practical calibrations

Reducing the radius coefficient can lower mean regret while increasing upper-tail regret on some instances. To isolate this effect, we vary only AϵA_\epsilon, from its theoretical value 288≈16.97\sqrt{288}\approx16.97 to smaller values, keeping the theoretical validity condition and MoM blocking unchanged.

We fix K=2K=2, T=262,144T=262{,}144, and ϵ=v=ρ=1\epsilon=v=\rho=1, and evaluate 19 coefficients on 100 prespecified instances, with 5,000 independent runs per instance and shared reward streams across coefficients. The instances comprise 20 light-tailed controls and 80 heavy-tailed instances, including skewed distributions and rare-shock stress tests. Relative to the theoretical calibration, the observed comparisons are:

Radius coefficientInstances with lower mean regretLower 99th percentileHigher 99th percentile
111001000
0.50.597973
0.080.08918713

Thus, Aϵ=0.08A_\epsilon=0.08 improves both metrics on 87 instances, but increases the 99th percentile on 13; four of these also have lower mean regret. For example, on a one-sided heavy-shock instance, it reduces mean regret from 16,38416{,}384 to 2,2922{,}292, while increasing the 99th percentile from 16,38416{,}384 to 65,02465{,}024. Regret was above the common threshold x=0.2Tx=0.2T in 0/5,0000/5{,}000 runs with the theoretical coefficient and 99/5,00099/5{,}000 runs with Aϵ=0.08A_\epsilon=0.08. In all 500,000 simulated runs, the theoretical calibration correctly eliminated the suboptimal arm with at least half the horizon remaining.

The improvement in both metrics at Aϵ=1A_\epsilon=1 on all 100 tested instances also illustrates the conservatism of our sufficient constants. Appendix G.1 gives the experimental details, and Table 3 reports the comparison.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.