論文の概要: Sequential Stochastic Combinatorial Optimization Using Hierarchal Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2502.05537v1
- Date: Sat, 08 Feb 2025 12:00:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-11 14:34:35.634244
- Title: Sequential Stochastic Combinatorial Optimization Using Hierarchal Reinforcement Learning
- Title（参考訳）: 階層強化学習を用いた逐次確率的組合せ最適化
- Authors: Xinsong Feng, Zihan Yu, Yanhai Xiong, Haipeng Chen,
- Abstract要約: 本稿では,上位層への適応的な予算配分と下位層へのノード選択を同時に決定する2層オプションベースフレームワークを提案する。
実験の結果,WS-option は従来の方法と比較して,有効性と一般化性が著しく向上していることがわかった。
- 参考スコア（独自算出の注目度）: 5.57541853212632
- License:
- Abstract: Reinforcement learning (RL) has emerged as a promising tool for combinatorial optimization (CO) problems due to its ability to learn fast, effective, and generalizable solutions. Nonetheless, existing works mostly focus on one-shot deterministic CO, while sequential stochastic CO (SSCO) has rarely been studied despite its broad applications such as adaptive influence maximization (IM) and infectious disease intervention. In this paper, we study the SSCO problem where we first decide the budget (e.g., number of seed nodes in adaptive IM) allocation for all time steps, and then select a set of nodes for each time step. The few existing studies on SSCO simplify the problems by assuming a uniformly distributed budget allocation over the time horizon, yielding suboptimal solutions. We propose a generic hierarchical RL (HRL) framework called wake-sleep option (WS-option), a two-layer option-based framework that simultaneously decides adaptive budget allocation on the higher layer and node selection on the lower layer. WS-option starts with a coherent formulation of the two-layer Markov decision processes (MDPs), capturing the interdependencies between the two layers of decisions. Building on this, WS-option employs several innovative designs to balance the model's training stability and computational efficiency, preventing the vicious cyclic interference issue between the two layers. Empirical results show that WS-option exhibits significantly improved effectiveness and generalizability compared to traditional methods. Moreover, the learned model can be generalized to larger graphs, which significantly reduces the overhead of computational resources.
- Abstract（参考訳）: 強化学習(Reinforcement Learning, RL)は、高速で効果的で一般化可能な解を学習する能力から、組合せ最適化(CO)問題のための有望なツールとして登場した。
それにもかかわらず、既存の研究は主に一発決定性COに焦点を当てているが、適応的影響最大化(IM)や感染症の介入といった幅広い応用にもかかわらず、逐次確率CO(SSCO)の研究はめったに行われていない。
本稿では、まず、全ての時間ステップの予算(例えば、適応IMにおけるシードノード数)を決定し、各時間ステップ毎にノード群を選択するSSCO問題について検討する。
SSCOに関するいくつかの既存の研究は、時間的地平線上で均一に分散した予算配分を仮定することで問題を単純化し、最適解を得る。
本稿では,上位層への適応的予算配分と下位層へのノード選択を同時に決定する2層オプションベースのフレームワークである,ウェイク-スリープオプション(WS-option)と呼ばれる汎用階層的RL(HRL)フレームワークを提案する。
WS-optionは、2層のMarkov決定プロセス(MDP)のコヒーレントな定式化から始まり、2つの決定層間の相互依存性をキャプチャします。
これに基づいて、WS-Optitionはモデルのトレーニング安定性と計算効率のバランスをとるために、いくつかの革新的な設計を採用しており、2つの層間の悪質な循環的干渉を防止しています。
実験の結果,WS-option は従来の方法と比較して,有効性と一般化性が著しく向上していることがわかった。
さらに、学習したモデルをより大きなグラフに一般化することで、計算資源のオーバーヘッドを大幅に削減することができる。
関連論文リスト
- Majorization-Minimization Dual Stagewise Algorithm for Generalized Lasso [2.1066879371176395]
本稿では,一般化ラッソ問題の全解経路を効率的に追従するために,一般化最小化二段階法(MM-DUST)アルゴリズムを提案する。
我々は,MM-DUSTの計算複雑性を解析し,近似解経路の一様収束性を確立する。
論文 参考訳（メタデータ） (2025-01-04T05:20:26Z) - UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems [8.871356150316224]
2段階のニューラル手法は、大規模なCO問題に対処する際の効率性を示している。
本稿では,一般の大規模CO問題の解法として,統一型ニューラルディバイド・アンド・コンカー・フレームワーク(UDC)を開発する。
論文 参考訳（メタデータ） (2024-06-29T04:29:03Z) - DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems [37.205311971072405]
DISCOは、大規模な組合せ最適化問題に対する効率的な拡散解法である。
サンプリング空間は、解残基によって導かれるより有意義な領域に制約され、出力分布のマルチモーダルな性質は保たれる。
大規模なトラベリングセールスマン問題や最大独立セットのベンチマークに挑戦し、他の拡散手段よりも最大5.28倍の速度で推論を行う。
論文 参考訳（メタデータ） (2024-06-28T07:36:31Z) - 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) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳（メタデータ） (2023-07-01T18:35:21Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳（メタデータ） (2021-03-10T03:16:12Z) - Resource Allocation via Model-Free Deep Learning in Free Space Optical
Communications [119.81868223344173]
本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。
本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-27T17:38:51Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Simplified Swarm Optimization for Bi-Objection Active Reliability
Redundancy Allocation Problems [1.5990720051907859]
信頼性冗長性割り当て問題(RRAP)は、システム設計、開発、管理においてよく知られた問題である。
本研究では, コスト制約を新たな目標として変更することにより, 両対象RRAPを定式化する。
提案課題を解決するために,ペナルティ関数を備えた新しい簡易スワム最適化 (SSO) ,実効1型ソリューション構造,数値ベースの自己適応型新しい更新機構,制約付き非支配型ソリューション選択,および新しいpBest代替ポリシーを開発した。
論文 参考訳（メタデータ） (2020-06-17T13:15:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。