Limites inférieures exponentielles pour la planification dans les PDM avec des fonctions action-valeur optimales linéairement réalistes.

Résumé

Nous considérons le problème de la planification locale dans des processus de décision de Markov (PDM) à horizon fixe et actualisés avec approximation de fonction linéaire et modèle génératif, en supposant que la fonction action-valeur optimale se trouve dans l'étendue d'une carte de caractéristiques disponible pour le planificateur. Des travaux antérieurs ont laissé ouverte la question de savoir s'il existe des planificateurs solides qui ne nécessitent que des requêtes poly(H,d) indépendamment du MDP, où H est l'horizon et d la dimensionnalité des caractéristiques. Nous répondons à cette question par la négative : nous montrons que tout planificateur sain doit interroger au moins min(exp(Ω(d)),Ω(2H)) échantillons dans le cadre de l'horizon fisé et exp(Ω(d)) échantillons dans le cadre actualisé. Nous montrons également que pour tout δ>0, l'algorithme d'itération de la valeur des moindres carrés avec O(H5dH+1/δ2) requêtes peut calculer une politique δ-optimale dans le cadre de l'horizon fixe. Nous discutons des implications et des questions ouvertes restantes.