Multi-Armed Bandit Problem

Other sources: * https://tor-lattimore.com/downloads/book/book.pdf by lattimore2020bandit by * Intro to Multi-Armed Bandits slivkins2019introduction @book{lattimore2020bandit, title={Bandit algorithms}, author={Lattimore, Tor and Szepesv{‘a}ri, Csaba}, year={2020}, publisher={Cambridge University Press} }

@article{slivkins2019introduction, title={Introduction to multi-armed bandits}, author={Slivkins, Aleksandrs and others}, journal={Foundations and Trends{\textregistered} in Machine Learning}, volume={12}, number={1-2}, pages={1–286}, year={2019}, publisher={Now Publishers, Inc.} }

@article{thompson1933likelihood, title={On the likelihood that one unknown probability exceeds another in view of the evidence of two samples}, author={Thompson, William R}, journal={Biometrika}, volume={25}, number={3-4}, pages={285–294}, year={1933}, publisher={Oxford University Press} }

Multi-Armed Bandit Problem#

Introduction#

The Multi-Armed Bandit (MAB) problem is a classical reinforcement learning problem that exemplifies the exploration-exploitation trade-off. The goal is to maximize the cumulative reward by choosing the best arm to pull at each time step.

Formal Definition#

A multi-armed bandit problem can be formally defined as follows:

Arms: A set of $K$ arms, where each arm $i$ provides a reward from an unknown probability distribution $P_i$.
Time Steps: The agent interacts with the bandit over a sequence of $T$ time steps.
Rewards: At each time step $t$, the agent selects an arm $a_t$ and receives a reward $r_t$ drawn from the distribution $P_{a_t}$.

The objective is to maximize the expected cumulative reward over $T$ time steps.

POssible applications; a crowdsourcing platform can improve the assignment of tasks, workers and prices

Key Concepts#

Exploration vs. Exploitation#

Exploration: Trying different arms to gather information about their reward distributions.
Exploitation: Selecting the arm with the highest known reward based on the information gathered so far.

Balancing these two aspects is crucial for achieving optimal performance in the MAB problem.

Regret#

Regret measures the difference between the cumulative reward obtained by the optimal strategy and the reward obtained by the algorithm. It is defined as:

\[ R(T) = T \mu^* - \sum_{t=1}^T \mu_{a_t} \]

where $\mu^*$ is the mean reward of the best arm, and $\mu_{a_t}$ is the mean reward of the arm chosen at time $t$.

Strategies for Multi-Armed Bandit Problems#

1. Epsilon-Greedy#

The epsilon-greedy strategy is one of the simplest approaches:

With probability $\epsilon$, select a random arm (exploration).
With probability $1 - \epsilon$, select the arm with the highest average reward observed so far (exploitation).

import numpy as np

class EpsilonGreedy:
    def __init__(self, n_arms, epsilon):
        self.n_arms = n_arms
        self.epsilon = epsilon
        self.counts = np.zeros(n_arms)
        self.values = np.zeros(n_arms)
    
    def select_arm(self):
        if np.random.rand() < self.epsilon:
            return np.random.randint(0, self.n_arms)
        else:
            return np.argmax(self.values)
    
    def update(self, chosen_arm, reward):
        self.counts[chosen_arm] += 1
        n = self.counts[chosen_arm]
        value = self.values[chosen_arm]
        self.values[chosen_arm] = ((n - 1) / n) * value + (1 / n) * reward

# Example usage
n_arms = 10
epsilon = 0.1
n_rounds = 1000

bandit = EpsilonGreedy(n_arms, epsilon)
rewards = np.random.rand(n_arms)  # Simulated rewards for each arm

for _ in range(n_rounds):
    chosen_arm = bandit.select_arm()
    reward = rewards[chosen_arm]
    bandit.update(chosen_arm, reward)

print("Estimated values:", bandit.values)

Estimated values: [0.70444882 0.06226676 0.98735776 0.94992464 0.69063516 0.28637876
 0.50889944 0.29081675 0.75176366 0.67070882]

Uppder Confidence Bound (UCB)#

The UCB algorithm selects the arm that maximizes the upper confidence bound of the reward estimate. For each arm $i$, the upper confidence bound is calculated as: $$ UCB_i (t) = \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}} $$

class UCB1:
    def __init__(self, n_arms):
        self.n_arms = n_arms
        self.counts = np.zeros(n_arms)
        self.values = np.zeros(n_arms)
    
    def select_arm(self):
        total_counts = np.sum(self.counts)
        if 0 in self.counts:
            return np.argmin(self.counts)
        else:
            ucb_values = self.values + np.sqrt((2 * np.log(total_counts)) / self.counts)
            return np.argmax(ucb_values)
    
    def update(self, chosen_arm, reward):
        self.counts[chosen_arm] += 1
        n = self.counts[chosen_arm]
        value = self.values[chosen_arm]
        self.values[chosen_arm] = ((n - 1) / n) * value + (1 / n) * reward

# Example usage
bandit = UCB1(n_arms)

for _ in range(n_rounds):
    chosen_arm = bandit.select_arm()
    reward = rewards[chosen_arm]
    bandit.update(chosen_arm, reward)

print("Estimated values:", bandit.values)

Estimated values: [0.70444882 0.06226676 0.98735776 0.94992464 0.69063516 0.28637876
 0.50889944 0.29081675 0.75176366 0.67070882]

Thompson Sampling#

Thompson Sampling is a Bayesian approach to the MAB problem:

Maintain a probability distribution (prior) over the possible reward distributions of each arm.
At each time step, sample from these distributions (posterior) and select the arm with the highest sampled value.
Update the posterior distributions based on the observed rewards.

class ThompsonSampling:
    def __init__(self, n_arms):
        self.n_arms = n_arms
        self.successes = np.zeros(n_arms)
        self.failures = np.zeros(n_arms)
    
    def select_arm(self):
        samples = np.random.beta(self.successes + 1, self.failures + 1)
        return np.argmax(samples)
    
    def update(self, chosen_arm, reward):
        if reward == 1:
            self.successes[chosen_arm] += 1
        else:
            self.failures[chosen_arm] += 1

# Example usage
bandit = ThompsonSampling(n_arms)

for _ in range(n_rounds):
    chosen_arm = bandit.select_arm()
    reward = np.random.binomial(1, rewards[chosen_arm])  # Simulated binary reward
    bandit.update(chosen_arm, reward)

print("Successes:", bandit.successes)
print("Failures:", bandit.failures)

Successes: [  0.   0. 934.  22.   2.   0.   0.   1.   1.  16.]
Failures: [ 1.  1. 12.  2.  1.  1.  1.  1.  1.  3.]

Variants of the Multi-Armed Bandit Problem#

Contextual Bandits#

In contextual bandits, the decision-making process is conditioned on the context $x_t$ available at each time step $t$. The objective is to learn a policy that maps contexts to arms, maximizing the cumulative reward.

class ContextualBandit:
    def __init__(self, n_arms, n_features):
        self.n_arms = n_arms
        self.n_features = n_features
        self.beta = np.zeros((n_arms, n_features))
    
    def select_arm(self, context):
        means = context @ self.beta.T
        return np.argmax(means)
    
    def update(self, chosen_arm, context, reward):
        x = context
        self.beta[chosen_arm] += (reward - x @ self.beta[chosen_arm]) * x

# Example usage
n_features = 5
contextual_bandit = ContextualBandit(n_arms, n_features)
contexts = np.random.rand(n_rounds, n_features)  # Simulated contexts

for t in range(n_rounds):
    context = contexts[t]
    chosen_arm = contextual_bandit.select_arm(context)
    reward = rewards[chosen_arm]  # Simulated reward based on context
    contextual_bandit.update(chosen_arm, context, reward)

print("Estimated beta values:", contextual_bandit.beta)

Estimated beta values: [[-1.32673078e-01 -6.36613568e-01 -3.36326975e-01 -2.51716458e-01
  -2.27676174e-01]
 [-2.18363948e-02  3.97079800e-02 -2.48581689e-02  4.83899573e-03
  -1.81184636e-02]
 [-9.48570725e-01 -4.25467312e-01 -1.81707246e+00 -9.41316232e-01
  -1.02836969e+00]
 [ 9.14430170e-02 -7.83374660e-01 -3.78409757e-02 -1.58077821e-01
  -2.31084655e-02]
 [-4.43216295e-01 -1.05227746e+00 -1.05023871e+00 -5.97755398e-01
  -2.67820756e-01]
 [-5.29923055e-01 -3.70664154e-03 -3.35768365e-01 -2.65852870e-01
  -7.12783112e-02]
 [-3.63026021e-01 -3.36760060e-01 -3.18007016e-01  9.97236539e-02
  -5.46745466e-04]
 [ 2.93724424e-02 -4.91095405e-01  2.33189510e-01 -3.61279396e-01
   3.77202717e-01]
 [-3.28717316e-01 -1.34442140e-01 -5.60745459e-01  2.75928363e-02
  -5.93695545e-01]
 [-2.28522270e-01 -7.19347374e-01  3.65264062e-01 -6.51574869e-01
  -4.01368606e-01]]

Non-Stationary Bandits#

Non-stationary bandits consider scenarios where the reward distributions of the arms change over time. Algorithms for this variant need to adapt to these changes, often incorporating mechanisms for discounting past observations or detecting change points.

Combinatorial Bandits#

Combinatorial bandits involve selecting subsets of arms rather than a single arm at each time step. This variant is relevant in scenarios where the decision-maker must allocate resources across multiple options simultaneously.

Applications#

The multi-armed bandit problem has numerous real-world applications, including:

Online Advertising: Selecting which ads to display to maximize click-through rates.
Clinical Trials: Allocating treatments to patients to identify the most effective treatment.
Recommendation Systems: Presenting items (e.g., movies, products) to users to maximize engagement.