Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets
Researchers propose Bellman-Taylor score decoding, a novel deep reinforcement learning framework designed to handle Markov decision processes with state-dependent action constraints common in operations research. The method decouples policy learning into a Euclidean score space while maintaining feasibility through an action decoder, enabling standard DRL algorithms to optimize complex systems like queueing networks without architectural modifications.
This research addresses a fundamental gap between theoretical reinforcement learning and practical operations research problems. Standard DRL algorithms assume either fixed action catalogs or continuous Euclidean spaces, but real-world systems like supply chain networks and job scheduling involve state-dependent constraints that make actions feasible only under specific operational conditions. The Bellman-Taylor framework solves this by translating the problem into an auxiliary latent-score MDP, allowing researchers to leverage existing DRL infrastructure without requiring custom action decoders that would complicate gradient computation.
The theoretical contribution lies in decomposing the optimality gap into structural approximation error and algorithmic learning error, providing interpretability about where performance degrades. This mathematical foundation distinguishes the approach from heuristic constraint-handling methods. The queueing network application demonstrates practical relevance, as dispatch rules are critical bottlenecks in logistics and cloud computing resource allocation.
For the AI research community, this work bridges a long-standing gap between academic RL and operational implementation. Organizations managing complex systems with implicit constraints—from hospital scheduling to data center load balancing—could benefit from more robust optimization techniques. The framework's compatibility with standard DRL algorithms (PPO, SAC, etc.) reduces implementation friction compared to specialized solvers. Numerical experiments showing near-optimal performance on smaller instances and improvements over benchmarks on larger systems suggest scalability potential, though real-world deployment in high-stakes environments would require extensive validation.
- →Bellman-Taylor score decoding enables standard DRL algorithms to optimize problems with state-dependent action constraints without architectural modifications
- →The approach decomposes optimality gaps into interpretable structural and algorithmic error components, improving transparency over blackbox constraint handling
- →Successfully demonstrated on queueing network control problems where it learns index-based dispatching rules outperforming existing benchmarks
- →Bridges a critical gap between academic reinforcement learning theory and practical operations research applications with implicit constraints
- →Maintains computational efficiency by avoiding differentiation through complex action decoders while leveraging existing deep RL infrastructure