# Efficient-UCBV: An Almost Optimal Algorithm using Variance Estimates

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2017.

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

- [Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits](https://mlsanity.com/paper/2310.00968/) (2023)
- [ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling](https://mlsanity.com/paper/2203.04510/) (2022)
- [Stochastic Multi-Armed Bandits with Control Variates](https://mlsanity.com/paper/2105.03962/) (2021)
- [Offline-to-online hyperparameter transfer for stochastic bandits](https://mlsanity.com/paper/2501.02926/) (2025)
- [Improving LLM-based Global Optimization with Search Space Partitioning](https://mlsanity.com/paper/2505.21372/) (2025)
- [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024)
- [SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits](https://mlsanity.com/paper/2301.12357/) (2023)
- [Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling](https://mlsanity.com/paper/2303.09033/) (2023)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards](https://mlsanity.com/paper/2304.14989/) (2023)
- [Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Bandits](https://mlsanity.com/paper/2406.06552/) (2024)
- [Learnable Sparse Customization in Heterogeneous Edge Computing](https://mlsanity.com/paper/2412.07216/) (2024)
- [Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2511.02123/) (2025)
- [Variance-Optimal Arm Selection: Misallocation Minimization and Best Arm Identification](https://mlsanity.com/paper/2505.11985/) (2025)
- [A Framework for Fair Evaluation of Variance-Aware Bandit Algorithms](https://mlsanity.com/paper/2510.27001/) (2025)
- [Covariance-adapting algorithm for semi-bandits with application to sparse rewards](https://mlsanity.com/paper/2604.13738/) (2026)
- [On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback](https://mlsanity.com/paper/2503.05662/) (2025)
- [Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2508.06247/) (2025)
- [Complexity as Advantage: A Regret-Based Perspective on Emergent Structure](https://mlsanity.com/paper/2511.04590/) (2025)
- [Stochastic Multi-Armed Bandits with Limited Control Variates](https://mlsanity.com/paper/2603.02100/) (2026)

## Abstract (arXiv)

We propose a novel variant of the UCB algorithm (referred to as Efficient-UCB-Variance (EUCBV)) for minimizing cumulative regret in the stochastic multi-armed bandit (MAB) setting. EUCBV incorporates the arm elimination strategy proposed in UCB-Improved citepauer2010ucb, while taking into account the variance estimates to compute the arms' confidence bounds, similar to UCBV citepaudibert2009exploration. Through a theoretical analysis we establish that EUCBV incurs a gap-dependent regret bound of scriptsize Oleft( dfracKσ2max log (TDelta2 /K)Deltaright) after T trials, where Delta is the minimal gap between optimal and sub-optimal arms; the above bound is an improvement over that of existing state-of-the-art UCB algorithms (such as UCB1, UCB-Improved, UCBV, MOSS). Further, EUCBV incurs a gap-independent regret bound of scriptsize Oleft(√KTright) which is an improvement over that of UCB1, UCBV and UCB-Improved, while being comparable with that of MOSS and OCUCB. Through an extensive numerical study we show that EUCBV significantly outperforms the popular UCB variants (like MOSS, OCUCB, etc.) as well as Thompson sampling and Bayes-UCB algorithms.