Research map / Reinforcement learning / Visual and representation RL

Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization

ICML 2024 · Reinforcement learning › Visual and representation RL · approach: Scalable RL systems and environments · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes symmetric replay training (SRT), an add-on that replays high-reward trajectories transformed by solution-preserving symmetries (e.g., cyclic shifts/reversal in TSP) via imitation loss, improving sample efficiency of A2C, REINFORCE-rollout, PPO, GFlowNet and REINVENT on TSP, DPP and molecular optimization.

Problem

Deep RL for combinatorial optimization needs many reward evaluations, which is costly when objective functions are expensive black-box simulations or wet-lab assessments.

Approach

Reuse already-evaluated high-reward solutions by sampling their symmetric action trajectories (same solution, different action sequence) and training the policy by maximum likelihood (imitation) on them in a separate replay step, so no extra reward calls are needed and no importance weights are required even for on-policy methods.

Key results

• On TSP50 with 100K reward calls, GFlowNet + SRT reduces average cost from 6.797 to 6.596 (about 3.76% reduction).
• On chip-package PDN, A2C + SRT improves average reward from 9.772 to 12.757 (the largest reported gain, about 30.5%).
• On PMO, REINVENT + SRT raises average AUC top-10 from 0.615 to 0.632 and GFlowNet + SRT from 0.431 to 0.489 across 23 oracles.

Measured effects reported in the paper

Surprising findings

• Naive reward-maximizing training on augmented symmetric trajectories (data augmentation) can increase cost early on and inflate log-likelihood differences, so symmetric signal must be used carefully with on-policy methods.
• PPO + SRT on chip-package PDN showed longer wall-clock time than PPO alone (4,700 vs 3,884 s), so runtime overhead is not always negligible.

Limitations

• Gains on some PMO oracles are negligible or negative (e.g., REINVENT-SMILES + SRT is worse on deco_hop and median1), and the paper reports no gains on several tasks.
• Requires a known symmetry structure of the problem (e.g., cyclic shifts/reversal in TSP, decap permutation); the adversarial and importance-sampling variants need analytic knowledge or O(N) evaluation.
• Hyperparameters such as the SRT scale coefficient and the number of replayed samples are tuned per method and task.

Experimental setup

Datasets: synthetic TSP instances (N=50, 100) CVRP instances (N=50, 100) chip-package PDN HBM PDN PMO benchmark

Benchmarks: synthetic TSP50/TSP100 CVRP50/CVRP100 DPP chip-package PDN DPP HBM PDN PMO (23 oracles)

Metrics: average cost average reward AUC top-10 wall-clock time

Baselines: A2C PG-Rollout PPO GFlowNet REINVENT POMO Sym-NCO GPBO Graph GA AM Critic AM Rollout

Builds on: REINFORCE PPO GFlowNet Attention Model REINVENT

Closest papers by meaning

• Sample-Efficient Reinforcement Learning by Breaking the Replay Ratio Barrier (ICLR 2023 · similarity 0.90)
• Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces (ICML 2026 · similarity 0.89)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Method (NeurIPS 2023 · similarity 0.88)
• Learning What to Defer for Maximum Independent Sets (ICML 2020 · similarity 0.88)
• When Does Non-Uniform Replay Matter in Reinforcement Learning? (NeurIPS 2026 · similarity 0.87)
• Structured Reinforcement Learning for Combinatorial Decision-Making (NeurIPS 2025 · similarity 0.87)