論文の概要: Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the Unknown

• arxiv url: http://arxiv.org/abs/2402.08511v1
• Date: Tue, 13 Feb 2024 15:05:54 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-14 15:07:28.518299
• Title: Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the Unknown
• Title（参考訳）: 未知数に着目したモンテカルロ木探索の増幅探索
• Authors: Cedric Derstroff, Jannis Brugger, Jannis Bl\"uml, Mira Mezini, Stefan Kramer, Kristian Kersting
• Abstract要約: モンテカルロ木探索(MCTS)は、探索木の有望なセグメントに焦点を合わせるために、戦略的に計算資源を割り当てる。 提案手法はAmEx-MCTSと呼ばれ,新しいMCTSの定式化を導入することでこの問題を解決する。 実験による評価は,AMEx-MCTSの優れた性能を示し,従来のMCTSと関連するアプローチを実質的なマージンで上回っている。
• 参考スコア（独自算出の注目度）: 19.664506834858244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Monte-Carlo tree search (MCTS) is an effective anytime algorithm with a vast amount of applications. It strategically allocates computational resources to focus on promising segments of the search tree, making it a very attractive search algorithm in large search spaces. However, it often expends its limited resources on reevaluating previously explored regions when they remain the most promising path. Our proposed methodology, denoted as AmEx-MCTS, solves this problem by introducing a novel MCTS formulation. Central to AmEx-MCTS is the decoupling of value updates, visit count updates, and the selected path during the tree search, thereby enabling the exclusion of already explored subtrees or leaves. This segregation preserves the utility of visit counts for both exploration-exploitation balancing and quality metrics within MCTS. The resultant augmentation facilitates in a considerably broader search using identical computational resources, preserving the essential characteristics of MCTS. The expanded coverage not only yields more precise estimations but also proves instrumental in larger and more complex problems. Our empirical evaluation demonstrates the superior performance of AmEx-MCTS, surpassing classical MCTS and related approaches by a substantial margin.
• Abstract（参考訳）: モンテカルロ木探索(MCTS)は、膨大な応用量を持つ実効性のあるアルゴリズムである。 戦略的に計算資源を割り当てて探索木の有望な部分に集中し、大きな探索空間において非常に魅力的な探索アルゴリズムとなる。 しかし、最も有望な道が残っているときに、以前検討した地域を再評価することに限られた資源を浪費することが多い。 提案手法はAmEx-MCTSと呼ばれ,新しいMCTSの定式化を導入することでこの問題を解決する。 AmEx-MCTSの中心となるのは、値更新、訪問カウント更新、ツリー検索中の選択されたパスの分離である。 この分離は、MCTS内の探索・探索バランスと品質指標の両方に対する訪問数の有用性を保っている。 この拡張により、MCTSの本質的な特性を保ちながら、同一の計算資源を用いたより広範な探索が容易となる。 拡張されたカバレッジは、より正確に見積もられるだけでなく、より大きく複雑な問題にも役立ちます。 実験による評価は,AMEx-MCTSの優れた性能を示し,従来のMCTSと関連するアプローチをかなり上回っている。

関連論文リスト

• Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization [18.25487451605638]
  状態占有度を正則化した政策最適化に基づく木探索アルゴリズムを導出し,それをボリュームMCTSと呼ぶ。 本研究では,この状態占有率の正規化目標に対する近似解として,カウントベース探索とサンプリングベース動作計画が導出可能であることを示す。 我々は,いくつかのロボットナビゲーション問題に対して本手法を試行し,Volume-MCTSがAlphaZeroより優れており,長期探査特性が著しく向上していることを見出した。
  論文  参考訳（メタデータ） (2024-07-07T22:58:52Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
  大規模言語モデルは、高度なプロンプト技術で顕著な推論能力に優れています。 近年の研究では、LLMがより困難な推論タスクを解くために受動的木探索を行えるように、検索ロジックを定義するために外部プログラムを活用することが提案されている。 我々は,LLMの自律木探索能力という新しい概念を提案し,正しい解を求める探索軌跡を含む応答を自動生成する。
  論文  参考訳（メタデータ） (2023-10-14T14:14:38Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  連続モンテカルログラフサーチ(Continuous Monte Carlo Graph Search, CMCGS)は、モンテカルログラフサーチ(MCTS)のオンラインプランニングへの拡張である。 CMCGSは、計画中、複数の州で同じ行動方針を共有することで高いパフォーマンスが得られるという洞察を生かしている。 並列化によってスケールアップすることができ、学習力学モデルによる連続制御においてクロスエントロピー法(CEM)よりも優れている。
  論文  参考訳（メタデータ） (2022-10-04T07:34:06Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  行動認識に基づく新規性探索(BR-NS)という,新規性推定の代替手法について議論する。 BR-NSはアーカイブを必要とせず、行動空間で定義できるメトリクスを前提にせず、近隣の検索に依存しません。 我々は、その実現可能性とダイナミクス、および時間複雑性の観点からアーカイブベースのnsよりも潜在的に有利な点について洞察を得るために実験を行う。
  論文  参考訳（メタデータ） (2021-04-08T17:31:34Z)
• Prioritized Architecture Sampling with Monto-Carlo Tree Search [54.72096546595955]
  ワンショットニューラルアーキテクチャサーチ(NAS)法は,検索空間全体を1つのネットワークとして考えることにより,検索コストを大幅に削減する。 本稿では,モンテカルロ木(MCT)をモデルとした探索空間を用いたモンテカルロ木探索(MCTS)に基づくサンプリング戦略について紹介する。 公平な比較のために、CIFAR-10で評価されたマクロ検索空間、すなわちNAS-Bench-MacroのオープンソースNASベンチマークを構築する。
  論文  参考訳（メタデータ） (2021-03-22T15:09:29Z)
• Improved POMDP Tree Search Planning with Prioritized Action Branching [33.94599291823342]
  本稿では,PA-POMCPOWとよばれる手法を提案する。 実験により、PA-POMCPOWは、大きな離散的な作用空間を持つ問題において、既存の最先端の解法よりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-10-07T18:33:57Z)
• Unlucky Explorer: A Complete non-Overlapping Map Exploration [0.949996206597248]
  エージェントがすべてのセルを訪問するハミルトニアンパスを見つけなければならない探索問題として,Maze Dashパズルを紹介した。 提案したモンテカルロ木探索(MCTS)アルゴリズムに最適化を適用し,有望な結果を得た。 比較の結果,MCTSをベースとしたアプローチは,テストケースの小型化と中型化を両立させる手法であることがわかった。
  論文  参考訳（メタデータ） (2020-05-28T17:19:24Z)
• The Second Type of Uncertainty in Monte Carlo Tree Search [2.564530030795554]
  モンテカルロ木探索(MCTS)は、数えきれない不確実性に基づいて、木探索における探索と利用の効率よくバランスをとる。 まず、この2番目の不確実性型が欠如しているため、MCTSはよく知られたスパース探索問題で完全に失敗する可能性があることを示す。 次に、アクションの下のサブツリーのサイズを推定する新しいアルゴリズムを導入し、UCB式におけるこれらの情報を活用して、より直接探索する。
  論文  参考訳（メタデータ） (2020-05-19T09:10:51Z)

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

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