論文の概要: Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning

• arxiv url: http://arxiv.org/abs/2305.09840v2
• Date: Mon, 3 Jul 2023 20:00:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-06 22:18:50.877578
• Title: Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning
• Title（参考訳）: 古典的計画における探索と搾取のスケール適応的バランス
• Authors: Stephen Wissow, Masataro Asai
• Abstract要約: 我々は,MAB文献のより詳細な理論的理解が,既存の計画アルゴリズムの改善に役立つことを示す。 本稿では, UCB1-Normal bandit を用いた MCTS/THTS アルゴリズムである GreedyUCT-Normal を提案する。
• 参考スコア（独自算出の注目度）: 5.025654873456756
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Balancing exploration and exploitation has been an important problem in both game tree search and automated planning. However, while the problem has been extensively analyzed within the Multi-Armed Bandit (MAB) literature, the planning community has had limited success when attempting to apply those results. We show that a more detailed theoretical understanding of MAB literature helps improve existing planning algorithms that are based on Monte Carlo Tree Search (MCTS) / Trial Based Heuristic Tree Search (THTS). In particular, THTS uses UCB1 MAB algorithms in an ad hoc manner, as UCB1's theoretical requirement of fixed bounded support reward distributions is not satisfied within heuristic search for classical planning. The core issue lies in UCB1's lack of adaptations to the different scales of the rewards. We propose GreedyUCT-Normal, a MCTS/THTS algorithm with UCB1-Normal bandit for agile classical planning, which handles distributions with different scales by taking the reward variance into consideration, and resulted in an improved algorithmic performance (more plans found with less node expansions) that outperforms Greedy Best First Search and existing MCTS/THTS-based algorithms (GreedyUCT,GreedyUCT*).
• Abstract（参考訳）: ゲームツリー探索と自動計画において,探索と利用のバランスが重要な問題となっている。 しかし,MAB(Multi-Armed Bandit)の文献では,この問題は広く分析されているものの,これらの結果を適用しようとすると,計画コミュニティは限られた成功を収めている。 さらに,mab文献のより詳細な理論的理解は,モンテカルロ木探索 (mcts) / 試行ベースのヒューリスティック木探索 (thts) に基づく既存の計画アルゴリズムの改善に役立つことを示す。 特に、THTS は UCB1 MAB アルゴリズムをアドホックな方法で使用しており、UTB1 の固定有界サポート報酬分布の理論的な要件は、古典的な計画のヒューリスティックな探索では満たされない。 主な問題は、 UCB1 の報酬の異なるスケールへの適応の欠如にある。 提案するMCTS/THTSアルゴリズムであるGreedyUCT-Normal, UCB1-Normal bandit for agile classical Planningでは,報奨分散を考慮した分散処理を行うとともに,Greedy Best First Searchと既存のMCTS/THTSベースのアルゴリズム(GreedyUCT,GreedyUCT*)より優れたアルゴリズム性能(ノード拡張が少ない計画が多い)を実現した。

関連論文リスト

• Anytime Sequential Halving in Monte-Carlo Tree Search [1.3820916757781068]
  本稿では,任意のタイミングで停止し,良好な結果を返すアルゴリズムの任意のバージョンを提案する。 合成MAB問題と10の異なるボードゲームにおける経験的結果から、アルゴリズムの性能がSequential Halving や UCB1と競合していることが示されている。
  論文  参考訳（メタデータ） (2024-11-11T17:49:47Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• AlphaZeroES: Direct score maximization outperforms planning loss minimization [61.17702187957206]
  実行時の計画では、シングルエージェントとマルチエージェントの両方の設定でエージェントのパフォーマンスが劇的に向上することが示されている。 実行時に計画するアプローチのファミリは、AlphaZeroとその変種で、Monte Carlo Tree Searchと、状態値とアクション確率を予測することによって検索をガイドするニューラルネットワークを使用する。 複数の環境にまたがって、エピソードスコアを直接最大化し、計画損失を最小限に抑えることを示す。
  論文  参考訳（メタデータ） (2024-06-12T23:00:59Z)
• Diverse, Top-k, and Top-Quality Planning Over Simulators [9.924007495979582]
  本稿ではモンテカルロ木探索(MCTS)を用いた新しい代替手法を提案する。 本稿では,事前生成した探索木から最優先の順序で計画の有界集合を抽出する手法と,探索木を通る経路の相対的品質を評価する指標について述べる。 提案手法は,古典的プランナが適用できない領域において,多様かつ高品質なプランセットを生成することができることを示す。
  論文  参考訳（メタデータ） (2023-08-25T02:55:19Z)
• DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization [10.513103815142731]
  PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。 我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
  論文  参考訳（メタデータ） (2023-01-28T17:03:56Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。 性能は不特定な事前条件で優雅に低下することを示す。
  論文  参考訳（メタデータ） (2021-07-03T23:17:26Z)
• Limited depth bandit-based strategy for Monte Carlo planning in continuous action spaces [4.1208902102156015]
  本稿では,階層最適化(HOO)アルゴリズムの限界深度変種であるLD-HOOを提案する。 提案アルゴリズムは,より高速で,よりメモリ効率のよいオリジナルのHOOと同様の累積的後悔を示す。 次に,最適制御問題に対するLD-HOOに基づくモンテカルロ木探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-29T17:30:01Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。 効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。 我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
  論文  参考訳（メタデータ） (2020-06-15T21:36:00Z)

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

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