Timezone: »
Poster
Batched Coarse Ranking in Multi-Armed Bandits
Nikolai Karpov · Qin Zhang
We study the problem of coarse ranking in the multi-armed bandits (MAB) setting, where we have a set of arms each of which is associated with an unknown distribution. The task is to partition the arms into clusters of predefined sizes, such that the mean of any arm in the $i$-th cluster is larger than that of any arm in the $j$-th cluster for any $j > i$. Coarse ranking generalizes a number of basic problems in MAB (e.g., best arm identification) and has many real-world applications. We initiate the study of the problem in the batched model where we can only have a small number of policy changes. We study both the fixed budget and fixed confidence variants in MAB, and propose algorithms and prove impossibility results which together give almost tight tradeoffs between the total number of arms pulls and the number of policy changes. We have tested our algorithms in both real and synthetic data; our experimental results have demonstrated the efficiency of the proposed methods.
Author Information
Nikolai Karpov (Indiana University Bloomington)
Qin Zhang (Indiana University Bloomington)
More from the Same Authors
-
2018 Poster: A Practical Algorithm for Distributed Clustering and Outlier Detection »
Jiecao Chen · Erfan Sadeqi Azer · Qin Zhang -
2018 Poster: Tight Bounds for Collaborative PAC Learning via Multiplicative Weights »
Jiecao Chen · Qin Zhang · Yuan Zhou -
2016 Poster: Communication-Optimal Distributed Clustering »
Jiecao Chen · He Sun · David Woodruff · Qin Zhang