Duellbandit problemet är en variation av den klassiska multi-armad bandit där tillåtna åtgärder är bullriga jämförelser mellan par av armar. Detta dokument fokuserar på en ny metod för att hitta den "bästa" armen enligt Bordakriteriet med hjälp av bullriga jämförelser. Vi bevisar att i avsaknad av strukturella antaganden, provet komplexiteten i detta problem är proportionell mot summan av den inversa kvadraten luckor mellan Borda poäng för varje suboptimal arm och den bästa armen. Vi utforskar detta beroende ytterligare och överväger strukturella begränsningar på parvis jämförelsematris (en särskild form av gleshet naturligt till detta problem) som kan avsevärt minska provet komplexitet. Detta motiverar en ny algoritm som heter Successive Elimination with Comparison Sparsity (SECS) som utnyttjar gleshet för att hitta Borda vinnare med färre prover än standardalgoritmer. Vi utvärderar också den nya algoritmen experimentellt med syntetiska och verkliga data. Resultaten visar att sparsamhetsmodellen och den nya algoritmen kan ge betydande förbättringar jämfört med standardmetoder.
REF studerar problemet genom att tillåta bullerjämförelser mellan duellerna.
Sparse Dueling Bandits
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}