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.

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.

Bearbeiten