# Few-for-Many Best-Arm Identification in Multi-Objective Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 43 references that are in the map.
- First posted on arXiv 12 Oct 2026.

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

- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations](https://mlsanity.com/paper/1805.12168/) (2018)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Smooth Tchebycheff Scalarization for Multi-Objective Optimization](https://mlsanity.com/paper/2402.19078/) (2024)
- [Multi-objective Contextual Bandit Problem with Similarity Information](https://mlsanity.com/paper/1803.04015/) (2018)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization](https://mlsanity.com/paper/2405.19650/) (2024)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Pure Exploration of Multi-armed Bandit Under Matroid Constraints](https://mlsanity.com/paper/1605.07162/) (2016)
- [Pareto Regret Analyses in Multi-objective Multi-armed Bandit](https://mlsanity.com/paper/2212.00884/) (2022)
- [Vector Optimization with Stochastic Bandit Feedback](https://mlsanity.com/paper/2110.12311/) (2021)
- [Optimal Scalarizations for Sublinear Hypervolume Regret](https://mlsanity.com/paper/2307.03288/) (2023)
- [Online Evaluation of Audiences for Targeted Advertising via Bandit Experiments](https://mlsanity.com/paper/1907.02178/) (2019)
- [Preference-based Pure Exploration](https://mlsanity.com/paper/2412.02988/) (2024)
- [Optimal Multi-Objective Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2501.13607/) (2025)
- [FraPPE: Fast and Efficient Preference-based Pure Exploration](https://mlsanity.com/paper/2508.16487/) (2025)
- [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026)
- [Thompson Sampling for Multi-Objective Linear Contextual Bandit](https://mlsanity.com/paper/2512.00930/) (2025)
- [Few-for-Many Personalized Federated Learning](https://mlsanity.com/paper/2603.11992/) (2026)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)
- [Decision-making with multiple correlated binary outcomes in clinical trials](https://mlsanity.com/paper/1908.10158/) (2019)
- [An Efficient Evolutionary Algorithm for Few-for-Many Optimization](https://mlsanity.com/paper/2601.06387/) (2026)

## Abstract (arXiv)

Real-world systems often serve many objectives but can deploy only a few options, whose performance must be learned from noisy feedback. Modeling each option as an arm in a multi-objective bandit, we introduce few-for-many best-arm identification, which seeks a small set of arms minimizing the worst weighted degradation from the objective-wise optima, rather than the best arm for every objective. We consider both known objective groups and latent groups specified only by a representative budget, and propose textscGFM-Elim and textscAFM-Elim with instance-dependent sample-complexity guarantees. For Gaussian rewards, we further derive a lower bound for the latent-group setting and show that it is asymptotically attainable with high probability by an oracle-based Track-and-Stop procedure. Our results show that sharing observations across objectives and ignoring irrelevant objective-wise distinctions can substantially reduce the sampling cost, as confirmed by experiments on synthetic and real-world tasks.