In the ideal world of "full-information" online learning, an algorithm sees the outcome of every possible choice it could have made. This transparency allows learners to be incredibly nimble: if the data is "easy"—perhaps the losses are small, or one action is consistently best—the algorithm can achieve near-zero regret.
However, most real-world decision-making happens in the dark. In the bandit feedback setting, you only see the result of the action you actually took. This information gap creates a fundamental "adaptivity barrier." Research across several domains shows that without knowing the specific characteristics of the environment beforehand—such as how smooth a function is or how volatile the losses are—a bandit learner faces a mathematical ceiling that a full-information learner does not.
The Information Gap and Range Invariance
The most intuitive way to understand this barrier is through the lens of range invariance. In full-information settings, if all losses suddenly shrink from the range $[0, 1]$ to $[0, 0.01]$, the regret of a good algorithm scales down proportionally.
As Nicolò Cesa-Bianchi and Ohad Shamir demonstrate in Bandit Regret Scaling with the Effective Loss Range, this is impossible for pure bandits. Because the learner cannot see the losses of unchosen actions, they cannot distinguish between a small range of losses and a large range that has simply been shifted. Without a fixed reference point, the learner is forced to hedge against the worst-case global maximum loss, preventing them from exploiting "easy" data.
This isn't just a matter of suboptimal algorithm design; it is a fundamental limit. Sébastien Gerchinovitz and Tor Lattimore proved in Refined Lower Bounds for Adversarial Bandits that even if one action is consistently optimal, a bandit learner's regret must still grow with the square root of time ($\sqrt{T}$), whereas a full-information learner could achieve constant regret.
The Polynomial Cost of Unknown Regularity
The barrier extends beyond loss ranges to the very "shape" of the rewards. In continuum-armed bandits, where the learner chooses from an infinite space of actions, performance depends on the smoothness (Hölder regularity) of the reward function.
If an oracle tells you exactly how smooth the function is, you can optimize your exploration. But as Hédi Hadiji shows in Polynomial Cost of Adaptation for X-Armed Bandits, if that smoothness is unknown, there is a "polynomial cost of adaptation." You cannot match the oracle; you must pay a price in performance for the lack of prior knowledge.
Similarly, in batched settings, Cong Ma and Rong Jiang identify a "price of unknown margin" in The Adaptivity Barrier in Batched Nonparametric Bandits. If you don't know the gap between the best and second-best actions, your performance suffers a polynomial penalty that only vanishes if you can update your strategy frequently.
Why Detecting Change is Hard
The adaptivity barrier is most punishing in non-stationary environments. To be "strongly adaptive"—performing well over every sub-interval of time—an algorithm must quickly detect when the environment has shifted.
Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz established in Strongly Adaptive Online Learning that this is mathematically impossible under standard bandit feedback. The exploration required to "notice" a change in an unchosen arm is so costly that it outweighs the benefits of adapting. This creates a catch-22: you can't adapt without exploring, but you can't explore enough to adapt without ruining your regret bounds.
Bypassing the Barrier
If the barrier is fundamental, how do we move past it? The research suggests that the wall is not made of stone, but of information. By adding even a tiny amount of extra feedback, the impossibility results dissolve:
- Two Queries: Zhou Lu and colleagues demonstrated in Adaptive Regret for Bandits Made Possible: Two Queries Suffice that while one query per round is insufficient for strong adaptivity, just two queries allow a learner to detect shifts and achieve near-optimal adaptive regret.
- Limited Advice: Tobias Sommer Thune and Yevgeny Seldin showed in Adaptation to Easy Data in Prediction with Limited Advice that observing just one additional arm's loss per round (the SODA algorithm) allows the learner to bypass the range-invariance barrier and adapt to "easy" data.
These results highlight that the "Adaptivity Barrier" is specifically a consequence of the single-action feedback constraint. The transition from one observation to two is not just a quantitative change; it is a qualitative leap that restores the learner's ability to sense the environment's structure.