Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning

• URL: http://arxiv.org/abs/2510.01824v1
• Date: Thu, 02 Oct 2025 09:12:17 GMT
• Title: Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning
• Authors: Olivier Goudet, Quentin Suire, Adrien Goëffon, Frédéric Saubion, Sylvain Lamprier,
• Abstract summary: We introduce an order-invariant reinforcement learning framework for black-box optimization.<n>We parameterize a multivariate autoregressive generative model trained without a fixed variable ordering.<n>We adapt Generalized Reinforcement Policy Optimization (GRPO) to this setting, providing stable policy-gradient updates from scale-invariant advantages.
• Score: 9.588315721253169
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 Generalized Reinforcement 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.

Related papers

• ADORA: Training Reasoning Models with Dynamic Advantage Estimation on Reinforcement Learning [32.8666744273094]
  We introduce textbfADORA (textbfAdvantage textbfDynamics via textbfOnline textbfRollout textbfAdaptation), a novel framework for policy optimization.
  arXiv  Detail & Related papers  (2026-02-10T17:40:39Z)
• GDPO: Group reward-Decoupled Normalization Policy Optimization for Multi-reward RL Optimization [133.27496265096445]
  We show how to apply Group Relative Policy Optimization under multi-reward setting without examining its suitability.<n>We then introduce Group reward-Decoupled Normalization Policy Optimization (GDPO), a new policy optimization method to resolve these issues.<n>GDPO consistently outperforms GRPO, demonstrating its effectiveness and generalizability for multi-reward reinforcement learning optimization.
  arXiv  Detail & Related papers  (2026-01-08T18:59:24Z)
• Multimodal Large Language Models with Adaptive Preference Optimization for Sequential Recommendation [60.33386541343322]
  We propose a Multimodal Large Language Models framework that integrates Hardness-aware and Noise-regularized preference optimization for Recommendation (HaNoRec)<n>Specifically, HaNoRec dynamically adjusts optimization weights based on both the estimated hardness of each training sample and the policy model's real-time responsiveness.
  arXiv  Detail & Related papers  (2025-11-24T04:10:46Z)
• An Integrated Fusion Framework for Ensemble Learning Leveraging Gradient Boosting and Fuzzy Rule-Based Models [59.13182819190547]
  Fuzzy rule-based models excel in interpretability and have seen widespread application across diverse fields.<n>They face challenges such as complex design specifications and scalability issues with large datasets.<n>This paper proposes an Integrated Fusion Framework that merges the strengths of both paradigms to enhance model performance and interpretability.
  arXiv  Detail & Related papers  (2025-11-11T10:28:23Z)
• MIBoost: A Gradient Boosting Algorithm for Variable Selection After Multiple Imputation [0.0]
  In practice, analyses are often complicated by missing data.<n>We propose MIBoost, a novel algorithm that employs a uniform variable-selection mechanism across imputed datasets.
  arXiv  Detail & Related papers  (2025-07-29T13:42:38Z)
• Few-shot Steerable Alignment: Adapting Rewards and LLM Policies with Neural Processes [50.544186914115045]
  Large language models (LLMs) are increasingly embedded in everyday applications.<n> Ensuring their alignment with the diverse preferences of individual users has become a critical challenge.<n>We present a novel framework for few-shot steerable alignment.
  arXiv  Detail & Related papers  (2024-12-18T16:14:59Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Ensemble Kalman Filtering Meets Gaussian Process SSM for Non-Mean-Field and Online Inference [47.460898983429374]
  We introduce an ensemble Kalman filter (EnKF) into the non-mean-field (NMF) variational inference framework to approximate the posterior distribution of the latent states. This novel marriage between EnKF and GPSSM not only eliminates the need for extensive parameterization in learning variational distributions, but also enables an interpretable, closed-form approximation of the evidence lower bound (ELBO) We demonstrate that the resulting EnKF-aided online algorithm embodies a principled objective function by ensuring data-fitting accuracy while incorporating model regularizations to mitigate overfitting.
  arXiv  Detail & Related papers  (2023-12-10T15:22:30Z)
• Adaptive Discrete Communication Bottlenecks with Dynamic Vector Quantization [76.68866368409216]
  We propose learning to dynamically select discretization tightness conditioned on inputs. We show that dynamically varying tightness in communication bottlenecks can improve model performance on visual reasoning and reinforcement learning tasks.
  arXiv  Detail & Related papers  (2022-02-02T23:54:26Z)
• A Variational Inference Approach to Inverse Problems with Gamma Hyperpriors [60.489902135153415]
  This paper introduces a variational iterative alternating scheme for hierarchical inverse problems with gamma hyperpriors. The proposed variational inference approach yields accurate reconstruction, provides meaningful uncertainty quantification, and is easy to implement.
  arXiv  Detail & Related papers  (2021-11-26T06:33:29Z)
• Leveraging Recursive Gumbel-Max Trick for Approximate Inference in Combinatorial Spaces [4.829821142951709]
  Structured latent variables allow incorporating meaningful prior knowledge into deep learning models. Standard learning approach is to define a latent variable as an algorithm output and to use a differentiable surrogate for training. We extend the Gumbel-Max trick to define distributions over structured domains.
  arXiv  Detail & Related papers  (2021-10-28T12:46:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.