Explore-then-commit algorithm

Short description: Algorithm for the multi-armed bandit problem

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.

Multi-armed bandit problem

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

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

Regret minimization

The goal is to minimize the regret at time $T$ that is defined as

$R_T:=\sum _{a=1}^K{\mathrm{\Delta }}_a\mathbb{𝔼}[N_a(T)]$

where

• ${\mu }_a:=\mathbb{𝔼}[{\nu }_a]$ is the mean of arm $a$
• ${\mu }^{*}:=\underset{a}{\max }{\mu }_a$ is the highest mean
• ${\mathrm{\Delta }}_a:={\mu }^{*}-{\mu }_a$
• $N_a(t)$ is the number of pulls of arm $a$ up to turn $t$

The player has to find an algorithm that chooses at each turn $t$ which arm to pull based on the previous actions and observations $(a_s,X_s{)}_{s<t}$ to minimize the regret $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).

Algorithm

File:ETCdoublerun.gif

Two runs of ETC with the same M = 10. On the first run it does manage to find the best arm after the exploration while it does not on the second run

The algorithm explores each arm $M$ times. For the rest of the game the algorithm exploits its discoveries by playing the arm with the highest mean. If the horizon $T$ is known, then the number of explorations $M$ can depend on $T$.

Adaptations of the algorithm exist and can be found in the literature for other settings.

Pseudocode

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]

Theoretical results

File:ETCregret.png

Trade of between exploration (large M) and exploitation (small M) for ETC

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

$R_T\le M\sum _{i=1}^K{\mathrm{\Delta }}_i+(T-MK)\sum _{i=1}^K{\mathrm{\Delta }}_i\exp (-\frac{M{\mathrm{\Delta }}_i^2}{4})$

the first term is considered the cost of the exploration

$M\sum _{i=1}^K{\mathrm{\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.

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

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

For two arms with Gaussian distribution of variance $1$, it was proved that ETC cannot achieve the asymptotic optimal regret of the Equation of Lai-Robbins.

See also

• multi-armed bandit
• Confidence interval