Ce travail étudie la complexité de l'échantillonnage des processus de décision de Markov robustes (RMDP) L'objectif est d'optimiser les performances dans le pire des cas lorsque l'environnement se situe dans un ensemble d'incertitudes défini entourant un certain processus de Markov décisionnels (MDP) dit nominal. Malgré des efforts récents, la complexité d'échantillonnage des processus décisionnels de Markov robustes reste indéterminée. Bien que cette question ait été étudiée dans certains cas spécifiques, la généralisation des résultats existants reste incertaine, en particulier en comparaison avec les MDPs standards. En supposant l'accès à un modèle génératif qui échantillonne à partir du MDP nominal, nous examinons la complexité d'échantillonnage des RMDPs en utilisant une norme arbitraire comme fonction de "distance" pour l'ensemble d'incertitude, sous deux conditions couramment adoptées sa-rectangulaire et s-rectangulaire.
Nous fournissons une borne supérieure quasi-optimale et une borne inférieure minimax correspondante pour les scénarios sa- rectangulaires. Pour les scénarios s-rectangulaires, nous améliorons la borne supérieure de pointe et dérivons une borne inférieure pour la norme L infinie et L 1.
Les résultats impliquent que les RMDPs peuvent être plus efficaces en termes d'échantillonnage que les MDP standards sous des normes générales dans les cas sa- et s-rectangulaires.