A Song of FIRE and ICE: Policy Optimization in Stochastic and Adversarial CMDPs

Existing state-of-the-art Policy Optimization (PO) methods for Constrained Markov Decision Processes (CMDPs) assume Slater's condition and give vacuous regret-violation bounds for small slackness $\rho$. When Slater's condition fails, some primal-dual PO methods artificially shrink their dual spaces to achieve sublinear bounds. We feed Lyapunov drift-plus-penalty surrogate losses to a PO subroutine for adversarial unconstrained MDPs. Since the surrogates are unbounded, we keep the feasibility state outside the optimizer and normalize the surrogates with an epoch-based geometric-doubling trick. Our main algorithm, Feasible Iterative Restarts in Expectation (FIRE), is Slater-free, projection-free, has $\tilde{\mathcal{O}}(T^{\frac{1}{2}})$ regret and strong violation in the stochastic case, and a Pareto lower bound shows that these exponents cannot be jointly improved without Slater's condition. Being an adversarial extension, In-Hindsight Constrained Exploration (ICE) has $\tilde{\mathcal{O}}(T^{\frac{3}{4}})$ regret and weak violation for oblivious adversaries, which improve to $\tilde{\mathcal{O}}(T^{\frac{1}{2}})$ if the prefix-regret is non-negative. We prove that ICE's reflected queue cannot certify sublinear strong violation, identifying the structure a stronger adversarial bound needs. Synthetic experiments illustrate our mechanisms and tradeoffs.