Contextual Bandits in Production

Contextual Bandit Workflow

  1. User Arrives ──► Observe Context Vector x_t (Age=25, Device=iOS, Location=NYC, Time=Evening)
                            │
                            ▼
               [ CONTEXTUAL BANDIT MODEL (LinUCB) ]
               Evaluates predicted reward + uncertainty for all candidate Arms:
               - Arm 1 (Sports Ad):   Predicted CTR = 0.02, Bonus = 0.01 ──► Bound = 0.03
               - Arm 2 (Tech News):   Predicted CTR = 0.12, Bonus = 0.04 ──► Bound = 0.16 (WINNER!)
                            │
                            ▼
  2. Serve Tech News ──► 3. Observe Click Feedback r_t ∈ {0, 1} ──► 4. Update Arm 2 Ridge Model!

The LinUCB Algorithm (Li et al., 2010 - Yahoo! News)

Assume linear relationship between context $x_{t,a} \in \mathbb{R}^d$ and expected reward:

$$\mathbb{E}[r_{t,a} \mid x_{t,a}] = x_{t,a}^T \theta_a^*$$

For each arm $a$, maintain:

• $A_a = D_a^T D_a + I_d$ ($d \times d$ covariance matrix).
• $b_a = D_a^T c_a$ ($d \times 1$ response vector).

Estimated Ridge Parameters:

$$\hat{\theta}_a = A_a^{-1} b_a$$

Action Selection Rule:

$$a_t = \arg\max_{a \in A} \left[ x_{t,a}^T \hat{\theta}_a + \alpha \sqrt{x_{t,a}^T A_a^{-1} x_{t,a}} \right]$$

• $x_{t,a}^T \hat{\theta}_a$: Predicted expected CTR.
• $\alpha \sqrt{x_{t,a}^T A_a^{-1} x_{t,a}}$: Standard deviation confidence bound in context space.

Industrial Production Applications

• Yahoo! / MSN News Personalization: Selects articles for incoming visitors based on user demographic context.
• Netflix Artwork Selection: Selects movie thumbnail images tailored to individual user viewing history context.
• Dynamic Push Notifications: Decides optimal send time and message copy per user.

Say this out loud

"Contextual Bandits observe user context vectors x_t before taking action a_t to serve personalized recommendations. Algorithms like LinUCB fit linear models per arm, selecting arms using upper bounds x^T θ + α √(x^T A^-1 x). Contextual Bandits are 100x more sample-efficient than full RL for e-commerce because session clicks do not alter future user demographic states."

Follow-ups to expect

• What is Off-Policy Evaluation (OPE) for Contextual Bandits? Evaluating a new contextual bandit policy using historical interaction logs collected by an older policy, using Inverse Propensity Scoring (IPS): $V_{\text{IPS}}(\pi_{\text{new}}) = \frac{1}{N} \sum \frac{\pi_{\text{new}}(a_i \mid x_i)}{\pi_{\text{old}}(a_i \mid x_i)} r_i$.
• How do Neural Contextual Bandits work? Replaces linear models $x^T \theta_a$ with a shared Deep Neural Network backbone + arm-specific heads, using Neural Tangent Kernel (NTK) approximations for uncertainty bounds.