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

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.