論文の概要: Finite-Time Analysis of MCTS in Continuous POMDP Planning

• arxiv url: http://arxiv.org/abs/2605.07703v1
• Date: Fri, 08 May 2026 13:13:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:39.061457
• Title: Finite-Time Analysis of MCTS in Continuous POMDP Planning
• Title（参考訳）: 連続PMDP計画におけるMCTSの有限時間解析
• Authors: Da Kong, Vadim Indelman,
• Abstract要約: 本稿では, 部分観測可能決定過程(POMDP)におけるモンテカルロ木探索(MCTS)の有限時間解析について述べる。 離散観測空間と連続観測空間の両方に確率的濃度境界がある。 本稿では, ボロノイセルを用いた連続観測空間を適応的に分割する, f inite-time 保証付き POMCPOW の変種を提案する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 本稿では,部分観測可能なマルコフ決定過程 (POMDP) におけるモンテカルロ木探索 (MCTS) の有限時間解析について述べる。 POMCPのようなMCTSスタイルの解法は、多くの応用において経験的な成功を収めるが、厳密な有限時間保証は、非定常性やヒューリスティックな行動選択(例えば UCB)によって引き起こされる相互依存性のために、未解決の問題のままである。 離散的な設定では、多項式探索ボーナスをPMDP設定で UCB に拡張し、根ノードでの経験値推定のための多項式濃度境界を出力することで、これらの課題に対処する。 連続観測空間に対しては,抽象的なパーティショニングフレームワークを導入し,パーティショニング損失に対する有限時間境界を提案する。 軽度条件下では, 連続観測空間を持つPOMDPの値推定値に高確率で依存することを示す。 具体的には,POMCPOWの変種であるVoro-POMCPOWを提案する。 このアプローチは、元の観測生成器を保持しながら有限分岐係数を維持する。 実証的な検証は、提案されたVoro-POMCPOWは、理論的保証を提供しながら、競争性能を示すことを示している。 本分析は連続PMDPに焦点をあてるが,本手法は連続MDPにも適用でき,MDP側の別のギャップを埋めることができる。

関連論文リスト

• On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
  我々は、平均報酬マルコフ決定過程(MDP)の文脈における政策勾配の最初の有限時間大域収束解析を示す。 我々の分析によると、ポリシー勾配は、$Oleft(frac1Tright)$のサブリニアレートで最適ポリシーに収束し、$Oleft(log(T)right)$ regretに変換され、$T$は反復数を表す。
  論文  参考訳（メタデータ） (2024-03-11T15:25:03Z)
• Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
  部分的に観測可能なマルコフ決定プロセス(POMDP)は、現実の意思決定と制御の問題に対する柔軟な表現を提供する。 POMDPは、特に状態と観測空間が連続的またはハイブリッドである場合、解決するのが非常に難しい。 本稿では,これらのアルゴリズムが使用する粒子フィルタリング手法の近似誤差を特徴付ける理論を提案する。
  論文  参考訳（メタデータ） (2022-10-10T21:11:55Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  本稿では、時間差学習(TD)による政策評価の世代的視点について考察する。 OS-GPTDアプローチは、状態-逆ペアのシーケンスを観測することにより、与えられたポリシーの値関数を推定するために開発された。 1つの固定カーネルに関連する限られた表現性を緩和するために、GP前の重み付けアンサンブル(E)を用いて代替のスキームを生成する。
  論文  参考訳（メタデータ） (2021-12-01T23:15:09Z)
• Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity [2.685668802278156]
  状態と行動の量子化による標準ボレル MDP のQ-ラーニングが限界に収束することを示す。 本稿では,連続型MDPに対するQ-ラーニングの適用性について,非常に一般的な収束と近似結果を示す。
  論文  参考訳（メタデータ） (2021-11-12T15:47:10Z)
• Monte Carlo Information-Oriented Planning [6.0158981171030685]
  rho-POMDPとして表現された情報収集問題を解決する方法について議論する。 我々はPOMCPアルゴリズムを用いてrho-POMDPのモンテカルロツリー探索を提案する。
  論文  参考訳（メタデータ） (2021-03-21T09:09:27Z)
• Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes [0.0]
  システム力学と測定チャネルモデルが知られていると仮定したPOMDPの計画問題について検討する。 軽度非線形フィルタ安定性条件下で近似的信念モデルに対する最適ポリシーを求める。 また、有限ウィンドウメモリサイズと近似誤差境界を関連づけた収束結果のレートを確立する。
  論文  参考訳（メタデータ） (2020-10-15T00:37:51Z)
• A maximum-entropy approach to off-policy evaluation in average-reward MDPs [54.967872716145656]
  この研究は、無限水平非カウントマルコフ決定過程(MDPs)における関数近似を伴うオフ・ポリティ・アセスメント(OPE)に焦点を当てる。 提案手法は,第1の有限サンプル OPE 誤差境界であり,既存の結果がエピソードおよびディスカウントケースを超えて拡張される。 この結果から,教師あり学習における最大エントロピー的アプローチを並列化して,十分な統計値を持つ指数関数型家族分布が得られた。
  論文  参考訳（メタデータ） (2020-06-17T18:13:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。