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 von Zustand aus zu erreichen, ist nur von abhängig und nicht von Vorgängern von .
Formale Definition Bearbeiten
Ein MEP ist ein Tupel , wobei
- eine Menge von Zuständen,
- eine Menge von Aktionen,
- das Aktionsmodell (auch Transitionswahrscheinlichkeit) ist, so dass die Wahrscheinlichkeit ist, von Zustand und Ausführung von Aktion in den Zustand zu gelangen.
- die Belohnungsfunktion ist, die jedem Übergang vom letzten zum aktuellen Zustand eine Belohnung zuordnet und
- die Startverteilung ist, die zu jedem Zustand angibt, wie wahrscheinlich es ist, in diesem Zustand zu starten.
Beispiel Bearbeiten
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 Bearbeiten
Die Lösung eines MEP ist eine Funktion , 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 Bearbeiten
- PPT-Vortrag (englisch) (PDF; 739 kB)