Explore-then-commit algorithm

The multi-armed bandit problem is a sequential game where one player has to choose at each turn between ${\displaystyle K}$ actions (arms). Behind every arm ${\displaystyle a}$ there is an unknown distribution ${\displaystyle \nu _{a}}$ that lies in a set ${\displaystyle {\mathcal {D}}}$ known by the player (for example, ${\displaystyle {\mathcal {D}}}$ can be the set of Gaussian distributions or Bernoulli distributions).

At each turn ${\displaystyle t}$ the player chooses (pulls) an arm ${\displaystyle a_{t}}$, they then get an observation ${\displaystyle X_{t}}$ of the distribution ${\displaystyle \nu _{a_{t}}}$.

The goal is to minimize the regret at time ${\displaystyle T}$ that is defined as

${\displaystyle R_{T}:=\sum _{a=1}^{K}\Delta _{a}\mathbb {E} [N_{a}(T)]}$

where

• ${\displaystyle \mu _{a}:=\mathbb {E} [\nu _{a}]}$ is the mean of arm ${\displaystyle a}$
• ${\displaystyle \mu ^{*}:=\max _{a}\mu _{a}}$ is the highest mean
• ${\displaystyle \Delta _{a}:=\mu ^{*}-\mu _{a}}$
• ${\displaystyle N_{a}(t)}$ is the number of pulls of arm ${\displaystyle a}$ up to turn ${\displaystyle t}$

The player has to find an algorithm that chooses at each turn ${\displaystyle t}$ which arm to pull based on the previous actions and observations ${\displaystyle (a_{s},X_{s})_{s<t}}$ to minimize the regret ${\displaystyle R_{T}}$.

This is a trade-off problem between exploration (finding the arm with the highest mean) and exploitation (playing the arm which is perceived to be the best as much as possible).^[1]

The idea of the algorithm is to explore each arm ${\displaystyle M}$ times. Then for the rest of the game the algorithm exploits its discoveries by playing the arm with the highest mean. If the horizon ${\displaystyle T}$ is known, then the number of explorations ${\displaystyle M}$ can depend on ${\displaystyle T}$.

Adaptations of the algorithm exist^[2] and can be found in the literature for other settings.^[3]

The player chooses M
 for each arm i do:
    select arm i M times
    update empirical mean mu[i]
for t from MK+1 to T do:
    select arm a with highest empirical mean mu[a]