Learning the Pareto Set Under Incomplete Preferences: Pure Exploration in Vector Bandits
Efe Mert Karagözlü, Yaşar Cahit Yıldırım, Cağın Ararat, Cem Tekin
Abstract
We study pure exploration in bandit problems with vector-valued rewards, where the goal is to (approximately) identify the Pareto set of arms given incomplete preferences induced by a polyhedral convex cone. We address the open problem of designing sample-efficient learning algorithms for such problems. We propose Pareto Vector Bandits (PaVeBa), an adaptive elimination algorithm that nearly matches the gap-dependent and worst-case lower bounds on the sample complexity of $(\epsilon, \delta)$-PAC Pareto set identification. Finally, we provide an in-depth numerical investigation of PaVeBa and its heuristic variants by comparing them with the state-of-the-art multi-objective and vector optimization algorithms on several real-world datasets with conflicting objectives.
BibTeX
@InProceedings{pmlr-v238-karagozlu24a,
title = {Learning the {P}areto Set Under Incomplete Preferences: Pure Exploration in Vector Bandits},
author = {Karag{\"o}zl{\"u}, Efe Mert and Y{\i}ld{\i}r{\i}m, Ya{\c{s}}ar Cahit and Ararat, Ca\u{g}{\i}n and Tekin, Cem},
booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics},
pages = {3070--3078},
year = {2024},
editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen},
volume = {238},
series = {Proceedings of Machine Learning Research},
month = {02--04 May},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v238/karagozlu24a/karagozlu24a.pdf},
url = {https://proceedings.mlr.press/v238/karagozlu24a.html},
abstract = {We study pure exploration in bandit problems with vector-valued rewards, where the goal is to (approximately) identify the Pareto set of arms given incomplete preferences induced by a polyhedral convex cone. We address the open problem of designing sample-efficient learning algorithms for such problems. We propose Pareto Vector Bandits (PaVeBa), an adaptive elimination algorithm that nearly matches the gap-dependent and worst-case lower bounds on the sample complexity of $(\epsilon, \delta)$-PAC Pareto set identification. Finally, we provide an in-depth numerical investigation of PaVeBa and its heuristic variants by comparing them with the state-of-the-art multi-objective and vector optimization algorithms on several real-world datasets with conflicting objectives.}
}