The Two Worlds of Multi-Armed Bandits
In multi-armed bandit (MAB) problems, a learner repeatedly chooses actions and receives rewards or incurs losses. Traditionally, these problems are divided into two distinct environments:
- Stochastic Environments: Losses are drawn from fixed, unknown distributions. In this setting, learners aim for "fast" regret that grows logarithmically with time ($O(\log T)$).
- Adversarial Environments: Losses are chosen arbitrarily by an opponent. Here, the environment is much harsher, and the best a learner can typically achieve is regret that grows with the square root of time ($O(\sqrt{T})$).
Historically, algorithms are highly specialized. A stochastic algorithm (like UCB or Thompson Sampling) performs exceptionally well in a stochastic setting but fails catastrophically against an adversary. Conversely, an adversarial algorithm (like Exp3) is overly cautious, failing to exploit the simplicity of a stochastic environment and resulting in suboptimal performance.
This paper tackles the combinatorial semi-bandit setting—a complex variant where the learner picks a subset of arms (a combinatorial action) and observes the individual loss of each arm in that subset. While "best-of-both-worlds" (BOBW) algorithms exist for simple MABs, extending them to the combinatorial setting with optimal constants has remained a significant open challenge. This paper introduces the first general algorithm to achieve this feat.
A Novel Hybrid Regularizer
To bridge the gap between these two worlds, the authors utilize the Follow-the-Regularized-Leader (FTRL) framework. The core innovation is a novel hybrid regularizer ($\Psi$) designed specifically for the semi-bandit feedback structure.
Instead of relying on complex "gap estimation" or hypothesis testing to detect the environment type and switch strategies, the algorithm blends two mathematical concepts to adapt arm-by-arm:
- Tsallis Entropy (with power 1/2): This is applied to arms that are likely suboptimal. It provides the necessary exploration characteristic of traditional bandit problems.
- Shannon Entropy (on the complement): This is applied to arms likely to be in the optimal set. By applying Shannon entropy to the complement of the action ($1-x$), the algorithm mimics "full-information" learning, behaving as if it has more certain data about these high-performing arms.
By combining these approaches, the algorithm treats "good" arms like a full-information problem and "bad" arms like a bandit problem. Crucially, it achieves this using a simple, time-decaying learning rate ($\eta_t = 1/\sqrt{t}$).
Key Theoretical Insights
The paper's theoretical analysis reveals several fascinating properties of this approach:
- Self-Bounding Regret: In stochastic settings, the regret naturally "bounds itself." Because the algorithm quickly identifies suboptimal arms, the variance of its estimators drops. This naturally leads to the faster $O(\log T)$ rate without requiring explicit changes to the algorithm's code.
- The $m$-set Symmetry: For the specific case where a learner must pick exactly $m$ arms out of $d$, the authors found a surprising result: if $m > d/2$, the semi-bandit problem is actually no harder than a full-information problem in the adversarial case.
Ultimately, the algorithm achieves theoretically optimal bounds: $O(C_{sto} \log T)$ in stochastic settings and $O(C_{adv} \sqrt{T})$ in adversarial settings, with optimal constants for both full combinatorial sets and fixed-size $m$-sets.
Empirical Performance
To validate the theory, the algorithm was evaluated on synthetic datasets designed to test the limits of both regimes. The stochastic environment featured fixed mean losses with a set gap between the best and second-best subsets. The adversarial environment used a challenging "switching" setup where the identity of the optimal arms changed periodically, mimicking real-world scenarios like network routing under targeted attacks.
As shown in the results, the "Hybrid" algorithm successfully achieves the best of both worlds. In the stochastic test, it is nearly as fast as Thompson Sampling (a top-tier stochastic-only algorithm). However, in the adversarial test, Thompson Sampling fails completely (exhibiting linear regret), while the Hybrid algorithm significantly outperforms standard adversarial baselines like EXP2.
Limitations and Future Directions
While this paper represents a major step forward for combinatorial semi-bandits, a few challenges remain:
- Full Bandit Feedback: The paper provides a preliminary extension to the full bandit case (where the learner only sees the total loss of the subset, not individual arms), but this is currently limited to the simplest action sets. Extending BOBW results to general action sets under full bandit feedback remains a difficult open problem.
- Instance Optimality: While the leading constants are optimal in a "worst-case" sense, it is not yet clear if the stochastic bound is "instance-optimal" (the absolute best possible constant for a specific, unique distribution of arm losses).
- Computational Complexity: For very complex combinatorial sets (e.g., specific graph structures), computing the FTRL update or sampling the action can be computationally expensive. Future work may need to focus on optimizing the underlying solvers for practical deployment.
Summary updated