Contextual Bandit

A Contextual Bandit extends MAB with an observable context feature $x_t \in \mathbb{R}^d$ per round; the policy $\pi(x)$ picks an action given features, maximizing the conditional expected reward $\mathbb{E}[r \mid x, a]$. The representative algorithm LinUCB assumes a linear reward model $r_{t,a} = \theta_a^T x_{t,a} + \epsilon$, estimates per-arm parameters by ridge regression $\hat{\theta}_a = (X_a^T X_a + \lambda I)^{-1} X_a^T y_a$ ($X_a$/$y_a$: arm $a$'s historical feature matrix and reward vector, $\lambda I$ the regularizer), builds the confidence bound $p_{t,a} = \hat{\theta}_a^T x_{t,a} + \alpha \sqrt{x_{t,a}^T (X_a^T X_a + \lambda I)^{-1} x_{t,a}}$, and plays the arm with the largest upper bound.

personalized recommendation (user + item features), ad bidding, dynamic pricing, feed ranking; interviews connect it to RecSys — context is feature engineering and the model is an online reward predictor.

context-free MAB treats all users identically, with weak personalization and cold-start; contextual bandits share samples across contexts via features, speeding up cold-start and lifting reward, occupying a pragmatic middle ground between pure exploration and full RL/supervised learning — needing only live feedback, no offline datasets or simulators.

Write LinUCB's ridge solution and confidence term; explain $(X_a^T X_a + \lambda I)^{-1}$ and the role of $\lambda I$?

Compute the cost of estimating $\hat{\theta}_a$ in $d$ dimensions; why does the inverse covariance shrink as samples accumulate?

Fundamental differences among contextual bandits, full RL, and supervised (offline) ML?

How do you construct context features for recsys, and how do contextual bandits mitigate cold-start?

LinUCB vs online logistic regression/GBDT: what if linearity fails (kernel / neural contextual bandits)?