Fugu-MT 論文翻訳(概要): Policy-Guided Heuristic Search with Guarantees

論文の概要: Policy-Guided Heuristic Search with Guarantees

arxiv url: http://arxiv.org/abs/2103.11505v1
Date: Sun, 21 Mar 2021 22:30:57 GMT
ステータス: 処理完了
システム内更新日: 2021-03-23 14:56:15.179031
Title: Policy-Guided Heuristic Search with Guarantees
Title（参考訳）: 保証付き政策誘導ヒューリスティック探索
Authors: Laurent Orseau, Levi H. S. Lelis
Abstract要約: Policy-guided Heuristic Search (PHS) は、関数とポリシーの両方を利用する新しい検索アルゴリズムである。 PHS は A*, Weighted A*, Greedy Best-First Search, LevinTS, PUCT と, 解決された問題数と検索時間の点で比較できる。
参考スコア（独自算出の注目度）: 31.323430201941378
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The use of a policy and a heuristic function for guiding search can be quite effective in adversarial problems, as demonstrated by AlphaGo and its successors, which are based on the PUCT search algorithm. While PUCT can also be used to solve single-agent deterministic problems, it lacks guarantees on its search effort and it can be computationally inefficient in practice. Combining the A* algorithm with a learned heuristic function tends to work better in these domains, but A* and its variants do not use a policy. Moreover, the purpose of using A* is to find solutions of minimum cost, while we seek instead to minimize the search loss (e.g., the number of search steps). LevinTS is guided by a policy and provides guarantees on the number of search steps that relate to the quality of the policy, but it does not make use of a heuristic function. In this work we introduce Policy-guided Heuristic Search (PHS), a novel search algorithm that uses both a heuristic function and a policy and has theoretical guarantees on the search loss that relates to both the quality of the heuristic and of the policy. We show empirically on the sliding-tile puzzle, Sokoban, and a puzzle from the commercial game `The Witness' that PHS enables the rapid learning of both a policy and a heuristic function and compares favorably with A*, Weighted A*, Greedy Best-First Search, LevinTS, and PUCT in terms of number of problems solved and search time in all three domains tested.
Abstract（参考訳）: 検索を導くためのポリシーとヒューリスティック関数の使用は、puct探索アルゴリズムに基づいたalphagoとその後継によって示されるように、敵対的問題において非常に効果的である。 PUCTは単エージェント決定論的問題を解くためにも使用できるが、その探索努力の保証が欠如しており、実際は計算的に非効率である。 A*アルゴリズムと学習されたヒューリスティック関数を組み合わせることはこれらの領域ではうまく機能するが、A*とその変種はポリシーを使用しない。さらに、A* の使用の目的は最小コストのソリューションを見つけることであり、代わりに探索損失を最小化すること(例えば探索ステップの数)を目指している。 LevinTSはポリシーによってガイドされ、ポリシーの品質に関連する探索ステップの数を保証するが、ヒューリスティックな機能を使用しない。本研究では, ヒューリスティック関数とポリシーを併用し, ヒューリスティックとポリシーの双方の品質に関連する探索損失を理論的に保証する新しい探索アルゴリズムである, ポリシー誘導ヒューリスティック探索(phs)を提案する。市販ゲーム「the witness」の「slide-tile puzzle」「sokoban」「the witness」において、phsはポリシーとヒューリスティック機能の両方の迅速な学習を可能にし、a*, weighted a*, greedy best-first search, levints, puctと、テストされた3つの領域すべてにおいて解決された問題数と検索時間の観点から好意的に比較できることを示す。

関連論文リスト

Augmented Bayesian Policy Search [14.292685001631945]
実際には、探索は主に決定論的な政策によって行われる。第一次ベイズ最適化(BO)法は、決定論的ポリシーを用いた探索の原則的な方法を提供する。確率モデルに新しい平均関数を導入する。これにより、アクション値関数を持つBOメソッドが増大する。
論文参考訳（メタデータ） (2024-07-05T20:56:45Z)
A Multi-Heuristic Search-based Motion Planning for Automated Parking [0.0]
駐車場や建設現場のような非構造環境においては、リアルタイムな計画の実現が困難である。我々は、複数の関数とその個々の利点を利用できるマルチヒューリスティック検索アプローチを採用しています。 Multi-Heuristic A*アルゴリズムは、非常に人気のある検索ベースのアルゴリズムであるHybrid A*に対してベンチマークされる。
論文参考訳（メタデータ） (2023-07-15T17:33:06Z)
Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文参考訳（メタデータ） (2021-09-13T18:10:52Z)
Exploiting Learned Policies in Focal Search [0.49723239539321284]
政策学習を有界-準最適探索アルゴリズムに統合する方法を示す。提案手法は3つのベンチマーク領域を対象とし,15-puzzleでは150万のサンプルを用いて学習したニューラルネットワークを用いて解析を行った。本稿では,emphDiscrepancy Focal Searchにおいて,対応する経路が最適経路の接頭辞である確率の近似を最大化するノードを拡大し,実行時および解の質の観点から最もよい結果が得られることを示す。
論文参考訳（メタデータ） (2021-04-21T13:50:40Z)
Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
本稿では,2つの多様性探索アルゴリズム,ノベルティ探索アルゴリズムとゴール探索処理アルゴリズムの特性について検討する。 mpアルゴリズムとの関係は、ポリシーパラメータ空間と結果空間の間のマッピングの滑らかさ、あるいは滑らかさの欠如が検索効率において重要な役割を担っていることを示している。
論文参考訳（メタデータ） (2021-04-10T13:52:27Z)
Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文参考訳（メタデータ） (2021-04-09T14:50:59Z)
Loss Function Discovery for Object Detection via Convergence-Simulation Driven Search [101.73248560009124]
本稿では,効率的な収束シミュレーションによる進化的探索アルゴリズムCSE-Autolossを提案する。一般的な検出器上での損失関数探索の広範囲な評価を行い、探索された損失の優れた一般化能力を検証した。実験の結果, 2段検出器と1段検出器のmAPでは, 最適損失関数の組み合わせが1.1%と0.8%を上回っていることがわかった。
論文参考訳（メタデータ） (2021-02-09T08:34:52Z)
Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-08T00:43:04Z)
Searching for a Search Method: Benchmarking Search Algorithms for Generating NLP Adversarial Examples [10.993342896547691]
自然言語処理(NLP)タスクの逆例を生成するために,複数のブラックボックス探索アルゴリズムの動作について検討した。検索アルゴリズム,検索空間,検索予算の3つの要素を詳細に分析する。
論文参考訳（メタデータ） (2020-09-09T17:04:42Z)
Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem [6.555180412600522]
二次代入問題 (QAP) はNPハード問題に属する最適化問題である。ヒューリスティックスとメタヒューリスティックスアルゴリズムはこの問題の一般的な解法である。本稿では,QAPの解法に異なるメタヒューリスティックアルゴリズムを適用するための比較研究の1つである。
論文参考訳（メタデータ） (2020-07-29T15:02:07Z)
Best-First Beam Search [78.71330480725668]
本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
論文参考訳（メタデータ） (2020-07-08T05:56:01Z)

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

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