Extreme bandits

Alexandra Carpentier; Michal Valko

stat.MLApr 27, 2026

Extreme bandits

Authors: Alexandra Carpentier, Michal Valko

Organizations: Statistical Laboratory, CMS University of Cambridge, UK · SequeL team INRIA Lille - Nord Europe, France

Abstract

In many areas of medicine, security, and life sciences, we want to allocate limited resources to different sources in order to detect extreme values. In this paper, we study an efficient way to allocate these resources sequentially under limited feedback. While sequential design of experiments is well studied in bandit theory, the most commonly optimized property is the regret with respect to the maximum mean reward. However, in other problems such as network intrusion detection, we are interested in detecting the most extreme value output by the sources. Therefore, in our work we study extreme regret which measures the efficiency of an algorithm compared to the oracle policy selecting the source with the heaviest tail. We propose the ExtremeHunter algorithm, provide its analysis, and evaluate it empirically on synthetic and real-world experiments.

Explore similar work

Price of Fairness in Bandits: A Tight Minimax Characterization
Jul 15, 2026Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray ChowdhuryLinear Regret Bandits
Trading off rewards and errors in multi-armed bandits
May 1, 2026Akram Erraqabi, Alessandro Lazaric, Michal Valko +2Multi-Armed Bandits Regret
Finite-Time Regret Analysis of Retry-Aware Bandits
May 20, 2026Bingkui Tong, Junpei Komiyama, Soichiro Nishimori +1Multi-Armed Bandits Linear Regret

Jul 15, 2026 · stat.MLJ/K move · Enter open · S save

Price of Fairness in Bandits: A Tight Minimax Characterization

Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury

1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized

p

-mean, interpolating between utilitarian welfare (

p=1

), Nash welfare (

p\to0

), and Rawlsian fairness (

p\to-\infty

). Although tight guarantees are known for

p\ge0

, the strictly fair regime

q=-p>0

remains unresolved because negative-power means are dominated by the smallest per-round rewards. For

σ

-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret

O(k^{(q+1)/2}/\sqrt{T})

, while the only general lower bound was the classical

Ω(σ\sqrt{k/T})

. Thus it was unclear whether the extra dependence on

k

was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound

Ω(σ\sqrt{k^{\max(1,q)}/T})

; for

q>1

, this shows that the penalty

k^{q/2}

is information-theoretically unavoidable. We then introduce \textsf{UCB-HARE} (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is

\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})

, matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that \textsf{UCB-HARE} improves over uniform-exploration baselines, with gains increasing as

q

grows.

Linear Regret Bandits Minimax Fairness Constraints Fairness Interventions Prices Characterization

Open paper Ask about it PDF

Abstract

Explore similar work

Price of Fairness in Bandits: A Tight Minimax Characterization

Trading off rewards and errors in multi-armed bandits

Finite-Time Regret Analysis of Retry-Aware Bandits