論文の概要: 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*)より優れたアルゴリズム性能(ノード拡張が少ない計画が多い)を実現した。
関連論文リスト
- Diverse, Top-k, and Top-Quality Planning Over Simulators [9.924007495979582]
本稿ではモンテカルロ木探索(MCTS)を用いた新しい代替手法を提案する。
本稿では,事前生成した探索木から最優先の順序で計画の有界集合を抽出する手法と,探索木を通る経路の相対的品質を評価する指標について述べる。
提案手法は,古典的プランナが適用できない領域において,多様かつ高品質なプランセットを生成することができることを示す。
論文 参考訳(メタデータ) (2023-08-25T02:55:19Z) - Policy-Based Self-Competition for Planning Problems [0.0]
我々は、シングルプレイヤータスクをバイナリ出力に変換するために、セルフコンペティションを使用します。
2つのよく知られた最適化問題において,本手法の有効性を示す。
論文 参考訳(メタデータ) (2023-06-07T13:02:24Z) - 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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - 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) - Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
暗黙的な逐次計画の仮定に代わるものを検討する。
本稿では,最適計画の近似を行うため,Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS)を提案する。
計画順序に対するこのアルゴリズム的柔軟性は,グリッドワールドにおけるナビゲーションタスクの改善に繋がることを示す。
論文 参考訳(メタデータ) (2020-04-23T18:08:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。