Feasible Arm Identification

Julian Katz-Samuels, Clay Scott
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2535-2543, 2018.

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.

Cite this Paper

BibTeX
@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.} }
Endnote
%0 Conference Paper %T Feasible Arm Identification %A Julian Katz-Samuels %A Clay Scott %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-katz-samuels18a %I PMLR %P 2535--2543 %U https://proceedings.mlr.press/v80/katz-samuels18a.html %V 80 %X 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.
APA
Katz-Samuels, J. & Scott, C.. (2018). Feasible Arm Identification. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2535-2543 Available from https://proceedings.mlr.press/v80/katz-samuels18a.html.

Related Material