# On Explore-Then-Commit Strategies

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2016.

## Built on by (most cited first, 30 of 47)

- [Diffusion Models for Black-Box Optimization](https://mlsanity.com/paper/2306.07180/) (2023)
- [Aligning LLM Agents by Learning Latent Preference from User Edits](https://mlsanity.com/paper/2404.15269/) (2024)
- [Generative Pretraining for Black-Box Optimization](https://mlsanity.com/paper/2206.10786/) (2022)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Minimal Expected Regret in Linear Quadratic Control](https://mlsanity.com/paper/2109.14429/) (2021)
- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms](https://mlsanity.com/paper/2309.00591/) (2023)
- [Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification](https://mlsanity.com/paper/2102.07711/) (2021)
- [From Finite to Countable-Armed Bandits](https://mlsanity.com/paper/2105.10721/) (2021)
- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility](https://mlsanity.com/paper/2401.01528/) (2024)
- [Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning](https://mlsanity.com/paper/2410.04376/) (2024)
- [Meta Policy Learning for Cold-Start Conversational Recommendation](https://mlsanity.com/paper/2205.11788/) (2022)
- [Logarithmic Neyman Regret for Adaptive Estimation of the Average Treatment Effect](https://mlsanity.com/paper/2411.14341/) (2024)
- [Linear Bandits on Ellipsoids: Minimax Optimal Algorithms](https://mlsanity.com/paper/2502.17175/) (2025)
- [A Diffusion Analysis of Policy Gradient for Stochastic Bandits](https://mlsanity.com/paper/2603.10219/) (2026)
- [Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs](https://mlsanity.com/paper/2308.04314/) (2023)
- [Online Policy Learning and Inference by Matrix Completion](https://mlsanity.com/paper/2404.17398/) (2024)
- [Sequential Choice Bandits with Feedback for Personalizing users' experience](https://mlsanity.com/paper/2101.01572/) (2021)
- [Replicability is Asymptotically Free in Multi-armed Bandits](https://mlsanity.com/paper/2402.07391/) (2024)
- [Optimistic Algorithms for Adaptive Estimation of the Average Treatment Effect](https://mlsanity.com/paper/2502.04673/) (2025)
- [Efficient Adversarial Attacks on High-dimensional Offline Bandits](https://mlsanity.com/paper/2602.01658/) (2026)
- [Active Covering](https://mlsanity.com/paper/2106.02552/) (2021)
- [Tuning Confidence Bound for Stochastic Bandits with Bandit Distance](https://mlsanity.com/paper/2110.02690/) (2021)
- [Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty](https://mlsanity.com/paper/2302.09700/) (2023)
- [Simple Modification of the Upper Confidence Bound Algorithm by Generalized Weighted Averages](https://mlsanity.com/paper/2308.14350/) (2023)
- [Forced Exploration in Bandit Problems](https://mlsanity.com/paper/2312.07285/) (2023)

## Abstract (arXiv)

We study the problem of minimising regret in two-armed bandit problems with Gaussian rewards. Our objective is to use this simple setting to illustrate that strategies based on an exploration phase (up to a stopping time) followed by exploitation are necessarily suboptimal. The results hold regardless of whether or not the difference in means between the two arms is known. Besides the main message, we also refine existing deviation inequalities, which allow us to design fully sequential strategies with finite-time regret guarantees that are (a) asymptotically optimal as the horizon grows and (b) order-optimal in the minimax sense. Furthermore we provide empirical evidence that the theory also holds in practice and discuss extensions to non-gaussian and multiple-armed case.