Abstrakt. Det restless bandit problemet är en av de mest välstuderade generaliseringar av den berömda stokastiska multi-armad bandit (MAB) problem i beslutsteori. I sin slutliga allmängiltighet är det restless bandit problemet känt för att vara PSPACE-Hard till approximation till någon icke trivial faktor, och få framsteg har gjorts i detta problem, trots dess betydelse i modellering aktivitet allokering under osäkerhet. I denna artikel, vi anser FEEDBACK MAB problem, där belöningen som erhålls genom att spela var och en av n oberoende armar varierar beroende på en underliggande på / av Markov process vars exakta tillstånd endast avslöjas när armen spelas. Målet är att utforma en policy för att spela armarna för att maximera den oändliga horisonten tid genomsnittlig förväntad belöning. Detta problem är också ett exempel på en delvis observable Markov Decision Process (POMDP), och är allmänt studerad i trådlös schemaläggning och obemannade luftfartyg (UAV) routing. Till skillnad från det stokastiska MAB-problemet medger FEEDBACK MAB-problemet inte giriga indexbaserade optimala strategier. Vi utvecklar en ny dualitetsbaserad algoritmisk teknik som ger en förvånansvärt enkel och intuitiv (2 + ) ungefärlig girig politik till detta problem. Vi visar att både när det gäller approximationsfaktor och beräkningseffektivitet är vår policy nära relaterad till Whittle-indexet, som i stor utsträckning används för dess enkelhet och effektivitet i beräkningen. Därefter definierar vi en multi-state generalization, att vi kallar MONOTONE bandits, som förblir subklass av restless bandit problem. Vi visar att vår politik förblir en 2- approximation i denna miljö, och vidare, vår teknik är tillräckligt robust för att införliva olika sido-spärrar som blockera pjäser, byta kostnader, och även modeller där bestämma tillståndet för en arm är en separat operation från att spela den. Vår teknik är också av oberoende intresse för andra rastlösa banditproblem, och vi ger ett exempel på icke förebyggande maskinpåfyllning. Det är intressant att lägga märke till att vår politik i detta fall ger en konstant faktorgaranti, medan Whittle-indexet bevisligen är mer polynomiskt sämre. Denna artikel kombinerar och generaliserar resultat som presenteras i två uppsatser [Guha och Munagala 2007b; Guha et al. 2009 ] som förekom vid FOCS '07 respektive SODA '09 konferenser, respektive. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning.
De problem som behandlas i REF är ett oändligt problem med rastlösa banditer.
Approximation algorithms for restless bandit problems
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}