TY  - THES
AB  - 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.
AU  - Haddenhorst, Björn
CY  - Paderborn
DA  - 2023
DO  - 10.17619/UNIPB/1-1777
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 05.04.2023
N1  - Universität Paderborn, Dissertation, 2023
PB  - Veröffentlichungen der Universität
PY  - 2023
SP  - 1 Online-Ressource (xx, 263 Seiten)
T2  - Institut für Informatik
TI  - Testing coherence and identifying winners in dueling bandits: theory and algorithms
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-45392
Y2  - 2026-01-12T08:57:36
ER  -