Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees

Constrained decision-making is essential for designing safe policies in real-world control systems, yet simulated environments often fail to capture real-world adversities. We consider the problem of learning a policy that will maximize the cumulative reward while satisfying a constraint, even when there is a mismatch between the real model and an accessible simulator/nominal model. In particular, we consider the robust constrained Markov decision problem (RCMDP) where an agent needs to maximize the reward and satisfy the constraint against the worst possible stochastic model under the uncertainty set centered around an unknown nominal model. Primal-dual methods, effective for standard constrained MDP (CMDP), are not applicable here because of the lack of the strong duality property. Further, one cannot apply the standard robust value-iteration based approach on the composite value function either as the worst case models may be different for the reward value function and the constraint value function. We propose a novel technique that effectively minimizes the constraint value function-to satisfy the constraints; on the other hand, when all the constraints are satisfied, it can simply maximize the robust reward value function. We prove that such an algorithm finds a policy with at most ϵ sub-optimality and feasible policy after O(ϵ -2 ) iterations. In contrast to the state-of-the-art methods, we do not need to employ a binary search, thus, we reduce the computation time for larger value of discount factor (γ), and achieve a better performance for large state space.

Recently, [8] proposed an epigraph approach to solve the problem in (1). In particular, they considered

Hence, the objective is passed on to the constraint with an objective of how tight the constraint can be.

[8] finds the optimal policy for each b 0 , and then optimized b 0 using a binary search. They showed that for each b 0 , the iteration complexity is O(ϵ -4 ) to find the optimal policy. Note that one needs to evaluate robust value function at every iteration for each b 0 which is costly operation especially when γ is large as it is evident by Table 1. Further, the binary search method only works when the estimation is perfect [9], thus, if the robust policy evaluator is noisy which is more likely for the large state-space, the binary search method may not work as it is evident in our function approximation setup (Appendix G). Moreover, the complexity of iteration is only O(log(ϵ -1 )ϵ -4 ), which is worse than that of the CMDP [10]. We seek to answer the following:

Can we develop a computationally more efficient (without binary search) approach for robust CMDP problem with a faster iteration complexity bound?

• We propose a novel approach to address the optimization problem. Specifically, we reformulate it as follows:

This formulation balances the trade-off between optimizing the objective and satisfying the constraints. When max n J π cn -b n > 0, the focus is on reducing constraint violations. Otherwise, the objective J π c0 is minimized, scaled by the factor λ. Notably, this framework eliminates the need for binary search over λ; solving the above problem directly yields a policy that respects the constraints for an appropriately chosen λ. We show the almost equivalence of optimal solution of (3) and (1). However, because of the point-wise maximum over the multiple objectives, it introduces additional challenges in achieving the iteration complexity, as the index of the value function of the objective now depends on the policy.

• We propose an algorithm (RNPG) that gives a policy which is at most ϵ-sub optimal and feasible after O(ξ -2 ϵ -2 ) iterations if the strict feasibility parameter ξ is known. This is the first result to show that strict safety feasibility can be achieved. This improves the existing iteration complexity