En kritisk fråga för tillämpningen av Markovs beslutsprocesser på realistiska problem är hur komplexa planeringsskalor med storleken på MDP är. I stokastiska miljöer med mycket stora eller oändliga tillståndsutrymmen kan traditionella planerings- och förstärkningsalgoritmer vara otillämpliga, eftersom deras körtid vanligtvis växer linjärt med tillståndsstorleken i värsta fall. I detta dokument presenterar vi en ny algoritm som, givet endast en generativ modell (en naturlig och gemensam typ av simulator) för en godtycklig MDP, utför on-line, nära optimal planering med en per-state körtid som inte har något beroende av antalet stater. Löptiden är exponentiell i horisonten (som endast beror på rabattfaktorn γ och den önskade graden av tillnärmning till den optimala politiken). Vår algoritm ger därmed en annan komplexitet kompromiss än klassiska algoritmer såsom värde iteration-snarare än skalning linjärt i både horisont tid och tillstånd rymdstorlek, vår körtid handel ett exponentiellt beroende av den förra i utbyte mot inget beroende av den senare. Vår algoritm är baserad på idén om sparsam provtagning. Vi bevisar att ett slumpmässigt urval av utseende-ahead träd som bara täcker en försvinnande bråkdel av det fulla utseende-ahead träd ändå räcker för att beräkna nära-optimala åtgärder från något tillstånd av en MDP. Praktiska implementationer av algoritmen diskuteras, och vi drar kopplingar till våra relaterade senaste resultat om att hitta en nästan bästa strategi från en viss klass av strategier i mycket stora delvis observerbara MDPs (Kearns, Mansour, & Ng. System för behandling av neural information 13, som ska visas).
Motiverad av resultatet i REF att körtiden för att beräkna den nästan optimala politiken i godtyckligt stora, ostrukturerade MDP inte beror på antalet stater, anser vi att MDP kan vara fullt tillämpligt i praktiken.
A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes
{'venue': 'Machine Learning', 'journal': 'Machine Learning', 'mag_field_of_study': ['Computer Science']}