📊 statistics

Fitted Occupancy-Ratio Evaluation without Bellman Completeness

Cet article introduit l'Évaluation par Ratio d'Occupation Ajusté (FORE), une méthode d'évaluation de politique hors ligne qui atteint la convergence sans complétude de Bellman en s'appuyant uniquement sur la réalisabilité du ratio d'occupation actualisé via une récursion de Bellman adjointe basée sur une contraction de type KL.

Auteurs originaux : Lars van der Laan, Nathan Kallus

Publié 2026-07-29

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Lars van der Laan, Nathan Kallus

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'apprendre à un robot comment jouer à un jeu vidéo, mais que vous n'avez pas le droit de laisser le robot jouer lui-même. À la place, vous ne disposez que d'un immense carnet poussiéreux rempli de mouvements et de résultats d'un autre joueur qui jouait à ce jeu il y a longtemps. C'est le monde de l'« apprentissage par renforcement hors ligne » (offline reinforcement learning). Le défi est que la nouvelle stratégie du robot pourrait être très différente de celle du joueur du carnet. Si le robot tente de visiter une partie du monde du jeu que l'ancien joueur n'a jamais touchée, le carnet n'aura aucune donnée pour cet endroit. C'est comme essayer de naviguer dans une nouvelle ville en utilisant la carte d'une ville différente ; vous pourriez vous perdre ou faire des suppositions dangereuses. Pour corriger cela, les scientifiques utilisent un truc mathématique appelé « ratio d'occupation ». Considérez ce ratio comme une loupe spéciale ou un ensemble de poids qui dit au robot : « Hé, l'ancien joueur est rarement venu ici, mais notre nouveau plan prévoit d'y aller tout le temps. Donc, quand nous regardons les anciennes données, nous devons accorder une importance supplémentaire aux rares fois où il y est allé, et ignorer les endroits où il n'est jamais allé. »

Pendant longtemps, calculer ces poids revenait à essayer de résoudre un puzzle où chaque pièce placée rendait la recherche de la suivante plus difficile. Les méthodes standards exigeaient une condition très stricte : la « carte » de la nouvelle stratégie devait être parfaitement compatible avec la « carte » des anciennes données d'une manière mathématique complexe. Si la nouvelle stratégie était trop différente, les mathématiques s'effondraient, et le robot apprenait de mauvaises leçons. Ce papier introduit une nouvelle méthode appelée Fitted Occupancy-Ratio Evaluation (FORE). Au lieu de forcer les pièces du puzzle à s'emboîter parfaitement, FORE utilise une approche astucieuse, étape par étape, qui se corrige naturellement. Il traite le problème comme une partie de « chaud et froid », où le robot ajuste lentement ses poids pour se rapprocher de la vérité, sans avoir besoin de la compatibilité stricte qui était autrefois requise. Les auteurs montrent que tant que le nouveau plan du robot peut être décrit par les outils dont il dispose, il peut apprendre les poids corrects et faire des prédictions précises et sûres sur sa propre performance, même si les anciennes données étaient désordonnées ou incomplètes.

L'histoire de la loupe auto-correctrice

Dans le monde de l'intelligence artificielle, il existe un problème classique : comment évaluer un nouveau plan en utilisant uniquement d'anciennes données ? Imaginez que vous soyez un entraîneur essayant d'évaluer la stratégie d'une nouvelle équipe de football, mais que les seules images dont vous disposez sont celles d'une équipe complètement différente jouant dans une ligue différente. Si la nouvelle équipe tente de marquer depuis un endroit que l'ancienne équipe n'a jamais touché, vos images sont inutiles. Vous avez besoin d'un moyen de « re-pondérer » les anciennes images pour qu'elles donnent l'impression que c'est la nouvelle équipe qui a joué. C'est là qu'intervient le ratio d'occupation. C'est un nombre qui vous indique à quel point la nouvelle équipe visite un endroit spécifique plus (ou moins) souvent que l'ancienne équipe.

Les auteurs du papier ont remarqué que les anciennes façons de calculer ce ratio étaient comme essayer d'équilibrer une balançoire avec une barre lourde et rigide. Il fallait supposer que la « balançoire » (les mathématiques sous-jacentes) était parfaitement stable et que les mouvements de la nouvelle équipe étaient parfaitement prévisibles basés sur ceux de l'ancienne équipe. Si la nouvelle équipe faisait quelque chose d'inattendu, tout le calcul vacillait et échouait. Ils ont appelé cela le besoin de « complétude de Bellman » (Bellman completeness), une façon sophistiquée de dire : « Les mathématiques doivent être capables de décrire parfaitement chaque mouvement futur possible. »

Entrée en scène de FORE (Fitted Occupancy-Ratio Evaluation).

Les auteurs proposent une nouvelle façon de trouver ces poids qui est beaucoup plus flexible. Au lieu d'essayer de résoudre une équation géante et impossible d'un seul coup, FORE travaille comme un sculpteur qui dégrossit un bloc de pierre. Il commence par une estimation grossière, puis l'affine de manière répétée.

Voici le tour de magie :

La récursion de Bellman adjointe : Imaginez le ratio d'occupation comme l'ombre projetée par la stratégie de la nouvelle équipe. Le papier montre que cette ombre suit une règle spécifique (une « équation de Bellman adjointe »).
La projection KL : Au lieu de forcer l'ombre à entrer dans un moule rigide, FORE utilise un type spécial de « loupe » appelé divergence KL (une façon de mesurer à quel point deux distributions de probabilité sont différentes). À chaque étape, FORE prend l'estimation actuelle de l'ombre et la projette sur la meilleure forme possible qu'il puisse créer avec les outils à sa disposition.
L'auto-correction : La partie la plus excitante est que ce processus réduit naturellement l'erreur. Les auteurs prouvent qu'à chaque étape, l'estimation se rapproche de la vraie valeur du ratio, comme une balle roulant vers le fond d'une vallée. Crucialement, cela se produit sans nécessiter la stricte condition de « complétude de Bellman ». La méthode fonctionne tant que le vrai ratio peut être approximé par les outils dont le robot dispose, même si ces outils ne peuvent pas décrire parfaitement chaque mouvement futur.

Ce que le papier a réellement découvert

Les auteurs n'ont pas seulement imaginé cela ; ils l'ont prouvé mathématiquement et l'ont testé.

La découverte principale : Ils ont démontré que FORE converge vers le ratio d'occupation correct. Si le vrai ratio existe dans la classe de fonctions utilisée par l'algorithme (une condition appelée « réalisabilité »), l'erreur diminue de manière géométrique. Cela signifie que la méthode est stable et fiable, même lorsque la nouvelle stratégie est très différente des anciennes données.
Ce qu'il écarte : Le papier argumente explicitement contre l'idée selon laquelle vous avez besoin de la « complétude de Bellman » ou de la « complétude de Bellman adjointe » pour obtenir de bons résultats. Par le passé, les chercheurs pensaient qu'il fallait une carte parfaite de tous les futurs possibles pour que cela fonctionne. FORE montre que ce n'est pas le cas. Vous avez juste besoin d'une bonne approximation du ratio lui-même.
Les scénarios de « Et si ? » (Couverture) : Le papier traite également du problème de la « couverture insuffisante ». Que se passe-t-il si la nouvelle équipe va dans une partie du terrain que l'ancienne équipe n'a jamais visitée ? Dans ce cas, le ratio complet ne peut être connu. Les auteurs introduisent le Coverage-Stopped FORE. Cette version agit comme une soupape de sécurité. Elle estime la valeur de la nouvelle stratégie uniquement jusqu'au point où les données viennent à manquer. Elle fournit une « borne inférieure conservatrice », disant essentiellement : « Nous savons avec certitude que l'équipe obtiendra au moins cette valeur, même si nous ne savons pas ce qui se passe dans les zones inexplorées. »

La preuve et la pratique

Pour appuyer leurs affirmations, les auteurs ont fait deux choses :

Preuves mathématiques : Ils ont fourni des preuves rigoureuses montrant que l'erreur de leur méthode est bornée. Ils ont décomposé l'erreur en trois parties : l'écart de l'estimation initiale, la capacité des outils à approximer le vrai ratio, et le bruit statistique dû à la quantité limitée de données. Ils ont montré que la méthode gère ces trois aspects avec élégance.
Simulations : Ils ont mené des expériences informatiques pour voir comment FORE se comporte dans le monde réel des nombres.
- Expérience 1 (MRP de type Baird) : Ils ont utilisé un problème classique en forme d'étoile où les anciennes méthodes (comme le Fitted Q-Evaluation standard) sont connues pour exploser et échouer. FORE, cependant, est resté stable et a convergé vers la bonne réponse.
- Expérience 2 (Linéaire-Gaussien) : Ils ont testé un problème continu où les mathématiques deviennent complexes. Là encore, les méthodes standards ont eu du mal, mais FORE et une version de FORE qui « re-pondère » les données (FORE-reweighted FQE) ont bien mieux performé, maintenant les erreurs à un niveau bas même lorsque le jeu devenait plus difficile.
- Expérience 3 (Données manquantes) : Ils ont simulé une situation où la nouvelle stratégie tentait d'aller dans des zones non couvertes par les anciennes données. Le Coverage-Stopped FORE a identifié avec succès la partie « sûre » de la stratégie et a donné une estimation conservatrice, tandis que les méthodes standards, qui tentaient de deviner les parties manquantes, ont lamentablement échoué.

Pourquoi cela importe

Ce papier est important car il lève un obstacle majeur dans l'apprentissage de l'IA à partir de données anciennes. Pendant des années, les scientifiques pensaient qu'il fallait une compréhension parfaite et complète du futur pour apprendre du passé. FORE démontre qu'on peut être « assez bon » et obtenir quand même une réponse fiable. C'est comme dire qu'on n'a pas besoin de connaître chaque rue d'une ville pour donner de bonnes directions ; il suffit d'avoir une carte qui couvre bien les itinéraires principaux.

Les auteurs précisent avec prudence que ce n'est pas une baguette magique qui résout tous les problèmes. Si la nouvelle stratégie se rend dans des endroits que les anciennes données n'ont jamais touchés, on ne peut toujours pas connaître la vérité totale. Mais pour les parties que l'on peut observer, FORE offre un moyen beaucoup plus stable et fiable de mesurer le succès. Il transforme un calcul fragile à enjeux élevés en un processus robuste, étape par étape, qui s'améliore avec l'expérience.

En bref, FORE est une nouvelle façon plus résiliente d'apprendre aux robots à tirer des leçons de l'histoire, prouvant qu'on n'a pas besoin d'une boule de cristal parfaite pour faire une bonne supposition sur l'avenir.

Résumé Technique : Évaluation de l'Équivalence de Ratio d'Occupation par Ajustement sans Complétude de Bellman

Énoncé du Problème

L'évaluation de politique hors ligne (OPE - Offline Policy Evaluation) vise à estimer la performance d'une politique cible $\pi$ en utilisant des données collectées à partir d'une politique de comportement. Un défi central consiste à corriger le décalage de distribution entre la distribution des données hors ligne $\nu$ et la mesure d'occupation d'état-action actualisée de la politique cible $d_{\pi,\gamma}$ .

Les méthodes existantes se divisent généralement en deux catégories :

Méthodes basées sur la valeur (ex: Fitted Q-Evaluation, FQE) : Elles estiment la fonction de valeur en régressant de manière itérative les cibles de Bellman sur une classe de fonctions. Cependant, les garanties théoriques pour FQE nécessitent généralement la complétude de Bellman (l'image de Bellman de toute fonction de la classe doit appartenir à la classe) ou la stabilité de l'opérateur de Bellman projeté. Sans cela, la composition de l'opérateur de Bellman et de la projection (sous la distribution hors ligne) peut ne pas être contractante, entraînant une instabilité.
Méthodes basées sur le ratio (ex: Primal-Dual, Minimax) : Elles estiment le ratio d'occupation $\omega_{\pi,\gamma} = d d_{\pi,\gamma} / d\nu$ en imposant des moments d'équilibre sur une classe de critiques. Ces approches nécessitent généralement la réalisabilité duale ou la complétude de Bellman adjointe (la classe de critiques doit être assez riche pour détecter les résidus générés par la classe de ratios), déplaçant ainsi la charge de l'approximation vers une paire de classes couplées.

L'article traite le cas où ni la complétude de la fonction de valeur ni la complétude duale ne sont satisfaites, mais où le ratio d'occupation cible lui-même est bien approximé par une classe d'hypothèses.

Méthodologie : Évaluation de l'Équivalence de Ratio d'Occupation par Ajustement (FORE)

Les auteurs proposent la méthode Fitted Occupancy-Ratio Evaluation (FORE), une méthode de point fixe par ajustement qui estime le ratio d'occupation actualisé via une récursion de Bellman adjointe.

Mécanisme Central

Identification de Bellman Adjointe : Le ratio d'occupation actualisé satisfait l'équation de point fixe $\omega_{\pi,\gamma} = B^\pi_\gamma \omega_{\pi,\gamma}$ , où $B^\pi_\gamma$ est l'opérateur de Bellman adjoint. Contrairement aux opérateurs de Bellman standards, $B^\pi_\gamma$ agit sur les densités.
Itération par Projection KL : Au lieu de résoudre un problème de point de selle minimax, FORE itère la carte de Bellman adjointe. À chaque étape $k$ , étant donné une estimation $\omega^{(k)}$ , la méthode calcule l'estimation suivante $\omega^{(k+1)}$ en projetant l'image exacte de Bellman $B^\pi_\gamma \omega^{(k)}$ sur une classe d'hypothèses $\mathcal{W}$ (de log-ratios normalisés) en utilisant la divergence de Kullback–Leibler (KL) :
$\omega^{(k+1)} = \Pi^{\text{KL}}_{\mathcal{W}} (B^\pi_\gamma \omega^{(k)})$
Objectif à Niveau Unique : Crucialement, la projection KL de l'image de Bellman adjointe peut être calculée via un objectif de ratio de densité à un seul niveau (Lemme 3.2). Cela évite d'avoir besoin d'une classe de critique distincte. L'objectif implique :
- Le moment de l'état initial $E_{d_0}[h(X)]$ .
- Le moment de transition d'un pas $E_\nu[\omega(X)h(X^+)]$ .
- Un terme de normalisation de la partition logarithmique.
  Cela permet une implémentation utilisant des apprenants supervisés standards (ex: arbres boostés par gradient, réseaux de neurones).

Fondement Théorique

La stabilité de FORE repose sur la géométrie de la divergence KL :

Contraction KL : L'opérateur de Bellman adjoint non projeté est une contraction en entropie relative (divergence KL) avec un facteur $\gamma$ (Lemme 3.1).
Projection Compatible : Parce que la projection est effectuée dans la même géométrie KL, l'opérateur projeté hérite de cette propriété de contraction.
Condition d'Approximation : La condition centrale est simplement la réalisabilité (ou l'approximation) du ratio d'occupation actualisé cible par la classe d'hypothèses. La méthode ne nécessite pas que la classe soit fermée sous l'opérateur de Bellman adjoint (c'est-à-dire qu'aucune complétude de Bellman adjointe n'est requise).

Gestion de la Couverture Limitée

Lorsque la politique cible visite des paires état-action non supportées par les données hors ligne (violant l'absolue continuité), le ratio complet n'est pas identifiable. Les auteurs introduisent la méthode Coverage-Stopped FORE :

Elle cible l'occupation actualisée accumulée avant la première paire état-action non couverte.
Elle utilise un classificateur de couverture appris pour identifier et écarter la composante singulière de la mise à jour de Bellman.
Elle utilise le découpage (clipping) pour régulariser l'estimation dans les régions faiblement couvertes.
L'estimation de valeur résultante sert de borne inférieure conservatrice sur la véritable valeur de la politique cible pour les récompenses non négatives.

Contributions Clés

Formulation Algorithmique : Caractérisation du ratio d'occupation actualisé comme l'unique point fixe d'une récursion de Bellman adjointe et introduction de FORE, qui l'estime via des objectifs répétés de ratio de densité KL à un seul niveau.
Théorie de la Population : Développement d'une théorie de l'approximation basée directement sur la réalisabilité du ratio d'occupation. L'opérateur de Bellman adjoint projeté par la KL contracte en entropie relative vers le ratio réel, jusqu'à l'erreur d'approximation déterminée par la classe du log-ratio, sans nécessiter la complétude de Bellman adjointe.
Garanties en Échantillon Fini : Preuve de bornes de regret en échantillon fini pour la récursion ajustée empirique. L'erreur de KL généralisée se décompose en un terme d'initialisation à décroissance géométrique, un terme d'approximation de la population et un terme statistique régi par la complexité de Rademacher locale des classes de multiplicateur et de log-ratio induites.
Applications d'Évaluation de Politique :
- Repondération de Récompense : Estimation directe de la valeur en utilisant le ratio ajusté.
- Estimation Doubly Robust : Une borne d'erreur de forme produit combinant le ratio ajusté avec une fonction Q ajustée.
- FQE Pondéré par FORE : Utilisation du ratio ajusté comme poids de projection dans FQE pour stabiliser la récursion de Bellman sans les hypothèses de complétude de Bellman sur la classe de valeur.
Extension Coverage-Stopped : Une extension aux contextes de couverture limitée qui fournit des bornes inférieures conservatrices et diagnostique la couverture effective.

Résultats

Résultats Théoriques

Convergence : Sous la condition de réalisabilité du ratio d'occupation, la récursion de la population converge géométriquement en divergence KL.
Bornes d'Erreur : La borne d'erreur en échantillon fini passe par l'erreur d'approximation de la classe de ratio et la complexité statistique (rayon critique) de la classe d'hypothèses. Notamment, le terme d'erreur d'approximation évolue selon $\sqrt{\epsilon_{KL}/(1-\gamma)}$ , ce qui est plus favorable que l'échelle $(1-\gamma)^{-1}$ souvent observée dans les bornes de fonction de valeur sous complétude de Bellman approximative.
Stabilité : La méthode stabilise FQE lorsqu'elle est utilisée comme mécanisme de pondération, même si la classe de fonction de valeur n'est pas Bellman complète.

Expériences Numériques

L'article valide sa théorie à travers trois expériences :

MRP de type Baird (Fini) : Démontre qu'un FQE linéaire peut être instable (expansif) sous la distribution des données hors ligne, tandis que FORE reste stable et converge vers le vrai ratio. Un FQE repondéré par FORE stabilise également l'estimation de la valeur.
Évaluation de Politique Gaussienne Linéaire : Dans un cadre continu où la classe de valeur n'est pas Bellman complète, le FQE linéaire échoue (multiplicateur > 1). FORE converge rapidement (multiplicateur $\approx 0,086$ ), et le FQE repondéré par FORE restaure la contraction. FORE atteint une erreur de ratio de densité plus faible et une RMSE de valeur compétitive par rapport aux méthodes minimax (MWL, DualDICE).
Coverage-Stopped FORE : Sous une couverture de données insuffisante, le FORE standard et le découpage a posteriori échouent à cibler la mesure de probabilité sous-jacente correcte. Le Coverage-Stopped FORE récupère avec succès le ratio d'occupation "coverage-stopped" et fournit des bornes inférieures précises sur la valeur, surpassant les bases tant en erreur de ratio qu'en erreur de valeur.

Signification et Revendications

L'article affirme identifier la réalisabilité du ratio d'occupation actualisé comme une condition suffisante pour l'évaluation de politique hors ligne, supprimant le besoin de :

La complétude de Bellman d'une classe de valeur.
La complétude de Bellman adjointe d'une classe de ratio.
La complétude duale d'une classe de critique.

La signification réside dans le déplacement de la charge d'approximation des conditions de clôture complexes (qui sont souvent restrictives et difficiles à vérifier) vers la représentabilité directe du décalage de distribution. En exploitant la géométrie KL, FORE atteint une stabilité et des garanties de convergence qui sont structurellement distinctes et souvent plus faibles que les hypothèses requises par FQE ou les méthodes de ratio minimax. Les auteurs positionnent cela comme une alternative fondamentale aux approches basées sur la valeur et aux approches de ratio minimax, particulièrement dans les contextes où le ratio d'occupation est bien approximé mais où les classes de fonctions de valeur ou de critiques manquent des propriétés de complétude nécessaires.

L'article reste modeste quant aux limites : la récupération du ratio complet nécessite toujours une couverture (absolue continuité), et dans les environnements de haute dimension ou quasi-déterministes, l'estimation du ratio peut être aussi difficile que l'estimation de la fonction de valeur. L'extension "coverage-stopped" répond à cela en changeant l'estimand pour une borne inférieure conservatrice plutôt qu'une extrapolation dans les régions non supportées.