Feasible Arm Identification

@InProceedings{pmlr-v80-katz-samuels18a,
  title = 	 {Feasible Arm Identification},
  author =       {Katz-Samuels, Julian and Scott, Clay},
  booktitle = 	 {Proceedings of the 35th International Conference on Machine Learning},
  pages = 	 {2535--2543},
  year = 	 {2018},
  editor = 	 {Dy, Jennifer and Krause, Andreas},
  volume = 	 {80},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {10--15 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v80/katz-samuels18a/katz-samuels18a.pdf},
  url = 	 {https://proceedings.mlr.press/v80/katz-samuels18a.html},
  abstract = 	 {We introduce the feasible arm identification problem, a pure exploration multi-armed bandit problem where the agent is given a set of $D$-dimensional arms and a polyhedron $P = \{x : A x \leq b \} \subset R^D$. Pulling an arm gives a random vector and the goal is to determine, using a fixed budget of $T$ pulls, which of the arms have means belonging to $P$. We propose three algorithms MD-UCBE, MD-SAR, and MD-APT and provide a unified analysis establishing upper bounds for each of them. We also establish a lower bound that matches up to constants the upper bounds of MD-UCBE and MD-APT. Finally, we demonstrate the effectiveness of our algorithms on synthetic and real-world datasets.}
}