Abstract
We propose RandUCB, a bandit strategy that uses theoretically derived confidence intervals similar to upper confidence bound (UCB) algorithms, but akin to Thompson sampling (TS), uses randomization. By randomizing the width of these intervals, RandUCB bridges the gap between the two most popular exploration paradigms. It achieves the minimax-optimal regret of UCB while matching or exceeding the superior empirical performance of Thompson Sampling across multi-armed, linear, and generalized linear bandit settings.
Introduction
The multi-armed bandit (MAB) problem is a fundamental framework for decision-making under uncertainty, requiring a balance between exploration (learning about new actions) and exploitation (choosing the best-known action). Traditionally, two approaches have dominated:
- Optimism in the Face of Uncertainty (OFU/UCB): These algorithms use deterministic confidence intervals. While theoretically robust, they are often overly conservative in practice, leading to mediocre performance on typical problems.
- Thompson Sampling (TS): A randomized approach that samples from a posterior distribution. It often yields superior empirical results but is difficult to analyze theoretically in structured settings and can be computationally demanding when no closed-form posterior exists.
RandUCB aims to provide a "best of both worlds" solution: an algorithm that is computationally efficient, theoretically optimal, and empirically high-performing.
The RandUCB Meta-Algorithm
The core innovation of RandUCB is a simple but powerful modification to the standard UCB formula. Instead of using a fixed constant $\beta$ to scale the confidence interval, RandUCB introduces a random variable $Z_t$:
$$\text{Score}_t = \text{Estimate}_t + Z_t \times \text{Confidence Interval}_t$$
The algorithm then selects the arm with the highest score in each round.
Key Design Principles
- Randomized Optimism: By sampling $Z_t$ from a discretized, truncated Gaussian distribution, the algorithm explores different levels of optimism in each round.
- Coupled Randomization: Surprisingly, the authors found that using a single $Z_t$ for all arms in a given round ("coupling") performs better and simplifies analysis compared to independent sampling for each arm.
- Versatility: RandUCB is a meta-algorithm applicable to standard MAB, Linear Bandits, and Generalized Linear Bandits (GLB). For GLBs, it avoids the complex posterior sampling required by TS by simply randomizing existing, easy-to-calculate UCB bounds.
Experimental Evaluation
The authors evaluated RandUCB against state-of-the-art baselines in several synthetic environments to precisely control the reward gaps between arms.
Multi-Armed Bandits (MAB)
In standard MAB settings with Bernoulli and Beta reward distributions, RandUCB consistently outperformed UCB1 and often surpassed Thompson Sampling (B-TS), particularly in "hard" configurations with small reward gaps.
Structured Bandits
In linear and logistic (GLB) environments, RandUCB matched the performance of specialized strategies while maintaining a simpler implementation. It is notably the first randomized algorithm to achieve near-optimal regret in the infinite-armed case for structured bandits.
Key Insights and Results
- Theoretical Optimality: RandUCB achieves minimax-optimal regret: $O(\sqrt{KT})$ for $K$ arms over $T$ rounds in MAB, and $O(d\sqrt{T})$ for $d$-dimensional structured bandits.
- Unification: The framework demonstrates that UCB and TS can be viewed as special cases of randomized optimism, suggesting that the "magic" of TS stems from this underlying principle.
- Efficiency: By avoiding complex posterior updates or Laplace approximations, RandUCB provides a scalable alternative for GLBs where traditional TS is computationally prohibitive.
Conclusion
RandUCB successfully combines the theoretical rigor of UCB with the empirical flexibility of Thompson Sampling. Its simplicity and robustness—requiring minimal hyper-parameter tuning—make it a powerful tool for a wide range of bandit problems. Future work may extend this randomized confidence interval approach to adversarial settings or more complex decision-making frameworks like Monte-Carlo Tree Search (MCTS).
Summary updated