# Best Group Identification in Multi-Objective Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 36 references that are in the map.
- First posted on arXiv 23 May 2025.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration](https://mlsanity.com/paper/1706.01081/) (2017)
- [Multi-Objective Generalized Linear Bandits](https://mlsanity.com/paper/1905.12879/) (2019)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Bandit Pareto Set Identification: the Fixed Budget Setting](https://mlsanity.com/paper/2311.03992/) (2023)
- [Sample complexity of partition identification using multi-armed bandits](https://mlsanity.com/paper/1811.05654/) (2018)
- [Pareto Regret Analyses in Multi-objective Multi-armed Bandit](https://mlsanity.com/paper/2212.00884/) (2022)
- [Maximin Action Identification: A New Bandit Framework for Games](https://mlsanity.com/paper/1602.04676/) (2016)
- [Max-Min Grouped Bandits](https://mlsanity.com/paper/2111.08862/) (2021)
- [Optimal Multi-Objective Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2501.13607/) (2025)
- [Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context](https://mlsanity.com/paper/2502.03061/) (2025)
- [Pareto Set Identification With Posterior Sampling](https://mlsanity.com/paper/2411.04939/) (2024)
- [Max-Quantile Grouped Infinite-Arm Bandits](https://mlsanity.com/paper/2210.01295/) (2022)

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

- [Active Context Selection Improves Simple Regret in Contextual Bandits](https://mlsanity.com/paper/2605.20040/) (2026)
- [Top-k Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection](https://mlsanity.com/paper/2607.26273/) (2026)

## Abstract (arXiv)

We introduce the Best Group Identification problem in a multi-objective multi-armed bandit setting, where an agent interacts with groups of arms with vector-valued rewards. The performance of a group is determined by an efficiency vector which represents the group's best attainable rewards across different dimensions. The objective is to identify the set of optimal groups in the fixed-confidence setting. We investigate two key formulations: group Pareto set identification, where efficiency vectors of optimal groups are Pareto optimal and linear best group identification, where each reward dimension has a known weight and the optimal group maximizes the weighted sum of its efficiency vector's entries. For both settings, we propose elimination-based algorithms, establish upper bounds on their sample complexity, and derive lower bounds that apply to any correct algorithm. Through numerical experiments, we demonstrate the strong empirical performance of the proposed algorithms.