Exploratory Combinatorial Optimization Problem Solving via Gauge Transformation

The combinatorial optimization problems (COPs) over graph are of great significance both in theory and practice, covering a wide range of scenarios in daily life and industrial production. Recent years, reinforcement learning (RL) based models have emerged as a promising direction, which treat solving the COPs as a heuristic learning problem. However, current finite-horizon Markov Decision Process (MDP) based RL models are not allowed to explore adquately for improving solutions at test time, which may be necessary given the complexity of NP-hard optimization tasks. Some recent attempts solve this issue by focusing on reward design and state feature engineering, which are tedious and ad-hoc. To address this challenge, we introduce a physics-inspired technique called gauge transformation (GT), which is highly effective in enabling RL agents to explore and continuously enhance solution quality during testing. GT seamlessly transforms any state within the MDP back to its initial state, allowing the RL agent to continue exploration within the transformed space. Empirically, we demonstrate that traditional RL models equipped with the GT technique achieve the SOTA performance on the MaxCut problem. Moreover, GT is exclusively applied during testing and does not alter the training phase of the model. It can be readily integrated into existing RL models, providing a pathway for more effective exploration in solving the COPs.