Diffusion-MPC in Discrete Domains: Feasibility Constraints, Horizon Effects, and Critic Alignment: Case study with Tetris

Diese Studie untersucht die Anwendbarkeit von Diffusions-basiertem Modellvorhersage-Steuerung (Diffusion-MPC) im diskreten Tetris-Umfeld und zeigt, dass eine durch Logit-Masking erzwungene Feasibility-Beschränkung sowie kurze Planungshorizonte entscheidend sind, um die systematische Fehlausrichtung von DQN-Critics und die Unsicherheitsakkumulation bei langen Rollouts zu überwinden.

Das Wesentliche

Stell dir vor, du spielst Tetris, aber anstatt selbst zu steuern, hast du einen künstlichen Intelligenz-Assistenten, der dir sagt, wie du die Blöcke legen sollst. Dieser Assistent ist ein bisschen wie ein visionärer Architekt: Er malt sich aus, wie das Spiel in den nächsten paar Zügen aussehen wird, und schlägt dir verschiedene Pläne vor.

Die Forscherin Haochuan Kevin Wang von der MIT hat untersucht, wie man diesen Assistenten am besten baut. Ihr Projekt heißt DIFFTETRIS. Hier ist die Geschichte dahinter, einfach erklärt:

1. Der große Fehler: Der Assistent träumt zu viel

Stell dir vor, dein Assistent schlägt dir 100 verschiedene Pläne vor, wie du die Blöcke legen könntest. Das Problem ist: Fast die Hälfte dieser Pläne ist unmöglich.
In Tetris gibt es harte Regeln. Ein Block passt nicht einfach so in eine Lücke, wenn er zu breit ist oder wenn darunter ein Loch ist. Wenn der Assistent einen unmöglichen Plan vorschlägt, ist das Spiel sofort vorbei.

• Die Lösung (Die "Verbotene-Liste"): Die Forscher haben dem Assistenten eine Art "Verbotene-Liste" gegeben. Bevor er einen Plan ausspricht, prüft er sofort: "Passt das überhaupt?" Wenn nein, streicht er es durch.
• Das Ergebnis: Ohne diese Liste war der Assistent chaotisch und verlor schnell. Mit der Liste wurde er plötzlich 6,8-mal besser und überlebte 5,6-mal länger. Es ist, als würde man einem Architekten sagen: "Bau keine Häuser, die in den Himmel ragen, ohne Fundament."

2. Der falsche Berater: Der "Experte", der alles vermasselt

Nachdem der Assistent einige gute (mögliche) Pläne vorgeschlagen hat, muss jemand entscheiden, welcher Plan der beste ist. Dafür haben die Forscher zwei Arten von Beratern getestet:

• Der erfahrene Spieler (Heuristik): Ein alter, bewährter Algorithmus, der einfache Regeln kennt (z. B. "Mache den Boden flach", "Vermeide Löcher").
• Der KI-Experte (DQN): Ein trainiertes neuronales Netz, das gelernt hat, Tetris zu spielen, indem es Millionen von Spielen gesehen hat.

Das Überraschende: Der KI-Experte war schlechter als der einfache erfahrene Spieler!
Warum? Stell dir vor, der KI-Experte ist wie ein Sportwissenschaftler, der die Theorie perfekt kennt, aber im echten Spiel panisch wird, wenn die Situation nicht exakt wie in seinem Training aussieht. Er wählte Pläne, die theoretisch gut aussahen, aber in der Praxis sofort zum Verlust führten.

• Die Lektion: Ein KI-Experte, der nicht genau weiß, wie der Assistent denkt, kann mehr schaden als nützen. Wenn man ihn doch nutzt, muss man ihn sehr vorsichtig einsetzen (nur als "Tie-Breaker"), damit er nicht die Kontrolle übernimmt.

3. Die Falle der Weitsicht: "Je weiter man schaut, desto mehr verirrt man sich"

Normalerweise denkt man: "Je weiter in die Zukunft mein Assistent schaut, desto besser ist der Plan."
Aber in diesem Experiment war das Gegenteil der Fall!

• Der kurze Blick (4 Züge voraus): Der Assistent war schnell, präzise und gewann oft.
• Der lange Blick (8 Züge voraus): Der Assistent wurde langsamer und machte mehr Fehler.

Warum? Stell dir vor, du versuchst, das Wetter für die nächsten 8 Tage vorherzusagen. Je weiter du in die Zukunft schaust, desto unsicherer wird die Vorhersage. In Tetris addieren sich diese kleinen Unsicherheiten. Wenn der Assistent versucht, 8 Züge im Voraus zu planen, erfindet er Szenarien, die so unwahrscheinlich sind, dass sie ihn verwirren. Ein kurzer, klarer Blick war hier besser als ein langer, verschwommener Traum.

4. Die Menge macht's: Mehr Vorschläge = Bessere Entscheidungen

Am Ende hängt alles davon ab, wie viele Pläne der Assistent überhaupt vorschlagen darf (die "Kandidaten").

• Wenn er nur wenige Pläne vorschlägt (z. B. 16), ist er oft unglücklich und wählt einen schlechten aus.
• Wenn er viele Pläne vorschlägt (z. B. 64), findet er fast garantiert einen genialen Plan.
• Der Haken: Mehr Pläne zu prüfen kostet mehr Zeit. Es ist wie beim Einkaufen: Wenn du nur 3 Supermärkte abhast, findest du vielleicht den besten Preis. Wenn du 60 abhast, findest du den absolut besten Preis, aber du bist den ganzen Tag unterwegs.

Zusammenfassung in einem Satz

Um einen KI-Assistenten für Tetris (und ähnliche komplexe Spiele) erfolgreich zu machen, muss man ihm verbieten, unmögliche Züge zu machen, ihn nicht blind auf einen KI-Berater hören lassen, ihn nicht zu weit in die Zukunft träumen lassen und ihm genug Zeit geben, viele Optionen durchzuprobieren.

Die Studie zeigt also: Manchmal ist es besser, einen klugen, bescheidenen Planer mit klaren Regeln zu haben, als einen hochintelligenten Träumer, der die Realität ignoriert.

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert die Herausforderung, Diffusionsmodelle für die Planung (Planning) in diskreten, kombinatorischen Domänen mit harten Gültigkeitsbedingungen (Hard Feasibility Constraints) einzusetzen.

• Kontext: Während Diffusionsmodelle in der kontinuierlichen Steuerung (z. B. Robotik) erfolgreich sind, scheitern sie oft in diskreten Räumen, wenn sie ungültige Aktionen generieren.
• Domäne: Tetris wurde als Testumgebung gewählt. Der Aktionsraum ist diskret (Rotation $\times$ x-Position), und die Gültigkeit einer Aktion hängt strikt von der aktuellen Brettkonfiguration und dem fallenden Tetromino ab.
• Kernproblem: Ein einzelner ungültiger Schritt macht eine gesamte geplante Trajektorie unbrauchbar. Herkömmliches Sampling aus einem Diffusionsmodell erzeugt in diesem Raum eine hohe Masse an ungültigen Aktionen, was die Planungseffizienz drastisch mindert.

2. Methodik: DIFFTETRIS

Die Autoren stellen DIFFTETRIS vor, einen Diffusions-basierten Model Predictive Control (MPC) Planer.

• Architektur (PlanDenoiser):

  • Ein konditionierter Transformer (basierend auf MaskGIT), der Sequenzen von Token-Paaren (Rotation, x-Position) generiert.
  • Eingaben: Kodierter Brettzustand (via CNN), Embeddings für das aktuelle und das nächste Teil.
  • Training: Masked Prediction Objective (Cross-Entropy) auf Expertentrajektorien (Behavior Cloning).

• Planungsloop (MPC):

  1. Generierung von $K$ Kandidaten-Trajektorien der Länge $H$ (Horizont).
  2. Bewertung (Reranking) der Kandidaten durch Vorwärtssimulation.
  3. Ausführung des ersten Schritts der besten Kandidaten.

• Schlüsselkomponenten:

  • Feasibility-Constrained Sampling (Logit-Masking): Im Gegensatz zum parallelen Sampling wird hier ein autoregressives Sampling verwendet. Bei jedem Schritt $h$ wird eine Maske berechnet, die alle geometrisch ungültigen $(r, x)$-Paare basierend auf dem simulierten Brettzustand auf $-\infty$ setzt. Dies erzwingt, dass nur gültige Aktionen gesampelt werden.
  • Reranking-Strategien:
    • Heuristik: Handkodierte Bewertung (Linien, Löcher, Höhe, etc.).
    • DQN-Critic: Ein vortrainiertes Deep Q-Network zur Bewertung des Zustands nach der Simulation.
    • Hybrid: Kombination aus Heuristik und DQN (z-score normalisiert).
  • Metrik (Decision-Level Regret): Eine neue Diagnose-Metrik, die die Lücke zwischen dem Score des gewählten Kandidaten und dem besten verfügbaren Kandidaten (gemessen durch die Heuristik) misst.

3. Wichtige Beiträge und Erkenntnisse

A. Notwendigkeit von Feasibility-Masking

• Ergebnis: Ohne Maskierung liegt der durchschnittliche Score bei nur 0,13 (5% der Episoden > 0). Mit Maskierung steigt der Score auf 0,89 (28% > 0).
• Effekt: Das Maskieren entfernt durchschnittlich 46% der Aktionsmasse (ungültige Platzierungen). Es wandelt den Planer von einem Generator ungültiger Aktionen in einen Suchraum innerhalb gültiger Trajektorien um.
• Gewinn: 6,8-fache Steigerung des Scores und 5,6-fache Steigerung der Überlebensrate im Vergleich zum unbeschränkten Sampling.

B. Fehlausrichtung von DQN-Critics (Critic Misalignment)

• Ergebnis: Der naive Ersatz der Heuristik durch einen DQN-Critic führt zu einem katastrophalen Leistungsabfall (Score sinkt auf 0,14).
• Ursache: Der DQN ist systematisch fehlausgerichtet (misaligned) mit dem Rollout-Ziel.
  • Der DQN wurde unter seiner eigenen Verhaltensverteilung trainiert, nicht für Trajektorien eines Diffusions-Proposers (Out-of-Distribution Problem).
  • Er bewertet oft Zustände falsch, was zu einem hohen Decision Regret führt (durchschnittlich 17,6 bei $H=8$; in 63% der Entscheidungen > 10).
  • Der DQN ignoriert oft lokale, kritische Fehler (wie Löcher), die für das Überleben in Tetris entscheidend sind.

C. Horizont-Effekte (Horizon Effects)

• Überraschendes Ergebnis: Ein kürzerer Planungshorizont ($H=4$) übertrifft einen längeren ($H=8$) sowohl in der Qualität (Score 1,48 vs. 0,89) als auch in der Latenz (1663ms vs. 2761ms).
• Erklärung:
  • Bei längeren Horizonten häufen sich Unsicherheiten in den simulierten Zukünften (insbesondere bei unbekannten zukünftigen Teilen).
  • Das Modell wurde auf kurze Horizonte (Behavior Cloning) trainiert; längere Rollouts führen zu einer stärkeren Verteilungsverschiebung (Distribution Shift).
  • Kürzere Horizonte reduzieren auch die Rechenlast für das Masking (weniger sequentielle Simulationen).

D. Skalierung und Fehlermodi

• Anzahl der Kandidaten ($K$): Die Leistung skaliert monoton mit $K$. Mehr Kandidaten erhöhen die Chance, hochwertige Trajektorien zu finden.
• Fehlermodi:
  • Bei kleinem $K$ ist die Proposal-Scarcity (Mangel an guten Vorschlägen) der limitierende Faktor.
  • Bei großem $H$ werden Alignment-Probleme (Critic-Fehlausrichtung) und Simulationsunsicherheit zu den dominierenden Fehlerquellen.

4. Signifikanz und Fazit

Das Paper liefert wichtige Erkenntnisse für die Anwendung von Diffusionsmodellen in der diskreten Entscheidungsfindung:

1. Feasibility ist kritisch: In diskreten Räumen mit harten Constraints ist das reine Generieren von Trajektorien ohne Validierung nutzlos. Logit-Masking ist kein kleiner Regularizer, sondern eine fundamentale Voraussetzung für Funktionalität.
2. Vorsicht bei gelernten Critic: Das bloße Ersetzen von Heuristiken durch vortrainierte RL-Critics (wie DQN) kann die Leistung verschlechtern, wenn die Verteilungen nicht übereinstimmen. Ein Hybrid-Ansatz (Heuristik + gewichteter Critic) oder die Beschränkung des Critic-Einflusses ist sicherer.
3. Kürzerer Horizont ist oft besser: In Umgebungen mit spärlichen Belohnungen und hoher Unsicherheit in der Zukunft (wie Tetris) können längere Planungs-Horizonte kontraproduktiv sein, da sie Unsicherheiten akkumulieren und das Modell überfordern.
4. Metrik für Alignment: Die vorgeschlagene Decision-Level Regret-Metrik ist ein leistungsfähiges, modellfreies Werkzeug, um die Qualität von Reranking-Strategien zu diagnostizieren, ohne auf Ground-Truth-Werte zurückgreifen zu müssen.

Zusammenfassend zeigt das Paper, dass Diffusion-MPC in kombinatorischen Domänen weniger vom generativen Modell selbst abhängt, sondern vielmehr von gültigkeitsbewusstem Sampling, der Ausrichtung des Critics und der intelligenten Wahl der Rechenparameter ($K, H$).