Markow-Entscheidungsproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Die Lösung eines MEP ist eine Strategie , die zu jedem Zustand die Aktion ausgibt, mit der der Gewinn über die Zeit maximiert wird. Bekannte Lösungsverfahren sind unter anderem das Value-Iteration-Verfahren und Bestärkendes Lernen.

Weblinks[Bearbeiten | Quelltext bearbeiten]