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:
- 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.
- 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