論文の概要: Anytime Sequential Halving in Monte-Carlo Tree Search

• arxiv url: http://arxiv.org/abs/2411.07171v1
• Date: Mon, 11 Nov 2024 17:49:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-12 14:11:29.998558
• Title: Anytime Sequential Halving in Monte-Carlo Tree Search
• Title（参考訳）: モンテカルロ木探索における逐次Halving
• Authors: Dominic Sagers, Mark H. M. Winands, Dennis J. N. J. Soemers,
• Abstract要約: 本稿では,任意のタイミングで停止し,良好な結果を返すアルゴリズムの任意のバージョンを提案する。 合成MAB問題と10の異なるボードゲームにおける経験的結果から、アルゴリズムの性能がSequential Halving や UCB1と競合していることが示されている。
• 参考スコア（独自算出の注目度）: 1.3820916757781068
• License:
• Abstract: Monte-Carlo Tree Search (MCTS) typically uses multi-armed bandit (MAB) strategies designed to minimize cumulative regret, such as UCB1, as its selection strategy. However, in the root node of the search tree, it is more sensible to minimize simple regret. Previous work has proposed using Sequential Halving as selection strategy in the root node, as, in theory, it performs better with respect to simple regret. However, Sequential Halving requires a budget of iterations to be predetermined, which is often impractical. This paper proposes an anytime version of the algorithm, which can be halted at any arbitrary time and still return a satisfactory result, while being designed such that it approximates the behavior of Sequential Halving. Empirical results in synthetic MAB problems and ten different board games demonstrate that the algorithm's performance is competitive with Sequential Halving and UCB1 (and their analogues in MCTS).
• Abstract（参考訳）: モンテカルロ木探索(MCTS)は、通常、UCB1のような累積的後悔を最小限に抑えるために設計されたマルチアーム・バンディット(MAB)戦略を選択戦略として用いている。 しかし、探索木の根ノードでは、単純な後悔を最小限に抑えるのがより賢明である。 これまでの研究では、ルートノードの選択戦略としてシークエンシャル・ハルヴィング(Sequential Halving)を用いることが提案されてきた。 しかし、シークエンシャル・ハルヴィングは、しばしば非現実的なイテレーションの予算を定める必要がある。 本稿では,任意のタイミングで停止し,良好な結果を返すことができるアルゴリズムを,逐次Halvingの挙動を近似するように設計した。 合成MAB問題と10の異なるボードゲームにおける経験的な結果から、アルゴリズムの性能はSequential Halvingや UCB1(MCTSの類似)と競合することが示された。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction [11.49169644917995]
  我々はモンテカルロ木探索(MCTS)の探索効率を向上させるための新しい確率木状態抽象化(PTSA)アルゴリズムを提案する。 経路遷移性を持つ一般的なツリー状態抽象化が定義され、さらに、アグリゲーションステップ中に少ないミスに対して確率木状態抽象化が提案される。 実験結果から,提案手法は検索空間を10%-45%削減した最先端アルゴリズムの学習過程を高速化できることが示された。
  論文  参考訳（メタデータ） (2023-10-10T10:55:12Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
  我々は、マルコフ連鎖モンテカルロ(MCMC)を本質的に並列なアルゴリズムであるシーケンシャルモンテカルロ(SMC)に置き換えることを提案する。 実験により、SMCと進化的アルゴリズム(EA)を組み合わせることで、MCMCの100倍のイテレーションでより正確な結果が得られることが示された。
  論文  参考訳（メタデータ） (2023-05-30T06:17:35Z)
• Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning [1.6574413179773757]
  我々は,MAB文献のより詳細な理論的理解が,既存の計画アルゴリズムの改善に役立つことを示す。 本稿では, UCB1-Normal bandit を用いた MCTS/THTS アルゴリズムである GreedyUCT-Normal を提案する。
  論文  参考訳（メタデータ） (2023-05-16T22:46:37Z)
• Towards Correlated Sequential Rules [4.743965372344134]
  高実用性シーケンシャルルールマイニング(HUSRM)は、結果のシーケンシャルパターンの発生を予測できる信頼度や確率を調査するために設計された。 HUSRMと呼ばれる既存のアルゴリズムは、生成されたシーケンシャルルール間の相関を無視しながら、すべての許容ルールを抽出することに制限されている。 本稿では,HUSRMに相関の概念を統合するために,CoUSR(Cocorlation High-utility Sequence Rule Minr)と呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-27T17:27:23Z)
• TaSPM: Targeted Sequential Pattern Mining [53.234101208024335]
  本稿では,高速CM-SPAMアルゴリズムに基づく汎用フレームワークTaSPMを提案する。 また,マイニングプロセスにおける無意味な操作を減らすために,いくつかのプルーニング戦略を提案する。 実験の結果,新たなターゲットマイニングアルゴリズムであるTaSPMは実行時間を短縮し,メモリ消費を低減できることがわかった。
  論文  参考訳（メタデータ） (2022-02-26T17:49:47Z)
• Reconstructing Sparse Signals via Greedy Monte-Carlo Search [6.660458629649825]
  高次元環境下でスパース信号を再構成するモンテカルロ法を提案する。 欲求モンテカルロ探索アルゴリズムは、欲求モンテカルロ探索アルゴリズム (greedy Monte-Carlo search algorithm) と呼ばれる。
  論文  参考訳（メタデータ） (2020-08-07T13:36:57Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。 効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。 我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
  論文  参考訳（メタデータ） (2020-06-15T21:36:00Z)
• Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
  Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 後悔の最小化手法を開発するための新しい枠組みを開発する。 MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
  論文  参考訳（メタデータ） (2020-02-19T23:05:41Z)

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

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