Markov Decision Process
En matematisk ramme til modellering af beslutningstagning i stokastiske miljøer, defineret ved tilstande, handlinger, overgangssandsynligheder, belønninger og en diskonteringsfaktor.
Kort fortalt
En model der beskriver, hvordan en agent kan træffe beslutninger i en situation med usikkerhed, hvor hver handling påvirker både den øjeblikkelige belønning og fremtidige tilstande.
- Kategori
- begreb
- Niveau
- øvet
- Udtale
- /ˈmɑːrkɒf dɪˈsɪʒən ˈprɒsɛs/
Betydninger
1- 1
En Markov-beslutningsproces (MDP) er en diskret tidsstokastisk kontrolproces, der giver en formel ramme for modellering af beslutningstagning i situationer, hvor resultater er delvist tilfældige og delvist under kontrol af en beslutningstager.
- I et Markov Decision Process vælger agenten en handling baseret på den nuværende tilstand, hvorefter miljøet overgår til en ny tilstand og giver en belønning. — Sutton & Barto, 2018
- MDP-rammen forudsætter Markov-egenskaben, dvs. at fremtiden kun afhænger af den aktuelle tilstand, ikke af tidligere historik. — Sutton & Barto, 2018
Hvornår bruges det
MDP'er anvendes primært inden for forstærkningslæring til at formalisere problemer, hvor en agent skal lære en optimal politik gennem interaktion med miljøet. De danner grundlag for algoritmer som Q-learning og policy gradient-metoder.
Formel
(S, A, P, R, γ)Kodeeksempel
class SimpleMDP:
def __init__(self):
self.states = [0, 1]
self.actions = [0, 1] # 0: stay, 1: move
self.transitions = {
(0, 0): [(1.0, 0, 0)],
(0, 1): [(0.8, 1, 1), (0.2, 0, 0)],
(1, 0): [(1.0, 1, 0)],
(1, 1): [(0.9, 0, 1), (0.1, 1, 0)]
}
def step(self, state, action):
import random
outcomes = self.transitions[(state, action)]
prob, next_state, reward = random.choices(outcomes, weights=[p for p,_,_ in outcomes])[0]
return next_state, rewardEt simpelt MDP med to tilstande (0 og 1) og to handlinger (bliv eller flyt). Hvert (tilstand, handling)-par har en liste af mulige udfald med sandsynligheder.
Oprindelse
Opkaldt efter den russiske matematiker Andrej Markov (1856-1922), og 'beslutningsproces' henviser til sekventiel beslutningstagning.