Pareto Front Identification from Stochastic Bandit Feedback

Peter Auer, Chao-Kai Chiang, Ronald Ortner, Madalina Drugan
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:939-947, 2016.

Abstract

We consider the problem of identifying the Pareto front for multiple objectives from a finite set of operating points. Sampling an operating point gives a random vector where each coordinate corresponds to the value of one of the objectives. The Pareto front is the set of operating points that are not dominated by any other operating point in respect to all objectives (considering the mean of their objective values). We propose a confidence bound algorithm to approximate the Pareto front, and prove problem specific lower and upper bounds, showing that the sample complexity is characterized by some natural geometric properties of the operating points. Experiments confirm the reliability of our algorithm. For the problem of finding a sparse cover of the Pareto front, we propose an asymmetric covering algorithm of independent interest.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-auer16, title = {Pareto Front Identification from Stochastic Bandit Feedback}, author = {Auer, Peter and Chiang, Chao-Kai and Ortner, Ronald and Drugan, Madalina}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {939--947}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/auer16.pdf}, url = {https://proceedings.mlr.press/v51/auer16.html}, abstract = {We consider the problem of identifying the Pareto front for multiple objectives from a finite set of operating points. Sampling an operating point gives a random vector where each coordinate corresponds to the value of one of the objectives. The Pareto front is the set of operating points that are not dominated by any other operating point in respect to all objectives (considering the mean of their objective values). We propose a confidence bound algorithm to approximate the Pareto front, and prove problem specific lower and upper bounds, showing that the sample complexity is characterized by some natural geometric properties of the operating points. Experiments confirm the reliability of our algorithm. For the problem of finding a sparse cover of the Pareto front, we propose an asymmetric covering algorithm of independent interest.} }
Endnote
%0 Conference Paper %T Pareto Front Identification from Stochastic Bandit Feedback %A Peter Auer %A Chao-Kai Chiang %A Ronald Ortner %A Madalina Drugan %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-auer16 %I PMLR %P 939--947 %U https://proceedings.mlr.press/v51/auer16.html %V 51 %X We consider the problem of identifying the Pareto front for multiple objectives from a finite set of operating points. Sampling an operating point gives a random vector where each coordinate corresponds to the value of one of the objectives. The Pareto front is the set of operating points that are not dominated by any other operating point in respect to all objectives (considering the mean of their objective values). We propose a confidence bound algorithm to approximate the Pareto front, and prove problem specific lower and upper bounds, showing that the sample complexity is characterized by some natural geometric properties of the operating points. Experiments confirm the reliability of our algorithm. For the problem of finding a sparse cover of the Pareto front, we propose an asymmetric covering algorithm of independent interest.
RIS
TY - CPAPER TI - Pareto Front Identification from Stochastic Bandit Feedback AU - Peter Auer AU - Chao-Kai Chiang AU - Ronald Ortner AU - Madalina Drugan BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-auer16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 939 EP - 947 L1 - http://proceedings.mlr.press/v51/auer16.pdf UR - https://proceedings.mlr.press/v51/auer16.html AB - We consider the problem of identifying the Pareto front for multiple objectives from a finite set of operating points. Sampling an operating point gives a random vector where each coordinate corresponds to the value of one of the objectives. The Pareto front is the set of operating points that are not dominated by any other operating point in respect to all objectives (considering the mean of their objective values). We propose a confidence bound algorithm to approximate the Pareto front, and prove problem specific lower and upper bounds, showing that the sample complexity is characterized by some natural geometric properties of the operating points. Experiments confirm the reliability of our algorithm. For the problem of finding a sparse cover of the Pareto front, we propose an asymmetric covering algorithm of independent interest. ER -
APA
Auer, P., Chiang, C., Ortner, R. & Drugan, M.. (2016). Pareto Front Identification from Stochastic Bandit Feedback. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:939-947 Available from https://proceedings.mlr.press/v51/auer16.html.

Related Material