- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper gives a rank-based approach to learning with heavy-tailed rewards in contextual bandits. Concretely, the authors define the score of an arm as its evaluation under the CDF of the average reward distribution, obtaining the probability of beating a randomly chosen arm. They then define rank-regret under this score. The main algorithm is a rank-UCB approach which estimates this score with empirical CDF observations. The authors use an \ell_\infty norm sketching approach to compress the need for all historical rewards.
The final guarantees are gap-dependent O(T^{2/3}) or worst-case T^{7/9}.
The authors also compare with some prior works on heavy-tailed bandits empirically.
Critical strengths
The proposed score and the corresponding regret objective is interesting and the algorithm and the analysis carried out under it is novel. The sketching approach used to compress the historical reward stream is also a nice addition to the paper.
Critical weaknesses
There are a few things I was disappointed with in this paper:
-
It is reasonable to redefine estimators, but redefining the objective requires greater justification than this work offers. Once the regret is reformulated in terms of scores, the authors give no intuition on if/when it can be linked back to the standard regret in terms of reward gaps.
-
Even in terms of comparisons, the uniform reference is an arbitrary choice that is never justified. If most arms are bad, then the average benchmark can occlude small differences between the good arms. The literature on dueling bandits offers stronger alternative comparitive notions, and vonNeumann regret could have been a different benchmark to build of, for example, which directly compares pairs of arms.
-
The degradation in estimation rates is terrible! While I appreciate that the authors might prefer the rank-based approach stylistically, there is a rich literature on making heavy-tailed bandits also more adaptive to various problem dependent constants, when using Huber/Catoni style estimators in theory, with nearly no loss in rates. Given the very slow rates here, there is a high burden of proof on the authors to defend their choices through a more extensive evaluation with the state-of-the-art alternatives (which are missing), and through other favorable theoretical properties of their approach which might be missing from the more typical robust estimators.
Questions for authors
Please see the weaknesses above.
Thank you for recognizing the novel score and analysis, useful compression, and clear presentation. We appreciate the opportunity to connect the objective, guarantees, and experiments more directly.
Answer to W1: Motivation and connection to mean regret
The score measures how often an arm performs at least as well as an independently sampled alternative. Proposition 6.6 gives a useful calibration: under FSD, rank scores, quantiles, and finite means preserve the distributional ordering. The Pareto and exponential experiments evaluate this common ordering directly.
There is also a quantitative connection. When the finite-mean and rank objectives share the same unique optimal arm, write mi=ERi. Then
C_\nu=\max_{i\ne i^\star} \frac{m_\star-m_i}{\mu_\star-\mu_i}<\infty.$$ This links the regrets through their arm-gap ratios. We will add this bridge to the appendix. Appendix D.5 reports both regrets on the shared-ordering benchmarks. --- **Answer to W2: Uniform reference, poor arms, and von Neumann comparisons** The uniform reference corresponds to comparison with a randomly selected candidate and keeps the benchmark independent of the learner's changing allocation. It also lets each scalar observation provide information against all maintained arm distributions. The induced UCB-styled single-arm scalar accumulation index is very easy to understand and implement. The poor arms dilution effect can be quantified. Consider two continuous leading arms and $K-2$ arms whose outcomes are always lower. Their common contribution cancels, giving $$\mu_1-\mu_2 =\frac1K\left[ \Pr(R_1\ge R'_2)-\Pr(R_2\ge R'_1) \right].$$ The leading arms retain their ordering, with an explicit $1/K$ scaling of the pairwise advantage. The von Neumann criterion optimizes performance against an adversarial opponent. Our criterion measures average performance against the specified population. Its implementation uses only $K$ compressed CDF structures and scalar score sums, rather than estimating the full $K\times K$ matrix of pairwise win probabilities and solving for a Nash equilibrium of the resulting zero-sum game. Tables 1–2 show more than a 350-fold reduction in peak CDF entries per arm, with closely matching allocation behavior. --- **Answer to W3: Regret rates and adaptive robust baselines** Theorem 6.1 establishes almost-sure logarithmic regret for exact no-FE. Our additional analysis gives, for a known horizon, a data-dependent FE rule with **$O_\nu(\log T)$ expected regret on fixed instances** with a unique best arm, including a GK version retaining historical scores. Given that existing heavy-tailed MAB algorithms based on robust estimators also achieve logarithmic regret under fixed-instance assumptions, our rank-based approach does not entail a significant degradation in the estimation rate. However, a continuous and bounded construction also gives an **$\Omega(T^{2/3})$ uniform lower bound** through the cost of sampling an informative, constantly suboptimal arm. The $T^{2/3}$ exploration schedule adopted in the main algorithm is intended to obtain a uniform gap-independent regret bound that remains valid as $\Delta_{\min}\to 0$. We will include both results in the revision. The rank formulation provides guarantees beyond finite-mean objectives. The adaptive mean-bandit results cited in Section 2 assume a finite $(1+\epsilon)$ moment. Our score and regret remain well-defined without it. In Table 10, the same GK FE configuration reaches 95.95% rank-optimal allocation when all five Pareto means are infinite. Appendix D.5 provides a substantial robust-mean comparison: Truncated-Mean and Median-of-Means UCB receive oracle moment bounds, with 7,600 pilot trials for radius selection and 1,000 fresh trials per formal configuration. Rank-UCB1 uses fixed settings across environments and requires neither moment inputs nor instance-specific tuning. We will extend this evaluation with recent adaptive robust baselines in the revision. --- We hope these connections clarify the statistical and practical value of the approach. Thank you again for your thoughtful review; we would appreciate your reconsideration of the overall assessment.