Abstract
Fast changing states or volatile environments pose a significant challenge to online optimization, which needs to perform rapid adaptation under limited observation. In this paper, we give query and regret optimal bandit algorithms under the strict notion of strongly adaptive regret, which measures the maximum regret over any contiguous interval $I$. Due to its worst-case nature, there is an almost-linear $\Omega(|I|^{1-\epsilon})$ regret lower bound, when only one query per round is allowed [Daniely el al, ICML 2015]. Surprisingly, with just two queries per round, we give Strongly Adaptive Bandit Learner (StABL) that achieves $\tilde{O}(\sqrt{n|I|})$ adaptive regret for multi-armed bandits with $n$ arms. The bound is tight and cannot be improved in general. Our algorithm leverages a multiplicative update scheme of varying stepsizes and a carefully chosen observation distribution to control the variance. Furthermore, we extend our results and provide optimal algorithms in the bandit convex optimization setting. Finally, we empirically demonstrate the superior performance of our algorithms under volatile environments and for downstream tasks, such as algorithm selection for hyperparameter optimization.
Introduction: The Challenge of Volatility
In the world of online optimization, success is typically measured by regret: the performance gap between an algorithm and the single best fixed strategy in hindsight. However, in non-stationary or "volatile" environments—where the optimal strategy changes over time—standard regret is often insufficient as it rewards static behavior. Researchers instead turn to adaptive regret, which evaluates performance over every possible time interval.
Achieving low adaptive regret usually requires running multiple "base learners" in parallel, which necessitates querying (evaluating) $O(\log T)$ or $O(\log \log T)$ options per round. In many practical applications, such as hyperparameter optimization for large-scale models, evaluating even a handful of options is prohibitively expensive. Given that a single query per round is theoretically insufficient for near-optimal adaptive regret, this paper investigates whether optimal adaptivity can be achieved with just two queries.
The Strongly Adaptive Bandit Learner (StABL)
The authors introduce the Strongly Adaptive Bandit Learner (StABL). StABL utilizes a "Master-and-Experts" framework with a novel information-gathering strategy. It maintains base learners (EXP3 instances) assigned to a geometric interval set, ensuring a specialized learner exists for any time scale.
The core innovation is the Two-Query Strategy:
- Query 1 (The Play): The algorithm selects an arm to play and incurs its associated loss.
- Query 2 (The Exploration): A second query samples an arm from a carefully designed distribution $P(t)$. This distribution is a mixture designed to control variance for both base learners and the meta-learner.
By decoupling the randomness of the play from the exploration, StABL constructs a bounded, unbiased estimator of the loss vector, allowing all active learners to update their weights without observing every arm's loss.
Empirical Performance and Key Results
The paper demonstrates that StABL achieves an expected adaptive regret of $\tilde{O}(\sqrt{n|I|})$, matching theoretical lower bounds. Empirically, StABL was tested on synthetic environments with shifting rewards and on algorithm selection for hyperparameter optimization using Black-Box Optimization Benchmark (BBOB) functions.
Key findings include:
- Rapid Recovery: StABL recovers significantly faster than standard EXP3 after environmental shifts.
- Exploration Efficiency: The specialized exploration distribution $P(t)$ significantly outperforms naive uniform exploration (StABL_naive), and the multi-scale geometric interval approach outperforms single-scale baselines.
- BCO Efficiency: For continuous domains (Bandit Convex Optimization), the authors achieved $\tilde{O}(\sqrt{|I|})$ adaptive regret with just three queries, independent of the condition number of the functions.
Conclusion and Future Directions
StABL proves that near-optimal adaptivity in volatile environments is possible with minimal query overhead. While the current regret bound includes a $\log^{1.5} T$ factor, future work may aim to reduce this to $\sqrt{\log T}$. Additionally, while 3 queries are proven sufficient for BCO, the authors suspect a 2-query strategy might also be feasible. Extending these query-efficient techniques to dynamic regret remains an open and challenging problem.
Summary updated