On the Optimal Deterministic Policy Learning in Chance-Constrained Markov Decision Processes

Constrained Markov Decision Processes (CMDPs) are widely used for online decision-making under constraints. However, their applicability is often limited by the reliance on expectation-based linear constraints. Chance-Constrained MDPs (CCMDPs) address this by incorporating nonlinear, probabilistic constraints, yet are often intractable and approximated via CVaR-based reformulations. In this letter, we propose a tractable framework for CCMDPs to exactly solve the best deterministic policies based on a three-stage, model-based constraint learning algorithm. Theoretically, we establish a polynomial sample complexity guarantee for feasible policy optimization using a novel distributional concentration analysis. A case study on a thermostatically controlled load demonstrates the effectiveness of our approach.