Adapting to Stochastic and Adversarial Environments

696 concepts290 papers1 proposal

In sequential decision-making, algorithms are traditionally forced to specialize in one of two distinct environments. In a stochastic environment, rewards or losses are drawn from fixed, stationary probability distributions. Here, an agent can exploit this consistency to achieve a fast, logarithmic regret rate—meaning the cost of learning diminishes rapidly over time. In an adversarial environment, an opponent can manipulate losses arbitrarily or maliciously. To remain safe, an agent must adopt a conservative, highly exploratory strategy, which slows the optimal regret rate to a square-root curve ($\sqrt{T}$).

As established by Sebastien Bubeck et al. in Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, algorithms optimized for one world typically fail in the other. A purely stochastic algorithm can be completely misled by a brief sequence of adversarial inputs, while a purely adversarial algorithm wastes valuable opportunities to exploit stability when it occurs.

The "Best-of-Both-Worlds" (BOBW) research direction aims to design a single, environment-agnostic algorithm that automatically achieves optimal performance in both settings: $O(\log T)$ regret if the environment happens to be stable, and $O(\sqrt{T})$ regret if it turns out to be chaotic, without knowing the regime in advance.

The Failure of Explicit Detection

A natural first instinct is to build a meta-algorithm that acts as an environment detector. This detector would monitor the history of losses, run a statistical test for stationarity, and switch from a stochastic algorithm to an adversarial one if it detects malicious behavior.

However, this explicit switching strategy is fundamentally vulnerable. An intelligent adversary can easily exploit the detector by mimicking a clean, stochastic environment for a long period—inducing the agent to switch to a vulnerable, low-exploration stochastic mode—before unleashing a catastrophic sequence of altered losses. By the time the detector registers the change, the agent has already incurred massive regret.

To achieve true robustness, BOBW algorithms avoid explicit detection entirely. Instead, they rely on continuous mathematical mechanisms that naturally accelerate or decelerate based on the intrinsic difficulty of the loss sequence.

The Engine: Self-Bounding Regret

The core mechanism behind modern BOBW algorithms is the self-bounding property. Rather than treating the stochastic and adversarial settings as two separate code paths, researchers structure the algorithm's mathematical regret bound so that it implicitly adapts to the environment.

In a standard adversarial framework like Follow-the-Regularized-Leader (FTRL) or Online Mirror Descent (OMD), the agent's regret against the best fixed action is bounded by a combination of the regularizer's diameter and the variance of the loss estimators. As analyzed by Shinji Ito in Revisiting Online Submodular Minimization: Gap-Dependent Regret Bounds, Best of Both Worlds and Adversarial Robustness, a self-bounding framework structures the regret inequality such that the adversarial regret bound can be bounded by a function of the algorithm's own performance.

Conceptually, the regret $R_T$ in a stable environment can be written in a form resembling:

$$R_T \le \sum_{i \neq i^*} \frac{C}{\Delta_i} + \alpha \cdot (\text{Adversarial Variance Terms})$$

where $\Delta_i$ represents the sub-optimality gap of action $i$, and $C$ is a constant. In a stable stochastic world, the algorithm's probability of choosing sub-optimal actions decays over time. Because the regularizer is chosen carefully, this decay causes the "Adversarial Variance Terms" to shrink in proportion to the regret itself. This allows the system to naturally solve for $R_T$ as a purely logarithmic function of time. If the environment becomes adversarial, the variance terms do not shrink, and the bound gracefully relaxes back to the standard worst-case $\sqrt{T}$ guarantee.

Designing the Right Curvature

The magic of self-bounding regret depends entirely on the choice of regularization or perturbation. Standard FTRL algorithms often use Shannon entropy as a regularizer, which forces the algorithm to maintain a relatively uniform exploration profile across all actions. While this guarantees $\sqrt{T}$ robustness against adversaries, it prevents the algorithm from rapidly locking onto a single superior action in a stochastic setting.

To fix this, BOBW algorithms alter the geometric curvature of the action space near its boundaries. Two primary strategies dominate this design:

1. Tsallis Entropy and Log-Barrier Regularizers

Instead of Shannon entropy, researchers utilize regularizers with steeper gradients near the edges of the probability simplex. As shown by Aadirupa Saha and Pierre Gaillard in Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences, regularizers like Tsallis entropy allow the algorithm to automatically tighten its regret bounds when it encounters a stable environment.

When one action is consistently better than the others, the steep curvature of Tsallis entropy allows the probability weights of sub-optimal actions to drop rapidly toward zero. This rapid decay dramatically reduces the variance of the importance-weighted loss estimators, collapsing the adversarial $\sqrt{T}$ bound into a gap-dependent $\log T$ bound.

2. Heavy-Tailed Perturbations

An alternative to regularizing the leader is to perturb the leader's history with random noise, a framework known as Follow-the-Perturbed-Leader (FTPL). Traditionally, FTPL uses light-tailed noise (like Gumbel or Gaussian distributions), which fails to achieve the best of both worlds.

However, Jongyeong Lee et al. demonstrated in Follow-the-Perturbed-Leader with Fréchet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds that utilizing heavy-tailed perturbations (such as Fréchet distributions) achieves the exact same dual-optimality as specialized regularizers. The heavy tails ensure that the algorithm occasionally explores aggressively enough to remain robust against adaptive adversaries, yet the specific polynomial decay of the tail allows the algorithm to quickly stabilize its choices when a clear stochastic gap emerges.

Generalizing Beyond Simple Bandits

The intuition of self-bounding regret and adaptive curvature has expanded far beyond the classic multi-armed bandit problem into more complex decision-making domains.

  • Episodic Markov Decision Processes (MDPs): In reinforcement learning, an agent must navigate state transitions while managing unknown dynamics. Tiancheng Jin et al. in The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition proved that by combining transition estimation confidence sets with mirror descent, an agent can achieve $O(\text{polylog}(T))$ regret in stable MDPs and $O(\sqrt{T})$ regret in adversarial MDPs, even when the underlying physics of the world are completely unknown.
  • Constrained Optimization: When decisions are bound by resource constraints (the online knapsack problem), Matteo Castiglioni et al. in Online Learning with Knapsacks: the Best of Both Worlds demonstrated that embedding BOBW regret minimizers within a primal-dual optimization loop allows a system to maintain optimal competitive ratios against adversaries while maximizing resource efficiency in i.i.d. settings.

By shifting the focus from explicit environment detection to the intrinsic geometry of the optimization space, best-of-both-worlds algorithms provide a mathematically elegant guarantee: they exploit predictability whenever it is present, without ever compromising safety when it disappears.

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 2, frozen text):

@misc{lacuna_best_of_both_worlds_adaptation_01065b88_v2,
  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/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake