Résumé Technique : Q-MMR : Évaluation Hors-Politique par Recalage Récursif et Appariement de Moments

1. Énoncé du Problème

L'article traite de l'Évaluation Hors-Politique (OPE) dans les Processus de Décision Markoviens (MDP) à horizon fini. L'objectif est d'estimer le retour espéré $J(\pi)$ d'une politique cible $\pi$ en utilisant un jeu de données collecté à partir d'une politique de comportement $\pi_D$. Le cadre implique une Approximation Fonctionnelle Générale (GFA), où une classe de fonctions $\mathcal{F}$ est utilisée pour modéliser la fonction Q de la politique cible, $Q^\pi$.

Les auteurs identifient deux lacunes théoriques principales dans la littérature existante sur l'OPE :

1. Dépendance à la Dimension : Les analyses standard pour la GFA (par exemple, l'Évaluation Q Ajustée, FQE) produisent généralement des bornes d'erreur qui dépendent de la complexité statistique de la classe de fonctions (par exemple, $\log |\mathcal{F}|$ ou les nombres de recouvrement). Cette dépendance est souvent lâche, en particulier dans les contextes en politique où les estimations de Monte-Carlo sont indépendantes de la dimension.
2. Incohérence avec les Analyses Linéaires/Tabulaires : Des garanties affinées et indépendantes de la dimension existent pour les contextes linéaires et tabulaires (souvent sous la seule hypothèse de réalisabilité), mais ces résultats ne s'étendent pas naturellement aux classes de fonctions générales. De plus, les analyses linéaires reposent souvent sur des conditions plus faibles (réalisabilité) par rapport aux hypothèses de complétude de Bellman requises pour les analyses GFA générales.

2. Méthodologie : Q-MMR

Les auteurs proposent Q-MMR (Recalage Apparié aux Moments basé sur la Fonction Q), un cadre algorithmique novateur qui apprend un ensemble de poids scalaires, un pour chaque point de données, de manière inductive de haut en bas.

Aperçu de l'Algorithme

Étant donné $n$ trajectoires i.i.d. et une classe de fonctions $\mathcal{F} = \{\mathcal{F}_h\}_{h=1}^H$ :

1. Initialisation : Définir les poids $w^{(i)}_0 \equiv 1$ pour tous les points de données $i$ (puisque la paire état-action initiale est fixe).
2. Recalage Récursif : Pour chaque étape de temps $h = 1$ à $H$, l'algorithme apprend un vecteur de poids $w^{[n]}_h = \{w^{(i)}_h\}_{i=1}^n$ en résolvant un problème d'optimisation minimax :
   $$\hat{w}^{[n]}_h = \arg\min_{w^{[n]}_h} \sup_{f \in \mathcal{F}_h} \left| \frac{1}{n} \sum_{i=1}^n w^{(i)}_h f(s^{(i)}_h, a^{(i)}_h) - \frac{1}{n} \sum_{i=1}^n \hat{w}^{(i)}_{h-1} f(s^{(i)}_h, \pi) \right|$$
   Cet objectif minimise l'écart (via une Métrique de Probabilité Intégrale) entre la distribution recalée des paires état-action courantes et la distribution recalée du prochain état sous la politique cible.
3. Estimation : L'estimation finale du retour est la somme recalée des récompenses :
   $$\hat{J}(\pi) = \frac{1}{n} \sum_{i=1}^n \sum_{h=1}^H w^{(i)}_h r^{(i)}_h$$

Choix de Conception Clés

• Poids Non-Paramétriques : Contrairement aux méthodes d'Échantillonnage d'Importance Marginalisée (MIS) qui apprennent une fonction paramétrique pour les poids, Q-MMR apprend un scalaire distinct pour chaque point de données.
• Principe du Moindre 2ème Moment : Puisque le minimiseur de la perte d'appariement n'est généralement pas unique, l'algorithme sélectionne la solution ayant le 2ème moment empirique minimal ($\|w^{[n]}_h\|_{[n]}$) pour contrôler la variance.
• Induction de Haut en Bas : Les poids sont calculés niveau par niveau, de $h=0$ à $H$, en s'appuyant sur les poids de l'étape précédente.

3. Contributions Clés et Résultats Théoriques

A. Garantie Finie Indépendante de la Dimension

La contribution théorique principale est le Théorème 1, qui fournit une borne finie dépendante des données pour l'erreur d'OPE. Sous l'Hypothèse Standard de Réalisabilité ($Q^\pi \in \mathcal{F}$), avec une probabilité d'au moins $1-\delta$ :
$$|\hat{J}(\pi) - J(\pi)| \leq \sum_{h=1}^H \hat{L}_h(\hat{w}^{[n]}_h; \hat{w}^{[n]}_{h-1}) + \sum_{h=0}^H \epsilon^{\text{stat}}_h$$
où :

• $\hat{L}_h$ est la perte d'appariement empirique atteinte par l'algorithme.
• $\epsilon^{\text{stat}}_h \propto \| \hat{w}^{[n]}_h \|_{[n]} \sqrt{\frac{\log(1/\delta)}{n}}$.

Signification :

• Indépendant de la Dimension : La borne ne dépend pas explicitement de la complexité statistique de $\mathcal{F}$ (par exemple, aucun terme $\log |\mathcal{F}|$) dans l'ordre dominant. Cela est obtenu en évitant les bornes d'union sur la classe de fonctions et en s'appuyant plutôt sur des arguments de concentration spécifiques aux poids réalisés.
• WYSIWYG (Ce que vous voyez est ce que vous obtenez) : La borne est directement calculable à partir des données, car elle dépend de la perte d'appariement observée et du 2ème moment des poids appris.
• Hypothèses Plus Faibles : La garantie tient sous la seule Réalisabilité, sans nécessiter l'hypothèse de complétude de Bellman plus forte généralement requise pour la GFA.

B. Lien avec les Méthodes Existantes

L'article établit que Q-MMR unifie et retrouve les résultats connus dans des cas particuliers :

• Contextes Linéaires et Tabulaires : Lorsqu'il est spécialisé pour des classes de fonctions linéaires (avec une matrice de covariance d'échantillon inversible) ou des contextes tabulaires, Q-MMR coïncide respectivement avec le FQE Linéaire et le FQE Tabulaire (ou l'équivalence de certitude basée sur un modèle).
• Récupération de Bornes Granulaires : Dans ces cas particuliers, l'analyse Q-MMR retrouve les taux indépendants de la dimension et en $O(1/\sqrt{n})$ trouvés dans la littérature linéaire/tabulaire antérieure (par exemple, Duan et al., 2020 ; Yin et Wang, 2021), comblant ainsi le fossé entre les analyses générales et linéaires.
• Monte-Carlo et Échantillonnage d'Importance : Dans les contextes en politique, définir les poids à 1 retrouve l'estimateur de Monte-Carlo. Avec des modifications spécifiques, il peut également retrouver l'échantillonnage d'importance étape par étape.

C. Insights sur la Couverture

L'article fournit une compréhension théorique plus profonde de la couverture dans l'apprentissage par renforcement hors ligne :

• Magnitude des Poids comme Couverture : Le terme $\|w^{[n]}_h\|_{[n]}$ (et son équivalent population $\|w^\star_h\|_{2, d_D}$) agit comme un paramètre de couverture empirique.
• Nature de la Couverture : Grâce à une analyse ultérieure (Section 4), les auteurs montrent que la "couverture" requise n'est pas simplement la couverture de l'occupation de caractéristiques de la politique cible $E_{d^\pi}[\phi]$, mais plutôt la couverture d'un vecteur défini par un système dynamique linéaire spécifique (analogue à $\psi_h$ dans les analyses linéaires).
• Complétude de Bellman : Sous complétude de Bellman, les poids populationnels $w^\star_h$ récupèrent parfaitement la distribution cible $d^\pi_h$, et le terme de stabilité contrôlant l'explosion des poids est borné par 1. Sans complétude, la stabilité dépend de la norme operatorielle des opérateurs de transition projetés, ce qui peut entraîner une croissance exponentielle des poids si le système est instable.

4. Signification et Revendications

L'article revendique fournir un cadre théorique unifié qui résout la tension entre l'approximation fonctionnelle générale et les analyses linéaires/tabulaires en OPE.

• Unification : Il démontre que les propriétés "indépendantes de la dimension" observées dans les contextes linéaires/tabulaires ne sont pas des artefacts de la linéarité mais peuvent être atteintes dans des contextes généraux sous réalisabilité, à condition d'utiliser une approche d'appariement de moments avec des poids non paramétriques.
• Nouveauté de l'Analyse : L'analyse est décrite comme "starkement simple", évitant les bornes d'union complexes sur la classe de fonctions. Elle exploite la nature télescopique de l'équation de Bellman et la structure spécifique de l'objectif d'appariement de moments.
• Implications Pratiques : La borne dépendante des données offre un mécanisme intégré pour la quantification de l'incertitude, car la borne d'erreur est calculable à partir du jeu de données sans avoir besoin de connaître la complexité réelle de la classe de fonctions.

Les auteurs notent des limitations, notamment l'exigence de données de trajectoires i.i.d. (ce qui échoue dans la collecte adaptative) et la nature greedy et locale de l'optimisation des poids (qui ne prend pas explicitement en compte les effets en aval, bien que ce soit un compromis pour éviter les problèmes de double échantillonnage trouvés dans d'autres méthodes MIS).

En résumé, Q-MMR offre une approche théoriquement rigoureuse et indépendante de la dimension pour l'OPE qui généralise les propriétés favorables des méthodes linéaires aux classes de fonctions générales tout en ne reposant que sur la réalisabilité.