Bandits with Probing: Optimal Coverage and the Role of Feedback
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≤ k<n, the minimax regret is Θ((n−k)/nmin{T,n/k}), the cost of locating an unknown good arm, and observing only the maximum suffices to attain it. In particular, two probes give Θ(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 Θ(1), Θ(√T), and Θ(T): rounding preserves conditional means but not the rate.
Related
- Near-Optimal First-Order Regret for Bandits with Feedback Graphs
- m-Set Adversarial Bandits with Winner Feedback
- Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback
- Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
- Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
BibTeX
@misc{guan2026bandits,
title = {{Bandits with Probing: Optimal Coverage and the Role of Feedback}},
author = {Yongjie Guan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.15248},
eprint = {2609.15248},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15248},
}
RIS
TY - UNPB
TI - Bandits with Probing: Optimal Coverage and the Role of Feedback
AU - Yongjie Guan
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2609.15248
UR - https://arxiv.org/abs/2609.15248
AB - 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≤ k<n, the minimax regret is Θ((n−k)/nmin{T,n/k}), the cost of locating an unknown good arm, and observing only the maximum suffices to attain it. In particular, two probes give Θ(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 Θ(1), Θ(√T), and Θ(T): rounding preserves conditional means but not the rate.
ER -