PaperlayerView exact revision on arXiv

Source-linked AI summary

On Context-Dependent Clustering of Bandits

Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglou, Evans Etrue, Giovanni Zappella

arXiv:1608.03544v2cs.LGcs.AIcs.IRstat.ML

TL;DR

Dynamic recommendation must balance exploration of new items with using accumulated preference information. CAB shares feedback through context-dependent user clusters; experiments report improved prediction performance over state-of-the-art contextual bandit methods, while its regret analysis depends on the expected number of clusters.

  • Problem

    Dynamic recommendation must balance exploring new items for preference information with exploiting accumulated user-item feedback, including collaborative effects.

    Source: §1 · p. 1

  • Method

    CAB uses context-dependent user clusters to share feedback between users who confidently agree on an item, incorporating collaborative effects into contextual bandit recommendations.

    Source: §1 · pp. 1–2, §3 · p. 4

  • Results

    CAB significantly outperforms state-of-the-art contextual bandit algorithms on production and real-world datasets, with benefits in the cold-start region and a continuing lead on the first three datasets.

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

  • Takeaways & Limitations

    The regret bound depends on the expected number of context-dependent clusters, which the paper identifies as a measure of the learning task's predictive difficulty.

    Source: §1 · p. 2

    Experimental validation of the sparse bandit version is still planned, and the paper reports no results for it.

    Source: §6 · p. 9

Abstract

from arXiv · show

We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating the neighborhood of users in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into inference as well as learning processes in a manner that seamlessly interleaving explore-exploit tradeoffs and collaborative steps. We prove regret bounds under various assumptions on the data, which exhibit a crisp dependence on the expected number of clusters over the users, a natural measure of the statistical difficulty of the learning task. Experiments on production and real-world datasets show that CAB offers significantly increased prediction performance against a representative pool of state-of-the-art methods.

1. Introduction

Dynamic recommendation must balance exploration of new content with exploitation of user-item preferences, including collaborative effects. CAB addresses this with item-specific user groupings and reports theoretical and empirical gains over contextual bandit approaches that omit or use context-independent clustering.

1. Introduction

  • Dynamic recommendation must explore new items while exploiting collected preferences, including collaborative effects across users and items.The challenge is especially relevant when new users and items arrive continuously.Source: §1 · p. 1
  • CAB is presented as a simple, flexible linear contextual bandit that incorporates collaborative effects ignored by traditional contextual bandit approaches.The introduction cites (Auer, 2002; Li et al., 2010; Chu et al., 2011; Abbasi-Yadkori et al., 2011) as examples.Source: §1 · p. 1
  • CAB groups users separately for each item, enabling feedback sharing among users who tend to react similarly to that content.The induced clusters are few relative to the total user population, and distinct items may induce distinct groupings.Source: §1 · p. 2
  • CAB’s regret analysis depends on the expected number of context-dependent user clusters, while experiments report significantly better prediction performance than contextual bandits without clustering or with context-independent clustering.The paper also gives a sharper regret bound under sparsity assumptions on user model vectors.Source: §1 · p. 2

1.1. Related Work

  • Earlier user-clustering approaches and social-information feedback-sharing methods group users in ways that are not context-dependent; Li et al. (2016) also requires a finite, advance-known content universe.CAB is contrasted as simple and flexible, including for adding or removing users.Source: §1.1 · p. 2

2. Notation and Preliminaries

The model represents each user's average payoff with an unknown linear vector and allows the user partition to vary with the item context. Its regret analysis aims to reflect the expected number of context-dependent clusters rather than the full user count.

2. Notation and Preliminaries

  • For context x, users are partitioned into clusters whose members behave similarly on x, with the number of clusters m(x) small relative to the total user count.The partition and within-cluster behavior are unknown to the learner and must be inferred from feedback.Source: §2 · p. 2
  • The context-dependent clusters are modeled through unknown user vectors, with a γ-gap assumption separating users in different clusters.The model assumes unit-norm user vectors; users in the same cluster have equal projected behavior on the context, while different clusters have projected behavior separated by at least γ.Source: §2 · p. 2
  • The payoff model treats the user-context response as linear with conditionally zero-mean sub-Gaussian noise and bounded payoffs.The noise variance parameter is bounded by σ^2, and payoffs lie in [−1, +1].Source: §2 · p. 3
  • At each round, the learner receives a user and available item contexts, recommends one item, and observes a payoff whose conditional expectation is that user’s vector dotted with the chosen context.The user-context sequence is generated by an exogenous process, and performance depends on its properties.Source: §2 · p. 3
  • The desired regret bound should improve with stronger context-dependent clustering, because collaboration is expected to help most when m(x) is small.Under suitable stochastic assumptions on the data, the analysis replaces dependence on n by E[m(x)], with expectation over contexts.Source: §2 · p. 3

3. The Context-Aware Bandit Algorithm

CAB uses an upper-confidence-bound approach to recommend items using estimated, item-specific user neighborhoods. It also shares feedback by updating other users’ proxies when confidence supports similar behavior on the selected item.

3. The Context-Aware Bandit Algorithm

  • CAB computes an estimated neighborhood for each candidate item, then uses aggregated confidence bounds and proxy vectors in an upper-confidence item-selection step.The algorithm initializes user-specific proxy and correlation estimates and receives the user and candidate contexts at each round.Source: §3 · pp. 3–4
  • CAB lifts user proxies and confidence bounds to a set of users by flat averaging their estimates.The resulting aggregates support item selection over the candidate set.Source: §3 · p. 4
  • After observing feedback, CAB updates other users’ proxies when the served user and those users are confidently estimated to agree on the selected item.If confidence is insufficient for the served user, only that user’s proxy is updated; otherwise, confident users in the estimated neighborhood receive the same update.Source: §3 · p. 4
  • CAB’s context-sensitive aggregation at every round allows users to be added or dropped on the fly.The paper contrasts this with approaches based on static network Laplacians or time-evolving connected components over a given user set.Source: §3 · p. 4

4. Regret Analysis

The regret analysis gives CAB a deterministic cumulative-regret bound whose dependence on the user population is tied to context-dependent neighborhoods. Favorable sampling assumptions control the bound’s hardness term, while unrestricted or adaptive data generation can make it uninformative.

4. Regret Analysis

  • Theorem 1 gives CAB a deterministic cumulative-regret bound under a γ-gap and uniform confidence-radius condition, replacing total-user dependence in its second term with the served users’ context-dependent neighborhood size.The bound also includes a data-sequence hardness term.Source: §4 · p. 5
  • Under Lemma 1’s i.i.d. context and uniform user-sampling assumptions, the hardness term admits a high-probability logarithmic-in-T bound.The assumptions also require bounded context vectors, full-rank context covariance, and the stated variance condition.Source: §4 · p. 5
  • When contexts are sampled favorably, the summed inverse neighborhood sizes can be related to the expected number of context-dependent user clusters.For the second term, the passage gives the special case of a constant neighborhood size B.Source: §4 · p. 5
  • With no assumptions whatsoever about how the pairs are generated, it is hard to exploit cluster structure; the passage gives generation by an adaptive adversary as an example.Source: §4 · p. 5
  • The linear dependence on c in the second-term bound can become logarithmic with an additional sub-Gaussian assumption on |N_i(x)|.Source: §4 · p. 5
  • For s-sparse user vectors with s ≪ d, replacing Step 4’s least-squares solution with a two-stage fully corrective method yields an improved regret bound.The passage says this improves the dimension-dependent term but does not provide its complete replacement expression.Source: §4 · p. 6

5. Experiments

Experiments compare CAB on production and real-world recommendation datasets against standard and state-of-the-art baselines. CAB leads on four of five datasets, with the size of its advantage varying across datasets.

5.1. Dataset Description

  • Evaluation spans three advertising datasets and two recommendation logs, with one-hot ad vectors and 25-component item contexts for LastFM and Delicious.The LastFM and Delicious item contexts were generated from tf-idf representations using the first 25 principal components.Source: §5 · p. 6, §5.1 · pp. 6–7

5.2. Algorithms

  • The authors tuned parameters on the first 20% of each dataset, evaluated on the remaining 80%, averaged results over five runs, and compared against bandit and clustering baselines.The comparison pool included CLUB, DynUCB, and shared-user and per-user LinUCB variants.Source: §5.2 · p. 7

5.3. Results

  • CAB outperformed all baselines on four of five datasets; on Tuenti it delivered almost double CTR versus some baselines and led throughout the ad datasets, including cold start.The ad datasets were Tuenti, KDD Cup, and Avazu.Source: Figure 1 · p. 7, §5.3 · p. 8
  • On LastFM CAB outperformed all methods, while on Delicious LinUCB-MULTIPLE was best, consistent with more separated user models on Delicious than LastFM.The authors report that Delicious models are more separated than LastFM models, which they say helps explain LinUCB-MULTIPLE’s effectiveness.Source: Figure 2 · p. 8, §5.3 · p. 8

6. Conclusions and Ongoing Research

The paper concludes that CAB offers flexible, context-dependent feedback sharing and regret bounds tied to expected cluster counts. It identifies preliminary Thompson Sampling tests, a missing lower bound, and planned sparse-model evaluation as ongoing work.

6. Conclusions and Ongoing Research

  • CAB incorporates collaborative effects through context-dependent feedback sharing and supports on-the-fly inclusion or exclusion of users.Its regret analysis depends on the expected number of context-dependent clusters, with improved bounds under sparse user models.Source: §6 · p. 9
  • The reported experiments compare CAB with available approaches on production and real-world datasets and show encouraging results.The conclusion describes the comparison as extensive but supplies no numeric performance summary in this passage.Source: §6 · p. 9
  • The authors have not yet established a lower bound to characterize regret complexity, and sparse CAB still needs experimental validation.They also report that Thompson Sampling comparisons remain preliminary and have shown no significant statistical difference so far.Source: §6 · p. 9

A. Proofs

The proof connects confidence-based neighborhood estimation and profile updates to regret bounds expressed through context-dependent cluster hardness.

A. Proofs

  • A γ-gap lemma relates estimated neighborhoods to true neighborhoods and identifies which users’ profiles are updated.Under the stated hypotheses, the update set coincides with the true neighborhood for the selected context.Source: A. Proofs · pp. 12–13
  • The regret argument bounds rounds with incorrect estimated neighborhoods through the hardness term HD({i_t, C_t}^T_{t=1}, η) and controls updates using confidence bounds.The proof links the number of profile updates to true neighborhood sizes when confidence bounds are sufficiently small.Source: A. Proofs · p. 13
  • For fixed context x, users partition into m(x) neighborhoods; concentration of neighborhood sizes relates the analysis to the expected cluster count.The proof uses a martingale difference sequence and concentration inequalities for the neighborhood-size quantity.Source: A. Proofs · p. 16

B. Extending CAB to Sparse User Models

spCAB adapts CAB to high-dimensional settings with sparse user models by replacing its least-squares proxy estimation with sparse recovery. Sparse models allow users to have different supports, and are relevant when only some features encode each user’s preferences or dense models are costly.

B. Extending CAB to Sparse User Models

  • Each user model has at most s* nonzero coordinates, and every nonzero coordinate has magnitude greater than π.Users may have different supports, but each is required to be s*-sparse.Source: B. Extending CAB to Sparse User Models · p. 16
  • Sparse models fit settings where only some features encode each user’s preferences, while dense regression may require O(d) trials per user.The passage notes that users typically interact sparsely with recommendation systems, making that trial requirement potentially prohibitive.Source: B. Extending CAB to Sparse User Models · p. 16
  • spCAB replaces CAB’s least-squares proxy estimation with sparse recovery to handle extremely high-dimensional features and sparse user models.The section identifies a two-stage fully corrective method as a suitable sparse-recovery approach for the ridge-regression objective.Source: B. Extending CAB to Sparse User Models · pp. 16–17

B.1. Regret Analysis for spCAB

The sparse-model analysis bounds spCAB’s regret under the requisite properties and yields weak dependence on ambient dimension. When item contexts lie in a low-dimensional space, the stated bound depends on d only logarithmically.

B.1. Regret Analysis for spCAB

  • The sparse-case proof uses sparse-recovery guarantees and martingale arguments, then establishes bounds on confidence and restricted eigenvalues.The passage relates the confidence-bound task to lower bounds on restricted eigenvalues, equivalent to RSC/RSS properties of the objective.Source: §B.1 · pp. 17–18
  • The analysis assumes restricted strong convexity and restricted strong smoothness conditions for the sparse-recovery objective.Theorem 2 specifies parameters for these conditions and requires the sparse-recovery algorithm’s stated parameter constraints.Source: §B.1 · pp. 17–18
  • In the sparse model case, the exploration parameter is much smaller than the dense-model parameter, which scales as √(d log t).The sparse-case passage gives α_sp(t) as scaling with s log T/δ and describes it as a stark improvement in exploration-parameter behavior.Source: §B.1 · p. 18
  • spCAB’s sparse-model regret bound has weak dependence on ambient dimension d, with the stated dependence involving d and log d.The theorem is stated for s*-sparse user models satisfying the requisite properties, with logarithmic factors hidden by the eO notation.Source: §B.1 · pp. 18–19
  • When item contexts are supported on a low r-dimensional space, the regret bound depends on d only through logarithmic terms.The passage states this bound applies without modifying spCAB.Source: §B.1 · p. 19
Loading 1608.03544v2…