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

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

## Key facts

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

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

- [The Primacy Bias in Deep Reinforcement Learning](https://mlsanity.com/paper/2205.07802/) (2022)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Batched Thompson Sampling](https://mlsanity.com/paper/2110.00202/) (2021)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Combinatorial Neural Bandits](https://mlsanity.com/paper/2306.00242/) (2023)
- [Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2401.02749/) (2024)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)
- [Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification](https://mlsanity.com/paper/2102.07711/) (2021)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [From Finite to Countable-Armed Bandits](https://mlsanity.com/paper/2105.10721/) (2021)
- [Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions](https://mlsanity.com/paper/2106.13669/) (2021)
- [Logarithmic regret bounds for continuous-time average-reward Markov decision processes](https://mlsanity.com/paper/2205.11168/) (2022)
- [Improving Adaptive Online Learning Using Refined Discretization](https://mlsanity.com/paper/2309.16044/) (2023)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Dueling Bandits: From Two-dueling to Multi-dueling](https://mlsanity.com/paper/2211.10293/) (2022)
- [Federated Linear Contextual Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2403.00116/) (2024)
- [Federated Online Sparse Decision Making](https://mlsanity.com/paper/2202.13448/) (2022)
- [Primal-Dual Contextual Bayesian Optimization for Control System Online Optimization with Time-Average Constraints](https://mlsanity.com/paper/2304.06104/) (2023)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Sequential Choice Bandits with Feedback for Personalizing users' experience](https://mlsanity.com/paper/2101.01572/) (2021)

## 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).