Abstract
This paper provides a rigorous theoretical analysis of Combinatorial Thompson Sampling (CTS) for the Combinatorial Multi-Armed Bandit (CMAB) problem with Probabilistically Triggered Arms (PTAs). While Upper Confidence Bound (UCB) methods have established theoretical guarantees in this setting, Thompson Sampling—a Bayesian alternative often superior in practice—lacked a formal regret bound for general Lipschitz continuous reward functions. The authors close this gap by proving that CTS achieves an order-optimal logarithmic regret bound and demonstrate its empirical superiority in cascading bandit scenarios.
Introduction
In classical Multi-Armed Bandit (MAB) problems, an agent selects a single action per round to maximize cumulative rewards. The Combinatorial Multi-Armed Bandit (CMAB) extension allows for the selection of a "super arm" (a subset of base arms). This research focuses on a complex variant: CMAB with Probabilistically Triggered Arms (PTAs). In this environment, selecting a super arm triggers a chain reaction that probabilistically activates other base arms. A primary example is influence maximization in social networks, where targeting specific users influences their connections in a cascading fashion.
The Combinatorial Thompson Sampling (CTS) Algorithm
The authors analyze the CTS algorithm, which maintains a Beta posterior distribution for the unknown mean outcome of each base arm. In each round, the algorithm:
- Samples a parameter from each posterior distribution.
- Uses an exact optimization "oracle" to identify the optimal super arm based on these samples.
- Plays the selected super arm and observes outcomes from all triggered arms (semi-bandit feedback).
- Updates the posteriors based on these observations.
Proving regret bounds for CTS in the presence of probabilistic triggering is challenging. The authors introduce a novel analytical tool called a trial threshold. This mathematical technique decouples the number of times an arm is attempted to be triggered from the number of times it is actually observed, allowing for a bound on regret caused by under-explored arms.
Theoretical Results
The paper establishes a quantitative regret bound of $O(\sum_{i=1}^m \log T / (p_i \Delta_i))$, where $m$ is the number of base arms, $T$ is the time horizon, $p_i$ is the minimum triggering probability, and $\Delta_i$ is the suboptimality gap. This result shows that CTS is theoretically as robust as CUCB, achieving order-optimal logarithmic regret. However, the bound highlights an unavoidable "triggering penalty": if an arm is rarely triggered (low $p_i$), the algorithm requires more time to learn its true reward, increasing total regret.
Empirical Performance
The authors evaluated CTS against CUCB using synthetic simulations of cascading bandit problems, such as search engine recommendations.
Disjunctive vs. Conjunctive Scenarios
In the disjunctive form (e.g., a user clicks the first attractive page they see), CTS demonstrates massive empirical dominance. As shown in Figure 2, CUCB's regret climbs rapidly due to rigid over-exploration of suboptimal combinatorial arms, while CTS's regret flattens quickly as it identifies the optimal strategy.
In a specifically crafted conjunctive scenario (e.g., a user reports the first unattractive page), the authors observed an interesting edge case. In an environment with 1 bad page and 999,999 good pages, CUCB initially outperforms CTS because it deterministically drops the bad arm once observed. However, as seen in Figure 1, CTS eventually overtakes CUCB after approximately 80 rounds, as CUCB's deterministic confidence bounds lead to unnecessary exploration in the long run.
Conclusion and Future Work
This work confirms that Thompson Sampling is a theoretically sound and practically superior choice for CMAB-PTA problems. Despite its success, two primary challenges remain: the theoretical dependence on the minimum triggering probability ($1/p^*$) and the assumption of an exact optimization oracle. Future research may focus on relaxing these constraints, particularly by developing regret bounds that accommodate approximation oracles for NP-hard combinatorial problems.
Summary updated