Optimal Adaptation to Stochastic and Adversarial Regimes

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2200 papers276 conceptsfrozen 2026-10-04

In sequential decision-making, an agent must choose actions to maximize rewards without knowing the future. Traditionally, researchers have split this problem into two distinct universes. In the stochastic universe, rewards follow a stable, hidden distribution; here, an agent can achieve "fast" logarithmic regret ($O(\log T)$) by identifying the single best action. In the adversarial universe, rewards are chosen by a malicious opponent; here, the agent must be cautious and settle for "slow" square-root regret ($O(\sqrt{T})$) to avoid being exploited.

The "Best-of-Both-Worlds" (BoBW) research direction seeks a single, environment-agnostic algorithm that automatically achieves the optimal rate for whichever universe it happens to inhabit.

The Dilemma of Specialization

Most online learning algorithms are specialists. An algorithm like Upper Confidence Bound (UCB) excels in stochastic settings but can be easily "tricked" by an adversary into making catastrophic mistakes. Conversely, adversarial algorithms like EXP3 are designed for the worst case; they are so pessimistic that they continue to explore even when the environment is perfectly stable, leaving significant rewards on the table.

As noted by Tiancheng Jin, Junyan Liu, and Haipeng Luo in Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits, the challenge is that the strategies required for these two regimes often conflict. A BoBW algorithm must be "optimistic" enough to exploit stability but "randomized" enough to defend against malice.

The Mechanism of Adaptive Regularization

The breakthrough in BoBW design often centers on the Follow-the-Regularized-Leader (FTRL) framework. In FTRL, the agent chooses an action distribution that minimizes the sum of past losses plus a "regularizer" that prevents the agent from switching actions too wildly.

The choice of regularizer is the secret sauce. While standard Shannon entropy leads to adversarial robustness, it doesn't naturally yield logarithmic regret in stochastic settings. Researchers like Shinji Ito and Masahiro Kato have shown in LC-Tsalis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits that using Tsallis entropy (specifically with an index of 1/2) allows the algorithm to adapt.

Tsallis entropy acts as a bridge: it provides enough curvature to ensure the agent doesn't over-commit (protecting against adversaries) but allows the learning rate to effectively accelerate when a clear "gap" between the best arm and others is detected (exploiting stochasticity).

Self-Bounding Regret Analysis

How does the math "know" which regime it is in? The core intuition is the self-bounding technique. In a stochastic environment, the regret can be mathematically bounded by a function of itself.

As explained by Shinji Ito, Kevin Jamieson, and Haipeng Luo in Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback, the algorithm's adversarial regret bound (the $O(\sqrt{T})$ part) is forced to "contract" when the losses are consistent. If the environment is stable, the variance of the rewards is low, and the self-bounding property automatically collapses the square-root growth into a logarithmic one. This happens without the agent ever explicitly "deciding" which environment it is in.

Beyond Simple Bandits

The BoBW philosophy has recently expanded to more complex and constrained scenarios:

  • Reinforcement Learning: Christoph Dann and Julian Zimmert demonstrated in Best of Both Worlds Policy Optimization that policy optimization can achieve these dual guarantees in full Markov Decision Processes (MDPs).
  • Resource Constraints: In Unifying the stochastic and the adversarial Bandits with Knapsack, Long Tran-Thanh and Anshuka Rangi extended BoBW to "Bandits with Knapsacks," where the agent must manage limited budgets while adapting to environmental volatility.
  • Heavy-Tailed Distributions: Yu Chen and Longbo Huang in uniINF developed algorithms that are not only BoBW but also "parameter-free," meaning they don't even need to know the "heaviness" of the reward distribution's tails to remain optimal.

Toward Best of All Worlds

The ultimate goal of this field is "Best-of-All-Worlds" performance. As explored by Liad Erez and Tomer Koren in Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs, this involves creating algorithms that handle not just the binary stochastic/adversarial split, but also intermediate "corrupted" environments where a mostly-stable signal is peppered with occasional adversarial attacks. By using hybrid regularizers like Tsallis-Shannon entropy, these agents maintain the highest possible efficiency across the entire spectrum of environmental difficulty.

Papers in this version

Showing 60 of 200 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 339 papers
  2. Version 1 · 2026-10-04 · 200 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_best_of_both_worlds_adaptation_01065b88,
  title = {best-of-both-worlds adaptation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/best-of-both-worlds-adaptation/rdr_01065b88eeb446b9b9e0f2a02097ef6f},
  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_optimal_adaptation_to_stochastic_and_adv_01065b88_v1,
  title = {Optimal Adaptation to Stochastic and Adversarial Regimes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-adaptation-to-stochastic-and-adversarial-regimes/rdr_01065b88eeb446b9b9e0f2a02097ef6f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}