When Random Exploration Fails: Directed Exploration for Combinatorial Optimization

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.