📊 statistics

Learning Kernel-Based MDPs from Episodic Preferential Feedback

Cet article présente un cadre théorique rigoureux pour l'apprentissage d'MDP épisodiques à base de noyaux en utilisant uniquement des préférences binaires de trajectoires, établissant des bornes de regret sous-linéaires à haute probabilité qui garantissent que la politique apprise converge vers la politique optimale.

Auteurs originaux : Nikola Pavlovic, Sattar Vakili, Qing Zhao

Publié 2026-05-25

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Nikola Pavlovic, Sattar Vakili, Qing Zhao

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

La Vue d'Ensemble : Apprendre par la Comparaison, pas par le Score

Imaginez que vous entraînez un robot à cuisiner un repas parfait. Dans les anciennes méthodes d'entraînement de l'IA, vous deviez agir comme un critique culinaire strict, attribuant au robot un score précis (comme 7,5 sur 10) pour chaque plat qu'il préparait. C'est difficile car les humains sont mauvais pour donner des nombres précis. Nous savons qu'un plat est « meilleur » qu'un autre, mais nous ne pouvons pas toujours dire combien il est meilleur.

Ce papier aborde un problème où l'IA apprend uniquement par la comparaison. Au lieu de donner des scores, un humain dit simplement : « Je préfère les pâtes à la pizza. » L'IA doit trouver le meilleur moyen de cuisiner en écoutant uniquement ces choix « A contre B ».

Les chercheurs ont développé une nouvelle méthode mathématique (un algorithme) permettant à une IA d'apprendre efficacement la meilleure stratégie, même lorsque le monde dans lequel elle évolue est incroyablement complexe et désordonné (mathématiquement parlant, cela s'appelle un « MDP à noyau »).

Le Défi : La « Boîte Noire » des Préférences

La difficulté ici est que l'IA reçoit très peu d'informations.

L'Ancienne Méthode (Récompenses Numériques) : Si vous dites à l'IA « Cette pizza a eu un 9/10 », vous obtenez beaucoup de données. Vous savez exactement à quel point elle était bonne.
La Nouvelle Méthode (Préférences) : Si vous dites simplement « Je préfère les pâtes », l'IA perd beaucoup d'informations. Elle ne sait pas si les pâtes étaient incroyables et la pizza terrible, ou si les deux étaient juste correctes. C'est comme essayer de deviner la température d'une pièce en vous contentant d'être informé « Il fait plus chaud qu'hier » sans connaître les degrés réels.

De plus, l'IA doit apprendre cela dans un environnement complexe où une petite erreur au début peut ruiner tout le repas (la « trajectoire »). Le papier explique comment apprendre efficacement lorsque l'environnement est complexe (en utilisant les mathématiques des « Noyaux » pour gérer des motifs non linéaires et désordonnés) et que le retour se limite à un seul choix « Oui/Non » par tour.

La Solution : PROSTO (Le Chef Optimiste)

Les auteurs présentent un algorithme appelé PROSTO. Imaginez PROSTO comme un chef très optimiste qui tente d'apprendre la meilleure recette.

Voici comment PROSTO fonctionne, étape par étape :

Le Jeu du « Et Si » (Exploration) :
Puisque le chef ne connaît pas encore la recette parfaite, il doit essayer de nouvelles choses. Mais il ne peut pas simplement deviner au hasard ; ce serait gaspilleur. PROSTO utilise une astuce mathématique appelée Perturbation par Processus Gaussien.
- Analogie : Imaginez que le chef possède un « shaker à épices magique ». À chaque fois qu'il cuisine, il secoue un peu d'« incertitude aléatoire » dans son plan. Cela le force à essayer des versions légèrement différentes des pâtes ou de la pizza. Cela garantit qu'il explore tous les coins de la cuisine pour trouver les pépites cachées, plutôt que de s'en tenir à ce qu'il connaît déjà.
Le Score de « Confiance » (Régularisation) :
Le chef doit savoir à quel point il est sûr de ses hypothèses. S'il est très incertain, il devrait être plus aventureux. S'il est sûr, il devrait s'en tenir au plan.
- Le papier utilise une technique appelée Régression Logistique à Noyau Régularisée. Imaginez cela comme un « compteur de confiance ». Il équilibre le désir du chef d'essayer de nouvelles choses avec la nécessité d'être précis. Il empêche le chef de devenir trop fou (ce qui mène à de mauvais repas) ou trop ennuyeux (ce qui mène à manquer la meilleure recette).
Le Moteur de « Comparaison » :
À chaque tour, le chef cuisine deux repas différents (deux stratégies différentes) et demande à l'humain : « Lequel aimez-vous ? »
- L'algorithme prend cette unique réponse « Oui/Non » et l'utilise pour mettre à jour sa carte interne de la cuisine. Il ne met pas à jour uniquement le repas spécifique ; il met à jour sa compréhension de l'ensemble du processus de cuisson, même pour les étapes qu'il n'a pas directement observées.

Pourquoi ce Papier est Spécial (La Partie « Magique »)

Les chercheurs affirment avoir résolu un casse-tête mathématique très difficile.

Le Problème du « Recouvrement » : En mathématiques complexes, pour prouver qu'un algorithme fonctionne, vous devez montrer que vous pouvez « recouvrir » tous les scénarios possibles avec un nombre gérable de suppositions. Habituellement, lorsque vous ajoutez du « bruit aléatoire » (comme le shaker à épices magique) pour faire explorer l'IA, cela fait exploser les mathématiques et les rend impossibles à calculer.
La Percée : Les auteurs ont trouvé un moyen de garder les mathématiques « calmes ». Ils ont prouvé que même avec ce bruit aléatoire, le nombre de suppositions nécessaires pour trouver la meilleure solution croît lentement (de manière sous-linéaire) à mesure que l'IA apprend davantage.
Le Résultat : Ils ont prouvé que leur algorithme, PROSTO, finira par trouver la meilleure stratégie possible, et ce, efficacement, sans avoir besoin de millions de comparaisons humaines. Il fonctionne pour une large classe d'environnements complexes (noyaux de Matérn), ce qui couvre de nombreux scénarios réels où les choses ne sont pas parfaitement lisses ou prévisibles.

La Conclusion

Ce papier présente une nouvelle façon, mathématiquement rigoureuse, pour l'IA d'apprendre à partir des préférences humaines (comme « Je préfère A à B ») dans des situations complexes et réelles.

Le Problème : Apprendre à partir de simples choix « A contre B » est difficile car vous perdez de l'information, et les environnements complexes rendent cela encore plus difficile.
La Solution : Un algorithme appelé PROSTO qui utilise une « exploration optimiste » (essayer de nouvelles choses basées sur l'incertitude) et un réglage mathématique minutieux pour rester efficace.
La Preuve : Les auteurs ont prouvé mathématiquement que cette méthode fonctionne et s'améliore avec le temps, convergeant vers la meilleure solution possible sans avoir besoin d'une puissance de calcul impossible.

En bref, ils ont créé un moyen plus intelligent pour l'IA d'apprendre à partir de nos simples retours « pouce en l'air » ou « pouce en bas », même lorsque la tâche est compliquée.

Résumé technique : Apprentissage d'MDP à noyau à partir de retours préférentiels épisodiques

Formulation du problème
Ce travail aborde le problème de l'apprentissage par renforcement à partir de retours humains (RLHF) dans le cadre des processus de décision markoviens (MDP) épisodiques. Contrairement à l'apprentissage par renforcement standard où les agents reçoivent des récompenses scalaires, l'apprenant reçoit ici uniquement des retours préférentiels binaires. À chaque épisode $k$ , l'apprenant déploie deux politiques, $\pi$ et $\pi'$ , depuis un état de départ commun pour générer deux trajectoires, $\tau_k$ et $\tau'_k$ . Le retour consiste en une seule étiquette binaire $y_k \in \{0, 1\}$ indiquant quelle trajectoire est préférée. Cette préférence est modélisée via une fonction de liaison Bradley–Terry–Luce (BTL) appliquée à la différence des récompenses cumulées (non observées) :
$y_k \sim \text{Ber}\left(\sigma\left(\sum_{h=1}^H r_h(z^k_h) - \sum_{h=1}^H r_h(z'^k_h)\right)\right)$
où $\sigma$ est la fonction sigmoïde. L'objectif est d'apprendre une politique qui maximise la fonction de valeur $V^\pi_1$ tout en minimisant le regret cumulatif, défini comme la différence entre la valeur optimale et la valeur moyenne des politiques déployées.

Le cadre suppose une structure de MDP à noyau, où la fonction de récompense $r_h$ et l'opérateur de transition $P_h$ sont des éléments d'un Espace de Hilbert à Noyau Reproduisant (RKHS) $\mathcal{H}_k$ induit par un noyau connu $k$ . Plus précisément, les auteurs se concentrent sur la famille de noyaux Matérn, qui capture des structures non linéaires et est équivalente en norme aux espaces de Sobolev, offrant une généralisation au-delà des MDP linéaires.

Méthodologie : Algorithme PROSTO
Les auteurs proposent PROSTO (Optimisation Régularisée basée sur les Préférences via l'Optimisme Induit par des Trajectoires Échantillonnées). L'algorithme fonctionne par épisodes et utilise une approche d'itération de valeur adaptée aux retours préférentiels et à l'approximation par fonction de noyau.

Estimation de la récompense via Régression Logistique à Noyau Régularisée (KLRR) :
Puisque le retour est au niveau de la trajectoire et binaire, le vecteur de récompense $\theta$ est estimé en utilisant l'estimation du maximum de vraisemblance avec une pénalité pondérée par la norme. L'estimateur $\hat{\theta}_k$ minimise la vraisemblance négative des préférences observées plus un terme de régularisation $\tau \|\theta\|^2_{\mathcal{H}_k}$ . Les covariables pour cette régression sont les caractéristiques de différence de trajectoire $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$ .
Exploration via Perturbation GP Randomisée :
Pour assurer une exploration suffisante au niveau de la trajectoire sans connaître à l'avance la dynamique de transition (ce qui empêche les bonus elliptiques déterministes), PROSTO utilise une exploration randomisée. Un vecteur de bruit d'exploration $\epsilon_k$ est échantillonné à partir d'un Processus Gaussien (GP) dont la structure de covariance dépend de la covariance empirique des différences de trajectoires. Ce bruit est ajouté à l'estimation de la récompense pour induire de l'optimisme.
Estimation de la fonction de valeur via Régression Ridge à Noyau (KRR) :
La fonction de valeur est estimée de manière récursive. La valeur attendue de l'état suivant est approximée en utilisant la régression ridge à noyau standard sur les échantillons de transition. L'estimation finale de la fonction Q, $\hat{Q}^k_h$ , combine l'estimation de la récompense (KLRR + bruit GP) et l'estimation de la transition (KRR), soumise à un écrêtage pour garantir la bornitude.
Exécution de la politique :
L'apprenant sélectionne deux politiques, $\pi$ et $\pi'$ , qui sont gourmandes par rapport à leurs estimations respectives de fonctions Q optimistes. Ces politiques sont exécutées pour générer les trajectoires et les retours préférentiels de l'épisode suivant.

Contributions techniques clés et défis
L'article identifie trois défis techniques principaux spécifiques à la combinaison des MDP à noyau avec des retours préférentiels au niveau de la trajectoire et fournit des solutions novatrices :

Contrôle des nombres de recouvrement logarithmiques : Dans les MDP à noyau, le nombre de recouvrement logarithmique de la classe de fonctions de valeur croît polynomialement avec l'inverse du maillage de recouvrement $\epsilon$ et dépend des normes RKHS des estimateurs. Contrairement aux MDP linéaires, où les nombres de recouvrement sont logarithmiques par rapport au nombre d'épisodes, les paramètres à noyau peuvent conduire à des bornes de regret vides si les normes des estimateurs deviennent trop grandes.
- Solution : Les auteurs ajustent soigneusement le paramètre de régularisation $\tau$ dans la KLRR pour contrôler explicitement la norme RKHS de l'estimateur de récompense. Cela maintient le nombre de recouvrement de la classe de fonctions induite faible, permettant des bornes de confiance significatives.
Exploration au niveau de la trajectoire avec un bruit non lisse : Les bonus d'exploration standards (bonus elliptiques) nécessitent la connaissance de la trajectoire complète, qui n'est pas disponible au moment de la décision. L'exploration randomisée via l'échantillonnage GP est utilisée, mais les trajectoires d'échantillons GP issues d'un noyau Matérn n'appartiennent généralement pas au RKHS correspondant (elles sont moins lisses). Cela rend les bornes de recouvrement standards inapplicables.
- Solution : Les auteurs dérivent de nouvelles bornes de recouvrement gaussiennes à haute probabilité pour les trajectoires d'échantillons GP a posteriori. Ils s'appuient sur les résultats de van der Vaart et van Zanten [2008] pour montrer que, bien que les trajectoires GP se situent en dehors de la boule RKHS, elles se trouvent à l'intérieur d'un voisinage $\epsilon$ (en norme $\ell_\infty$ ) d'une boule RKHS convenablement élargie avec une haute probabilité. Cela permet de dériver les bornes de recouvrement nécessaires à l'analyse du regret.
Équilibrage des paramètres de régularisation et de recouvrement : Le réglage des paramètres de régularisation ( $\tau$ pour la récompense, $\lambda$ pour la transition) et du maillage de recouvrement $\epsilon$ n'est pas trivial. Un petit $\epsilon$ réduit l'erreur de spécification mais gonfle le nombre de recouvrement ; un grand $\epsilon$ fait l'inverse.
- Solution : Les auteurs optimisent conjointement $\tau$ , $\lambda$ et $\epsilon$ en tant que fonctions du nombre d'épisodes $K$ et du paramètre de régularité du noyau $\beta_p$ . Cet équilibre garantit que les largeurs de confiance restent suffisamment serrées pour un regret sous-linéaire tout en contrôlant la complexité de la classe de fonctions.

Résultats et bornes de regret
L'article démontre que PROSTO atteint une borne de regret cumulatif sous-linéaire pour tous les noyaux de la famille Matérn. Plus précisément, le regret $R(K)$ évolue comme suit :
$R(K) \leq \tilde{O}\left( \kappa_Z \max\left( H^{2.5} K^{1 - \frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}}, H^3 K^{1 - \frac{\beta_p-1}{2(\beta_p+1)}} \right) \right)$
où $\beta_p > 1$ est le paramètre de décroissance des valeurs propres du noyau, $H$ est l'horizon, et $\kappa_Z$ est le gradient inverse maximal de la liaison. L'exposant de $K$ est strictement inférieur à 1, impliquant une convergence vers la politique optimale lorsque $K \to \infty$ .

De plus, l'algorithme est computationalement efficace, avec un temps d'exécution polynomial par rapport au nombre d'épisodes $K$ . Cela le distingue des travaux antérieurs sur les MDP à noyau avec des récompenses standards (par exemple, Maran et al. [2024b]) qui, bien qu'atteignant un regret sous-linéaire, reposent sur un partitionnement du domaine ou des oracles d'optimisation qui ne sont pas connus pour être traitables en temps polynomial pour des paramètres de noyau généraux.

Importance et affirmations
Les auteurs affirment que ce travail fournit le premier algorithme pour le RL basé sur les préférences dans les MDP à noyau qui atteint un regret sous-linéaire prouvé pour l'ensemble de la famille de noyaux Matérn tout en étant computationnellement efficace.

Nouveauté théorique : Ce travail comble le fossé entre le RL basé sur les préférences (qui gère généralement des paramètres tabulaires ou linéaires) et l'approximation de fonction basée sur les noyaux (qui gère des paramètres non linéaires). Il introduit de nouvelles techniques pour gérer l'absence de régularité dans le bruit d'exploration GP dans le contexte de l'itération de valeur.
Efficacité computationnelle : Contrairement aux algorithmes sans regret précédents pour les MDP lisses qui peuvent nécessiter une optimisation intraitable, PROSTO offre une implémentation en temps polynomial.
Limites : Les auteurs reconnaissent que la borne de regret peut ne pas être optimale en ordre. Ils notent que les approches de partitionnement du domaine, qui offrent actuellement des bornes optimales en ordre dans certains paramètres de noyau, sont incompatibles avec les retours au niveau de la trajectoire en raison de la stochasticité des transitions empêchant l'estimation localisée de l'opérateur de Bellman.

L'article conclut que, bien que la borne de regret dérivée soit sous-linéaire, atteindre une borne optimale en ordre reste une question ouverte, nécessitant probablement des techniques fondamentalement différentes des méthodes actuelles de partitionnement du domaine ou de recouvrement uniforme.