論文の概要: Combinatorial Optimization with Policy Adaptation using Latent Space Search

• arxiv url: http://arxiv.org/abs/2311.13569v1
• Date: Mon, 13 Nov 2023 12:24:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-27 00:24:00.812443
• Title: Combinatorial Optimization with Policy Adaptation using Latent Space Search
• Title（参考訳）: 潜在空間探索を用いたポリシー適応による組合せ最適化
• Authors: Felix Chalumeau, Shikha Surana, Clement Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, Thomas D. Barrett
• Abstract要約: 本稿では,複雑なNPハード問題を解くために,パフォーマンスアルゴリズムを設計するための新しいアプローチを提案する。 我々の検索戦略は11の標準ベンチマークタスクにおける最先端のアプローチよりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 46.02102888864839
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial Optimization underpins many real-world applications and yet, designing performant algorithms to solve these complex, typically NP-hard, problems remains a significant research challenge. Reinforcement Learning (RL) provides a versatile framework for designing heuristics across a broad spectrum of problem domains. However, despite notable progress, RL has not yet supplanted industrial solvers as the go-to solution. Current approaches emphasize pre-training heuristics that construct solutions but often rely on search procedures with limited variance, such as stochastically sampling numerous solutions from a single policy or employing computationally expensive fine-tuning of the policy on individual problem instances. Building on the intuition that performant search at inference time should be anticipated during pre-training, we propose COMPASS, a novel RL approach that parameterizes a distribution of diverse and specialized policies conditioned on a continuous latent space. We evaluate COMPASS across three canonical problems - Travelling Salesman, Capacitated Vehicle Routing, and Job-Shop Scheduling - and demonstrate that our search strategy (i) outperforms state-of-the-art approaches on 11 standard benchmarking tasks and (ii) generalizes better, surpassing all other approaches on a set of 18 procedurally transformed instance distributions.
• Abstract（参考訳）: Combinatorial Optimizationは多くの現実世界のアプリケーションを支えるが、これらの複雑なNPハードを解くために高性能なアルゴリズムを設計することは、依然として重要な研究課題である。 強化学習(RL)は、幅広い問題領域にわたるヒューリスティックを設計するための汎用的なフレームワークを提供する。 しかし、顕著な進歩にもかかわらず、RLは産業用解決器をGo-toソリューションとして置き換えていない。 現在のアプローチでは、ソリューションを構築するが、単一のポリシーから多数のソリューションを確率的にサンプリングしたり、個々の問題インスタンスに対して計算的に高価な微調整を施したりといった、限定的なばらつきを持つ探索手順に依存する事前学習ヒューリスティックが強調されている。 提案手法は,事前学習中に推論時間における性能的探索を期待する直観に基づいて,連続的な潜在空間上で条件付けられた多様かつ専門的なポリシーの分布をパラメータ化する新しいRL手法であるCompASSを提案する。 トラベリングセールスマン、キャパシタンドカールーティング、ジョブショップスケジューリングの3つの標準問題におけるCompASSを評価し、検索戦略を実証する。 (i)11の標準ベンチマークタスクにおける最先端アプローチと性能 (ii)18の手続き変換されたインスタンス分布の組の他のすべてのアプローチを上回って、より一般化する。

関連論文リスト

• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  我々はC-PGと呼ばれる探索非依存のアルゴリズムを導入し、このアルゴリズムは(弱)勾配支配仮定の下でのグローバルな最終点収束を保証する。 制約付き制御問題に対して,我々のアルゴリズムを数値的に検証し,それらを最先端のベースラインと比較する。
  論文  参考訳（メタデータ） (2024-07-15T14:54:57Z)
• Joint Demonstration and Preference Learning Improves Policy Alignment with Human Feedback [58.049113055986375]
  我々は、報酬モデルとポリシーをトレーニングするために、AIHF(Alignment with Integrated Human Feedback)と呼ばれる単一ステージアプローチを開発する。 提案した手法は、一般的なアライメントアルゴリズムに容易に還元し、活用できる、効率的なアルゴリズムの集合を認めている。 本研究では,LLMにおけるアライメント問題と,MuJoCoにおけるロボット制御問題を含む広範な実験により,提案手法の有効性を実証する。
  論文  参考訳（メタデータ） (2024-06-11T01:20:53Z)
• Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach [0.3093890460224435]
  我々は、新しい強化学習手法を用いて、人気のあるWordleパズルの解法に対処する。 Wordleパズルでは、比較的控えめな計算コストで最適に近いオンラインソリューション戦略が得られる。
  論文  参考訳（メタデータ） (2022-11-15T03:46:41Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)
• Efficient lifting of symmetry breaking constraints for complex combinatorial problems [9.156939957189502]
  この作業は、Answer Set Programmingのためのモデルベースのアプローチの学習フレームワークと実装を拡張します。 Inductive Logic Programming System ILASPに新たなコンフリクト解析アルゴリズムを組み込む。
  論文  参考訳（メタデータ） (2022-05-14T20:42:13Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Math Programming based Reinforcement Learning for Multi-Echelon Inventory Management [1.9161790404101895]
  強化学習は、ロボット工学、ゲーム、その他多くの分野において、かなりのブレークスルーをもたらしている。 しかし、複雑な実世界の意思決定問題におけるRLの応用は依然として限られている。 これらの特徴は、ステップアクションの問題を解くために列挙法に依存する既存のRL法において、問題を解くのをかなり難しくする。 本研究では,不確実性分布の適切に選択された離散化が,不確実性からのサンプルがごく少ない場合でも,最適なアクターポリシーに近づきうることを示す。 PARLはベースストックを44.7%、RL法を12.1%上回っている。
  論文  参考訳（メタデータ） (2021-12-04T01:40:34Z)
• SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning [102.78958681141577]
  SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。 SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
  論文  参考訳（メタデータ） (2020-07-09T17:08:44Z)
• Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
  最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。 強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
  論文  参考訳（メタデータ） (2020-03-07T16:19:45Z)

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

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