I det budgeterade inlärningsproblemet får vi experimentera med en uppsättning alternativ (med en fast försöksbudget) med målet att välja ett enda alternativ med största möjliga förväntade vinst. Tillnärmningsalgoritmer för detta problem utvecklades av Guha och Munagala genom avrundning av ett linjärt program som par de olika alternativen tillsammans. I detta dokument presenterar vi ett index för detta problem, som vi kallar kvotindex, som också garanterar en konstant faktor approximation. Indexbaserade policyer har fördelen att ett enda nummer (dvs. Indexet) kan beräknas för varje alternativ oberoende av alla andra alternativ, och alternativet med det högsta indexet testas. Detta är jämförbart med det berömda Gittins-indexet för det diskonterade multiarmade banditproblemet. Kvotindexet har flera intressanta strukturella egenskaper. Först visar vi att det kan beräknas i starkt polynom tid. För det andra visar vi att med lämplig rabattfaktor är Gittins index och vårt kvotindex konstanta faktor approximationer av varandra, och därmed ger Gittins index också en konstant faktor approximation till det budgeterade inlärningsproblemet. Slutligen visar vi att kvotindexet kan användas för att skapa en indexbaserad policy som uppnår en O(1)-uppskattning för den finita horisontversionen av det flerarmade banditproblemet. Dessutom kräver politiken ingen kunskap om horisonten (där vi jämför dess resultat med en optimal strategi som är medveten om horisonten). Detta ger följande överraskande resultat: Det finns en indexbaserad policy som uppnår en O(1)-uppskattning för det multi-armade banditproblemet, omedveten om den underliggande rabattfaktorn.
Goel och Al. REF införde en indexpolitik, liknande Gittins indexpolicy, med konstant tillnärmning för tidshorisonten som begränsade MAB-problemet.
The Ratio Index for Budgeted Learning, with Applications
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}