Dans ce travail, nous présentons un framework d'apprentissage par renforcement invariant à l'ordre de génération pour l'optimisation combinatoire de type boîte noire. Les algorithmes classiques d'estimation de distribution (EDA), sous-classe des algorithmes évolutionnaires, résolvent de tels problèmes en apprenant et en échantillonnant un modèle probabiliste des solutions prometteuses. Ils s'appuient souvent sur l'apprentissage de graphes explicites de dépendance entre variables, ce qui peut s'avérer coûteux et ne pas permettre de saisir efficacement les interactions complexes entre les variables. Dans ce travail, nous paramétrons un modèle génératif autorégressif multivarié entraîné sans ordre fixe des variables. En échantillonnant des ordres de génération aléatoires pendant l'entraînement (une forme de dropout préservant les informations), le modèle est encouragé à être invariant par rapport à l'ordre des variables, ce qui favorise l'exploration de l'espace de recherche et façonne le modèle pour qu'il se concentre sur les dépendances variables les plus pertinentes, améliorant ainsi l'efficacité de l'échantillonnage de nouvelles solutions. Nous adaptons l'algorithme d'apprentissage par renforcement Generalized Reinforcement Policy Optimization (GRPO) [Shao et al. 2024] à ce contexte, ce qui permet de fournir des mises à jour stables du gradient des politiques à partir d'avantages invariants à toute transformation monotone de la fonction objectif. En comparaison avec un large éventail d'algorithmes de référence et sur un panel diversifié d'instances de problèmes de tailles variées, notre méthode atteint fréquemment les meilleures performances.