Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

Résumé Technique : Complexité Temporelle Fortement Polynomiale de l'Itération de Politique pour les RMDP en $L_\infty$

Énoncé du Problème
Le papier traite un problème ouvert fondamental dans la prise de décision séquentielle sous incertitude : l'existence d'algorithmes à temps fortement polynomial pour les Processus de Décision Markoviens Robustes (RMDP) avec des ensembles d'incertitude $L_\infty$ et un facteur de remise fixé. Alors que les MDP classiques admettent des algorithmes en temps fortement polynomial pour le calcul exact de la valeur (Ye, 2011), et que des algorithmes en temps polynomial existent pour les RMDP via la programmation linéaire, la question de savoir si les RMDP admettent des algorithmes fortement polynomiaux (où le nombre d'opérations arithmétiques est indépendant de la longueur en bits des coefficients d'entrée) restait non résolue. Plus précisément, les tentatives précédentes de réduction des RMDP $(s, a)$-rectangulaires vers des jeux stochastiques à tours alternés ont échoué à produire des réductions en temps polynomial en raison du nombre exponentiel d'actions requis pour représenter les polytopes d'incertitude $L_\infty$.

Modèle et Définitions
Les auteurs se concentrent sur les RMDP $(s, a)$-rectangulaires avec des ensembles d'incertitude $L_\infty$.

• Rectangularité $(s, a)$ : L'environnement sélectionne les probabilités de transition indépendamment pour chaque paire état-action, préservant une structure de programmation dynamique.
• Incertitude $L_\infty$ : Pour chaque paire état-action $(s, a)$, le vecteur de transition réel se situe dans une boule $L_\infty$ de rayon $\delta_{s,a}$ autour d'une estimation nominale $\hat{P}_{s,a}$.
• Objectif : L'agent cherche une politique $\sigma$ qui minimise le coût attendu dans le pire des cas contre une politique d'environnement adverse $\tau$.
• Temps Fortement Polynomial : Un algorithme est fortement polynomial si le nombre d'opérations arithmétiques est borné par un polynôme du nombre de variables et de contraintes, et que la taille des nombres pendant le calcul est polynomiale de la taille de l'entrée, indépendamment des valeurs numériques des coefficients.

Méthodologie
Le papier analyse l'algorithme d'Itération de Politique Robuste (PI), qui alterne entre l'Évaluation de Politique et l'Amélioration de Politique.

1. Chaînes Markoviens Robustes (RMC) : Les auteurs analysent d'abord le cas plus simple où l'agent possède une seule action par état (RMC-PI).

   • Amélioration de Politique : Au lieu de résoudre un programme linéaire (LP) qui dépend de la précision binaire, les auteurs utilisent un Algorithme d'Homotopie (Behzadian et al., 2021) pour calculer la réponse optimale de l'environnement. Cet algorithme s'exécute en $O(n \log n)$ et produit des politiques possédant une propriété structurelle spécifique : les probabilités de transition sont ajustées en déplaçant la masse de états "donneurs" vers des états "receveurs" jusqu'à ce que les frontières (0, 1 ou le rayon d'incertitude) soient atteintes.
   • Fonction de Potentiel : Une nouvelle fonction de potentiel $f_\tau(s, s', s'')$ est introduite pour suivre le transfert de masse de probabilité permis par l'algorithme d'homotopie. Cette fonction mesure l'amélioration potentielle de la valeur en déplaçant la masse d'un état ayant une valeur plus faible vers un état ayant une valeur plus élevée.
   • Bornes Combinatoires : Les auteurs prouvent que la "discrépance" entre les probabilités de transition de la politique actuelle et les optimales diminue géométriquement. Crucialement, ils établissent un lemme combinatoire (Lemme 8) concernant le nombre de bits les plus significatifs (MSB) distincts dans les sommes partielles signées de nombres réels. Ce lemme, dérivé d'un théorème plus général (Théorème 20/21), borne le nombre de MSB possibles par $O(|X| \log |X|)$.
   • Argument de Convergence : En combinant la contraction géométrique de l'erreur de valeur (Lemme 2) avec le nombre fini de MSB possibles pour la discrépance (Lemme 8), les auteurs montrent que l'algorithme ne peut pas effectuer des mises à jour arbitrairement petites indéfiniment. Le MSB de la discrépance doit changer un nombre polynomial de fois.

2. MDP Robustes (RMDP) : L'analyse est étendue au cas général des RMDP (RMDP-PI).

   • L'algorithme résout de manière itérative le sous-problème RMC pour la politique actuelle de l'agent afin de trouver la pire réponse de l'environnement, puis met à jour la politique de l'agent pour minimiser le coût résultant.
   • Une fonction de potentiel similaire est définie pour les actions, suivant le coût de la déviation par rapport à l'action optimale de l'agent.
   • La même logique s'applique : l'action ayant le potentiel maximal ne peut persister qu'un nombre logarithmique d'itérations avant que la contraction de l'erreur de valeur ne force un changement.

Contributions Clés et Résultats

• RMC-PI en Temps Fortement Polynomial : Les auteurs prouvent que l'Itération de Politique Robuste pour les RMC avec $n$ états et un facteur de remise constant $\gamma$ se termine en $O(n^4 \log n \cdot \frac{\log((1-\gamma)/n^2)}{\log \gamma})$ itérations. Puisque chaque itération implique des opérations en temps polynomial (inversion de matrice et étapes d'homotopie), le temps d'exécution total est fortement polynomial.
• RMDP-PI en Temps Fortement Polynomial : Le résultat est généralisé aux RMDP avec $n$ états et $m$ actions. L'algorithme se termine en $O(n \cdot m \cdot \frac{\log(1-\gamma)}{\log \gamma})$ itérations, établissant que le RMDP-PI est également fortement polynomial.
• Lemme Combinatoire : Le papier introduit le Lemme 8, un résultat combinatoire novateur bornant le nombre de MSB distincts dans les sommes partielles signées, qui est central à la preuve de complexité. Les auteurs notent qu'une version plus forte de ce théorème a été dérivée indépendamment par un agent de recherche IA (Aletheia), soulignant une contribution de l'IA à la mathématique.

Signification et Revendications
Le papier affirme résoudre un problème ouvert majeur dans la théorie de l'optimisation robuste. En démontrant qu'un algorithme d'itération de politique robuste s'exécute en temps fortement polynomial pour les RMDP $(s, a)$-rectangulaires en $L_\infty$, les auteurs généralisent le résultat séminal de Ye (2011) pour les MDP classiques à l'environnement robuste. Ce résultat est significatif car :

1. Il fournit une garantie théorique pour calculer des valeurs exactes (plutôt que des approximations) pour les RMDP sans dépendance à la longueur en bits des paramètres d'entrée.
2. Il surmonte les limites des techniques de réduction précédentes qui ont échoué en raison d'une explosion exponentielle du nombre d'actions.
3. Il établit que l'opérateur de Bellman robuste, malgré l'ensemble d'incertitude infini, peut être navigué efficacement en utilisant les propriétés combinatoires de l'algorithme d'homotopie.

Les auteurs concluent que bien que les fondations théoriques soient désormais établies, les travaux futurs pourraient explorer des études empiriques sur des ensembles d'incertitude basés sur les données et déterminer si ces arguments basés sur le potentiel peuvent mener à des variantes pratiques ou des critères d'arrêt améliorés. Ils notent également que la question des bornes polynomiales pour les variantes standards de l'itération de politique des MDP reste ouverte.