A Measure-Theoretic Finite-Sample Theory for Adaptive-Data Fitted Q-Iteration

Résumé technique : Une théorie des échantillons finis fondée sur la théorie de la mesure pour l'itération de Q ajustée avec des données adaptatives

Énoncé du problème
Malgré le succès empirique de l'apprentissage par renforcement (RL) profond hors politique et sans modèle dans des domaines complexes (par exemple, Atari, Go, StarCraft II, contrôle de la fusion nucléaire), une fondation théorique rigoureuse reste insaisissable. Les auteurs identifient un « fossé entre la théorie et la pratique » causé par l'isolement de trois traditions de recherche distinctes :

1. Théorie des MDP fondée sur la théorie de la mesure : Elle fournit des fondements rigoureux pour les espaces boréliens généraux (non dénombrables) et la contraction de Bellman, mais se limite à la programmation dynamique exacte, ignorant l'approximation de fonction et les erreurs d'estimation statistique.
2. Propagation de l'erreur d'approximation : Elle analyse comment les erreurs d'approximation s'accumulent via les sauvegardes de Bellman en utilisant des coefficients de concentrabilité, mais suppose généralement une infrastructure MDP bien définie sans traiter l'estimation sur échantillons finis ou les problèmes de mesurabilité.
3. Analyse sur échantillons finis : Elle fournit des bornes PAC et des garanties de regret pour les MDP discrets ou linéaires en utilisant des mesures de complexité statistique (par exemple, complexité de Rademacher, dimension d'éviction), mais repose sur des hypothèses d'échantillonnage i.i.d. et échoue à gérer la collecte de données adaptative et dépendante de la politique inhérente au RL pratique.

Par conséquent, aucun cadre existant n'offre de garanties de performance sur échantillons finis pour le RL hors politique avec approximation de fonction sur des espaces d'état-action continus qui soient à la fois rigoureux du point de vue de la théorie de la mesure et statistiquement solides sous une collecte de données adaptative.

Méthodologie
L'article propose un cadre théorique unifié pour l'itération de Q ajustée (FQI) sur des espaces boréliens mesurables généraux. La FQI est choisie car elle sert de modèle algorithmique pour le RL profond hors politique moderne, où les mises à jour itératives de Bellman sont approximées par une régression supervisée.

La méthodologie centrale implique une dérivation en trois étapes :

1. Fondation fondée sur la théorie de la mesure : Les auteurs établissent l'infrastructure nécessaire sur des espaces boréliens généraux $(S, \Sigma_S)$ et $(A, \Sigma_A)$, garantissant l'existence de sélecteurs optimaux mesurables (via le théorème de Jankov–von Neumann) et de mesures de trajectoire rigoureuses (via le théorème d'Ionescu–Tulcea). Ils définissent les opérateurs de Bellman comme des applications fonctionnelles sur des espaces de Banach de fonctions mesurables bornées, prouvant leurs propriétés de contraction.
2. Analyse des données adaptatives : Pour traiter la nature non i.i.d. des données de RL (où la politique de comportement dépend de l'itération courante), les auteurs emploient la complexité de Rademacher séquentielle. Cela généralise la complexité de Rademacher classique aux arbres prévisibles, permettant de contrôler les déviations des processus empiriques le long de chemins d'échantillonnage adaptatifs arbitraires.
3. Propagation de l'erreur et concentrabilité : L'analyse comble le fossé entre la distribution d'entraînement (mesures d'échantillonnage $\mu_k$) et la distribution d'évaluation ($\rho$) en utilisant un coefficient de concentrabilité adaptatif. Ce coefficient quantifie le décalage de distribution entre le processus générateur de données et les politiques induites pendant l'apprentissage.

Le cadre décompose l'erreur totale en :

• Erreur d'approximation : Erreur structurelle due au fait que la classe de fonctions $\mathcal{F}$ ne contient pas la cible réelle de Bellman.
• Erreur statistique : Erreur d'estimation contrôlée par la complexité de Rademacher séquentielle.
• Erreur d'optimisation : Marge due à la minimisation du risque empirique approximative (ERM).

Contributions clés

1. Cadre unifié : L'article synthétise les fondements des MDP basés sur la théorie de la mesure, la contraction des opérateurs de Bellman dans les espaces de Banach et la théorie de l'apprentissage statistique en un seul cadre cohérent pour la FQI sur des espaces boréliens généraux.
2. Bornes adaptatives sur échantillons finis : Il fournit la première borne de performance sur échantillons finis pour la FQI sous collecte de données adaptative (où les données dépendent de l'historique d'apprentissage). La borne est dérivée en enchaînant la probabilité fondée sur la théorie de la mesure avec la contraction des opérateurs de Bellman.
3. Contrôle par complexité de Rademacher séquentielle : Les auteurs prouvent que la complexité de Rademacher séquentielle contrôle l'erreur de généralisation de la régression de Bellman sous une collecte de données dépendante de la politique. Cela étend les analyses par lots précédentes au cadre en ligne et adaptatif.
4. Extension du regret : L'analyse est étendue pour fournir une garantie de regret en ligne cumulatif et pathwise, sous réserve de « certificats résiduels » spécifiques (contrôle des résidus diagonaux de Bellman) et d'hypothèses de couverture plus fortes.
5. Instantiation : Le cadre est instancié pour des classes linéaires, des espaces de Hilbert à noyau reproduisant (RKHS) et des réseaux de neurones contrôlés par une norme, retrouvant une échelle de résidu basée sur la norme de $O(n^{-1/4})$ sur des espaces continus.

Résultats

• Théorème 4 (Borne de performance) : Sous les hypothèses de classes de fonctions bornées, d'ERM approximative et de concentrabilité adaptative, la politique gourmande $\hat{\pi}_K$ extraite de la dernière itération de FQI $\hat{Q}_K$ satisfait une borne de performance sur échantillons finis :
  $$\|V^* - V^{\hat{\pi}_K}\|_{1,\rho} \leq \frac{4\sqrt{C_{ad}}}{(1-\gamma)^2 (1-\gamma^K)} \max_{0 \leq k < K} (\varepsilon_{app,k} + \sqrt{2\alpha'_k} + \varepsilon_{opt,k}) + \frac{8B\gamma^K}{1-\gamma}$$
  où $\alpha'_k$ évolue avec la complexité de Rademacher séquentielle de la classe de résidus de Bellman.
• Taux : La borne produit un taux « lent » standard de $O(n^{-1/4})$ pour l'échelle de résidu dans les espaces continus (par exemple, boules de Sobolev), ce qui est une conséquence de l'utilisation de la complexité de Rademacher séquentielle globale plutôt que de mesures localisées.
• Comparaison avec les travaux antérieurs : Les résultats englobent la théorie par lots existante (spécialisation i.i.d.) tout en s'étendant aux cadres adaptatifs. Contrairement aux travaux antérieurs qui supposent des espaces discrets ou des modèles linéaires, ce cadre gère des espaces boréliens généraux.

Signification et affirmations
L'article prétend poser les fondements nécessaires à l'analyse formelle de nombreux algorithmes modernes de RL profond. En comblant le fossé entre la rigueur de la théorie de la mesure et la complexité statistique, il fournit une justification formelle pour le RL profond hors politique sur des espaces d'état-action continus, un contexte où les théories précédentes étaient soit trop restrictives (discret/linéaire), soit dépourvues de garanties statistiques (DP exacte).

Les auteurs sont modestes quant à la portée de leurs résultats :

• Ils reconnaissent que le taux $O(n^{-1/4})$ est un « taux lent » par rapport aux taux rapides potentiels réalisables avec des mesures de complexité localisées, mais soutiennent que le cadre global offre un outil plus flexible pour les classes de fonctions à haute capacité.
• Ils déclarent explicitement que le résultat principal borne la sous-optimalité de la politique gourmande finale, et non le regret en ligne cumulatif de toute la trajectoire. Combler cet écart pour atteindre le regret cumulatif nécessite des hypothèses structurelles supplémentaires (par exemple, stabilité des itérations ou mécanismes d'exploration explicites comme UCB ou Thompson Sampling), identifiés comme des questions ouvertes.
• Le cadre suppose une concentrabilité adaptative (couverture des mesures d'évaluation des résidus de la politique finale par les mesures de conception), une hypothèse standard mais non triviale dans l'apprentissage hors politique.

En résumé, l'article ne propose pas un nouvel algorithme ou un benchmark expérimental, mais offre une « chaîne » théorique rigoureuse, allant de la bien-poséité borélienne à la généralisation séquentielle, ancrant le RL profond hors politique moderne dans les limites fondamentales des systèmes de transition boréliens.