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

14 Citations (Scopus)
78 Downloads (Pure)

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 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.
Publishers.n.
Pages939-947
Publication statusPublished - 1 May 2016

Keywords

  • Stochastic bandits
  • Pareto front identification
  • Upper bounds

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

Cite this