Markov Decision Processing Networks (MDPNs), introduced in 2025, model multiclass queueing systems whose service availability is a controlled finite-state Markov decision process: each scheduling action both serves waiting requests and reshapes which services will be available later, as in quantum switches, assemble-to-order systems, ride-hailing platforms, and cross-skilled call centers. For this class the capacity region is characterized, the classical MaxWeight policy is provably not throughput-optimal, and the Weighted Average Reward Policy (WARP), which solves an average-reward MDP scalarized by current queue lengths once per epoch, is proved throughput-optimal - but only under two idealizations: the server MDP is fully known and is solved exactly. The source paper poses, as its stated future direction, establishing guarantees for multiobjective reinforcement learning in this setting. The open problem is to design scheduling policies for MDPNs that learn the server process from data and/or replace exact dynamic programming with approximation, and prove what such policies achieve - throughput optimality, or an explicitly quantified nondegenerate fraction of the capacity region (a stabilized subset of C\mathcal{C} with nonempty interior relative to C\mathcal{C}, and hence of positive volume), together with sample-complexity bounds on the data required and robustness of the achieved throughput to estimation and approximation error - or prove matching impossibility results. As of August 2026 no public work provides any such guarantee; the only adjacent progress is a polynomial-time LP-based policy stabilizing a fraction of the capacity region for the quantum-switch special case (Srikant, 2026), and an unpublished 2026 preprint by the original authors reportedly showing that one value-iteration step per time instant suffices for throughput optimality under a known model, which addresses computation but not learning from data.

Background

Markov Decision Processing Networks (MDPNs), introduced by Bhambay, Vasantam and Walton in 2025, are multiclass queueing networks - queueing models in which jobs of several types wait for service activities - in which service availability is itself a controlled Markov decision process (MDP), meaning a controlled stochastic process whose transition probabilities depend on the controller's actions. Time is discrete: requests of RR types arrive as i.i.d. bounded processes with means λr\lambda_r and wait in FIFO queues, while a server process occupies a finite set Z\mathcal{Z} of states; in state zz the controller chooses an action aa from a finite set, which produces a random schedule σ\sigma - the numbers of requests served of each type - and moves the server to state z′z' with probability P(z′∣z,a)P(z'|z,a). Serving one class can thus consume or preclude server states needed by another class: service is decision-dependent, so today's scheduling shapes tomorrow's service options. This captures assemble-to-order inventory systems, ride-hailing platforms, cross-skilled call centers, and quantum switches that must choose between consuming entanglement to satisfy requests and retaining or regenerating it for future ones; the model generalizes the two-sided matching view of a quantum switch developed by the same authors.

For such networks the central performance question is throughput. The capacity region C\mathcal{C} is the set of arrival-rate vectors λ\lambda for which some scheduling policy keeps the queue-length Markov chain positive recurrent; a policy is throughput-optimal if it stabilizes every λ\lambda in the interior of C\mathcal{C} without knowing λ\lambda. For classical switched queueing networks, the MaxWeight (backpressure) policy - serve, in each slot, a schedule maximizing the queue-weighted sum ∑rQrσr\sum_r Q_r\sigma_r - is throughput-optimal, a foundational result of Tassiulas and Ephremides (1992) and McKeown et al. (1999) that underlies most of the literature on scheduling and learning in queueing networks. The MDPN paper proves two structural results that break this program. First (Theorem 1), the capacity region of an MDPN is characterized, up to the boundary, by request-agnostic policies - policies that ignore the queues entirely and control the server MDP so that, at its stationary distribution μ\mu, the average service satisfies λr≤∑z,aμ(z)π(a∣z)σr(z,a)\lambda_r \le \sum_{z,a}\mu(z)\pi(a|z)\sigma_r(z,a) for every class rr; achievable throughput therefore depends on the long-run mix of server states the controller induces, not on a fixed convex hull of schedules. Second (Theorem 2, via an explicit three-server cyclic example), MaxWeight is not throughput-optimal for MDPNs: by greedily serving single-server classes it destroys server configurations needed by classes requiring several servers at once, and its stability region is a strict subset of C\mathcal{C} (in the example, MaxWeight requires λr3<(1−λr1)(1−λr2)\lambda_{r_3} < (1-\lambda_{r_1})(1-\lambda_{r_2}) while the capacity constraints are λr1+λr3<1\lambda_{r_1}+\lambda_{r_3}<1, λr2+λr3<1\lambda_{r_2}+\lambda_{r_3}<1; λr=0.4\lambda_r=0.4 for all rr separates them).

To recover maximal stability, the authors treat the server process as a multi-objective MDP - an MDP whose reward is a vector, here the schedule σ\sigma with one component per request class - scalarized by the current queue lengths qq: the one-step reward is u(a,z;q)=∑rqrσr(z,a)u(a,z;q)=\sum_r q_r\sigma_r(z,a), and one solves the associated average-reward MDP (an MDP optimized for long-run time-averaged reward rather than discounted reward), whose optimal policy π⋆(q)\pi^\star(q) maximizes the stationary expected weighted service rate. Their Weighted Average Reward Policy (WARP) divides time into epochs whose length τ(Q)\tau(Q) is a non-decreasing function of the queue vector with τ(Q)=ω(log⁡∥Q∥1)\tau(Q)=\omega(\log\|Q\|_1) (Assumption 1), computes π⋆(Q)\pi^\star(Q) exactly at each epoch start, and applies it for the whole epoch. The proof of Theorem 3 (WARP is throughput-optimal) rests on a two-timescale separation made rigorous through the fluid limit, the limit of the queue trajectories under large initial congestion: the O(1)O(1)-state server process equilibrates within an epoch while the order-cc request queues drift slowly, so each epoch's policy acts at its stationary mix; a multiplicative Foster-Lyapunov drift argument (a standard technique certifying positive recurrence via a Lyapunov function with negative drift outside a bounded set) then yields stability.

Two idealizations make WARP, as proved, hard to deploy: it requires (i) full knowledge of the server MDP - the transition probabilities P(z′∣z,a)P(z'|z,a) and schedule distributions - and (ii) exact solution of the average-reward MDP at every epoch, although the state and action spaces grow with the number of server-state configurations (for a quantum switch, exponentially in the number of entanglement buffers, as noted by Srikant in 2026). The authors state that in practice offline reinforcement learning - learning good policies from data rather than from a known model - and function approximation - representing the policy or value function compactly, for instance by a parametric form, instead of a table with one entry per state - would be used, and their Conclusions pose as the paper's future direction 'to establish guarantees for the multiobjective reinforcement learning algorithms in the context of these queueing networks'. Nothing of the kind is known: whether learned or approximately computed policies remain throughput-optimal, how much data learning the server process requires, and how estimation or approximation errors trade against the achievable throughput region are all open. The classical learning-augmented scheduling literature does not transfer, because it leans on MaxWeight, which is provably unstable here, and because the object to be learned is not a set of exogenous service rates but a controlled process whose induced stationary mix determines capacity.

Problem Statement

The problem is to replace the two idealized ingredients of the MDPN throughput-optimality theorem - exact knowledge of the server MDP and exact per-epoch solution of the average-reward MDP - with learning or approximation, while proving what is achieved. For the MDPN model of Bhambay, Vasantam and Walton (2025) (discrete time; RR request types with i.i.d. bounded arrivals; finite-state server process with transition probabilities P(z′∣z,a)P(z'|z,a) and schedule distributions, the number of requests served in each time slot bounded above by a constant BB, and the server process ergodic under any fixed policy; monotone feasible schedules, i.e. if a schedule is realizable then so is every componentwise-smaller one), design and analyze a scheduling policy that does not require exact solution of the queue-weight-parameterized average-reward MDP (Eqs. (8)-(12) of the source), and establish:

  1. a stability/throughput guarantee: the policy keeps the queue process positive recurrent for every arrival-rate vector in the interior of the MDPN capacity region C\mathcal{C} characterized in Theorem 1 of the source (throughput optimality), or provably stabilizes an explicitly quantified nondegenerate fraction or subset of C\mathcal{C} (a subset with nonempty interior relative to C\mathcal{C}, and hence of positive volume);

  2. a data guarantee: upper bounds on the observation or interaction time required before the guarantee holds when the server MDP is not known in advance; and

  3. an error-robustness guarantee: an explicit relation between the estimation error of the learned server model, or the approximation error of the function-approximation or iterative scheme used in place of exact dynamic programming, and the achievable throughput region or queue-length performance.

These components jointly support one objective: an implementable MDPN controller whose end-to-end performance is provable from data. The matching negative direction is part of the question as well: an impossibility theorem showing that no policy that learns the server MDP from data, or that computes its scheduling rule approximately, can be throughput-optimal over the general MDPN model class, or that a stated data requirement is necessary for every such policy. The guarantees are sought for every model in the general MDPN class - models satisfying the regularity conditions above, under epoch-based policies whose epoch length τ(Q)\tau(Q) satisfies Assumption 1 of the source. Results that address general stochastic processing networks with routing, or that weaken the epoch-growth and mixing conditions of Assumption 1, are outside this problem.

References

  1. Sanidhay Bhambay, Thirupathaiah Vasantam, Neil Walton. Markov Decision Processing Networks. arXiv:2509.24541, 2025. https://arxiv.org/abs/2509.24541
  2. R. Srikant. LP-Based Algorithms for Scheduling in a Quantum Switch. arXiv:2603.27812, 2026. https://arxiv.org/abs/2603.27812
  3. Sanidhay Bhambay, Thirupathaiah Vasantam, Neil Walton. Optimal Scheduling in a Quantum Switch. arXiv:2501.05380, 2025. https://arxiv.org/abs/2501.05380
  4. Panagiotis Promponas, Víctor Valls, Konstantinos Nikolakakis, Dionysis Kalogerias, Leandros Tassiulas. Throughput-Optimal Scheduling via Rate Learning. arXiv:2409.09198, 2024. https://arxiv.org/abs/2409.09198
  5. L. Tassiulas, A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control 37(12):1936-1948, 1992. DOI: 10.1109/9.182479. https://doi.org/10.1109/9.182479
  6. N. McKeown, A. Mekkittikul, V. Anantharam, J. Walrand. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communications 47(8):1260-1267, 1999. DOI: 10.1109/26.780463. https://doi.org/10.1109/26.780463