---
title: Explore-then-commit algorithm
slug: explore-then-commit-algorithm
qid: 
snapshot: enwiki-001360960470
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1360960470
tags: [20165933, 20235111, 20476448, 23603337, 23617828, 26220375, 26709330, 27424735]
---

# Explore-then-commit algorithm

> [!note] Provenance
> Snapshot `enwiki-001360960470` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1360960470> · Licensed CC BY-SA 4.0

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

Explore Then Commit (ETC) is an algorithm for the multi-armed bandit problem focused on finding the best trade-off between exploration and exploitation. R_T := \sum_{a=1}^K \Delta_a \mathbb{E}[N_a(T)] where \mu_a := \mathbb{E}[\nu_a] is the mean of arm a \mu^* := \max_a \mu_a is the highest mean \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 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). R_T \leq M \sum_{i = 1}^K \Delta_i + (T - M K) \sum_{i=1}^K \Delta_i \exp\left( -\frac{M \Delta_i^2}{4} \right) the first term is considered the cost of the exploration 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. (T - M K) \sum_{i=1}^K \Delta_i \exp\left( -\frac{M \Delta_i^2}{4} \right) Increasing M increases the first term while decreasing the second term. The best possible M must depend on the (\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.
