Processus décisionnels de Markov avec un tournoi valué sur les politiques

Hugo Gilbert, Olivier Spanjaard, Paolo Viappiani, Paul Weng
ROADEF 2015

Abstract : Le modèle des processus décisionnels de Markov (MDP) offre un formalisme pour modéliser et résoudre des problèmes de planification dans l’incertain. Etant donné un espace d’état, un espace d’action, une fonction de transition et une fonction de récompense, le problème consiste à trouver une politique optimale selon un critère de décision donné. Dans le cadre le plus classique, la politique optimale maximise l’espérance de la somme des récompenses obtenues. Ce critère ne prend pas en compte l’attitude vis-à-vis du risque (goût pour le risque ou adversaire du risque) et peut donner des résultats discutables si l’issue de la politique obtenue est risquée et que le nombre d’essais à effectuer est faible. Plusieurs critères de décision alternatifs ont été proposés pour pallier cet inconvénient (espérance d’utilité, espérance d’utilité dépendant du rang, ...). Tous ces critères partagent toutefois le point commun de supposer la commensurabilité des probabilités et des récompenses. Nous proposons ici d’étudier un critère naturel qui ne s’appuie pas sur l’utilisation d’une fonction d’utilité, ne nécessite pas d’élicitation de préférences et ne suppose pas que les probabilités et les récompenses soient commensurables. Dans cette communication, nous identifions des ensembles de politiques sur lesquels il est suffisant de focaliser la recherche car on peut prouver qu’ils suffisent pour construire une politique optimale pour notre critère. Nous exposons ensuite une méthode pour calculer une politique optimale en faisant le lien avec des algorithmes classiques de la théorie des jeux.

PDF