I detta dokument behandlas användningen av en enkel bakre provtagningsalgoritm för att balansera prospektering och utnyttjande när man lär sig att optimera åtgärder som till exempel vid multiarmade banditproblem. Algoritmen, även känd som Thompson Provtagning och som sannolikhetsmatchning, ger betydande fördelar jämfört med den populära övre förtroende bundna (UCB) metoden, och kan tillämpas på problem med ändliga eller oändliga action utrymmen och komplicerade relationer mellan åtgärder belöningar. Vi gör två teoretiska bidrag. Den första upprättar en koppling mellan bakre provtagning och UCB-algoritmer. Detta resultat låter oss konvertera ånger gränser utvecklat för UCB algoritmer till Bayesian ånger gränser för bakre provtagning. Vårt andra teoretiska bidrag är en Bayesian ånger bundet för bakre provtagning som gäller brett och kan specialiseras på många modellklasser. Denna gräns beror på ett nytt begrepp som vi kallar eluderdimensionen, som mäter graden av beroende av handlingsvinster. Jämfört med UCB algoritm Bayesian ångrar gränser för specifika modellklasser, våra generella bundna matchar den bästa tillgängliga för linjära modeller och är starkare än den bästa tillgängliga för generaliserade linjära modeller. Vidare ger vår analys insikt i prestandafördelarna med bakre provtagning, vilka framhävs genom simuleringsresultat som visar prestanda som överträffar nyligen föreslagna UCB-algoritmer.
Genom REF, Thompson provtagning har samma Bayesian ångra.
Learning to Optimize Via Posterior Sampling
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}