https://dumas.ccsd.cnrs.fr/dumas-00636782Perng, Chao-WenChao-WenPerngTelecom Bretagne - Rennes - Télécom BretagneGenerating Heuristic Functions for Stochastic Shortest Path Problems by Targeted Aggregation of StatesHAL CCSD2011Reinforcement learningMarkov processshortest path problem[INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]V. Gouranton Et S. Blazy, Co-Responsables Du Mri2011-10-28 11:46:322021-10-05 10:18:032011-10-28 16:06:57enMaster Thesisapplication/pdf1In 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.