Active Ranking of Experts Based on their Performances in Many Tasks

El Mehdi Saad, Nicolas Verzelen, Alexandra Carpentier
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:29490-29513, 2023.

Abstract

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 ploy-logarithmic factor. Finally, we adapt our strategy to the relaxed problem of best expert identification and provide numerical simulation consistent with our theoretical results

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-saad23b, title = {Active Ranking of Experts Based on their Performances in Many Tasks}, author = {Saad, El Mehdi and Verzelen, Nicolas and Carpentier, Alexandra}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {29490--29513}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/saad23b/saad23b.pdf}, url = {https://proceedings.mlr.press/v202/saad23b.html}, abstract = {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 ploy-logarithmic factor. Finally, we adapt our strategy to the relaxed problem of best expert identification and provide numerical simulation consistent with our theoretical results} }
Endnote
%0 Conference Paper %T Active Ranking of Experts Based on their Performances in Many Tasks %A El Mehdi Saad %A Nicolas Verzelen %A Alexandra Carpentier %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-saad23b %I PMLR %P 29490--29513 %U https://proceedings.mlr.press/v202/saad23b.html %V 202 %X 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 ploy-logarithmic factor. Finally, we adapt our strategy to the relaxed problem of best expert identification and provide numerical simulation consistent with our theoretical results
APA
Saad, E.M., Verzelen, N. & Carpentier, A.. (2023). Active Ranking of Experts Based on their Performances in Many Tasks. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:29490-29513 Available from https://proceedings.mlr.press/v202/saad23b.html.

Related Material