論文の概要: Reinforcement Learning Methods for Neighborhood Selection in Local Search

• arxiv url: http://arxiv.org/abs/2601.07948v1
• Date: Mon, 12 Jan 2026 19:25:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-14 18:27:18.916372
• Title: Reinforcement Learning Methods for Neighborhood Selection in Local Search
• Title（参考訳）: 地域探索における地区選択のための強化学習手法
• Authors: Yannick Molinghen, Augustin Delecluse, Renaud De Landtsheer, Stefano Michelini,
• Abstract要約: 我々は,強化学習に基づく地区選択戦略の評価を行った。 本稿では,検索固有の特徴,特に制約違反によるコストの変動が,慎重に設計された報酬関数を必要とすることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning has recently gained traction as a means to improve combinatorial optimization methods, yet its effectiveness within local search metaheuristics specifically remains comparatively underexamined. In this study, we evaluate a range of reinforcement learning-based neighborhood selection strategies -- multi-armed bandits (upper confidence bound, $ε$-greedy) and deep reinforcement learning methods (proximal policy optimization, double deep $Q$-network) -- and compare them against multiple baselines across three different problems: the traveling salesman problem, the pickup and delivery problem with time windows, and the car sequencing problem. We show how search-specific characteristics, particularly large variations in cost due to constraint violation penalties, necessitate carefully designed reward functions to provide stable and informative learning signals. Our extensive experiments reveal that algorithm performance varies substantially across problems, although that $ε$-greedy consistently ranks among the best performers. In contrast, the computational overhead of deep reinforcement learning approaches only makes them competitive with a substantially longer runtime. These findings highlight both the promise and the practical limitations of deep reinforcement learning in local search.
• Abstract（参考訳）: 強化学習は,最近,組合せ最適化法の改良手段として注目されているが,局所探索メタヒューリスティックスにおけるその有効性は,比較的過小評価されている。 本研究では,多武装の盗賊(upper confidence bound,$ε$-greedy)と深層強化学習(proximal policy optimization, double deep $Q$-network)を対象とし,旅行セールスマン問題,時間窓付きピックアップ・デリバリー問題,カーシークエンシング問題という3つの異なる問題に比較した。 本稿では,検索固有の特徴,特に制約違反によるコストの変動が,安定かつ情報的な学習信号を提供するために,慎重に設計された報酬関数を必要とすることを示す。 我々の広範な実験によると、アルゴリズムの性能は問題によって大きく異なるが、$ε$-greedyは一貫して最高のパフォーマーにランク付けされている。 対照的に、深層強化学習アプローチの計算オーバーヘッドは、かなり長いランタイムと競合するだけである。 これらの結果は,地域探索における深層強化学習の約束と実践的限界の両方を浮き彫りにした。

関連論文リスト

• RLIF: Interactive Imitation Learning as Reinforcement Learning [56.997263135104504]
  我々は,対話型模倣学習と類似するが,さらに実践的な仮定の下で,非政治強化学習によってパフォーマンスが向上できることを実証する。 提案手法は,ユーザ介入信号を用いた強化学習を報奨として利用する。 このことは、インタラクティブな模倣学習において介入する専門家がほぼ最適であるべきだという仮定を緩和し、アルゴリズムが潜在的に最適でない人間の専門家よりも改善される行動を学ぶことを可能にする。
  論文  参考訳（メタデータ） (2023-11-21T21:05:21Z)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)
• Adversarial Robustness with Semi-Infinite Constrained Learning [177.42714838799924]
  入力に対する深い学習は、安全クリティカルなドメインでの使用に関して深刻な疑問を提起している。 本稿では,この問題を緩和するために,Langevin Monte Carlo のハイブリッドトレーニング手法を提案する。 当社のアプローチは、最先端のパフォーマンスと堅牢性の間のトレードオフを軽減することができることを示す。
  論文  参考訳（メタデータ） (2021-10-29T13:30:42Z)
• Off-policy Reinforcement Learning with Optimistic Exploration and Distribution Correction [73.77593805292194]
  我々は、政治以外のアクター批判的枠組みにおいて、批評家のほぼ上位信頼度を最大化するために、別の調査政策を訓練する。 最近導入されたDICEフレームワークを応用して、非政治アクター犯罪訓練のための分布補正比を学習する。
  論文  参考訳（メタデータ） (2021-10-22T22:07:51Z)
• Learning Enhanced Optimisation for Routing Problems [3.747361228408185]
  L2GLS(Learning to Guide Local Search)は、ルーティング問題に対する学習ベースのアプローチである。 L2GLSは、局所探索(LS)演算子の強度とペナルティ項を組み合わせ、局所最適から逃れる。 L2GLSは、他の機械学習手法よりも大きなTSPとCVRPに対して、最先端の新たな結果が得られることを示す。
  論文  参考訳（メタデータ） (2021-09-17T04:47:26Z)
• MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learning [65.52675802289775]
  本研究では,不確かさを意識した分類器が,強化学習の難しさを解消できることを示す。 正規化最大度(NML)分布の計算法を提案する。 得られたアルゴリズムは、カウントベースの探索法と、報酬関数を学習するための先行アルゴリズムの両方に多くの興味深い関係を持つことを示す。
  論文  参考訳（メタデータ） (2021-07-15T08:19:57Z)
• Learning Vehicle Routing Problems using Policy Optimisation [4.093722933440819]
  最先端のアプローチは強化学習を使ってポリシーを学習し、学習ポリシーは擬似解法として機能する。 これらのアプローチは、あるケースでは優れた性能を示しているが、ルーティング問題に典型的な大きな検索空間を考えると、ポリシーの貧弱さに早すぎる可能性がある。 より多くのポリシーを提供することで探索を支援するエントロピー正規化強化学習(ERRL)を提案する。
  論文  参考訳（メタデータ） (2020-12-24T14:18:56Z)
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
  古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
  論文  参考訳（メタデータ） (2020-10-07T01:33:06Z)
• Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning [2.4565068569913384]
  本研究では,2オプト演算子に基づく局所的な探索勾配を深層強化学習により学習することを提案する。 学習したポリシは、ランダムな初期解よりも改善でき、従来の最先端のディープラーニング手法よりも高速に、ほぼ最適解にアプローチできることを示す。
  論文  参考訳（メタデータ） (2020-04-03T14:51:54Z)
• Average Reward Adjusted Discounted Reinforcement Learning: Near-Blackwell-Optimal Policies for Real-World Applications [0.0]
  強化学習は、与えられたマルコフ決定プロセスの最適な定常ポリシーを見つけることを目的としている。 本稿では,広く適用されている標準割引強化学習フレームワークについて,理論的考察を行う。 我々はブラックウェル-最適強化学習アルゴリズムを新たに構築する。
  論文  参考訳（メタデータ） (2020-04-02T08:05:18Z)

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

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