Search papers, labs, and topics across Lattice.
This paper introduces Bellman-Taylor score decoding, a novel framework for addressing Markov decision processes (MDPs) with state-dependent feasible action sets, which are challenging for traditional deep reinforcement learning (DRL) methods. By transitioning policy learning to a Euclidean score space and utilizing an action decoder to ensure feasibility, the proposed method allows standard DRL algorithms to be applied without the need for differentiating through the decoder. The framework is validated through a queueing network control problem, demonstrating near-optimal performance in small instances and significant improvements over existing benchmarks in larger systems.
State-dependent action constraints can be effectively managed in DRL, leading to near-optimal solutions in complex queueing networks.
Many Markov decision processes (MDPs) in operations research have feasible actions that are state dependent and defined implicitly by various operational constraints. These features make it difficult to use standard deep reinforcement learning (DRL) algorithms, whose action interfaces typically assume either a fixed finite action catalog or a simple Euclidean space. Motivated by a Taylor expansion of the optimal action-value function, we propose Bellman--Taylor score decoding, a framework that moves policy learning to a Euclidean score space while enforcing feasibility through an action decoder. The induced latent-score MDP then can be optimized by standard DRL algorithms without differentiating through the decoder. We provide a performance guarantee showing that the optimality gap of this approach decomposes into a structural approximation error and an algorithmic learning error. Lastly, we apply this framework to a queueing network control problem, where the policy essentially learns a state-dependent index-based dispatching rule. Numerical experiments show near-optimal performance in small instances and considerable improvements over benchmarks in larger systems.
