Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search

• URL: http://arxiv.org/abs/2609.06489v1
• Date: Sun, 06 Sep 2026 09:04:39 GMT
• Title: Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search
• Abstract summary: 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.
• Score: 0.6903929927172916
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Monte Carlo Tree Search (MCTS) has demonstrated success in online planning for deterministic environments, yet significant challenges remain in adapting it to stochastic Markov Decision Processes (MDPs), particularly in continuous state-action spaces. Existing methods, such as HOOT, which combines MCTS with the Hierarchical Optimistic Optimization (HOO) bandit strategy, address continuous spaces but rely on a logarithmic exploration bonus that lacks theoretical guarantees in non-stationary, stochastic settings. Recent advancements, such as POLY-HOOT, introduced a polynomial bonus term to achieve convergence in deterministic MDPs, though a similar theory for stochastic MDPs remains undeveloped. In this paper, we propose a novel MCTS algorithm, \Algname, designed for continuous, stochastic MDPs. \Algname integrates a power mean as a value backup operator, alongside a polynomial exploration bonus to address the non-stationarity inherent in continuous action spaces. Our theoretical analysis establishes that \Algname converges at a polynomial rate of $\mathcal{O}(n^{-ζ})$, $ζ\in (0,1/2)$, where \( n \) is the number of visited trajectories, thereby extending the non-asymptotic convergence guarantees of POLY-HOOT to stochastic environments. Experimental results on stochastic tasks validate our theoretical findings, demonstrating the effectiveness of \Algname in continuous, stochastic domains.

Related papers

• Finite-Time Analysis of MCTS in Continuous POMDP Planning [9.578783083599621]
  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.
  arXiv  Detail & Related papers  (2026-05-08T13:13:29Z)
• Decentralized Proximal Stochastic Gradient Langevin Dynamics [4.385194124090593]
  Decentralized Proximal Gradient Langevin Dynamics (DE-PSGLD) for sampling from a log-concave probability distribution constrained to a convex domain.<n>As the first decentralized approach for constrained domains, our algorithm exhibits fast posterior concentration and high predictive accuracy.
  arXiv  Detail & Related papers  (2026-05-01T15:11:06Z)
• Polynomial Regret Concentration of UCB for Non-Deterministic State Transitions [18.347534843178355]
  This paper extends the theoretical framework of Monte Carlo Tree Search (MCTS) to non-deterministic state transitions.<n>Our primary contribution is proving that these bounds also apply to non-deterministic environments, ensuring robust performance in settings.<n>This broadens the applicability of MCTS to real-world decision-making problems with outcomes, such as in autonomous systems and financial decision-making.
  arXiv  Detail & Related papers  (2025-02-09T15:46:42Z)
• MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times [49.1574468325115]
  We investigate the problem of minimizing the expectation of smooth non functions in a setting with multiple parallel workers that are able to compute optimal gradients.<n>A challenge in this context is the presence of arbitrarily heterogeneous and distributed compute times.<n>We introduce MindFlayer SGD, a novel parallel SGD method specifically designed to handle this gap.
  arXiv  Detail & Related papers  (2024-10-05T21:11:32Z)
• Power Mean Estimation in Stochastic Monte-Carlo Tree_Search [25.058008522872747]
  Monte-Carlo Tree Search (MCTS) is a widely-used strategy for online planning that combines Monte-Carlo sampling with forward tree search. The theoretical foundation of UCT is incomplete due to an error in the logarithmic bonus term for action selection. This paper introduces an algorithm using the power mean estimator and tailored for MDPs.
  arXiv  Detail & Related papers  (2024-06-04T11:56:37Z)
• 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)
• Exponential convergence rates for momentum stochastic gradient descent in the overparametrized setting [0.6445605125467574]
  We prove bounds on the rate of convergence for the momentum gradient descent scheme (MSGD) We analyze the optimal choice of the friction and show that the MSGD process almost surely converges to a local.
  arXiv  Detail & Related papers  (2023-02-07T15:59:08Z)
• 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)
• 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)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime. We show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. We prove that the Overlap Gap Property (OGP) holds in a significant part of the hard regime.
  arXiv  Detail & Related papers  (2020-06-18T17:18:02Z)
• POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with Non-Asymptotic Analysis [24.373900721120286]
  We consider Monte-Carlo planning in an environment with continuous state-action spaces. We introduce Poly-HOOT, an algorithm that augments Monte-Carlo planning with a continuous armed bandit strategy. We investigate for the first time, for the first time, the regret of the enhanced HOO algorithm in non-stationary bandit problems.
  arXiv  Detail & Related papers  (2020-06-08T15:23:19Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation. We present an provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.
  arXiv  Detail & Related papers  (2020-03-01T17:47:03Z)

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.