Explore-then-commit algorithm

Explore Then Commit (ETC) is an algorithm for the multi-armed bandit problem foc,used on finding the best trade-off between exploration and exploitation.

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}$ 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 algorithm explores each arm ${\displaystyle M}$ times. 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]

When all arms are ${\displaystyle 1}$-sub gaussian, by choosing to explore each arm ${\displaystyle M}$ times, the regret at time ${\displaystyle T}$ verify

${\displaystyle R_{T}\leq M\sum _{i=1}^{K}\Delta _{i}+(T-MK)\sum _{i=1}^{K}\Delta _{i}\exp \left(-{\frac {M\Delta _{i}^{2}}{4}}\right)}$^[1]

the first term is considered the cost of the exploration

${\displaystyle M\sum _{i=1}^{K}\Delta _{i}}$.

The second term is the cost of not having explored enough, leading to a probability of not having an optimal arm as the arm with the highest empirical mean.

${\displaystyle (T-MK)\sum _{i=1}^{K}\Delta _{i}\exp \left(-{\frac {M\Delta _{i}^{2}}{4}}\right)}$

Increasing ${\displaystyle M}$ increases the first term while decreasing the second term. The best possible ${\displaystyle M}$ must depend on the ${\displaystyle (\Delta _{i})_{i}}$ which is unknown by the player.

For two arms with Gaussian distribution of variance ${\displaystyle 1}$, it was proved that ETC cannot achieve the asymptotic optimal regret of the Equation of Lai-Robbins.^[4]

• multi-armed bandit
• Confidence interval