SOURCE-LINKED INTELLIGENCE

Bandits with Probing: Optimal Regret and the Limits of Winner Feedback

arXiv · AI, language, vision and robotics · article · Sep 14, 2026 · UTC

A learner probes at most $k$ of $n$ arms each round, receives the maximum of their rewards in $[0,1]$, and competes with the best fixed arm. When does the probing advantage pay for learning? We determine two minimax laws. Under independent stochastic rewards with winner feedback (the maximum and a winning label), or on arbitrary fixed sequences given a single signed contrast between block maxima, the minimax regret has order $Φ_{n,k}(T)=\min\{\frac{n-k}{n}T,\frac{n-k}{k}\}$, $2\le k<n$. Under winner feedback, both arbitrary joint i.i.d. rewards and fixed sequences have minimax regret of order

Read original source ↗ Open in workspace

recordType

paper

region

Global