Recherche en ligne pour les processus décisionnels de Markov
La résolution de processus décisionnels de Markov (PDMs) de grande dimension est habituellement basée sur le calcul hors-ligne d'une approximation de la fonction de valeur optimale et sur son exploitation en ligne pour définir une politique gloutonne. Toutefois, quand l'espace d'états est très vaste et qu'aucune représentation structurée efficace n'est connue, le calcul d'une bonne approximation de la fonction de valeur optimale s'avère souvent une tâche difficile. Dans cet article, nous proposons une méthode alternative reposant sur le développement en chaque état courant d'un arbre de recherche construit à partir de la simulation stochastique du PDM sur un certain horizon de raisonnement. Nous montrons expérimentalement son bon comportement anytime sur un problème de navigation modélisé comme un plus court chemin stochastique.
Markov Decision Processes (MDPs) have become a standard for solving problems of sequential decision under uncertainty. The usual request in this framework is the computation of an optimal policy that defines an optimal action for every state of the system. For complex MDPs, exact computation of optimal policies is often untractable. Several approaches have been developed to compute near optimal policies for complex MDPs by means of function approximation and simulation. In this paper, we propose a method for refining near optimal policies via online search techniques, by developping from each current state a randomly sampled look-ahead tree. We show on a navigation problem modeled as a stochastic shortest path that this online search strategy provides good "anytime" profiles.
L.PÉRET, F.GARCIA
processus décisionnels de Markov, apprentissage par renforcement, recherche heuristique.
Markov decision processes, reinforcement learning, heuristic search.
Français
|
