Optimala lösningar på Markovs beslutsproblem kan vara mycket känsliga när det gäller sannolikheten för statsövergång. I många praktiska problem är uppskattningen av dessa sannolikheter långt ifrån exakt. Därför är skattningsfel begränsande faktorer vid tillämpningen av Markovs beslutsprocesser på verkliga problem. Vi anser att ett robust kontrollproblem för en ändlig-state, ändlig-aktion Markov beslutsprocess, där osäkerhet om övergångsmatriser beskrivs i termer av möjligen icke konvexa uppsättningar. Vi visar att perfekt dualitet håller för detta problem, och att det därför kan lösas med en variant av den klassiska dynamiska programmeringsalgoritmen, den "robust dynamiska programmeringen" algoritmen. Vi visar att ett särskilt val av osäkerhet sätter, med sannolikhet regioner eller entropi gränser, leder till både en statistiskt korrekt representation av osäkerhet, och en komplexitet av robust rekursion som är nästan samma som den klassiska rekursion. Därför kan robusthet läggas till på praktiskt taget ingen extra datorkostnad. Vi får liknande resultat för andra osäkerhetsuppsättningar, inklusive ett med ett begränsat antal möjliga värden för övergångsmatriserna. Vi beskriver i ett praktiskt vägplaneringsexempel fördelarna med att använda en robust strategi i stället för den klassiska optimala strategin; även om osäkerhetsnivån bara är grovt gissad ger den robusta strategin en mycket bättre och sämre beräknad restid.
I REF är övergångssannolikhetsfördelningen begränsad till att ligga nära den empiriska sannolikhetsfördelningen när det gäller entropi.
Ghaoui, L.: Robust control of Markov decision processes with uncertain transition matrices
{'venue': 'Operations Research', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}