# Old Dog Learns New Tricks: Randomized UCB for Bandit Problems

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Oct 2019.

## Built on by (most cited first, 21 of 21)

- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Optimal Design for Reward Modeling in RLHF](https://mlsanity.com/paper/2410.17055/) (2024)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [A general class of surrogate functions for stable and efficient reinforcement learning](https://mlsanity.com/paper/2108.05828/) (2021)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [When and why randomised exploration works (in linear bandits)](https://mlsanity.com/paper/2502.08870/) (2025)
- [Random Latent Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/2407.13755/) (2024)
- [Machine Learning for Online Algorithm Selection under Censored Feedback](https://mlsanity.com/paper/2109.06234/) (2021)
- [Randomized Confidence Bounds for Stochastic Partial Monitoring](https://mlsanity.com/paper/2402.05002/) (2024)
- [Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2506.01250/) (2025)
- [CORe: Capitalizing On Rewards in Bandit Exploration](https://mlsanity.com/paper/2103.04387/) (2021)
- [Some performance considerations when using multi-armed bandit algorithms in the presence of missing data](https://mlsanity.com/paper/2205.03820/) (2022)
- [Optimistic Thompson Sampling for No-Regret Learning in Unknown Games](https://mlsanity.com/paper/2402.09456/) (2024)
- [Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Bandits](https://mlsanity.com/paper/2307.03587/) (2023)
- [Exploration via Feature Perturbation in Contextual Bandits](https://mlsanity.com/paper/2510.17390/) (2025)
- [Conformal bandits: bringing statistical validity and reward efficiency under weak arm separability](https://mlsanity.com/paper/2512.09850/) (2025)
- [A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression](https://mlsanity.com/paper/2602.05019/) (2026)
- [Randomized Exploration for Linear Bandits via Absolute Perturbations](https://mlsanity.com/paper/2606.28616/) (2026)

## Abstract (arXiv)

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 widetildeO(√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 widetildeO(d √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.