mlsanityData to 14 Oct 2026

What Doubling Tricks Can and Can't Do for Multi-Armed Bandits

arXiv 1803.06971 ↗First posted 19 Mar 2018stat.ML cs.LG math.STcited by 71

Not on the map. Why?

Abstract (arXiv)

An online reinforcement learning algorithm is anytime if it does not need to know in advance the horizon T of the experiment. A well-known technique to obtain an anytime algorithm from any non-anytime algorithm is the "Doubling Trick". In the context of adversarial or stochastic multi-armed bandits, the performance of an algorithm is measured by its regret, and we study two families of sequences of growing horizons (geometric and exponential) to generalize previously known results that certain doubling tricks can be used to conserve certain regret bounds. In a broad setting, we prove that a geometric doubling trick can be used to conserve (minimax) bounds in RT = O(√T) but cannot conserve (distribution-dependent) bounds in RT = O(log T). We give insights as to why exponential doubling tricks may be better, as they conserve bounds in RT = O(log T), and are close to conserving bounds in RT = O(√T).

Key facts. Cited by 71 papers in the map (data through 14 Oct 2026). First posted on arXiv 19 Mar 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 14; 2022: 13; 2023: 12; 2024: 8; 2025: 9; 2026: 15.

71 papers.

Sort:

By area:

  1. 2022The Primacy Bias in Deep Reinforcement Learningcited by 247
  2. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 31
  3. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 21
  4. 2021Batched Thompson Samplingcited by 19
  5. 2023A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedbackcited by 19
  6. 2023Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedbackcited by 19
  7. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 18
  8. 2023Combinatorial Stochastic-Greedy Banditcited by 18
  9. 2023Combinatorial Neural Banditscited by 16
  10. 2024Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decodingcited by 15
  11. 2021Learning to Persuade on the Fly: Robustness Against Ignorancecited by 12
  12. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
38 more
  1. 2024Federated Combinatorial Multi-Agent Multi-Armed Banditscited by 11
  2. 2022Bayesian Optimization under Stochastic Delayed Feedbackcited by 10
  3. 2021Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verificationcited by 9
  4. 2021Generalized non-stationary banditscited by 8
  5. 2021From Finite to Countable-Armed Banditscited by 8
  6. 2021Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributionscited by 8
  7. 2022Logarithmic regret bounds for continuous-time average-reward Markov decision processescited by 8
  8. 2023Improving Adaptive Online Learning Using Refined Discretizationcited by 8
  9. 2021Be Greedy in Multi-Armed Banditscited by 7
  10. 2024Low-rank Matrix Bandits with Heavy-tailed Rewardscited by 7
  11. 2024Contractual Reinforcement Learning: Pulling Arms with Invisible Handscited by 5
  12. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  13. 2022Dueling Bandits: From Two-dueling to Multi-duelingcited by 4
  14. 2024Federated Linear Contextual Bandits with Heterogeneous Clientscited by 4
  15. 2022Federated Online Sparse Decision Makingcited by 3
  16. 2023Primal-Dual Contextual Bayesian Optimization for Control System Online Optimization with Time-Average Constraintscited by 3
  17. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 3
  18. 2021Sequential Choice Bandits with Feedback for Personalizing users' experiencecited by 2
  19. 2022Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demandcited by 2
  20. 2022Bridging Adversarial and Nonstationary Multi-armed Banditcited by 2
  21. 2022Autonomous Drug Design with Multi-Armed Banditscited by 2
  22. 2022Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Modelcited by 2
  23. 2025Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Banditscited by 2
  24. 2025Re-evaluating Minimum Bayes Risk Decoding for Automatic Speech Recognitioncited by 2
  25. 2026A single algorithm for both restless and rested rotting banditscited by 2
  26. 2021Online Sub-Sampling for Reinforcement Learning with General Function Approximationcited by 1
  27. 2021Dynamic Selection in Algorithmic Decision-makingcited by 1
  28. 2021Bandits with Dynamic Arm-acquisition Costscited by 1
  29. 2022A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Designcited by 1
  30. 2023Bayesian Optimization of Expensive Nested Grey-Box Functionscited by 1
  31. 2024Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processescited by 1
  32. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  33. 2024Localized exploration in contextual dynamic pricing achieves dimension-free regretcited by 1
  34. 2025Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approachcited by 1
  35. 2025Safe Learning Under Irreversible Dynamics via Asking for Helpcited by 1
  36. 2025Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inferencecited by 1
  37. 2025Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraintscited by 1
  38. 2026Shuffle and Joint Differential Privacy for Generalized Linear Contextual Banditscited by 1

50 most cited of 71 All 71 (JSON)