Résumé technique : Apprentissage par renforcement avec des politiques de diffusion discrète pour des espaces d'actions combinatoires

1. Énoncé du problème

L'apprentissage par renforcement (RL) fait face à des défis majeurs lors de sa mise à l'échelle vers de grands espaces d'actions discrets combinatoires, prévalents dans des applications réelles telles que la planification hiérarchique avec des macro-actions, la coordination multi-agents et les recommandations de listes dans les systèmes de recommandation. Les algorithmes RL standards peinent avec ces espaces en raison de la croissance exponentielle de la taille de l'espace d'actions, exigeant des paramétrisations de politiques et des stratégies d'exploration hautement efficaces.

Les approches antérieures ont tenté d'atténuer cette complexité par la réduction de dimensionnalité, l'entraînement hiérarchique ou l'hypothèse de propriétés structurelles spécifiques. Plus récemment, des modèles autorégressifs ont été appliqués aux actions combinatoires ; cependant, ils souffrent de coûts computationnels élevés lors de l'inférence en raison d'une génération séquentielle et imposent des ordonnancements causaux artificiels des actions qui peuvent restreindre l'expressivité de la politique. Bien que les modèles de diffusion aient montré des promesses dans le contrôle continu et les tâches génératives discrètes, un cadre principé et efficace pour l'entraînement de politiques de diffusion discrète via un RL en ligne reste inexploré.

2. Méthodologie : RL-D2

Les auteurs introduisent RL-D2, un cadre novateur pour entraîner des modèles de diffusion discrets en tant que politiques pour des espaces d'actions combinatoires. L'innovation centrale réside dans un processus d'entraînement en ligne efficace qui découple l'optimisation de l'objectif RL de la tâche complexe d'apprentissage de représentations.

2.1. Cible de Descente de Miroir de Politique (PMD)

Le cadre reformule la mise à jour de la politique comme un problème d'appariement de distributions. Au lieu d'optimiser directement l'objectif RL, la méthode utilise la Descente de Miroir de Politique (PMD) pour définir une distribution cible idéale et régularisée ($\pi_{MD}$). Étant donné une politique actuelle $\pi_{old}$ et une fonction d'avantage $A_{\pi_{old}}$, la distribution cible est dérivée analytiquement :
$$\pi_{MD}(a|s) \propto \pi_{old}(a|s) \exp(A_{\pi_{old}}(s, a)/\lambda)$$
où $\lambda$ est un paramètre de température. Le modèle de diffusion expressif est ensuite entraîné pour répliquer cette distribution cible stable.

2.2. Minimisation de la divergence

La mise à jour de la politique est obtenue en minimisant la divergence entre la politique de diffusion ($\pi_\theta$) et la cible PMD ($\pi_{MD}$). L'article analyse deux variantes spécifiques basées sur la divergence de Kullback-Leibler (KL) :

• KL direct (FKL) : Minimise $d_{KL}(\pi_{MD}, \pi_\theta)$. Ce comportement de « recherche de moyenne » encourage la politique à couvrir les modes de la distribution cible, favorisant l'exploration. Les auteurs dérivent une perte ELBO pondérée traitable pour cet objectif, permettant un entraînement hors politique et réajustant les actions échantillonnées en fonction de leurs valeurs d'avantage.
• KL inverse (RKL) : Minimise $d_{KL}(\pi_\theta, \pi_{MD})$. Ce comportement de « recherche de mode » se concentre sur les actions de plus haute valeur et est théoriquement équivalent à l'optimisation PMD originale. En raison de l'ingérabilité de la vraisemblance de diffusion, les auteurs construisent un MDP augmenté pour dériver un ratio d'échantillonnage d'importance traitable, optimisant l'objectif en utilisant un mécanisme de clipping de style PPO.

2.3. Apprentissage de diffusion sur politique

Pour aligner la distribution d'entraînement avec la distribution d'inférence, les auteurs proposent un Apprentissage de diffusion sur politique. Au lieu de générer des actions bruitées à partir d'un processus direct fixe démarrant d'une action propre, la trajectoire de diffusion est générée sur politique en échantillonnant à partir du processus inverse appris de la politique actuelle. Cela améliore la stabilité et l'efficacité des échantillons.

3. Contributions clés

1. Cadre RL-D2 : Un nouveau cadre d'entraînement en ligne efficace pour l'utilisation de modèles de diffusion discrets en tant que politiques en RL pour des espaces d'actions combinatoires. Il reformule les mises à jour de politique comme des problèmes d'appariement de distributions utilisant des cibles PMD.
2. Dérivations théoriques : La dérivation et l'analyse de deux méthodes pratiques d'amélioration de politique basées sur la minimisation des divergences KL direct et inverse vers la cible PMD.
3. Validation empirique : Des expériences extensives sur trois domaines difficiles démontrant des résultats de l'état de l'art :
   • Génération de séquences d'ADN : Affinement guidé par la récompense d'un modèle de diffusion discret.
   • RL à long horizon : Planification de macro-actions dans les environnements MinAtar et Atari.
   • RL multi-agents : Apprentissage coopératif dans le domaine du Google Research Football.

4. Résultats expérimentaux

L'article rapporte des performances supérieures et une efficacité des échantillons dans tous les domaines testés :

• Génération de séquences d'ADN : RL-D2 a obtenu des scores de récompense de l'état de l'art tout en maintenant une haute vraisemblance logarithmique (naturalité) des séquences générées. Il a démontré une efficacité computationnelle significative, réduisant la consommation de mémoire GPU de 66,4 Go à 10,6 Go et le temps d'entraînement de 268 minutes à 97 minutes par rapport à la référence DRAKES.
• Atari (Macro-actions) : RL-D2 a surpassé des références solides (DQN, IMPALA, R2D2, PPO) dans 36 environnements Atari sur 56. Il a montré une force particulière dans les tâches nécessitant des stratégies à long terme (par exemple, Breakout, Space Invaders). La méthode a démontré une évolutivité, maintenant les performances à mesure que les longueurs de macro-actions augmentaient (jusqu'à 16), tandis que des références comme DQN-Macro échouaient en raison de la croissance exponentielle de l'espace d'actions.
• Google Research Football : Dans des tâches multi-agents coopératives (jusqu'à 11 contre 11), la politique de diffusion discrète a atteint les taux de victoire moyens les plus élevés, surpassant les références autorégressives (MAT, MAPPO) et démontrant la capacité à capturer des dépendances inter-agents complexes sans factorisation restrictive.

Compromis empiriques : FKL vs RKL

Les auteurs soulignent un compromis clé entre les deux variantes de divergence :

• FKL : Démontre une efficacité des échantillons supérieure et une convergence initiale plus rapide, le rendant adapté aux scénarios contraints en données (par exemple, Atari). Cependant, il est moins stable et nécessite un réglage soigneux de la température pour éviter l'effondrement.
• RKL : Assure un entraînement stable et atteint des performances asymptotiques plus élevées sur des tâches difficiles avec suffisamment de données (par exemple, Google Football), bien qu'il apprenne légèrement plus lentement au début.

5. Importance et affirmations

L'article affirme que RL-D2 fournit une solution évolutive et performante au défi de longue date du RL dans de grands espaces d'actions combinatoires. En tirant parti du pouvoir expressif des modèles de diffusion discrets et en stabilisant l'apprentissage par l'appariement de distributions basé sur PMD, le cadre gère efficacement des problèmes de prise de décision complexes où les méthodes traditionnelles échouent souvent.

Les auteurs soulignent que leur approche offre un avantage distinct par rapport aux solveurs discrets boîte noire standards (par exemple, les algorithmes évolutionnaires) en apprenant une politique conditionnée à l'état qui exploite les dynamiques de transition et se généralise à des états non vus, plutôt qu'en optimisant des objectifs statiques à partir de zéro. De plus, la nature découplée de la méthode stabilise le processus d'apprentissage, améliorant considérablement les performances dans des espaces discrets complexes et non structurés.