💬 NLP

On Advantage Estimates for Max@K Policy Gradients

Cet article introduit MaxPO, une nouvelle méthode de gradient de politique pour l'optimisation des objectifs max@K en apprentissage par renforcement avec récompenses vérifiables, qui utilise une nouvelle base Leave-Two-Out pour assurer des avantages centrés, réduire la variance du gradient et unifier les estimateurs existants pour un post-entraînement plus efficace des LLM.

Auteurs originaux : Shota Takashiro, Soichiro Nishimori, Paavo Parmas, Yongmin Kim, Kohsei Matsutani, Gouki Minegishi, Yusuke Iwasawa, Takeshi Kojima, Yutaka Matsuo

Publié 2026-06-05

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shota Takashiro, Soichiro Nishimori, Paavo Parmas, Yongmin Kim, Kohsei Matsutani, Gouki Minegishi, Yusuke Iwasawa, Takeshi Kojima, Yutaka Matsuo

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 enseignant essayant de former un élève à résoudre un problème de mathématiques très difficile. L'élève est une IA, et le problème est une « tâche de raisonnement ».

Dans l'ancienne méthode d'entraînement de ces IA (Apprentissage par Renforcement), l'enseignant demandait à l'élève de tenter de résoudre le problème une seule fois. Si la réponse était fausse, l'élève ne recevait aucun retour (récompense nulle). S'il avait raison, il recevait une étoile d'or. Le problème ? L'élève devait deviner le bon chemin dans un immense labyrinthe de possibilités, et obtenir une étoile d'or était si rare que l'élève restait souvent bloqué, ne sachant pas quels essais étaient « presque corrects » et lesquels étaient « complètement faux ».

Pour corriger cela, les chercheurs ont commencé une nouvelle stratégie : l'approche du « Tenter de nombreuses fois ».

Au lieu de demander à l'élève de résoudre le problème une seule fois, l'enseignant lui demande de générer K solutions différentes en même temps. Le but n'est pas seulement d'obtenir une seule bonne réponse ; c'est de s'assurer qu'au moins une de ces K tentatives est correcte. C'est ce qu'on appelle l'optimisation pour Max@K (ou Pass@K).

Le problème avec les anciennes méthodes de « Tentative multiple »

L'article soutient que, bien que cette approche de « Tenter de nombreuses fois » soit excellente, les mathématiques utilisées pour enseigner à l'IA comment s'améliorer étaient légèrement erronées.

Imaginez que vous avez un groupe de 8 élèves (un « batch ») essayant de résoudre un puzzle. Vous voulez dire à chaque élève comment il s'en est sorti.

L'ancienne méthode (EI uniquement) : Elle regardait la réponse d'un élève et la comparait à la meilleure réponse des 7 autres élèves. Si l'élève faisait mieux que les autres, il recevait un énorme signal « Bon travail ! ». S'il faisait moins bien, il recevait un signal « 0 ».
La faille : Comme le signal « Bon travail ! » était toujours positif (ou nul) et jamais négatif, l'enseignant disait essentiellement : « Vous faites toujours mieux que la moyenne ! ». C'est trompeur. C'est comme un entraîneur qui ne dirait que « Bravo ! » et ne pointerait jamais du doigt qu'un joueur est en réalité en dessous de son véritable potentiel. Cela crée beaucoup de « bruit » (variance) dans l'apprentissage, rendant l'apprentissage de l'IA instable et lent.

La solution : La base de référence « Leave-Two-Out »

Les auteurs de cet article proposent une manière plus intelligente de noter les élèves, qu'ils appellent MaxPO (Max@K Policy Optimization).

Ils introduisent une nouvelle règle de notation, qu'ils appellent la base de référence Leave-Two-Out (L2O) (Retirer deux éléments). Voici comment cela fonctionne en utilisant une analogie simple :

Imaginez que vous jugez un concours de talents avec 8 candidats.

L'ancienne méthode : Pour juger le Candidat A, vous le comparez au meilleur des 7 autres. Si A est le meilleur, il reçoit un score élevé. S'il ne l'est pas, il reçoit un zéro. C'est biaisé car le « meilleur des 7 autres » est une cible mouvante qui change selon qui est présent dans la pièce.
La nouvelle méthode (L2O) : Pour juger le Candidat A, vous retirez temporairement le Candidat A et le Candidat B de la pièce. Vous regardez ensuite les 6 personnes restantes pour voir à quoi ressemble une performance « équitable » moyenne.
- Vous calculez comment le Candidat A aurait performé face à ce groupe « équitable ».
- Crucialement, en retirant deux personnes, vous vous assurez que le groupe « équitable » n'inclut pas accidentellement la personne que vous essayez de juger (le Candidat A) ou un « rival » spécifique (le Candidat B) qui pourrait fausser la comparaison.

Pourquoi est-ce mieux ?
Cette méthode garantit que le score « moyen » de l'ensemble du groupe est exactement égal à zéro. Certains élèves obtiennent un score positif (ils ont fait mieux que la moyenne équitable), et d'autres un score négatif (ils ont fait moins bien). Ces scores positifs et négatifs s'annulent parfaitement.

Le résultat : L'IA reçoit un signal beaucoup plus clair et moins « bruyant ». Elle sait exactement où elle se situe par rapport à une base de référence équitable, plutôt que de simplement se faire dire « tu es super » ou « tu ne vaux rien ».

Ce que l'article a découvert

Les chercheurs ont testé cette nouvelle méthode « Leave-Two-Out » de deux manières :

Dans des jeux simples (Bandits et Labyrinthes) : Ils ont montré que leur nouvelle méthode réduisait le « bruit » du signal d'apprentissage d'une marge énorme (jusqu'à 77 % de bruit en moins dans certains cas). Cela signifie que l'IA apprend de manière plus régulière et ne se laisse pas confondre par les fluctuations aléatoires.
Dans de vrais modèles d'IA (LLM) : Ils ont testé cela sur de grands modèles de langage (comme Llama et Qwen) essayant de résoudre des problèmes mathématiques.
- Le résultat : L'IA entraînée avec leur nouvelle méthode (MaxPO) est devenue nettement meilleure pour résoudre des problèmes lorsqu'on lui permet d'essayer de nombreuses fois (par exemple, Pass@256).
- Sur le modèle Qwen, elle a amélioré le taux de réussite de 5,2 %.
- Sur le modèle Llama, elle a amélioré le taux de réussite de 2,4 %.

La vue d'ensemble

Considérez l'ancienne méthode comme un entraîneur excessivement optimiste qui donne un autocollant « Bon travail » à tout le monde, même quand ils sont en difficulté. La nouvelle méthode (MaxPO) est un entraîneur qui utilise un système de notation strict, équitable et équilibré. En éliminant le « bruit » et en centrant les scores autour de zéro, l'IA peut apprendre beaucoup plus rapidement et efficacement, surtout lorsque l'objectif est de trouver au moins une réponse correcte parmi de nombreuses tentatives.

L'article conclut que cette approche « Leave-Two-Out » est la manière mathématiquement correcte d'entraîner les IA pour ces tâches de « tentative multiple », fournissant une base unifiée et stable pour les améliorations futures.

Résumé technique : Sur les estimations d'avantage pour les gradients de politique Max@K

Énoncé du problème

L'apprentissage par renforcement avec récompenses vérifiables (RLVR) est un paradigme dominant pour le post-entraînement des grands modèles de langage (LLM) sur des tâches de raisonnement. Cependant, ces contextes reposent généralement sur des récompenses éparses basées sur le résultat (par exemple, un signal binaire correct/incorrect), ce qui rend l'exploration difficile dans de grands espaces combinatoires. Bien que des méthodes telles que la régularisation de l'entropie et les bonus basés sur le comptage existent, elles introduisent des objectifs auxiliaires qui nécessitent un réglage minutieux.

Une approche complémentaire consiste à optimiser directement les objectifs d'inférence tels que le pass@K (la probabilité qu'au moins une des $K$ complétions échantillonnées soit correcte) et sa généralisation continue, le max@K (l'espérance du maximum de récompense parmi $K$ échantillons). Plusieurs travaux récents ont proposé des estimateurs de gradient de politique (PG) non biaisés pour ces objectifs. Cependant, les relations entre ces estimateurs restent obscures. Plus précisément, les estimateurs existants utilisent souvent des signaux, des bases (baselines) et des normalisations différents. Un problème critique identifié dans ce travail est que les estimateurs de pointe (par exemple, ceux basés sur l'amélioration attendue ou Expected Improvement) sont des estimateurs PG non biaisés mais produisent des avantages non centrés. Un avantage non centré (ayant une moyenne non nulle) correspond à une base sous-estimée, ce qui peut orienter l'optimisation vers des actions sous-optimales et augmenter la variance du gradient.

Méthodologie

Le papier propose MaxPO (Max@K Policy Optimization), une méthode qui introduit une base Leave-Two-Out (L2O) pour corriger l'estimation de l'avantage pour les objectifs max@k.

1. Analyse des estimateurs existants

Les auteurs réexaminent l'estimateur d'amélioration attendue (EI) utilisé dans les travaux antérieurs (par exemple, Walder et Karkhanis [54]). Ils démontrent que, bien que l'estimateur basé sur l'EI soit un estimateur PG non biaisé, le signal d'avantage résultant $s(a)$ est strictement non négatif (en raison de l'opération ReLU dans la définition de l'EI). Par conséquent, $E[s(a)] > 0$ , ce qui signifie que l'avantage n'est pas centré. Ce manque de centrage laisse une marge de réduction de la variance.

2. La base Leave-Two-Out (L2O)

Pour obtenir un avantage exactement centré tout en préservant l'absence de biais de la PG, les auteurs introduisent la base L2O.

Le défi : Une base standard Leave-One-Out (L1O) échoue dans le contexte max@K car la récompense d'un échantillon $i$ peut influencer implicitement le calcul de l'avantage d'autres échantillons $j$ (car $i$ agit comme un comparateur potentiel dans l'opération max). Cette dépendance viole la condition d'indépendance requise pour une estimation PG non biaisée.
La solution : La base L2O $b_{-i}^{L2O}$ est calculée en faisant la moyenne des scores d'amélioration attendue de tous les autres échantillons $j$ , où chaque score est calculé sur un sous-ensemble de comparateurs excluant à la fois l'échantillon cible $i$ et l'échantillon $j$ lui-même.
Propriétés :
- Indépendance : En excluant $i$ de l'ensemble des comparateurs pour tout $j$ , la base $b_{-i}^{L2O}$ est indépendante de la récompense $r_i$ , garantissant que l'estimateur PG reste non biaisé.
- Centrage : Les auteurs prouvent que l'avantage moyen réalisé par lot est exactement nul pour chaque lot échantillonné : $\frac{1}{B}\sum_{i=1}^B (s_i - b_{-i}^{L2O}) = 0$ .
- Efficacité : Bien qu'un calcul naïf soit en $O(B^3)$ , les auteurs dérivent une implémentation vectorisée utilisant des formulations basées sur ReLU qui calcule la base L2O en $O(B^2)$ , ce qui la rend réalisable pour l'entraînement de LLM accéléré par GPU.

3. Avantage canonique à lot fini

Le papier dérive un avantage canonique à lot fini pour max@K, défini comme $u_i - v_i$ :

$u_i$ : La valeur espérée conditionnelle de max@K d'un groupe contenant la réponse $i$ .
$v_i$ : La valeur espérée de max@K leave-one-out calculée à partir de groupes excluant $i$ .
Les auteurs montrent que l'estimateur MaxPO (EI + L2O) récupère exactement ce signal canonique ( $s_i - b_{-i}^{L2O} = u_i - v_i$ ). Cela fournit une vue unifiée des estimateurs existants, les classant en "non centrés" (par exemple, EI-seul/PKPO) et "(normalisés) canoniques" (par exemple, MaxPO, et certaines variantes analytiques de pass@K).

4. Intégration dans l'entraînement des LLM

MaxPO est intégré dans les algorithmes d'apprentissage par renforcement basés sur des groupes (comme GRPO). Pour chaque prompt, un groupe de $G$ sorties est échantillonné. La base L2O est calculée au sein de chaque groupe pour générer des avantages au niveau de la séquence, qui sont ensuite diffusés aux pertes au niveau du jeton (token-level).

Contributions clés

Identification des avantages non centrés : Le papier identifie que les principaux estimateurs PG de max@K (spécifiquement ceux basés sur l'EI) sont des estimateurs de gradient non biaisés mais ne produisent pas d'avantages centrés, ce qui entraîne des propriétés de variance sous-optimales.
Base Leave-Two-Out (L2O) : Une conception de base novatrice qui préserve l'absence de biais de la PG dans le contexte non linéaire de max@K tout en garantissant que l'avantage réalisé par lot est de moyenne nulle.
Unification canonique : La dérivation de l'avantage canonique à lot fini ( $u_i - v_i$ ) et la preuve que MaxPO récupère ce signal, offrant un cadre unifié pour comparer et catégoriser les estimateurs de pass@K/max@K existants.
Implémentation efficace : Un algorithme vectorisé en $O(B^2)$ pour calculer la base L2O, permettant une application pratique dans le post-entraînement des LLM.

Résultats expérimentaux

Les auteurs valident la méthode via des expériences contrôlées de bandit/labyrinthe et des tâches de raisonnement de LLM.

Réduction de la variance : Dans les environnements de bandit, la base L2O réduit considérablement la variance du gradient par rapport aux estimateurs EI bruts, avec un effet croissant à mesure que la taille de l'espace d'action augmente. Dans l'entraînement de LLM (Llama-3.2-3B-Instruct), la méthode a réduit le proxy de variance du gradient de 77,4 % par rapport à PKPO (la base EI-seule).
Gains de performance : Sur cinq benchmarks de raisonnement mathématique (AIME24, AIME25, AMC23, MATH500, Minerva), MaxPO a surpassé les bases solides incluant PKPO, GRPO et Entropy-Adv.
- Sur Qwen2.5-Math-7B, MaxPO a amélioré le pass@256 de 5,2 % par rapport à PKPO.
- Sur Llama-3.2-3B-Instruct, il a amélioré le pass@256 de 2,4 % par rapport à PKPO.
Mise à l'échelle du calcul d'inférence : Les gains de performance de MaxPO étaient plus prononcés aux niveaux de calcul d'inférence plus élevés (plus grand $k$ dans pass@k), suggérant que la méthode aide la politique à mieux utiliser les échantillons de test supplémentaires.

Signification et affirmations

Le papier affirme que MaxPO fournit une base principielle pour concevoir et comparer les estimateurs de gradient de politique pour les objectifs d'inférence comme max@K. En identifiant la forme canonique de l'avantage et en corrigeant le biais des estimateurs existants, ce travail offre une méthode pour améliorer l'efficacité et la stabilité des modèles de raisonnement en post-entraînement.

Les auteurs notent modestement que leur analyse se concentre sur l'estimation on-policy à lot fini, sous échantillonnage i.i.d. Ils reconnaissent les limites concernant l'entraînement off-policy, l'échantillonnage adaptatif et les contextes de générations corrélées comme des directions pour des travaux futurs. De plus, ils soulignent que bien que la méthode améliore l'optimisation, une meilleure optimisation des objectifs de raisonnement par échantillonnage répété comporte des impacts plus larges, pouvant renforcer des modèles qui pourraient être utilisés de manière abusive pour une assistance trompeuse ou la résolution automatisée de problèmes.