acceptodds
Under review as a conference paper at ICLR 2027

Learning from Ill-Behaved Rewards via Population-Relative Feedback

Abstract

Heavy-tailed real-valued feedback can make numerical reward statistics unstable or even undefined. Rather than robustly estimating such statistics, we change the representation of the feedback itself. Each reward is mapped to its rank under the uniform mixture of arm distributions, producing a bounded population-relative score equal to the probability of beating an independently sampled, uniformly chosen opponent. Thus a single scalar observation yields implicit comparison feedback without pairwise queries, reward moments, tail parameters, or truncation thresholds. The reference distribution is unknown and must itself be learned online from adaptively sampled arms. We develop Rank-UCB1, which estimates it using uniformly weighted per-arm empirical CDFs, compresses them with Greenwald–Khanna summaries, and controls the accumulated error of historical scores computed under earlier reference estimates. The resulting algorithm achieves expected rank-regret on every fixed finite-arm instance with positive gaps, together with a uniform sublinear finite-horizon guarantee. An exact variant without continued forced exploration has almost-sure logarithmic rank-regret and sublinear expected regret. Under first-order stochastic dominance, population-relative scores preserve parameter, quantile, and finite-mean orderings. Experiments across heavy-tailed and infinite-mean settings show effective allocation and negligible loss from streaming compression.

Primary area:
learning theory
Keywords:
heavy-tailed bandits, online learning, rank-based feedback, streaming sketches

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_7353OpenReview ↗
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:

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

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

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

1 comment

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=ERim_i=\mathbb E R_i. 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.
Reviewer_hxEfOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the multi-armed bandit problem with heavy-tailed reward distributions. The authors propose RANK-UCB1, an algorithm that learns from the relative performance of different arms without estimating their mean rewards, and establish a sublinear regret upper bound.

Critical strengths

This paper introduces a population-relative learning framework that does not rely on moment assumptions on the reward distributions, allowing the algorithm to operate without prior knowledge of reward moments, tail parameters, or truncation thresholds.

Critical weaknesses
  1. The regret upper bound of the proposed algorithm is relatively weak. Due to the forced-exploration cost of T2/3T^{2/3}, the authors can only establish a regret upper bound of T2/3T^{2/3}. However, even a simple horizon-aware explore-then-commit (ETC) algorithm may achieve a better regret bound. For example, with (log⁡T)2(\log T)^2 samples, it seems possible to obtain a regret upper bound of (log⁡T)2(\log T)^2. Since the proposed algorithm relies on forced exploration, it would be worth considering the different forced-exploration strategies introduced in [1], although that work addresses a different problem. I suspect that using an exponentially increasing exploration schedule could also improve the regret upper bound of the proposed UCB algorithm.

  2. [2] is closely related to the present paper. The core technical idea of the present paper already has a clear precedent in [2]. Although the authors have cited this work, the Related Work section does not sufficiently discuss its feedback mechanism or the technical differences between the two approaches.

[1] Han, Q., Zhu, L., & Guo, F. Forced exploration in bandit problems. In Proceedings of the AAAI Conference on Artificial Intelligence, 38(11):12270-12277,2024.

[2] Liyuan Xu, Junya Honda, and Masashi Sugiyama. Dueling bandits with qualitative feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):5549–5556, 2019.

Questions for authors
  1. Xu et al. (2019) have already studied how to estimate pairwise winning probabilities directly from single-arm qualitative feedback and use Borda-UCB to identify the Borda winner. Could the authors clarify the key technical novelty of the present paper compared with this prior work?

  2. Why use forced exploration on the order of T2/3T^{2/3}? Is it possible to obtain a better expected regret guarantee by reducing forced exploration, adopting adaptive exploration, or further analyzing the no-FE version?

3 comments

Thank you for recognizing the value of learning population-relative performance without reward-moment assumptions, tail parameters, or truncation thresholds. We appreciate your suggestions on exploration and the connection to earlier qualitative-feedback methods.


Answer to Q1: Technical contribution relative to Xu et al. (2019)

Xu et al. learn Borda preferences from single-arm ordinal feedback over a known finite alphabet. Rank-UCB1 handles arbitrary real-valued streams through CDF summaries and scalar score accumulation. Its analysis jointly controls errors from earlier reference estimates and deterministic GK compression, giving guarantees for the actual streaming learner. The reference is learned from the same observations used for arm selection. We will clarify this relationship in Related Work.


Answer to Q2: Forced exploration and logarithmic expected regret

The manuscript gives complementary guarantees for the two exploration choices. Theorem 6.1 establishes an almost-sure logarithmic limit for exact no-FE. For the main FE algorithm, Theorem 6.3 gives the more precise statement

ERT=RTFE+Oν(1).\mathbb E R_T=R_T^{\mathrm{FE}}+O_\nu(1).

Thus the expected cumulative regret outside prescribed coverage rounds is bounded independently of the horizon. Table 1 also measures the role of coverage: FE reduces the standard deviation of optimal-arm allocation by 23% on Pareto-5 and 53% on lognormal.

Every arm contributes to the common reference, including infrequently selected arms. Our additional lower-bound analysis makes this information cost explicit: in a continuous, bounded three-arm construction, distinguishing two leading arms requires sampling a third arm with a constant regret gap. This gives an Ω(T2/3)\Omega(T^{2/3}) uniform expected-regret lower bound. The main T2/3T^{2/3} exploration schedule supplies ongoing reference coverage, supporting Corollary 6.4's gap-free guarantee and GK storage O(KT1/3log⁡T)O(KT^{1/3}\log T).

Your suggestion of lighter exploration is also productive. Our additional analysis establishes a data-dependent FE rule, for a known horizon, with gap-dependent Oν(log⁡T)O_\nu(\log T) expected regret on each fixed instance with a unique best arm. It retains all historical scores and also supports GK compression with the manuscript's horizon-dependent precision. We will include this logarithmic extension and the uniform lower-bound construction in the revision.


We hope these results clarify the exploration choices and guarantees. We would be grateful for your reconsideration of the soundness and overall assessments.

Thank you to the authors for the clarification. In the new version, the authors have added a new regret lower bound, but the current algorithm’s gap-free upper bound is still not optimal, so I maintain my score unchanged.

Dear Reviewer hxEf,

Thank you for following up on the gap-free rate. Corollary 6.4 gives a uniform O~(T7/9)\widetilde O(T^{7/9}) bound for Algorithm 1’s interleaved exploration schedule. Its tight worst-case rate remains open. Theorem 6.8 identifies the cost of learning the shared reference and provides the gap-free lower bound.

A comparison with the same exploration budget shows what the streaming update can achieve. For a known horizon TT, take Algorithm 1’s F≍T2/3F\asymp T^{2/3} round-robin exploration pulls first (rather than interleavd FE), retain every score, and then use the same UCB index and GK sketches. Write m=⌊F/K⌋m=\lfloor F/K\rfloor. Averaging the early scoring errors and controlling subsequent sample prefixes gives an expected error of OK(m−1/2+η)O_K(m^{-1/2}+\eta) for the retained arm means. Adding the exploration cost and UCB bonuses gives

=O_K\\!\left(F+T/\sqrt m+T\eta+\sqrt{T\log T}\right) =O_K(T^{2/3})$$ at the paper’s precision $\eta=T^{-1/3}$. This **matches the lower bound** in its dependence on $T$ for fixed $K$. Interleaving lets Algorithm 1 act on promising arms while it is still learning the reference. In our 50,000-round Pareto-5 runs, its mean cumulative rank regret by round 1,000 was 28.59. Front-loading the same 1,358 exploration pulls would allocate exactly 200 pulls to each arm by that checkpoint, giving cumulative rank regret 101.54. Thank you again for your continued insightful feedback. We will explicitly clarify this trade-off in the revised paper: front-loaded exploration can match the theoretical gap-free lower bound, whereas interleaved exploration can achieve better empirical early-stage learning performance.
Reviewer_8nRAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies stochastic bandits with a rank objective: the probability of matching or exceeding an independent reward from a uniformly chosen arm. It proposes Rank-UCB1, which uses forced exploration and compressed per-arm empirical CDFs, and analyzes errors from retaining scores computed under earlier reference estimates. The paper presents sublinear expected rank-regret guarantees and an almost-sure logarithmic guarantee for an exact-eCDF variant without continued forced exploration.

Critical strengths

The analysis accounts for the accumulated error from scores computed under earlier reference estimates, as well as CDF compression error. It provides sublinear expected rank-regret guarantees without reward moment assumptions for an implementation that avoids storing the full reward history or recomputing past scores.

Critical weaknesses
  1. The objective needs stronger motivation. Heavy tails alone do not justify using uniformly weighted candidate arms as the comparison population. Quantile-based bandit formulations also permit learning without finite reward moments (Szörényi et al., 2015). Scale invariance and FSD calibration provide some justification, but the connection between this particular comparison population and the motivating applications remains unclear.
  2. The advance over existing ordinal/Borda methods seems insufficiently established. Section 2 describes the cited approaches as receiving comparisons or rankings, whereas Xu, Honda, and Sugiyama (2019) already learn the Borda winner from individual ordinal observations without explicit duels. Although their results assume a finite alphabet, a closer comparison is needed to explain what the general real-valued setting, retained historical scores, and CDF compression add theoretically or computationally.
Questions for authors
  1. For the motivating applications given, why is average win probability against a uniformly chosen arm a suitable objective function?
  2. What is the main advance over Xu, Honda, and Sugiyama (2019) ? In particular, what tradeoff in regret, computation, and memory motivates retaining historical scores instead of updating Borda estimates using the current empirical distributions?
3 comments

Thank you for your careful review and positive assessment of soundness. We appreciate your recognition of the joint control of historical reference errors and CDF compression without reward moments or rescoring past observations.


Answer to W1 / Q1: Motivation for the objective and comparison with quantile bandits

For the routing applications, our score measures the probability of matching or improving on random routing. With latency or cost oriented so that larger rewards mean better outcomes,

μi=Pr⁡(Ri≥RJ′),J∼Unif([K]),\mu_i=\Pr(R_i\ge R'_J),\qquad J\sim\mathrm{Unif}([K]),

where the opponent's outcome is sampled independently. Uniform weighting gives each candidate an equal role in the benchmark, independently of the learner's allocation, and requires no external reward scale.

A quantile objective concerns a specified percentile qq. Our objective averages relative performance across the outcome distribution without choosing qq. Rank-UCB1 uses fixed settings across the suite, without moment bounds or tail parameters. On Pareto-5 and exponential rewards, where the objectives share the same optimal arm, its best-arm allocation is 95.94% and 93.62%, compared with 92.2% and 80.3% for QoMax-SDA. These results illustrate the value of learning each observation's position against the comparison population.


Answer to W2 / Q2: Advance over Xu et al. (2019) and the role of historical scores

Thank you for clarifying the connection to Xu et al. (2019). They learn from individual ordinal observations without explicit duels, using distributions over a known finite alphabet. We will describe this mechanism explicitly in Related Work.

We handle arbitrary real-valued streams through compressed CDFs and analyze scores computed under an evolving reference. The storage costs are:

Reference representationTotal reference storage
Finite alphabet of size LL in Xu et al.O(KL)O(KL)
Exact empirical CDFsO(T+K)O(T+K)
Our GK summaries, at most MM entries per armO(KM)O(KM)

With the paper's precision, M=O(T1/3log⁡T)M=O(T^{1/3}\log T). Each observation requires one CDF insertion and KK queries, then updates one scalar score sum. Retaining scores avoids revisiting earlier rewards under each new reference. Lemma 6.2 controls the accumulated error, Theorem 6.3 identifies the expected coverage cost, and Corollary 6.5 incorporates compression.

Tables 1–2 demonstrate this design: GK reduces peak internal CDF entries per arm from about 48,000 to 134, with mean optimal-arm allocation changing by less than 0.0004 on both main examples.


We will incorporate these explanations into the revision. Thank you again for your suggestions; we would appreciate your reconsideration of the overall assessment.

Thank you for the clarifications.

Regarding W1: The routing example clarifies the interpretation of the objective, but its motivation/justification still seems limited to me. Specifically, it is still unclear to me why maximizing the probability of outperforming a uniformly selected candidate is appropriate for routing decisions.

Regarding W2: The updated discussion of Xu et al. and the explanation of storage and update costs provide helpful context. However, the overall tradeoff in regret, computation, and memory between retaining historical scores and maintaining current Borda estimates still seems insufficiently established to me.

These concerns still affect my overall assessment, so I maintain my scores.

Dear Reviewer 8nRA,

Thank you for your thoughtful follow-up. We appreciate your acknowledgment that our earlier clarifications were helpful, and welcome the opportunity to address the remaining concerns.


W1: Practical justification of the objective.

The probability of outperforming a uniformly selected candidate provides a robust, distribution-independent measure of routing performance: it quantifies how often a selected replica achieves lower latency than uniform random routing, with a direct operational interpretation regardless of the latency distribution's shape.

More importantly, this objective can align with established service-level goals. Consider replicas whose latencies share a common distributional shape but differ in scale, Li=siZL_i=s_iZ. Selecting the smallest scale simultaneously maximizes the probability of meeting every latency deadline, minimizes all latency quantiles, and minimizes mean latency whenever finite. Proposition 6.6 establishes that our rank objective selects the same replica through first-order stochastic dominance. Thus, the justification extends beyond interpreting win probability to consistency with multiple operational objectives.

This is not merely an isolated example. Common-shape service-time models with heterogeneous server speeds, including Pareto distributions, are explicitly studied by [1], while heavy-tailed latency and straggler effects are well documented in distributed systems ([2]).

[1] Abdul Jaleel, Jazeem, et al. "A general “power-of-d” dispatching framework for heterogeneous systems." Queueing Systems 102.3 (2022): 431-480.

[2] Dean, Jeffrey, and Luiz André Barroso. "The tail at scale." Communications of the ACM 56.2 (2013): 74-80.


W2: Regret, computation, and memory tradeoffs.

The revised Theorem 6.7 establishes Oν(log⁡T)O_\nu(\log T) expected regret on fixed instances with a unique optimal arm. Crucially, this result uses data-dependent forced exploration while retaining historical scores, and applies to both exact eCDFs and GK compression. Thus, lightweight historical-score updates are compatible with logarithmic expected regret.

Regarding computation, directly recomputing all current Borda estimates from KK GK summaries containing at most MM entries each requires O(K2M)O(K^2M) operations per round using straightforward pairwise merging. Under our default precision M=O(T1/3log⁡T)M=O(T^{1/3}\log T). In contrast, Rank-UCB1 requires only KK CDF queries, and one scalar-score update per round, only O(Klog⁡M)O(K\log M) operations. While more sophisticated Borda implementations may reduce recomputation costs, our approach offers a particularly simple, theoretically justified streaming alternative.

Our broader goal is to provide a general-purpose preprocessing layer for ill-behaved real-valued feedback. Retaining historical scalar scores enables direct integration with familiar UCB-style learning rules, making the approach accessible to researchers and practitioners without requiring specialized dueling-bandit machinery.


We sincerely appreciate your continued engagement. We believe these further clarifications, together with the strengthened theoretical guarantees, improve the revised paper.

Comments on the paper

2 comments

Dear reviewers,

If you believe the authors have addressed your questions, please respond to the rebuttal.

Best, AC

AuthorsOpenReview ↗

Summary of the Rebuttal Revision PDF

Dear reviewers and AC,

We sincerely thank the reviewers for their constructive feedback. We have completed a revision addressing the main concerns about the objective, relationship to prior work, regret guarantees, and recent adaptive baselines. The additions build on the submitted method and strengthen its central contribution: learning population-relative performance from individual real-valued observations without reward-moment assumptions, while controlling historical reference errors and streaming compression.


1. Stronger theory explains the exploration choices.

Theorem 6.7 establishes gap-dependent Oν(log⁡T)O_\nu(\log T) expected regret for fixed instances with a unique optimal arm and a known horizon. This extension uses data-dependent forced exploration (FE), preserves every historical score, and covers both exact eCDFs and GK compression. It demonstrates that logarithmic fixed-instance learning is fully compatible with our approach.

The original polynomial FE schedule provides simple, continuing reference coverage and supports the uniform gap-free sublinear guarantee in Corollary 6.4. Its fixed-instance polynomial regret reflects the prescribed coverage budget. Theorem 6.8 complements this analysis with an Ω(T2/3)\Omega(T^{2/3}) uniform lower bound, even for bounded, continuous rewards: distinguishing two leading arms can require sampling a third arm with a constant regret cost. Appendix E provides the new pseudocode and complete proofs.


2. New adaptive-baseline experiments reinforce the main algorithm's practical performance.

We added uniINF and AdaR-ETC on the existing Pareto-5 and Exponential benchmarks, using 1,000 trials per configuration, T=50,000T=50{,}000, common seeds and per-arm reward streams, and no additional tuning search. The original GK FE algorithm achieves lower mean regret, lower rank regret, and higher optimal-arm allocation than both new baselines on both benchmarks. GK FE's optimal-arm allocations are 95.94% and 93.62% on Pareto-5 and exponential rewards, respectively; AdaR-ETC reaches 92.07% and 87.85%. In contrast, uniINF incorrectly locks onto a suboptimal arm in the Pareto-5 setting.

Appendix D.5 documents the evaluation protocol; Table 9 and Figure 5 report all three metrics, with standard deviations in the table.


3. The objective and technical contribution are clearer.

Sections 2–3 explain the random-candidate benchmark and its distinction from a fixed quantile, and explicitly describe Xu et al.'s single-arm ordinal feedback. Appendix B.3 adds a quantitative bridge to mean regret, characterizes the effect of uniformly inferior arms, and explains the uniform-reference and von Neumann criteria. Section 7.1 and Appendix C.4 clarify the storage benefits of retaining scores and compressing the reference.


These additions complement the original evidence: FE improves allocation stability, GK reduces peak CDF entries by over 350-fold while closely preserving exact-eCDF behavior, and the same configuration reaches 95.95% rank-optimal allocation when all reward means are infinite. Algorithm 1 and its default settings are retained. The new experimental reproduction materials are to be included in the updated supplement, and additions are highlighted in purple in the revised paper.

We are grateful for the reviewers' suggestions and respectfully invite a reassessment of the revised paper in light of these theoretical and empirical additions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.