Details

Autor(en) / Beteiligte

• Haddenhorst, Björn
• Hüllermeier, Eyke[Akademischer Betreuer]
• Clémençon, Stephan[Akademischer Betreuer]
• Kolb, Martin[Akademischer Betreuer]

Titel

Testing coherence and identifying winners in dueling bandits: theory and algorithms

Ort / Verlag

Paderborn

Erscheinungsjahr

2023

Link zu anderen Inhalten

• Volltext
• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 05.04.2023
• ger: Zahlreiche Lernalgorithmen im stochastischen (Multi)-Dueling-Banditen-Szenario (engl.:(multi-)dueling bandits scenario; (M)DB) erfordern, dass die dem Feedback-Mechanismus zugrunde liegenden Gewinnwahrscheinlichkeiten gewisse Arten von Kohärenz erfüllen. In dieser Arbeit diskutieren wir das Testen derartiger Kohärenzannahmen und führen das Problem des Testifizierens des Condorcet Gewinners (engl.: Condorcet winner; CW) in DB ein, als das Problem, den CW zu identifizieren, falls er existiert, und andernfalls Nichtexistenz zu detektieren. Des Weiteren diskutieren wir die Identifikation des verallgemeinerten Condorcet Gewinners (engl.: generalized Condorcet winner; GCW) in MDB unter der Annahme, dass er existiert. Wir zeigen unter anderem, dass die Kohärenz der Gewinnwahrscheinlichkeiten mit einem Plackett-Luce-Modell in MDB unter der sogenannten Low-Noise-Annahme nicht derart getestet werden kann, dass die erwartete Probenkomplexität (engl.: sample complexity) im schlechtesten Fall endlich ist, und gleiches gilt in DB für diverse Arten stochastischer Transitivität. Im Gegensatz dazu sind sowohl das Testen von schwacher stochastischer Transitivität (engl.: weak stochastic transitivity; WST) als auch das Testifizieren des CW in diesem Sinne möglich. Für das Testen von WST, die Testifikation des CW als auch die Identifikation des GCW präsentieren wir algorithmische Lösungen im sogenannten fixed-confidence Setting und leiten instanzspezifische untere und obere Schranken an die zur Lösung der Probleme benötigten Probenkomplexität her, welche im schlechtesten Fall bis auf logarithmische Faktoren asymptotisch optimal sind. Zusätzlich untersuchen wir, in welchem Maße eine Plackett-Luce-Annahme an den stochastischen Feedback-Mechanismus das Lernproblem vereinfacht.
• eng: Many learning algorithms in the stochastic (multi-)dueling bandits scenario assume the winning probabilities underlying the environments feedback mechanism to be appropriately coherent. This thesis approaches the problem of checking the validity of several types of coherence in this regard. Moreover, we introduce the task of CW identification in dueling bandits, which consists of identifying the Condorcet winner (CW) if it exists, and detecting non-existence otherwise. Finally, we investigate the problem of identifying the generalized Condorcet winner (GCW) in multi-dueling bandits assuming its existence. We show that, amongst others, coherence of the winning probabilities with a Plackett-Luce model cannot be tested under the low-noise assumption in multi-dueling bandits within a finite expected sample complexity in the worst case, and the same holds for several types of stochastic transitivity in dueling bandits. In contrast, testing of weak stochastic transitivity (WST) and even CW testification are solvable in this regard. For all of WST testing, CW testification and GCW identification, we present multiple algorithmic solutions in the active fixed confidence setting and derive instance-dependent sample complexity upper and lower bounds that are in the worst case asymptotically tight up to logarithmic terms. In addition, we investigate to which extent a Plackett-Luce assumption on the probabilistic feedback mechanism simplifies the identification of the GCW.