I detta dokument studeras aktivt lärande inom ramen för robust statistik. Särskilt föreslår vi en variant av problemet med bästa armidentifiering för kontaminerade banditer, där varje armdrag har sannolikhet att generera ett prov från en godtycklig kontamineringsfördelning i stället för den verkliga underliggande fördelningen. Målet är att identifiera den bästa (eller ungefär bästa) sanna fördelningen med hög sannolikhet, med ett sekundärt mål att ge garantier för kvaliteten på denna fördelning. Den främsta utmaningen med den kontaminerade banditinställningen är att de verkliga distributionerna endast delvis kan identifieras, även med oändliga prover. För att ta itu med detta utvecklar vi först snäva, icke-asymptotiska prov komplexitet gränser för hög sannolikhet uppskattning av de första två robusta ögonblicken (median och median absolut avvikelse) från kontaminerade prover, som kan vara av oberoende intresse. Med hjälp av dessa resultat anpassar vi flera klassiska bästa armidentifieringsalgoritmer till den kontaminerade banditinställningen och härleder provkomplexa övre gränser för vårt problem. Slutligen ger vi matchande informations-teoretiska nedre gränser på provet komplexitet (upp till en liten logaritmisk faktor). Våra resultat tyder på en inneboende robusthet hos klassiska bästa armidentifieringsalgoritmer.
REF överväga kontaminerade stokastiska banditer i den nära besläktade bästa-arm identifieringsinställningen, där rundor av en stokastisk banditer instans är förorenade enhetligt slumpmässigt av en "ytterligare" distribution, och målet är att identifiera den bästa armen trots korruptionen.
Best Arm Identification for Contaminated Bandits
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}