An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Authors: Jiahui Zhu
Kihyun Yu
Dabeen Lee
Xin Liu
Honghao Wei
Venue: ICML 2025 poster (2025)
Keywords: Constrained Reinforcement Learning; Constrained MDP; online learning
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We propsed a new algorithm to deal with adversarial constraint in CMDP

Abstract: Online safe reinforcement learning (RL) plays a key role in dynamic environments, with applications in autonomous driving, robotics, and cybersecurity. The objective is to learn optimal policies that maximize rewards while satisfying safety constraints modeled by constrained Markov decision processes (CMDPs). Existing methods achieve sublinear regret under stochastic constraints but often fail in adversarial settings, where constraints are unknown, time-varying, and potentially adversarially designed. In this paper, we propose the Optimistic Mirror Descent Primal-Dual (OMDPD) algorithm, the first to address online CMDPs with anytime adversarial constraints. OMDPD achieves optimal regret $\tilde{\mathcal{O}}(\sqrt{K})$ and strong constraint violation $\tilde{\mathcal{O}}(\sqrt{K})$ without relying on Slater’s condition or the existence of a strictly known safe policy. We further show that access to accurate estimates of rewards and transitions can further improve these bounds. Our results offer practical guarantees for safe decision-making in adversarial environments.

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Jiahui Zhu
Kihyun Yu²
Dabeen Lee² Xin Liu
Honghao Wei!
Abstract
straints when interacting with unknown environment. These safety-critical sequential decision-main making problems are formally modeled as constrained Markov decision pro- cesses (CMDPs) (Altman, 1999). We study the problem of learning such policies in episodic CMDPs where the agent must balance exploration and exploitation to mini- mize strong regret(regret and hard constraint violation). metric quantifying the cumulative performance loss rela- tive to the optimal safe policy-while avoiding excessive constraint violations.
Online safe reinforcement learning (RL) plays key role in dynamic environments, with ap- plications in autonomous driving, robotics, and cybersecurity. The objective is to learn opti- mal policies that maximize rewards while satis- fying safety constraints modeled by constrained Markov decision processes (CMDPs). Existing methods achieve sublinear regret under stochastic constraints but often fail in adversarial settings, where constraints are unknown, üime-varying and potentially adversarially designed. In this paper, we propose the Optimistic Mirror Descent Primal- Dual (OMDPD) algorithm, the first address on- line CMDPs with anytime adversarial constraints. OMDPD achieves optimal regret O(v (V) and strong constraint violation Ō(VK) without re- lying on Slater's condition or the existence of a strictly known safe policy. We further show that access to accurate estimates of rewards and tran- sitions can further improve these bounds. Our results offer practical guarantees for safe decision- making in adversarial environments.
In many practical scenarios, especially in safety-critical applications, the environment is often dynamic, with con- ditions that can change unpredictably or even adversarially, Relying solely on stationary models can lead to suboptimal unsafe outcomes, these models fail to capture the time- varying nature of constraints and system dynamics. For instance, in autonomous driving (Kirschner et al., 2021), it is crucial to avoid collisions in variable environments in- fluenced by changing traffic flows and weather conditions. Similarly, in cybersecurity (Yinka-Banjo Ugot, 2020), adversarial CMDPs can model interactions between sys- tem defenders and attackers, requiring defenders to make decisions under uncertainty and strict system constraints while accounting for potential adversarial actions. This ne- cessitates the consideration of adversarial settings, where constraints may be unknown, time dene-depnndent, and poten- tially adversarially designed to challenge the learning pro- cess. Existing methods (Efroni et al., 2020; Müller et al., 2023; Germano et al., 2023; Müller et al., 2024; Kitamura et al., 2024) provide sublinear regret guarantees for stochas- tic constraints but struggle to generalize to such adversarial cases. The adversarial setting is inherently more challenging due to the dynamic and unpredictable nature of constraints, compounded by the assumption that error cancellation in constraint violations is not allowed. Adversarial CMDPs are thus erucial for handling dynamic environments, ensur- ing robust and safe decision-making in situations where conventional stochastic models fall short.
1. Introduction
Online safe reinforcement learning (RL) has been applied successfully across various domains, including autonomous driving (Isele al., 2018), recommender systems (Chow al., 2017), and robotics (Achiam et al., 2017). It en- ables the efficient development of policies that adhere to essential safety requirements, such as collision avoidance, budget compliance, and reliability. In safe RL, the objec- tive is to learn an optimal policy that maximizes cumulative rewards while satisfying expected cumulative safety con-
'School of Electrical Engineering & Computer Science, Pull- man. USA 'Department of Industrial & Systems Engineering, KAIST, Daejeon, South Korea "Scool of Information Science & Technology, ShanghaiTech University, Shanghai, China. Corre- spondence to: Jiahui Zhu <jiahui.zhue wsu.edu>.
Constraint violation is usually used to theoretically evaluate the performance of the safety of a safe RL algorithm. One commonly used constraint violation evaluates the policies in the beverage sense such that it allows error cancellation, as defined by (Efroni al., 2020), involves summing positive
Proceedings of the 4 International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
(unsafe) and negative (safe) constraint violations, ensuring sublinear total constraint violation during learning. In this paper we consider stronger notion of constraint violation, focusing exclusively on the sum of positive errors. To il- lustrate, consider a cost function d(TT)) which equals -1 when the policy Ty used in episode & is safe, and I when it unsafe. half of the policies over K episodes are safe and the other half are unsafe, the weak constraint violation- permitting cancellation results in [ΣX=1 d+ 0, where L-]+ m 03. However, under strong constraint violation, which disallows cancellation, the total violation [d[TT)]] = K/2 /2 Clearly, weaker sublinear becomes _ 1
versarial cost functions by proposing a novel unified al- gorithm, OMDPD, capable of handling both stochastic and adversarial rewards/costs without relying Slater's condition. OMDPD achieves Ō(vK) regret and Ö v K) strong constraint violation when rewards and costs are either stochastic or adversarial, both of which are optimal with respect to the total number of learning episodes K.
It is well known that one of the bottlenecks of forbidding algorithms for online CMDP from achieving a higher bound is because of the estimation errors of reward/cost and transition kernels. We further show that if perfect simulator (generative model) is given such that we can have an accurate estimate of the reward and transition kernels (cost function is also not known and can be adver- sarial), our regret bound can be further improved to O(1) when the reward function(also unknown) is fixed.
constraint violations do not ensure relatively safe policies during learning.
In this work, we aim address two fundamental research questions: RQ1: Can we design unified algorithm that achieves the optimal order of regret and hard constraint violation in unknown CMDPs with both stochastic and ad- versarial costs under minimum assumption? RQ2: What are the bottlenecks for further improving the bound?
2. More Related Work
Müller et al. (2023) proposes an augmented Lagrangian method for addressing CMDPs with strong constraint vio- lations under a requirement of a strictly known safe policy. Stradi et al. (2024c) propose primal-dual algorithm (CPD- PO), building on the policy optimization framework of (Luo et al., 2021), which achieves Ö (V) regret. However, nei- ther of these works addresses the adversarial cost setting. In addition, Stradi et al. (2024b) consider the adversarial reward setting but still assume stochastic constraints, requir- ing strong assumptions such as access to a strictly feasible policy and knowledge of its associated cost. Clearly, Stradi et al. (2024b) also cannot be applied to adversarial constraint scenarios. Additional studies by (Müller et al., 2024) and (Kitamura al., 2024) focus on last-iterate convergence under stochastic constraints, achieving rates of Ö(K and Ó K*/7), respectively. These results crucially rely on stationary setting. A detailed comparison of the theoretical results between our algorithm and the most existing studies is summarized in Table 1.
CMDPs with cumulative constraints that allow cancellation have been extensively studied under both model-free (Wei et al., 2022a;b; 2023; Ghosh et al., 2022; Bai et al., 2022) and model-based approaches (Ding et al., 2021; Liu et al., 2021a; Bura et al., 2021; Singh et al., 2020; Ding et al., 2021; Chen et al., 2022; Efroni et al., 2020). The study by (Qiu et al., 2020; Stradi et al., 2024a) focuses on CMDPs with only an adversarial reward function. Recent work (Germano et al., 2023; Stradi al., 2024c) considers online learning CMDPs under strong constraint violation for the long-term average cost and sublinear regret and violation results are well established. However, we note that in our scenario, the constraints are sufficiently strict-patticularly in adversarial settings-that an average safe policy fails to guarantee safety for euch individual episode. Consequently, focusing on the long-ten average constraint alone less meaningful under these conditions. Other works such as (Ding & Lavaei, 2022; Wei et al., 2023) consider scenarios where rewards, costs, and transition kernels are non-stationary, assuming bounded total variation. However, all of the above works we mentioned are not applicable to settings with adversarial costs, and they only address weak constraint violations.
3. Preliminaries
Notation. For any n E N, we use the short-hand notation [n] to refer to the set of integers {1..... nz..
For x E I, we define the operation [x]] =- max(0, x) to be the positive truncation of x. Throughout the paper, we use || to denote the Euclidean norm. Additionally, for a given I-strongly convex function U, we detine the Bregman divergence be- tween two points: D(a, U(a) - (b) (V)) a-b)
To address the aforementioned challenges, we propose the Optimistic Mirror Descent Primal-Dur (OMDPD) algo- rithm that ensures optimal regret and strong constraint vi- olation bounds with respect to the number of episodes K, regardless of whether the reward and cost functions are gen- crated stochastically or adversarially. Our contributions are
summarized as follows:
We consider a finite-horizon episodic CMDP, which is defined as a tuple M = (H, H, (Pr {ra)k k-1 (<)) where μ is the initial state distribution, S and A are the state and action spaces. We assume that both the state space and action space are finite and countable
We present the first work addressing online CMDPs with tnytime adversarial constraints. Our work advances the theoretical understanding of CMDPs under unknown ad-
2

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Algorithm
Regret
Adversarial Violation
Stochastic Violation Slater's Condition
Known Safe Policy
(Efroni et al., 2020)
((vK)
N/A
O(vK)
No
(Mäller et al., 2
K(
N/A
K)
Yes
(Stradi et al., 2024c)
O(vK)
N/A
((VK)
/
No
(Mäller et al., 2024)
O(K0093)
N/A
O(K0093)
/
No
(Kitamura al., 2024)1
O(K+)
N/A
((K+)
/
No
OMDPD
O(vK)
((VK)
(vvK)
X
No
Table 1. Comparison between OMDPD and existing related work. We omit the dependence on the dimension of the action, state space, and the number steps in CMDPs here. Consider the stronger notion of constraint violation, which disallows cancellation. (Efroni al., 2020) only consider weaker version. (Müller al., 2024) need to access strictly feasible policy. More discussions can be found in Section 2.
with cardinalities |S] = S A. In the online learn- ing under finite-horizon episodic CMDPs, each episode k E [K] has H steps and at each h E [H], we use (s : S x A x S - [0, 1] to denote the tran- sition kernel from state action pair (s, to a next state s' at step h. Without loss of generality, we assume that the reward function {rw) is a sequence of vectors at each episode & [K], particular,
In the following, we denote by the set of all the possible policies the agent choose from. we are interested in solving the following optimization problem:
प E arg max V (F(Fp) sell
s.t. (dd $ 0, (stochastic cost),
s.t. V (dt, p) 0, Ak [K] (adversarial cost),
(Tk,1:;..,,TK where Fk.h S x A [0, vh [H].k E [K]. Similar, the cost function dę,d at step h in episode & is de,A= Sx [-1, 1], both rewards and costs are bounded for any h E [H] k E [K]. The transition kemels,, reward functions, and cost functions are unknown. this paper, we consider the stochastic reward where T a random variable distributed according to a distribution for every k K, with two different types of cost functions: stochastic constraint and adversarial constraint:
where F == E,-.lr] = Ea-D[d]. The solution of this offline optimization problem (3) is considered as the base- line algorithm which serves to evaluate the performances of online algorithms. The goal of the online CMDP problem to learn optimal policy to minimize cumulative regret and strong cumulative violation of constraints after K episodes, which are defined below:
Regret( Σ
v=* (F.p) - (F((F))
(4)
Stochastic cost:
In stochastic cost setting, de is ran- dom variable distributed according to fixed probability distribution D for every & E [K].
Violation K)
T (d, [d.p)] (stochastic cost) (5)
Adversarial cost: In adversarial cost setting, d, are adversariilll--selcoed and unknown.
Violation (K)
Σ [V (de, 1)] (adversarial (6)
In online CMDPs, the agent interacts with the CMDP by executing a policy = (2,,,,,,,.......... .... n where (-Is) E A(A),, and A(-) is a probability simplex. We denote by (-Is) the probability distribution for state E S, When- ever the agent takes an action a in state s at step h, in episode k, it observes reward Tk.n(8, a) sampled from fixed dis- tribution, and cost, dx, (s, a) sampled either from a fixed distribution for the stochastic setting or chosen by an adver- sary for the adversarial setting. Then the value function for the reward and cost under the policy ı and transition kemne p are defined as:
Alternatively, the online optimization problem (3) can also be represented using the notion of occupancy measure (Alt- man, 1999) fg (s. a; h-1 under a policy and transition kernel p. For everys S, E A, we have the occupancy measure defined as:
9% (s, Pr(sh+1 = s'ssh= = s,a = =alp, IT, $1
th (5,
Σ (s, s'eS
It is well known that the CMDP problem can be formulated as an LP problem (Altman, 1999), then the optimal occu- pancy measure can be obtained by solving the following optimization problem:
("T(k,p) == E
Fk ( (4)[81, TT T.P
max TT ge Q
(8)
(T(d,))) = E
d (sn J.P
(2)
s.t. d g & 0. (stochastic cost)
(9)
3

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
s.l. q & 0, Vk e [K], (adversarial cost),
(10)
|ix a) - ph (s')s, a) & ( BA:- 1ol Vs, h ph (+1s,a) (R,(s,
where e [0, 1] is the occupancy measure vector, with its values defined in Eq. (7), and Q represents the set of all valid occupancy measures. F [0, 1sSAH and d( d(dx)) E [-1, 11,1JsA ssS denote the reward and cost vectors, respectively, with slight abuse of notation. On either hand, for any 9, the corresponding policy can be reconstructed as:
(17)
where (5,
0 is a UCB-type bonus, which de- notes the confidence threshold for the transitions and is de- fined in Appendix B.I. Thus, we can construct candidate set for selecting the policy at each episode k as:
(u(8,a)
2s (1 E SAH ा p Be),
(18)
(als) = Ens Qh (8(),aa)
(11)
where we denote 9 (p) E RSAH as the stacked occupancy measure vector under transition kernel p. a policy म, and IT is the set of all the feasible policies.
Given all the notations above, we denote the optimal so- lution to the optimization problem (3) as q², which also serves as the baseline. In this paper, following the standard assumptions, we consider the bandit feedback setting in which the learner observes only the rewards and costs for the chosen actions in the stochastic cost setting. However, in the adversarial cost setting, the full cost vector da is re- vealed after episode k, while the reward remains as bandit feedback throughout.
4.2. Surrogate Objective Function
The objective of online CMDP learning is twofold: (1) to control the constraint violations over time, and (2) to maximize cumulative reward. Thus, after constructing the feasible candidate set for the policy Qu. our algorithm aims to solve the following optimization problem at each episode:
4. Main Algorithm
max df 9
Tk q-
(19)
In this section, we introduce our main algorithm and the designs behind that to ensure the optimal order on the regret and violation bounds.
Inspired by (Sinha & Vaze, 2024; Guo et al., 2022) we
consider the following surrogate objective function with an exponential potential Lyapunov function: ((x)) == exp(Brr) - 1, for some constant 3 >>00 0:
4.1. Optimistic Estimates
fx( - (- +
b11 2x12. (20)
To encourage the exploration of the unknown CMDP, we first need to use the principle of optimistic estimate (Auer
Using the prediction (estimation) of the reward and cost function together with the online mirror descent optimiza- tion methods we can achieve tighter bound.
et al., 2008). Let n (s,a) = - "st''a.o -a) de- note the number of times that the state-action pair (s,a) is visited at step h before episode k. Here, (s ag) de- notes the action pair visited step h in episode k', and ( is the indicator function. Then the empirical transition kernels, rewards and violations can be calculated as follows:
The dual variable 2 aims to track cumulative constraint violations during learning. Then through analysis of the drift term (Axx) (Ax-1)), the algorithm adaptively reg- ulates long-term violation behavior: exponential growth in ((>x) dynamically amplifies constraint penalties during high-violation regimes, while bounded drift guarantees vi- olations remain controllable. Together, these components enforce an safe exploration.
k-
ph (s'ss,))) = -1 (00 -a -a,ch"i-= =80)
(12)
k- (s, a) v
n
1/ ( () = -x=1 RK (s, a) (1 (sk -s.0 -o)
(13) Specifically, we define the dual variable update as
mh (s,a) v
2h (5'(((ls,,)) == M DK (s, a) 1st -aof ma)
= + a a[d]qx]"
(21)
(14)
n (s, v
where de is the estimated constraint vector (Eq. 16) for the stochastic cost and is replaced with dy when the cost is adversarial. The operator [-]+ considers only the positively violated cost to efficiently control the hard constraint. We then employ the Lyapunov function (bAs) to track the evo- lution of these violations. Then we will show later that the one-step Lyapunov drift can be bounded by:
where a v b b max Remark that Eq. (14) is only used for the stochastic cost case. Then we can define the optimistic rewards, costs, and confidence set of transition kernels (x, a) as
(s, a)= == pk-1 (s. + (s,
(15)
ds, g (s, a) (8, a)
(16)
2(Ac) +()--1) & 2'(x)) a[deg=]* (22)
(s, = (fn(-18, a) E A(S) V
4

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Then by using the drintallus-penalty framework (Neely, 2010), we are able minimize the surrogate cost fune- tions (fa(g) 1t=1 which is the combination of the drift upper bound (Eq. 22) and the cost function. More precisely, by selecting 1 to minimize (x(g) within the feasible set Qk and summing over K episodes, we can obtain
Algorithm 1 OMDPD
Input: Q1, E -i Fi di X 0, learning rate r/k-
Parameters: xxx)) exp(3z) - 1, 2(1+VL,)SAH
Ls is defined in Appendix B.1.
Define function fx by:
1 fe(()) al-i E (At)
-219 9ke
$ ((xx) +o
(r - F
Σ ((l()))falot (oln)-fate (23)
for k = 1 to K do Construct the optimistic occupancy measure Gc+1 by:
9k+1 arg min (a ff((a))) D(g. Qk) ge@s
We refer the term (I) as Regretaig. Hence, minimizing this algorithm's 's regret is crucial to bound the cumulative reward and constraint violation.
Assume fA+1 = fis: Compute 7/+11 and update q&+1 by:
4.3. Optimistic OMD
9k+1 = arg min Mx+1 V ( 9x+1)
To obtain a tight bound on term (T), we adopt the Optimistic Online Mirror Descent (OMD) algorithm to dynamically control the constraints and adapt to evolving environments. The algorithm alternates between two phases in each it- eration. In the optimistic phase, the algorithm constructs an anticipated occupancy measure, QK+1, by solving the following regularized optimization problem:
Construct Th+1 by 4++1 and execute policy, and get estimation Fx de+1 by (q,() (16).
dx+1 is revealed to the agent for the adversarial case. Update AR+1 as follows:
{ Du + a [[dk+1 q++1] (Stochastic Case) (x + aldx+1 q (Adversarial Case)
Au+1 =
gk+1 arg min mgg.. V.fa(()))) ((q..4))
2
Update set 26+1 by (q.(
end for Return: TK*1
where 77& is the learning rate, and ((g, (x) represents the Bregman divergence, ensuring smooth updates. This step predicts the next occupancy measure by incorporating the gradient of the current potential function and regularization. In the refinement phase, the algorithm updates its policy by leveraging the predicted gradient V f ((k+1). Follow- ing the setup in (Rakhlin & Sridharan, 2013), we assume fx+1 = fx. The subsequent occupancy measure, 1 is obtained by solving:
VC min have with probability at least 1 25, OMDPD achieves:
We
IV. - -..
Regret(K) & ō ÖVNSAHH* + AH'
+ VCVSAHK SAH).
Violation K) & δ (VNSAHSK AH'
0++1- arg min (9, V f + D(g, (x+1). 2
+ +VCVSAHK (Both settings)
After we obtain the 9k+1, we can then construct T ing Eq. (11) and execute the policy and get estimations of the reward function, transition kernels, and cost functions for the stochastic setting. The optimistic update is criti- cal for enabling a tighter bound by incorporating historical gradients and occupancy measures. The full algorithm is presented in Algorithm 1.
Theorem 5.1 establishes the optimal Ō(VK) regret and constraint violation bounds under minimum assumptions. This is the first result with optimal order in terms of the total episode K, for the online CMDPS with anytime adversar- ial constraints. Our results do not rely on the satisfaction of Slater's 's condition- a common assumption requiring the existence of a strictly feasible solution. Since in the adver- sarial setting, is possible to make the slackness arbitrarily small by the adversary, thus the upper bound could be ex- tremely large. The removal of this restrictive assumption represents a key theoretical contribution, as it aligns the algorithmic framework more closely with practical settings where Slater's condition cannot be ensured priori.
5. Main Result
We first provide the main theoretical results of OMDPD.
Theorem 5.1. Choose
2(1+VL,)SAH 8
SAH BVCVGSAHK and denote C sup D(gi, q2). where L5 is defined in Appendix B.I. Let Vk
V fe(gg)) VE-1 ((k-1(9h-1) and consider T]
Remark 5.2. Our approach depends on the cumulative vari-
5

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
ation of consecutive gradients, which is often very small when the reward is fixed and known can be accurately estimated. Specifically, by choosing B & 3.5VCV2AAKK and setting 11k in Theorem 5.1, we can ensure that F% gk] is bounded by ((1). Consequently,
policy for the given 2s in each episode i e [K], which make it possible bound the regret and violation. Detailed proof can be found in Appendix B.1.
AH
Lemma 5.7. Conditioning the Good event G, the opti- mal policy x$ is a feasible solution policy for any episode tc E [K] such that:
Ek [ - in CMDP with generative model or perfect simulator is given, such that the transitional kernels and reward functions can be accurately estimated (which eliminates the estimation step in Section 4.1, the error term ÓV S AH) will be replaced by a constant that independent with episode K. Thus, the regret is bounded as (1). The detailed proof is deferred in Appendix D.2.
** { (x: (x:47(00 = &0,p' E Ba)
Therefore, π a feasible solution for any episode [K], where qr* is the occupancy measure under the optimal policy x* and we denote q" by ga for simplicity. Lemma 5.7 ensures that the optimal solution q² is a feasible solution given the confidence set at any episode k. which makes it comparable to the policy used by OMDPD.
Remark 5.3 (The Constant Bound C). The constant C' de- pends on the divergence measurement. If 'D is chosen as the KL. divergence, it does not admit a uniform upper bound over the simplex, as (gllll"") may go to infinity. However, smoothing track can be applied to keep all updated distri- butions bounded away from the boundary of the simplex. Such smoothing can ensure a boundness of C which is inde- pendent of the time horizon K. This technique is standard in online convex optimization under entropy regularization, more details can be found in (Wei et al., 2020).
Upper Bound of Regrefalg (Eq. (23)) Based on the Good event G, we first present the upper bound of the Regret Using optimistic online mirror for selecting the policies in Algorithm 1, we have
Lemma 5.8. Let C =
1ffa-1(9 suPa Du(li, 92).
V = v(fulgu)). Vk-1 and
define the learning rate
as:
m
5.1. Sketch of the Theoretical Analysis
ve VE IV.
In this section, we show the theoretical analysis of Al- gorithm 1. We first introduce the following facts for the CMDPs considered in this paper.
Then, the regret is bounded as:
Fact 5.4. For any 42 E Qx, Vk [K], we have ||g] q2ll E VSAH.
Regrelatg & <3.5C
Σ
V - 1
Fact 5.5. For any Pk. de or de, the reward/cost value func-
tion in terms of q E 22 is convex and Lipschitz continu-
This lemma shows that the upper bound depends on the sequence of the one-step gradient of the surrogate objective function over K episodes which can be shown that be further bounded by Ö(VK). Then, we will introduce the following
ous such that [ 91 q2 q2l & (1 /Ls) SAH (1
9ell-14% 91 d. 92) & VSAH q1 - 92ll. d 91 d% 92l <
(1 + VL8V qı 22l. Vg,, q2 Qx, vk, where L8 is the logarithmic term defined in Appendix B.1.
lemma to specify how the term be bounded.
IV V- 12 can
Now, we introduce the Good event which captures the con- fidence of the current estimation and will be used to prove the policy used by OMDPD comparable to the optimal solution. Our goal is to show that with a high probability, the true transition kernel lies in our confidence set such that the optimal solution is feasible solution given the current estimation. We first show that Good event happens with a high probability. The detailed proof is deferred to Appendix B.I due to page limit.
Lemma 5.9. V = fellg) denote the subgradient of the surrogate objective function fú evaluated qs (Eq, (19) Under OMDPD, the cumulative variation of consecutive gradients is bounded as:
K
K Σ k=1
V VR-1
F - F
K 1 (dw))dd 4 (A (11))
Lemma 5.6. With probability at least 1-8, Pr[G] > 1-6, where G is the good event and ó E (0, 1).
Basically, the good event shows that our estimation for the CMDP model is close to the true underlying model with high probability under the UCB-type exploration. Next, we will show that under the condition of Good event, the optimal solution of the CMDP problem E3. is feasible
K
2
Σ
1ix Fa- Fn- -'x (d
R-1
65AHA(1 + ('(k)))
SAH
6

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
This lemma first establishes that the aggregated variation of policy gradients under OMDPD can be bounded by O(SAll K)) ( We also recall the foun- dational inequality: & ((Ak) + a - (FT qb) <
parameters, and (ii) optimization error, which is influenced by the online learning algorithm. In the following, we will analyze and bound each term individually.
To better illustrate the analysis of the main theorem, we provide a proof roadmap in Figure 1, which establishes the inequality ((Ax) + > (fk q² - F qs) & Regretaig along with the resulting regret and violation bounds.
I - f))(")). Here, for simplicity, we momen- tarily ignore the factor of SAH to discuss how the (11)
result in Remark 5.2 can be achieved. First, choosing the function (xx) = exp(3xx) - ensures that & (xxx) can be combined with (AAx) the foundational inequality. Using Lemma 5.9, we obtain $(Ax) + a ( 9* )2) & V + 4' (A Then rearrange to get Th
5.3. Upper Bound of Estimation Error
In the following lemma, we provide an upper bound on the estimation errors for both regret and violation.
ER_ (T 9" (%.)) 9x) & exp(3Ax) (IVK-)
By choosing the 33 from Theorem 5.1 so that Bv O, it follows that 1x-1(FT
Lemma 5.10. Let P&. denote the transition kernel in the candidate set BE, and let 8s. and dy be the estimations used by OMDPD. Then, conditioned on the good event G, the estimation errors for the stochastic cost case can be bounded as follows:
- 77 9x)= < VK, which has an O(vK) K) bound. Now, when the reward fixed, terms (i) and (iii) vanish (because FR = Fk-1),, which makes Ek (F - FT qx) & exp(5Xx)
- -1) + 1, so that the VK factor disappears and a suitable 3 yields an (1)) bound. The details for showing Σ 9 T 9 & x1)1) are deferred to Appendix D.2. Consequently, using Lemmas 5.8 and 5.9, we can now move on to prove Theorem 5.1 in the following sections.
K Σ (Fx
O(NNSAN*K-SAAM
VTN (d. -) (d
5.2. Proof of the Main Theorem
< OWNNSAHK-SSAM
To prove the main theorem, we first know that the regret can be expressed as:
The estimation error for the adversarial cost case can be bounded as follows:
K RK = IV (Fk. VV* (F.pF))
K
Σ
V (da, -V
Estimation Error
(r,p)- ( (24)
< ÖWNNSAHSK+S
Optimization Error
The above lemma bounds the error incurred by using the esti- mated transition kernels, rewards, and costs during the learn- ing process, which improves upon Lemma 29 of (Efroni et al., 2020) by a factor of (VHH) This improvement is achieved by leveraging a Bellman- type law of total variance to control the expected sum of value estimates for bounding the error from estimating the transition kernel (Azar et al., 2017; Chen & Luo, 2021). The detailed proof is deferred in Appendix C.2. Next, will bound the optimization error.
Similarly, the violation in stochastic setting can be formu- lated as:
K Σ
Violation(K) =
you (d.p) - Va (de,
Esstiattio Error
Th (de, ph))
(25)
Optimization Error
5.4. Upper Bound of Optimization Error
In the constrained adversarial setting, we do not explicitly perform estimation on constraint d, so the only source of estimation error arises from the unknown transition kernel.
Regret Analysis. We first focus bounding the optimiza- tion error associated with regret. The following lemma es- tablishes that the cumulative variation of gradients between consecutive episodes under OMDPD is bounded, enabling adaptive regret-violation guarantees.
Overall, the decomposition operation separates the regret and violation into two distinct components: (i) estimation er- ror, which arises due to inaceuracies in the estimated model
To further relate the regret optimization error to Algorithm
7

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
K Φ(>k) + Fr q- Fx qml S Regret
Prove Regretalg
Lemma 5.7
k=1
Prove
Combine
Prove
Lemma 5,8
K
Lemma 5.11
Regret(K)
F 9
fg
9k
Lemma 5.10
Lemma 5.9
Violation(Sto)
Prove
Prove
<((xk)
Prove
Lemma 5.12
Lemma S.9(dvv)
Violation(Adv)
Combine
Figure I. Proof Roadmap of the Theorem 5.1
consider:
Violation Analysis. We now analyze the sublinear violation guarantee in stochastic and adversarial settings.
K
K
(f,p)- V (Fk, Ph)
B q²1 - 1 gR.]
Stochastic Setting, As discussed earlier, in the stochastic setting, the overall violation can be decomposed into esti- mation and optimization parts, with Lemma 5.10 addressing the estimation error. We now turn our attention to bounding the optimization error. The following lemma provides the critical result needed for analyzing this optimization error.
K
K
B 9-1 Σ
B
+
B 90' - 7 2x
(26)
Lemma 5.13. Based on Lemma 5.8, 5.9. Then, the follow- ing upper bound holds:
Notably, Term 2 corresponds to the violation-regret relation- ship in Eq. (23), providing critical link to our theoretical analysis. Consequently, we will first derive an upper bound for Term 2 in the regret decomposition.
K
gd & 16(1+ VLA)VVVSSAHK In(A)
Lemma 5.11. Based on Lemma 5.8, 5.9, the following upper bound holds:
where A= (K
(K (K+8VC
VGSAHK SAH
+2): ds dg under
stochastic setting and d; = dg in adversarial setting.
Σ FT F qx]
Thus, by combining the estimation bound from Lemma 5.10 with the violation analysis from Lemma 5.13, we have de- rived the complete violation bound for the stochastic setting,
< 2[H
A Adversarial Setting. As defined in (6) the estimation error in the adversarial setting differs slightly from that in the stochastic setting, since there is no estimation error asso- ciated with the constraints and the only source of estimation error arises from the transition kernel. Consequently, based Lemma 5.10 under the adversarial case and Lemma 5.13, we obtain the complete violation bound for the adversarial setting. A detailed proof of Lemma 5.13 can be found in Appendix C.6.
To complete the upper bound for the optimization error in regret, we now consider Term 1. The following lemma provides the required result:
Lemma 5.12. Under the stochastic rewards setting, with probability at least 1-25, we have:
(K (K-1)
2 In 5
q" - < &SHA
SAH
6. Simulation
By combining Term and Term 2, we can obtain the bound of Ex=1 [v== (F.p) V* (Fx. ]. Finally, by incorpo- rating the estimation error bounds from Lemma 5.10, we can establish the complete regret bound, combining both the estimation and optimization errors. The detailed proofs of Lemmas 5.9, 5.11 and 5.12 can be found in Appendix C.3, C.4, C.5.
We evaluate algorithm in synthetic and mnite-horizon CMDP environment constructed to assess performance un- der both stochastic and adversarial cost settings. The CMDP consists of a state space S (0, 1, 3, 4) with five discrete states and an action space AA {0, 1,2) with three available actions. The decision process unfolds over fixed horizon of
8

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
H steps. At each time step, the agent receives a reward [0, (J,15XX sampled uniformly from the unit interval. In the stochastic setting, the cost E 1-1, 1 is also drawn uniformly and held fixed across episodes. In contrast, the adversarial setting introduces a discrete cost perturbation mechanism: in each episode, the cost is independently sam- pled from a finite set {-1.0, -0.6- -0. 0.2, 0.0, 0.2, 0.6, 1.0), simulating abrupt shifts in constraint feedback. The tran- sition dynamics are time-dependent, where each transition distribution Pr. is independently sampled from Dirich- 0.5. A
formance guarantees. Our work advances the theoretical understanding of CMDPss and provides a robust solution for safe decision-making in adversarial and non-stationary environments. Future research directions include extend- ing our framework to multi-agent settings and investigating scenarios with partial observability.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
let distribution with concentration parameter smaller concentration parameter like 0.5 encourages spar- sity in the resulting probability vectors, meaning that the sampled distributions are likely to concentrate mass on a small subset of next states. This induces partially deter- ministic behavior while still preserving stochasticity across transitions. The initial state is sampled uniformly, ensuring that each trajectory starts from a randomly selected state. Throughout all experiments, the cumulative cost constraint threshold is 0. This controlled CMDP environment enables us to evaluate our algorithm under both stochastic and adver- sarial constraint settings. We plot the cumulative constraint violation across learning episodes(K 3000), where both the stochastic and adversarial curves clearly demonstrate the algorithm's 's ability to ensure sublinear violation growth. In particular, the observed trend aligns with the theoretical O(vK) K), highlighting the algorithm's 's robustness in main- taining feasibility over time.
A Acknowledgment
This work was supported by the National Research Founda- tion of Korea (NRF) grants (No. RS-2024-00350703 and No. AS-2002-000410082)
References
Achiam, J., Held, D., Tamar, A., and Abbeel, P. Constrained policy optimization. In Inl. Conf. Machine Learning (ICML), volume 70, pp. 22-31. JMLR, 2017.
Altman, E. Constrained Markov decision processes, vol- ume CRC Press, 1999.
Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. NeurlPS, 21, 2008.
1000
Adversarfal Vislation
Curulaaive Vitlation
Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In International con- ference on machine learning, pp. 263-272. PMLR, 2017.
800
600
400
Bai, Q., Bedi, A. S., Agarwal, M., Koppel, A., and Ag- garwal, V. Achieving zero constraint violation for con- strained reinforcement learning via primal-dual approach. In AAAI Conf. Artificial Intelligence, volume 36, pp. 3682- 3689, 2022.
200
500
1000
1500
2000
2500
3000
Episode
Figure Cumulative Violation over Learning Episodes
7. Conclusion
Bura, A., HasanzadeZonuzy, A., Kalathil, D., Shakkottai, S., and Chamberland, J.-F. Safe exploration for constrained reinforcement learning with provable guarantees. arXiv preprint arXiv:21 / 22008855 2021.
In this work, we addressed the challenge of online safe reinforcement learning in dynamic environments with ad- versarial constraints by proposing the Optimistic Mirror Descent Primal-Dual (OMDPD) algorithm. Our approach the first to provide optimal guarantees in terms of both regret and strong constraint violation under anytime adver- sarial cost functions, without requiring Slater's condition or the existence of strictly known safe policy. OMDPD achieves regret and violation bounds of Ō(VK), which are optimal with respect to the number of learning episodes K. We also demonstrated that access to accurate estimates of rewards and transitions can further improve these per-
Chen, L. and Luo, H. Finding the stochastic shortest path with low regret: The adversarial cost and unknown tran- sition case, 2021. URL https: /ttp:///axxvvvvo org. /bs/ 2:1 02. 05284.
Chen, L., Jain, R., and Luo, H. Learning infinite-horizer average-reward markov decision process with constraints. In Int. Conf. Machine Learning (ICML), pp. PMLR, 2022.

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Chow, Y., Ghavamzadeh, M., Janson, L., and Pavone, M. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 2017.
Lekeufack, J. and Jordan, M. I. An optimistic algorithm for online convex optimization with adversarial constraints. arXiv preprint arXiv:2412.08000 2024.
Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. Learning policies with zero or bounded constraint viola- tion for constrained MDPs. In Advances Neural Informa- tion Processing Systems (NeurIPS), volume 34, 202 la.
Dann, C., Lattimore, T., and Brunskill, Unifying pac and Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
regret:
Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, Learning policies with zero bounded constraint viola- tion for constrained mdps. Advances in Neural Informa- tion Processing Systems, 34:17183-17111 2021b.
Ding, D., Wei, X., Yang, Z., Wang, Z.,, and Jovanovic, M. Provably efficient safe exploration via primal-dual policy optimization. In Int. Conf. Artificial Intelligence and Statistics (AISTATS), volume 130, pp. 13304-3312 PMLR, 2021.
Luo, H., Wei, C.-Y., and Lee, C.-W. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing
Ding, Y. and Lavaei, J. Provably efficient primal-dual rein- forcement learning for emdps with non-stationary objec- tives and constraints. arXiv preprint arXiv:2201.11900 2022.
Systems, 14222931-22942, 2021.
Müller, A., Alatur, P., Ramponi, G., and He, N. Cancellation- free regret bounds for lagrangian approaches in con- strained markov decision processes. arXiv preprint arXiv:2306.0700) 2023.
Efroni, Y., Mannor, S., and Pirotta, M. Exploration- exploitation in constrained MDPs. arXiv preprint arXiv:2003.021899 2020.
Müller, A., Alatur, P., Cevher, V., Ramponi, G., and He, N. Truly no-regret learning in constrained mdps. arXiv preprint arXiv:2402. 2024.
Germano, J., Stradi, E., Genalti, G., Castiglioni, M., Marchesi, A., and Gatti, N. A best-of-both-worldd algo- rithm for constrained mdps with long-term constraints. arXiv preprint ar arXiv:2304. 14326, 2023.
Neely, M. Stochastic network optimization with applica- tion communication and queueing systems. Synthesis Lectures Communication Networks, 3(1):1-211, 2010.
Ghosh, A., Zhou, X., and Shroff, Provably efficient model-free constrained with linear function approxima- tion. In NeurlPS, 2022.
Qiu, S., Wei, X., Yang, Z., Ye, J., and Wang. Z. Upper confidence primal-dual reinforcement learning for CMDP with adversarial loss. In Advances Neural Information Processing Systems (NeurIPS), volume 33, pp. 15277- 15287. Curran Associates, Inc., 2020.
Guo, H., Liu, X.,
Wei, H., and Ying. I.. Online convex optimization with hard constraints: Towards the best of two worlds and beyond. In Advances Neural Information Processing Systems (NeurIPS), 2022.
Isel,, D., Nakhaei, A., and Fujimura, K. Safe reinforcement learning on autonomous vehicles. 2018 IEEE/RSJ In- ternational Conference on Intelligent Robots and Systems (IROS). pp. 1-6. IEEE, 2018.
Rakhlin, S. and Sridharan, K. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
Singh, R., Gupta, A., and Shroff, N. B. Learning in markov decision processes under constraints. arXiv preprint arXiv:2002.12433. 2020.
Jin, C., Jin, T., Luo, H., Sra, S., and Yu, T. Learning ad- versarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pp. 4860 4869. PMLR, 2020.
Sinha, A. and Vaze, Optimal algorithms for online convex optimization with adversarial constraints, 2024. URL https: http:://axxvv.oorre abs abs//as/....../.// 18955.
Kirschner, J., Lattimore, T., Vernade, C., and Szepesvári, C. Asymptotically optimal information-directe sampling. Arxiv preprint arXiv:201 1.05944, 2021.
Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Learning adversarial mdps with stochastic hard con- straints. arXiv preprint arXiv:2403.03672. 2024a.
Kitamura, T., Kozuno, T., Kato, M., Ichihara, Y., Nishi- mori, S., Sannai, A., Sonoda, S., Kumagai, W. and Matsuo, A policy gradient primal-dual algorithm for constrained mdps with uniform pac guarantees. arXiv preprint arXiv:2401. 2024.
Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Learning adversarial mdps with stochastic hard con- straints. arXiv preprint wxxiv2203..36777 2024b.
10

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Optimal strong regret and violation in constrained mdps via policy optimization. arXiv preprint arX0v:2410.02275, 2024c.
Wei, H., Liu, X., and Ying, L. Triple-Q: model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In Int. Conf. Artificial Intelligence and Statistics (AISTATS), 2022a.
Wei, H., Liu, X., and Ying, L. provably-efficient model- free algorithm for infinite-horizon average-reward con- strained markov decision processes. In AAAI Conf. Artifi- cial Intelligence, February 2022b.
Wei, H., Ghosh, A., Shroff, N., Ying, L., and Zhou, X. Prov- ably efficient model-free algorithms for non-stationary CMDPs. In Int. Conf. Artificial Intelligence and Statistics (AISTATS), pp. 6527-6570. PMLR, 2023.
Wei, X., Yu, H., and Neely, M. J. Online primal-dual mir- ror descent under stochastic constraints. Proceedings of the ACM Measurement and Analysis of Computing Systems, 4(2):1-366 2020.
Yinka- Baaka, C. and Ugot, O.-A. A review of generative adversarial networks and its application in cybersecurity. Artificial Intelligence Review, 53:1721-1736, 2020.

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
A. Missing Related Work
Online Constrained Optimization. Recently, (Sinha & Vaze, 2024) achieved sublinear regret in an adversarial violation setting, However, their approach relies on Online Gradient Descent and thus cannot attain a tighter bound even when the reward is fixed. Meanwhile, Lekeufack & Jordan (2024) proposed an algorithm based on optimistic online mirror descent, attaining comparable regret and violation bounds to ours.
B. Optimistic estimates Related Lemmas
B.1. Proof Lemma 5.6
Lemma 5.6. With probability at least - 6, Pr[G] > 6, where is the good event defined in Eq. (27) for stochastic constraint setting and (2) for adversarial setting, where E (0, 1).
Proof:
Define the following failure events representing the set in which the transitions and observations are far from our current optimistic-estimation::
F
is, as,aa,,, s', h: pp ph (s' (5'1s,a) (s'(s,,,, (s,,
Ih (s,alp)
2HK 8'
FN_
4HSA 2HSAMK 4hn
#-1 (8, v
R=
(s,a.h) Th
Tu (s,ap))
2HK
> 6HSA+ 2HVSAK + 2HSAM 55m
k= (8,0,) V n k- (s, v1
8'
F = {3s, a, -n(3 - (s),,)) (s,
F = h: (s ds a)
> (s, a)} (Stochastic setting)
we define Se, as
k-
a) - 5k (s'
14 (s. a)
3 as, :
21
Ph
3
n (s, a) v
L8
(x, = 31, (8, =
n k- as, -
where set Ls In 128AHK L. In 6SAHK and 8' 3.
Then set FP = UK= F
UK=IFF
UK_i Fg. Hence the Good event is denoted as:
G
CF=
FN FFN U FT U
(27)
And because we did not estimate constraint d in the adversarial setting, the Good event is defined as:
G = FN
Fr
(28)
Finally, is easy to show that the good event G happens with probability at least 1-8. 8. Specifically, Pr[FP F u Fd] [d][ < 28. where the detailed proof can be found (Efroni al., 2020)(Appendix A.1). Furthermore, by Lemma E.2, Pr[ 8 8. Then we can prove that Pr[G]] å by union bound.
B.2. Proof Lemma 5.7
Lemma 5.7. Conditioning on the Good event G, the optimal policy ** induced by the occupancy measure qt under the optimal policy for solving the CMDP problem (3) a feasible solution policy for any episode & [K] such that:
T A de a (v') 0,p's Bs
12

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Proof: For the stochastic cost case, the good event G implies that [d, a) ds,n(s, a) $ & (s, for all (s, h, k) S x A x 8 x [K]. Due to the definition of the optimistic cost dæ, we have (s,a( & ds. Then we have 4.4² & d q² Since x* is feasible solution of (3), have d= d' O. For the adversarial cost case, take dN = dg. Furthermore, conditioned on the good event G, know that the true transition kemnl p Bg. Therefore, q" satisfies that 9r' {9: q(p') 0,p' Bk
C. Key Lemmas proofs for Theorem 5.1
C.I. Proof of Lemma 5.8
Lemma 5.8. Let C VC min
P(gi, (2), Va V(Ju(qu)), VE-I= v(fa-1(mx1)) and define the learning rate as: Then, the regret is bounded as:
?
Regretalg 3.5vC
VE VR-1l +
Proof:
Updating rule use for Optimistic OMD in Algorithm 1:
1
(x(4) al-i + 8' (Au)) - gill
where we know fi) 1-strong convex. By apply Optimistic OMD and convexity of fa fx((),, we have:
(fx(gk) - fx((*)) & (V(()(()))) )²)
For easy notation, we denote v(Ja(ze)) k, V(5x (9)=-(())1)) Ra- Then, we can arrange for the following equal transformation:
term
term
term 3
(g
(qk
Gk. V vk-1)
(qk 2c, V
(gc- 9 V
(29)
We can directly have upper bound for term
<qk ic, V - Va-1) < 119k 9xl12| V
VA-1l12
And any update of the form a" arg min Ka, x) + P(a.c) satisfies for any d e A:
1
<a - d
(Dd, c) a - - .))
11
In our form, replace a² Tk d = Tk, C = I x = R--1 1/ = 1/k we have upper bound for term 2:
(yk - 9k, VE-1) E
(Diāe, Qx-1) D(ue, qu) D(4x, qx-1))
(30)
Replace a* -kx, g², = Qk-1, x Vks 7 = The we have upper bound for term 3:
(qx q
(D(g* qu-1) -D(g* "xx" Diau, 9x-1))
(31)
Combine their upper bound together we have:
(gk- - 4th V
Qh - V/ VE-112 + ID 9k-1) - D(Gu, 9t) D(gk, Gx-1))
1/
1 [D(9" -x-1) DD9*, -D(@k- 9x-1)]
(32)
n7
/ V V4-112 DD(9" ( - D(q", .qk) D(ār. 9k)
D(gk: 9k-1)]
13

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Because we set U is a 1-strongly convex function, have D(g 92)
$ 11
-22l2: then:
1 D "0=","-1) - " ;
1 11 9:112
(9L- q², v & llax - Tall2/V. - Va-1l2
77
2
Then, sum it:
K Σ
1 D(a (0) +
1 1
qt 9², Vv>
19kk Tel12/Vx Va-1llz
Σ
D(g 9k
1
171
171
77--1
k=2
1
(11g= qxll2 + 11.c 12))
27/
We define C = @ (gq,, 42), then we have:
term (h)
term (c)
1
qh
JC+
11gh
V V
VA-1/2
(112
2x11 + 11
7/1
217je
k
Besides, we will use the following fact:
14
4u 2/ Vn
V-- = inf
p
v
vx-
+
1
ok 0x11
2
2p
And by setting p = 1, we have upper bound for term (b):
1as V V &
2
IV
V
+ 27
9k 4u112
Then, consider learning rate Th in the following condition:
VC min
V V-11l +
V. - v,-1
2==1
m
min
2
-i=1
| v
1
1
max
2
Σ
V V 1-11
VC
i-1
Then for term (a), the upper bound is (2)
VVC & vC(2 EKE
VV Va-Ill + 2). Now, get:
nx
K
K
K
yh
g* V+) & ve
2
Σ
V - V - 12 +
+
V - V 12
2
k
K
+
14k
1x
1kk
||gx - as- 112
2m
2TT
277x
k-
VC
2
V
V
V
2
+
7
V - V
2
k=1
k=1
1
qn
2
qx 3
21
211
k=
where the second inequality arrived by dropping positive term
1lgk
1
Now, we first deal with the last two terms:
K
K
1
C
1
C
-
Σ
Ig
21
27jk
2
M
21
R-1
k
14

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Now, we get:
K
K
K
qk
9
VR
VV
V
Vk-
+2
T
Vk
VR-18
+
2
2
K
K
< <3vC
V1 - V V4-1 +1
+
Σ
7k+1
V
- V 4 1
2
k=1
And notice 7
M min
E V v
|V V
min
Vv VA-1
Thus, we get:
vC
7]++1
VE
VR-1112 E
Σ V. V V--
V V
2 k
k=1
vC
K Σ
V V
Next, we can have the upper bound:
K
The o vk) & 3v0
V V V +1
1
V vA-1
2
3.5vC
Σ VE V +1
Finally, we get:
K
(fu(an) - fb((²)) &
(V(f((g))) 9b - -³*> = Σ
{q q", v
K
& 3.5vC
Vx V +
C.2. Proof of Lemma 5.10
Lemma 5.10. Let p& denote the transition kernel in the candidate set BR. and let Fs and du be the estimations used by OMDPD. Then, conditioned on the good event G, the estimation errors for the stochastic cost case can be bounded as follows:
V (Fx, (F,P)) Ó(VNSAH2K + SA
(33)
VTA - - (da,
ÖOVNSSHHK + SH
k-1
The estimation error for the adversarial cost case can be bounded as follows:
y (de,p) V (du, & Ö(VNSAHPK + AH
(34)
15

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Proof: To prove (33), it is sufficient show that
K
yo (Cx, (G)) (* & Ó (VNSAH'K+ + S A113)
for & r, The right-hand side of the above inequality can be decomposed
K
K
4T (4x. V (L,pp)))
vTa (Gn. pw) TT (Cx.p)
Th ( (L,pp)
Term 1
Term 2
Note that Kh,n (8) v LL/lnn - - v 1) & VTg. Then the estimated function & satisfies (8, E [-1 VLs, 1 + Ls] for all (s,a, ES xS Ax [H] x [K]. By Lemma E.6 with = 1 vLs. Term bounded as
Term & Ô (VNSAH3K + *HHAH)
To bound Term 2, by Lemma E. we can write it as
K
H
Term Σ
IE
Σ
en (Sh. an) - (an an) 88, 81, Tk.
Furthermore, conditioned on the good event G, it follows that
(u((s,a) (o(s,a)-Eaal (s, & [E)(,,a) - 2h (s,
+ 26 +1 ( ( (asa)-lanle Ban(s,a) 521 as,
L8
ni k-
Applying this, Term 2 can be bounded as
Term &
Σ
EE
Σ
11
2
k n
Ls
81, Tk.
& &HHNSAK + HSA)
where the last inequality follows from Lemma E.2. Finally, we have
K
y TTh (2x, - V* (t.p) = Term + Term & Ô (VNSAH*K- + AHH
as required.
Next, (34) direct consequence of Lemma E.6 with C 1.
C.3. Proof of Lemma 5.9
Lemma 5.9. Let V f4x( denote the subgradient of the potential function fa evaluated at qs. Under OMDPD, the cumulative variation of consecutive gradients bounded as:
V6SAHK(1 ('(Ak))
V
SAH
Proof: In the algorithm, we have:
A++1 = A& + ((x) = exp(3x) - 1, falg) = a(-rta+ ('AA)) gl+) - qx
Based on convexity, we have:
((Ax) < 4({ + 1 (A() - AR-1)
= + ('(e)) -ald
16

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Based on drift analysis, have:
((Ax)) (AA=-1) (Aa)) alldk gxl+)
(35)
And we know:
1
Su(gk) = a(-ik + 4' (>x) (x1=)= (x++) [v( + a(Fkg))) = ('(ss) a((dk ac]+t
2
lluue 9k 1
(36)
Combine (35) and (36) together:
((Ax)) p(Ax-1) & fa(g)) + a(Fx qx)
Also, we have:
[x(4²) = - + 45 ('xax) [dx (1 -110** qail2
p/ aº 1 11a 9
2
Combine the equation together, we have:
x(Ax) - $(Ax-1) & Sa((s) + alFF
((Ax) 2(Ax - a 9h) - fola*) & fa(()) - fxla*)
o(\x) (( + a(Fi * - ax) & fa(()) fx(9")
Take the summation over K, we have:
K
K
((Ax)
( * r 9k)== & Σ fk(()) f4(9*)
Based on Lemma 5.8, we have:
- -a(")) & 33.5C
Σ | V
Now, we analyze the upper bound part. V = V/K(( VR-1 = v
V
V/((qa)) = a--ix + ((()
Vik-i(g--1) a-- + Φ $1(Xe-1)dx- dx-
Thus:
Vx 7 [V - V (
= a²l - (fx 46 (Ax) Ax)dd 22 (> 1)
-² ف 12 + 1 (Nt (x - 8' (Xi= 12 2allix Fr fl-illo'AAndd
)d
(1()))d ('(Nx-1)d 1| ||0 1 (A (Ax-1) )d, + D'(A 1dd
=|dx 4' 1)) + 2' (A--1))1))))))) (ds 1)12
< 2( + v LB) SSH 1 (Ax)) - (Az )) + 2(1 + v VLs) &' 6((A=11)lI
First deal with (1)=-)))1 we define (xx) = exp( (3x) - 1, so we have ('(A.) = Bexp( > O, Vk: E K. Because
exp(x) increasing, we have ('(1)) < 2222)) & & 4 ((()). Thus, Vk K we obtain:
| ( - )| & [}xx()))
For (0((x) - 1112 we use (a b)2 & 2 + 8² and have:
| (Ats) Φb (a+-1) )2 (Ae))1 2 + |b (A+-1)11
17

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
[| (Ax)) = 21 (Ax))
Therefore, we have the upper bound:
@ (dx 4 (X < 2(1 + V L 4 (Aa) ('(++11)11 + 2(1 VLS) SAHI (X
$ 2(1 + STH 2|0'(Axx]1 + 2(1 + T.8 (>x))]]
6(1 + L [>)]) (2x))
Therefore,
V V v 1
K
K
K
Σ Fi 1 12+
| (Aw)de - D' ('(Aa-1) 1d 21 +2
Σ
| -
- E 0'(Ax-1)da)
--1
K
K
K
& Ox
Fk
12
Σ
('Axx) dr (0(AA-1)dd +
| - nk- - (1(As-1)dE-) 1ddk-1l
diff
2
difl 3
For diff 1:
Fk Fx- 15 a/ (1+ 2
For diff 2:
K
1' (W 12 a
6(1 ==== / LLA Σ
For diff 3:
K (1+ A (dx--1)d
Ph Pk Fx-1ll - I'(A6-1)d--ll1 &
K
(1 + TT) 6(1 + (IASSAH((AR)
K SAH 24(1 + (Lo)
K
Σ
SAH 36(1 + (Lo)
K
Σ 6(1 + / 2 = (((A)) + 2
(Q((A)) + 1) v 6(1 + LL)
where the last inequality holds for vā & + 1, > 0. Therefore, we have the upper bound of / =k=1 Vt V
K
K
K
V
Σ
ih - Āー 12
Σ
(Do - - (0aaa11)d (Xo--)))
diff
diff 2
18

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
2
Fx Āk- |||| (Ax)dd 4' (x
k=1
diff 3
2/ (1 V (T) SHHK ('((A)) 6(1 + v (T)
1
2HI2
+ a/ 6(1 + v SAHK + aF (F 6(1 (TS)SSAHK
dift
< 20/ 6(1 + LL) + 204' 6(1 (L))SSHAK = 2a(1+ VLJ (1 (((K))
V6SAHK (1 ('()))
SAH
where the last equality holds for choosing a 2(1+vL,)SAH
C.4. Proof of Lemma 5.11
Lemma 5.11. Based on Lemma 5.9, the following upper bound holds:
K Σ
Fl n < 2(1 + (LA 4VCVGSAHK)
Proof: Based on Lemma 5.8, 5.9, we have the following relation:
K
K
K
((Ak) + a Σ (FI 4d Ttg)) E Σ fa(mx) fx(l*))+*++)))""))"))))))))))f < 3.5vC
V V
k=1
< 3.5vC
V - v=-1l3 +1
V6SAHK (1 + ('(AK))
< 3.5vC
SAH
Now we can have:
K
V6SAHK + (AK))
((Ak) + >
[i
gr & 3.5vC
SAH
k=1
K
VGSAHK(1 + +x(KK))
((xx)
-f & 3.5VC
SAH
K
VGSAHK SAH
+AVE Bexp(BAk) MANIBAKWGSSS 66AHK
exp(BAk) + Σ
[1 1tth [g) $ 4vC
SAH
K
B A.CAVGSAAKK 1)
V6SAHK
17 9th -x < exp(3Ak)
AVC
+1
SAH
SAH
K
B A.CCVBB 1
V6SAHK
>
[i 9t [x < exp(3Ak)
+4VC
aSAH
aSAH
= 2(1 + VLYSAH + 8(14 VL)VVV 66AHK
2(1 (SAH +VVCGGSAHK
where the last equality obtained by 2(1+VLGSAHH 3
SAH
AVEV6SAHK
19

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
C.5. Proof of Lemma 5.12 Lemma 5.12. Under the stochastic rewards setting, with probability least 1-26, have:
K
K 2 SSAH
[ SAH
2 In(
Proof: Based on the optimistic estimates, we know that: n = kk- + 8k 1 (s, a). Then, we have the following relationship:
F q F q F q² 19 (s,
< F nr 1-
where the inequality holds for 8k (s, and at is non-negative. Thus, we have the following relationship easily:
K
K
F
F 9-h
19"1
Based on norm property, and for each episode kt we have:
FF - 1 1- 1117-Ax-llyy 2 11
and from the definition of reward and Fact 5.4, we know that ||F f--1 and 11 & SAH. Thus:
|T - 1 & SAH
If the objective costs are stochastic under Lemma 5.6, and by the Azuma-Hoefrding inequality we have:
Pr
Σ
Σ
3 M
$ 8
2e
Thus by setting M as:
KK 1)
M = SAH
In
2
have when the objective costs stochastic, with the probability least
28:
K-1
K-1
(K
1)
2
Σ
q
Σ
10
<
&SAH
In
Then, by the absolute value property, we can obtain:
K
K-1
K-1
Σ
F
d"
Fl
1- 19
+ + a²
1
K-1 Σ A=1
1-
+
(K - 1)
2 8
SAH
In(
+ SAH
2
C.6. Proof of Lemma 5.13
Lemma 5.13. Based on Lemma 5.8, 5.9. Then, the following upper bound holds:
K
x 16(1 + VLA)VCVSSAHK K K
VVSAHK SAH
d 9k)
+
where dj dg under stochastic setting and d; dy in adversarial setting.
20

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Proof: To begin with, we deal with the stochastic setting first, which dg dg. Since have the fact that min and max value for regret that: - gxl & gF Ft (x) $ 1 9xl- And 1A Fl & ||Felllll9* gxll2
(1 + ALH. Thus, we have:
K 3
Σ gK - r/z 9k)
pkgg))
F q 9xl = -11+ LLASAHKK
Therefore, we have:
V6SAHK(1 + ('RR))
((Ak) + Σ 17 arh - gx & 3.5VC
SAH
V6SAH + ('(A))
(AAx) + a(-(11+ SAHKH & 3.5VC
SAH
VGSAHK
B (exp(BAK) 6SAHK
exp(8Ax) 1 a11(1(( SLASAHH) & 4VC
+ +4V0
SAH
SAH
(1-8- (
VGGSAHK
AGAHHK
exp(3)x)
& <0((1 + V (T)SAHK) + AVC
+1
SAH
SAH
a((1 + (LS)SAHK) 4VC
V6SAHK
+1
SAH
exp(BAR)
(1- 1--8-VVC
VBSAHK SAH
where the last inequality holds for choosing such that 4.C
V6SAHK
O:
SAH
V6SAHK
SAH 4VC/6SAHK
8 B.4
<1-B<
SAH
which the choosing of match when we prove the regret bound in that choose 3 &
SAH AGAAASAHK
Here, let
SAH and we have:
8/CV6SAHK
a((1 + (LASAHK) 4VC
VOSAHK
+1
SAH
exp(3Ak) &
1 113..4V6
VESAHK
SAH
a((1 (TA)SHH) 4VC
(BSAHK SAH
66AAHK
- -2a((1 + VT.JSAHK) + 8VC
+
SAH
VGSAHK
-K+8VC
+
SAH
where the last inequality holds for take 20+V
Then, recall the definition d A + ald] gx so
AK a Et= [d]
K Idd q+ Thus, take the log operation and we have:
66SAHK
BAx & In
K K+8VC
+2)
+2
SAH
1
VGSAHK
Ax
$
In
K &VC
+2
B
SAH
1
66SAH
T
ln
K K+8VC
+
3
SAH
21

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
K
1 &
V6SAHK
de
In
K
K
+
a.
SAH
V6SAHK SAH
16(1 + VLJ)VCVSAHHKI
K K+8VC
+
The proof of d2 dy is almost same with the situation that d2 dr. Hence, can directly have:
au & 16(1 + VLs) in (K+8VC
v V6SAHK SAH
+
D. Main Theoretical Analysis
D.1. Proof of Theorem 5.1
Proof: In this section, our proof is based on the roadmap described in Figure 3. The context divided into Regret and Violation parts, respectively.
K $(Ax) + Σ
Prove Regreetag
F - 7x qk S Regretaig
Lemma 5.7
R=1
Prove
Combine
Prove
Lemma 5.8
K
Lomma 5.11
Regret(K)
11 9- PC gk]
hm
Lemma 5.10
Lemma 5.9
Violation(Sto)
Prove
Prove
- (b(k))
Prove
Lemma
Lemma 5.9(Adv)
Violation(Adv)
Combine
Figure Proof Roadmap Theorem 5.1
1.1.1. REGRET BOUND PROOF
Recall the definition of Regret:
Regret( K)
Σ v"* (F.p) -V*
K Σ
[ (Fk, VTL (F. (F,p))
yT (F,p) V (Fx,
(Fx, px))
Estimation Error
Optimization Error
We can bound the "Estimation Error" term by using Lemma 5.10. Now, let's go through the details of the "Optimization Error" term. We will first decompose it as follows:
y (F.p) a* (Fu,
Σ EE - -
$
B
E
q- 1 gu
Term 1
Term
Thus, it's clear that we can use Lemma 5.11 and Lemma 5.12 to bound these two terms, respectively. Therefore, the Regret bounded in the following inequality:
Regret(K)
Σ h-1
y (F.p) V (F,
Σ
(Tk, - (F.p)) + Σ y* (F.p) V**
k-1
22

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
K
K
[F,p]] (Tk, (F,
+
E q-1
Blrk
- El m+
Lemmaa
K
In 2
OHS SAHA
SAH + 2(1 (L) AVCV6SAHK)
KK
2 In 0
OWNSAHPRSSAAAT A SAH
3(1 + (LS) AVCV6SAHK)
D.1.2. VIOLATION BOUND PROOF
Stochastic setting. Recall the definition of stochastic Violation:
K Violation(K)- Σ [vT (d.p)) Σ yau (d. VAN (dpss px))
K V (dx, pkk
Estimation Error
Optimization Error
Similarly, first Lemma 5.10 to bound "Estimation Error" term under the stochastic setting. Next, we will deal with the optimization error term by Lemma 5.13:
Σ V (dx.
Σ BBd +x] & 16(1 + VL.) K
[K+8V
V65AHK SAH
+
Hence, the whole stochastic Violation is bounded as:
K
K
Violation(K) (K)
Σ
[ (d,))]
Σ (dd -
- (de,
+
Σ
VTL (dk.
Lemma 5.10
Lemma 5.13
V66SAKK
&ÖWNSAH*K-S AH") 16(1 VIS In
K K+8VC
+
SAH
Adversarial setting, When we deal with adversarial constraint, by the definition:
K
K [v (x))
Violation K) (v=,
= (dk. - V (x)) +
Listiattio
Optimization
In this situation, we proved an additional estimation error bound Lemma 5.10 with adversarial case and with Lemma 5.13, the following bound can be obtained:
K
K
Violation K)
= (dk.
m th (dr,p) t (dk: Px)]+
v px)]
Lemma 5.10
Lomma 5.13
V6SSAK SAH
SWNNSAH*K+S 16(1+ GLYVVVGAAKG
K K+8VC
+
D.2. Proof of Remark 5.2
If we fix the reward and constraint, where 7z = dg = dg-1, then we have the following relationship adapted from Lemma 5.9;
Vx VELIP a
Σ ('ce)dd ('(Aa-1)da-1
23

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
<
Tighter Bound Analysis. Similar to proof in Appendix C.4 we can obtain:
K
V 2
((Ax) + a >
[i
- 1 mx ] & 3.5vC
2SAH
K
2SAHK
exp(3Ax) - 1 +
[ik q - - qm & 3exp(3Ax) 335vC
2S
K
V2SAHK
>
[ - -x & exp(BAR)
8 3.5VVC
+1
2SAH
B-3.5VC
/2SAHK
1 q-' - p/ exp(BAk)
25AH
1
1
a
a
2(1 + VL
where the last equality obtained by a 2(1+VT.)AA B
1
2SAH
Now, clearly prove O(1) bound for
3.5v CV C.W.V/SSHHR 2SAHK
L - Fx ]-
E. Useful Lemmas
Lemma E.I (Lemma E.15 of (Dann al., 2017)). Consider two MDPs Mi
(r)) and M2
(8, A, ( (r ,). For any policy and s, h, the following relation holds.
Vū (s; p²) VT (s; 22²)
H
(37)
=
(1, an) - - an) + (p) - -. 8h, V..
sh = 8, xpp
where (p), (- 8h, an) b+ (5r ,p²)
Lps (s' sh an) (s';r (st))
Lemma E.2 (Lemma D.5 of (Liu et al., 2021b)). With probability at least 1 - 8, Th (8,a)
K
6HHSA SHASK 2HSAI K 5ln 2HK
5
1
h-
(8,0)
A
(38)
Σ
K
H
In
(s,a)
& 4HSA 2HSAI K 4ln
2HK
(s. Th
8
(8.0)
where 9% (s, = Pr(s; s, ab a $1, T).
Lemma E.3 (Lemma of (Jin et al., 2020)). Conditioned the good event for all S)xxxx,,)))Sxxxxxxxxxx there exists constants C1, C2 0 for which we have for all id BB that
an (s,
C2
k-1 (pm- P 18,0)1 C.V.
(s-() v "h
k-
The following lemma is Lemma 10 of (Chen & Luo, 2021) with boundedness constant C for the reward function rj-
Lemma E,4 (Lemma 10 of (Chen & Luo, 2021)). Let Tk be an arbitrary function such that T (s, a) [-C, for all (s,0, E S x A x [M] x [K]. If the true transition kernel satisfies p Bj. then for any j E B3 we have
Σ
E Σ
(p
F. 8h, (1) (V (:Tk.))) V V 81, Th.P
O(CHAS
Lemma E.5 (Lemma 4 of (Chen & Luo, 2021)). For any reward function policy transition kernel p.
(s an) ) 8T, > Var Σ
E
Wa(sn, Oni R,) 81, T
(39)
24

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Lemma E.6 (Estimation Error for p). Let py denote the transition kernel in the candidate set Bg, and let Eg be arbitrary function with (s, a) [-C, CJ for all (8,a, a, h k) S x A [H] [K] and some C O. Then, conditioned on the good event G, the estimation error the transition kernel can be bounded follows:
v (Lx.P) - V (lx. Pk)1 & ÓICVNSAHHK + AH").
Proof. By Lemma E.1, the desired term can be rewritten
v (Cx, - TMH (cr.
E
Σ (pn
p-)(- 1h, a (1; Cu F²) 11,, TR.
h-
1
E
Σ
(ph
ph sh, an) (2, 81, TR.P
h=
Term (I)
E
(ph ph) she an) (1 Lx. V4 (1l,,, $1, TR.
Term (11)
where we use the short-hand notation Pa( we have
= Eves Pa (s() Under the good event G,
ah (s, v
C2L
(pn - ph) |s,a)] & Cy..
(40)
k-
n (s,a)
k-
nh
due to Lemma E.3, Applying this, Term (I) can be written as
K
Term (I)
E
Σ (ph- p-)( 8h, an V (x,P) |81, TK,P
Σ
E
(pn- (s' 8h. un V (s, 81, TR.
Σ
E
Σ (ph phs sh (n) (s': (x.p) - 1E (ss"pa((lsnaa) V (s"; Cx. p)) 81, Tk,
E
(pn. pss sny an) (s'; (sk p) (- Voa (s" (1, |
S1, Tk.
(s 8h, an) 1.B k- (sns an) v
E
h+t (s'slx.p)) p) E E Ba V (s" Ex,, p)
81, T..
n
Torm (I-a)
C2L (sh, and
E
V v (8': Ex, Byg nu (1 V (x 81, Thp
h-1
1h
Term (1-b)
where the third equality follows from (ph (s')
s, E.a) ( an) Vi ( p) = 0, and the last inequality is
due to (40). Note that the expectations can expressed by occupancy measures. Furthermore, in Term (I-a), we can replace
25

---

An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
E. with pa Then this be rewritten
Term (I-a)
K
H
Pn(s' Sh and n/ (sh. an)
= =
E
1 (s'; ; - E Es -p (1) Veti (s"; Lb. 81, Tk.P
5
of s'-ph, (s' |s,a)=00
K
H
Ph(s' Shi an) (V (s; L. p) Bx hit (5": Eus p))²
= CiV 17
Σ
E
Σ
Σ
88, T
n '(hh
8f sh-ph (8' 1s,
K
V Phis's s.a) h+1 (s: lk. p) Bp
h+1 (s"; pk)
= CIV LI
Σ
as:
Σ
T (5- v
k=1 (s,a,h)
K
CIV
Σ
Th asp
Σ
pals' (s: Es (11,,) TTt
Viti(s"; (5"; lk. p))
(v.0.h)
o sspi, (s))))
K
(s, a) T (s. v
Σ
Σ
Σ
1=1 (s.0.h) sppa ())
where the inequality follows from the Cauchuy-Schward inequality. Here,
Σ
(n(s' | 8s a,,)) (e41 (5; lx. Eg (1a,a)) Vht (8"; ls, p)) Vu(s,aTTE,))
d'pp (=)))))0000 Then, Term (I-a) is upper bounded as
K
9h Th (s, (s,a;p) a;p)
Term (I-a) & CIv LID
Σ (s,a,h)
9 ((ss.a)VVass
Σ
n -s, a)
k=1 (s,a.h) step (s))
K
H
K
In (s,
CI TP
E
81, TR.P Wn (8h, 4h3 ah3 Pk
x N
Σ
k- Th
(8,
(a,a,h)
Since >"" (sp, an) El-CH, CHJ almost surely, we have Var (>iH- (s an) 31, TK:P) & C²2 Furthermore, we can bound the later term with Lemma E.2. Then it follows that
By Lemma E.5, we have E
D (sh, ass Tk.P) $1, TK.
< Var EEiL Ck an)
$1, Tk.
Term (I-a) Ō(CVKH² VNSAH) Ō(CVNSAHPK)
To bound Term (I-b), under the good event G, we have | (s'; - Esr -pa (lIanan)) Vol (s" :k,pp) & 2CH. By Lemma E.2,
C2
81, 18, Tk. 1 1 O(CHH(
Term (I-b) & 2CHS Σ
E
T1p
(Shy an) v
Then we have
Term (1) Term (I-a) + Term (I-b) = Ô (CVNSSAHHK+ +CHSA))
By Lemma E.4, we can bound Term (II) as
Term (II) S(H
Finally, we have
K
V Th (lx.p) - (=(((x,++) & Term (I) + Term (II) = Ō(CUNSAHHK + SH A).
26


Reviews:
[{"review_id": "PVJbr6qw2N", "reviewer": "Reviewer_zWwP", "summary": "The paper studies the online learning problem for episodic constrained Markov decision processes, where the constraint functions are either stochastic or adversarial, and the transition function is unknown. A key technique the authors introduce is a surrogate objective function for the policy optimization step. The authors propose an optimistic mirror descent primal-dual algorithm: (1) the primal step updates the occupancy measure via the standard optimistic gradient step for the surrogate objective function; (2) the dual step performs the standard dual ascent step. In both stochastic and adversarial settings, the authors prove that the standard regret and the strong constraint violation (only counts non-negative violations) are sublinear in the number of episodes, without assuming Slater's condition and knowing a strictly feasible policy.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the valuable comments provided by the reviewer. We address the reviewer's questions as follows.\n\n>**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.\n\n[1] arxiv.org/abs/1908.00305\n\n[2] arxiv.org/abs/1311.1869\n\n>**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.\n\n[1] arxiv.org/abs/2310.18955\n\n[2] \"Online convex optimization with hard constraints: Towards the best of two worlds and beyond.\" \n\n[3] \"Online learning in CMDPs: Handling stochastic and adversarial constraints.\" \n\n>**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.\n\n>**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.\n\n>**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.\n\n\n>**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.\n\n>**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.\n\n>**W3:** The proof of Eq.(23) is shown in the proof of Lemma 5.8(Appendix C.3, line 816-851).\n\n>**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.\n\n>**Q2:** $\\mathcal{N}$ is maximum number of non-zero transition probabilities\n\n>**Q3:**  The optimal policy is not episode-dependent, defined in Eq.(3). \n\n>**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.", "claims_and_evidence": "(1) A key quantity of the main result is $\\mathcal{C}$ which is used throughout the proof. Since it is not well-defined for the KL divergence, the main result can be vacuous. \n\n(2) For the adversarial cost case, the authors assume the feasibility of all constraints, which is not the standard adversarial loss setting.\n\n(3) In the regret analysis, the comparison policy is a nearly feasible policy instead of an optimal policy. In this sense, the regret bounds can be suboptimal.", "methods_and_evaluation_criteria": "The proposed primal-dual method seems appropriate for the problem, but its conditions for correct performance characterization remain unclear.", "theoretical_claims": "I went through the proof sketch in Section 5, but I didn't check the proofs. The authors provide a proof sketch for the adversarial and stochastic settings. Their key difference is the violation analysis. It is not clear the reason why both cases can use the same comparison policy in Lemma 5.6.", "experimental_designs_or_analyses": "The authors didn't provide experimental results.", "relation_to_broader_scientific_literature": "This work is of interest to the broader safe reinforcement learning community.", "essential_references_not_discussed": "To the best of my knowledge, essential references have been discussed.", "other_strengths_and_weaknesses": "Other weaknesses on clarity:\n\n(1) The violation analysis of adversarial constraints in Theorem 5.12 follows the same analysis. This suggests that the adversarial setting is not inherently more challenging than the stochastic setting. It would be helpful if the authors could clarify the technical challenges for analyzing adversarial constraints. \n\n(2) The authors apply the optimistic online mirror descent to a surrogate objective function for the primal update, achieving strong constraint violation bounds. It would be helpful if the author could clarify why this is the case for the strong constraint violation bounds, not strong regret bounds. The optimistic gradient method was used in the following papers to improve convergence. It would be helpful if the authors could clarify the challenges of obtaining strong regret and constraint violation bounds. \n\n- ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs\n\n- Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs\n\n(3) A key step to bound the violation of adversarial constraints is to use the drift-plus-penalty framework for (23). It would be helpful if the authors could provide a formal proof of it for the CMDP setting?", "other_comments_or_suggestions": "It would be helpful if the authors could compare different techniques in the literature that lead to varying regret guarantees and highlighted the technical challenges in achieving strong regret or constraint violation bounds in the adversarial/stochastic settings.", "questions_for_authors": "(1) What is the definition of anytime adversarial constraints?\n\n(2) What is the definition of $\\mathcal{N}$ in Theorem 5.1?\n\n(3) Is the optimal policy in Theorem 5.6 episode-dependent?\n\n(4) How do accurate estimates of rewards and transitions improve regret bounds?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vk0M5Vm5br", "reviewer": "Reviewer_7EBa", "summary": "This paper introduces the Optimistic Mirror Descent Primal-Dual (OMDPD) algorithm, a novel approach for online constrained Markov decision processes (CMDPs) with anytime adversarial constraints. Unlike prior methods that assume known safe policies or rely on Slater’s condition, OMDPD achieves optimal regret $\\tilde{O}(\\sqrt{K})$ and strong constraint violation bounds $\\tilde{O}(\\sqrt{K})$ even in dynamic and adversarial settings. The algorithm leverages optimistic estimates, online mirror descent, and adaptive dual updates to balance exploration and constraint satisfaction. If accurate reward and transition estimates are available (via a generative model), the regret can further improve to O(1). OMDPD surpasses existing CMDP approaches by handling both stochastic and adversarial constraints, making it highly relevant for applications in autonomous systems, robotics, and cybersecurity. ## update after rebuttal", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the valuable comments provided by the reviewer. We address the reviewer's questions as follows.\n>**Response to Weakness**\n\n>**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. \n\n[1] \"Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization.\"\n\n[2] \"Online learning in CMDPs: Handling stochastic and adversarial constraints.\"\n\n[3] \"Cancellation-free regret bounds for lagrangian approaches in constrained markov decision processes.\"\n\n[4] \"Learning adversarial mdps with stochastic hard constraints.\"\n\n[5] \"Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback.\"\n\n>**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:  \n$$\n\\max_{q \\in \\mathcal{Q}} \\ \\frac{1}{K} \\sum_{k=1}^K h_k(q) \\quad \\text{s.t.} \\quad g_k(q) \\leq 0.\n$$ \nTo ensure theoretical guarantees, we require the following basic conditions:\n(1) The reward is generated stochastically; The cost can be generated either stochastically or adversarially;\n(2) The potential function $f$ used in the updates is 1-strongly convex;\n(3) The occupancy measure lies in a compact convex set(Fact 5.3);\n(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.$\nUnder these conditions, the core structure of our algorithm remains applicable. We will provide the proof in our final version.\n\n>**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: \n\n| Episode               | K=1   | K=500   | K=1000  | K=1500  | K=2000  | K=2500  | K=3000  |\n|-----------------------|-------|---------|---------|---------|---------|---------|---------|\n| Constraint Violation  | 12.75 | 757.07  | 882.14  | 957.41  | 1012.13 | 1055.41 | 1091.21 |\n\nIt is clear that a sublinear regret for the constraint violation is achieved. \n\nWe 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.", "claims_and_evidence": "The paper provides a thorough theoretical analysis and compares its results against various existing CMDP algorithms. The findings demonstrate that the proposed method achieves sublinear regret and sublinear constraint violation under adversarial settings, effectively validating its theoretical claims.", "methods_and_evaluation_criteria": "The paper introduces the Optimistic Mirror Descent Primal-Dual (OMDPD) algorithm, which combines optimistic online mirror descent (OMD) with a primal-dual framework to handle adversarial constraints in CMDPs. The method leverages optimistic estimates for transition kernels, rewards, and costs, using confidence sets and Lyapunov-based updates to regulate constraint violations dynamically. The evaluation is based on two key theoretical criteria: regret minimization and strong constraint violation bounds.", "theoretical_claims": "The proof of Theorem 5.1 is well-structured, and Figure 1 effectively illustrates the relationships between Lemmas 5.7–5.11. The detailed proof steps in the appendix are logically sound, clearly presented, and follow a rigorous progression.", "experimental_designs_or_analyses": "No experiment results. While the paper provides strong theoretical guarantees, it lacks empirical experiments to validate the practical performance of OMDPD in real-world CMDP scenarios. Benchmarking against existing algorithms on simulated or real datasets would strengthen its applicability.", "relation_to_broader_scientific_literature": "This paper contributes to the broader literature on constrained reinforcement learning (RL), online convex optimization, and adversarial learning by introducing a unified framework for CMDPs with both stochastic and adversarial constraints. By leveraging optimistic mirror descent and primal-dual methods, the proposed OMDPD algorithm achieves optimal regret and strong constraint violation bounds, advancing research on safe decision-making in dynamic and adversarial environments with applications in autonomous systems, robotics, and cybersecurity.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n+ The paper establishes that OMDPD achieves optimal regret $\\tilde{O}(\\sqrt{K})$  and strong constraint violation bounds $\\tilde{O}(\\sqrt{K})$, ensuring both efficiency and safety in stochastic and adversarial settings. These bounds improve upon prior approaches that only handle stochastic constraints or allow weaker forms of violation.\n+ OMDPD provides a generalized approach that works under both stochastic and adversarial rewards/costs, bridging the gap between these two settings. \n+ The theoretical results show that if accurate estimates of rewards and transitions are available ( through a generative model), the regret bound can be further improved to O(1). This highlights the algorithm’s adaptability and potential for achieving near-optimal learning in CMDPs with additional information.\n+ This paper uses refined error bounds(Lemma 5.9) for estimating transition kernels, rewards, and costs in CMDPs. By leveraging a Bellman-type law of total variance, it improves upon Lemma 29 of Efroni et al. (2020)[1] by a factor of $\\tilde{O}(\\sqrt{H})$, enabling more precise value estimation and better learning efficiency.\n\nWeaknesses:\n+ The paper claims that removing Slater’s condition is an advancement, as it eliminates the need for a strictly feasible policy. However, in many practical scenarios, a near-feasible solution is often available, making this contribution less impactful than suggested.\n+ The proposed algorithm is developed under the assumption that reward and cost functions are linear, which may limit its applicability. It remains unclear whether this approach can generalize to a broader class of convex CMDP settings where rewards and costs exhibit nonlinear dependencies on state-action pairs. Many real-world problems, such as risk-sensitive decision-making or energy management, involve complex, non-convex constraints that may not align with the assumptions made in the theoretical analysis. A discussion on potential extensions to general convex or non-convex CMDPs would strengthen the paper’s contributions and applicability.\n+ While the paper provides strong theoretical guarantees, it lacks empirical experiments to validate the practical performance of OMDPD in real-world CMDP scenarios. Benchmarking against existing algorithms on simulated or real datasets would strengthen its applicability.\n\n[1] Efroni, Yonathan, Shie Mannor, and Matteo Pirotta. \"Exploration-exploitation in constrained mdps.\" arXiv preprint arXiv:2003.02189 (2020)", "other_comments_or_suggestions": "None.", "questions_for_authors": "Please refer to the Other Strengths And Weaknesses part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LLcusqHryO", "reviewer": "Reviewer_7ukS", "summary": "The paper considers the online learning problems in the constrained MDP problems. The objective is to maximize the reward while satisfying the constraints, where the system state transits according to an underlying MDP. The problem is formulated as a finite horizon episodic setting with $H$ periods in each episode. The main goal of the paper is to develop an on-policy learning algorithm to achieve a $O(\\sqrt{K})$ regret upper bound on the objective and the constraint violation, where $K$ denotes the number of episodes.\n\nThe main algorithm of the paper is based on a primal-dual framework. The optimal policy for the CMDP problems can be formulated as an LP. However, the LP cannot be directly solved since the problem parameters are unknown. Therefore, the paper considers the Lagrangian dual formulation of the LP and updates the primal variable, which is the occupancy measure, and the dual variable in an online manner. To be specific, the paper employs an optimistic mirror descent algorithm to update the primal variable occupancy measure, while using the online gradient descent algorithm to update the dual variable. At each step, the newly observed data is again collected to refine the estimation of the problem parameters, which will be used in the update of the next step. \n\nThe paper shows that by properly picking the parameters in the mirror descent algorithms that update the primal and dual, the main algorithm of the paper is able to achieve a regret bound of $O(\\sqrt{K})$ over the total reward and the constraint violations. The paper further shows that when the reward and cost functions are deterministic, then the algorithm would achieve an $O(1)$ bound on the total reward, since the primal variable is updated using optimistic mirror descent, however, the constraint violation bound turns out to still be at the order of $O(\\sqrt{K})$. \n\nOne theoretical contribution claimed by the paper is that their result does not require the slater's condition to be satisfied, which is usually adopted to bound the range of the dual variable by the existing algorithms. Therefore, even if there is no guarantee of the existence of a strictly feasible solution, the algorithm in the paper still works.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the valuable comments provided by the reviewer. We address the reviewer's questions as follows.\n>**Response to Essential References Not Discussed**\n\nWe 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.\n\n>**Response to Weakness and Question**\n\n>**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. \n\n>**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.\n\n>**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.\n\n>**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.\n\n>**Q2: Benefits of using OMD** Please see the response in Weakness-(3). Please let us know if further explanation is needed\n\n>**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.\n\n>**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.\n\nWe 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.", "claims_and_evidence": "The claim looks convincing to me.", "methods_and_evaluation_criteria": "The proposed algorithm comes with theoretical guarantees. However, there is no numerical validation of the algorithm.", "theoretical_claims": "The proof looks correct to me.", "experimental_designs_or_analyses": "There is no numerical experiment.", "relation_to_broader_scientific_literature": "The paper develops primal-dual algorithms to study the constrained MDP problems. The algorithm is based on a LP formulation of the CMDP problems. The new part of the algorithm is to utilize the optimistic mirror descent algorithm to update the primal decision variable.  The paper shows that such a design could achieve a better bound over the objective value when the reward and cost functions are deterministic.", "essential_references_not_discussed": "The algorithm developed in the paper is based on the LP formulation, where the primal-dual algorithmic framework is widely developed to solve it. However, primal-based algorithms have also been developed to solve the LP formulation or the CMDP problems in general. For example, the primal-based algorithm has been developed in [1], [2], [3], [4], and [5]. In particular, the paper [6] develops resolving primal LP methods to solve the CMDP and achieves the first instance-dependent $O(1/\\epsilon)$ sample complexity. I think these papers are worth mentioning in the literature.\n\nReferences:\n\n[1]. Yongshuai Liu, Jiaxin Ding, and Xin Liu. Ipo: Interior-point policy optimization under constraints. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 4940–4947, 2020.\n\n[2]. Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(167):1–51, 2018.\n\n[3]. Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. Lyapunov-based safe policy optimization for continuous control. arXiv preprint arXiv:1901.10031, 2019.\n\n[4]. Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. arXiv preprint arXiv:1801.08757, 2018.\n\n[5]. Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480–11491. PMLR, 2021.\n\n[6]. Jiang, Jiashuo, and Yinyu Ye. \"Achieving $\\tilde {O}(1/\\epsilon) $ Sample Complexity for Constrained Markov Decision Process.\" NeurIPS, 2024.", "other_strengths_and_weaknesses": "Strength:\n\nThe paper develops a primal-dual algorithm to solve the CMDP problems. Using the optimistic mirror descent to update the primal variable is an interesting idea and the benefits is that when the reward and cost functions are deterministic, the bound over the gap of objective values can be improved to $O(1)$ (though the constraint violation gap is still $O(\\sqrt{T})$). In the general case, the algorithm enjoys an $O(\\sqrt{K})$ bound over the gap of objective values and constraint violations.\n\nWeakness:\n\n1. The $O(\\sqrt{K})$ bound (or the equivalent $O(1/\\epsilon^2)$ sample complexity) is now quite standard in the literature and has been developed in many previous works. Though the result can be improved to $O(1)$ when the reward and cost functions are deterministic, the bound over the constraint violation is still $O(\\sqrt{K})$.\n\n2. It is claimed that the paper considers a stronger formulation of the constraint, as discussed in line 60. However, it turns out that the problem can still be formulated as LP, which is the same as the formulation induced by the weaker formulation of the constraint. The algorithm is also developed to solve the LP in an online primal-dual manner. Therefore, I am not sure whether the stronger anytime constraint formulation would introduce any difference here. I have asked a question for further clarification from the authors.\n\n3. The primal-dual framework has been widely developed, see for example Efroni et al., 2020. The main difference of the algorithm in the paper seems to be that optimistic mirror descent has been adopted to update the primal variables. However, the only benefits seems to be that when the reward and cost functions are deterministic, the bound over the gap of objective values can be improved to $O(1)$. But the bound on the constraint violation is still $O(\\sqrt{K})$. So the benefits of using optimistic mirror descent is not immediately clear to me.", "other_comments_or_suggestions": "Please refer to my questions below.", "questions_for_authors": "1. It is claimed that the paper considers a stronger formulation of the constraint, as discussed in line 60. However, it turns out that the problem can still be formulated as LP with decision variables being the occupancy measure, which is the same as the formulation induced by the weaker formulation of the constraint. The algorithm is also developed to solve the LP in an online primal-dual manner. Therefore, I am not sure whether the stronger anytime constraint formulation would introduce any difference here. Could you please provide further clarification on this?\n\n2. Could you provide more explanation on the benefits of using an optimistic mirror descent to update the primal variable? I understand that one potential benefit is that when the reward and cost functions are deterministic, the bound over the gap of objective values can be improved to $O(1)$. But the bound on the constraint violation is still $O(\\sqrt{K})$.\n\n3. One of the theoretical contribution is that the algorithm does not require the slater's condition to be satisfied. However, previous work, for example, Efroni et al. (2020), requires this condition to develop an upper bound on the dual variable, which is useful for scaling the range of the dual variable to a unit box. However, I think even if the slater's condition does not hold, there must be some other way to upper bound the dual variable, or we just assume a given upper bound over the dual variable. So it seems to me that removing the Slater's condition is not a big part. Please correct me if I am wrong about this. \n\n4. Could you please comment on the practical performance of your algorithm, since there is no numerical experiment in the paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper tackles constraint MDP with adversarial loss and adversarial constraints (the constraint is represented in the form of another cost function).  It improves previous work by removing the regret dependency on the constant involved in the Slater's condition, and also allows for adversarial constraints.  The former improvement comes from the use of a surrogate objective function that has appeared in previous work for full-information settings.  Overall, the technique used in this work is a natural combination of existing techniques, and turns out to give a new bound in the considered setting. I recommend for acceptance. 

Reviewer zWwP pointed out that the constant $\mathcal{C}$ in Theorem 5.1 is undetermined.  Although the proposed solution is reasonable and standard, please make it clear in the revised version.
Decision: Accept (poster)