Twice Sequential Monte Carlo for Tree Search

Model-based reinforcement learning (RL) methods that leverage search are responsible for many milestone breakthroughs in RL. Sequential Monte Carlo (SMC) recently emerged as an alternative to the Monte Carlo Tree Search (MCTS) algorithm which drove these breakthroughs. SMC is easier to parallelize and more suitable to GPU acceleration. However, it also suffers from large variance and path degeneracy which prevent it from scaling well with increased search depth, i.e., increased sequential compute. To address these problems, we introduce Twice Sequential Monte Carlo Tree Search (TSMCTS). Across discrete and continuous environments TSMCTS outperforms the SMC baseline as well as a popular modern version of MCTS as a policy improvement operator, scales favorably with sequential compute, reduces estimator variance and mitigates the effects of path degeneracy while retaining the properties that make SMC natural to parallelize.

Model-based reinforcement learning agents are among the best-performing Artificial-Intelligence (AI) methods for decision making in challenging situations by leveraging planning in the model, using methods such as Sequential Monte Carlo (SMC). Although having many beneficial properties, SMC struggles with planning far into the future due to problems such as sharply-increasing variance and path degeneracy. To address these problems, we introduce a novel method, Twice Sequential Monte Carlo for Tree Search (TSMCTS). TSMCTS effectively mitigates both the sharp variance increase and the effects of path degeneracy. As a result, TSMCTS significantly improves the ability of AI agents which use SMC to plan to make - and learn from - better decisions to scale with increased planning horizon.