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