Pareto Front Identification with Regret Minimization
Wonyoung Kim Garud Iyengar Assaf Zeevi
We consider Pareto front identification for linear bandits (PFILin) where the
goal is to identify a set of arms whose reward vectors are not dominated by any
of the others when the mean reward vector is a linear function of the context.
PFILin includes the best arm identification problem and multi-objective active
learning as special cases. The sample complexity of our proposed algorithm is
$\tilde{O}(d/\Delta^2)$, where $d$ is the dimension of contexts and $\Delta$ is
a measure of problem complexity. Our sample complexity is optimal up to a
logarithmic factor. A novel feature of our algorithm is that it uses the
contexts of all actions. In addition to efficiently identifying the Pareto
front, our algorithm also guarantees $\tilde{O}(\sqrt{d/t})$ bound for
instantaneous Pareto regret when the number of samples is larger than
$\Omega(d\log dL)$ for $L$ dimensional vector rewards. By using the contexts of
all arms, our proposed algorithm simultaneously provides efficient Pareto front
identification and regret minimization. Numerical experiments demonstrate that
the proposed algorithm successfully identifies the Pareto front while
minimizing the regret.