Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actions

Résumé Technique : Politique de Flux Sphérique Latent pour l'Apprentissage par Renforcement avec Actions Combinatoires

1. Définition du Problème

L'article traite du défi consistant à appliquer l'apprentissage par renforcement (RL) à des environnements dotés d'espaces d'actions combinatoires. Dans ces contextes, les actions sont des décisions structurées (par exemple, la sélection de sous-ensembles, le routage, l'ordonnancement) régies par des contraintes de faisabilité strictes. L'ensemble des actions faisables, $\mathcal{A}(s)$, croît typiquement de manière exponentielle avec la taille du problème, rendant la paramétrisation directe de la politique sur toutes les actions valides intraçable.

Les approches existantes font face à un compromis :

• Optimisation de la valeur basée sur un solveur : Intègre des réseaux de valeur dans des programmes de programmation linéaire en nombres entiers mixtes (MIP) pour extraire des actions gloutonnes. Cela nécessite souvent des architectures de valeur spécifiques et passe mal à l'échelle avec la complexité du réseau.
• Couches de décision induites par l'optimisation : Apprend des politiques structurées de bout en bout mais produit généralement des politiques déterministes, ce qui limite l'expressivité et l'exploration dans des paysages complexes.

Bien que les modèles génératifs modernes (diffusion et modèles de flux) aient montré un succès dans le contrôle continu en représentant des distributions stochastiques riches et multimodales, ils ne peuvent pas être appliqués directement au RL combinatoire car ils n'imposent pas intrinsèquement de contraintes de faisabilité discrètes. Une adaptation naïve conduit à des actions infaisables.

2. Méthodologie : LSFLOW

Les auteurs proposent LSFLOW (Latent Spherical Flow Policy), un cadre qui découple l'expressivité de la politique de l'application de la faisabilité. L'idée centrale est d'apprendre une politique stochastique dans un espace latent continu compact et de déléguer la faisabilité à un solveur d'optimisation combinatoire (CO).

A. Politique de Flux Sphérique Induite par le Solveur

• Représentation Latente : Au lieu de produire directement des actions, la politique apprend une distribution sur des vecteurs de coût $\mathbf{c} \in \mathbb{R}^m$.
• Correspondance du Solveur : Un solveur CO associe un vecteur de coût échantillonné à une action faisable via un objectif linéaire : $\mathbf{a}^*(s, \mathbf{c}) = \arg\min_{\mathbf{a} \in \mathcal{A}(s)} \mathbf{c}^\top \mathbf{a}$.
• Contrainte Sphérique : En raison de l'invariance d'échelle positive du solveur (l'action optimale dépend uniquement de la direction de $\mathbf{c}$, et non de sa magnitude), l'espace latent est restreint à la sphère unité $\mathbb{S}^{m-1}$.
• Modèle Génératif : La politique $\pi_\theta(\mathbf{c} | s)$ est modélisée à l'aide d'un flux de correspondance sphérique (spherical flow matching). Elle apprend un champ de vecteurs dépendant du temps sur la sphère pour transporter une distribution de base vers une distribution cible de directions de coût. Cela permet à la politique de représenter n'importe quelle distribution stochastique sur les actions faisables sans les énumérer explicitement.

B. Entraînement Efficace dans l'Espace Latent
Pour éviter le goulot d'étranglement computationnel consistant à appeler le solveur CO de manière répétée pendant les mises à jour de la politique, LSFLOW entraîne à la fois l'acteur et le critique directement dans l'espace de coût latent.

• Critique : Un réseau de valeur $\tilde{Q}_\phi(s, \mathbf{c})$ est entraîné pour approximer $Q(s, \mathbf{a}^*(s, \mathbf{c}))$. Cela amortit les coûts du solveur, ne nécessitant qu'un seul appel au solveur par étape d'environnement plutôt que par proposition de politique.
• Mise à jour de la Politique : La politique est mise à jour à l'aide d'un objectif de correspondance de flux sphérique pondéré. Les propositions sont repondérées en fonction de la valeur estimée par le critique, déplaçant la distribution vers les directions de coût qui produisent des actions faisables de plus haute valeur.

C. Opérateur de Bellman Lissé
Un défi critique est que la correspondance entre la direction du coût et l'action est par morceaux constante et discontinue (en raison du solveur), ce qui entraîne une instabilité de l'apprentissage de la valeur.

• Lissage vMF : Les auteurs introduisent un noyau von Mises–Fisher (vMF) pour lisser l'opérateur de Bellman. Au lieu d'évaluer la valeur à une direction unique $\mathbf{c}$, la cible est calculée en moyennant sur un voisinage de directions échantillonnées à partir du noyau vMF.
• Garanties Théoriques : Les auteurs prouvent que cet opérateur lissé est une application contractante avec un point fixe unique qui est infiniment dérivable ($C^\infty$) par rapport à la direction du coût. Cela garantit des cibles d'apprentissage stables et à faible variance. Ils démontrent également qu'à mesure que le paramètre de concentration du noyau $\kappa \to \infty$, la valeur lissée converge vers la véritable fonction de valeur presque partout.

3. Contributions Clés

1. Premier Cadre de Flux/Diffusion pour le RL Combinatoire : LSFLOW est le premier cadre de politique transférant l'expressivité des modèles génératifs de type flux à des espaces d'actions combinatoires tout en garantissant la faisabilité via un solveur.
2. Optimisation Efficace dans l'Espace Latent : La méthode introduit un paradigme d'entraînement où l'acteur et le critique opèrent tous deux dans l'espace de coût latent, évitant les appels répétés au solveur pendant l'optimisation.
3. Apprentissage Stabilisé par Lissage : L'article propose un opérateur de Bellman lissé utilisant des noyaux vMF pour atténuer l'instabilité causée par les discontinuités induites par le solveur, fournissant des preuves théoriques de contraction et de lissage.

4. Résultats Expérimentaux

Les auteurs évaluent LSFLOW sur des benchmarks publics et une application réelle :

• Benchmarks Publics : Testé sur quatre tâches dynamiques (Ordonnancement, Routage, Assignation, Intervention) de Xu et al. (2025). LSFLOW a surpassé les meilleures lignes de base (incluant SEQUOIA et SRL) avec une récompense supérieure de 20,6 % en moyenne.
• Application Réelle : Appliqué à une tâche de dépistage des infections sexuellement transmissibles (IST) impliquant un criblage par réseau pour la gonorrhée, le VIH, la syphilis et le chlamydia. LSFLOW a démontré une efficacité de détection plus élevée (fraction de cas positifs trouvés) par rapport aux bases de référence, particulièrement dans les régimes de budget faible à moyen.
• Efficacité : LSFLOW était environ 3,0 fois plus rapide en temps d'entraînement que la ligne de base de RL structuré (SRL) déterministe, car il évite de dériver à travers le solveur ou de résoudre des MIP intégrés pendant l'entraînement.

5. Signification et Revendications

L'article affirme que LSFLOW offre une voie principled et scalable vers le RL avec des actions combinatoires. En transférant la charge de la faisabilité vers un solveur et en apprenant une politique stochastique expressive dans un espace sphérique latent, la méthode surmonte les limites des approches précédentes qui sacrifient soit la généralité (méthodes basées sur le solveur), soit l'expressivité (méthodes déterministes).

Les auteurs soulignent que leur approche transfère avec succès les avantages des politiques génératives modernes (multimodalité, exploration riche) aux domaines contraints. Ils reconnaissent des limites, notant que le lissage introduit un compromis biais-variance et que l'inférence nécessite toujours des appels au solveur, suggérant des travaux futurs sur le lissage adaptatif et le guidage appris pour réduire davantage le temps d'exécution.