Parallelization of Monte Carlo Tree Search in Continuous Domains

• URL: http://arxiv.org/abs/2003.13741v1
• Date: Mon, 30 Mar 2020 18:43:59 GMT
• Title: Parallelization of Monte Carlo Tree Search in Continuous Domains
• Authors: Karl Kurzer, Christoph H\"ortnagl, J. Marius Z\"ollner
• Abstract summary: Monte Carlo Tree Search (MCTS) has proven to be capable of solving challenging tasks in domains such as Go, chess and Atari. Our work builds upon existing parallelization strategies and extends them to continuous domains.
• Score: 2.658812114255374
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Monte Carlo Tree Search (MCTS) has proven to be capable of solving challenging tasks in domains such as Go, chess and Atari. Previous research has developed parallel versions of MCTS, exploiting today's multiprocessing architectures. These studies focused on versions of MCTS for the discrete case. Our work builds upon existing parallelization strategies and extends them to continuous domains. In particular, leaf parallelization and root parallelization are studied and two final selection strategies that are required to handle continuous states in root parallelization are proposed. The evaluation of the resulting parallelized continuous MCTS is conducted using a challenging cooperative multi-agent system trajectory planning task in the domain of automated vehicles.

Related papers

• Parallel Approaches to Accelerate Bayesian Decision Trees [1.9728521995447947]
  We propose two methods for exploiting parallelism in the MCMC. In the first, we replace the MCMC with another numerical Bayesian approach. In the second, we consider data partitioning.
  arXiv  Detail & Related papers  (2023-01-22T09:56:26Z)
• SimCS: Simulation for Domain Incremental Online Continual Segmentation [60.18777113752866]
  Existing continual learning approaches mostly focus on image classification in the class-incremental setup. We propose SimCS, a parameter-free method complementary to existing ones that uses simulated data to regularize continual learning.
  arXiv  Detail & Related papers  (2022-11-29T14:17:33Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  Continuous Monte Carlo Graph Search ( CMCGS) is an extension of Monte Carlo Tree Search (MCTS) to online planning. CMCGS takes advantage of the insight that, during planning, sharing the same action policy between several states can yield high performance. It can be scaled up through parallelization, and it outperforms the Cross-Entropy Method (CEM) in continuous control with learned dynamics models.
  arXiv  Detail & Related papers  (2022-10-04T07:34:06Z)
• Parallel Training of GRU Networks with a Multi-Grid Solver for Long Sequences [1.9798034349981162]
  We present a novel parallel training scheme (called parallel-in-time) for Gated Recurrent Unit (GRU) networks. MGRIT partitions a sequence into multiple shorter sub-sequences and trains the sub-sequences on different processors in parallel. Experimental results on the HMDB51 dataset, where each video is an image sequence, demonstrate that the new parallel training scheme achieves up to 6.5$times$ speedup over a serial approach.
  arXiv  Detail & Related papers  (2022-03-07T11:32:44Z)
• Parallel Attention Network with Sequence Matching for Video Grounding [56.649826885121264]
  Given a video, video grounding aims to retrieve a temporal moment that semantically corresponds to a language query. We propose a Parallel Attention Network with Sequence matching (SeqPAN) to address the challenges in this task.
  arXiv  Detail & Related papers  (2021-05-18T12:43:20Z)
• Parallel Training of Deep Networks with Local Updates [84.30918922367442]
  Local parallelism is a framework which parallelizes training of individual layers in deep networks by replacing global backpropagation with truncated layer-wise backpropagation. We show results in both vision and language domains across a diverse set of architectures, and find that local parallelism is particularly effective in the high-compute regime.
  arXiv  Detail & Related papers  (2020-12-07T16:38:45Z)
• Learning Robust State Abstractions for Hidden-Parameter Block MDPs [55.31018404591743]
  We leverage ideas of common structure from the HiP-MDP setting to enable robust state abstractions inspired by Block MDPs. We derive instantiations of this new framework for both multi-task reinforcement learning (MTRL) and meta-reinforcement learning (Meta-RL) settings.
  arXiv  Detail & Related papers  (2020-07-14T17:25:27Z)
• Auto-MAP: A DQN Framework for Exploring Distributed Execution Plans for DNN Workloads [11.646744408920764]
  Auto-MAP is a framework for exploring distributed execution plans for workloads. It can automatically discovering fast parallelization strategies through reinforcement learning on IR level of deep learning models. Our evaluation shows that Auto-MAP can find the optimal solution in two hours, while achieving better throughput on several NLP and convolution models.
  arXiv  Detail & Related papers  (2020-07-08T12:38:03Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree. How to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. We demonstrate how proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms.
  arXiv  Detail & Related papers  (2020-06-15T21:36:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.