論文の概要: Population-Based Reinforcement Learning for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2210.03475v1
• Date: Fri, 7 Oct 2022 11:58:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-10 13:17:29.111801
• Title: Population-Based Reinforcement Learning for Combinatorial Optimization
• Title（参考訳）: 組合せ最適化のための人口ベース強化学習
• Authors: Nathan Grinsztajn, Daniel Furelos-Blanco, Thomas D. Barrett
• Abstract要約: そこで我々は,Poppyが相補的なポリシーを複数生成し,3つのNPハード問題に対する最先端のRL結果を得ることを示した。 Poppyは過去の最先端よりも優れており、最適性ギャップを5分し、推論時間を1桁以上削減している。
• 参考スコア（独自算出の注目度）: 5.392822954974537
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Applying reinforcement learning (RL) to combinatorial optimization problems is attractive as it removes the need for expert knowledge or pre-solved instances. However, it is unrealistic to expect an agent to solve these (often NP-)hard problems in a single shot at inference due to their inherent complexity. Thus, leading approaches often implement additional search strategies, from stochastic sampling and beam-search to explicit fine-tuning. In this paper, we argue for the benefits of learning a population of complementary policies, which can be simultaneously rolled out at inference. To this end, we introduce Poppy, a simple theoretically grounded training procedure for populations. Instead of relying on a predefined or hand-crafted notion of diversity, Poppy induces an unsupervised specialization targeted solely at maximizing the performance of the population. We show that Poppy produces a set of complementary policies, and obtains state-of-the-art RL results on three popular NP-hard problems: the traveling salesman (TSP), the capacitated vehicle routing (CVRP), and 0-1 knapsack (KP) problems. On TSP specifically, Poppy outperforms the previous state-of-the-art, dividing the optimality gap by 5 while reducing the inference time by more than an order of magnitude.
• Abstract（参考訳）: 強化学習(RL)を組合せ最適化問題に適用することは、専門家の知識や事前解決されたインスタンスの必要性を排除し、魅力的である。 しかし、エージェントがこれらの(しばしばNP-)ハード問題を単発推論で解くのは、その固有の複雑さのために非現実的である。 このように、先導的なアプローチは、確率的サンプリングやビーム探索から明示的な微調整まで、しばしば追加の探索戦略を実装している。 本稿では,補完的政策の集団を学習することの利点を議論する。 そこで本研究では,理論上は人口の訓練手順であるpoppyを紹介する。 事前に定義または手作りの多様性の概念に頼る代わりに、ポピーは人口のパフォーマンスを最大化することだけを目的とした教師なしの専門化を誘導する。 そこで我々は,Poppyが相補的なポリシーを作成し,旅行セールスマン(TSP),キャパシタンドカールーティング(CVRP),0-1knapsack(KP)の3つの問題に対して,最先端のRLが得られることを示す。 特にTSPでは、Poppyは過去の最先端よりも優れており、最適性ギャップを5倍に分割し、推論時間を1桁以上削減している。

関連論文リスト

• Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning [55.65738319966385]
  我々は、新しいオンラインアルゴリズム、反復的ナッシュポリシー最適化(INPO)を提案する。 従来の方法とは異なり、INPOは個々の応答に対する期待される勝利率を推定する必要性を回避している。 LLaMA-3-8BベースのSFTモデルで、INPOはAlpacaEval 2.0で42.6%、Arena-Hardで37.8%の勝利率を達成した。
  論文  参考訳（メタデータ） (2024-06-30T08:00:34Z)
• Adversarial Imitation Learning On Aggregated Data [0.0]
  逆強化学習(IRL: Inverse Reinforcement Learning)は、いくつかの専門家による実証から最適なポリシーを学習し、適切な報酬関数を指定するという面倒なプロセスを避ける。 本稿では,AILAD(Adversarial Imitation Learning on Aggregated Data)と呼ばれる動的適応手法を用いて,これらの要件を除去する手法を提案する。 非線型報酬関数とそれに付随する最適ポリシーの両方を、敵対的枠組みを用いて共役的に学習する。
  論文  参考訳（メタデータ） (2023-11-14T22:13:38Z)
• Combinatorial Optimization with Policy Adaptation using Latent Space Search [44.12073954093942]
  本稿では,複雑なNPハード問題を解くために,パフォーマンスアルゴリズムを設計するための新しいアプローチを提案する。 我々の検索戦略は11の標準ベンチマークタスクにおける最先端のアプローチよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-11-13T12:24:54Z)
• Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
  我々は、dタスクのパフォーマンスに基づいて、n名のエキスパートをランク付けする問題を考察する。 我々は,各専門家のペアに対して,各タスクにおいて他方よりも優れているという,単調な仮定を定めている。
  論文  参考訳（メタデータ） (2023-06-05T06:55:39Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Jump-Start Reinforcement Learning [68.82380421479675]
  本稿では、オフラインデータやデモ、あるいは既存のポリシーを使ってRLポリシーを初期化するメタアルゴリズムを提案する。 特に,タスク解決に2つのポリシーを利用するアルゴリズムであるJump-Start Reinforcement Learning (JSRL)を提案する。 実験により、JSRLは既存の模倣と強化学習アルゴリズムを大幅に上回っていることを示す。
  論文  参考訳（メタデータ） (2022-04-05T17:25:22Z)
• NeuPL: Neural Population Learning [37.02099221741667]
  戦略ゲームで学ぶには、多様なポリシーの発見が必要である。 これはしばしば、既存の政策に対して反復的に新しい政策を訓練することで達成される。 この反復的アプローチは現実世界のゲームにおいて2つの問題に悩まされる: (a) 有限の予算の下では、各イテレーションにおける最適応答作用素を近似すると、各々のイテレーションの個体数が減少し、結果として、未学習の良応答が人口を膨らませ、b) 各イテレーションにおける基本スキルの繰り返し学習は無駄であり、ますます強い相手の存在下では難解になる。
  論文  参考訳（メタデータ） (2022-02-15T14:05:18Z)
• Can Q-learning solve Multi Armed Bantids? [0.0]
  現在の強化学習アルゴリズムでは,マルチアーマッド・バンディット問題を解くことができないことを示す。 これはポリシー間の差異が原因であり、2つの問題を引き起こす。 本稿では,アダプティブ・シンメトリ・リワード・ノーミング(ASRN)手法を提案する。
  論文  参考訳（メタデータ） (2021-10-21T07:08:30Z)
• Explore and Control with Adversarial Surprise [78.41972292110967]
  強化学習(Reinforcement Learning, RL)は、目標指向のポリシーを学習するためのフレームワークである。 本稿では,RLエージェントが経験した驚きの量と競合する2つのポリシーを相殺する対戦ゲームに基づく,新しい教師なしRL手法を提案する。 本手法は, 明確な相転移を示すことによって, 複雑なスキルの出現につながることを示す。
  論文  参考訳（メタデータ） (2021-07-12T17:58:40Z)
• SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning [102.78958681141577]
  SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。 SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
  論文  参考訳（メタデータ） (2020-07-09T17:08:44Z)

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

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