Abstract
In this paper we propose the Augmented-UCB (AugUCB) algorithm for a fixed-budget version of the
thresholding bandit problem (TBP), where the objective is to identify a set of arms whose quality is
above a threshold. A key feature of AugUCB is that
it uses both mean and variance estimates to eliminate arms that have been sufficiently explored; to
the best of our knowledge this is the first algorithm
to employ such an approach for the considered
TBP. Theoretically, we obtain an upper bound on
the loss (probability of mis-classification) incurred
by AugUCB. Although UCBEV in literature provides a better guarantee, it is important to emphasize that UCBEV has access to problem complexity
(whose computation requires arms’ mean and variances), and hence is not realistic in practice; this is
in contrast to AugUCB whose implementation does
not require any such complexity inputs. We conduct extensive simulation experiments to validate
the performance of AugUCB. Through our simulation work, we establish that AugUCB, owing to its
utilization of variance estimates, performs signifi-
cantly better than the state-of-the-art APT, CSAR
and other non variance-based algorithms