Logo Logo
Hilfe
Hilfe
Switch Language to English

Haddenhorst, Björn ORCID logoORCID: https://orcid.org/0000-0002-4023-6646; Bengs, Viktor; Brandt, Jasmin und Hüllermeier, Eyke ORCID logoORCID: https://orcid.org/0000-0002-9944-4108 (27. Juli 2021): Testification of Condorcet Winners in dueling bandits. Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, Virtual, July 27-30, 2021. de Campos, Cassio und Maathuis, Marloes H. (Hrsg.): In: Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, Bd. 161 PMLR. S. 1195-1205 [PDF, 875kB]

Abstract

Several algorithms for finding the best arm in the dueling bandits setting assume the existence of a Condorcet winner (CW), that is, an arm that uniformly dominates all other arms. Yet, by simply relying on this assumption but not verifying it, such algorithms may produce doubtful results in cases where it actually fails to hold. Even worse, the problem may not be noticed, and an alleged CW still be produced. In this paper, we therefore address the problem as a ”testification” task, by which we mean a combination of testing and identification: The online identification of the CW is combined with the statistical testing of the CW assumption. Thus, instead of returning a supposed CW at some point, the learner has the possibility to stop sampling and refuse an answer in case it feels confident that the CW assumption is violated. Analyzing the testification problem formally, we derive lower bounds on the expected sample complexity of any online algorithm solving it. Moreover, a concrete algorithm is proposed, which achieves the optimal sample complexity up to logarithmic terms.

Dokument bearbeiten Dokument bearbeiten