Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning

We introduce an order-invariant reinforcement learning framework for black-box combinatorial optimization. Classical estimation-of-distribution algorithms (EDAs) often rely on learning explicit variable dependency graphs, which can be costly and may fail to capture complex interactions efficiently. In contrast, we parameterize a multivariate autoregressive generative model trained without a fixed variable ordering. By sampling random generation orders during training, a form of information-preserving dropout, the model is encouraged to be invariant to variable order, promoting search-space diversity, and shaping the model to focus on the most relevant variable dependencies, improving sample efficiency. We adapt Group Relative Policy Optimization (GRPO) to this setting, providing stable policy-gradient updates from scale-invariant advantages. Across a wide range of benchmark problem instances of varying sizes, our method frequently achieves the best performance and consistently avoids catastrophic failures.

Many real-world challenges, such as optimizing complex systems, designing machines, or planning efficient delivery routes, are difficult because we can only evaluate solutions by testing them, without fully understanding how all the components interact. To tackle this type of problem, we developed a method that learns from experience. It generates candidate solutions, evaluates their performance, and gradually improves them over time. Rather than following a fixed sequence of steps, it explores multiple possible orders, much like solving a puzzle by trying different ways of fitting the pieces together. This flexible approach allows it to discover meaningful patterns more quickly. As a result, the method is both more adaptable and more efficient, consistently identifying high-quality solutions across a wide range of problems.