mlsanityData to 13 Oct 2026

On Explore-Then-Commit Strategies

arXiv 1605.08988 ↗First posted 29 May 2016math.ST cs.LG stat.THcited by 46

Not on the map. Why?

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.

Key facts. Cited by 46 papers in the map (data through 13 Oct 2026). First posted on arXiv 29 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 8; 2022: 5; 2023: 10; 2024: 6; 2025: 8; 2026: 9.

46 papers.

Sort:

By area:

  1. 2023Diffusion Models for Black-Box Optimizationcited by 75
  2. 2024Aligning LLM Agents by Learning Latent Preference from User Editscited by 66
  3. 2022Generative Pretraining for Black-Box Optimizationcited by 36
  4. 2021A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithmscited by 30
  5. 2022A survey on multi-player banditscited by 18
  6. 2023Player-optimal Stable Regret for Bandit Learning in Matching Marketscited by 17
  7. 2021Bandits with many optimal armscited by 16
  8. 2021Minimal Expected Regret in Linear Quadratic Controlcited by 13
  9. 2022Non-Stationary Bandits with Auto-Regressive Temporal Dependencycited by 10
  10. 2023Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithmscited by 10
  11. 2021Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verificationcited by 9
  12. 2021From Finite to Countable-Armed Banditscited by 8
34 more
  1. 2023Optimal Batched Best Arm Identificationcited by 8
  2. 2024Putting Gale & Shapley to Work: Guaranteeing Stability Through Learningcited by 7
  3. 2022Meta Policy Learning for Cold-Start Conversational Recommendationcited by 6
  4. 2024Improved Bandits in Many-to-one Matching Markets with Incentive Compatibilitycited by 6
  5. 2024Logarithmic Neyman Regret for Adaptive Estimation of the Average Treatment Effectcited by 4
  6. 2025Linear Bandits on Ellipsoids: Minimax Optimal Algorithmscited by 4
  7. 2026A Diffusion Analysis of Policy Gradient for Stochastic Banditscited by 4
  8. 2023Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costscited by 3
  9. 2024Online Policy Learning and Inference by Matrix Completioncited by 3
  10. 2021Sequential Choice Bandits with Feedback for Personalizing users' experiencecited by 2
  11. 2024Replicability is Asymptotically Free in Multi-armed Banditscited by 2
  12. 2025Optimistic Algorithms for Adaptive Estimation of the Average Treatment Effectcited by 2
  13. 2026Efficient Adversarial Attacks on High-dimensional Offline Banditscited by 2
  14. 2021Active Coveringcited by 1
  15. 2021Tuning Confidence Bound for Stochastic Bandits with Bandit Distancecited by 1
  16. 2023Leveraging Reviews: Learning to Price with Buyer and Seller Uncertaintycited by 1
  17. 2023Simple Modification of the Upper Confidence Bound Algorithm by Generalized Weighted Averagescited by 1
  18. 2025Optimization of Epsilon-Greedy Explorationcited by 1
  19. 2025Two-Player Zero-Sum Games with Bandit Feedbackcited by 1
  20. 2025Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspectivecited by 1
  21. 2025Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicalitycited by 1
  22. 2022On Penalization in Stochastic Multi-armed Banditscited by 0
  23. 2023Efficient and Interpretable Bandit Algorithmscited by 0
  24. 2023Little Exploration is All You Needcited by 0
  25. 2023Forced Exploration in Bandit Problemscited by 0
  26. 2025Infrequent Exploration in Linear Banditscited by 0
  27. 2025Behavioural Effects of Agentic Messaging: A Case Study on a Financial Service Applicationcited by 0
  28. 2026Sampling-Based Safe Reinforcement Learningcited by 0
  29. 2026Online Market Making and the Value of Observing the Order Bookcited by 0
  30. 2026Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Banditscited by 0
  31. 2026Human Decision-Making with AI Assistance under Correlated Featurescited by 0
  32. 2026Experimentation and Commitment under Reward Shiftscited by 0
  33. 2026Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stoppingcited by 0
  34. 2026A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Setscited by 0