Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910004739571712 |
|---|---|
| author | Goudet, Olivier Suire, Quentin Goëffon, Adrien Saubion, Frédéric Lamprier, Sylvain |
| author_facet | Goudet, Olivier Suire, Quentin Goëffon, Adrien Saubion, Frédéric Lamprier, Sylvain |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01824 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning Goudet, Olivier Suire, Quentin Goëffon, Adrien Saubion, Frédéric Lamprier, Sylvain Machine 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 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. |
| title | Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2510.01824 |