# Double Explore-then-Commit: Asymptotic Optimality and Beyond

arXiv: https://arxiv.org/abs/2002.09174 · HTML: https://mlsanity.com/paper/2002.09174/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2020.

## Built on by (most cited first, 24 of 24)

- [Batched Neural Bandits](https://mlsanity.com/paper/2102.13028/) (2021)
- [Batched Thompson Sampling](https://mlsanity.com/paper/2110.00202/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms](https://mlsanity.com/paper/2309.00591/) (2023)
- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits](https://mlsanity.com/paper/2110.00158/) (2021)
- [Batched Nonparametric Contextual Bandits](https://mlsanity.com/paper/2402.17732/) (2024)
- [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026)
- [Replicability is Asymptotically Free in Multi-armed Bandits](https://mlsanity.com/paper/2402.07391/) (2024)
- [Batched Stochastic Bandit for Nondegenerate Functions](https://mlsanity.com/paper/2405.05733/) (2024)
- [Optimal and Practical Batched Linear Bandit Algorithm](https://mlsanity.com/paper/2507.08438/) (2025)
- [Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates](https://mlsanity.com/paper/2606.00984/) (2026)
- [Best Arm Identification in Batched Multi-armed Bandit Problems](https://mlsanity.com/paper/2312.13875/) (2023)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [A Batch Sequential Halving Algorithm without Performance Degradation](https://mlsanity.com/paper/2406.00424/) (2024)
- [On Penalization in Stochastic Multi-armed Bandits](https://mlsanity.com/paper/2211.08311/) (2022)
- [Efficient and Interpretable Bandit Algorithms](https://mlsanity.com/paper/2310.14751/) (2023)
- [Optimal Regret Bounds for Collaborative Learning in Bandits](https://mlsanity.com/paper/2312.09674/) (2023)
- [Breaking the log(1/Delta2) Barrier: Better Batched Best Arm Identification with Adaptive Grids](https://mlsanity.com/paper/2501.17370/) (2025)
- [A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond](https://mlsanity.com/paper/2502.07514/) (2025)
- [Batched Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2510.03798/) (2025)
- [The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin](https://mlsanity.com/paper/2511.03708/) (2025)
- [Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping](https://mlsanity.com/paper/2609.22690/) (2026)

## Abstract (arXiv)

We study the multi-armed bandit problem with subgaussian rewards. The explore-then-commit (ETC) strategy, which consists of an exploration phase followed by an exploitation phase, is one of the most widely used algorithms in a variety of online decision applications. Nevertheless, it has been shown in Garivier et al. (2016) that ETC is suboptimal in the asymptotic sense as the horizon grows, and thus, is worse than fully sequential strategies such as Upper Confidence Bound (UCB). In this paper, we show that a variant of ETC algorithm can actually achieve the asymptotic optimality for multi-armed bandit problems as UCB-type algorithms do and extend it to the batched bandit setting. Specifically, we propose a double explore-then-commit (DETC) algorithm that has two exploration and exploitation phases and prove that DETC achieves the asymptotically optimal regret bound. To our knowledge, DETC is the first non-fully-sequential algorithm that achieves such asymptotic optimality. In addition, we extend DETC to batched bandit problems, where (i) the exploration process is split into a small number of batches and (ii) the round complexity is of central interest. We prove that a batched version of DETC can achieve the asymptotic optimality with only a constant round complexity. This is the first batched bandit algorithm that can attain the optimal asymptotic regret bound and optimal round complexity simultaneously.