mlsanityData to 7 Oct 2026

lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits

arXiv 1312.7308 ↗First posted 27 Dec 2013stat.ML cs.LGcited by 148

Not on the map. Why?

Abstract (arXiv)

The paper proposes a novel upper confidence bound (UCB) procedure for identifying the arm with the largest mean in a multi-armed bandit game in the fixed confidence setting using a small number of total samples. The procedure cannot be improved in the sense that the number of samples required to identify the best arm is within a constant factor of a lower bound based on the law of the iterated logarithm (LIL). Inspired by the LIL, we construct our confidence bounds to explicitly account for the infinite time horizon of the algorithm. In addition, by using a novel stopping time for the algorithm we avoid a union bound over the arms that has been observed in other UCB-type algorithms. We prove that the algorithm is optimal up to constants and also show through simulations that it provides superior performance with respect to the state-of-the-art.

Key facts. Cited by 148 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Dec 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 26; 2022: 29; 2023: 28; 2024: 20; 2025: 22; 2026: 23.

148 papers.

Sort:

By area:

  1. 2022Anytime-valid off-policy inference for contextual banditscited by 37
  2. 2022Top Two Algorithms Revisitedcited by 34
  3. 2025FOCUS: Efficient Keyframe Selection for Long Video Understandingcited by 30
  4. 2021Best Arm Identification with Safety Constraintscited by 25
  5. 2022Revisiting Simple Regret: Fast Rates for Returning a Good Armcited by 25
  6. 2021Online certification of preference-based fairness for personalized recommender systemscited by 22
  7. 2021Near-optimal inference in adaptive linear regressioncited by 20
  8. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  9. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 19
  10. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  11. 2021Martingale Methods for Sequential Estimation of Convex Functionals and Divergencescited by 17
  12. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
38 more
  1. 2021Bandits with many optimal armscited by 16
  2. 2022Almost Optimal Variance-Constrained Best Arm Identificationcited by 16
  3. 2022Active Learning with Safety Constraintscited by 16
  4. 2024On Speeding Up Language Model Evaluationcited by 14
  5. 2021Pure Exploration in Kernel and Neural Banditscited by 13
  6. 2021Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Banditscited by 13
  7. 2023Adaptive Algorithms for Relaxed Pareto Set Identificationcited by 13
  8. 2023Bandit Pareto Set Identification: the Fixed Budget Settingcited by 13
  9. 2025Sample Complexity and Representation Ability of Test-time Scaling Paradigmscited by 12
  10. 2022Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Banditscited by 11
  11. 2022Almost Cost-Free Communication in Federated Best Arm Identificationcited by 11
  12. 2022Non-Asymptotic Analysis of a UCB-based Top Two Algorithmcited by 11
  13. 2021Understanding the Origin of Information-Seeking Exploration in Probabilistic Objectives for Controlcited by 10
  14. 2024Model Assessment and Selection under Temporal Distribution Shiftcited by 10
  15. 2021Variance-Dependent Best Arm Identificationcited by 9
  16. 2022Combinatorial Pure Exploration of Causal Banditscited by 9
  17. 2023Practical Bandits: An Industry Perspectivecited by 9
  18. 2023Tight Regret Bounds for Single-pass Streaming Multi-armed Banditscited by 9
  19. 2024Online Experimental Design With Estimation-Regret Trade-off Under Network Interferencecited by 9
  20. 2021The Role of Contextual Information in Best Arm Identificationcited by 8
  21. 2021Learning from an Exploring Demonstrator: Optimal Reward Estimation for Banditscited by 8
  22. 2021A unified framework for bandit multiple testingcited by 8
  23. 2021Best-Arm Identification in Correlated Multi-Armed Banditscited by 8
  24. 2021Comparing Sequential Forecasterscited by 8
  25. 2022Federated Best Arm Identification with Heterogeneous Clientscited by 8
  26. 2023Optimal Batched Best Arm Identificationcited by 8
  27. 2024Optimal Multi-Fidelity Best-Arm Identificationcited by 8
  28. 2025Strategic Scaling of Test-Time Compute: A Bandit Learning Approachcited by 8
  29. 2021A Non-asymptotic Approach to Best-Arm Identification for Gaussian Banditscited by 7
  30. 2021Bandit Quickest Changepoint Detectioncited by 7
  31. 2023Huber-Robust Confidence Sequencescited by 7
  32. 2024Query-Efficient Correlation Clustering with Noisy Oraclecited by 7
  33. 2024Tighter Confidence Bounds for Sequential Kernel Regressioncited by 7
  34. 2024Taming False Positives in Out-of-Distribution Detection with Human Feedbackcited by 7
  35. 2026Best Arm Identification with LLM Judges and Limited Humancited by 7
  36. 2021Mean-based Best Arm Identification in Stochastic Bandits under Reward Contaminationcited by 6
  37. 2022Parallel Best Arm Identification in Heterogeneous Environmentscited by 6
  38. 2023Semi-parametric inference based on adaptively collected datacited by 6

50 most cited of 148 All 148 (JSON)