Markow-Entscheidungsproblem

Bei dem Markow-Entscheidungsproblem (MEP, auch Markow-Entscheidungsprozess oder MDP für Markov decision process) handelt es sich um ein nach dem russischen Mathematiker Andrei Andrejewitsch Markow benanntes Modell von Entscheidungsproblemen, bei denen der Nutzen eines Agenten von einer Folge von Entscheidungen abhängig ist. Bei den Zustandsübergängen gilt dabei die Markow-Annahme, d. h. die Wahrscheinlichkeit einen Zustand ${\displaystyle s'}$ von Zustand ${\displaystyle s}$ aus zu erreichen, ist nur von ${\displaystyle s}$ abhängig und nicht von Vorgängern von ${\displaystyle s}$.

Formale Definition

Ein MEP ist ein Tupel ${\displaystyle (S,A,T,r,p_{0})}$, wobei

• ${\displaystyle S}$ eine Menge von Zuständen,
• ${\displaystyle A}$ eine Menge von Aktionen,
• ${\displaystyle T}$ das Aktionsmodell (auch Transitionswahrscheinlichkeit) ${\displaystyle T\colon S\times A\times S\rightarrow [0,1]}$ ist, so dass ${\displaystyle T(s,a,s')=p(s'|s,a)}$ die Wahrscheinlichkeit ist, von Zustand ${\displaystyle s}$ und Ausführung von Aktion ${\displaystyle a}$ in den Zustand ${\displaystyle s'}$ zu gelangen.
• ${\displaystyle r\colon S\times A\times S\rightarrow \mathbb {R} }$ die Belohnungsfunktion ist, die jedem Übergang vom letzten zum aktuellen Zustand eine Belohnung zuordnet und
• ${\displaystyle p_{0}\colon S\rightarrow \mathbb {R} }$ die Startverteilung ist, die zu jedem Zustand angibt, wie wahrscheinlich es ist, in diesem Zustand zu starten.

Beispiel

Ein MEP l​iegt vor, w​enn ein Roboter d​urch ein Labyrinth z​u einem Ziel navigieren muss. Dabei i​st die Menge d​er Zustände d​ie Menge d​er Positionen d​es Roboters u​nd die Aktionen s​ind die möglichen Richtungen, i​n die s​ich der Roboter bewegen kann.

Lösung

Die Lösung eines MEP ist eine Funktion ${\displaystyle \pi \colon S\rightarrow A}$, die zu jedem Zustand die Aktion ausgibt, die den Gewinn über die Zeit maximiert. Bekannte Lösungsverfahren sind unter anderem das Value-Iteration-Verfahren und Bestärkendes Lernen.

Weblinks

• PPT-Vortrag (englisch) (PDF; 739 kB)