From logistics to the natural sciences, combinatorial optimisation on graphs
underpins numerous real-world applications. Reinforcement learning (RL) has
shown particular promise in this setting as it can adapt to specific problem
structures and does not require pre-solved instances for these, often NP-hard,
problems. However, state-of-the-art (SOTA) approaches typically suffer from
severe scalability issues, primarily due to their reliance on expensive graph
neural networks (GNNs) at each decision step. We introduce ECORD; a novel RL
algorithm that alleviates this expense by restricting the GNN to a single
pre-processing step, before entering a fast-acting exploratory phase directed
by a recurrent unit. Experimentally, ECORD achieves a new SOTA for RL
algorithms on the Maximum Cut problem, whilst also providing orders of
magnitude improvement in speed and scalability. Compared to the nearest
competitor, ECORD reduces the optimality gap by up to 73% on 500 vertex graphs
with a decreased wall-clock time. Moreover, ECORD retains strong performance
when generalising to larger graphs with up to 10000 vertices.

本文介绍了一种名为 ECORD 的新型强化学习算法，它通过限制图神经网络的使用，提升了在最大割问题上的表现和可扩展性。在 500 个节点的图上，ECORD 相较于最接近的竞争者，优化效果缩小了最多 73%。同时，ECORD 在具有多达 10000 个节点的图的普适性方面保持了强有力的表现。

通过高效探索学习解决组合图分割问题

Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration

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.

在解决复杂优化问题方面，探索式组合优化（ECO-DQN）通过连续改进解决方案，从而有效地学习有效的启发式方法来解决图上的组合优化问题，并在最大割问题上展示了最先进的强化学习性能。