論文の概要: BQ-NCO: Bisimulation Quotienting for Generalizable Neural Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2301.03313v2
• Date: Thu, 12 Jan 2023 10:08:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-13 15:22:54.830175
• Title: BQ-NCO: Bisimulation Quotienting for Generalizable Neural Combinatorial Optimization
• Title（参考訳）: BQ-NCO: 一般化可能なニューラルコンビネーション最適化のためのビシミュレータ
• Authors: Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors and Jean-Marc Andreoli
• Abstract要約: 我々はマルコフ決定過程(MDP)として現実的最適化(CO)問題の新しい定式化を提案する。 我々はCO問題の対称性を用いて配当の堅牢性を改善する。 合成ベンチマークから最大1000ノードのインスタンスに対して、最先端の新たな結果を得る。
• 参考スコア（独自算出の注目度）: 2.0789230137053014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the success of Neural Combinatorial Optimization methods for end-to-end heuristic learning, out-of-distribution generalization remains a challenge. In this paper, we present a novel formulation of combinatorial optimization (CO) problems as Markov Decision Processes (MDPs) that effectively leverages symmetries of the CO problems to improve out-of-distribution robustness. Starting from the standard MDP formulation of constructive heuristics, we introduce a generic transformation based on bisimulation quotienting (BQ) in MDPs. This transformation allows to reduce the state space by accounting for the intrinsic symmetries of the CO problem and facilitates the MDP solving. We illustrate our approach on the Traveling Salesman, Capacitated Vehicle Routing and Knapsack Problems. We present a BQ reformulation of these problems and introduce a simple attention-based policy network that we train by imitation of (near) optimal solutions for small instances from a single distribution. We obtain new state-of-the-art generalization results for instances with up to 1000 nodes from synthetic and realistic benchmarks that vary both in size and node distributions.
• Abstract（参考訳）: エンドツーエンドのヒューリスティック学習のためのNeural Combinatorial Optimization手法の成功にもかかわらず、アウト・オブ・ディストリビューションの一般化は依然として課題である。 本稿では, 分散ロバスト性を改善するために, co問題の対称性を効果的に活用するマルコフ決定過程 (mdps) として, 組合せ最適化 (co) 問題の新たな定式化を提案する。 構成的ヒューリスティックの標準 MDP の定式化から始めて,MDP におけるバイシミュレート商化 (BQ) に基づく汎用変換を導入する。 この変換により、CO問題の固有の対称性を考慮し、状態空間を小さくすることができ、MDP解決を容易にする。 我々は,移動セールスマン,キャパシタブル・ルーティング,ナップサック問題に対する我々のアプローチを説明する。 本稿では,これらの問題のBQ再構成を行い,単一分布から小さなインスタンスに対して(ほぼ)最適解を模倣して訓練する,シンプルな注意に基づくポリシーネットワークを提案する。 我々は,最大1000ノードのインスタンスに対して,サイズとノード分布の両方が異なる合成および現実的なベンチマークから,新たな最先端の一般化結果を得る。

関連論文リスト

• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Semi-Infinitely Constrained Markov Decision Processes and Efficient Reinforcement Learning [17.04643707688075]
  通常のCMDPの場合のように、有限個の制約ではなく制約の連続性を考える。 我々はSI-CRLとSI-CPOと呼ぶSICMDPのための2つの強化学習アルゴリズムを考案した。 我々の知る限り、我々は、制約付き強化学習問題を解決するために、半無限プログラミング(SIP)のツールを最初に適用しました。
  論文  参考訳（メタデータ） (2023-04-29T12:52:38Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning [156.5667417159582]
  本稿では,逐次情報設計の新たなモデル,すなわちマルコフ説得過程(MPP)を提案する。 MPPのプランニングは、ミオピックレシーバーに同時に説得されるシグナルポリシーを見つけ、送信者の最適な長期累積ユーティリティを誘導する、というユニークな課題に直面している。 我々は,楽観主義と悲観主義の両原理の新たな組み合わせを特徴とする,実証可能な効率のよい非回帰学習アルゴリズム,Optimism-Pessimism Principle for Persuasion Process (OP4) を設計する。
  論文  参考訳（メタデータ） (2022-02-22T05:41:43Z)
• Pretrained Cost Model for Distributed Constraint Optimization Problems [37.79733538931925]
  分散制約最適化問題(DCOP)は、最適化問題の重要なサブクラスである。 本稿では,DCOPのための新しい非巡回グラフスキーマ表現を提案し,グラフ表現を組み込むためにグラフ注意ネットワーク(GAT)を利用する。 我々のモデルであるGAT-PCMは、幅広いDCOPアルゴリズムを向上するために、オフラインで最適なラベル付きデータで事前訓練される。
  論文  参考訳（メタデータ） (2021-12-08T09:24:10Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Logistic Q-Learning [87.00813469969167]
  MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。 提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
  論文  参考訳（メタデータ） (2020-10-21T17:14:31Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
  本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。 我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。 その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
  論文  参考訳（メタデータ） (2020-06-22T03:13:07Z)

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

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