論文の概要: On Effective Parallelization of Monte Carlo Tree Search
- arxiv url: http://arxiv.org/abs/2006.08785v2
- Date: Sun, 4 Oct 2020 21:13:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 02:23:15.509859
- Title: On Effective Parallelization of Monte Carlo Tree Search
- Title（参考訳）: モンテカルロ木探索の効果的な並列化について
- Authors: Anji Liu and Yitao Liang and Ji Liu and Guy Van den Broeck and Jianshu
Chen
- Abstract要約: モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
- 参考スコア（独自算出の注目度）: 51.15940034629022
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite its groundbreaking success in Go and computer games, Monte Carlo Tree
Search (MCTS) is computationally expensive as it requires a substantial number
of rollouts to construct the search tree, which calls for effective
parallelization. However, how to design effective parallel MCTS algorithms has
not been systematically studied and remains poorly understood. In this paper,
we seek to lay its first theoretical foundation, by examining the potential
performance loss caused by parallelization when achieving a desired speedup. In
particular, we discover the necessary conditions of achieving a desirable
parallelization performance, and highlight two of their practical benefits.
First, by examining whether existing parallel MCTS algorithms satisfy these
conditions, we identify key design principles that should be inherited by
future algorithms, for example tracking the unobserved samples (used in WU-UCT
(Liu et al., 2020)). We theoretically establish this essential design
facilitates $\mathcal{O} ( \ln n + M / \sqrt{\ln n} )$ cumulative regret when
the maximum tree depth is 2, where $n$ is the number of rollouts and $M$ is the
number of workers. A regret of this form is highly desirable, as compared to
$\mathcal{O} ( \ln n )$ regret incurred by a sequential counterpart, its excess
part approaches zero as $n$ increases. Second, and more importantly, we
demonstrate how the proposed necessary conditions can be adopted to design more
effective parallel MCTS algorithms. To illustrate this, we propose a new
parallel MCTS algorithm, called BU-UCT, by following our theoretical
guidelines. The newly proposed algorithm, albeit preliminary, out-performs four
competitive baselines on 11 out of 15 Atari games. We hope our theoretical
results could inspire future work of more effective parallel MCTS.
- Abstract（参考訳）: Goやコンピュータゲームで成功しているにもかかわらず、Monte Carlo Tree Search (MCTS)は、効率的な並列化を要求する検索ツリーを構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
しかし、効果的な並列MCTSアルゴリズムの設計方法は体系的に研究されておらず、まだ理解されていない。
本稿では,所望の高速化を達成する際に並列化によって生じる潜在的な性能損失を調べることにより,最初の理論的基礎を築こうとする。
特に、望ましい並列化性能を達成するために必要な条件を発見し、その実用上の利点の2つを強調する。
まず、既存の並列MCTSアルゴリズムがこれらの条件を満たすかどうかを調べることにより、将来のアルゴリズムによって継承されるべき重要な設計原則を同定する。
この本質的な設計を理論的に確立すると、最大木深さが 2 であるとき、$\mathcal{o} ( \ln n + m / \sqrt{\ln n} )$ cumulative regret となり、ここで $n$ はロールアウト数、$m$ はワーカー数である。
この形式の後悔は非常に望ましいものであり、$\mathcal{O} ( \ln n )$ regret がシーケンシャルな関係によって引き起こされるのに対して、その余剰部分は $n$ の増加とともに 0 に近づく。
第2に,より効率的な並列mctsアルゴリズムを設計するために,提案する条件をどのように適用できるかを示す。
これを説明するために,我々は理論ガイドラインに従うことにより,新しい並列mctsアルゴリズムであるbu-uctを提案する。
新たに提案されたアルゴリズムは、15のatariゲームのうち11ゲームで4つのベースラインを上回っている。
我々の理論結果が、より効果的な並列MCTSの将来的な研究を刺激することを期待している。
関連論文リスト
- LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳（メタデータ） (2024-06-29T05:14:04Z) - Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning [15.46907000938726]
協調型マルチエージェント強化学習(MARL)における確率的ランダム化探索に関する最初の研究について述べる。
並列マルコフ決定過程(MDP)におけるランダム化探索のための統一されたアルゴリズムフレームワークと,2つのトンプソンサンプリング型アルゴリズムであるCoopTS-PHEとCoopTS-LMCを提案する。
提案手法は, 深層探査問題 (textiti.e.$N$-chain) , ビデオゲーム, エネルギーシステムにおける実世界の問題などを含む, 並列RL環境における提案手法の評価を行う。
論文 参考訳（メタデータ） (2024-04-16T17:01:38Z) - No Compromise in Solution Quality: Speeding Up Belief-dependent Continuous POMDPs via Adaptive Multilevel Simplification [6.300736240833814]
一般的な信念に依存した報酬を持つ継続的POMDPは、オンラインでの解決が難しいことで知られている。
与えられた外部構築された信条木の設定に対する適応的多レベル単純化の完全証明可能な理論を提案する。
我々は,信念に依存した報酬で,POMDPのオンラインプランニングを高速化する3つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-16T10:59:22Z) - Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions [89.89612827542972]
本稿では,モンテカルロ木探索 (MCTS) の変種を提案する。
9倍のGoボードゲームとAtariゲームの性能と計算結果を評価した。
実験の結果,提案手法は,平均検索時間50%以下で,元の検索アルゴリズムに匹敵する性能が得られることがわかった。
論文 参考訳（メタデータ） (2022-10-23T06:39:20Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。
LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
論文 参考訳（メタデータ） (2021-11-15T17:10:40Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Practical Massively Parallel Monte-Carlo Tree Search Applied to
Molecular Design [7.992550355579791]
我々は,1000の作業規模で効率的に動作する並列モンテカルロ木探索法(MP-MCTS)を提案し,分子設計に適用する。
MP-MCTSは大規模に検索品質を維持し,256CPUコア上でわずか10分間MP-MCTSを実行することで,42時間動作した非並列MCTSと類似のスコアを持つ候補分子を得た。
論文 参考訳（メタデータ） (2020-06-18T13:23:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。