In many operations management problems, we need to make decisions
sequentially to minimize the cost while satisfying certain constraints. One
modeling approach to study such problems is constrained Markov decision process
(CMDP). When solving the CMDP to derive good operational policies, there are
two key challenges: one is the prohibitively large state space and action
space; the other is the hard-to-compute transition kernel. In this work, we
develop a sampling-based primal-dual algorithm to solve CMDPs. Our approach
alternatively applies regularized policy iteration to improve the policy and
subgradient ascent to maintain the constraints. Under mild regularity
conditions, we show that the algorithm converges at rate $
O(\log(T)/\sqrt{T})$, where T is the number of iterations. When the CMDP has a
weakly coupled structure, our approach can substantially reduce the dimension
of the problem through an embedded decomposition. We apply the algorithm to two
important applications with weakly coupled structures: multi-product inventory
management and multi-class queue scheduling, and show that it generates
controls that outperform state-of-art heuristics.

本文提出了一种基于采样的原始 - 对偶算法来解决带约束的马尔科夫决策过程，通过应用正则化策略迭代来改善策略，应用次梯度上升来保持约束。在弱耦合结构的情况下，通过嵌入式分解方法，能够显著减少问题的维度。将算法应用于多产品库存管理和多类队列调度，并表明它产生优于现有启发式算法的控制。