Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Résumé Technique : Processus de Décision Markoviens à Récompense Moyenne Robustes

Formulation du Problème
Ce travail étudie la complexité statistique de l'apprentissage d'une politique $\epsilon$-optimale pour les Processus de Décision Markoviens à Récompense Moyenne (AMDP) distributionnellement robustes dans un cadre de modèle génératif. L'agent opère au sein d'un environnement nominal défini par un noyau de transition $P^0$ et une fonction de récompense $r$. Cependant, la dynamique réelle de l'environnement est incertaine et peut se situer dans un ensemble d'incertitude prescrit $\mathcal{P}$ centré sur $P^0$. Plus précisément, l'article considère des ensembles d'incertitude de type variation totale (TV) rectangulaires $(s, a)$ avec un rayon au plus de $\sigma$.

L'objectif est de maximiser la récompense moyenne robuste, définie comme la pire récompense moyenne à long terme sur tous les noyaux de transition dans $\mathcal{P}$ :
$$\rho^{\pi, \sigma} := \inf_{P \in \mathcal{P}} \lim_{T \to \infty} \mathbb{E}^\pi_P \left[ \frac{1}{T} \sum_{t=0}^{T-1} r(s_t, a_t) \right]$$
Le but de l'apprentissage est de calculer une politique $\hat{\pi}$ en utilisant $N$ échantillons par paire état-action telle que $\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$, où $\rho^{\star, \sigma}$ est la récompense moyenne robuste optimale.

Paramètres Clés et Hypothèses Structurelles
L'analyse repose sur deux paramètres structurels critiques :

1. Étendue du Biais Optimal Nominal ($H_0$) : l'étendue de la fonction de biais satisfaisant l'équation de Bellman optimalité nominale.
2. Étendue du Biais Optimal Robuste ($H_\sigma$) : l'étendue de la fonction de biais satisfaisant l'équation de Bellman optimalité robuste.

L'article établit que $H_0$ et $H_\sigma$ sont généralement indépendants ; l'un ne contrôle pas l'autre. Une échelle de perturbation cruciale est identifiée comme étant $\sigma H_0$, qui sépare le problème d'apprentissage en deux régimes distincts :

• Régime de Haute Tolérance ($\epsilon \gtrsim \sigma H_0$) : la perturbation causée par l'incertitude est faible par rapport à la précision cible.
• Régime de Basse Tolérance ($\epsilon \lesssim \sigma H_0$) : la perturbation est significative, et l'optimisation nominale seule est insuffisante pour garantir l'optimalité robuste.

Méthodologie : Procédures de Réduction par Substitution (Plug-in)
La contribution méthodologique centrale est un cadre de réduction qui transforme le problème difficile de la récompense moyenne robuste en un problème de MDP à remise (discounted) robuste plus traitable. Les auteurs proposent deux algorithmes basés sur cette réduction :

1. Procédure Informée par l'Étendue (Algorithme 1) : suppose que $H_0$ et $H_\sigma$ sont connus. Elle sélectionne de manière adaptative entre une réduction nominale (résolution d'un MDP à remise standard avec le noyau empirique) et une réduction robuste (résolution d'un MDP à remise sur l'ensemble d'incertitude). Le choix dépend de l'ordre de $H_0$ et $H_\sigma$ et du régime de tolérance. Le facteur de remise $\gamma$ est calibré en fonction du paramètre d'étendue pertinent (par exemple, $\gamma = 1 - \epsilon/(3H_\sigma)$).
2. Procédure Agnostique à l'Étendue (Algorithme 2) : opère sans connaissance de $H_0$ ou $H_\sigma$. Elle construit un ensemble de politiques candidates issues de rédactions tant nominales que robustes à travers une grille dyadique de facteurs de remise. Elle sélectionne ensuite la meilleure politique en utilisant une borne inférieure de confiance (LCB) sur la récompense moyenne robuste, dérivée d'un « certificat d'ancrage » calculé à partir d'un lot de données séparé. Cela permet à l'algorithme de choisir de manière adaptative la bonne réduction et le bon facteur de remise.

L'analyse s'appuie sur trois raffinements techniques clés pour obtenir des bornes serrées :

• Comparer le problème à remise robuste avec une solution de référence nominale (ancre) pour resserrer les termes de variance.
• Contrôler les fonctions de valeur à remise via leurs étendues ($H_\sigma$) plutôt que par l'horizon effectif.
• Utiliser des bornes de concentration localisées régies par ces étendues.

Résultats Principaux : Complexité d'Échantillonnage Minimax
L'article fournit des bornes supérieures et inférieures correspondantes pour la complexité d'échantillonnage minimax $N_{SA}$ (échantillons par paire état-action), à un facteur logarithmique près. La complexité est caractérisée par un résumé en quatre régimes basé sur l'ordre de $H_0$ et $H_\sigma$ ainsi que sur le régime de tolérance :

$$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{si } \epsilon \gtrsim \sigma H_0 \quad (\text{Haute Tolérance}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{si } \epsilon \lesssim \sigma H_0 \quad (\text{Basse Tolérance}) \end{cases}$$

• Régime de Haute Tolérance : la complexité est dominée par le terme d'étendue linéaire $\min\{H_0, H_\sigma\}$. Si $H_\sigma \leq H_0$, la réduction robuste produit une borne plus serrée que la nominale.
• Régime de Basse Tolérance : un terme supplémentaire « spécifique à la robustesse » $\sigma H_\sigma^2$ apparaît, représentant le coût de la gestion de l'incertitude de distribution lorsque la précision requise est élevée.
• Borne Inférieure : les auteurs prouvent une borne inférieure minimax qui correspond à la borne supérieure, établissant que le terme $\sigma H_\sigma^2$ est fondamental et ne peut être évité dans le régime de basse tolérance. Il s'agit de la première borne inférieure caractérisant les limites statistiques des AMDP distributionnellement robustes.

Signification et Revendications
L'article affirme fournir la première caractérisation minimax-optimale de la complexité d'échantillonnage pour les AMDP distributionnellement robustes. Les principales contributions sont :

• Résolution de l'écart de complexité d'échantillonnage : les précédentes bornes supérieures robustes (ex: Roch et al., 2025, 2026) dépendaient de façon quadratique des paramètres d'étendue robustes ($H_{Roch}^2$ ou $H_{RHI}^2$) sans distinguer la haute et la basse tolérance. Ce travail affine la dépendance vers $\min\{H_0, H_\sigma\}$ dans le régime de haute tolérance et identifie le coût précis de $\sigma H_\sigma^2$ dans le régime de basse tolérance.
• Algorithmes Adaptatifs : la procédure agnostique à l'étendue (Algorithme 2) atteint ces taux optimaux sans connaissance préalable des paramètres d'étendue, s'adaptant automatiquement au régime et aux magnitudes relatives de $H_0$ et $H_\sigma$.
• Généralité : les résultats tiennent même si seule l'étendue robuste $H_\sigma$ est supposée bornée, produisant une complexité de $\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$.

Les résultats expérimentaux sur des simulations contrôlées vérifient la dépendance linéaire prédite sur $\min\{H_0, H_\sigma\}$ et la dépendance quadratique sur $\sigma H_\sigma^2$ dans le régime de basse tolérance, ainsi que l'adaptativité de l'algorithme agnostique à l'étendue. Les auteurs notent que des travaux futurs pourraient explorer des structures d'incertitude couplées et des contextes en ligne (basés sur le regret), mais le présent travail se concentre strictement sur le cadre du modèle génératif.