Optimal strategies for learning with limited reward probes in bandit problems
Bandits with Probing: Optimal Regret and the Limits of Winner Feedback
Machine LearningData Structures and Algorithms
Summary
This paper looks at a situation where a learner can check just a few choices each time and only sees the best reward from those checks. The authors find exact limits on how well anyone can do in these problems, depending on how many choices are checked and what kind of feedback they get. They show that sometimes just knowing the winner is enough to reduce mistakes, but in other cases, more detailed information helps. Their results clarify when exploring a few options each round actually helps learning and when it doesn’t.
What this means in practice
- •For online advertising teams: Optimize ad selection by probing limited ad options and using winner feedback to reduce regret in displaying the best performing ads.
- •For inventory managers: Improve restocking decisions by selectively testing a subset of products and learning which yields highest revenue with minimal exploration cost.
A theory result. No direct application yet.
Authors
Yongjie Guan
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 $Φ_{n,k}(T)=\min\{\frac{n-k}{n}T,\frac{n-k}{k}\}$, $2\le 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.