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...
Yong-Jie Guan
· 0 citations