Strategien entwickeln (Q-Learning & MDPs)
Strategien, gelernt durch Trial and Error — die formale Version dessen, was jedes Kind tut.
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
Definition
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:
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
Definition
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.
Deep Q-Networks: KI lernt Atari aus Pixeln
Rund ein Jahr bevor AlphaGo Schlagzeilen machte, brachte DeepMind 2015 eine KI dazu, Atari-Videospiele allein aus den rohen Bildpunkten zu lernen — und legte damit den Grundstein des Deep Reinforcement Learning. Im Februar 2015 stellte das Team um Volodymyr Mnih in Nature „Human-level control through deep reinforcement learning“ vor (ein erster Vorläufer war 2013 erschienen). Ein neuronales Netz, das nur Bildschirm und Punktestand sah, lernte 49 verschiedene Atari-Spiele — mit derselben Architektur, ohne pro Spiel nachzujustieren. Technisch verband DeepMind ein Faltungsnetz mit Q-Learning, einem Erfahrungs-Speicher (Experience Replay, von Lin Anfang der 1990er eingeführt) und einem stabilisierenden Ziel-Netzwerk. Bei der Einordnung lohnt Präzision: Das System erreichte auf mehr als der Hälfte der Spiele (29 von 49) menschliches Niveau und schlug auf 43 von 49 alle früheren Verfahren — bei Spielen mit seltener Belohnung wie Montezuma's Revenge scheiterte es jedoch fast völlig. Trotzdem war es der Beweis, dass tiefe Netze und Reinforcement Learning im großen Maßstab zusammenpassen — die Brücke vom Q-Learning der 1990er zu AlphaGo und AlphaZero.
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
Definition
Zuverlässig, aber der Agent bleibt bei der erstbesten Strategie. Bessere Wege werden nie entdeckt.
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).
AlphaStar erreicht Grandmaster-Level
Die Eroberung der komplexesten Echtzeit-Strategie durch künstliche Intelligenz. Im Juli und August 2019 trat DeepMinds AlphaStar anonym im Ranglisten-Modus auf Battle.net an; am 30. Oktober 2019 berichtete DeepMind in der Fachzeitschrift Nature, dass das System als erste KI das Grandmaster-Level in StarCraft II erreicht hatte – einem Spiel, das als zu komplex für Maschinen galt. AlphaStar rangierte über 99,8% aller aktiven Battle.net-Spieler und beherrschte alle drei Völker: Protoss, Terran und Zerg. Zuvor hatte AlphaStar bereits die Profispieler Grzegorz 'MaNa' Komincz und Dario 'TLO' Wünsch jeweils 5:0 besiegt. Die Besonderheit lag in der Multi-Agent Reinforcement Learning-Architektur, die verschiedene Strategien und Gegenstrategien in einer Liga trainierte. In den Partien gegen MaNa und TLO lag AlphaStar mit durchschnittlich rund 280 Aktionen pro Minute sogar unter menschlichen Profis, bewies aber präzisere Ausführung. Diese Leistung markierte einen Meilenstein für KI in Videospielen und Echtzeit-Entscheidungen.
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
- 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."
- 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.
- Epsilon-Greedy mit Decay löst das Exploration-Exploitation-Dilemma: Zuerst breit erkunden, dann schrittweise die bestbekannte Strategie nutzen.
- 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
Welches der folgenden ist KEIN Bestandteil eines Markov Decision Process?
Wähle eine Antwort
1. Welches der folgenden ist KEIN Bestandteil eines Markov Decision Process?
2. Was garantiert die Markov-Eigenschaft bei einem MDP?
3. Gegeben: Q(s,a)=4,0, α=0,1, r=3, γ=0,9, max Q(s',a')=7,0. Wie lautet der neue Q(s,a)?
4. Ein Agent nutzt Epsilon-Greedy mit ε=0,3. Wie viele zufällige Aktionen führt er in 200 Schritten ungefähr aus?
5. Ein Q-Learning-Agent wählt immer die Aktion mit dem höchsten Q-Wert (ε=0). Nach 1.000 Episoden ist seine Leistung immer noch schlecht. Was ist die wahrscheinlichste Ursache?
6. Warum ist tabellarisches Q-Learning für ein Spiel wie Schach unpraktikabel?
Prüfen
Verständnisprüfung
Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.
0 von 3 sitzen