論文の概要: Heuristics for Combinatorial Optimization via Value-based Reinforcement Learning: A Unified Framework and Analysis
- arxiv url: http://arxiv.org/abs/2512.08601v1
- Date: Tue, 09 Dec 2025 13:40:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-10 22:28:07.979637
- Title: Heuristics for Combinatorial Optimization via Value-based Reinforcement Learning: A Unified Framework and Analysis
- Title（参考訳）: 価値に基づく強化学習による組合せ最適化のためのヒューリスティックス:統一フレームワークと分析
- Authors: Orit Davidovich, Shimrit Shtern, Segev Wasserkrug, Nimrod Megiddo,
- Abstract要約: 我々はマルコフ決定プロセス(MDP)を通じてCO問題をモデル化するための統一的なフレームワークを導入し、それらを強化学習技術を用いて解決する。
我々は,CO問題に対する最適解を提供する等価な非カウント型MDPとして,CO問題を定式化できるという簡単な仮定を提供する。
収束解析では,(1)各RLにおけるバッチサイズの増加率,(2)問題パラメータと目標RL精度の最適性ギャップ,(3)状態空間埋め込みの選択の重要性について検討した。
- 参考スコア（独自算出の注目度）: 3.7118625429889742
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Since the 1990s, considerable empirical work has been carried out to train statistical models, such as neural networks (NNs), as learned heuristics for combinatorial optimization (CO) problems. When successful, such an approach eliminates the need for experts to design heuristics per problem type. Due to their structure, many hard CO problems are amenable to treatment through reinforcement learning (RL). Indeed, we find a wealth of literature training NNs using value-based, policy gradient, or actor-critic approaches, with promising results, both in terms of empirical optimality gaps and inference runtimes. Nevertheless, there has been a paucity of theoretical work undergirding the use of RL for CO problems. To this end, we introduce a unified framework to model CO problems through Markov decision processes (MDPs) and solve them using RL techniques. We provide easy-to-test assumptions under which CO problems can be formulated as equivalent undiscounted MDPs that provide optimal solutions to the original CO problems. Moreover, we establish conditions under which value-based RL techniques converge to approximate solutions of the CO problem with a guarantee on the associated optimality gap. Our convergence analysis provides: (1) a sufficient rate of increase in batch size and projected gradient descent steps at each RL iteration; (2) the resulting optimality gap in terms of problem parameters and targeted RL accuracy; and (3) the importance of a choice of state-space embedding. Together, our analysis illuminates the success (and limitations) of the celebrated deep Q-learning algorithm in this problem context.
- Abstract（参考訳）: 1990年代以降、組合せ最適化(CO)問題に対する学習的ヒューリスティックスとして、ニューラルネットワーク(NN)のような統計モデルを訓練するためのかなりの実験が実施されている。
このようなアプローチが成功すると、専門家が問題タイプごとにヒューリスティックを設計する必要がなくなる。
その構造のため、強化学習(RL)による処理には多くの難解なCO問題が発生する。
実際、我々は、経験的最適性ギャップと推論ランタイムの両方の観点から、有望な結果を伴う価値ベース、ポリシー勾配、アクター批判アプローチを使用して、NNを訓練する豊富な文献を見つける。
それにもかかわらず、CO問題にRLを用いることを前提とした理論的な研究が数多く行われている。
この目的のために,マルコフ決定プロセス(MDP)を通じてCO問題をモデル化するための統一的なフレームワークを導入し,RL手法を用いてそれらを解く。
我々は,CO問題に対する最適解を提供する等価な非カウント型MDPとして,CO問題を定式化できるという簡単な仮定を提供する。
さらに、値に基づくRL手法がCO問題の近似解に収束し、関連する最適性ギャップが保証される条件を確立する。
我々の収束分析は,(1)バッチサイズの増加率と各RLイテレーションにおける勾配降下ステップの投影率,(2)問題パラメータと目標RL精度の最適性ギャップ,(3)状態空間埋め込みの選択の重要性を提供する。
この問題において,本分析は,有望なQ-ラーニングアルゴリズムの成功(および限界)を照らすものである。
関連論文リスト
- Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。
大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。
統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
論文 参考訳（メタデータ） (2025-05-13T16:47:00Z) - UniCO: Towards a Unified Model for Combinatorial Optimization Problems [30.524941693870534]
Combinatorial Optimization (CO)は多くの現実世界のシナリオで発生する幅広い問題を含んでいる。
我々は,様々なCO問題を解決する統一モデルであるUniCOを紹介する。
論文 参考訳（メタデータ） (2025-05-07T12:39:33Z) - Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization [7.85458999849461]
我々は,拡散モデルをゼロから直接訓練する,教師なしCOフレームワークであるIC/DCを提案する。
私たちは、問題固有の制約を順守しながら、ソリューションのコストを最小限に抑えるために、自己監督的な方法でモデルをトレーニングします。
並列マシンスケジューリング問題(PMSP)と非対称トラベリングセールスマン問題(ATSP)における既存のNCO手法と比較して、IC/DCは最先端の性能を達成する
論文 参考訳（メタデータ） (2024-10-15T06:53:30Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。
汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。
我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
論文 参考訳（メタデータ） (2023-10-10T01:39:04Z) - 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) - Understanding Curriculum Learning in Policy Optimization for Online
Combinatorial Optimization [66.35750142827898]
本稿では,オンラインCO問題に対するポリシー最適化手法に関する最初の体系的研究について述べる。
我々は、オンラインCO問題は、潜在マルコフ決定過程(LMDP)として自然に定式化でき、自然政策勾配(NPG)に収束することを示す。
さらに,本理論はカリキュラム学習の利点を解説し,強力なサンプリングポリシーを見出すことができ,流通シフトを低減できることを示した。
論文 参考訳（メタデータ） (2022-02-11T03:17:15Z) - USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization
Problems [9.015720257837575]
入力-解対のサンプルから高品質な最適化解を推定することを目的として,空間間の回帰を考察する。
基礎学習にはPAC-Bayesianフレームワークを用いて学習エラー分析を行う。
我々は,合成データセットと実世界のデータセットの両方において,古典的な問題に対する高い励振実験結果を得た。
論文 参考訳（メタデータ） (2021-07-15T17:59:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。