Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization

• URL: http://arxiv.org/abs/2407.17206v1
• Date: Wed, 24 Jul 2024 12:06:09 GMT
• Title: Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization
• Authors: Jonathan Pirnay, Dominik G. Grimm,
• Abstract summary: We present a simple and problem-independent sequence decoding method for self-improved learning. By modifying the policy to ignore previously sampled sequences, we force it to consider only unseen alternatives. Our method outperforms previous NCO approaches on the Job Shop Scheduling Problem.
• Score: 1.1510009152620668
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The constructive approach within Neural Combinatorial Optimization (NCO) treats a combinatorial optimization problem as a finite Markov decision process, where solutions are built incrementally through a sequence of decisions guided by a neural policy network. To train the policy, recent research is shifting toward a 'self-improved' learning methodology that addresses the limitations of reinforcement learning and supervised approaches. Here, the policy is iteratively trained in a supervised manner, with solutions derived from the current policy serving as pseudo-labels. The way these solutions are obtained from the policy determines the quality of the pseudo-labels. In this paper, we present a simple and problem-independent sequence decoding method for self-improved learning based on sampling sequences without replacement. We incrementally follow the best solution found and repeat the sampling process from intermediate partial solutions. By modifying the policy to ignore previously sampled sequences, we force it to consider only unseen alternatives, thereby increasing solution diversity. Experimental results for the Traveling Salesman and Capacitated Vehicle Routing Problem demonstrate its strong performance. Furthermore, our method outperforms previous NCO approaches on the Job Shop Scheduling Problem.

Related papers

• Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement [1.1510009152620668]
  Current methods for constructive neural optimization usually train a policy using behavior cloning from expert solutions or policy gradient methods from reinforcement learning. We bridge the two by sampling multiple solutions for random instances using the current model in each epoch and then selecting the best solution as an expert trajectory for supervised imitation learning. We evaluate our approach on the Traveling Salesman Problem and the Capacitated Vehicle Routing Problem. The models trained with our method achieve comparable performance and generalization to those trained with expert data.
  arXiv  Detail & Related papers  (2024-03-22T13:09:10Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Sample-Efficient Multi-Objective Learning via Generalized Policy Improvement Prioritization [8.836422771217084]
  Multi-objective reinforcement learning (MORL) algorithms tackle sequential decision problems where agents may have different preferences. We introduce a novel algorithm that uses Generalized Policy Improvement (GPI) to define principled, formally-derived prioritization schemes. We empirically show that our method outperforms state-of-the-art MORL algorithms in challenging multi-objective tasks.
  arXiv  Detail & Related papers  (2023-01-18T20:54:40Z)
• Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach [0.3093890460224435]
  We address the solution of the popular Wordle puzzle, using new reinforcement learning methods. For the Wordle puzzle, they yield on-line solution strategies that are very close to optimal at relatively modest computational cost.
  arXiv  Detail & Related papers  (2022-11-15T03:46:41Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  Various algorithms for reinforcement learning (RL) exhibit dramatic variation in their convergence rates as a function of problem structure. This research provides guarantees that explain textitex post the performance differences observed. A natural next step is to convert these theoretical guarantees into guidelines that are useful in practice.
  arXiv  Detail & Related papers  (2022-01-21T04:25:35Z)
• Modularity in Reinforcement Learning via Algorithmic Independence in Credit Assignment [79.5678820246642]
  We show that certain action-value methods are more sample efficient than policy-gradient methods on transfer problems that require only sparse changes to a sequence of previously optimal decisions. We generalize the recently proposed societal decision-making framework as a more granular formalism than the Markov decision process.
  arXiv  Detail & Related papers  (2021-06-28T21:29:13Z)
• Logistic Q-Learning [87.00813469969167]
  We propose a new reinforcement learning algorithm derived from a regularized linear-programming formulation of optimal control in MDPs. The main feature of our algorithm is a convex loss function for policy evaluation that serves as a theoretically sound alternative to the widely used squared Bellman error.
  arXiv  Detail & Related papers  (2020-10-21T17:14:31Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
  This paper presents a framework to tackle constrained optimization problems using deep Reinforcement Learning (RL) We extend the Neural Combinatorial Optimization (NCO) theory in order to deal with constraints in its formulation. In that context, the solution is iteratively constructed based on interactions with the environment.
  arXiv  Detail & Related papers  (2020-06-22T03:13:07Z)
• A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning [3.614984020677526]
  This paper proposes a Deep Reinforcement Learning (DRL) approach for solving knapsack problem. The state aggregation policy is applied to each problem instance of the knapsack problem. The proposed model with the state aggregation strategy not only gives better solutions but also learns in less timesteps, than the one without state aggregation.
  arXiv  Detail & Related papers  (2020-04-25T11:52:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.