Vi introducerar en ny modell av stokastiska banditer med kontradiktoriska korruption som syftar till att fånga inställningar där de flesta av indata följer ett stokastiskt mönster men en del av det kan motsträvigt ändras för att lura algoritmen, t.ex. klicka bedrägeri, falska recensioner och e-post spam. Målet med denna modell är att uppmuntra utformningen av banditalgoritmer som (i) fungerar bra i blandade kontradiktoriska och stokastiska modeller, och (ii) vars prestanda försämras graciöst när vi går från helt stokastiska till helt kontradiktoriska modeller. I vår modell är belöningarna för alla vapen initialt hämtade från en distribution och förändras sedan av en adaptiv motståndare. Vi tillhandahåller en enkel algoritm vars prestanda graciöst försämrar med den totala korruption som motståndaren injicerat i data, mätt som summan över den största förändringen motståndaren gjort i data i den omgången; denna totala korruption betecknas av C. Vår algoritm ger en garanti som behåller den optimala garantin (upp till en logaritmisk term) om inputen är stokastisk och vars prestanda degraderas linjärt till mängden korruption C, medan avgörande är agnostic till det. Vi ger också en lägre gräns som visar att denna linjära nedbrytning är nödvändig om algoritmen uppnår optimal prestanda i den stokastiska inställningen (den nedre gränsen fungerar även för en känd mängd korruption, ett specialfall där vår algoritm uppnår optimal prestanda utan extra logaritm).
I REF föreslår författarna en multi-lager aktiv arm eliminering ras algoritm för stokastiska banditer med kontradiktoriska korruption vars prestanda bryter linjärt mot mängden korruption, och visar att denna linjära nedbrytning är nödvändig.
Stochastic bandits robust to adversarial corruptions
{'venue': 'STOC 2018', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}