# Bandit Pareto Set Identification: the Fixed Budget Setting

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 7 Nov 2023.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [Information-Directed Selection for Top-Two Algorithms](https://mlsanity.com/paper/2205.12086/) (2022)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [Bayesian Fixed-Budget Best-Arm Identification](https://mlsanity.com/paper/2211.08572/) (2022)
- [Vector Optimization with Stochastic Bandit Feedback](https://mlsanity.com/paper/2110.12311/) (2021)
- [Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget](https://mlsanity.com/paper/2211.14768/) (2022)

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

- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Preference-based Pure Exploration](https://mlsanity.com/paper/2412.02988/) (2024)
- [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)
- [Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2405.15090/) (2024)
- [Best Group Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2505.17869/) (2025)
- [Bandit Pareto Set Identification in a Multi-Output Linear Model](https://mlsanity.com/paper/2507.04255/) (2025)
- [Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits](https://mlsanity.com/paper/2605.14553/) (2026)
- [Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits](https://mlsanity.com/paper/2511.05802/) (2025)
- [On the Problem of Best Arm Retention](https://mlsanity.com/paper/2504.11866/) (2025)
- [Risk-Averse Best Arm Set Identification with Fixed Budget and Fixed Confidence](https://mlsanity.com/paper/2506.22253/) (2025)
- [Box Thirding: Anytime Best Arm Identification under Insufficient Sampling](https://mlsanity.com/paper/2602.18186/) (2026)
- [Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits](https://mlsanity.com/paper/2606.18785/) (2026)
- [When More Objectives Make Identification Easier: The Role of Preferences and Feedback](https://mlsanity.com/paper/2610.18577/) (2026)

## Abstract (arXiv)

We study a multi-objective pure exploration problem in a multi-armed bandit model. Each arm is associated to an unknown multi-variate distribution and the goal is to identify the distributions whose mean is not uniformly worse than that of another distribution: the Pareto optimal set. We propose and analyze the first algorithms for the fixed budget Pareto Set Identification task. We propose Empirical Gap Elimination, a family of algorithms combining a careful estimation of the ``hardness to classify'' each arm in or out of the Pareto set with a generic elimination scheme. We prove that two particular instances, EGE-SR and EGE-SH, have a probability of error that decays exponentially fast with the budget, with an exponent supported by an information theoretic lower-bound. We complement these findings with an empirical study using real-world and synthetic datasets, which showcase the good performance of our algorithms.