# Initial Distribution Sensitivity of Constrained Markov Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 16 references that are in the map.
- First posted on arXiv 30 Sep 2025.

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

- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertainty](https://mlsanity.com/paper/2010.04870/) (2020)
- [Robust Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.06866/) (2022)
- [Distributionally Robust Constrained Reinforcement Learning under Strong Duality](https://mlsanity.com/paper/2406.15788/) (2024)

## Abstract (arXiv)

Constrained Markov Decision Processes (CMDPs) are notably more complex to solve than standard MDPs due to the absence of universally optimal policies across all initial state distributions. This necessitates re-solving the CMDP whenever the initial distribution changes. In this work, we analyze how the optimal value of CMDPs varies with different initial distributions, deriving bounds on these variations using duality analysis of CMDPs and perturbation analysis in linear programming. Moreover, we show how such bounds can be used to analyze the regret of a given policy due to unknown variations of the initial distribution.