Planification efficace dans les grands PDM avec une approximation faible de la fonction linéaire.

Résumé

Les processus de décision de Markov (PDM) à grande échelle nécessitent des algorithmes de planification dont le temps d'exécution est indépendant du nombre d'états du PDM. Nous considérons le problème de la planification dans les MDPs en utilisant l'approximation linéaire de la fonction de valeur avec seulement de faibles exigences : une faible erreur d'approximation pour la fonction de valeur optimale, et un petit ensemble d'états " centraux " dont les caractéristiques couvrent celles des autres états. En particulier, nous ne faisons aucune hypothèse sur la représentabilité des politiques ou des fonctions de valeur des politiques non-optimales. Notre algorithme produit des actions quasi-optimales pour n'importe quel état en utilisant un oracle génératif (simulateur) pour le MDP, tandis que son temps de calcul s'échelonne de façon polynomiale avec le nombre de caractéristiques, d'états centraux et d'actions et l'horizon effectif.