Finite-Time Analysis of MCTS in Continuous POMDP Planning

• URL: http://arxiv.org/abs/2605.07703v1
• Date: Fri, 08 May 2026 13:13:29 GMT
• Title: Finite-Time Analysis of MCTS in Continuous POMDP Planning
• Abstract summary: This paper presents a finite-time analysis for Monte Carlo Tree Search (MCTS) in Partially Observable Decision Processes (POMDPs)<n>It has probabilistic concentration bounds in both discrete and continuous observation spaces.<n>We propose a variant of POMCPOW with f inite-time guarantees that adaptively partitions the continuous observation space using Voronoi cells.
• Score: 9.578783083599621
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a finite-time analysis for Monte Carlo Tree Search (MCTS) in Partially Observable Markov Decision Processes (POMDPs), with probabilistic concentration bounds in both discrete and continuous observation spaces. While MCTS-style solvers such as POMCP achieve empirical success in many applications, rigorous finite-time guarantees remain an open problem due to the nonstationarity and the interdependencies induced by heuristic action selection (e.g., UCB). In the discrete setting, we address these challenges by extending the polynomial exploration bonus to UCB in POMDP setting, yielding polynomial concentration bounds for the empirical value estimation at the root node. For continuous observation spaces, we introduce an abstract partitioning framework and propose a finite-time bound on partitioning loss. Under mild conditions, we prove highprobability bound on value estimates in POMDPs with continuous observation space. Specifically, we propose Voro-POMCPOW, a variant of POMCPOW with f inite-time guarantees that adaptively partitions the continuous observation space using Voronoi cells. This approach maintains a finite branching factor while preserving the original observation generator. Empirical validation demonstrates that the proposed Voro-POMCPOW shows competitive performance while providing theoretical guarantees. Although our analysis focuses on continuous POMDPs, the techniques developed herein are also applicable to continuous MDPs, closing another gap on the MDP side.

Related papers

• Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search [0.6903929927172916]
  We propose a novel Monte Carlo Tree Search (MCTS) algorithm for continuous Markov Decision Processes (MDPs)<n>Our theoretical analysis establishes that Algname converges at a rate of $mathcalO(n-)$, $in (0,1/2)$, where ( n) is the number of visited trajectories, thereby extending the non-asymptotic convergence guarantees.
  arXiv  Detail & Related papers  (2026-09-06T09:04:39Z)
• Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation [49.86232017439639]
  We introduce Multi-Output Augmented Behavioral Cloning (MA-BC)<n>MA-BC partitions divergent expert data while pooling state-action pairs where no behavior conflict is observed.<n>We establish a novel lower bound for multi-objective imitation learning, demonstrating that MA-BC is minimax optimal.
  arXiv  Detail & Related papers  (2026-05-12T11:49:08Z)
• On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
  We present the first finite time global convergence analysis of policy gradient in the context of average reward Markov decision processes (MDPs) Our analysis shows that the policy gradient iterates converge to the optimal policy at a sublinear rate of $Oleft(frac1Tright),$ which translates to $Oleft(log(T)right)$ regret, where $T$ represents the number of iterations.
  arXiv  Detail & Related papers  (2024-03-11T15:25:03Z)
• Safe Reinforcement Learning in Tensor Reproducing Kernel Hilbert Space [9.823296458696882]
  In traditional partially observable Markov decision processes, ensuring safety typically involves estimating the belief in latent states. We propose a model-based approach that guarantees RL safety almost surely in the face of unknown system dynamics.
  arXiv  Detail & Related papers  (2023-12-01T17:01:37Z)
• Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
  Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. POMDPs are notoriously difficult to solve, especially when the state and observation spaces are continuous or hybrid. We propose a theory characterizing the approximation error of the particle filtering techniques that these algorithms use.
  arXiv  Detail & Related papers  (2022-10-10T21:11:55Z)
• Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings [97.12538243736705]
  We study reinforcement learning with function approximation for large-scale Partially Observable Decision Processes (POMDPs) Our algorithm provably scales to large-scale POMDPs.
  arXiv  Detail & Related papers  (2022-06-24T05:13:35Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  The paper takes a generative perspective on policy evaluation via temporal-difference (TD) learning. The OS-GPTD approach is developed to estimate the value function for a given policy by observing a sequence of state-reward pairs. To alleviate the limited expressiveness associated with a single fixed kernel, a weighted ensemble (E) of GP priors is employed to yield an alternative scheme.
  arXiv  Detail & Related papers  (2021-12-01T23:15:09Z)
• Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity [2.685668802278156]
  We show that Q-learning for standard Borel MDPs via quantization of states and actions converges to a limit. Our paper presents a very general convergence and approximation result for the applicability of Q-learning for continuous MDPs.
  arXiv  Detail & Related papers  (2021-11-12T15:47:10Z)
• Monte Carlo Information-Oriented Planning [6.0158981171030685]
  We discuss how to solve information-gathering problems expressed as rho-POMDPs. We build on the POMCP algorithm to propose a Monte Carlo Tree Search for rho-POMDPs.
  arXiv  Detail & Related papers  (2021-03-21T09:09:27Z)
• Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes [0.0]
  We study a planning problem for POMDPs where the system dynamics and measurement channel model is assumed to be known. We find optimal policies for the approximate belief model under mild non-linear filter stability conditions. We also establish a rate of convergence result which relates the finite window memory size and the approximation error bound.
  arXiv  Detail & Related papers  (2020-10-15T00:37:51Z)
• A maximum-entropy approach to off-policy evaluation in average-reward MDPs [54.967872716145656]
  This work focuses on off-policy evaluation (OPE) with function approximation in infinite-horizon undiscounted Markov decision processes (MDPs) We provide the first finite-sample OPE error bound, extending existing results beyond the episodic and discounted cases. We show that this results in an exponential-family distribution whose sufficient statistics are the features, paralleling maximum-entropy approaches in supervised learning.
  arXiv  Detail & Related papers  (2020-06-17T18:13:37Z)

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.