LinUCB

LinUCB is a contextual multi-armed bandit algorithm introduced by Lihong Li, Wei Chu, John Langford, and Robert E. Schapire (Yahoo Research) in their 2010 WWW paper “A Contextual-Bandit Approach to Personalized News Article Recommendation”. The algorithm extends the classic UCB1 bandit to the contextual setting, where each round the agent observes a context vector (per-request features such as user demographics, time of day, geographic location) before choosing an arm, and where each arm’s reward is modeled as a linear function of the context plus noise. The algorithm uses Ridge regression to estimate each arm’s reward function and pulls the arm with the highest upper confidence bound on its expected reward given the current context. LinUCB was deployed at Yahoo for personalized news recommendation, where it produced a 12.5% click-through-rate lift over a context-free bandit baseline. The algorithm is the canonical reference for contextual bandits in recommendation and remains widely deployed in production cold-start handling and personalized exploration.

1. The Contextual Bandit Setting

The classic MAB problem assumes each arm has a single unknown reward distribution. In recommendation, this is too coarse — the same item may have very different click probabilities for different users. The contextual bandit extension addresses this:

At each round t:

1. The environment reveals a context vector x_t ∈ ℝ^d (e.g., features of the user making the request).
2. The agent chooses an arm a_t ∈ {1, ..., K} (e.g., which article to display).
3. The agent observes a reward r_t ∈ ℝ drawn from a distribution depending on both the context and the chosen arm.

The agent’s goal is to maximize cumulative reward, equivalent to minimizing contextual regret: Σ_t [ r*(x_t) − r_{a_t}(x_t) ] where r*(x_t) is the reward of the optimal arm for context x_t.

LinUCB makes a parametric assumption: each arm’s expected reward is a linear function of the context.

2. The Linear Reward Model

For each arm a, assume the expected reward given context x is:

E[r | x, a] = θ_aᵀ · x

where θ_a ∈ ℝ^d is an unknown weight vector specific to arm a. The arms have different weight vectors so that different contexts favor different arms — this is what enables personalization.

This assumption is restrictive (the true reward function may be non-linear), but it is what enables tractable analysis and efficient algorithms. In practice, the linear assumption is often a reasonable approximation, especially when the context features are themselves the outputs of a more sophisticated upstream model (e.g., a deep network’s user embedding).

3. The Algorithm

LinUCB maintains, for each arm a, a Ridge-regression-style estimator of θ_a:

A_a = I_d  (initialize d × d matrix to identity)
b_a = 0    (initialize d-vector)

At each round t with observed context x_t:

1. For each arm a:
   • Compute the estimated weight: θ̂_a = A_a^{-1} · b_a.
   • Compute the upper confidence bound: UCB_a(x_t) = θ̂_aᵀ · x_t + α · √( x_tᵀ · A_a^{-1} · x_t ).
2. Pull the arm a_t = argmax_a UCB_a(x_t).
3. Observe the reward r_t.
4. Update arm a_t’s estimator:
   • A_{a_t} ← A_{a_t} + x_t · x_tᵀ
   • b_{a_t} ← b_{a_t} + r_t · x_t

Where:

• α > 0 is a tunable exploration parameter. Larger α means more aggressive exploration.
• θ̂_aᵀ · x_t is the predicted mean reward.
• √(x_tᵀ · A_a^{-1} · x_t) is the standard deviation of the prediction (from Ridge regression’s posterior covariance) — an estimate of the prediction uncertainty.
• The UCB combines mean prediction with uncertainty: arms with high predicted mean or high uncertainty get pulled.

The matrix update A_a ← A_a + x_t · x_tᵀ is a rank-1 update; if x_t is sparse, the inverse A_a^{-1} can be updated efficiently via the Sherman-Morrison formula.

4. The Hybrid Variant

The 2010 paper also presents hybrid LinUCB, where some arm parameters are shared across arms (capturing context features that have similar effects across arms) and others are arm-specific. This addresses a limitation of disjoint LinUCB: arms with little training data have high-variance estimates because they share no parameters with other arms.

The hybrid model:

E[r | x, a] = θ_aᵀ · x  +  βᵀ · z(x, a)

where θ_a is arm-specific (as before) and β is shared across arms, applied to a feature vector z(x, a) that combines context and arm features. The shared β is updated using all observations across all arms; the disjoint θ_a is updated only on observations from arm a.

Hybrid LinUCB substantially outperforms disjoint LinUCB on Yahoo’s news data, particularly for arms with little training data — a cold-arm benefit.

5. The Yahoo Deployment

The 2010 paper applied LinUCB to Yahoo’s Front Page news recommendation: candidates were news articles, contexts were user features (demographics, recent activity, etc.), reward was binary click. The dataset comprised 33 million events over a roughly 10-day period.

Results:

• LinUCB achieved a 12.5% click-through-rate lift over a context-free bandit baseline.
• Hybrid LinUCB outperformed disjoint LinUCB.
• The advantage of contextual modeling grows with data scarcity (small training sets benefit more from context-aware exploration).

The paper also addressed a key methodological challenge: how to evaluate bandit algorithms offline without re-running them in production. The proposed solution — replay-based evaluation on randomized exploration logs — became the standard offline-evaluation methodology for contextual bandits.

6. When to Use LinUCB

LinUCB is appropriate when:

• You have per-request features (context) that affect reward.
• The reward function is approximately linear in the context (or you have a feature engineering pipeline that produces well-calibrated features).
• You can afford the per-arm matrix updates and inversions.
• Exploration is a primary need (cold start, popularity-bias breaking).

Do not use LinUCB when:

• The reward function is highly non-linear — use neural-network-based contextual bandits (deep contextual bandits).
• The arm set is too large (e.g., all items in a million-item catalog) — use a hierarchical or clustered approach, or restrict bandits to a reduced candidate set.
• You need offline batch training — bandits are an online learning paradigm.

7. Strengths

• Provable regret bounds under the linear assumption.
• Production-proven at Yahoo and many subsequent deployments.
• Efficient updates via rank-1 matrix updates.
• Standard offline evaluation methodology via replay (also from this paper).

8. Weaknesses

• Linear assumption may not hold in practice for complex reward surfaces.
• Per-arm matrix storage scales linearly with arm count and quadratically with feature dimension.
• Tuning of α requires care.
• Cold-arm problem partially solved by hybrid variant, not eliminated.

9. See Also

• Multi-Armed Bandit Algorithms — non-contextual MAB foundations
• Cold Start Problem — exploration is a primary cold-start strategy
• Beyond-Accuracy Objectives — bandits are one approach to breaking popularity bias
• Recommender Algorithms Catalog
• Recommender Systems