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

arXiv: https://arxiv.org/abs/2609.15248 · HTML: https://mlsanity.com/paper/2609.15248/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 14 references that are in the map.
- First posted on arXiv 14 Sep 2026.

## Builds on (most cited first, 4 of 4)

- [Dueling Bandits With Weak Regret](https://mlsanity.com/paper/1706.04304/) (2017)
- [Online Learning and Bandits with Queried Hints](https://mlsanity.com/paper/2211.02703/) (2022)
- [Can Probabilistic Feedback Drive User Impacts in Online Platforms?](https://mlsanity.com/paper/2401.05304/) (2024)
- [Multi-Armed Bandits With Best-Action Queries](https://mlsanity.com/paper/2605.08287/) (2026)

## Abstract (arXiv)

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 Phin,k(T)=minfracn-knT,fracn-kk, 2≤ k<n. Under winner feedback, both arbitrary joint i.i.d. rewards and fixed sequences have minimax regret of order Rn,k(T)=fracn-knminT,fracn+Tk,√fracnTk. Both laws have universal constants and anytime upper bounds. The first reduces regret to a pure coverage cost: same-round contrasts absorb the stability cost, and independence permits exact resampling whose gains fund sample advancement. The second adds a learning cost that becomes comparable to coverage at horizon n; beyond nk, numerical maxima improve over labels alone. The lower bound allows every adaptive action size.