acceptodds
Withdrawn from ICLR 2027

When Random Exploration Fails: Directed Exploration for Combinatorial Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Sparse-reward reinforcement learning (RL) poses a fundamental challenge for combinatorial optimization problems (COPs): when rewarding solutions are rarely sampled, the policy receives little useful gradient signal and training can stall. A natural remedy is to perturb the learning process to encourage exploration, but it remains unclear whether simply increasing stochasticity is sufficient. We systematically study undirected perturbations, including Gaussian noise in the weight, reward, and gradient spaces and NoisyNet, and find a consistent pattern: they can accelerate learning when rewarding trajectories are already reachable, but do not reliably enable learning once the vanilla policy is trapped in a zero-reward regime. This motivates directed exploration. We introduce Construction-Sequence Exploration (CSE), which maintains visitation counts over consecutive decisions in the autoregressive construction sequence and rewards trajectories containing under-explored transitions. Unlike random perturbations, this count-based novelty signal remains informative when the extrinsic reward vanishes and explicitly directs the policy toward less explored solution structures. Across eight routing, scheduling, and subset-selection COPs, CSE enables learning in challenging sparse-reward settings where vanilla RL and undirected exploration often fail, while preserving performance under dense rewards.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, combinatorial optimization, sparse reward

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_ZieqOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies sparse feedback in autoregressive RL for combinatorial optimization. It compares several exploration strategies and proposes Construction-Sequence Exploration (CSE), which uses decayed visitation counts of consecutive construction decisions to provide a novelty bonus that is gradually annealed during training. Experiments cover eight combinatorial optimization problems and evaluate final costs under various dense and gated reward settings.

Critical strengths

None

Critical weaknesses

The motivation is questionable. Section 3.1 defines the COP reward such that only a complete globally optimal solution receives nonzero reward. This is not the standard setting in RL4CO or NCO, where the cost of a feasible solution is typically used as a dense terminal objective. If the paper intends to study sparse rewards, it should clearly frame this as an artificially constructed threshold or gated benchmark rather than a general COP setting.

The experimental evaluation is insufficiently justified and documented. The paper repeatedly refers to globally optimal solutions, yet does not clarify whether exact optima are available for all tasks, how they are obtained, or how they are used. Even basic information such as instance sizes is missing, along with important details on instance generation, dataset splits, training settings, and inference procedures. The set of compared methods is also quite limited, making it difficult to assess the significance of the reported results. Moreover, the evaluation mainly reports raw final costs without optimality gaps or other standard metrics, making it difficult to assess solution quality or compare performance across tasks. Finally, some of the related GFlowNet references described as “recent” are in fact relatively old, which raises concerns about the completeness and currency of the related-work discussion.

Questions for authors

I would like the authors to restate their motivation and clearly define the reward function for the COP.

Reviewer_18muOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies exploration for sparse-reward RL in combinatorial optimization. It first motivates by showing undirected perturbations (Gaussian noise in weights, rewards or gradients, and NoisyNet) can speed up learning when rewarding solutions are already reachable, but fail when the policy is stuck with zero reward, which is more often under sparse reward setting. It then proposes Construction-Sequence Exploration (CSE), which reduces visitation counts over consecutive construction decisions (edges) and adds an annealed novelty bonus to the return. CSE is evaluated on eight different problems under sparse and dense rewards.

Critical strengths
  1. The problem is relevant, and the method is simple and cheap to implement.
  2. The distinction between undirected and directed exploration in COPs is clearly motivated, and the experiments cover a reasonable range of problem types.
Critical weaknesses
  1. The results don’t support the main claims. In Table 1, CSE is best only on PCTSP. Undirected reward noise beats it on TSP, CVRP and SMTWTP, which contradicts the paper’s central argument.
  2. There are internal inconsistencies in its paper writing. The captions of Figs. 3, 4 and 5 describe content the figures don’t show (for example, Fig. 4’s "distinct valid tours" and "undirected noise"). The Table 1 caption lists OP as a success, while line 356 says all methods fail on OP. The training budget is given as 500, 250 or 2500 steps depending on the section.
  3. Similar to the 2nd point mentioned above, the setup is unclear. The reward in sec. 3.1 (nonzero only for globally optimal solutions) doesn’t match the threshold-based rewards in the appendix, and Table 1 doesn’t say which reward mode is used. The adaptive perturbation in Sec. 3.3 is presented as a contribution but never evaluated.
Questions for authors
  1. Which reward mode (threshold, gated or sparse) and problem size are used in Table 1?
  2. Given that reward noise outperforms CSE on TSP, CVRP and SMTWTP, how do you reconcile this with the claim that undirected perturbations fail in sparse regimes?
  3. Can you clarify the training budget and explain why the TSP-100 results differ between Table 1 and the ablations?
  4. How does CSE compare to standard count-based or novelty methods such as RND or pseudo-counts applied to the same construction states?
Reviewer_VuJoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies exploration strategies for sparse-reward reinforcement learning in combinatorial optimization. After examining several undirected perturbation methods, the authors propose Construction-Sequence Exploration (CSE), which uses decayed edge-visitation counts to provide intrinsic rewards for under-explored action transitions. Experiments across eight combinatorial optimization problems show that CSE can improve learning under artificially sparse rewards while maintaining competitive performance in dense-reward settings.

Critical strengths
  • Exploration under sparse rewards is an important problem for reinforcement learning, particularly in large combinatorial search spaces.
  • The paper considers eight combinatorial optimization tasks, multiple perturbation baselines, and several ablation studies.
  • The proposed method is simple and easy to implement, with relatively low computational overhead.
Critical weaknesses
  • CSE is essentially a count-based intrinsic reward applied to consecutive action pairs. The distinction from existing count-based exploration is incremental, and the experiments do not establish a substantial advantage of edge-based novelty over other count-based alternatives.
  • Table 1 shows that simple reward perturbation actually outperforms CSE on TSP, CVRP, and SMTWTP. CSE also exhibits substantial variance on TSP and provides little improvement on several other tasks.
  • The ablation results in Figure 3 show only small differences between edge-level, node-level, and full-tour novelty. This raises the question of whether the improvement mainly comes from intrinsic rewards rather than the proposed construction-sequence design.
  • It is unclear how visitation counts are maintained across different problem instances. For example, node indices in randomly generated TSP instances do not necessarily represent the same locations. The authors should clarify whether the count table is instance-specific or shared across training instances.
Questions for authors
  • The paper could include stronger exploration baselines, such as Random Network Distillation (RND), to better demonstrate the advantage of CSE over existing intrinsic-motivation methods.
  • Please report results with more random seeds, particularly given the large variance observed in some tasks.
Reviewer_GiniOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies reinforcement learning for combinatorial optimization when most completed solutions receive zero reward. The proposed method, Construction-Sequence Exploration (CSE), gives an exploration bonus to consecutive decisions that have been used less often. It maintains decayed visitation counts and reduces the bonus during training. The authors compare CSE with several random perturbation methods on eight problems. The largest improvement over the competing methods is on PCTSP. They also report experiments with dense rewards, different counting schemes, bonus parameters, and problem sizes.

Critical strengths

CSE computes its exploration bonus from a table of consecutive-decision counts, without an additional learned model. On PCTSP, it obtains a cost of 16.4±1.816.4 \pm 1.8, compared with 24.7±0.124.7 \pm 0.1 for vanilla RL and 23.7±1.223.7 \pm 1.2 for reward noise. Figure 4 also shows CSE reaching rewarding solutions in a gated TSP setting where vanilla continues to receive zero reward. These results suggest that the approach can help in some sparse-reward settings.

Critical weaknesses
  1. The main argument is that random perturbations help an already learnable policy, while CSE can recover a policy stuck without reward. However, Table 1 shows reward noise performing similarly to or better than CSE on TSP, CVRP, and SMTWTP, where vanilla also performs poorly. On TSP, reward noise obtains 10.5±0.110.5 \pm 0.1, versus 11.4±12.511.4 \pm 12.5 for CSE. The authors discuss reward sparsity and acknowledge cases where CSE struggles. What remains unexplained is why PCTSP benefits much more than these other problems. Is its reward harder to discover, or does its construction process suit the proposed bonus better? Figure 1 shows random perturbations failing under a hard TSP setting, but its relationship to Table 1 and the CSE ablations is not sufficiently specified. I cannot tell from the current comparisons which conditions account for the difference.

  2. Edge, node, and full-tour counting obtain costs of 9.45, 9.68, and 9.75, respectively, while vanilla obtains 43.2. Most of the improvement is therefore shared by all three counting schemes. The small remaining difference has no reported uncertainty, so it is difficult to judge the additional value of recording adjacent decisions. node-count result also needs an explanation. Every TSP tour visits every city once. If node bonuses are calculated from a fixed count table and averaged over the tour, the result is independent of visit order. How this produces different advantages across tours depends on implementation details that are currently missing. There is a related issue with Eqs. (5) and (12): a positive novelty bonus does not necessarily produce a nonzero expected policy gradient. A bonus that is constant across trajectories has zero expected policy gradient. Thus, the positive mean novelty in Figure 4 is insufficient to establish the proposed explanation. The count updates, baseline calculation, and any additional gradient noise need to be specified before these results can be attributed to the edge-based bonus.

Questions for authors
  1. What accounts for the large advantage on PCTSP, given that reward noise is competitive on several other problems? i ask for specifying how the reward settings and training budgets in Figure 1, Table 1, and the hard-TSP ablations relate. Under matched conditions, how often does each method discover an extrinsic reward, and how many samples does this take?

  2. How does the TSP node-count ablation produce different advantages across tours? Describing the order of count updates, decay, and bonus calculation; whether counts are kept separately for each instance; and how the intrinsic reward is handled in the self-critical baseline. Does the implemented procedure produce variation in novelty across tours during the zero-reward phase?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.