🤖 machine learning

Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

Cet article introduit le concours de décision markovien en tant que nouveau cadre pour l'apprentissage par renforcement avec des préférences par paires, prouvant que les politiques markoviennes stationnaires sont optimales et démontrant qu'un algorithme itératif simple atteint une efficacité d'apprentissage supérieure dans les problèmes à horizon long et à haute dimension par rapport aux méthodes antérieures.

Auteurs originaux : Jonathan Colaço Carr, Prakash Panangaden, Doina Precup, Benjamin Van Roy

Publié 2026-06-02

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jonathan Colaço Carr, Prakash Panangaden, Doina Precup, Benjamin Van Roy

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 essayez d'apprendre à un robot comment marcher, ou comment jouer à un jeu vidéo. Dans l'ancienne méthode pour faire cela (appelée Apprentissage par Renforcement), vous agissez comme un professeur strict avec une fiche de notation. Vous dites au robot : « Si tu fais ce pas, tu gagnes +10 points. Si tu tombes, tu perds -5 points. » Le seul objectif du robot est de maximiser ces points.

Mais parfois, donner un score spécifique à un robot est difficile. Il est plus facile de dire : « Je préfère cette façon de marcher à celle-là. » Peut-être que vous ne savez pas exactement pourquoi l'une est meilleure, vous savez juste que vous l'aimez davantage. C'est ce qu'on appelle la préférence par paire.

Le problème est que les anciennes méthodes pour enseigner aux robots en utilisant ces comparaisons de type « je préfère ceci à cela » ne fonctionnent bien que pour des jeux courts. Si le jeu dure longtemps (comme un robot apprenant à marcher pendant des heures), les anciennes méthodes deviennent confuses, lentes et inefficaces. Elles ne peuvent pas non plus garantir qu'une règle de décision simple, prise « sur le moment », soit aussi bonne qu'une règle complexe qui se souvient de tout ce qui s'est passé par le passé.

Ce document présente une nouvelle façon de résoudre cela, appelée Concours de Décision de Markov (Markov Decision Contest). Voici comment cela fonctionne, en utilisant quelques analogies simples :

1. Le nouveau jeu : Un « Concours » plutôt qu'une fiche de notation

Au lieu de donner une fiche de notation au robot, imaginez que le robot joue un tour contre un miroir de lui-même.

La configuration : Le robot joue un tour. Ensuite, un « clone » du robot joue un tour en utilisant une stratégie différente.
Le juge : Un juge regarde les deux tours et dit : « Je préfère le premier », ou « Je préfère le second », ou « Ils sont égaux ».
L'objectif : Le robot veut trouver une stratégie qui soit si bonne que, quelle que soit la stratégie utilisée par son clone, le juge ne préférera jamais systématiquement la stratégie du clone à celle du robot.

C'est ce que les auteurs appellent un Concours de Décision de Markov. Cela transforme le problème de « l'apprentissage à partir des préférences » en un jeu équitable entre deux joueurs.

2. La grande surprise : La simplicité gagne

Dans beaucoup de jeux complexes, vous pourriez penser qu'il faut se souvenir de chaque mouvement que vous avez fait (une stratégie « dépendante de l'historique ») pour gagner. Mais les auteurs ont prouvé quelque chose de surprenant : vous n'avez pas besoin de mémoire.

Ils ont prouvé qu'une stratégie « stationnaire » — une stratégie qui se contente de regarder la situation actuelle et décide quoi faire à l'instant présent sans se soucier du passé — est en réalité tout aussi bonne que n'importe quelle stratégie complexe qui se souvient de tout l'historique.

Analogie : Imaginez jouer aux échecs. Vous pourriez penser qu'il faut se souvenir des 50 derniers coups pour faire le meilleur coup. Les auteurs ont prouvé que pour ce type de jeu spécifique, vous n'avez besoin que de regarder l'échiquier en ce moment même pour faire le coup parfait. Cela rend le problème beaucoup plus facile à résoudre.

3. Résoudre l'énigme efficacement

Les auteurs ont montré que résoudre ce « Concours » est mathématiquement gérable.

Solution exacte : Si le problème n'est pas trop vaste, on peut le résoudre parfaitement en utilisant des outils mathématiques standards, et cela ne prendra pas une éternité. Il appartient à la même « classe de difficulté » que les problèmes mathématiques que nous savons déjà résoudre.
Solution approximative (l'algorithme « HPI ») : Pour les problèmes énormes et complexes (comme le contrôle de robots à haute dimension), ils ont créé un algorithme itératif simple appelé Hedged Policy Iteration (HPI).
- Comment ça marche : Le robot essaie une stratégie, voit comment elle se compare à un clone, et ajuste légèrement sa stratégie pour faire mieux la prochaine fois. Il fait cela encore et encore.
- Le résultat : Le robot devient de plus en plus performant, convergeant vers la meilleure stratégie à une vitesse prévisible.

4. Est-ce que cela a fonctionné ? (Les expériences)

Les auteurs ont testé leur nouvelle méthode contre les meilleures méthodes existantes pour l'apprentissage à partir des préférences. Ils ont utilisé un ensemble de tâches de contrôle de robot à long terme (des environnements simulés où les robots doivent marcher, atteindre un objet ou courir pendant des milliers d'étapes).

Le résultat : Leur nouvelle méthode (HPI) a appris beaucoup plus vite et plus efficacement que les anciennes méthodes.
Le tournant « non-transitif » : Ils ont même testé des scénarios où les préférences sont étranges. Par exemple : « Je préfère A à B, B à C, mais C à A » (comme le Pierre-Papier-Ciseaux). Les anciennes méthodes luttent avec cela, mais le nouveau modèle de « Concours » le gère naturellement.

Résumé

Le papier dit : « Arrêtez d'essayer de forcer les robots à maximiser une fiche de notation complexe quand vous n'avez que des préférences. À la place, laissez-les jouer un "Concours" contre eux-mêmes. Nous avons prouvé que des décisions simples, prises "sur le moment", sont suffisantes pour gagner ce concours, et nous avons construit un algorithme rapide et fiable pour leur apprendre à le faire, même pour des tâches très longues et complexes. »

Ceci est particulièrement utile pour l'entraînement des modèles de langage de grande taille (comme celui avec lequel vous discutez actuellement), où le « jeu » (une conversation ou une tâche) peut durer très longtemps, et où il est souvent plus facile de dire « Je préfère cette réponse à celle-là » que d'attribuer un nombre spécifique à une réponse.

Résumé technique : Apprentissage par renforcement avec préférences par paires dans les problèmes de décision à long terme

Définition du problème
L'apprentissage par renforcement (RL) traditionnel formule les objectifs comme la maximisation de la valeur attendue d'une fonction de récompense scalaire au sein d'un processus de décision de Markov (MDP). Cependant, dans de nombreuses applications, telles que l'ajustement fin (fine-tuning) de grands modèles de langage (LLM), la spécification de préférences par paires (par exemple, « la trajectoire A est meilleure que la trajectoire B ») est souvent plus naturelle et réalisable que la définition d'une récompense scalaire. Les méthodes existantes pour le RL avec des préférences par paires cherchent généralement à inférer une fonction de récompense ou à optimiser directement les préférences, mais elles souffrent de deux limitations critiques :

Elles reposent sur des horizons temporels finis et fixes, ce qui est impraticien pour les problèmes de décision à long terme où les agents ne se terminent pas à une étape fixe.
Elles manquent de garanties théoriques que les politiques de Markov stationnaires sont optimales par rapport aux politiques dépendantes de l'historique, ce qui est un pilier de la théorie standard des MDP.

De plus, les approches standards échouent souvent à capturer les préférences non transitives (par exemple, le paradoxe de Condorcet), où la préférence agrégée d'un groupe ou d'une évaluation multi-caractéristiques ne forme pas un ordre transitif.

Méthodologie : Concours de Décision Markoviens (MDC)
Les auteurs proposent un nouveau modèle de problème appelé Concours de Décision Markovien (MDC) pour combler ces lacunes. Un MDC est défini par un environnement fini $(S, A, P, \mu)$ et une marge de préférence markovienne $M: (S \times A) \times (S \times A) \to \mathbb{R}$ . L'objectif est de trouver une politique $\pi$ qui maximise la marge de préférence moyenne contre toute autre politique $\pi'$ , formulée comme un jeu à somme nulle :
$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$
où $x_\pi$ représente la fréquence état-action de l'état limite (mesure d'occupation).

Pour assurer la tractabilité théorique dans les contextes à horizon infini, les auteurs supposent que la fonction de probabilité de transition est unichaine et aperiodique. Sous ces conditions, ils établissent que l'ensemble des mesures d'occupation pour les politiques dépendantes de l'historique est équivalent à l'enveloppe convexe des mesures d'occupation des politiques déterministes stationnaires.

Contributions clés

Optimalité des politiques stationnaires : L'article prouve que, dans les MDC unichaines finies, une politique aléatoire stationnaire est optimale parmi toutes les politiques dépendantes de l'historique. Cela justifie la restriction de l'espace de recherche aux politiques de Markov, comblant ainsi un fossé entre la théorie et la pratique pour le RL basé sur les préférences.
Complexité computationnelle : Les auteurs démontrent que la résolution exacte d'un MDC appartient à la classe P (temps polynomial). Plus précisément, ils construisent un programme linéaire avec $|S||A| + |S| + 1$ variables et $2|S||A| + |S| + 1$ contraintes. Cette complexité est comparable aux MDP à récompense moyenne standard, bien que les MDC soient une généralisation stricte supportant des préférences non transitives.
Hedged Policy Iteration (HPI) : Un algorithme itératif approximatif, l'Hedged Policy Iteration (HPI), est introduit. Il utilise l'algorithme Hedge pour mettre à jour les règles de décision basées sur des « valeurs marginales » (marges de préférence cumulées).
- Convergence : HPI converge vers une politique optimale à un taux sous-linéaire de $O(1/\sqrt{K})$ , où $K$ est le nombre d'itérations.
- Scalabilité : Les auteurs dérivent une forme de gradient de politique de HPI et une implémentation de deep learning (Algorithme 3) qui utilise des buffers et des approximations de fonctions de valeur, ce qui la rend adaptée aux environnements à haute dimension.

Résultats expérimentaux
Les auteurs ont évalué HPI et une variante tronquée (HPI-Clip) contre le Self-Play Preference Optimization (SPPO) (Swamy et al., 2024) sur 13 tâches à haute dimension avec de longs horizons temporels (2048 étapes) en utilisant la suite Mujoco-v5.

Configuration : Les tâches comprenaient des problèmes de contrôle continu standards (où les préférences étaient dérivées des différences de récompense) et des tâches « Mujoco-NT » présentant des marges de préférence explicitement non transitives (par exemple, des règles de type « meilleur deux sur trois »).
Performance : Dans 12 tâches sur 13, HPI et HPI-Clip ont démontré une efficacité d'apprentissage nettement supérieure (mesurée par l'Aire Sous la Courbe du retour épisodique ou l'écart d'optimalité inversé) par rapport à SPPO.
Ablation : Les résultats ont été maintenus même lorsque les modèles de préférence étaient appris à partir de données hors ligne (offline).

Signification et affirmations
L'article affirme que l'apprentissage par renforcement avec des préférences par paires dans les problèmes de décision à long terme est plus tractable qu'on ne le pensait. En introduisant le modèle MDC, les auteurs fournissent un cadre où :

Les politiques stationnaires sont théoriquement suffisantes, éliminant le besoin de stratégies complexes dépendantes de l'historique.
Le problème reste efficace sur le plan computationnel (dans P), même avec des préférences non transitives.
Les algorithmes pratiques (HPI) passent à l'échelle pour les problèmes à haute dimension et à long horizon, surpassant les méthodes de pointe actuelles.

Les auteurs notent que bien que ces résultats soient prometteurs pour des applications comme les LLM dans des tâches à long horizon, des investigations supplémentaires sont nécessaires pour déterminer quand l'apprentissage de la marge de préférence l'emporte sur l'apprentissage de la récompense et comment ces méthodes alignent efficacement les modèles de langage en pratique. Ce travail vise à rapprocher la théorie et la pratique du RL par préférences par paires.