Ein Markov-Entscheidungsprozess (MDP) ist ein mathematisches Modell für sequentielle Entscheidungsfindung bei unsicheren Ergebnissen. Es handelt sich um eine Art stochastischer Entscheidungsprozess, der häufig mit Methoden der stochastischen dynamischen Programmierung gelöst wird. Ursprünglich aus der Operations Research der 1950er Jahre stammend, haben MDPs seitdem Anerkennung in Bereichen wie Ökologie, Wirtschaft, Gesundheitswesen, Telekommunikation und Verstärkungslernen gewonnen. Im Verstärkungslernen modelliert das MDP-Framework die Interaktion zwischen einem lernenden Agenten und seiner Umgebung, die durch Zustände, Aktionen und Belohnungen gekennzeichnet ist, und bietet eine vereinfachte Darstellung wesentlicher Elemente von Herausforderungen der künstlichen Intelligenz, einschließlich von Ursache und Wirkung, Ungenauigkeit und expliziten Zielen.
Der Name leitet sich von seiner Verbindung zu Markov-Ketten ab, die von dem russischen Mathematiker Andrey Markov entwickelt wurden. Die "Markov"-Eigenschaft bezieht sich auf die zugrunde liegende Struktur, bei der Zustandsübergänge nur vom aktuellen Zustand und der Handlung abhängen, nicht von der vorherigen Geschichte. Der Prozess wird als "Entscheidungsprozess" pfählt, da er Entscheidungen beinhaltet, die diese Übergänge beeinflussen, und damit Markov-Ketten auf Entscheidungsfindung unter Unsicherheit erweitert.
Formelle Definition
Ein MDP wird typischerweise als ein 4-Tupel \(\(S, A, P_a, R_a\\)) definiert, wobei:
- \(S\) ist der Zustandsraum, der diskret oder kontinuierlich sein kann (z. B. die Menge der reellen Zahlen).
- \(A\) ist der Handlungsraum, mit \(A_s\), das die Menge der Handlungen kennzeichnet, die aus Zustand \(s\) verfügbar sind. Diese Menge kann ebenfalls diskret oder kontinuierlich sein.
- \(P_a(s, s')\) ist die Übergangswahrscheinlichkeit, dass die Handlung \(a\) im Zustand \(s\) zum Zeitpunkt \(t\) zum Zustand \(s'\) zum Zeitpunkt \(t+1\) führt. Für diskrete Zustände gilt \(P_a(s, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)\). Für stetige Zustandsräume wird die Wahrscheinlichkeit über ein Integral definiert, häufig bezüglich des Lebesgue-Maßes.
- \(R_a(s, s')\) ist die unmittelbare Belohnung (oder erwartete Belohnung), die nach der Ausführung der Handlung \(a\) beim Übergang von \(s\) zu \(s'\) erhalten wird. Die Belohnung ist im Allgemeinen eine Zufallsvariable.
Eine Politikfunktion \(\pi\) ist eine (möglicherweise probabilistische) Zuordnung vom Zustandsraum zum Handlungsraum, die angibt, welche Handlung in jedem Zustand ausgeführt werden soll.
Optimierungsziel
Das Ziel in einem MDP ist es, eine Politik \(\pi\) zu finden, die eine kumulative Funktion von Zufallsbelohnungen - in der Regel die erwartete diskontierte Summe über einen unendlichen Horizont - \(\mathbb{E}[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})]\\) maximiert, wobei \(\gamma \in [0, 1)\) ein Diskontierungsfaktor ist. Sobald eine Politik festgelegt ist, verhält sich das MDP wie eine Markov-Kette, da die Handlung in jedem Zustand durch \(\pi(s)\) bestimmt wird.
Gängige Lösungsmethoden umfassen dynamische Programmiertechniken wie Vertwertiteration und Politikiteration, die optimale Wertfunktionen oder Politiken berechnen. Diese Methoden sind grundlegend für Algorithmen des Reinforcement learning wie Q-Learning und SARSA.
Anwendungen
MDPs werden in einer Vielzahl von Bereichen angewendet. In der Ökonomie modellieren sie optimale Konsum- und Investitionsentscheidungen. Im Gesundheitswesen leiten sie die Behandlungsplanung unter Cous die Unsicherheit, wie die Behandlung chronischer Erkrankungen. In der Le Konferenz kommunikation optimieren sie Ressourcenzuweisung und Netzwerkvermittlung. In der Ökologie unterstützen sie Schutzstrategien für das Artenmanagement. In Machine learning sind MDPs zentral beim Verstärkungslernen, das Agenten ermöglicht, durch Interaktion mit Umgebungen zu lernen, wie in Robotik, Spie lösen und autonomen Systemen zu sehen.
Beziehung zum Verstarkurngslernen
Das Verstärungslernen (RL) verwendet das MDP-Framework, um die Agent Umgebungs-Interaktion zu formalisieren. Im RL kennt der Agent die Übergangswahrscheinlichkeiten oder Belohnungsfunktionen im Vorhinein nicht; stattdessen lernt er eine optimale Politik durch Versuch und Irrtum, indem er Stichproben von der Umgebung verwendet. Dies unterscheidet RL von klass[a] MDP-Lösung, die angenommenes Modellisten kenntren. Moderne RL, einschließlich tiefes Verstärungslernens, kombiniert MDPs mit Neural network Funktionsapproximatoren, um große Zustandräume zu handhaben, wie in Anwendungen wie Spielen und autonomen Fahren demonstriert.
Erweiterungen und Variationen
Ch Verlag für mehrere Erweiterungen die Limitationen des Grund-MDPs. Teil beobachtbare Markov-Entscheidungsprozesse (PQMW) befassen sich mit Situationen, in denen der Agent den vollständigen Zustand nicht direkt beobachten kann. Faktorisierte MDPs nutzen dann Struktur in Zustandvariablen, um die Skalierbarkeit zu verbessern. Multi-Agenten-MDPs erweitern das Framework auf mehrere Entscheidungsträger mit Energiewebereichndenen Zielen. Diese Variationen beibehalten die Kern-Markov-Eigenschaft, passen sich aber an komplexere reale Probleme an.
Historischer Kontext
Die Formalisierung von MDPs wirdiam zu Richard Bellman in den 1950er Jahren zugeschrieben, der auch die dynamische Programmierung entwickelte. Andrei Markovs frühere Arbeiten über stochastische Prozesse haben die Verwicklungen Schaffung der theoretischen Grundlagen. Seitdem sind MDPs zu einem Eckpfeiler des Operations Research und der künstlichen Intelligenz geworden und beeinflussen sowohl theoretische als auch angewandte Arbeiten zur sequenziellen Entscheidungsfindung.