Pareto front identification from stochastic bandit feedback

P. Auer, C.-K. Chiang, R. Ortner, M.M. Drugan

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

22 Citations (Scopus)
108 Downloads (Pure)


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 use a confidence bound algorithm to approximate the Pareto front, and we 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.
Original languageEnglish
Title of host publicationInternational Conference on Artificial Intelligence and Statistics (AISTATS), 9-11 May 2016, Cadiz, Spain
Place of Publications.l.
Publication statusPublished - 1 May 2016


  • Stochastic bandits
  • Pareto front identification
  • Upper bounds


Dive into the research topics of 'Pareto front identification from stochastic bandit feedback'. Together they form a unique fingerprint.

Cite this