Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form

Authors: Toshinori Kitamura, Tadashi Kozuno, Wataru Kumagai, Kenta Hoshino, Yohei Hosoe, Kazumi Kasaura, Masashi Hamaya, Paavo Parmas, Yutaka Matsuo
Primary area: reinforcement learning
Keywords: Markov Decision Process, Constrained Optimization, Robust Optimization

Abstract:
Designing a safe policy for uncertain environments is crucial in real-world control systems. However, this challenge remains inadequately addressed within the Markov decision process (MDP) framework. This paper presents the first algorithm guaranteed to identify a near-optimal policy in a robust constrained MDP (RCMDP), where an optimal policy minimizes cumulative cost while satisfying constraints in the worst-case scenario across a set of environments. We first prove that the conventional policy gradient approach to the Lagrangian max-min formulation can become trapped in suboptimal solutions. This occurs when its inner minimization encounters a sum of conflicting gradients from the objective and constraint functions. To address this, we leverage the epigraph form of the RCMDP problem, which resolves the conflict by selecting a single gradient from either the objective or the constraints. Building on the epigraph form, we propose a bisection search algorithm with a policy gradient subroutine and prove that it identifies an $\varepsilon$-optimal policy in an RCMDP with $\widetilde{\mathcal{O}}(\varepsilon^{-4})$ robust policy evaluations.

Decision: accept (poster)
Reviewer scores: 6, 3, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1730665887007

thread_type:
official_review

<thread_object>
creator: reviewer_flm4

<content>
summary:
The paper introduces Epigraph Robust Constrained Policy Gradient Search, an algorithm designed to identify near-optimal policies in RCMDPs. The epigraph form can address gradient conflicts and theoretical techniques of prior approaches, ensuring convergence to an 
$ϵ-optimal$ policy across uncertain environments while satisfying safety constraints.

strengths:
This paper is well structured and written, it addresses the difficulties of applying existing CMDP algorithms in RCMDP by providing the first algorithm with theoretical performance guarantees for near-optimal policy identification. The proposed epigraph form effectively resolves gradient conflicts inherent in the Lagrangian formulation. They also include a toy example to show the challenges in RCMDP which makes the paper easy to follow and the empirical results demonstrate that EpiRC-PGS outperforms baselines in various RCMDP settings.

weaknesses:
The proposed algorithm’s double-loop structure may become computationally intensive in environments with high-dimensional action or state spaces, limiting real-time applicability.  The binary search and the projection in the policy updates are highly computationally inefficient. Assumption 2 requires an initial distribution over all the states, which is impractical, especially in the RCMDP setting, since some states are unsafe. Since the design of the algorithm is based on the monotonical property of $\Delta_b^*,$ it requires assumptions 3,4,5 to have accurate estimations. The empirical evaluation could benefit from complicated or additional real-world applications to validate the robustness in practical MDP scenarios.

comments:
It is better to discuss all the assumptions before presenting the main theorem.

questions:
In robust RL, sample complexity and convergence results typically depend on the gap between the transition kernels in the uncertainty set. Could the authors elaborate on how the results depend on this gap or specify which parts of the analysis are impacted by it?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730726130713

thread_type:
official_review

<thread_object>
creator: reviewer_yt6u

<content>
summary:
The paper present the first algorithm to solve Robust Constrained Markov Decision Process (RCMDP). The proposed algorithm achieves $\epsilon$-optimality with $\mathcal{O}(\epsilon^{-4})$ iteration complexity provided the uncertainty set is known apriori. The paper uses epigraph method which is different from the standard Lagrange approach used in the literature.

strengths:
1. Good intuition and presentation.
2. Mathematically sound results.

weaknesses:
**Minor Comments**

1. Assumption $5$ is used in Theorem $3$, however it appears later. Please correct it. 

**Major Comments**

1. To my understanding, this algorithm works if the uncertainty set is exactly characterized and known (otherwise, getting a subgradient evaluator might be difficult). However, one of the potential application of Robust MDP is to ensure that policies trained on an unknown model $P_0$ does not deviate too much if the actual model $P$ is close to the model $P_0$ in some sense. In this case, one can probably guess the shape of the uncertainty set but cannot fully characterize it since $P_0$ is unknown. For example, if $P$ lies in a ball of radius $r$ centered around $P_0$, then the shape of the uncertainty set is a high dimensional sphere but its centre, $P_0$ is unknown. Information about $P_0$ is available only through a simulator with model $P_0$. My question is: how can the proposed algorithm provide guarantees in such cases? If it cannot, then that should be highlighted in the abstract and introduction as a drawback.

questions:
1. Please categorize the related works into two groups: one that assumes the uncertainty set is fully characterized apriori (see the weakness above) and others that do not. This will help readers put the work into context. 

2. What are the challenges in extending this result to the case where the uncertainty set is not fully known apriori?

3. Does the algorithm scale with the size of the state space? Does it scale with the size of the uncertainty set? Some comments on these should be provided in the paper.

4. What is the typical computational complexity to generate a subgradient estimate with $\mathcal{O}(\epsilon^2)$ error? Such complexities should be elaborated in the paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730772857141

thread_type:
official_review

<thread_object>
creator: reviewer_yfqk

<content>
summary:
The paper aims to develop an algorithm to identify a near-optimal policy in Robust Constrained Markov Decision Processes (RCMDPs). RCMDPs aim to minimize cumulative costs while satisfying constraints in the worst-case scenarios. The authors note that conventional policy gradient approaches to the Lagrangian formulation for RCMDPs often get trapped in suboptimal solutions due to gradient conflicts. To address this, they propose using the epigraph form of the RCMDP problem, which circumvents these conflicts by optimizing the objective or the constraints individually. This approach allows the policy gradient to avoid local minima associated with conflicting gradients. They introduce the Epigraph Robust Constrained Policy Gradient Search (EpiRC-PGS) algorithm, a binary search-based method that iteratively refines policy selection, with theoretical guarantees to find an ε-optimal policy in RCMDPs.

strengths:
1. Applying the epigraph form to RCMDPs is a novel solution to address gradient conflict issues that arise with traditional Lagrangian formulations. 

2. The authors offer theoretical proofs that guarantee the proposed algorithm’s convergence to an ε-optimal policy. 

3. The paper includes empirical evaluations across several RCMDP settings. The experiments show that the proposed EpiRC-PGS algorithm reliably converges to feasible and low-cost policies, significantly outperforming Lagrangian-based methods in robust settings.

weaknesses:
1. The double-loop structure of the EpiRC-PGS algorithm, while effective, is computationally intensive. The paper mentions this as a limitation, suggesting that a single-loop alternative could improve efficiency, which is a potential area for improvement.

2. The algorithm’s effectiveness relies on the coverage of the initial distribution (Assumption 2). This assumption may not always hold, especially when the state space is large.

questions:
1. How does the algorithm perform when Assumption 2 on the initial distribution is partially met but not fully satisfied? Would the relaxation of this assumption degrade the policy quality significantly?

2. Have alternative subgradient methods or other non-gradient-based approaches been considered for this epigraph-form RCMDP problem? If so, how do they compare with the EpiRC-PGS algorithm in terms of robustness and feasibility?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731337887854

thread_type:
official_review

<thread_object>
creator: reviewer_kwav

<content>
summary:
This paper reformulate robust constrained MDPs via epigraphical reformulation and propose a bisection algorithm to solve this problem.

strengths:
- This paper addresses an important problem in the field of MDPs

- The idea of bisection search is interesting.

weaknesses:
- The writing is extremely confusing. For example line 205, it is not clear what does "Does pi^star \in...hold?" mean, given that the exact phrase was given in line 204. Also, there are many diamond-shape notation in the draft, and they should be typos.

- The idea, although is interesting, is very simple. The use of epigraphical reformulation is standard and not surprising and technical. The most technical part should be the evaluation of \Delta, but the proposed algorithm relies on existing methods to do this step. 

- The underlying idea of Algorithm 1 is not clear and the presentation is poor. 

- The convergence of the proposed algorithm is not fast, O(eps^-4), and there is no discuss on the complexity. 

- Experiments are not working on large-scale problems.

questions:
See weaknesses.

- What do you mean by "is an unknown value" in Assumption 4?

- Algorithm 1, how do you set T?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731467414361

thread_type:
official_review

<thread_object>
creator: reviewer_1d8s

<content>
summary:
This paper proposes the EpiRC-PGS algorithm for solving the robust constrained Markov Decision Process (RCMDP) problem and provides a theoretical proof for identifying an $\epsilon$-optimal policy. The paper first highlights the limitations of the traditional Lagrangian formulation in RCMDPs, introducing the epigraph form as a more effective approach for handling the policy optimization process. Finally, the authors present the EpiRC-PGS algorithm as a solution, which leverages the epigraph form to address RCMDPs effectively.

strengths:
1. This paper identifies key limitations in traditional algorithms for robust constrained Markov Decision Processes (RCMDPs) and presents an innovative, streamlined approach to overcome these challenges. 
2. The shift to an epigraph form represents a significant advancement, simplifying the solution method and providing an effective framework for robust optimization. 
3. The empirical comparison highlights the practical effectiveness of EpiRC-PGS, showing its ability to achieve low-return, constraint-satisfying policies, making it an attractive solution in robust decision-making applications.

weaknesses:
1. A key area for improvement is a more thorough analysis of the algorithm’s efficiency, especially in higher-dimensional state spaces. 
2. While the $\epsilon$-optimality proof is solid, addressing any computational overhead in the inner loop for larger state spaces would enhance its applicability to real-world problems.

questions:
Currently, experiments appear limited to low-dimensional cases. Extending tests to a more complex environment, like a two-dimensional space (e.g., velocity and distance in driving), could clarify if EpiRC-PGS maintains its time and space efficiency as complexity grows.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731912183807

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
**First of all, we would like to sincerely thank all the reviewers for their valuable feedback and comments.**

The reviewers mainly pointed out the strengths of our theoretical contributions: our paper identifies key limitations in the traditional Lagrangian approach for robust constrained MDPs (RCMDPs), and overcomes the challenges by the simple epigraph approach. 

On the other hand, the main criticisms were: 
1. the lack of a high-dimensional algorithmic extension and experiment [1d8S, KWav],
2. the lack of complexity analysis [KWav, yT6U, FLm4],
3. and the inefficiency of the double-loop structure [YFQK, FLm4],
4. Additionally, the reviewer KWaV pointed out the readability issue of our paper.

For each review, we have provided detailed responses and used the feedback to refine our draft, improving its readability and addressing several questions. Below, we outline our key comments and summarize the key updates in the revised draft:

## Restatement of our contribution

We remark that our EpiRC-PGS is the first algorithm that is **theoretically** guaranteed to identify a near-optimal policy in RCMDPs. While several papers have tackled RCMDPs (Russel et al. (2020); Mankowitz et al. (2020), Sun et al. (2024), Ghosh (2024), Zhang et al. (2024) in the draft), **even in the tabular setting, none have succeeded in solving the RCMDP.**

Most of these existing RCMDP research has predominantly focused on large-scale empirical algorithms, overlooking the foundational theory of tabular MDPs. **However, as evidenced by the history of RL, a solid theoretical foundation in tabular MDPs is essential for the advancement of large-scale algorithms.** For example, DQN is based on Q-learning, TRPO stems from Safe Policy Iteration [1], and SAC originates from Soft Q-learning. Without theoretical guarantees in the tabular setting, it would be impossible to establish reliable RL algorithms that perform well in high-dimensional problems. This study contributes to addressing this gap by establishing foundational theories for RCMDPs.

[1]: Safe Policy Iteration: https://proceedings.mlr.press/v28/pirotta13.html
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies the problem of identifying near-optimal policies in Robust Constrained Markov Decision Processes (RCMDPs) using a novel approach based on the epigraph formulation. It achieves theoretical guarantees with convergence to an $\epsilon$-optimal policy, addressing key limitations in traditional Lagrangian methods through binary search and policy gradient subroutines. The reviewers highlighted the significant theoretical contributions, such as addressing gradient conflicts in robust optimization and demonstrating limitations of existing approaches, while also raising concerns about computational efficiency and the scope of experiments. During the rebuttal phase, the authors effectively clarified these points, emphasizing the foundational nature of the work and the relevance of their theoretical framework in advancing robust reinforcement learning. Although one rejecting reviewer criticized the lack of large-scale experiments, this critique appears misplaced, given the paper’s focus on theoretical advancements. Overall, the paper makes a substantial contribution to the theory of RCMDPs and is well-positioned for acceptance based on its foundational impact.