Bandit Algorithms

Bandit algorithms are policies for the multi-armed bandit problem: choose one arm, observe reward only for the arm shown, and update the policy before the next round. This page focuses on the concrete policies. The base notation, partial-feedback setup, and regret definition live on Multi-Armed Bandits.

In recommendation systems, these policies are useful when the product must learn from live exposure: a new headline, notification template, recommendation module, or item bucket may be better than the current winner, but the system cannot know that without showing it to users.

Shared state

For each arm $a$, a basic bandit policy maintains:

Quantity	Meaning
$n_a$	number of times arm $a$ has been shown
$w_a$	number of observed successes, such as clicks
${\hat{\mu }}_a=w_a/n_a$	empirical reward rate
$t$	current round or total number of decisions so far

Different algorithms use this same state differently. Greedy trusts ${\hat{\mu }}_a$ immediately. Epsilon-greedy injects random exploration. UCB adds an uncertainty bonus. Thompson sampling samples from a posterior belief.

The diagram shows the distinction between estimate, uncertainty, and randomized belief. The algorithm changes how the next arm is chosen; the underlying bandit feedback remains the same partial-feedback loop from Multi-Armed Bandits.

Greedy

A greedy policy always chooses the arm with the largest empirical reward:

$$a_t=\arg \underset{a}{\max }{\hat{\mu }}_a.$$

It is simple and cheap, but brittle. If a mediocre arm gets a few lucky early clicks, greedy can keep exploiting it and never gather enough evidence about the other arms. Greedy is useful as a baseline, not as a safe default for cold-start or changing content.

Epsilon-Greedy

Epsilon-greedy chooses randomly with probability $ϵ$ and otherwise chooses the current empirical winner:

$$a_t=\{\begin{array}{ll}\text{random arm},& \text{with probability }ϵ,\\ \arg {\max }_a{\hat{\mu }}_a,& \text{with probability }1-ϵ.\end{array}$$

The parameter $ϵ$ is the exploration rate. Larger $ϵ$ learns more about alternatives but spends more traffic on arms that currently look worse. Smaller $ϵ$ protects short-term reward but can converge slowly or prematurely. In production, $ϵ$ is often bounded by eligibility, safety, fatigue, and product-quality rules rather than applied to every possible item.

UCB

Upper-confidence-bound policies choose the arm with the largest optimistic score:

$$a_t=\arg \underset{a}{\max }\left({\hat{\mu }}_a+\sqrt{\frac{2\log t}{n_a}}\right).$$

The first term, ${\hat{\mu }}_a$, exploits high empirical reward. The second term,

$$\sqrt{\frac{2\log t}{n_a}},$$

is the exploration bonus: it is larger for arms with fewer observations and shrinks as $n_a$ grows. The UCB score is the sum of the empirical reward estimate and this bonus. The policy then chooses the arm with the largest UCB score. As $t$ grows, arms that have been neglected become worth checking again. UCB is deterministic once the observed rewards are fixed, which makes it easier to debug than random exploration.

Thompson Sampling

Thompson sampling is randomized, but not uniformly random. It samples one plausible reward rate for each arm from the current posterior belief, then chooses the arm with the largest sampled value.

For binary rewards, a common model is a Beta-Bernoulli bandit:

$${\theta }_a\sim \mathrm{Beta}({\alpha }_a,{\beta }_a),a_t=\arg \underset{a}{\max }{\theta }_a.$$

Here ${\theta }_a$ is a sampled plausible click rate for arm $a$. After a click, update ${\alpha }_a\leftarrow {\alpha }_a+1$. After a non-click, update ${\beta }_a\leftarrow {\beta }_a+1$. Arms with little data have wider posterior distributions, so they occasionally sample high values and get explored. Arms with much data have tighter posteriors, so the policy becomes more stable.

Worked example

Suppose a homepage can show one of three modules. The product optimizes immediate clicks, and the current logged state is:

Arm	Shows $n_a$	Clicks $w_a$	Empirical CTR ${\hat{\mu }}_a$
A: sports roundup	120	6	0.050
B: finance tips	40	3	0.075
C: weather alerts	8	1	0.125

At first glance, arm C has the largest empirical CTR. But it also has only eight observations, so the estimate is uncertain. Different policies make different next decisions:

Policy	Decision rule	Next arm	Reason
Greedy	choose largest ${\hat{\mu }}_a$	C	highest observed CTR
Epsilon-greedy	usually greedy, sometimes random	usually C	random exploration may choose A or B
UCB	choose empirical CTR plus confidence bonus	C	high CTR and high uncertainty
Thompson sampling	sample plausible CTRs from posteriors	often C, sometimes B	C has a wide posterior; B still has plausible upside

Now imagine C receives 30 more impressions and no more clicks. Its empirical CTR drops from $1/8=0.125$ to $1/38\approx 0.026$. A greedy policy would stop showing it only after the damage is visible. UCB and Thompson sampling are designed to make that trial bounded: early uncertainty earns C a chance, but disappointing evidence reduces its future score.

This example also shows why bandit logs need action propensities. If yesterday’s policy rarely showed C, ordinary supervised evaluation cannot infer what would have happened had C been shown more often. See Offline Versus Online Evaluation for replay and inverse-propensity evaluation.

Choosing a policy

Policy	Strength	Weakness	Good fit
Greedy	simple and stable after exploration is complete	can lock onto early noise	mature arms with enough randomized history
Epsilon-greedy	easy to reason about and control	wastes exploration uniformly	simple experiments and low-risk surfaces
UCB	explores uncertain arms more deliberately	confidence formula assumes a clean reward process	small arm sets with fast feedback
Thompson sampling	naturally balances uncertainty and reward	needs a reward model and randomized serving	click, conversion, or binary success rewards

For personalized ranking, move to Contextual Bandits: the policy should condition on user, item, query, device, and time features rather than treating every request as exchangeable.

Production considerations

• Define the reward before choosing the algorithm: clicks, saves, purchases, retention, and satisfaction can point to different arms.
• Keep eligibility filters outside the bandit: exploration should not show unavailable, unsafe, or permission-ineligible items.
• Log the chosen arm, reward, timestamp, policy version, and selection probability when available.
• Separate exploration traffic from final product ranking when the cost of mistakes is high.
• Use minimum exposure floors or priors for new arms so cold-start items can be evaluated without taking over the surface.
• Watch non-stationarity: stale arms, news cycles, seasonality, and product changes can make old reward estimates misleading.

Caveats

Bandit algorithms optimize observed rewards, not necessarily user welfare. A click reward can over-promote sensational content, repeated notifications, or short-term engagement at the cost of trust. Delayed rewards, repeated exposure, interference between users, and position effects violate the clean assumptions behind the simplest algorithms. For high-impact recommenders, combine bandits with guardrails, diversity constraints, and online experiments.

References

• Auer et al., 2002, Finite-time Analysis of the Multiarmed Bandit Problem
• Chapelle and Li, 2011, An Empirical Evaluation of Thompson Sampling
• Li et al., 2010, A Contextual-Bandit Approach to Personalized News Article Recommendation
• Li et al., 2010, Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms

Nav

Section — Recommendation Systems and Personalization

← Multi-Armed Bandits Contextual Bandits →