Pourquoi une seule stratégie ne suffit pas : des portefeuilles de politiques adaptatifs pour les MDP robustes
Les processus de décision markoviens (MDP) classiques supposent que la dynamique de l'environnement est connue avec précision. En pratique, ce n'est presque jamais le cas : nous ne pouvons qu'esquisser un ensemble de scénarios plausibles. Les MDP robustes abordent cela de manière radicale — ils cherchent une politique unique qui fonctionnera suffisamment bien dans le pire des transitions possibles. Mais cette approche a un coût caché : elle est calibrée pour le pire cas et s'avère donc souvent excessivement conservatrice.
Cela est particulièrement visible dans les situations où l'incertitude diminue avec le temps. L'environnement se déploie devant l'agent, et une partie de sa dynamique devient observable et partiellement identifiable. La politique optimale, calculée avant le déploiement, n'utilise pas cette nouvelle information. En substance, nous continuons à jouer le pire cas même là où nous savons déjà qu'il ne s'est pas réalisé. Des chercheurs de l'Université de Twente et d'Anvers — Kasper Engelen, Sebastian Junges, Guillermo A. Pérez et Marnix Suilen — dans leur travail « Adaptive Policy Portfolios for Robust Markov Decision Processes » (arXiv:2608.17929, cs.AI/cs.LO) proposent une approche plus flexible.
Portefeuilles adaptatifs : un ensemble de politiques au lieu d'une seule
Au lieu d'une politique robuste unique, les auteurs considèrent un portefeuille de politiques — un ensemble fini de politiques randomisées sans mémoire, synthétisées à l'avance, hors ligne. En complément, un sélecteur en ligne léger est utilisé pour choisir la politique la plus appropriée du portefeuille pendant le fonctionnement. Cela rappelle un ensemble de modèles en apprentissage automatique, mais avec une formulation théorique claire.
La métrique clé de qualité d'un tel portefeuille devient le regret robuste (robust regret). Pour chaque environnement concret de l'ensemble des scénarios plausibles, il mesure à quel point la politique choisie par le sélecteur en ligne est inférieure à la politique idéale que nous aurions construite si nous avions connu cet environnement à l'avance. En d'autres termes, un portefeuille est considéré comme bon si son meilleur membre est suffisamment proche de l'optimum pour tout environnement. Cette perspective déplace l'accent des garanties dans le pire cas vers le coût de l'adaptation.
Des idées similaires ont été développées précédemment par Ghavamzadeh et al. (2016), mais avec un accent sur les méthodes approximatives et les relaxations pour l'amélioration sûre des politiques. Le nouveau travail fait progresser considérablement les fondements théoriques de ce domaine.
Complexité de la certification et de la synthèse
Le portefeuille n'est pas simplement une heuristique d'ingénierie. Les auteurs fournissent une analyse théorique de la complexité rigoureuse des problèmes qui se posent lors du travail avec les portefeuilles.
Le premier problème est la certification d'un portefeuille donné : peut-on garantir que pour tous les environnements plausibles, il existe une politique avec un regret acceptable ? Il s'avère que ce problème est ∀R-complet déjà pour les portefeuilles déterministes dans les RMDP acycliques (s,a)-rectangulaires. Cela signifie que vérifier la qualité même d'un petit ensemble de politiques est une tâche computationnellement lourde, comparable en complexité à la résolution de systèmes d'inégalités réelles.
Encore plus difficile est le problème de la synthèse d'un portefeuille de taille bornée (unary-bounded). Pour les polytopes rationnels généraux, il s'avère ∃∀R-complet — même avec un facteur d'actualisation fixe et une dynamique acyclique. Une telle complexité indique qu'aucun algorithme combinatoire simple n'existe ici : le problème combine à la fois la recherche discrète et la complexité algébrique. Il est remarquable que même le cas d'une seule politique soit non trivial et « coûteux » sur les deux axes.
Comment rapprocher cela de la pratique ?
Les résultats obtenus sur la complexité peuvent rebuter, mais les auteurs ne s'arrêtent pas aux conclusions négatives. Ils proposent une construction hors ligne concrète de portefeuille qui permet une spécialisation à l'exécution (runtime specialization). L'idée est de préparer à l'avance un ensemble de politiques, puis, pendant l'interaction avec l'environnement, d'ajuster rapidement le choix en fonction de l'observation actuelle. Cette approche permet de combiner des garanties strictes avec une flexibilité pratique.
La conclusion est simple : dans les tâches où l'incertitude se révèle partiellement avec le temps, une stratégie unique fixée est nécessairement plus faible qu'un ensemble adaptatif. Le portefeuille de politiques paie par une complexité computationnelle plus élevée, mais offre en retour le droit à l'erreur et la capacité de basculer au fur et à mesure que les données arrivent. C'est une étape importante sur le chemin des méthodes purement conservatrices vers des systèmes de prise de décision intelligents dans l'incertitude.
