Multi-Armed Bandit Algorithms

The multi-armed bandit (MAB) problem is the canonical formal model for online sequential decision-making under uncertainty: an agent must repeatedly choose one of several actions (each modeled as a slot machine arm), receives a stochastic reward from the chosen arm, and aims to maximize cumulative reward over many rounds. The agent faces an explicit exploration-vs-exploitation trade-off — should the next pull be the arm with the highest empirical mean (exploitation) or an under-pulled arm whose true mean is uncertain (exploration). Three classical algorithms address this trade-off: ε-greedy (the simplest — random action with probability ε, otherwise greedy), Upper Confidence Bound (UCB1) (deterministic algorithm using statistical confidence bounds), and Thompson Sampling (Bayesian algorithm sampling from posteriors over arm rewards). All three appear in production recommender systems for cold-start handling, exploration in personalized ranking, and breaking the popularity feedback loop. The contextual variant — contextual bandits — extends the framework to account for per-request features and is treated separately in LinUCB.

1. The Bandit Problem Setup

The classic K-armed bandit problem:

• There are K arms (actions, items, advertisements). Each arm a has an unknown true reward distribution with mean μ_a.
• At each round t = 1, 2, ..., T, the agent chooses an arm a_t ∈ {1, ..., K} and receives a stochastic reward r_t ~ P_{a_t} drawn from the chosen arm’s distribution.
• The objective is to maximize the expected cumulative reward E[Σ_{t=1}^{T} r_t], equivalent to minimizing the regret: R(T) = T · μ* − E[Σ_{t=1}^{T} r_t] where μ* = max_a μ_a is the true best arm’s mean.

The challenge: the agent does not know μ_a for any arm. Estimating μ_a requires pulling arm a (which yields rewards but may be suboptimal); not pulling arm a keeps the regret of suboptimal arms at zero but prevents the agent from learning a is actually best.

2. ε-Greedy

The simplest bandit algorithm:

For each round t:
    With probability ε:  pull a random arm.
    With probability 1−ε:  pull the arm with the highest empirical mean reward.

The empirical mean for arm a after n_a pulls with rewards r_1, ..., r_{n_a} is μ̂_a = (1/n_a) · Σ r_i.

Hyperparameter: ε ∈ [0, 1]. Common choices:

• Constant ε (e.g., 0.1) — always 10% exploration.
• Decaying ε(t) = c/t — exploration rate decreases as the agent gathers more data.

ε-greedy’s regret is O(K · log(T)) with optimal ε(t) schedules and O(T^{2/3}) with constant ε. The optimal-ε analysis gives the same asymptotic regret as UCB but is harder to tune in practice.

Strengths: trivial to implement; easy to interpret; always works. Weaknesses: no concept of arm uncertainty (an under-explored arm and a well-explored one are treated the same); pulls equally many times to all arms when exploring (does not focus exploration on uncertain arms).

3. Upper Confidence Bound (UCB1)

UCB1 (Auer, Cesa-Bianchi, Fischer 2002) selects the arm that maximizes a upper confidence bound on the true mean reward:

UCB(a, t) = μ̂_a  +  c · √( 2 · log(t) / n_a )

where:

• μ̂_a is the empirical mean reward of arm a so far.
• n_a is the number of times arm a has been pulled.
• c is a tunable constant (often 1 in theoretical analyses).
• √( 2 · log(t) / n_a ) is the upper-confidence half-width — large for under-pulled arms, small for well-explored arms.

The algorithm at each round pulls the arm with the largest UCB value:

a_t = argmax_a  UCB(a, t)

This is deterministic — given the same history, UCB always makes the same choice. There is no random exploration; instead, exploration emerges from the upper-confidence-bound term, which is large for under-explored arms (high uncertainty) and small for well-explored arms (low uncertainty).

UCB1’s regret bound is O(K · log(T) / Δ) where Δ is the gap between the best arm and the second-best — an instance-dependent logarithmic regret, which is provably optimal up to constants.

Strengths: deterministic and analyzable; tight regret guarantee; no tuning of exploration rate. Weaknesses: the confidence-bound formula assumes bounded rewards in [0, 1]; relies on Hoeffding-style assumptions that may not hold in practice; theoretical bounds use a confidence parameter that practitioners often tune empirically.

4. Thompson Sampling

Thompson sampling (Thompson 1933, revived in the 2010s) takes a Bayesian approach: maintain a posterior distribution over each arm’s true mean reward; at each round, sample from each posterior and pull the arm with the highest sample.

For the classical Bernoulli bandit (rewards in {0, 1}), the posterior over arm a’s mean is a Beta distribution updated by conjugacy:

Initialize: For each arm a, prior Beta(α_a = 1, β_a = 1).
For each round t:
    For each arm a, sample θ_a ~ Beta(α_a, β_a).
    Pull arm a_t = argmax_a θ_a.
    Observe reward r_t ∈ {0, 1}.
    Update: α_{a_t} += r_t,  β_{a_t} += (1 - r_t).

For Gaussian-reward bandits, the posterior is Gaussian and the update is conjugate similarly.

Thompson sampling has O(log(T)) regret comparable to UCB but with often better empirical performance on real datasets. It is also easier to extend to more complex settings (contextual bandits, structured rewards) because the Bayesian framework adapts naturally.

Strengths: strong empirical performance; principled Bayesian framework; easy to extend; auto-balances exploration and exploitation. Weaknesses: requires conjugate priors (or approximate posterior inference); harder to analyze theoretically than UCB.

5. Comparison Across the Three

For a typical recommender setting (each item is an arm, reward is click or some satisfaction signal):

Algorithm	Hyperparameters	Regret	Empirical	Implementation
ε-greedy	ε (or ε(t) schedule)	O(K log T) with optimal schedule	Good but tuning matters	Trivial
UCB1	c (often 1)	O(K log T / Δ)	Good	Easy
Thompson Sampling	Prior parameters (often uniform)	O(K log T)	Often best	Requires posterior inference

In practice, Thompson sampling is the modern default for production recommender exploration when feasible. UCB is preferred when deterministic behavior is required (e.g., for reproducibility or A/B test parity). ε-greedy is the trivial baseline.

6. Application to Recommendation

The mapping from MAB to recommender systems:

• Arms = items in the catalog (or candidate set per request).
• Reward = user feedback (click, dwell time, conversion).
• Rounds = user requests.

Production complications:

Catalog is huge. A million items as arms makes pure MAB infeasible — you cannot pull each arm enough times to estimate its mean. Solutions: cluster items into a smaller arm set, use contextual bandits with shared parameters across items (LinUCB), or restrict exploration to a candidate subset selected by a non-bandit retriever.

Each user-item pair is its own arm. True personalization requires per-user-per-item exploration, which is the contextual bandit setting. See LinUCB.

Delayed rewards. A click is observed quickly; conversion or long-term engagement is delayed. Bandit theory typically assumes immediate reward; production deployments use approximations.

Non-stationarity. Items’ true reward distributions drift over time (popularity shifts). Standard MAB assumes stationary; production deployments use windowed estimates or non-stationary variants.

7. When to Use Pure MAB vs Contextual Bandits

Pure MAB is appropriate for non-personalized exploration — finding the globally best item or set of items independent of user features. This is rare in modern recommendation.

LinUCB and other contextual bandits are appropriate for personalized exploration, where each request comes with user features and the reward depends on both the item and the user.

In practice, production recommender systems most often use contextual bandits if they use bandits at all.

8. See Also

• LinUCB — contextual bandit with linear reward models
• Cold Start Problem — bandits are a primary cold-start strategy
• Beyond-Accuracy Objectives — exploration is one strategy for breaking popularity bias
• Recommender Algorithms Catalog
• Recommender Systems