Improved POMDP Tree Search Planning with Prioritized Action Branching

• URL: http://arxiv.org/abs/2010.03599v1
• Date: Wed, 7 Oct 2020 18:33:57 GMT
• Title: Improved POMDP Tree Search Planning with Prioritized Action Branching
• Authors: John Mern, Anil Yildiz, Larry Bush, Tapan Mukerji, Mykel J. Kochenderfer
• Abstract summary: This paper proposes a method called PA-POMCPOW to sample a subset of the action space that provides varying mixtures of exploitation and exploration for inclusion in a search tree. Experiments show that PA-POMCPOW is able to outperform existing state-of-the-art solvers on problems with large discrete action spaces.
• Score: 33.94599291823342
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online solvers for partially observable Markov decision processes have difficulty scaling to problems with large action spaces. This paper proposes a method called PA-POMCPOW to sample a subset of the action space that provides varying mixtures of exploitation and exploration for inclusion in a search tree. The proposed method first evaluates the action space according to a score function that is a linear combination of expected reward and expected information gain. The actions with the highest score are then added to the search tree during tree expansion. Experiments show that PA-POMCPOW is able to outperform existing state-of-the-art solvers on problems with large discrete action spaces.

Related papers

• 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)
• Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstraction [27.53460927687747]
  We propose an action abstraction based on the compositional structure between a state and sub-actions. Our method learns a latent dynamics model with an auxiliary network that captures sub-actions relevant to the transition on the current state.
  arXiv  Detail & Related papers  (2024-06-02T04:31:30Z)
• Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the Unknown [19.664506834858244]
  Monte-Carlo tree search (MCTS) strategically allocates computational resources to focus on promising segments of the search tree. Our proposed methodology, denoted as AmEx-MCTS, solves this problem by introducing a novel MCTS formulation. Our empirical evaluation demonstrates the superior performance of AmEx-MCTS, surpassing classical MCTS and related approaches by a substantial margin.
  arXiv  Detail & Related papers  (2024-02-13T15:05:54Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Planner reframes task planning with Large Language Models into three distinct phases. Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
  arXiv  Detail & Related papers  (2023-10-12T17:59:50Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Adaptive Discretization using Voronoi Trees for Continuous POMDPs [7.713622698801596]
  We propose a new sampling-based online POMDP solver, called Adaptive Discretization using Voronoi Trees (ADVT) It uses Monte Carlo Tree Search in combination with an adaptive discretization of the action space as well as optimistic optimization to efficiently sample high-dimensional continuous action spaces. ADVT scales substantially better to high-dimensional continuous action spaces, compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-02-21T04:47:34Z)
• Adaptive Discretization using Voronoi Trees for Continuous-Action POMDPs [7.713622698801596]
  We propose a new sampling-based online POMDP solver, called Adaptive Discretization using Voronoi Trees (ADVT) ADVT uses Monte Carlo Tree Search in combination with an adaptive discretization of the action space as well as optimistic optimization. Experiments on simulations of four types of benchmark problems indicate that ADVT outperforms and scales substantially better to high-dimensional continuous action spaces.
  arXiv  Detail & Related papers  (2022-09-13T05:04:49Z)
• Bayesian Optimized Monte Carlo Planning [34.8909579244631]
  Monte Carlo tree search with progressive widening attempts to improve scaling by sampling from the action space to construct a policy search tree. We present a general method for efficient action sampling based on Bayesian optimization. We implement the proposed approach in a new online tree search algorithm called Bayesian Optimized Monte Carlo Planning.
  arXiv  Detail & Related papers  (2020-10-07T18:29:27Z)
• Planning in Markov Decision Processes with Gap-Dependent Sample Complexity [48.98199700043158]
  We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process. We prove an upper bound on the number of calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability.
  arXiv  Detail & Related papers  (2020-06-10T15:05:51Z)
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
  Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs) We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching.
  arXiv  Detail & Related papers  (2020-02-12T17:43:23Z)

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.