2-armed Gaussian bandits

Let’s start from the simplest case and program a 2-armed bandit with Gaussian rewards. Imagine you are a farmer, and can choose to either plant one of two crops: wheat vs. potato. At the end of the growing season, you then earn a reward proportional to how well your crop performed. However, one of the crops may produce reliably better yields, and it is up to the farmer to figure out which crop is better.

The farmer may experience better yields or poorer yields depending on the choice of crops as well as some raddom noise from the environment.

Year after year, there may be variations in yield for a given crop, which we can model using Gaussian noise. Thus, we can describe the reward for option \(k\) as a sample from a Gaussian distribution (also known as a Normal distribution, hence the fancy \(\mathcal{N}\)):

\[ r_k \sim \mathcal{N}(\mu_k, \sigma_k^2) \]

We can now describe a payoff function for each option in terms of a mean or expected reward \(\mu_k\) and the variability \(\sigma_k^2\) (expressed as a variance). Note that the variability can also be expressed in terms of a standard deviation as \(\sigma_k = \sqrt{\sigma_k^2}\).

(Note: people using MacOS Ventura may have issues rendering the equations due to changes in the font library. If you see a box instead of a fancy N, then you can fix the issue using right-click > Math Settings > Math Renderer > “Common HTML”).

Generative model of the environment

A generative model of the environment takes a choice as an input and returns a payoff as an output.

Let’s now program a generative model of the bandit task. By defining the number of options, and providing the expected reward and variability for each option, we can define a function that takes an action and returns a reward. We provide the function in the code block below and generate payoffs for 25 random choices.

K = 2 #number of options
meanVec <- runif(n=K, min = -10, max = 10) #Payoff means, which we sample from uniform distribution between -10 to 10
sigmaVec <- rep(1, K) #Variability of payoffs (as a standard deviation), which we assume is the same for all options. 

banditGenerator <- function(k) {#k is an integer or k vector of integers, selecting one of the 1:K arms of the bandit
  payoff <- rnorm(n = length(k), mean = meanVec[k], sd = sigmaVec[k])
  return (payoff)
}

actionSequence <- sample(1:K, size = 25, replace = TRUE) # select 25 random actions
payoffs <- banditGenerator(actionSequence)

df <- data.frame(action = actionSequence, payoff = payoffs)
knitr::kable(df)

Let’s now visualize the environment, where we use a large number of samples (n=10000) to paint an accurate picture of the true generative reward structure (vertical density plot), and plot that against a small number (n=25) of sampled payoffs (dots):

source('codeSnippets/geom_flat_violin.R') 
# Use samples to approximate the reward distribution
sampleDF <- data.frame()
nsamples = 10000 #Samples used to approximate the normal distribution
plotsamples = 25 #samples to plot as dots

rewardSamples <- c(sapply(1:K, FUN=function(k) banditGenerator(rep(k, nsamples))))#use an apply function to simulate multiple samples of each arm
sampleDF <- data.frame(option = rep(1:K, each = nsamples), payoff=rewardSamples, nsample = rep(1:nsamples, K)) #create a dataframe for plotting

ggplot(sampleDF, aes(x = factor(option), y = payoff, fill = factor(option)))+
  geom_flat_violin(position = position_nudge(x = 0.3, y = 0), alpha = .5) +
  geom_jitter(data = subset(sampleDF, nsample<=plotsamples), aes(y = payoff, color = factor(option)),width = 0.2 )+  #Plot only a subset of points show how well a limited number of samples approximates the true distribution
  ylab('Payoff')+
  xlab('Option')+
  theme_classic() +
  scale_fill_viridis_d()+
  scale_color_viridis_d()+
  ggtitle('Payoff conditions')+
  theme(legend.position ='none')

Scaling up

Of course, a 2-armed bandit is quite a simple learning environment. But we can very easily scale up the number of options. How many trials do you think it would take you to identify the best option below?

#define larger set of option
K <- 10
meanVec <- runif(n=K, min = -10, max = 10) #Payoff means, which we sample from uniform distribution between -10 to 10
sigmaVec <- rep(1, K)

# Use samples to approximate the reward distribution
sampleDF <- data.frame()
nsamples = 10000 #Samples used to approximate the normal distribution
plotsamples = 25 #samples to plot as dots

rewardSamples <- c(sapply(1:K, FUN=function(k) banditGenerator(rep(k, nsamples))))#use an apply function to simulate multiple samples of each arm
sampleDF <- data.frame(option = rep(1:K, each = nsamples), payoff=rewardSamples, nsample = rep(1:nsamples, K)) #create a dataframe for plotting

ggplot(sampleDF, aes(x = factor(option), y = payoff, fill = factor(option)))+
  geom_flat_violin(position = position_nudge(x = 0.3, y = 0), alpha = .5) +
  geom_jitter(data = subset(sampleDF, nsample<=plotsamples), aes(y = payoff, color = factor(option)),width = 0.2 )+  #Plot only a subset of points show how well a limited number of samples approximates the true distribution
  ylab('Payoff')+
  xlab('Option')+
  theme_classic() +
  scale_fill_viridis_d()+
  scale_color_viridis_d()+
  ggtitle('Payoff conditions')+
  theme(legend.position ='none')

K <- 10
successVec = runif(K) #different success probabilities for each option sampled from a uniform distribution between 0 and 1
binaryGenerator <- function(k) {#k is an integer or k vector of integers, selecting one of the 1:K arms of the bandit
  payoff <- rbernoulli(n = length(k), p=successVec[k]) #a Bernoulli distribution can be used to describe a binary reward structure
  return (payoff)
}
binaryGenerator(sample(1:10, 25, replace = TRUE)) 

Individual learning

We will start with a simple individual learning version of the task, where you’ll each be on your own. Think about how you learn which options provide the best rewards and how you navigate the explore-exploit dilemma.

A 16-armed bandit task.

The demo game is an 16-armed bandit task. Suppose you are in the fishing boat and trying to catch as many fish as possible. The ocean is divided into the 16 grid cells. Some grid areas will provide more fish than other grid areas. To make a decision, just click/tap one of the cells.

Individual learning experiment

Social learning

Now, let’s switch to a social version of the task. Beyond simply learning from your own experiences, you can observe the actions of others and use that to inform your decisions. Here, we start with the simplest case where all players are interacting with the exact same reward function. Of course, this isn’t always the case in the real world, but it is the simplest starting point.

You will be able to observe the actions of other players, but not see the rewards they earn. Do you think that collectively, you will be able to identify the best option? When do you think social learning will outperform individual learning, and when would it fail?

Social learning experiment

Competitive social learning (if time)

We now add a small twist to the social version of the task. As in many real-world examples of crowded tourist destinations or crowded watering holes, high-value options will tend to attract many individuals seeking rewards. Yet as the number of individuals increases, the rewards can decrease due to social competition. Here, we’ve implemented a simple version of social competition, where everyone who selects the same option will need to split the reward amongst one another. How will this change the social learning dynamics? Can you still use social information to learn about which options are rewarding? What strategies can you use to avoid unncessary competition?

Competitive social learning experiment

Spatial structure

Many social interactions unfold in spatial settings, where both social information (Sridhar et al., 2021) and rewards are defined by spatial structure (Hawkins et al., in press). For instance, high-valued rewards may tend to be clustered together, such like good restaurants in a hip part of a city or prey/vegetation naturally occurring in patchy distributions.

Spatially correlated bandit task from Wu et al. (2018)

One paradigm that adds spatial structure to bandit tasks is the “spatially correlated bandit” (Wu et al., 2018). Whereas bandit tasks typically assume that the rewards for each option are completely independent from all other options, the spatially correlated bandit places up to 121 options onto a 2D grid and informs participants options tend to have similar rewards to other nearby options. The spatial structure of rewards can be used (by people as young as age 5: Giron et al., in press) to guide exploration towards promising regions of the search space. With the following link, you can try a version of the task where the rewards were derived from the yield of various crops on an experimental farm, such that the rows and columns of the grid correspond to the rows and columns of a field (see Exp. 3 in Wu et al., 2018 for details):

Spatially correlated bandit experiment

More recently, Wu et al. (2023) developed an immersive variant of the task with collective foraging dynamics. Participants are tasked with foraging for binary rewards (indicated by a blue splash), and in the condition below, rewards are clustered together. This means that observing another player acquire a reward provides a valuable social signal that there are likely to be other rewards nearby:

Task tutorial

embed_url("https://www.youtube.com/watch?v=QksKYOoElxg")

POV video from social round with smooth rewards

embed_url("https://www.youtube.com/watch?v=wyk7RbmHiok")

Foraging tasks

Much research on social learning has used the naturalistic context of foraging, where an organism can use social cues to help find food or other important resources (Giraldeau & Caraco, 2018; Hoppitt & Laland, 2013; Zentall et al., 1988). Foraging tasks can be framed as a special kind of multi-armed bandit, where the dynamics of the natural world mean that rewards are typically finite and diminish over time. Just as bandits simply decision-making problems into a discrete number of choices, research on foraging also simplifies the natural world into a discrete number of patches. For instance, in this illustration of a producer-scrounger task (Barnard & Sibly, 1981), experimenters place food pellets in a limited number of wells on a grid and observe how animals engage in either individual learning (“producer” strategy) or social imitation (“scrounger” strategy). We will be discussing the dynamics of different learning strategies in more detail in Tutorial 2.

Producer-Scrounger task from Keynan et al. (2015)

Innovation and cumulative culture

Beyond only foraging and learning in spatial environments, we also want to describe social learning problems in more open-ended environments. We may want to model how people or animals come up with new innovations, such as new behaviors (Miu et al., 2018) or new tools (Mesoudi & O’Brien, 2008). For example, in the arrow head task by Mesoudi & O’Brien (2008), participants were tasked with learning which combination of height, width, shape, color, and thickness produced the best hunting outcomes.

from Mesoudi & O’Brien (2008)

One method for describing learning along an arbitrary number of abstract dimensions is a fitness landscape. Originally introduced in the 1930s to study genetic evolution, fitness landscapes can also be used to map any combination of latent features to some fitness value. Learning, can thus be compared to an optimization process as an organism learns to acquire better solutions through a combination of both individual and social learning (Barkoczi et al., 2016; Mason & Watts, 2012).

from De Visser & Krug (2014)

This is still quite similar to how the spatially correlated bandit (Wu et al., 2018) maps each of the options onto a 2D grid. The main difference is that a fitness landscape introduces an arbitrary number of dimensions that may have abstract rather than spatial relationships between options or “locations” on the search space. And while there are many similarities in how people learn and search in spatial vs. non-spatial environments, there are also important differences (Wu et al., 2020). For instance, compared to learning spatially correlated rewards, Wu et al. (2020) found that participants explored in a distinctly different fashion when learning on the exact same reward structure, but the with x- and y-dimensions mapped instead onto the tilt and stripe frequency of a Gabor patch.

from Wu et al. (2020)

Beyond bandits

Of course, bandit tasks cannot capture all interesting learning problems (Brändle et al., 2022). But it is incredibly versatile and using similar code to what have provided above, you can describe a wide-range of interesting social learning problems.