Zurück zum Lernbereich

Strategien entwickeln (Q-Learning & MDPs)

Strategien, gelernt durch Trial and Error — die formale Version dessen, was jedes Kind tut.

  • Grundlagen
  • 10 min
  • Fortgeschritten

Einfache Sprache

Diese Vorschau ist in Einfacher Sprache. Das ganze Portal gibt es auch in Einfacher Sprache. Du kannst oben die Sprache wechseln. Oder nutze den Knopf unten. Unsere Texte in Einfacher Sprache entstehen KI-gestützt und werden redaktionell begleitet. Sie orientieren sich an den Grundprinzipien der Leichten Sprache, sind aber keine geprüfte Leichte Sprache: Eine Prüfgruppe von Menschen mit Lernschwierigkeiten prüft sie nicht.

Vorschau: Lernen durch Belohnung

Was ist Q-Learning?

Q-Learning ist eine Lernmethode. Ein Agent ist ein KI-Programm. Es probiert verschiedene Aktionen aus. Es bekommt Belohnungen für gute Aktionen. So verbessert es seine Strategie.

Die Q-Tabelle

Der Agent führt eine Tabelle. Diese Tabelle heißt Q-Tabelle. In der Tabelle steht: Wie gut ist Aktion X in Zustand Y? Der Agent sucht immer die Aktion mit dem höchsten Wert.

Erkunden oder nutzen?

Der Agent muss wählen. Er kann bekannte gute Aktionen nutzen. Er kann aber auch neue Aktionen ausprobieren. Das nennt man Exploration. Exploration bedeutet: neue Wege erkunden. So findet er vielleicht bessere Strategien.

Du kennst bereits Agenten, Umgebungen, Zustände, Aktionen und Belohnungen aus dem RL-Grundlagenartikel. Aber wie entscheidet der Agent tatsächlich, was er tun soll? Q-Learning gibt ihm einen einfachen Buchführungstrick: eine Tabelle, die festhält, wie vielversprechend jedes Zustand-Aktions-Paar bisher war.

In diesem Artikel lernst du das mathematische Gerüst (MDP), das die Spielregeln definiert, den Algorithmus (Q-Learning), der die beste Strategie findet, und den Balanceakt (Exploration vs. Exploitation), der den Agenten davor bewahrt, bei einer mittelmäßigen Strategie stecken zu bleiben.

Die Spielregeln — Markov Decision Process

Definition

Markov Decision Process (MDP)

Analogie

Stell dir ein Brettspiel vor: Das Spielbrett definiert alle möglichen Felder (Zustände), die Regeln bestimmen erlaubte Züge (Aktionen), Würfelwürfe erzeugen Übergangswahrscheinlichkeiten, Siegpunkte sind Belohnungen, und der Diskontfaktor ist wie menschliche Ungeduld — hättest du lieber 10 Euro heute oder 11 Euro nächste Woche?

Das Brettspiel-Bild hat Grenzen: Reale Umgebungen passen nicht immer perfekt in das MDP-Schema, besonders wenn der Agent nicht alles beobachten kann. Für den Einstieg ist das Modell aber ein mächtiges Werkzeug. Stell dir als Umgebung ein einfaches 4×4-Gitter vor:

Start Oben links — hier beginnt der Agent
Ziel (+10) Unten rechts — Belohnung von +10 Punkten
Falle (-10) Position (2,2) — Strafe von -10 Punkten
Schritt (-1) Jeder Zug kostet -1 Punkt

Der Diskontfaktor γ verändert die Strategie grundlegend: Mit γ=0,9 spürt der Agent das Ziel schon viele Schritte vorher und lernt den kürzesten Weg an der Falle vorbei. Mit γ=0,1 ist er kurzsichtig: Ein Ziel, das mehr als zwei Schritte entfernt ist, zählt kaum, die Wege unterscheiden sich in seiner Tabelle nur winzig, und er irrt lange umher.

Achtung

Häufiger Irrtum

Der Diskontfaktor ist kein unwichtiger Feintuning-Parameter. Er verändert die Strategie fundamental: Nahe 0 greift der Agent die nächste Belohnung, egal welche Konsequenzen folgen. Nahe 1 akzeptiert er kurzfristige Kosten für langfristig höhere Gewinne.

Im 4×4-Gitter mit γ=0,9 bewertet der Agent das Ziel (+10) mehrere Schritte im Voraus: 0,9³ × 10 = 7,29 Punkte schon vier Schritte entfernt. Darum findet er den kürzesten Weg zum Ziel und meidet die Falle (-10). Mit γ=0,1 dagegen: 0,1³ × 10 = 0,01 Punkte — das Ziel ist vier Schritte entfernt praktisch wertlos. Fast nur die unmittelbaren Schrittkosten zählen: Am Start unterscheiden sich die Q-Werte der Richtungen erst in der vierten Nachkommastelle, und der Agent braucht sehr lange, bis sich eine klare Richtung abzeichnet.

Der Buchhalter-Algorithmus — Q-Learning

Definition

Q-Learning

Analogie

Stell dir einen Touristen vor, der eine neue Stadt erkundet und ein Notizbuch führt. Nach jedem Spaziergang notiert er: "Von dieser Kreuzung links abzubiegen führte zu einer tollen Aussicht" (hoher Q-Wert) oder "rechts abzubiegen war eine Sackgasse" (niedriger Q-Wert). Nach vielen Spaziergängen konvergiert das Notizbuch zur optimalen Sightseeing-Route.
Q(s,a) ← Q(s,a) + α · [r + γ · max Q(s',a') − Q(s,a)]
Q-Learning Update-Regel

Merke

Rechenbeispiel

Alter Q-Wert: Q(s,a) = 5,0. Der Agent führt die Aktion aus und erhält Belohnung r = 2. Bester Q-Wert im Folgezustand: max Q(s',a') = 8,0. Lernrate α = 0,1, Diskontfaktor γ = 0,9. Berechnung: 5,0 + 0,1 × [2 + 0,9 × 8,0 − 5,0] = 5,0 + 0,1 × [2 + 7,2 − 5,0] = 5,0 + 0,1 × 4,2 = 5,42. Der Q-Wert stieg, weil die neue Erfahrung wertvoller war als erwartet.

Eine besondere Eigenschaft von Q-Learning: Der Algorithmus ist off-policy — er lernt die optimale Strategie, selbst wenn der Agent dabei suboptimale Aktionen ausführt. Das Notizbuch wird immer besser, egal welchen Weg der Tourist tatsächlich geht, solange er jede Abzweigung immer wieder einmal ausprobiert.

Achtung

Häufiger Irrtum

Q-Learning funktioniert nicht für jedes Problem. Die Tabelle muss einen Eintrag pro Zustand-Aktions-Paar speichern. Schach hat etwa 10⁴⁴ Zustände — eine Tabelle dieser Größe ist physisch unmöglich. Für komplexe Probleme verwenden Deep Q-Networks (DQN) neuronale Netze, um Q-Werte zu approximieren.

Das 4×4-Gitter hat 16 Zustände × 4 Aktionen = 64 Q-Werte (gelernt werden davon 56, weil Ziel und Falle die Episode beenden) — kein Problem. Aber Schach hat geschätzte 10⁴⁴ Zustände. Eine Q-Tabelle dieser Größe würde den gesamten verfügbaren Speicherplatz der Erde bei weitem sprengen. Mnih et al. (2013, ausgebaut 2015 in Nature) lösten dieses Problem mit Deep Q-Networks: Ein neuronales Netz lernt, Q-Werte für beliebige Zustände zu schätzen, statt sie in einer Tabelle zu speichern. Das DQN lernte 49 Atari-Spiele und erreichte bei der Mehrzahl menschliches Niveau und öffnete die Tür zum modernen Deep Reinforcement Learning.

Mitmachen: Die Q-Tabelle füllt sich

Jetzt füllst du die Q-Tabelle selbst. Der Agent startet oben links im 4×4-Gitter von vorhin und weiß noch nichts: Alle Q-Werte stehen auf 0. Jeder Klick auf „Nächster Schritt“ macht einen Zug und ändert genau einen Wert nach der Update-Regel. Spiel dann ganze Episoden: Die +10 des Ziels wandern Schritt für Schritt zurück bis zum Start, und nach vielen Episoden zeigen die Pfeile den kürzesten Weg an der Falle vorbei.

Mitmachen: Optimist gegen Realist (TD & SARSA)

Die Differenz in der eckigen Klammer der Update-Regel heißt TD-Fehler (Temporal Difference). Q-Learning ist off-policy: Es lernt mit dem besten möglichen nächsten Zug (max Q). SARSA ist der on-policy-Zwilling: Es lernt mit dem Zug, den es tatsächlich als Nächstes macht. Hier siehst du beide gleichzeitig — und spürst, warum on-policy vorsichtiger ist.

Das Restaurant-Dilemma — Exploration vs. Exploitation

Definition

Epsilon-Greedy-Strategie

Analogie

Jeden Freitag musst du wählen: dein Lieblingsrestaurant (Exploitation — zuverlässig, aber du verpasst vielleicht das tolle neue Lokal um die Ecke) oder ein zufälliges neues Restaurant (Exploration — riskant, aber vielleicht findest du etwas noch Besseres). Am Anfang lohnt es sich, viele Restaurants auszuprobieren. Nach Jahren gehst du meist zu bewährten Favoriten, probierst aber gelegentlich etwas Neues.
Nur Exploitation

Zuverlässig, aber der Agent bleibt bei der erstbesten Strategie. Bessere Wege werden nie entdeckt.

Nur Exploration

Entdeckt alles, nutzt aber bekanntes Wissen nie aus. Der Agent stolpert ziellos umher.

Im Gitter-Welt-Beispiel: Episoden 1–100, ε=1,0 (rein zufällige Exploration, der Agent stolpert überall hin). Episoden 101–500, ε sinkt von 1,0 auf 0,1 (der Agent folgt immer öfter der besten Route und weicht am Ende nur noch zu 10% ab, um Abkürzungen zu entdecken). Ab Episode 500, ε=0,01 (der Agent folgt der optimalen Route und weicht kaum noch ab).

Achtung

Häufiger Irrtum

Mehr Exploration ist nicht immer besser. Exploration ist nur während des Lernens und in sich verändernden Umgebungen wertvoll. Ein Agent, der nie aufhört zu explorieren, verschwendet Ressourcen auf Aktionen, die er längst als schlecht kennt. Der Epsilon-Decay stellt sicher, dass Exploration nach und nach der Exploitation weicht.

Merke

Kernaussagen

  1. Ein MDP formalisiert die RL-Umgebung in Zustände, Aktionen, Übergänge, Belohnungen und einen Diskontfaktor — die Markov-Eigenschaft besagt: "Nur die Gegenwart zählt."
  2. Q-Learning füllt eine Tabelle mit erwarteten zukünftigen Belohnungen für jedes Zustand-Aktions-Paar, aktualisiert nach jeder Erfahrung durch eine einzige Rechenregel.
  3. Epsilon-Greedy mit Decay löst das Exploration-Exploitation-Dilemma: Zuerst breit erkunden, dann schrittweise die bestbekannte Strategie nutzen.
  4. Tabellarisches Q-Learning funktioniert für kleine Umgebungen. Für komplexe Probleme approximieren neuronale Netze die Q-Werte stattdessen (Deep Q-Networks).

Prüfen

Quiz: Q-Learning & MDPs

Noch offen

Welches der folgenden ist KEIN Bestandteil eines Markov Decision Process?

Wähle eine Antwort

Auflösung: 1) C · 2) B · 3) A · 4) B · 5) B · 6) B

Prüfen

Verständnisprüfung

Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.

0 von 3 sitzen