Adversarial Bandits against Arbitrary Strategies

Jung-hun Kim, Se-Young Yun

Abstract

We investigate the adversarial multi-armed bandit problem in non-stationary environments where the optimal action changes over time. The difficulty of this setting is characterized by an unknown parameter $S$, representing the number of switches in the best arm in hindsight. To address the challenge of unknown $S$, we employ a master-base framework utilizing Online Mirror Descent (OMD). We first demonstrate a master-base algorithm using simple OMD that achieves a regret bound of $\tilde{O}(S^{1/2}K^{1/3}T^{2/3})$, where the $T^{2/3}$ dependence arises from the variance of loss estimators. To mitigate this variance, we propose an advanced algorithm incorporating adaptive learning rates and log-barrier regularization. This approach achieves a near-optimal regret bound of $\tilde{O}(\min\{\sqrt{SKT\rho}, S\sqrt{KT}\})$, where $\rho$ represents a variance term, effectively overcoming the suboptimal time-dependence of previous parameter-free methods.

Introduction

In the classic multi-armed bandit (MAB) problem, an agent seeks to minimize cumulative regret by balancing exploration and exploitation. While the adversarial version of this problem assumes arbitrary losses, a significant complication arises in non-stationary environments where the "best" arm changes over time. If the number of switches, $S$, is known a priori, algorithms like EXP3.S can achieve optimal regret. However, in practical applications—such as recommendation systems or financial modeling—$S$ is typically unknown.

Previous "parameter-free" approaches designed to adapt to unknown $S$ have historically suffered from suboptimal regret bounds, often scaling with $T^{3/4}$ or $T^{2/3}$. This paper presents a hierarchical framework that achieves the gold-standard $\sqrt{T}$ time-dependence, providing a robust solution for adversarial bandits against arbitrary switching strategies.

The Master-Base Framework

The core of the proposed solution is a hierarchical Master-Base Framework. This structure manages the uncertainty of $S$ by running multiple "Base" algorithms in parallel, each initialized with a different hypothesis regarding the environment's volatility.

Algorithm 1: Simple OMD

The authors first analyze a version of the framework using standard Online Mirror Descent (OMD) with a negative entropy regularizer. In this setup, a "Master" algorithm selects a "Base" algorithm, which then selects an arm. While intuitive, this "double sampling" introduces significant variance in the loss estimators. Consequently, Algorithm 1 yields a regret bound of $\tilde{O}(S^{1/2}K^{1/3}T^{2/3})$. While an improvement over some benchmarks in long horizons ($T = \omega(S^6 K^4)$), the $T^{2/3}$ factor remains a bottleneck for efficiency.

Algorithm 2: Adaptive OMD and Log-Barrier Regularization

To achieve near-optimal regret, the authors introduce two critical modifications to the OMD structure:

  1. Log-Barrier Regularization: Instead of the standard negative entropy, the Master algorithm utilizes a log-barrier regularizer. The geometry of the log-barrier function provides a "negative bias" term that mathematically compensates for the high variance inherent in the hierarchical sampling process.
  2. Adaptive Learning Rates: The learning rates for both the Master and Base algorithms are not fixed. Instead, they adapt dynamically based on the observed variance of the loss estimators. When the variance of a specific base algorithm exceeds a calculated threshold, the Master increases the learning rate to adapt more aggressively to the changing environment.

Key Theoretical Results

The primary contribution of this work is the achievement of a regret bound that scales with $\sqrt{T}$ without prior knowledge of $S$. Algorithm 2 achieves: $$\tilde{O}(\min\{\sqrt{SKT\rho}, S\sqrt{KT}\})$$

This result is significant because it matches the performance of algorithms that are given $S$ as an input, effectively making the framework "universal." Furthermore, the authors demonstrate that these adversarial bounds extend naturally to non-stationary stochastic bandits, ensuring robustness across various types of environmental noise.

Discussion and Future Work

While the framework provides a theoretical breakthrough in parameter-free bandit optimization, it introduces certain practical considerations. The Master-Base structure requires running $O(\log T)$ base algorithms simultaneously. Although this logarithmic overhead is computationally manageable, it is more intensive than single-level algorithms.

Additionally, the authors note the use of a "uniform-mixing" trick in practical implementations to prevent the probability of selecting any arm from reaching zero, which would cause infinite variance. Future research may focus on providing a rigorous regret analysis for this specific implementation detail and extending these adaptive log-barrier techniques to more complex structures, such as linear or combinatorial bandits, where the number of switches remains unknown.

Summary updated

Abstract

We study the adversarial bandit problem against arbitrary strategies, where the difficulty is captured by an unknown parameter $S$, which is the number of switches in the best arm in hindsight. To handle this problem, we adopt the master-base framework using the online mirror descent method (OMD). We first provide a master-base algorithm with simple OMD, achieving $\tilde{O}(S^{1/2}K^{1/3}T^{2/3})$, in which $T^{2/3}$ comes from the variance of loss estimators. To mitigate the impact of the variance, we propose using adaptive learning rates for OMD and achieve $\tilde{O}(\min\{\sqrt{SKTρ},S\sqrt{KT}\})$, where $ρ$ is a variance term for loss estimators.
BibTeX
@article{kim2025adversarial,
  author = {Jung-hun Kim and Se-Young Yun},
  title = {{Adversarial Bandits against Arbitrary Strategies}},
  journal = {Accepted by TMLR},
  year = {2025},
  url = {https://openreview.net/forum?id=x4QrOh8uCs},
}
Figure