1 Multi-armed Bandits

1.1 Introduction

The multi-armed bandit problem has been actively studied in various fields, including statistics and reinforcement learning. The name “multi-armed bandit” comes from the analogy of a gambler at a row of slot machines (one-armed bandits), each with an unknown probability of a payout. The gambler wants to maximize their cumulative reward over a series of plays by choosing which machines to play.

The key challenge in the multi-armed bandit problem is the trade-off between exploration and exploitation. The gambler must decide whether to explore machines to gather more information about their rewards or to exploit a machine with the highest estimated expected reward.

The multi-armed bandit problem has a wide range of applications.

Clinical Trials: In clinical trials, researchers may want to test multiple treatments for a disease. Each treatment can be thought of as an arm of the bandit, and the goal is to find the treatment that provides the best outcome for patients.
Online Advertising: In online advertising, advertisers may want to test multiple ads to see which one performs the best. Each ad can be thought of as an arm of the bandit, and the goal is to find the ad that generates the most clicks or conversions.
Recommendation Systems: In recommendation systems, the goal is to recommend items that users are likely to enjoy. Each item can be thought of as an arm of the bandit, and the goal is to find the items that users are most likely to engage with.
Hyperparameter Tuning: In machine learning, hyperparameter tuning is the process of finding the best hyperparameters for a model. Each set of hyperparameters can be thought of as an arm of the bandit, and the goal is to find the hyperparameters that result in the best model performance.

These applications can involve different objectives. Maximizing expected cumulative reward concerns the rewards earned throughout learning, whereas best-arm identification concerns the quality of the option recommended at the end. Hyperparameter tuning often uses the latter objective. This chapter focuses on maximizing expected cumulative reward.

1.2 Notation

k: Number of actions
n: Number of time steps
t \in \{1, 2, \dots, n\}: Time step
A_t: Action at time t
R_t: Reward at time t
q_*(a): Expected reward for taking action a
Q_t(a): Estimated value of action a before the action at time t is selected
N_t(a): Number of times action a has been selected before time t

1.3 The Multi-armed Bandit Problem

Consider the multi-armed bandit problem with k actions. A decision-maker plays the game for n rounds. In each round t = 1, 2, \dots, n, the agent selects an action A_t from a set of actions \mathcal{A} = \{1, 2, \dots, k\} and receives a reward R_t \in \mathbb{R}. The sequence of actions and rewards can be represented as

A_1, R_1, A_2, R_2, \dots, A_n, R_n.

The decision-maker chooses action A_t based on the history H_{t-1} = \{A_1, R_1, A_2, R_2, \dots, A_{t-1}, R_{t-1}\}. Define a policy \pi as a mapping from the history to a probability distribution over actions. One common objective of the multi-armed bandit problem is to maximize the total reward over the n rounds, which is \sum_{t=1}^{n} R_t.

We assume that the rewards for each action are IID (independent and identically distributed) draws from an unknown distribution. There are also other bandit settings that allow reward distributions to change over time or depend on an observed context. We will discuss these settings in later chapters.

Try it yourself

Before reading on, play the two-armed bandit warm-up to experience this trade-off. You choose between two slot machines whose average payouts are unknown, and you decide for yourself how to compare them.

1.4 Expected Reward and Estimated Reward

Define q_*(a) as the expected reward for taking action a, i.e.,

q_*(a) = \mathbb{E} \left[ R_t | A_t = a \right].

If the true action values were known, it would be optimal to select any action a_* \in \arg \max_a q_*(a) at every time step. However, since the reward distributions are unknown, we cannot directly compute q_*(a). Thus, we need to find a way to estimate q_*(a).

Let Q_t(a) be the estimated value of action a at time t. A simple idea is to use the sample average of rewards obtained from action a up to time t-1:

Q_t(a) = \frac{\sum_{i=1}^{t-1} R_i \mathbb{I} \left\{ A_i = a \right\}}{N_t(a)}, \qquad N_t(a) > 0,

where \mathbb{I} \left\{ A_i = a \right\} is an indicator function that is equal to 1 if A_i = a and 0 otherwise. Here, N_t(a) = \sum_{i=1}^{t-1} \mathbb{I} \left\{ A_i = a \right\} is the number of times action a has been taken up to time t-1, and the numerator is the sum of rewards obtained from action a up to time t-1. When N_t(a)=0, the sample average is undefined, so we use an initial estimate such as Q_t(a)=0 instead.

1.5 Incremental Implementation

Let R_n denote the reward from its nth selection, and let Q_n denote its estimated value after n-1 selections. Thus, for n \ge 2, Q_n is the average of R_1,\dots,R_{n-1}, while Q_1 is an initial estimate. After observing R_n, we update the estimate using

Q_{n+1} = Q_n + \frac{1}{n} \left( R_n - Q_n \right).

Proof. For n \ge 2,

\begin{align*} Q_{n+1} & = \frac{R_1 + R_2 + \dots + R_{n}}{n} \\ & = \frac{1}{n} \sum_{i=1}^{n} R_i \\ & = \frac{1}{n} \left( R_n + \sum_{i=1}^{n-1} R_i \right) \\ & = \frac{1}{n} \left( R_n + (n-1) \frac{R_1 + R_2 + \dots + R_{n-1}}{n-1} \right) \\ & = \frac{1}{n} \left( R_n + (n-1) Q_n \right) \\ & = Q_n + \frac{1}{n} \left( R_n - Q_n \right) \\ \end{align*}

For n=1, the update gives Q_2 = Q_1 + (R_1-Q_1) = R_1 for any initial estimate Q_1, so the formula also holds for the first observation.

The incremental implementation only needs to store a current estimate and a selection count for each action. When a new reward arrives, we first increment that action’s count and then use the updated count as the denominator in the update.

Now, we can use the incremental implementation to estimate the expected reward for each action. The next question is how to choose the action in each period.

1.6 Exploration and Exploitation

Remember that the objective in this chapter is to maximize the cumulative reward over T rounds. To achieve this objective, we need to

explore the environment to estimate q_*(a) and
exploit the estimated values to choose actions with high expected rewards.

How should we balance exploring actions to improve our estimates of q_*(a) against exploiting an action with the highest estimated value to obtain rewards now? This is known as the exploration-exploitation dilemma.

The \epsilon-greedy policy is a simple policy that balances exploration and exploitation. In this policy, \epsilon is a probability in the range [0, 1]. With probability \epsilon, the agent chooses uniformly at random from all k actions (exploration), and with probability 1-\epsilon, the agent chooses an action with the highest estimated value (exploitation), breaking ties uniformly at random. The exploration branch can therefore also select a greedy action. Small values such as 0.1 or 0.01 are common choices for \epsilon.

1.7 A Simple Bandit Algorithm

We have discussed the incremental implementation of the sample average and the \epsilon-greedy policy. Now, we can combine these methods to create a simple bandit algorithm. The pseudocode is as follows:

\begin{algorithm} \caption{A Simple Bandit Algorithm} \begin{algorithmic} \For{$a = 1, 2, \dots, k$} \State $Q(a) \leftarrow 0$ \State $N(a) \leftarrow 0$ \EndFor \For{$t = 1, 2, \dots, T$} \State Choose $A_t$ using the $\epsilon$-greedy policy based on $Q$ \State $R_t \leftarrow \texttt{bandit}(A_t)$ \State $N(A_t) \leftarrow N(A_t) + 1$ \State $Q(A_t) \leftarrow Q(A_t) + \frac{1}{N(A_t)} \left( R_t - Q(A_t) \right)$ \EndFor \end{algorithmic} \end{algorithm}

Initially, we set the stored estimate Q(a) and selection count N(a) for each action to 0. At the start of period t, these correspond to Q_t(a) and N_t(a). We choose A_t using the \epsilon-greedy policy and receive R_t. We then increment N(A_t) and update Q(A_t) using this new count. The resulting stored values correspond to N_{t+1}(a) and Q_{t+1}(a); values for unselected actions remain unchanged.

Play again with the algorithm

Play the two-armed bandit game. It shows N(a) and Q(a) after every pull, marks each pull as greedy or exploratory, and compares your choices with the \epsilon-greedy algorithm on the same two machines.

1.8 Python Implementation

1.8.1 Multi-armed Bandit Problem

The experiment below compares three \epsilon-greedy policies. Within each run, all policies use the same true action values, but each agent learns from its own sampled rewards. ?fig-bandit-average-reward-vs-steps shows the reward at each time step averaged across 2,000 runs.

# ```{python}
#| label: fig-bandit-average-reward-vs-steps
#| fig-cap: "Average Reward vs. Steps"
#| echo: true

import numpy as np
import matplotlib.pyplot as plt


class GaussianBandit:
    """A stationary bandit with Gaussian rewards of variance 1."""

    def __init__(self, true_values, rng):
        self.true_values = np.array(true_values, dtype=float, copy=True)
        if self.true_values.ndim != 1 or self.true_values.size == 0:
            raise ValueError("true_values must be a nonempty one-dimensional array.")
        self.k = self.true_values.size
        self.rng = rng

    def pull(self, action):
        return self.rng.normal(loc=self.true_values[action], scale=1.0)


class EpsilonGreedyAgent:
    """Estimate action values using sample averages and select actions epsilon-greedily."""

    def __init__(self, bandit, epsilon, rng):
        if not 0 <= epsilon <= 1:
            raise ValueError("epsilon must be between 0 and 1.")
        self.bandit = bandit
        self.epsilon = epsilon
        self.rng = rng
        self.k = bandit.k
        self.Q = np.zeros(self.k)
        self.N = np.zeros(self.k, dtype=int)

    def select_action(self):
        if self.rng.random() < self.epsilon:
            return self.rng.integers(self.k)

        # Break ties randomly among actions with the highest estimated value.
        greedy_actions = np.flatnonzero(self.Q == self.Q.max())
        return self.rng.choice(greedy_actions)

    def run(self, steps):
        """Continue learning for the given steps and return this call's rewards."""
        rewards = np.zeros(steps)
        for t in range(steps):
            action = self.select_action()
            reward = self.bandit.pull(action)

            # Update the selected action's count and sample-average value.
            self.N[action] += 1
            self.Q[action] += (reward - self.Q[action]) / self.N[action]
            rewards[t] = reward
        return rewards


if __name__ == "__main__":
    # Use separate random streams for problem instances, rewards, and actions.
    rng = np.random.default_rng(0)
    instance_rng, reward_rng, action_rng = rng.spawn(3)

    k = 10
    steps = 1000
    epsilon_list = [0, 0.1, 0.01]
    num_runs = 2000

    # Store rewards with axes: policy, run, time step.
    rewards = np.zeros((len(epsilon_list), num_runs, steps))
    for run_index in range(num_runs):
        # Compare all policies on the same problem, each with a fresh agent.
        true_values = instance_rng.normal(loc=0.0, scale=1.0, size=k)
        for i, epsilon in enumerate(epsilon_list):
            bandit = GaussianBandit(true_values, reward_rng)
            agent = EpsilonGreedyAgent(bandit, epsilon, action_rng)
            rewards[i, run_index, :] = agent.run(steps)

    # Average across runs at each time step, rather than across time steps.
    mean_rewards = rewards.mean(axis=1)
    time_steps = np.arange(1, steps + 1)
    plt.figure(figsize=(10, 6))
    for i, epsilon in enumerate(epsilon_list):
        plt.plot(
            time_steps,
            mean_rewards[i],
            label=rf"$\epsilon = {epsilon}$",
        )
    plt.xlabel("Steps", fontsize=14)
    plt.ylabel("Average Reward", fontsize=14)
    plt.title("Average Reward vs. Steps", fontsize=16)
    plt.tick_params(axis="both", which="major", labelsize=12)
    plt.legend(fontsize=12)
    plt.show()

Example 1.1 Figure 1.1 shows a violin plot for a 10-armed bandit. The x-axis represents the 10 different actions, and the y-axis represents the reward distribution for each action. The width of the violin plot at each y-value represents the density of the reward distribution at that value. The wider the violin plot, the more likely it is to observe a reward at that value.

Figure 1.1: Violin plot for a 10-armed bandit

1.9 Upper Confidence Bound

1.9.1 Hoeffding inequality

P\left(\mu \geq \hat{\mu} + \epsilon\right) \leq \exp\left(- \frac{N\epsilon^2}{2 \delta^2}\right)

Let \delta \in (0, 1) be a confidence level.

\delta = \exp\left(- \frac{N\epsilon^2}{2 \delta^2}\right)

We have

\epsilon = \sqrt{\frac{2 \delta^2 \ln(1/\delta)}{N}}

Therefore,

P\left(\mu \geq \hat{\mu} + \sqrt{\frac{2 \delta^2 \ln(1/\delta)}{N}}\right) \leq \delta

1.9.2 UBC1

A_t = \arg\max_{a \in \mathcal{A}} \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]

Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} is the confidence width.

1.10 Summary

The expected reward q_*(a) can be estimated using the sample average.
The incremental implementation can be used to update the estimated value without storing all the rewards and actions.
The \epsilon-greedy policy balances exploration and exploitation.
We introduce a simple bandit algorithm by combining the incremental implementation and the \epsilon-greedy policy.
UCB1 guides exploration with a confidence bonus and uses the same incremental value update.

1.11 Exercises

Exercise 1.1 (Decreasing \epsilon) ?exr-epsilon-greedy-regret shows that \epsilon-greedy with a fixed \epsilon > 0 keeps exploring at the same rate even after its estimates have become accurate. A natural remedy is to explore often at the beginning, when the estimates are poor, and less often later. Modify Algorithm 1 so that round t uses the \epsilon-greedy policy with

\epsilon_t = \min\left\{1, \frac{c}{t}\right\},

where c > 0 is a constant.

Write a class DecayingEpsilonGreedyAgent with the same interface as EpsilonGreedyAgent, except that it takes a function epsilon_schedule that returns \epsilon_t for round t instead of a fixed epsilon.
Repeat the experiment in ?fig-bandit-average-reward-vs-steps (k = 10, 1,000 steps, 2,000 runs) with c = 1, 10, 100 and with the fixed \epsilon = 0.1. Plot the average reward against the steps.
Because \epsilon_t does not depend on the history, the expected number of rounds in which the agent explores during the first n rounds is \sum_{t=1}^{n} \epsilon_t. Compute this sum for each of the four policies with n = 1{,}000. Use the results to explain your plot: why does c = 1 level off at a low reward, and why does c = 100 start slowly?