Vi studerar ett specifikt kombinatoriskt rent utforskande stokastiskt bandit problem där eleven syftar till att hitta uppsättningen av armar vars medel är över en given tröskel, upp till en given precision, och för en fast tidshorisont. Vi föreslår en parameterfri algoritm baserad på en originell heuristisk, och bevisar att den är optimal för detta problem genom att härleda matchande övre och nedre gränser. Såvitt vi vet är detta den första icke-triviala ren undersökningsmiljö med fast budget för vilken optimala strategier konstrueras.
I REF studeras fastställandet av uppsättningen vapen (av ändligt många) över en given tröskel i en fast tidshorisont.
An optimal algorithm for the Thresholding Bandit Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}