Online-lärande algoritmer är utformade för att lära sig även när deras insats genereras av en motståndare. Den allmänt accepterade formella definitionen av en online-algoritm förmåga att lära är den spelteoretiska begreppet ånger. Vi hävdar att standarddefinitionen av ånger blir otillräcklig om motståndaren tillåts anpassa sig till online-algoritmens åtgärder. Vi definierar det alternativa begreppet politiskt beklagande, som försöker ge ett mer meningsfullt sätt att mäta en online-algoritm prestanda mot adaptiva motståndare. Med fokus på online bandit inställning, visar vi att ingen bandit algoritm kan garantera en sublinjär politik ånger mot en adaptiv motståndare med obegränsat minne. Å andra sidan, om motståndarens minne begränsas, presenterar vi en allmän teknik som omvandlar varje banditalgoritm med en sublinjär ånger bunden till en algoritm med en sublinjär politik ångra bunden. Vi utvidgar detta resultat till andra varianter av ånger, såsom att byta ånger, inre ånger och byta ånger.
Ref introducerar begreppet politiskt beklagande som ett mer meningsfullt alternativ till beklagande för mätning av en online-algoritms prestanda mot adaptiva motståndare.
Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
{'venue': 'ICML', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}