mlsanityData to 14 Oct 2026

Initial Distribution Sensitivity of Constrained Markov Decision Processes

arXiv 2510.00348 ↗First posted 30 Sep 2025cs.LGcited by 0

Not on the map. Why?

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.

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

4 of 16 references.

References · 4

  1. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 337
  2. 2020Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertaintycited by 23
  3. 2022Robust Constrained Reinforcement Learningcited by 15
  4. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Convex Approximations of Random Constrained Markov Decision Processes ↗
  2. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
  3. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process
  4. 2025Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
  5. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm
  6. 2025Transition Uncertainties in Constrained Markov Decision Models: A Robust Optimization Approach
  7. 2024Truly No-Regret Learning in Constrained MDPs
  8. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization