Balancing Performance and Costs in Best Arm Identification

Michael O. Harding, Kirthevasan Kandasamy · 2025

Read Balancing Performance and Costs in Best Arm Identification by Michael O. Harding, Kirthevasan Kandasamy (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-20583.txt.

Introduction

Michael Harding and Kirthevasan Kandasamy reframe the search for the best option as a balance of gain and testing cost in two thousand twenty-five. In the classic bandit problem, a learner samples arms to find the best one. Old setups fix either the budget or the confidence, leaving practitioners to guess the knobs.

Their frame charges a cost for each sample and a penalty for ending on a weak arm, then asks the learner to cut the sum. Two penalty styles, miss chance and regret size, get matching lower bounds on the best possible risk. Their algorithm, DBCARE, meets those bounds nearly everywhere. Simulations show classic methods wasting money or settling poorly under the new yardstick.

Catalog record

CREATORMichael O. Harding, Kirthevasan Kandasamy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-20583

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Balancing Performance and Costs in Best Arm Identification Michael O. Harding, Kirthevasan Kandasamy Abstract We consider the problem of identifying the best arm in a multi-armed bandit model. Despite a wealth of literature in the traditional fixed budget and fixed confidence regimes of the best arm identification problem, it still remains a mystery to most practitioners as to how to choose an approach and corresponding budget or confidence parameter. We propose a new formalism to avoid this dilemma altogether by minimizing a risk functional which explicitly balances the performance of the recommended arm and the cost incurred by learning this arm. In this framework, a cost is incurred for each observation during the sampling phase, and upon recommending an arm, a performance penalty is incurred for identifying a suboptimal arm. The learner’s goal is to minimize the sum of the penalty and cost. This new regime mirrors the priorities of many practitioners, e.g. maximizing profit in an A/B testing framework, better than classical fixed budget or confidence settings. We derive theoretical lower bounds for the risk of each of two choices for the performance penalty, the probability of misidentification and the simple regret, and propose an algorithm called DBCARE to match these lower bounds up to polylog factors on nearly all problem instances. We then demonstrate the performance of DBCARE on a number of simulated models, comparing to fixed budget and confidence algorithms to show the shortfalls of existing BAI paradigms on this problem. 1 Introduction Best Arm Identification (BAI) in multi-armed bandits is a fundamental problem in decision-making under uncertainty. The objective is to identify the arm with the highest expected reward by adaptively drawing samples from distributions associated with each arm. BAI arises in many real-world applications. In advertising, arms represent different ads, and the aim is to find the ad which maximizes revenue generated [ 18 ] . In statistical model selection, arms represent different hyperparameter configurations, and the aim is to find the best-performing one with minimal computational resources [ 20 ] . Traditionally, BAI has been studied under two paradigms: the fixed budget setting [ 2 , 8 ] , which seeks to maximize performance—i.e. the ability of a policy to recover the optimal arm—within a given sampling budget, and the fixed performance (e.g., fixed confidence [ 33 , 15 ] ) setting, which aims to minimize the number of samples needed to meet a target performance level. While algorithms for these settings have been successfully deployed in many real-world settings [ 32 , 35 , 51 , 18 ] , these settings are not a natural fit for all use cases. For instance, while determining the best arm is desirable, a slightly suboptimal choice may be acceptable if the cost of distinguishing between top candidates is prohibitively high. On the other hand, it is often unnecessary to continue sampling until reaching some pre-specified horizon when there is already enough evidence to determine the optimal arm. To this end, we propose a novel paradigm for BAI, in which a policy should explicitly balance performance and sampling cost on the fly, without being constrained by a fixed performance level or a pre-specified sampling budget. This framework allows policies to adaptively terminate according to the difficulty of the problem. The following is an example where such a framework would be natural. Example (Advertising) . Consider a firm choosing among K versions of an ad. To inform its choice, the firm may show versions to participants in a focus group (arm pull), incurring a cost c per showing. The firm wishes to choose an algorithm to maximize the expected profit, i.e. the expected revenue of the selected ad ( \widehat{I} ) minus the expected cost of the sampling procedure: \E[\text{revenue}_{\widehat{I}}]-c\E[\#\text{ arm pulls}] . Letting I^{\star} be the ad with the highest expected revenue, then maximizing expected profit can be equivalently stated as minimizing \E[\text{revenue}_{I^{\star}}-\text{revenue}_{\widehat{I}}]+c\E[\#\text{ arm pulls}] . Traditional fixed budget or confidence algorithms would be a poor fit for this problem, as it is unclear how one should choose the budget or confidence level to optimize the objective. 1.1 Model We will now formally introduce our setting. A learner has access to a MAB model \nu=\{\nu_{a}\}_{a\in[K]} , which consists of K arms, each associated with a probability distribution \nu_{a} . Let \mu_{a}=\mathbb{E}_{\nu_{a}}[X] denote the expected reward of arm a\,. Following common conventions in the BAI literature, we assume without loss of generality that the arms are ordered so that \mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{K} (the learner is unaware of this ordering). We will assume that for each arm a\in[K] , the distribution \nu_{a} is \sigma -sub-Gaussian and that \mu_{a}\in[0,B] . The learner is aware of \sigma and B . A learner interacts with the bandit model over a sequence of rounds t=1,2,\dots . On round t , the learner selects an arm A_{t}\in[K] according to a policy \pi and observes an independent sample X_{t} drawn from \nu_{A_{t}} . The choice of A_{t} may depend on the history \{(A_{s},X_{s})\}_{s=1}^{t-1} of previous actions and observations. Upon termination, the policy recommends an arm \widehat{I}\in[K] as the estimated best arm. Prior work. Traditionally, BAI has been studied under two main regimes: (1) Fixed budget: The learner is allowed at most T\in\mathbb{N} samples and aims to minimize either the probability of misidentification [ 2 ] \Prob(\mu_{1}\neq\mu_{\widehat{I}}) or the simple regret [ 8 ] \E[\mu_{1}-\mu_{\widehat{I}}] , i.e. the expected gap between the optimal and selected arms. (2) Fixed performance: The learner must satisfy a specified performance goal while minimizing the number of samples. The most common instantiation is fixed-confidence BAI [ 6 , 16 ] , where the probability of misidentification \Prob(\mu_{1}\neq\mu_{\widehat{I}}) is at most a given goal \delta . This work. Both the fixed-budget and fixed-performance formulations neglect practical situations where one may not have a pre-specified budget or performance goal, but would like to trade-off between performance and sampling cost based on problem difficulty. Motivated by such considerations, we propose a new setting, where the goal is to minimize a risk functional that captures both a performance penalty and the cumulative sampling cost. Choosing either the probability of misidentification or the simple regret as the penalty, we study the following two risk measures: \displaystyle\begin{split}\mathcal{R}_{\rm MI}(\pi,\nu)&:=\E_{\nu,\pi}\left[\mathbbm{1}\left(\mu_{1}\neq\mu_{\widehat{I}}\right)+c\tau\right]=\Prob_{\nu,\pi}\left(\mu_{1}\neq\mu_{\widehat{I}}\right)+c\,\mathbb{E}_{\nu,\pi}[\tau]\,,\\ \mathcal{R}_{\rm SR}(\pi,\nu)&:=\E_{\nu,\pi}\left[\left(\mu_{1}-\mu_{\widehat{I}}\right)+c\tau\right]=\mathbb{E}_{\nu,\pi}\left[\mu_{1}-\mu_{\widehat{I}}\right]+c\,\mathbb{E}_{\nu,\pi}[\tau]\,.\end{split} (1) Here, c>0 is the (known) cost required to collect a sample, relative to the performance penalty, and \tau is the stopping time (total number of samples) of the policy \pi . Moreover, \Prob_{\nu,\pi} and \E_{\nu,\pi} denote the probability and expectation with respect to all randomness arising from the interaction between the policy \pi and the bandit model \nu . 1.2 Summary of our contributions and results Novel problem formalism. To the best of our knowledge, we are the first to study this risk-based formalism for BAI which trades off between performance and sampling costs. We design policies for both risk measures in ( 1 ), upper bound the risk, and provide nearly matching lower bounds. Lower bounds. To summarize our lower bounds, let \Delta_{k}=\mu_{1}-\mu_{k} denote the sub-optimality gap of arm k , and let H:=\sum_{k=2}^{K}\Delta_{k}^{-2} be a problem complexity parameter [ 33 , 15 , 26 , 21 , 28 , 30 ] . We show that the problem difficulty exhibits a phase transition depending on the magnitude

Read the complete text