LinUCB

LinUCB assumes the expected reward for an action is a linear function of the context vector. For a given arm a with unknown coefficient vector θₐ, the predicted reward is xᵀθₐ. This linearity enables closed-form ridge regression updates, avoiding iterative gradient descent and making the algorithm highly sample-efficient when the assumption holds. The model maintains a design matrix Aₐ and a response vector bₐ for each arm, updated incrementally with each observation.

At each decision step, LinUCB selects the arm that maximizes xᵀθ̂ₐ + α√(xᵀAₐ⁻¹x). The first term is the estimated reward, while the second is the exploration bonus proportional to the standard deviation of the estimate. The hyperparameter α (alpha) controls the exploration-exploitation trade-off:

• Higher α: more exploration, wider confidence intervals
• Lower α: more exploitation, greedier selections This bonus shrinks as more data is collected for an arm, naturally reducing exploration over time.

Unlike neural bandits that require backpropagation, LinUCB updates parameters analytically using Ridge Regression. After observing reward r for action a with context x:

• Aₐ ← Aₐ + xxᵀ (outer product update)
• bₐ ← bₐ + rx (reward-weighted context)
• θ̂ₐ ← Aₐ⁻¹bₐ (solved via matrix inversion) This O(d²) per-update complexity, where d is the feature dimension, makes LinUCB suitable for moderate-dimensional problems with strict latency budgets.

Two primary LinUCB variants exist:

• Disjoint LinUCB: Each arm maintains its own independent parameter vector θₐ. Best when arms are heterogeneous with little shared structure.
• Hybrid LinUCB: Combines arm-specific parameters with a shared parameter vector capturing common patterns across all arms. This is advantageous when arms share underlying dynamics, such as items in the same product category. The hybrid model introduces a shared feature matrix and additional hyperparameters, trading increased computational cost for improved generalization across arms.

LinUCB provides a sublinear regret bound of O(d√(T log(T))) under the linear realizability assumption, where d is the feature dimension and T is the time horizon. This means the average regret per step approaches zero as T grows large. The bound depends critically on:

• The condition number of the design matrices
• The boundedness of contexts and rewards
• The correct specification of the ridge penalty Violations of the linearity assumption can lead to linear regret, motivating the use of kernelized or neural extensions.

In production personalization systems, LinUCB requires careful engineering:

• Feature normalization: Context vectors must be scaled to prevent numerical instability in matrix inversion.
• Regularization strength: The ridge penalty λ prevents singular matrices during cold-start; typical values range from 0.1 to 1.0.
• Matrix inversion: Use the Sherman-Morrison formula for efficient rank-1 updates instead of full matrix inversion on each step.
• Model staleness: In non-stationary environments, implement a forgetting factor or sliding window to discount old observations.

LinUCB inherits its core selection strategy directly from the Upper Confidence Bound principle. The algorithm selects the arm that maximizes the sum of the predicted reward and an exploration bonus. This bonus is proportional to the standard deviation of the model's uncertainty for that specific arm, given the context. The 'UCB' in LinUCB refers to this exact mechanism, which provides a deterministic, analytically derived alternative to the probabilistic exploration of Thompson Sampling.

LinUCB operates on a d-dimensional real-valued vector representing the current user, session, or item. This is the 'Contextual' part of the algorithm. The expected reward is modeled as a linear function of this vector. Feature engineering is critical here; the vector might include:

• User features: historical click-through rate, segment ID
• Action features: product price, category embedding
• Joint features: interaction terms between user and action The linearity assumption makes the model computationally efficient but requires features that capture meaningful linear relationships.

Under the hood, LinUCB solves a regularized least-squares problem for each arm independently. It maintains a design matrix and an inverse covariance matrix to estimate the weight vector. The algorithm uses the Sherman-Morrison formula to perform rank-1 updates to the inverse matrix in O(d²) time per observation, avoiding a full O(d³) matrix inversion. This closed-form Bayesian linear regression with L2 regularization provides both the point estimate of the reward and the exact posterior variance used in the UCB calculation.

Two primary architectural variants exist for modeling shared structure:

• Disjoint LinUCB: Learns a completely separate linear model for each arm. The parameters for arm A are independent of arm B. This is simpler but fails to share information between arms with similar characteristics.
• Hybrid LinUCB: Introduces a shared, latent feature matrix across all arms, combining it with arm-specific parameters. This allows the algorithm to generalize learning about one product to similar products, dramatically improving performance in large action spaces with sparse feedback.

The theoretical performance of LinUCB is measured by its cumulative regret, defined as the difference between the total reward of an optimal oracle policy and the reward accumulated by the algorithm. LinUCB achieves a regret bound of Õ(√T) under linear realizability assumptions, where T is the number of rounds. This sub-linear regret means the average per-round regret tends to zero over time, proving the algorithm learns the optimal policy. The exploration bonus parameter α directly controls the regret bound's constant factor.

Before deploying a LinUCB policy live, it must be safely evaluated on historical data. Off-policy evaluation techniques like Inverse Propensity Scoring (IPS) re-weight the observed rewards by the inverse probability of the logging policy's action. For LinUCB, this means computing the probability the old policy would have taken the same action, then using that to unbias the reward signal. The Doubly Robust Estimator further combines IPS with a direct reward model to reduce variance, providing a reliable estimate of LinUCB's potential business impact without risking user experience.