# Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets Source: [Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets]() Collection index: [llms.txt]() Data updated: 2026-06-11T05:00:14.404Z Authors: Yi Chen, Rushuai Yang, Qiang Chen, Dongyan (Lucy) Huo Published: 2026-06-09T15:15:21.000Z ## Abstract 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. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [Inpatient Overflow Routing Control on 5x5 Queueing Network Case B1](): Inpatient Overflow Routing Control; 5x5 Queueing Network Case B1; Cost: 224.2. - [Inpatient Overflow Routing Control on 5x5 Queueing Network Case B2](): Inpatient Overflow Routing Control; 5x5 Queueing Network Case B2; Cost: 351.2. - [Inpatient Overflow Routing Control on 5x5 Queueing Network Case B3](): Inpatient Overflow Routing Control; 5x5 Queueing Network Case B3; Cost: 547.8. - [Inpatient Overflow Routing Control on 5x5 Queueing Network Case T1](): Inpatient Overflow Routing Control; 5x5 Queueing Network Case T1; Cost: 208.5. - [Inpatient Overflow Routing Control on 5x5 Queueing Network Case T2](): Inpatient Overflow Routing Control; 5x5 Queueing Network Case T2; Cost: 346.4. - [Inpatient Overflow Routing Control on 5x5 Queueing Network Case T3](): Inpatient Overflow Routing Control; 5x5 Queueing Network Case T3; Cost: 395.7. - [Inpatient Overflow Routing Control on 5x5 Queueing Network Case O1](): Inpatient Overflow Routing Control; 5x5 Queueing Network Case O1; Cost: 196.5. - [Inpatient Overflow Routing Control on 5x5 Queueing Network Case O2](): Inpatient Overflow Routing Control; 5x5 Queueing Network Case O2; Cost: 305. - [Inpatient Overflow Routing Control on 5x5 Queueing Network Case O3](): Inpatient Overflow Routing Control; 5x5 Queueing Network Case O3; Cost: 414.9. - [Policy Evaluation on 2x2 Queueing Network rho = (0.90, 0.90)](): Policy Evaluation; 2x2 Queueing Network rho = (0.90, 0.90); Value: 1316.9. - [Policy Evaluation on 2x2 Queueing Network rho = (0.95, 0.85)](): Policy Evaluation; 2x2 Queueing Network rho = (0.95, 0.85); Expected Value: 1198.1. ## Original sources and implementation [Original paper]() [PDF]()