- 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 and 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 and 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 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
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.
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. 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,ϵ), with guarantees for every ϵ∈[ϵmin,1]; ϵmin>0 is a known lower bound. Fix ϵ0∈[ϵmin,1), write p=1+ϵ0, and take K=2, T=2n, v=1, and ρ=logn. 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.