Résumé Technique : Bootstrap Basé sur un Modèle pour les Chaînes de Markov Contrôlées

Énoncé du Problème

L'article aborde le défi de l'inférence statistique pour les Chaînes de Markov Contrôlées (CMC) finies dans des contextes où la politique de comportement générant les données peut être non stationnaire ou dépendante de l'historique. Ce scénario est prévalent dans l'apprentissage par renforcement (RL) hors ligne, où les données sont collectées par une politique inconnue $\pi_b$ qui ne satisfait pas nécessairement les hypothèses de stationnarité ou de markovianité.

Les méthodes de bootstrap existantes pour les chaînes de Markov reposent souvent sur la stationnarité ou des conditions de mélange spécifiques qui ne s'appliquent pas aux CMC générales avec des contrôles dépendants de l'historique. De plus, les intervalles de confiance (IC) standards par substitution basés sur les Théorèmes Limite Centraux (TLC) nécessitent une estimation de la covariance, ce qui peut dégrader les performances en échantillons finis. Les auteurs identifient deux problèmes ouverts :

1. Peut-on développer un bootstrap basé sur un modèle pour les CMC finies sans exiger la stationnarité ou la markovianité de la politique de contrôle ?
2. Peut-on établir la consistance distributionnelle d'un tel estimateur de bootstrap et l'étendre à des tâches RL en aval comme l'Évaluation Hors Politique (OPE) et la Récupération de Politique Optimale (OPR) ?

Méthodologie

Modèle et Configuration des Données

Les auteurs considèrent une CMC finie $\{(X_i, A_i)\}_{i \ge 0}$ avec un espace d'états $\mathcal{S}$ et un espace d'actions $\mathcal{A}$. Le noyau de transition est $M(a)_{s,t} = P(X_{i+1}=t | X_i=s, A_i=a)$. L'ensemble de données hors ligne observé $\mathcal{D}_n$ consiste en $K$ épisodes de longueur fixe $T$ (où $n=KT$), générés par une politique de comportement inconnue $\pi_b$. La politique $\pi_b$ est autorisée à être non stationnaire et dépendante de l'historique.

À partir de $\mathcal{D}_n$, les auteurs calculent :

• Estimateur empirique de transition basé sur les comptes : $\hat{M}(a)_{s,t} = N(a)_{s,t} / N(a)_s$.
• Politique de comportement empirique : $\hat{\pi}_b(a|s) = N(a)_s / N_s$.

Procédure de Bootstrap Basé sur un Modèle

La méthode proposée construit une CMC de bootstrap $\{(X^*_i, A^*_i)\}_{i \ge 0}$ en utilisant le noyau de transition empirique $\hat{M}$ et la politique de comportement empirique $\hat{\pi}_b$.

1. Initialisation : Pour chaque réplique de bootstrap $j$, le processus commence à l'état initial observé de l'épisode original, $X^{*(k,j)}_0 = X^{(k)}_0$.
2. Simulation : Les transitions sont générées séquentiellement en échantillonnant des actions $A^{*(k,j)}_i \sim \hat{\pi}_b(\cdot | X^{*(k,j)}_i)$ et des états suivants $X^{*(k,j)}_{i+1} \sim \hat{M}(A^{*(k,j)}_i)_{X^{*(k,j)}_i, \cdot}$.
3. Estimation : À partir de l'ensemble de données simulé $\mathcal{D}^*_n$, un estimateur de transition de bootstrap $\hat{M}^*$ est calculé.
4. Répétition : Ce processus est répété $B$ fois pour obtenir les répliques de bootstrap $\hat{M}^{*(1)}, \dots, \hat{M}^{*(B)}$.

Applications en Aval

Le bootstrap est appliqué à deux cibles en aval :

• Évaluation Hors Politique (OPE) : Estimation des fonctions de valeur $V_\pi$ et des fonctions Q $Q_\pi$ pour une politique cible fixe $\pi$ en résolvant les équations de Bellman avec $\hat{M}$ et $\hat{M}^*$.
• Récupération de Politique Optimale (OPR) : Estimation des fonctions de valeur optimales $V_\star$ et $Q_\star$ en résolvant les équations de Bellman optimales avec $\hat{M}$ et $\hat{M}^*$.

Les intervalles de confiance sont construits en utilisant les quantiles empiriques des répliques de bootstrap (IC de percentile) ou via des méthodes pivots.

Contributions Théoriques Clés

1. Consistance Distributionnelle du Bootstrap

L'article établit les premiers résultats de consistance distributionnelle pour les bootstraps basés sur un modèle dans les CMC finies avec des politiques potentiellement non stationnaires ou dépendantes de l'historique.

• Régime Chaîne Unique ($K=1, T \to \infty$) : Le Théorème 1 prouve que, conditionnellement aux données $\mathcal{D}_n$, $\sqrt{n} \text{vec}(\hat{M}^* - \hat{M})$ converge en distribution vers une limite gaussienne $N(0, \bar{\Lambda})$, correspondant à la distribution asymptotique de l'estimateur original $\sqrt{n} \text{vec}(\hat{M} - M)$.
• Régime Épisodes ($T$ fixe, $K \to \infty$) : La Proposition 1 étend ce résultat au cadre épisodique en intégrant les épisodes dans une seule chaîne via des pseudo-transitions. Elle confirme que le bootstrap reste consistant même lorsque les épisodes sont séparés par des réinitialisations.

Outils Techniques :

• Une nouvelle Loi des Grands Nombres (LLN) de Bootstrap pour les comptes de visite ($N^*_s/n \to p_s$ p.s.).
• Une nouvelle application du Théorème Limite Central (TLC) des Martingales pour les incréments de transition de bootstrap, utilisant des conditions de mélange faible (Hypothèses 1–3) pour gérer la structure de dépendance.

2. Validité pour l'OPE et l'OPR

La Proposition 2 étend la consistance distributionnelle aux estimateurs de fonctions de valeur et Q en utilisant la Méthode Delta.

• Les auteurs vérifient la différentiabilité de Hadamard des opérateurs de Bellman par rapport à la matrice bloc de transition.
• Pour l'OPE, les répliques de bootstrap de $V_\pi$ et $Q_\pi$ convergent vers les mêmes limites gaussiennes que les estimateurs originaux.
• Pour l'OPR, sous une condition de non-dégénérescence (écart strictement positif entre les actions optimales et sous-optimales), les répliques de bootstrap de $V_\star$ et $Q_\star$ atteignent également la consistance distributionnelle.

Résultats Expérimentaux

Les auteurs évaluent les performances en échantillons finis sur le problème RiverSwim ($S=6, A=2$), un benchmark connu pour son exploration difficile due à des fréquences de visite déséquilibrées et des politiques optimales presque dégénérées.

• Configuration : Des comparaisons ont été faites contre le bootstrap épisodique (Hao et al., 2021) et les IC par substitution TLC (Zhu et al., 2024 ; Su et al., 2026) sur diverses tailles d'échantillons ($n$) et longueurs d'épisodes ($T$).
• Constats :
  • Les IC de percentile de bootstrap basé sur un modèle proposés surpassent considérablement les lignes de base, atteignant une couverture quasi-nominale (par exemple, 0,48–0,54 pour 50 %, 0,87–0,94 pour 90 %, 0,92–0,97 pour 95 %) dans des régimes bien échantillonnés ($n \ge 500$).
  • Les lignes de base (bootstrap épisodique et substitution TLC) présentent une sous-coverage systématique, en particulier pour les petites tailles d'échantillons et les courtes longueurs d'épisodes.
  • Le bootstrap épisodique échoue complètement à $n=50$ lorsque $T \ge 50$ (s'effondrant vers une couverture nulle) car un seul épisode élimine la variation du bootstrap.
  • Les performances sont les plus faibles pour les paires état-action rarement visitées (près de l'état 6) et les horizons courts ($T=10$), ce qui est cohérent avec les contraintes théoriques de normalité asymptotique et de non-dégénérescence.

Importance et Limites

Importance :
L'article fournit une fondation théorique rigoureuse pour l'utilisation de bootstraps basés sur un modèle en RL hors ligne, abordant spécifiquement le vide où les politiques de comportement sont non stationnaires ou dépendantes de l'historique. Il démontre que de tels bootstraps produisent des intervalles de confiance asymptotiquement valides pour les noyaux de transition et les cibles RL en aval sans nécessiter d'estimation explicite de la covariance.

Limites et Perspectives (telles que déclarées par les auteurs) :

• Fonction de Récompense : L'analyse suppose une fonction de récompense connue. Bien que les auteurs notent que la validité tient probablement si l'estimation de la récompense converge, les effets en échantillons finis de l'erreur d'estimation de la récompense ne sont pas analysés.
• Espace État-Action : Les résultats actuels sont limités aux espaces état-action finis. L'extension à l'approximation de fonction ou aux espaces continus est laissée pour un travail futur.
• Régimes Asymptotiques : L'analyse épisodique suppose que $T$ est fixe et $K \to \infty$. La consistance du bootstrap dans le régime où $K$ est fixe ($K>1$) et $T \to \infty$ reste une question ouverte.
• Politiques Non Stationnaires : Bien que la théorie prenne en charge les politiques non stationnaires, les expériences numériques ont principalement utilisé des politiques de comportement stationnaires ; de nouvelles expériences avec des politiques non stationnaires sont suggérées.