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

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een meester in Tetris bent, maar je moet spelen met een robot die net zo slim is als een peuter die net de letters van het alfabet heeft geleerd. Die robot probeert blokjes te plaatsen, maar hij maakt vaak de meest belachelijke fouten: hij probeert een blokje door de muur te duwen of in een gat te laten vallen waar het niet past.

Dit artikel, getiteld "Diffusion-MPC in Discrete Domains", vertelt het verhaal van hoe onderzoekers van MIT een slimme robot hebben gebouwd die beter Tetris speelt door een nieuwe techniek te gebruiken die lijkt op het "ontdooien" van een bevroren plaatje.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. De Robot die "Droomt" (Diffusion-MPC)

Stel je voor dat je een droom hebt over hoe je de volgende 8 zetten in Tetris moet doen. In plaats van één zet te bedenken, laat deze robot 64 verschillende dromen tegelijkertijd ontstaan.

Hoe werkt het? De robot begint met een "bevroren" wazige droom (een willekeurige reeks zetten) en probeert deze langzaam te ontdooien tot een duidelijk plan. Dit heet een diffusiemodel.
Het probleem: Omdat Tetris een spel is met harde regels (een blokje past niet als er geen ruimte is), droomt de robot vaak dingen die onmogelijk zijn. Hij probeert bijvoorbeeld een blokje in de lucht te laten zweven.

2. De "Onmogelijkheids-Filter" (Feasibility Constraints)

Dit is het belangrijkste ontdekking van het artikel.

Zonder filter: De robot droomt 64 plannen, maar de helft daarvan is onzin (zoals een auto die door een muur rijdt). Als je deze plannen uitvoert, crasht het spel direct.
Met filter (De "Bord-Check"): De onderzoekers hebben een strenge controleur toegevoegd. Voordat de robot een zet in zijn droom vastzet, vraagt hij: "Past dit blokje hier wel?" Als het antwoord "nee" is, wordt die optie direct geschrapt.
Het resultaat: Dit klinkt logisch, maar het was een enorme verrassing. Door alleen de mogelijke zetten te laten dromen, werd de robot 6,8 keer beter in scoren en 5,6 keer langer in het spel blijven. Het is alsof je een chef-kok die vaak vergiftig eten maakt, een lijst geeft met alleen veilige ingrediënten. Plotseling wordt het eten eetbaar.

3. De "Slimme Jury" die faalt (Critic Alignment)

Na het dromen van 64 plannen, moet de robot er één kiezen. Hiervoor gebruikten ze twee methoden:

De Gewone Regel (Heuristiek): Een simpele, menselijke regel: "Maak een vlakke berg, maak geen gaten."
De AI-Jury (DQN): Een zeer slimme, getrainde AI die denkt dat hij alles weet over Tetris.

De verrassende ontdekking: De slimme AI-jury was slechter dan de simpele menselijke regel!

Waarom? De AI-jury was getraind om te kijken naar de huidige staat van het bord, maar hij kon de toekomst niet goed voorspellen. Hij koos vaak een zet die er op dat moment slim uitzag, maar die later tot een ramp leidde.
De Metafoor: Het is alsof je een gids hebt die heel goed is in het beoordelen van de straat waar je nu staat, maar die totaal geen idee heeft van de afgronden die je over 10 minuten tegenkomt. Hij leidt je de verkeerde kant op.
De oplossing: Ze maakten een hybride jury. Ze luisterden 95% naar de simpele menselijke regel en slechts 5% naar de slimme AI. Zo kregen ze het beste van beide werelden zonder de fouten van de AI.

4. Korte Dromen vs. Lange Dromen (Horizon Effects)

De robot kon plannen maken voor 4 zetten vooruit of voor 8 zetten vooruit.

Verwachting: Je zou denken dat "8 zetten vooruit plannen" altijd beter is.
Realiteit: De robot was beter met plannen voor slechts 4 zetten.
De reden: Hoe verder je in de toekomst kijkt, hoe meer je moet "gokken" over wat er gaat gebeuren (want je weet niet welke blokjes er komen). Bij 8 zetten stapelen deze gokken zich op tot een enorme onzekerheid. Het is alsof je probeert het weer te voorspellen: voor morgen is het makkelijk, maar voor over 8 dagen is het pure speculatie. Een kortere, scherpere blik werkt beter dan een wazige, lange blik.

5. Meer is niet altijd beter (Compute Scaling)

De onderzoekers keken ook hoeveel "dromen" (K) de robot mocht maken.

Resultaat: Hoe meer dromen je maakt, hoe beter de robot wordt. Maar het kost ook steeds meer tijd.
De balans: Als je snelheid belangrijk vindt, is het slim om minder dromen te maken (maar dan wel met de "Onmogelijkheids-Filter"). Als je de allerbeste score wilt, moet je meer tijd steken in het dromen.

Conclusie in één zin

Om een robot slim Tetris te laten spelen, is het niet genoeg om hem te laten "dromen" over de toekomst; je moet hem eerst een filter geven dat onmogelijke zetten blokkeert, hem niet blindelings laten vertrouwen op een slimme AI die de toekomst verkeerd inschat, en hem laten focussen op de korte termijn in plaats van te proberen te voorspellen wat er over een uur gebeurt.

Het artikel leert ons dat in complexe spelletjes (en misschien ook in het echte leven), discipline (de filter) en realisme (korte horizon) vaak belangrijker zijn dan pure "slimheid".

Each language version is independently generated for its own context, not a direct translation.

Titel en Context

Paper: Diffusion-MPC in Discrete Domains: Feasibility Constraints, Horizon Effects, and Critic Alignment: Case study with Tetris
Auteur: Haochuan Kevin Wang (MIT)
Doel: Onderzoek naar de toepassing van Diffusie-Model Predictive Control (Diffusion-MPC) in discrete, combinatorische domeinen met harde geldigheidsbeperkingen, specifiek getest op het spel Tetris.

1. Het Probleem

Diffusiemodellen zijn krachtige generatieve modellen voor sequentiële besluitvorming, maar hun toepassing in discrete domeinen (zoals Tetris) brengt unieke uitdagingen met zich mee:

Harde geldigheidsbeperkingen (Feasibility Constraints): In tegenstelling tot continue controle, waar kleine afwijkingen vaak acceptabel zijn, zijn acties in Tetris strikt binair: een plaatsing is ofwel geldig ofwel onmogelijk (bijv. door de vorm van het blok of de bordconfiguratie). Een enkele ongeldige actie maakt een hele traject-candidate onbruikbaar.
Combinatorische complexiteit: Tetris is NP-hard, zelfs voor benaderingen. De actie-ruimte (rotatie × x-positie) is discreet, maar niet alle 40 mogelijke acties zijn op elk moment geldig.
Critic Alignment: Het is onduidelijk of geleerde waardeschatters (zoals DQN-critics) effectief kunnen worden gebruikt om kandidaat-trajecten te selecteren in een MPC-omgeving, vooral als de verdelingen van de planner en de critic niet overeenkomen.

2. Methodologie: DIFFTETRIS

De auteurs presenteren DIFFTETRIS, een planner die een diffusiemodel combineert met MPC. De kerncomponenten zijn:

A. PlanDenoiser Architectuur

Model: Een conditionele Transformer (gebaseerd op MaskGIT) die sequenties van token-paren (rotatie, x-positie) genereert.
Input: De huidige bordtoestand (gecodeerd via CNN), de huidige en volgende blokidentiteit, en een gedeeltelijk gemaskeerde sequentie van acties.
Training: Getraind met een "masked prediction" doelstelling op expert-trajecten gegenereerd door een heuristische agent.

B. Feasibility-Constrained Sampling (Geldigheidsbeperkte Sampling)

Dit is de meest kritieke innovatie voor discrete domeinen:

Methode: Tijdens het genereren van een kandidaat-traject wordt bij elke stap (autoregressief) een validity mask berekend. Dit maskert alle ongeldige acties (logits) in de softmax-verdeling.
Effect: Dit garandeert dat elke gegenereerde actie fysiek uitvoerbaar is. Het proces is sequentieel (niet parallel) omdat de bordtoestand na elke stap moet worden gesimuleerd om de volgende mask te berekenen.
Observatie: Ongeveer 46% van de actie-ruimte is op elk moment ongeldig. Zonder masking zou de planner veel tijd verspillen aan het genereren van onuitvoerbare trajecten.

C. Reranking Strategieën

Na het genereren van $K$ kandidaat-trajecten, moet er één worden geselecteerd. Drie strategieën worden vergeleken:

Heuristische Reranking: Een handgemaakte scorefunctie (lijnen, gaten, hoogte, bumpiness) die het resultaat van het gesimuleerde traject evalueert.
DQN Reranking: Een vooraf getrainde Deep Q-Network (DQN) die de waarde van de eindtoestand van het traject schat.
Hybride Reranking: Een combinatie van de heuristische score en de genormaliseerde DQN-score.

D. Decision-Level Regret

De auteurs introduceren een nieuwe diagnostische metric: Regret.

Dit meet het verschil tussen de score van de gekozen kandidaat en de beste beschikbare kandidaat (gebaseerd op de heuristische rollout-score).
Een hoge regret betekent dat de selectie-strategie (bijv. DQN) systematisch slechtere opties kiest dan wat er beschikbaar was.

3. Belangrijkste Resultaten

A. Essentieelheid van Feasibility Masking

Zonder masking scoort de planner gemiddeld 0.13 punten en overleeft hij slechts 5% van de spellen.
Met masking stijgt de gemiddelde score naar 0.89 (een 6.8x verbetering) en het overlevingspercentage naar 28% (een 5.6x verbetering).
Conclusie: Masking is geen kleine regularisatie, maar een fundamentele noodzaak om de zoekruimte te beperken tot uitvoerbare acties.

B. Het Falen van Naive DQN Reranking

Het vervangen van de heuristiek door een DQN-critic leidt tot een dramatische prestatiedaling (score daalt terug naar ~0.14).
Regret-analyse: De DQN vertoont een hoge systematische regret (gemiddeld 17.6 bij horizon 8). In 63% van de beslissingen kiest de DQN een kandidaat die aanzienlijk slechter is dan de beste optie.
Oorzaak: De DQN is getraind op zijn eigen gedragsverdeling en is niet goed afgestemd op de trajecten gegenereerd door de diffusieplanner (distributional shift). De DQN schat waarden die niet correleren met de werkelijke bordkwaliteit zoals gemeten door forward simulation.

C. Horizon Effecten (Kort vs. Lang)

Verrassende bevinding: Een kortere horizon ( $H=4$ $H = 4$ ) presteert beter dan een langere horizon ( $H=8$ $H = 8$ ).
- $H=4$ : Score 1.48, Latentie 1663ms.
- $H=8$ : Score 0.89, Latentie 2761ms.
Redenering: Bij langere horizons compenseert de onzekerheid in de gesimuleerde toekomst (onbekende blokken) de voordelen van vooruitplanning. De planner is getraind op korte-termijn gedrag (behavior cloning), wat leidt tot fouten die zich opstapelen in langere rollouts.

D. Compute Scaling (Aantal Kandidaten $K$ )

Prestaties schalen monotoon met het aantal kandidaten $K$ $K$ .
- $K=16$ : Score 0.31.
- $K=64$ : Score 0.89.
Dit suggereert dat de kwaliteit van de "proposal distribution" (het denoiser) beperkend is; meer samples vergroten de kans op het vinden van een hoogwaardig traject.

E. Hybride Aanpak

Een hybride aanpak (heuristic + kleine DQN bijdrage, $\alpha=0.05$ ) herstelt de prestaties van de pure heuristiek (score 0.89) met bijna nul regret. Dit toont aan dat geleerde critics veilig kunnen worden gebruikt als ze strikt begrensd worden.

4. Belang en Conclusie

De studie levert cruciale inzichten voor het toepassen van Diffusion-MPC in discrete, combinatorische controleproblemen:

Feasibility is King: In discrete domeinen met harde beperkingen is het filteren van ongeldige acties tijdens het generatieproces (via masking) de belangrijkste factor voor succes. Zonder dit faalt de planner volledig.
Critic Alignment is Kritiek: Geleerde critics (zoals DQN) zijn niet direct overdraagbaar naar MPC-selectie als ze niet perfect afgestemd zijn op de proposal-distributie. Ze kunnen systematisch "anti-helpful" zijn. Regret is een nuttige metric om dit te diagnosticeren.
Korte Horizons zijn Beter: In domeinen met trage beloningen en onzekerheid (zoals Tetris) kunnen kortere horizons beter presteren dan langere, omdat ze minder last hebben van cumulatieve simulatiefouten en beter aansluiten bij de korte-termijn prioriteiten van de getrainde denoiser.
Compute-Aware Tuning: De keuze tussen het aantal kandidaten ( $K$ ) en de horizon ( $H$ ) bepaalt het type falen: te weinig $K$ leidt tot schaarste aan goede voorstellen, terwijl te grote $H$ leidt tot onzekerheid en misalignement.

Conclusie: Voor succesvolle Diffusion-MPC in combinatorische domeinen moet de focus liggen op geldigheidsbewust sampling, regret-gebaseerde diagnostiek voor critic-alignement, en een compute-bewuste selectie van hyperparameters, waarbij geleerde critics alleen met voorzichtigheid en beperking worden ingezet.