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

• arxiv url: http://arxiv.org/abs/2401.14636v1
• Date: Fri, 26 Jan 2024 04:00:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-29 16:04:21.470993
• Title: Efficient Constraint Generation for Stochastic Shortest Path Problems
• Title（参考訳）: 確率的最短経路問題に対する効率的な制約生成
• Authors: Johannes Schmalz, Felipe Trevizan
• Abstract要約: 最短経路問題(SSP)に対する制約生成の効率的なバージョンを提案する。 この手法により、アルゴリズムは準最適動作を無視し、コスト・ツー・ゴーの計算を回避できる。 実験の結果, CG-iLAO* は iLAO* の作用の最大57% を無視し, LRTDP や iLAO* よりも最大8倍, 3倍高速に問題を解くことがわかった。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Current methods for solving Stochastic Shortest Path Problems (SSPs) find states' costs-to-go by applying Bellman backups, where state-of-the-art methods employ heuristics to select states to back up and prune. A fundamental limitation of these algorithms is their need to compute the cost-to-go for every applicable action during each state backup, leading to unnecessary computation for actions identified as sub-optimal. We present new connections between planning and operations research and, using this framework, we address this issue of unnecessary computation by introducing an efficient version of constraint generation for SSPs. This technique allows algorithms to ignore sub-optimal actions and avoid computing their costs-to-go. We also apply our novel technique to iLAO* resulting in a new algorithm, CG-iLAO*. Our experiments show that CG-iLAO* ignores up to 57% of iLAO*'s actions and it solves problems up to 8x and 3x faster than LRTDP and iLAO*.
• Abstract（参考訳）: 確率的短経路問題(ssps:stastic shortest path problem)の解法では、ベルマンバックアップを適用して状態のコストを求める。 これらのアルゴリズムの基本的な制限は、各状態バックアップ中に適用可能なすべてのアクションに対するコスト・ツー・ゴーを計算する必要があることである。 本稿では,計画と運用研究の新たなつながりについて述べるとともに,SSPの制約生成の効率的なバージョンを導入することで,不要な計算の問題に対処する。 この手法により、アルゴリズムは最適なサブアクションを無視し、コストの計算を回避できる。 また,新しい手法を ilao* に適用し,cg-ilao* というアルゴリズムを開発した。 実験の結果, CG-iLAO* は iLAO* の作用の最大57% を無視し, LRTDP や iLAO* よりも最大8倍, 3倍高速に問題を解くことがわかった。

関連論文リスト

• Exponentially Weighted Algorithm for Online Network Resource Allocation with Long-Term Constraints [0.6466206145151128]
  本稿では,ジョブ転送を伴う通信ネットワークにおける最適資源予約問題について検討する。 本稿では,長期制約を含むランダム化指数重み付け法に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-03T10:12:40Z)
• High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
  本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。 我々は、ETCアルゴリズムの最適レートを$T$で導出し、探索とエクスプロイトのバランスをとることで、このレートを実現できることを示す。 本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T15:29:32Z)
• Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs [31.673857053336352]
  本稿では,時間ホリゾン$H$において,エピソード数と線形数に切り替えコストの対数性を持たせることで,ほぼ最適の後悔を実現するアルゴリズムを提案する。 また、ELEANOR-LowSwitchingで使われる「二重化トリック」を一般化線形関数近似にさらに活用できることを示す。
  論文  参考訳（メタデータ） (2023-02-24T05:14:27Z)
• CACTO: Continuous Actor-Critic with Trajectory Optimization -- Towards global optimality [5.0915256711576475]
  本稿では,Tlayy(TO)とReinforcement Learning(RL)を1つの軌道で組み合わせた,動的システムの連続制御のための新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-12T10:16:35Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Logistic Q-Learning [87.00813469969167]
  MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。 提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
  論文  参考訳（メタデータ） (2020-10-21T17:14:31Z)
• Learning the Step-size Policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
  本稿では,L-BFGSアルゴリズムのステップサイズポリシの学習方法について考察する。 入力として電流勾配の局所的な情報を用いたニューラルネットワークアーキテクチャを提案する。 ステップ長ポリシは、同様の最適化問題のデータから学習され、目的関数のさらなる評価を回避し、出力ステップが予め定義された間隔内に留まることを保証します。
  論文  参考訳（メタデータ） (2020-10-03T09:34:03Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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