論文の概要: The Second Type of Uncertainty in Monte Carlo Tree Search
- arxiv url: http://arxiv.org/abs/2005.09645v1
- Date: Tue, 19 May 2020 09:10:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-01 14:08:03.384499
- Title: The Second Type of Uncertainty in Monte Carlo Tree Search
- Title（参考訳）: モンテカルロ木探索における2番目の不確かさ
- Authors: Thomas M Moerland, Joost Broekens, Aske Plaat, Catholijn M Jonker
- Abstract要約: モンテカルロ木探索(MCTS)は、数えきれない不確実性に基づいて、木探索における探索と利用の効率よくバランスをとる。
まず、この2番目の不確実性型が欠如しているため、MCTSはよく知られたスパース探索問題で完全に失敗する可能性があることを示す。
次に、アクションの下のサブツリーのサイズを推定する新しいアルゴリズムを導入し、UCB式におけるこれらの情報を活用して、より直接探索する。
- 参考スコア（独自算出の注目度）: 2.564530030795554
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Monte Carlo Tree Search (MCTS) efficiently balances exploration and
exploitation in tree search based on count-derived uncertainty. However, these
local visit counts ignore a second type of uncertainty induced by the size of
the subtree below an action. We first show how, due to the lack of this second
uncertainty type, MCTS may completely fail in well-known sparse exploration
problems, known from the reinforcement learning community. We then introduce a
new algorithm, which estimates the size of the subtree below an action, and
leverages this information in the UCB formula to better direct exploration.
Subsequently, we generalize these ideas by showing that loops, i.e., the
repeated occurrence of (approximately) the same state in the same trace, are
actually a special case of subtree depth variation. Testing on a variety of
tasks shows that our algorithms increase sample efficiency, especially when the
planning budget per timestep is small.
- Abstract（参考訳）: モンテカルロ木探索 (monte carlo tree search, mcts) は、木探索における探索と搾取の効率良くバランスをとる。
しかし、これらのローカル訪問数は、アクション以下のサブツリーのサイズによって引き起こされる第2のタイプの不確実性を無視します。
我々はまず,この第2の不確実性タイプが欠如していることから,強化学習コミュニティでよく知られたスパース探索問題において,mctsが完全に失敗する可能性を示す。
次に、アクションの下のサブツリーのサイズを推定する新しいアルゴリズムを導入し、UCB式におけるこれらの情報を利用して直接探索する。
その後、これらのアイデアを一般化し、ループ、すなわち、同じトレースにおける同じ状態の(およそ)繰り返し発生は、実際には部分木の深さ変化の特別な場合であることを示す。
さまざまなタスクのテストでは,特に時間単位の計画予算が小さい場合には,アルゴリズムのサンプリング効率が向上することが示された。
関連論文リスト
- 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) - Depth-Bounded Epistemic Planning [50.42592219248395]
本稿では,動的てんかん論理に基づく新しい計画法を提案する。
新規性は、計画エージェントの推論の深さを上界bに制限することである。
推論深度の境界b内における解を持つ計画タスクに関して、完全なものであることを示す。
論文 参考訳（メタデータ） (2024-06-03T09:30:28Z) - Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the
Unknown [19.664506834858244]
モンテカルロ木探索(MCTS)は、探索木の有望なセグメントに焦点を合わせるために、戦略的に計算資源を割り当てる。
提案手法はAmEx-MCTSと呼ばれ,新しいMCTSの定式化を導入することでこの問題を解決する。
実験による評価は,AMEx-MCTSの優れた性能を示し,従来のMCTSと関連するアプローチを実質的なマージンで上回っている。
論文 参考訳（メタデータ） (2024-02-13T15:05:54Z) - 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) - Branching Time Active Inference: the theory and its generality [3.1542695050861544]
本稿では,構造学習問題として,木探索と能動推論を統合することを目的とした代替フレームワークを提案する。
第1は期待される自由エネルギーを前方に伝播し、第2は後方に伝搬する。
そして, 前向きと後向きの伝搬がそれぞれ, 活発な推論と洗練された推論に関係していることを示し, これら2つの計画戦略の違いを明らかにする。
論文 参考訳（メタデータ） (2021-11-22T10:56:03Z) - Complex Event Forecasting with Prediction Suffix Trees: Extended
Technical Report [70.7321040534471]
複合イベント認識(CER)システムは、イベントのリアルタイムストリーム上のパターンを"即時"検出する能力によって、過去20年間に人気が高まっている。
このような現象が実際にCERエンジンによって検出される前に、パターンがいつ発生するかを予測する方法が不足している。
複雑なイベント予測の問題に対処しようとする形式的なフレームワークを提案する。
論文 参考訳（メタデータ） (2021-09-01T09:52:31Z) - Probabilistic DAG Search [29.47649645431227]
探索空間の潜伏構造を利用して探索木間で情報を共有するための確率的フレームワークを開発する。
我々は、Tic-Tac-Toeの既存の非確率的代替品と特徴選択アプリケーションとを比較検討するアルゴリズムを実証的に見出した。
論文 参考訳（メタデータ） (2021-06-16T11:35:19Z) - Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。
RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。
我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
論文 参考訳（メタデータ） (2021-06-02T01:37:52Z) - Neural Pruning via Growing Regularization [82.9322109208353]
プルーニングの2つの中心的な問題:プルーニングのスケジュールと重み付けの重要度だ。
具体的には, ペナルティ要因が増大するL2正規化変種を提案し, 精度が著しく向上することを示した。
提案アルゴリズムは,構造化プルーニングと非構造化プルーニングの両方において,大規模データセットとネットワークの実装が容易かつスケーラブルである。
論文 参考訳（メタデータ） (2020-12-16T20:16:28Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。