LinUCB In Depth

Ridge regression reward model, confidence ellipsoid, disjoint vs hybrid, Sherman-Morrison

LinUCB is contextual bandit theory turned into a deployable algorithm. The core insight is geometric: to know how uncertain you are about the reward at a given context x, you need to know how far x is from the contexts you have actually observed. If x is in a direction where you have abundant observations (span of historical contexts), your estimate is confident. If x is in an under-observed direction, your estimate is uncertain and you should explore. The term x^T A^{-1} x captures exactly this: A = X^T X + λI accumulates the information you have observed, and x^T A^{-1} x is large for contexts in the null space of observed data.

This gives exact O(d√T) regret guarantees with efficient O(d²) online updates via Sherman-Morrison. The Yahoo! news paper found the theory-suggested α was 25× too large — always tune α empirically, never use the theoretical constant.

Key points

• Ridge regression for reward: θ̂_a = A_a^{-1} b_a where A_a = Σ x_i x_i^T + λI and b_a = Σ r_i x_i. The λI regularisation ensures A_a is invertible even with few observations (no data collapse) and acts as an isotropic Gaussian prior θ ~ N(0, I/λ). Without it, early rounds with few observations per arm produce degenerate, numerically unstable solutions.
• Confidence ellipsoid: under the linear model r_t = θ_a^T x_t + ε_t with subgaussian noise, the true θ_a lies in the ellipsoid {θ : (θ − θ̂_a)^T A_a (θ − θ̂_a) ≤ β} with high probability. The UCB for context x is the maximum of θ^T x over this ellipsoid: θ̂_a^T x + α√(x^T A_a^{-1} x). The term x^T A_a^{-1} x is the width of the ellipsoid projected onto direction x — how much the estimated reward could plausibly differ from the predicted value.
• Geometric intuition for x^T A^{-1} x: A_a = X_a^T X_a + λI accumulates the information from all observed contexts. Directions in R^d well-covered by historical observations have large eigenvalues in A_a, which correspond to small eigenvalues in A_a^{-1} — the UCB bonus is small there. Directions under-observed have small A_a eigenvalues and large A_a^{-1} eigenvalues — the UCB bonus is large. Exploration is targeted at the directions in context space where you lack data.
• Confidence parameter α: theory gives α = O(σ√(d ln T)) ≈ 5 for Yahoo! news parameters. The empirically optimal α was 0.2 — 25× smaller. Theory is conservative: it guarantees coverage for all possible θ and all reward realisations, including adversarial worst cases. Actual estimation error is much smaller. Always tune α on held-out OPE data in the range [0.1, 1.0] rather than using the theoretical value.
• Disjoint model: separate (A_a, b_a, θ̂_a) per arm, no information sharing across arms. The exploration bonus is arm-specific — an arm with few observations has high uncertainty for all contexts. Works best when arms have genuinely different response patterns to the same features. Storage: K × d² floats for A_a^{-1}; with K=100, d=50, that's 250K floats — feasible.
• Hybrid model: reward = β^T z_t + θ_a^T x_t where z_t are shared features (e.g., user features) and x_t are arm-specific features (e.g., ad content features). β is shared across all arms, enabling information sharing. More sample-efficient when arms share response patterns to shared features. Harder to implement — requires joint statistics and more complex updates.
• Sherman-Morrison online update: after one new observation (x, r), A_a_new = A_a + x x^T. Naive recomputation of A_a^{-1} costs O(d³). Sherman-Morrison: (A + xx^T)^{-1} = A^{-1} − (A^{-1} x x^T A^{-1}) / (1 + x^T A^{-1} x). Cost: O(d²) — two matrix-vector products. At d=100 and 10,000 QPS, this is 10^8 FLOPs/second — feasible on one core. This enables real-time updates without full matrix inversion.
• Reward model misspecification: if the true reward is nonlinear (f(x) = sin(x^T θ)) but LinUCB uses a linear model, the confidence ellipsoid no longer contains the true parameter. The algorithm may be systematically over-confident in directions where the linear approximation is wrong. Detection: monitor reward model residuals on held-out data. Large systematic residuals (not random noise) indicate misspecification — switch to NeuralTS or add polynomial/interaction features.
• Covariate shift breaks the calibration: A_a was built on historical contexts. If the current context distribution differs from historical (new user demographics, seasonal shifts), x^T A_a^{-1} x may be small — the new context looks "in-distribution" for old data but is genuinely novel. The UCB is under-calibrated. Fix: periodic reset of A_a with a forgetting factor, or use only recent observations to compute A_a.

Recap

• Ridge regression reward: $θ̂_a = A_a^{-1} b_a$, A_a = Σ x_i x_i^T + λI; λI keeps A_a invertible (Gaussian prior).
• Confidence ellipsoid → index: θ̂_a^T x + α√(x^T A_a^{-1} x); the bonus is the ellipsoid width projected onto x.
• x^T A^{-1} x = geometric uncertainty: large in under-observed directions of context space, small where data is abundant.
• Tune α empirically: Yahoo! news optimal α=0.2 was 25× below the theoretical ≈5 — worst-case constants aren't production constants.
• Disjoint vs hybrid: per-arm (A_a, b_a) with no sharing vs shared β^T z + θ_a^T x for sample efficiency.
• Sherman-Morrison: O(d²) online update instead of O(d³) inversion — feasible at 10K QPS on one core.
• Watch failures: nonlinear reward breaks the ellipsoid (monitor residuals); covariate shift under-calibrates the bonus (forgetting factor).

Check your understanding