🤖 machine learning

Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities

Cet article présente un cadre quotient-DAG et l'algorithme Forward-DP pour éliminer la variance de nuisance et permettre le calcul exact des propensions de listes non ordonnées afin d'évaluer efficacement les politiques hors politique dans les systèmes de recommandation autorégressifs.

Auteurs originaux : Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

Publié 2026-05-29

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un chef essayant d'évaluer la qualité d'une nouvelle recette (la Politique Cible), mais que vous ne pouvez pas réellement la cuisiner dans votre propre cuisine car c'est trop coûteux ou risqué. À la place, vous avez un carnet rempli de recettes cuisinées par un autre chef (la Politique de Comportement) dans le passé. Votre objectif est d'estimer à quel point la nouvelle recette serait délicieuse en utilisant uniquement ce vieux carnet. C'est le problème central de l'Évaluation Hors-Politique (OPE).

Le Problème : Compter les Mauvaises Choses

Habituellement, pour juger la nouvelle recette, vous examinez chaque étape prise par l'ancien chef. Vous dites : « D'accord, ils ont ajouté du sel, puis du poivre, puis de l'ail. » Vous calculez un score basé sur cette séquence exacte.

Mais voici le hic : parfois, l'ordre dans lequel vous ajoutez les ingrédients ne change pas réellement le goût du plat final.

Le Scénario : Imaginez un « plateau » d'articles (comme une playlist de 5 chansons ou un plateau de 5 apéritifs). Le client ne se soucie que de quels 5 articles sont sur le plateau, pas de l'ordre dans lequel le chef les y a placés.
L'Erreur : L'ancien carnet enregistre l'ordre (Chanson A, puis B, puis C...). Si vous calculez votre score basé sur cet ordre spécifique, vous traitez l'« ordre » comme important. Mais puisque le client s'en fiche, vous ajoutez du « bruit » à votre calcul.
Le Résultat : Ce bruit crée une énorme quantité de confusion (variance). C'est comme essayer de deviner le poids d'une valise en pesant chaque chaussette à l'intérieur individuellement, plutôt que de simplement peser la valise dans son ensemble. Vous obtenez beaucoup de réponses différentes selon la façon dont vous avez compté les chaussettes.

De plus, calculer la « vraie » probabilité d'obtenir un groupe spécifique de 5 articles (en ignorant l'ordre) est un cauchemar mathématique. Si vous avez 5 articles, il y a 120 façons différentes (5 factorielles) dont ils auraient pu être choisis. Faire ce calcul pour chaque entrée de votre carnet est computationnellement impossible pour de grands groupes.

La Solution : Le « DAG Quotient » (La Carte de Regroupement)

Les auteurs proposent une nouvelle façon astucieuse d'observer les données. Au lieu d'examiner chaque chemin individuel que le chef a emprunté, ils suggèrent de regrouper tous les chemins qui mènent au même résultat.

L'Analogie : Imaginez un arbre géant où chaque branche représente un ordre différent d'ajout d'ingrédients.
- Ancienne Méthode : Vous parcourez chaque branche individuelle, mesurez le poids et essayez de les moyenner.
- Nouvelle Méthode (DAG Quotient) : Vous réalisez que toutes les branches qui aboutissent au même ensemble d'ingrédients sont en fait le même « nœud » sur votre carte. Vous effondrez toutes ces branches en un seul point.
- La Carte : Cela crée un « Graphe Acyclique Dirigé » (DAG) — une carte où vous ne vous souciez que de l'ensemble d'articles choisis jusqu'à présent, pas de l'ordre.

Le Tour de Magie : L'Échantillonnage par Importance à Flux Avant

Une fois que vous avez cette carte simplifiée, vous devez connaître la probabilité que le nouveau chef atteigne un « ensemble » spécifique par rapport à l'ancien chef.

L'Ancienne Méthode : Vous devriez sommer les probabilités de tous les 120 ordres différents pour obtenir la réponse.
La Nouvelle Méthode (Forward-DP) : Les auteurs ont inventé une méthode appelée Forward-DP (Programmation Dynamique). Imaginez cela comme une calculatrice intelligente qui construit la réponse étape par étape.
- Elle commence avec un plateau vide (probabilité 1).
- Elle demande : « Si j'ai 1 article, quelle est la chance d'ajouter un 2ème ? »
- Elle demande : « Si j'ai 2 articles, quelle est la chance d'ajouter un 3ème ? »
- Elle continue de construire la probabilité de l'ensemble complet sans jamais avoir besoin de lister les 120 ordres.

Cette méthode est exacte (elle ne devine pas) et rapide. Au lieu de prendre des années pour calculer (temps factoriel), elle prend un temps gérable (exponentiel par rapport à la taille du plateau, mais polynomial par rapport à la taille du menu).

Pourquoi Cela Compte

Moins de Bruit : En ignorant les détails « d'ordre » non pertinents, les mathématiques deviennent beaucoup plus claires. Les estimations sont plus précises et stables.
Faisabilité : Cela rend possible l'évaluation de systèmes de recommandation complexes (comme « montrez-moi 10 films ») qui étaient auparavant trop difficiles à calculer exactement.
Test Réel : Les auteurs ont testé cela sur :
- Données Médicales : Simulant des traitements pour le sepsis (infection du sang). Leur méthode a donné des prédictions beaucoup plus précises des résultats des patients que les anciennes méthodes.
- Données de Recommandation : Utilisant un ensemble de données appelé KuaiRec (recommandations vidéo). Ils ont montré que leur méthode pouvait calculer la probabilité « vraie » d'un groupe de vidéos étant recommandé en quelques secondes, alors que l'ancienne méthode prendrait des jours ou serait impossible.

Résumé

L'article introduit une façon de cesser de sur-analyser le « comment » (l'ordre des actions) et de se concentrer sur le « quoi » (l'ensemble final d'articles). En regroupant les chemins équivalents et en utilisant une méthode de calcul intelligente et étape par étape (Forward-DP), ils peuvent évaluer de nouvelles stratégies beaucoup plus précisément et efficacement, en particulier dans des domaines comme la santé et les moteurs de recommandation où tester de nouvelles idées dans la réalité est trop dangereux ou coûteux.

Résumé technique : DAG quotients pour l'évaluation hors politique

Énoncé du problème

L'évaluation hors politique (OPE) estime la performance d'une politique cible $\pi$ à l'aide de données collectées par une politique comportementale $\beta$ . L'échantillonnage d'importance (IS) standard réajuste les trajectoires enregistrées par le produit des rapports de probabilités d'action cible/comportementale. Cependant, cette approche traite souvent les détails du processus de génération comme significatifs, même lorsque l'objectif d'évaluation les ignore.

Un cas principal de ce problème se manifeste dans la recommandation de listes (slate), où les générateurs modernes construisent souvent des listes (ensembles d'éléments) de manière autorégressive, exposant les probabilités à chaque étape selon un ordre spécifique. Pourtant, la récompense et les estimateurs en aval dépendent souvent uniquement de la liste non ordonnée. L'IS de trajectoire standard attribue un rapport de vraisemblance à un chemin ordonné spécifique, créant un « écart de propension conjointe » : l'enregistreur expose une probabilité d'ordre, tandis que l'estimateur nécessite la probabilité totale de la liste non ordonnée. Le calcul de cette propension non ordonnée exacte nécessite généralement de sommer sur tous les $K!$ ordres de génération, ce qui est computationnellement intraitable pour des tailles de listes modérées. De plus, traiter l'ordre comme significatif introduit une variance de nuisance lorsque la récompense est invariante à l'ordre de génération.

Méthodologie

L'article introduit une vue par DAG quotient pour résoudre ces problèmes. L'idée centrale est de quotienter l'arbre de déploiement des préfixes d'historique par une relation d'équivalence suffisante pour l'objectif d'évaluation.

DAG quotient et flux avant :
- L'arbre de déploiement est effondré en fusionnant les préfixes d'historique qui sont équivalents pour l'objectif d'évaluation (par exemple, les préfixes contenant le même ensemble d'éléments sélectionnés, indépendamment de l'ordre).
- Cela forme un graphe orienté acyclique (DAG) en couches où les nœuds représentent des classes d'équivalence (états quotients).
- Au lieu de pondérer par le rapport d'un chemin réalisé unique, la méthode attribue des poids en utilisant le rapport de flux avant $F_\pi(z)/F_\beta(z)$ , où $F_\mu(z)$ est la masse de probabilité atteignant le nœud $z$ sous la politique $\mu$ .
- Cette approche généralise les méthodes existantes : l'IS décision par décision, l'IS marginalisé et l'IS à abstraction connue (MIS) sont des cas particuliers correspondant à différents choix de relations d'équivalence.
Échantillonnage d'importance par flux avant (FF-IS) :
- Pour l'OPE générale à horizon fini, l'estimateur remplace le rapport de préfixe échantillonné dans l'IS décision par décision (PDIS) par le rapport de vraisemblance quotient.
- L'analyse théorique montre que pour les retours mesurables par le quotient terminal, cette pondération élimine le décalage cible-comportemental « intra-classe », fournissant une expression exacte de l'écart de variance qui quantifie la réduction de la variance de nuisance.
Rétropropagation avant (Forward-DP) pour l'OPE de listes :
- L'article spécialise ce cadre à la génération autorégressive de listes sous une interface suffisante par ensemble (Définition 1). Une politique est suffisante par ensemble si la probabilité de sélectionner l'élément suivant dépend uniquement du contexte et de l'ensemble des éléments déjà sélectionnés, et non de leur ordre.
- Sous la suffisance par ensemble, le quotient de permutation correspond à un DAG de sous-ensembles, où les nœuds sont des sous-ensembles du catalogue et les arêtes ajoutent des éléments non sélectionnés.
- Algorithme Forward-DP : Un algorithme de programmation dynamique calcule la propension exacte de liste non ordonnée $F_\mu(S|x)$ $F_{μ} (S ∣ x)$ en sommant sur les sous-ensembles plutôt que sur les permutations.
  - Complexité : $O((M + K) \cdot 2^K)$ , où $M$ est la taille du catalogue et $K$ la taille de la liste. Cela évite l'énumération $K!$ .
  - Optimalité : L'article démontre que tout algorithme déterministe calculant des propensions non ordonnées exactes pour des politiques suffisantes par ensemble doit interroger chaque sous-ensemble propre de la liste dans le pire des cas, établissant ainsi Forward-DP comme optimal en requêtes jusqu'aux facteurs constants.

Contributions clés

Cadre théorique : Une vue unifiée par DAG quotient pour l'OPE qui dérive des rapports de vraisemblance exacts comme des rapports de flux avant sur un espace d'échantillonnage plus grossier.
Innovation algorithmique : L'algorithme Forward-DP, qui calcule des propensions exactes de listes non ordonnées pour des enregistreurs autorégressifs dépendants du contexte et suffisants par ensemble, en un temps polynomial par rapport à la taille du catalogue et exponentiel par rapport à la taille de la liste (traitable en paramètre fixe en $K$ ).
Réduction de variance : Une preuve formelle que la pondération par quotient élimine la composante de variance découlant des ordres de génération non pertinents (variance de nuisance d'ordre), en particulier lorsque les récompenses sont invariantes à la séquence de génération de la liste.
Primitives pour l'OPE de listes : L'introduction de Forward-DP comme primitive permettant une évaluation exacte basée sur la propension et une sélection de modèle pour les recommandateurs de listes basés sur des transformateurs, comblant ainsi le vide pour les enregistreurs dépendants du contexte où les formules fixes de Plackett-Luce ne s'appliquent pas.

Résultats expérimentaux

Les auteurs évaluent la méthode sur des benchmarks d'MDP à horizon fini et des tâches de recommandation de listes :

MDPs à horizon fini (Sepsis & ICU-Sepsis) :
- L'IS par flux avant (FF-IS) réduit considérablement l'erreur quadratique moyenne (RMSE) par rapport à l'IS de trajectoire standard et à d'autres références (par exemple, DualDICE, GenDICE).
- Sur le benchmark Sepsis, FF-WIS a réduit le RMSE de 0,291 (WIS) à 0,0568.
- Ces gains ont été obtenus en utilisant uniquement les trajectoires enregistrées sans ajuster de modèle de transition.
Expériences de listes KuaiRec :
- Efficacité computationnelle : Forward-DP calcule des propensions exactes des ordres de grandeur plus rapidement que l'énumération $K!$ . Pour $K=8$ , l'énumération a pris environ 97 108 secondes, tandis que Forward-DP a pris environ 8,94 secondes. Pour $K=12$ , l'énumération est infeasible, tandis que Forward-DP se termine en environ 13,7 secondes.
- OPE en aval : Les estimateurs utilisant les poids Forward-DP (FF-OIS, FF-DR) ont systématiquement surpassé leurs homologues pondérés par trajectoire (OIS, DR) pour toutes les tailles de listes ( $K \in \{4, 6, 8\}$ ) en termes de RMSE.
- Sélection de modèle : Dans la sélection de modèle hors politique parmi des recommandateurs transformateurs autorégressifs, les estimateurs utilisant Forward-DP (par exemple, Tree-DR, DP-OPCB-DR) ont atteint une précision Top-1 supérieure, une corrélation de Spearman plus élevée et un regret plus faible que les méthodes basées sur les trajectoires.

Signification et affirmations

L'article affirme que le cadre proposé fournit une Rao–Blackwellisation de l'IS décision par décision. En quotientant l'arbre de déploiement sous des relations d'équivalence suffisantes, la méthode élimine la variance de nuisance associée aux détails d'historique non pertinents (comme l'ordre de génération dans la recommandation de listes).

Spécifiquement pour la recommandation de listes, l'article affirme que Forward-DP fournit la primitive OPE manquante pour les enregistreurs autorégressifs dépendants du contexte. Contrairement aux méthodes précédentes qui reposent sur des hypothèses de scores fixes (où les scores des éléments ne changent pas avec la liste partielle) ou des approximations de Monte Carlo, Forward-DP gère le cas où le softmax de l'élément suivant dépend de la liste partielle, en calculant la propension conjointe exacte sans énumération factorielle. Cela permet une évaluation pratique et exacte basée sur la propension et une sélection de modèle pour les recommandateurs modernes basés sur des transformateurs.

Les auteurs notent des limitations, notamment l'exigence de l'hypothèse de suffisance par ensemble (qui peut nécessiter une canonicalisation de l'ensemble sélectionné lors du déploiement) et l'échelle exponentielle avec la taille de la liste $K$ , bien qu'ils soutiennent que cela reste pratique pour les tailles de listes typiques ( $K \le 10$ ) où $K!$ est intraitable.