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{nn−kT,kn−k},
2≤k<n. Under winner feedback, both arbitrary joint i.i.d. rewards and fixed sequences have minimax regret of order
Rn,k(T)=nn−kmin{T,kn+T,knT}. 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.