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 $s'$ von Zustand $s$ aus zu erreichen, ist nur von $s$ abhängig und nicht von Vorgängern von $s$.

Formale Definition

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

• $S$ eine Menge von Zuständen,
• $A$ eine Menge von Aktionen,
• $T$ das Aktionsmodell (auch Transitionswahrscheinlichkeit) $T\colon S\times A\times S\rightarrow [0,1]$ ist, so dass $T(s,a,s')=p(s'|s,a)$ die Wahrscheinlichkeit ist, von Zustand $s$ und Ausführung von Aktion $a$ in den Zustand $s'$ zu gelangen.
• $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
• $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 liegt vor, wenn ein Roboter durch ein Labyrinth zu einem Ziel navigieren muss. Dabei ist die Menge der Zustände die Menge der Positionen des Roboters und die Aktionen sind die möglichen Richtungen, in die sich der Roboter bewegen kann.

Lösung

Die Lösung eines MEP ist eine Funktion $\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)