Bandit Algorithms for Recommendation Systems: Context‑Free, Thompson Sampling, and Contextual Approaches

The Ctrip technical team introduces the multi‑armed bandit (MAB) problem, where a gambler must choose among n identical arms with unknown reward probabilities P_i to maximize cumulative gain. In recommendation scenarios, this models the need to discover a user's interest across different content categories without excessive data collection.

Context‑free Bandit (UCB) : The Upper Confidence Bound algorithm selects arms based on an optimistic estimate of expected reward, balancing exploitation (average reward) and exploration (confidence interval width). The score for arm i at time t is computed as the sum of the empirical mean reward and a term proportional to the inverse square root of the number of times the arm has been pulled.

Thompson Sampling : This Bayesian method samples a reward probability from the posterior Beta distribution for each arm (Beta(α,β) for Bernoulli rewards). After observing a click, the arm’s parameters are updated to Beta(α+1,β); otherwise to Beta(α,β+1). The article notes the use of org.apache.commons.math3.distribution.BetaDistribution for implementation and discusses batch updates to reduce latency.

Contextual Bandit : Extends the MAB by incorporating real‑time user and item features x_t. The expected reward is modeled as a function f(x_t), allowing the algorithm to tailor arm selection to each user’s context. Linear Thompson Sampling is presented as a concrete contextual method.

Scenario Applications : The authors apply bandit algorithms to ad‑copy selection, replacing traditional test‑rollout strategies that allocate equal traffic and suffer from cold‑start and Matthew‑effect issues. By using an exploration‑exploitation (E&E) framework, high‑quality and low‑quality copies can coexist while keeping user experience loss under control.

Update Mechanisms : Two batch‑update formulas are described. The sum‑update adds the batch’s click (S) and non‑click (F) counts to the arm’s α and β parameters: α_{i,t+1}=α_{i,t}+S_{i,t} , β_{i,t+1}=β_{i,t}+F_{i,t} . The normalized update rescales parameters by the total exposure M_t/K to address traffic imbalance.

Offline Evaluation : The paper outlines a replay‑based offline evaluation using logged data D={(x,a,r)} where each arm is chosen uniformly (1/K). It discusses the partial‑label problem, the need for unbiased estimators, and references Li et al. and Nicol et al. for improved replay and bootstrapping techniques.

Practical Experience : Key lessons include the importance of informative priors (non‑uniform Beta), adjusting α and β with a variance‑controlling factor γ, ensuring exploration candidates have acceptable baseline quality, and deciding between real‑time sampling versus table‑lookup based on latency constraints.

Optimization Points : The authors note that static reward probabilities assume a stationary environment, whereas non‑stationary settings require adaptive strategies. They also suggest using richer feedback (e.g., dwell time) instead of binary clicks to mitigate click fraud.

Overall, the article demonstrates how bandit algorithms can be integrated into large‑scale recommendation pipelines to improve cold‑start handling, diversity, and unbiased data collection while maintaining user experience.