Further Adaptive Best-of-Both-Worlds Algorithm for Combinatorial Semi-Bandits

Taira Tsuchiya, Shinji Ito, Junya HondaAISTATS 2023 · OpenReview

Abstract

We consider the combinatorial semi-bandit problem and present a new algorithm with a best-of-both-worlds regret guarantee; the regrets are bounded near-optimally in the stochastic and adversarial regimes. In the stochastic regime, we prove a variance-dependent regret bound depending on the tight suboptimality gap introduced by Kveton et al. (2015) with a good leading constant. In the adversarial regime, we show that the same algorithm simultaneously obtains various data-dependent regret bounds. Our algorithm is based on the follow-the-regularized-leader framework with a refined regularizer and adaptive learning rate. Finally, we numerically test the proposed algorithm and confirm its superior or competitive performance over existing algorithms, including Thompson sampling under most settings.

Introduction: The Challenge of Dual Regimes

In online decision-making, the combinatorial semi-bandit problem requires a learner to choose a "super-arm" (e.g., a path in a graph or a recommendation list) and observe individual losses for each constituent item. Traditionally, algorithms are optimized for one of two environments: the stochastic regime, where losses are i.i.d. and regret grows logarithmically, or the adversarial regime, where losses are arbitrary and regret grows with the square root of time.

The real-world challenge is that the environment's nature is often unknown. An algorithm specialized for stability may fail under attack, while a purely adversarial algorithm is often too conservative to exploit stable structures. This paper introduces a "Best-of-Both-Worlds" (BOBW) approach that adapts to either regime, specifically leveraging low variance—a common feature in real-world data like click-through rates—to achieve significantly tighter bounds.

The LBINFV Algorithm

The authors propose LBINFV (Logarithmic Barrier Implicit Normalized Forecaster considering Variances), built on the Optimistic Follow-the-Regularized-Leader (OFTRL) framework.

Algorithm 1: The LBINFV framework for semi-bandits.

Key innovations include:

  • Hybrid Regularizer: Combines a logarithmic barrier with Shannon entropy to handle combinatorial structures more effectively than standard methods.
  • Adaptive Learning Rate: Dynamically adjusts based on the cumulative squared error of the algorithm's predictions.
  • Dual Prediction Flavors: Offers two variants: Least Squares (LS) for optimal stochastic constants and Gradient Descent (GD) for path-length regret bounds in slowly changing environments.

Theoretical Superiority and Variance Awareness

A central insight of this work is that variance is the "secret sauce." In many applications, the variance of an arm is much smaller than the worst-case $1/4$. By making regret bounds dependent on variance ($\sigma^2$) rather than just dimension ($d$), the algorithm becomes far more efficient.

Comparison of regret bounds across different algorithms and regimes.

As shown in the comparison table above, the proposed LS-based algorithm achieves a leading constant in the stochastic regime that is at least 81 times smaller than previous state-of-the-art BOBW algorithms. In the adversarial regime, it simultaneously achieves first-order, second-order, and path-length bounds, demonstrating unprecedented versatility.

Empirical Performance

The algorithm was evaluated using synthetic Bernoulli distributions and semi-synthetic data from the KDD Cup 2012 (Tencent search engine dataset). The latter represents real-world click-through rates characterized by very low means and variances ($< 0.05$), making it an ideal test for variance-aware algorithms.

Key empirical findings include:

  • Consistency: LBINFV-LS and LBINFV-GD consistently outperformed existing BOBW baselines like HYBRID and LBINF.
  • Competitiveness: The algorithm performed competitively with Thompson Sampling, a specialized benchmark for pure stochastic regimes that is notoriously difficult to beat.
  • Resilience: Unlike standard stochastic algorithms (e.g., UCB), LBINFV maintained low regret even when subjected to adversarial shifts or corruptions.

Conclusion and Future Directions

While LBINFV sets a new standard for BOBW performance, it currently requires iterative optimization in each round, which can be computationally intensive for very high-dimensional sets. Future work may explore removing the Shannon entropy component to find closed-form solutions for action probabilities, potentially speeding up the algorithm significantly. Additionally, further refining how action-set structures (beyond matroids) impact performance constants remains an open area of research.

Summary updated

Abstract

We consider the combinatorial semi-bandit problem and present a new algorithm with a best-of-both-worlds regret guarantee; the regrets are bounded near-optimally in the stochastic and adversarial regimes. In the stochastic regime, we prove a variance-dependent regret bound depending on the tight suboptimality gap introduced by Kveton et al. (2015) with a good leading constant. In the adversarial regime, we show that the same algorithm simultaneously obtains various data-dependent regret bounds. Our algorithm is based on the follow-the-regularized-leader framework with a refined regularizer and adaptive learning rate. Finally, we numerically test the proposed algorithm and confirm its superior or competitive performance over existing algorithms, including Thompson sampling under most settings.
BibTeX
@inproceedings{tsuchiya2023further,
  author = {Taira Tsuchiya and Shinji Ito and Junya Honda},
  title = {{Further Adaptive Best-of-Both-Worlds Algorithm for Combinatorial Semi-Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=ncGjn4UTXp},
}
Figure