Abstrakt. Vi studerar komplexiteten i en klass av Markov beslutsprocesser och, mer allmänt, stokastiska spel, kallas 1-exit Recursive Markov beslutsprocesser (1-RMDP) och enkla stokastiska spel (1-RSSGs) med strikt positiva belöningar. Dessa är en klass av ändligt presenterade countable-state nollsum stokastiska spel, med total förväntad belöning mål. De subsumerar standard ändstate MDP och Condons enkla stokastiska spel och motsvarar optimering och spelversioner av flera klassiska stokastiska modeller, med belöningar. Sådana stokastiska modeller uppstår naturligt som modeller av probabilistiska procedurprogram med rekursion, och de problem vi tar itu med är motiverade av målet att analysera den optimala/pessimala förväntade körtiden i en sådan miljö. Vi ger polynomiska tidsalgoritmer för 1-exit Recursive Markov beslutsprocesser (1-RMDP) med positiva belöningar. Specifikt visar vi att det exakta optimala värdet av både maximering och minimering 1-RMDP med positiva belöningar kan beräknas i polynom tid (detta värde kan vara ∞). För två spelare 1-RSSGs med positiva belöningar, visar vi en "stackless och minneslös" determinacy resultat, och visar att avgöra om spelet värdet är minst ett givet värde r är i NP  på coNP. Vi visar också att en samtidig strategi förbättring algoritm konvergerar till värdet och optimala strategier för dessa stokastiska spel. Om denna algoritm körs i P-tid är öppen, precis som dess klassiska version för ändliga SSGs. Vi observerar att 1-RSSG positiva belöning spel är "hårdare" än finit-state SSGs i flera sinnen.
I REF studerades 1-RMDP med ett annat mål, nämligen att optimera den totala förväntade belöningen i en miljö med positiva belöningar.
Recursive stochastic games with positive rewards
{'venue': 'In Proceedings of ICALP 2008, Part I, volume 5125 of LNCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}