Markovbeslissingsprocessen

Markovbeslissningsprocessen (MDP) är en matematisk modell för beslutsfattande i situationer där resultatet påverkas av både beslut och slump. Den beskriver en agent som rör sig mellan tillstånd i ett tillståndsrum och väljer åtgärder som styr övergångarna till nästa tillstånd och de erhållna belöningarna. En MDP består av ett tillståndsrum S, ett åtgärdsrum A, en övergångsfunktion P(s'|s,a) som anger sannolikheten att gå från tillståndet s till s' när åtgärden a vidtas, och en belöningsfunktion R(s,a,s') som anger belöningen vid övergången. Modellen antar Markov-egenskapen: framtida utveckling beror endast på nuvarande tillstånd och vald åtgärd, inte på tidigare historia. Ofta används en diskonteringsfaktor γ ∈ [0,1) som viktar framtida belöningar.

En politik π specificerar vilka åtgärder som skall väljas i varje tillstånd: π(a|s) ger sannolikheten att vidta åtgärden a när tillståndet är s. Målet är att hitta en policy som maximerar den förväntade diskonterade belöningssumman: E[ sum_t γ^t R(s_t,a_t,s_{t+1}) ]. Värdefunktionerna V^π(s) och Q^π(s,a) beskriver den förväntade belöningen under en given policy. Bellman-ekvationerna relaterar dessa rekursivt: V^π(s) = ∑_a π(a|s) ∑_{s'} P(s'|s,a) [ R(s,a,s') + γ V^π(s') ], och V*(s) = max_a ∑_{s'} P(s'|s,a) [ R(s,a,s') + γ V*(s') ]. Den optimala policyn π* uppnår V*.

Metoder för att hitta bra policys inkluderar modellbaserad dynamisk programmering såsom värdeiteration och policyiteration, samt modellfria metoder som Q-lärande och SARSA. Vid stora eller kontinuerliga tillstånd används ofta funktionell approximation. Tillämpningar finns inom robotik, logistik, planering, ekonomi och operativ forskning. MDP:n utgör grunden för förstärkningsinlärning och relaterade metoder som lär policyer från interaktion med omgivningen. Vid osäkerhet i observationer används ofta utvidgningar som POMDP.