# Almost Optimal Variance-Constrained Best Arm Identification

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 54 references that are in the map.
- First posted on arXiv 25 Jan 2022.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Learning Bounds for Risk-sensitive Learning](https://mlsanity.com/paper/2006.08138/) (2020)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Thompson Sampling Algorithms for Mean-Variance Bandits](https://mlsanity.com/paper/2002.00232/) (2020)
- [Optimal Thompson Sampling strategies for support-aware CVaR bandits](https://mlsanity.com/paper/2012.05754/) (2020)
- [Multi-objective Contextual Bandit Problem with Similarity Information](https://mlsanity.com/paper/1803.04015/) (2018)
- [Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measure](https://mlsanity.com/paper/1604.05257/) (2016)
- [Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards](https://mlsanity.com/paper/1906.00569/) (2019)
- [Generalized Risk-Aversion in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1405.0833/) (2014)
- [Risk-Constrained Thompson Sampling for CVaR Bandits](https://mlsanity.com/paper/2011.08046/) (2020)
- [Variance-Dependent Best Arm Identification](https://mlsanity.com/paper/2106.10417/) (2021)
- [A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits](https://mlsanity.com/paper/2108.11345/) (2021)
- [Constrained regret minimization for multi-criterion multi-armed bandits](https://mlsanity.com/paper/2006.09649/) (2020)
- [Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/2008.13629/) (2020)
- [An Asymptotically Optimal Strategy for Constrained Multi-armed Bandit Problems](https://mlsanity.com/paper/1805.01237/) (2018)

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

- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Variance-Aware Sparse Linear Bandits](https://mlsanity.com/paper/2205.13450/) (2022)
- [Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget](https://mlsanity.com/paper/2211.14768/) (2022)
- [A Survey of Risk-Aware Multi-Armed Bandits](https://mlsanity.com/paper/2205.05843/) (2022)
- [Best Arm Identification with Resource Constraints](https://mlsanity.com/paper/2402.19090/) (2024)
- [Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Bandits](https://mlsanity.com/paper/2406.06552/) (2024)
- [Constrained Best Arm Identification in Grouped Bandits](https://mlsanity.com/paper/2412.08031/) (2024)
- [Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2301.13393/) (2023)
- [Variance-Optimal Arm Selection: Misallocation Minimization and Best Arm Identification](https://mlsanity.com/paper/2505.11985/) (2025)
- [Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget](https://mlsanity.com/paper/2506.02386/) (2025)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Constrained Best Arm Identification with Tests for Feasibility](https://mlsanity.com/paper/2511.09808/) (2025)
- [Fixed-Budget Constrained Best Arm Identification in Grouped Bandits](https://mlsanity.com/paper/2603.04007/) (2026)
- [Risk-Averse Best Arm Set Identification with Fixed Budget and Fixed Confidence](https://mlsanity.com/paper/2506.22253/) (2025)
- [Learning with a Budget: Identifying the Best Arm with Resource Constraints](https://mlsanity.com/paper/2602.24146/) (2026)
- [SAVER: Stochastic Adaptive Variance-Driven Exploration and Reconstruction for Low-Dose Computed Tomography](https://mlsanity.com/paper/2607.03761/) (2026)

## Abstract (arXiv)

We design and analyze VA-LUCB, a parameter-free algorithm, for identifying the best arm under the fixed-confidence setup and under a stringent constraint that the variance of the chosen arm is strictly smaller than a given threshold. An upper bound on VA-LUCB's sample complexity is shown to be characterized by a fundamental variance-aware hardness quantity HVA. By proving a lower bound, we show that sample complexity of VA-LUCB is optimal up to a factor logarithmic in HVA. Extensive experiments corroborate the dependence of the sample complexity on the various terms in HVA. By comparing VA-LUCB's empirical performance to a close competitor RiskAverse-UCB-BAI by David et al. (2018), our experiments suggest that VA-LUCB has the lowest sample complexity for this class of risk-constrained best arm identification problems, especially for the riskiest instances.