論文の概要: Learning to Stop: Dynamic Simulation Monte-Carlo Tree Search
- arxiv url: http://arxiv.org/abs/2012.07910v1
- Date: Mon, 14 Dec 2020 19:49:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-08 19:02:57.160081
- Title: Learning to Stop: Dynamic Simulation Monte-Carlo Tree Search
- Title(参考訳): learning to stop: dynamic simulation monte-carlo tree search
- Authors: Li-Cheng Lan, Meng-Yu Tsai, Ti-Rong Wu, I-Chen Wu, Cho-Jui Hsieh
- Abstract要約: モンテカルロ木探索(MCTS)は、囲碁やアタリゲームなど多くの領域で最先端の結果を得た。
我々は,現在の検索状況の不確かさを予測し,その結果を用いて検索をやめるべきかどうかを判断することで,この目標を達成することを提案する。
- 参考スコア(独自算出の注目度): 66.34387649910046
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Monte Carlo tree search (MCTS) has achieved state-of-the-art results in many
domains such as Go and Atari games when combining with deep neural networks
(DNNs). When more simulations are executed, MCTS can achieve higher performance
but also requires enormous amounts of CPU and GPU resources. However, not all
states require a long searching time to identify the best action that the agent
can find. For example, in 19x19 Go and NoGo, we found that for more than half
of the states, the best action predicted by DNN remains unchanged even after
searching 2 minutes. This implies that a significant amount of resources can be
saved if we are able to stop the searching earlier when we are confident with
the current searching result. In this paper, we propose to achieve this goal by
predicting the uncertainty of the current searching status and use the result
to decide whether we should stop searching. With our algorithm, called Dynamic
Simulation MCTS (DS-MCTS), we can speed up a NoGo agent trained by AlphaZero
2.5 times faster while maintaining a similar winning rate. Also, under the same
average simulation count, our method can achieve a 61% winning rate against the
original program.
- Abstract(参考訳): モンテカルロ木探索(MCTS)は、ディープニューラルネットワーク(DNN)と組み合わせることで、GoやAtariゲームのような多くのドメインで最先端の結果を得た。
より多くのシミュレーションが実行されると、MCTSは高いパフォーマンスを達成するが、大量のCPUとGPUリソースを必要とする。
しかし、全ての州が、エージェントが発見できる最良の行動を特定するのに長い時間を必要とするわけではない。
例えば、19x19 GoとNoGoでは、半数以上の州で、DNNが予測する最良のアクションは、2分間検索しても変わっていないことが分かりました。
これは、現在の検索結果に自信がある場合に、早期に検索を止めることができれば、かなりの量のリソースを節約できることを意味します。
本稿では,現在の検索状況の不確かさを予測し,その結果を用いて検索をやめるべきかどうかを判断することで,この目標を達成することを提案する。
我々のアルゴリズムであるDynamic Simulation MCTS (DS-MCTS)では、AlphaZeroがトレーニングしたNoGoエージェントを2.5倍高速化し、同様の勝利率を維持することができる。
また,同じ平均シミュレーション数で,本手法は元のプログラムに対して61%の勝利率を達成することができる。
関連論文リスト
- Tree Search for Language Model Agents [69.43007235771383]
対話型Web環境での探索と多段階計画を行うために,LMエージェントの推論時探索アルゴリズムを提案する。
我々のアプローチは、実環境空間内で機能する最優先木探索の一形態である。
現実的なWebタスクにおいて有効性を示すLMエージェントのための最初の木探索アルゴリズムである。
論文 参考訳(メタデータ) (2024-07-01T17:07:55Z) - AlphaZeroES: Direct score maximization outperforms planning loss minimization [61.17702187957206]
実行時の計画では、シングルエージェントとマルチエージェントの両方の設定でエージェントのパフォーマンスが劇的に向上することが示されている。
実行時に計画するアプローチのファミリは、AlphaZeroとその変種で、Monte Carlo Tree Searchと、状態値とアクション確率を予測することによって検索をガイドするニューラルネットワークを使用する。
複数の環境にまたがって、エピソードスコアを直接最大化し、計画損失を最小限に抑えることを示す。
論文 参考訳(メタデータ) (2024-06-12T23:00:59Z) - Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions [89.89612827542972]
本稿では,モンテカルロ木探索 (MCTS) の変種を提案する。
9倍のGoボードゲームとAtariゲームの性能と計算結果を評価した。
実験の結果,提案手法は,平均検索時間50%以下で,元の検索アルゴリズムに匹敵する性能が得られることがわかった。
論文 参考訳(メタデータ) (2022-10-23T06:39:20Z) - Batch Monte Carlo Tree Search [9.114710429587479]
この性質に基づいて,バッチ推論を用いたモンテカルロ木探索アルゴリズムを提案する。
転置テーブルは推論の結果を含むが、検索ツリーはモンテカルロツリー検索の統計情報を含む。
また、検索を改善する複数のアルゴリズムを分析することも提案している:$mu$ fpu、仮想平均、反復、第2の移動は続く。
論文 参考訳(メタデータ) (2021-04-09T09:54:21Z) - Dual Monte Carlo Tree Search [0.0]
我々はDual MCTSが、様々な対称ゲームや非対称ゲームにおいて最も広く使われているニューラルMCTSアルゴリズムであるAlphaZeroよりも優れていることを示す。
デュアルMCTSは、2つの異なる検索木、単一のディープニューラルネットワーク、PUCB、スライドウィンドウ、およびepsilon-greedyアルゴリズムの組み合わせを使用して検索木のための新しい更新技術を使用しています。
論文 参考訳(メタデータ) (2021-03-21T23:34:11Z) - Resource Allocation in Multi-armed Bandit Exploration: Overcoming
Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。
特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文 参考訳(メタデータ) (2020-10-31T18:19:29Z) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳(メタデータ) (2020-06-15T21:36:00Z) - Single-Agent Optimization Through Policy Iteration Using Monte-Carlo
Tree Search [8.22379888383833]
モンテカルロ・ツリー・サーチ(MCTS)と深部強化学習の組み合わせは,2プレイヤー完全情報ゲームにおける最先端の手法である。
本稿では,MCTS の変種を利用した探索アルゴリズムについて述べる。1) 潜在的に有界な報酬を持つゲームに対する新たなアクション値正規化機構,2) 効果的な探索並列化を可能にする仮想損失関数の定義,3) 世代ごとのセルフプレイによって訓練されたポリシーネットワークについて述べる。
論文 参考訳(メタデータ) (2020-05-22T18:02:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。