Active Ranking of Experts Based on their Performances in Many Tasks
El Mehdi Saad Nicolas Verzelen Alexandra Carpentier
We consider the problem of ranking n experts based on their performances on d
tasks. We make a monotonicity assumption stating that for each pair of experts,
one outperforms the other on all tasks. We consider the sequential setting
where in each round, the learner has access to noisy evaluations of actively
chosen pair of expert-task, given the information available up to the actual
round. Given a confidence parameter $\delta$ $\in$ (0, 1), we provide
strategies allowing to recover the correct ranking of experts and develop a
bound on the total number of queries made by our algorithm that hold with
probability at least 1 -- $\delta$. We show that our strategy is adaptive to
the complexity of the problem (our bounds are instance dependent), and develop
matching lower bounds up to a poly-logarithmic factor. Finally, we adapt our
strategy to the relaxed problem of best expert identification and provide
numerical simulation consistent with our theoretical results.