Résumé Technique : Apprendre Quand S'Arrêter : Apprentissage par Imitation Sélectif Sous Décalages de Dynamique Arbitraires

1. Formulation du Problème

L'article aborde le défi de l'Apprentissage par Imitation (IL) dans des contextes où les dynamiques de transition de l'environnement de test diffèrent arbitrairement de l'environnement d'entraînement. Dans l'IL hors ligne classique, un apprenant entraîné sur des démonstrations d'expert provenant d'un environnement source $M$ est déployé dans un environnement cible $N$. Si les supports d'états de $M$ et $N$ sont disjoints ou significativement décalés, une politique standard peut performer de manière arbitrairement médiocre car elle ne peut pas reconnaître lorsque ses données d'entraînement ne fournissent plus de guidance fiable.

Les auteurs proposent un cadre pour l'Apprentissage par Imitation Sélectif, où l'apprenant se voit accorder la possibilité de s'abstenir (arrêter l'exécution) en cours de trajectoire lorsqu'il détecte que l'état actuel se situe en dehors du support fiable de ses données d'entraînement. L'objectif est d'apprendre une politique sélective $(\pi, \tau)$, composée d'une politique de base $\pi$ et d'un temps d'arrêt $\tau$, qui satisfait deux objectifs concurrents :

1. Complétude : La politique devrait rarement s'abstenir dans l'environnement d'entraînement $M$ (c'est-à-dire $\alpha_M(\pi, \tau) \le \epsilon$).
2. Sûreté : La politique devrait encourir un faible regret dans l'environnement de test $N$ avant de s'arrêter (c'est-à-dire $Regret_N(\pi, \tau) \le \epsilon$).

Le cadre suppose l'accès à :

• Déroulements d'entraînement étiquetés : Paires état-action $(s, a)$ provenant de l'expert $\pi^\star$ dans l'environnement $M$.
• Déroulements de test non étiquetés : Trajectoires uniquement d'états provenant de l'expert $\pi^\star$ dans l'environnement $N$. Cette asymétrie modélise des scénarios réels où la télémétrie d'action est coûteuse ou propriétaire (par exemple, des images de caméra de bord pour la conduite autonome sans commandes de direction).

2. Méthodologie : SeqRejectron

L'algorithme central, SeqRejectron, généralise l'algorithme Rejectron de la classification sélective (Goldwasser et al., 2020) à la prise de décision séquentielle. L'idée clé est que, au lieu de prendre des décisions indépendantes à chaque pas de temps (ce qui conduit à une complexité d'échantillonnage dépendante de l'horizon), l'algorithme certifie des préfixes de trajectoires entiers en utilisant un ensemble sparse de politiques validateurs.

Mécanisme Central

1. Politique de Base : L'apprenant sélectionne une politique de base $\pi_0$ cohérente avec les données d'entraînement (par exemple, l'estimation du maximum de vraisemblance).
2. Ensembles de Validateurs : L'algorithme construit un petit ensemble de politiques "validateurs" $\Phi$ tirées de l'espace des versions (politiques cohérentes avec les données d'entraînement).
3. Règle d'Arrêt : L'apprenant exécute $\pi_0$ et ne continue que tant que chaque validateur dans $\Phi$ est d'accord avec $\pi_0$. Le premier point de désaccord déclenche un arrêt (abstention).
4. Distribution Sparse de Validateurs : Une contribution théorique critique est la preuve qu'un ensemble de validateurs sparse (de taille indépendante de l'horizon $H$) suffit à garantir la sécurité. Cela est réalisé via un argument minimax sur un jeu à somme nulle entre un "défiant" (choisissant une politique concurrente) et un "validateur" (choisissant un ensemble de validateurs).

Variantes pour Différents Contextes

L'article adapte ce cadre à trois contextes de plus en plus généraux :

• Politiques Déterministes :

  • Mécanisme : Utilise un test de désaccord binaire. Le temps d'arrêt $\tau$ est le premier pas où un validateur $\pi \in \Phi$ quelconque est en désaccord avec $\pi_0$.
  • Implémentation : La distribution de validateurs est construite en utilisant des dynamiques sans regret (spécifiquement, une réduction efficace en oracle vers l'apprentissage multiple-instance réalisable pondéré).
  • Résultat : Atteint une complexité d'échantillonnage sans horizon $\tilde{O}(\sqrt{\log|\Pi|/n})$ sous des coûts épars.

• Politiques Stochastiques :

  • Défi : Le désaccord binaire est trop grossier ; les distributions peuvent différer "doucement" à chaque pas sans une seule divergence alarmante.
  • Mécanisme : Remplace le test binaire par un temps d'arrêt basé sur la distance de Hellinger cumulative. L'apprenant s'arrête lorsque la distance de Hellinger au carré accumulée entre $\pi_0$ et n'importe quel validateur dépasse un seuil $\theta$.
  • Résultat : Fournit des bornes à échantillon fini sur la distance de Hellinger des trajectoires arrêtées. L'article établit une borne inférieure de $\Omega(1/\epsilon^3)$ pour la complexité d'échantillonnage étiqueté dans le contexte stochastique à un pas, correspondant à la partie pilotée par le coût de la borne supérieure.

• Classes de Politiques Mal Spécifiées :

  • Défi : L'expert $\pi^\star$ peut ne pas appartenir à la classe de politiques $\Pi$ de l'apprenant.
  • Mécanisme : Remplace la contrainte stricte de l'espace des versions par un jeu régulé symétriquement. Les validateurs sont autorisés à être en désaccord avec la politique de base sur les données source, mais ce désaccord est pénalisé.
  • Résultat : Les garanties se dégradent gracieusement avec la quantité de mauvaise spécification (mesurée par l'erreur de mauvaise spécification la meilleure de la classe $\Delta$).

3. Contributions et Résultats Clés

Garanties Théoriques

• Complexité Sans Horizon : Pour les politiques déterministes, la complexité d'échantillonnage est indépendante de l'horizon $H$ (sauf à travers l'échelle de coût totale $C_{max}$), évoluant comme $\tilde{O}(\sqrt{\log|\Pi|/n})$. Cela améliore les réductions naïves pas à pas qui subissent une pénalité de $O(H^2)$.
• Validation Sparse : L'article prouve l'existence d'une distribution de validateurs supportée sur des ensembles de taille $O(1/\epsilon)$, indépendante de l'espace d'états, de l'espace d'actions ou de l'horizon.
• Bornes Inférieures : Les auteurs prouvent une borne inférieure de $\Omega(1/\epsilon^3)$ pour la complexité d'échantillonnage étiqueté dans le contexte stochastique à un pas, montrant que la dépendance cubique en $1/\epsilon$ est inévitable pour les régimes pilotés par le coût.
• Robustesse à la Mauvaise Spécification : Le cadre s'étend aux contextes agnostiques où l'expert n'est pas dans la classe, avec des bornes de regret qui évoluent avec la racine carrée de l'erreur de mauvaise spécification.

Évaluation Empirique

Les auteurs évaluent SeqRejectron dans l'environnement LunarLander-v3.

• Configuration : L'entraînement a lieu dans un environnement sans vent ; le test a lieu dans un environnement venteux avec des impulsions initiales différentes.
• Constats : L'algorithme détecte avec succès les dynamiques hors distribution. En ajustant un seuil de sécurité $\theta$, les auteurs démontrent un compromis où la politique s'abstient minimalement sur les données dans la distribution (entraînement) tout en s'arrêtant de manière fiable sur les données hors distribution (test), empêchant ainsi des défaillances catastrophiques. Le nombre de validateurs s'est révélé robuste, avec une performance se saturant rapidement.

4. Signification et Revendications

L'article revendique d'établir l'abstention comme une réponse principielle et théoriquement fondée aux décalages de dynamiques imprévus dans l'apprentissage par imitation.

• Au-delà des Heuristiques : Contrairement aux approches d'RL robuste ou de randomisation de domaine qui nécessitent des hypothèses sur la nature du décalage ou un accès en ligne à la distribution de test, SeqRejectron fournit des garanties PAC sans distribution en utilisant uniquement des données hors ligne.
• Analogue Séquentiel de l'Apprentissage PQ : Ce travail se positionne comme un analogue séquentiel du cadre d'apprentissage PQ (Goldwasser et al., 2020), étendant la capacité de s'abstenir des prédictions uniques aux préfixes de trajectoires entiers.
• Mécanisme de Sécurité : En découplant la décision de quoi faire de celle de quand s'arrêter, le cadre offre un mécanisme de sécurité qui empêche l'apprenant de conduire le système vers des états irrécupérables lorsque ses données d'entraînement sont non informatives.

Les auteurs reconnaissent les limites, notant que le contexte stochastique manque actuellement d'une réduction computationnelle efficace en oracle (contrairement au cas déterministe) et que les taux de complexité d'échantillonnage pilotés par la variance pour les politiques stochastiques restent un écart ouvert entre les bornes supérieure et inférieure. Ils suggèrent également que des travaux futurs pourraient incorporer une connaissance structurelle partielle (par exemple, une distance TV bornée) pour resserrer les taux d'arrêt côté test.