Timezone: »
Poster
Feasible Arm Identification
Julian Katz-Samuels · Clay Scott
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.
Author Information
Julian Katz-Samuels (University of Michigan)
Clay Scott (University of Michigan)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Oral: Feasible Arm Identification »
Thu. Jul 12th 12:30 -- 12:50 PM Room A5
More from the Same Authors
-
2023 Poster: Mixture Proportion Estimation Beyond Irreducibility »
Yilun Zhu · Aaron Fjeldsted · Darren Holland · George Landon · Azaree Lintereur · Clay Scott -
2022 Poster: Training OOD Detectors in their Natural Habitats »
Julian Katz-Samuels · Julia Nakhleh · Robert Nowak · Sharon Li -
2022 Spotlight: Training OOD Detectors in their Natural Habitats »
Julian Katz-Samuels · Julia Nakhleh · Robert Nowak · Sharon Li -
2021 Poster: An exact solver for the Weston-Watkins SVM subproblem »
Yutong Wang · Clay Scott -
2021 Spotlight: An exact solver for the Weston-Watkins SVM subproblem »
Yutong Wang · Clay Scott