Multi-Armed Bandits

A Multi-Armed Bandit problem is a hypothetical experiment where an agent must choose between multiple actions, each with an unknown payout.

A $k$$\large k$-armed bandit provides $k$$\large k$ actions, each with expected or mean rewards.

where $q_{\ast }(a)$$\large q_*(a)$ is the expected reward (also referred to as the value) when action $a$$\large a$ is selected, $A_t$$\large A_t$ is the action selected at time step $t$$\large t$, and $R_t$$\large R_t$ is the corresponding reward. $Q_t$$\large Q_t$ is the estimated value of $q_{\ast }(a)$$\large q_*(a)$ at time step $t$$\large t$.

Exploration vs Exploitation

Exploration is the task of trying out new actions to learn their rewards.

Exploitation is the task of preferring actions that appear to have the best rewards.

A good solution to the multi-armed bandit problem should have a good balance of exploration and exploitation.

$ϵ$$\epsilon$-Greedy Algorithm

The $ϵ$$\large \epsilon$-Greedy Algorithm involves choosing random exploration with probability $ϵ$$\large \epsilon$ and choosing exploitation with probability $1-ϵ$$\large 1 - \epsilon$.

Incremental Implementation

We can use the average value of $R_i$$\large R_i$ as an estimate for $Q_n$$\large Q_n$:

Pseudocode

Nonstationary Problems

For bandits that are nonstationary (i.e. they change over time), it makes sense to assign higher weight to more recently recorded rewards than to old ones. Thus, we can use a weighted average estimation method by using a defined step size $\alpha$$\large \alpha$:

If $\alpha$$\large \alpha$ is varying in each step, the variation must conform to the following conditions in order to ensure $Q(a)$$\large Q(a)$ converges to $q_{\ast }(a)$$\large q_*(a)$:

Pseudocode

Upper-Confidence-Bound Action Selection

Instead of selecting exploration or exploitation based on probability, it makes sense to explore more at the beginning and reduce exploration over time. Upper-Confidence-Bound Action Selection involves using an additional term that accounts for the uncertainty in the value of $Q(a)$$\large Q(a)$:

where $N_t(a)$$\large N_t(a)$ denotes the number of times action $a$$\large a$ has been selected and $c$$\large c$ controls the degree of exploration.

Pseudocode

Gradient Bandit Algorithm

The Gradient Bandit Algorithm involves learning a numerical preference $H_t(a)\in \mathbb{R}$$\large H_t(a) \in \mathbb{R}$ for each action $a$$\large a$ and using that to determine the current action.

We define ${\pi }_t(a)$$\large \pi_t(a)$ as the probability of taking action $a$$\large a$ at time $t$$\large t$:

The learning algorithm for $H_t(a)$$\large H_t(a)$ is based on stochastic gradient ascent:

or equivalently:

where $1_{a=A_t}$$\large 1_{a=A_t}$ is an indicator function: