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

• arxiv url: http://arxiv.org/abs/2301.03313v3
• Date: Thu, 28 Sep 2023 21:06:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-02 19:27:05.129861
• Title: BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
• Title（参考訳）: BQ-NCO: 効率的なニューラルコンビネーション最適化のためのビシミュレート・クオタイリング
• Authors: Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors and Jean-Marc Andreoli
• Abstract要約: マルコフ決定過程(MDP)としての組合せ最適化問題(COP)の新たな定式化について述べる。 本稿では,これらの問題の対称性を活用し,MDPの解法を促進する方法を示す。 本稿では, ユークリッドと非対称トラベリングセールスマン, キャパシタン, オリエンテーリング, クナプサックの5つの古典的問題について述べる。
• 参考スコア（独自算出の注目度）: 1.5806557511612143
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the success of neural-based 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 Problems (COPs) as Markov Decision Processes (MDPs) that effectively leverages common symmetries of COPs to improve out-of-distribution robustness. Starting from a direct MDP formulation of a constructive method, we introduce a generic way to reduce the state space, based on Bisimulation Quotienting (BQ) in MDPs. Then, for COPs with a recursive nature, we specialize the bisimulation and show how the reduced state exploits the symmetries of these problems and facilitates MDP solving. Our approach is principled and we prove that an optimal policy for the proposed BQ-MDP actually solves the associated COPs. We illustrate our approach on five classical problems: the Euclidean and Asymmetric Traveling Salesman, Capacitated Vehicle Routing, Orienteering and Knapsack Problems. Furthermore, for each problem, we introduce a simple attention-based policy network for the BQ-MDPs, which we train by imitation of (near) optimal solutions of small instances from a single distribution. We obtain new state-of-the-art results for the five COPs on both synthetic and realistic benchmarks. Notably, in contrast to most existing neural approaches, our learned policies show excellent generalization performance to much larger instances than seen during training, without any additional search procedure.
• Abstract（参考訳）: エンドツーエンドのヒューリスティック学習のためのニューラルネットワークに基づく組合せ最適化手法の成功にもかかわらず、分散の一般化は依然として課題である。 本稿では,共同最適化問題(COP)をマルコフ決定過程(MDP)として新たに定式化し,COPの共通対称性を効果的に活用し,分布外ロバスト性を改善する。 構成的手法の直接 MDP の定式化から始めて,MDP における Bisimulation Quotienting (BQ) に基づく状態空間の簡易化手法を提案する。 そして,再帰的な性質を持つCOPに対して,バイシミュレーションを専門とし,還元状態がこれらの問題の対称性をどのように活用し,MDP解決を促進するかを示す。 提案したBQ-MDPに対する最適ポリシーが実際に関連するCOPを解くことを証明する。 我々は, ユークリッドと非対称走行セールスマン, キャパシタブル・ルーティング, オリエンテーリング, ナップサック問題という, 5つの古典的な問題に対する我々のアプローチを説明する。 さらに,各問題に対して,BQ-MDPに対するシンプルなアテンションベースのポリシーネットワークを導入し,単一分布から小さなインスタンスの(ほぼ)最適解を模倣して学習する。 人工的および現実的なベンチマークにおいて,5つのCOPに対する最新の結果を得た。 特に、既存のほとんどのニューラルアプローチとは対照的に、我々の学習ポリシーは、追加の探索手順なしで、トレーニング中に見られるよりもはるかに大きなインスタンスに対して優れた一般化性能を示す。

関連論文リスト

• 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)

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

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