Online Learning Against Adaptive Adversaries

This direction is merged into another direction: adaptive adversary robustness (oblivious adversary assumption). Its last version stays readable and citable here.

Version 1 of 154 papers57 conceptsfrozen 2026-10-04

In the standard model of online learning, a learner makes a sequence of decisions, and an "adversary" reveals the costs associated with those decisions. Most classical guarantees in this field rely on a crucial simplification: the adversary is oblivious. This means the adversary must commit to a sequence of losses before the game even begins.

However, real-world environments—from high-frequency trading to autonomous multi-agent systems—are rarely so polite. In these settings, the environment is adaptive; it observes the learner’s past actions and adjusts its future strategy to exploit weaknesses. Bridging the gap between oblivious and adaptive environments is the central challenge of modern online optimization.

The Knowledge Gap: Oblivious vs. Adaptive

The distinction between these two types of adversaries is often a matter of information. As Sebastian Pokutta and Huan Xu clarify in Adversaries in Online Learning Revisited, the confusion often stems from whether an adversary can anticipate a learner’s internal randomness.

If an algorithm is randomized, an oblivious adversary only knows the distribution of the learner's choices. An adaptive adversary, however, can react to the specific realizations of those choices. This feedback loop can invalidate traditional regret bounds. For instance, in Bandits with Movement Costs and Adaptive Pricing, Tomer Koren, Roi Livni, and Yishay Mansour demonstrate that when switching actions is expensive, an adaptive adversary can force a learner into a "damned if you do, damned if you don't" scenario by punishing both stability and movement.

From Average Success to High-Probability Guarantees

To handle adaptivity, researchers have shifted focus from expected regret (how well the algorithm performs on average across many parallel universes) to high-probability regret (how well it performs in this specific run).

The intuition is that if an algorithm's performance is stable across almost all possible outcomes, an adversary has fewer "edge cases" to exploit. Peter Bartlett, Alexander Rakhlin, and their colleagues pioneered this in High-Probability Regret Bounds for Bandit Online Linear Optimization. By introducing the GEOMETRICHEDGE.P algorithm, they used martingale concentration inequalities to ensure that the learner's regret stays low even when the adversary is actively trying to push the learner into a high-variance state.

Similarly, Gábor Braun and Sebastian Pokutta showed in An efficient high-probability algorithm for Linear Bandits that one can achieve $O(T^{2/3})$ regret against adaptive adversaries with computationally efficient tools. This ensures that the algorithm's performance remains reliable in dynamic environments where the adversary reacts to every move.

Complexity and the "Dimension Tax"

In high-dimensional spaces, the problem of adaptivity becomes even more acute. In Bandit Convex Optimization (BCO), the learner only sees the loss of the specific point they chose, not the entire function. Sébastien Bubeck and Ronen Eldan famously addressed the fundamental limits of this setting in Multi-scale exploration of convex functions and bandit convex optimization.

The difficulty here is that the learner must use their choices to both minimize loss and probe the landscape. An adaptive adversary can make this probing misleading. Recent work by Hang Yu and Peng Zhao in Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variation attempts to reduce the "dimension tax" in these settings, though they note that extending these bounds to fully adaptive adversaries remains a major open frontier.

Stability as a Defense

One surprising way to combat adaptivity is through laziness or stability. If an algorithm doesn't change its mind too often, the adversary has less "signal" to react to.

  • Switching Budgets: Uri Sherman and Tomer Koren explore this in Lazy OCO, showing that restricting how often a player changes decisions can actually be a viable strategy, though it creates a performance gap between oblivious and adaptive settings.
  • Randomized Stability: Luc Devroye and Gergely Neu suggest in Prediction by random-walk perturbation that adding specific types of noise (like a random walk) to the leader’s path can prevent "flip-flopping," making the learner less predictable and more robust to reactive losses.

Privacy and Strategic Interaction

The challenge of adaptivity also intersects with Differential Privacy. In Private Online Learning against an Adaptive Adversary, Bo Li and Wei Wang show that while adaptive feedback loops usually degrade performance, it is possible to achieve optimal logarithmic mistake bounds even when the adversary sees past predictions. This suggests that privacy—which inherently limits how much an adversary can learn about the learner's internal state—can act as a natural buffer against adaptivity.

Finally, in multi-agent settings like Bayesian Persuasion, the "adversary" is often a receiver who is learning from the sender. Martino Bernasconi and Nicola Gatti demonstrate in Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion that by using "type reporting" mechanisms, senders can maintain $O(\sqrt{T})$ regret even when receivers adjust their strategies based on historical signaling.

Conclusion: The Best of Both Worlds

The ultimate goal of this research direction is to create "Best of Both Worlds" algorithms. As Anshuka Rangi and Long Tran-Thanh argue in Unifying the Stochastic and the Adversarial Bandits with Knapsack, we need learners that are efficient in stable, stochastic environments but remain robust when the environment turns adversarial and adaptive. By moving beyond the oblivious assumption, the field is developing a more realistic and resilient theory of decision-making under uncertainty.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_online_learning_against_adaptive_adversa_a628cf38,
  title = {Online Learning Against Adaptive Adversaries},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-against-adaptive-adversaries/rdr_a628cf38b2934fa98c6f9c9ba96e3bfe},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_online_learning_against_adaptive_adversa_a628cf38_v1,
  title = {Online Learning Against Adaptive Adversaries},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-against-adaptive-adversaries/rdr_a628cf38b2934fa98c6f9c9ba96e3bfe/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}