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.
Figures & tables
Figure 1: Left. Example of the generation, at time t , of a population Γλt with λ=2 individuals for a maximization problem with n=3 . The generation order of the first individual is indicated by blue arrows. When constructing this individual using the MDP and a given order σG1=(3,1,2) , we start with xσG1<11=(0,0,0) given as input to the neural network gθ3 , generating x3=1 . Then xσG1<21=(0,0,1) is provided to to gθ1 , which generates x1=−1 . Finally, xσG1<31=(−1,0,1) is passed to gθ2 , which generates x2 , yielding the complete solution (−1,−1,1) . Once all individuals in the population have been sampled, the evaluation phase starts, where advantages are computed such that AΓλt(xbesti)=+1 and AΓλt(xworsei)=−1 (Eq. ( 5 )). Right. Training phase over E epochs with the λ=2 solutions sampled at this generation. At each epoch, new generation orders σG are sampled for each individual. Conditional action probabilities are then computed according to the corresponding causal masks. This allows the computation of L^λ(θ) (Eq. ( 8 )) and the update of θ=(θ1,θ2,θ3) by gradient ascent.
Figure 2: X-axis: number of calls to the objective function. Y-axis: Evolution of average scores (a) and average distances (b) obtained by the different variants of multivariate RL EDA for 100 independent runs on instances of the NK problem with n=256 and K=4 .
Figure 3: X-axis: number of calls to the objective function. Y-axis: Evolution of average scores.
Figure 4: NAS-Bench-101 benchmark. X-axis: number of calls to the objective function. Y-axis: Evolution of the average accuracy of the architectures.
Appendix figures & tables27 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Probability of having exactly k available (non-masked) input variables during neural inference of the generation probabilities of values for any dimension. Left: input dropout without order permutations. Right: input dropout combined with order permutations.
Algorithm 1 (σ,σ) -RL-EDA with parameters λ∈N∗ , β∈R+ , utility function U , number of epochs E and functional mechanism g .
Type instance K
r
d
α
0
0.05
1
1
1
0.05
10
1
2
0.05
10
1.09
3
0.2
1
1
4
0.2
10
1
5
0.2
10
1.09
Appendix
Table 1: Parameters of PUBOi instances.
Parameter
Description
Value
EDA parameters
λ
Size of the population
10
L
Number of hidden layers in g
1
nl
Number of neurons in hidden layer
20
ϵ
Probability threshold coefficient
0.001
PPO parameters
Appendix
Table 2: Hyperparameters settings for (σ,σ) -RL-EDA
Size instance
CPU time (s)
GPU time (s)
CMApara (Nevergrad)
64
61
-
128
78
-
256
141
-
Multivariate BOA EDA
64
460
-
Appendix
Table 3: CPU/GPU wall-clock times required to solve a QUBO instance with a budget of 10,000 calls to the objective function.
Instances
Methods
Pb
n
K
(σ,σ) -RL-EDA
PBIL
MIMIC
BOA
Best method (others)
Rank
Score
Rank
Score
Rank
Score
Rank
Score
Name
Rank
Score
QUBO
64
0
33/504
200.8
61/504
199.8
249/504
188.2
267/504
184.6
CMAL3
1/504
206.2 *
QUBO
64
1
82/504
148.8
91/504
147.8
134/504
146.0
140/504
145.4
CMApara
1/504
154.3 *
QUBO
64
2
115/504
138.1
88/504
139.1
119/504
137.6
154/504
137.4
DiscreteDE
1/504
143.4 *
QUBO
64
3
79/504
411.2
89/504
410.4
264/504
379.4
266/504
377.5
ChainCMAwithRsqrt
1/504
430.7 *
Appendix
Table 4: Global rankings and average scores obtained by (σ,σ) -RL-EDA and the other EDAs ( PBIL , MIMIC , and BOA ) are reported. The last columns present the ranking and average score of the best-performing method among the 500 additional algorithms considered (496 for NK3 problems). Rankings are computed over all 504 algorithms (499 for NK3 problems) by comparing the best score achieved after 10,000 objective function evaluations, averaged across 100 independent runs. Bold values highlight the best results among all competing methods. A star associated with the results obtained by (σ,σ) -RL-EDA indicates that it is significantly better on average (over 100 runs) than the best other competitor. A star associated with a result obtained by another algorithm indicates that it is significantly better on average (over 100 runs) than (σ,σ) -RL-EDA . A difference on the average scores is said statistically significant according to a t-test with p-value 0.001.
Figure 6: Evolution of the average scores with respect to the number of calls to the objective function obtained by (σ,σ) -RL-EDA and the best 10 other competitors for the different types of QUBO instances with n=128 .
Figure 7: Evolution of the average scores with respect to the number of calls to the objective function obtained by (σ,σ) -RL-EDA and the best 10 other competitors for the different types of NK3 instances with n=128 .
Figure 8: Evolution of the average scores with respect to the number of calls to the objective function, obtained by the four different versions of the multivariate RL EDA with additional structural dropout for sampling and training for the instances of the NK landscape problem with n=256 and K=4 .
Figure 9: Evolution of the average scores with respect to the number of calls to the objective function, obtained by the four different versions of the multivariate RL EDA with additional structural dropout for sampling and training for the instances of the QUBO problem with n=256 and K=5 .
Figure 10: Evolution of the average scores with respect to the number of calls to the objective function for the variants (δ,p) -RL-EDA and (σ,p) -RL-EDA for the instances of the NK landscape problem with n=256 and K=4 .
Figure 11: Evolution of the average scores with respect to the number of calls to the objective function for the variants (δ,p) -RL-EDA and (σ,p) -RL-EDA for the instances of the QUBO problem with n=256 and K=5 .
Figure 12: Evolution of the average scores with respect to the number of calls to the objective function, obtained by (σ,σ) -RL-EDA with and without known interaction graph.
Figure 13: Sensitivity to the population size in (σ,σ) -RL-EDA .
Figure 14: Sensitivity to the KL penalty coefficient β in (σ,σ) -RL-EDA .
Figure 15: Sensitivity to the logistic regression models used in each conditional generative network of (σ,σ) -RL-EDA . NN corresponds to neural network. L is the number of hidden layer in each neural network and nl is the number of neurons in each hidden layer.
Figure 16: Sensitivity to the number E of training epochs at each generation
Figure 17: Sensitivity of (σ,σ) -RL-EDA to the learning rate lr of the Adam optimizer.
Instances
Baseline
Adaptive
Δ(%)
QUBO
64
0
201
206
+2.49
QUBO
64
1
148
150
+1.35
QUBO
64
2
138
141
+2.17
QUBO
64
3
410
430
+4.88
QUBO
64
4
326
335
+2.76
QUBO
64
5
309
316
+2.27
Appendix
Table 5: Performance comparison between baseline and adaptive β . We report per-instance results along with averages and relative improvements ( Δ ). Relative improvements are computed as (Adaptive−Baseline)/Baseline . Higher is better.
Figure 18: NAS-Bench-101 benchmark. X-axis: number of calls to the objective function. Y-axis: Evolution of the average accuracy of the architectures.
Instances
Methods
Pb
n
K
(σ,σ) -RL-EDA
PBIL
MIMIC
BOA
Best method (others)
Rank
Score
Rank
Score
Rank
Score
Rank
Score
Name
Rank
Score
QUBO
64
0
1/504
195.9 *
243/504
159.7
336/504
139.0
362/504
117.9
Carola4
2/504
187.4
QUBO
64
1
1/504
147.7 *
127/504
137.3
225/504
129.6
343/504
113.8
LargeCMA
2/504
144.7
QUBO
64
2
1/504
136.6
123/504
131.3
191/504
127.5
345/504
114.5
LargeCMA
2/504
136.4
QUBO
64
3
1/504
394.8 *
275/504
318.9
346/504
271.2
359/504
234.9
Carola4
2/504
378.6
Appendix
Table 6: Global rankings and average scores obtained by (σ,σ) -RL-EDA and the other EDAs ( PBIL , MIMIC , and BOA ) are reported. The last columns present the ranking and average score of the best-performing method among the 500 additional algorithms considered (496 for NK3 problems). Rankings are computed over all 504 algorithms (499 for NK3 problems) by comparing the best score achieved with short budget after 1,000 objective function evaluations , averaged across 100 independent runs. Bold values highlight the best results among all competing methods. A star associated with the results obtained by (σ,σ) -RL-EDA indicates that it is significantly better on average (over 100 runs) than the best other competitor. A star associated with a result obtained by another algorithm indicates that it is significantly better on average (over 100 runs) than (σ,σ) -RL-EDA . A difference in average scores is said statistically significant according to a t-test with p-value 0.001.
Figure 19: Sensitivity to the parameter ρ in (σ,σ) -RL-EDA .
Instances
Methods
Pb
n
K
Fast- (σ,σ) -RL-EDA
PBIL
MIMIC
BOA
Best method (others)
Rank
Score
Rank
Score
Rank
Score
Rank
Score
Name
Rank
Score
QUBO
64
0
1/504
189.5 *
243/504
159.7
336/504
139.0
362/504
117.9
Carola4
2/504
187.4
QUBO
64
1
17/504
142.6
127/504
137.3
225/504
129.6
343/504
113.8
LargeCMA
1/504
144.7 *
QUBO
64
2
21/504
134.3
123/504
131.3
191/504
127.5
345/504
114.5
LargeCMA
1/504
136.4 *
QUBO
64
3
1/504
396.3 *
275/504
318.9
346/504
271.2
359/504
234.9
Carola4
2/504
378.6
Appendix
Table 7: Global rankings and average scores obtained by Fast- (σ,σ) -RL-EDA and the other EDAs ( PBIL , MIMIC , and BOA ) are reported. The last columns present the ranking and average score of the best-performing method among the 500 additional algorithms considered (496 for NK3 problems). Rankings are computed over all 504 algorithms (499 for NK3 problems) by comparing the best score achieved with short budget after 1,000 objective function evaluations , averaged across 100 independent runs. Bold values highlight the best results among all competing methods. A star associated with the results obtained by Fast- (σ,σ) -RL-EDA indicates that it is significantly better on average (over 100 runs) than the best competing method. A star associated with a result obtained by another algorithm indicates that it is significantly better on average (over 100 runs) than Fast- (σ,σ) -RL-EDA . A difference in average scores is considered statistically significant according to a t-test with p-value 0.001.
Instances
Methods
Pb
n
K
(σ,σ) -RL-EDA
(σ,σ) -RL-EDA-critic
QUBO
64
0
200.8 *
195.3
QUBO
64
1
148.8 *
146.7
QUBO
64
2
138.1 *
134.7
QUBO
64
3
411.2 *
407.7
QUBO
64
4
326.1
326.4
Appendix
Table 8: Average scores obtained by (σ,σ) -RL-EDA and its variant (σ,σ) -RL-EDA-critic . Bold values highlight the best results. A star associated with the results indicates that it is significantly better on average (over 100 runs). A difference in the average scores is said statistically significant according to a t-test with p-value 0.001.
Instances
Methods
Pb
n
K
(σ,σ) -RL-EDA
(σ,σ) -RL-EDA-share-params
QUBO
64
0
200.8
198.7
QUBO
64
1
148.8 *
145.9
QUBO
64
2
138.1
137.9
QUBO
64
3
411.2
415.4
QUBO
64
4
326.1 *
323.6
Appendix
Table 9: Average scores obtained by (σ,σ) -RL-EDA and its variant (σ,σ) -RL-EDA-share-params . Bold values highlight the best results. A star associated with the results indicates that it is significantly better on average (over 100 runs). A difference on the average scores is said statistically significant according to a t-test with p-value 0.001.
Figure 20: NK instances with n=1024 and K=8 .
Figure 21: Evolution of the score of a variant with Gibbs sampling with different numbers of iterations G for the sampling, in comparison with the standard version (σ,σ) -RL-EDA
Combinatorial black-box optimization in high-dimensional settings demands a careful trade-off between exploiting promising regions of the search space and preserving sufficient exploration to identify multiple optima. Although Estimation-of-Distribution Algorithms (EDAs) provide a powerful model-based framework, they often concentrate on a single region of interest, which may result in premature convergence when facing complex or multimodal objective landscapes. In this work, we incorporate the Stein operator to introduce a repulsive mechanism among particles in the parameter space, thereby encouraging the population to disperse and jointly explore several modes of the fitness landscape. Empirical evaluations across diverse benchmark problems show that the proposed method achieves performance competitive with, and in several cases superior to, leading state-of-the-art approaches, particularly on large-scale instances. These findings highlight the potential of Stein variational gradient descent as a promising direction for addressing large, computationally expensive, discrete black-box optimization problems.
Thomas Landais, Olivier Goudet, Adrien Goëffon +2
LERIA, Université d’Angers, 2 Boulevard Lavoisier, Angers 49045, France
Policy-gradient methods usually optimize expected return, but many real world applications care about distributional properties of returns: tail risk, outlier robustness, or best-of-K discovery. We introduce OrderGrad, a family of likelihood-ratio and reparameterization gradient estimators for order-statistic objectives. OrderGrad optimizes finite-sample L-statistics, i.e., weighted averages of sorted rewards or costs, recovering objectives such as VaR, CVaR, trimmed means, medians, and top-m/best-of-K criteria by changing only the rank weights. For any fixed sample size and rank-weight vector, OrderGrad provides an unbiased gradient estimator for the corresponding order-statistic objective. The method is implemented as a simple reward transformation that can then be used in an otherwise standard policy-gradient or reparameterized update. We study the resulting estimator's variance behavior and evaluate it on tasks where mean optimization is mismatched to the deployment objective, including LLM math post-training and other tasks. OrderGrad provides a unified, plug-and-play route to risk-averse, robust, and exploratory learning. Code: https://github.com/paavo5/ordergrad
Large language models (LLMs) typically approach combinatorial optimization as an inference-time procedure, solving each instance separately through sampling, search, or repeated prompting. We ask whether reinforcement learning can instead shift part of this reasoning cost into the weights of a code LLM, so that the model synthesizes a reusable solver for an entire problem family. We study this question on Synergistic Dependency Selection (SDS), a controlled variant of constrained Quadratic Knapsack designed to expose a specific failure mode: local signals and strict feasibility constraints make greedy heuristics attractive but unreliable. Under identical scaffolding, Best-of-64 base-model sampling saturates at an approximately 28.7% gap to the global Virtual Best Solver (VBS); code audits show that the base model often retrieves Simulated Annealing templates but misimplements the Metropolis acceptance rule. We fine-tune Qwen2.5-Coder-14B-Instruct with Group Relative Policy Optimization (GRPO) using a feasibility-gated reward and light structural scaffolding. The resulting policy converges to a constraint-aware Simulated Annealing template in 99.8% of feasible SDS outputs, achieves a 5.0% gap to that VBS, and is 91 times cheaper in post-generation execution/search cost than cumulative Best-of-64 evaluation. A compile-once check shows that one best frozen solver per seed remains highly competitive when reused unchanged across the SDS test set, while an additional-domain evaluation on Job Shop Scheduling provides narrower but positive evidence that the scaffold transfers beyond SDS. Negative ablations reveal the limits of this recipe: standard stabilizers degrade performance, a soft feasibility gate fails, and results remain sensitive to reward normalization and domain-specific design choices.
Soheyl Massoudi, Gabriel Apaza, Milad Habibi +1
ETH Zürich Zürich, Switzerland · University of Maryland College Park, MD, USA