Markov-Entscheidungsprozesse verstehen: Ein Leitfaden zur Lösung von CS7644 Assignment 4

Einführung in Markov-Entscheidungsprozesse (MDPs)

Markov-Entscheidungsprozesse (MDPs) sind ein grundlegendes Werkzeug im Reinforcement Learning (RL), um Entscheidungsfindung in unsicheren Umgebungen zu modellieren. In diesem Tutorial zeigen wir dir, wie du zwei interessante MDPs entwirfst, sie mit Value Iteration und Policy Iteration löst und schließlich einen RL-Algorithmus wie Q-Learning anwendest. Dabei greifen wir auf aktuelle Beispiele aus der Schulwelt und Gaming-Trends zurück, um die Konzepte greifbar zu machen – perfekt für dein CS7644 Assignment 4.

Was ist ein MDP?

Ein MDP besteht aus einer Menge von Zuständen S, Aktionen A, einer Übergangsfunktion T(s, a, s'), einer Belohnungsfunktion R(s, a, s') und einem Diskontfaktor γ. Ziel ist es, eine Policy π zu finden, die die erwartete kumulative Belohnung maximiert. Stell dir vor, du planst deine Lernstrategie für eine Woche: Jeder Tag ist ein Zustand, deine Lernmethoden (z. B. Karteikarten, Übungen) sind Aktionen, und die Note in der Prüfung ist die Belohnung. Das ist ein MDP!

Zwei MDPs entwerfen – klein und groß

Für dein Assignment musst du zwei MDPs entwickeln: eines mit wenigen Zuständen („klein“) und eines mit vielen („groß“). Vermeide Grid-World-Probleme – sei kreativ! Hier sind zwei Beispiele, die du anpassen kannst.

Kleines MDP: Lernplan für eine Prüfung

Zustände: S = {Anfang, Gelernt, Überfordert, Bestanden}. Aktionen: A = {Lernen, Pause machen}. Übergänge: Wenn du lernst, gehst du mit 80 % Wahrscheinlichkeit zu „Gelernt“ und mit 20 % zu „Überfordert“. Machst du Pause, bleibst du oft im selben Zustand. Belohnungen: „Bestanden“ gibt +100, „Überfordert“ −10. Dieses MDP ist klein (4 Zustände) und ideal für den Einstieg – ähnlich wie eine einfache Entscheidung im Schulalltag.

Großes MDP: Charakterentwicklung in einem RPG

Stell dir ein Rollenspiel vor, in dem dein Charakter Fähigkeiten trainiert. Zustände sind Kombinationen aus Stufen (1–10) und Skill-Leveln (Niedrig, Mittel, Hoch) – das ergibt 30 Zustände. Aktionen: Trainieren, Kämpfen, Ausruhen. Übergänge sind probabilistisch: Training erhöht Fertigkeiten, Kämpfen bringt Erfahrung, aber auch Risiko. Belohnungen: Kämpfen gibt sofortige EP, Training verbessert langfristige Werte. Dieses MDP ist „groß“ (30 Zustände) und spiegelt typische Gaming-Mechaniken wider – ein Trend, den viele Studierende kennen.

MDPs lösen mit Value Iteration und Policy Iteration

Jetzt implementierst du beide Algorithmen. Value Iteration aktualisiert iterativ den Wert jedes Zustands, bis die Änderung unter einem Schwellwert ε liegt. Policy Iteration wechselt zwischen Policy-Evaluation und Policy-Improvement, bis die Policy stabil ist. Für das kleine MDP konvergiert Value Iteration oft in 10–20 Iterationen, Policy Iteration in 3–5. Beim großen MDP (30 Zustände) brauchst du vielleicht 50–100 Iterationen. Teste verschiedene ε-Werte (z. B. 1e-6) und dokumentiere die Konvergenzgeschwindigkeit. Warum ist Policy Iteration schneller? Weil sie direkt die Policy verbessert, während Value Iteration alle Zustandswerte feinjustiert. Beide sollten zur gleichen optimalen Policy führen – ein wichtiger Check für deine Reinforcement-Learning-Aufgabe.

Reinforcement Learning ohne Modell: Q-Learning

In der Realität kennst du oft die Übergangswahrscheinlichkeiten nicht. Dann kommt Q-Learning, ein modellfreier RL-Algorithmus, ins Spiel. Du lässt den Agenten die MDPs erkunden und aktualisiert die Q-Werte mit der Bellman-Gleichung. Für das kleine MDP reichen 500 Episoden mit ε-gieriger Exploration (ε = 0.1). Für das große MDP brauchst du 5000 Episoden und einen abklingenden ε-Wert. Vergleiche die Ergebnisse: Q-Learning sollte nahe an die optimale Policy herankommen, aber wegen der Exploration etwas langsamer sein. Zeige in deiner Analyse, wie die Anzahl der Zustände die Lernkurve beeinflusst – ein zentraler Punkt in deinem CS7644 Assignment 4.

Trends und Praxisbezug

MDPs sind nicht nur Theorie – sie stecken in vielen KI-Anwendungen von heute. Zum Beispiel nutzen Empfehlungssysteme auf Streaming-Plattformen MDPs, um dir personalisierte Inhalte vorzuschlagen. Oder in der Finanzwelt modellieren sie Handelsstrategien. Auch in autonomen Fahrzeugen entscheiden MDPs über Spurwechsel. Indem du diese Verbindungen in deiner Analyse zeigst, machst du deine Arbeit relevant und interessant.

Fazit

Mit diesem Leitfaden hast du eine solide Grundlage, um dein Assignment zu meistern. Denk daran: Wähle originelle MDPs, dokumentiere deine Experimente genau und erkläre, warum deine Ergebnisse Sinn ergeben. Viel Erfolg bei deiner MDP-Analyse!