# Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning

arXiv: https://arxiv.org/abs/2510.01824 · HTML: https://mlsanity.com/paper/2510.01824/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 24 of its 67 references that are in the map.
- First posted on arXiv 2 Oct 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 24 of 24)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Normalizing Flows for Probabilistic Modeling and Inference](https://mlsanity.com/paper/1912.02762/) (2019)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [NAS-Bench-101: Towards Reproducible Neural Architecture Search](https://mlsanity.com/paper/1902.09635/) (2019)
- [MADE: Masked Autoencoder for Distribution Estimation](https://mlsanity.com/paper/1502.03509/) (2015)
- [Neural Architecture Search with Bayesian Optimisation and Optimal Transport](https://mlsanity.com/paper/1802.07191/) (2018)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [Batch Bayesian Optimization via Local Penalization](https://mlsanity.com/paper/1505.08052/) (2015)
- [Neural Autoregressive Distribution Estimation](https://mlsanity.com/paper/1605.02226/) (2016)
- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [σ-GPTs: A New Approach to Autoregressive Models](https://mlsanity.com/paper/2404.09562/) (2024)
- [Benchmarking Discrete Optimization Heuristics with IOHprofiler](https://mlsanity.com/paper/1912.09237/) (2019)
- [Consistent Dropout for Policy Gradient Reinforcement Learning](https://mlsanity.com/paper/2202.11818/) (2022)
- [On the Regularization Properties of Structured Dropout](https://mlsanity.com/paper/1910.14186/) (2019)
- [Gray-box optimization and factorized distribution algorithms: where two worlds collide](https://mlsanity.com/paper/1707.03093/) (2017)
- [A discrete version of CMA-ES](https://mlsanity.com/paper/1812.11859/) (2018)
- [General Univariate Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.11198/) (2022)
- [Modified CMA-ES Algorithm for Multi-Modal Optimization: Incorporating Niching Strategies and Dynamic Adaptation Mechanism](https://mlsanity.com/paper/2407.00939/) (2024)

## Built on by (most cited first, 1 of 1)

- [Stein Variational Black-Box Combinatorial Optimization](https://mlsanity.com/paper/2604.15837/) (2026)

## Abstract (arXiv)

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 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 algorithms and problem instances of varying sizes, our method frequently achieves the best performance and consistently avoids catastrophic failures.