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

Hironori Ohigashi; Shinichiro Hamada

cs.LGMar 26, 2026

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

Authors: Hironori Ohigashi, Shinichiro Hamada

Organizations: Panasonic Connect Co., Ltd., Japan

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.

Figures & tables

Figure 1: Overview of the proposed method’s architecture. The transformer encoder calculates a node embedding vector from the coordinates of the graph nodes. As observation $o_{t}$ and action $a_{t}$ , the embedding vectors $\boldsymbol{f}^{e}_{t}$ and $\boldsymbol{f}^{e}_{t+1}$ of the nodes transitioned at time $t$ and $t+1$ , respectively, are input to the causal transformer decoder along with the RTG $\hat{R}_{t}$ . The value $\tilde{R}_{t}$ is the RTG prediction by the causal transformer decoder.

Data	Method	$N=20$	$N=50$	$N=100$
NN	Original	17.24 $\pm$ 10.24	22.73 $\pm$ 8.21	24.81 $\pm$ 6.47
	BC	17.28 $\pm$ 10.23	22.74 $\pm$ 8.21	24.75 $\pm$ 6.50
	DT (Ours)	16.73 $\pm$ 10.07	22.60 $\pm$ 8.17	24.76 $\pm$ 6.48
NI	Original	13.24 $\pm$ 6.99	19.12 $\pm$ 4.78	21.77 $\pm$ 3.43
	BC	12.26 $\pm$ 7.13	18.20 $\pm$ 5.44	22.00 $\pm$ 5.29
	DT (Ours)	6.43 $\pm$ 4.86	14.98 $\pm$ 4.91	19.84 $\pm$ 4.85

Table 1: Optimality gap (%) and its standard deviation for each method on the test dataset. The "Data" column indicates the heuristic method used for training. The "Method" column represents the original heuristic method (Original), behavior cloning (BC), and our proposed method (DT).

		Fixed RTG		Predicted RTG using expectile regression
$N$	Data	0	mean of data	$\alpha=0.50$	$\alpha=0.70$	$\alpha=0.99$
20	NN	67.90 $\pm$ 29.58	17.21 $\pm$ 10.17	17.22 $\pm$ 10.17	17.14 $\pm$ 10.13	16.73 $\pm$ 10.07
	NI	68.39 $\pm$ 26.26	13.12 $\pm$ 7.62	13.09 $\pm$ 6.29	11.02 $\pm$ 5.96	6.43 $\pm$ 4.86
	FI	89.69 $\pm$ 31.21	3.33 $\pm$ 4.78	1.70 $\pm$ 2.33	1.61 $\pm$ 2.27	1.30 $\pm$ 2.27
	SA	106.03 $\pm$ 31.37	2.52 $\pm$ 4.50	0.97 $\pm$ 1.77	0.84 $\pm$ 1.50	0.83 $\pm$ 1.60
50	NN	213.67 $\pm$ 41.84	22.71 $\pm$ 8.18	22.69 $\pm$ 8.17	22.66 $\pm$ 8.17	22.60 $\pm$ 8.17

Table 2: Optimality gap (%) for different RTG targets (Fixed vs. Predicted) and values of

\alpha

N=20,50

Data	$N=20$ (offset)	$N=50$ (offset)	$N=100$ (offset)
NN	15.82 $\pm$ 9.96 (1.00)	22.45 $\pm$ 8.14 (1.00)	24.58 $\pm$ 6.49 (2.00)
NI	3.94 $\pm$ 4.34 (0.50)	10.40 $\pm$ 5.10 (2.00)	16.50 $\pm$ 5.06 (2.00)
FI	1.29 $\pm$ 2.21 (-0.05)	3.07 $\pm$ 2.37 (0.20)	4.51 $\pm$ 2.20 (0.50)
SA	0.79 $\pm$ 1.49 (-0.10)	2.39 $\pm$ 2.10 (0.00)	5.32 $\pm$ 2.87 (0.50)

Table 3: Optimality gap (%) with optimal RTG offsets. The applied offset values are shown in parentheses.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Data	$N=20$	$N=50$	$N=100$
Training	Download	Download	Download
Validation	Download	Generate (Seed 9999)	Generate (Seed 9999)
Test	Download	Download	Download

Appendix

Table 4: Details of TSP dataset generation and sources.

Parameter	$N=20$	$N=50$	$N=100$
Maximum (starting) temperature	2.5	2.5	2.5
Minimum (ending) temperature	0.025	0.0025	0.0025
Number of iterations	50,000	5,000,000	5,000,000

Appendix

Table 5: Hyperparameters for SA used for generating solution data.

Parameter	Value
Number of layers	2
Number of attention heads	8
Embedding dimension	128
Activation function	GELU
Normalization method	Layer Normalization
Dropout rate	0.0

Appendix

Table 6: Architectural details of the transformer encoder.

Parameter	Value
Number of layers	2
Number of attention heads	8
Embedding dimension	128
Activation function	GELU
Normalization method	Layer Normalization
Dropout rate	0.0

Appendix

Table 7: Architectural details of the Causal transformer decoder.

Parameter	Value
Loss balance coefficient $c$	0.5
Optimizer	Schedule-Free AdamW [ 6 ]
Learning rate	0.0025
Weight decay	0.0
AdamW betas	(0.9, 0.999)
AdamW epsilon	1e-8

Appendix

Table 8: Training hyperparameters.

Parameter	$N=20$	$N=50$	$N=100$
Training time	19 hours	1 days 3 hours	1 days 23 hours
Prediction time	0.63 seconds	0.86 seconds	1.10 seconds

Appendix

Table 9: The computational time in training and predicting on NN dataset. The prediction time was measured as the duration required to predict a single instance.

Data	Method	$N=20$	$N=50$	$N=100$
Optimal		3.83 $\pm$ 0.30	5.69 $\pm$ 0.25	7.76 $\pm$ 0.23
NN	Original	4.49 $\pm$ 0.55	6.99 $\pm$ 0.57	9.69 $\pm$ 0.58
	BC	4.49 $\pm$ 0.54	6.99 $\pm$ 0.57	9.69 $\pm$ 0.58
	DT (Ours)	4.47 $\pm$ 0.54	6.98 $\pm$ 0.56	9.69 $\pm$ 0.58
NI	Original	4.33 $\pm$ 0.39	6.78 $\pm$ 0.35	9.45 $\pm$ 0.33
	BC	4.30 $\pm$ 0.39	6.73 $\pm$ 0.37	9.47 $\pm$ 0.44

Appendix

Table 10: Actual average solution costs corresponding to the optimality gaps reported in Table 1 . The first row "Optimal" shows the average cost of the optimal solutions.

		Fixed RTG		Predicted RTG using expectile regression
$N$	Data	0	mean of data	$\alpha=0.50$	$\alpha=0.70$	$\alpha=0.99$
20	NN	6.43 $\pm$ 1.25	4.49 $\pm$ 0.54	4.49 $\pm$ 0.54	4.49 $\pm$ 0.54	4.47 $\pm$ 0.54
	NI	6.44 $\pm$ 1.04	4.32 $\pm$ 0.23	4.33 $\pm$ 0.36	4.25 $\pm$ 0.36	4.07 $\pm$ 0.33
	FI	7.25 $\pm$ 1.23	3.95 $\pm$ 0.26	3.90 $\pm$ 0.33	3.89 $\pm$ 0.32	3.88 $\pm$ 0.33
	SA	7.88 $\pm$ 1.27	3.92 $\pm$ 0.26	3.87 $\pm$ 0.32	3.86 $\pm$ 0.32	3.86 $\pm$ 0.32
50	NN	17.84 $\pm$ 2.38	6.99 $\pm$ 0.56	6.98 $\pm$ 0.56	6.98 $\pm$ 0.57	6.98 $\pm$ 0.56

Appendix

Table 11: Actual average solution costs corresponding to the optimality gaps reported in Table 2 .

Data	$N=20$ (offset)	$N=50$ (offset)	$N=100$ (offset)
NN	4.44 $\pm$ 0.53 (1.00)	6.97 $\pm$ 0.56 (1.00)	9.67 $\pm$ 0.58 (2.00)
NI	3.98 $\pm$ 0.36 (0.50)	6.28 $\pm$ 0.38 (2.00)	9.04 $\pm$ 0.45 (2.00)
FI	3.88 $\pm$ 0.32 (-0.05)	5.87 $\pm$ 0.29 (0.20)	8.11 $\pm$ 0.28 (0.50)
SA	3.86 $\pm$ 0.32 (-0.10)	5.83 $\pm$ 0.29 (0.00)	8.18 $\pm$ 0.31 (0.50)

Appendix

Table 12: Actual average solution costs corresponding to the optimality gaps reported in Table 3 . The applied offset values are shown in parentheses.

Pointer Networks

See all 10 papers

Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search
Jul 26, 2026Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang +1Traveling Salesperson Problem Inference-Time Search
Department of Psychology, The University of Warwick, Coventry, United Kingdom. · Department of Psychology, The University of Hong Kong, Hong Kong, China. · Department of Psychology, The Chinese University of Hong Kong, Hong Kong, China. +2
Compute Time Scaling with Recursive Models for Combinatorial Optimization
Sep 28, 2026Zhengxi Zhang, Paul SwobodaTraveling Salesperson Problem Inference-Time Scaling
GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem
Jun 22, 2026Xiang LiTraveling Salesperson Problem Graph Neural Networks
College of Computer Science, Yangtze University, Jingzhou, China

Jul 26, 2026J/K move · Enter open · S save

Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search

Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang, Ming Meng

Department of Psychology, The University of Warwick, Coventry, United Kingdom. · Department of Psychology, The University of Hong Kong, Hong Kong, China. · Department of Psychology, The Chinese University of Hong Kong, Hong Kong, China.+2

Traveling Salesperson Problem Inference-Time Search Combinatorial Optimization Imitation Learning RL for Combinatorial Optimization Neural Combinatorial Optimization

Open paper AskPDF arXiv

Humans often find good solutions to combinatorial optimization problems that are computationally hard even for advanced computer algorithms. In the Euclidean traveling salesman problems (TSP), people rapidly produce tours that are near-optimal, despite severe limits on time and computation. What makes a tour human-like, and how might such solutions be learned? Here we address these questions through a large-scale behavioral and computational investigation of human performance in Euclidean TSP. We sampled a broad space of TSP instances, collected human solutions, and compared them with neural policies based on Pointer Networks, which are recurrent neural networks with an attention-based pointing mechanism that define probability distributions over valid tours. We trained these networks under multiple objectives, including reinforcement learning (RL), supervised learning from optimal tours, supervised learning from human tours, and RL fine-tuning after optimal-supervised pretraining. Human tours were not identical to optimal tours, but occupied a near-optimal geometric basin: they shared many structural properties with optimal solutions while preserving systematic human-specific deviations. The best account of human tours was not direct imitation of optimal tours, but a model pretrained on optimal tours, fine-tuned by RL, and decoded through

\text{Best-of-}N

sampling. These findings suggest that human-like solutions may emerge from a combination of structured supervised learning, RL, and test-time search, echoing computational principles underlying many modern artificial intelligence systems.

Abstract

Pointer Networks

Explore similar work

Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search

Compute Time Scaling with Recursive Models for Combinatorial Optimization

GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem