Vector Optimization with Stochastic Bandit Feedback
  We introduce vector optimization problems with stochastic bandit feedback,
which extends the best arm identification problem to vector-valued rewards. We
consider $K$ designs with multi-dimensional mean reward vectors, which are
partially ordered according to a polyhedral ordering cone $C$. This generalizes
the concept of the Pareto set in multi-objective optimization and allows
different sets of preferences of decision-makers to be encoded by $C$.
Different than prior work, we define approximations of the Pareto set based on
direction-free covering and gap notions. We study an ($\epsilon,\delta$)-PAC
Pareto set identification problem where an evaluation of each design yields a
noisy observation of the mean reward vector. In order to characterize the
difficulty of learning the Pareto set, we introduce the concept of {\em
ordering complexity}, i.e., geometric conditions on the deviations of empirical
reward vectors from their mean under which the Pareto front can be approximated
accurately. We show how to compute the ordering complexity of any polyhedral
ordering cone. We provide gap-dependent and worst-case lower bounds on the
sample complexity and show that in the worst-case the sample complexity scales
with the square of ordering complexity. Furthermore, we investigate the sample
complexity of the na\"ive elimination algorithm and prove that it nearly
matches the worst-case sample complexity. Finally, we run experiments to verify
our theoretical results and illustrate how $C$ and sampling budget affect the
Pareto set, returned ($\epsilon,\delta$)-PAC Pareto set and the success of
identification.
