Markov-Entscheidungsproblem

Bei dem Markow-Entscheidungsproblem (MEP, auch Markow-Entscheidungsprozess) 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 Markov-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₀), wobei

• S eine Menge von Zuständen,
• A eine Menge von Aktionen,
• T eine Abbildung $T: S \times A \times S \rightarrow P(S)$ 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: S \rightarrow R$ die Belohnungsfunktion ist, die jedem Zustand eine Belohnung zuordnet und
• p₀ die Startverteilung ist, die zu jedem Zustand angibt, wie wahrscheinlich es ist, in diesem Zustand zu starten.

Lösung

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

Weblinks

PPT-Vortrag (englisch)