Explore-then-commit algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1360960470 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.