Markow-Entscheidungsproblem

Bei dem Markow-Entscheidungsproblem (MEP, auch Markow-Entscheidungsprozess oder MDP für englisch Markov decision process) handelt es sich um ein Modell für Entscheidungsprobleme mit unsicheren Ergebnissen. Erstmals beschrieben wurde das Modell 1957 von Richard Bellman. Seitdem findet es auf vielen Gebieten Beachtung, darunter Ökologie, Ökonomie, Gesundheitsversorgung, Telekommunikation und bestärkendes Lernen.

Der Name geht zurück auf die Markow-Kette, die der russische Mathematiker Andrei Andrejewitsch Markow im frühen 20. Jahrhundert untersucht hat. Eine Markow-Kette beschreibt einen stochastischen Prozess ohne Gedächtnis. Dieser Prozess hat eine vorgegebene Anzahl von Zuständen. Der Prozess wechselt zufällig von dem aktuellen Zustand in einen Folgezustand. Dabei gilt die Markow-Annahme: Die Wahrscheinlichkeit für einen Zustandsübergang hängt nur von dem aktuellen Zustand und dem Folgezustand ab und nicht von früheren Zustandsübergängen.

Der Markow-Entscheidungsprozess erweitert die Markow-Ketten um einen Agenten, der sich zwischen mehreren möglichen Aktionen entscheiden kann und positive oder negative Belohnungen als Rückmeldung erhält.