論文の概要: A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs

• arxiv url: http://arxiv.org/abs/2406.14697v2
• Date: Mon, 22 Jul 2024 08:03:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-24 00:52:06.468931
• Title: A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs
• Title（参考訳）: グラフ上の最大被覆問題に対するディープRL法のベンチマーク
• Authors: Zhicheng Liang, Yu Yang, Xiangyu Ke, Xiaokui Xiao, Yunjun Gao,
• Abstract要約: MCPとIMの5種類のDeep-RL法の有効性と有効性について検討した。 その結果,様々なシナリオにおいて,Lazy GreedyアルゴリズムはMPPのDeep-RL法を常に上回っていることがわかった。 IMの場合、理論上IMMやOPIMのような健全なアルゴリズムは、ほとんどのシナリオでDeep-RL法よりも優れている。
• 参考スコア（独自算出の注目度）: 36.08652149015519
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent years have witnessed a growing trend toward employing deep reinforcement learning (Deep-RL) to derive heuristics for combinatorial optimization (CO) problems on graphs. Maximum Coverage Problem (MCP) and its probabilistic variant on social networks, Influence Maximization (IM), have been particularly prominent in this line of research. In this paper, we present a comprehensive benchmark study that thoroughly investigates the effectiveness and efficiency of five recent Deep-RL methods for MCP and IM. These methods were published in top data science venues, namely S2V-DQN, Geometric-QN, GCOMB, RL4IM, and LeNSE. Our findings reveal that, across various scenarios, the Lazy Greedy algorithm consistently outperforms all Deep-RL methods for MCP. In the case of IM, theoretically sound algorithms like IMM and OPIM demonstrate superior performance compared to Deep-RL methods in most scenarios. Notably, we observe an abnormal phenomenon in IM problem where Deep-RL methods slightly outperform IMM and OPIM when the influence spread nearly does not increase as the budget increases. Furthermore, our experimental results highlight common issues when applying Deep-RL methods to MCP and IM in practical settings. Finally, we discuss potential avenues for improving Deep-RL methods. Our benchmark study sheds light on potential challenges in current deep reinforcement learning research for solving combinatorial optimization problems.
• Abstract（参考訳）: 近年,グラフ上の組合せ最適化(CO)問題に対するヒューリスティックスを導出するために,深層強化学習(Deep-RL)を採用する傾向が高まっている。 最大被覆問題(MCP)とそのソーシャルネットワーク上での確率的変異、影響最大化(IM)は、この研究の分野において特に顕著である。 本稿では,MPPとIMの5つの新しいDeep-RL法の有効性と効率について,総合的なベンチマーク研究を行った。 これらの手法はS2V-DQN、Geometric-QN、GCOMB、RL4IM、LeNSEといったトップデータサイエンスの会場で発表された。 その結果,様々なシナリオにおいて,Lazy GreedyアルゴリズムはMPPのDeep-RL法を常に上回っていることがわかった。 IMの場合、IMMやOPIMのような音響アルゴリズムは、ほとんどのシナリオでDeep-RL法よりも優れた性能を示す。 特に,IMM法とOPIM法では,予算の増大とともに影響がほとんど拡大しない場合に,Deep-RL法がIMMとOPIMをわずかに上回り,IM問題における異常現象が観察された。 さらに,本実験では,MPPとIMにDeep-RL法を適用した場合の一般的な問題点について検討した。 最後に,Deep-RL法の改良手法について検討する。 我々のベンチマーク研究は、組合せ最適化問題を解決するための現在の深層強化学習研究における潜在的な課題に光を当てている。

関連論文リスト

• UDQL: Bridging The Gap between MSE Loss and The Optimal Value Function in Offline Reinforcement Learning [10.593924216046977]
  まず,MSEによる過大評価現象を理論的に解析し,過大評価誤差の理論的上限を与える。 最後に、過小評価演算子と拡散ポリシーモデルに基づくオフラインRLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-05T14:37:42Z)
• Hyperparameter Optimization for Multi-Objective Reinforcement Learning [0.27309692684728615]
  強化学習(Reinforcement Learning, RL)は、複雑な問題に対処するための強力なアプローチである。 近年,多目的強化学習(MORL)の導入により,RLの範囲が拡大した。 実際には、このタスクは難しいことがしばしば証明され、これらのテクニックのデプロイが失敗に終わる。
  論文  参考訳（メタデータ） (2023-10-25T09:17:25Z)
• Evolving Populations of Diverse RL Agents with MAP-Elites [1.5575376673936223]
  政策だけでなく,任意の強化学習(RL)アルゴリズムの利用を可能にするフレキシブルなフレームワークを導入する。 我々は,多数のロボット制御問題に対する広範な数値実験を通じて,我々のフレームワークがもたらすメリットを実証する。
  論文  参考訳（メタデータ） (2023-03-09T19:05:45Z)
• Train Hard, Fight Easy: Robust Meta Reinforcement Learning [78.16589993684698]
  実世界のアプリケーションにおける強化学習(RL)の大きな課題は、環境、タスク、クライアントの違いである。 標準的なMRL法は、タスクよりも平均的なリターンを最適化するが、リスクや難易度の高いタスクでは悪い結果に悩まされることが多い。 本研究では, MRL の頑健な目標を制御レベルで定義する。 ロバストメタRLアルゴリズム(RoML)を用いてデータ非効率に対処する
  論文  参考訳（メタデータ） (2023-01-26T14:54:39Z)
• A Survey of Meta-Reinforcement Learning [69.76165430793571]
  我々は,メタRLと呼ばれるプロセスにおいて,機械学習問題自体として,より優れたRLアルゴリズムを開発した。 本稿では,タスク分布の存在と各タスクに利用可能な学習予算に基づいて,高レベルでメタRL研究をクラスタ化する方法について議論する。 RL実践者のための標準ツールボックスにメタRLを組み込むことの道程について,オープンな問題を提示することによって,結論を下す。
  論文  参考訳（メタデータ） (2023-01-19T12:01:41Z)
• ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning [4.266866385061998]
  本稿では、影響最大化(IM)問題に対処するため、新しいエンドツーエンドDRLフレームワークToupleGDDを提案する。 我々のモデルは、小さな予算でランダムに生成されたいくつかの小さなグラフで訓練され、様々な大きな予算の下で全く異なるネットワークでテストされる。
  論文  参考訳（メタデータ） (2022-10-14T03:56:53Z)
• Reinforcement Learning-Empowered Mobile Edge Computing for 6G Edge Intelligence [76.96698721128406]
  モバイルエッジコンピューティング(MEC)は、第5世代(5G)ネットワークなどにおける計算と遅延に敏感なタスクのための新しいパラダイムであると考えた。 本稿では、フリー対応RLに関する総合的な研究レビューと、開発のための洞察を提供する。
  論文  参考訳（メタデータ） (2022-01-27T10:02:54Z)
• Behavioral Priors and Dynamics Models: Improving Performance and Domain Transfer in Offline RL [82.93243616342275]
  適応行動優先型オフラインモデルに基づくRL(Adaptive Behavioral Priors:MABE)を導入する。 MABEは、ドメイン内の一般化をサポートする動的モデルと、ドメイン間の一般化をサポートする振る舞いの事前が相補的であることの発見に基づいている。 クロスドメインの一般化を必要とする実験では、MABEが先行手法より優れていることが判明した。
  論文  参考訳（メタデータ） (2021-06-16T20:48:49Z)
• On Multi-objective Policy Optimization as a Tool for Reinforcement Learning: Case Studies in Offline RL and Finetuning [24.264618706734012]
  より効率的な深層強化学習アルゴリズムの開発方法について述べる。 ケーススタディとして,オフラインRLとファインタニングに注目した。 専門家の混合蒸留(DiME)について紹介する オフラインのRLでは、DMEが最先端のアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-15T14:59:14Z)
• Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning [83.66080019570461]
  課題の難易度について,環境にとらわれない,アルゴリズムにとらわれない2つの定量的指標を提案する。 これらの指標は、様々な代替案よりも、正規化タスク可解性スコアとの相関が高いことを示す。 これらのメトリクスは、鍵設計パラメータの高速かつ計算効率の良い最適化にも使用できる。
  論文  参考訳（メタデータ） (2021-03-23T17:49:50Z)

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

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