Vi anser att stokastiska bandit problem med en sammanhängande uppsättning av armar och där den förväntade belöningen är en kontinuerlig och unimodal funktion av armen. Inga ytterligare antaganden görs om den förväntade belöningsfunktionens smidighet och struktur. Vi föreslår Stochastic Pentachotomi (SP), en algoritm för vilken vi härleder ändlig tid ångra övre gränser. I synnerhet visar vi att för alla förväntade belöningsfunktion μ som beter sig som μ(x) = μ(x ) − C.x − x  på lokal nivå runt sin maximering x för vissa X, C > 0, SP algoritmen är ordning-optimal, dvs. dess ångra skalor som O( T log(T )) när tidshorisonten T växer stor. Denna ångra skalning uppnås utan kunskap om och C. Vår algoritm är baserad på asymptotiskt optimala sekventiella statistiska tester som används för att successivt beskära ett intervall som innehåller den bästa armen med hög sannolikhet. Som vi vet utgör SP-algoritmen den första sekventiella armurvalsregeln som uppnår en ångerskalning som O( ❌ T ) upp till en logaritmisk faktor för icke-smooth förväntade belöningsfunktioner, samt för smidiga funktioner med okänd jämnhet.
Ref överväga stokastiska bandit problem med en kontinuerlig uppsättning av armar och där den förväntade belöningen är en kontinuerlig och unimodal funktion av armen.
Unimodal Bandits without Smoothness
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}