imported>Dk1909: gr

2026-04-02T15:06:02Z

Neue Seite

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

Der Name geht zurück auf die [[Markow-Kette]], die der russische Mathematiker [[Andrei Andrejewitsch Markow (Mathematiker, 1856)|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 [[schwache Markoweigenschaft|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 [[Software-Agent|Agenten]], der sich zwischen mehreren möglichen Aktionen entscheiden kann und positive oder negative Belohnungen als Rückmeldung erhält.

== Übersicht ==
Das Modell eines Markow-Entscheidungsprozesses hat mehrere Zustände und mehrere Aktionen. Der Prozess befindet sich zum Zeitpunkt <math>t</math> in einem bestimmten Zustand <math>s=s_t</math>. Dann führt eine Aktion <math>a=a_t</math> dazu, dass der Prozess mit der Wahrscheinlichkeit <math>p</math> zum Zeitpunkt <math>t+1</math> einen bestimmten Folgezustand <math>s'=s_{t+1}</math> erreicht. Dabei gilt die Markow-Annahme: Die Zustände haben kein Gedächtnis, d. h., die Wahrscheinlichkeit <math>p</math> ist nur von den Zuständen <math>s</math> und <math>s'</math> abhängig und nicht von Vorgängern von <math>s</math>. Der Zustandsübergang kann zu einer positiven oder negativen Belohnung <math>r(s,s')</math> führen.

Wenn alle Zustände, alle Aktionen und alle Übergangswahrscheinlichkeiten bekannt sind, kann die optimale Strategie für den Agenten mit dem [[Optimalitätsprinzip von Bellman]] berechnet werden. Eine Methode dazu ist die [[dynamische Programmierung]], die auf [[Rückwärtsinduktion]] beruht.

Auf diesen Grundlagen bauen Methoden auf, die beim bestärkenden Lernen verwendet werden, um eine [[Strategie (Spieltheorie)|Strategie]] zu erlernen, mit der ein [[Software-Agent]] seine Aktionen so wählt, dass er von seiner Umwelt möglichst viele Belohnungen erhält.<ref name="geron" details="743–747">{{Literatur |Autor=Aurélien Géron |Titel=Praxiseinstieg Machine Learning |Auflage=3 |Verlag=dpunkt Verlag |Ort=Heidelberg |Datum=2023 |ISBN=978-3-96009-212-4}}</ref>

== Formale Definition ==
[[Datei:Markov Decision Process.svg|mini|Beispiel für ein einfaches MEP mit drei Zuständen (grüne Kreise), zwei Aktionen (orange Kreise) und zwei Belohnungen (orange Pfeile)]]
Ein MEP ist ein Tupel <math>(S,A,T,r, p_0)</math>, wobei
* <math>S</math> eine Menge von Zuständen,
* <math>A</math> eine Menge von Aktionen,
* <math>T</math> das ''Aktionsmodell'' (auch Transitionswahrscheinlichkeit) <math>T\colon S \times A \times S \rightarrow [0,1]</math> ist, so dass <math>T(s_t,a_t,s_{t+1}) = p(s_{t+1}|s_t,a_t)</math> die Wahrscheinlichkeit ist, von Zustand <math>s_t</math> durch Ausführen von Aktion <math>a_t</math> in den Zustand <math>s_{t+1}</math> zu gelangen.
* <math>r\colon S \times A \times S\rightarrow \R</math> die Belohnungsfunktion ist, die allen Zustandsübergängen eine Belohnung zuordnet und
* <math>p_0\colon S \rightarrow \R</math> die Startverteilung ist, die zu jedem Zustand angibt, wie wahrscheinlich es ist, in diesem Zustand zu starten.

Ein Agent wählt seine Aktionen mit Hilfe einer Strategie <math>\pi</math> aus. Die Strategie ordnet jedem Zustand genau eine Aktion zu.
* <math>\pi\colon S \rightarrow A; \pi(s_t) = a_t </math>

=== Optimale Strategie ===
Das Ziel ist, dass der Agent bei seinen Entscheidungen einer guten Strategie folgt: einer Funktion <math>\pi</math>, die für jeden Zustand <math>s</math> bestimmt, welche Aktion <math>\pi(s)</math> der Agent wählt. Wenn der Agent einer Strategie folgt, ist seine Aktion für jeden Zustand fest vorgegeben. Der Prozess verhält sich dann wie eine Markow-Kette.

Gesucht wird eine optimale Strategie <math>\pi^*</math>, die den Gewinn maximiert, den der Agent durch seine Aktionen erreicht. Das [[Optimalitätsprinzip von Bellman]] besagt, dass eine optimale Strategie in jedem Zustand <math>s</math> die Aktion <math>a</math> wählt, bei der zukünftig der größte Gewinn zu erwarten ist.

Der zukünftig zu erwartende Gewinn wird auch kumulierter Reward genannt. Er wird in der Regel als Summe aller Belohnungen <math>r</math> über unendlich viele Zustandsübergänge berechnet:

: <math>\mathbb{E}[G_t] = \mathbb{E}\left[\sum_{i=0}^\infty \gamma^i\cdot r_{t+i}\right]</math> mit <math> 0 \le \gamma <1</math>

Dabei ist <math>r_{t+i}</math> die Belohnung, die der Agent wahrscheinlich im Zeitschritt <math>t+1</math> erhält. Der [[Diskontierungsfaktor]] <math>\gamma</math> gewichtet Belohnungen, die kurzfristig erfolgen, höher als solche, die später erfolgen. Er sorgt auch dafür, dass die Summe für kontinuierliche Probleme (unendlich viele Zustandsübergänge) gegen einen Grenzwert konvergiert. Für <math>\gamma = 0</math> zählt nur die direkte Belohnung einer Aktion, alle zukünftigen Belohnungen werden ignoriert. Für <math>\gamma \rightarrow 1</math> erhalten zukünftige Belohnungen immer mehr Gewicht.<ref name="frochte" details="487–491">{{Literatur |Autor=Jörg Frochte |Titel=Maschinelles Lernen: Grundlagen und Algorithmen in Python |Auflage=3., überarbeitete und erweiterte Auflage |Verlag=Hanser |Ort=München |Datum=2021 |Reihe=Hanser eLibrary |ISBN=978-3-446-46144-4}}</ref><ref name="lorenz">{{Literatur |Autor=Uwe Lorenz |Titel=Reinforcement Learning: Aktuelle Ansätze verstehen – mit Beispielen in Java und Greenfoot |Auflage=2. Aufl. 2024 |Verlag=Springer Berlin Heidelberg |Ort=Berlin, Heidelberg |Datum=2024 |ISBN=978-3-662-68310-1 |Seiten=17}}</ref> Typische Werte für <math>\gamma</math> liegen zwischen 0,95 und 0,99.<ref name="geron" details="738" />

== Beispiel ==
Bei einem [[Determinismus|deterministischen]] Markow-Entscheidungsproblem führt jede Aktion zu genau einem Folgezustand. Ein solches Problem liegt vor, wenn ein Roboter durch ein Labyrinth zu einem Ziel navigieren soll. Dabei entspricht die Menge der Zustände der Menge der möglichen Positionen des Roboters und die Aktionen sind Schritte des Roboters in verschiedene Richtungen. Der Roboter erhält für den letzten Schritt, mit dem er das Ziel erreicht, eine positive Belohnung. Durch den Diskontierungsfaktor <math>\gamma</math> erreicht der Roboter den maximalen kumulierten Reward, wenn er mit möglichst wenigen Schritten das Ziel erreicht.

== Algorithmen ==
Die folgenden Algorithmen sind Beispiele dafür, wie mit der [[Dynamische Programmierung|dynamischen Programmierung]] ein komplexes Problem [[Iteration|iterativ]] gelöst werden kann. Sie können auf MEPs angewendet werden, bei denen die Anzahl von Zuständen und Aktionen endlich ist und alle Transaktionswahrscheinlichkeiten und Belohnungen bekannt sind. Für solche MEPs können sie eine optimale Strategie finden oder überprüfen. Sie bilden deshalb die mathematische Grundlage für eine Reihe von Algorithmen, die beim [[Bestärkendes Lernen|bestärkenden Lernen]] zum Lösen von ähnlichen Problemen eingesetzt werden.

=== Value-Iteration-Algorithmus ===
Das Optimalitätsprinzip von Bellman beschreibt den optimalen Wert des aktuellen Zustands als maximal zu erwartenden kumulierten Reward. Dieser Zustandswert entspricht der Summe aus der durchschnittlichen Belohnung, die im aktuellen Zustand mit der bestmöglichen Aktion erreicht wird und allen zukünftigen Belohnungen, die zu erwarten sind, wenn der Agent auch in allen Folgezuständen die jeweils bestmögliche Aktion ausführt.

Daraus hat Bellman eine rekursive Formel für den Value-Iteration-Algorithmus abgeleitet, mit dem man den optimalen Zustandswert für jeden möglichen Zustand abschätzen kann:

: <math> V_{i+1}(s) := \max_a \left\{ \sum_{s'} P_a(s,s') \left( R_a(s,s') + \gamma V_i(s') \right) \right\} </math> für alle <math>s</math>

Darin sind <math>i</math> die Nummer des aktuellen Durchlaufs und <math>V_{i+1}(s)</math> der geschätzte Zustandswert für <math>s</math> im Durchlauf <math>i+1</math>. Der erste Durchlauf beginnt im Zustand <math>s</math>, mit <math>i = 0</math> und allen Schätzwerten auf <math>0</math>. In jedem Durchlauf werden die Schätzungen <math>V_{i+1}</math> für alle Zustände <math>s</math> basierend auf den Schätzungen des vorigen Durchlaufs neu berechnet. Mit genügend Wiederholungen konvergieren die Schätzungen zu den Zustandswerten, die mit einer optimalen Strategie erreicht werden können.<ref name="geron" details="745,746" />

=== Q-Wert-Iterationsalgorithmus ===
Bellman fand auch eine Formel für einen ähnlichen Algorithmus, mit dem man die optimalen Zustands-Aktions-Werte, auch Q-Werte (Qualitätswerte) genannt, abschätzen kann:

: <math> Q_{i+1}(s,a) := \sum_{s'}P_a(s,s')\left\{R_a(s,s') + \gamma\max_a \left( Q_i(s',a') \right) \right\} </math> für alle <math>(s,a)</math>
Das Vorgehen entspricht dem für den Value-Iteration-Algorithmus. Wenn der Q-Wert-Iterationsalgorithmus die optimalen Q.Werte gefunden hat, steht die optimale Strategie <math>\pi^*(s)</math> des Agenten fest. Dabei wählt er in jedem Zustand die Aktion, die für diesen Zustand den höchsten Q-Wert hat.<ref name="geron" details="746,747" />

== Weblinks ==
* [http://ais.informatik.uni-freiburg.de/teaching/ss03/ams/DecisionProblems.pdf PPT-Vortrag (englisch)] (PDF; 739 kB)

== Einzelnachweise ==
<references />

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Logik]]

Markow-Entscheidungsproblem - Versionsgeschichte

imported>Dk1909: gr