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

arXiv:2609.15248v1 Announce Type: new Abstract: 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 Phi_{n,k}(T)=min{frac{n-k}{n}T,frac{n-k}{k}}, 2le k<n. Under winner feedback, both arbitrary joint i.i.d. rewards and fixed sequences have minimax regret of order R_{n,k}(T)=frac{n-k}{n}min{T,frac{n+T}{k},sqrt{frac{nT}{k}}}. 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.

Source: arXiv cs.LG | 2026-09-15