Multi-Armed Bandits and Exploration

Introduction and Context

Many reinforcement-learning problems require an agent to choose among actions whose consequences are initially uncertain. A recommendation system may decide which article to display, an online retailer may select among advertisements, and a clinical decision-support system may compare treatment options. In each case, the agent must learn from feedback while also making decisions that produce immediate value.

The multi-armed bandit is the simplest formal model of this situation. It captures repeated decision-making with a set of actions, unknown reward distributions, and no explicit state transitions. Although simpler than a full Markov decision process, the bandit model isolates a central challenge in reinforcement learning: the trade-off between exploiting actions that currently appear valuable and exploring actions that might be better.

This chapter develops greedy methods, optimistic initialization, upper-confidence-bound (UCB) methods, Thompson sampling, and contextual bandits. It also introduces regret, experimental design, implementation concerns, and ethical issues in practical bandit systems.

Learning Objectives

By the end of this chapter, you should be able to:

• formulate a stationary multi-armed bandit problem;
• distinguish exploration from exploitation;
• explain and implement greedy, epsilon-greedy, optimistic-initialization, UCB, and Thompson-sampling methods;
• calculate and interpret cumulative and pseudo-regret;
• explain how contextual bandits extend ordinary bandits;
• design practical experiments with appropriate evaluation and safeguards;
• critically assess limitations, bias, nonstationarity, and ethical risks.

1. The Multi-Armed Bandit Model

A bandit has a finite action set \(\mathcal A=\{1,2,\ldots,K\}\). At each time step \(t\), an agent selects action \(A_t\), observes reward \(R_t\), and updates its information. Action \(a\) has an unknown expected reward

\[

\mu_a=\mathbb E[R_t\mid A_t=a].

\]

The standard stochastic bandit assumes that rewards obtained from action \(a\) are independent and identically distributed over time, with fixed mean \(\mu_a\). Rewards may be bounded, for example \(R_t\in[0,1]\), or may follow a known distributional family such as Bernoulli or Gaussian distributions.

Let \(\mu^*=\max_a\mu_a\) denote the best expected reward. The optimal action need not be known to the agent. The action-value estimate based on observed rewards is

\[

Q_t(a)=\frac{1}{N_t(a)}\sum_{i=1}^{t}R_i\mathbf 1\{A_i=a\},

\]

where \(N_t(a)=\sum_{i=1}^{t}\mathbf 1\{A_i=a\}\) is the number of times action \(a\) has been selected. The estimate is defined only after the action has been sampled at least once. An incremental update avoids storing all observations:

\[

Q_{t+1}(a)=Q_t(a)+\frac{1}{N_{t+1}(a)}\bigl(R_{t+1}-Q_t(a)\bigr)

\]

when action \(a=A_{t+1}\) is selected; estimates for other actions remain unchanged. This is the sample-average update and assumes a stationary reward distribution.

Exploration and Exploitation

Exploitation selects the action with the highest current estimated value. It uses existing knowledge to obtain reward. Exploration selects uncertain or under-sampled actions to improve knowledge. Exploration can reduce immediate reward but may reveal a superior action.

The tension is unavoidable. An agent that always exploits can become trapped by an early lucky observation. An agent that explores excessively may gather information without using it effectively. No method is universally best: the appropriate strategy depends on the time horizon, reward noise, cost of experimentation, and consequences of errors.

2. Greedy and Epsilon-Greedy Methods

A purely greedy policy selects

\[

A_t\in\arg\max_a Q_t(a).

\]

Ties should be broken randomly or by a documented rule. Pure greed is simple and efficient once estimates are accurate, but it may never revisit an action that initially appears inferior.

The epsilon-greedy policy explores randomly with probability \(\varepsilon\) and exploits with probability \(1-\varepsilon\). Formally, assuming uniform random exploration,

\[

\pi(a\mid Q_t)=

\begin{cases}

1-\varepsilon+\varepsilon/K, & a\in\arg\max_b Q_t(b)\text{ under a single selected tie};\\

\varepsilon/K, & \text{otherwise}.

\end{cases}

\]

In implementation, one usually draws a random number: if it is below \(\varepsilon\), choose a random action; otherwise choose a greedy action. A constant epsilon provides persistent exploration. A decaying schedule, such as \(\varepsilon_t=c/t\) or \(\varepsilon_t=\max(\varepsilon_{\min},\varepsilon_0\lambda^t)\), gradually emphasizes exploitation. Decay must be selected carefully: rapid decay can cause premature commitment, while slow decay can waste opportunities.

Worked Example: Epsilon-Greedy Choice

Suppose there are four actions with estimates \(Q(a)=(0.50,0.70,0.65,0.40)\), \(\varepsilon=0.20\), and exploration chooses uniformly. Action 2 is greedy. The probability of selecting action 2 is \(0.80+0.20/4=0.85\), while each non-greedy action has probability \(0.20/4=0.05\). The expected estimated reward under this policy is

\[

0.85(0.70)+0.05(0.50+0.65+0.40)=0.6775.

\]

This is lower than the greedy estimate of 0.70, but exploration may improve future decisions.

3. Optimistic Initialization

Optimistic initialization assigns every action an initial value larger than its plausible true mean. For rewards in \([0,1]\), setting \(Q_1(a)=1\) is optimistic if the likely means are below 1. A greedy policy then selects each action because all initially appear attractive; after an action receives an ordinary reward, its estimate decreases and another action is tried.

This method converts initial uncertainty into directed early exploration without an explicit random exploration probability. It is particularly useful for short experiments in stationary environments. However, it has limitations:

• it provides mainly a transient exploration bonus;
• it can fail when rewards are noisy or unbounded;
• the initial value is not a neutral prior and can produce excessive exploration;
• it does not automatically respond to later changes in the environment.

Optimistic initialization should be paired with an appropriate update rule and a realistic reward scale.

4. Upper Confidence Bound Methods

UCB methods select actions according to an optimistic estimate consisting of an empirical mean plus an uncertainty bonus. A common form for bounded rewards is

\[

U_t(a)=Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}},

\]

where \(t\ge 2\), \(N_t(a)>0\), and \(c>0\) controls the exploration strength. The action with the largest \(U_t(a)\) is selected. Actions never sampled are normally selected first, or assigned infinite index.

The bonus decreases as an action is sampled more often and increases slowly with time. Thus, UCB explores actions with high uncertainty while exploiting actions with high observed means. The logarithm means that an action must become increasingly competitive to receive further samples.

A classical UCB1 index is

\[

Q_t(a)+\sqrt{\frac{2\ln t}{N_t(a)}},

\]

under bounded-reward assumptions and a particular theoretical analysis. The tunable form with \(c\) is often more convenient in engineering practice. The exact coefficient should not be treated as universally optimal.

Why the Confidence Bonus Works

For an action sampled \(n\) times, the sample mean becomes more reliable as \(n\) increases. Concentration inequalities imply that large deviations between the sample mean and the true mean become less likely as the sample size grows. UCB adds a confidence radius to account for this uncertainty. The algorithm is optimistic because it evaluates an action according to a plausible upper estimate of its value.

UCB is most appropriate when rewards are reasonably stationary and bounded or have controlled tails. For heavy-tailed rewards, robust estimators may be required. For changing environments, sliding-window or discounted UCB variants can be more suitable.

5. Thompson Sampling

Thompson sampling is a Bayesian or Bayesian-inspired method. It maintains a posterior distribution over each action's unknown reward parameter, samples one plausible parameter for every action, and selects the action with the largest sampled value.

For Bernoulli rewards, let action \(a\) have success probability \(\theta_a\). A Beta prior is conjugate to the Bernoulli likelihood:

\[

\theta_a\sim\operatorname{Beta}(\alpha_a,\beta_a).

\]

After observing \(s_a\) successes and \(f_a\) failures, the posterior is

\[

\theta_a\mid\text{data}\sim\operatorname{Beta}(\alpha_a+s_a,\beta_a+f_a).

\]

At each round, sample \(\widetilde\theta_a\) from each posterior and choose

\[

A_t\in\arg\max_a \widetilde\theta_a.

\]

The posterior sample represents one plausible world. Actions with uncertain posteriors sometimes generate high samples and are explored; actions with strong evidence of high reward are selected frequently.

Worked Example: Beta-Bernoulli Updating

Two advertisements have independent uniform priors, \(\operatorname{Beta}(1,1)\). Advertisement A has produced 7 clicks in 10 displays, so its posterior is \(\operatorname{Beta}(8,4)\), with posterior mean \(8/(8+4)=0.667\). Advertisement B has produced 4 clicks in 5 displays, giving \(\operatorname{Beta}(5,2)\), with posterior mean \(5/7\approx0.714\).

The posterior mean alone would favor B, but Thompson sampling does not simply choose the larger posterior mean. It samples from both distributions. B may be selected often because its mean is higher, while A may still be selected because its posterior has substantial uncertainty. The method therefore balances evidence and uncertainty probabilistically.

The prior is consequential. A strongly informative prior can accelerate learning when justified by reliable historical evidence, but can also encode bias. Prior choices must be documented and monitored.

6. Regret and Evaluation

The principal theoretical measure is regret. The expected instantaneous regret at time \(t\) is

\[

r_t=\mu^*-\mathbb E[\mu_{A_t}],

\]

and cumulative expected regret over horizon \(T\) is

\[

R_T=\sum_{t=1}^{T}(\mu^*-\mathbb E[\mu_{A_t}]).

\]

An equivalent expression uses the suboptimality gap \(\Delta_a=\mu^*-\mu_a\):

\[

R_T=\sum_{a=1}^{K}\Delta_a\,\mathbb E[N_T(a)].

\]

This assumes fixed action means and defines regret relative to always choosing an optimal action. Pseudo-regret uses expected means and is distinct from realized regret, which compares actual random rewards with a benchmark. Regret is not the same as total reward: two policies can have similar total reward but different patterns of risk and learning.

For empirical studies, report cumulative reward, regret when a credible benchmark exists, action-selection frequencies, confidence intervals, and performance over time. Offline evaluation is difficult because logged data usually reflect an earlier policy. Counterfactual evaluation requires assumptions such as adequate coverage, where actions of interest have nonzero probability of appearing in the logs.

7. Contextual Bandits

Ordinary bandits assume that all decisions share the same reward distribution. A contextual bandit observes a context \(X_t\), selects an action, and observes reward only for that action. Context may include device type, time, location, user history, or product characteristics.

The expected reward becomes action- and context-dependent:

\[

\mu(x,a)=\mathbb E[R_t\mid X_t=x,A_t=a].

\]

The goal is to choose actions with high expected reward for the current context, not merely actions that are globally popular. A simple model assumes linear rewards:

\[

\mathbb E[R_t\mid x,a]=x_a^\top\theta_a,

\]

where \(x_a\) is a feature vector and \(\theta_a\) is an unknown parameter. Linear-UCB methods use a regression estimate plus a confidence bonus; contextual Thompson sampling samples plausible parameter values and acts greedily under those samples.

Contextual bandits differ from supervised learning because the learner observes the reward only for the selected action. They also differ from full reinforcement learning because actions do not ordinarily change a multi-step state transition or determine delayed rewards. Contextual bandits are appropriate when decisions are repeated, feedback is relatively immediate, and the primary consequence is the selected action's reward.

Feature quality is critical. Context variables can improve personalization but may encode protected characteristics or proxies for them. Models should be tested for disparate performance, unequal exposure, and feedback loops.

8. Practical Experimentation Strategy

A professional bandit deployment should begin with a clearly specified decision and outcome. Define the action set, reward window, attribution rule, horizon, constraints, and safety limits before tuning an algorithm.

A sound workflow includes:

1. Establish a baseline. Compare against the current production policy, a uniform policy, or a strong fixed heuristic.

2. Start with safe exploration. Use traffic caps, eligibility rules, conservative actions, and human review where harm is plausible.

3. Instrument correctly. Log context, selected action, policy probability, reward outcome, timestamps, model version, and exclusion rules.

4. Protect randomization. Do not allow operational staff or hidden ranking rules to selectively override treatment assignment without logging it.

5. Monitor delayed outcomes. Immediate clicks may conflict with retention, satisfaction, revenue quality, or safety.

6. Detect nonstationarity. Track reward distributions, action availability, seasonality, and changes in user behavior.

7. Evaluate uncertainty. Use bootstrap intervals or appropriate sequential methods; do not stop solely because a short-term estimate looks favorable.

8. Review subgroup outcomes. Examine performance and exposure across relevant populations.

9. Plan rollback. A production system requires a tested fallback policy and alert thresholds.

Exploration should be proportional to the value of information and the cost of mistakes. In a low-risk recommendation test, more exploration may be acceptable. In medical, financial, employment, or safety-critical applications, exploration must be constrained by domain expertise and regulation.

9. Illustrative Case: News-Headline Selection

Background

A digital news service wants to select one of four headlines for each reader. A click is observed immediately, but the organization also values reading time and subscription retention. The platform has contextual information such as device type, referral source, and broad content category.

Problem

A greedy system initially favors a sensational headline that receives high click-through rates from early traffic. It rarely tests alternative headlines, so it cannot determine whether the apparent advantage is due to chance or whether sensational headlines reduce long-term satisfaction.

Analysis

An epsilon-greedy policy would guarantee some testing but might select clearly unsuitable headlines for users. A UCB method could prioritize headlines with strong performance and limited data. A contextual bandit could learn that different headlines work for different reader segments. However, click feedback alone creates a proxy-reward problem: optimizing clicks may encourage misleading or low-quality content.

Approach

The service introduces a constrained contextual Thompson-sampling system. It uses a model for immediate engagement and a separate delayed-quality metric. New headlines receive a minimum but capped exposure. Headlines violating editorial standards are excluded. The logging system records the probability with which each headline was selected, enabling later inverse-propensity evaluation. A human-reviewed baseline remains available.

Outcome

The system improves click-through rate moderately while preserving reading time and reducing extreme headline exposure. Some segments receive different headlines, but fairness and editorial audits identify that the model under-explores stories relevant to minority-language readers because historical data contain fewer observations for them. Additional targeted data collection and editorial constraints are introduced.

Learning Points

The case illustrates that algorithmic exploration is not merely a mathematical issue. Reward definition, delayed effects, logging, coverage, content governance, and subgroup analysis determine whether a bandit improves the real objective. A higher immediate reward can be harmful if it optimizes a misleading proxy.

10. Limitations, Ethics, and Governance

Bandit theory often assumes stationary rewards, independent observations, known action availability, and a clearly defined objective. Real systems violate these assumptions. Users influence one another, actions may affect future demand, rewards may be delayed, and competitors may react. Confidence estimates can therefore be overconfident.

Exploration can expose users to inferior or risky choices. In healthcare, a poorly designed policy could harm patients; in lending, it could distribute opportunities unfairly; in education, it could repeatedly assign ineffective content to struggling learners. Governance should include documented objectives, risk classification, approval procedures, privacy protection, fairness assessment, audit logs, monitoring, and rollback mechanisms.

Personal data used as context require lawful collection, purpose limitation, access controls, and retention policies. Sensitive attributes should not be used casually, and excluding them does not eliminate discrimination because proxy variables may remain. Human oversight is especially important where rewards represent welfare, rights, or access to essential services.

11. Choosing Among Methods

• Greedy: suitable when estimates are already reliable or exploration is externally controlled; vulnerable to early errors.
• Epsilon-greedy: simple and robust; requires choosing an exploration rate and may explore obviously poor actions.
• Optimistic initialization: effective for initial exploration in stationary problems; sensitive to the chosen initial scale.
• UCB: principled uncertainty-directed exploration; depends on assumptions and confidence calibration.
• Thompson sampling: often strong empirically and naturally balances uncertainty; depends on a suitable probabilistic model or approximation.
• Contextual methods: appropriate when observable user or environmental features genuinely explain reward differences; require careful feature, bias, and coverage management.

No algorithm should be selected from benchmark results alone. The decision should reflect risk, feedback delay, nonstationarity, interpretability, computational resources, and the cost of exploration.

Chapter Summary

Multi-armed bandits model repeated action selection with uncertain rewards and no explicit multi-step state transition. Their central challenge is balancing exploration, which improves knowledge, with exploitation, which uses current estimates. Greedy policies exploit but may become prematurely committed; epsilon-greedy policies introduce explicit random exploration; optimistic initialization encourages early exploration through high initial values; UCB adds an uncertainty bonus to empirical means; and Thompson sampling explores by sampling plausible reward parameters from posterior distributions.

Regret measures the cost of failing to select an optimal action and provides a foundation for theoretical and empirical comparison. Contextual bandits extend the model by conditioning decisions on observed features, making them useful for personalization and adaptive decision systems. Practical deployment requires reliable logging, safe experimentation, delayed-outcome monitoring, subgroup analysis, and rollback plans. Ethical governance is essential because exploration can impose real costs and because optimizing a proxy reward may produce harmful outcomes.

Key Terms

Multi-armed bandit: A repeated decision problem with multiple actions and uncertain reward distributions.

Arm: One available action in a bandit problem.

Reward: Feedback received after selecting an action.

Action-value estimate: An estimate of an action's expected reward.

Exploration: Selecting actions to gain information.

Exploitation: Selecting the action currently believed to be best.

Greedy policy: A policy that selects an action with the highest estimated value.

Epsilon-greedy: A policy that explores randomly with probability epsilon and exploits otherwise.

Optimistic initialization: Assigning high initial action values to encourage exploration.

UCB: An upper-confidence-bound method that combines estimated value with an uncertainty bonus.

Confidence bonus: An added term representing uncertainty about an action's value.

Thompson sampling: Selecting actions using samples from posterior or approximate posterior distributions.

Contextual bandit: A bandit whose reward depends on an observed context.

Regret: The loss relative to a benchmark, commonly the optimal expected action.

Pseudo-regret: Expected regret expressed using action means rather than realized reward noise.

Stationarity: The assumption that an action's reward distribution remains stable over time.

Nonstationarity: Change in reward distributions, users, or environments over time.

Coverage: The extent to which logged data include actions needed for counterfactual evaluation.

Delayed reward: Feedback observed after a time lag rather than immediately.

Counterfactual evaluation: Estimating how a policy would have performed using data generated by another policy.

Review Questions

Short Answer Questions

1. What is the exploration–exploitation trade-off in a multi-armed bandit?

2. Why can a purely greedy policy fail after an unlucky initial observation?

3. What roles do \(Q_t(a)\) and \(N_t(a)\) play in bandit learning?

4. How does Thompson sampling explore uncertain actions?

5. What distinguishes a contextual bandit from an ordinary bandit?

Long Answer Questions

1. Compare epsilon-greedy, optimistic initialization, UCB, and Thompson sampling in terms of exploration mechanism, assumptions, and limitations.

2. Derive the regret expression \(R_T=\sum_a\Delta_a\mathbb E[N_T(a)]\) and explain its interpretation.

3. Explain why offline evaluation of a new bandit policy requires action-propensity information and adequate coverage.

4. Discuss how nonstationarity affects sample-average estimates and propose practical adaptations.

5. Design a governance framework for a bandit system used in a high-impact domain.

Analytical / Application Questions

1. Three actions have estimated means 0.4, 0.6, and 0.5. With \(\varepsilon=0.15\) and uniform random exploration, calculate the probability of selecting the greedy action and each nongreedy action.

2. A Bernoulli action has a Beta(2,3) prior and observes 6 successes and 4 failures. Compute its posterior parameters and posterior mean. Explain how Thompson sampling would use this posterior.

3. Design a contextual-bandit experiment for recommending educational exercises. Specify the context, actions, reward, exploration safeguards, logging requirements, and fairness checks.

Multiple Choice Questions with Answers

Question 1

What is the main purpose of exploration in a multi-armed bandit?

A. To guarantee selection of the action with the highest immediate estimate

B. To gather information about uncertain actions

C. To eliminate all reward variability

D. To avoid updating action-value estimates

Correct Answer: B. To gather information about uncertain actions

Question 2

Under epsilon-greedy selection with K actions, what happens with probability epsilon?

A. The action with the lowest estimate is selected

B. The action with the highest estimate is selected twice

C. An exploratory action is selected, commonly uniformly at random

D. The policy stops learning

Correct Answer: C. An exploratory action is selected, commonly uniformly at random

Question 3

Which expression is a common UCB action index?

A. Q(a) minus c times the uncertainty term

B. Q(a) plus c sqrt(ln(t)/N(a))

C. N(a) divided by Q(a)

D. epsilon times the reward variance only

Correct Answer: B. Q(a) plus c sqrt(ln(t)/N(a))

Question 4

What does optimistic initialization do?

A. Sets initial action values high to encourage early exploration

B. Sets all rewards permanently to one

C. Removes the need for reward observations

D. Guarantees optimality in nonstationary environments

Correct Answer: A. Sets initial action values high to encourage early exploration

Question 5

A Beta(1,1) prior observes 7 successes and 3 failures. What is the posterior distribution?

A. Beta(1,1)

B. Beta(7,3)

C. Beta(8,4)

D. Beta(3,7)

Correct Answer: C. Beta(8,4)

Question 6

What is the defining action-selection step in Thompson sampling?

A. Always selecting the action with the largest posterior mean

B. Sampling plausible parameters and selecting the action best under those samples

C. Selecting actions in a fixed alphabetical order

D. Choosing only actions that have never been sampled

Correct Answer: B. Sampling plausible parameters and selecting the action best under those samples

Question 7

If the best expected reward is 0.8 and an action's expected reward is 0.5, what is its suboptimality gap?

A. 0.3

B. 0.5

C. 0.8

D. 1.3

Correct Answer: A. 0.3

Question 8

What additional information does a contextual bandit use when selecting an action?

A. Only the total number of previous rounds

B. An observed context describing the current decision situation

C. The rewards of every unselected action

D. A complete future trajectory

Correct Answer: B. An observed context describing the current decision situation

Question 9

Why is click-through rate alone potentially problematic as a reward in the news-headline case?

A. Clicks can never be measured

B. It may encourage clicks while reducing quality or long-term satisfaction

C. It is always lower than reading time

D. It prevents all contextual modeling

Correct Answer: B. It may encourage clicks while reducing quality or long-term satisfaction

Question 10

If an action has been selected many times, how does the standard UCB uncertainty bonus generally change, holding time fixed?

A. It increases without limit

B. It decreases as the action count increases

C. It becomes equal to the reward mean

D. It changes sign

Correct Answer: B. It decreases as the action count increases