Online Optimization 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 120 papers20 conceptsfrozen 2026-10-04

In the standard model of online learning, we often imagine ourselves playing a game against "Nature." We make a choice, Nature reveals a cost, and we move on. Crucially, we usually assume Nature is oblivious: it might be malicious, but it has already decided the entire sequence of costs before we even start playing.

However, real-world environments—from high-frequency trading to competitive recommendation engines—are rarely so indifferent. They are adaptive. When you change your strategy, the environment changes its response. This shift from oblivious to adaptive (or non-oblivious) adversaries represents the current frontier across multiple subfields of online optimization.

The Feedback Loop of Adaptivity

The core difficulty of an adaptive adversary is the feedback loop. In an oblivious setting, your current action only affects your current reward. In an adaptive setting, your current action influences the adversary’s future choices.

As David Henry Mguni, Long Tran-Thanh, and their colleagues argue in Online Markov decision processes with non-oblivious strategic adversary, traditional reinforcement learning often fails here because it treats the environment as a static backdrop. When the environment is a "strategic agent" watching your every move, the regret—the measure of how much you lost by not playing the best fixed strategy—becomes much harder to control.

The Gap in Combinatorial Bandits

This challenge is particularly acute in Combinatorial Multi-Armed Bandits (CMAB), where a learner chooses a set of items (like a set of paths in a network) rather than a single one.

Recent breakthroughs have mastered the "stochastic" version of this problem, where rewards follow a fixed distribution. For instance, Xutong Liu and Siwei Wang recently established a framework for Offline Learning for Combinatorial Multi-armed Bandits, but they explicitly note that extending this to adversarial settings remains an unresolved hurdle. Similarly, Alexia Atsidakou and Constantine Caramanis have pushed the boundaries of Combinatorial Blocking Bandits with Stochastic Delays, yet the jump from stochastic "cool-down" periods to an adversary that strategically blocks arms remains an open problem.

Why Memory and Fairness Complicate the Fight

The move toward adaptive robustness isn't just about performance; it's about constraints.

  1. Memory Constraints: In streaming settings, we often have "bounded recall." Jon Schneider and Kiran Vodrahalli show in Online Learning with Bounded Recall that while we can achieve optimal regret against oblivious foes with limited memory, we lack the same theoretical guarantees against adaptive ones. An adversary that knows you can only remember the last $M$ rounds can potentially "cycle" its strategy to exploit your amnesia.
  2. Fairness Constraints: When we add requirements like group fairness, the problem becomes a max-min game. Rad Niazadeh and Fransisca Susan developed a primal-dual framework for Online Combinatorial Optimization with Group Fairness Constraints, but they highlight that their current success relies on the environment being stochastic. An adaptive adversary could theoretically force a learner to choose between high utility and maintaining fairness by reacting to the learner's attempts to balance the two.

The Path Forward: Beyond Obliviousness

Whether in the realm of submodular maximization—where Tim Roughgarden and Joshua Wang have defined optimal bounds for the oblivious case—or in the emerging field of quantum optimization, the goal is the same. Jianhao He and his team, in their work on Quantum algorithm for online convex optimization, identify the transition to adaptive adversaries as a primary hurdle for practical quantum advantage.

To solve this, researchers are looking toward algorithms that don't just minimize regret against a fixed "best" action, but remain robust against an environment that evolves in response to the learner. This requires moving away from simple averaging of past performance and toward strategies that account for the long-term consequences of a single decision.

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_optimization_against_adaptive_adv_72c54a8e,
  title = {Online Optimization Against Adaptive Adversaries},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-optimization-against-adaptive-adversaries/rdr_72c54a8e56a742adba83dc6c1919a118},
  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_optimization_against_adaptive_adv_72c54a8e_v1,
  title = {Online Optimization Against Adaptive Adversaries},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-optimization-against-adaptive-adversaries/rdr_72c54a8e56a742adba83dc6c1919a118/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}