Exploration vs exploitation: epsilon-greedy, UCB, Thompson sampling

Summary

Exploration gathers information; exploitation chooses the action that currently appears best from available evidence. Arm A leads by estimated reward, but arm B has far fewer observations. Compare a random switch, an uncertainty index, and a posterior draw before choosing the next observation.

The setup

There are $K$ eligible actions with unknown stationary reward means $μ_{a}$ . Each round chooses one action and observes its reward. For horizon $T$ , pseudo-regret compares chosen means with the best eligible mean:

$R_{T} = T max_{a} μ_{a} - \sum_{t = 1}^{T} μ_{a_{t}} .$

This rewards cumulative performance, not necessarily precise identification at a fixed deadline. Never explore an action outside safety, permission, or resource eligibility. Our displayed means are generic bounded-reward estimates, not exact Bernoulli success fractions.

An uncertainty bonus or a posterior draw can overturn the mean leader

Derivation

Dots and whiskers show UCB means and bonuses, not confidence guarantees for this chosen coefficient. Thompson curves are explicit toy assumptions. Only the displayed draw selects B.

Check: Why can B be selected despite its lower mean? How do UCB and Thompson justify that choice differently?

Read it this way: The mean favors A. An upper-confidence score or posterior draw can favor B; the table uses illustrative, not empirical, values.
Can the lower estimated mean win an uncertainty-aware choice?

$ϵ$ -greedy

Choose the empirical leader with probability $1 - ϵ$ ; otherwise sample uniformly across all $K$ eligible arms. Declare a fixed order for exact score ties. For $K = 3$ and $ϵ = 0.3$ , the probabilities are $(0.8, 0.1, 0.1)$ , not $(0.7, 0.15, 0.15)$ .

UCB (Upper Confidence Bound)

Initialize untried eligible arms first, or give them infinite priority. For positive pull counts $N_{a}$ , select the largest index:

a_{t} = ar g a max (\overset{μ}{^}_{a} + c \frac{ln t}{N _{a}}),

For the displayed $t = 64, c = 0.2$ , the indices are approximately $(0.684489, 0.753933, 0.441202)$ , selecting B. This coefficient illustrates selection; it does not supply UCB1’s stated guarantee. Classical logarithmic, gap-dependent UCB1 bounds assume stationary independent bounded rewards and the corresponding bonus convention.

Thompson sampling

Draw one plausible mean per eligible arm from its posterior; select the largest draw and update from the observed reward. Draws $(0.58, 0.78, 0.31)$ select B, not necessarily on the next round. Separately, a Bernoulli likelihood and Beta $(1, 1)$ prior become Beta $(3, 2)$ after two successes and one failure. Its posterior mean is $3/5$ .

When each strategy is the right choice

Reward means drift

New task: respond when a product update changes rewards.

Picture and change: compare accumulated evidence with a declared recent window or a justified reset/discount model.

Check: 90 successes and ten failures yield Beta $(91, 11)$ . After ten new failures, pooling gives Beta $(91, 21)$ , mean $0.8125$ . Using only the new window gives Beta $(1, 11)$ , mean $1/12$ . Discarding history reacts faster but increases uncertainty; stationary regret guarantees no longer transfer automatically.

Use when: fixed means no longer describe the environment.

Estimate a causal comparison

New task: estimate a common-population effect, not merely reward during learning.

Picture and change: specify randomized assignments, recorded propensities, mature outcomes, and a valid adaptive-inference plan.

Check: two independent units have assignment probabilities $p_{t} (A) = (0.8, 0.2)$ . The first receives A, the second B; both rewards equal one. Inverse-propensity population means are $μ_{A} = (1/0.8 + 0) /2 = 0.625$ and $μ_{B} = (0 + 1/0.8) /2 = 0.625$ . These estimates do not supply a fixed-sample confidence interval after arbitrary adaptive stopping.

Use when: an identified effect and its precision drive the design; retain required controls.

Beyond bandits

Contextual bandits condition reward estimates on available features. Delayed outcomes require pending-assignment accounting rather than treating missing rewards as zeros. Costs and permissions constrain the eligible set before selection.

In sequential RL, actions also change future states. Boltzmann policies sample proportionally to $exp (Q (s, a) / τ)$ . Maximum-entropy objectives reward policy entropy; intrinsic bonuses target chosen novelty signals. These change the objective or observation process, not merely the bandit score.

Common pitfalls

A bare $ϵ_{t} = 1/ t$ schedule is not a universal logarithmic-regret theorem. Insufficient exploration can preserve a noisy leader; excessive exploration incurs continuing opportunity cost. Hoeffding bonuses do not directly handle arbitrary unbounded rewards. Posterior sampling does not automatically track drift or guarantee optimality under a misspecified likelihood.

Is constant epsilon always wrong?

Answer

No: continuing support or adaptation may be required. If the true means equal the displayed estimates, the fixed probabilities yield reward $0.586$ , short of $0.62$ by $0.034$ . That fixed rule incurs expected regret $0.034 T$ under these stationary means. Judge its information benefit against the stated objective.

UCB’s action is deterministic given history and tie rules, but that history contains random rewards. Thompson draws are reproducible with controlled random state and execution; compare repeated seeds and matching reward streams.