Timezone: »

 
Poster
Feasible Arm Identification
Julian Katz-Samuels · Clay Scott

Thu Jul 12 09:15 AM -- 12:00 PM (PDT) @ Hall B #144
in Posters Thu »
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.
[ PDF] 

Author Information

Julian Katz-Samuels (University of Michigan)
Clay Scott (University of Michigan)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors