Draft:Explore-then-commit algorithm

Submission declined on 20 February 2026 by MSK (talk). This draft's references do not show that the subject meets Wikipedia's criteria for inclusion. The draft requires multiple published secondary sources that: provide significant coverage: discuss the subject in detail, not just brief mentions or routine announcements; are reliable: from reputable outlets with editorial oversight; are independent: not connected to the subject, such as interviews, press releases, the subject's own website, or sponsored content. Please add references that meet all three of these criteria. If none exist, the subject is not yet suitable for Wikipedia. If you would like to continue working on the submission, click on the "Edit" tab at the top of the window. If you have not resolved the issues listed above, your draft will be declined again and potentially deleted. If you need extra help, please ask us a question at the AfC Help Desk or get live help from experienced editors. Please do not remove reviewer comments or this notice until the submission is accepted. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Declined by MSK 5 months ago. Last edited by Adrien PREVOST 4 months ago. Reviewer: Inform author. Resubmit Please note that if the issues are not fixed, the draft will be declined again.

• Comment: Source 2 is on arXiv, which is considered unreliable as there is no editorial or peer review needed to publish there. monkey_smashing^keyboards (talk) 21:57, 20 February 2026 (UTC)

Explore Then Commit (ETC) is an algorithm for the Multi-armed bandit problem where you have to do a trade-off between exploration/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}$ 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}}$, he then gets 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 to find the best arm (the arm with the highest mean) and exploitation to play as much as possible the arm that we think is the best arm.^[1]

The idea of the algorithm is to explore each arm ${\displaystyle M}$ times. Then for the rest of the game the algorithm exploit by playing the arm with the highest mean. If the horizon ${\displaystyle T}$ is known then the number of exploration ${\displaystyle M}$ can depends on ${\displaystyle T}$.

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

The player choose 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 highestempirical 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]

We can see the first term as the cost of the exploration

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

And the second term as the cost of not having exploring 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}$ increase the first term while decreasing the second term. The best possible ${\displaystyle M}$ must depends 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 can't achieve the asymptotic optimal regret of the Equation of Lai-Robbins.^[4]