Online Robust Reinforcement Learning with General Function Approximation

Cet article propose un algorithme d'apprentissage par renforcement robuste entièrement en ligne avec approximation fonctionnelle générale, qui apprend des politiques résilientes uniquement par interaction et établit des garanties de regret sublinéaires basées sur la dimension d'Eluder de Bellman robuste.

L'essentiel

🌧️ Le Problème : L'Élève qui apprend dans une salle de classe vide

Imaginez que vous apprenez à conduire une voiture.

• L'apprentissage classique (RL standard) : Vous apprenez dans un simulateur parfait, avec un temps toujours ensoleillé et des routes lisses. Vous devenez un champion. Mais le jour où vous prenez la vraie route, il pleut, la route est glissante et un enfant traverse brusquement. Votre "champion" panique et fait un accident. Pourquoi ? Parce qu'il n'a jamais appris à gérer l'imprévu.
• L'approche robuste (DR-RL) : L'idée est d'entraîner le conducteur non pas seulement pour le temps parfait, mais pour le pire scénario possible (pluie torrentielle, freins qui lâchent, etc.) tout en restant dans une zone de "réalisme". On veut un conducteur qui ne panique pas, même si le monde change un peu.

Le problème, c'est que les méthodes actuelles pour faire cela sont soit trop gourmandes en données (il faut des millions d'heures de simulation), soit elles ne fonctionnent que pour des problèmes très simples (comme des grilles de jeu). Elles n'arrivent pas à gérer les situations complexes du monde réel.

💡 La Solution : RFL-ϕ (Le "Coach de Survie" Intelligent)

Les auteurs de ce papier proposent une nouvelle méthode appelée RFL-ϕ. C'est un algorithme qui apprend uniquement en interagissant avec le monde réel, sans avoir besoin de bases de données géantes ni de simulateurs parfaits.

Voici comment cela fonctionne, avec une analogie :

1. Le Double Jeu : Le Chef et l'Avocat du Diable

Imaginez que vous entraînez un joueur d'échecs.

• Le Chef (la fonction de valeur) : Il essaie de trouver la meilleure stratégie pour gagner.
• L'Avocat du Diable (la fonction duale) : C'est la nouveauté. Au lieu de juste regarder les coups joués, cet avocat essaie activement de trouver le pire coup possible que l'adversaire pourrait jouer, pour voir si votre stratégie tient le choc.

Dans cette méthode, l'algorithme apprend ces deux rôles en même temps. Il ne se contente pas de dire "c'est bien", il dit "c'est bien, même si l'adversaire essaie de me piéger de cette manière précise".

2. L'Exploration "Optimiste" mais Prudente

En apprenant, l'agent doit explorer (essayer de nouvelles choses).

• L'approche classique : "Essayons tout, on verra bien !" (Risque de catastrophe).
• L'approche RFL-ϕ : "Je vais essayer ce qui semble le mieux, mais je vais ajouter une 'marge de sécurité' (un bonus d'incertitude) pour chaque action. Si je ne connais pas bien une zone, je suppose qu'elle pourrait être dangereuse, donc je m'y prépare."

C'est comme un randonneur qui, face à un brouillard, ne marche pas aveuglément vers le précipice, mais garde une distance de sécurité calculée mathématiquement.

3. La "Boussole" Intelligente (La Dimension de Bellman-Eluder Robuste)

C'est le cœur théorique du papier. Pour savoir si l'algorithme est efficace, les chercheurs ont inventé une nouvelle "boussole" appelée Dimension de Bellman-Eluder Robuste.

• L'analogie : Imaginez que vous essayez de dessiner une carte d'un territoire inconnu.
  • Si le territoire est très complexe et chaotique, il vous faut des millions de points pour le dessiner correctement.
  • Si le territoire a des structures cachées (des routes, des rivières), vous avez besoin de beaucoup moins de points.
  • Cette "boussole" mesure exactement combien de points d'information sont réellement nécessaires pour comprendre la complexité du problème, même dans le pire des cas.

Le résultat incroyable ? L'algorithme prouve qu'il n'a pas besoin de connaître la taille du monde entier (le nombre de villes, de routes, etc.) pour réussir. Il s'adapte à la complexité réelle du problème. C'est comme si un navigateur pouvait traverser l'océan sans avoir besoin de compter chaque goutte d'eau, mais juste en comprenant les courants.

🚀 Pourquoi c'est important ?

1. Pas besoin de super-ordinateur : Contrairement aux méthodes précédentes qui nécessitaient des données massives (comme un générateur de mondes infinis), celle-ci apprend "sur le tas", comme un humain.
2. Évolutivité : Elle fonctionne aussi bien sur un petit jeu vidéo que sur des systèmes complexes comme la conduite autonome ou la gestion de réseaux électriques, car elle ne dépend pas de la taille brute du problème, mais de sa structure.
3. Sécurité garantie : Les mathématiques derrière prouvent que l'algorithme va apprendre à être robuste sans faire d'erreurs catastrophiques pendant l'entraînement.

En résumé

Ce papier présente un nouvel algorithme d'intelligence artificielle qui apprend à prendre de bonnes décisions dans un monde incertain et changeant.

Au lieu de simplement apprendre "ce qui marche", il apprend "ce qui marche même si tout va mal", en utilisant un système de double vérification (un optimiste et un pessimiste) et une boussole mathématique intelligente pour ne pas perdre de temps. C'est un pas de géant vers des IA plus sûres, plus fiables et capables de fonctionner dans la vraie vie, pas seulement dans des laboratoires.

Résumé technique

1. Problématique et Contexte

Le défi de la robustesse en RL :
Les systèmes d'apprentissage par renforcement (RL) classiques souffrent souvent d'une dégradation des performances lors du déploiement si l'environnement réel diffère de celui observé pendant l'entraînement (problème de "mismatch" ou de non-stationnarité). L'apprentissage par renforcement robuste distributionnellement (DR-RL) vise à résoudre ce problème en optimisant la performance dans le pire des cas, au sein d'un ensemble d'incertitude défini autour des dynamiques nominales.

Limites des approches existantes :
La plupart des méthodes DR-RL actuelles reposent sur des hypothèses de données irréalistes pour des applications pratiques :

• Accès à un modèle génératif (capable de produire des échantillons arbitraires).
• Utilisation de grands jeux de données hors ligne (offline) avec une couverture garantie.
• Restriction aux environnements tabulaires (petits espaces d'états/actions), ce qui empêche la mise à l'échelle vers des problèmes complexes.
• Manque d'algorithmes purement en ligne (online) capables d'apprendre uniquement par interaction, sans données pré-collectées, tout en gérant de grands espaces d'états via l'approximation de fonctions.

Objectif de l'article :
Développer un algorithme DR-RL purement en ligne, efficace en échantillons, capable de fonctionner avec une approximation de fonction générale (non linéaire, non tabulaire), et fournir des garanties théoriques rigoureuses sans hypothèses de couverture globale (coverage) ou de concentrabilité.

---

2. Méthodologie : L'algorithme RFL-ϕ

Les auteurs proposent RFL-ϕ (Robust Fitted Learning with ϕ-Divergence), un algorithme basé sur une procédure d'apprentissage par ajustement (fitted learning) pilotée par une formulation duale.

A. Cadre Formel

• Modèle : Processus de Décision Markovien Robuste (RMDP) avec un horizon fini.
• Ensemble d'incertitude : Défini par une divergence ϕ (incluant la Distance Totale de Variation TV, la divergence $\chi^2$ et la divergence KL). L'ensemble contient toutes les transitions possibles à une distance $\sigma$ de la transition nominale $P^\star$.
• Objectif : Maximiser la valeur robuste (pire cas) $V^{\pi, \sigma}$.

B. Innovations Algorithmiques Clés

1. Opérateur de Bellman Robuste Dual :
   Au lieu de calculer l'opérateur de Bellman robuste directement (ce qui est coûteux car il implique une optimisation sur un ensemble d'incertitude pour chaque paire état-action), l'article utilise une formulation duale.

   • L'espérance robuste est réécrite comme un problème d'optimisation convexe sur des variables duales $(\eta, \nu)$.
   • Cela permet de transformer le calcul de la mise à jour robuste en un problème de minimisation de perte fonctionnelle sur un espace de fonctions.

2. Apprentissage par Ajustement (Fitted Learning) Global :

   • L'algorithme maintient un ensemble de confiance (confidence set) de fonctions de valeur $F^{(k)}$.
   • Il utilise une optimisation fonctionnelle pour approximer les variables duales globalement, plutôt que de calculer des bonus par état-action (comme dans les méthodes UCB tabulaires).
   • À chaque épisode, l'algorithme :
     1. Collecte des trajectoires avec la politique courante.
     2. Met à jour l'ensemble de confiance en minimisant l'erreur de Bellman robuste empirique (via la perte duale).
     3. Sélectionne une politique optimiste (principe de l'optimisme face à l'incertitude) à partir de l'ensemble de confiance.

3. Gestion de l'Approximation de Fonction :
   Contrairement aux méthodes linéaires, RFL-ϕ fonctionne avec des classes de fonctions générales (ex: réseaux de neurones), sous des hypothèses de réalisabilité (la fonction de valeur optimale est dans la classe) et de complétude (l'opérateur de Bellman robuste préserve la classe de fonctions).

---

3. Contributions Théoriques Majeures

A. La Dimension de Bellman-Eluder Robuste (Robust BE Dimension)

C'est la contribution théorique centrale. Les auteurs introduisent une nouvelle mesure de complexité intrinsèque : la Robust Bellman-Eluder (BE) dimension.

• Définition : Elle mesure la complexité statistique de l'apprentissage des fonctions de valeur robustes en se basant sur la classe des résidus de Bellman robustes $(I - T^{\phi, \sigma})F$.
• Avantage : Contrairement aux mesures précédentes basées sur la couverture (coverage) ou les ratios de visite, cette dimension ne dépend pas de la taille de l'espace d'états/actions. Elle capture la difficulté d'apprentissage spécifique aux dynamiques adverses.
• Généralité : Elle englobe des cas connus comme les RMDP tabulaires, linéaires et les POMDP réactifs.

B. Garanties de Regret

Les auteurs établissent des bornes de regret pour RFL-ϕ qui sont :

• Sous-linéaires par rapport au nombre d'épisodes $K$.
• Indépendantes de la taille des espaces d'états ($S$) et d'actions ($A$).
• Dépendantes uniquement de la dimension Robust BE ($d$) et des paramètres de l'incertitude ($\sigma$).

La borne de regret est de l'ordre de :
$$\text{Regret}(K) \leq \tilde{O}\left( \sqrt{d H^2 B_\phi(\sigma)^2 K} + \epsilon_{\text{dual}} \right)$$
où $B_\phi(\sigma)$ est une constante liée à la divergence choisie et $\epsilon_{\text{dual}}$ est l'erreur d'approximation duale.

C. Complexité Échantillonnaire

Pour obtenir une politique $\epsilon$-optimale, le nombre d'échantillons requis est :
$$T = \tilde{O}\left( \frac{H^5 (\text{facteur } \sigma)^2 d \log(|F||G|)}{\epsilon^2} \right)$$
Ces bornes sont prouvées pour les divergences TV, $\chi^2$ et KL, et sont proches de l'optimalité minimax pour les cas tabulaires et linéaires.

---

4. Résultats Expérimentaux

Les auteurs valident leur approche sur le benchmark CartPole-v1 avec des perturbations réalistes :

1. Perturbation d'action : L'environnement ignore l'action de l'agent avec une probabilité $\rho$.
2. Perturbation de la force : Multiplication de la force appliquée par un facteur scalaire.
3. Perturbation de la longueur du poteau : Modification de la physique du système.

Résultats clés :

• Supériorité sur les méthodes non robustes : RFL-TV (version TV de l'algorithme) surpasse significativement DQN, GOLF et GOLF-DUAL (non robustes) sous toutes les perturbations, maintenant des récompenses élevées là où les autres échouent.
• Comparaison avec l'oracle tabulaire : RFL-TV, bien qu'utilisant des réseaux de neurones (approximation de fonction), atteint des performances comparables, voire supérieures, à OPROVI-TV, un algorithme tabulaire exact qui résout les équations de Bellman robustes. Cela démontre que l'approche par approximation de fonction ne sacrifie pas la précision théorique tout en étant scalable.
• Impact du rayon d'incertitude ($\sigma$) et de la capacité du réseau : Une augmentation du rayon $\sigma$ et de la capacité du réseau dual améliore la robustesse, confirmant la nécessité d'un compromis entre l'expressivité du modèle et la force de la régularisation robuste.

---

5. Signification et Impact

Ce travail est une avancée majeure pour plusieurs raisons :

1. Passage à l'échelle du DR-RL : Il brise la barrière des méthodes tabulaires et des hypothèses de données massives, rendant le RL robuste applicable à des problèmes réels à haute dimension (robotique, contrôle de systèmes complexes).
2. Cadre théorique unifié : L'introduction de la Robust BE dimension fournit un cadre théorique solide pour analyser l'apprentissage robuste avec approximation de fonction, comblant le fossé entre la théorie du RL standard et le RL robuste.
3. Praticité : L'algorithme est purement en ligne et ne nécessite pas de données pré-collectées, ce qui le rend directement applicable dans des environnements où la simulation est coûteuse ou impossible.
4. Efficacité computationnelle : En remplaçant les bonus par état-action par une quantification d'incertitude globale via l'optimisation fonctionnelle, l'approche est plus efficace pour les grands espaces d'états.

En conclusion, cet article pose les bases théoriques et algorithmiques pour un apprentissage par renforcement robuste, scalable et applicable dans des environnements dynamiques et incertains, sans dépendre de données hors ligne ou de modèles génératifs.