Timezone: »
Poster
Verification Based Solution for Structured MAB Problems
Zohar Karnin
We consider the problem of finding the best arm in a stochastic Mutli-armed Bandit (MAB) game and propose a general framework based on verification that applies to multiple well-motivated generalizations of the classic MAB problem. In these generalizations, additional structure is known in advance, causing the task of verifying the optimality of a candidate to be easier than discovering the best arm. Our results are focused on the scenario where the failure probability $\delta$ must be very low; we essentially show that in this high confidence regime, identifying the best arm is as easy as the task of verification. We demonstrate the effectiveness of our framework by applying it, and improving the state-of-the art results in the problems of: Linear bandits, Dueling bandits with the Condorcet assumption, Copeland dueling bandits, Unimodal bandits and Graphical bandits.
Author Information
Zohar Karnin (Yahoo Research)
More from the Same Authors
-
2016 Poster: Multi-armed Bandits: Competing with Optimal Sequences »
Zohar Karnin · Oren Anava -
2015 Poster: Copeland Dueling Bandits »
Masrour Zoghi · Zohar Karnin · Shimon Whiteson · Maarten de Rijke -
2013 Poster: Distributed Exploration in Multi-Armed Bandits »
Eshcar Hillel · Zohar Karnin · Tomer Koren · Ronny Lempel · Oren Somekh -
2013 Spotlight: Distributed Exploration in Multi-Armed Bandits »
Eshcar Hillel · Zohar Karnin · Tomer Koren · Ronny Lempel · Oren Somekh -
2013 Poster: Near-Optimal Entrywise Sampling for Data Matrices »
Dimitris Achlioptas · Zohar Karnin · Edo Liberty