Explore-then-commit algorithm
≈ 3 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.
Multi-armed bandit problem
edit edit sourceThe 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 ν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 at, they then get an observation Xt of the distribution νat.
Regret minimization
edit edit sourceThe goal is to minimize the regret at time T that is defined as
- RT:=∑a=1KΔa𝔼[Na(T)]
where
- μa:=𝔼[νa] is the mean of arm a
- μ∗:=maxaμa is the highest mean
- Δa:=μ∗−μa
- Na(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 (as,Xs)s<t to minimize the regret RT.
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]
Algorithm
edit edit sourceThe 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[2] and can be found in the literature for other settings.[3]
Pseudocode
edit edit source 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
edit edit sourceWhen all arms are 1-sub gaussian, by choosing to explore each arm M times, the regret at time T verify
- RT≤M∑i=1KΔi+(T−MK)∑i=1KΔiexp(−MΔi24)[1]
the first term is considered the cost of the exploration
- M∑i=1KΔ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)∑i=1KΔiexp(−MΔi24)
Increasing M increases the first term while decreasing the second term. The best possible M must depend on the (Δ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.[4]
See also
edit edit sourceReferences
edit edit source- ^ a b Lattimore, Tor; Szepesvári, Csaba (2020). Bandit Algorithms. Cambridge University Press. doi:10.1017/9781108571401.
- ^ Jin, Tianyuan; Xu, Pan; Xiao, Xiaokui; Gu, Quanquan (2021). "Double Explore-then-Commit: Asymptotic Optimality and Beyond". Conference on Learning Theory. Proceedings of Machine Learning Research. pp. 2584–2633.
- ^ Nie, Guanyu; Agarwal, Mridul; Umrawal, Abhishek Kumar; Aggarwal, Vaneet; Quinn, Christopher John (2022). "An Explore-then-Commit Algorithm for Submodular Maximization under Full-Bandit Feedback". Uncertainty in Artificial Intelligence. Proceedings of Machine Learning Research. pp. 1541–1551.
- ^ Garivier, Aurélien; Kaufmann, Emilie; Lattimore, Tor (2016). "On Explore-Then-Commit Strategies". Advances in Neural Information Processing Systems 29.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1360960470 under CC BY-SA 4.0; modifications have been made.