PaperlayerView exact revision on arXiv

Source-linked AI summary

Thompson Sampling for Combinatorial Semi-Bandits

Siwei Wang, Wei Chen

arXiv:1803.04623v5cs.LG

TL;DR

The paper studies combinatorial bandit analysis under dependence among super arms. It reports results on dropping an independence assumption and compares methods experimentally.

  • Problem

    Dependence among super arms may invalidate the preceding high-probability analysis.

  • Method

    The paper analyzes combinatorial bandit regret using quantities including the largest super-arm size and minimum gaps.

  • Results

    The paper reports that independence assumptions can be dropped in a considered setting and presents experimental comparisons among algorithms.

  • Takeaways & Limitations

    The analysis covers multi-armed bandit and matroid bandit problems and obtains theoretical regret results.

  • Takeaways & Limitations

    The paper assumes that all base-arm distributions satisfy a stated condition, while an adaptive choice is left as a further question.

Abstract

from arXiv · show

In this paper, we study the application of the Thompson sampling (TS) methodology to the stochastic combinatorial multi-armed bandit (CMAB) framework. We first analyze the standard TS algorithm for the general CMAB model when the outcome distributions of all the base arms are independent, and obtain a distribution-dependent regret bound of $O(m\log K_{\max}\log T / Δ_{\min})$, where $m$ is the number of base arms, $K_{\max}$ is the size of the largest super arm, $T$ is the time horizon, and $Δ_{\min}$ is the minimum gap between the expected reward of the optimal solution and any non-optimal solution. This regret upper bound is better than the $O(m(\log K_{\max})^2\log T / Δ_{\min})$ bound in prior works. Moreover, our novel analysis techniques can help to tighten the regret bounds of other existing UCB-based policies (e.g., ESCB), as we improve the method of counting the cumulative regret. Then we consider the matroid bandit setting (a special class of CMAB model), where we could remove the independence assumption across arms and achieve a regret upper bound that matches the lower bound. Except for the regret upper bounds, we also point out that one cannot directly replace the exact offline oracle (which takes the parameters of an offline problem instance as input and outputs the exact best action under this instance) with an approximation oracle in TS algorithm for even the classical MAB problem. Finally, we use some experiments to show the comparison between regrets of TS and other existing algorithms, the experimental results show that TS outperforms existing baselines.

1. Introduction

This paper studies Thompson sampling for stochastic combinatorial multi-armed bandits, including independent-arm CMAB, matroid bandits, and oracle limitations. It develops tighter regret analyses, removes independence in the matroid setting, and reports stronger empirical performance than existing baselines.

  • Problem setting: CMAB selects sets of base arms as super arms and observes outcomes for every selected arm in the semi-bandit setting.The framework is motivated by applications including wireless networking, social networks, and online advertising.
  • Thompson sampling: TS uses Bayesian updates: it samples parameters, selects an action using those parameters, and updates the distribution from current feedback.The paper combines standard TS with an exact offline oracle to obtain combinatorial Thompson sampling (CTS).
  • Independent-arm CMAB: Under independent base-arm outcomes, CTS obtains a tighter distribution-dependent regret bound by removing one log Kmax factor from prior CMAB analyses.The analysis also reduces one log Kmax factor in the regret bound of the ESCB policy while retaining comparable bounds.
  • Matroid bandits: For matroid bandits, CTS drops the independence assumption and achieves a regret upper bound matching the known lower bound.The paper generalizes top-k bandits to matroid bandits while preserving the matching regret guarantee.
  • Experiments and limitations: Experiments report that Thompson sampling performs better than existing UCB-based CMAB policies on both matroid and non-matroid instances.The paper also shows that replacing CTS’s exact offline oracle with an approximation oracle can produce Θ(T) approximation regret, even for classical MAB.

2. Model and Definitions

The CMAB model represents actions as super arms selected from a feasible family, with unknown base-arm outcome distributions and semi-bandit feedback. Its objective is to minimize expected regret over a finite horizon, under reward regularity assumptions; matroid bandits are a special case.

  • A CMAB instance is specified by base arms, feasible super arms, an outcome distribution, reward and feedback functions, and a parameter vector of mean outcomes.
  • At each time t, the player selects a super arm, receives a reward based on the sampled outcome vector, and observes feedback generated from that action and outcome.The outcome vector is drawn from the environment distribution independently of other random variables.
  • Under semi-bandit feedback, the observation consists of each selected base arm and its outcome.
  • The learning algorithm uses historical selected actions and feedback through time t−1 to choose the next action.
  • The reward of a super arm depends only on the mean outcomes of its included base arms and is assumed Lipschitz-continuous in those means under the one-norm.The Lipschitz condition uses a constant B and the projected mean vectors on the super arm.
  • The objective is to minimize total expected regret over horizon T, with matroid bandits forming a special CMAB setting whose feasible family is a matroid.

3. Combinatorial Thompson Sampling

The paper defines combinatorial Thompson Sampling (CTS) for CMAB by sampling base-arm parameters, selecting a super arm through an exact oracle, and updating Beta priors from observations. Under independent base-arm outcomes, its regret analysis improves the logarithmic dependence on K_max, while showing limitations for approximation oracles and an unavoidable exponential constant term.

  • Algorithm: CTS samples each base arm’s parameter from its Beta posterior, sends the sample vector to an exact oracle, and plays the returned super arm.Observations from selected arms are transformed into Bernoulli variables and used to update their Beta distributions.
  • Regret upper bound: Under mutually independent base-arm outcomes and the stated Lipschitz assumptions, Theorem 1 gives a distribution-dependent regret bound for CTS.The analysis uses concentration inequalities for empirical means and an ε-neighborhood to handle the continuous Beta prior.
  • Regret upper bound: O(m log K_max log T/Δ_min) is the leading log T term, improving prior O(m(log K_max)^2 log T/Δ_min) bounds by one log K_max factor.The same analysis also reduces ESCB’s regret upper bound to O(m log K_max log T/Δ_min).
  • Computational comparison: CTS can avoid ESCB’s exponential computation over all super arms by using an efficient offline oracle, such as Dijkstra’s algorithm for minimum-weight paths.ESCB must enumerate paths and compute confidence bounds for each, whereas CTS invokes the oracle on sampled parameters.
  • Exponential constant term: The general CTS analysis contains an exponential constant term that the paper proves unavoidable for CMAB, arising from a bad initial prior distribution.The algorithm needs all k* arms in the optimal super arm to receive samples close to their means simultaneously.
  • Oracle limitation: An approximation oracle can yield Θ(T) approximation regret even for a classical MAB instance, so CTS requires an exact oracle for its stated guarantees.The paper constructs an MAB instance and approximation oracle with approximation regret at least Ω(min{2^k*, T}).

4. Matroid Bandit Case

For matroid bandits, CTS uses the greedy exact oracle and a bijection-based regret decomposition that compares individual base arms rather than whole super arms. This structure removes the need for independent outcome distributions, and the leading log T term matches the regret lower bound.

  • Greedy oracle: The matroid oracle greedily adds the feasible remaining arm with the largest parameter until no further arm can be included.Existing results establish that this greedy policy is exact for the matroid setting.
  • Regret upper bound: The leading log T term in the matroid regret bound matches the corresponding lower bound when ε is small.The bound is stated for the CTS algorithm under the matroid bandit setting, with constants independent of the problem instance.
  • Independence assumption: The matroid structure removes the independence assumption across base-arm outcome distributions.The analysis compares two base arms at one greedy step instead of requiring independence across complete super arms.
  • Regret decomposition: A bijection maps the arms selected in each greedy action to the optimal super arm, decoupling super-arm regret into paired base-arm comparisons.The mapped arms remain feasible at the corresponding greedy step, enabling comparisons analogous to classical MAB analysis.

5. Experiments

The experiments compare CTS with UCB- and ESCB-based baselines on matroid and general CMAB problems. CTS generally achieves lower regret, especially as the horizon grows, while some tuned baselines perform better only in limited settings.

  • Matroid Bandit: CTS has smaller regret than CUCB, CUCB-m, and C-KL-UCB in both maximum-spanning-tree experiments.The experiments include independent arm distributions and correlated arm distributions generated from a shared random variable.
  • Matroid Bandit: C-KL-UCB-m performs better for small T but loses to CTS when T is very large.The authors note that C-KL-UCB-m uses parameters without a theoretical guarantee.
  • General CMAB: The shortest-path setting minimizes path cost using independent Bernoulli edge outcomes, whereas ESCB is omitted because its per-super-arm computation is too expensive.Each super arm contains five of the 20 base arms in the additional comparison.
  • The Shortest Path: CTS has much smaller regret than CUCB, CUCB-m, and C-KL-UCB on the shortest-path experiments, especially when T is large.The graphs contain many near-optimal paths, including paths disjoint from the optimal path.
  • General CMAB: CTS outperforms both ESCB policies in the general CMAB experiment, while all compared policies outperform CUCB.The experiment varies the number of available super arms between 10 and 100.

6. Conclusion and Future Work

The paper applies combinatorial Thompson sampling to multi-armed and matroid bandits and derives theoretical regret bounds. It identifies correlated-arm analysis and adaptive initialization as directions for further work.

  • Contributions: The paper applies combinatorial Thompson sampling to combinatorial multi-armed bandit and matroid bandit problems.The stated contribution includes theoretical regret upper bounds for these settings.
  • Future Work: Pulling each base arm initially can reduce the constant term to non-exponential, but the player does not know how many initial slots are sufficient.The paper identifies adaptive policies or additional assumptions as possible ways to address this uncertainty.
  • Open Questions: The analysis remains limited by an independence assumption for base-arm distributions in the general setting.The paper raises correlated arm distributions as an open question for CTS analysis.

Appendix A.1. Proof of Lemma 2

The proof of Lemma 2 repeatedly restricts candidate oracle outputs using intersections with the optimal super arm. Each step reduces the relevant subset, while Lipschitz and optimality arguments preserve the required bounds.

  • Oracle Restriction: The proof claims that an oracle output disjoint from the optimal super arm cannot occur under the constructed parameter vector.The argument uses the fact that the parameter vector differs from the true vector only on the optimal super arm.
  • Inequality Justification: The proof combines oracle optimality, Lipschitz continuity, and the definition of the solution gap to establish the intermediate inequalities.These ingredients are explicitly identified when justifying the displayed equations.
  • Induction: When the oracle output intersects the optimal super arm in a nonempty proper subset, the proof repeats the restriction argument on that subset.The constructed output is represented as S1 with intersection Z1 satisfying Z1 ≠ S* and Z1 ≠ ∅.
  • Induction: Each induction step decreases the relevant subset by at least one until the procedure reaches a subset of the optimal super arm.The accumulated error remains bounded by Bk*^2ε, below the threshold used in the proof.

Appendix A.2. Proof of Lemma 3

The proof of Lemma 3 bounds the expected duration of events involving posterior samples by analyzing binomial feedback probabilities. It first derives concentration bounds and then extends them to updates occurring at arbitrary time steps.

  • Binomial Bounds: The proof splits the binomial analysis into three ranges of the feedback count and applies Chernoff-Hoeffding bounds for sufficiently large q.The resulting bounds include terms of the form 1 − 2e^(-q/(8ε^2)).
  • Feedback Accounting: The proof tracks feedback counts for a fixed base-arm subset Z and defines pZ,NZ(t),ε as the probability that the second event does not occur.At the q-th relevant time, each arm in Z has q feedbacks.
  • Feedback Accounting: Conditioning on observation histories lets the proof express expected waiting times through reciprocal event probabilities.The expected number of slots between successive relevant events is written as E[1/pZ,NZ] − 1 in the simplified setting.
  • Arbitrary Updates: The real setting permits prior updates at arbitrary time steps, so the waiting-time expression becomes a weighted mean over larger feedback-count vectors.The proof retains an upper bound despite not knowing the exact weights.

Appendix B. Proof of Theorem 4

The appendix introduces Fact 6 and uses a greedy-order bijection to decompose action-level regret into mapped pairs of selected and optimal arms.

  • Regret decomposition: Fact 6 provides a bijection from the greedy-selected arms to the optimal set.The bijection maps positions in the selected action to arms in S∗.
  • Regret decomposition: The bijection decouples each action’s regret into contributions from mapped arm pairs.This converts the analysis from whole actions to individual selected–optimal arm pairs.
  • Regret decomposition: N_i,j(t) counts rounds in which selected arm i is mapped to optimal arm j.The count is defined for i outside S∗ and j inside S∗ over the horizon.
  • Proof structure: The appendix then bounds these pair counts through intermediate lemmas before presenting Theorem 4’s proof.The stated proof structure is to establish lemmas and then complete the theorem proof.

Appendix B.1. Proof of Some Lemmas

This subsection establishes lemmas for controlling sampled-arm events and pair-count terms, using the independence of sampled values in Algorithm 1 and a greedy-oracle argument.

  • Exceptional events: The proof defines W_j as sampled-value configurations where some A_i,j(t) occurs without C_i,j(t), with W_-j projecting away coordinate j.These sets organize the exceptional events used in the lemma bounds.
  • Probability control: Algorithm 1 treats θ_j(t) as independent of the remaining sampled values θ_-j(t), conditional on past feedback.This conditional independence supports factorizing probabilities involving arm j and the other sampled values.
  • Probability control: The probability that θ_j(t) exceeds µ_j−ε changes only when base arm j receives feedback.The analysis indexes these changes by τ_j,q, the time of arm j’s q-th observation.
  • Greedy selection: Fact 7 analyzes greedy selection by separating cases where earlier greedy steps remain unchanged from cases altered by a larger sampled value.The argument tracks how a changed step can affect the selection of arm i.

Appendix B.2. Main Proof of Theorem 4

The main proof bounds Theorem 4 by decomposing regret into mapped-arm contributions, controlling estimation errors and sampled-value events, and summing the resulting terms under an ε-gap condition.

  • Theorem statement: Theorem 4 states a regret upper bound for Algorithm 1 in the matroid bandit setting.The supplied theorem passage identifies the result but does not include the bound’s displayed expression.
  • Conditions: The analysis assumes ε > 0 with Δ_i−2ε > 0 for every relevant non-optimal arm.The constant α_2 is stated to be independent of the problem instance.
  • Regret decomposition: A bijection between selected and optimal arms decomposes action regret into pairwise contributions counted by N_i,j(t).This is the structural basis for summing regret over mapped-arm pairs.
  • Term bounds: The proof separately controls estimation-error rounds and the contribution from sampled values crossing thresholds involving µ_jk−µ_i−2ε.The argument uses concentration bounds for empirical means and a bound on how often threshold crossings occur.
  • Conclusion: The final step sums all bounded terms to obtain the total expected regret upper bound.The supplied passages indicate this summation and conclusion without reproducing the complete final expression.
Loading 1803.04623v5…