## Multi-Armed Bandits

Suppose you have $N$ slot machines (a multi-armed bandit) with each bandit having an unkwown probability of distributing a prize. Assuming the prizes are the same for each bandit and only their probabilities of winning are different, our goal is to develop a strategy to maximize our winnings with fewest trials. If we knew which of the bandits results in the highest probability of winning, we would exercise that bandit all the time. However, a sub-optimal bandit can generate a winning sequence purely by chance and even if we found a good enough bandit, do we keep using it or explore in the hope of finding an even higher probability of winning.

A Bayesian solution to the multi-armed bandit problem involves updating our prior belief on the probability of success for each bandit based on the observed draws. A beta-binomial model provides a conjugate likelihood and prior with closed form posterior updates. Thus, we can assume an uninformative $Beta(1,1)$ prior for each of the $N$ bandits. Thus, our bayesian bandits algorithm can be summarized as follows:

1. Draw a sample $X_b$ from the prior of bandit $b$ for all $b$
2. Select the bandit with the largest sample: $B = \arg \max X_b$
3. Observe the result of pulling banding $B$ and update your prior on bandit $B$
4. Repeat

This algorithm suggests that we shouldn't discard low success probability bandits but instead that we should pick them at a decreasing rate as we gather more confidence that there exist better bandits.


```
%matplotlib inline
import numpy as np
import pandas as pd
import scipy.stats as stats

import seaborn as sns
import matplotlib.pyplot as plt

```


```
class Bandits(object):
    """
    This class represents N bandits machines.

    parameters:
        p_array: a (n,) Numpy array of probabilities >0, <1.

    methods:
        pull( i ): return the results, 0 or 1, of pulling 
                   the ith bandit.
    """
    def __init__(self, p_array):
        self.p = p_array
        self.optimal = np.argmax(p_array)
        
    def pull(self, i):
        #i is which arm to pull
        return np.random.rand() < self.p[i]
    
    def __len__(self):
        return len(self.p)

```


```
class BayesianStrategy(object):
    """
    Implements a online, learning strategy to solve
    the Multi-Armed Bandit problem.
    
    parameters:
        bandits: a Bandit class with .pull method
    
    methods:
        sample_bandits(n): sample and train on n pulls.

    attributes:
        N: the cumulative number of samples
        choices: the historical choices as a (N,) array
        bb_score: the historical score as a (N,) array
    """
    
    def __init__(self, bandits):
        
        self.bandits = bandits
        n_bandits = len(self.bandits)
        self.wins = np.zeros(n_bandits)
        self.trials = np.zeros(n_bandits)
        self.N = 0
        self.choices = []
        self.bb_score = []

    
    def sample_bandits(self, n=1):
        
        bb_score = np.zeros(n)
        choices = np.zeros(n)
        
        for k in range(n):
            #sample from the bandits's priors, and select the largest sample
            choice = np.argmax(np.random.beta(1 + self.wins, 1 + self.trials - self.wins))
            
            #sample the chosen bandit
            result = self.bandits.pull(choice)
            
            #update priors and score
            self.wins[choice] += result
            self.trials[choice] += 1
            bb_score[k] = result 
            self.N += 1
            choices[k] = choice
            
        self.bb_score = np.r_[self.bb_score, bb_score]
        self.choices = np.r_[self.choices, choices]
        return 

```


```
def plot_priors(bayesian_strategy, prob, lw = 3, alpha = 0.2, plt_vlines = True):
    ## plotting function
    wins = bayesian_strategy.wins
    trials = bayesian_strategy.trials
    for i in range(prob.shape[0]):
        y = beta(1+wins[i], 1 + trials[i] - wins[i])
        p = plt.plot(x, y.pdf(x), lw = lw)
        c = p[0].get_markeredgecolor()
        plt.fill_between(x,y.pdf(x),0, color = c, alpha = alpha, 
                         label="underlying probability: %.2f" % prob[i])
        if plt_vlines:
            plt.vlines(prob[i], 0, y.pdf(prob[i]) ,
                       colors = c, linestyles = "--", lw = 2)
        plt.autoscale(tight = "True")
        plt.title("Posteriors After %d pull" % bayesian_strategy.N +\
                    "s"*(bayesian_strategy.N > 1))
        plt.autoscale(tight=True)
    return

```


```
def regret(probabilities, choices):
    w_opt = probabilities.max()
    return (w_opt - probabilities[choices.astype(int)]).cumsum()

```


```
rand = np.random.rand
beta = stats.beta
x = np.linspace(0.001,.999,200)
```


```
#bandits success probability
hidden_prob = np.array([0.85, 0.60, 0.75])
    
#instantiate multi-armed bandit class
bandits = Bandits(hidden_prob)
bayesian_strat = BayesianStrategy(bandits)
```


```
#generate plots
draw_samples = [1, 1, 3, 10, 10, 25]
for j,i in enumerate(draw_samples):
    plt.subplot(3, 2, j+1) 
    bayesian_strat.sample_bandits(i)
    plot_priors(bayesian_strat, hidden_prob)
    #plt.legend()
    plt.autoscale(tight = True)
plt.tight_layout()
plt.show()
```

In the above figure we are showing the posterior distributions for a mutli-armed bandit with $N=3$ arms for multiple draws with hidden winning probability marked by the dashed lines. We can see that all three bandits were exercised with red and blue giving the highest returns. The mode of the posterior distribution shows that green and red bandits produced returns higher then their hidden probability purely by chance. Nonetheless the blue bandit was chosen the greatest number of time leading to the highest reward probability.


```
regret_bound = regret(hidden_prob, bayesian_strat.choices)
    
plt.figure()
plt.plot(regret_bound, lw=3)
plt.xlabel('number of trials')
plt.ylabel('regret')
plt.show()
```

We can measure the performance of our on-line algorithm using a regret bound as shown in the figure above. The best we can do is to always pick the bandit with the largest probability of winning ($w_opt$). We can make our score relevant to the optimum bandit probability:
\begin{equation}
    R_T = \sum_{t=1}^{T} (w_{opt} - w_{B(i)})
\end{equation}
where $w_{B(i)}$ is the probability of winning for a chosen bandit in $i$-th round. A regret of zero means the strategy is matching the best possible score. Ideally, our strategy should flatten as it learns the best bandit.

ae9f9c0d8fea58af4982342e6f53909ce117f761
ipynb
Jupyter Notebook
chp01/multi_armed_bandits.ipynb
gerket/experiments_with_python
5dd6dbd69deaaa318bfa7d2c3c9f7fae6220c460
MIT
2017-08-22T13:14:54.000Z
2022-03-28T17:56:59.000Z
chp01/multi_armed_bandits.ipynb
gerket/experiments_with_python
5dd6dbd69deaaa318bfa7d2c3c9f7fae6220c460
MIT
2017-07-31T00:52:36.000Z
2018-10-01T14:29:51.000Z
chp01/multi_armed_bandits.ipynb
gerket/experiments_with_python
5dd6dbd69deaaa318bfa7d2c3c9f7fae6220c460
MIT
2017-08-23T08:08:32.000Z
2022-03-09T07:04:01.000Z
Qwen/Qwen-72B
1. YES
2. YES