Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem

• URL: http://arxiv.org/abs/2603.25241v1
• Date: Thu, 26 Mar 2026 09:47:22 GMT
• Title: Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem
• Abstract summary: Neural Combinatorial Optimization has shown promise, but its reliance on online reinforcement learning hampers deployment and underutilizes decades of algorithmic knowledge.<n>We address these limitations by applying the offline RL framework, Decision Transformer, to learn superior strategies directly from datasets.<n>We show that our method consistently produces higher-quality tours than the four classical tours, demonstrating the potential of offline RL to unlock and exceed the performance embedded in existing domain knowledge.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Combinatorial optimization problems like the Traveling Salesman Problem are critical in industry yet NP-hard. Neural Combinatorial Optimization has shown promise, but its reliance on online reinforcement learning (RL) hampers deployment and underutilizes decades of algorithmic knowledge. We address these limitations by applying the offline RL framework, Decision Transformer, to learn superior strategies directly from datasets of heuristic solutions; it aims to not only to imitate but to synthesize and outperform them. Concretely, we (i) integrate a Pointer Network to handle the instance-dependent, variable action space of node selection, and (ii) employ expectile regression for optimistic conditioning of Return-to-Go, which is crucial for instances with widely varying optimal values. Experiments show that our method consistently produces higher-quality tours than the four classical heuristics it is trained on, demonstrating the potential of offline RL to unlock and exceed the performance embedded in existing domain knowledge.

Related papers

• Guided Riemannian Optimization (GuRO): Bridging Model Predictive Control and Decision Transformers [2.3133509474600964]
  Decision-making in high-dimensional, nonlinear systems remains a central challenge in robotics.<n>Model-based methods like Model Predictive Control (MPC) offer sample efficiency and interpretability, but suffer from high sample unstable optimization.<n>We propose a novel framework that integrates MPC with in a sequence decision-making framework.
  arXiv  Detail & Related papers  (2026-08-24T12:55:30Z)
• Optimizers Qualitatively Alter Solutions And We Should Leverage This [62.662640460717476]
  Deep Neural Networks (DNNs) can not guarantee convergence to a unique global minimum of the loss when using only local information, such as SGD.<n>We argue that the community should aim at understanding the biases of already existing methods, as well as aim to build new DNNs with the explicit intent of inducing certain properties of the solution.
  arXiv  Detail & Related papers  (2025-07-16T13:33:31Z)
• Offline RL by Reward-Weighted Fine-Tuning for Conversation Optimization [44.3655156382259]
  We propose a practical approach to offline RL with large language models (LLMs)<n>We recast the problem as reward-weighted fine-tuning, which can be solved using similar techniques to supervised fine-tuning (SFT)
  arXiv  Detail & Related papers  (2025-06-08T01:59:30Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• Q-SFT: Q-Learning for Language Models via Supervised Fine-Tuning [62.984693936073974]
  Value-based reinforcement learning can learn effective policies for a wide range of multi-turn problems.<n>Current value-based RL methods have proven particularly challenging to scale to the setting of large language models.<n>We propose a novel offline RL algorithm that addresses these drawbacks, casting Q-learning as a modified supervised fine-tuning problem.
  arXiv  Detail & Related papers  (2024-11-07T21:36:52Z)
• Preference Elicitation for Offline Reinforcement Learning [59.136381500967744]
  We propose Sim-OPRL, an offline preference-based reinforcement learning algorithm.<n>Our algorithm employs a pessimistic approach for out-of-distribution data, and an optimistic approach for acquiring informative preferences about the optimal policy.
  arXiv  Detail & Related papers  (2024-06-26T15:59:13Z)
• Memory-Enhanced Neural Solvers for Routing Problems [8.255381359612885]
  We present MEMENTO, an approach that leverages memory to improve the search of neural solvers at inference.<n>We validate its effectiveness on the Traveling Salesman and Capacitated Vehicle Routing problems, demonstrating its superiority over tree-search and policy-gradient fine-tuning.<n>We successfully train all RL auto-regressive solvers on large instances, and verify MEMENTO's scalability and data-efficiency.
  arXiv  Detail & Related papers  (2024-06-24T08:18:19Z)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  This paper proposes the first end-to-end differentiable meta-BO framework that generalises neural processes to learn acquisition functions via transformer architectures. We enable this end-to-end framework with reinforcement learning (RL) to tackle the lack of labelled acquisition data.
  arXiv  Detail & Related papers  (2023-05-25T10:58:46Z)
• Q-learning Decision Transformer: Leveraging Dynamic Programming for Conditional Sequence Modelling in Offline RL [0.0]
  Decision Transformer (DT) combines the conditional policy approach and a transformer architecture. DT lacks stitching ability -- one of the critical abilities for offline RL to learn the optimal policy. We propose the Q-learning Decision Transformer (QDT) to address the shortcomings of DT.
  arXiv  Detail & Related papers  (2022-09-08T18:26:39Z)
• Behavioral Priors and Dynamics Models: Improving Performance and Domain Transfer in Offline RL [82.93243616342275]
  We introduce Offline Model-based RL with Adaptive Behavioral Priors (MABE) MABE is based on the finding that dynamics models, which support within-domain generalization, and behavioral priors, which support cross-domain generalization, are complementary. In experiments that require cross-domain generalization, we find that MABE outperforms prior methods.
  arXiv  Detail & Related papers  (2021-06-16T20:48:49Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  Reinforcement learning (RL) has recently emerged as a new framework to tackle these problems. We propose a general RL framework that not only exhibits state-of-the-art empirical performance but also generalizes to a variety class of COPs.
  arXiv  Detail & Related papers  (2021-02-14T18:05:42Z)

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.