# Variance-Optimal Arm Selection: Misallocation Minimization and Best Arm Identification

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 17 May 2025.

## Builds on (most cited first, 10 of 10)

- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Thompson Sampling Algorithms for Mean-Variance Bandits](https://mlsanity.com/paper/2002.00232/) (2020)
- [Efficient-UCBV: An Almost Optimal Algorithm using Variance Estimates](https://mlsanity.com/paper/1711.03591/) (2017)
- [Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards](https://mlsanity.com/paper/1906.00569/) (2019)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits](https://mlsanity.com/paper/2108.11345/) (2021)
- [Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/2008.13629/) (2020)
- [A Distribution Optimization Framework for Confidence Bounds of Risk Measures](https://mlsanity.com/paper/2306.07059/) (2023)
- [Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Bandits](https://mlsanity.com/paper/2406.06552/) (2024)

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

- [Order Optimal Regret Bounds for Sharpe Ratio Optimization under Thompson Sampling](https://mlsanity.com/paper/2508.13749/) (2025)

## Abstract (arXiv)

This paper focuses on selecting the arm with the highest variance from a set of K independent arms. Specifically, we focus on two settings: (i) misallocation minimization setting, that penalizes the number of pulls of suboptimal arms in terms of variance, and (ii) fixed-budget best arm identification setting, that evaluates the ability of an algorithm to determine the arm with the highest variance after a fixed number of pulls. We develop a novel online algorithm called UCB-VV for the misallocation minimization (MM) and show that its upper bound on misallocation for bounded rewards evolves as Oleft(lognright) where n is the horizon. By deriving the lower bound on the misallocation, we show that UCB-VV is order optimal. For the fixed budget best arm identification (BAI) setting we propose the SHVV algorithm. We show that the upper bound of the error probability of SHVV evolves as expleft(-fracnlog(K) Hright), where H represents the complexity of the problem, and this rate matches the corresponding lower bound. We extend the framework from bounded distributions to sub-Gaussian distributions using a novel concentration inequality on the sample variance and standard deviation. Leveraging the same, we derive a concentration inequality for the empirical Sharpe ratio (SR) for sub-Gaussian distributions, which was previously unknown in the literature. Empirical simulations show that UCB-VV consistently outperforms ε-greedy across different sub-optimality gaps though it is surpassed by VTS, which exhibits the lowest misallocation, albeit lacking in theoretical guarantees. We also illustrate the superior performance of SHVV, for a fixed budget setting under 6 different setups against uniform sampling. Finally, we conduct a case study to empirically evaluate the performance of the UCB-VV and SHVV in call option trading on 100 stocks generated using GBM.