論文の概要: Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction

• arxiv url: http://arxiv.org/abs/2310.06513v1
• Date: Tue, 10 Oct 2023 10:55:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-11 15:58:42.478310
• Title: Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction
• Title（参考訳）: 確率木状態抽象化によるモンテカルロ木探索の高速化
• Authors: Yangqing Fu, Ming Sun, Buqing Nie, Yue Gao
• Abstract要約: 我々はモンテカルロ木探索(MCTS)の探索効率を向上させるための新しい確率木状態抽象化(PTSA)アルゴリズムを提案する。 経路遷移性を持つ一般的なツリー状態抽象化が定義され、さらに、アグリゲーションステップ中に少ないミスに対して確率木状態抽象化が提案される。 実験結果から,提案手法は検索空間を10%-45%削減した最先端アルゴリズムの学習過程を高速化できることが示された。
• 参考スコア（独自算出の注目度）: 11.49169644917995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Monte Carlo Tree Search (MCTS) algorithms such as AlphaGo and MuZero have achieved superhuman performance in many challenging tasks. However, the computational complexity of MCTS-based algorithms is influenced by the size of the search space. To address this issue, we propose a novel probability tree state abstraction (PTSA) algorithm to improve the search efficiency of MCTS. A general tree state abstraction with path transitivity is defined. In addition, the probability tree state abstraction is proposed for fewer mistakes during the aggregation step. Furthermore, the theoretical guarantees of the transitivity and aggregation error bound are justified. To evaluate the effectiveness of the PTSA algorithm, we integrate it with state-of-the-art MCTS-based algorithms, such as Sampled MuZero and Gumbel MuZero. Experimental results on different tasks demonstrate that our method can accelerate the training process of state-of-the-art algorithms with 10%-45% search space reduction.
• Abstract（参考訳）: AlphaGoやMuZeroのようなモンテカルロ木探索(MCTS)アルゴリズムは多くの課題において超人的性能を達成した。 しかし、MCTSに基づくアルゴリズムの計算複雑性は、探索空間のサイズに影響される。 そこで本研究では,MCTSの探索効率を向上させるために,新しい確率木状態抽象化(PTSA)アルゴリズムを提案する。 経路遷移性を持つ一般的なツリー状態抽象化を定義する。 さらに, 確率木状態の抽象化は, 集約過程における誤りが少ないために提案されている。 さらに、推移性と凝集誤差境界の理論的保証を正当化する。 PTSAアルゴリズムの有効性を評価するため,Sampred MuZeroやGumbel MuZeroといった最先端のMCTSベースのアルゴリズムと統合した。 異なるタスクにおける実験結果は,10%-45%の探索空間削減で最先端アルゴリズムの学習プロセスを高速化できることを示した。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq [4.987556615430226]
  本稿では,確実な確率で最適化された量子最小探索アルゴリズムを提案する。 性能評価の結果,本アルゴリズムはDHAアルゴリズムよりも精度と効率が高いことがわかった。
  論文  参考訳（メタデータ） (2023-09-25T14:07:27Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究 まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。 次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
  論文  参考訳（メタデータ） (2023-06-21T16:04:03Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial Optimization Problems [0.0]
  本稿では、マルコフ連鎖からSAに基づく奥行き制限木への探索空間の拡大による探索アルゴリズムを提案する。 それぞれのイテレーションにおいて、このアルゴリズムは、先を見据えて、木に沿って探索することで、実現可能な探索空間内で最高の準最適解を選択する」。 以上の結果から,IsingのNP最適化問題に対する高次木探索戦略は,より少ないエポックの範囲で解決可能であることが示唆された。
  論文  参考訳（メタデータ） (2022-03-09T10:07:26Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)

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

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