Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation

# Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation
Source: [https://arxiv.org/html/2608.04333](https://arxiv.org/html/2608.04333)
22footnotetext:Corresponding AuthorBo Xue Zhi Hong Jiayi Li Yuanyu Wan Ji Cheng Shuang Qiu†City University of Hong Kong\. Email:boxue4\-c@my\.cityu\.edu\.hkSouth China University of Technology\. Email:zhih1008@gmail\.comZhejiang University\. Email:LJY@bupt\.edu\.cnZhejiang University\. Email:wanyy@zju\.edu\.hkCity University of Hong Kong\. Email:J\.Cheng@my\.cityu\.edu\.hkCity University of Hong Kong\. Email:shuanqiu@cityu\.edu\.hk

###### Abstract

Large language model \(LLM\) configuration evaluation is challenging due to limited evaluation budgets, varying costs, and multiple competing objectives\. In this paper, we formulate LLM configuration evaluation as a cost\-aware multi\-objective bandit problem, where each configuration evaluation incurs a configuration\-dependent cost and yields a noisy vector\-valued outcome\. Under this framework, we study two fundamental problems: online configuration selection and Pareto configuration identification\. For online configuration selection, we propose a hypervolume\-based UCB algorithm that optimizes an optimistic hypervolume\-per\-cost index\. We establish a budgeted regret bound of orderO​\(∑i≠i⋆log⁡BΔi\)O\\bigl\(\\sum\_\{i\\neq i^\{\\star\}\}\\frac\{\\log B\}\{\\Delta\_\{i\}\}\\bigr\), whereBBis the evaluation budget,i⋆i^\{\\star\}is the optimal configuration in terms of hypervolume efficiency, andΔi\\Delta\_\{i\}is the corresponding efficiency gap of configurationii\. This bound retains the logarithmic budget dependence of classical single\-objective budgeted bandits\. For fixed\-budget Pareto identification, we develop a cost\-aware empirical gap elimination algorithm and prove that its error probability is of orderO​\(exp⁡\(−BHμ,c\)\)O\\bigl\(\\exp\(\-\\frac\{B\}\{H\_\{\\mu,c\}\}\)\\bigr\), whereHμ,cH\_\{\\mu,c\}is a cost\-aware Pareto identification complexity depending on configuration costs and Pareto classification gaps\. This error probability decays exponentially with the evaluation budget and recovers the standard Pareto set identification guarantee when all configuration costs are identical\. Experiments on LLM configuration evaluation tasks demonstrate that the proposed framework enables efficient online decision\-making and accurate cost\-aware Pareto identification under limited budgets\.

## 1Introduction

In real\-world large language model \(LLM\) applications, users must select suitable configurations, such as base models, prompt templates, and retrieval settings, while operating under limited evaluation budgets\. Evaluating a configuration may require model inference, long\-form generation, LLM\-as\-a\-judge scoring, or human assessment, leading to substantially different monetary costs across configurations\(Zhenget al\.,[2023](https://arxiv.org/html/2608.04333#bib.bib257); Changet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib255); Liet al\.,[2025](https://arxiv.org/html/2608.04333#bib.bib256)\)\. For example, larger models and chain\-of\-thought prompting may improve task performance but often consume more tokens\(Weiet al\.,[2022](https://arxiv.org/html/2608.04333#bib.bib251); Shiet al\.,[2024b](https://arxiv.org/html/2608.04333#bib.bib252); Zhouet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib280)\)\. Moreover, LLM evaluation is inherently multi\-objective: beyond task accuracy, practitioners often care about latency and efficiency\(Lianget al\.,[2023](https://arxiv.org/html/2608.04333#bib.bib279); Changet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib255)\)\. Therefore, reliable LLM configuration evaluation requires adaptive allocation of a limited budget across candidate configurations while accounting for both varying evaluation costs and multiple quality objectives\.

A straightforward approach to identifying the optimal LLM configuration is to exhaustively evaluate every candidate on the entire validation set and select the one with the highest empirical performance\. This protocol aligns with standard benchmark\-based evaluation practices, where models or systems are assessed across a predefined collection of tasks, examples, and metrics\(Lianget al\.,[2023](https://arxiv.org/html/2608.04333#bib.bib279); Changet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib255)\)\. Despite its simplicity and statistical reliability, exhaustive evaluation is increasingly impractical for modern LLM applications, as assessing a large number of configurations requires a substantial number of inference queries, leading to considerable monetary costs, token consumption, and computational overhead\(Zhenget al\.,[2023](https://arxiv.org/html/2608.04333#bib.bib257); Liet al\.,[2025](https://arxiv.org/html/2608.04333#bib.bib256); Fenget al\.,[2025](https://arxiv.org/html/2608.04333#bib.bib258)\)\.

Recent studies have therefore explored adaptive evaluation strategies to improve evaluation efficiency\.Zhouet al\.\([2025](https://arxiv.org/html/2608.04333#bib.bib245)\)formulate language model evaluation as a bandit\-based adaptive sampling problem\. Similarly,Shiet al\.\([2024a](https://arxiv.org/html/2608.04333#bib.bib249)\)leverage best\-arm identification techniques for prompt selection, with the goal of identifying high\-performing prompts under a limited evaluation budget\. These studies show that bandit\-based adaptive sampling can significantly reduce evaluation costs by allocating more evaluation resources to promising candidates, instead of uniformly evaluating all candidates across all validation instances\.

Despite these advances, existing adaptive evaluation methods still leave three limitations\.\(a\)They often overlook configuration\-dependent evaluation costs, even though differences in model scale, reasoning strategy, and retrieval pipeline can lead to substantial variation in token consumption and computational overhead\(Chenet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib299); Onget al\.,[2025](https://arxiv.org/html/2608.04333#bib.bib300)\)\.\(b\)Most existing formulations are restricted to single\-objective optimization, focusing on a scalar performance metric or ranking criterion\. However, practical LLM evaluation often requires balancing multiple objectives, including task effectiveness, robustness and latency\(Lianget al\.,[2023](https://arxiv.org/html/2608.04333#bib.bib279); Changet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib255)\)\.\(c\)Bandit\-based LLM evaluation methods typically follow a pure\-exploration formulation, assessing only the final configuration selected\(Poloet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib301); Zhouet al\.,[2025](https://arxiv.org/html/2608.04333#bib.bib245)\)\. They therefore overlook the quality of intermediate decisions, which directly affects cumulative utility in continuous evaluation systems\(Lattimore and Szepesvári,[2020](https://arxiv.org/html/2608.04333#bib.bib55); Onget al\.,[2025](https://arxiv.org/html/2608.04333#bib.bib300); Ashizawaet al\.,[2025](https://arxiv.org/html/2608.04333#bib.bib247)\)\.

Motivated by these limitations, we formulate LLM configuration evaluation as a cost\-aware multi\-objective bandit problem with a finite evaluation budget\. Each configuration is modeled as an arm, and each evaluation consumes a configuration\-dependent cost while producing stochastic vector\-valued feedback\. This formulation captures two central characteristics of practical LLM evaluation: the need to allocate a limited budget across configurations with varying costs and the need to optimize multiple performance criteria\.

To the best of our knowledge, this is the first study of cost\-aware multi\-objective bandits\. We consider two complementary learning objectives: online configuration selection through regret minimization and Pareto\-optimal configuration identification under a fixed budget\. Our main contributions are summarized as follows:

- •We propose a hypervolume\-based UCB algorithm for cost\-aware online configuration selection, which optimizes a hypervolume\-per\-cost index to balance multi\-objective performance and evaluation cost\. Its regret is bounded byO​\(∑i≠i⋆log⁡BΔi\)O\\bigl\(\\sum\_\{i\\neq i^\{\\star\}\}\\frac\{\\log B\}\{\\Delta\_\{i\}\}\\bigr\), whereBBis the evaluation budget,i⋆i^\{\\star\}is the optimal configuration in terms of hypervolume efficiency, andΔi\\Delta\_\{i\}is the corresponding efficiency gap of configurationii\. This bound matches the single\-objective result in both budget and gap dependence\(Dinget al\.,[2013](https://arxiv.org/html/2608.04333#bib.bib278)\)\.
- •We develop a cost\-aware Pareto configuration identification algorithm, which allocates samples according to evaluation costs and progressively eliminates configurations using empirical Pareto gaps\. Its error probability is bounded byO​\(exp⁡\(−BHμ,c\)\)O\\bigl\(\\exp\(\-\\frac\{B\}\{H\_\{\\mu,c\}\}\)\\bigr\), whereHμ,cH\_\{\\mu,c\}is a cost\-aware Pareto identification complexity depending on configuration costs and Pareto classification gaps\. This error probability decays exponentially with the evaluation budget and recovers the standard error rate for fixed\-budget Pareto set identification when all configurations have identical evaluation costs\(Koneet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib292)\)\.
- •We conduct experiments on LLM configuration evaluation tasks involving different models, prompts and decoding parameters\. Comparisons with cost\-insensitive bandit algorithms and single\-objective selection strategies, our methods demonstrate the benefits of jointly accounting for evaluation cost and multiple performance objectives\.

## 2Related Work

This section reviews the literature on budgeted bandits, multi\-objective bandits, and recent bandit\-based methods for LLMs\.

#### Budgeted Bandits\.

Classical bandit research has primarily considered two learning objectives: regret minimization, which evaluates the quality of decisions made throughout the learning process\(Lai and Robbins,[1985](https://arxiv.org/html/2608.04333#bib.bib31); Auer,[2002](https://arxiv.org/html/2608.04333#bib.bib10)\), and best\-arm identification, which focuses on the quality of the final recommendation after exploration\(Audibert and Bubeck,[2010](https://arxiv.org/html/2608.04333#bib.bib32); Gabillonet al\.,[2012](https://arxiv.org/html/2608.04333#bib.bib33); Jamiesonet al\.,[2014](https://arxiv.org/html/2608.04333#bib.bib261)\)\.Dinget al\.\([2013](https://arxiv.org/html/2608.04333#bib.bib278)\)formalized the budgeted multi\-armed bandit with stochastic costs, which captures the reward\-cost trade\-off through an expected reward\-per\-cost criterion and provides logarithmic regret guarantees\. Subsequent works have extended this line in several directions\.Xiaet al\.\([2015](https://arxiv.org/html/2608.04333#bib.bib281)\)developed Thompson sampling algorithms for budgeted bandits with random costs and showed that Bayesian sampling achieves logarithmic regret in the budget\.Xiaet al\.\([2016](https://arxiv.org/html/2608.04333#bib.bib282)\)investigated the multiple\-play setting, in which several arms are selected in each round under a shared budget\.Li and Xia \([2017](https://arxiv.org/html/2608.04333#bib.bib283)\)considered budgeted bandits with infinitely many arms, highlighting the additional exploration cost incurred when searching over a large action space\. A broader related framework is bandits with knapsacks, which generalizes budgeted bandits to multiple resource constraints\(Badanidiyuruet al\.,[2018](https://arxiv.org/html/2608.04333#bib.bib285),[2014](https://arxiv.org/html/2608.04333#bib.bib286); Immorlicaet al\.,[2022](https://arxiv.org/html/2608.04333#bib.bib288); Sankararaman and Slivkins,[2018](https://arxiv.org/html/2608.04333#bib.bib287); Liuet al\.,[2022](https://arxiv.org/html/2608.04333#bib.bib289)\)\. These studies provide a principled foundation for decision\-making under resource constraints, but they mainly focus on scalar rewards\.

#### Multi\-Objective Bandits\.

Multi\-objective bandits address sequential decision\-making with vector\-valued rewards\. Existing studies have considered several performance criteria, including scalarization\-based regret\(Drugan and Nowe,[2013](https://arxiv.org/html/2608.04333#bib.bib68)\), Pareto regret\(Luet al\.,[2019](https://arxiv.org/html/2608.04333#bib.bib47)\), hypervolume regret\(Zhang,[2024](https://arxiv.org/html/2608.04333#bib.bib290)\), and Pareto set identification \(PSI\)\(Aueret al\.,[2016](https://arxiv.org/html/2608.04333#bib.bib69)\)\. A relevant line optimizes the hypervolume indicator\.Zhang and Golovin \([2020](https://arxiv.org/html/2608.04333#bib.bib291)\)introduced random hypervolume scalarizations for multi\-objective black\-box optimization, andZhang \([2024](https://arxiv.org/html/2608.04333#bib.bib290)\)later established optimal sublinear hypervolume regret guarantees for this approach\. Another closely related line investigates PSI, whose goal is to identify all non\-dominated arms\.Aueret al\.\([2016](https://arxiv.org/html/2608.04333#bib.bib69)\)studied PSI under stochastic bandit feedback,Koneet al\.\([2023](https://arxiv.org/html/2608.04333#bib.bib147)\)developed adaptive algorithms for relaxed fixed\-confidence PSI, andKoneet al\.\([2024](https://arxiv.org/html/2608.04333#bib.bib292)\)proposed successive\-rejects\-based algorithms for the fixed\-budget setting\. More recent work has also examined the sequential learning of Pareto fronts in multi\-objective bandits\(Creponet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib223)\)\. Furthermore, multi\-objective reinforcement learning with bandit feedback\(Qiuet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib2)\)extends the bandit problem to Markov decision processes\. Although these studies provide important foundations for multi\-objective exploration, they typically constrain the total number of sampling rounds without explicitly accounting for arm\-dependent evaluation costs\.

#### Bandits for LLMs\.

Bandit learning has recently been explored in several LLM\-related problems, including prompt optimization, model selection, and budget\-efficient evaluation\. ProTeGi incorporates a bandit\-based selection mechanism into beam search to identify promising prompt candidates\(Pryzantet al\.,[2023](https://arxiv.org/html/2608.04333#bib.bib298)\)\.Linet al\.\([2024](https://arxiv.org/html/2608.04333#bib.bib293)\)employ neural bandits with transformer\-based representations for instruction optimization, whereasWuet al\.\([2024](https://arxiv.org/html/2608.04333#bib.bib294)\)apply neural bandits to order\-aware in\-context exemplar selection\. More recently,Honget al\.\([2026](https://arxiv.org/html/2608.04333#bib.bib295)\)propose MASPOB for prompt optimization in LLM\-based multi\-agent systems, where UCB\-style exploration is combined with graph neural networks to capture topology\-induced coupling among agents\. Another related line formulates model, prompt, or evaluation selection as a bandit problem\.Shiet al\.\([2024a](https://arxiv.org/html/2608.04333#bib.bib249)\)connect prompt selection with fixed\-budget best arm identification, whilePoonet al\.\([2025](https://arxiv.org/html/2608.04333#bib.bib248)\)study online LLM selection under contextual information and cost\-quality trade\-offs\. For budget\-efficient evaluation,Zhouet al\.\([2025](https://arxiv.org/html/2608.04333#bib.bib245)\)integrate multi\-armed bandits with low\-rank matrix factorization to adaptively allocate evaluations and identify high\-performing configurations using fewer observations\. These studies demonstrate the potential of bandit methods to reduce the costs of prompt search, model selection, and performance evaluation\. Nevertheless, most existing approaches either optimize a single scalar objective or focus primarily on offline best\-arm identification\.

## 3Preliminaries

We consider LLM configuration evaluation with multiple competing objectives under a total evaluation budgetB\>0B\>0\.

At each roundt=1,2,…t=1,2,\\ldots, the learner selects a configurationit∈\[K\]≔\{1,…,K\}i\_\{t\}\\in\[K\]\\coloneqq\\\{1,\\ldots,K\\\}\. The selected configuration is evaluated on a validation sample, such as a question drawn from GSM8K\(Cobbeet al\.,[2021](https://arxiv.org/html/2608.04333#bib.bib262)\)or PIQA\(Bisket al\.,[2020](https://arxiv.org/html/2608.04333#bib.bib263)\), and produces a reward vector

𝒓it,t=\(rit,t\(1\),…,rit,t\(D\)\)∈\[0,1\]D,\\bm\{r\}\_\{i\_\{t\},t\}=\\bigl\(r\_\{i\_\{t\},t\}^\{\(1\)\},\\ldots,r\_\{i\_\{t\},t\}^\{\(D\)\}\\bigr\)\\in\[0,1\]^\{D\},where each coordinate corresponds to one normalized objective, such as task accuracy, inference efficiency, or other deployment\-relevant criteria\. All objectives are formulated so that larger values are preferred\. For each configurationi∈\[K\]i\\in\[K\], its reward vectors are i\.i\.d\. with unknown mean

𝝁i=\(μi\(1\),…,μi\(D\)\)=E​\[𝒓i,t\]\.\\bm\{\\mu\}\_\{i\}=\\bigl\(\\mu\_\{i\}^\{\(1\)\},\\ldots,\\mu\_\{i\}^\{\(D\)\}\\bigr\)=\\mathrm\{E\}\[\\bm\{r\}\_\{i,t\}\]\.
In addition to producing a multi\-objective reward, each evaluation consumes part of the available budget\. This cost may represent monetary API expenditure, token consumption, or human\-annotation effort\. Although these criteria can also be incorporated into the reward vector, the evaluation cost determines the total number of evaluations\.

We distinguish between two cost models for the two learning settings\. In online cost\-aware configuration selection, the evaluation cost may be random\. Specifically, evaluating configurationiiat roundttincurs a cost

ci,t∈\[λ,1\],μic=E​\[ci,t\],0<λ≤1\.c\_\{i,t\}\\in\[\\lambda,1\],\\quad\\mu\_\{i\}^\{c\}=\\mathrm\{E\}\[c\_\{i,t\}\],\\quad 0<\\lambda\\leq 1\.
For fixed\-budget Pareto set identification, we instead consider deterministic and known evaluation costs,

ci∈\[λ,1\]\.c\_\{i\}\\in\[\\lambda,1\]\.This model is appropriate when the cost of a single evaluation can be estimated in advance, for example, a fixed inference protocol, or a standardized human\-evaluation procedure\.

### 3\.1Budgeted Online Configuration Selection

LetCt=∑s=1tcis,sC\_\{t\}=\\sum\_\{s=1\}^\{t\}c\_\{i\_\{s\},s\}denote the cumulative cost afterttevaluations\. Given an evaluation budgetB\>0B\>0, the number of evaluations completed within the budget is

T​\(B\)=max⁡\{t≥0:Ct≤B\}\.T\(B\)=\\max\\\{t\\geq 0:C\_\{t\}\\leq B\\\}\.
We quantify the multi\-objective performance of each configuration using the hypervolume indicator\. With the zero vector as the reference point, the single\-point hypervolume of configurationiiis

Hi=H​\(𝝁i\)=HV⁡\(𝝁i\)=∏j=1Dμi\(j\)\.H\_\{i\}=H\(\\bm\{\\mu\}\_\{i\}\)=\\operatorname\{HV\}\(\\bm\{\\mu\}\_\{i\}\)=\\prod\_\{j=1\}^\{D\}\\mu\_\{i\}^\{\(j\)\}\.
To account for varying evaluation costs, we define the hypervolume efficiency for anyi∈\[K\]i\\in\[K\]asνi=Hiμic\\nu\_\{i\}=\\frac\{H\_\{i\}\}\{\\mu\_\{i\}^\{c\}\}\. Leti⋆=arg⁡maxi∈\[K\]⁡νii^\{\\star\}=\\arg\\max\_\{i\\in\[K\]\}\\nu\_\{i\}denote the optimal configuration and define the corresponding efficiency gap asΔi=νi⋆−νi\\Delta\_\{i\}=\\nu\_\{i^\{\\star\}\}\-\\nu\_\{i\}\. The hypervolume\-efficiency regret under budgetBBis

RBHV=∑t=1T​\(B\)Δit\.R\_\{B\}^\{\\operatorname\{HV\}\}=\\sum\_\{t=1\}^\{T\(B\)\}\\Delta\_\{i\_\{t\}\}\.We further consider the standard hypervolume regret

RBstd=RB⋆−∑t=1T​\(B\)Hit,R\_\{B\}^\{\\operatorname\{std\}\}=R\_\{B\}^\{\\star\}\-\\sum\_\{t=1\}^\{T\(B\)\}H\_\{i\_\{t\}\},whereRB⋆R\_\{B\}^\{\\star\}denotes the maximum expected cumulative hypervolume attainable under budgetBB\.

Both regret notions measure cumulative performance under the budget constraint, whileRBHVR\_\{B\}^\{\\operatorname\{HV\}\}further emphasizes hypervolume gain per unit cost\.

### 3\.2Budgeted Pareto Configuration Identification

We also consider the fixed\-budget identification setting, where the learner aims to recover the Pareto\-optimal configuration set under a prescribed budgetB\>0B\>0\.

FollowingKoneet al\.\([2024](https://arxiv.org/html/2608.04333#bib.bib292)\), for any𝒖,𝒗∈ℝD\\bm\{u\},\\bm\{v\}\\in\\mathbb\{R\}^\{D\}, we write𝒖⪯𝒗\\bm\{u\}\\preceq\\bm\{v\}ifu\(j\)≤v\(j\)u^\{\(j\)\}\\leq v^\{\(j\)\}for anyj∈\[D\]j\\in\[D\]and𝒖≺𝒗\\bm\{u\}\\prec\\bm\{v\}ifu\(j\)<v\(j\)u^\{\(j\)\}<v^\{\(j\)\}for anyj∈\[D\]j\\in\[D\]\. Configurationjjstrictly Pareto dominates configurationiiif𝝁i≺𝝁j\\bm\{\\mu\}\_\{i\}\\prec\\bm\{\\mu\}\_\{j\}\. The true Pareto set is therefore

𝒫⋆=\{i∈\[K\]:∄​j∈\[K\]​such that​𝝁i≺𝝁j\}\.\\mathcal\{P\}^\{\\star\}=\\left\\\{i\\in\[K\]:\\nexists j\\in\[K\]\\ \\text\{such that\}\\ \\bm\{\\mu\}\_\{i\}\\prec\\bm\{\\mu\}\_\{j\}\\right\\\}\.
The learner adaptively evaluates configurations with deterministic costs\{ci\}i=1K\\\{c\_\{i\}\\\}\_\{i=1\}^\{K\}and, upon exhausting the available budget, outputs an estimate𝒫^B\\widehat\{\\mathcal\{P\}\}\_\{B\}\. Its performance is measured by the misidentification probability

Pr​\(𝒫^B≠𝒫⋆\)\.\\mathrm\{Pr\}\\left\(\\widehat\{\\mathcal\{P\}\}\_\{B\}\\neq\\mathcal\{P\}^\{\\star\}\\right\)\.
To characterize the difficulty of Pareto classification, for any pairi,j∈\[K\]i,j\\in\[K\], define

m​\(i,j\)\\displaystyle m\(i,j\)=mind∈\[D\]⁡\(μj\(d\)−μi\(d\)\),\\displaystyle=\\min\_\{d\\in\[D\]\}\\left\(\\mu\_\{j\}^\{\(d\)\}\-\\mu\_\{i\}^\{\(d\)\}\\right\),M​\(i,j\)\\displaystyle M\(i,j\)=maxd∈\[D\]⁡\(μi\(d\)−μj\(d\)\)\.\\displaystyle=\\max\_\{d\\in\[D\]\}\\left\(\\mu\_\{i\}^\{\(d\)\}\-\\mu\_\{j\}^\{\(d\)\}\\right\)\.Following the gap construction of Empirical Gap Elimination\(Koneet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib292)\), define

Δi−=maxj∈\[K\]∖\{i\}⁡m​\(i,j\)\\Delta\_\{i\}^\{\-\}=\\max\_\{j\\in\[K\]\\setminus\\\{i\\\}\}m\(i,j\)and, for a Pareto\-optimal configurationi∈𝒫⋆i\\in\\mathcal\{P\}^\{\\star\},

Δi\+\\displaystyle\\Delta\_\{i\}^\{\+\}=minj∈\[K\]∖\{i\}⁡\[M​\(i,j\)∧\(M​\(j,i\)\+\+\(Δj−\)\+\)\],\\displaystyle=\\min\_\{j\\in\[K\]\\setminus\\\{i\\\}\}\\left\[M\(i,j\)\\wedge\\left\(M\(j,i\)^\{\+\}\+\\left\(\\Delta\_\{j\}^\{\-\}\\right\)^\{\+\}\\right\)\\right\],wherex\+=max⁡\{x,0\}x^\{\+\}=\\max\\\{x,0\\\}anda∧b=min⁡\{a,b\}a\\wedge b=\\min\\\{a,b\\\}\. Thus, the classification gap is

γi=\{Δi−,i∉𝒫⋆,Δi\+,i∈𝒫⋆\.\\gamma\_\{i\}=\\begin\{cases\}\\Delta\_\{i\}^\{\-\},&i\\notin\\mathcal\{P\}^\{\\star\},\\\\\[4\.30554pt\] \\Delta\_\{i\}^\{\+\},&i\\in\\mathcal\{P\}^\{\\star\}\.\\end\{cases\}For a dominated configuration,γi\\gamma\_\{i\}measures the strongest uniform domination margin\. For a Pareto\-optimal configuration, the two terms inΔi\+\\Delta\_\{i\}^\{\+\}jointly account for its separation from other Pareto arms and from dominated competitors\.

We assumeγi\>0\\gamma\_\{i\}\>0for everyii, as exact identification is not statistically well posed when a classification gap is zero\. Letγ\(1\)≤γ\(2\)≤⋯≤γ\(K\)\\gamma\_\{\(1\)\}\\leq\\gamma\_\{\(2\)\}\\leq\\cdots\\leq\\gamma\_\{\(K\)\}denote the ordered classification gaps\. For any𝒜⊆\[K\]\\mathcal\{A\}\\subseteq\[K\], its aggregate cost isC​\(𝒜\)=∑i∈𝒜ci\.C\(\\mathcal\{A\}\)=\\sum\_\{i\\in\\mathcal\{A\}\}c\_\{i\}\.The deterministic\-cost problem complexity is

H𝝁,c=max∅≠𝒜⊆\[K\]⁡C​\(𝒜\)γ\(\|𝒜\|\)2\.H\_\{\\bm\{\\mu\},c\}=\\max\_\{\\emptyset\\neq\\mathcal\{A\}\\subseteq\[K\]\}\\frac\{C\(\\mathcal\{A\}\)\}\{\\gamma\_\{\(\|\\mathcal\{A\}\|\)\}^\{2\}\}\.This quantity jointly captures the statistical difficulty of distinguishing Pareto\-optimal and dominated configurations and the cost of evaluating the configurations that remain unresolved\.

## 4Algorithms

In this section, we present two cost\-aware algorithms for multi\-objective bandits, addressing online selection and Pareto set identification, respectively\.

### 4\.1Cost\-Aware Hypervolume UCB

We first introduceCoHV\-UCBfor budgeted online multi\-objective configuration selection\. Following the optimism\-in\-the\-face\-of\-uncertainty principle, the algorithm constructs an optimistic reward vector for each configuration and evaluates it using the hypervolume indicator\. It then divides the optimistic hypervolume by a lower confidence bound on the expected evaluation cost, yielding an optimistic hypervolume\-per\-cost index for configuration selection\.

CoHV\-UCBstarts with an initialization phase\. It pulls each arm once, observes its reward vector and evaluation cost, and initializes the empirical reward and cost estimates\. At the beginning of each round,CoHV\-UCBfirst computes empirical estimates for every arm\. For each objectived∈\[D\]d\\in\[D\], the empirical mean reward of armiiis

r¯i,t\(d\)=1ni,t​∑s<t:is=iri,s\(d\),\\bar\{r\}\_\{i,t\}^\{\(d\)\}=\\frac\{1\}\{n\_\{i,t\}\}\\sum\_\{s<t:i\_\{s\}=i\}r\_\{i,s\}^\{\(d\)\},whereni,t=∑s<t𝕀​\{is=i\}n\_\{i,t\}=\\sum\_\{s<t\}\\mathbb\{I\}\\\{i\_\{s\}=i\\\}is the number of times armiihas been evaluated before roundtt\.

Given the budgetBB, defineTB=⌈Bλ⌉\+1\.T\_\{B\}=\\left\\lceil\\frac\{B\}\{\\lambda\}\\right\\rceil\+1\.Because each evaluation incurs a cost of at leastλ\\lambda,TBT\_\{B\}provides a deterministic upper bound on the effective evaluation horizon\. Accordingly, the confidence radius for armiiat roundttis

βi,t=α​log⁡TBni,t,α≥2\.\\beta\_\{i,t\}=\\sqrt\{\\frac\{\\alpha\\log T\_\{B\}\}\{n\_\{i,t\}\}\},\\quad\\alpha\\geq 2\.
Using this confidence radius,CoHV\-UCBconstructs an optimistic estimate of thedd\-th objective:

Ui,t\(d\)=min⁡\{1,r¯i,t\(d\)\+βi,t\},d=1,…,D\.U\_\{i,t\}^\{\(d\)\}=\\min\\left\\\{1,\\,\\bar\{r\}\_\{i,t\}^\{\(d\)\}\+\\beta\_\{i,t\}\\right\\\},\\quad d=1,\\ldots,D\.Clipping the estimate ensures that the resulting objective vector remains within the normalized reward domain\[0,1\]D\[0,1\]^\{D\}\. The algorithm then estimates the evaluation cost of each arm\. The empirical mean cost of armiiis

c¯i,t=1ni,t​∑s<t:is=ici,s\.\\bar\{c\}\_\{i,t\}=\\frac\{1\}\{n\_\{i,t\}\}\\sum\_\{s<t:i\_\{s\}=i\}c\_\{i,s\}\.Because the selection index is inversely proportional to the estimated cost, underestimating the denominator can excessively inflate the index\. To avoid this issue,CoHV\-UCBemploys the truncated lower confidence bound

c¯i,t=max⁡\{λ2,c¯i,t−βi,t\}\.\\underline\{c\}\_\{i,t\}=\\max\\left\\\{\\frac\{\\lambda\}\{2\},\\,\\bar\{c\}\_\{i,t\}\-\\beta\_\{i,t\}\\right\\\}\.
Algorithm 1CoHV\-UCB: Cost\-aware HyperVolume UCB0:Budget

BB, number of arms

KK, cost lower bound

λ\\lambda
1:Pull each arm

i∈\[K\]i\\in\[K\]once and set

t=Kt=K
2:while

∑s=1tcas,s≤B\\sum\_\{s=1\}^\{t\}c\_\{a\_\{s\},s\}\\leq Bdo

3:Set

t=t\+1t=t\+1\.

4:foreach arm

i∈\[K\]i\\in\[K\]do

5:Compute the optimistic vector

𝐔i,t\\mathbf\{U\}\_\{i,t\}with entries

Ui,t\(d\)=min⁡\{1,r¯i,t\(d\)\+βi,t\},d=1,…,DU\_\{i,t\}^\{\(d\)\}=\\min\\left\\\{1,\\,\\bar\{r\}\_\{i,t\}^\{\(d\)\}\+\\beta\_\{i,t\}\\right\\\},\\quad d=1,\\ldots,D
6:Compute the lower confidence bound of the evaluation cost:

c¯i,t=max⁡\{λ/2,c¯i,t−βi,t\}\\underline\{c\}\_\{i,t\}=\\max\\left\\\{\\lambda/2,\\,\\bar\{c\}\_\{i,t\}\-\\beta\_\{i,t\}\\right\\\}
7:Compute the cost\-aware hypervolume index:

Ii,t=HV⁡\(𝐔i,t\)c¯i,tI\_\{i,t\}=\\frac\{\\operatorname\{HV\}\(\\mathbf\{U\}\_\{i,t\}\)\}\{\\underline\{c\}\_\{i,t\}\}
8:endfor

9:Pull the arm with the largest index:

it=arg⁡maxi∈\[K\]⁡Ii,ti\_\{t\}=\\arg\\max\_\{i\\in\[K\]\}I\_\{i,t\}
10:endwhile

After constructing the optimistic rewards and the lower confidence estimate of the evaluation cost,CoHV\-UCBcomputes the cost\-aware hypervolume UCB index,Ii,t=HV⁡\(𝐔i,t\)c¯i,t\.I\_\{i,t\}=\\frac\{\\operatorname\{HV\}\(\\mathbf\{U\}\_\{i,t\}\)\}\{\\underline\{c\}\_\{i,t\}\}\.The numerator measures the optimistic multi\-objective quality of the configuration, while the denominator measures a conservative estimate of its evaluation cost\. Thus,Ii,tI\_\{i,t\}provides an optimistic estimate of the hypervolume efficiency\.

At roundtt,CoHV\-UCBselects the configuration with the largest index,it=arg⁡maxi∈\[K\]⁡Ii,t\.i\_\{t\}=\\arg\\max\_\{i\\in\[K\]\}I\_\{i,t\}\.It then evaluates configurationiti\_\{t\}, observes the corresponding reward vector and evaluation cost, and updates the empirical reward and cost\. This procedure continues until the budgetBBis exhausted\.

We next establish the regret guarantee forCoHV\-UCB\. The resulting regret retains the logarithmic budget dependence and inverse\-gap dependence of cost\-aware single\-objective budgeted bandits\(Dinget al\.,[2013](https://arxiv.org/html/2608.04333#bib.bib278)\), up to additional factors arising from the hypervolume objective\.

###### Theorem 1\(Regret bound ofCoHV\-UCB\)

Letα≥2\\alpha\\geq 2and defineCλ,H=4​Dλ\+4λ2\.C\_\{\\lambda,H\}=\\frac\{4D\}\{\\lambda\}\+\\frac\{4\}\{\\lambda^\{2\}\}\.For each suboptimal armi≠i⋆i\\neq i^\{\\star\}, letni​\(B\)n\_\{i\}\(B\)denote the number of times armiiis pulled before the budgetBBis exhausted\. Then, underCoHV\-UCB,

𝔼​\[ni​\(B\)\]≤1\+⌈4​α​Cλ,H2​log⁡TBΔi2⌉\+2​K​\(D\+1\)​TB2−2​α\.\\displaystyle\\mathbb\{E\}\[n\_\{i\}\(B\)\]\\leq 1\+\\left\\lceil\\frac\{4\\alpha C\_\{\\lambda,H\}^\{2\}\\log T\_\{B\}\}\{\\Delta\_\{i\}^\{2\}\}\\right\\rceil\+2K\(D\+1\)T\_\{B\}^\{2\-2\\alpha\}\.Consequently, the hypervolume\-efficiency regret satisfies

𝔼​\[RBHV\]=∑i≠i⋆Δi​𝔼​\[ni​\(B\)\]=O​\(∑i≠i⋆Cλ,H2​log⁡BΔi\)\.\\displaystyle\\mathbb\{E\}\[R\_\{B\}^\{\\operatorname\{HV\}\}\]=\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\\,\\mathbb\{E\}\[n\_\{i\}\(B\)\]=O\\left\(\\sum\_\{i\\neq i^\{\\star\}\}\\frac\{C\_\{\\lambda,H\}^\{2\}\\log B\}\{\\Delta\_\{i\}\}\\right\)\.

Theorem[1](https://arxiv.org/html/2608.04333#Thmthm1)bounds the online loss in hypervolume per unit cost\. We next translate this result into a standard budgeted hypervolume regret bound, which compares the cumulative hypervolume with that of the optimal budgeted policy\.

###### Corollary 1\(Standard regret bound ofCoHV\-UCB\)

Under the conditions of Theorem[1](https://arxiv.org/html/2608.04333#Thmthm1), the standard budgeted hypervolume regret ofCoHV\-UCBsatisfies

𝔼​\[RBstd\]=O​\(∑i≠i⋆Cλ,H2​log⁡BΔi\)\.\\mathbb\{E\}\[R\_\{B\}^\{\\operatorname\{std\}\}\]=O\\left\(\\sum\_\{i\\neq i^\{\\star\}\}\\frac\{C\_\{\\lambda,H\}^\{2\}\\log B\}\{\\Delta\_\{i\}\}\\right\)\.

### 4\.2Cost\-Aware Pareto Set Identification

We now proposeCoPSI, a cost\-aware algorithm that allocates samples according to configuration\-dependent costs and progressively identifies the Pareto\-optimal configurations\.

Throughout the procedure,CoPSImaintains three sets\. At phaserr, the active set𝒜r\\mathcal\{A\}\_\{r\}contains the configurations whose Pareto status has not yet been resolved\. The set𝒫^\\widehat\{\\mathcal\{P\}\}collects configurations identified as Pareto\-optimal, whereasℛ^\\widehat\{\\mathcal\{R\}\}contains those identified as dominated\. Initially, all configurations are active, so that𝒜1=\[K\]\\mathcal\{A\}\_\{1\}=\[K\], while𝒫^\\widehat\{\\mathcal\{P\}\}andℛ^\\widehat\{\\mathcal\{R\}\}are both empty\.

At the beginning of phaserr,CoPSIcomputes the total cost of evaluating the active configurations,Cr=C​\(𝒜r\)=∑i∈𝒜rci\.C\_\{r\}=C\(\\mathcal\{A\}\_\{r\}\)=\\sum\_\{i\\in\\mathcal\{A\}\_\{r\}\}c\_\{i\}\.It then sets the cumulative sampling target tonr=⌊BLK,λ​Cr⌋,n\_\{r\}=\\left\\lfloor\\frac\{B\}\{L\_\{K,\\lambda\}C\_\{r\}\}\\right\\rfloor,whereLK,λ=1\+∑ℓ=2K11\+\(ℓ−1\)​λ\.L\_\{K,\\lambda\}=1\+\\sum\_\{\\ell=2\}^\{K\}\\frac\{1\}\{1\+\(\\ell\-1\)\\lambda\}\.This allocation assigns the number of evaluations to each active configuration while accounting for the aggregate cost of evaluating the current active set\. As the active set shrinks, the budget can support more samples for the remaining configurations\.

Given the targetnrn\_\{r\},CoPSIthen brings every active configuration up to this sampling level\. Specifically, each configurationi∈𝒜ri\\in\\mathcal\{A\}\_\{r\}is samplednr−Nin\_\{r\}\-N\_\{i\}additional times, whereNiN\_\{i\}denotes the number of previous evaluations of configurationii\. The empirical mean vector is then updated by

𝝁^i,r=1Ni​∑s=1Ni𝒓i,s\.\\widehat\{\\bm\{\\mu\}\}\_\{i,r\}=\\frac\{1\}\{N\_\{i\}\}\\sum\_\{s=1\}^\{N\_\{i\}\}\\bm\{r\}\_\{i,s\}\.
Using these empirical means,CoPSIconstructs the empirical Pareto set over the active configurations:

𝒫^remp=\{i∈𝒜r:∄​j∈𝒜r∖\{i\}​such that​𝝁^i,r≺𝝁^j,r\}\.\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\,\\mathrm\{emp\}\}=\\left\\\{i\\in\\mathcal\{A\}\_\{r\}:\\nexists j\\in\\mathcal\{A\}\_\{r\}\\setminus\\\{i\\\}\\text\{ such that \}\\widehat\{\\bm\{\\mu\}\}\_\{i,r\}\\prec\\widehat\{\\bm\{\\mu\}\}\_\{j,r\}\\right\\\}\.Thus, every configuration outside𝒫^remp\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\mathrm\{emp\}\}is empirically dominated by at least one active configuration, whereas every configuration in𝒫^remp\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\mathrm\{emp\}\}is empirically nondominated\.

Algorithm 2CoPSI: Cost\-aware Pareto Set Identification0:Budget

BB, arm costs

\{ci\}i=1K\\\{c\_\{i\}\\\}\_\{i=1\}^\{K\}
1:Initialize the active set

𝒜1=\[K\]\\mathcal\{A\}\_\{1\}=\[K\], the accepted Pareto set

𝒫^=∅\\widehat\{\\mathcal\{P\}\}=\\emptyset, and the rejected set

ℛ^=∅\\widehat\{\\mathcal\{R\}\}=\\emptyset
2:Set

Ni=0N\_\{i\}=0for all

i∈\[K\]i\\in\[K\]
3:Set

LK,λ=1\+∑ℓ=2K11\+\(ℓ−1\)​λL\_\{K,\\lambda\}=1\+\\sum\_\{\\ell=2\}^\{K\}\\frac\{1\}\{1\+\(\\ell\-1\)\\lambda\}
4:Set

n0=0n\_\{0\}=0
5:for

r=1,…,K−1r=1,\\ldots,K\-1do

6:Set

kr=\|𝒜r\|k\_\{r\}=\|\\mathcal\{A\}\_\{r\}\|and

Cr=C​\(𝒜r\)=∑i∈𝒜rciC\_\{r\}=C\(\\mathcal\{A\}\_\{r\}\)=\\sum\_\{i\\in\\mathcal\{A\}\_\{r\}\}c\_\{i\}\.

7:Set the cumulative sampling target

nr=⌊BLK,λ​Cr⌋\.n\_\{r\}=\\left\\lfloor\\frac\{B\}\{L\_\{K,\\lambda\}C\_\{r\}\}\\right\\rfloor\.
8:for

i∈𝒜ri\\in\\mathcal\{A\}\_\{r\}do

9:Pull arm

iiexactly

nr−Nin\_\{r\}\-N\_\{i\}additional times

10:Update

Ni←nrN\_\{i\}\\leftarrow n\_\{r\}
11:Compute the empirical mean

𝝁^i,r=1Ni​∑s=1Ni𝒓i,s\.\\widehat\{\\bm\{\\mu\}\}\_\{i,r\}=\\frac\{1\}\{N\_\{i\}\}\\sum\_\{s=1\}^\{N\_\{i\}\}\\bm\{r\}\_\{i,s\}\.
12:endfor

13:Compute the empirical Pareto set:

𝒫^remp=\{i∈𝒜r:∄​j∈𝒜r∖\{i\}​such that​𝝁^i,r≺𝝁^j,r\}\.\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\mathrm\{emp\}\}=\\\{i\\in\\mathcal\{A\}\_\{r\}:\\nexists j\\in\\mathcal\{A\}\_\{r\}\\setminus\\\{i\\\}\\text\{ such that \}\\widehat\{\\bm\{\\mu\}\}\_\{i,r\}\\prec\\widehat\{\\bm\{\\mu\}\}\_\{j,r\}\\\}\.
14:Compute the empirical gap

γ^i,r\\widehat\{\\gamma\}\_\{i,r\}for all

i∈𝒜ri\\in\\mathcal\{A\}\_\{r\}by \([1](https://arxiv.org/html/2608.04333#S4.E1)\)

15:Choose

er∈arg⁡maxi∈𝒜r⁡γ^i,re\_\{r\}\\in\\arg\\max\_\{i\\in\\mathcal\{A\}\_\{r\}\}\\widehat\{\\gamma\}\_\{i,r\}; if there are multiple maximizers, select one in

𝒜r∖𝒫^remp\\mathcal\{A\}\_\{r\}\\setminus\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\mathrm\{emp\}\}whenever possible

16:if

er∈𝒫^rempe\_\{r\}\\in\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\mathrm\{emp\}\}then

17:Accept

ere\_\{r\}:

𝒫^←𝒫^∪\{er\}\.\\widehat\{\\mathcal\{P\}\}\\leftarrow\\widehat\{\\mathcal\{P\}\}\\cup\\\{e\_\{r\}\\\}\.
18:else

19:Reject

ere\_\{r\}:

ℛ^←ℛ^∪\{er\}\.\\widehat\{\\mathcal\{R\}\}\\leftarrow\\widehat\{\\mathcal\{R\}\}\\cup\\\{e\_\{r\}\\\}\.
20:endif

21:Update the active set

𝒜r\+1=𝒜r∖\{er\}\.\\mathcal\{A\}\_\{r\+1\}=\\mathcal\{A\}\_\{r\}\\setminus\\\{e\_\{r\}\\\}\.
22:endfor

23:return

𝒫^B=𝒫^∪𝒜K\.\\widehat\{\\mathcal\{P\}\}\_\{B\}=\\widehat\{\\mathcal\{P\}\}\\cup\\mathcal\{A\}\_\{K\}\.

After identifying the empirical Pareto set,CoPSIfurther quantifies how confidently each active configuration can be classified\. For any phaserrand any two configurationsi,j∈𝒜ri,j\\in\\mathcal\{A\}\_\{r\}, define the empirical pairwise margins

m^r​\(i,j\)\\displaystyle\\widehat\{m\}\_\{r\}\(i,j\)=mind∈\[D\]⁡\(μ^j,r\(d\)−μ^i,r\(d\)\),\\displaystyle=\\min\_\{d\\in\[D\]\}\\left\(\\widehat\{\\mu\}\_\{j,r\}^\{\(d\)\}\-\\widehat\{\\mu\}\_\{i,r\}^\{\(d\)\}\\right\),M^r​\(i,j\)\\displaystyle\\widehat\{M\}\_\{r\}\(i,j\)=maxd∈\[D\]⁡\(μ^i,r\(d\)−μ^j,r\(d\)\)\.\\displaystyle=\\max\_\{d\\in\[D\]\}\\left\(\\widehat\{\\mu\}\_\{i,r\}^\{\(d\)\}\-\\widehat\{\\mu\}\_\{j,r\}^\{\(d\)\}\\right\)\.Here,m^r​\(i,j\)\\widehat\{m\}\_\{r\}\(i,j\)measures the minimum coordinate\-wise advantage of configurationjjover configurationii, whileM^r​\(i,j\)\\widehat\{M\}\_\{r\}\(i,j\)measures the largest coordinate\-wise advantage\.

Letx\+=max⁡\{x,0\}x^\{\+\}=\\max\\\{x,0\\\}\. For each active configurationi∈𝒜ri\\in\\mathcal\{A\}\_\{r\}, define the empirical dominatedness gap

Δ^i,r−=maxj∈𝒜r∖\{i\}⁡m^r​\(i,j\),\\widehat\{\\Delta\}\_\{i,r\}^\{\-\}=\\max\_\{j\\in\\mathcal\{A\}\_\{r\}\\setminus\\\{i\\\}\}\\widehat\{m\}\_\{r\}\(i,j\),which measures the strongest empirical evidence thatiiis dominated by another active configuration\. We also define the empirical nondominatedness gap

Δ^i,r\+=minj∈𝒜r∖\{i\}⁡\[M^r​\(i,j\)∧\(M^r​\(j,i\)\+\+\(Δ^j,r−\)\+\)\]\.\\widehat\{\\Delta\}\_\{i,r\}^\{\+\}=\\min\_\{j\\in\\mathcal\{A\}\_\{r\}\\setminus\\\{i\\\}\}\\left\[\\widehat\{M\}\_\{r\}\(i,j\)\\wedge\\left\(\\widehat\{M\}\_\{r\}\(j,i\)^\{\+\}\+\\left\(\\widehat\{\\Delta\}\_\{j,r\}^\{\-\}\\right\)^\{\+\}\\right\)\\right\]\.This quantity evaluates the empirical evidence thatiishould remain Pareto optimal, while also accounting for whether its competitors are themselves empirically dominated\.

The empirical classification gap is then defined according to the empirical status of configurationii:

γ^i,r=\{Δ^i,r−,i∉𝒫^remp,Δ^i,r\+,i∈𝒫^remp\.\\widehat\{\\gamma\}\_\{i,r\}=\\begin\{cases\}\\widehat\{\\Delta\}\_\{i,r\}^\{\-\},&i\\notin\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\mathrm\{emp\}\},\\\\\[4\.30554pt\] \\widehat\{\\Delta\}\_\{i,r\}^\{\+\},&i\\in\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\mathrm\{emp\}\}\.\\end\{cases\}\(1\)Thus,γ^i,r\\widehat\{\\gamma\}\_\{i,r\}measures how reliably the current empirical evidence supports the classification of configurationiias either dominated or nondominated\. A larger value indicates that the status of the configuration is easier to determine, and hence the configuration can be safely removed from the active set\.

Finally,CoPSIremoves the active configuration with the largest empirical classification gap:er∈arg⁡maxi∈𝒜r⁡γ^i,r\.e\_\{r\}\\in\\arg\\max\_\{i\\in\\mathcal\{A\}\_\{r\}\}\\widehat\{\\gamma\}\_\{i,r\}\.If the maximizer is not unique,CoPSIselects one from𝒜r∖𝒫^remp\\mathcal\{A\}\_\{r\}\\setminus\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\mathrm\{emp\}\}whenever possible\. The selected configuration is accepted if it belongs to𝒫^remp\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\mathrm\{emp\}\}and rejected otherwise\.

Ifer∈𝒫^rempe\_\{r\}\\in\\widehat\{\\mathcal\{P\}\}\_\{r\}^\{\\,\\mathrm\{emp\}\}, it is accepted into𝒫^\\widehat\{\\mathcal\{P\}\}\. Otherwise, it is rejected and added intoℛ^\\widehat\{\\mathcal\{R\}\}\. The classified configuration is then removed from the active set:

𝒜r\+1=𝒜r∖\{er\}\.\\mathcal\{A\}\_\{r\+1\}=\\mathcal\{A\}\_\{r\}\\setminus\\\{e\_\{r\}\\\}\.The procedure runs forK−1K\-1phases, leaving one unclassified arm in𝒜K\\mathcal\{A\}\_\{K\}\. This final arm is included in the output, so that𝒫^B=𝒫^∪𝒜K\\widehat\{\\mathcal\{P\}\}\_\{B\}=\\widehat\{\\mathcal\{P\}\}\\cup\\mathcal\{A\}\_\{K\}\.

This elimination procedure is cost\-aware because the sampling target in each phase depends on the total costCrC\_\{r\}of the active configurations\. It is also Pareto\-aware because configurations are accepted or rejected according to empirical dominance relations\. These properties makeCoPSIparticularly suitable for fixed\-budget LLM configuration evaluation, where the objective is to identify a diverse set of nondominated configurations that captures different trade\-offs among accuracy, latency, and efficiency\.

We next establish the theoretical guarantee ofCoPSI, showing that the probability of incorrectly identifying the Pareto set decreases exponentially with the available evaluation budget\.

###### Theorem 2\(Fixed\-budget error probability ofCoPSI\)

LetK≥2K\\geq 2and defineLK,λ=1\+∑ℓ=2K11\+\(ℓ−1\)​λ\.L\_\{K,\\lambda\}=1\+\\sum\_\{\\ell=2\}^\{K\}\\frac\{1\}\{1\+\(\\ell\-1\)\\lambda\}\.If the budget satisfiesB≥2​LK,λ​H𝛍,c,B\\geq 2L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\},then the Pareto set estimate returned byCoPSIsatisfies

Pr​\(𝒫^B≠𝒫⋆\)≤2​K2​D​exp⁡\(−B256​LK,λ​H𝝁,c\)\.\\mathrm\{Pr\}\\left\(\\widehat\{\\mathcal\{P\}\}\_\{B\}\\neq\\mathcal\{P\}^\{\\star\}\\right\)\\leq 2K^\{2\}D\\exp\\left\(\-\\frac\{B\}\{256L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\}\}\\right\)\.

Theorem[2](https://arxiv.org/html/2608.04333#Thmthm2)quantifies the difficulty of fixed\-budget Pareto configuration identification through the cost\-aware complexity measureH𝝁,cH\_\{\\bm\{\\mu\},c\}\. In particular, the probability of incorrectly identifying the Pareto set decreases exponentially with the available budgetBB\. Moreover, when all configurations have unit evaluation costs, the bound recovers the standard exponential error rate for fixed\-budget Pareto set identification\(Koneet al\.,[2024](https://arxiv.org/html/2608.04333#bib.bib292)\)\.

## 5Experiments

In this section, we conduct numerical experiments to evaluate the statistical performance and budget efficiency of the proposed methods on real LLM configuration data\.

### 5\.1Experimental Setup

Table 1:Configuration\-level dataset statistics\.#### Datasets\.

We use GSM8K\(Cobbeet al\.,[2021](https://arxiv.org/html/2608.04333#bib.bib262)\)and PIQA\(Bisket al\.,[2020](https://arxiv.org/html/2608.04333#bib.bib263)\), with 1,000 validation instances evaluated for every configuration\. Each configuration combines a model, temperature, generation limit, and prompting strategy\. GSM8K contains nine models and 108 configurations, while PIQA contains 11 models and 132 configurations\. Table[1](https://arxiv.org/html/2608.04333#S5.T1)summarizes their configuration\-level statistics\.

![Refer to caption](https://arxiv.org/html/2608.04333v1/x1.png)Figure 1:Configuration landscapes on GSM8K and PIQA\.
#### Configuration landscapes\.

Beyond the aggregate ranges in Table[1](https://arxiv.org/html/2608.04333#S5.T1), Figure[1](https://arxiv.org/html/2608.04333#S5.F1)shows the accuracy–efficiency trade\-offs of individual configurations\. Both axes are maximization objectives: efficiency is measured by normalized inverse latency\. Point size represents mean token consumption, and the black curve marks the empirical Pareto front\.

#### Evaluation settings\.

Online selection uses every configuration in each dataset\. For exact Pareto identification, the complete sets contain many tied or near\-tied empirical means; we therefore use a pre\-specified 14\-arm subset comprising seven common models at temperatures 0\.5 and 1\.0\. It contains two Pareto arms on GSM8K and three on PIQA\. Full\-set approximate recovery and all preprocessing, replay, budget, and hyperparameter details are provided in the Appendix[A](https://arxiv.org/html/2608.04333#A1)\.

#### Baselines\.

For online selection, we compareCoHV\-UCBwith three baselines\.HV\-UCBremoves the cost denominator from the proposed index and isolates the effect of cost awareness\.Accuracy\-Cost\-UCBoptimizes optimistic accuracy per token and isolates the value of modeling multiple objectives\. Uniform round\-robin allocation provides a non\-adaptive reference\. All three UCB\-based methods use the same experimental confidence\-radius calibration\.

For fixed\-budget identification, we compareCoPSIwith PSI\-SR, which ignores heterogeneous evaluation costs, and uniform allocation followed by empirical Pareto estimation\. These comparisons separate the effect of cost\-aware allocation from that of successive elimination and provide a strong non\-adaptive reference when the arm gaps are relatively balanced\.

![Refer to caption](https://arxiv.org/html/2608.04333v1/x2.png)Figure 2:Main experimental results\. Panels \(a\)–\(b\) show hypervolume\-efficiency regret over 100 paired replays; panels \(c\)–\(d\) showlog10⁡Pr​\(𝒫^B≠𝒫⋆\)\\log\_\{10\}\\mathrm\{Pr\}\(\\widehat\{\\mathcal\{P\}\}\_\{B\}\\neq\\mathcal\{P\}^\{\\star\}\)in the structured 14\-arm setting over 500 replays\. Shaded regions are 95% confidence intervals\.

### 5\.2Experimental Results

#### Online selection\.

The primary measure is hypervolume\-efficiency regret, which evaluates the quality obtained per unit cost over the decision process\. Standard hypervolume regret, within\-run trajectories, and additional diagnostics are provided in Appendix[A](https://arxiv.org/html/2608.04333#A1)\.

Figure[2](https://arxiv.org/html/2608.04333#S5.F2)\(a\)–\(b\) shows that adaptive multi\-objective selection consistently outperforms uniform allocation as the budget increases\. At the largest tested token budgets,CoHV\-UCBreduces the hypervolume\-efficiency regret from 169\.45 to 59\.88 on GSM8K and from 6538\.22 to 1097\.75 on PIQA, corresponding to relative reductions of 64\.7% and 83\.2%, respectively\. These results indicate thatCoHV\-UCBeffectively uses the available token budget and avoids repeatedly evaluating configurations with poor multi\-objective efficiency\.

The improvement ofCoHV\-UCBoverHV\-UCBis smaller on GSM8K than on PIQA\. This is because rewards and costs are more aligned on GSM8K\. Its profiling token costs vary only mildly, from 118\.37 to 147\.21 tokens, and the configuration with the largest hypervolume also achieves the largest hypervolume\-per\-cost value\. Thus, cost normalization barely changes the arm ranking\. In contrast, PIQA has larger cost dispersion, with costs ranging from 95\.01 to 152\.16 tokens, and its hypervolume\-maximizing configuration differs from its efficiency\-maximizing configuration\. As a result, the cost denominator changes the preferred configuration more substantially, leading to a larger advantage forCoHV\-UCB\.

CoHV\-UCBalso consistently improves overAccuracy\-Cost\-UCB, showing the benefit of optimizing both accuracy and efficiency rather than accuracy alone\. Because the horizontal axis displayslog2⁡B\\log\_\{2\}B, logarithmic dependence on the budget corresponds to a linear trend in this coordinate\. The finite\-budget curves may deviate from exact linearity because Theorem[1](https://arxiv.org/html/2608.04333#Thmthm1)provides an upper bound rather than an equality\.

#### Pareto set identification\.

Figure[2](https://arxiv.org/html/2608.04333#S5.F2)\(c\)–\(d\) reports the base\-10 logarithm of the identification error probability in Theorem[2](https://arxiv.org/html/2608.04333#Thmthm2)\. The advantage of successive elimination becomes clearer as the budget increases\. On GSM8K,CoPSIreduces the error probability from 0\.614 to 0\.004 over the displayed budget range, compared with 0\.662 to 0\.026 for uniform allocation\. At the largest budget, this corresponds to an 84\.6% relative reduction\. On PIQA,CoPSIachieves an error probability of 0\.148 at the largest budget, compared with 0\.270 for uniform allocation, yielding 45\.2% lower error\.

Uniform allocation is competitive at the smallest budgets because it avoids committing to noisy early classifications\. With more observations, however,CoPSIcan eliminate arms whose status is already clear and concentrate the remaining budget on configurations near the Pareto boundary\. This explains why its advantage over uniform allocation widens with the budget\. The cost\-insensitive PSI\-SR method also benefits from successive elimination, butCoPSIattains lower errors at the largest budget, with 0\.004 versus 0\.006 on GSM8K and 0\.148 versus 0\.164 on PIQA\. The modest difference between the two elimination methods is consistent with the limited cost dispersion in the selected configurations\. Additional results and analysis are provided in Appendix[A](https://arxiv.org/html/2608.04333#A1)\.

## 6Conclusion and Future Work

In this paper, we studied LLM configuration evaluation as a cost\-aware multi\-objective bandit problem under limited evaluation budgets\. We considered two complementary objectives: online configuration selection through regret minimization and Pareto\-optimal configuration identification under a fixed budget\. For online selection, we proposedCoHV\-UCB, which selects configurations by optimizing a hypervolume\-per\-cost index\. We proved that its standard budgeted regret bound isO​\(∑i≠i⋆Cλ,H2​log⁡BΔi\)O\\left\(\\sum\_\{i\\neq i^\{\\star\}\}\\frac\{C\_\{\\lambda,H\}^\{2\}\\log B\}\{\\Delta\_\{i\}\}\\right\), showing logarithmic dependence on the evaluation budget and matching the classical single\-objective budgeted bandit result in budget and gap dependence\. For fixed\-budget identification, we proposedCoPSI, which uses cost\-aware sampling and empirical Pareto gaps to identify non\-dominated configurations\. Its error probability is bounded by2​K2​D​exp⁡\(−B256​LK,λ​H𝝁,c\)2K^\{2\}D\\exp\\left\(\-\\frac\{B\}\{256L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\}\}\\right\), which recovers the standard fixed\-budget Pareto set identification rate when all evaluation costs are equal\. Experiments on LLM configuration evaluation tasks further demonstrate the benefit of jointly considering evaluation cost and multiple objectives\.

Several directions remain for future work\. First, the current formulation treats each LLM configuration as an independent arm; incorporating structural information among models, prompts, and decoding parameters may further improve sample efficiency\. Second, extending the framework to contextual or non\-stationary settings would be useful for personalized evaluation and evolving deployment environments\. Third, more robust Pareto identification algorithms are needed when objective gaps are small or early estimates are unreliable\.

## References

- Bandit\-based prompt design strategy selection improves prompt optimizers\.InFindings of the Association for Computational Linguistics: ACL 2025,pp\. 20799–20817\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p4.1)\.
- J\. Audibert and S\. Bubeck \(2010\)Best arm identification in multi\-armed bandits\.InProceedings of the 23rd Annual Conference on Learning Theory,pp\. 41–53\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- P\. Auer, C\. Chiang, R\. Ortner, and M\. Drugan \(2016\)Pareto front identification from stochastic bandit feedback\.InProceedings of the 19th International Conference on Artificial Intelligence and Statistics,pp\. 939–947\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px2.p1.1)\.
- P\. Auer \(2002\)Using confidence bounds for exploitation\-exploration trade\-offs\.Journal of Machine Learning Research3\(11\),pp\. 397–422\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Badanidiyuru, R\. Kleinberg, and A\. Slivkins \(2018\)Bandits with knapsacks\.Journal of the ACM65\(3\),pp\. 1–55\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Badanidiyuru, J\. Langford, and A\. Slivkins \(2014\)Resourceful contextual bandits\.InProceedings of The 27th Conference on Learning Theory,pp\. 1109–1134\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- Y\. Bisk, R\. Zellers, R\. L\. Bras, J\. Gao, and Y\. Choi \(2020\)PIQA: reasoning about physical commonsense in natural language\.InProceedings of the 34th AAAI Conference on Artificial Intelligence,Cited by:[§3](https://arxiv.org/html/2608.04333#S3.p2.2),[§5\.1](https://arxiv.org/html/2608.04333#S5.SS1.SSS0.Px1.p1.1)\.
- Y\. Chang, X\. Wang, J\. Wang, Y\. Wu, L\. Yang, K\. Zhu, H\. Chen, X\. Yi, C\. Wang, Y\. Wang, W\. Ye, Y\. Zhang, Y\. Chang, P\. S\. Yu, Q\. Yang, and X\. Xie \(2024\)A survey on evaluation of large language models\.ACM Transactions on Intelligent Systems and Technology15\(3\),pp\. 1–45\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p1.1),[§1](https://arxiv.org/html/2608.04333#S1.p2.1),[§1](https://arxiv.org/html/2608.04333#S1.p4.1)\.
- L\. Chen, M\. Zaharia, and J\. Zou \(2024\)FrugalGPT: how to use large language models while reducing cost and improving performance\.Transactions on Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p4.1)\.
- K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano, C\. Hesse, and J\. Schulman \(2021\)Training verifiers to solve math word problems\.External Links:2110\.14168,[Link](https://arxiv.org/abs/2110.14168)Cited by:[§3](https://arxiv.org/html/2608.04333#S3.p2.2),[§5\.1](https://arxiv.org/html/2608.04333#S5.SS1.SSS0.Px1.p1.1)\.
- É\. Crepon, A\. Garivier, and W\. M Koolen \(2024\)Sequential learning of the Pareto front for multi\-objective bandits\.InProceedings of The 27th International Conference on Artificial Intelligence and Statistics,pp\. 3583–3591\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px2.p1.1)\.
- W\. Ding, T\. Qiny, X\. Zhang, and T\. Liu \(2013\)Multi\-armed bandit with budget constraint and variable costs\.InProceedings of the 27th AAAI Conference on Artificial Intelligence,pp\. 232–238\.Cited by:[1st item](https://arxiv.org/html/2608.04333#S1.I1.i1.p1.5),[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2608.04333#S4.SS1.p7.1)\.
- M\. M\. Drugan and A\. Nowe \(2013\)Designing multi\-objective multi\-armed bandits algorithms: a study\.InThe 2013 International Joint Conference on Neural Networks,pp\. 1–8\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px2.p1.1)\.
- K\. Feng, K\. Ding, T\. Hongzhi, K\. Ma, Z\. Wang, S\. Guo, C\. Yuzhou, G\. Sun, G\. Zheng, Q\. Zhang, and H\. Chen \(2025\)Sample\-efficient human evaluation of large language models via maximum discrepancy competition\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 10913–10947\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p2.1)\.
- V\. Gabillon, M\. Ghavamzadeh, and A\. Lazaric \(2012\)Best arm identification: a unified approach to fixed budget and fixed confidence\.InAdvances in Neural Information Processing Systems 25,pp\. 3212 – 3220\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- Z\. Hong, Q\. Zhang, J\. Sun, Z\. Shang, M\. Kong, X\. Wang, Y\. Shu, and Z\. Dai \(2026\)MASPOB: bandit\-based prompt optimization for multi\-agent systems with graph neural networks\.InProceedings of the 43rd International Conference on Machine Learning,Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px3.p1.1)\.
- N\. Immorlica, K\. Sankararaman, R\. Schapire, and A\. Slivkins \(2022\)Adversarial bandits with knapsacks\.Journal of the ACM69\(6\),pp\. 1–47\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- K\. Jamieson, M\. Malloy, R\. Nowak, and S\. Bubeck \(2014\)Lil’ ucb : an optimal exploration algorithm for multi\-armed bandits\.InProceedings of The 27th Conference on Learning Theory,pp\. 423–439\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- C\. Kone, E\. Kaufmann, and L\. Richert \(2023\)Adaptive algorithms for relaxed pareto set identification\.InAdvances in Neural Information Processing Systems 36,Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px2.p1.1)\.
- C\. Kone, E\. Kaufmann, and L\. Richert \(2024\)Bandit Pareto set identification: the fixed budget setting\.InProceedings of The 27th International Conference on Artificial Intelligence and Statistics,pp\. 2548–2556\.Cited by:[2nd item](https://arxiv.org/html/2608.04333#S1.I1.i2.p1.2),[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px2.p1.1),[§3\.2](https://arxiv.org/html/2608.04333#S3.SS2.p2.10),[§3\.2](https://arxiv.org/html/2608.04333#S3.SS2.p4.7),[§4\.2](https://arxiv.org/html/2608.04333#S4.SS2.p13.2)\.
- T\. L\. Lai and H\. Robbins \(1985\)Asymptotically efficient adaptive allocation rules\.Advances in Applied Mathematics6\(1\),pp\. 4–22\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- T\. Lattimore and C\. Szepesvári \(2020\)Bandit algorithms\.Cambridge University Press\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p4.1)\.
- D\. Li, B\. Jiang, L\. Huang, A\. Beigi, C\. Zhao, Z\. Tan, A\. Bhattacharjee, Y\. Jiang, C\. Chen, T\. Wu, K\. Shu, L\. Cheng, and H\. Liu \(2025\)From generation to judgment: opportunities and challenges of LLM\-as\-a\-judge\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,pp\. 2757–2791\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p1.1),[§1](https://arxiv.org/html/2608.04333#S1.p2.1)\.
- H\. Li and Y\. Xia \(2017\)Infinitely many\-armed bandits with budget constraints\.InProceedings of the 31st AAAI Conference on Artificial Intelligence,pp\. 2182–2188\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- P\. Liang, R\. Bommasani, T\. Lee, and et al\. \(2023\)Holistic evaluation of language models\.Transactions on Machine Learning Research\.External Links:ISSN 2835–8856Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p1.1),[§1](https://arxiv.org/html/2608.04333#S1.p2.1),[§1](https://arxiv.org/html/2608.04333#S1.p4.1)\.
- X\. Lin, Z\. Wu, Z\. Dai, W\. Hu, Y\. Shu, S\. Ng, P\. Jaillet, and B\. K\. H\. Low \(2024\)Use your INSTINCT: INSTruction optimization for LLMs usIng neural bandits coupled with transformers\.InProceedings of the 41st International Conference on Machine Learning,pp\. 30317–30345\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px3.p1.1)\.
- S\. Liu, J\. Jiang, and X\. Li \(2022\)Non\-stationary bandits with knapsacks\.InAdvances in Neural Information Processing Systems 35,pp\. 16522–16532\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Lu, G\. Wang, Y\. Hu, and L\. Zhang \(2019\)Optimal algorithms for lipschitz bandits with heavy\-tailed rewards\.InProceedings of the 36th International Conference on Machine Learning,pp\. 4154–4163\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px2.p1.1)\.
- I\. Ong, A\. Almahairi, V\. Wu, W\. Chiang, T\. Wu, J\. E\. Gonzalez, M\. W\. Kadous, and I\. Stoica \(2025\)RouteLLM: learning to route LLMs with preference data\.InThe 13th International Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p4.1)\.
- F\. M\. Polo, R\. Xu, L\. Weber, M\. Silva, O\. Bhardwaj, L\. Choshen, A\. F\. M\. de Oliveira, Y\. Sun, and M\. Yurochkin \(2024\)Efficient multi\-prompt evaluation of large language models\.InAdvances in Neural Information Processing Systems 37,pp\. 22483–22512\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p4.1)\.
- M\. Poon, X\. Dai, X\. Liu, F\. Kong, J\. C\. S\. Lui, and J\. Zuo \(2025\)Online multi\-llm selection via contextual bandits under unstructured context evolution\.External Links:2506\.17670,[Link](https://arxiv.org/abs/2506.17670)Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px3.p1.1)\.
- R\. Pryzant, D\. Iter, J\. Li, Y\. Lee, C\. Zhu, and M\. Zeng \(2023\)Automatic prompt optimization with “gradient descent” and beam search\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,pp\. 7957–7968\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px3.p1.1)\.
- S\. Qiu, D\. Zhang, R\. Yang, B\. Lyu, and T\. Zhang \(2024\)Traversing pareto optimal policies: provably efficient multi\-objective reinforcement learning\.arXiv preprint arXiv:2407\.17466\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px2.p1.1)\.
- K\. A\. Sankararaman and A\. Slivkins \(2018\)Combinatorial semi\-bandits with knapsacks\.InProceedings of the Twenty\-First International Conference on Artificial Intelligence and Statistics,pp\. 1760–1770\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- C\. Shi, K\. Yang, Z\. Chen, J\. Li, J\. Yang, and C\. Shen \(2024a\)Efficient prompt optimization through the lens of best arm identification\.InAdvances in Neural Information Processing Systems 37,pp\. 99646–99685\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p3.1),[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px3.p1.1)\.
- C\. Shi, H\. Yang, D\. Cai, Z\. Zhang, Y\. Wang, Y\. Yang, and W\. Lam \(2024b\)A thorough examination of decoding methods in the era of LLMs\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,pp\. 8601–8629\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p1.1)\.
- J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, b\. ichter, F\. Xia, E\. Chi, Q\. V\. Le, and D\. Zhou \(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.InAdvances in Neural Information Processing Systems 35,pp\. 24824–24837\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p1.1)\.
- Z\. Wu, X\. Lin, Z\. Dai, W\. Hu, Y\. Shu, S\. Ng, P\. Jaillet, and B\. K\. H\. Low \(2024\)Prompt optimization with ease? efficient ordering\-aware automated selection of exemplars\.InAdvances in Neural Information Processing Systems 37,pp\. 122706–122740\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px3.p1.1)\.
- Y\. Xia, H\. Li, T\. Qin, N\. Yu, and T\. Liu \(2015\)Thompson sampling for budgeted multi\-armed bandits\.InProceedings of the 24th International Conference on Artificial Intelligence,pp\. 3960–3966\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- Y\. Xia, T\. Qin, W\. Ma, N\. Yu, and T\. Liu \(2016\)Budgeted multi\-armed bandits with multiple plays\.InProceedings of the 25th International Joint Conference on Artificial Intelligence,pp\. 2210–2216\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px1.p1.1)\.
- Q\. \(\. Zhang \(2024\)Optimal scalarizations for sublinear hypervolume regret\.InAdvances in Neural Information Processing Systems 37,pp\. 39963–39999\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px2.p1.1)\.
- R\. Zhang and D\. Golovin \(2020\)Random hypervolume scalarizations for provable multi\-objective black box optimization\.InProceedings of the 37th International Conference on Machine Learning,pp\. 11096–11105\.Cited by:[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px2.p1.1)\.
- L\. Zheng, W\. Chiang, Y\. Sheng, S\. Zhuang, Z\. Wu, Y\. Zhuang, Z\. Lin, Z\. Li, D\. Li, E\. Xing, H\. Zhang, J\. E\. Gonzalez, and I\. Stoica \(2023\)Judging llm\-as\-a\-judge with mt\-bench and chatbot arena\.InAdvances in Neural Information Processing Systems 36,pp\. 46595–46623\.Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p1.1),[§1](https://arxiv.org/html/2608.04333#S1.p2.1)\.
- J\. P\. Zhou, C\. K\. Belardi, R\. Wu, T\. Zhang, C\. P\. Gomes, W\. Sun, and K\. Q\. Weinberger \(2025\)On speeding up language model evaluation\.InThe 13th International Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p3.1),[§1](https://arxiv.org/html/2608.04333#S1.p4.1),[§2](https://arxiv.org/html/2608.04333#S2.SS0.SSS0.Px3.p1.1)\.
- Z\. Zhou, X\. Ning, K\. Hong, T\. Fu, J\. Xu, S\. Li, Y\. Lou, L\. Wang, Z\. Yuan, X\. Li, S\. Yan, G\. Dai, X\. Zhang, Y\. Dong, and Y\. Wang \(2024\)A survey on efficient inference for large language models\.External Links:2404\.14294,[Link](https://arxiv.org/abs/2404.14294)Cited by:[§1](https://arxiv.org/html/2608.04333#S1.p1.1)\.

## Appendix AAdditional Experimental Details and Results

### Experimental Details

This subsection provides the preprocessing, replay construction, budget selection, and hyperparameter details used to produce the experimental results in the main paper and the supplementary material\.

We split the 1,000 instances once into 200 profiling and 800 evaluation instances\. The profiling split determines the latency percentiles\(τ5,τ95\)\(\\tau\_\{5\},\\tau\_\{95\}\), the maximum token costcmaxc\_\{\\max\}, and the deterministic arm costcic\_\{i\}, defined as the profiling mean token count\. For configurationiiand evaluation instanceqq, a pull returns binary accuracy, token costci,qc\_\{i,q\}, and normalized inverse latency

ri,qeff=clip⁡\(ti,q−1−τ95−1τ5−1−τ95−1,0,1\)\.r^\{\\rm eff\}\_\{i,q\}=\\operatorname\{clip\}\\\!\\left\(\\frac\{t\_\{i,q\}^\{\-1\}\-\\tau\_\{95\}^\{\-1\}\}\{\\tau\_\{5\}^\{\-1\}\-\\tau\_\{95\}^\{\-1\}\},0,1\\right\)\.Online methods internally usec~i,q=ci,q/cmax\\widetilde\{c\}\_\{i,q\}=c\_\{i,q\}/c\_\{\\max\}, while figures report actual token budgets\. Feedback is generated by arm\-wise bootstrap sampling from the evaluation split, with a shared pre\-generated stream for all methods in each repetition\.

We parameterize budget byρ=B/\(K​c¯\)\\rho=B/\(K\\bar\{c\}\)\. Online experiments useρ∈\{2,4,8,16,32\}\\rho\\in\\\{2,4,8,16,32\\\}and 100 paired replays\. Their reward and cost confidence radii are

βi,tr=sr​α​log⁡\(TB\)/ni,t,βi,tc=sc​α​log⁡\(TB\)/ni,t,\\beta^\{r\}\_\{i,t\}=s\_\{r\}\\sqrt\{\\alpha\\log\(T\_\{B\}\)/n\_\{i,t\}\},\\qquad\\beta^\{c\}\_\{i,t\}=s\_\{c\}\\sqrt\{\\alpha\\log\(T\_\{B\}\)/n\_\{i,t\}\},withninit=max⁡\{1,⌊η​ρ⌋\}n\_\{\\rm init\}=\\max\\\{1,\\lfloor\\eta\\rho\\rfloor\\\}\. Profiling\-only selection uses

sr\\displaystyle s\_\{r\}∈\{0\.003,0\.01,0\.03,0\.1\},\\displaystyle\\in\\\{003,01,03,1\\\},sc\\displaystyle s\_\{c\}∈\{0\.001,0\.003,0\.01\},\\displaystyle\\in\\\{001,003,01\\\},η\\displaystyle\\eta∈\{0\.05,0\.1\},\\displaystyle\\in\\\{05,1\\\},and selects\(sr,sc,η\)=\(0\.01,0\.01,0\.05\)\(s\_\{r\},s\_\{c\},\\eta\)=\(0\.01,0\.01,0\.05\)on both datasets\. Feasible selection uses the profiling mean cost to avoid exceeding the remaining budget\.

The 14\-arm identification subset is formed outcome\-independently from GPT\-2, CodeLlama\-7B, Tulu\-7B, Tulu\-2\-7B, Gemma\-7B, LLaMA\-7B, and Mistral\-7B at temperatures 0\.5 and 1\.0, with generation length 128 and direct prompting\. Its minimum population gaps are 0\.005 on GSM8K and 0\.010 on PIQA\. We useρ∈\{20,50,100,200,500,1000,2000,5000\}\\rho\\in\\\{20,50,100,200,500,1000,2000,5000\\\}and 500 paired repetitions\. Gap ties use relative tolerance10−1010^\{\-10\}and absolute tolerance10−1210^\{\-12\}\. Complete\-set experiments useρ∈\{10,20,50,100,200\}\\rho\\in\\\{10,20,50,100,200\\\}and 100 repetitions\. The stochastic\-cost robustness comparison also uses 500 paired repetitions for each method and budget\.

#### Supplementary evaluation metrics\.

For an online trajectory, letΔis=νi⋆−νis\\Delta\_\{i\_\{s\}\}=\\nu\_\{i^\{\\star\}\}\-\\nu\_\{i\_\{s\}\}be the hypervolume\-efficiency gap incurred at pullss\. The moving\-average per\-pull regret at pulltt, with window lengthww, is

Δ¯t\(w\)=1min⁡\{w,t\}​∑s=max⁡\{1,t−w\+1\}tΔis\.\\overline\{\\Delta\}\_\{t\}^\{\(w\)\}=\\frac\{1\}\{\\min\\\{w,t\\\}\}\\sum\_\{s=\\max\\\{1,t\-w\+1\\\}\}^\{t\}\\Delta\_\{i\_\{s\}\}\.We usew=50w=50\. Unlike cumulative regret, this metric measures recent decision quality and is not mechanically increasing with the number of pulls\.

For full\-set Pareto recovery, let𝒫^B\\widehat\{\\mathcal\{P\}\}\_\{B\}be the estimated Pareto set and𝒫⋆\\mathcal\{P\}^\{\\star\}the true set\. We report their F1 score,

F1=2​\|𝒫^B∩𝒫⋆\|\|𝒫^B\|\+\|𝒫⋆\|,\\operatorname\{F1\}=\\frac\{2\\left\|\\widehat\{\\mathcal\{P\}\}\_\{B\}\\cap\\mathcal\{P\}^\{\\star\}\\right\|\}\{\\left\|\\widehat\{\\mathcal\{P\}\}\_\{B\}\\right\|\+\\left\|\\mathcal\{P\}^\{\\star\}\\right\|\},which is the harmonic mean of Pareto precision and Pareto recall\. It equals one only under exact recovery and provides a graded measure when ties or very small gaps make exact identification difficult\.

### Additional Experimental Results

This subsection complements the main results with standard hypervolume regret, within\-run online trajectories, full\-set approximate Pareto recovery, and robustness to stochastic token costs\.

![Refer to caption](https://arxiv.org/html/2608.04333v1/x3.png)Figure 3:Standard hypervolume regret versus actual token budget\.#### Standard hypervolume regret\.

Figure[3](https://arxiv.org/html/2608.04333#A1.F3)complements the efficiency\-regret result in the main paper with the standard budgeted metric\. Across all five budgets and both datasets,CoHV\-UCBattains the lowest mean standard regret among the four methods\. Its advantage becomes most pronounced on PIQA as the budget increases\. Atρ=32\\rho=32, the regrets ofCoHV\-UCB,HV\-UCB,Accuracy\-Cost\-UCB, and uniform allocation are 161\.07, 447\.35, 241\.79, and 1517\.77, respectively\. Thus,CoHV\-UCBreduces standard regret by 64\.0% relative toHV\-UCB, by 33\.4% relative toAccuracy\-Cost\-UCB, and by 89\.4% relative to uniform allocation\. These comparisons separately demonstrate the value of accounting for token cost, retaining the efficiency objective, and adapting the allocation to observed rewards\.

The corresponding GSM8K regrets atρ=32\\rho=32are 29\.01, 30\.62, 63\.75, and 87\.69\. The difference between the two hypervolume UCB methods is smaller because the highest hypervolume arm is also highly competitive in hypervolume per cost on this dataset\. Nevertheless,CoHV\-UCBremains best and reduces regret by 54\.5% relative toAccuracy\-Cost\-UCBand by 66\.9% relative to uniform allocation\. The results therefore show that cost aware multi\-objective selection improves not only the efficiency\-normalized criterion used to construct the index, but also the cumulative hypervolume collected under the same token budget\.

![Refer to caption](https://arxiv.org/html/2608.04333v1/x4.png)Figure 4:Online decision trajectories at the fixed budgetρ=32\\rho=32\. Shaded regions are 95% confidence intervals over 100 paired replays\. The moving\-average panels use the most recent 50 pulls\. All horizontal axes report consumed tokens\.
#### Online decision trajectories\.

To expose performance during the decision process rather than only at the stopping budget, Figure[4](https://arxiv.org/html/2608.04333#A1.F4)fixesρ=32\\rho=32and records each method after every pull\. Curves are aligned by consumed tokens, so the methods are compared at equal resource expenditure even when they complete different numbers of evaluations\. The left column reports cumulative hypervolume\-efficiency regret, while the right column reports the moving average of the per\-pull efficiency gap over the most recent 50 decisions\.

On PIQA, the separation emerges early and persists throughout most of the trajectory\. At the end of the displayed budget,CoHV\-UCBhas cumulative regret 1149\.32, compared with 2179\.81 forHV\-UCB, 1495\.65 forAccuracy\-Cost\-UCB, and 6544\.07 for uniform allocation\. Its final moving\-average per\-pull regret is 0\.156, approximately one third of the 0\.455 value ofHV\-UCBand about one tenth of the 1\.466 value of uniform allocation\. It is also comparable to the 0\.157 value ofAccuracy\-Cost\-UCB, while achieving substantially smaller cumulative regret\. This indicates thatCoHV\-UCBcombines strong recent decisions with better performance over the full trajectory\.

The GSM8K trajectories exhibit the same ordering against the single\-objective and nonadaptive baselines\. The final cumulative regret ofCoHV\-UCBis 59\.85, versus 118\.04 forAccuracy\-Cost\-UCBand 169\.55 for uniform allocation\. The corresponding moving\-average values are 0\.0148, 0\.0334, and 0\.0502\.CoHV\-UCBandHV\-UCBremain close, with the latter ending at cumulative regret 61\.81 and moving\-average regret 0\.0156, which agrees with the limited cost dispersion discussed in the main paper\. Although the moving averages do not monotonically converge to zero,CoHV\-UCBconsistently avoids the much larger recent losses incurred by accuracy\-only and uniform selection\.

![Refer to caption](https://arxiv.org/html/2608.04333v1/x5.png)Figure 5:Pareto F1 on all 108/132 configurations, where ties make exact identification uninformative\.
#### Approximate recovery on the complete configuration sets\.

The complete GSM8K and PIQA sets contain ties and gaps near zero, making exact identification uninformative at the available sample size\. Figure[5](https://arxiv.org/html/2608.04333#A1.F5)therefore reports Pareto F1 on all 108 and 132 configurations\.CoPSIoutperforms uniform allocation at every reported budget on both datasets\. The advantage is already visible atρ=10\\rho=10: the F1 scores are 0\.323 versus 0\.265 on GSM8K and 0\.250 versus 0\.148 on PIQA\. Hence adaptive elimination is useful even when the budget is too small for accurate recovery of the full front\.

As the budget increases toρ=200\\rho=200,CoPSIreaches 0\.727 on GSM8K and 0\.486 on PIQA, whereas uniform allocation reaches only 0\.677 and 0\.409\. These improvements correspond to absolute F1 gains of 0\.050 and 0\.077, respectively\. The larger relative gain on PIQA, 18\.7%, is particularly notable because PIQA contains more arms and a denser set of near\-boundary configurations\. By rejecting configurations whose status is already clear,CoPSIreserves more evaluations for the ambiguous part of the front\.

CoPSIand the cost\-insensitivePSI\-SRbaseline are closer, as expected from the moderate cost dispersion in these data\. Their F1 values atρ=200\\rho=200are 0\.727 and 0\.732 on GSM8K and 0\.486 and 0\.480 on PIQA\. Across the complete budget range, neither method uniformly dominates the other, but both consistently improve over uniform allocation\. The important observation is that incorporating configuration\-dependent costs preserves the statistical benefit of successive elimination while making the allocation compatible with a token budget\.

#### Robustness to stochastic token costs\.

The theorem\-aligned results charge the fixed profiling meancic\_\{i\}on every pull\. In the robustness setting, all three methods are instead charged the realized costci,qc\_\{i,q\}\.CoPSIcontinues to use the profiling estimatecic\_\{i\}in its cost\-aware allocation,PSI\-SRretains its cost\-insensitive allocation, and uniform allocation adds only complete sampling rounds so that every arm receives the same number of observations\. All methods use the same pre\-generated feedback stream within each repetition\.

![Refer to caption](https://arxiv.org/html/2608.04333v1/x6.png)Figure 6:Pareto identification error atρ=5000\\rho=5000under deterministic and stochastic token costs over 500 paired repetitions\. Values above the bars are empirical error probabilities\.Figure[6](https://arxiv.org/html/2608.04333#A1.F6)shows that realized token variability causes no material degradation for any method\. On GSM8K, the deterministic and stochastic errors are both 0\.004 forCoPSIand both 0\.006 forPSI\-SR; uniform allocation changes only from 0\.026 to 0\.028\. On PIQA, the corresponding values are 0\.148 in both settings forCoPSI, 0\.164 forPSI\-SR, and 0\.270 versus 0\.266 for uniform allocation\. The paired replay therefore indicates that replacing fixed costs by realized token charges has negligible influence at this budget\. This occurs because the phase\-wise sampling targets of both elimination methods are still computed from profiling costs\. At the large evaluation budget, realized token fluctuations average out over many pulls and do not activate the budget stopping rule before these targets are reached\. Consequently, the two cost settings usually evaluate the same feedback samples and return the same Pareto estimate\. Uniform allocation shows a small difference because its number of complete sampling rounds is determined directly by the realized costs\.

Under stochastic costs,CoPSIretains the lowest error on both datasets\. On GSM8K, its error of 0\.004 is 33\.3% below the 0\.006 error ofPSI\-SRand 85\.7% below the 0\.028 error of uniform allocation\. On PIQA, its error of 0\.148 is 9\.8% belowPSI\-SRand 44\.4% below uniform allocation\. These results support using profiling means for cost\-aware allocation when the exact token charge of an individual evaluation is unknown in advance\.

## Appendix BProof of Theorem[1](https://arxiv.org/html/2608.04333#Thmthm1)

###### Lemma 1\(Optimal benchmark upper bound\)

Consider the budgeted multi\-objective bandit problem where pulling armiiincurs a random costci,t∈\[λ,1\]c\_\{i,t\}\\in\[\\lambda,1\]with meanμic\\mu\_\{i\}^\{c\}and yields a scalar hypervolume utility

Hi=HV⁡\(\{𝝁i\}\)\.H\_\{i\}=\\operatorname\{HV\}\(\\\{\\bm\{\\mu\}\_\{i\}\\\}\)\.Let

i⋆=arg⁡maxi∈\[K\]⁡Hiμic,νi⋆=Hi⋆μi⋆c\.i^\{\\star\}=\\arg\\max\_\{i\\in\[K\]\}\\frac\{H\_\{i\}\}\{\\mu\_\{i\}^\{c\}\},\\qquad\\nu\_\{i^\{\\star\}\}=\\frac\{H\_\{i^\{\\star\}\}\}\{\\mu\_\{i^\{\\star\}\}^\{c\}\}\.Assume that the cost samples of each arm are i\.i\.d\. across pulls and that, conditional on the history and the selected arm, the next cost has meanμic\\mu\_\{i\}^\{c\}\. A policy may include the boundary pull that first exhausts the budget\. Then the optimal expected total hypervolume utility under budgetBBsatisfies

𝔼​\[∑t=1T​\(B\)HIt\]≤νi⋆​\(B\+1\)\.\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\(B\)\}H\_\{I\_\{t\}\}\\right\]\\leq\\nu\_\{i^\{\\star\}\}\(B\+1\)\.

#### Proof\.

LetItI\_\{t\}denote the arm selected at pulltt, letT​\(B\)T\(B\)be its number of pulls, and define

Ni​\(B\)=∑t=1T​\(B\)𝕀​\{It=i\}\.N\_\{i\}\(B\)=\\sum\_\{t=1\}^\{T\(B\)\}\\mathbb\{I\}\\\{I\_\{t\}=i\\\}\.By the definition ofi⋆i^\{\\star\}, every arm satisfies

Hi≤νi⋆​μic\.H\_\{i\}\\leq\\nu\_\{i^\{\\star\}\}\\mu\_\{i\}^\{c\}\.Consequently, the expected utility is bounded as

𝔼​\[∑t=1T​\(B\)HIt\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\(B\)\}H\_\{I\_\{t\}\}\\right\]=∑i=1KHi​𝔼​\[Ni​\(B\)\]\\displaystyle=\\sum\_\{i=1\}^\{K\}H\_\{i\}\\,\\mathbb\{E\}\[N\_\{i\}\(B\)\]≤νi⋆​∑i=1Kμic​𝔼​\[Ni​\(B\)\]\.\\displaystyle\\leq\\nu\_\{i^\{\\star\}\}\\sum\_\{i=1\}^\{K\}\\mu\_\{i\}^\{c\}\\,\\mathbb\{E\}\[N\_\{i\}\(B\)\]\.SinceItI\_\{t\}is measurable with respect to the history before pullttand the next cost has conditional meanμItc\\mu\_\{I\_\{t\}\}^\{c\}, the tower property gives

∑i=1Kμic​𝔼​\[Ni​\(B\)\]=𝔼​\[∑t=1T​\(B\)cIt,t\]\.\\sum\_\{i=1\}^\{K\}\\mu\_\{i\}^\{c\}\\,\\mathbb\{E\}\[N\_\{i\}\(B\)\]=\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\(B\)\}c\_\{I\_\{t\},t\}\\right\]\.Immediately before the last pull, the cumulative cost is at mostBB\. Because every pull costs at most one, including the boundary pull yields

∑t=1T​\(B\)cIt,t≤B\+1\\sum\_\{t=1\}^\{T\(B\)\}c\_\{I\_\{t\},t\}\\leq B\+1almost surely\. Thus every admissible policy satisfies

𝔼​\[∑t=1T​\(B\)HIt\]≤νi⋆​\(B\+1\)\.\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\(B\)\}H\_\{I\_\{t\}\}\\right\]\\leq\\nu\_\{i^\{\\star\}\}\(B\+1\)\.Taking the supremum over all admissible policies proves the claim\.□\\square

#### Proof of Theorem[1](https://arxiv.org/html/2608.04333#Thmthm1)\.

The proof consists of four steps\.

Step 1: A uniform concentration event\.For each armii, objectivedd, and sample sizess, letμ^i,s\(d\)\\hat\{\\mu\}\_\{i,s\}^\{\(d\)\}denote the empirical mean of the firstssobserved samples of thedd\-th objective of armii\. Similarly, letμ^i,sc\\hat\{\\mu\}\_\{i,s\}^\{c\}denote the empirical mean of the firstsscost samples of armii\.

Define the good event

ℰ=\{\|μ^i,s\(d\)−μi\(d\)\|≤α​log⁡TBs,∀i∈\[K\],d∈\[D\],s≤TB,\|μ^i,sc−μic\|≤α​log⁡TBs,∀i∈\[K\],s≤TB\}\.\\mathcal\{E\}=\\left\\\{\\begin\{aligned\} &\|\\hat\{\\mu\}\_\{i,s\}^\{\(d\)\}\-\\mu\_\{i\}^\{\(d\)\}\|\\leq\\sqrt\{\\frac\{\\alpha\\log T\_\{B\}\}\{s\}\},\\quad\\forall i\\in\[K\],\\ d\\in\[D\],\\ s\\leq T\_\{B\},\\\\ &\|\\hat\{\\mu\}\_\{i,s\}^\{c\}\-\\mu\_\{i\}^\{c\}\|\\leq\\sqrt\{\\frac\{\\alpha\\log T\_\{B\}\}\{s\}\},\\quad\\forall i\\in\[K\],\\ s\\leq T\_\{B\}\\end\{aligned\}\\right\\\}\.Since rewards and costs are bounded in\[0,1\]\[0,1\], Hoeffding’s inequality gives, for any fixedi,d,si,d,s,

Pr​\(\|μ^i,s\(d\)−μi\(d\)\|\>α​log⁡TBs\)≤2​TB−2​α\.\\mathrm\{Pr\}\\left\(\|\\hat\{\\mu\}\_\{i,s\}^\{\(d\)\}\-\\mu\_\{i\}^\{\(d\)\}\|\>\\sqrt\{\\frac\{\\alpha\\log T\_\{B\}\}\{s\}\}\\right\)\\leq 2T\_\{B\}^\{\-2\\alpha\}\.The same bound holds for the empirical cost mean\. Taking a union bound over all arms, all objectives, the cost coordinate, and all sample sizess≤TBs\\leq T\_\{B\}, we obtain

Pr​\(ℰc\)≤2​K​\(D\+1\)​TB⋅TB−2​α=2​K​\(D\+1\)​TB1−2​α\.\\mathrm\{Pr\}\(\\mathcal\{E\}^\{c\}\)\\leq 2K\(D\+1\)T\_\{B\}\\cdot T\_\{B\}^\{\-2\\alpha\}=2K\(D\+1\)T\_\{B\}^\{1\-2\\alpha\}\.Because each pull costs at leastλ\\lambda, the total number of pulls before the budget is exhausted is at mostTBT\_\{B\}\. Hence the contribution of the failure event to the expected number of pulls of any fixed arm is at most

TB​Pr​\(ℰc\)≤2​K​\(D\+1\)​TB2−2​α\.T\_\{B\}\\mathrm\{Pr\}\(\\mathcal\{E\}^\{c\}\)\\leq 2K\(D\+1\)T\_\{B\}^\{2\-2\\alpha\}\.
Step 2: Optimism of the optimal arm\.On the eventℰ\\mathcal\{E\}, for any armiiand any timet≤TBt\\leq T\_\{B\}, we have

μi\(d\)≤r¯i,t\(d\)\+βi,t,d=1,…,D\.\\mu\_\{i\}^\{\(d\)\}\\leq\\bar\{r\}\_\{i,t\}^\{\(d\)\}\+\\beta\_\{i,t\},\\qquad d=1,\\ldots,D\.Sinceμi\(d\)≤1\\mu\_\{i\}^\{\(d\)\}\\leq 1, the clipping in the definition ofUi,t\(d\)U\_\{i,t\}^\{\(d\)\}preserves the inequality

μi\(d\)≤Ui,t\(d\)\.\\mu\_\{i\}^\{\(d\)\}\\leq U\_\{i,t\}^\{\(d\)\}\.Therefore, by the coordinate\-wise monotonicity of hypervolume,

H​\(𝝁i\)≤H​\(𝐔i,t\)\.H\(\\bm\{\\mu\}\_\{i\}\)\\leq H\(\\mathbf\{U\}\_\{i,t\}\)\.Moreover, onℰ\\mathcal\{E\},

c¯i,t−βi,t≤μic\.\\bar\{c\}\_\{i,t\}\-\\beta\_\{i,t\}\\leq\\mu\_\{i\}^\{c\}\.Sinceλ/2≤μic\\lambda/2\\leq\\mu\_\{i\}^\{c\}, we also have

c¯i,t=max⁡\{λ2,c¯i,t−βi,t\}≤μic\.\\underline\{c\}\_\{i,t\}=\\max\\left\\\{\\frac\{\\lambda\}\{2\},\\bar\{c\}\_\{i,t\}\-\\beta\_\{i,t\}\\right\\\}\\leq\\mu\_\{i\}^\{c\}\.Applying these inequalities to the optimal armi⋆i^\{\\star\}gives

Di⋆,t=H​\(𝐔i⋆,t\)c¯i⋆,t≥H​\(𝝁i⋆\)μi⋆c=νi⋆\.D\_\{i^\{\\star\},t\}=\\frac\{H\(\\mathbf\{U\}\_\{i^\{\\star\},t\}\)\}\{\\underline\{c\}\_\{i^\{\\star\},t\}\}\\geq\\frac\{H\(\\bm\{\\mu\}\_\{i^\{\\star\}\}\)\}\{\\mu\_\{i^\{\\star\}\}^\{c\}\}=\\nu\_\{i^\{\\star\}\}\.Thus, on the good event, the index of the optimal arm is optimistic\.

Step 3: Upper bounding the index of a suboptimal arm\.Fix a suboptimal armi≠i⋆i\\neq i^\{\\star\}\. We show that once armiihas been pulled sufficiently many times, its index is smaller than the index of the optimal arm on the good event\.

Onℰ\\mathcal\{E\}, for every coordinatedd,

Ui,t\(d\)=min⁡\{1,r¯i,t\(d\)\+βi,t\}≤μi\(d\)\+2​βi,t\.U\_\{i,t\}^\{\(d\)\}=\\min\\\{1,\\bar\{r\}\_\{i,t\}^\{\(d\)\}\+\\beta\_\{i,t\}\\\}\\leq\\mu\_\{i\}^\{\(d\)\}\+2\\beta\_\{i,t\}\.Therefore,

‖𝐔i,t−𝝁i‖∞≤2​βi,t\.\\\|\\mathbf\{U\}\_\{i,t\}\-\\bm\{\\mu\}\_\{i\}\\\|\_\{\\infty\}\\leq 2\\beta\_\{i,t\}\.By the Lipschitz continuity ofHH,

H​\(𝐔i,t\)−H​\(𝝁i\)≤2​D​βi,t\.H\(\\mathbf\{U\}\_\{i,t\}\)\-H\(\\bm\{\\mu\}\_\{i\}\)\\leq 2D\\beta\_\{i,t\}\.For the denominator, onℰ\\mathcal\{E\},

c¯i,t≥μic−βi,t,\\bar\{c\}\_\{i,t\}\\geq\\mu\_\{i\}^\{c\}\-\\beta\_\{i,t\},and hence

c¯i,t−βi,t≥μic−2​βi,t\.\\bar\{c\}\_\{i,t\}\-\\beta\_\{i,t\}\\geq\\mu\_\{i\}^\{c\}\-2\\beta\_\{i,t\}\.Since

c¯i,t=max⁡\{λ2,c¯i,t−βi,t\},\\underline\{c\}\_\{i,t\}=\\max\\left\\\{\\frac\{\\lambda\}\{2\},\\bar\{c\}\_\{i,t\}\-\\beta\_\{i,t\}\\right\\\},we always have

c¯i,t≥λ2,\\underline\{c\}\_\{i,t\}\\geq\\frac\{\\lambda\}\{2\},and also

c¯i,t≥μic−2​βi,t\.\\underline\{c\}\_\{i,t\}\\geq\\mu\_\{i\}^\{c\}\-2\\beta\_\{i,t\}\.The latter inequality implies

μic−c¯i,t≤2​βi,t\.\\mu\_\{i\}^\{c\}\-\\underline\{c\}\_\{i,t\}\\leq 2\\beta\_\{i,t\}\.
Now consider

Ii,t−νi=H​\(𝐔i,t\)c¯i,t−H​\(𝝁i\)μic\.I\_\{i,t\}\-\\nu\_\{i\}=\\frac\{H\(\\mathbf\{U\}\_\{i,t\}\)\}\{\\underline\{c\}\_\{i,t\}\}\-\\frac\{H\(\\bm\{\\mu\}\_\{i\}\)\}\{\\mu\_\{i\}^\{c\}\}\.Adding and subtracting

H​\(𝝁i\)c¯i,t,\\frac\{H\(\\bm\{\\mu\}\_\{i\}\)\}\{\\underline\{c\}\_\{i,t\}\},we obtain

Ii,t−νi\\displaystyle I\_\{i,t\}\-\\nu\_\{i\}=H​\(𝐔i,t\)−H​\(𝝁i\)c¯i,t\+H​\(𝝁i\)​\(1c¯i,t−1μic\)\\displaystyle=\\frac\{H\(\\mathbf\{U\}\_\{i,t\}\)\-H\(\\bm\{\\mu\}\_\{i\}\)\}\{\\underline\{c\}\_\{i,t\}\}\+H\(\\bm\{\\mu\}\_\{i\}\)\\left\(\\frac\{1\}\{\\underline\{c\}\_\{i,t\}\}\-\\frac\{1\}\{\\mu\_\{i\}^\{c\}\}\\right\)=H​\(𝐔i,t\)−H​\(𝝁i\)c¯i,t\+H​\(𝝁i\)​\(μic−c¯i,t\)c¯i,t​μic\.\\displaystyle=\\frac\{H\(\\mathbf\{U\}\_\{i,t\}\)\-H\(\\bm\{\\mu\}\_\{i\}\)\}\{\\underline\{c\}\_\{i,t\}\}\+\\frac\{H\(\\bm\{\\mu\}\_\{i\}\)\(\\mu\_\{i\}^\{c\}\-\\underline\{c\}\_\{i,t\}\)\}\{\\underline\{c\}\_\{i,t\}\\mu\_\{i\}^\{c\}\}\.Using

c¯i,t≥λ2,μic≥λ,\\underline\{c\}\_\{i,t\}\\geq\\frac\{\\lambda\}\{2\},\\qquad\\mu\_\{i\}^\{c\}\\geq\\lambda,together with

H​\(𝐔i,t\)−H​\(𝝁i\)≤2​D​βi,t,H\(\\mathbf\{U\}\_\{i,t\}\)\-H\(\\bm\{\\mu\}\_\{i\}\)\\leq 2D\\beta\_\{i,t\},H​\(𝝁i\)≤1,H\(\\bm\{\\mu\}\_\{i\}\)\\leq 1,and

μic−c¯i,t≤2​βi,t,\\mu\_\{i\}^\{c\}\-\\underline\{c\}\_\{i,t\}\\leq 2\\beta\_\{i,t\},we get

Ii,t−νi\\displaystyle I\_\{i,t\}\-\\nu\_\{i\}≤2​D​βi,tλ/2\+2​βi,t\(λ/2\)​λ\\displaystyle\\leq\\frac\{2D\\beta\_\{i,t\}\}\{\\lambda/2\}\+\\frac\{2\\beta\_\{i,t\}\}\{\(\\lambda/2\)\\lambda\}=\(4​Dλ\+4λ2\)​βi,t\.\\displaystyle=\\left\(\\frac\{4D\}\{\\lambda\}\+\\frac\{4\}\{\\lambda^\{2\}\}\\right\)\\beta\_\{i,t\}\.Define

Cλ,H=4​Dλ\+4λ2\.C\_\{\\lambda,H\}=\\frac\{4D\}\{\\lambda\}\+\\frac\{4\}\{\\lambda^\{2\}\}\.Then

Ii,t≤νi\+Cλ,H​βi,t\.I\_\{i,t\}\\leq\\nu\_\{i\}\+C\_\{\\lambda,H\}\\beta\_\{i,t\}\.
Step 4: Bounding the number of pulls of a suboptimal arm\.Suppose armi≠i⋆i\\neq i^\{\\star\}is selected at roundtton the eventℰ\\mathcal\{E\}\. Since the algorithm chooses the arm with the largest index,

Ii,t≥Ii⋆,t\.I\_\{i,t\}\\geq I\_\{i^\{\\star\},t\}\.Meanwhile,

Ii⋆,t≥νi⋆,Ii,t≤νi\+Cλ,H​βi,t\.I\_\{i^\{\\star\},t\}\\geq\\nu\_\{i^\{\\star\}\},\\quad I\_\{i,t\}\\leq\\nu\_\{i\}\+C\_\{\\lambda,H\}\\beta\_\{i,t\}\.Therefore, if armiiis selected onℰ\\mathcal\{E\}, it must hold that

νi\+Cλ,H​βi,t≥νi⋆\.\\nu\_\{i\}\+C\_\{\\lambda,H\}\\beta\_\{i,t\}\\geq\\nu\_\{i^\{\\star\}\}\.Equivalently,

Cλ,H​βi,t≥Δi\.C\_\{\\lambda,H\}\\beta\_\{i,t\}\\geq\\Delta\_\{i\}\.For convenience, it is enough to require the stronger condition

Cλ,H​βi,t≤Δi2,C\_\{\\lambda,H\}\\beta\_\{i,t\}\\leq\\frac\{\\Delta\_\{i\}\}\{2\},under which armiicannot be selected\.

Since

βi,t=α​log⁡TBni,t,\\beta\_\{i,t\}=\\sqrt\{\\frac\{\\alpha\\log T\_\{B\}\}\{n\_\{i,t\}\}\},the condition

Cλ,H​βi,t≤Δi2C\_\{\\lambda,H\}\\beta\_\{i,t\}\\leq\\frac\{\\Delta\_\{i\}\}\{2\}is guaranteed whenever

ni,t≥4​α​Cλ,H2​log⁡TBΔi2\.n\_\{i,t\}\\geq\\frac\{4\\alpha C\_\{\\lambda,H\}^\{2\}\\log T\_\{B\}\}\{\\Delta\_\{i\}^\{2\}\}\.Therefore, define

Ni=⌈4​α​Cλ,H2​log⁡TBΔi2⌉\.N\_\{i\}=\\left\\lceil\\frac\{4\\alpha C\_\{\\lambda,H\}^\{2\}\\log T\_\{B\}\}\{\\Delta\_\{i\}^\{2\}\}\\right\\rceil\.On the eventℰ\\mathcal\{E\}, after armiihas been pulled at leastNiN\_\{i\}times, it cannot be selected again\. Thus,

ni​\(B\)≤1\+Nin\_\{i\}\(B\)\\leq 1\+N\_\{i\}onℰ\\mathcal\{E\}, where the additional11accounts for the possible boundary pull\.

On the complement eventℰc\\mathcal\{E\}^\{c\}, the number of pulls is at mostTBT\_\{B\}\. Therefore,

E​\[ni​\(B\)\]\\displaystyle\\mathrm\{E\}\[n\_\{i\}\(B\)\]≤\(1\+Ni\)​Pr​\(ℰ\)\+TB​Pr​\(ℰc\)\\displaystyle\\leq\(1\+N\_\{i\}\)\\mathrm\{Pr\}\(\\mathcal\{E\}\)\+T\_\{B\}\\mathrm\{Pr\}\(\\mathcal\{E\}^\{c\}\)≤1\+Ni\+2​K​\(D\+1\)​TB2−2​α\.\\displaystyle\\leq 1\+N\_\{i\}\+2K\(D\+1\)T\_\{B\}^\{2\-2\\alpha\}\.Substituting the definition ofNiN\_\{i\}proves the pull\-count bound\.

Finally, by the definition of hypervolume\-efficiency regret,

RBHV=∑i≠i⋆Δi​E​\[ni​\(B\)\]\.R\_\{B\}^\{\\mathrm\{HV\}\}=\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\\mathrm\{E\}\[n\_\{i\}\(B\)\]\.Using the above pull\-count bound gives

RBHV=O​\(∑i≠i⋆Cλ,H2​log⁡BΔi\),R\_\{B\}^\{\\mathrm\{HV\}\}=O\\left\(\\sum\_\{i\\neq i^\{\\star\}\}\\frac\{C\_\{\\lambda,H\}^\{2\}\\log B\}\{\\Delta\_\{i\}\}\\right\),where we usedTB=O​\(B/λ\)T\_\{B\}=O\(B/\\lambda\)and treatλ\\lambdaas a problem\-dependent constant\. This completes the proof\.□\\hfill\\square

## Appendix CProof of Corollary[1](https://arxiv.org/html/2608.04333#Thmcor1)

#### Proof\.

The proof follows the standard regret decomposition for budgeted multi\-armed bandits, with the scalar reward of armiireplaced by its hypervolume utilityHiH\_\{i\}\.

First, by Lemma[1](https://arxiv.org/html/2608.04333#Thmlem1)applied with scalar reward meanHiH\_\{i\}and cost meanμic\\mu\_\{i\}^\{c\}, the optimal expected total hypervolume utility is upper bounded by

RB⋆≤Hi⋆μi⋆c​\(B\+1\)=νi⋆​\(B\+1\)\.R\_\{B\}^\{\\star\}\\leq\\frac\{H\_\{i^\{\\star\}\}\}\{\\mu\_\{i^\{\\star\}\}^\{c\}\}\(B\+1\)=\\nu\_\{i^\{\\star\}\}\(B\+1\)\.Therefore,

RBstd\\displaystyle R\_\{B\}^\{\\mathrm\{std\}\}=RB⋆−E​\[∑t=1T​\(B\)Hit\]\\displaystyle=R\_\{B\}^\{\\star\}\-\\mathrm\{E\}\\left\[\\sum\_\{t=1\}^\{T\(B\)\}H\_\{i\_\{t\}\}\\right\]≤νi⋆​\(B\+1\)−E​\[∑t=1T​\(B\)Hit\]\.\\displaystyle\\leq\\nu\_\{i^\{\\star\}\}\(B\+1\)\-\\mathrm\{E\}\\left\[\\sum\_\{t=1\}^\{T\(B\)\}H\_\{i\_\{t\}\}\\right\]\.
SinceHiH\_\{i\}is deterministic once the arm is fixed, we have

E​\[∑t=1T​\(B\)Hit\]=∑i=1KHi​E​\[ni​\(B\)\]\.\\mathrm\{E\}\\left\[\\sum\_\{t=1\}^\{T\(B\)\}H\_\{i\_\{t\}\}\\right\]=\\sum\_\{i=1\}^\{K\}H\_\{i\}\\mathrm\{E\}\[n\_\{i\}\(B\)\]\.
Next, denote by

CT​\(B\)=∑t=1T​\(B\)cit,tC\_\{T\(B\)\}=\\sum\_\{t=1\}^\{T\(B\)\}c\_\{i\_\{t\},t\}the total cost consumed before stopping\. By the definition ofT​\(B\)T\(B\),

CT​\(B\)≤B<CT​\(B\)\+1\.C\_\{T\(B\)\}\\leq B<C\_\{T\(B\)\+1\}\.Since every cost is bounded by11, the overshoot is at most one, and thus

Taking expectation and using the standard optional\-sampling identity for adaptively sampled bounded costs gives

∑i=1Kμic​E​\[ni​\(B\)\]≥B−1\.\\sum\_\{i=1\}^\{K\}\\mu\_\{i\}^\{c\}\\mathrm\{E\}\[n\_\{i\}\(B\)\]\\geq B\-1\.Equivalently,

B\+1−∑i=1Kμic​E​\[ni​\(B\)\]≤2\.B\+1\-\\sum\_\{i=1\}^\{K\}\\mu\_\{i\}^\{c\}\\mathrm\{E\}\[n\_\{i\}\(B\)\]\\leq 2\.
Using this inequality, we obtain

RBstd\\displaystyle R\_\{B\}^\{\\mathrm\{std\}\}≤νi⋆​\(B\+1\)−∑i=1KHi​E​\[ni​\(B\)\]\\displaystyle\\leq\\nu\_\{i^\{\\star\}\}\(B\+1\)\-\\sum\_\{i=1\}^\{K\}H\_\{i\}\\mathrm\{E\}\[n\_\{i\}\(B\)\]=νi⋆​\(B\+1−∑i=1Kμic​E​\[ni​\(B\)\]\)\\displaystyle=\\nu\_\{i^\{\\star\}\}\\left\(B\+1\-\\sum\_\{i=1\}^\{K\}\\mu\_\{i\}^\{c\}\\mathrm\{E\}\[n\_\{i\}\(B\)\]\\right\)\+∑i=1K\(νi⋆​μic−Hi\)​E​\[ni​\(B\)\]\\displaystyle\\quad\+\\sum\_\{i=1\}^\{K\}\\left\(\\nu\_\{i^\{\\star\}\}\\mu\_\{i\}^\{c\}\-H\_\{i\}\\right\)\\mathrm\{E\}\[n\_\{i\}\(B\)\]≤2​νi⋆\+∑i=1K\(νi⋆​μic−Hi\)​E​\[ni​\(B\)\]\.\\displaystyle\\leq 2\\nu\_\{i^\{\\star\}\}\+\\sum\_\{i=1\}^\{K\}\\left\(\\nu\_\{i^\{\\star\}\}\\mu\_\{i\}^\{c\}\-H\_\{i\}\\right\)\\mathrm\{E\}\[n\_\{i\}\(B\)\]\.For the optimal armi⋆i^\{\\star\},

νi⋆​μi⋆c−Hi⋆=0\.\\nu\_\{i^\{\\star\}\}\\mu\_\{i^\{\\star\}\}^\{c\}\-H\_\{i^\{\\star\}\}=0\.For each suboptimal armi≠i⋆i\\neq i^\{\\star\},

νi⋆​μic−Hi=μic​\(νi⋆−νi\)=μic​Δi\.\\nu\_\{i^\{\\star\}\}\\mu\_\{i\}^\{c\}\-H\_\{i\}=\\mu\_\{i\}^\{c\}\\left\(\\nu\_\{i^\{\\star\}\}\-\\nu\_\{i\}\\right\)=\\mu\_\{i\}^\{c\}\\Delta\_\{i\}\.Therefore,

RBstd≤2​νi⋆\+∑i≠i⋆μic​Δi​E​\[ni​\(B\)\]\.R\_\{B\}^\{\\mathrm\{std\}\}\\leq 2\\nu\_\{i^\{\\star\}\}\+\\sum\_\{i\\neq i^\{\\star\}\}\\mu\_\{i\}^\{c\}\\Delta\_\{i\}\\mathrm\{E\}\[n\_\{i\}\(B\)\]\.
It remains to substitute the pull\-count bound of CoHV\-UCB\. From the suboptimal\-pull analysis, for everyi≠i⋆i\\neq i^\{\\star\},

E​\[ni​\(B\)\]≤1\+⌈4​α​Cλ,H2​log⁡TBΔi2⌉\+2​K​\(D\+1\)​TB2−2​α\.\\mathrm\{E\}\[n\_\{i\}\(B\)\]\\leq 1\+\\left\\lceil\\frac\{4\\alpha C\_\{\\lambda,H\}^\{2\}\\log T\_\{B\}\}\{\\Delta\_\{i\}^\{2\}\}\\right\\rceil\+2K\(D\+1\)T\_\{B\}^\{2\-2\\alpha\}\.Substituting this inequality into the previous regret decomposition yields the stated finite\-budget bound\.

Finally, sinceμic≤1\\mu\_\{i\}^\{c\}\\leq 1, the leading term satisfies

μic​Δi⋅Cλ,H2​log⁡BΔi2=μic​Cλ,H2​log⁡BΔi≤Cλ,H2​log⁡BΔi\.\\mu\_\{i\}^\{c\}\\Delta\_\{i\}\\cdot\\frac\{C\_\{\\lambda,H\}^\{2\}\\log B\}\{\\Delta\_\{i\}^\{2\}\}=\\frac\{\\mu\_\{i\}^\{c\}C\_\{\\lambda,H\}^\{2\}\\log B\}\{\\Delta\_\{i\}\}\\leq\\frac\{C\_\{\\lambda,H\}^\{2\}\\log B\}\{\\Delta\_\{i\}\}\.This gives the big\-OOregret bound\.□\\hfill\\square

## Appendix DProof of Theorem[2](https://arxiv.org/html/2608.04333#Thmthm2)

#### Proof\.

The proof separates the deterministic classification argument from the cost\-aware sampling calculation\. The elimination rule ofCoPSIis the successive\-rejects version of Empirical Gap Elimination \(EGE\): in each phase, it removes one active arm with the largest empirical classification gap, and if several arms attain the same largest gap, an empirically dominated arm is removed whenever possible\. The only difference from standard EGE\-SR is the cost\-aware choice of the sampling targetnrn\_\{r\}\.

#### Step 1: Deterministic correctness of the elimination rule\.

We first state the deterministic implication of EGE\-SR that will be used in the proof\.

###### Lemma 2\(Deterministic correctness of EGE\-SR\)

Consider the successive\-rejects version of EGE with the empirical classification gap defined in \([1](https://arxiv.org/html/2608.04333#S4.E1)\)\. At phaserr, letkr=\|𝒜r\|k\_\{r\}=\|\\mathcal\{A\}\_\{r\}\|\. Suppose that, for every phaserrand every active pairi,j∈𝒜ri,j\\in\\mathcal\{A\}\_\{r\}, the empirical margins satisfy

\|m^r​\(i,j\)−m​\(i,j\)\|≤γ\(kr\)8,\|M^r​\(i,j\)−M​\(i,j\)\|≤γ\(kr\)8\.\\left\|\\widehat\{m\}\_\{r\}\(i,j\)\-m\(i,j\)\\right\|\\leq\\frac\{\\gamma\_\{\(k\_\{r\}\)\}\}\{8\},\\qquad\\left\|\\widehat\{M\}\_\{r\}\(i,j\)\-M\(i,j\)\\right\|\\leq\\frac\{\\gamma\_\{\(k\_\{r\}\)\}\}\{8\}\.Then every removed arm is classified correctly\. Moreover, if one arm remains active at the end of the procedure, this final surviving arm is Pareto optimal\. Hence the returned set satisfies

𝒫^B=𝒫⋆\.\\widehat\{\\mathcal\{P\}\}\_\{B\}=\\mathcal\{P\}^\{\\star\}\.

#### Proof\.

For each dominated armii, fix

i†∈arg⁡maxj∈𝒫⋆⁡m​\(i,j\)\.i^\{\\dagger\}\\in\\arg\\max\_\{j\\in\\mathcal\{P\}^\{\\star\}\}m\(i,j\)\.This choice satisfiesm​\(i,i†\)=γim\(i,i^\{\\dagger\}\)=\\gamma\_\{i\}\. Indeed, starting from any arm that dominatesii, repeatedly moving to one of its dominators must terminate at a Pareto arm, and every move can only increase the coordinate\-wise domination margin\. Hence the maximum inΔi−=maxj≠i⁡m​\(i,j\)\\Delta\_\{i\}^\{\-\}=\\max\_\{j\\neq i\}m\(i,j\)is attained by a Pareto arm\.

Fix a phaserr, writek=krk=k\_\{r\}, and letε=γ\(k\)/8\\varepsilon=\\gamma\_\{\(k\)\}/8\. We first record three deterministic consequences of the assumed pairwise error bounds\.

*Gap representation\.*For every active arm,

γ^i,r=max⁡\{Δ^i,r−,Δ^i,r\+\}\.\\widehat\{\\gamma\}\_\{i,r\}=\\max\\left\\\{\\widehat\{\\Delta\}\_\{i,r\}^\{\-\},\\widehat\{\\Delta\}\_\{i,r\}^\{\+\}\\right\\\}\.\(2\)Ifiiis empirically dominated, thenΔ^i,r−\>0\\widehat\{\\Delta\}\_\{i,r\}^\{\-\}\>0andΔ^i,r\+≤0\\widehat\{\\Delta\}\_\{i,r\}^\{\+\}\\leq 0; if it is empirically Pareto optimal, the two inequalities are reversed\. Thus \([2](https://arxiv.org/html/2608.04333#A4.E2)\) follows directly from \([1](https://arxiv.org/html/2608.04333#S4.E1)\)\.

*Lower bound on active empirical gaps\.*Suppose that every active dominated armiihas its fixed Pareto dominatori†i^\{\\dagger\}active\. Then

γ^i,r≥γi−2​ε,i∈𝒜r\.\\widehat\{\\gamma\}\_\{i,r\}\\geq\\gamma\_\{i\}\-2\\varepsilon,\\qquad i\\in\\mathcal\{A\}\_\{r\}\.\(3\)For a dominated arm,i†∈𝒜ri^\{\\dagger\}\\in\\mathcal\{A\}\_\{r\}and the pairwise error bound give

Δ^i,r−≥m^r​\(i,i†\)≥m​\(i,i†\)−ε=γi−ε\.\\widehat\{\\Delta\}\_\{i,r\}^\{\-\}\\geq\\widehat\{m\}\_\{r\}\(i,i^\{\\dagger\}\)\\geq m\(i,i^\{\\dagger\}\)\-\\varepsilon=\\gamma\_\{i\}\-\\varepsilon\.For a Pareto armii, consider any active competitorj∈𝒜r∖\{i\}j\\in\\mathcal\{A\}\_\{r\}\\setminus\\\{i\\\}\. The pairwise error bound gives

M^r​\(i,j\)≥M​\(i,j\)−ε,M^r​\(j,i\)\+≥M​\(j,i\)\+−ε\.\\widehat\{M\}\_\{r\}\(i,j\)\\geq M\(i,j\)\-\\varepsilon,\\qquad\\widehat\{M\}\_\{r\}\(j,i\)^\{\+\}\\geq M\(j,i\)^\{\+\}\-\\varepsilon\.Moreover, the invariant ensures that, wheneverjjis dominated, an arm attainingΔj−\\Delta\_\{j\}^\{\-\}remains active; ifjjis Pareto optimal, then\(Δj−\)\+=0\(\\Delta\_\{j\}^\{\-\}\)^\{\+\}=0\. In either case,

\(Δ^j,r−\)\+≥\(Δj−\)\+−ε\.\\left\(\\widehat\{\\Delta\}\_\{j,r\}^\{\-\}\\right\)^\{\+\}\\geq\\left\(\\Delta\_\{j\}^\{\-\}\\right\)^\{\+\}\-\\varepsilon\.Consequently,

M^r​\(i,j\)∧\[M^r​\(j,i\)\+\+\(Δ^j,r−\)\+\]\\displaystyle\\widehat\{M\}\_\{r\}\(i,j\)\\wedge\\left\[\\widehat\{M\}\_\{r\}\(j,i\)^\{\+\}\+\\left\(\\widehat\{\\Delta\}\_\{j,r\}^\{\-\}\\right\)^\{\+\}\\right\]≥\{M​\(i,j\)∧\[M​\(j,i\)\+\+\(Δj−\)\+\]\}−2​ε\.\\displaystyle\\qquad\\geq\\left\\\{M\(i,j\)\\wedge\\left\[M\(j,i\)^\{\+\}\+\\left\(\\Delta\_\{j\}^\{\-\}\\right\)^\{\+\}\\right\]\\right\\\}\-2\\varepsilon\.Taking the minimum over active competitors can only increase the population minimum over all competitors\. Therefore, by the definition ofΔi\+=γi\\Delta\_\{i\}^\{\+\}=\\gamma\_\{i\},

Δ^i,r\+≥γi−2​ε\.\\widehat\{\\Delta\}\_\{i,r\}^\{\+\}\\geq\\gamma\_\{i\}\-2\\varepsilon\.Equation \([3](https://arxiv.org/html/2608.04333#A4.E3)\) follows from \([2](https://arxiv.org/html/2608.04333#A4.E2)\)\.

*A missed empirical domination has a small population margin\.*Ifiiis dominated, bothiiandi†i^\{\\dagger\}are active, andi†i^\{\\dagger\}does not empirically dominateii, then

γi=m​\(i,i†\)≤ε\.\\gamma\_\{i\}=m\(i,i^\{\\dagger\}\)\\leq\\varepsilon\.\(4\)Indeed, the premise impliesm^r​\(i,i†\)≤0\\widehat\{m\}\_\{r\}\(i,i^\{\\dagger\}\)\\leq 0, and the pairwise error bound completes the claim\.

We now establish the dominator\-preservation invariant

𝒬r:i∈𝒜r∖𝒫⋆⟹i†∈𝒜r\\mathcal\{Q\}\_\{r\}:\\quad i\\in\\mathcal\{A\}\_\{r\}\\setminus\\mathcal\{P\}^\{\\star\}\\Longrightarrow i^\{\\dagger\}\\in\\mathcal\{A\}\_\{r\}\(5\)by induction over the phases\. It holds atr=1r=1because𝒜1=\[K\]\\mathcal\{A\}\_\{1\}=\[K\]\. Assume that it holds at phaserrand, for a contradiction, suppose that the selected arm iser=i†e\_\{r\}=i^\{\\dagger\}while the corresponding dominated armiiremains active\. Among thekkactive arms there exists an armaawithγa≥γ\(k\)\\gamma\_\{a\}\\geq\\gamma\_\{\(k\)\}\. By \([3](https://arxiv.org/html/2608.04333#A4.E3)\) and the maximality ofere\_\{r\},

γ^i†,r≥γ^a,r≥γ\(k\)−2​ε=6​ε\.\\widehat\{\\gamma\}\_\{i^\{\\dagger\},r\}\\geq\\widehat\{\\gamma\}\_\{a,r\}\\geq\\gamma\_\{\(k\)\}\-2\\varepsilon=6\\varepsilon\.\(6\)
Ifi†i^\{\\dagger\}is empirically dominated, its population Pareto optimality impliesm​\(i†,j\)≤0m\(i^\{\\dagger\},j\)\\leq 0for everyjj\. Henceγ^i†,r=Δ^i†,r−≤ε\\widehat\{\\gamma\}\_\{i^\{\\dagger\},r\}=\\widehat\{\\Delta\}\_\{i^\{\\dagger\},r\}^\{\-\}\\leq\\varepsilon, contradicting \([6](https://arxiv.org/html/2608.04333#A4.E6)\)\.

Suppose instead thati†i^\{\\dagger\}is empirically Pareto optimal\. It cannot empirically dominateii\. Otherwiseiiis empirically dominated and, usingiias a competitor in the minimum definingΔ^i†,r\+\\widehat\{\\Delta\}\_\{i^\{\\dagger\},r\}^\{\+\},

γ^i†,r≤M^r​\(i,i†\)\+\+\(Δ^i,r−\)\+=γ^i,r\.\\widehat\{\\gamma\}\_\{i^\{\\dagger\},r\}\\leq\\widehat\{M\}\_\{r\}\(i,i^\{\\dagger\}\)^\{\+\}\+\\left\(\\widehat\{\\Delta\}\_\{i,r\}^\{\-\}\\right\)^\{\+\}=\\widehat\{\\gamma\}\_\{i,r\}\.The inequality is either strict, in which casei†i^\{\\dagger\}cannot be selected, or it is an equality, in which case the tie rule selects the empirically dominated armii\. Both alternatives contradict the removal ofi†i^\{\\dagger\}whileiiremains\.

It follows from \([4](https://arxiv.org/html/2608.04333#A4.E4)\) thatγi≤ε\\gamma\_\{i\}\\leq\\varepsilon\. Moreover,M​\(i,i†\)=−m​\(i,i†\)=−γi≤0M\(i,i^\{\\dagger\}\)=\-m\(i,i^\{\\dagger\}\)=\-\\gamma\_\{i\}\\leq 0, and thusM^r​\(i,i†\)\+≤ε\\widehat\{M\}\_\{r\}\(i,i^\{\\dagger\}\)^\{\+\}\\leq\\varepsilon\. The uniform pairwise bound also gives

\(Δ^i,r−\)\+≤γi\+ε≤2​ε\.\\left\(\\widehat\{\\Delta\}\_\{i,r\}^\{\-\}\\right\)^\{\+\}\\leq\\gamma\_\{i\}\+\\varepsilon\\leq 2\\varepsilon\.Usingiias a competitor once more yields

γ^i†,r=Δ^i†,r\+≤3​ε,\\widehat\{\\gamma\}\_\{i^\{\\dagger\},r\}=\\widehat\{\\Delta\}\_\{i^\{\\dagger\},r\}^\{\+\}\\leq 3\\varepsilon,again contradicting \([6](https://arxiv.org/html/2608.04333#A4.E6)\)\. Therefore𝒬r\+1\\mathcal\{Q\}\_\{r\+1\}holds, and induction proves \([5](https://arxiv.org/html/2608.04333#A4.E5)\) at every phase\.

It remains to show that the arm removed at each phase is classified correctly\. The invariant and \([3](https://arxiv.org/html/2608.04333#A4.E3)\) imply, exactly as in \([6](https://arxiv.org/html/2608.04333#A4.E6)\), that

γ^er,r≥6​ε\.\\widehat\{\\gamma\}\_\{e\_\{r\},r\}\\geq 6\\varepsilon\.\(7\)Ifere\_\{r\}is empirically dominated but truly Pareto optimal, thenγ^er,r=Δ^er,r−≤ε\\widehat\{\\gamma\}\_\{e\_\{r\},r\}=\\widehat\{\\Delta\}\_\{e\_\{r\},r\}^\{\-\}\\leq\\varepsilon, a contradiction\. Ifere\_\{r\}is empirically Pareto optimal but truly dominated, its fixed dominatorer†e\_\{r\}^\{\\dagger\}is active by \([5](https://arxiv.org/html/2608.04333#A4.E5)\)\. Empirical Pareto optimality means thater†e\_\{r\}^\{\\dagger\}does not empirically dominateere\_\{r\}, so \([4](https://arxiv.org/html/2608.04333#A4.E4)\) givesγer≤ε\\gamma\_\{e\_\{r\}\}\\leq\\varepsilon\. SinceM​\(er,er†\)=−γer≤0M\(e\_\{r\},e\_\{r\}^\{\\dagger\}\)=\-\\gamma\_\{e\_\{r\}\}\\leq 0, the pairwise error bound and the first term in the minimum definingΔ^er,r\+\\widehat\{\\Delta\}\_\{e\_\{r\},r\}^\{\+\}give

γ^er,r=Δ^er,r\+≤M^r​\(er,er†\)\+≤ε,\\widehat\{\\gamma\}\_\{e\_\{r\},r\}=\\widehat\{\\Delta\}\_\{e\_\{r\},r\}^\{\+\}\\leq\\widehat\{M\}\_\{r\}\(e\_\{r\},e\_\{r\}^\{\\dagger\}\)^\{\+\}\\leq\\varepsilon,again contradicting \([7](https://arxiv.org/html/2608.04333#A4.E7)\)\. Thus every accepted arm is truly Pareto optimal and every rejected arm is truly dominated\.

AfterK−1K\-1phases, a dominated final survivor would, by \([5](https://arxiv.org/html/2608.04333#A4.E5)\), require a distinct active Pareto dominator\. This is impossible because𝒜K\\mathcal\{A\}\_\{K\}is a singleton\. The final survivor is therefore Pareto optimal, and the returned set is exactly𝒫⋆\\mathcal\{P\}^\{\\star\}\.□\\square

It remains to prove that the cost\-aware sampling schedule ensures these inequalities with high probability\.

#### Step 2: Budget feasibility\.

At phaserr,CoPSIsets

nr=⌊BLK,λ​Cr⌋,Cr=C​\(𝒜r\)=∑i∈𝒜rci\.n\_\{r\}=\\left\\lfloor\\frac\{B\}\{L\_\{K,\\lambda\}C\_\{r\}\}\\right\\rfloor,\\qquad C\_\{r\}=C\(\\mathcal\{A\}\_\{r\}\)=\\sum\_\{i\\in\\mathcal\{A\}\_\{r\}\}c\_\{i\}\.Since exactly one arm is removed in each phase and every arm has positive cost,CrC\_\{r\}is decreasing and thereforenrn\_\{r\}is nondecreasing\. The algorithm stops after phaseK−1K\-1, where the last sampled active set contains two arms; the remaining singleton𝒜K\\mathcal\{A\}\_\{K\}is returned without further sampling\. Thus, the total cost spent by the algorithm is

∑r=1K−1Cr​\(nr−nr−1\),n0=0\.\\sum\_\{r=1\}^\{K\-1\}C\_\{r\}\(n\_\{r\}\-n\_\{r\-1\}\),\\qquad n\_\{0\}=0\.By summation by parts,

∑r=1K−1Cr​\(nr−nr−1\)\\displaystyle\\sum\_\{r=1\}^\{K\-1\}C\_\{r\}\(n\_\{r\}\-n\_\{r\-1\}\)=CK−1​nK−1\+∑r=1K−2\(Cr−Cr\+1\)​nr\.\\displaystyle=C\_\{K\-1\}n\_\{K\-1\}\+\\sum\_\{r=1\}^\{K\-2\}\(C\_\{r\}\-C\_\{r\+1\}\)n\_\{r\}\.Using

nr≤BLK,λ​Cr,n\_\{r\}\\leq\\frac\{B\}\{L\_\{K,\\lambda\}C\_\{r\}\},we obtain

∑r=1K−1Cr​\(nr−nr−1\)\\displaystyle\\sum\_\{r=1\}^\{K\-1\}C\_\{r\}\(n\_\{r\}\-n\_\{r\-1\}\)≤BLK,λ\+BLK,λ​∑r=1K−2Cr−Cr\+1Cr\.\\displaystyle\\leq\\frac\{B\}\{L\_\{K,\\lambda\}\}\+\\frac\{B\}\{L\_\{K,\\lambda\}\}\\sum\_\{r=1\}^\{K\-2\}\\frac\{C\_\{r\}\-C\_\{r\+1\}\}\{C\_\{r\}\}\.At phaserr, the active set has sizekr=K−r\+1k\_\{r\}=K\-r\+1\. The removed arm has cost at most11, while the remainingkr−1k\_\{r\}\-1active arms have total cost at least\(kr−1\)​λ\(k\_\{r\}\-1\)\\lambda\. Hence

Cr−Cr\+1Cr≤11\+\(kr−1\)​λ\.\\frac\{C\_\{r\}\-C\_\{r\+1\}\}\{C\_\{r\}\}\\leq\\frac\{1\}\{1\+\(k\_\{r\}\-1\)\\lambda\}\.Therefore,

∑r=1K−1Cr​\(nr−nr−1\)\\displaystyle\\sum\_\{r=1\}^\{K\-1\}C\_\{r\}\(n\_\{r\}\-n\_\{r\-1\}\)≤BLK,λ​\(1\+∑r=1K−211\+\(kr−1\)​λ\)\\displaystyle\\leq\\frac\{B\}\{L\_\{K,\\lambda\}\}\\left\(1\+\\sum\_\{r=1\}^\{K\-2\}\\frac\{1\}\{1\+\(k\_\{r\}\-1\)\\lambda\}\\right\)≤BLK,λ​\(1\+∑ℓ=2K11\+\(ℓ−1\)​λ\)=B\.\\displaystyle\\leq\\frac\{B\}\{L\_\{K,\\lambda\}\}\\left\(1\+\\sum\_\{\\ell=2\}^\{K\}\\frac\{1\}\{1\+\(\\ell\-1\)\\lambda\}\\right\)=B\.Thus, the sampling schedule is feasible under budgetBB\.

#### Step 3: A phase\-wise lower bound on the number of samples\.

By the definition of the cost\-aware complexity,

H𝝁,c=max∅≠𝒜⊆\[K\]⁡C​\(𝒜\)γ\(\|𝒜\|\)2,H\_\{\\bm\{\\mu\},c\}=\\max\_\{\\emptyset\\neq\\mathcal\{A\}\\subseteq\[K\]\}\\frac\{C\(\\mathcal\{A\}\)\}\{\\gamma\_\{\(\|\\mathcal\{A\}\|\)\}^\{2\}\},we have, for every realized active set𝒜r\\mathcal\{A\}\_\{r\},

Cr=C​\(𝒜r\)≤H𝝁,c​γ\(kr\)2\.C\_\{r\}=C\(\\mathcal\{A\}\_\{r\}\)\\leq H\_\{\\bm\{\\mu\},c\}\\gamma\_\{\(k\_\{r\}\)\}^\{2\}\.Since rewards are bounded in\[0,1\]\[0,1\], every positive classification gap is at most one\. Hence

Cr≤H𝝁,c\.C\_\{r\}\\leq H\_\{\\bm\{\\mu\},c\}\.Under the assumption

B≥2​LK,λ​H𝝁,c,B\\geq 2L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\},we have

BLK,λ​Cr≥2\.\\frac\{B\}\{L\_\{K,\\lambda\}C\_\{r\}\}\\geq 2\.Therefore, using the elementary inequality⌊x⌋≥x/2\\lfloor x\\rfloor\\geq x/2for allx≥2x\\geq 2, we obtain

nr\\displaystyle n\_\{r\}=⌊BLK,λ​Cr⌋≥B2​LK,λ​Cr\.\\displaystyle=\\left\\lfloor\\frac\{B\}\{L\_\{K,\\lambda\}C\_\{r\}\}\\right\\rfloor\\geq\\frac\{B\}\{2L\_\{K,\\lambda\}C\_\{r\}\}\.Multiplying both sides byγ\(kr\)2\\gamma\_\{\(k\_\{r\}\)\}^\{2\}gives

nr​γ\(kr\)2≥B​γ\(kr\)22​LK,λ​Cr≥B2​LK,λ​H𝝁,c\.\\displaystyle n\_\{r\}\\gamma\_\{\(k\_\{r\}\)\}^\{2\}\\geq\\frac\{B\\gamma\_\{\(k\_\{r\}\)\}^\{2\}\}\{2L\_\{K,\\lambda\}C\_\{r\}\}\\geq\\frac\{B\}\{2L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\}\}\.\(8\)

#### Step 4: Concentration at adaptive sampling targets\.

For each armiiand coordinatedd, expose in advance an infinite i\.i\.d\. sequence of rewards with meanμi\(d\)\\mu\_\{i\}^\{\(d\)\}\. Letμ¯i,n\(d\)\\overline\{\\mu\}\_\{i,n\}^\{\(d\)\}be the empirical mean of the firstnnobservations in this sequence\. Although the active set and the targetnrn\_\{r\}are data\-dependent, the following time\-uniform Hoeffding bound remains valid:

Pr\(∃n≥N:\|μ¯i,n\(d\)−μi\(d\)\|\>x\)≤2exp\(−2Nx2\)\.\\mathrm\{Pr\}\\left\(\\exists n\\geq N:\\left\|\\overline\{\\mu\}\_\{i,n\}^\{\(d\)\}\-\\mu\_\{i\}^\{\(d\)\}\\right\|\>x\\right\)\\leq 2\\exp\(\-2Nx^\{2\}\)\.\(9\)This follows from Ville’s inequality applied to the Hoeffding exponential supermartingales for the upper and lower tails\.

For each phaserr, define the good event

ℰr=\{∀i∈𝒜r,∀d∈\[D\]:\|μ^i,r\(d\)−μi\(d\)\|≤γ\(kr\)16\},\\mathcal\{E\}\_\{r\}=\\left\\\{\\forall i\\in\\mathcal\{A\}\_\{r\},\\ \\forall d\\in\[D\]:\\left\|\\widehat\{\\mu\}\_\{i,r\}^\{\(d\)\}\-\\mu\_\{i\}^\{\(d\)\}\\right\|\\leq\\frac\{\\gamma\_\{\(k\_\{r\}\)\}\}\{16\}\\right\\\},and let

ℰ=⋂r=1K−1ℰr\.\\mathcal\{E\}=\\bigcap\_\{r=1\}^\{K\-1\}\\mathcal\{E\}\_\{r\}\.Onℰr\\mathcal\{E\}\_\{r\}, for any active pairi,j∈𝒜ri,j\\in\\mathcal\{A\}\_\{r\}, the empirical pairwise margins satisfy

\|m^r​\(i,j\)−m​\(i,j\)\|≤γ\(kr\)8,\|M^r​\(i,j\)−M​\(i,j\)\|≤γ\(kr\)8,\\left\|\\widehat\{m\}\_\{r\}\(i,j\)\-m\(i,j\)\\right\|\\leq\\frac\{\\gamma\_\{\(k\_\{r\}\)\}\}\{8\},\\qquad\\left\|\\widehat\{M\}\_\{r\}\(i,j\)\-M\(i,j\)\\right\|\\leq\\frac\{\\gamma\_\{\(k\_\{r\}\)\}\}\{8\},because each pairwise margin is a minimum or maximum of coordinate\-wise differences and each empirical mean has error at mostγ\(kr\)/16\\gamma\_\{\(k\_\{r\}\)\}/16\.

We now boundPr​\(ℰrc\)\\mathrm\{Pr\}\(\\mathcal\{E\}\_\{r\}^\{c\}\)\. By \([8](https://arxiv.org/html/2608.04333#A4.E8)\), every realized targetnrn\_\{r\}satisfies

nr≥B2​LK,λ​H𝝁,c​γ\(kr\)2\.n\_\{r\}\\geq\\frac\{B\}\{2L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\}\\gamma\_\{\(k\_\{r\}\)\}^\{2\}\}\.Applying \([9](https://arxiv.org/html/2608.04333#A4.E9)\) with

x=γ\(kr\)16,N=B2​LK,λ​H𝝁,c​γ\(kr\)2,x=\\frac\{\\gamma\_\{\(k\_\{r\}\)\}\}\{16\},\\qquad N=\\frac\{B\}\{2L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\}\\gamma\_\{\(k\_\{r\}\)\}^\{2\}\},and taking a union bound over at mostKKactive arms andDDcoordinates, we obtain

Pr​\(ℰrc\)\\displaystyle\\mathrm\{Pr\}\(\\mathcal\{E\}\_\{r\}^\{c\}\)≤2​K​D​exp⁡\(−2⋅B2​LK,λ​H𝝁,c​γ\(kr\)2⋅γ\(kr\)2162\)\\displaystyle\\leq 2KD\\exp\\left\(\-2\\cdot\\frac\{B\}\{2L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\}\\gamma\_\{\(k\_\{r\}\)\}^\{2\}\}\\cdot\\frac\{\\gamma\_\{\(k\_\{r\}\)\}^\{2\}\}\{16^\{2\}\}\\right\)=2​K​D​exp⁡\(−B256​LK,λ​H𝝁,c\)\.\\displaystyle=2KD\\exp\\left\(\-\\frac\{B\}\{256L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\}\}\\right\)\.A union bound over theK−1K\-1phases gives

Pr​\(ℰc\)\\displaystyle\\mathrm\{Pr\}\(\\mathcal\{E\}^\{c\}\)≤∑r=1K−1Pr​\(ℰrc\)\\displaystyle\\leq\\sum\_\{r=1\}^\{K\-1\}\\mathrm\{Pr\}\(\\mathcal\{E\}\_\{r\}^\{c\}\)≤2​K2​D​exp⁡\(−B256​LK,λ​H𝝁,c\)\.\\displaystyle\\leq 2K^\{2\}D\\exp\\left\(\-\\frac\{B\}\{256L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\}\}\\right\)\.

#### Step 5: Concluding the proof\.

On the eventℰ\\mathcal\{E\}, the pairwise concentration conditions of Lemma[2](https://arxiv.org/html/2608.04333#Thmlem2)hold in every phase\. Therefore, all arms removed byCoPSIare classified correctly, and the final surviving arm in𝒜K\\mathcal\{A\}\_\{K\}is Pareto optimal\. SinceCoPSIreturns

𝒫^B=𝒫^∪𝒜K,\\widehat\{\\mathcal\{P\}\}\_\{B\}=\\widehat\{\\mathcal\{P\}\}\\cup\\mathcal\{A\}\_\{K\},we have

𝒫^B=𝒫⋆\\widehat\{\\mathcal\{P\}\}\_\{B\}=\\mathcal\{P\}^\{\\star\}onℰ\\mathcal\{E\}\. Hence

Pr​\(𝒫^B≠𝒫⋆\)\\displaystyle\\mathrm\{Pr\}\\left\(\\widehat\{\\mathcal\{P\}\}\_\{B\}\\neq\\mathcal\{P\}^\{\\star\}\\right\)≤Pr​\(ℰc\)\\displaystyle\\leq\\mathrm\{Pr\}\(\\mathcal\{E\}^\{c\}\)≤2​K2​D​exp⁡\(−B256​LK,λ​H𝝁,c\)\.\\displaystyle\\leq 2K^\{2\}D\\exp\\left\(\-\\frac\{B\}\{256L\_\{K,\\lambda\}H\_\{\\bm\{\\mu\},c\}\}\\right\)\.This completes the proof\.□\\square