Résumé Technique : Sur la complexité de l'apprentissage par renforcement hors ligne avec approximation de $Q^\star$ et couverture partielle

Énoncé du Problème

Ce travail étudie les limites théoriques de l'apprentissage par renforcement (RL) hors ligne dans le cadre de la $Q^\star$-réalisabilité et de la couverture partielle. Dans ce paradigme, un agent apprend une politique à partir d'un ensemble de données fixes, pré-collectées, sans interaction supplémentaire avec l'environnement. L'ensemble de données est généré par une politique de comportement qui peut ne pas couvrir l'intégralité de l'espace état-action (couverture partielle).

La question ouverte centrale est de savoir si la $Q^\star$-réalisabilité (la véritable fonction Q optimale appartient à une classe de fonctions connue), combinée à la complétude de Bellman (l'opérateur de Bellman projette la classe de fonctions dans un surensemble) et à la couverture partielle, est suffisante pour un apprentissage efficace en termes d'échantillonnage (sample-efficient). Bien que ces conditions permettent la construction d'un ensemble de confiance contenant la véritable $Q^\star$, l'article questionne si cela suffit à garantir une sélection de politique robuste.

Méthodologie

1. Borne Inférieure Information-Théorique

Les auteurs établissent d'abord que les conditions susmentionnées sont insuffisantes pour un apprentissage efficace en termes d'échantillonnage. Ils construisent une famille de processus de décision markoviens (MDP) où :

• La $Q^\star$-réalisabilité et la complétude de Bellman sont satisfaites.
• La couverture de la politique optimale est constante ($\Theta(1)$).
• Malgré le fait que la véritable fonction de valeur soit bien localisée au sein de la classe de fonctions, l'apprenant ne peut pas distinguer les politiques menant à des erreurs catastrophiques de celles qui sont sûres.
• La complexité d'échantillonnage requise est de l'ordre de $\Omega(\frac{1}{\epsilon} \min\{\sqrt{|S|}, \frac{1}{\Delta^2}\})$, où $\Delta$ est l'écart de valeur (value gap). Cela indique que même avec un petit écart, la complexité d'échantillonnage peut être prohibitive, et que la difficulté ne provient pas seulement de l'estimation de $Q^\star$, mais de la prise de décision robuste au sein de l'ensemble d'ambiguïté.

2. Cadre de Décomposition Décision-Estimation

Pour combler la lacune identifiée, les auteurs introduisent un cadre général de décision-estimation inspiré du coefficient de décision-estimation (DEC) de l'apprentissage RL en ligne. Ils décomposent la sous-optimalité du RL hors ligne en deux composantes modulaires :

1. Complexité de Décision : La difficulté de sélectionner une politique robuste à partir d'un ensemble de confiance de modèles plausibles.
2. Erreur d'Estimation : L'erreur encourue lors de l'estimation de la fonction de valeur ou des paramètres du modèle à partir des données hors ligne.

Ils définissent le Coefficient de Décision-Estimation Robuste Hors Ligne ($Ordec$) :
$$Ordec\text{-}OD_\gamma(F_{conf}) := \min_{\rho \in \Delta(\Pi)} \max_{M \in \mathcal{M}_{conf}} \mathbb{E}_{\pi \sim \rho} \left[ J_M(\pi_M) - J_M(\pi) - \gamma \max_{f \in F_{conf}} D_\pi(f \| M) \right]$$
Où :

• $F_{conf}$ est l'ensemble de confiance des fonctions $Q^\star$ plausibles.
• $\mathcal{M}_{conf}$ est l'ensemble induit des modèles plausibles.
• $\rho$ est une distribution sur les politiques.
• $D_\pi(f \| M)$ est une mesure de divergence (par exemple, l'erreur de Bellman) entre une fonction et un modèle, évaluée sous la politique optimale du modèle candidat $\pi_M$ (contrairement au DEC en ligne qui utilise la politique de l'apprenant).

Le cadre propose un algorithme (E2D.OR) qui produit une politique de mélange $\hat{\pi}$ satisfaisant :
$$J(\pi^\star) - \mathbb{E}[J(\hat{\pi})] \leq Ordec + \text{Erreur d'Estimation}$$

Contributions Clés

1. Résultat Négatif sur la Suffisance

L'article fournit une borne inférieure information-théorique prouvant que la $Q^\star$-réalisabilité, la couverture partielle et la complétude de Bellman ne sont pas suffisantes pour un apprentissage par renforcement hors ligne efficace en termes d'échantillonnage. Cela souligne que le défi central dans les contextes de couverture partielle est le problème de la "décision" — distinguer les politiques sûres des politiques dangereuses au sein de l'ensemble de confiance — plutôt que le simple problème de l' "estimation".

2. Cadre Unifié et Bornes Améliorées

Le cadre $Ordec$ proposé unifie et améliore les résultats existants :

• Contexte de l'Écart de Valeur (Value-Gap) : Récupère les résultats de Chen et Jiang (2022) mais élimine la nécessité de connaître la valeur de l'écart ou d'effectuer des interactions en ligne supplémentaires. La borne s'adapte automatiquement à l'écart réel.
• Contexte Régularisé : Améliore la borne de complexité d'échantillonnage pour le Soft Q-learning sous couverture partielle, passant de $\epsilon^{-4}$ (Uehara et al., 2023) à $\epsilon^{-2}$. Ceci est réalisé via un nouveau lemme de différence de performance de second ordre pour les MDP régularisés.
• Frontière de Décision Courbe : Introduit un nouveau régime apprenable basé sur la courbure de la frontière de décision dans les espaces d'actions continus, répondant aux préoccupations pratiques concernant l'hypothèse stricte de l'écart de valeur.

3. Nouveaux Régimes Apprenables pour l'Erreur d'Estimation

L'article caractérise le rôle des hypothèses structurelles dans le contrôle de l'erreur d'estimation :

• Complétude de Bellman : Fournit la première analyse de complexité d'échantillonnage pour le Conservative Q-Learning (CQL) sous approximation de fonction générale (précédemment limitée aux cas tabulaires).
• Faible Rang de Bellman : Étudie l'apprentissage hors ligne des MDP à faible rang de Bellman (un cadre canonique du RL en ligne). Les auteurs montrent que sous des hypothèses de données standards, le faible rang de Bellman est insuffisant pour l'apprentissage hors ligne. Ils introduisent deux conditions nécessaires pour l'apprentissage dans ce régime :
  1. Échantillonnage de Politique Double : Les données doivent être générées en échantillonnant une politique puis deux transitions indépendantes.
  2. Couverture des Caractéristiques de Politique : Une condition de couverture spécifique sur l'espace des caractéristiques des politiques.
     Le relâchement de l'une ou l'autre de ces conditions brise la garantie de complexité d'échantillonnage polynomiale.

Résumé des Résultats

• Borne Inférieure : Démontré que $Q^\star$-réalisabilité + complétude de Bellman + couverture partielle $\nRightarrow$ apprentissage efficace en termes d'échantillonnage.
• Borne Supérieure : Établi une borne de sous-optimalité générale décomposée en $Ordec$ (complexité de décision) et erreur d'estimation.
• Bornes Spécifiques :
  • Non-régularisé (Value Gap) : $\tilde{O}(\frac{H^2}{\gamma \Delta^2} + \gamma \frac{C_{\pi^\star}}{n})$. S'adapte aux écarts inconnus.
  • Régularisé : $\tilde{O}(\sqrt{\frac{C_{\pi^\star}}{n}})$, produisant une complexité d'échantillonnage de $\epsilon^{-2}$.
  • CQL : Première garantie d'approximation de fonction générale pour CQL sous couverture partielle.
  • Faible Rang de Bellman : Prouvé l'impossibilité sous des hypothèses standards ; identifié l'échantillonnage de politique double et la couverture des caractéristiques de politique comme nécessaires à l'apprentissage.

Signification et Revendications

L'article affirme fournir une compréhension plus complète du potentiel et des limites du RL hors ligne sous approximation de $Q^\star$ et couverture partielle. Sa signification réside dans :

1. Clarification de la Source de la Difficulté : Il déplace le focus théorique des erreurs d'estimation pures vers la complexité de décision inhérente aux contextes de couverture partielle, montant que même avec une estimation parfaite, la prise de décision robuste peut être impossible sans hypothèses structurelles supplémentaires.
2. Unification : Il offre un cadre modulaire qui récupère, améliore et étend les résultats antérieurs (Chen et Jiang, 2022 ; Uehara et al., 2023) en séparant les complexités de décision et d'estimation.
3. Pertinence Pratique : En analysant le CQL sous approximation de fonction générale et en identifiant les exigences structurelles spécifiques pour les problèmes à faible rang de Bellman, ce travail comble le fossé entre les algorithmes pratiques et les garanties théoriques dans des contextes auparavant considérés comme intraitables ou mal compris.
4. Nouveauté des Contextes : Il établit les premières conditions d'apprentissage pour les MDP à faible rang de Bellman en RL hors ligne et fournit la première borne $\epsilon^{-2}$ pour le Soft Q-learning régularisé sous couverture partielle.

Les auteurs notent que bien que le cadre soit théoriquement solide, la résolution exacte de l'algorithme minimax est numériquement difficile, bien qu'elle puisse être approximée via des méthodes acteur-critique. Le travail sert principalement à identifier de nouveaux régimes apprenables et à caractériser les conditions structurelles requises pour eux.