# Sequential Learning of the Pareto Front for Multi-objective Bandits

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 29 Jan 2025.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection](https://mlsanity.com/paper/1702.03605/) (2017)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits](https://mlsanity.com/paper/2010.12247/) (2020)
- [Adaptive Sampling for Best Policy Identification in Markov Decision Processes](https://mlsanity.com/paper/2009.13405/) (2020)
- [Optimal Best-Arm Identification Methods for Tail-Risk Measures](https://mlsanity.com/paper/2008.07606/) (2020)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Thresholding Bandit for Dose-ranging: The Impact of Monotonicity](https://mlsanity.com/paper/1711.04454/) (2017)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [Pareto Regret Analyses in Multi-objective Multi-armed Bandit](https://mlsanity.com/paper/2212.00884/) (2022)
- [Optimal Best Markovian Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1912.00636/) (2019)
- [Maximin Action Identification: A New Bandit Framework for Games](https://mlsanity.com/paper/1602.04676/) (2016)
- [MaxGap Bandit: Adaptive Algorithms for Approximate Ranking](https://mlsanity.com/paper/1906.00547/) (2019)
- [Adaptive Multiple-Arm Identification](https://mlsanity.com/paper/1706.01026/) (2017)
- [Skyline Identification in Multi-Armed Bandits](https://mlsanity.com/paper/1711.04213/) (2017)

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

- [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)
- [Best Group Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2505.17869/) (2025)
- [Constrained Pareto Set Identification with Bandit Feedback](https://mlsanity.com/paper/2506.08127/) (2025)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)
- [Multi-thresholding Good Arm Identification with Bandit Feedback](https://mlsanity.com/paper/2503.10386/) (2025)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm](https://mlsanity.com/paper/2506.13125/) (2025)
- [Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits](https://mlsanity.com/paper/2511.05802/) (2025)
- [Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Bandits](https://mlsanity.com/paper/2601.11924/) (2026)
- [Probe-then-Commit Multi-Objective Bandits: Theoretical Benefits of Limited Multi-Arm Feedback](https://mlsanity.com/paper/2602.03175/) (2026)
- [Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits](https://mlsanity.com/paper/2606.18785/) (2026)
- [Selective Ensemble Based on Preference-Directed Multi-Objective Bandits](https://mlsanity.com/paper/2606.21929/) (2026)
- [Few-for-Many Best-Arm Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2610.16840/) (2026)
- [When More Objectives Make Identification Easier: The Role of Preferences and Feedback](https://mlsanity.com/paper/2610.18577/) (2026)

## Abstract (arXiv)

We study the problem of sequential learning of the Pareto front in multi-objective multi-armed bandits. An agent is faced with K possible arms to pull. At each turn she picks one, and receives a vector-valued reward. When she thinks she has enough information to identify the Pareto front of the different arm means, she stops the game and gives an answer. We are interested in designing algorithms such that the answer given is correct with probability at least 1-δ. Our main contribution is an efficient implementation of an algorithm achieving the optimal sample complexity when the risk δ is small. With K arms in d dimensions p of which are in the Pareto set, the algorithm runs in time O(Kpd) per round.