Skip to Main content Skip to Navigation
Master Thesis

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

Abstract : 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.
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download

https://dumas.ccsd.cnrs.fr/dumas-00636782
Contributor : Co-Responsables Du Mri V. Gouranton Et S. Blazy <>
Submitted on : Friday, October 28, 2011 - 11:46:32 AM
Last modification on : Friday, March 6, 2020 - 1:25:31 AM
Long-term archiving on: : Monday, January 30, 2012 - 11:14:44 AM

Identifiers

  • HAL Id : dumas-00636782, version 1

Collections

Citation

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

Share

Metrics

Record views

195

Files downloads

78