Sequential learning of the Pareto front for multi-objective bandits

élise crepon, Aurélien Garivier, Wouter M Koolen
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:3583-3591, 2024.

Abstract

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-\delta$. Our main contribution is an efficient implementation of an algorithm achieving the optimal sample complexity when the risk $\delta$ is small. With $K$ arms in $d$ dimensions, $p$ of which are in the Pareto set, the algorithm runs in time $O(K p^d)$ per round.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-crepon24a, title = {Sequential learning of the {P}areto front for multi-objective bandits}, author = {{c}repon, \'{e}lise and Garivier, Aur\'{e}lien and M Koolen, Wouter}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {3583--3591}, 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/crepon24a/crepon24a.pdf}, url = {https://proceedings.mlr.press/v238/crepon24a.html}, abstract = {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-\delta$. Our main contribution is an efficient implementation of an algorithm achieving the optimal sample complexity when the risk $\delta$ is small. With $K$ arms in $d$ dimensions, $p$ of which are in the Pareto set, the algorithm runs in time $O(K p^d)$ per round.} }
Endnote
%0 Conference Paper %T Sequential learning of the Pareto front for multi-objective bandits %A élise crepon %A Aurélien Garivier %A Wouter M Koolen %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-crepon24a %I PMLR %P 3583--3591 %U https://proceedings.mlr.press/v238/crepon24a.html %V 238 %X 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-\delta$. Our main contribution is an efficient implementation of an algorithm achieving the optimal sample complexity when the risk $\delta$ is small. With $K$ arms in $d$ dimensions, $p$ of which are in the Pareto set, the algorithm runs in time $O(K p^d)$ per round.
APA
crepon, é., Garivier, A. & M Koolen, W.. (2024). Sequential learning of the Pareto front for multi-objective bandits. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:3583-3591 Available from https://proceedings.mlr.press/v238/crepon24a.html.

Related Material