Markow-Entscheidungsproblem

Markow-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 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,p0), 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
  • p0 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)


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • MEP — Die Abkürzung MEP steht für: Markow Entscheidungsproblem, Modell von Entscheidungsproblemen Landkreis Meppen (Kfz Kennzeichen) Message Exchange Pattern, siehe Web Services Description Language Ministery of Environmental Protection of the People s …   Deutsch Wikipedia

  • Berechnungstheorie — Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen… …   Deutsch Wikipedia

  • Church'sche These — Die Church Turing These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing berechenbaren Funktionen ist genau die Klasse der… …   Deutsch Wikipedia

  • Churchsche These — Die Church Turing These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing berechenbaren Funktionen ist genau die Klasse der… …   Deutsch Wikipedia

  • Rekursionstheorie — Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen… …   Deutsch Wikipedia

  • Theorie der Berechenbarkeit — Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen… …   Deutsch Wikipedia

  • These von Church — Die Church Turing These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing berechenbaren Funktionen ist genau die Klasse der… …   Deutsch Wikipedia

  • Berechenbarkeitstheorie — Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere damit, welche Probleme mit Hilfe einer Maschine (genauer: eines… …   Deutsch Wikipedia

  • Church-Turing-These — Die Church Turing These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing berechenbaren Funktionen ist genau die Klasse der… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”