Learning from Ill-Behaved Rewards via Population-Relative Feedback

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 $O(T^{2/3})$ 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.