Vi presenterar en algoritm baserad på bakre provtagning (aka Thompson provtagning) som uppnår nästan optimala värsta fall ånger gränser när den underliggande Markov beslutsprocessen (MDP) kommunicerar med en ändlig, om än okänd, diameter. Vårt huvudsakliga resultat är en hög sannolikhet ångra övre gränsen av Õ(D ε SAT ) för alla kommunicerande MDP med S-tillstånd, A åtgärder och diameter D, när T ≥ S 5 A. Här beklagar jämför den totala belöningen som uppnås av algoritmen med den totala förväntade belöningen av en optimal oändlig-horisont odiskonterad genomsnittlig belöning politik, i tidshorisonten T. Detta resultat förbättras över den bästa tidigare kända övre gränsen av Õ (DS ε AT ) som uppnås av någon algoritm i denna inställning, och matchar beroendet av S i den etablerade nedre gränsen av ∂( ε DSAT ) för detta problem. Våra tekniker innebär att bevisa några nya resultat om antikoncentrationen av Dirichlet distribution, som kan vara av oberoende intresse.
Nyligen lyckades författarna till REF uppnå en ångergaranti för Õ(D ε SAT ), men endast giltig när T ≥ S 5 A.
Posterior sampling for reinforcement learning: worst-case regret bounds
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}