In standard online classification, a learner makes a prediction and is immediately told the correct answer. This "full-information" feedback allows the model to see exactly how far it was from the truth and in which direction it should adjust its weights. However, in many real-world scenarios—like recommending a movie or diagnosing a patient—we only receive a binary signal: was the choice correct or not?
If the choice was wrong, the true label remains hidden. This is the bandit feedback setting. The challenge is to learn the underlying patterns of multiple classes while only ever seeing a "yes" or "no" for the specific class we happened to guess.
The Information Gap and the Banditron
The fundamental difficulty of bandit feedback is that a "no" (a mistake) provides very little information. In a problem with 1,000 possible labels, knowing that the answer is not "Label A" still leaves 999 possibilities. As Sham M. Kakade, Ambuj Tewari, and Shai Shalev‐Shwartz demonstrated with the Banditron, the learner must explicitly balance exploitation (choosing the label it thinks is best) with exploration (occasionally choosing a random label to see if it might be correct).
The Banditron adapts the classic Perceptron by using a randomized rule: most of the time it predicts the highest-scoring class, but with a small probability, it explores. This allows it to achieve a mistake bound of $O(\sqrt{T})$, proving that learning is possible even when the "teacher" only says "wrong."
The Price of Banditry
How much harder is it to learn with bandit feedback than with full information? This is often called the "price of bandit feedback." Amit Daniely and colleagues showed in Multiclass learnability and the ERM principle that this price is generally proportional to the number of available classes. Intuitively, if you have more classes to choose from, you have to explore more "wrong" options before you can reliably find the "right" one.
Jesse Geneson and Espen Slettnes further quantified this in Sharp bounds on the price of bandit feedback, showing that in complex scenarios, the number of extra mistakes can grow significantly, establishing a theoretical limit on how efficient any bandit learner can be.
Measuring Complexity with Bandit Littlestone Dimensions
In full-information online learning, the "Littlestone dimension" measures how many mistakes a learner will make in the worst case. To handle the bandit setting, researchers had to invent new tools. Ananth Raman and Ambuj Tewari introduced the Bandit Littlestone dimension (BLdim) in Multiclass Online Learnability under Bandit Feedback.
This dimension captures the complexity of a hypothesis class when the learner only sees binary feedback. Crucially, they showed that BLdim characterizes learnability even when the number of possible labels is infinite. This shifted the focus from the size of the label space to the structural complexity of how those labels are assigned to inputs.
Beyond Random Exploration
While the Banditron uses simple random exploration, more sophisticated algorithms use uncertainty to guide their guesses. Claudio Gentile and Koby Crammer developed Confidit, which uses an Upper Confidence Bound (UCB) approach.
Instead of guessing randomly, Confidit maintains a measure of confidence for each class. It chooses the class that has the highest potential (score plus uncertainty). This "optimism in the face of uncertainty" ensures the model explores classes it knows little about but stops wasting time on classes it is sure are wrong. This approach improved the regret bound from $O(T^{2/3})$ to $O(\sqrt{T} \log T)$.
The Limits of Learnability
Recent work has pushed into even more restrictive or complex settings. Steve Hanneke and Amirreza Shaeiri explored the "trichotomy" of mistake rates in Multiclass Transductive Online Learning, proving that mistake growth follows strict patterns (constant, logarithmic, or linear).
However, bandit feedback isn't always a perfect substitute for full information. In Non-Uniform Multiclass Learning with Bandit Feedback, Steve Hanneke and Hongao Wang discovered a fundamental gap: some problems that are learnable when the true label is revealed become mathematically impossible to learn with only "right/wrong" feedback. This suggests that while bandit algorithms are powerful, the information lost by not knowing the true label creates a boundary that some learning problems simply cannot cross.