精读笔记

Problem Setting

论文标题：Baseline-Free Policy Optimization for Neural Combinatorial Optimization（arXiv preprint / 2026）。

这篇论文不是在解决 TSP/CVRP 本身，也不是在证明 GRPO 是更强的神经启发式 solver；它真正瞄准的是 AM-style NCO 训练中一个长期被当作工程细节处理的问题：policy-gradient 的 baseline 机制是否会成为系统性不稳定源。

在 NCO 里，自回归策略的 reward 是整条解的 cost，梯度天然高方差。AM 使用 frozen rollout baseline，POMO 使用 multi-start shared baseline，本质都是给 trajectory 一个相对参照。但困难点在于：baseline 的质量不是外生给定的，它由同一类策略生成。问题变大后，greedy rollout 可能既不稳定也不够好，于是 advantage 估计从 variance reduction 变成 noisy reference。关键矛盾是：训练需要 baseline 稳定策略，而 baseline 又需要策略已经足够好。

作者把这个矛盾具体化为 TSP-100 上的 collapse：warmup 阶段策略迅速从随机水平改善，但 rollout baseline 一启用后训练退化。这一现象在论文中被解释为策略—baseline 耦合导致的负反馈。这个解释有说服力，但仍需要注意：文中证明的是特定 RL4CO 配置下的 failure mode，不等于所有 rollout-baseline NCO 都必然失败。

Motivation

已有路线的问题不是没有 baseline，而是太依赖 baseline。AM 的 rollout baseline 假设 frozen greedy policy 可以提供稳定参照；POMO 通过多起点利用对称性，降低 variance 并提升探索；PPO 用 learned critic 替代显式 rollout baseline。但这些方案都在某种形式上引入了外部参照：冻结策略、shared group baseline 或 value function。

作者的核心观察是：在小规模 routing 上 baseline 看起来无害，是因为任何合理 greedy tour 都足以作为参照；在更大或更受约束的问题上，这个前提不成立。于是 NCO 缺的不是又一个更复杂的 critic，而是一个不依赖外部 baseline 质量、但仍能从同一实例内产生相对学习信号的优化方式。

选择 GRPO 的动机很直接：LLM alignment 中的 GRPO 已经证明可以用 group-relative reward normalization 替代 learned value baseline。迁移到 NCO 后，同一 instance 下多条 sampled tours 天然形成 preference set，这比语言任务里的人类偏好或 reward model 更干净：cost 是确定的，可直接比较。

Core Idea

核心思想是把 NCO 的 advantage 从“trajectory 相对于外部 baseline 的好坏”改写为“同一 instance 内多个 sampled trajectories 的相对好坏”。这改变了训练信号的参照系：不再问当前解是否优于 frozen greedy policy，而是问它是否优于同一输入下同时采样出的其他解。

这个改写引入了一个很强的 inductive bias：routing policy 的学习信号应该是 instance-conditional ranking，而不是跨 instance 的绝对 reward 回归。由于不同 TSP/CVRP 实例的 cost scale 和难度不同，组内标准化天然消除了实例尺度差异；同时，即使策略整体很差，只要组内存在相对更好的 trajectory，梯度仍可指向局部改进方向。

与 prior 的本质区别在于，GRPO 不维护 frozen policy，也不训练 critic，而是把 baseline 内生化为同一 instance 的采样分布统计量。它不是更强的表示学习方法，而是一种重组 credit assignment 信息流的方法：从外部参照转向局部相对比较。

Method

方法层面真正必要的机制很少。

第一，group sampling。对每个实例采样多条 trajectory，目的是制造可比较对象。单条 trajectory 无法 baseline-free 地给出有方向的 advantage；多条 trajectory 则把一个绝对 cost optimization 问题转成局部排序问题。这里的关键不是 G 的具体数值，而是同一 instance 条件下的竞争集合。

第二，组内 z-score advantage。它解决两个问题：一是避免 reward scale 随 instance size / difficulty 变化影响梯度；二是避免外部 baseline 质量控制训练方向。这个机制把 cost 的绝对值压缩成组内相对位置，因此对 affine reward transformation 不敏感。但它也丢弃了部分绝对差距信息，尤其当组内方差很小时，信号会退化。

第三，PPO-style clipping 与 trajectory reuse。它允许对同一批采样轨迹做多轮更新，提升每个 instance 的利用率，并约束 policy ratio 防止更新过大。这里的收益有两部分：一个是 baseline-free 相对 advantage，另一个是更多 gradient updates / sample reuse。论文通过 update-matched comparison 承认后者不可忽略。

第四，temperature annealing。它不是核心理论贡献，而是维持 group diversity 的工程条件。没有足够多样的 group，z-score advantage 就没有意义。因此温度调度更像使 GRPO 可用的辅助机制，而不是算法本体。

Key Insight / Why It Works

最重要的 insight 是：在 NCO 中，baseline 的作用可以由同一实例下的相对采样分布替代。由于 TSP/CVRP 的 reward 是确定 cost，trajectory 之间的优劣比较几乎无噪声；这使 group-relative optimization 比在 LLM alignment 中更自然。LLM 里 GRPO 依赖 reward model 或偏好信号，NCO 里 cost oracle 本身就是精确 evaluator。

GRPO 有效的原因不是它学到了更好的 graph representation，而是它改变了梯度估计的 failure mode。rollout baseline 的风险在于外部参照和 policy 同源且滞后，一旦 baseline 质量差，advantage 方向会变得混乱；GRPO 的参照来自当前 sampling group，哪怕所有解都很差，也能比较谁相对更好。因此它更像一种 robust credit assignment / local ranking normalization，而不是新 solver。

最可能的核心贡献是“instance-conditioned relative normalization”。这点可迁移到其他 CO/RL 问题：当 absolute reward scale 难以比较、critic 难学、baseline 易崩时，用同一输入下多候选的相对排序替代外部 value 估计，往往更稳。

但论文中的性能增益不能完全归因于这个 insight。epoch-matched 结果里 GRPO 做了约 8 倍 gradient updates，这是典型 optimization scaling / sample reuse 增益。update-matched 后，POMO 仍略优，说明 GRPO 不是 per-update 更高效的方法。更准确的判断是：GRPO 换来了更高稳定性和更高 per-instance 利用率，但牺牲了 per-update efficiency。

P3O 的表现也说明 pairwise relative feedback 本身不够。两条 trajectory 的比较方差更大，尤其在 CVRP 这类约束结构更复杂的问题上，pairwise signal 可能太稀疏或太受采样偶然性影响。GRPO 的 group statistic 比 pairwise preference 更稳，这可能是它优于 P3O 的真正原因。

Relation To Prior Work

这篇论文最接近三条路线：AM/REINFORCE rollout baseline、POMO multi-start optimization、以及 LLM alignment 中的 GRPO/P3O。

相对 AM，区别不是 architecture，而是去掉 frozen rollout baseline。AM 的 baseline 是一个外部 greedy policy snapshot；GRPO 的 baseline 是组内 return 均值和方差。前者依赖历史策略质量，后者依赖当前采样多样性。

相对 POMO，GRPO 和它都使用多个解，但语义不同。POMO 的多起点利用 routing 问题的多最优解/对称性，shared baseline 更像结构先验；GRPO 的多样本是同一 instance 下的相对 ranking pool，主要服务于 advantage normalization。POMO 是把问题结构编码进训练过程，GRPO 是把 reward comparison 编码进优化过程。

相对 PPO/critic 方法，GRPO 避免学习一个从 graph state 预测 episode return 的 value function。对于 NCO，这个 critic 问题很难，因为初始 graph 到最终 tour cost 的映射高度依赖策略分布和组合结构。论文中 PPO 在大实例早停/退化，与这个判断一致。

从技术谱系看，这不是 NCO 里的全新范式，而是把 preference / relative policy optimization 搬到 combinatorial construction policy 上。实质创新在于发现 NCO 的 deterministic cost oracle 与 group-relative optimization 非常匹配，并用 baseline collapse 作为切入点证明其价值。看似新颖的部分主要是跨领域重组，而非新优化理论。

Dataset / Evaluation

evaluation 覆盖了 TSP 和 CVRP 两类标准 routing benchmark，规模到 100 节点，统一使用 RL4CO 和同一 AM architecture。这足以检验“在标准 learned-routing 设置下 GRPO 是否可替代 rollout baseline”，但不足以支持更广泛的“baseline-free 更 scalable”结论。

论文较好的地方是做了 epoch-matched 和 gradient-update-matched 两种比较。前者展示 practical training speed，后者揭示 GRPO 的优势很大程度来自更多 inner updates。这个区分非常关键，否则结论会被 compute budget 污染。

不过 evaluation 仍偏窄：只有两种 problem family、两组 seed、单一 architecture、greedy decoding，没有 TSP-200+、更强约束 VRP、distribution shift、真实 logistics 或 simulator-in-the-loop 设置。所谓 larger/harder 主要是 TSP-100 和 CVRP-100，离真正复杂部署还很远。

核心 claim 中“REINFORCE rollout baseline 会结构性失败”只在 TSP-100 上非常强，在 CVRP-100 上 REINFORCE 延长训练反而可以达到不错结果。这意味着 baseline fragility 是条件性的，而不是普遍定律。文中未充分说明为什么 TSP-100 更触发 collapse，而 CVRP-100 不同。

没有明显 benchmark leakage 或 memorization 问题，因为训练实例在线生成、验证/测试固定。但由于分布是标准 uniform random Euclidean routing，数据覆盖很规则，不能证明真实场景泛化。

Limitation

最大的限制是归因仍不完全清楚。GRPO 的效果来自三件事混合：baseline-free group-relative advantage、多 trajectory exploration、以及多轮 PPO inner updates。论文做了 update-matched 对照，但没有充分 ablate group size、temperature、inner epoch、z-score vs mean baseline 等因素，因此无法精确判断哪一项贡献最大。

方法成立依赖组内 diversity。如果 sampling temperature 降低后多条 trajectory 收敛到相同或近似相同解，组内标准差趋近于零，advantage 会退化。换句话说，GRPO 不是不需要 baseline，而是把 baseline 问题转移成“如何持续产生有信息量的候选集”。这在大规模、强约束或 near-deterministic policy 下可能成为新的瓶颈。

scalability 上限也不明确。每个实例采样 G 条 trajectory，再做多轮 inner update，会增加显存、采样和优化成本。对于节点数更大、解构造更长的问题，trajectory log-prob 存储和 ratio 计算成本可能不可忽略。GRPO 更 sample-efficient per unique instance，但不一定 wall-clock efficient。

REINFORCE collapse 的解释有一定说服力，但可能过度归因于 rollout baseline 本身。warmup 只有 1 epoch、baseline 切换突然、temperature 固定、entropy/control 设置等都可能放大失败。文中未充分说明更平滑 baseline schedule 或更长 warmup 是否能修复。因此“结构性漏洞”这个表述偏强。

泛化 claim 也有限。论文没有证明 GRPO 学到更 general 的 routing heuristics；它只是更稳定地优化同一分布上的 AM policy。所谓更 scalable 目前主要是训练机制稳定性，而不是解质量随规模外推的证据。

Takeaway

• 1. 对 NCO 来说，baseline 不是纯 variance reduction 工具；在困难实例上它可能成为训练动力学的一部分，并引入负反馈。
• 以后比较 NCO 训练算法时，baseline schedule 和 failure dynamics 应该被当作核心变量，而不是实现细节。
• 2. 同一 instance 下的多候选相对比较是一个很值得迁移的范式。
• 它适合任何 reward 可精确计算、但 critic 难学、absolute scale 不稳定的组合优化问题。

一句话总结

这篇论文把 GRPO 从 LLM alignment 迁移到 NCO，实质贡献是用 instance-level relative ranking 替代 rollout/critic baseline，从而暴露并部分绕开 AM-style policy-gradient 在困难 routing 实例上的 baseline 耦合脆弱性。