論文の概要: Bilevel MCTS for Amortized O(1) Node Selection in Classical Planning

• arxiv url: http://arxiv.org/abs/2508.08385v1
• Date: Mon, 11 Aug 2025 18:12:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-13 21:07:34.205662
• Title: Bilevel MCTS for Amortized O(1) Node Selection in Classical Planning
• Title（参考訳）: 記憶型O(1)ノード選択のための古典的計画におけるバイレベルMCTS
• Authors: Masataro Asai,
• Abstract要約: マルチアーマッド・バンドイット(MAB)をベースとしたモンテカルロ木探索(MCTS)の効率的な実装について検討した。 MCTSの弱点のひとつは、次にどのノードを拡張するかを決めるのにかなりの時間を費やしていることだ。 本稿では,各葉ノードから最優先探索を行うMCTSの2段階修正を提案し,拡張予算は$d$に比例する。
• 参考スコア（独自算出の注目度）: 1.9580473532948401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study an efficient implementation of Multi-Armed Bandit (MAB)-based Monte-Carlo Tree Search (MCTS) for classical planning. One weakness of MCTS is that it spends a significant time deciding which node to expand next. While selecting a node from an OPEN list with $N$ nodes has $O(1)$ runtime complexity with traditional array-based priority-queues for dense integer keys, the tree-based OPEN list used by MCTS requires $O(\log N)$, which roughly corresponds to the search depth $d$. In classical planning, $d$ is arbitrarily large (e.g., $2^k-1$ in $k$-disk Tower-of-Hanoi) and the runtime for node selection is significant, unlike in game tree search, where the cost is negligible compared to the node evaluation (rollouts) because $d$ is inherently limited by the game (e.g., $d\leq 361$ in Go). To improve this bottleneck, we propose a bilevel modification to MCTS that runs a best-first search from each selected leaf node with an expansion budget proportional to $d$, which achieves amortized $O(1)$ runtime for node selection, equivalent to the traditional queue-based OPEN list. In addition, we introduce Tree Collapsing, an enhancement that reduces action selection steps and further improves the performance.
• Abstract（参考訳）: マルチアーマド・バンドイット(MAB)をベースとしたモンテカルロ木探索(MCTS)を,古典的計画のための効率的な実装として検討した。 MCTSの弱点のひとつは、次にどのノードを拡張するかを決めるのにかなりの時間を費やしていることだ。 N$ノードでOPENリストからノードを選択すると、高密度整数キーに対する従来の配列ベースの優先度キューと$O(1)$ランタイムの複雑さを持つが、MCTSが使用するツリーベースのOPENリストは$O(\log N)$で、検索深度$d$とほぼ一致する。 古典的な計画では、$d$は任意に大きい(例えば、$2^k-1$ in $k$-disk Tower-of-Hanoi)。 このボトルネックを改善するために,従来のキューベースOPENリストと等価なノード選択のための$O(1)$ランタイムを実現する拡張予算を$d$に比例して,選択した葉ノードからベストファースト検索を実行するMCTSのバイレベル修正を提案する。 さらに、アクション選択のステップを減らし、パフォーマンスをさらに向上する拡張であるTree Collapsingを導入する。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
  我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。 時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。 この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
  論文  参考訳（メタデータ） (2024-06-07T11:40:54Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• End-to-end Feature Selection Approach for Learning Skinny Trees [13.388576838688202]
  木アンサンブルにおける特徴選択のための最適化に基づく新しい手法を提案する。 Skinny Treesは、ツリーアンサンブルの機能選択のためのエンドツーエンドツールキットである。
  論文  参考訳（メタデータ） (2023-10-28T00:15:10Z)
• Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
  現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。 孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
  論文  参考訳（メタデータ） (2023-09-29T19:55:56Z)
• On the Power of Learning-Augmented Search Trees [7.325724756104182]
  本稿では,Treapsを用いた学習強化二分探索木(BST)について,慎重に設計した優先順位で検討する。 その結果、各項目の深さが予測重量$w_x$によって決定される単純な探索木となる。
  論文  参考訳（メタデータ） (2022-11-16T22:50:40Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization [61.20639338417576]
  グラフニューラルネットワーク(GNN)は、隣接するノードを集約することでノードの表現を学習する。 オーバースムーシングは、レイヤーの数が増えるにつれてGNNのパフォーマンスが制限される重要な問題のひとつです。 2つのオーバースムースなメトリクスと新しいテクニック、すなわち微分可能群正規化(DGN)を導入する。
  論文  参考訳（メタデータ） (2020-06-12T07:18:02Z)

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

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