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

Lilian Besson, Emilie KaufmannarXiv 2018 · OpenReview

Abstract

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 $R_T = O(\sqrt{T})$ but cannot conserve (distribution-dependent) bounds in $R_T = O(\log T)$. We give insights as to why exponential doubling tricks may be better, as they conserve bounds in $R_T = O(\log T)$, and are close to conserving bounds in $R_T = O(\sqrt{T})$.

Introduction

In the Multi-Armed Bandit (MAB) framework, an agent seeks to maximize cumulative rewards by choosing between several "arms" with unknown reward distributions. A significant portion of state-of-the-art MAB algorithms are designed for a fixed, known time horizon $T$. However, in practical applications such as clinical trials or real-time bidding, the duration of the experiment is rarely known in advance. This necessitates the development of anytime algorithms—algorithms that perform optimally regardless of when the process is terminated.

The "Doubling Trick" is the standard meta-algorithm for converting a fixed-horizon algorithm into an anytime one. It operates by dividing time into a sequence of intervals, running the fixed-horizon algorithm from scratch at the start of each new interval with a horizon length corresponding to that interval. While this technique is ubiquitous, its impact on different types of regret bounds—specifically minimax ($O(\sqrt{T})$) and distribution-dependent ($O(\log T)$) bounds—has lacked a comprehensive comparative analysis until now.

The Doubling Trick Framework

This paper formally analyzes the Doubling Trick ($DT$) using two distinct families of doubling sequences:

  1. Geometric Growth: The horizon of the $i$-th period is defined as $T_i = \lceil T_0 b^i \rceil$ (e.g., $2, 4, 8, 16, \dots$).
  2. Exponential Growth: The horizon grows much faster, defined as $T_i = \lceil \frac{T_0}{a} a^{b^i} \rceil$ (e.g., $2, 4, 16, 256, \dots$).

The researchers derived general upper and lower bounds for the regret of anytime versions of algorithms that satisfy generic regret bounds of the form $R_T = O(T^\gamma (\log T)^\delta)$. These theoretical findings were then validated using modern non-anytime algorithms: AFHG (for Gaussian bandits) and kl-UCB++ (for Bernoulli bandits).

Key Insights: The Failure of Geometric Doubling

A primary contribution of this work is the proof that geometric doubling is insufficient for preserving logarithmic regret.

In stochastic bandit problems, the gold standard for regret is $O(\log T)$. However, when a geometric doubling trick is applied, the algorithm restarts too frequently. Each restart introduces a new logarithmic regret term. Summing these terms over the sequence of intervals results in a total regret of $O(\log^2 T)$. This "blow up" represents a significant loss in efficiency. Mathematically, Theorems 4 and 5 prove that while geometric doubling successfully preserves minimax bounds ($O(\sqrt{T})$), it fundamentally fails to maintain the logarithmic rate.

The Case for Exponential Doubling

To address the limitations of geometric sequences, the authors propose and analyze exponential doubling. Because exponential sequences grow at an accelerating rate, the number of restarts is significantly reduced. Theorem 7 demonstrates that this faster growth allows the anytime algorithm to preserve the $O(\log T)$ bound.

However, this improvement comes with a trade-off. While exponential doubling is superior for logarithmic regret, it can lead to a substantial "manipulative loss" in the minimax ($O(\sqrt{T})$) setting unless the initial parameters (like the first step $T_0$) are tuned with extreme precision. This suggests that the choice of doubling sequence must be carefully aligned with the expected regret profile of the underlying algorithm.

Empirical Evaluation and Heuristics

The theoretical results were confirmed through simulations on synthetic environments, including Bernoulli bandits (with both easy and random mean distributions) and Gaussian bandits (focusing on "hard" instances with close means).

For algorithms like kl-UCB++, simulations showed that a fast-growing exponential sequence ($T_i = 200 \times 2^i$) allowed the anytime version to track the performance of the fixed-horizon version closely. In contrast, geometric doubling showed a visible divergence in regret over time.

Additionally, the authors explored a "No Restart" heuristic. In this variant, the algorithm is not reset at the end of an interval; instead, its internal parameters are simply updated to reflect the new horizon. While this heuristic performed exceptionally well in empirical tests, the authors noted that it is significantly harder to analyze theoretically and cannot be applied to all algorithm classes, such as those relying on arm elimination.

Conclusion

The Doubling Trick is a powerful but nuanced tool. This research clarifies that for algorithms intended to achieve logarithmic regret, geometric doubling is a sub-optimal choice, and exponential doubling should be preferred. However, doubling tricks generally introduce a multiplicative constant factor—a "price of adaptivity"—that prevents them from reaching asymptotic optimality. Future work remains to develop a formal regret upper bound for the "No Restart" heuristic and to determine if any doubling-style meta-algorithm can ever match the exact constants of optimal fixed-horizon algorithms.

Summary updated

Abstract

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 $R\_T = O(\sqrt{T})$ but cannot conserve (distribution-dependent) bounds in $R\_T = O(\log T)$. We give insights as to why exponential doubling tricks may be better, as they conserve bounds in $R\_T = O(\log T)$, and are close to conserving bounds in $R\_T = O(\sqrt{T})$.
BibTeX
@misc{besson2018what,
  author = {Lilian Besson and Emilie Kaufmann},
  title = {{What Doubling Tricks Can and Can't Do for Multi-Armed Bandits}},
  year = {2018},
  eprint = {1803.06971},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.06971},
}

Loading related content...

Figure