# Balancing Performance and Costs in Best Arm Identification

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

## Key facts

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

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

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [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)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [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)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Humor in AI: Massive Scale Crowd-Sourced Preferences and Benchmarks for Cartoon Captioning](https://mlsanity.com/paper/2406.10522/) (2024)
- [Bridging the gap between regret minimization and best arm identification, with application to A/B tests](https://mlsanity.com/paper/1810.04088/) (2018)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Bounded regret in stochastic multi-armed bandits](https://mlsanity.com/paper/1302.1611/) (2013)
- [Comparison Lift: Bandit-based Experimentation System for Online Advertising](https://mlsanity.com/paper/2009.07899/) (2020)
- [Optimal Multi-Fidelity Best-Arm Identification](https://mlsanity.com/paper/2406.03033/) (2024)
- [On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits](https://mlsanity.com/paper/2210.00895/) (2022)
- [Multi-armed Bandits with Cost Subsidy](https://mlsanity.com/paper/2011.01488/) (2020)
- [Multi-Fidelity Multi-Armed Bandits Revisited](https://mlsanity.com/paper/2306.07761/) (2023)
- [Best Arm Identification with Minimal Regret](https://mlsanity.com/paper/2409.18909/) (2024)

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

- [Deceptive Exploration in Multi-armed Bandits](https://mlsanity.com/paper/2510.08794/) (2025)

## Abstract (arXiv)

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.