# Vector Optimization with Stochastic Bandit Feedback

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 35 references that are in the map.
- First posted on arXiv 23 Oct 2021.

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

- [A Practical Guide to Multi-Objective Reinforcement Learning and Planning](https://mlsanity.com/paper/2103.09568/) (2021)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Predictive Entropy Search for Multi-objective Bayesian Optimization](https://mlsanity.com/paper/1511.05467/) (2015)
- [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)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [Multi-objective Contextual Bandit Problem with Similarity Information](https://mlsanity.com/paper/1803.04015/) (2018)
- [An Optimal Elimination Algorithm for Learning a Best Arm](https://mlsanity.com/paper/2006.11647/) (2020)
- [A norm minimization-based convex vector optimization algorithm](https://mlsanity.com/paper/2104.10282/) (2021)

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

- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [Bandit Pareto Set Identification: the Fixed Budget Setting](https://mlsanity.com/paper/2311.03992/) (2023)
- [FERERO: A Flexible Framework for Preference-Guided Multi-Objective Learning](https://mlsanity.com/paper/2412.01773/) (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)
- [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)
- [Vector Optimization with Gaussian Process Bandits](https://mlsanity.com/paper/2412.02484/) (2024)
- [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 introduce vector optimization problems with stochastic bandit feedback, in which preferences among designs are encoded by a polyhedral ordering cone C. Our setup generalizes the best arm identification problem to vector-valued rewards by extending the concept of Pareto set beyond multi-objective optimization. We characterize the sample complexity of (ε,δ)-PAC Pareto set identification by defining a new cone-dependent notion of complexity, called the ordering complexity. In particular, we provide gap-dependent and worst-case lower bounds on the sample complexity and show that, in the worst-case, the sample complexity scales with the square of ordering complexity. Furthermore, we investigate the sample complexity of the na"ive elimination algorithm and prove that it nearly matches the worst-case sample complexity. Finally, we run experiments to verify our theoretical results and illustrate how C and sampling budget affect the Pareto set, the returned (ε,δ)-PAC Pareto set, and the success of identification.