PaperlayerView exact revision on arXiv

Source-linked AI summary

Cascading Bandits: Learning to Rank in the Cascade Model

Branislav Kveton, Csaba Szepesvari, Zheng Wen, Azin Ashkan

arXiv:1502.02763v2cs.LGstat.ML

TL;DR

The paper studies how to learn the K most attractive items when users scan lists sequentially and feedback is limited by the first attractive item. It formulates this setting as cascading bandits, proposes two UCB-based algorithms, and analyzes their regret. The algorithms achieve logarithmic, item-linear upper bounds, while the CascadeKL-UCB upper bound nearly matches the lower bound and performs well empirically even under violated assumptions.

  • Problem

    The paper asks how to learn an optimal list of K items when item attraction probabilities are unknown and user feedback reveals only partial information.

  • Method

    The paper formulates cascading bandits as stochastic combinatorial partial monitoring and proposes CascadeUCB1 and CascadeKL-UCB.

  • Results

    The regret upper bounds are O(log n), linear in L, improve as K increases, and the CascadeKL-UCB upper bound matches the lower bound up to a logarithmic factor.

  • Takeaways & Limitations

    The algorithms perform well on several problems, including when the modeling assumptions are violated.

  • Takeaways & Limitations

    The framework is not practical when the number of items L is large, and its assumptions include independent item weights and at most one user click.

Abstract

from arXiv · show

A search engine usually outputs a list of $K$ web pages. The user examines this list, from the first web page to the last, and chooses the first attractive page. This model of user behavior is known as the cascade model. In this paper, we propose cascading bandits, a learning variant of the cascade model where the objective is to identify $K$ most attractive items. We formulate our problem as a stochastic combinatorial partial monitoring problem. We propose two algorithms for solving it, CascadeUCB1 and CascadeKL-UCB. We also prove gap-dependent upper bounds on the regret of these algorithms and derive a lower bound on the regret in cascading bandits. The lower bound matches the upper bound of CascadeKL-UCB up to a logarithmic factor. We experiment with our algorithms on several problems. The algorithms perform surprisingly well even when our modeling assumptions are violated.

1. Introduction

The paper introduces cascading bandits as an online learning variant of the cascade model, aiming to identify the K most attractive items from partial feedback. It develops algorithms, regret bounds, a lower bound, and empirical evaluations.

  • 1. Introduction: Cascading bandits extend the cascade model by requiring an agent to learn unknown item attraction probabilities while recommending lists of K items.The agent observes the clicked item's index and receives reward one when a click occurs.
  • 1. Introduction: The feedback reveals that items before the clicked item were unattractive, making it richer than the observed reward alone.
  • 1. Introduction: The paper formulates cascading bandits as a stochastic combinatorial partial monitoring problem and proposes CascadeUCB1 and CascadeKL-UCB.CascadeKL-UCB is expected to perform better when attraction probabilities are low.
  • 1. Introduction: The analysis provides gap-dependent regret upper bounds, a lower bound, and shows that the lower bound matches CascadeKL-UCB's upper bound up to a logarithmic factor.
  • 1. Introduction: Experiments on several problems show that the algorithms perform well even when the modeling assumptions are violated.

2. Background

The cascade model describes users scanning ranked items sequentially and clicking the first attractive item. Although simple and unable to model multiple clicks, it remains useful because it can reasonably fit click data.

  • 2. Background: The cascade model represents a ranked list of K items scanned from first to last, with each item having an attraction probability.
  • 2. Background: A user clicks an attractive item and stops examining the remaining items; otherwise, the user continues to the next item.
  • 2. Background: The probability that at least one item is attractive is maximized by selecting the K most attractive items.
  • 2. Background: The model cannot explain users clicking multiple items, although extended models represent multiple clicks and user persistence more accurately.
  • 2. Background: Despite this limitation, the cascade model remains attractive because it is simpler and can be reasonably fit to click data.

3. Cascading Bandits

Cascading bandits model learning when an agent recommends K items, observes only the user’s first click, and seeks the K most attractive items. Under independent Bernoulli attractions, two UCB-based algorithms use partial feedback to select lists and are evaluated through cumulative regret.

  • Problem setting: At each time t, the agent recommends K items from L, the user clicks the first attractive item, and the agent receives reward one for a click.Items up to the click are observed, while later items are unobserved; if no item attracts the user, no click occurs.
  • Model assumptions: Independent Bernoulli item attractions make expected list reward depend only on individual attraction probabilities and enable efficient learning from observed prefixes.The model assumes each item’s weight is independently drawn across items and time.
  • Objective: The learning objective is to maximize total reward, equivalently minimizing cumulative regret relative to the optimal list of K most attractive items.The optimal solution is unique as a set for exposition, although permutations have identical payoff.
  • Algorithms: The paper proposes CascadeUCB1 and CascadeKL-UCB, which estimate attraction-probability upper confidence bounds and recommend the K items with largest UCBs.The algorithms differ in how they compute the UCB; CascadeKL-UCB uses a Bernoulli KL-divergence criterion whose optimization is efficient.
  • Algorithm operation: The algorithms initialize item statistics with one sample, update estimates for recommended items observed before or at the click, and then recompute UCBs.Initialization can be performed in O(L) steps by presenting each item first once.

4. Analysis

The analysis connects regret to observed suboptimal items, yielding gap-dependent upper bounds for both algorithms and a matching lower-bound comparison under a restricted instance family.

  • Core analysis: Regret can occur only when the learner recommends suboptimal items that are observed.This connects the reward and feedback structures and drives the subsequent regret analysis.
  • Problem structure: The optimal solution consists of the K items with the highest attraction probabilities, while gaps measure item-discrimination difficulty.Items are ordered by decreasing attraction probability, with the first K labeled optimal and the remainder suboptimal.
  • Core analysis: A technical lemma rewrites expected differences between products of random variables into a form used to bound conditional regret.The lemma applies to two lists of K items with no repeated item across lists.
  • Upper bounds: Theorem 2 and Theorem 3 provide gap-dependent upper bounds for CascadeUCB1 and CascadeKL-UCB, respectively.Their proofs control confidence failures, decompose regret using Theorem 1, bound suboptimal-item selections, and apply algorithm-specific peeling arguments.

5. Experiments

The experiments evaluate regret scaling, item-ordering effects, robustness to DBN model violations, and comparison with ranked bandits. CascadeKL-UCB generally performs strongly, including when assumptions are violated, but some observed behavior remains unexplained theoretically.

  • Experimental design: The experiments test regret scaling, alternative item ordering, robustness under violated modeling assumptions, and comparison with ranked bandits.Four experiments cover these settings, including a comparison against RankedKL-UCB.
  • 5.1. Regret Bounds: CascadeUCB1 and CascadeKL-UCB show regret trends consistent with the upper bounds: regret increases with L and decreases with K and Δ.The reported trends are that regret doubles when L doubles, decreases as K increases, and increases when Δ decreases.
  • 5.1. Regret Bounds: CascadeKL-UCB outperforms CascadeUCB1, consistent with KL-UCB’s tighter confidence intervals when Bernoulli payoffs are low.The experiment uses n = 10^5 steps and averages results over 20 runs in Table 1.
  • 5.2. Worst-of-Best First Item Ordering: Reversing the item order reduces regret for both algorithms across all tested K, L, and Δ settings, especially for large K.The analysis does not explain this phenomenon and leaves it for future work.
  • 5.3. Imperfect Model: Under the DBN model, CascadeKL-UCB’s regret flattens in all experiments, indicating that it learns the DBN-optimal solution despite violated modeling assumptions.The setup varies satisfaction probabilities and user persistence, while using the last click as an indicator of user satisfaction.
  • 5.4. Ranked Bandits: RankedKL-UCB has about three times the regret of CascadeKL-UCB in the DBN comparison, although CascadeKL-UCB is not guaranteed to be optimal there.Both methods use KL-UCB as their base oracle, so the comparison is intended to reflect statistical efficiency rather than oracle choice.

6. Related Work

The paper relates cascading bandits to ranked bandits, stochastic combinatorial bandits, and partial-monitoring problems. Its distinguishing setting combines nonlinear rewards with feedback that reveals only a subset of recommended items.

  • Ranked bandits: Cascading bandits resemble ranked bandits but can learn the optimal list, whereas ranked-bandit solutions are (1 − 1/e) approximate with regret Ω(K).Ranked bandits treat each list position as an independent bandit problem; cascading bandits model independently attracting recommended items.
  • Stochastic combinatorial bandits: Unlike stochastic combinatorial semi-bandits, cascading bandits use a nonlinear reward function and observe only a subset of recommended items.The learning objective is to identify K most attractive items out of L.
  • Partial monitoring: Finite partial-monitoring algorithms apply conceptually, but the cited general algorithm is computationally inefficient here and lacks logarithmic distribution-dependent regret bounds.Its inefficiency comes from reasoning over all action pairs and storing vectors of length 2^L.
  • Related partial-monitoring settings: Other partial-monitoring work differs because it assumes state observations or feedback that is linear in item weights, unlike the nonlinear feedback in cascading bandits.The cited comparisons include Agrawal et al. and Lin et al.; other work studies observing supersets of chosen items.

7. Conclusions

The paper concludes that cascading bandits can be analyzed and solved effectively, but the framework has important scalability and modeling boundaries. It also identifies open theoretical and modeling extensions.

  • 7. Conclusions: The paper proposes a learning variant of the cascade model and evaluates two algorithms, CascadeUCB1 and CascadeKL-UCB, under nonlinear rewards and limited feedback.The algorithms perform well on several problems even when the modeling assumptions are violated.
  • 7. Conclusions: The framework is not practical when the number of items L is large because cascading-bandit regret is Ω(L).The authors propose embedding items in a feature space as a possible way to address this issue.
  • 7. Conclusions: The analysis leaves open closing the gap between upper and lower regret bounds, deriving gap-free bounds, and explaining why reverse item ordering yields smaller regret.These are identified as theoretical directions for future work.

A.1. Proof of Theorem 2

The proof of Theorem 2 decomposes CascadeUCB1 regret into confidence-failure and regular terms, then bounds suboptimal-item selections using event counting and decreasing gaps.

  • A.1. Proof of Theorem 2: CascadeUCB1 regret is decomposed according to whether empirical attraction probabilities remain inside their high-probability confidence intervals.The complement event is handled using conditional expectations and the tower rule.
  • A.1. Proof of Theorem 2: The confidence-failure contribution is controlled with Hoeffding’s inequality, while the remaining terms are bounded using a lemma from Kveton et al. (2014a).The cited bound contributes 12 ∆e,K log n before the final summation over suboptimal items.
  • A.1. Proof of Theorem 2: When confidence intervals hold, a suboptimal item can contribute regret only under an event linking it to an optimal item.The proof uses the ordering of upper confidence bounds to control such events.
  • A.1. Proof of Theorem 2: Each event Ge,e∗,t increases the counter of item e, occurs for at most one optimal item at time t, and is bounded by τe,e∗.The monotonicity τe,1 ≤ ... ≤ τe,K yields a bound by τe,K after summing over optimal items.
  • A.1. Proof of Theorem 2: Because the gaps decrease across optimal items, the associated optimization has solution m∗e,K = τe,K − τe,K−1.This converts the event-counting expression into the final upper-bound form.

A.2. Proof of Theorem 3

The proof of Theorem 3 applies a KL-UCB confidence analysis, controls the number of suboptimal selections through divergence-based thresholds, and removes an extra factor of K with a new peeling argument.

  • A.2. Proof of Theorem 3: CascadeKL-UCB regret is decomposed according to whether an optimal item’s attraction probability exceeds its upper confidence bound.The complement event is used for the regular part of the analysis.
  • A.2. Proof of Theorem 3: For each suboptimal item e and optimal item e∗, the selection threshold scales with (log n + 3 log log n) divided by DKL(¯w(e) ∥ ¯w(e∗)).An ε adjustment appears in the threshold expression.
  • A.2. Proof of Theorem 3: The proof bounds the remaining regret by summing divergence-based contributions over suboptimal items and optimal-item comparisons.The argument invokes the same structure as Theorem 2 together with Lemma 8 of Garivier and Cappe (2011).

B. Technical Lemmas

The technical lemmas establish list-comparison identities and divergence bounds used to control the regret analyses. The final bound is obtained by combining these inequalities.

  • B. Technical Lemmas: Lemma 1 compares two lists of K items under a factored item-weight distribution.Its proof proceeds by induction on K and factors expectations using the distributional assumption.
  • B. Technical Lemmas: Lemma 2 considers ordered probabilities p1 ≥ ... ≥ pK > p and gaps ∆k = pk − p.It bounds a gap-weighted sum involving KL divergences.
  • B. Technical Lemmas: The proof of Lemma 2 replaces a decreasing summation involving 1/DKL(p ∥ p + x) with a definite integral.Because the integral lacks a simple analytic solution, the proof integrates an upper bound instead.
  • B. Technical Lemmas: The resulting divergence-based expression includes a term proportional to ∆K DKL(p ∥ pK) log(1/∆K).The proof then chains the inequalities to obtain the final result.
Loading 1502.02763v2…