mlsanityData to 7 Oct 2026

Almost Optimal Variance-Constrained Best Arm Identification

arXiv 2201.10142 ↗First posted 25 Jan 2022cs.LG cs.AI cs.ITcited by 16

Not on the map. Why?

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.

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

Builds on

21 of 54 references.

References · 21

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  3. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 220
  4. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 148
  5. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  6. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  7. 2016Conservative Banditscited by 58
  8. 2020Learning Bounds for Risk-sensitive Learningcited by 33
  9. 2017The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regimecited by 31
  10. 2020Thompson Sampling Algorithms for Mean-Variance Banditscited by 27
  11. 2020Optimal Thompson Sampling strategies for support-aware CVaR banditscited by 26
  12. 2016Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measurecited by 20
9 more
  1. 2018Multi-objective Contextual Bandit Problem with Similarity Informationcited by 19
  2. 2019Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewardscited by 19
  3. 2014Generalized Risk-Aversion in Stochastic Multi-Armed Banditscited by 11
  4. 2020Risk-Constrained Thompson Sampling for CVaR Banditscited by 10
  5. 2021Variance-Dependent Best Arm Identificationcited by 9
  6. 2021A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Banditscited by 9
  7. 2020Constrained regret minimization for multi-criterion multi-armed banditscited by 6
  8. 2020Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed Banditscited by 4
  9. 2018An Asymptotically Optimal Strategy for Constrained Multi-armed Bandit Problemscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 1; 2024: 4; 2025: 5; 2026: 3.

16 papers.

Sort:

  1. 2024Cost Aware Best Arm Identificationcited by 12
  2. 2022Variance-Aware Sparse Linear Banditscited by 11
  3. 2022Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budgetcited by 9
  4. 2022A Survey of Risk-Aware Multi-Armed Banditscited by 8
  5. 2024Best Arm Identification with Resource Constraintscited by 3
  6. 2024Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Banditscited by 2
  7. 2024Constrained Best Arm Identification in Grouped Banditscited by 2
  8. 2023Probably Anytime-Safe Stochastic Combinatorial Semi-Banditscited by 1
  9. 2025Variance-Optimal Arm Selection: Misallocation Minimization and Best Arm Identificationcited by 1
  10. 2025Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budgetcited by 1
  11. 2025Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validationcited by 1
  12. 2025Constrained Best Arm Identification with Tests for Feasibilitycited by 1
4 more
  1. 2026Fixed-Budget Constrained Best Arm Identification in Grouped Banditscited by 1
  2. 2025Risk-Averse Best Arm Set Identification with Fixed Budget and Fixed Confidencecited by 0
  3. 2026Learning with a Budget: Identifying the Best Arm with Resource Constraintscited by 0
  4. 2026SAVER: Stochastic Adaptive Variance-Driven Exploration and Reconstruction for Low-Dose Computed Tomographycited by 0