Bandits with Probing: Optimal Coverage and the Role of Feedback

arXiv:2609.15248v2 Announce Type: replace Abstract: In bandits with probing, a learner selects at most $k$ of $n$ arms per round, earns the largest of their rewards, and competes with the best fixed single arm. For independent arms with i.i.d. rewards in $[0,1]$ and $2\le k<n$, the minimax regret is $\Theta\bigl(\frac{n-k}{n}\min\{T,n/k\}\bigr)$, the cost of locating an unknown good arm, and observing only the maximum suffices to attain it. In particular, two probes give $\Theta(\min\{T,n\})$ regret, which resolves two open questions of Bhaskara et al. (2023) with weaker feedback. Our policy turns the probing surplus, the excess of the maximum over each probed arm, into exploration capital, and a permanent random core yields the sharp dependence on $k$. On arbitrary fixed reward arrays, same-round contrasts between blocks of arms attain the same rate, because the surplus pays for the stability of mirror descent. Winner feedback, the maximum together with its winning label, instead incurs an additional learning cost under joint i.i.d. rewards and on fixed arrays. We characterize this cost even when values are revealed only intermittently, using policies that know neither the horizon nor the revelation rate. For three independent arms and two probes, exact maxima, Bernoulli-rounded maxima with winning labels, and winning labels alone have minimax regret $\Theta(1)$, $\Theta(\sqrt T)$, and $\Theta(T)$: rounding preserves conditional means but not the rate.