Monte Carlo Tree Search (MCTS) has achieved impressive results on a range of discrete environments, such as Go, Mario and Arcade games, but it has not yet fulfilled its true potential in continuous domains. In this work, we introduceTPO, a tree search based policy optimization method for continuous environments. TPO takes a hybrid approach to policy optimization.   Building the MCTS tree in a continuous action space and updating the policy gradient using off-policy MCTS trajectories are non-trivial. To overcome these challenges, we propose limiting tree search branching factor by drawing only few action samples from the policy distribution and define a new loss function based on the trajectories’ mean and standard deviations.   Our approach led to some non-intuitive findings.   MCTS training generally requires a large number of samples and simulations. However, we observed that bootstrappingtree search with a pre-trained policy allows us to achieve high quality results with a low MCTS branching factor and few number of simulations. Without the proposed policy bootstrapping, continuous MCTS would require a much larger branching factor and simulation count, rendering it computationally and prohibitively expensive. In our experiments, we use PPO as our baseline policy optimization algorithm. TPO significantly improves the policy on nearly all of our benchmarks.   For example, in complex environments such as Humanoid, we achieve a 2.5×improvement over the baseline algorithm. Fueled by advances in neural representation learning, the field of model-free reinforcement learning has rapidly evolved over the past few years. These advances are due in part to the advent of algorithms capable of navigating larger action spaces and longer time horizons [2, 32, 42] , as well as the distribution of data collection and training across massive-scale computing resources [42, 38, 16, 32] . While learning algorithms have been continuously improving, it is undeniable that tree search methods have played a large role in some of the most successful applications of RL (e.g., AlphaZero [42] , Mario [10] and Arcade games [48] ). Tree search methods enable powerful explorations of the action space in a way which is guided by the topology of the search space, focusing on branches (actions) that are more promising. Although tree search methods have achieved impressive results on a range of discrete domains, they have not yet fulfilled their true potential in continuous domains. Given that the number of actions is inherently unbounded in continuous domains, traditional approaches to building the search tree become intractable from a computational perspective. In this paper, we introduce TPO, a Tree Search Policy Optimization for environments with continuous action spaces. We address the challenges of building the tree and running simulations by adopting a hybrid method, in which we first train a policy using existing model-free RL methods, and then use the pre-trained policy distribution to draw actions with which to build the tree. Once the tree has been constructed, we run simulations to generate experiences using an Upper Confidence Bounds for Trees (UCT) approach [33] . Populating the tree with the action samples drawn from a pre-trained policy enables us to perform a computationally feasible search. TPO is a variation of the policy iteration method [35, 44, 42, 1] . Broadly, in these methods, the behavior of policy is iteratively updated using the trajectories generated by an expert policy. Then, the newly updated policy in return guides the expert to generate higher quality samples. In TPO, we use tree search as an expert to generate high quality trajectories. Later, we employ the updated policy to re-populate the tree search. For tree search, we use the Monte Carlo Tree Search (MCTS) [5] expansion and selection methods. However, it is challenging to directly infer the probability of selected actions for rollout; unlike in discrete domains where all actions can be exhaustively explored, in continuous domains, we cannot sample more than a subset of the effectively innumerable continuous action space. Furthermore, to use the trajectories generated by MCTS, we must perform off-policy optimization. To address this challenge, we define a new loss function that uses the weighted mean and standard deviation of the tree search statistics to update the pre-trained policy. For ease of implementation and scalability, we use Proximal Policy Optimization (PPO) [38] and choose as our policy optimization baseline. In phase 1, we perform a policy gradient based optimization training to build a target policy. In phase 2, we iteratively build an MCTS tree using the pre-trained target policy and update the target policy using roll-out trajectories from MCTS. Both training and data collection are done in a distributed manner. Our approach led to some non-intuitive findings. MCTS training generally requires a large number of branches and simulations. For example, AlphaGo uses 1600 simulations per tree search and a branching factor of up to 362 [40] . However, we observed that if we pre-train the policy, we require far fewer simulations to generate high quality trajectories. While we do benefit from exploring a greater number of branches, especially for higher dimensional action spaces (e.g. Humanoid), we observed diminishing returns after only a small number of branches (e.g., 32) across all of the evaluated environments. Furthermore, performance quickly plateaued as we increased the number of simulations past 32. This property did not hold when we initialized tree search with an untrained policy. This is a critical advantage of our method as it would otherwise be computationally infeasible to generate high quality trajectories using tree search. The main contributions of TPO are summarized as follows: 1. Tree search policy optimization for continuous action spaces. TPO is one of the very first techniques that integrates tree search into policy optimization for continuous action spaces. This unique integration of tree search into policy optimization yields a superior performance compared to baseline policy optimization techniques for continuous action spaces. 2. Policy bootstrapping. We propose a policy bootstrapping technique that significantly improves the sample efficiency of the tree search and enables us to discretize continuous action spaces into only a few number of highly probable actions. More specifically, TPO only performs 32 tree searches compared to substantially larger number of tree searches (1600, 50× more) in AlphaGo [42] . In addition, TPO narrows down the number of tree expansion (actions) compared to discretization techniques such as Tang et al. [45] which requires 7-11 bins per action dimension. This number of bins translates to a prohibitively large number of actions even in discrete domain for complex environments such as Humanoid which has a 17 dimensional action space. In contrast, TPO only samples 32 actions at each simulation step across all the environments. 3. Infrastructure and results. On the infrastructure side, we developed a distributed system (shown in Figure 1 ), in which both policy optimization and data collection are performed on separate distributed platforms. The policy optimization is done on a TPU-v2 using multiple cores, and MCTS search is performed on a rack of CPU nodes. A synchronous policy update and data collection approach is used to train the policy and generate trajectories. TPO readily extends to challenging and high-dimensional tasks, such the Humanoid benchmark [9] . Our empirical results indicate that TPO significantly improves the performance of the baseline policy optimization algorithm, achieving up to 2.5× improvement. In this paper, we have studied Monte Carlo Tree Search in continuous space for improving the performance of a baseline on-policy algorithm [38] . Our results show that MCTS policy optimization can indeed improve the quality of policy in choosing better actions during policy evaluation at the cost of more samples during MCTS rollout. We show that bootstrapping tree search with a pretrained policy enables us to achieve high performance with a low MCTS branching factor and few simulations. On the other hand, without pre-training, we require a much larger branching factor and simulation count, rendering MCTS computationally infeasible. One of the future research direction is to explore techniques for improving the sample efficiency and removing the need for having a reset-able environment. To achieve these goals, we can use a trained model of the environment similar to model-based reinforcement learning approaches [20, 23, 6] , instead of interacting directly with the environment in MCTS. Recently, MBPO [20] showed that they can train a model of Mujoco environments that is accurate enough for nearly 200-step rollouts in terms of accumulated rewards. This level of accuracy horizon is more than enough for the shallow MCTS simulations (32 simulations) that is employed in TPO. As mentioned earlier, TPO assumes access to an environment that can be restarted from an arbitrary state for MCTS simulations. While this assumption can be readily satisfied in some RL problems such as playing games, it may be harder to achieve for physical RL problems like Robotics. This assumption can also be relaxed using a modeled environment to replace the interactions with the real environment during MCTS simulations.
We use MCTS to further optimize a bootstrapped policy for continuous action spaces under a policy iteration setting.
{"src": "scitldr-AIC_train", "paper_id": "HJew70NYvH"}