Introduction¶
In this notebook we implement two examples of the Multi-Armed Bandit problem. The problem is defined as follows:
For a specified number of time steps, an agent is faced with a choice among k different actions. After each choice the agent receives a numerical reward value chosen from a stationary probability distribution corresponding to the action the agent selected. The agent's objective is to maximize the expected total reward over the number of time steps given.
We approximate the expected reward of an action $a$ using a value $Q(a)$, updating our estimate each time. At any given time step, $Q(a)$ is given as the sum of the total reward received when taking action $a$ over the number of times action $a$ was taken. Computing $Q(a)$ in this way assures that it will approximate the expected value of the reward distribution $q^{*}(a)$ of an action $a$ over time.
At any time step $t$, we can choose to take the action with the best q-value. This is called a greedy approach. However, until we have explored all the actions sufficiently, the best q-value may not represent the optimal action. So, we may choose to occasionally explore a random action, say with probability $\epsilon$. This notebook will demonstrate the usefulness of the $\epsilon$-greedy approach on the 10-armed testbed described in Chapter 2 of the Barto and Sutton Reinforcement Learning textbook (see references) using different $\epsilon$ values. We will also explore this approach using a toy advertisement dataset.
Psuedocode¶
#imports
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import random
import cv2
An agent takes actions in a bandit environment according to the following psuedocode:
img = cv2.imread('Project 1 psuedocode.jpg')
plt.figure(figsize=(17, 17))
plt.imshow(img)
plt.xlabel('Figure 2')
plt.show()
Note that:
$$Q(A)<-Q(A)+1/N(A)[R-Q(A)]$$The reward of an action will be sampled from the normal reward distribution of each action, given below. $N(A)$ represents the a count of the number of times an action has been taken. The action taken will either be the one with the highest Q-value if exploiting or a random action if exploring.
10 Armed Testbed Experiment¶
Implementation¶
We will first test out the epsilon-greedy method of the bandit algorithm on the 10-armed testbed. The 10-armed testbed referenced above has the following reward distribution:
img = cv2.imread('testbed_reward.jpg')
plt.figure(figsize=(17, 17))
plt.imshow(img)
plt.xlabel('Figure 1')
plt.show()
The rest of our implementation steps are detailed below:
Helper Functions¶
q_star=np.array((0.3, -1, 2.5, 0.8, 2, -1.8, -0.2, -1, 1, -0.3)) #store the mean of the reward distribution of each action in
#an array
Q=np.empty(10) #initialize q-value array
N=np.empty(10) #initialize array to keep track of count of each action
def bandit_distribution(A):
"""returns the reward value R from an action A based on the normal reward distribution with mean q-star and standard
deviation 1"""
reward= np.random.normal(q_star[A], 1)
return reward
def take_action_testbed(A):
"""Given an action A, take it, receive a reward R from the normal reward distirbution of A, and update N and Q values
according to bandit algorithm"""
R=bandit_distribution(A)
N[A] +=1
Q[A] += 1/N[A]*(R-Q[A])
return R
Experiment and Parameters¶
We will perform some experiments with four different epsilon values. Following the framework presented in the Sutton and Barto Reinforcement Learning book, we will perform 2000 iterations, each with 10000 timesteps. The original example only used 1000 timesteps, but we use more to demonstrate results. We will test out $\epsilon=1$ (random), $\epsilon=0.1$, $\epsilon=0.01$, and $\epsilon=0$ (greedy). We will average the total reward values over the 2000 iterations for each timestep, and then plot the results.
def run_bandit_experiment_1(runs, steps, epsilon):
"""Runs the experiment described in the beginning of this section for a certain amount of steps and a probability epsilon
for exploration"""
reward_matrix=np.empty((runs, steps))
for i in range(0, runs):
for a in range(0, 10): #reset experiment
Q[a]=0
N[a]=0
total_reward=0
for j in range(0, steps):
p=random.random()
if p<1-epsilon: #exploit with probability 1-epsilon
A=np.random.choice(np.flatnonzero(Q == Q.max()))
total_reward+=take_action_testbed(A)
reward_matrix[i][j]=total_reward/(j+1) #average reward
else: #explore if possible with probability epsilon
A=np.random.randint(0, 10)
total_reward+=take_action_testbed(A)
reward_matrix[i][j]=total_reward/(j+1) #average reward
return reward_matrix
Results¶
The results from our experiments are presented in the plot below:
#run experiment with different epsilon values
epsilon_1_reward=run_bandit_experiment_1(2000, 10000, 1)
epsilon_0_1_reward=run_bandit_experiment_1(2000, 10000, 0.1)
epsilon_0_0_1_reward=run_bandit_experiment_1(2000, 10000, 0.01)
epsilon_0_reward=run_bandit_experiment_1(2000, 10000, 0)
#average results
epsilon_1_averages=np.mean(epsilon_1_reward, axis=0)
epsilon_0_1_averages=np.mean(epsilon_0_1_reward, axis=0)
epsilon_0_0_1_averages=np.mean(epsilon_0_0_1_reward, axis=0)
epsilon_0_averages=np.mean(epsilon_0_reward, axis=0)
#plot results
plt.plot(epsilon_1_averages, label='epsilon=1')
plt.plot(epsilon_0_1_averages, label='epsilon=0.1')
plt.plot(epsilon_0_0_1_averages, label='epsilon=0.01')
plt.plot(epsilon_0_averages, label='epsilon=0')
plt.xlabel('Time(t)')
plt.ylabel('Average Reward')
plt.legend()
plt.show()
Conclusions¶
From the plot above, we can make the following observations:
- $\epsilon=1$ represents a completely random agent which produces the lowest overall average reward that is relatively constant
- $\epsilon=0.1$ converges sooner, but only achieves the second best overall average reward
- $\epsilon=0.01$ takes longer to converge, but achieves the best overall average reward
- $\epsilon=0$ (greedy) only exploits without any exploration and produces the second lowest overall average reward
In our experiment, we begin by initializing the q-values of all actions to 0. Some actions have negative expected values.
The $\epsilon=1$ approach explores for the whole experiment, creating an agent that takes completely random actions over all timesteps. We will use this as a control group or baseline of sorts.
The $\epsilon=0.1$ approach has a 10% probability of exploration, in which it will take a random action. The optimal action in this experiment is action 3. Once the agent takes this action, it will continue to take this action 90% of the time for the rest of the experiment, and it will begin to converge at this point.
The $\epsilon=0.01$ approach has a 1% probability of exploration. Because of this, it will take longer to find the optimal action, but once it is found, it will be taken 99% of the time, and will eventually surpass the 10% exploration approach in the long term. This is why we chose to run each iteration with 10000 timesteps, as the original 1000 timestep approach may have deceived the reader into believing that the choice of $\epsilon=0.1$ is the best approach.
In the case of the $\epsilon=0$ (greedy) approach, the agent will take random actions until it finds an action with a positive q-value, and take this action for the rest of the experiment. This is when the greedy approach converges, and though it is possible for the action the greedy agent takes to be the optimal one, it is unlikely. Averaging demonstrates this.
These experimental results suggest that smaller nonzero epsilon values produce the best long-term reward.
Advertisement Experiment¶
We will also test the epsilon-greedy approach to the bandit problem on the toy advertising dataset found here:
https://drive.google.com/file/d/1whkIInL4FKeHg2IfdcbT1j18L26fg9aF/view
In this dataset, suppose an advertising company is running 10 different ads targeted towards a similar set of population on a webpage. Each column index represents a different ad. We have a 1 if the ad was clicked by a user, and 0 if it was not.
First we load the dataset:
Implementation¶
#load dataset
ads_optimization=pd.read_csv('Ads_Optimisation.csv')
reward_array=np.empty(10)
#get reward values
for i in range(0, 10):
reward_array[i]=ads_optimization['Ad '+str(i+1)].sum()
print(reward_array)
Note that we defined the reward value of each advertisement to be the number of users that clicked on an advertisement. The reward values are listed above. Unlike the first dataset, these reward values are discrete and not sampled from a continuous normal distribution.
Helper Functions¶
def bandit_ads(A):
"""returns the reward value R of an action A for the ads dataset"""
reward=reward_array[A]
return reward
def take_action_ads(A):
"""Given an action A, take it, receive a reward R based on the reward values from the ads datset and update N and Q values
according to bandit algorithm"""
R=bandit_ads(A)
N[A] +=1
Q[A] += 1/N[A]*(R-Q[A])
return R
Experiment and Parameters¶
We will perform the same experiments as in the 10-armed testbed with four different epsilon values. We will perform 2000 iterations, each with 10000 timesteps. We will test out $\epsilon=1$ (random), $\epsilon=0.1$, $\epsilon=0.01$, and $\epsilon=0$ (greedy), averaging and plotting the results.
def run_bandit_experiment_2(runs, steps, epsilon):
"""Runs the experiment described in the beginning of this section for a certain amount of steps and a probability epsilon
for exploration"""
reward_matrix=np.empty((runs, steps))
for i in range(0, runs):
for a in range(0, 10): #reset experiment
Q[a]=0
N[a]=0
total_reward=0
for j in range(0, steps):
p=random.random()
if p<1-epsilon: #exploit with probability 1-epsilon
A=np.random.choice(np.flatnonzero(Q == Q.max()))
total_reward+=take_action_ads(A)
reward_matrix[i][j]=total_reward/(j+1) #average reward
else: #explore if possible with probability epsilon
A=np.random.randint(0, 10)
total_reward+=take_action_ads(A)
reward_matrix[i][j]=total_reward/(j+1) #average reward
return reward_matrix
#run experiment with different epsilon values
epsilon_1_reward=run_bandit_experiment_2(2000, 10000, 1)
epsilon_0_1_reward=run_bandit_experiment_2(2000, 10000, 0.1)
epsilon_0_0_1_reward=run_bandit_experiment_2(2000, 10000, 0.01)
epsilon_0_reward=run_bandit_experiment_2(2000, 10000, 0)
#average results
epsilon_1_averages=np.mean(epsilon_1_reward, axis=0)
epsilon_0_1_averages=np.mean(epsilon_0_1_reward, axis=0)
epsilon_0_0_1_averages=np.mean(epsilon_0_0_1_reward, axis=0)
epsilon_0_averages=np.mean(epsilon_0_reward, axis=0)
Results¶
The results from our experiments are presented in the plot below:
#plot results
plt.plot(epsilon_1_averages, label='epsilon=1')
plt.plot(epsilon_0_1_averages, label='epsilon=0.1')
plt.plot(epsilon_0_0_1_averages, label='epsilon=0.01')
plt.plot(epsilon_0_averages, label='epsilon=0')
plt.xlabel('Time(t)')
plt.ylabel('Average Reward')
plt.legend()
plt.show()
Conclusions¶
From the plot above, we can make the following observations:
- $\epsilon=1$ represents a completely random agent which produces the second lowest overall average reward that is relatively constant
- $\epsilon=0.1$ converges sooner, but does not achieve the best overall average reward
- $\epsilon=0.01$ takes longer to converge, but achieves the best overall average reward.
- $\epsilon=0$ (greedy) only exploits without any exploration and produces the lowest overall average reward that is also constant.
In our experiment, we begin by initializing the q-values of all actions to 0. In this dataset, all actions have positive reward values.
The $\epsilon=1$ approach explores for the whole experiment, creating an agent that takes completely random actions over all timesteps. We will use this as a control group or baseline of sorts. In this case, it actually performs slighly better than the greedy approach, because it performs all possible actions randomly, instead of one action consistently throughout the whole experiment.
The $\epsilon=0.1$ approach has a 10% probability of exploration, in which it will take a random action. The optimal action in this experiment is action 5. Once the agent takes this action, it will continue to take this action 90% of the time for the rest of the experiment, and it will begin to converge at this point.
The $\epsilon=0.01$ approach has a 1% probability of exploration. Because of this, it will take longer to find the optimal action, but once it is found, it will be taken 99% of the time, and will eventually surpass the 10% exploration approach in the long term. This is why we chose to run each iteration with 10000 timesteps, as the original 1000 timestep approach may have deceived the reader into believing that the choice of $\epsilon=0.1$ is the best approach.
In the case of the $\epsilon=0$ (greedy) approach, the agent will take random actions until it finds an action with a nonzero q-value, and take this action for the rest of the experiment. The greedy approach will have a static reward value because of this when averaged over many timesteps. Though it is possibe for the action the greedy agent takes to be the optimal one, it is unlikely. Averaging demonstrates this.
These experimental results suggest that smaller nonzero epsilon values produce the best long-term reward.
Final Remarks¶
Since both experiments demonstrate that lower epsilon values produce a lower average reward, we can conclude that:
- Greedy approaches will converge fatest but are not guaranteed to find the optimal action, and will likely not in the long term.
- The utility of greedy appraches depends on the value of the expected reward for each action (positive or negative).
- As epsilon values decrease, the speed at which they converge will decrease, but they are guaranteed to take the optimal action more in the long term.
These are consistent with the theoretical results described in the Sutton and Barto book.
References¶
[1] Sutton, Richard S. and Barto, Andrew G. Chapter 2: Multi-Armed Bandits from Reinforcement Learning. pps. 25-46. Kindle Edition. 2018.
[2] Ni, Zhen. Multi-Armed Bandits. Lecture notes. pps. 8, 10. 2020.