Markov-Entscheidungsprozess (MDP)

Kernbestandteile eines MDP

Ein MDP wird in der Regel durch mehrere Schlüsselkomponenten definiert:

• Zustände (S): Eine Reihe von möglichen Situationen oder Konfigurationen, in denen sich der Agent befinden kann. Zum Beispiel die Position eines Roboters in einem Raum oder der Lagerbestand eines Produkts.
• Handlungen (A): Eine Reihe von Wahlmöglichkeiten, die dem Agenten in jedem Zustand zur Verfügung stehen. Zum Beispiel die Richtung, in die sich ein Roboter bewegen kann, oder die Menge eines zu bestellenden Produkts.
• Übergangswahrscheinlichkeiten (P): Die Wahrscheinlichkeit, von einem Zustand in einen anderen zu gelangen, nachdem eine bestimmte Handlung ausgeführt wurde. Dies spiegelt die Unsicherheit in der Umgebung wider. Der Versuch, sich vorwärts zu bewegen, kann zum Beispiel in 90 % der Fälle gelingen und in 10 % der Fälle scheitern (an Ort und Stelle bleiben oder gegen ein Hindernis stoßen).
• Belohnungen (R): Ein numerisches Signal, das der Agent erhält, wenn er aufgrund einer Aktion von einem Zustand in einen anderen wechselt. Die Belohnungen zeigen an, wie wünschenswert der Übergang unmittelbar ist. Das Ziel ist in der Regel, die kumulierte Belohnung über die Zeit zu maximieren.
• Strategie (π): Die Strategie des Agenten, die vorgibt, welche Aktion in jedem Zustand zu wählen ist. Das Ziel beim Lösen eines MDP ist es normalerweise, eine optimale Strategie zu finden, die den erwarteten langfristigen Gewinn maximiert. Techniken aus dem Deep Reinforcement Learning werden häufig eingesetzt, um solche Strategien in komplexen Umgebungen zu finden.

Die Markov-Eigenschaft

Ein entscheidendes Merkmal von MDPs ist die Markov-Eigenschaft. Diese Annahme besagt, dass der zukünftige Zustand und die Belohnung nur vom aktuellen Zustand und der durchgeführten Aktion abhängen, nicht aber von der Abfolge der Zustände und Aktionen, die zum aktuellen Zustand geführt haben. Im Grunde genommen enthält der aktuelle Zustand alle relevanten Informationen aus der Vergangenheit, um eine optimale Entscheidung für die Zukunft zu treffen. Das vereinfacht den Modellierungsprozess erheblich. Weitere Details findest du auf der Wikipedia-Seite zur Markov-Eigenschaft.

Anwendungen in der realen Welt

MDPs bilden die theoretische Grundlage für die Lösung vieler sequenzieller Entscheidungsprobleme in der realen Welt:

• Robotik Navigation: Ein Roboter entscheidet, wie er sich bewegen soll, um ein Ziel zu erreichen und dabei Hindernissen auszuweichen. Zustände sind die möglichen Standorte und Ausrichtungen des Roboters, Aktionen sind Bewegungsbefehle (vorwärts, abbiegen), Übergänge sind Wahrscheinlichkeiten für eine erfolgreiche Bewegung und Belohnungen können positiv für das Erreichen des Ziels und negativ für Kollisionen oder die benötigte Zeit sein. Das gilt auch für komplexe Systeme wie autonome Fahrzeuge.
• Bestandsmanagement: Bestimmung der optimalen Bestellpolitik für Produkte mit unsicherer Nachfrage. Zustände stellen Lagerbestände dar, Aktionen sind Bestellmengen, Übergänge hängen von der stochastischen Kundennachfrage ab, und Belohnungen gleichen Umsatzerlöse mit Bestell- und Lagerkosten aus. Dies ist entscheidend für Anwendungen wie KI für ein intelligenteres Bestandsmanagement im Einzelhandel. Akademische Arbeiten, die sich mit MDPs beschäftigen, findest du unter Operations Research.
• Spiele spielen: KI-Agenten, die lernen, Spiele wie Schach oder Go zu spielen, bei denen der Zustand die Konfiguration des Brettes ist, Aktionen legale Züge sind und Belohnungen für das Gewinnen des Spiels vergeben werden. Die Arbeit von DeepMind an AlphaGo zeigt die Leistungsfähigkeit von RL in solchen Bereichen.

Relevanz in KI und maschinellem Lernen

MDPs formalisieren die Problemstruktur für die meisten Reinforcement Learning-Aufgaben. Im Gegensatz zum überwachten Lernen (Lernen aus markierten Daten) oder zum unüberwachten Lernen (Finden von Mustern) konzentriert sich RL auf das Lernen durch Interaktion und Feedback (Belohnungen), um ein langfristiges Ziel zu erreichen. Das macht MDPs zu einem natürlichen Rahmen. Dieses Paradigma ist entscheidend für das Training von Agenten, die in dynamischen Umgebungen eine Reihe von Entscheidungen treffen müssen, was in Bereichen wie Computer Vision (CV) für Aufgaben, die aktive Wahrnehmung oder Interaktion erfordern, immer wichtiger wird. Das übergeordnete Ziel in diesem Bereich des maschinellen Lernens (ML) ist oft die Optimierung der langfristigen Genauigkeit oder des Aufgabenerfolgs über das Belohnungssignal.

Beziehung zu anderen Konzepten

MDPs sind zwar mit Sequenzmodellen wie Hidden Markov Models (HMMs) verwandt, unterscheiden sich aber dadurch, dass ein Agent aktiv Handlungen auswählt, um Übergänge zu beeinflussen und Belohnungen zu maximieren, während HMMs typischerweise Systeme modellieren, bei denen Zustandsübergänge auf der Grundlage von Wahrscheinlichkeiten stattfinden, ohne dass ein Agent die Kontrolle über seine Handlungen hat. Zur Lösung von MDPs werden oft Techniken wie Dynamische Programmierung (wenn das Modell vollständig bekannt ist) oder RL-Algorithmen wie Q-Learning und Policy-Gradienten-Methoden eingesetzt, wenn das Modell unbekannt ist. Diese Methoden stützen sich oft auf die Bellman-Gleichung, um den Wert eines Zustands mit den Werten der nachfolgenden Zustände in Beziehung zu setzen. Tools wie OpenAI Gym (jetzt Gymnasium) bieten Umgebungen zum Entwickeln und Testen von RL-Agenten, die oft mit Frameworks wie PyTorch. Plattformen wie Ultralytics HUB, die verschiedene KI-Workflows unterstützen, können die Verwaltung des Trainings und der Modellbereitstellung solch komplexer Modelle erleichtern, darunter auch solche, die moderne Modelle wie Ultralytics YOLO. Ein umfassendes Verständnis findest du in Ressourcen wie dem RL-Buch von Sutton & Barto.