Variance-Optimal Arm Selection: Misallocation Minimization and Best Arm Identification
Sabrina Khurshid, Gourab Ghatak · 2025
Read Variance-Optimal Arm Selection: Misallocation Minimization and Best Arm Identification by Sabrina Khurshid, Gourab Ghatak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11985.txt.
Introduction
Sabrina Khurshid, Gourab Ghatak, and Mohammad Shahid Abdulla tackle a twist on the multi-armed bandit problem in a two thousand twenty-five paper. Instead of the arm with the highest average reward, the goal is the arm with the highest variance.
Two settings are studied: minimizing misallocation of pulls to suboptimal arms, and identifying the best arm within a fixed budget. Their UCB-VV algorithm achieves logarithmic misallocation and is order optimal, while SHVV handles the fixed-budget case at a matching error rate. The framework extends to sub-Gaussian rewards through a new concentration inequality, also yielding one for the Sharpe ratio. Simulations and a stock-options case study test the methods.
Catalog record
| CREATOR | Sabrina Khurshid, Gourab Ghatak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-11985
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Variance-Optimal Arm Selection: Misallocation Minimization and Best Arm Identification Thanks: Sabrina Khurshid and G. Ghatak are with the Department of Electrical Engineering, IIT Delhi, New Delhi, India, 110016; Email: [email protected], [email protected]. M.S.Abdulla is with the Information Systems, IIM Kozhikiode, Kerela, India, 110020; Email: [email protected] Sabrina Khurshid, Gourab Ghatak Abstract This paper focuses on selecting the arm with the highest variance from a set of K 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 MM ( MM ) and show that its upper bound on misallocation for bounded rewards evolves as 𝒪 ( log n ) \mathcal{O}\left(\log{n}\right) where n n is the horizon. By deriving the lower bound on the misallocation, we show that UCB-VV is order optimal. For the fixed budget BAI ( BAI ) setting we propose the SHVV algorithm. We show that the upper bound of the error probability of SHVV evolves as exp ( − n log ( K ) H ) \exp\left(-\frac{n}{\log(K)H}\right) , where H 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 ϵ \epsilon -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 100 stocks generated using GBM ( GBM ). TS Thompson sampling MAB multi-armed bandit SRTS Sharpe ratio Thompson sampling MM misallocation minimization BAI best arm identification GBM geometric Brownian motion MDP Markov decision process RL reinforcement learning MPT modern portfolio theory OTC over-the-counter UCB upper confidence bound TS Thompson sampling i.i.d independent and identically distributed CVaR conditional value-at-risk VaR value-at-risk SR Sharpe ratio I Introduction and Motivation Historically, variance has served as the first and foundational risk measure in portfolio optimization. The modern portfolio theory is based upon the classical Markowitz model, which also employs variance as a measure of risk [ 1 , 2 , 3 ] . In economic models, the decision-makers account for uncertainty and variance to maintain robustness [ 4 ] . In decision-making and optimization, identifying and mitigating sources of high variance is crucial to ensuring stability and robustness in outcomes [ 5 , 6 , 7 ] . Recent advances in risk-sensitive decision making involve more sophisticated risk measures such as VaR ( VaR ) and CVaR ( CVaR ) [ 8 , 9 , 10 , 11 , 12 ] . Unlike VaR and CVaR , which rely on tail-specific assumptions and involve complex computations related to probability thresholds and conditional expectations, variance is distribution-agnostic and computationally lightweight. From the perspective of selecting the arm with the highest variance, we study two settings of the MAB ( MAB ) framework - MM and BAI . Specifically, the MM setting attempts to minimize the number of pulls of sub-optimal arms in terms of the variance. On the contrary, the BAI setting attempts to determine the arm with the highest variance with a high probability. The fixed-budget BAI focuses on identifying the best arm with minimum error for a fixed number of samples [ 13 , 14 , 15 ] . This is particularly relevant in scenarios like A/B testing, clinical trials, or recommendation systems, where the ultimate goal is to find the single best option. Variance has been central to research on asset pricing and portfolio management. High-variance assets introduce instability and expose portfolios to erratic swings, requiring their identification and possible exclusion. For portfolio managers, maximizing the frequency of selecting the highest variance option unlocks opportunities to optimize returns while leveraging the asymmetrical payoff structure of call options from favorable price movements. For example, for a call option buyer, a higher variance is particularly advantageous as it increases the potential for substantial gains while capping the maximum loss to the premium paid for the option. In this paper, we develop bandit algorithms for identification of arm with the highest variance in MM and BAI settings. It must be noted that the results of our framework can be extended to the setting to pick the arm with the minimum variance as well. I-A Related work I-A 1 Literature in bandit setting In the regret setting, [ 16 ] investigates UCB-V , a variant of the UCB ( UCB ) algorithm for stochastic MAB that incorporates empirical variance estimates of arm payoffs to pick the arm with the highest mean. The algorithm performs better than traditional methods, especially when suboptimal arms have low variance. However, it depends on an unavoidable upper-limit u , which can reduce efficiency when u is large but actual variances are small. The authors in [ 17 ] present E-UCBV , a variance-aware UCB algorithm that achieves tighter regret bounds than UCB1 . By incorporating efficient arm elimination, E-UCBV demonstrates superior performance in scenarios with small gaps and low-variance suboptimal arms. However, the algorithm has notable limitations, including high complexity in regret bounds and constraints on n . The authors in [ 18 , 19 ] address risk-aware decision-making and design algorithms for mean-variance MAB . The BAI problem has been extensively investigated across a broad range of settings, e.g, for linear bandits [ 20 ] , cost-aware BAI [ 21 ] , as well as risk-averse bandits [ 22 ] . In risk-averse BAI problem, [ 23 ] considers VaR -optimization. Also, [ 22 ] , [ 24 ] , optimizes a mean-CVaR framework within a fixed budget framework. They propose distribution oblivious algorithms, i.e, they do not require prior knowledge of the arms’ underlying distributions and are asymptotically near-optimal. However, these algorithms come with weaker performance guarantees compared to those that leverage prior knowledge of the arm distributions, highlighting an inherent trade-off between robustness and efficiency. Variance optimization, in particular, often necessitates stronger assumptions about the reward distributions (e.g., sub-Gaussianity) to ensure accurate and reliable estimation. Without such assumptions, variance estimates can become highly sensitive to noise and hence unreliable. I-A 2 Literature in finance In the context of finance, variance is used to model risk premium, providing insights into market sentiment and investor behavior. Specifically, the variance risk premium (a compensation that investors demand for bearing the risk associated with the volatility in the returns of an asset) plays a critical role in both theoretical and practical applications. This concept has been leveraged to develop trading strategies, such as selling volatility when the