Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms

Alihan Hüyük, Cem TekinarXiv 2018 · arXiv · OpenReview

Abstract

We analyze the regret of combinatorial Thompson sampling (CTS) for the combinatorial multi-armed bandit with probabilistically triggered arms under the semi-bandit feedback setting. We assume that the learner has access to an exact optimization oracle but does not know the expected base arm outcomes beforehand. When the expected reward function is Lipschitz continuous in the expected base arm outcomes, we derive $O(\sum_{i =1}^m \log T / (p_i \Delta_i))$ regret bound for CTS, where $m$ denotes the number of base arms, $p_i$ denotes the minimum non-zero triggering probability of base arm $i$ and $\Delta_i$ denotes the minimum suboptimality gap of base arm $i$. We also compare CTS with combinatorial upper confidence bound (CUCB) via numerical experiments on a cascading bandit problem.

Introduction

The Multi-armed Bandit (MAB) framework is a cornerstone of reinforcement learning, addressing the fundamental trade-off between exploration and exploitation. However, many real-world applications involve complex interactions where pulling a "super arm" (a set of actions) triggers a sequence of probabilistic events. For instance, in a search engine, presenting a list of links triggers user interactions that depend on previous items in the list. This scenario is modeled as the Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms (CMAB-PTA).

While Upper Confidence Bound (UCB) algorithms have been rigorously analyzed for CMAB-PTA, Thompson Sampling (TS)—a Bayesian alternative often favored for its empirical performance—lacked a tight theoretical regret analysis in this specific setting. This paper bridges that gap by providing the first order-optimal regret bound for Combinatorial Thompson Sampling (CTS) under semi-bandit feedback.

The CTS Algorithm

The CTS algorithm maintains a posterior distribution (typically a Beta distribution) for the success probability of each base arm. At each round $t$:

  1. Sampling: The learner draws a sample from the posterior of each base arm.
  2. Optimization: An exact optimization oracle uses these samples to select the optimal super arm.
  3. Feedback: The learner observes outcomes for all base arms triggered by the chosen super arm (semi-bandit feedback).
  4. Update: The posterior distributions are updated based on the observed outcomes.

The authors introduce a novel regret decomposition that handles the complexities of probabilistic triggering without requiring the reward function to be monotonic, a common restriction in previous UCB-based analyses.

Theoretical Contributions

The primary contribution is the derivation of a logarithmic regret bound: $O(\sum_{i=1}^m \frac{\log T}{p_i \Delta_i})$.

  • The $1/p_i$ Factor: The bound depends inversely on $p_i$, the minimum probability that arm $i$ is triggered. While this suggests higher regret for rarely triggered arms, the authors argue this is a fundamental characteristic of the problem: arms that are seldom seen take longer to learn.
  • Tightness: This bound matches the theoretical lower bounds for this class of problems, establishing CTS as an order-optimal algorithm.

Numerical Experiments

The authors evaluate CTS against the Combinatorial Upper Confidence Bound (CUCB) algorithm using synthetic cascading bandit problems.

Disjunctive Cascading Bandit

In the standard cascading model (disjunctive case), where a user clicks the first attractive item and stops, CTS demonstrates a significant performance advantage over CUCB. CUCB tends to suffer from excessive exploration as its deterministic confidence bounds remain high for extended periods.

Regret comparison between CTS and CUCB in a disjunctive cascading bandit scenario.

Conjunctive "Hard" Case

The authors also tested a "conjunctive" case where feedback stops at the first failure. In this more challenging environment, CUCB initially performs better due to its deterministic nature handling a single "bad arm" more effectively. However, as shown in the figure below, CTS adapts more efficiently in the long run, overtaking CUCB around round 80.

Regret comparison in a conjunctive "hard" case, showing CTS overtaking CUCB after an initial lag.

Conclusion and Future Work

This work provides a solid theoretical foundation for the use of Thompson Sampling in combinatorial settings with probabilistic triggering. While the current analysis assumes an exact optimization oracle, future research is needed to extend these guarantees to settings where only approximation oracles are available—a common constraint in NP-hard problems like influence maximization. Additionally, exploring conditions that might mitigate the $1/p_i$ dependence remains an open and promising direction.

Summary updated

Abstract

We analyze the regret of combinatorial Thompson sampling (CTS) for the combinatorial multi-armed bandit with probabilistically triggered arms under the semi-bandit feedback setting. We assume that the learner has access to an exact optimization oracle but does not know the expected base arm outcomes beforehand. When the expected reward function is Lipschitz continuous in the expected base arm outcomes, we derive $O(\sum_{i =1}^m \log T / (p_i \Delta_i))$ regret bound for CTS, where $m$ denotes the number of base arms, $p_i$ denotes the minimum non-zero triggering probability of base arm $i$ and $\Delta_i$ denotes the minimum suboptimality gap of base arm $i$. We also compare CTS with combinatorial upper confidence bound (CUCB) via numerical experiments on a cascading bandit problem.
BibTeX
@misc{huyuk2018thompson,
  author = {Alihan Hüyük and Cem Tekin},
  title = {{Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms}},
  year = {2018},
  eprint = {1809.02707},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.02707},
}
Figure