# QPLEX Decision Processes: Formulation via Nonlinear Markov Chains and Optimization via Policy Gradients

arXiv: https://arxiv.org/abs/2605.17149 · HTML: https://mlsanity.com/paper/2605.17149/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 16 May 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 7 of 7)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Mean Field Markov Decision Processes](https://mlsanity.com/paper/2106.08755/) (2021)
- [Differentiable Discrete Event Simulation for Queuing Network Control](https://mlsanity.com/paper/2409.03740/) (2024)
- [Dynamic Pricing for Reusable Resources: The Power of Two Prices](https://mlsanity.com/paper/2308.13822/) (2023)
- [The Power of Static Pricing for Reusable Resources](https://mlsanity.com/paper/2302.11723/) (2023)

## Abstract (arXiv)

We introduce a QPLEX Decision Process (QDP) as a model for dynamic control of queueing systems with non-stationary arrivals, general service distributions, and service-level chance constraints. QDPs integrate QPLEX, a computational modeling methodology for transient analysis of stochastic systems, into a nonlinear Markov decision framework. Since QPLEX approximations use nonlinear transition probabilities with orders-of-magnitude smaller state spaces, QDPs circumvent the curse of dimensionality associated with general service times. Via forward and backward iterative schemes, we can rapidly compute gradients deterministically on the much smaller state space, eliminating sampling variance. We further address optimization through natural-gradient-inspired methods with block-diagonal Fisher approximations. To illustrate the QDP methodology, we formulate a single-station dynamic pricing problem with non-stationary demand as a QDP. When the reward structure uses waiting and terminal costs, our approach can find near-optimal policies in seconds on a single CPU; when the reward structure uses penalties for deviating from service-level chance constraints, the optimization landscape is substantially more challenging yet our approach can find a high-quality, practical policy in approximately a minute on a single CPU.