Finite-Time Convergence of Distributionally Robust Q-Learning with Linear Function Approximation

Résumé Technique : Convergence en Temps Fini de l'Apprentissage Q Distributionnellement Robuste avec Approximation de Fonction Linéaire

Énoncé du Problème
L'article traite du défi consistant à apprendre des politiques optimales dans l'Apprentissage par Renforcement Distributionnellement Robuste (DRRL) lorsque l'environnement de déploiement diffère de l'environnement d'entraînement (nominal). Plus précisément, les auteurs se concentrent sur l'apprentissage Q robuste à horizon de discote réduit (discounted) et sans modèle sous un ensemble d'incertitude $\chi^2$ $(s, a)$-rectangulaire.

Le cadre implique un apprenant opérant sur une trajectoire markovienne unique générée par un noyau de transition nominal $P_0$ inconnu et une politique de comportement $\pi_b$. L'apprenant ne dispose pas d'un accès génératif (il ne peut pas échantillonner des couples état-action arbitraires) et ne connaît pas $P_0$. L'objectif est d'apprendre la fonction Q robuste optimale, $Q^\star_\chi$, qui maximise la valeur la plus défavorable sur l'ensemble d'incertitude.

Le problème présente deux difficultés couplées :

1. Difficulté d'Approximation de Fonction : Bien que l'opérateur de Bellman robuste exact soit une contraction dans $\ell_\infty$, l'opérateur de Bellman robuste projeté induit par l'approximation de fonction linéaire n'est pas connu pour être une contraction pour des facteurs de remise (discount factors) $\gamma \in (0, 1)$ généraux.
2. Difficulté d'Estimation Robuste : La mise à jour de Bellman robuste $\chi^2$ implique une minimisation interne sur les distributions de transition. Son gradient dual dépend de moments conditionnels (spécifiquement, la partie positive de l'écart de Bellman et son carré) qui doivent être estimés à partir d'une trajectoire unique. Les analyses standard pour l'apprentissage Q tabulaire ou l'apprentissage Q linéaire ne s'étendent pas directement à ce cadre.

Méthodologie
Les auteurs proposent l'Algorithme 1, un algorithme d'approximation stochastique à plusieurs étapes qui combine une boucle externe de réseau cible (target-network) avec un schéma d'approximation de fonction dual. L'algorithme opère dans des blocs externes où la fonction Q cible est gelée. Au sein de chaque bloc, trois étapes se produisent :

1. Étape 1 : Optimisation Duale avec Suivi de Moment.
   L'algorithme résout la minimisation interne de la mise à jour de Bellman robuste $\chi^2$ via sa forme scalaire duale. Au lieu de résoudre un problème dual distinct pour chaque paire état-action, la variable duale $\eta$ est approximée linéairement ($\eta_\nu(i) = \psi(i)^\top \nu$).

   • Schéma à Deux Échelles de Temps (Two-Time-Scale) : La variable duale $\nu$ est mise à jour sur une échelle de temps lente, tandis que deux « critiques de suivi de moment » ($\omega_1, \omega_2$) estiment les moments conditionnels requis ($Z_1$ et $Z_2$) sur une échelle de temps plus rapide.
   • Lissage (Smoothing) : Pour gérer le manque de lissé global de l'objectif dual $\chi^2$ (qui pose des problèmes d'analyse de bruit markovien), les auteurs optimisent un objectif substitut lissé utilisant un paramètre ajustable $\tau > 0$. Cela garantit que le gradient dual est Lipschitz continu.
   • Moyennage de Suffixe (Suffix Averaging) : Les itérés duaux sont moyennés par suffixe pour obtenir une estimation stable $\bar{\nu}_t$.

2. Étape 2 : Évaluation Fraîche (Fresh Evaluation).
   Avant de mettre à jour la fonction Q, l'algorithme effectue une « évaluation fraîche » du moment de type variance ($Z_1$) en utilisant le paramètre dual moyenné $\bar{\nu}_t$. Cette étape isole l'estimation du moment de la trajectoire d'optimisation, empêchant l'accumulation de biais qui se produirait si les critiques de l'Étape 1 (appris pendant que $\nu$ se déplaçait) étaient réutilisés directement.

3. Étape 3 : Mise à jour de Q.
   L'algorithme effectue une mise à jour de différence temporelle (TD) lente du paramètre $\theta$ de la fonction Q robuste contre la cible évaluée et fixe dérivée des Étapes 1 et 2.

Contributions Clés

1. Garantie de Convergence en Temps Fini : L'article fournit la première borne de convergence en temps fini pour l'apprentissage Q robuste avec approximation de fonction linéaire à partir de données de trajectoire unique, sans imposer de restrictions de petit facteur de remise.
2. Analyse de Réseau Cible pour le RL Robuste : Les auteurs adaptent la technique du réseau cible (courante dans le RL profond non robuste) au cadre robuste. En gelant la fonction Q cible au sein de blocs externes, ils contournent la non-contractivité de l'opérateur de Bellman robuste projeté, permettant à l'analyse de reposer sur la contraction de l'opérateur non projeté à travers les blocs.
3. Estimation Duale Scalable : Ils introduisent une méthode pour approximer la variable duale elle-même en utilisant une classe de fonctions linéaires, couplée à des critiques de suivi de moment. Cela évite les problèmes de scalabilité liés à la résolution de problèmes duaux indépendants pour de grands espaces d'états.
4. Lissage et Contrôle du Biais : Le papier introduit un substitut lissé pour l'objectif dual $\chi^2$. Cela résout le problème du gradient non-Lipschitz inhérent à la formulation $\chi^2$ exacte, permettant des bornes rigoureuses d'approximation stochastique en temps fini sous bruit markovien. Les auteurs notent explicitement que les preuves précédentes pour l'apprentissage Q robuste tabulaire avec incertitude $\chi^2$ reposaient sur des hypothèses de lissé global qui ne tiennent pas ; leur preuve corrige cette lacune.

Résultats
Le résultat théorique principal (Théorème 1) établit une borne de convergence de bout en bout de la forme :
$$\mathbb{E}[\| \hat{Q}_T - Q^\star_\chi \|_\infty] \leq \gamma^T \| \hat{Q}_0 - Q^\star_\chi \|_\infty + \frac{E_{stat}(N, M, K, \tau) + E_{app}(\tau)}{1 - \gamma}$$
où :

• Le premier terme représente l'erreur de contraction du réseau cible.
• $E_{stat}$ capture les erreurs d'échantillonnage fini de la mise à jour de Q, de l'optimisation duale, du lissage et de l'évaluation fraîche.
• $E_{app}$ capture les erreurs d'approximation dues à l'approximation de fonction et au lissage.

Le Corollaire 2 dérive la complexité d'échantillonnage, montrant que pour atteindre une erreur $\epsilon$, la longueur totale de la trajectoire passe à $\tilde{O}(\epsilon^{-5/(1-a)})$ (où $a$ est un paramètre de taille de pas), à des facteurs logarithmiques près.

Les expériences sur l'MDP FrozenLake valident la théorie, démontrant la convergence vers la valeur de référence robuste et illustrant le compromis introduit par le paramètre de lissage $\tau$ (un $\tau$ plus petit réduit le biais mais augmente la variance/l'erreur d'optimisation).

Signification et Revendications
Le papier prétend combler un fossé important entre le succès empirique des algorithmes de RL robuste et les garanties théoriques disponibles pour leurs homologues non robustes. Les travaux antérieurs sur le RL robuste sans modèle étaient limités aux contextes tabulaires, nécessitaient un accès génératif, supposaient une exploration active ou imposaient des conditions restrictives sur le facteur de remise.

Les auteurs affirment que leur travail fournit la première garantie de convergence en temps fini pour l'apprentissage Q robuste sans modèle à horizon réduit avec approximation de fonction linéaire à partir de données de trajectoire unique, sans hypothèse de petit facteur de remise. De plus, ils affirment que leur preuve pour le cas $\chi^2$ (même dans la limite tabulaire) semble être la première preuve correcte de convergence, car elle traite l'absence de lissé global dans l'objectif dual que les analyses précédentes avaient négligée ou ignorée. Le cadre est présenté comme un modèle analysable pouvant être étendu à des implémentations de réseaux de neurones à grande échelle.