T hans papper anser att den effektiva exakta beräkningen av motsvarigheten till Gittins index för en finithorizon diskret-state bandit, som mäter för varje inledande tillstånd den genomsnittliga produktiviteten, ges av den maximala kvoten av förväntade totala diskonterade belöning intjänad till förväntad total diskonterad tid som kan uppnås genom ett antal på varandra följande pjäser stoppas vid den givna horisonten. Förutom att karakterisera optimal politik för det finita-horisontella enarmade banditproblemet, ger ett sådant index en suboptimal heuristisk indexregel för det oåtkomliga finita-horisontella multiarmade banditproblemet, som representerar den naturliga förlängningen av Gittins indexregeln (optimalt i det oändligt-horisontella fallet). Även om ett sådant finit-horizon index infördes i klassiskt arbete på 1950-talet, har undersökningen av dess effektiva exakta beräkning fått liten uppmärksamhet. I detta dokument introduceras en rekursiv adaptiv-grå algoritm med endast aritmetiska operationer som beräknar indexet i (pseudo-)polynom tid i problemparametrarna (antal projekttillstånd och tidshorisontslängd). I det särskilda fallet med ett projekt med begränsade övergångar per stat minskar komplexiteten antingen eller beror endast på tidshorisontens längd. Den föreslagna algoritmen jämförs i en beräkningsstudie mot den konventionella kalibreringsmetoden.
Se även REF för härledning av en finit-horisontell approximation av Gittins-indexet och relaterade beräkningsfrågor.
Computing a Classic Index for Finite-Horizon Bandits
{'venue': 'INFORMS J. Comput.', 'journal': 'INFORMS J. Comput.', 'mag_field_of_study': ['Computer Science']}