Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets

Technical Summary: Bellman–Taylor Score Decoding for MDPs with State-Dependent Feasible Action Sets

1. Problem Statement

Many sequential decision-making problems in operations research (OR), such as inventory control, queueing network management, and resource allocation, can be formulated as Markov Decision Processes (MDPs). A critical challenge in applying Deep Reinforcement Learning (DRL) to these problems is the action interface.

Standard DRL algorithms (e.g., DQN, PPO) typically assume actions are drawn from a fixed finite catalog or a simple Euclidean space. However, in many OR models, the set of feasible actions $A(s)$ is state-dependent, high-dimensional, and implicitly defined by complex operational constraints (e.g., capacity limits, integrality, and combinatorial coupling). These constraints make it difficult to enumerate actions for value-based methods or to define simple probability distributions for policy-based methods. Existing solutions, such as action masking, projection layers, or differentiable optimization layers, often require problem-specific engineering, specialized training pipelines, or rely on explicit action catalogs that may be prohibitively large.

2. Methodology: Bellman–Taylor Score Decoding

The authors propose Bellman–Taylor Score Decoding, a framework that decouples policy learning from feasibility enforcement. The core idea is to shift the learning objective from the irregular, constrained natural action space to a regular, unconstrained Euclidean "score" space.

Key Components:

• Structural Representation: The method assumes the MDP admits a structural transition representation where the next state $s'$ is determined by a post-action configuration $\phi_s(a)$ and an exogenous disturbance $\xi_s$ via a known transition function $\Xi_s$.
• Taylor Expansion Motivation: The optimal action-value function $Q^*(s, a)$ is approximated using a first-order Taylor expansion of the continuation-value function $G^*_s(x)$ around a reference post-action configuration. This yields a linear surrogate:
  $$Q^*(s, a) \approx \alpha(s) + \psi_s(a) + \langle z^*(s), \phi_s(a) \rangle$$
  where $z^*(s)$ represents the marginal value (gradient) of the post-action configuration.
• Latent-Score MDP: Instead of learning a policy $\pi(a|s)$ directly, the agent learns a policy $\pi(z|s)$ that outputs a latent score vector $z$ in a Euclidean space.
• Action Decoder: A deterministic decoder $\Gamma(s, z)$ maps the score $z$ to a feasible natural action by solving an optimization problem over the original state-dependent feasible set:
  $$\Gamma(s, z) = \arg\max_{a \in A(s)} \{ \psi_s(a) + \langle z, \phi_s(a) \rangle \}$$
  This decoder enforces all operational constraints (integrality, capacity, etc.) exactly.
• Training: The DRL algorithm (e.g., PPO) optimizes the score policy on the induced latent-score MDP. Crucially, the decoder is not part of the differentiable computation graph. The policy gradient updates depend only on the score distribution, not on the derivative of the decoder's optimization step. This avoids the difficulties associated with differentiating through integer programs or non-smooth optimizers.
• Generalization: The framework supports higher-order Taylor expansions (up to order $K$), where the decoder optimizes over higher-order feature maps of the post-action configuration to capture non-linearities in the continuation value.

3. Theoretical Contributions

The paper provides a performance guarantee that decomposes the optimality gap of the learned policy into two distinct terms:

1. Structural Approximation Error: This term measures the residual variation in the Bellman continuation value that cannot be explained by the linear (or higher-order) score approximation. It is bounded by the local curvature of the value function and the deviation of feasible post-action configurations from the reference point. The authors show that exact action selection is possible if this residual oscillation is smaller than the local Bellman action gap.
2. Algorithmic Learning Error: This term represents the error incurred by the DRL algorithm (e.g., PPO) in solving the induced latent-score MDP, including finite-sample and function approximation errors.

This analysis clarifies that the restricted class of score-decoding policies can approximate Bellman-greedy decisions well when the continuation value is locally smooth and the Taylor remainder is small.

4. Empirical Results

The framework was evaluated on two problem domains:

• Inventory Control (Sanity Check): A multi-location inventory problem with cross-transshipment and non-linear receiving losses.

  • Findings: The first-order decoder performed well when the system dynamics were nearly linear. As non-linearity (congestion/loss) increased, the first-order decoder's performance degraded, but the second-order decoder maintained near-optimal performance, demonstrating the utility of higher-order expansions for complex dynamics.

• Queueing Network Control (Case Study): A multi-class, multi-pool dynamic routing problem where actions are integer dispatching matrices constrained by queue lengths and server capacities.

  • Small-Scale: In a $2 \times 2$ network where the optimal policy could be computed exactly, the proposed BTSD-PPO algorithm achieved costs within 1.1% to 2.5% of the exact optimum.
  • Moderate-Scale: In a $5 \times 5$ network, BTSD-PPO significantly outperformed state-of-the-art benchmarks, including classical index-based heuristics (c$\mu$, max-weight), an atomic-action PPO (which decomposes actions sequentially), and a MIP-based value-lookahead algorithm. Improvements ranged from 4.0% to 23.7% over the best benchmark.
  • Ablation Study: Applying the BTSD interface to different DRL backbones (PPO, SAC, DQN) consistently improved performance over their "vanilla" counterparts (which used action masking/projection), confirming that the gain stems from the action interface rather than the specific optimizer.

5. Significance and Claims

The paper claims that Bellman–Taylor score decoding offers a general, plug-and-play interface for applying standard off-the-shelf DRL algorithms to MDPs with complex, state-dependent feasible action sets.

• Separation of Concerns: It separates the learning of value gradients (handled by standard DRL in Euclidean space) from the enforcement of operational constraints (handled by a fixed optimization decoder).
• No Differentiable Optimization: Unlike differentiable optimization layers, this method does not require the decoder to be differentiable, making it suitable for problems with integer or combinatorial constraints where gradients are undefined or difficult to approximate.
• Learned Index Rules: In the queueing context, the method effectively learns a state-dependent, max-weight-type dispatching rule, automatically discovering optimal indices without manual specification.
• Modest Scope: The authors acknowledge that the approach introduces computational overhead (solving an optimization problem per action selection) and that the policy class is restricted by the Taylor approximation. They note that the framework currently assumes known transition dynamics and a specific structural representation of the post-action state, which may limit direct application to purely data-driven settings without further adaptation.

The paper concludes that this framework bridges the gap between standard continuous-action DRL solvers and the complex, constrained action spaces prevalent in operations research, offering a path to near-optimal control without extensive problem-specific algorithmic engineering.