An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints

We appreciate the valuable comments provided by the reviewer. We address the reviewer's questions as follows.

Response to Essential References Not Discussed

We will explicitly cite and discuss these references in our final revised manuscript, clearly positioning our primal-dual contributions against this closely related primal-only approach.

Response to Weakness and Question

W1: Regarding Standard Result We would like to mention that although the $\tilde{O}(\sqrt{K})$ regret for reward is standard, it is the optimal order under unknown reward, other approaches can not achieve this result even under a deterministic reward. For the constraint violation, achieving a $\tilde{O}(\sqrt{K})$ bound in the adversarial constraint setting is not standard and is extremely difficult and nontrivial. We are the first to establish such a result in the anytime constraints setting.

W2: Difference of Stronger and Weaker constraint LP only serves as a general framework for solving optimization problems, it is well-known that the CMDP problem is equivalent to an LP problem. So LP is used as a standard tool for optimizing the inner problem at each step, however the primal-dual formulation and the Lyapunov function may be different. In other words, the theoretical results established in our paper are due to the carefully constructed Lyapunov function and LP is formulation is due to the natural of the CMDP problem. Please let us know if further explanation is needed. We will also revise the manuscript to make these points clearer.

W3: Benefits of using OMD It is indeed true that the primal-dual method is a central tool for solving CMDP problems, primarily because CMDPs can be formulated as linear programs and are essentially constrained optimization problems. However, the primal-dual framework is just one part of the overall solution strategy. There remain many open challenges in CMDPs due to their numerous variants—such as soft vs. hard constraints, adversarial constraints, and both model-based and model-free formulations. In our work, the achieved regret bound of $\tilde{\mathcal{O}}(\sqrt{K})$ matches the known lower bound and is optimal in the case of unknown rewards. In contrast, other approaches cannot achieve the $\mathcal{O}(1)$ reward bound even under deterministic rewards. As for constraint violation, obtaining a $\tilde{\mathcal{O}}(\sqrt{K})$ bound under adversarial constraints is highly non-trivial and, to our knowledge, has not been shown before in the {anytime constraint} setting. Our work is the first to establish such a result. The use of optimistic mirror descent (OMD) in our algorithm enables us to bound the regret through a sequence of one-step gradients of the surrogate objective function $f$ across $K$ episodes, as shown in Lemma 5.7. This approach, combined with a carefully designed Lyapunov function, ensures both low regret and strong constraint satisfaction. In summary, OMD is critical not only for improving convergence in the deterministic setting, but also for controlling the gap between the observed and optimal performance in each episode. Together with our Lyapunov-based dual control mechanism, it enables a unified and near-optimal treatment of both stochastic and adversarial CMDPs. We will revise the manuscript to better emphasize this connection and clarify the contributions beyond the use of OMD.

Q1: Regarding Standard Result Besides the response in Weakness-(2), algorithms developed under weaker constraint formulations are not directly applicable to stronger formulations. This is because weaker constraints allow for cancellation of constraint violations during the learning process (see lines 56–65 in the main paper), a property that does not hold in the stronger constraint setting.

Q2: Benefits of using OMD Please see the response in Weakness-(3). Please let us know if further explanation is needed

Q3: Removing Slater’s condition Due to response length limitations, we have addressed this question under Reviewer 7EBa. Kindly refer to the response to Weakness-(1) in that section.

Q4: Experiment Result Due to response length limitations, we have addressed this question under Reviewer 7EBa. Kindly refer to the response to Weakness-(3) in that section.

We sincerely thank the reviewer for the helpful feedback. If our response satisfactorily addresses your concerns, we would greatly appreciate your consideration in raising the evaluation score. We're happy to clarify any further questions during the discussion.

We appreciate the valuable comments provided by the reviewer. We address the reviewer's questions as follows.

Response to Weakness

W1: Removing Slater’s condition While it is true that in some practical scenarios, a near-feasible solution may exist, it doesn't make any changes to our results. A relaxed assumption is always desired for theoretical analysis. We would like to emphasize that, from a theoretical perspective, we achieve the best result without the need for the Slater's condition—an important and nontrivial contribution. The reason is that some existing methods, [1, 2, 3, 4, 5] rely on Slater’s condition with a slackness parameter $\rho$ , which quantifies how well the condition is satisfied. Their final regret and constraint violation bounds depend directly on this parameter, and when $\rho$ is small, these bounds can degrade significantly. Moreover, some algorithms([1, 3]) need to know the slackness $\rho$ which is not practical.

[1] "Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization."

[2] "Online learning in CMDPs: Handling stochastic and adversarial constraints."

[3] "Cancellation-free regret bounds for lagrangian approaches in constrained markov decision processes."

[4] "Learning adversarial mdps with stochastic hard constraints."

[5] "Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback."

W2: Convex CMDP applicability We would like to clarify that our algorithm is not inherently restricted to linear reward and cost functions. In fact, it can be naturally extended to a broader class of convex CMDP settings where the reward and cost functions are general convex functions of the occupancy measure $q$. Specifically, if we define the reward and cost functions as $h_k(q)$ and $g_k(q)$, respectively, the general optimization problem becomes:

To ensure theoretical guarantees, we require the following basic conditions: (1) The reward is generated stochastically; The cost can be generated either stochastically or adversarially; (2) The potential function $f$ used in the updates is 1-strongly convex; (3) The occupancy measure lies in a compact convex set(Fact 5.3); (4) The reward $h_k$ and cost $g_k$ functions are convex and Lipschitz continuous with respect to the occupancy measure $q$:$|h_k(q_1) - h_k(q_2)| \leq C_1 \|q_1 - q_2\|_2, \quad |g_k(q_1) - g_k(q_2)| \leq C_2 \|q_1 - q_2\|_2.$ Under these conditions, the core structure of our algorithm remains applicable. We will provide the proof in our final version.

W3: Experiment Results We implemented our algorithm on a synthetic CMDP with the following settings: $\mathcal{S} = 5$, $\mathcal{A} = 3$, and $H = 5$. For the adversarial constraint, the cost function was randomly selected from a fixed cost set with values in the range $[-1,1]$. After running the algorithm for $K = 3{,}000$ episodes, we report the cumulative constraint violation in the table below:

It is clear that a sublinear regret for the constraint violation is achieved.

We sincerely thank the reviewer for the helpful feedback. If our response satisfactorily addresses your concerns, we would greatly appreciate your consideration in raising the evaluation score. We're happy to clarify any further questions during the discussion.

We appreciate the valuable comments provided by the reviewer. We address the reviewer's questions as follows.

C1: Bounded $\mathcal{C}$ In our paper, we assume that $U$ is a 1-strongly convex function. When $U(q)$ is the entropy function, the resulting Bregman divergence is the KL divergence, which lacks a guaranteed upper bound. A common remedy is assuming a bound on the KL divergence [1] or introduce a probability mixing step to avoid boundary issues [1][2]. In both cases, the constant $\mathcal{C}$ is measure-dependent but independent of the time horizon $K$, so our algorithm's performance bound remains valid.

[1] arxiv.org/abs/1908.00305

[2] arxiv.org/abs/1311.1869

C2: Adversarial setting We clarify that the adversarial loss setting in our paper follows the standard formulation widely studied in constrained online convex optimization ([1,2]). The reviewer may be referring to a different setting, where constraints are satisfied only in expectation over time ([3]). In contrast, our work focuses on the stricter anytime constraint setting, requiring constraint satisfaction in every episode. To our knowledge, ours is the first to achieve a sublinear $\tilde{O}(\sqrt{K})$ constraint violation under this setting, which we hope will inspire further research.

[1] arxiv.org/abs/2310.18955

[2] "Online convex optimization with hard constraints: Towards the best of two worlds and beyond."

[3] "Online learning in CMDPs: Handling stochastic and adversarial constraints."

C3: Regrading near optimal policy The comparison policy is the optimal policy for the CMDP problem (3), we decomposite the regret analysis into two error terms in Eq.(24). This is the standard definition of regret.

Methods Criteria We clarify that our theoretical guarantees rely on the following key assumptions: (1) without Slater condition (a main contribution); (2) stochastic rewards, stochastic/adversarial costs; (3) the potential function is 1-strongly convex (due to our Lyapunov choice); (4) the occupancy measure is a compact convex set; and (5) reward/cost functions are convex and Lipschitz in the occupancy measure.

Theoretical Claims and Experiment We would like to clarify that we use a single notation $\pi^*$ to denote the optimal policy under both stochastic and adversarial constraint settings for simplicity, although the optimal policies in these two cases are generally different, which theoretical analysis applies to both scenarios. Kindly refer to the response to Weakness-(3) in Reviewer 7EBa to check the experiment results.

W1: Challenging of adversarial setting While our algorithm is designed for the adversarial constraint, it also applies to the stochastic constraint setting. This is one of the main contributions of our work—the proposed algorithm provides a unified framework that achieves near-optimal performance in both settings, without requiring prior knowledge of the environment type. Compared with existing approaches, reaching this level of generality and optimality requires careful design of the surrogate objective function, which ensures that unsafe actions are avoided while maintaining regret bounds through the use of the OMD algorithm. Our carefully constructed Lyapunov function plays a key role in guaranteeing these theoretical properties.

W2: We emphasize that minimizing regret and enforcing strong constraint satisfaction are different objectives. Our paper primarily addresses adversarial constraint violations. While both [1][2] adopt OMD, the key novelty of our work lies in Eq.(23), which provides an upper bound on the sum of exponential dual variable and cumulative estimated regret. This result is enabled by Lyapunov function (Eq.(20)), which incorporates both the reward and cost via rectified transformation. The theoretical contribution doesn't arise solely from using the OMD update. Its advantage is that it allows us to bound the episode-wise difference $\sum_{k=1}^K \left(f_k(q_k) - f_k(q^*)\right)$ in a clean way. Since [1, 2] do not adopt a similar Lyapunov-based design, they are unable to provide strong bounds on constraint violations under adversarial costs. Moreover, from the drift analysis, we show that the dual variable $\lambda_K$ can be controlled by bounding its exponential transformation.

W3: The proof of Eq.(23) is shown in the proof of Lemma 5.8(Appendix C.3, line 816-851).

Q1: The anytime adversarial constraint assumes that the cost functions are chosen adversarially at each episode, and the agent is required to satisfy the constraints in anytime.

Q2: $\mathcal{N}$ is maximum number of non-zero transition probabilities

Q3: The optimal policy is not episode-dependent, defined in Eq.(3).

Q4: $O(1)$ bound The improvement can be achieved due to our design of the Lyapunov function and the OMD component. Following Lemma 5.8, the term(I),(III) will disapper when reward is deterministic, which will benefit the bound.