論文の概要: Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau

• arxiv url: http://arxiv.org/abs/2609.23293v1
• Date: Sun, 20 Sep 2026 02:05:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-23 18:04:03.927992
• Title: Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau
• Title（参考訳）: 最終高原における標準A*Tie-Breaking戦略による膨張数
• Abstract要約: A*探索アルゴリズムでは、同じ$f値のノードのタイブレーキング戦略により、最終$f層上でA*が膨張する状態を決定する。 標準の9つのタイブレーキング戦略について、各ペアが任意の大きさの付加的拡張ギャップによって、それぞれの戦略に有利な正のコストのインスタンスを持つことが示される。
• 参考スコア（独自算出の注目度）: 2.741266294612776
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the A* search algorithm, the tie-breaking strategies for nodes with the same $f$-value determines which states A* expands on the final $f$-layer. For nine standard tie-breaking strategies, we show that under a consistent heuristic, every pair has positive-cost instances favoring each strategy over the other by an arbitrarily large additive expansion gap. A parameterized unit-cost grid example also gives unbounded expansion-count ratios between low-$h$ with FIFO and LIFO. In unit-cost search with $h > 0$ at non-goals, exact heuristic values near the goal lead to complementary extremal results: low-$h$ minimizes the number of remaining expansions from a common configuration within the perfect region, while high-$h$ maximizes the total number of expansions when every final-plateau state with $h=1$ is a goal predecessor. Finally, with the evaluation function $f_α = g + αh$, when $h>0$ at non-goals, every heuristic weight $0 \leq α<1$ eliminates tie-breaking sensitivity, and all tie-breaking strategies expand the same set of states.
• Abstract（参考訳）: A*探索アルゴリズムでは、同じ$f$-valueを持つノードのタイブレーキング戦略により、最終$f$-layer上でA*が拡張する状態を決定する。 9つの標準的なタイブレーキング戦略において、一貫したヒューリスティックの下では、各ペアが任意の大きな加算拡張ギャップによって、互いに有利な戦略を好む正のコストのインスタンスを持つことが示される。 パラメータ化された単位コストグリッドの例は、FIFO とLIFO との低価h$の非有界展開数比も与えている。 非ゴールで$h > 0$ の単価探索では、ゴールに近い正確なヒューリスティックな値は相補的な極端結果をもたらす: low-h$ は完全領域内の共通構成から残る拡張の数を最小にし、 high-h$ は最終プレート状態が $h=1$ のときの展開の総数を最大化する。 最後に、評価関数 $f_α = g + αh$, if $h>0$, if $h>0$, every heuristic weight $0 \leq α<1$ はタイブレーキング感度を排除し、全てのタイブレーキング戦略は同じ状態の集合を拡張する。

関連論文リスト

• A Convergence Framework for Deep $V$-Learning: Error Propagation and Sharp Action-Gap Bounds [0.0]
  更新エラーを、フィッティング、遷移再利用、ターゲット構築、リプレイ、アクション選択、探索の6つの残差に分解する。 次数$n-$の統計的誤差境界に対して、最適連続割り当てと、制約された最適値の係数2$以内の整数割り当てを導出する。 これらの結果から, FIFO/インターリーブされたSGDに対して, 厳密な動作スコアを有する固定水平生成-リセット近似-ERM法に対して, 期待されるポリシ-ロス一貫性が得られた。
  論文  参考訳（メタデータ） (2026-09-16T15:03:46Z)
• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
  論文  参考訳（メタデータ） (2026-08-12T14:54:15Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。 この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。 この設定のための最初のポリシー最適化アルゴリズムを紹介します。
  論文  参考訳（メタデータ） (2025-02-06T12:03:24Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)

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

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