ニューラル組合せ最適化のためのオフライン・ディシジョン・トランスフォーマ：巡回セールスマン問題でヒューリスティックを上回る

要旨: トラベリング・セールスマン問題のような組合せ最適化問題は産業において重要であるにもかかわらずNP困難です。ニューラル組合せ最適化は有望であることが示されていますが、そのオンライン強化学習（RL）への依存は導入を妨げるとともに、数十年にわたるアルゴリズム知識を十分に活用できていません。私たちは、オフラインRLフレームワークであるDecision Transformerを適用することで、これらの制約を解決します。ヒューリスティック解のデータセットから直接より優れた戦略を学習し、単に模倣するだけでなく、それらを合成し、さらに上回ることを目指します。具体的には、（i）ポインタネットワークを統合して、ノード選択のインスタンス依存の可変な行動空間を扱い、（ii）Return-to-Goの楽観的な条件付けに重要なexpectile回帰を用います。これは、最適値が大きく変動するインスタンスにとって特に重要です。実験の結果、提案手法は学習対象である4つの古典的ヒューリスティックよりも一貫して高品質な巡回路を生成し、オフラインRLが既存のドメイン知識に内在する性能を解き放ち、さらに超える可能性を示しています。