Policy-Based Primal-Dual Methods for Convex Constrained Markov Decision Processes

This paper addresses the challenge of solving Constrained Markov Decision Processes (CMDPs) with d > 1 constraints when the transition dynamics are unknown, but samples can be drawn from a generative model. We propose a modelbased algorithm for infinite horizon CMDPs with multiple constraints in the tabular setting, aiming to derive and prove sample complexity bounds for learning near-optimal policies. Our approach tackles both the relaxed and strict feasibility settings, where relaxed feasibility allows some constraint violations, and strict feasibility requires adherence to all constraints. The main contributions include the development of the algorithm and the derivation of sample complexity bounds for both settings. For the relaxed feasibility setting we show that our algorithm requires Õ d|S||A| log(1/δ) (1-γ) 3 ǫ 2 samples to return ǫ-optimal policy, while in the strict feasibility setting it requires * The authors are listed in alphabetical order. samples required to approximate the environment's behavior without requiring explicit knowledge of the underlying dynamics. In this work, we focus on solving CMDPs in scenarios where the transition dynamics are a priori unknown, but a generative model is available. Our aim is to derive and prove sample complexity bounds for learning near-optimal policies under both relaxed and strict feasibility settings. The relaxed feasibility setting allows for some constraint violations, whereas the strict feasibility setting requires policies to strictly adhere to all constraints, which is critical in high-stakes applications such as healthcare or autonomous driving where constraint violations can be disastrous. The main contributions of this research are as follows: • We develop an algorithm for solving infinite horizon CMDPs with multiple constraints in the tabular setting, when the transition dynamics are unknown but we have access to a generative model, addressing both relaxed and strict feasibility settings. • We derive sample complexity bounds for our algorithm, providing theoretical guarantees on the number of samples needed to achieve near-optimal policies. • Our analysis covers both the relaxed and strict feasibility settings, showing how the sample complexity differs between the two and underlining the challenges of achieving the latter.