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

Evaluating large language model (LLM) configurations is challenging because evaluation budgets are limited, evaluation costs differ across configurations, and several objectives must be traded off simultaneously. We formulate LLM configuration evaluation as a cost-aware multi-objective bandit problem, in which each evaluation incurs a configuration-dependent cost and yields a noisy vector-valued outcome. Within this framework, we study two fundamental problems: online configuration selection and Pareto configuration identification. For online selection, we propose a hypervolume-based UCB algorithm and establish a regret bound of order $O\left({\sum }_{i\ne i^{\star }}\frac{\log B}{{\Delta }_i}\right)$, where $B$ is the evaluation budget, $i^{\star }$ is the configuration with the highest hypervolume per unit cost, and ${\Delta }_i$ is the efficiency gap of configuration $i$. 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 order $O(\exp (-\frac{B}{H_{\mathbf{\mu },c}}))$, where $H_{\mathbf{\mu },c}$ is a cost-aware complexity that depends on the configuration costs and the Pareto classification gaps. This rate decays exponentially in the budget and recovers the standard Pareto set identification guarantee when all costs are identical. Experiments on real LLM configuration data and synthetic instances demonstrate the benefit of cost-aware allocation.