PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploratory Combinatorial Optimization with Reinforcement Learning

Thomas D. Barrett, William R. Clements, Jakob N. Foerster, A. I. Lvovsky

arXiv:1909.04063v2cs.LGcs.AIstat.ML

TL;DR

NP-hard graph optimization requires effective heuristics, but incremental construction prevents revising earlier choices. ECO-DQN learns test-time exploration with reversible vertex flips, achieving state-of-the-art RL performance on Max-Cut and supporting combination with other search methods.

  • Problem

    NP-hard graph optimization problems are often analytically intractable, while incremental solution construction prevents agents from revising earlier decisions.

  • Method

    ECO-DQN combines reinforcement learning and deep graph networks to explore solution spaces at test time by adding or removing vertices.

  • Results

    ECO-DQN achieves state-of-the-art reinforcement-learning performance on Maximum Cut and improves on the S2V-DQN baseline.

  • Takeaways & Limitations

    Because ECO-DQN can start from any valid state, it can operate independently or combine with other search heuristics, including random initialisations.

  • Takeaways & Limitations

    Using γ=0.95 gives strong performance but may limit exploration to relatively local regions of the solution space.

Abstract

from arXiv · show

Many real-world problems can be reduced to combinatorial optimization on a graph, where the subset or ordering of vertices that maximize some objective function must be found. With such tasks often NP-hard and analytically intractable, reinforcement learning (RL) has shown promise as a framework with which efficient heuristic methods to tackle these problems can be learned. Previous works construct the solution subset incrementally, adding one element at a time, however, the irreversible nature of this approach prevents the agent from revising its earlier decisions, which may be necessary given the complexity of the optimization task. We instead propose that the agent should seek to continuously improve the solution by learning to explore at test time. Our approach of exploratory combinatorial optimization (ECO-DQN) is, in principle, applicable to any combinatorial problem that can be defined on a graph. Experimentally, we show our method to produce state-of-the-art RL performance on the Maximum Cut problem. Moreover, because ECO-DQN can start from any arbitrary configuration, it can be combined with other search methods to further improve performance, which we demonstrate using a simple random search.

1 Introduction

Combinatorial optimization is difficult because exact methods for NP-hard problems become intractable, while heuristics often require problem-specific tailoring. ECO-DQN instead learns to explore and revise graph-based solutions at test time, achieving strong Max-Cut performance and scalability.

  • 1 Introduction: NP-hard combinatorial problems have practical applications, but exact algorithms become intractable and approximation methods may lack sufficiently strong bounds or scalability.
  • 1 Introduction: General heuristics often depend on the problem and require extensive tailoring or domain-specific knowledge.
  • 1 Introduction: ECO-DQN replaces irreversible one-at-a-time construction with test-time exploration that can add or remove vertices while seeking ever-improving solutions.
  • 1 Introduction: ECO-DQN combines reinforcement learning with deep graph networks and is designed for graph-based combinatorial problems whose solutions are vertex subsets.
  • 1 Introduction: Compared with S2V-DQN, ECO-DQN improves state-of-the-art reinforcement-learning performance on Maximum Cut.
  • 1 Introduction: ECO-DQN generalises to unseen graph distributions and achieves strong benchmark performance on graphs up to 2000 vertices despite training on graphs an order of magnitude smaller and structurally different.

2 Background

The paper frames Max-Cut as a weighted graph-partitioning problem and describes reinforcement learning through MDPs, Q-values, and graph-based message passing. Its MPNN produces action values for flipping each vertex in the solution subset.

  • Max-Cut Problem: Weighted Max-Cut seeks a vertex subset whose cut edges have the maximum total weight.
  • Max-Cut Problem: Max-Cut has applications including protein folding, investment portfolio optimization, and finding Ising-model ground states.
  • Q-learning: The optimization task is represented as an MDP with states, actions, transitions, rewards, and a discount factor, while policies map states to action distributions.
  • Q-learning: A DQN approximates optimal state-action Q-values and derives an approximate policy by greedily selecting the action with the highest predicted value.
  • Message Passing Neural Networks: The MPNN repeatedly updates vertex embeddings using information from neighboring vertices before a readout produces Q-values for flipping each vertex.

3 Exploiting Exploration

ECO-DQN replaces irreversible solution construction with reversible test-time exploration, repeatedly seeking improved states while using episode history and additional observations to guide vertex flips. On Max-Cut, this design outperforms prior RL baselines across graph settings and supports exploratory behavior that sacrifices short-term cut value to find better solutions.

  • Exploration-based formulation: ECO-DQN learns to explore for improving solutions rather than construct a single solution incrementally, continually reevaluating vertex additions and removals in episode context.Because actions are reversible, earlier decisions can be revised during test-time search.
  • Exploration-based formulation: The exploring agent rewards the best cut value seen so far, normalizing newly achieved improvements by |V| without penalizing temporary decreases in cut value.A discount factor of γ = 0.95 encourages reward pursuit within the finite horizon.
  • Exploration-based formulation: Additional intermediate rewards encourage reaching new locally optimal states, allowing the agent to hop between nearby promising optima during local search.The method focuses exploration on a subset of states likely to include the global optimum.
  • Agent information and training: The Q-value for each vertex flip uses seven observations, including vertex state, immediate cut change, episode timing, distance from the best solution, and available improving actions.These observations encode both the current solution and its relationship to the best state found so far.
  • Agent information and training: Removing reversible actions or additional observations reduces performance below S2V-DQN, while intermediate rewards speed and stabilize training.The result indicates that reversibility alone is insufficient; the agent must also be informed and rewarded to exploit it effectively.
  • Experimental behavior and performance: ECO-DQN achieves superior performance across most tested graph sizes and structures, with similar computational cost per action to S2V-DQN.Its trajectories include repeated actions, non-greedy moves, and occasional decreases in cut value, consistent with active solution-space exploration.

4 Leveraging Variance

ECO-DQN benefits from stochastic exploration through multiple random initialisations, improving generalisation and performance on larger or structurally different graphs. Intermediate rewards become increasingly valuable as test graphs grow.

  • Variance through initialisation: Different random initialisations produce varied search trajectories, allowing the best solution across multiple episodes to improve performance.This stochasticity helps explore multiple regions of the solution space while applying local optimisation.
  • Generalisation to larger graphs: Reversible agents outperform irreversible benchmarks across tests, with the performance gap widening as graph size increases.For BA graphs, S2V-DQN fails to generalise meaningfully to |V|≥200.
  • Variance through initialisation: 50 randomly initialised episodes give reversible agents a significant advantage, especially on larger graphs where single-episode performance is less sufficient.Even MCA-rev with 50 initialisations outperforms the highly trained irreversible S2V-DQN heuristic.
  • Intermediate rewards: Intermediate rewards have little effect on small graphs but noticeably improve performance when generalising to larger graphs at test time.The rewards encourage finding locally optimal solutions during training.
  • Generalisation across structures: ECO-DQN generalises across ER and BA structures, and with 50 random initialisations outperforms all other benchmarks even when trained on a different graph type.The same-distribution advantage is negligible for |V| ≤100.
  • Known benchmarks: On public benchmarks, ECO-DQN significantly outperforms other approaches even with one episode per graph, while on Physics graphs 37.6 % of episodes find an optimal solution.Among those optimal solutions, 90.4 % are unique.

5 Summary and Outlook

The paper introduces ECO-DQN as an exploratory reinforcement-learning algorithm for Max-Cut that generalises to unseen graph sizes and structures. Its ability to start from valid states supports combination with other search heuristics, while short-term reward discounting limits exploration to local regions.

  • 5 Summary and Outlook: ECO-DQN is presented as a state-of-the-art RL algorithm for Max-Cut that generalises to unseen graph sizes and structures.The approach is framed as continuously exploring to surpass the best observed solution.
  • 5 Summary and Outlook: ECO-DQN can initialise from any valid state, enabling combination with other search heuristics or solutions produced by other optimisation methods.Randomly initialised episodes already provide further performance improvements.
  • 5 Summary and Outlook: The short-term reward horizon from γ=0.95 likely limits exploration to local regions of the solution space.The paper identifies longer reward horizons and recurrent episode-history representations as directions for further work.
  • 5 Summary and Outlook: The approach is especially suited to settings requiring optimisation of many graphs with similar structure, including protein folding and portfolio optimisation.These applications are presented as practical settings where the demonstrated performance could be useful.

Code and graph availability.

The paper provides source code, experimental scripts, and testing and validation graphs, and specifies the graph-generation settings used for ER and BA experiments.

  • Code and graph availability: Source code, experimental scripts, and all testing and validation graphs are publicly available in the ECO-DQN GitHub repository.Repository: https://github.com/tomdbar/eco-dqn.
  • Code and graph availability: ER graphs use connection probability 0.15, BA graphs have average degree 4, and non-zero edges are randomly assigned weights ±1.The graphs were generated with NetworkX.

MPNN architecture.

The MPNN initializes vertex embeddings, incorporates neighborhood information through message passing, and reads out graph-wide Q-values for each vertex. The architecture uses 64-dimensional embeddings and three message-passing rounds, while allowing other suitable MPNN designs.

  • MPNN architecture.: Each vertex starts with an embedding computed from its input observation vector.The input vector has dimension m, and the initial embedding uses learned parameters θ1.
  • MPNN architecture.: Learned connection embeddings represent information associated with each vertex’s graph connections.The connection representation is combined with vertex information during subsequent updates.
  • MPNN architecture.: Message passing repeatedly updates vertex embeddings using information from local neighborhoods.After K rounds, the updated representations encode relevant local-neighborhood information.
  • MPNN architecture.: The network reads each vertex’s Q-value from its final embedding and information aggregated across the entire graph.The readout uses learned parameters applied after K message-passing rounds.
  • MPNN architecture.: The experiments use 64-dimensional embeddings and K=3 message-passing rounds, although many MPNN implementations can work successfully.The important architectural requirement is capturing relevant information about a vertex’s local neighborhood.

Training details.

ECO-DQN training uses experience replay and periodic minibatch stochastic-gradient updates across episodes initialized with random graph solutions. The supplied procedure specifies the sampling, action, and update loop but not the algorithm’s objective details.

  • Training details.: The implementation uses minibatches of 64, k=32 actions per gradient-descent step, learning rate 10^-4, and ε decreasing from 1 to 0.05 over approximately 10% of training.The same MPNN is used for S2V-DQN and ECO-DQN, and its S2V-DQN performance is reproduced on the Physics dataset.
  • Training details.: Training initializes an experience-replay memory and processes sampled graphs episode by episode.Each episode begins by sampling a graph from distribution D.
  • Training details.: Each episode starts from a randomly initialized solution set S0 contained in the graph’s vertex set.The agent then acts repeatedly on that graph.
  • Training details.: At each step, the selected vertex is added to or removed from the current solution depending on whether it is already present.The resulting transition is stored as (St, vt, Rt, St+1).
  • Training details.: Every k steps, the agent samples a minibatch from replay memory and updates θ using stochastic gradient descent.The pseudocode performs this update conditionally within each episode.

Extended data.

The extended data compares ECO-DQN and S2V-DQN with greedy MCA agents across graph sizes, emphasizing computational cost per action and time to solution. ECO-DQN and S2V-DQN have similar per-timestep computational costs.

  • Extended data.: ECO-DQN and S2V-DQN have similar computational cost per timestep because both primarily compute MPNN-predicted Q-values.Overall time to solution additionally depends on graph size and episode length.
  • Extended data.: Table 3 reports time per action for ECO-DQN and greedy MCA algorithms across different graph sizes.The experiments were performed on NVIDIA Tesla M60 GPUs.

Supplemental Material

The supplemental material evaluates optimization methods on Erdős–Rényi and Barabási–Albert graphs using approximation ratios, best-solution counts, and comparisons with commercial and heuristic solvers. Greedy MCA is nearly optimal on small graphs but deteriorates as graph size increases, while exact optimization becomes difficult on larger instances.

  • Supplemental Material: Six optimization methods are evaluated on 100 validation graphs for each graph structure and size, with the highest observed cut value used as the reference optimum.The tested sizes are |V|∈{20, 40, 60, 100, 200, 500}.
  • Supplemental Material: The experiments train agents up to |V|=200 and test them on graphs of the same or larger sizes using randomly initialized optimization episodes.For each agent–graph pair, 50 episodes are run; larger graphs may receive 300 episodes across five agents.
  • Supplemental Material: S2V-DQN agents are trained and tested equivalently to ECO-DQN agents, but use one deterministic test episode per agent–graph pair.ECO-DQN uses multiple randomly initialized episodes because its test-time behavior is exploratory.
  • Supplemental Material: MCA is a greedy algorithm evaluated in reversible and irreversible forms, with the best solution across its episodes taken as the MCA result.Each MCA variant is paired with corresponding ECO-DQN or S2V-DQN optimization episodes.
  • Supplemental Material: MCA finds optimal solutions on nearly all graphs up to |V|=60, but its performance rapidly deteriorates for larger graphs.The passage attributes this to the exponential growth of possible solution configurations and finite episode coverage.
  • Supplemental Material: Table 4 reports approximation ratios averaged over 100 graphs for each graph structure and size.The table compares the different optimization methods.
  • Supplemental Material: CPLEX solves every graph exactly up to 60 vertices within 10 minutes, while performance drops for 100-, 200-, and 500-vertex graphs.Only some 100-vertex graphs are solved optimally within the stated time budget.
  • Supplemental Material: Table 5 counts, out of 100 graphs, how often each method finds the best or equal-best solution.These counts show the methods’ relative contributions to the reference optimum solutions.
Loading 1909.04063v2…