Top Feasible Arm Identification
[edit]
Proceedings of Machine Learning Research, PMLR 89:15931601, 2019.
Abstract
We propose a new variant of the top arm identification problem, \emph{top feasible arm identification}, where there are $K$ arms associated with $D$dimensional distributions and the goal is to find $m$ arms that maximize some known linear function of their means subject to the constraint that their means belong to a given set $P \subset R^D$. This problem has many applications since in many settings, feedback is multidimensional and it is of interest to perform \emph{constrained maximization}. We present problemdependent lower bounds for top feasible arm identification and upper bounds for several algorithms. Our most broadly applicable algorithm, TFLUCBB, has an upper bound that is loose by a factor of $O(D \log(K))$. Many problems of practical interest are twodimensional and, for these, it is loose by a factor of $O(\log(K))$. Finally, we conduct experiments on synthetic and realworld datasets that demonstrate the effectiveness of our algorithms. Our algorithms are superior both in theory and in practice to a naive twostage algorithm that first identifies the feasible arms and then applies a best arm identification algorithm to the feasible arms.
Related Material


