論文の概要: Efficient Constraint Generation for Stochastic Shortest Path Problems

• arxiv url: http://arxiv.org/abs/2604.01855v1
• Date: Thu, 02 Apr 2026 10:10:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:10.673242
• Title: Efficient Constraint Generation for Stochastic Shortest Path Problems
• Title（参考訳）: 確率的最短経路問題に対する効率的な制約生成
• Authors: Johannes Schmalz, Felipe Trevizan,
• Abstract要約: 最短経路問題 (SSP) は、ベルマンバックアップを適用して各州のコスト・ツー・ゴ(英語版)を計算することで伝統的に解決される。 Bellmanバックアップは、適用可能なすべてのアクションを繰り返すことで州のコスト・ツー・ゴーを更新し、各アクションを適用した後のコスト・ツー・ゴーを計算し、最小のアクションのコスト・ツー・ゴーを選択する。 CG-iLAO*は、新しい手法でiLAO*を適応させる新しいアルゴリズムであり、多くの問題に対するiLAO*の作用の40%しか考慮していない。
• 参考スコア（独自算出の注目度）: 1.9336815376402718
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Stochastic Shortest Path problems (SSPs) are traditionally solved by computing each state's cost-to-go by applying Bellman backups. A Bellman backup updates a state's cost-to-go by iterating through every applicable action, computing the cost-to-go after applying each one, and selecting a minimal action's cost-to-go. State-of-the-art algorithms use heuristic functions; these give an initial estimate of costs-to-go, and lets the algorithm apply Bellman backups only to promising states, determined by low estimated costs-to-go. However, each Bellman backup still considers all applicable actions, even if the heuristic tells us that some of these actions are too expensive, with the effect that such algorithms waste time on unhelpful actions. To address this gap we present a technique that uses the heuristic to avoid expensive actions, by reframing heuristic search in terms of linear programming and introducing an efficient implementation of constraint generation for SSPs. We present CG-iLAO*, a new algorithm that adapts iLAO* with our novel technique, and considers only 40% of iLAO*'s actions on many problems, and as few as 1% on some. Consequently, CG-iLAO* computes on average 3.5x fewer costs-to-go for actions than the state-of-the-art iLAO* and LRTDP, enabling it to solve problems faster an average of 2.8x and 3.7x faster, respectively.
• Abstract（参考訳）: 確率的短経路問題(SSP)は、伝統的にベルマンバックアップを適用して各州のコスト・ツー・ゴーを計算することによって解決される。 Bellmanバックアップは、適用可能なすべてのアクションを繰り返すことで州のコスト・ツー・ゴーを更新し、各アクションを適用した後のコスト・ツー・ゴーを計算し、最小のアクションのコスト・ツー・ゴーを選択する。 最先端のアルゴリズムはヒューリスティック関数を使用し、これらは最初にコスト・トゥ・ゴーを推定し、予測されるコスト・トゥ・ゴーによって決定される有望な状態のみにベルマンのバックアップを適用する。 しかしながら、各ベルマンバックアップは、たとえヒューリスティックがこれらのアクションのいくつかが高すぎると教えてくれても、適用可能なアクションをすべて考慮している。 このギャップに対処するために、線形プログラミングの観点からヒューリスティック検索を緩和し、SSPに対する制約生成の効率的な実装を導入することで、高価な行動を避けるためにヒューリスティックを利用する手法を提案する。 CG-iLAO*は,新しい手法でiLAO*を適応させるアルゴリズムであり,多くの問題に対するiLAO*の作用の40%しか考慮していない。 その結果、CG-iLAO* は最先端の iLAO* や LRTDP よりも平均3.5倍のコスト対効果を計算し、それぞれ平均2.8倍と3.7倍の速度で問題を解くことができる。

関連論文リスト

• End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions [66.17960480460185]
  決定過程(MDP)における線形関数近似を用いた強化学習の研究 本稿では, 線形ベルマン完全オラクルに対して, 決定論的遷移, 初期状態, 報奨を伴う計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-24T17:32:29Z)
• Time-Varying Convex Optimization with $O(n)$ Computational Complexity [0.0]
  コスト関数が時間とともに変化する非拘束凸最適化の問題を考える。 提案アルゴリズムは,決定変数に対するコスト関数の1次微分のみを必要とする。 具体的には、提案アルゴリズムは、計算コストを1タイムステップあたり$(n3)$から$O(n)$に削減する。
  論文  参考訳（メタデータ） (2024-10-19T06:45:05Z)
• Efficient Constraint Generation for Stochastic Shortest Path Problems [0.0]
  最短経路問題(SSP)に対する制約生成の効率的なバージョンを提案する。 この手法により、アルゴリズムは準最適動作を無視し、コスト・ツー・ゴーの計算を回避できる。 実験の結果, CG-iLAO* は iLAO* の作用の最大57% を無視し, LRTDP や iLAO* よりも最大8倍, 3倍高速に問題を解くことがわかった。
  論文  参考訳（メタデータ） (2024-01-26T04:00:07Z)
• Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs [31.673857053336352]
  本稿では,時間ホリゾン$H$において,エピソード数と線形数に切り替えコストの対数性を持たせることで,ほぼ最適の後悔を実現するアルゴリズムを提案する。 また、ELEANOR-LowSwitchingで使われる「二重化トリック」を一般化線形関数近似にさらに活用できることを示す。
  論文  参考訳（メタデータ） (2023-02-24T05:14:27Z)
• Shielding in Resource-Constrained Goal POMDPs [0.0]
  我々は,特定の資源の供給を必要とするエージェントをモデル化して,部分的に観測可能なマルコフ決定プロセス(POMDP)を検討する。 このエージェントは、リソースの枯渇を防止しながら目標を達成するための期待コストを最小化することを目的としており、これは、Emphresource-Constrained goal Optimization (RSGO) と呼ばれる問題である。 本稿では,本アルゴリズムの実装と,その文献からのベンチマークへの適用性を示す実験を行う。
  論文  参考訳（メタデータ） (2022-11-28T14:30:05Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimization [60.72410937614299]
  提案手法は,2レベルAT(FAST-BAT)と呼ばれる新しいアルゴリズムセットの設計と解析である。 FAST-BATは、グラデーションサインメソッドや明示的なロバスト正規化を呼ぶことなく、符号ベースの投射降下(PGD)攻撃を防御することができる。
  論文  参考訳（メタデータ） (2021-12-23T06:25:36Z)
• Logistic Q-Learning [87.00813469969167]
  MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。 提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
  論文  参考訳（メタデータ） (2020-10-21T17:14:31Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Excursion Search for Constrained Bayesian Optimization under a Limited Budget of Failures [62.41541049302712]
  本稿では,所定の予算の失敗の関数として探索において許容されるリスクの量を制御する制御理論に基づく新しい意思決定者を提案する。 本アルゴリズムは, 種々の最適化実験において, 故障予算をより効率的に利用し, 一般に, 最先端の手法よりも, 後悔度を低くする。
  論文  参考訳（メタデータ） (2020-05-15T09:54:09Z)
• Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm [0.0]
  本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。 提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。 コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
  論文  参考訳（メタデータ） (2020-02-18T07:09:06Z)

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

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