Multi-Environment POMDPs with Finite-Horizon Objectives

Résumé technique : MEPOMDP à horizon fini avec objectifs

Énoncé du problème
Ce travail aborde le problème du calcul des valeurs et des politiques optimales dans les Processus de Décision Markoviens Partiellement Observables Multi-Environnements (MEPOMDP) avec des objectifs à horizon fini. Dans un Processus de Décision Markovien Partiellement Observable (POMDP) standard, un agent interagit avec un environnement stochastique en ne recevant qu'une information partielle sur l'état. Un MEPOMDP étend cela en supposant que l'état initial est inconnu et choisi de manière adversariale parmi un ensemble de $n$ états initiaux possibles $\{s_1, \dots, s_n\}$. L'agent doit calculer une politique unique qui maximise le gain espéré minimal parmi tous les environnements initiaux possibles. L'objectif est de maximiser la somme des récompenses sur un horizon fini $k$.

L'article se concentre sur deux problèmes de calcul :

1. Le problème de la valeur : Calculer la valeur optimale $v = \sup_{\sigma} \min_{i \in [n]} E^k_{s_i}(\sigma)$.
2. Le problème du seuil : Décider si $v \ge \lambda$ pour un seuil rationnel $\lambda$ donné.

Une nuance théorique critique identifiée est que, contrairement aux POMDP standards où des politiques déterministes suffisent pour l'optimalité, les MEPOMDP nécessitent généralement des politiques randomisées pour atteindre la valeur optimale, car les stratégies déterministes peuvent échouer à satisfaire la contrainte de l'état initial dans le pire des cas.

Méthodologie et algorithmes
Les auteurs développent à la fois des bornes de complexité théoriques et des algorithmes pratiques pour résoudre ces problèmes.

• Analyse de la complexité : L'article établit que le problème du seuil et sa version approchée sont PSPACE-complets. La borne inférieure est héritée de la difficulté PSPACE connue des POMDP standards (où $n=1$). La borne supérieure est prouvée via un algorithme non déterministe qui exploite le théorème de Carathéodory. Ce théorème implique que si une politique existe permettant d'atteindre une certaine valeur parmi $n$ environnements, il existe alors un « mélange » d'au plus $n$ politiques déterministes qui atteint la même garantie. Cela permet de réduire l'espace de recherche aux combinaisons d'un nombre limité de stratégies déterministes.

• Algorithme déterministe économe en espace (Algorithme 2) : Pour éviter les exigences exponentielles en espace du déterminisation standard (par exemple via le théorème de Savitch), les auteurs présentent un algorithme déterministe opérant dans un espace polynomial. Au lieu de deviner des politiques entières, l'algorithme énumère les valeurs de gains espérés multi-dimensionnels possibles et vérifie leur réalisabilité de manière récursive. Il construit des sommes partielles de l'équation de mise à jour de Bellman, en vérifiant si une valeur cible peut être décomposée en sous-stratégies valides. Bien que théoriquement optimal en espace ($O(|S| \cdot |O| \cdot n \cdot k \cdot \pi(N))$), les auteurs notent que cette approche est computationnellement irréalisable pour la plupart des instances pratiques en raison de boucles imbriquées.

• Algorithme pratique économe en temps (Algorithme 3) : Pour l'évaluation empirique, les auteurs proposent un algorithme ascendant qui calcule l'ensemble des gains espérés multi-dimensionnels réalisables pour des horizons croissants. Cette méthode maintient un ensemble de vecteurs de gains non dominés (la « frontière »). À chaque étape, elle élimine les vecteurs qui sont dominés de manière convexe par d'autres, car ceux-ci correspondent à des familles de politiques qui n'ont pas besoin d'être explorées davantage. Bien que cet algorithme puisse utiliser un espace exponentiel dans le pire des cas, il est conçu pour être évolutif en pratique.

Contributions clés

1. Classification de la complexité : L'article prouve que le calcul des valeurs dans les MEPOMDP à horizon fini est PSPACE-complet, correspondant à la complexité des POMDP standards malgré l'ajout de la contrainte d'état initial adversarial.
2. Insight théorique : Il démontre que les politiques optimales dans les MEPOMDP peuvent être représentées comme des mélanges d'au plus $n$ politiques déterministes, où $n$ est le nombre d'environnements initiaux.
3. Avancées algorithmiques :
   • Un algorithme déterministe à espace polynomial (Algorithme 2) fournissant une borne supérieure théorique sur la complexité en espace.
   • Un algorithme pratique économe en temps (Algorithme 3) utilisant l'élagage des vecteurs de gains dominés.
4. Validation empirique : L'algorithme pratique est évalué par rapport au seul algorithme exact précédemment connu (de Bovy et al. [1]) sur trois suites de benchmarks : Rock Sample, Navigation de robot et Identification (Ami ou Ennemi).

Résultats
Les résultats expérimentaux indiquent que l'algorithme pratique proposé (Algorithme 3) surpasse significativement l'outil de l'état de l'art de [1].

• Performance : La nouvelle méthode résout des instances allant jusqu'à 574 états et des horizons jusqu'à $k=7$ dans des délais raisonnables, tandis que l'outil de référence dépasse fréquemment le délai limite (3600 s) sur des instances beaucoup plus petites.
• Évolutivité : Le temps de calcul évolue fortement avec l'horizon $k$, qui est identifié comme le principal goulot d'étranglement pour l'évolutivité. Le nombre d'états et d'environnements initiaux a un effet moins dominant sur le temps d'exécution par rapport à l'horizon.
• Comparaison : Dans les benchmarks Rock Sample, la méthode proposée a résolu des instances où la méthode de référence a dépassé le délai, atteignant souvent des accélérations de plusieurs ordres de grandeur (par exemple, résolution d'une instance de 574 états en ~784 secondes contre un dépassement de délai pour la méthode de référence).

Signification et limites
L'article revendique une importance en fournissant les premières bornes de complexité serrées pour les MEPOMDP et en offrant un algorithme pratique qui améliore substantiellement les outils existants. Les auteurs reconnaissent un compromis standard entre performance théorique et pratique : l'algorithme économe en espace (Algorithme 2) est théoriquement solide mais pratiquement lent, tandis que l'algorithme économe en temps (Algorithme 3) est rapide en pratique mais ne garantit pas un espace polynomial dans le pire des cas.

Le travail est limité aux objectifs à horizon fini. Les auteurs notent que, bien que le problème exact pour les objectifs de somme actualisée soit indécidable pour les POMDP, leur algorithme pourrait potentiellement être adapté pour des objectifs actualisés approximatifs en les réduisant à des problèmes à horizon fini, bien que cela reste un travail futur. L'article ne propose pas de nouvelles applications au-delà des benchmarks standards utilisés pour l'évaluation.