Owen-Shapley Policy Optimization: A Principled RL Algorithm for Generative Search LLMs

L'article présente l'optimisation de politique Owen-Shapley (OSPO), un cadre d'apprentissage par renforcement novateur qui comble l'écart d'attribution de crédit dans les modèles de langage génératifs de recherche en redistribuant les récompenses au niveau de la séquence vers des segments de tokens sémantiquement cohérents à l'aide d'attributions Shapley-Owen, permettant ainsi une inférence robuste et sans étiquette de l'intention utilisateur latente sans nécessiter de modèles de valeur paramétriques.

L'essentiel

Imaginez que vous enseigniez à un robot à rédiger la liste de courses parfaite pour un client. Le robot écrit une longue phrase, comme : « J'ai besoin d'un blazer noir, d'un jean slim et d'un haut crème pour un look décontracté de bureau. »

Dans l'ancienne méthode d'enseignement de ce robot (utilisant des méthodes comme GRPO), vous attendiez que le robot termine toute la phrase, vérifiiez si le client avait acheté quelque chose, puis attribuiez au robot une seule note (une « récompense »). Si le client achetait le blazer, le robot obtenait un score élevé. S'il ne l'achetait pas, il obtenait un score faible.

Le Problème :
Le robot ne sait pas quelle partie de la phrase a mérité la note. Est-ce la partie « blazer noir » qui a fonctionné ? Ou était-ce le « jean slim » ? Ou peut-être le « haut crème » ? Parce que le robot reçoit la même note pour chaque mot qu'il écrit, il pourrait apprendre par accident que le mot « un » ou « et » est la partie la plus importante de la phrase. C'est comme un enseignant qui donne la note A à un élève pour un devoir entier sans lui indiquer quel paragraphe était le meilleur, de sorte que l'élève continue d'écrire les mêmes paragraphes médiocres encore et encore.

La Solution : OSPO (Optimisation de Politique Owen-Shapley)
Les auteurs de cet article ont créé une nouvelle méthode appelée OSPO. Ils utilisent un concept de la théorie des jeux (mathématiques sur la façon dont les équipes partagent les crédits) pour déterminer exactement quels mots ou quelles phrases ont aidé le robot à réussir.

Voici comment cela fonctionne, en utilisant une analogie simple :

1. L'expérience du « Test de Goût »

Imaginez que la phrase du robot est une soupe composée de différents ingrédients (phrases).

• Méthode Ancienne : Vous goûtez la soupe entière à la fin et dites : « C'est bon ! » Vous ne savez pas si le sel, le poivre ou les carottes l'ont rendue bonne.
• Méthode OSPO : Vous effectuez une série de mini-tests de goût.
  • Vous goûtez la soupe avec seulement les carottes. (Peut-être qu'elle est fade.)
  • Vous goûtez la soupe avec seulement le sel. (Peut-être qu'elle est trop salée.)
  • Vous goûtez la soupe avec des carottes et du sel. (Ah ! C'est délicieux !)
  • Vous goûtez la soupe avec des carottes, du sel et du poivre. (Encore mieux !)

En comparant ces différentes combinaisons, OSPO peut calculer mathématiquement exactement combien de crédit le « sel » (une phrase spécifique comme « slim ») mérite pour le résultat final délicieux.

2. L'Analogie de la « Carte de Crédit »

Dans l'ancienne méthode, la « carte de crédit » du robot (son signal d'apprentissage) est répartie équitablement entre tous les mots qu'il a écrits. S'il a écrit 100 mots, chaque mot reçoit 1 % du crédit.

Dans OSPO, la carte de crédit est répartie en fonction de la contribution marginale.

• Si la phrase « blazer noir » a été la clé pour trouver le bon produit, cette phrase reçoit une énorme part du crédit.
• Si la phrase « et ensuite » n'a pas aidé du tout, elle reçoit presque zéro crédit.
• Cela indique au robot : « Concentrez-vous sur l'écriture de plus de phrases de type « blazer noir » et arrêtez de perdre du temps avec des mots de remplissage. »

3. Pourquoi Cela Compte pour le Shopping

L'article a testé cela sur de vraies données de shopping (Amazon et H&M).

• Le Résultat : Le robot entraîné avec OSPO a appris deux fois plus vite que le robot entraîné avec l'ancienne méthode.
• La Robustesse : Même lorsque le robot a été testé sur un tout nouveau type de moteur de recherche (un qu'il n'avait jamais vu auparavant), il a toujours bien fonctionné. L'ancienne méthode avait tendance à « tricher » en mémorisant des modèles spécifiques de l'ancien moteur de recherche, mais OSPO a appris le sens réel des mots, lui permettant de s'adapter à de nouvelles situations.

Résumé

Pensez à OSPO comme à un entraîneur intelligent qui ne dit pas simplement « Bon match ! » à la fin d'un match. Au lieu de cela, l'entraîneur regarde la vidéo, met en pause à chaque passe et dit : « Cette passe vers la gauche était parfaite (haut crédit), mais cette course au milieu était inutile (faible crédit). »

En fournissant au robot des retours précis sur quelles parties spécifiques de sa réponse ont fonctionné, OSPO l'aide à apprendre à rédiger de meilleures recommandations d'achat plus précises, sans avoir besoin d'une IA « juge » complexe pour surveiller chaque étape du processus. Cela rend le processus d'apprentissage plus rapide, plus intelligent et plus fiable.

Résumé technique

Résumé Technique : Optimisation de Politique Owen-Shapley (OSPO)

1. Énoncé du Problème

Les modèles de langage de grande taille (LLM) sont de plus en plus déployés dans des systèmes de recommandation génératifs, où ils synthétisent les préférences des utilisateurs, affinent les requêtes et génèrent des artefacts en langage naturel pour conditionner la récupération et le classement en aval. Ces systèmes reposent souvent sur l'apprentissage par renforcement (RL) pour optimiser des signaux vérifiables au niveau de la séquence (par exemple, le NDCG de récupération) provenant de composants boîte noire tels que les récupérateurs ou les classeurs, évitant ainsi le besoin d'annotations humaines coûteuses.

Cependant, les méthodes standard de RL sans modèle de valeur, telles que l'optimisation de politique relative aux groupes (GRPO), font face à un écart critique d'attribution de crédit. Dans ces cadres, un avantage scalaire unique est attribué uniformément à tous les tokens d'une séquence générée, basé sur la récompense terminale. Cette approche obscurcit quelles phrases ou segments sémantiques spécifiques ont réellement conduit à l'utilité en aval. Par conséquent, les modèles peinent à distinguer les segments de raisonnement utiles des raccourcis exploitatifs, ce qui entraîne :

• Un apprentissage inefficace : Les mises à jour de gradient sont diluées sur des tokens non pertinents.
• Le piratage de récompense : Les modèles peuvent surajuster aux indices de surface dans les récupérateurs boîte noire plutôt que d'apprendre des représentations sémantiques robustes.
• Une mauvaise généralisation : L'attribution de crédit uniforme échoue à capturer la nature compositionnelle de l'intention de l'utilisateur, entraînant de mauvaises performances lors de décalages de distribution ou face à des récupérateurs inédits.

2. Méthodologie : Optimisation de Politique Owen-Shapley (OSPO)

OSPO comble l'écart d'attribution de crédit en redistribuant les avantages au niveau de la séquence basés sur les contributions marginales de segments de tokens sémantiquement cohérents. Il fonctionne sans modèles de valeur paramétriques (critiques), s'appuyant plutôt sur la théorie des jeux coopératifs pour attribuer la valeur.

Mécanisme Central

1. Segmentation et Coalitions :
   Une réponse générée $y$ est décomposée en $N$ segments sémantiquement significatifs (par exemple, phrases, phrases). OSPO traite ces segments comme des "joueurs" dans un jeu de coalition. Contrairement aux valeurs de Shapley classiques qui considèrent tous les $2^N$ sous-ensembles (computationalement intraitables), OSPO impose une contrainte de contiguïté. Il évalue uniquement les coalitions contiguës $S = \{i, i+1, \dots, i+w-1\}$, où $w$ est un hyperparamètre pour la largeur maximale de coalition. Cela réduit la complexité de $O(2^N)$ à $O(N \cdot w_{max})$, rendant l'évaluation en ligne réalisable pendant l'entraînement RL.

2. Calcul de la Valeur Owen :
   Pour chaque segment $j$, OSPO calcule la valeur Owen $\phi_j^{Owen}$, représentant sa contribution marginale attendue à la récompense totale. Cela est calculé en moyennant la différence de récompense $v(S \cup \{j\}) - v(S)$ sur toutes les coalitions contiguës $S$ où $j$ peut être ajouté tout en maintenant la contiguïté. La récompense $v(S)$ est obtenue en interrogeant le système en aval (par exemple, un récupérateur dense) avec la séquence partielle formée par la concaténation des segments dans $S$.

3. Redistribution de l'Avantage :
   OSPO comble le fossé entre les attributions au niveau du segment et les mises à jour de politique au niveau du token grâce à la redistribution de l'avantage :

   • Avantage de Groupe : Un avantage relatif de groupe standard $\hat{A}^{(g)}$ est calculé pour l'ensemble de la séquence basé sur la récompense terminale (similaire à GRPO).
   • Cartographie des Tokens : Les valeurs Owen au niveau du segment sont mappées vers des poids au niveau du token. Pour éviter le biais de longueur (où les séquences plus longues reçoivent des gradients disproportionnellement faibles), l'avantage du token $A_t^{(g)}$ est calculé comme suit :
     $$A_t^{(g)} = T \cdot \tilde{\phi}_t^{(g)} \cdot \hat{A}^{(g)}$$
     où $T$ est la longueur de la séquence et $\tilde{\phi}_t$ est la valeur Owen normalisée pour le token $t$. Cela garantit que l'avantage moyen du token égale l'avantage de séquence original, indépendamment de la longueur.
   • Objectif : L'objectif de substitution standard PPO/GRPO est modifié pour utiliser ces avantages de tokens pondérés par Owen, concentrant les mises à jour de gradient sur les segments à haute contribution.

Variantes

L'article évalue trois stratégies de redistribution :

• OSPO-PROP : Redistribution proportionnelle basée sur les valeurs Owen.
• OSPO-RANK : Mappe les valeurs Owen vers des rangs ordinaux avant redistribution pour améliorer la robustesse face aux estimations bruitées.
• OSPO-CLIP : Contraint les avantages redistribués en utilisant l'inégalité de Tchebychev pour borner les valeurs aberrantes.

3. Contributions Clés

• Attribution de Crédit Principée sans Critiques : OSPO introduit un cadre qui réalise une attribution de crédit fine dans le RL sans modèle de valeur en exploitant les valeurs Owen-Shapley, éliminant le besoin de réseaux de valeur appris ou de modèles de récompense de processus qui nécessitent des étiquettes de étapes intermédiaires.
• Attribution Basée sur les Coalitions : En modélisant les segments sémantiquement cohérents comme des coalitions contiguës, OSPO capture comment les combinaisons de phrases influencent conjointement les récompenses en aval, s'alignant sur la structure linguistique des sorties LLM dans les tâches de recommandation.
• Redistribution Invariante à la Longueur : La méthode introduit une garantie théorique (Lemme A.1) que le schéma de redistribution est invariant à la longueur, empêchant le biais d'entraînement où les séquences plus longues sont systématiquement sous-pénalisées ou sur-récompensées.
• Généralisation Agnostique au Récupérateur : L'approche apprend des représentations de requêtes qui se transfèrent efficacement à travers différents espaces d'encodage et récupérateurs inédits, abordant une limitation clé des méthodes standard de RLHF.

4. Résultats Expérimentaux

OSPO a été évalué sur deux tâches de commerce électronique : Affinement de Requêtes de Recherche de Produits (jeu de données ESCI) et Résumé de Profil Utilisateur (jeu de données H&M Fashion).

• Gains de Performance :

  • Sur le jeu de données ESCI, OSPO-PROP (modèle 7B) a atteint un NDCG de 0,522, surpassant GRPO (0,418) de 24,9 % et DPO (0,431) de 21,1 %.
  • Sur le jeu de données H&M Fashion plus complexe, OSPO-PROP a atteint un NDCG de 0,436, dépassant GRPO (0,379) de 15,0 %.
  • Notamment, OSPO-PROP avec 7 milliards de paramètres a surpassé un modèle de 32 milliards sur ESCI et l'a presque égalé sur H&M, démontrant une efficacité d'échantillonnage supérieure.

• Efficacité d'Échantillonnage :
  La dynamique d'entraînement a montré que OSPO atteignait la performance cible (85 % NDCG) en environ 400 étapes, tandis que GRPO nécessitait plus de 800 étapes pour approcher une performance similaire, malgré des données d'entraînement identiques.

• Généralisation et Robustesse :

  • Décalage du Récupérateur : Lorsqu'évalué sur des récupérateurs inédits (décalages d'encodage inter-domaines), OSPO a maintenu de solides performances de classement, tandis que GRPO et les bases de référence hors ligne (SFT, DPO) se sont dégradés de manière significative.
  • Atténuation du Piratage de Récompense : GRPO a exhibé des comportements de "piratage de récompense", tels que la réduction du nombre de tokens de raisonnement et la convergence vers des solutions sous-optimales à faible variance. OSPO a maintenu des traces de raisonnement plus longues et plus diversifiées et une variance de récompense plus élevée, indiquant un apprentissage stable.
  • Validité de l'Attribution : L'analyse de corrélation a montré que les attributions de crédit Owen-Shapley étaient 3,3 fois plus corrélées avec la qualité de récupération de phrases solo de vérité terrain que les proxies basés sur l'attention ou TF-IDF.

• Études d'Ablation :

  • Structure de Coalition : Des coalitions contiguës de largeur modérée (par exemple, $w=4$ à $8$) ont produit les meilleurs résultats. Des coalitions étroites ont conduit à un surajustement sur les co-occurrences locales, tandis que des coalitions non contiguës ont causé un effondrement des performances dû à une incohérence sémantique.
  • Profondeur d'Échantillonnage : Un échantillonnage Monte Carlo suffisant (déroulements) était critique ; la réduction des générations de 8 à 2 a provoqué une chute brutale de la précision.

5. Signification et Revendications

L'article revendique que OSPO représente une avancée significative dans l'alignement des LLM pour les tâches basées sur la récupération en résolvant le problème d'attribution de crédit inhérent au RL sans modèle de valeur. Sa signification réside dans :

1. Efficacité : Atteindre des performances de pointe avec des modèles plus petits (7B) par rapport à des bases de référence beaucoup plus grandes, réduisant les coûts computationnels pour le déploiement.
2. Interprétabilité : Fournir un mécanisme principé pour identifier quelles parties d'une réponse conduisent au succès, allant au-delà de l'attribution de crédit uniforme "boîte noire".
3. Robustesse : Démontrer que les attributions basées sur les coalitions apprennent des signaux transférables qui se généralisent à travers différents moteurs de récupération et décalages de distribution, une exigence critique pour les systèmes de recommandation réels où l'intention de l'utilisateur est latente et le feedback est rare.

Les auteurs concluent que OSPO apprend non pas en mémorisant des modèles de feedback, mais en exploitant des attributions basées sur des coalitions principées, favorisant des comportements stables, transférables et interprétables dans les LLM de recherche générative. Un travail futur est suggéré pour étendre ces crédits basés sur les coalitions aux interactions multi-tours et à la coordination multi-agents.