Vi bevisar att den klassiska policy-itering metod (Howard 1960), inklusive Simplex metoden (Dantzig 1947) med den mest negativa-reducerad kostnad pivoting regel, är en starkt polynom-tid algoritm för att lösa Markov beslutsproblem (MDP) med en fast diskonteringsränta. Dessutom är den beräkningsmässiga komplexiteten hos policyiteringsmetoden (inklusive Simplexmetoden) överlägsen den enda kända, starkt polynomiska, inre punktalgoritm ([28] 2005) för att lösa detta problem. Resultatet är förvånande eftersom Simplex metoden med samma pivoting regel visade sig vara exponentiell för att lösa ett generellt linjär programmering (LP) problem, Simplex (eller enkel policy-itering) metod med minsta-index pivoting regel visades vara exponentiell för att lösa en MDP oavsett diskonteringsränta, och policy-iteringsmetoden visades nyligen vara exponentiell för att lösa en odiskonterad MDP. Vi utökar också resultatet till att lösa MDP med sub-stokastiska och övergående tillståndsannolikhet matriser.
REF visar att den policy iteration av diskonterade MDP är en form av dual simplex metod, som är starkt polynomial för motsvarande linjära program och slutar i körtid O ( A×S på 2 1−γ ).
The Simplex and Policy-Iteration Methods are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}