Thresholding Bandit with Optimal Aggregate Regret

05/27/2019
by   Chao Tao, et al.
5

We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold θ, with a fixed budget of T trials. We introduce LSA, a new, simple and anytime algorithm that aims to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algorithm is instance-wise asymptotically optimal. We also provide comprehensive empirical results to demonstrate the algorithm's superior performance over existing algorithms under a variety of different scenarios.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset