Multi-Armed Bandit Problem #

The Multi-Armed Bandit (MAB) problem is the simplest setting for studying decision-making under uncertainty.

An agent repeatedly chooses one of \( k \) actions. Each action produces a numerical reward drawn from an unknown distribution. The objective is to maximise the expected total reward over time.

The k-Armed Bandit Problem ☆ #

At every time step:

1. choose an action from \( k \) possible actions;
2. receive a numerical reward;
3. update what is known about the selected action;
4. choose again.

Unlike a full Markov Decision Process, a basic non-associative bandit has no changing state representation. The same decision problem is faced repeatedly.

flowchart LR
    C[Choose one of k actions] --> R[Observe reward]
    R --> U[Update action knowledge]
    U --> C

    style C fill:#E1F5FE
    style R fill:#C8E6C9
    style U fill:#FFF9C4

True Action Value ☆ #

The true value of action \( a \) is its expected reward.

Where:

• \( A_t \) is the action selected at time \( t \) ;
• \( R_t \) is the reward received;
• \( q_*(a) \) is the unknown true action value.

If all true action values were known, the solution would be simple: always choose the action with the highest value.

In practice, the agent must estimate them.

Estimated Action Value ☆ #

Let \( Q_t(a) \) denote the estimated value of action \( a \) at time \( t \) .

Using the sample-average method:

This is the average of the rewards observed on previous occasions when action \( a \) was selected.

Greedy Action Selection ☆ #

A greedy method chooses the action with the highest current estimate.

Advantage #

• It exploits the best action currently known.

Limitation #

• Early estimates may be inaccurate.
• An apparently poor action may actually be optimal.
• A greedy method may never gather the evidence needed to correct its mistake.

Exploration versus Exploitation ☆ #

This is not a one-time decision. The agent must manage the trade-off throughout learning.

Epsilon-Greedy Action Selection ☆ #

An epsilon-greedy policy behaves greedily most of the time and selects a random action with probability \( \varepsilon \) .

The random choice is made from all actions, so the greedy action can also be selected during the exploratory part.

Probability of Selecting the Greedy Action ☆ #

With \( k \) actions and one unique greedy action:

For two actions and \( \varepsilon = 0.5 \) :

The 10-Armed Testbed #

The slides compare greedy and epsilon-greedy methods on a 10-armed testbed.

The qualitative result is:

• a fully greedy method improves quickly but may settle on a suboptimal action;
• a small amount of exploration improves long-term performance;
• in the shown experiment, \( \varepsilon = 0.1 \) achieves a higher average reward and a higher percentage of optimal actions than the greedy method;
• \( \varepsilon = 0.01 \) explores more slowly and therefore improves more gradually.

The best value of ( \varepsilon )

depends on reward uncertainty, the length of the task, and whether action values change over time.

Incremental Sample-Average Update ☆ #

Recomputing a complete average after every reward is inefficient. The estimate can be updated incrementally.

This has the general form:

The term \( R_n-Q_n \) is the estimation error.

Incremental Epsilon-Greedy Bandit Algorithm ☆ #

Initialise, for each action a:
    Q(a) = 0
    N(a) = 0

Repeat:
    With probability 1 - epsilon:
        choose an action with the largest Q(a)
    Otherwise:
        choose a random action

    Observe reward R
    N(a) = N(a) + 1
    Q(a) = Q(a) + (1 / N(a)) * (R - Q(a))

Minimal Python Implementation #

import random
from typing import Sequence


def select_action(values: Sequence[float], epsilon: float) -> int:
    """Select an action using epsilon-greedy exploration."""
    if not 0.0 <= epsilon <= 1.0:
        raise ValueError("epsilon must be between 0 and 1")
    if not values:
        raise ValueError("values must not be empty")

    if random.random() < epsilon:
        return random.randrange(len(values))

    best_value = max(values)
    best_actions = [i for i, value in enumerate(values) if value == best_value]
    return random.choice(best_actions)


def update_sample_average(old_value: float, reward: float, count: int) -> float:
    """Update an action value after its count-th observation."""
    if count <= 0:
        raise ValueError("count must be positive")
    return old_value + (reward - old_value) / count

Stationary and Non-Stationary Bandits ☆ #

Stationary Problem #

The reward distribution of each action remains fixed over time.

The sample-average method is suitable because all observations remain equally relevant.

Non-Stationary Problem #

The true action values change over time.

Older rewards may no longer describe the current problem, so recent observations should receive greater weight.

A constant step size is used:

Expanding the recursion gives an exponentially recency-weighted average:

Recent rewards receive larger weights than older rewards.

Sample Average versus Constant Step Size ☆ #

Optimistic Initial Values ☆ #

Instead of initialising every estimate to zero, the agent can begin with unrealistically high action values.

For example, setting every estimate to \( 5 \) makes the first rewards appear disappointing. The learner then switches between actions, causing several actions to be tried before estimates converge.

Benefits #

• encourages early exploration;
• simple to implement.

Limitations #

• depends on a suitable scale for the initial values;
• the effect is temporary for sample-average methods;
• with a constant step size, the initial bias can persist for longer;
• it is less reliable in non-stationary settings because it primarily encourages exploration near the start.

Upper-Confidence-Bound Action Selection ☆ #

Epsilon-greedy exploration treats non-greedy actions indiscriminately. Upper-Confidence-Bound (UCB) action selection instead prefers actions that are either promising or uncertain.

The two terms represent:

• \( Q_t(a) \) - estimated action value;
• \( c\sqrt{\ln(t)/N_t(a)} \) - uncertainty bonus.

An action selected infrequently has a larger uncertainty bonus. As it is selected more often, the bonus decreases.

UCB implements optimism in the face of uncertainty: an uncertain action is treated as potentially better until enough evidence is collected.

From Action Values to Action Preferences #

Value-based bandit methods estimate \( Q(a) \) . Gradient bandit methods instead learn a numerical preference \( H_t(a) \) for every action.

A softmax function converts preferences into probabilities.

Unlike hard argmax selection, softmax produces a differentiable stochastic policy and naturally supports exploration.

Gradient Bandit Update ☆ #

After choosing action \( A_t \) and receiving reward \( R_t \) , preferences are adjusted relative to a baseline \( \bar{R}_t \) .

For the selected action:

For every other action:

Interpretation #

• reward above the baseline increases the selected action’s preference;
• reward below the baseline decreases it;
• preferences of other actions move in the opposite direction;
• the baseline reduces variance and improves learning behaviour.

This is the bandit-gradient algorithm interpreted as stochastic gradient ascent on expected reward.

Associative Search and Contextual Bandits ☆ #

A basic bandit is non-associative: the agent repeatedly faces the same action-selection problem.

An associative or contextual bandit includes a situation or context. The best action may differ from one context to another.

Examples include:

• choosing an advertisement based on a user’s context;
• selecting a treatment based on patient features;
• recommending content based on current behaviour;
• selecting actions for different grid locations or operating conditions.

Contextual bandits form a bridge between simple bandits and full Markov Decision Processes.

Method Comparison ☆ #

Common Mistakes ☆ #

• Confusing the unknown true value ( q_*(a) )

with the estimate ( Q_t(a) )

.

• Assuming epsilon-greedy never selects the greedy action during random exploration.
• Using the sample-average update for a rapidly changing non-stationary problem without considering constant ( \alpha )

.

• Treating UCB’s uncertainty term as part of the estimated reward rather than an exploration bonus.
• Calling a contextual bandit a full MDP even though actions do not affect a sequence of future states in the same way.

Checklist ☆ #

You should be able to:

1. define the k-armed bandit problem;
2. distinguish \( q_*(a) \) from \( Q_t(a) \) ;
3. derive and apply the sample-average and incremental updates;
4. calculate epsilon-greedy action probabilities;
5. explain exploration versus exploitation;
6. compare stationary and non-stationary updates;
7. explain optimistic initial values;
8. interpret every term in the UCB equation;
9. derive softmax probabilities from action preferences;
10. explain the gradient bandit update and the role of the reward baseline;
11. distinguish non-associative from associative bandit tasks.

Key takeaway: Bandit methods learn which action to choose while simultaneously collecting the evidence needed to estimate action quality.

References #

1. Sutton and Barto, Reinforcement Learning: An Introduction, Chapter 2.
2. BITS Pilani Deep Reinforcement Learning course handout, Contact Session 2.
3. Supplied lecture slides on Multi-Armed Bandits, including action-value methods, non-stationarity, UCB, gradient bandits, and associative search.

Home | Deep Reinforcement Learning