Apprenticeship learning with prior beliefs using inverse optimization

Cet article propose un cadre unifié pour l'apprentissage par imitation et l'optimisation inverse dans les processus de décision markoviens, intégrant des croyances a priori via une régularisation pour résoudre l'ill-posedness du problème et démontrant que l'apprentissage par imitation classique en est un cas particulier.

L'essentiel

Imaginez que vous voulez apprendre à conduire une voiture. Vous avez un instructeur (l'expert) qui vous montre comment faire. Mais il y a un problème : vous ne connaissez pas les règles exactes qu'il suit. Est-ce qu'il conduit vite pour arriver en premier ? Est-ce qu'il conduit doucement pour économiser l'essence ? Ou est-ce qu'il évite les nids-de-poule pour ne pas abîmer la voiture ?

C'est là que se pose le défi de l'Apprentissage par Imitation (ou "Apprentissage par Apprentissage" dans le jargon technique). Le but est de deviner les règles cachées (le "coût" ou la "récompense") que l'instructeur utilise, pour pouvoir conduire aussi bien que lui, voire mieux.

Ce papier propose une nouvelle façon de résoudre ce casse-tête, en mélangeant trois idées : l'optimisation inverse (deviner les règles à partir des actions), l'apprentissage par démonstration, et... un peu de "magie" mathématique appelée régularisation.

Voici l'explication simple, étape par étape :

1. Le Problème : L'Instructeur n'est pas parfait

Dans la vie réelle, nos instructeurs ne sont pas des robots parfaits. Parfois, ils font des erreurs, ou ils ont des habitudes bizarres.

• L'ancienne méthode : Les chercheurs disaient : "Supposons que l'instructeur est parfait et qu'il suit des règles précises que nous connaissons déjà." C'est comme si on disait : "L'instructeur ne fait jamais de faute, et il utilise exactement ces 3 ingrédients pour cuisiner." Si l'instructeur triche ou utilise un ingrédient secret, la méthode échoue.
• Le problème mathématique : Il y a souvent plusieurs façons d'expliquer pourquoi quelqu'un fait quelque chose. C'est ce qu'on appelle un problème "mal posé". Comme un détective qui voit un suspect fuir : court-il parce qu'il est coupable ? Ou parce qu'il a juste peur des chiens ? Sans indices supplémentaires, on ne sait pas.

2. La Solution : Apporter sa propre "Intuition" (Les croyances a priori)

Les auteurs disent : "Attendez, nous avons aussi notre propre intuition sur la façon dont le monde fonctionne !"

Imaginez que vous essayez de deviner le prix d'une maison.

• Sans intuition : Vous regardez juste la maison et vous dites "Je ne sais pas".
• Avec intuition (la méthode du papier) : Vous savez que le quartier est cher, que la maison a 3 chambres, et que le marché est en baisse. Vous avez une estimation de départ (appelée $\hat{c}$ dans le papier).

Le papier propose d'utiliser cette estimation de départ comme un aimant.

• Si l'instructeur fait quelque chose de bizarre, le système va se demander : "Est-ce que c'est une erreur de l'instructeur, ou est-ce que ma propre intuition est fausse ?"
• Ils introduisent un bouton de réglage, appelé $\alpha$ (alpha).
  • Si $\alpha$ est faible : On fait confiance à l'instructeur, même s'il est imparfait. On ignore un peu notre intuition.
  • Si $\alpha$ est fort : On fait confiance à notre intuition (notre estimation de départ) et on dit à l'instructeur : "Tu as peut-être fait une erreur ici".

C'est comme si vous appreniez à cuisiner avec un grand-père qui a parfois des tremblements de main.

• Si vous ignorez votre propre connaissance des recettes (faible $\alpha$), vous copiez ses tremblements.
• Si vous vous fiez trop à votre livre de cuisine (fort $\alpha$), vous ignorez ses astuces secrètes.
• La méthode du papier trouve le juste milieu : elle apprend la recette vraie en corrigeant les tremblements du grand-père grâce à votre connaissance de base.

3. L'Outil Mathématique : Le "Miroir" et la Danse

Pour résoudre ce problème de compromis entre "l'instructeur imparfait" et "mon intuition", les auteurs utilisent un algorithme appelé Descente de Miroir Stochastique (SMD).

Imaginez deux danseurs qui doivent trouver un point d'équilibre sur une scène glissante :

1. Le danseur A essaie de trouver la meilleure recette (le coût).
2. Le danseur B essaie de trouver la meilleure façon de danser (la politique de l'apprenti).

Ils se regardent dans un miroir (c'est la partie "Miroir" de l'algorithme). Chaque fois que l'un bouge, l'autre ajuste sa position pour rester en harmonie.

• Ils ne regardent pas toute la scène d'un coup (ce serait trop lent). Ils regardent juste un petit coin à la fois (c'est la partie "Stochastique").
• À force de petits pas et de corrections, ils finissent par trouver la position parfaite où la recette et la danse correspondent parfaitement, tout en respectant notre "intuition" de départ.

4. Les Résultats : Pourquoi c'est génial ?

Les auteurs ont testé leur méthode sur deux jeux :

1. La gestion d'un stock de produits : Comme un magasin qui doit commander des produits sans en avoir trop ou trop peu.
2. Un monde de grille (Gridworld) : Un robot qui doit traverser un labyrinthe avec des obstacles.

Ce qu'ils ont découvert :

• Contre les experts imparfaits : Quand l'instructeur fait des erreurs, la méthode avec le bouton $\alpha$ (régularisation) réussit à retrouver la "vraie" recette beaucoup mieux que les anciennes méthodes. Elle ne copie pas bêtement les erreurs.
• Flexibilité : Les anciennes méthodes exigeaient de deviner à l'avance quelles étaient les "règles de base" (comme dire "la recette est un mélange de sel, poivre et sucre"). La nouvelle méthode n'a pas besoin de ça. Elle peut découvrir n'importe quelle règle, même très complexe, comme dans le labyrinthe.
• Vitesse : Parfois, c'est un peu plus lent de calculer, mais le résultat final est beaucoup plus intelligent et robuste.

En résumé

Ce papier dit : "Ne faites pas confiance aveuglément à l'instructeur, et ne faites pas confiance aveuglément à votre intuition. Utilisez les deux !"

En ajoutant un petit "poids" à votre intuition (la régularisation), vous pouvez apprendre d'un expert qui n'est pas parfait, et créer un apprenti qui finit par être plus performant que son maître. C'est une façon élégante de transformer l'incertitude en une opportunité d'apprentissage plus intelligent.

Résumé technique

1. Problématique et Contexte

Le papier aborde le problème de l'Apprentissage par Imitation (Learning from Demonstrations - LfD) et de l'Apprentissage par Mentorat (Apprenticeship Learning - AL) dans le cadre des Processus de Décision Markoviens (MDP).

• Le défi de l'IRL : L'Apprentissage par Renforcement Inverse (IRL) vise à déduire la fonction de coût sous-jacente qu'un expert optimise à partir de ses trajectoires. Cependant, ce problème est mal posé (ill-posed) : de nombreuses fonctions de coût peuvent expliquer le même comportement d'expert.
• Limites des approches existantes :
  • Les méthodes classiques (comme celles d'Abbeel & Ng, 2004) supposent souvent que la vraie fonction de coût appartient à un enveloppe convexe (convex hull) de vecteurs de base pré-spécifiés. Cela nécessite une ingénierie de caractéristiques (feature engineering) complexe et peut être restrictif.
  • La plupart des travaux supposent que l'expert est optimal. Or, dans la réalité, les experts sont souvent sous-optimaux.
  • L'absence de contraintes sur la structure du coût rend la recherche d'une solution unique difficile sans informations a priori.

Objectif du papier : Revisiter la relation entre l'IRL, l'AL et l'Optimisation Inverse (IO) pour intégrer des croyances a priori sur la structure du coût, gérer les experts sous-optimaux, et fournir un cadre théorique unifié avec des garanties de convergence.

---

2. Méthodologie et Cadre Théorique

Les auteurs proposent un cadre unifié basé sur l'Optimisation Inverse pour les MDP.

A. Formulation du Problème (IO-ALα)

Les auteurs définissent un nouveau problème d'optimisation, noté (IO-ALα), qui vise à apprendre une fonction de coût $c_A$ et une politique d'apprenti $\pi_A$ en tenant compte :

1. D'un vecteur de coût proxy $\hat{c}$ représentant les croyances a priori (qui peuvent être imparfaites).
2. D'un expert dont la politique $\pi_E$ peut être sous-optimale.

Le problème est formulé comme un problème de min-max régularisé :
$$\min_{c \in \mathcal{C}, u} \alpha \|c - \hat{c}\|^2_2 + \langle \mu_{\pi_E}, c - T_\gamma^\top u \rangle$$
sous la contrainte $c - T_\gamma^\top u \geq 0$.

• $\alpha$ : Paramètre de régularisation qui pondère l'importance de la croyance a priori ($\hat{c}$) par rapport aux démonstrations de l'expert.
• $\mu_{\pi_E}$ : Mesure d'occupation de l'expert.
• $u$ : Variable duale représentant la fonction de valeur.
• Le terme $\langle \mu_{\pi_E}, c - T_\gamma^\top u \rangle$ agit comme une relaxation des conditions de complémentarité de slackness, permettant de gérer l'optimalité imparfaite de l'expert.

B. Lien avec l'Apprentissage par Mentorat (AL)

Le papier démontre que la formulation classique de l'AL (basée sur l'analyse convexe de Kamoutsi et al., 2021) est un cas particulier de leur cadre lorsque le terme de régularisation est nul ($\alpha = 0$) et que l'expert est optimal. Leur approche généralise l'AL à une classe convexe générale de fonctions de coût sans nécessiter de définir à l'avance un ensemble de vecteurs de base.

C. Algorithme de Résolution : SMD-RLfD

Pour résoudre le problème min-max convexe-concave résultant, les auteurs adaptent l'algorithme de Descente de Miroir Stochastique (Stochastic Mirror Descent - SMD) :

• Estimateurs de gradient : Ils développent des estimateurs de gradient non biaisés basés sur des oracles de génération de modèles (pour les transitions et la mesure d'occupation de l'expert).
• Itération : L'algorithme alterne entre la mise à jour de la fonction de coût ($c$) et de la mesure d'occupation ($\mu$) via des étapes de descente et d'ascension stochastiques, suivies de projections sur des ensembles convexes (boîte et simplexe).
• Convergence : Ils établissent des bornes de convergence théoriques pour la solution $\epsilon$-approchée, montrant que le nombre d'itérations dépend quadratiquement du nombre d'actions et cubiquement du nombre d'états.

---

3. Contributions Clés

1. Unification IRL/AL/IO : Démonstration que le cadre de l'AL convexe-analytique est une relaxation de leur formulation d'optimisation inverse généralisée.
2. Gestion des experts sous-optimaux : Introduction du problème (IO-ALα) qui relaxe l'hypothèse d'optimalité de l'expert, rendant le modèle plus robuste aux démonstrations imparfaites.
3. Intégration de croyances a priori : Utilisation d'un vecteur de coût $\hat{c}$ et d'un paramètre $\alpha$ pour guider la recherche vers des solutions plausibles, résolvant ainsi l'indétermination du problème IRL.
4. Algorithme SMD-RLfD : Proposition d'un algorithme efficace avec des estimateurs de gradient adaptés aux oracles, accompagné de garanties de convergence théoriques.
5. Analyse comparative : Preuve que leur approche surpasse les méthodes basées sur l'enveloppe convexe (convex hull) dans les espaces d'états de grande dimension.

---

4. Résultats Expérimentaux

Les auteurs évaluent leur méthode sur deux cas d'usage : un problème de gestion de stocks (faible dimension) et un environnement Gridworld (dimension plus élevée).

• Robustesse aux croyances erronées (Misspecification) :
  • Même lorsque le vecteur de coût a priori $\hat{c}$ est bruité, l'algorithme parvient à récupérer une fonction de coût proche de la vérité terrain, surtout lorsque l'expert est optimal.
• Gestion de l'expert sous-optimal :
  • Dans le scénario de gestion de stocks avec un expert sous-optimal, l'ajout d'une régularisation ($\alpha > 0$) permet de récupérer une politique d'apprenti qui surpasse systématiquement l'expert et se rapproche de la politique optimale.
  • Le paramètre $\alpha$ permet de trouver un compromis optimal entre la fidélité aux démonstrations et la cohérence avec les connaissances a priori.
• Comparaison avec l'approche "Convex Hull" :
  • Sur des espaces d'états petits, les deux méthodes convergent de manière similaire.
  • Sur des espaces d'états plus grands, l'approche proposée (basée sur une boîte convexe) surpasse l'approche par enveloppe convexe en termes de performance de la politique apprise. L'approche par enveloppe convexe devient trop rigide et difficile à adapter sans une ingénierie de caractéristiques parfaite.
• Impact de la régularisation sur la convergence :
  • Une régularisation forte ($\alpha$ élevé) accélère la convergence du vecteur de coût $c$ (car il est contraint de rester proche de $\hat{c}$), mais ralentit la convergence de la dualité gap globale, conformément aux bornes théoriques.

---

5. Signification et Conclusion

Ce travail est significatif car il comble le fossé entre la théorie de l'optimisation inverse et l'apprentissage par imitation pratique.

• Pratique : Il offre une méthode robuste pour apprendre des politiques à partir d'experts imparfaits, un scénario très courant dans le monde réel (ex: conduite autonome, robotique).
• Flexibilité : En évitant la nécessité de définir manuellement un ensemble de vecteurs de base (comme le font les méthodes AL classiques), la méthode s'adapte mieux à des problèmes complexes où la structure du coût est inconnue ou difficile à modéliser par des combinaisons linéaires simples.
• Théorique : La fourniture de bornes de convergence et la caractérisation de la relation entre la solution approchée et la solution optimale renforcent la crédibilité théorique de l'approche.

En résumé, les auteurs proposent un cadre unifié où la régularisation par des croyances a priori est la clé pour résoudre l'indétermination de l'IRL et améliorer la performance de l'apprentissage par imitation face à des experts non parfaits.