Markovbeslutsprocesser

Markovbeslutsprocesser (MDP) är en teoretisk ram för att modellera beslut i osäkra miljöer där nästa tillstånd beror på nuvarande tillstånd och den valda åtgärden. En MDP består av mängderna av tillstånd S och åtgärder A, övergångsfunktionen P(s'|s,a) som ger sannolikheten att gå till tillståndet s' när åtgärden a utförs i s, samt en belöningsfunktion R(s,a,s') eller R(s,a) som ger omedelbar belöning vid övergången. En diskontveringsfaktor γ mellan 0 och 1 används ofta för att ge större vikt åt närvarande belöningar än framtida.

Målet i en MDP är att hitta en policy π som ger den största förväntade avkastningen över tid. En policy kan vara deterministisk eller stokastisk, och kan vara stationär eller tidsvarierande. Den vanligaste måttenheten är en värdefunktion, till exempel Vπ(s) = Eπ[sum_t γ^t R_t | s0 = s], vilken anger den förväntade avkastningen från tillståndet s under policyn π. Avledda funktioner som Qπ(s,a) beskriver förväntad avkastning om man i tillstånd s vidtar åtgärden a och följer π därefter. Bellman-ekvationerna kopplar samman värdefunktioner, policyn och övergångsmodellerna och används för att beräkna optimala policys.

Lösningar kan vara modellbaserade eller modellfria. Modellbaserade metoder, såsom value iteration och policyiteration, kräver fullständig kunskap om P och R. Modellfria metoder, ofta inom reinforcement learning, lär sig policyn direkt från interaktion med miljön. MDP används i robotik, spelteori, ekonomi och operationsforskning som grund för beslutsfattande under osäkerhet. Markaov-egenskapen innebär att framtiden beror endast på nuvarande tillstånd och handling, inte på historien.