Old Dog Learns New Tricks: Randomized UCB for Bandit Problems

Sharan Vaswani, Abbas Mehrabian, Audrey Durand, Branislav Kveton

Abstract

We propose $\tt RandUCB$, a bandit strategy that builds on theoretically derived confidence intervals similar to upper confidence bound (UCB) algorithms, but akin to Thompson sampling (TS), it uses randomization to trade off exploration and exploitation. In the $K$-armed bandit setting, we show that there are infinitely many variants of $\tt RandUCB$, all of which achieve the minimax-optimal $\widetilde{O}(\sqrt{K T})$ regret after $T$ rounds. Moreover, for a specific multi-armed bandit setting, we show that both UCB and TS can be recovered as special cases of $\tt RandUCB$. For structured bandits, where each arm is associated with a $d$-dimensional feature vector and rewards are distributed according to a linear or generalized linear model, we prove that $\tt RandUCB$ achieves the minimax-optimal $\widetilde{O}(d \sqrt{T})$ regret even in the case of infinitely many arms. Through experiments in both the multi-armed and structured bandit settings, we demonstrate that $\tt RandUCB$ matches or outperforms TS and other randomized exploration strategies. Our theoretical and empirical results together imply that $\tt RandUCB$ achieves the best of both worlds.

Introduction

The multi-armed bandit (MAB) problem is a fundamental framework for sequential decision-making under uncertainty, characterized by the classic exploration-exploitation trade-off. Two primary paradigms have dominated the field: Upper Confidence Bound (UCB) algorithms and Thompson Sampling (TS). UCB algorithms employ "optimism in the face of uncertainty" by selecting arms based on deterministic upper bounds of their estimated means. While theoretically robust, UCB is often overly conservative in practice. Conversely, Thompson Sampling uses randomized exploration based on posterior distributions, frequently yielding superior empirical performance but presenting significant challenges for theoretical analysis in complex settings like Generalized Linear Models (GLMs).

This paper introduces RandUCB, a meta-algorithm designed to bridge this gap. By randomizing the width of the confidence intervals used in UCB, RandUCB combines the analytical tractability of UCB with the empirical agility of randomized exploration.

The RandUCB Algorithm

RandUCB modifies the standard UCB decision rule. In a traditional UCB setting, the agent selects the arm $i$ that maximizes: $$\hat{\mu}_{i,t-1} + \beta \cdot \sigma_{i,t-1}$$ where $\hat{\mu}$ is the estimated mean, $\sigma$ is the standard deviation (confidence width), and $\beta$ is a fixed constant.

RandUCB replaces the deterministic $\beta$ with a random variable $Z_t$. In each round $t$, a single value $Z_t$ is sampled from a distribution (typically a truncated Gaussian) and applied to all arms: $$\text{Arm}_t = \arg\max_{i} ( \hat{\mu}_{i,t-1} + Z_t \cdot \sigma_{i,t-1} )$$

A key design choice is coupling: the same $Z_t$ is used for all arms in a single round. This "shared jitter" helps the algorithm maintain optimism while allowing for the randomized exploration characteristic of Thompson Sampling.

Theoretical Guarantees

The authors demonstrate that RandUCB is a versatile framework capable of recovering both UCB and TS as special cases through specific choices of the distribution for $Z_t$. More importantly, they provide strong regret bounds:

  • Multi-armed Bandits: RandUCB achieves minimax-optimal regret of $\widetilde{O}(\sqrt{KT})$ for $K$ arms over $T$ rounds.
  • Linear Bandits: In the structured setting with $d$-dimensional features, RandUCB achieves $\widetilde{O}(d\sqrt{T})$ regret, even with an infinite number of arms. This is the first randomized algorithm to achieve near-optimal dependence on $d$ in the infinite-armed case.

Experimental Evaluation

The performance of RandUCB was evaluated across three primary benchmarks: Multi-armed Bandits (Bernoulli and Beta distributions), Linear Bandits, and Logistic (GLM) Bandits.

Regret comparison across MAB (a), Linear (b), and GLM (c) bandit settings. RandUCB (red) consistently matches or outperforms state-of-the-art baselines like Thompson Sampling and LinPHE.

As shown in the figures above, RandUCB consistently performs among the top strategies. In MAB settings, it outperforms standard UCB1 and Thompson Sampling. In structured settings (Linear and GLM), it remains competitive with or superior to specialized algorithms like LinPHE and GLM-TS, demonstrating its scalability to high-dimensional problems.

Conclusion

RandUCB offers a compelling "best of both worlds" solution for bandit problems. It provides the rigorous theoretical guarantees expected of UCB-style algorithms while delivering the high empirical performance associated with Thompson Sampling. Its computational simplicity—requiring only point estimates and standard deviations—makes it an attractive candidate for real-world applications and potentially for more complex reinforcement learning tasks.

Summary updated

Abstract

We propose $\tt RandUCB$, a bandit strategy that builds on theoretically derived confidence intervals similar to upper confidence bound (UCB) algorithms, but akin to Thompson sampling (TS), it uses randomization to trade off exploration and exploitation. In the $K$-armed bandit setting, we show that there are infinitely many variants of $\tt RandUCB$, all of which achieve the minimax-optimal $\widetilde{O}(\sqrt{K T})$ regret after $T$ rounds. Moreover, for a specific multi-armed bandit setting, we show that both UCB and TS can be recovered as special cases of $\tt RandUCB$. For structured bandits, where each arm is associated with a $d$-dimensional feature vector and rewards are distributed according to a linear or generalized linear model, we prove that $\tt RandUCB$ achieves the minimax-optimal $\widetilde{O}(d \sqrt{T})$ regret even in the case of infinitely many arms. Through experiments in both the multi-armed and structured bandit settings, we demonstrate that $\tt RandUCB$ matches or outperforms TS and other randomized exploration strategies. Our theoretical and empirical results together imply that $\tt RandUCB$ achieves the best of both worlds.
BibTeX
@inproceedings{vaswani2020old,
  author = {Sharan Vaswani and Abbas Mehrabian and Audrey Durand and Branislav Kveton},
  title = {{Old Dog Learns New Tricks: Randomized UCB for Bandit Problems}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=rzGWk3i3Ix5},
}

Loading related content...

Figure