論文の概要: Domain-Independent Dynamic Programming

• arxiv url: http://arxiv.org/abs/2401.13883v1
• Date: Thu, 25 Jan 2024 01:48:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-26 15:57:39.435696
• Title: Domain-Independent Dynamic Programming
• Title（参考訳）: ドメインに依存しない動的プログラミング
• Authors: Ryo Kuroiwa, J. Christopher Beck
• Abstract要約: ドメイン独立動的プログラミング(DIDP)は動的プログラミング(DP)に基づく新しいモデルベースパラダイムである AI計画にインスパイアされた状態遷移システムに基づくDPモデルを定義するフォーマリズムである動的プログラミング記述言語(DyPDL)を導入する。 探索アルゴリズムを用いてDyPDLモデルの解法と7つのDIDP解法を提案する。
• 参考スコア（独自算出の注目度）: 6.437469175415774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For combinatorial optimization problems, model-based paradigms such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the `holy grail' of declarative problem solving. We propose domain-independent dynamic programming (DIDP), a new model-based paradigm based on dynamic programming (DP). While DP is not new, it has typically been implemented as a problem-specific method. We introduce Dynamic Programming Description Language (DyPDL), a formalism to define DP models based on a state transition system, inspired by AI planning. We show that heuristic search algorithms can be used to solve DyPDL models and propose seven DIDP solvers. We experimentally compare our DIDP solvers with commercial MIP and CP solvers (solving MIP and CP models, respectively) on common benchmark instances of eleven combinatorial optimization problem classes. We show that DIDP outperforms MIP in nine problem classes, CP also in nine problem classes, and both MIP and CP in seven.
• Abstract（参考訳）: 組合せ最適化問題において、混合整数プログラミング(mip)や制約プログラミング(cp)のようなモデルベースのパラダイムは、モデリングと問題解決を分離することを目的としている。 本稿では、動的プログラミング(DP)に基づく新しいモデルベースパラダイムであるドメイン独立動的プログラミング(DIDP)を提案する。 DPは新しいものではないが、通常は問題固有の方法として実装されている。 AI計画にインスパイアされた状態遷移システムに基づくDPモデルを定義するフォーマリズムである動的プログラミング記述言語(DyPDL)を導入する。 そこで本研究では,DyPDLモデルの解法としてヒューリスティック検索アルゴリズムを用いて7つのDIDP解法を提案する。 我々は,DDPソルバと商用MIPおよびCPソルバ(それぞれMIPとCPモデルを解いた)を,11の組合せ最適化問題クラスの共通ベンチマークインスタンス上で実験的に比較した。 その結果,DIDPは9つの問題クラス,CPは9つの問題クラス,MIPとCPは7つの問題クラスでMIPを上回っていることがわかった。

関連論文リスト

• Q-learning for Quantile MDPs: A Decomposition, Performance, and Convergence Analysis [30.713243690224207]
  マルコフ決定過程(MDPs)において、バリュー・アット・リスク(Value-at-Risk)のような量子リスク尺度は、特定の結果に対するRLエージェントの嗜好をモデル化するための標準指標である。 本稿では,強い収束と性能保証を有するMDPにおける量子化最適化のための新しいQ-ラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-31T16:53:20Z)
• Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimization [50.485788083202124]
  強化学習(Reinforcement Learning, RL)は、大規模言語モデルを人間の好みと整合させ、複雑なタスクを遂行する能力を向上させる上で重要な役割を担っている。 反応生成過程をマルコフ決定プロセス(MDP)として定式化し,ソフトアクター・クリティック(SAC)フレームワークを用いて,言語モデルによって直接パラメータ化されたQ関数を最適化する,直接Q関数最適化(DQO)を提案する。 GSM8KとMATHという2つの数学問題解決データセットの実験結果から、DQOは従来の手法よりも優れており、言語モデルを整合させるための有望なオフライン強化学習手法として確立されている。
  論文  参考訳（メタデータ） (2024-10-11T23:29:20Z)
• MDP Geometry, Normalization and Reward Balancing Solvers [15.627546283580166]
  マルコフ決定過程(英: Markov Decision Process、MDP)は、シーケンシャルな意思決定問題の数学的モデルである。 本稿では, 自然正規化手順によるMDPの幾何学的解釈を新たに提案する。これにより, 任意の政策に対する行動の利点を変えることなく, それぞれの状態における値関数を調整できる。
  論文  参考訳（メタデータ） (2024-07-09T09:39:45Z)
• Solving Multi-Model MDPs by Coordinate Ascent and Dynamic Programming [8.495921422521068]
  マルチモデルマルコフ決定プロセス(MMDP)は、コンピューティングポリシーのための有望なフレームワークである。 MMDP は,MDP モデルの分布よりも期待されるリターンを最大化する政策を見出すことを目的としている。 本稿では,コーディネート・アセント法と,MMDPを解く動的プログラミングアルゴリズムを組み合わせたCADPを提案する。
  論文  参考訳（メタデータ） (2024-07-08T18:47:59Z)
• Efficient Adaptation in Mixed-Motive Environments via Hierarchical Opponent Modeling and Planning [51.52387511006586]
  本稿では,HOP(Hierarchical Opponent Modeling and Planning)を提案する。 HOPは階層的に2つのモジュールから構成される: 相手の目標を推論し、対応する目標条件のポリシーを学ぶ、反対モデリングモジュール。 HOPは、さまざまな未確認エージェントと相互作用する際、優れた少数ショット適応能力を示し、セルフプレイのシナリオで優れている。
  論文  参考訳（メタデータ） (2024-06-12T08:48:06Z)
• Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
  文脈決定プロセス(CMDP)は、遷移カーネルと報酬関数がコンテキスト変数によってインデックス付けされた異なるMDPで時間とともに変化できる強化学習のクラスを記述する。 CMDPは、時間とともに変化する環境で多くの現実世界のアプリケーションをモデル化するための重要なフレームワークとして機能する。 CMDPを2つの線形関数近似モデルで検討する: 文脈変化表現とすべての文脈に対する共通線形重み付きモデルIと、すべての文脈に対する共通表現と文脈変化線形重み付きモデルIIである。
  論文  参考訳（メタデータ） (2024-02-05T03:25:04Z)
• Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization [13.386517072025722]
  動的プログラミング(DP)に基づく新しいモデルベースパラダイムであるドメイン非依存動的プログラミング(DIDP)を提案する。 DPモデルを定義するフォーマリズムである動的プログラミング記述言語(DyPDL)を提案し、DyP(CAASDy)のためのコスト代数型A*ソルバーを開発する。
  論文  参考訳（メタデータ） (2022-11-26T00:15:45Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。 $nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2021-12-01T22:55:23Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)

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

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