Conference Proceeding Article
Finding optimal policies for Markov Decision Processes with large state spaces is in general intractable. Nonetheless, simulation-based algorithms inspired by Sparse Sampling (SS) such as Upper Confidence Bound applied in Trees (UCT) and Forward Search Sparse Sampling (FSSS) have been shown to perform reasonably well in both theory and practice, despite the high computational demand. To improve the efficiency of these algorithms, we adopt a simple enhancement technique with a heuristic policy to speed up the selection of optimal actions. The general method, called Aux, augments the look-ahead tree with auxiliary arms that are evaluated by the heuristic policy. In this paper, we provide theoretical justification for the method and demonstrate its effectiveness in two experimental benchmarks that showcase the faster convergence to a near optimal policy for both SS and FSSS. Moreover, to further speed up the convergence of these algorithms at the early stage, we present a novel mechanism to combine them with UCT so that the resulting hybrid algorithm is superior to both of its components.
markov decision process, sparse sampling, forward sparse sampling, uct, heuristic
Theory and Algorithms
Intelligent Systems and Decision Analytics
Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014)
City or Country
Nguyen T., Silander T., Lee W., and Tze-Yun LEONG.
Bootstrapping simulation-based algorithms with a suboptimal policy. (2014). Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014). 190-198. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3000