# Pareto Regret Analyses in Multi-objective Multi-armed Bandit

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 19 references that are in the map.
- First posted on arXiv 1 Dec 2022.

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

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Refined Lower Bounds for Adversarial Bandits](https://mlsanity.com/paper/1605.07416/) (2016)
- [On Regret with Multiple Best Arms](https://mlsanity.com/paper/2006.14785/) (2020)

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

- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Provably Efficient Multi-Objective Bandit Algorithms under Preference-Centric Customization](https://mlsanity.com/paper/2502.13457/) (2025)
- [Best Group Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2505.17869/) (2025)
- [Thompson Sampling for Multi-Objective Linear Contextual Bandit](https://mlsanity.com/paper/2512.00930/) (2025)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)
- [Large-Batch, Iteration-Efficient Neural Bayesian Design Optimization](https://mlsanity.com/paper/2306.01095/) (2023)
- [Regret Lower Bounds in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2308.08046/) (2023)
- [Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm](https://mlsanity.com/paper/2506.13125/) (2025)
- [Procedural Fairness in Multi-Agent Bandits](https://mlsanity.com/paper/2601.10600/) (2026)
- [Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?](https://mlsanity.com/paper/2604.07096/) (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 Pareto optimality in multi-objective multi-armed bandit by providing a formulation of adversarial multi-objective multi-armed bandit and defining its Pareto regrets that can be applied to both stochastic and adversarial settings. The regrets do not rely on any scalarization functions and reflect Pareto optimality compared to scalarized regrets. We also present new algorithms assuming both with and without prior information of the multi-objective multi-armed bandit setting. The algorithms are shown optimal in adversarial settings and nearly optimal up to a logarithmic factor in stochastic settings simultaneously by our established upper bounds and lower bounds on Pareto regrets. Moreover, the lower bound analyses show that the new regrets are consistent with the existing Pareto regret for stochastic settings and extend an adversarial attack mechanism from bandit to the multi-objective one.