In this thesis, we describe Forward Sparse Sampling Search, an algorithm that was published in 2010 by Walsh et al., which combines model-based reinforcement learning with sample-based planning.
We show how it can be applied to solving an appropriate set of problems, as well as extend the original tests to give a better view on how the parameters of the algorithm work, and to further the understanding of the method.
First, we introduce the concept of reinforcement learning, and identify key environments and points of interest where FSSS is applicable. Next, we explain the terminology and relevant theories the method is based on. The aim is to introduce the reader to a powerful tool for control-problems, and show where to apply it and how to parameterize it. After reading this thesis, one is hopefully fitted with dealing with the basic setup and usage of FSSS.
In the final sections of the thesis, we report a series of tests which demonstrate how FSSS works in one particular environment - the Paint/Polish world. The tests focus on understanding the effects of various parameters that the method uses, yielding further understanding on how to effectively apply it, analyzing its performance and comparing it to more basic algorithms on the field. The principal theories and proofs will be explained, and possible paths to improve the algorithm will be explored.
