Solving the Multi-Armed Bandit Problem from Scratch with Python: A Comprehensive Guide

Introduction

Imagine you‘re at a casino faced with a wall of slot machines, each with an unknown payout probability. How do you decide which machines to play, and in what order, to maximize your winnings? This is the essence of the multi-armed bandit problem, a classic challenge in reinforcement learning.

But the applications go far beyond gambling. Multi-armed bandit algorithms power many real-world systems including:

• Online advertising: Which ad should be shown to a user to maximize click-through rate?
• Clinical trials: What treatment should be given to a patient to maximize effectiveness?
• Game design: What rewards should be given to a player to keep them engaged?
• Network routing: What path should a data packet take to minimize latency?

At its core, the multi-armed bandit problem highlights the tradeoff between exploration (trying new actions to gather information) and exploitation (choosing the action that has performed best so far). Navigating this tradeoff is crucial for learning optimal behaviors in uncertain environments.

In this guide, we‘ll dive deep into the multi-armed bandit problem and show you how to implement a range of solutions from scratch in Python. Whether you‘re a beginner looking for an intro to reinforcement learning or an experienced practitioner seeking to sharpen your skills, this guide has something for you. Let‘s get started!

The Multi-Armed Bandit Problem

A multi-armed bandit can be thought of as a set of slot machines, each with an arm that can be pulled. Each arm has an unknown probability of giving a reward (e.g. a payout). The goal is to maximize the total reward earned through a series of pulls.

More formally, a multi-armed bandit consists of:

• A set of K actions (arms)
• Each action has an associated reward probability that is initially unknown
• At each timestep t, the agent selects an action a_t and receives a reward r_t
• The agent‘s goal is to maximize the cumulative reward over a sequence of T actions

The key challenge is that the agent does not know the optimal action upfront – it must learn through trial and error. If it greedily chooses the action with the highest observed reward, it may miss out on even better options. But if it explores too much, it may waste time on suboptimal actions. Finding the right balance is what makes this problem interesting.

Key Concepts

Before diving into solution strategies, let‘s define some key concepts:

Action-Value Function

The action-value function Q(a) represents the expected reward for taking action a. If the reward probabilities are known, then Q(a) is simply the probability of receiving a reward for action a. In practice, we estimate Q(a) based on the observed rewards.

Regret

Regret is the difference between the total reward actually earned and the reward that could have been earned by always selecting the optimal action. It quantifies the cost of not knowing the optimal strategy upfront. A good algorithm will minimize cumulative regret over time.

Solution Strategies

Now let‘s look at some common algorithmic approaches for tackling the multi-armed bandit problem.

Greedy Approach

The simplest strategy is to estimate Q(a) for each action based on the observed rewards, and then always choose the action with the highest estimate. This pure exploitation approach quickly converges on a single action, but offers no mechanism for exploration. It risks getting stuck on a suboptimal action forever.

Epsilon-Greedy

The epsilon-greedy strategy offers a simple way to balance exploration and exploitation. With probability epsilon, it chooses a random action. With probability 1-epsilon, it chooses the greedy action (the one with the highest Q estimate). The value of epsilon controls the exploration rate – higher values favor more exploration.

Softmax Exploration

Instead of choosing actions randomly when exploring, softmax exploration weights each action according to its Q estimate. The probability of choosing action a is proportional to exp(Q(a) / tau), where tau is a temperature parameter controlling the randomness. High temperatures cause all actions to be equiprobable, while low temperatures favor the highest-value actions.

Decayed Epsilon-Greedy

A variant of epsilon-greedy where the value of epsilon decays over time. This allows for more exploration early on, but gradually shifts towards exploitation as the estimates become more certain. A common decay schedule is epsilon = 1 / log(t+0.00001).

Upper Confidence Bound (UCB)

UCB algorithms choose actions based on a combination of the Q estimate and an uncertainty bonus that favors less-explored actions. The UCB1 algorithm chooses the action maximizing Q(a) + sqrt(2 log(t) / N(a)), where N(a) is the number of times action a has been selected so far. This encourages exploration of promising but uncertain actions. Over time, the uncertainty bonus decreases and the algorithm converges on the optimal action.

Stationary vs Non-Stationary Problems

The strategies above assume that the underlying reward probabilities remain constant over time. This is known as the stationary setting.

In many real-world problems, however, the optimal action may change over time. For example, user preferences for ads may evolve, or the payout of a slot machine may be adjusted periodically. These are examples of non-stationary problems.

To handle non-stationarity, the algorithms need a way to give more weight to recent rewards versus old ones. One approach is to use a constant step-size parameter alpha to update Q estimates:

Q(a) <- Q(a) + alpha * (r – Q(a))

This causes the estimates to adapt more quickly to changing rewards. The choice of alpha controls the balance between rapid adaptation (high alpha) and stability (low alpha).

Python Implementation

Now let‘s see how to implement these ideas in Python. We‘ll use the example of optimizing click-through rates for online ads.

Suppose we have 10 different ad variants, each with an unknown click probability. At each timestep, we select one ad to display to a user. If the user clicks the ad, we receive a reward of 1, otherwise a reward of 0. Our goal is to maximize the total number of clicks over time.

First, let‘s generate a synthetic dataset representing the results of 10,000 ad impressions:

import numpy as np

num_ads = 10
num_impressions = 10000
true_probs = np.random.uniform(0.01, 0.05, num_ads) 
data = np.random.rand(num_impressions, num_ads) < true_probs

Here data is a binary matrix where each row represents an impression and each column an ad. A value of 1 indicates the ad was clicked.

Now let‘s implement the epsilon-greedy strategy:

def epsilon_greedy(data, epsilon):
    num_impressions, num_ads = data.shape
    Q = np.zeros(num_ads)  # estimated action values
    N = np.zeros(num_ads)  # number of times each action was chosen

    rewards = []
    actions = []

    for i in range(num_impressions):
        if np.random.rand() < epsilon:
            action = np.random.randint(num_ads)  # explore      
        else:
            action = np.argmax(Q)  # exploit

        actions.append(action)
        reward = data[i, action]
        rewards.append(reward)

        N[action] += 1
        Q[action] += (reward - Q[action]) / N[action]  # running average

    return rewards, actions

And here‘s the UCB1 algorithm:

def ucb1(data):
    num_impressions, num_ads = data.shape
    Q = np.zeros(num_ads)  
    N = np.zeros(num_ads)

    rewards = []
    actions = []

    for i in range(num_impressions):
        if 0 in N:
            action = np.where(N == 0)[0][0]  # play each ad once
        else:
            U = np.sqrt(2 * np.log(i+1) / N)
            action = np.argmax(Q + U)  # UCB action selection

        actions.append(action)   
        reward = data[i, action]
        rewards.append(reward)

        N[action] += 1
        Q[action] += (reward - Q[action]) / N[action]

    return rewards, actions  

Let‘s run both algorithms and compare their cumulative rewards:

epsilon = 0.1
rewards_eg, actions_eg = epsilon_greedy(data, epsilon)
rewards_ucb, actions_ucb = ucb1(data)

print(f‘Total reward (epsilon-greedy): {sum(rewards_eg)}‘)
print(f‘Total reward (UCB1): {sum(rewards_ucb)}‘)

On this synthetic dataset, UCB1 typically earns a higher total reward than epsilon-greedy, since it more quickly identifies and exploits the optimal action. However, the performance of each algorithm can vary depending on the specific reward probabilities and number of impressions.

We can visualize the action selection over time for each algorithm:

import matplotlib.pyplot as plt

plt.figure(figsize=(12,4))

plt.subplot(1,2,1)
plt.plot(np.cumsum(rewards_eg))
plt.title(f‘Epsilon-Greedy (epsilon={epsilon})‘)
plt.xlabel(‘Impressions‘)
plt.ylabel(‘Cumulative Reward‘)

plt.subplot(1,2,2)  
plt.plot(np.cumsum(rewards_ucb))
plt.title(‘UCB1‘)
plt.xlabel(‘Impressions‘)

plt.tight_layout()
plt.show()

This shows how the cumulative reward grows over time for each approach. We can see that UCB1 tends to converge faster on the optimal action, leading to a higher slope in the later stages.

Conclusion

The multi-armed bandit problem teaches us a lot about the fundamental tradeoff between exploration and exploitation in sequential decision making. Simple algorithms like epsilon-greedy and UCB offer principled ways to navigate this tradeoff and converge on optimal actions over time.

Of course, there are many more strategies beyond what we‘ve covered here. Thompson Sampling, for instance, takes a Bayesian approach by maintaining a distribution over each action‘s value and sampling from these distributions to guide exploration. Gradient bandits optimize a parameterized policy using stochastic gradient ascent. And contextual bandits consider side information (features) when choosing actions, allowing for personalized decisions.

Whichever approach you choose, the key principles remain the same: balance exploring new actions with exploiting the best-performing ones, and adapt to change in non-stationary environments. By putting these ideas into practice, you can build smarter systems that continuously learn and improve.

We hope this guide has given you a solid foundation in multi-armed bandits and reinforcement learning. The code examples provide a starting point for experimenting with these algorithms on your own datasets and applications. Try varying the parameters, comparing performance, and extending the methods to more complex problems. Most importantly, have fun exploring and learning!

Further Reading

• Richard S. Sutton and Andrew G. Barto. "Reinforcement Learning: An Introduction" (2018)
• Tor Lattimore and Csaba Szepesvári. "Bandit Algorithms" (2020)
• Lilian Weng. "A Primer on Multi-Armed Bandits" (2021)
• Aurélien Garivier and Eric Moulines. "On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems" (2011)