Contextual and Linear Bandits

Summary

The general Thompson-sampling algorithm (Algorithm 4.2, Bernoulli Bandit and Thompson Sampling Algorithm) extends far past independent Bernoulli arms: rewards can be linear or logistic (generalized linear) functions of a parameter vector, actions can carry side information/context observed before each decision, and the parameter space can be a matrix (product assortment) rather than a vector. This note collects the tutorial’s three running non-trivial-structure examples — correlated shortest-path edges, contextual news-article recommendation, and assortment optimization — plus the general recipe for turning “time-varying constraints” and “side information” into a straightforward extension of TS.

Overview

The unifying move in all these extensions is the same: TS never needed $\mathcal{X}$ to be small or $\theta$ to be low-dimensional — it only needs (a) a posterior over $\theta$ that can be sampled or approximated, and (b) an ability to solve $\arg {\max }_x{\mathbb{E}}_{q_{\hat{\theta }}}[r(y_t)\mid x_t=x]$ for a given sampled $\hat{\theta }$. Linear/GLM structure buys efficient conjugate (or near-conjugate) posterior updates; context and constraints are absorbed by simply augmenting the action space per period.

Main Content

Correlated linear-Gaussian rewards (Example 4.2)

Extending the independent log-Gaussian edge-time model (Example 4.1, Bernoulli Bandit and Thompson Sampling Algorithm), suppose travel times share common shocks: $y_{t,e}={\zeta }_{t,e}{\eta }_t{\nu }_{t,\ell (e)}{\theta }_e$, where ${\eta }_t$ is a day-wide factor and ${\nu }_{t,0},{\nu }_{t,1}$ are factors shared within each half of the graph. Taking logs, ${\varphi }_e=\ln ({\theta }_e)$ is jointly Gaussian with mean $\mu$ and covariance $\Sigma \in {\mathbb{R}}^{N\times N}$, updated in closed form via

$$(\mu ,\Sigma )\leftarrow (({\Sigma }^{-1}+\tilde{C}{)}^{-1}({\Sigma }^{-1}\mu +\tilde{C}{z}_t),({\Sigma }^{-1}+\tilde{C}{)}^{-1})$$

for an edge-wise “information” contribution $\tilde{C}$ built from the observed edges’ precision. TS samples $\hat{\varphi }\sim N(\mu ,\Sigma )$, exponentiates to get ${\hat{\theta }}_e=e^{{\hat{\varphi }}_e}$, and solves the deterministic shortest-path problem as before.

Coherent vs. misspecified TS (Fig. 4.3)

“Coherent TS” models the true edge-correlation structure above; “misspecified TS” pretends edges are independent (as in Example 4.1) despite the correlated data-generating process. Coherent TS substantially outperforms misspecified TS in both regret and cumulative-travel-time-vs.-optimal — a direct demonstration that correctly modeling dependencies among actions (not just marginal per-action uncertainty) materially accelerates learning, exactly the lesson CascadeTS also relies on (see UCB and Greedy Algorithms for Bandits).

Contextual bandits: side information before each decision (§6.2)

Contextual online decision problem

Before choosing $x_t$, the agent observes an independent random context $z_t$, and the outcome distribution becomes $p_{\theta }(\cdot \mid x_t,z_t)$. This is handled without any new algorithm by augmenting the action to ${\tilde{x}}_t=(x_t,z_t)$ and constraining its choice to ${\mathcal{X}}_t=\{(x,z_t):x\in \mathcal{X}\}$ — a time-varying constraint set — after which ordinary TS (Algorithm 4.2 of Bernoulli Bandit and Thompson Sampling Algorithm) applies unchanged to ${\tilde{x}}_1,{\tilde{x}}_2,\dots$.

News article recommendation (§7.1)

Logit contextual bandit for personalized recommendation (Li et al. 2010; Chapelle & Li 2011)

At each round $t$, the website observes a user feature vector $z_t\in {\mathbb{R}}^d$, chooses an article $x_t$ from $\{1,\dots ,k\}$, and observes a binary “liked” reward. Each article $x$ has parameter ${\theta }_x\in {\mathbb{R}}^d$; conditional on $(x_t,{\theta }_{x_t},z_t)$, a positive review occurs with probability $g(z_t^{\top }{\theta }_{x_t})$ for logistic function $g(a)=1/(1+e^{-a})$ — a generalized linear model per article. Per-period regret is ${\mathrm{regret}}_t={\max }_{x}g(z_t^{\top }{\theta }_x)-g(z_t^{\top }{\theta }_{x_t})$.

Because the logit link breaks Gaussian conjugacy, exact posterior updates are intractable; the tutorial applies the Laplace approximation and Langevin Monte Carlo approximate-sampling schemes of Approximate Thompson Sampling and Practical Extensions and finds both substantially outperform tuned $ϵ$-greedy (Fig. 7.1). Two generalization limitations are noted: (1) as written, ${\theta }_x$ must be estimated separately per article, with no transfer learning across articles — fixed by instead using a feature vector $z_{t,x}$ that encodes user–article interactions with a single shared $\theta$, enabling learning about one article to inform others; (2) the article set $\mathcal{X}$ was assumed time-invariant, whereas real news sites continually retire/add articles — still a contextual bandit, just with a time-varying ${\mathcal{X}}_t$ as in §6.2 above.

Product assortment optimization (§7.2)

Assortment planning with substitute/complement effects

$n$ products, profit $p_i$ per unit of product $i$. The agent offers a subset $x\in \{0,1{\}}^n$; log-demand for included product $i$ is Gaussian, $\log (d_i)\mid \theta ,x\sim N((\theta x{)}_i,{\sigma }^2)$, where $(\theta x{)}_i={\theta }_{ii}+{\sum }_{j\ne i}{x}_j{\theta }_{ij}$ — the diagonal ${\theta }_{ii}$ is product $i$‘s own popularity, off-diagonals ${\theta }_{ij}$ capture how offering $j$ shifts demand for $i$ (substitution/complementarity). Expected profit is ${\sum }_i{p}_i{x}_i{e}^{(\theta x{)}_i+{\sigma }^2/2}$.

Here $\theta$ is a matrix, not a vector, but the same multivariate-Gaussian-conjugacy machine applies after vectorizing $\theta$ (stacking its columns into $\bar{\theta }$) and forming a Kronecker-product design matrix $W=x^{\top }\otimes S$ from the offered assortment and a selection matrix $S$; the posterior mean/covariance update is the same generalized-least-squares-looking formula as ordinary Bayesian linear regression. TS strictly outperforms greedy and tuned $ϵ$-greedy in simulation (Fig. 7.2) — greedy in particular performs poorly because it fails to actively probe substitution effects.

Connections

• This note’s three examples are all instances of the general Thompson/greedy algorithms in Bernoulli Bandit and Thompson Sampling Algorithm — the “reward model” $q_{\theta }$ becomes linear-Gaussian or logistic instead of Bernoulli.
• Exact conjugate updates are available for the linear-Gaussian cases (correlated edges, assortment); the logistic news-recommendation case requires the approximate-sampling machinery of Approximate Thompson Sampling and Practical Extensions.
• The linear-bandit regret bound $O(d\sqrt{T}\log T)$ and the eluder-dimension generalization in Regret Bounds for Thompson Sampling are stated precisely for the reward models introduced here.
• Sparse linear models and assortment diversification reappear in Regret Bounds for Thompson Sampling as two of the four documented TS failure modes (TS explores one-hot/single-type actions when a more diverse or bisection-search-like strategy would learn faster) — a caution against naively deploying the algorithms in this note without checking the information-ratio diagnosis.

See Also

• Bernoulli Bandit and Thompson Sampling Algorithm — the base algorithm these examples specialize
• Approximate Thompson Sampling and Practical Extensions — Laplace/Langevin approximations needed for the logistic news-recommendation model
• Regret Bounds for Thompson Sampling — linear/eluder-dimension regret bounds, and the assortment/sparse-model failure modes
• UCB and Greedy Algorithms for Bandits — the ellipsoidal- vs. hyper-rectangular-confidence-set argument for why modeling correlation among actions (as in coherent TS here) matters