Timezone: »

On Top-k Selection in Multi-Armed Bandits and Hidden Bipartite Graphs
Wei Cao · Jian Li · Yufei Tao · Zhize Li

Thu Dec 10 08:00 AM -- 12:00 PM (PST) @ 210 C #92
This paper discusses how to efficiently choose from $n$ unknowndistributions the $k$ ones whose means are the greatest by a certainmetric, up to a small relative error. We study the topic under twostandard settings---multi-armed bandits and hidden bipartitegraphs---which differ in the nature of the input distributions. In theformer setting, each distribution can be sampled (in the i.i.d.manner) an arbitrary number of times, whereas in the latter, eachdistribution is defined on a population of a finite size $m$ (andhence, is fully revealed after $m$ samples). For both settings, weprove lower bounds on the total number of samples needed, and proposeoptimal algorithms whose sample complexities match those lower bounds.

Author Information

Wei Cao (Tsinghua University)
Jian Li (Tsinghua University)
Yufei Tao (CUHK)
Zhize Li (Tsinghua University)

Zhize Li is a PhD student at Institute for Interdisciplinary Information Sciences (IIIS), Tsinghua University (Advisor: Prof. Jian Li). His research interests lie in theoretical computer science and machine learning, in particular (non-)convex optimization algorithms, machine learning, algorithms and data structures.

More from the Same Authors