Résumé technique : Apprentissage par imitation adversaire hors-politique prouvablement efficace avec garanties de convergence

Énoncé du problème

L'apprentissage par imitation adversaire (AIL) cadre l'apprentissage par imitation comme un jeu à deux joueurs où un agent met à jour sa politique pour correspondre aux performances d'un expert, tandis qu'un adversaire met à jour une fonction de récompense pour maximiser l'écart de performance entre les deux. Les algorithmes d'AIL standards nécessitent des données on-policy (échantillons générés par la politique actuelle de l'agent) pour évaluer l'espérance des récompenses cumulées lors des mises à jour de la fonction de récompense. Cette exigence entraîne une inefficacité de l'échantillonnage, car elle nécessite de nouvelles interactions avec l'environnement à chaque étape de mise à jour, ce qui rend l'approche peu pratique dans les contextes où les interactions sont coûteuses ou limitées.

Bien que des méthodes off-policy aient été proposées pour réutiliser les données des politiques précédentes afin d'améliorer l'efficacité de l'échantillonnage, elles introduisent une erreur de décalage de distribution car les données ne correspondent plus parfaitement à la distribution de visite état-action de la politique actuelle. Les approches d'AIL off-policy existantes reposent soit sur l'échantillonnage préférentiel (importance sampling, qui induit une variance élevée), soit sur des transformations de variables complexes qui altèrent la fonction objectif, perdant ainsi souvent les garanties de convergence théoriques. Le défi central adressé par ce travail est le suivant : Pouvons-nous garantir la convergence de l'AIL off-policy et assurer l'efficacité de l'échantillonnage sans dépendre de techniques de correction off-policy explicites comme l'échantillonnage préférentiel ?

Méthodologie

Les auteurs proposent un algorithme d'AIL off-policy qui combine la descente de miroir basée sur un modèle pour les mises à jour de la politique avec une ascension de gradient projetée off-policy pour les mises à jour de la récompense. L'innovation clé réside dans le contrôle de l'erreur de décalage de distribution en sélectionnant soigneusement le nombre de politiques passées ($N$) dont les données sont réutilisées lors des mises à jour de la récompense.

1. Mises à jour de la politique

L'algorithme emploie une approche de descente de miroir basée sur un modèle.

• Estimation du modèle : La fonction de transition d'état $\hat{P}_h$ est estimée empiriquement à partir des rencontres état-action.
• Optimisation de la politique : La politique est mise à jour en utilisant une étape de descente de miroir régularisée par la divergence KL (Équation 3). Cette règle de mise à jour, dérivée des valeurs Q estimées, garantit que les changements de politique sont suffisamment conservateurs pour borner la distance de Variation Totale (TV) entre les politiques consécutives. Cette stabilité est cruciale pour contrôler le décalage de distribution dans les mises à jour de récompense off-policy.

2. Mises à jour de la récompense

Au lieu d'utiliser uniquement les données de la politique actuelle $\pi_{k-1}$, la mise à jour de la récompense utilise un mélange de données provenant des $N(k)$ politiques les plus récentes.

• Distribution de mélange : L'algorithme échantillonne à partir d'une distribution de mélange $d^{k-1, mix}_h = \sum_{n=1}^{N} \beta_n d^{k-n}_h$, où $\beta_n$ sont des poids uniformes.
• Objectif : Les paramètres de la récompense $\mu$ sont mis à jour via une ascension de gradient projetée pour maximiser la perte $L(\pi^{k-1, mix}, \mu) = J(\pi_E, \mu) - \frac{1}{N}\sum_{n=1}^N J(\pi_{k-n}, \mu)$.
• Contrôle de l'erreur : L'analyse théorique (Lemme 4.2 et Théorème 4.3) démontre que si les mises à jour de la politique sont suffisamment petites (contrôlées par le pas $\sigma$), la divergence entre la distribution de mélange et la distribution de la politique actuelle reste bornée.

3. Cadre théorique

Le regret de l'algorithme d'AIL est décomposé en regret de politique et regret de récompense (Lemme 3.2). Les auteurs dérivent des bornes pour les deux :

• Regret de politique : Borné par $\tilde{O}(\sqrt{H^4 S^2 A K})$ en utilisant la mise à jour de descente de miroir.
• Regret de récompense : Borné par un terme comprenant le regret standard, un terme d'erreur induit par les mises à jour off-policy, et un terme d'erreur d'estimation (Théorème 4.4).
• Résultat principal (Théorème 4.5) : Le regret total est sous-linéaire par rapport au nombre d'itérations $K$, à condition que le nombre de politiques réutilisées $N(k)$ évolue comme $o(\sqrt{K})$. Plus précisément, si $N$ est fixe, l'échelle optimale est $N^* = \tilde{O}((S/(HAB))^{1/3})$.

Principales contributions

1. Garanties de convergence sans correction : Le papier fournit les premières garanties de convergence théoriques pour un algorithme d'AIL off-policy qui ne nécessite pas de techniques de correction off-policy (ex: échantillonnage préférentiel).
2. Analyse de l'efficacité de l'échantillonnage : Les auteurs établissent que la réutilisation des échantillons des $o(\sqrt{K})$ politiques les plus récentes n'entrave pas la convergence. Ils prouvent que l'erreur de décalage de distribution est dominée par les bénéfices de l'augmentation de la disponibilité des données, particulièrement lorsque la taille de l'espace d'états ($S$) est grande par rapport à l'horizon ($H$) et l'espace d'action ($A$).
3. Validation pratique : L'algorithme est validé sur des tâches MiniGrid (espace discret) et des benchmarks OpenAI Gym (MuJoCo, espace continu), démontant que les variantes off-policy ($N > 1$) convergent plus rapidement et nécessitent moins d'échantillons que leurs homologues on-policy ($N=1$).

Résultats expérimentaux

• MiniGrid (Discret) : Dans les tâches EmptyRoom de tailles variées ($3\times3$, $5\times5$, $9\times9$), les algorithmes off-policy avec $N=32$ ont atteint des performances de niveau expert avec environ 1 000 interactions, alors que l'algorithme on-policy ($N=1$) a nécessité l'horizon complet de 10 000 interactions pour converger. Les résultats ont confirmé que les espaces d'états plus grands bénéficient d'un $N$ plus élevé.
• MuJoCo (Continu) : Dans les tâches HalfCheetah, Hopper et Walker2d, les algorithmes off-policy ont systématiquement surpassé la base de référence on-policy. Bien que le $N$ optimal varie selon les environnements, des gains significatifs ont été observés même avec un petit $N$ (ex: $N=4$ ou $N=16$).
• Observation : Les expériences soutiennent la thèse théorique selon laquelle l'AIL off-policy peut atteindre une efficacité d'échantillonnage supérieure, bien que le nombre optimal de politiques réutilisées dépende des caractéristiques spécifiques de l'environnement.

Signification et affirmations

Le papier prétend combler le fossé entre la compréhension théorique et l'application pratique de l'AIL off-policy. Alors que les travaux précédents ont démontré le succès pratique de l'AIL off-policy, ils manquaient de preuves de convergence rigoureuses. Ce travail démontre que :

• Support théorique : Il est possible de garantir la convergence de l'AIL off-policy en contrôlant simplement le décalage de distribution par des mises à jour de politique conservatrices et en limitant le nombre de politiques réutilisées.
• Efficacité de l'échantillonnage : L'« erreur » introduite par les données off-policy est théoriquement montrée comme étant compensée par les bénéfices statistiques d'avoir plus de données, surtout dans les espaces d'états à haute dimension.
• Simplicité : La méthode proposée évite les techniques complexes de réduction de variance comme l'échantillonnage préférentiel, offrant une alternative plus simple et théoriquement fondée qui s'aligne sur les observations empiriques de l'efficacité de l'échantillonnage en pratique.

Les auteurs notent modestement que leur analyse théorique suppose des contextes tabulaires (étendue aux MDP linéaires dans l'appendice) et que le $N$ optimal dans les contextes de deep RL (MuJoço) peut ne pas s'aligner parfaitement sur les bornes théoriques du pire cas en raison de la paramétrisation des réseaux de neurones, pourtant les tendances de performance restent cohérentes avec la théorie.