@inproceedings{3a0ff564e24a4328bf69669ad4267f75,
title = "Iteration Complexity for Robust CMDP for finite policy space",
abstract = "We consider the robust Constrained Markov decision (RCMDP) problem of learning a policy that will maximize the cumulative reward while satisfying a constraint against the worst possible stochastic model under the unknown uncertainty set. Such a problem is relevant when the simulated and the real environment differ. Such a problem poses significant additional challenges compared to the non-robust CMDP problem and the unconstrained robust MDP problem. We seek to characterize the number of iterations required to bound both the sub-optimality gap and the violations by at most ϵ. We observe that the primal-dual-based approaches that achieves iteration complexity bounds for non-robust CMDP cannot achieve the same in the robust CMDP case. We consider a modified problem where we consider the convex hull of the policy-spaces and the decision becomes the simplex over the policy space. We propose a primal-dual based approach and show that ϵ suboptimality gap and violation bound can be achieved after O(1/ϵ2) iterations. We also show that an extra-gradient based approach can achieve ϵ suboptimality gap and violation bound can be achieved after O(1/ϵ) iterations. This improves the existing bounds for robust CMDP problem OF O(1/ϵ4). Empirical evaluations show that our proposed approach can achieve feasible and yet optimal policies very fast.",
author = "Sourav Ganguly and Arnob Ghosh",
note = "Publisher Copyright: {\textcopyright} 2025 IEEE.; 64th IEEE Conference on Decision and Control, CDC 2025 ; Conference date: 09-12-2025 Through 12-12-2025",
year = "2025",
doi = "10.1109/CDC57313.2025.11312439",
language = "English (US)",
series = "Proceedings of the IEEE Conference on Decision and Control",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "2713--2719",
booktitle = "2025 IEEE 64th Conference on Decision and Control, CDC 2025",
address = "United States",
}