論文の概要: Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation

• arxiv url: http://arxiv.org/abs/2609.19956v1
• Date: Thu, 17 Sep 2026 09:28:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:54.202859
• Title: Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation
• Title（参考訳）: グラフベース確率パワーUCT:パワー平均推定を用いたモンテカルログラフ探索
• Abstract要約: ツリーベースのMonte-Carlo Tree Searchは、異なる軌跡から到達した時に同じ状態を複製する。 グラフベース最適電力UCTを導入し、同じ計画深度で到達した状態を共有すると同時に、異なる深さで到達した状態の別々の値を保持する。
• 参考スコア（独自算出の注目度）: 1.175956452196938
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tree-based Monte-Carlo Tree Search (MCTS) duplicates the same state when it is reached through different trajectories, which can waste simulations in stochastic MDPs. We introduce Graph-Based Stochastic-Power-UCT (GS-Power-UCT), which shares states reached at the same planning depth while keeping separate values for states reached at different depths. This design applies to general stochastic MDPs, including problems with cycles. We prove that for a fixed planning horizon, the root estimate converges to the finite-horizon value at rate $O(n^{-1/2})$, matching tree-based Stochastic-Power-UCT while reusing samples across shared states. We also study two full-state variants: GS-Power-UCT-F, which stores one node per physical state to increase sample sharing but may mix values from different remaining horizons, and GS-Power-UCT-F$^+$, which uses an adaptive horizon to control this bias. The latter converges to $V^{\star}(s_0)$, the optimal infinite-horizon discounted value at the root state $s_0$, when the remaining cross-depth gap vanishes. Experiments on stochastic planning benchmarks show improved sample efficiency over tree-based and graph-based baselines.
• Abstract（参考訳）: 木に基づくモンテカルロ木探索 (MCTS) は, 確率的MDPのシミュレーションを無駄にすることなく, 異なる軌道を通った場合と同じ状態を再現する。 グラフベースの確率パワーUCT(GS-Power-UCT)を導入し、異なる深さで到達した状態の異なる値を維持しながら、同じ計画深度で到達した状態を共有する。 この設計は、サイクルの問題を含む一般確率 MDP に適用される。 固定された計画地平線に対して、根の推定値は、共有状態のサンプルを再利用しながら、木に基づく確率-パワー-UCTと一致する速度$O(n^{-1/2})$で有限水平値に収束することを示す。 また、サンプル共有を増やすために物理状態当たり1ノードを格納するGS-Power-UCT-Fと、このバイアスを制御するために適応地平線を利用するGS-Power-UCT-F$+$の2つのフルステート変種についても検討した。 後者は$V^{\star}(s_0)$に収束し、根の状態$s_0$の最適無限水平割引値は、残りの深度ギャップが消える。 確率的計画ベンチマークの実験では、木ベースのベースラインとグラフベースのベースラインよりもサンプル効率が改善された。

関連論文リスト

• Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics [5.844015313757267]
  ランダム・スキャン・ガウス・グラウバー力学の1つの軌道からグラフの正確な復元について検討する。 混合のない2つのアルゴリズムを提案し、情報理論の下界の2$依存を実現する。
  論文  参考訳（メタデータ） (2026-07-20T22:44:45Z)
• Posterior Augmented Flow Matching [64.1559809786948]
  後拡張フローマッチング(PAFM)はフローマッチング(FM)の一般化である PAFMは、異なるモデルスケールで最大3.4FID50KでFMよりも改善されていることを示す。
  論文  参考訳（メタデータ） (2026-05-01T17:59:59Z)
• High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking [69.90407799170687]
  分散最適化における高確率収束保証について検討する。 その結果, 地平線上の条件は, 比較時間と同一であることがわかった。
  論文  参考訳（メタデータ） (2026-04-30T22:45:21Z)
• Spectral gap of Metropolis-within-Gibbs under log-concavity [1.4466802614938334]
  MwG(Metropolis-within-Gibbs)アルゴリズムは、高次元分布からサンプリングするためのマルコフ連鎖モンテカルロ法である。 我々は,MwGをRandom Walk Metropolis (RWM) 更新を用いて検討し,目標の条件変動に合わせるように調整された提案分散を用いて検討した。 その結果,MwGは分散適応型提案とかなり高速な混合が可能であり,その混合性能はギブスサンプリング器よりもわずかに劣ることがわかった。
  論文  参考訳（メタデータ） (2025-09-30T12:31:22Z)
• Entropy contraction of the Gibbs sampler under log-concavity [0.16385815610837165]
  ランダムスキャンギブスサンプリング器は相対エントロピーで収縮し、関連する収縮率を鋭く評価する。 我々の手法は多用途であり、Metropolis-within-GibbsスキームやHit-and-Runアルゴリズムにまで拡張されている。
  論文  参考訳（メタデータ） (2024-10-01T16:50:36Z)
• Power Mean Estimation in Stochastic Monte-Carlo Tree_Search [25.058008522872747]
  Monte-Carlo Tree Search (MCTS)は、Monte-Carloサンプリングとフォワードツリー検索を組み合わせたオンラインプランニングのための広く使われている戦略である。 UCTの理論的基礎は対数的ボーナス項の誤りにより不完全である。 本稿では,MDPに適したパワー平均推定器を用いたアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-04T11:56:37Z)
• Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
  非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。 対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。 我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
  論文  参考訳（メタデータ） (2024-05-27T00:53:18Z)
• Better Training of GFlowNets with Local Credit and Incomplete Trajectories [81.14310509871935]
  エネルギー関数が終端状態だけでなく中間状態にも適用できる場合を考える。 これは例えば、エネルギー関数が加法的であるときに達成され、軌道に沿って項が利用できる。 これにより、不完全なトラジェクトリであってもパラメータの更新に適用可能なトレーニングの目標が可能になる。
  論文  参考訳（メタデータ） (2023-02-03T12:19:42Z)
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
  分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。 本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。 総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
  論文  参考訳（メタデータ） (2021-02-09T02:44:24Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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