Nonstochastic Contextual Combinatorial Bandits

Lukas Zierahn, Dirk van der Hoeven, Nicolò Cesa-Bianchi, Gergely NeuAISTATS 2023 · OpenReview

Abstract

We study a contextual version of online combinatorial optimisation with full and semi-bandit feedback. In this sequential decision-making problem, an online learner has to select an action from a combinatorial decision space after seeing a vector-valued context in each round. As a result of its action, the learner incurs a loss that is a bilinear function of the context vector and the vector representation of the chosen action. We consider two natural versions of the problem: semi-bandit where the losses are revealed for each component appearing in the learner’s combinatorial action, and full-bandit where only the total loss is observed. We design computationally efficient algorithms based on a new loss estimator that takes advantage of the special structure of the problem, and show regret bounds order $\sqrt{T}$ with respect to the time horizon. The bounds demonstrate polynomial scaling with the relevant problem parameters which is shown to be nearly optimal. The theoretical results are complemented by a set of experiments on simulated data.

Introduction

In the field of online learning, bandit algorithms are essential for decision-making under uncertainty. Two major extensions to the basic bandit setup are contextual bandits (where a feature vector or 'hint' is provided before acting) and combinatorial bandits (where actions involve selecting a set of items, such as a list of recommendations). While previous research has successfully combined these into contextual combinatorial bandits, most work has assumed a stochastic setting where rewards follow a stationary distribution.

However, real-world environments are often nonstochastic; user preferences shift, and external factors can change dynamically. This paper addresses the nonstochastic (adversarial) contextual combinatorial bandit problem, where losses can be generated by any process, including an adaptive adversary. The primary challenge lies in efficiently estimating a large matrix of unknown parameters while receiving only partial feedback in a high-dimensional space.

Methodology

The authors propose two primary algorithms tailored to different feedback levels: CO2-FTRL for semi-bandit feedback (where individual component losses are observed) and Exp3-Tensor for full-bandit feedback (where only the total loss is observed).

Technical Innovations

To maintain computational efficiency, the authors introduce two key techniques:

  1. Matrix Geometric Resampling (MGR): Instead of explicitly inverting massive covariance matrices, which is computationally prohibitive, MGR uses a sampling-based approach to estimate the inverse of the expected matrix. This allows the algorithms to run in polynomial time even when the decision space is exponentially large.
  2. Tensor-Valued Estimators: For the full-bandit case, linear operators are represented as 4th-order tensors. This allows the construction of an unbiased loss estimator from a single scalar observation (the total loss), effectively 'unflattening' information across dimensions.
The Matrix Geometric Resampling (MGR) algorithm used for efficient matrix estimation.

Experimental Setup

The algorithms were evaluated using simulated data designed to test various complexities. The context spaces ($B_{d,m}$) consisted of $d$-dimensional binary vectors, while the action sets ($B_{K,m}$) involved selecting $m$ items out of $K$ possibilities. The experiments compared the new algorithms against RealLinExp3 (which handles context but ignores combinatorial structure) and CombBand (which handles structure but ignores context).

Key Results

The authors prove that their algorithms achieve a regret of $O(\sqrt{T})$, meaning the average mistake rate vanishes over time. These bounds are shown to be nearly optimal. Specifically, in the semi-bandit case, the regret is $\tilde{O}(m\sqrt{dKT})$, while the established lower bound is $\Omega(\sqrt{dmKT})$.

Empirical results demonstrate that the proposed algorithms significantly outperform baselines that ignore either context or combinatorial structure. As shown in the regret analysis, the structured approach leads to more stable performance compared to simpler baselines, particularly as the problem complexity increases.

Box plot comparing the regret of EXP3-Tensor against baselines like RealLinExp3 and ComBand.

Discussion and Limitations

This work effectively bridges the gap between structured online optimization and adversarial contextual learning, proving that stationary assumptions are not required for good performance in complex tasks. However, a small theoretical gap of $\sqrt{m}$ remains between the upper and lower bounds. Additionally, the Exp3-Tensor algorithm showed sensitivity to hyperparameter tuning in simple scenarios, suggesting that its true strengths may be more apparent in highly expressive, real-world datasets. Future research may extend these methods to continuous context spaces and investigate closing the remaining theoretical gaps.

Summary updated

Abstract

We study a contextual version of online combinatorial optimisation with full and semi-bandit feedback. In this sequential decision-making problem, an online learner has to select an action from a combinatorial decision space after seeing a vector-valued context in each round. As a result of its action, the learner incurs a loss that is a bilinear function of the context vector and the vector representation of the chosen action. We consider two natural versions of the problem: semi-bandit where the losses are revealed for each component appearing in the learner’s combinatorial action, and full-bandit where only the total loss is observed. We design computationally efficient algorithms based on a new loss estimator that takes advantage of the special structure of the problem, and show regret bounds order $\sqrt{T}$ with respect to the time horizon. The bounds demonstrate polynomial scaling with the relevant problem parameters which is shown to be nearly optimal. The theoretical results are complemented by a set of experiments on simulated data.
BibTeX
@inproceedings{zierahn2023nonstochastic,
  author = {Lukas Zierahn and Dirk van der Hoeven and Nicolò Cesa-Bianchi and Gergely Neu},
  title = {{Nonstochastic Contextual Combinatorial Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=6Vh0VROpa6},
}
Figure