PaperlayerView exact revision on arXiv

Source-linked AI summary

Combinatorial Cascading Bandits

Branislav Kveton, Zheng Wen, Azin Ashkan, Csaba Szepesvari

arXiv:1507.04208v3cs.LGstat.ML

TL;DR

Combinatorial cascading bandits address online optimization with unknown binary item weights, where reward depends jointly on chosen items and feedback reveals only the first zero. CombCascade adapts UCB to this setting; its regret bounds match those of CombUCB1 up to O(1/f*) factors despite less feedback, and it performs well on real-world problems even when assumptions are violated.

  • Problem

    Online combinatorial learning with unknown item-weight distributions is challenging when rewards are nonlinear and feedback reveals only the first zero-weight item.

    Source: §1 · p. 1

  • Method

    CombCascade is a UCB-like algorithm that learns item weights from first-failure feedback and selects feasible solutions using their estimated rewards.

    Source: §1 · p. 2, §2.1 · p. 2

  • Results

    CombCascade's regret bounds match those of CombUCB1 up to O(1/f*) factors despite less feedback, and it performs well on two real-world problems when assumptions are violated.

    Source: §3.2 · pp. 5–6, §6 · p. 8

  • Takeaways & Limitations

    CombCascade provides a practical approach for routing and recommendation problems, and CombUCB1 cannot solve some instances of this setting.

    Source: §1 · p. 2, §6 · p. 8

    The analysis critically assumes independent item weights, though this may be relaxed to conditional independence given item features as future work.

    Source: §2.1 · p. 3, §6 · p. 8

Abstract

from arXiv · show

We propose combinatorial cascading bandits, a class of partial monitoring problems where at each step a learning agent chooses a tuple of ground items subject to constraints and receives a reward if and only if the weights of all chosen items are one. The weights of the items are binary, stochastic, and drawn independently of each other. The agent observes the index of the first chosen item whose weight is zero. This observation model arises in network routing, for instance, where the learning agent may only observe the first link in the routing path which is down, and blocks the path. We propose a UCB-like algorithm for solving our problems, CombCascade; and prove gap-dependent and gap-free upper bounds on its $n$-step regret. Our proofs build on recent work in stochastic combinatorial semi-bandits but also address two novel challenges of our setting, a non-linear reward function and partial observability. We evaluate CombCascade on two real-world problems and show that it performs well even when our modeling assumptions are violated. We also demonstrate that our setting requires a new learning algorithm.

1 Introduction

The paper frames combinatorial cascading bandits as online learning for constrained choices with binary stochastic item weights and partial feedback. It introduces CombCascade and regret guarantees for a setting that combines nonlinear rewards with limited observability.

1 Introduction

  • The framework models routing and recommendation objectives using binary stochastic item weights and rewards that require all chosen items to succeed.Routing maximizes the probability that all links on a path are up, while recommendation minimizes the probability that none of the recommended items are attractive.Source: §1 · p. 1
  • The agent observes only the first chosen item with zero weight, and feasible sets may be arbitrary rather than uniform matroids.This feedback pattern occurs in routing when only the first down link blocking a path is observed.Source: §1 · p. 1
  • CombCascade addresses nonlinear rewards and partial observability, challenges that prior semi-bandit analyses do not straightforwardly resolve.The analysis builds on work on stochastic combinatorial semi-bandits, including CombUCB1.Source: §1 · p. 2
  • The paper proposes CombCascade, proves gap-dependent and gap-free regret upper bounds, and evaluates it on two practical problems, including cases with violated modeling assumptions.It also shows that CombUCB1 cannot solve some problem instances.Source: §1 · p. 2

2 Combinatorial Cascading Bandits

This section defines combinatorial cascading bandits, presents CombCascade for conjunctive rewards, and describes a disjunctive variant. The framework uses constrained tuples of items, first-failure feedback, and independent binary item weights.

2.1 Setting

  • A bandit instance specifies ground items, a weight distribution, and feasible tuples; reward is one only when every chosen item has weight one.The agent observes the first zero-weight item in its tuple, or +∞ if none exists; the factored distribution assumption is critical to the analysis.Source: §2.1 · pp. 2–3
  • In the SMTP example, the agent chooses a path to maximize email delivery and observes the first down link when delivery fails.The model's independence assumption requires network links to fail independently, as in existing routing models.Source: §2.1 · p. 3

2.2 CombCascade Algorithm

  • CombCascade computes item-level upper confidence bounds, optimizes the resulting reward over feasible solutions, and updates estimates using observed items.Its regret bounds do not depend on the number of feasible solutions |Θ| and are polynomial in other quantities of interest.Source: §2.2 · pp. 3–4

2.3 Disjunctive Objective

  • For disjunctive rewards, which succeed when any chosen item has weight one, a variant uses complemented observations and lower confidence bounds.This formulation models recommendations where the user is satisfied by any recommended item.Source: §2.3 · p. 4
  • The disjunctive variant has regret bounds of the same form as Theorems 1 and 2, with ∆e,min and f* redefined.The definitions are given for the disjunctive reward function.Source: §2.3 · p. 4

3 Analysis

The analysis establishes regret upper bounds for CombCascade despite its nonlinear reward and partial observations, using a reduction that avoids requiring every item in a chosen solution to be observed. The bounds are independent of the number of feasible solutions and, up to O(1/f*) factors, match CombUCB1’s semi-bandit bounds.

3.1 Upper Bounds

  • The analysis reduces the problem to stochastic combinatorial semi-bandits, while addressing the nonlinear reward and the fact that only some chosen items are observed.Conditioning on observing all items can yield a loose bound when the probability of observing a whole solution is low.Source: §3.1 · p. 5
  • For suboptimal solutions with low expected reward, CombCascade can distinguish them without learning every item’s expected weight, by analyzing suitable prefixes.The chosen prefixes have observation probability at least half the optimal reward and a gap at least half the original solution’s gap.Source: §3.1 · p. 5
  • The gap-dependent analysis has linear dependency on K, at the cost of a multiplicative factor of 534 in the upper bound.The paper also derives a gap-free bound, but the supplied theorem statement does not provide its complete expression.Source: §3.1 · p. 5

3.2 Discussion

  • The upper bounds do not depend on the number of feasible solutions and are polynomial in other quantities of interest.The discussion states that the bounds match CombUCB1’s stochastic combinatorial semi-bandit bounds up to O(1/f*) factors.Source: §3.2 · pp. 5–6
  • The discussion says a large optimal reward f* is often reasonable in routing, while optimal recommendation lists may fail to satisfy a reasonably large fraction of users.This qualifies the setting in which the bounds’ O(1/f*) factors may be favorable.Source: §3.2 · p. 6

4 Experiments

Across synthetic, routing, and recommendation experiments, CombCascade handles cases where CombUCB1 fails and has regret that improves or flattens over time. In the recommendation experiment, however, its regret does not flatten and it does not learn the optimal solution under violated modeling assumptions.

4 Experiments

  • The experiments compare CombCascade with CombUCB1 on a synthetic problem and evaluate CombCascade on routing and diverse recommendations.The routing experiment uses six RocketFuel networks; the recommendation experiment uses MovieLens data and violates the item-independence assumption.Source: §4 · p. 6, §4.2 · p. 6, §4.3 · p. 7

4.1 Synthetic

  • In the synthetic experiment, CombUCB1 suffers linear regret when its selection criterion cannot identify the optimal solution; CombCascade learns it, but has higher regret than CombUCB1 when modeling assumptions are violated.When the criteria agree, both algorithms learn the optimal solution and CombCascade’s regret is slightly lower.Source: §4.1 · p. 6

4.2 Network Routing

  • CombCascade’s regret flattens over time in all six routing networks, indicating that it learns near-optimal policies there.The network-routing results are averaged over 50 runs.Source: §4.2 · p. 7, Figure 2 · p. 7

4.3 Diverse Recommendations

  • In diverse recommendations, CombCascade’s regret is concave over time but does not flatten, and it does not learn the optimal solution under the violated assumptions.The paper reports that its theory cannot explain this behavior.Source: §4.3 · p. 7

5 Related Work

The paper extends cascading bandits to arbitrary combinatorial constraints and introduces a product-of-UCBs algorithm and a new analysis for that setting. It also distinguishes its nonlinear, partial feedback from prior combinatorial learning work.

5 Related Work

  • The framework generalizes Kveton et al.'s cascading bandits to arbitrary combinatorial constraints and extends combinatorial semi-bandits to cascade feedback.The original cascading-bandit feasible set is a uniform matroid; the extension is demonstrated on two real-world problems.Source: §5 · p. 7
  • For non-matroid feasible sets, CombCascade selects the solution maximizing the product of UCBs, whereas CombUCB1 and CascadeUCB1 use sums or top-K choices.The passage says CombUCB1 may learn a suboptimal solution in this setting; all three algorithms can find the optimum in cascading bandits.Source: §5 · p. 8
  • The analysis avoids item-exchangeability arguments used for matroid-like feasible sets, building on Kveton et al. to obtain linear dependency on K in Theorem 1.The rest of the analysis is described as novel.Source: §5 · p. 8
  • Earlier partial-monitoring algorithms are impractical for this setting, while Lin et al.'s combinatorial feedback is linear rather than the paper's nonlinear feedback.The cited formulation of Bartok et al. would require reasoning over |Θ|^2 action pairs and O(2^L) space.Source: §5 · p. 8
  • Chen et al. study a known monotone transformation of an unknown linear reward with semi-bandit feedback, which is more informative than the paper's feedback.Le et al. study a network optimization problem with reward nonlinear in observations.Source: §5 · p. 8

6 Conclusions

The paper proposes combinatorial cascading bandits and CombCascade, with upper bounds on regret. Its two real-world evaluations show good performance even when modeling assumptions are violated, while item-weight independence remains a critical assumption.

6 Conclusions

  • The paper proposes combinatorial cascading bandits and the UCB-like CombCascade algorithm, and proves gap-dependent and gap-free regret upper bounds.The framework models routing and recommendation problems.Source: §6 · p. 8
  • CombCascade performs well on two real-world problems even when the modeling assumptions are violated.Source: §6 · p. 8
  • Independence of item weights is the strongest assumption and is critical; conditional independence given item features is noted as a possible relaxation for future work.The paper also identifies deriving a regret lower bound as future theoretical work.Source: §6 · p. 8

A Proof of Theorem 1

The proof decomposes expected regret around confidence-interval events, then reduces the analysis to counting suboptimal fully observed prefixes and applying a combinatorial semi-bandit argument.

A Proof of Theorem 1

  • It changes the counted events from partially observed suboptimal solutions to their fully observed prefixes.Source: A Proof of Theorem 1 · p. 10
  • The proof bounds how often a suboptimal prefix is chosen instead of the optimal solution, then applies Kveton et al.'s counting argument.Source: A Proof of Theorem 1 · p. 10
  • The proof first bounds regret when the high-probability confidence intervals fail, using the complement event where all item means lie within their intervals.Source: A Proof of Theorem 1 · p. 10

A.1 Confidence Intervals Fail

The confidence-interval failure term is bounded using Hoeffding's inequality.

A.1 Confidence Intervals Fail

  • Hoeffding's inequality bounds the regret contribution from confidence-interval failure because regret is bounded and the intervals hold with high probability.Source: §A.1 · p. 10

A.2 From Partially-Observed Solutions to Fully-Observed Prefixes

Treating every item in a chosen solution as observed can yield a loose regret bound when the solution’s observation probability is low. The analysis instead uses feasible prefixes and counts suboptimal prefixes that are hard to distinguish from the optimum.

A.2 From Partially-Observed Solutions to Fully-Observed Prefixes

  • Analyzing the problem as though all chosen items were observed can give a loose regret bound when the solution’s observation probability is low.Prefixes are introduced to address this issue.Source: §A.2 · p. 10
  • A prefix can retain at least half the solution’s gap while having observation probability at least half the optimal value.The analysis treats prefixes as feasible solutions to the original problem.Source: §A.2 · p. 10

A.3 Counting Suboptimal Prefixes

  • The counting argument targets suboptimal prefixes that are hard to distinguish from the optimal solution and bounds their contribution using an event F_t.A chosen prefix has at least as large a UCB value as its full solution, while the chosen solution has at least the optimal solution’s UCB value.Source: §A.3 · pp. 11–12

A.4 CombUCB1 Analysis of Kveton et al. [12]

The analysis bounds regret by counting how often suboptimal prefixes can be selected. It adapts a semi-bandit counting argument to the observed items in the cascading setting.

A.4 CombUCB1 Analysis of Kveton et al. [12]

  • The regret bound uses infinitely many mutually exclusive events to bound how often suboptimal prefixes are chosen.The argument applies because the event being bounded can occur only when all items in the prefix are observed.Source: §A.4 · p. 12
  • Events G_i,t classify how many suboptimal items in a prefix were observed no more than a specified number of times, and the events are exhaustive under stated conditions.The thresholds α_i and β_i decrease toward zero.Source: §A.4 · p. 12
  • Item-specific events identify insufficiently observed items, allowing the regret bound to use their observation counts and ordered prefix gaps.The analysis invokes a lemma of Kveton et al..Source: §A.4 · pp. 12–13

B Proof of Theorem 2

The gap-free proof splits regret at a threshold ε, bounding small-gap and larger-gap terms separately. Technical lemmas support the prefix reduction and a bound used in the analysis.

B Proof of Theorem 2

  • The proof splits regret into solutions with gaps at most ε and gaps larger than ε, bounding the first term directly and the second as in the gap-dependent analysis.For the second term, the minimum item gap is at least ε.Source: B Proof of Theorem 2 · p. 13

C Technical Lemmas

  • For any feasible solution, a prefix can be chosen with gap at least half the solution’s gap and observation probability at least half the optimal value.The lemma supplies the prefix property used in the preceding analysis.Source: C Technical Lemmas · p. 14
  • The bound in Lemma 2 is tight when all p_k equal 1 and all u_k equal 0.Source: C Technical Lemmas · p. 14
Loading 1507.04208v3…