Structured Reinforcement Learning for Combinatorial Decision-Making
This addresses scalability and generalization issues in RL for real-world combinatorial problems, representing a novel method rather than an incremental improvement.
The paper tackles the challenge of applying reinforcement learning to combinatorial decision-making problems like routing and scheduling, where standard RL struggles with scalability and generalization. The proposed Structured Reinforcement Learning (SRL) method matches or surpasses unstructured RL and imitation learning on static tasks and improves by up to 92% on dynamic problems, with enhanced stability and convergence speed.
Reinforcement learning (RL) is increasingly applied to real-world problems involving complex and structured decisions, such as routing, scheduling, and assortment planning. These settings challenge standard RL algorithms, which struggle to scale, generalize, and exploit structure in the presence of combinatorial action spaces. We propose Structured Reinforcement Learning (SRL), a novel actor-critic paradigm that embeds combinatorial optimization-layers into the actor neural network. We enable end-to-end learning of the actor via Fenchel-Young losses and provide a geometric interpretation of SRL as a primal-dual algorithm in the dual of the moment polytope. Across six environments with exogenous and endogenous uncertainty, SRL matches or surpasses the performance of unstructured RL and imitation learning on static tasks and improves over these baselines by up to 92% on dynamic problems, with improved stability and convergence speed.