Source-linked AI summary
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
Wei Chen, Yajun Wang, Yang Yuan, Qinshi Wang
TL;DR
The paper addresses combinatorial bandits with nonlinear rewards and probabilistically triggered arms, where naive classical MAB treatment is inadequate. It introduces CMAB with an approximation oracle and CUCB, obtaining logarithmic distribution-dependent regret, broader distribution-independent bounds, and applications to coverage and influence maximization. The authors also correct an earlier claim by explicitly modeling probabilistic triggering in social influence maximization.
Problem
Combinatorial online learning must handle jointly played arms, nonlinear rewards, computationally hard optimization, and probabilistic triggering in applications such as advertising and viral marketing.
Method
The paper defines CMAB with super arms, semi-bandit observations, probabilistically triggered arms, and an (α,β)-approximation oracle, then develops CUCB regret analysis.
Results
CUCB achieves O(log n) distribution-dependent regret, distribution-independent bounds for broad CMAB classes, and significantly improves prior distribution-dependent bounds for linear combinatorial bandits.
Takeaways & Limitations
The framework supports nonlinear combinatorial bandit applications including probabilistic maximum coverage and social influence maximization, with the latter requiring probabilistically triggered arms.
Takeaways & Limitations
The analysis leaves open whether some bounds are tight, including dependence on 1/π for probabilistic triggering, and assumes a restricted form for expected nonlinear rewards.
Abstract
from arXiv · showhide
We define a general framework for a large class of combinatorial multi-armed bandit (CMAB) problems, where subsets of base arms with unknown distributions form super arms. In each round, a super arm is played and the base arms contained in the super arm are played and their outcomes are observed. We further consider the extension in which more based arms could be probabilistically triggered based on the outcomes of already triggered arms. The reward of the super arm depends on the outcomes of all played arms, and it only needs to satisfy two mild assumptions, which allow a large class of nonlinear reward instances. We assume the availability of an offline (α,β)-approximation oracle that takes the means of the outcome distributions of arms and outputs a super arm that with probability β generates an α fraction of the optimal expected reward. The objective of an online learning algorithm for CMAB is to minimize (α,β)-approximation regret, which is the difference between the αβ fraction of the expected reward when always playing the optimal super arm, and the expected reward of playing super arms according to the algorithm. We provide CUCB algorithm that achieves O(log n) distribution-dependent regret, where n is the number of rounds played, and we further provide distribution-independent bounds for a large class of reward functions. Our regret analysis is tight in that it matches the bound of UCB1 algorithm (up to a constant factor) for the classical MAB problem, and it significantly improves the regret bound in a earlier paper on combinatorial bandits with linear rewards. We apply our CMAB framework to two new applications, probabilistic maximum coverage and social influence maximization, both having nonlinear reward structures. In particular, application to social influence maximization requires our extension on probabilistically triggered arms.
1 Introduction
The paper develops a CMAB framework for combinatorial, nonlinear, and probabilistically triggered-arm settings, with CUCB providing regret guarantees through an approximation oracle. It applies the framework to advertising and social influence problems and improves prior linear-reward bounds.
- Motivation: Combinatorial applications require learning over jointly played arms, nonlinear rewards, and computationally hard offline optimization.Online advertising and viral marketing illustrate these challenges through page-user structures and stochastic social cascades.
- Framework: The CMAB framework plays super arms composed of base arms, observes their outcomes, and permits additional arms to be triggered probabilistically.This extension models settings such as social influence maximization, where triggering depends on outcomes of already played arms.
- Framework: An (α,β)-approximation oracle may return an α-quality super arm with probability β, so regret is measured against the αβ fraction of optimal expected reward.The oracle separates offline approximation from online learning while accommodating computationally hard combinatorial problems.
- Results: CUCB achieves O(log n) distribution-dependent regret and distribution-independent bounds for a large class of CMAB instances, including probabilistically triggered arms.For triggered arms, the bounds incorporate triggering probabilities.
- Applications: The framework covers nonlinear probabilistic maximum coverage and social influence maximization, applications not handled by existing work because of their nonlinear reward structures.The offline versions of both applications are NP-hard but have constant approximation algorithms.
- Results: Compared with prior combinatorial bandits with linear rewards, the analysis is tighter, adds distribution-independent bounds, and allows approximation-oracle failure probabilities.The framework also covers a broader class of linear and nonlinear rewards than the earlier work.
2 General CMAB Framework
The CMAB framework models super-arm selection with probabilistic triggering, shared observations, and nonlinear rewards under mild regularity assumptions. CUCB uses an approximation oracle to learn unknown arm means and achieves logarithmic distribution-dependent regret.
- CMAB model: A super arm is played each round, triggering its contained base arms and potentially additional arms through outcome-dependent cascades.Feedback consists of outcomes from the triggered arms; triggering events may depend on same-round outcomes and need not be mutually independent.
- Probabilistic triggering: Triggering probabilities quantify how likely each base arm is to be activated under a super arm, including the minimum nonzero probability p_i and global minimum p*.These probabilities may be unknown and can arise from combinatorial dependencies among triggered arms; deterministic triggering is the special case p_i = 1.
- Model flexibility: The model can include arms that are only probabilistically triggered, using dummy arms and super arms when necessary.This flexibility supports settings in which triggered arms do not belong directly to the selected super arm.
- Reward assumptions: The expected reward depends on the super arm and the vector of base-arm means, while supporting nonlinear reward functions.The framework assumes monotonicity and bounded smoothness, where changes in relevant means induce reward changes controlled by a continuous function f.
- Learning algorithm: CUCB maintains play counts and empirical means, then passes optimistic mean estimates to a computation oracle to select the next super arm.The oracle may use the expectation vector to return an α-approximate solution with success probability β, rather than requiring exact optimization.
- Regret objective: Approximation regret compares learning performance with the αβ fraction of the optimal expected reward because oracle success and approximation are both probabilistic or imperfect.The framework analyzes distribution-dependent and distribution-independent regret, with the former bounded by O(log n).
3 CUCB Algorithm for CMAB
CUCB maintains empirical means and confidence-adjusted estimates for base arms, then uses an approximation oracle to select super arms. Its analysis gives logarithmic distribution-dependent regret, distribution-independent bounds under polynomial bounded smoothness, and UCB1-level performance in classical MAB.
- Algorithm: CUCB maintains empirical means for each base arm and supplies confidence-adjusted estimates to the approximation oracle.The algorithm updates arm counts and empirical means after each round; it initializes unobserved arms optimistically to accommodate probabilistic triggering.
- Analysis: The analysis defines bad super arms, reward gaps, sampling thresholds, and oracle-failure events to bound approximation regret.A super arm is bad when its expected reward is below α · optµ, while oracle failure occurs with probability at most 1 − β.
- Regret bounds: O(log n) distribution-dependent regret is established for CUCB, with a more complicated leading term when some triggering probabilities are below 1.When all triggering probabilities equal 1, the result reduces to the non-probabilistic CMAB theorem; otherwise an additional 1/p_i factor appears in the leading ln n term.
- Regret bounds: For f(x) = γx^ω with 0 < ω ≤ 1, CUCB also achieves a distribution-independent regret bound for arbitrary arm distributions supported on [0, 1].The bound depends on the minimum triggering probability p* and the maximum reward gap Δmax.
- Refinements: When all triggering probabilities equal 1, the leading constant can be improved from 2(1 + c) to 4 at the cost of a second-order ln ln n term.The refined bound includes a term of the form 4(2 ln n + ln ln n) and an additive (1 + 2 ln ln n) · m · Δmax term.
- Special cases: In classical MAB, CUCB’s regret upper bound is at the same level as UCB1 up to a constant factor, with a tighter leading coefficient in the cited analysis.The paper reports 6/Δ_i versus 8/Δ_i in the leading ln n term and attributes the improvement to tighter analysis.
4 Applications
The paper applies CMAB to nonlinear probabilistic maximum coverage and social influence maximization, and specializes its analysis to linear-reward bandits. These applications receive approximation-regret guarantees, while the linear case improves prior bounds.
- 4.1 Probabilistic maximum coverage bandit: A deterministic (1 −1/e) approximation algorithm provides a (1 −1/e, 1)-approximation oracle for probabilistic maximum coverage.
- 4.1 Probabilistic maximum coverage bandit: Probabilistic maximum coverage models selecting k targets with unknown edge probabilities to maximize expected activated nodes.The CMAB formulation represents edges as Bernoulli arms and uses incident-edge super arms.
- 4.1 Probabilistic maximum coverage bandit: 12 · |E|2 · ln n · |E| · ∆max is the stated distribution-dependent approximation-regret bound for probabilistic maximum coverage.
- 4.1 Probabilistic maximum coverage bandit: For probabilistic maximum coverage, edges incident to the same selected node can share one counter, improving the ln n coefficient from edges to nodes in L.
- 4.2 Combinatorial bandits with linear rewards: The linear-reward specialization removes a factor of L+1 from the leading ln n coefficient compared with Gai et al. (2012).The paper also states that its coefficient is likely smaller than m · ∆max/(∆min)2 and derives a distribution-independent bound unavailable in that prior work.
5 Conclusion
The paper presents a general stochastic CMAB framework covering nonlinear rewards and probabilistically triggered arms, together with CUCB regret analysis and practical applications. It identifies several directions for extending the model and tightening its bounds.
- The framework accommodates nonlinear rewards among combinatorial stochastic arms and probabilistically triggered arms such as those in viral marketing.
- CUCB receives distribution-dependent and distribution-independent regret analyses, with applications to practical combinatorial bandit problems.
- Future work includes Markovian or restless CMAB, tighter regret bounds, and more general expected rewards depending beyond base-arm expectation vectors.The paper specifically questions the necessity of the 1/pi dependence under probabilistic triggering.
arXiv:1407.8339v6 [cs.LG] 29 Mar 2016
This excerpt develops a weaker theorem for bounded conditional-mean random variables and begins its martingale proof. The proof uses cumulative sums, filtrations, Markov’s inequality, and the inequality 1 + x ≤e^x.
- Theorem 2 considers Bernoulli-valued random variables with common conditional mean µ and defines their sum Y.
- The proof defines partial sums Yi and identifies Yn with the target sum Y.
- The argument uses the filtration {Fi} associated with the resulting martingale.
- Markov’s inequality and conditional-expectation factorization are used to bound the exponential moment of the sum.
- The Bernoulli distribution yields the inner expectation, and 1 + x ≤e^x supplies the final inequality step.