A Survey on Contextual Multi-armed Bandits

1. Introduction

• At each round, the agent observes a context and selects an arm; rewards may be stochastic or adversarial, and only the selected arm’s reward is revealed.The arm with the highest expected reward may differ across contexts.Source: §1 · p. 2
• Contextual bandits can model news personalization, where article and user features inform article choice to maximize click-through rate or dwell time.The survey defines regret against the best policy’s expected cumulative reward and sets minimizing that gap as the agent’s goal.Source: §1 · p. 2
• The appropriate benchmark depends on the algorithm: it may be the best arm, expert, or policy in a predefined set.The survey notes that reductions to classification or regression compete with the best policy in that set.Source: §1 · p. 2
• Table 2 summarizes the surveyed algorithms using C for distinct contexts, N for policies, K for arms, and d for context dimension.Its horizon column indicates whether knowing T is needed to attain the proposed regret bound, not necessarily to run the algorithm.Source: §1 · p. 3, Table 2 · p. 4

2. Unbiased Reward Estimator

• At round t, the observed reward vector has zeros for unchosen arms and records the true reward only for the selected arm.The algorithm selects that arm using probability vector p_t.Source: §2 · p. 5
• The observed vector is biased because the selected arm’s reward is observed only with its selection probability.The passage contrasts the expectation of the observed reward with the true reward.Source: §2 · p. 5
• The section introduces an unbiased estimate of the true reward vector, a trick used by many later algorithms.The supplied passage does not specify the complete estimator formula.Source: §2 · p. 5

3. Reduce to K-Armed Bandits

• When contexts are enumerable, the naive context-wise approach applies a K-armed bandit algorithm to each one but ignores relationships between contexts.Source: §3 · p. 5
• Applying EXP3 separately to each context yields the regret bound stated in Theorem 3.1.This reduction treats contexts independently and requires that they be enumerable.Source: §3 · p. 5
• The context-wise reduction is unsuitable for continuous contexts and lets learning one context provide no benefit for another.Its independence across contexts discards their relationships.Source: §3 · p. 6
• A second reduction treats each predefined policy as an arm and competes with the best policy in that set.The survey says this approach works with few policies and many arms, but its regret bound is weak for a huge policy set.Source: §3 · p. 6

4. Stochastic Contextual Bandits

• Stochastic contextual bandit algorithms assume arm rewards follow unknown distributions, with some methods further assuming sub-Gaussian rewards.Source: §4 · p. 6
• Under linear realizability, expected arm rewards are linear in the arm’s features.Source: §4 · p. 6
• The section also covers algorithms for arbitrary policy sets without the linear realizability assumption.Source: §4 · p. 6

4.1.1 LinUCB/SupLinUCB

• LinUCB assumes expected rewards are linear in arm features and selects the arm with the highest upper confidence bound.In the news-recommendation example, the feature vector can encode a user-article pair.Source: §4.1.1 · pp. 6–7
• SupLinUCB partitions observations into sets so rewards within each set are independent, enabling an Azuma-inequality regret analysis.The survey describes it as mainly for theoretical analysis, not as a practical algorithm.Source: §4.1.1 · p. 9

4.1.2 LinREL/SupLinREL

• LinREL uses spectral regularization by setting small eigenvalues to zero, whereas LinUCB adds an ℓ2 regularization term.The cited LinREL confidence-bound theorem assumes independent observed rewards, an assumption the survey says does not hold for adaptive actions.Source: §4.1.2 · pp. 9–10
• SupLinREL partitions observations into stages to make rewards within a stage independent, then applies LinREL and has a stated regret bound.The survey introduces it to address the dependence between earlier actions and later decisions.Source: §4.1.2 · p. 11

4.1.4 Thompson Sampling with Linear Payoffs

• Linear Thompson sampling permits adversarially chosen contexts and assumes expected rewards are linear in arm features.It uses a Gaussian likelihood and prior; the general Thompson-sampling procedure draws a parameter from the posterior and selects the arm with the highest predicted reward under that draw.Source: §4.1.4 · pp. 12–13

Proof

• Theorem 4.7 provides a way to update the parameter belief after observing new data, and the passage says that the corresponding procedure is described in Algorithm 4.Source: Proof · p. 13
• Chapelle and Li (2011) use Laplace approximation to obtain a Gaussian posterior with diagonal covariance for logistic-regression Thompson sampling.The survey states that each logistic-regression weight has a Gaussian distribution.Source: Proof · p. 14
• Chapelle and Li (2011) report good empirical results on display advertising but give no regret bound for their algorithm.Source: Proof · p. 14

4.2 Kernelized Stochastic Contextual Bandits

• The kernelized setting replaces linear reward realizability with an unknown, possibly nonlinear reward function in an RKHS.GP-UCB/CGP-UCB place a Gaussian Process prior on the function, while KernelUCB uses regularized linear regression in the RKHS.Source: §4.2 · p. 14

4.2.1 GP-UCB/CGP-UCB

• GP-UCB selects points using estimated reward and uncertainty, trading off exploitation and exploration.It places a Gaussian Process prior on the reward function and updates its posterior after observations.Source: §4.2.1 · p. 16
• For linear and squared-exponential kernels, the survey gives maximum-information-gain bounds of ˜O(d ln T) and ˜O((ln T)^(d+1)), respectively.The information gain γ_T depends on the chosen kernel.Source: §4.2.1 · p. 17
• CGP-UCB models contexts and arms jointly, allowing both spaces to be infinite and using a kernel over their joint space.One proposed kernel is the product of separate context-space and arm-space kernels.Source: §4.2.1 · p. 17

4.2.2 KernelUCB

• In the agnostic case, the survey says KernelUCB has a better regret bound than GP-UCB, relating this comparison to effective dimension and information gain.For a linear kernel, the effective dimension is at most d.Source: §4.2.2 · p. 19

4.3.1 Epoch-Greedy

• With probability 1−δ, Epoch-Greedy has regret O((K ln(N/δ))^1/3 T^2/3), using one uniform-random exploration step per epoch followed by exploitation.Its policy class can be finite or infinite with finite VC-dimension, without assuming linear payoff.Source: §4.3.1 · pp. 19, 23

4.3.2 RandomizedUCB

• RandomizedUCB has regret O(TK ln(TN/δ)) and sub-linear running time at each round t of O(t^5K^4 ln^2(tK/δ) ln N), using an argmax oracle.It considers the full policy set and uses history samples instead of requiring knowledge of Dx.Source: §4.3.2 · p. 27

4.3.3 ILOVETOCONBANDITS

• With probability at least 1−δ, ILOVETOCONBANDITS (Agarwal et al., 2014) achieves optimal regret and seeks to reduce RandomizedUCB’s AMO-call cost.It optimizes a sparse policy distribution at prespecified rounds, then samples actions from that distribution.Source: §4.3.3 · p. 28
• The optimization trades off empirical regret and estimator variance, assigning lower variance to low-regret policies and allowing higher variance for high-regret policies.The variance control makes reward estimates more accurate for policies with low empirical regret.Source: §4.3.3 · p. 29
• The resulting distribution has at most ~O(Kt/ln(N/δ)) policies in its support, making sampling sub-linear time.The support size matches the number of AMO calls in round t.Source: §4.3.3 · p. 29
• Agarwal et al. (2014) show that the total AMO-call count over T rounds is a vast improvement over RandomizedUCB.The supplied passage gives the call-count expression only partially.Source: §4.3.3 · p. 29
• Theorem 4.18 states that ILOVETOCONBANDITS has a regret bound with probability at least 1 − δ.The bound itself is not included in the supplied passage.Source: §4.3.3 · p. 30

5.1 EXP4

• EXP4 bounds regret against the best expert in expectation, and attaining its stated bound requires knowing the time horizon T.EXP4 makes no assumption on the reward distribution; its experts provide advice vectors over arms.Source: §5.1 · pp. 30, 34

5.2 EXP4.P

• EXP4.P achieves EXP4’s regret bound with high probability by using reward-estimator confidence intervals to bound experts’ cumulative rewards.Its guarantee assumes a uniform expert and ln(N/δ) ≤ KT.Source: §5.2 · pp. 34, 36
• EXP4.P differs from EXP4 by updating expert weights with upper confidence bounds rather than estimated rewards.This addresses the high variance of EXP4’s unbiased reward estimator.Source: §5.2 · pp. 34, 36

5.3 Infinite Many Experts

• EXP4 and EXP4.P cannot directly handle infinite expert sets, so VE approximates the set using policies’ predictions on sampled contexts.VE samples arms uniformly for the first τ rounds, constructs representatives for the prediction sequences, then applies EXP4 or EXP4.P.Source: §5.3 · pp. 39–40
• For policy sets with VC dimension d, VE’s analysis bounds the number of distinct prediction sequences over τ sampled contexts.The survey states that the number is less than (eτ/d)^d for τ > d.Source: §5.3 · pp. 40–41

• Contextual bandits can model user modeling, Internet advertising, search engines, and experiment optimization.Source: §6 · p. 41
• Offline evaluation is challenging when the evaluated policy differs from the data-generating policy; proposed methods use uniform logging, inverse propensity scoring, or combine IPS with the direct method.The survey attributes these methods to Li et al. (2011), Strehl et al. (2010), and Langford et al. (2011), respectively.Source: §6 · p. 42
• Algorithm selection should match the problem’s assumptions, since regret bounds are not the only criterion and problem-dependent bounds may differ from problem-independent ones.The survey notes that Epoch-Greedy can achieve an O(ln T) problem-dependent bound despite a non-optimal problem-independent bound.Source: §6 · p. 42