Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
This work provides sample complexity bounds for CMDPs with multiple constraints, which is an incremental improvement for researchers working on reinforcement learning with safety constraints.
This paper tackles Constrained Markov Decision Processes (CMDPs) with multiple constraints and unknown transition dynamics, using a model-based algorithm. The algorithm achieves an \tilde{\mathcal{O}} \left( \frac{d |\mathcal{S}| |\mathcal{A}| \log(1/\delta)}{(1-\gamma)^3\varepsilon^2} \right) sample complexity for relaxed feasibility and \tilde{\mathcal{O}} \left( \frac{d^3 |\mathcal{S}| |\mathcal{A}| \log(1/\delta)}{(1-\gamma)^5\varepsilon^2{\zeta_{\mathbf{c}}^*}^2} \right) for strict feasibility.
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 model-based 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 $\tilde{\mathcal{O}} \left( \frac{d |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^3ε^2} \right)$ samples to return $ε$-optimal policy, while in the strict feasibility setting it requires $\tilde{\mathcal{O}} \left( \frac{d^3 |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^5ε^2{ζ_{\mathbf{c}}^*}^2} \right)$ samples.