Résumé Technique : Apprentissage Q Asynchrone Tolérant aux Corruptions avec des Rates Presque Optimales

Formulation du Problème

Cet article aborde le problème de l'apprentissage d'une politique optimale dans un Processus de Décision Markovien (MDP) à horizon infini et à facteur d'actualisation, en présence de récompenses corrompues de manière adversaire. Le cadre implique un agent interagissant avec un environnement modélisé comme un MDP $(S, A, P, R, \gamma)$, où les données sont collectées en ligne via une politique de comportement $\mu$ qui induit une chaîne de Markov.

Le défi central est le modèle de contamination de Huber appliqué aux récompenses. À chaque pas de temps $t$, avec une probabilité $1-\epsilon$, l'agent observe une récompense échantillonnée à partir de la vraie distribution $R(s_t, a_t)$, qui peut être à queue lourde (admettant uniquement un moment d'ordre deux fini). Avec une probabilité $\epsilon$, la récompense est tirée d'une distribution adversaire arbitraire, potentiellement non bornée $Q$, qui peut dépendre de l'historique. L'objectif est d'estimer la fonction de valeur état-action optimale $Q^*$ avec une borne d'erreur à temps fini qui tient avec une forte probabilité, malgré la corruption et la nature temporellement corrélée des données (échantillonnage asynchrone, trajectoire unique).

Méthodologie

Les auteurs proposent Robust Async-Q, une variante novatrice de l'algorithme Q-learning conçue pour gérer l'échantillonnage asynchrone et la corruption adversaire. L'algorithme intègre deux mécanismes principaux :

1. Estimation Robuste des Récompenses par Moyennes Taillées :
   Au lieu d'utiliser les moyennes d'échantillons bruts, l'algorithme maintient un historique des récompenses pour chaque paire état-action $(s, a)$. Il emploie un estimateur de moyenne taillée univariée (basé sur Lugosi & Mendelson, 2021) pour calculer une estimation robuste de l'espérance de la récompense. Cet estimateur divise les données en deux moitiés, utilise l'une pour calculer des quantiles empiriques afin de filtrer, et moyenne les échantillons restants de la seconde moitié qui tombent dans ces quantiles. Cette approche offre une robustesse face aux distributions à queue lourde et à une fraction de valeurs aberrantes.

2. Seuillage Adaptatif :
   Pour répondre à la nature probabiliste des garanties d'estimation de la moyenne robuste (qui peuvent échouer lors d'événements extrêmes rares) et au manque de connaissance des statistiques des récompenses dans certains contextes, l'algorithme emploie un mécanisme de seuillage adaptatif.

   • Statistiques Connues : Si les bornes sur la moyenne et la variance des récompenses ($\bar{R}, \bar{\sigma}$) sont connues, un seuil adaptatif $G_t$ est construit. Si l'estimation robuste dépasse ce seuil, l'estimation est rejetée (mise à zéro). Le seuil rétrécit au fil du temps à mesure que davantage d'échantillons sont collectés.
   • Agnostique aux Récompenses (Statistiques Inconnues) : Lorsque les statistiques des récompenses sont inconnues, l'algorithme utilise une fonction de temps « croissant lentement », $m(t) = t^p$, comme substitut aux bornes inconnues. Cela garantit que le seuil finit par dominer toute borne constante vraie, permettant à l'algorithme de fonctionner sans connaissance préalable de l'échelle de la distribution des récompenses.

L'algorithme met à jour les valeurs Q en utilisant ces substituts de récompenses filtrés et seuillés dans la règle de mise à jour standard du Q-learning asynchrone. Pour le cadre markovien de trajectoire unique, les auteurs proposent une stratégie de sous-échantillonnage (utilisant chaque $\tau$-ème échantillon, où $\tau$ est lié au temps de mélange) pour découpler les dépendances temporelles, réduisant efficacement le problème à une analyse de type i.i.d.

Contributions Clés

1. Algorithme Novateur : L'article introduit Robust Async-Q et sa variante agnostique aux récompenses Robust Async-RAQ. Ce sont les premiers algorithmes à fournir des garanties de robustesse à temps fini pour le Q-learning asynchrone sous corruption adversaire et bruit à queue lourde.
2. Bornes Supérieures à Temps Fini :
   • Sous échantillonnage i.i.d., les auteurs prouvent que l'algorithme converge vers $Q^*$ à un taux de $\tilde{O}(1/\sqrt{T})$, correspondant au taux optimal pour le Q-learning standard, jusqu'à un terme additif évoluant avec $\sqrt{\epsilon}$.
   • Sous échantillonnage markovien (trajectoire unique), les bornes sont préservées jusqu'à un facteur d'inflation lié au temps de mélange de la chaîne sous-jacente, cohérent avec les résultats du Q-learning asynchrone non robuste.
3. Borne Inférieure Informationnelle : Les auteurs établissent une borne inférieure fondamentale de $\Omega(\sqrt{\epsilon})$ sur l'erreur d'estimation de $Q^*$. Cela prouve que le terme additif de corruption dans leur borne supérieure est inévitable, même dans un cadre synchrone où toutes les paires état-action sont observées simultanément.
4. Techniques de Preuve Novatrices :
   • Inégalité Azuma-Hoeffding Raffinée : Une contribution technique critique est l'application d'une variante raffinée de l'inégalité Azuma-Hoeffding (Shamir & Spencer, 1987). Cet outil est nécessaire car les différences de martingale dans le cadre agnostique aux récompenses admettent une borne déterministe grossière (évoluant avec le temps) mais une borne plus fine à forte probabilité. Les inégalités de concentration standard échouent à produire des résultats non vides dans ce contexte.
   • Couplage pour Données Markoviennes : L'analyse s'étend aux données de trajectoire unique en utilisant une technique de couplage pour relier la chaîne de Markov sous-échantillonnée à une séquence i.i.d.

Résultats

• Rates de Convergence : Les algorithmes proposés atteignent des rates à temps fini presque optimales. Spécifiquement, la borne d'erreur est de la forme :
  $$\|Q_T - Q^*\|_\infty \leq \tilde{O}\left(\frac{1}{\sqrt{T}}\right) + O(\sqrt{\epsilon})$$
  Le terme $O(\sqrt{\epsilon})$ dépend de la fraction de corruption et de la variance du bruit, mais est indépendant de l'ampleur des attaques adverses.
• Robustesse aux Queues Lourdes : Les algorithmes fonctionnent correctement même lorsque les distributions réelles des récompenses sont à queue lourde (seul un moment d'ordre deux fini), un cadre où le Q-learning standard échoue souvent ou nécessite des hypothèses sous-gaussiennes.
• Performance Agnostique : La variante agnostique aux récompenses (Robust Async-RAQ) atteint les mêmes rates que la variante aux statistiques connues, avec seulement une légère inflation polynomiale dans la dépendance au paramètre d'échelle inconnu.
• Simulations : Les résultats empiriques sur les environnements Grid-world, FrozenLake, CliffWalking et Taxi démontrent que le Q-learning standard subit des erreurs significatives sous corruption, tandis que les variantes robustes proposées convergent vers un voisinage de la fonction de valeur optimale.

Importance et Revendications

L'article revendique fournir la première étude principielle et complète de la robustesse adversaire dans le cadre RL à horizon infini et à facteur d'actualisation, avec des données asynchrones et markoviennes.

• Complétude Théorique : En fournissant des bornes supérieures et inférieures correspondantes (jusqu'au terme de corruption), l'ouvrage dresse un « tableau assez complet » des limites fondamentales de l'apprentissage dans de tels environnements adverses.
• Combler les Lacunes : Il comble le fossé entre les statistiques robustes (spécifiquement le modèle de Huber et les moyennes taillées) et l'analyse non asymptotique de l'approximation stochastique asynchrone.
• Pertinence Pratique : L'ouvrage répond à des préoccupations réelles où les données de feedback (récompenses) peuvent être bruyantes, biaisées ou malicieusement corrompues, comme dans le feedback humain pour les grands modèles de langage ou les données de capteurs dans les systèmes autonomes.
• Avancement Méthodologique : L'introduction de l'inégalité Azuma-Hoeffding raffinée pour gérer des bornes « déterministes grossières mais probabilistes fines » est mise en avant comme un outil ayant une applicabilité plus large potentielle dans l'étude des algorithmes de RL au-delà de ce problème spécifique.

Les auteurs notent que, bien que leur travail établisse de fortes garanties théoriques, les orientations futures incluent l'extension du cadre aux corruptions dans le flux complet de feedback (transitions et récompenses) et aux contextes d'approximation de fonctions.