Cascading Bandits for Large-Scale Recommendation Problems

• Users scan recommended items in order and typically click the first attractive item, leaving later items unexamined.Under the cascade model’s independence assumption, the best list contains the K most attractive items.Source: §1 · p. 1
• Cascading bandits learn user preferences through interaction, choosing K items from L candidates to maximize cumulative clicks.The agent receives a reward of one for a click and zero when no item is clicked.Source: §1 · p. 1
• CascadeUCB1’s regret grows linearly with candidate-set size L, making it impractical for large catalogs.The paper identifies feature-based prediction of attraction probabilities as a way to address this scaling challenge.Source: §1 · pp. 1–2
• Linear cascading bandits assume item attraction probabilities are linear functions of item features and introduce CascadeLinTS and CascadeLinUCB.The paper derives a regret upper bound for CascadeLinUCB and argues a similar bound should hold for CascadeLinTS.Source: §1 · p. 2
• The paper evaluates CascadeLinTS on restaurant, music, and movie recommendations, reporting good performance even when modeling assumptions are violated.The authors describe the work as the first top-K bandit study with cascading feedback and context.Source: §1 · p. 2

2.1 Cascade Model

• Under the cascade model, users examine a list sequentially and stop at the first attractive item; the probability of an item being examined depends on the preceding items.The probability that at least one item attracts the user is maximized by choosing the K most attractive items.Source: §2.1 · p. 2

2.2 Cascading Bandits

• A cascading bandit learns item preferences by recommending K items from L candidates and observing the first-click outcome or no click.The reward is one if at least one recommended item is attractive and zero otherwise; only items examined before the click are observed.Source: §2.2 · pp. 2–3
• The learning objective is to maximize cumulative reward, measured through regret against the optimal list under the model’s assumptions.The exposition assumes the optimal solution, as a set, is unique.Source: §2.2 · p. 3

2.3 Algorithm CascadeUCB1

• CascadeUCB1 computes itemwise upper confidence bounds, recommends the K items with largest bounds, and updates estimates from observed weights.Its confidence intervals use observed attraction averages and counts to bound each item’s attraction probability.Source: §2.3 · p. 3

3 LINEAR CASCADING BANDITS

• CascadeUCB1 regret grows linearly with L, making it impractical for large catalogs; for 100k movies and K = 10, it needs at least 10k interactions to start behaving intelligently.The proposed linear model assumes attraction probabilities can be approximated by a shared parameter applied to item features.Source: §3 · p. 3

3.1 Algorithms

• The algorithms estimate item attraction from shared features, then select a list using those estimates and update statistics from user feedback.CascadeLinTS samples a parameter vector from an approximate posterior; CascadeLinUCB uses an upper confidence bound.Source: §3 · p. 3, §3.1 · p. 4

3.2 Analysis and Discussion

• With perfect linear generalization, CascadeLinUCB has regret independent of L and sublinear in n, assuming item feature vectors have norm at most 1.The feature-norm condition can be ensured by rescaling feature vectors.Source: §3 · p. 3, §3.2 · p. 4
• CascadeLinTS has no formal regret analysis: its Gaussian posterior conflicts with bounded attraction probabilities, and partial monitoring complicates frequentist analysis.The authors therefore leave its formal analysis for future work and evaluate CascadeLinTS empirically.Source: §3.2 · p. 5

4.2 Metrics and Baselines

• The experiments compare CascadeLinTS with CascadeUCB1, which learns item attractions independently, and RankedLinTS, which uses the same LinTS base algorithm.The expected cumulative regret uses a greedy (1 − 1/e) approximation to the optimal list because finding that list is NP-hard.Source: §4.2 · p. 6

4.3 Features

• Item features are learned by applying rank-d truncated SVD to the training feedback matrix, and algorithms are evaluated on the held-out test matrix.The item feature vectors are rows of VΣ.Source: §4.3 · p. 6

4.4 Restaurant Recommendations

• The tasks infer attraction from prior restaurant reviews, song listens, and movie ratings above 3/5; objectives are at least one attractive restaurant or movie, and an attractive recommended song that is played.Source: §4.4 · p. 6, §4.5 · p. 7, §4.6 · p. 8

4.4.1 Results

• Across restaurant, song, and movie tasks, CascadeUCB1’s regret becomes orders of magnitude larger than CascadeLinTS’s as the item set grows; CascadeLinTS is similar to RankedLinTS on songs and lower on movies.For restaurants at L = 3k, RankedLinTS regret is almost three times CascadeLinTS regret.Source: Figure 1 · p. 7, §4.4.1 · p. 7, §4.5.1 · p. 8
• For restaurants, CascadeLinTS performs well across d settings: regret roughly doubles at d = 40 and is roughly halved at d = 10; it also learns across d on American Restaurants.The American Restaurants subset is the dataset’s largest restaurant category.Source: §4.4.1 · p. 7
• As K increases, CascadeLinTS regret rises even while learned-policy reward rises, which the authors attribute to faster growth in the optimal solution’s expected reward under model mismatch.The restaurant discussion specifically points to imperfect linear generalization and non-independent item attractions.Source: §4.4.1 · p. 7, Figure 2 · p. 8, §4.5.1 · p. 8

4.5.1 Results

• For songs, CascadeLinTS performs well across feature counts on the full dataset and Rock Songs, with lowest regret at d = 10 in both..Source: Figure 2 · p. 8, §4.5.1 · p. 8

4.6.1 Results

• For movies, CascadeLinTS performs well across feature counts on the full dataset and Adventures subset, with lowest regret at d = 20 in both.The supplied figure caption identifies panels 2a and 2b as the full-dataset and subset feature-count evaluations.Source: Figure 2 · p. 8, §4.6.1 · p. 9

Cascading bandits

• Unlike earlier cascading bandits, the paper assumes attraction weights are linear in known item features and an unknown parameter, yielding algorithms with regret sublinear in L.The paper compares CascadeLinTS with CascadeUCB1 in its experiments.Source: §5 · p. 9

Ranked bandits

• Ranked bandits model each recommendation position as an independent bandit, have (1 − 1/e)-approximate solutions, and incur regret linear in K, but do not assume independent item attractions.The paper compares CascadeLinTS with contextual ranked bandits using linear generalization.Source: §5 · p. 9

Partial monitoring

• General partial-monitoring algorithms may scale at least linearly with L, while one reward-observing method assumes a finite parameter set and cannot be applied here.The authors believe their algorithm and analysis may be relatively easily generalized to combinatorial action sets because the feedback model resembles Kveton et al.’s.Source: §5 · p. 9

Stochastic combinatorial bandits

• Compared with stochastic combinatorial bandits, this work has a nonlinear reward in unknown parameters and feedback that reveals less than semi-bandit feedback..Source: §5 · p. 9

6 CONCLUSIONS

• Linear cascading bandits model item attraction probabilities as a linear function of known features and an unknown learned parameter vector.The paper proposes CascadeLinTS and CascadeLinUCB as algorithms for this framework.Source: §6 · p. 9
• CascadeLinUCB has a regret bound, while the paper suggests a similar bound may be proved for CascadeLinTS.The paper evaluates CascadeLinTS on recommendation problems and reports orders-of-magnitude improvements over algorithms that do not use item features.Source: §6 · p. 9
• The analysis assumes independent item attraction and perfect linear generalization, both of which the authors say tend to be violated in practice.The current analysis cannot explain the observed behavior under those violations.Source: §6 · p. 9
• The cascade model allows at most one click, a limitation the authors identify as often violated in practice.They leave generalizing their results to a multiple-click setting for future work.Source: §6 · p. 9

A.1 Notations

• The notation includes a random permutation of the optimal set based on the recommended list, with remaining optimal items positioned arbitrarily.The passage introduces the permutation as (a*_{1,t}, ..., a*_{K,t}) of A* based on A_t.Source: §A.1 · p. 11
• H_t denotes the history by the end of time t; the recommended list and optimal-item permutation are determined by H_{t-1} at the start of time t.E_t[·] denotes expectation conditional on H_{t-1} when appropriate.Source: §A.1 · p. 11
• For vectors of the same dimension, the paper uses ⟨u, v⟩ to denote their inner product u^T v.Source: §A.1 · p. 11

A.2 Regret Decomposition

• The proof uses the law of total probability and bounds on probabilities and indicators to establish an intermediate inequality.Source: §A.2 · p. 12
• Under event E, the upper bound U_t(e) is at least the attraction probability w̄(e) for every item e and time t ≤ n.The passage uses this inequality in the subsequent bound.Source: §A.2 · p. 12
• The proof proceeds to establish a worst-case bound on P_n and a bound on P(Ē).Source: §A.2 · p. 12

A.3 Worst-Case Bound on Pn

• The worst-case P_n argument uses logarithms, strict concavity of h(y), and the Cauchy–Schwarz inequality.Source: §A.3 · pp. 13–14

A.4 Bound on P( ¯E)

• The complement-event analysis treats the noise terms as a bounded martingale-difference sequence and invokes a self-normalized bound for high-probability control.The resulting inequality is used to infer a condition for all times and items.Source: §A.4 · pp. 14–15

A.5 Conclude the Proof

• The proof combines the preceding bounds into a result stated for σ > 0, δ ∈ (0, 1), and nK.Source: §A.5 · p. 15