Initial Distribution Sensitivity of Constrained Markov Decision Processes

Alperen Tercan, Necmiye Ozay
9/30/2025
cs.LG

No official code found. Best implementation: alperentercan/CMDP-Sensitivity-Analysis (1 star, last commit 2025-09-09).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

alperentercan/CMDP-Sensitivity-AnalysisCommunity65%

Code accompanying the CDC 2025 paper “Initial Distribution Sensitivity of Constrained Markov Decision Processes”. Includes experiments, proofs-of-concept, and reproducible scripts for analyzing how CMDP optimal values vary with initial state distributions.

10Sep 9, 20251 years ago

Similar Papers

Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm

82% match2024

On the Fundamental Limitations of Dual Static CVaR Decompositions in Markov Decision Processes

80% match2025

Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form

80% match1 repo12024

Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form

80% match1 repo12024

Truly No-Regret Learning in Constrained MDPs

80% match2024

Risk-Averse MDPs under Reward Ambiguity

79% match2023

Cite this paper

@article{tercan2025initial,
  title  = {Initial Distribution Sensitivity of Constrained Markov Decision Processes},
  author = {Alperen Tercan and Necmiye Ozay},
  year   = {2025},
  eprint = {2510.00348},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2510.00348v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2510.00348.svg)](https://codeofpaper.com/paper/2510.00348)

Discussion