An Efficient Dynamic Sampling Policy For Monte Carlo Tree Search

• URL: http://arxiv.org/abs/2204.12043v1
• Date: Tue, 26 Apr 2022 02:39:18 GMT
• Title: An Efficient Dynamic Sampling Policy For Monte Carlo Tree Search
• Authors: Gongbo Zhang, Yijie Peng, Yilong Xu
• Abstract summary: We consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS) We propose a dynamic sampling tree policy that efficiently allocates limited computational budget to maximize the probability of correct selection of the best action at the root node of the tree.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in the context of finite-horizon Markov decision process. We propose a dynamic sampling tree policy that efficiently allocates limited computational budget to maximize the probability of correct selection of the best action at the root node of the tree. Experimental results on Tic-Tac-Toe and Gomoku show that the proposed tree policy is more efficient than other competing methods.

Related papers

• Optimized Monte Carlo Tree Search for Enhanced Decision Making in the FrozenLake Environment [0.0]
  Monte Carlo Tree Search (MCTS) is a powerful algorithm for solving complex decision-making problems. This paper presents an optimized MCTS implementation applied to the FrozenLake environment, a classic reinforcement learning task.
  arXiv  Detail & Related papers  (2024-09-25T05:04:53Z)
• Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
  We propose a Deep Tree-based Retriever (DTR) for efficient recommendation. DTR frames the training task as a softmax-based multi-class classification over tree nodes at the same level. To mitigate the suboptimality induced by the labeling of non-leaf nodes, we propose a rectification method for the loss function.
  arXiv  Detail & Related papers  (2024-08-21T05:09:53Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Monte Carlo Tree Search with Boltzmann Exploration [16.06815496704043]
  We introduce Boltzmann Tree Search (BTS) and Decaying ENtropy Tree-Search (DENTS) Our algorithms show consistent high performance across several benchmark domains, including the game of Go.
  arXiv  Detail & Related papers  (2024-04-11T13:25:35Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  We introduce MetaTree, a transformer-based model trained via meta-learning to directly produce strong decision trees. We fit both greedy decision trees and globally optimized decision trees on a large number of datasets, and train MetaTree to produce only the trees that achieve strong generalization performance.
  arXiv  Detail & Related papers  (2024-02-06T07:40:53Z)
• RJHMC-Tree for Exploration of the Bayesian Decision Tree Posterior [1.3351610617039973]
  This paper is directed towards learning decision trees from data using a Bayesian approach. It investigates using a Hamiltonian Monte Carlo (HMC) approach to explore the posterior of Bayesian decision trees more efficiently.
  arXiv  Detail & Related papers  (2023-12-04T02:23:32Z)
• UNSAT Solver Synthesis via Monte Carlo Forest Search [10.754275929551593]
  We introduce Monte Carlo Forest Search (MCFS), a class of reinforcement learning (RL) algorithms for learning policies in tree MDPs Examples of such problems include proving unsatisfiability of a SAT formula; counting the number of solutions of a satisfiable SAT formula. We dub Knuth Synthesis, an MCFS algorithm that learns DPLL branching policies for solving the satisfiability (SAT) problem.
  arXiv  Detail & Related papers  (2022-11-22T20:52:50Z)
• Contextual Decision Trees [62.997667081978825]
  We propose a multi-armed contextual bandit recommendation framework for feature-based selection of a single shallow tree of the learned ensemble. The trained system, which works on top of the Random Forest, dynamically identifies a base predictor that is responsible for providing the final output.
  arXiv  Detail & Related papers  (2022-07-13T17:05:08Z)
• Social Interpretable Tree for Pedestrian Trajectory Prediction [75.81745697967608]
  We propose a tree-based method, termed as Social Interpretable Tree (SIT), to address this multi-modal prediction task. A path in the tree from the root to leaf represents an individual possible future trajectory. Despite the hand-crafted tree, the experimental results on ETH-UCY and Stanford Drone datasets demonstrate that our method is capable of matching or exceeding the performance of state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-26T12:18:44Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)

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.