# Cost Aware Best Arm Identification

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 46 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## 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)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [The Multi-fidelity Multi-armed Bandit](https://mlsanity.com/paper/1610.09726/) (2016)
- [Bridging the gap between regret minimization and best arm identification, with application to A/B tests](https://mlsanity.com/paper/1810.04088/) (2018)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Gradient Ascent for Active Exploration in Bandit Problems](https://mlsanity.com/paper/1905.08165/) (2019)
- [Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk](https://mlsanity.com/paper/2204.00706/) (2022)
- [Dealing with Unknown Variances in Best-Arm Identification](https://mlsanity.com/paper/2210.00974/) (2022)
- [Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms](https://mlsanity.com/paper/2309.00591/) (2023)
- [The Role of Contextual Information in Best Arm Identification](https://mlsanity.com/paper/2106.14077/) (2021)
- [Multi-armed Bandits with Cost Subsidy](https://mlsanity.com/paper/2011.01488/) (2020)
- [A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits](https://mlsanity.com/paper/2105.12978/) (2021)
- [Multi-Fidelity Multi-Armed Bandits Revisited](https://mlsanity.com/paper/2306.07761/) (2023)

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

- [Optimal Multi-Fidelity Best-Arm Identification](https://mlsanity.com/paper/2406.03033/) (2024)
- [Best Arm Identification with Minimal Regret](https://mlsanity.com/paper/2409.18909/) (2024)
- [PromptWise: Online Learning for Cost-Aware Prompt Assignment in Generative Models](https://mlsanity.com/paper/2505.18901/) (2025)
- [Balancing Performance and Costs in Best Arm Identification](https://mlsanity.com/paper/2505.20583/) (2025)
- [Non-Asymptotic Analysis of (Sticky) Track-and-Stop](https://mlsanity.com/paper/2505.22475/) (2025)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Deceptive Exploration in Multi-armed Bandits](https://mlsanity.com/paper/2510.08794/) (2025)
- [Two-Fidelity Best-Action Identification for Stochastic Minimax Tree](https://mlsanity.com/paper/2606.01708/) (2026)
- [Cost-Aware Optimal Pairwise Pure Exploration](https://mlsanity.com/paper/2503.07877/) (2025)
- [Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy](https://mlsanity.com/paper/2605.07171/) (2026)
- [Self-Certification of Representation Adequacy: Sequential Certification at Minimum Task Loss](https://mlsanity.com/paper/2608.02267/) (2026)
- [Cost-Aware Best-LLM Identification using Dueling Feedback](https://mlsanity.com/paper/2609.30360/) (2026)
- [Test-Time Scaling via Budgeted Multi-Attribute Verification](https://mlsanity.com/paper/2609.34322/) (2026)

## Abstract (arXiv)

In this paper, we study a best arm identification problem with dual objects. In addition to the classic reward, each arm is associated with a cost distribution and the goal is to identify the largest reward arm using the minimum expected cost. We call it Cost Aware Best Arm Identification (CABAI), which captures the separation of testing and implementation phases in product development pipelines and models the objective shift between phases, i.e., cost for testing and reward for implementation. We first derive a theoretical lower bound for CABAI and propose an algorithm called mathsfCTAS to match it asymptotically. To reduce the computation of mathsfCTAS, we further propose a simple algorithm called Chernoff Overlap (CO), based on a square-root rule, which we prove is optimal in simplified two-armed models and generalizes well in numerical experiments. Our results show that (i) ignoring the heterogeneous action cost results in sub-optimality in practice, and (ii) simple algorithms can deliver near-optimal performance over a wide range of problems.