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

Cette étude analyse l'application de la planification par diffusion (Diffusion-MPC) au domaine discret du Tetris, démontrant que le masquage des contraintes de faisabilité est essentiel pour améliorer les performances, tandis que l'alignement imparfait des critiques et l'accumulation d'incertitude sur des horizons longs limitent l'efficacité de la méthode.

L'essentiel

🧱 Le Projet : "DiffTetris", le Tetris qui rêve avant d'agir

Imaginez que vous jouez au Tetris. Vous avez un bloc qui tombe, et vous devez décider instantanément où le poser pour ne pas perdre. C'est un jeu de logique rapide.

Les chercheurs de l'MIT (Massachusetts Institute of Technology) ont créé un robot nommé DiffTetris. Au lieu de jouer "au feeling" ou avec des règles fixes, ce robot utilise une technologie très avancée appelée modèle de diffusion (la même famille que celle qui crée des images d'art avec l'IA).

Mais ici, l'IA ne dessine pas des chats ; elle rêve de séquences de coups. Elle imagine : "Et si je tourne le bloc ici, puis là, puis là ?" et elle génère plusieurs scénarios possibles avant de choisir le meilleur.

Le problème ? Dans le Tetris, si vous essayez de poser un bloc dans un mur, c'est impossible. Le jeu vous dit "Non". Si l'IA imagine un coup impossible, tout son scénario devient nul.

---

🔍 Les 4 Découvertes Clés (avec des analogies)

Les chercheurs ont testé trois choses pour rendre ce robot plus intelligent : comment il imagine les coups, comment il choisit le meilleur, et combien de temps il y passe.

1. Le Filtre de Sécurité (La "Feuilles de Route")

• Le problème : Sans aide, l'IA imagine beaucoup de coups impossibles (comme essayer de poser un bloc carré dans un trou triangulaire). C'est comme si un chef cuisinier essayait de mettre des ingrédients dans un four qui n'existe pas.
• La solution : Ils ont ajouté un filtre de validité. À chaque fois que l'IA imagine un coup, le système vérifie immédiatement : "Est-ce que c'est physiquement possible ?". Si non, il efface l'idée.
• Le résultat : C'est crucial ! Sans ce filtre, le robot perd très vite. Avec le filtre, ses performances sont multipliées par 7. C'est comme passer d'un conducteur qui roule dans le mur à un pilote de course qui reste sur la route.

2. Le Juge (L'Expert vs. Le Livre de Recette)

Une fois que le robot a imaginé 64 scénarios différents, il doit en choisir un. Comment ?

• Option A (Le Livre de Recette) : Utiliser une règle simple et éprouvée (ex: "Évite les trous, garde la surface plate"). C'est fiable.
• Option B (L'Expert IA) : Utiliser une autre IA (un "DQN") entraînée pour juger les positions.
• Le twist : L'Option B (l'Expert IA) a échoué lamentablement.
  • Pourquoi ? Imaginez un critique de cinéma qui a vu des milliers de films, mais qui est habitué à juger des comédies. Si vous lui montrez un film d'horreur (un scénario de Tetris très complexe généré par le robot), il va le détester et vous dire de le rejeter, alors que c'est un chef-d'œuvre. L'IA "juge" mal les scénarios qu'elle n'a pas elle-même créés. Elle crée plus de confusion que de clarté.
  • La leçon : Parfois, une règle simple (le Livre de Recette) vaut mieux qu'un expert qui essaie de deviner.

3. Le Temps de Réflexion (Mieux vaut court et précis que long et flou)

Le robot peut imaginer 4 coups à l'avance (Horizon court) ou 8 coups (Horizon long).

• L'intuition : Plus on regarde loin, mieux c'est, non ?
• La réalité : Non ! Ici, regarder plus loin (8 coups) fait perdre.
  • L'analogie : Imaginez que vous devez prédire la météo. Prévoir s'il va pleuvoir demain (4 coups) est facile. Prévoir s'il va pleuvoir dans 8 jours (8 coups) est presque impossible car les erreurs s'accumulent. Plus le robot imagine loin, plus ses prédictions deviennent floues et erronées.
  • Résultat : Le robot qui regarde à 4 coups de distance joue mieux et plus vite que celui qui regarde à 8 coups.

4. La Quantité d'Essais (Plus on essaie, mieux c'est)

Le robot génère plusieurs scénarios (K) avant de choisir.

• Résultat : Plus le robot génère de scénarios (de 16 à 64), plus il trouve de bons coups. C'est logique : plus vous lancez des fléchettes, plus vous avez de chances de toucher le centre. Mais cela prend plus de temps de calcul. C'est un compromis entre la vitesse et la qualité.

---

🏆 Le Verdict Final

Cette étude nous apprend trois choses importantes pour l'avenir de l'IA dans les jeux et la robotique :

1. La sécurité avant tout : Dans un monde où les erreurs sont interdites (comme le Tetris), il faut forcer l'IA à ne penser qu'aux coups possibles. Sans cela, elle est aveugle.
2. Méfiez-vous des "experts" IA : Une IA entraînée pour juger peut parfois être pire qu'une règle simple si elle n'est pas parfaitement alignée avec la situation actuelle.
3. La simplicité gagne : Parfois, ne pas essayer de tout prévoir sur le long terme (horizon court) est plus efficace que de se perdre dans des scénarios complexes qui deviennent faux.

En résumé, DiffTetris est un robot qui apprend à jouer en imaginant des scénarios, mais qui a besoin d'un "gardien" pour s'assurer qu'il ne rêve pas de coups impossibles, et d'une règle simple pour choisir le bon coup, plutôt que d'un juge trop confiant.

Résumé technique

1. Problématique et Contexte

Le papier aborde l'application des modèles de diffusion à la planification dans des domaines discrets et combinatoires, en utilisant le jeu de Tetris comme cas d'étude.

• Le défi principal : Contrairement aux espaces d'action continus (où de petites déviations sont tolérables), les espaces discrets comme le Tetris imposent des contraintes de faisabilité rigides. Une seule action invalide (ex: placer une pièce dans un mur ou hors du plateau) rend toute une trajectoire candidate inutilisable.
• Le contexte : Les modèles de diffusion sont puissants pour la génération de trajectoires (MPC - Model Predictive Control), mais leur application directe à des espaces discrets sans gestion stricte des contraintes conduit à un échantillonnage massif d'actions impossibles, dégradant la performance.
• Objectif : Développer un planificateur Diffusion-MPC efficace pour le Tetris, en étudiant trois axes critiques : l'échantillonnage contraint par la faisabilité, l'alignement des fonctions de rééchantillonnage (critiques), et l'impact de l'horizon de planification.

2. Méthodologie : DIFFTETRIS

L'auteur propose DIFFTETRIS, un planificateur basé sur le contrôle prédictif par modèle (MPC) utilisant un dénoiseur de diffusion discret.

Architecture du Modèle (PlanDenoiser)

• Modèle : Un Transformer conditionnel (inspiré de MaskGIT) qui génère des séquences de tokens représentant des paires (rotation, position horizontale).
• Entrées : État du plateau (encodé par CNN), pièce actuelle, pièce suivante, et une séquence partiellement masquée de longueur $H$ (l'horizon).
• Entraînement : Apprentissage par imitation (behavior cloning) sur des trajectoires d'experts heuristiques, avec un objectif de prédiction masquée (MaskGIT).

Boucle de Planification (MPC)

Pour chaque étape de décision :

1. Échantillonnage : Génération de $K$ séquences d'actions candidates de longueur $H$.
2. Contrainte de Faisabilité (Clé) :
   • Sans contrainte : Échantillonnage parallèle standard (risque d'actions invalides).
   • Avec contrainte (Masking) : Échantillonnage autoregressif. À chaque étape de l'horizon, un masque de validité est calculé pour la configuration actuelle du plateau. Les logits des actions invalides sont masqués (mis à $-\infty$) avant l'échantillonnage. Cela garantit que chaque action générée est géométriquement valide.
3. Rééchantillonnage (Reranking) : Chaque candidate est simulée vers l'avant et notée selon trois stratégies :
   • Heuristique : Score basé sur des règles manuelles (lignes, trous, hauteur, etc.).
   • DQN : Utilisation d'un critique DQN pré-entraîné pour évaluer l'état final de la simulation.
   • Hybride : Combinaison pondérée du score de déroulement (rollout) heuristique et du score DQN normalisé.
4. Exécution : L'action initiale de la candidate ayant le meilleur score est exécutée.

Métrique Diagnostique : Regret au niveau de la décision

L'auteur introduit le regret pour évaluer la qualité du rééchantillonnage : la différence entre le score de déroulement de la meilleure candidate disponible et celle choisie par le stratège. Un regret élevé indique que le critique sélectionne systématiquement de mauvaises options par rapport à l'objectif de simulation.

3. Résultats Clés

Les expériences, menées sur 100 épisodes par configuration, révèlent quatre découvertes majeures :

A. L'importance cruciale de la contrainte de faisabilité

• Sans masquage : Le score moyen est de 0,13 et le taux de survie (score > 0) est de 5%. Environ 46% de l'espace d'action est invalide à chaque étape.
• Avec masquage : Le score moyen grimpe à 0,89 (+6,8x) et le taux de survie à 28% (+5,6x).
• Conclusion : Le masquage n'est pas un simple régularisateur ; il transforme le planificateur d'un générateur d'actions non exécutables en un chercheur de trajectoires valides.

B. L'échec du rééchantillonnage par DQN (Désalignement)

• Remplacer l'heuristique par un critique DQN entraîne une chute drastique des performances (score moyen 0,14, survie 7%).
• Analyse du regret : Le DQN présente un regret moyen élevé (17,6 à $H=8$), signifiant qu'il choisit souvent des candidats nettement inférieurs à la meilleure option disponible selon la simulation.
• Cause : Le DQN est entraîné sur sa propre distribution comportementale et évalue la qualité d'un état unique, tandis que le planificateur évalue des trajectoires entières. Il y a un désalignement fondamental entre l'estimation de valeur du DQN et la qualité réelle des trajectoires générées par le dénoiseur (hors distribution).

C. L'effet contre-intuitif de l'horizon court

• Une configuration avec un horizon court ($H=4$) surpasse l'horizon long ($H=8$) en termes de score (1,48 vs 0,89) et de latence (1663ms vs 2761ms).
• Explication : Dans un environnement à récompenses clairsemées et retardées comme le Tetris, les horizons longs amplifient l'incertitude des simulations futures (distribution shift) et les erreurs de complétion de tokens tardifs. De plus, le dénoiseur est entraîné par imitation de comportement sur des horizons courts, ce qui favorise la qualité à court terme.

D. Échelle de calcul et modes d'échec

• Nombre de candidats ($K$) : La performance augmente de manière monotone avec $K$ (de 0,31 pour $K=16$ à 0,89 pour $K=64$). La qualité est limitée par la rareté des propositions.
• Horizon ($H$) : Augmenter $H$ dégrade la qualité et la latence, et amplifie le désalignement du critique.
• Stratégie Hybride : Une combinaison faible ($\alpha=0,05$) de DQN et d'heuristique permet de récupérer les performances de l'heuristique pure tout en limitant les risques du DQN.

4. Contributions et Signification

Ce travail apporte plusieurs contributions techniques et conceptuelles :

1. Preuve de nécessité du masquage : Il démontre que dans les domaines discrets combinatoires, l'échantillonnage contraint par la faisabilité est une condition sine qua non pour la performance, bien plus critique que l'amélioration du modèle génératif lui-même.
2. Diagnostic de désalignement : L'introduction du regret au niveau de la décision comme métrique pour détecter les critiques mal alignés (ici, le DQN) qui sont non seulement bruyants mais systématiquement nuisibles ("anti-helpful").
3. Optimisation de l'horizon : La découverte que des horizons de planification plus courts peuvent être supérieurs aux horizons longs dans les environnements à récompenses retardées, en raison de la propagation de l'incertitude et du biais d'entraînement par imitation.
4. Frontière Qualité-Latence : La caractérisation de la façon dont les choix de calcul ($K, H$) déterminent le mode d'échec dominant (pénurie de propositions vs incertitude d'alignement).

Conclusion

Le papier conclut que pour le contrôle combinatoire par Diffusion-MPC, la priorité ne doit pas être donnée uniquement à la modélisation générative, mais plutôt à :

• L'échantillonnage conscient de la faisabilité.
• Le diagnostic d'alignement basé sur le regret.
• Le choix judicieux des points de fonctionnement computationnels.
• La prudence dans l'utilisation de critiques appris (comme le DQN) sans un alignement distributionnel explicite ou des objectifs d'entraînement adaptés à la planification.

DIFFTETRIS établit ainsi un cadre robuste pour l'application des modèles de diffusion à des problèmes de décision discrets complexes.