Generating Heuristic Functions for Stochastic Shortest Path Problems by Targeted Aggregation of States - DUMAS - Dépôt Universitaire de Mémoires Après Soutenance Accéder directement au contenu
Mémoires Année : 2011

Generating Heuristic Functions for Stochastic Shortest Path Problems by Targeted Aggregation of States

Résumé

In a reinforcement learning problem, the agent learns to achieve a goal from interacting with the environment. Markov decision process is a way to formulate such problems. We are interested in solving the stochastic shortest path (SSP) problems, which is a special case of Markov Decision Processes in which one seeks to calculate a policy that minimizes the average cost to reach a goal state. Real Time Dynamic Programming (RTDP) is a recent heuristic search algorithm that can solve SSP, and we will use the Labeled Real Time Dynamic Programming (LRTDP), an alternative version of RTDP with a labeling scheme that speeds up its convergence. Its behavior depends on the proximity of the heuristic. We seek to find such a heuristic by aggregating the states into macro-states and use the value function obtained from the abstracted problem as the heuristic for the original problem. We designed an aggregation algorithm to obtain an aggregation of good quality. Experiments are run on several benchmarks to see the performance time of the algorithm and how the heuristic obtained improves the performance of LRTDP.
Fichier principal
Vignette du fichier
Perng.pdf (450.52 Ko) Télécharger le fichier
Loading...

Dates et versions

dumas-00636782 , version 1 (28-10-2011)

Identifiants

  • HAL Id : dumas-00636782 , version 1

Citer

Chao-Wen Perng. Generating Heuristic Functions for Stochastic Shortest Path Problems by Targeted Aggregation of States. Machine Learning [cs.LG]. 2011. ⟨dumas-00636782⟩
112 Consultations
52 Téléchargements

Partager

Gmail Facebook X LinkedIn More