Learning Adversarial MDPs with Stochastic Hard Constraints
Authors: Francesco Emanuele Stradi
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Venue: ICML 2025 poster (2025)
Keywords: CMDP
hard constraints
online learning
Primary area: theory->online_learning_and_bandits

Abstract: We study online learning in constrained Markov decision processes (CMDPs) with adversarial losses and stochastic hard constraints, under bandit feedback. We consider three scenarios. In the first one, we address general CMDPs, where we design an algorithm attaining sublinear regret and cumulative positive constraints violation. In the second scenario, under the mild assumption that a policy strictly satisfying the constraints exists and is known to the learner, we design an algorithm that achieves sublinear regret while ensuring that constraints are satisfied at every episode with high probability. In the last scenario, we only assume the existence of a strictly feasible policy, which is not known to the learner, and we design an algorithm attaining sublinear regret and constant cumulative positive constraints violation. Finally, we show that in the last two scenarios, a dependence on the Slater's parameter is unavoidable. To the best of our knowledge, our work is the first to study CMDPs involving both adversarial losses and hard constraints. Thus, our algorithms can deal with general non-stationary environments subject to requirements much stricter than those manageable with existing ones, enabling their adoption in a much wider range of applications.

Learning Adversarial MDPs with Stochastic Hard Constraints
Francesco Emanuele Stradi! Matteo Castiglioni
Alberto Marchesi Nicola Gatti"
Abstract
autonomous vehicles must avoid crashing (Wen et al., 2020; Isele et al., 2018), bidding agents in ad auctions must not deplete their budget (Wu et al., 2018; He et al., 2021), and recommendation systems must not present offending items to their users (Singh et al., 2020). A commonly-used model that allows to capture such additional requirements is the constrained MDP (CMDP) (Altman, 1999), where the goal is to learn a loss-minimizing policy while the same time satisfying some constraints.
We study online learning in constrained Markov decision processes (CMDPs) with adversarial losses and stochastic hard constraints, under ban- dit feedback. We consider three scenarios. In the first one, we address general CMDPs, where we design an algorithm attaining sublinear regret and cumulative positive constraints violation. In the second scenario, under the mild assumption that a policy strictly satisfying the constraints exists and is known to the learner, we design an algorithm that achieves sublinear regret while ensuring that constraints are satisfied at every episode with high probability. In the last scenario, we only assume the existence of strictly feasible policy, which is not known to the learner, and we design al- gorithm attaining sublinear regret and constant cumulative positive constraints violation. Finally, we show that in the last two scenarios, a depen- dence on the Slater's parameter is unavoidable. To the best of our knowledge, our work is the first to study CMDPs involving both adversarial losses and hard constraints. Thus, our algorithms can deal with general non-stationary environments subject to requirements much stricter than those manageable with existing ones, enabling their adoption in a much wider range of applications.
We study online learning problems in episodic CMDPs with adversarial losses and stochastic hard constraints, under bandit feedback. In such settings, the goal of the learner is to minimize their regres-the difference between their cumulative loss and what they would have obtained by al- ways selecting a best-in-hindsight policy-, while at the same time guarantecing that the constraints satisfied during the learning process. We consider three scenarios that differ in the way in which constraints are satisfied and are all usually referred to as hard constraints settings in the literature (Liu et al., 2021; Guo et al., 2022). In the first scenario, the learner attains sublinear cumulative positive constraints violation. In the second one, the learner satisfies constraints every episode, while, in the third one, they achieve constan! cumulative positive constraints violation.
To the best of our knowledge, our work is the first to study CMDPs that involve both adversarial losses and hard con- straints. Indeed, all the works on adversarial CMDPs (see, egg., (Wei al., 2018; Qiu et al., 2020)) consider settings with sofi constraints. These much weaker than hard con- straints, they are only concerned with the minimization of the cumulative (both positive and negative) constraints violation. As a result, they allow negative violations to cancel out positive ones across different episodes. Such can- cellations are unreasonable in real-world applications. For instance, in autonomous driving, avoiding a collision clearly does not "repair" crash occurred previously. Furthermore. the only few works addressing stochastic hard constraints in CMDPs (Liu et al., 2021; Shi et al., 2023; Müller et al., 2024; Stradi et al., 2025) are restricted to stochastic losses. Thus, their techniques cannot be easily generalized to our setting. Our CMDP settings capture many more applications than theirs, since being able to deal with adversarial losses allows to tackle general -tationnn environments, which are ubiquitous in the real world.
1. Introduction
Reinforcement learning (Sutton & Barto, 2018) studies prob- lems where a learner sequentially takes actions in an envi- ronment modeled as a Markov decision process (MDP) (Put- erman, 2014). Most of the algorithms for such problems focus on learning policies that prescribe the learner how to take actions so as to minimize losses (equivalently, maxi- mize rewards). However, in many real-world applications, the learner must fulfill additional requirements. For instance,
DEIB, Politecnico di Milano, Milan, Italy. Cor- respondence to: Francesco Emanuele Stradi <francescoe- manucle.stradie @ polimi.it>..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning Adversarial MDPs with Stochastic Hard Constraints
We refer to Appendix A for a complete discussion on related works.
Search (CV- estimates such policy and its associ- ated constraints violation in a constant number of episodes. This is done by employing two no-regret algorithms. The first one with the objective of minimizing violation, and the second one with the goal of selecting the most violated con- straint. A stopping condition that depends on the guarantees of both the no-regret algorithms enforces that the number of episodes used to estimate the desired policy is sufficient, while still being constant. After that, CV-OPS S runs S-OPS with the estimated policy, attaining the desired results.
1.1. Original contributions
We start by addressing the first scenario, where we design an algorithm cagledthm-called Sublinear Violation Optimistic Pol- icy Search (SV-OPS) guarantees both sublinear re- gret and sublinear cumulative positive constraints viola- tion. SV-OPS builds on top of state-of-the-art learning algorithms in adversarial, unconstrained MDPs, by intro- ducing the tools necessary to deal with constraints violation. Specifically, SV-OPS works by selecting policies that opti- mistically satisfy the constraints. SV-OPS updates the set of such policies in an online fashion, guaranteeing that it is always non-empty with high probability and that it col- lapses to the (true) set of constraints constraints--ttiffying policies as the number of episodes increases. This allows SV-OPS to attain sublinear violation. Crucially, even though such an "optimistic" set of policies changes during the execution of the algorithm, it always contains the (true) set of constraints- satisfying policies. This allows SV-OPS attain sublinear regret. SV-OPS also addresses a problem left open by Qiu et al. (2020), i.e., learning with bandit feedback in CMDPs with adversarial losses and stochastic constraints. Indeed, SV-OPS goes even further, as Qiu et al. (2020) were only concerned with soft constraints, while SV-OPS is capable of managing positive constraints violation.
Finally. we provide a lower bound showing that any algo- rithm attaining o( (VT) violation cannot avoid a dependence on the Slater's parameter in the regret bound. We believe that this result may be of independent interest, since it not only applicable our second and third settings, but also to other settings where larger violation is allowed.
2. Preliminaries
2.1. Constrained Markov decision processes
We study episodic constrained MDPs (CMDPs) (Altman, 1999) with adversarial losses and stochastic constraints. These are tuples M == (X, A, P, {()) (G.) a). T is the number of episodes." X and A are finite state and action spaces. P : X x A x X + |0, 1] is transition fune- tion, where P(x' [x, a) denotes the probability of moving from state x E X to x' E X by taking a E A.2 {G))²-) is the sequence of vectors of losses at each episode, namely f, E [0, 1||xAA We refer to the loss for state-action pair (x,a) E X x A as (xxx. a). Losses are adversarial, i.e., no statistical assumption on how they are selected is made. {G.Y is the sequence of matrices that define the costs characterizing the m constraints at each episode, namely G, E [0, 1] for (2r, a) E Xx stochastic, i.e., the matrices G, are i.i.d. random variables distributed according to an (unknown) probability distribu- tion G. Finally, a = [ai...., Om]] E [0. r.]T is the vector of cost thresholds characterizing the m constraints, where o; denotes the threshold for the i-th constraint.
T
Next, we switch the attention to the second scenario, where we design a safe algorithm, i.e., one that satisfies the con- straints at every episode. To achieve this, we need to assume that the learner has knowledge about a policy strictly sat- isfying the constraints. Indeed, this is necessary even in simple stochastic multi-armer bandit settings, as shown in (Bernasconi al., 2022). This scenario begets consider- able additional challenges compared to the first one, since assuring safety extremely limits exploration capabilities, rendering techniques for adversarial, unconstrained MDPs inapplicable. Nevertheless, we design an algorithm-calle Safe Optimistic Policy Search (S-OPS) PPSPOPPSsthhe that attains sub- linear regret while being safe with high probability. S-OPS s works by selecting, at each episode, a suitable randomiza- tion between the policy that SV-OPS would choose and the (known) policy strictly satisfying the constraints. Crucially, the probability defining the randomization employed by the algorithm is carefully chosen in order to pessimistically ac- count for constraints satisfaction. This guarantees that a sufficient amount of exploration performed.
For E [m]. the i-th constraint cost x A is denoted by (t, a). Costs
The learner uses a policy π : X x A + [o, 1], which defines probability distribution over actions each state. We de- note by π (-|1z) the distribution at x E X, with <(a|z) being
We denote an episode by E [T). where (a... is the set of all integers from to and [b] := [I...]].
focus w.l.o.g. on loop-free CMDPs. This means that X is partitioned into L + 1 layers Xo...., Xt with X, = {aa] and X2 = {.t]. Moreover, the loop-free property requires that P(r'
"For case of notation,
Then, in the third scenario, we design algorithm that at- tains constant cumulative positive constraints violation and sublinear regret, by simply assuming that policy strictly satisfying the constraints exists, but is not known to learner. Our algorithm- called Constant Violation Optimistic Policy
P(r'(z, (x.a) > 0 only if x' E Xx+1 and
x Xx for some & E [0... L. LL-].. 1]. Any (episodic) CMDP with horizon H that is not loop-free can be cast into loop-free free one by duplicating the state space H times. In loop-free CMDPs, we let k(x)) E (0... I.] he the layer index in which state x E is.
2

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Algorithm 1 CMDP Interaction at episode t [T]
the loss while ensuring that all the constraints are satisfied. Thus, our baseline OPT,,G, is defined the optimal value of a parametric linear program, which reads follows:
1: lx, Gt chosen adversarially and stochastically, resp.
2: Learner chooses a policy iT' : X x A + [0,
3: Environment is initialized to state xop
4: for O,........ ...,,
do
mingeasay)
e Eqq s.t. G q S a,
5: Learner takes action dg ~ (T (- (T))
O.T,,G, ==
(I)
6: Learner sees & (TT, ax): (T,, ag) Vi E [m]
7: Environment evolves #h+1 P( (x)
8: Learner observes the next state 2-+11
where E [0. 1] is a vector encoding an occupancy measure, while ((M) is the set of valid occupancy mea- sures. Notice that, given the equivalence between policy and occupancy, the (offline) learning problem can be formulated as a linear program working in the space of the occupancy measures q. since expected losses and costs are linear in q-
9: end for
the probability of action a E A. Algorithm details the learner-environment interaction at episode E [7], where the learner has bandit feedback. Specifically, the learner observes the trajectory of state-action pairs (IR, as), for k E [O... L - 1], visited during the episode, their losses ( ax), and costs (t, (*) for E [m]] The learner knows X and A, but they do not know anything about the transition function P.
As customary in settings with adversarial losses, we mea- sure the performance of an algorithm by comparing it with the best- in hindsight constraint constraint-satisfiinng policy. The per- formance of the learner is evaluated in terms of the (cumu- lative) regret RT- =- Σi=1 ej of T OPT where i : + 1 l, is the average of the adversarial losses over the T cpisodes and G := gG] is the expected value of the stochastic cost matrices. We let q" be best-in- ii-hinssight constraint-satiifying occupancy measure, i.e., one achieving value OPTz, while we let x² be its corresponding policy.
We introduce the notion of occupancy measure (Rosenherg & Mansour, 2019a). Given transition function P and policy the vector gf E [0, |||XXxxX| is the occupancy measure induced by P and æ. For every E Xx. a E A, and x' E X with 1: E [0..... L 1], it holds pPa a, x²) == P[R = x. 0k = a. 2k+1 = x' PP. Moreover, we also let q (I, = Exrext qfT (xr, a, x²) and (P((()) = Eoea g (TT (2xa) a). Next, we define valid occupancies.
Thus, the regret reduces to Rr := - eg (g -²)) For the ease of notation, we refer to P by simply using thus omitting the dependency on and Te. Our goal is to design learning algorithms with Rr = oT)), while at the same time satisfying constraints. We consider three different settings, all falling under the umbrella of hard constraints settings (Guo et al., 2022), introduced in the following.
Lemma 2.1 (Rosenberg& & Mansour (2019b)). A vector q [0, 10 is valid occupancy measure of episodic loop-free MDP if and only if it holds:
ΣEE
Ak (O..O...LL L-1]
2.2.1. 1. GUARANTEEING SUBLINEAR VIOLATION
2EX; aEA E'X2+1
Σ Σ a(x,a,z))= = E Σ g(2', a)
In this setting, we consider the (cumulative) positive con- straints violation VT == max Σt= G qt =+}+=
rEA
x'eX, 4 18EA
Vk E [1... L- 1), Vx E X₃
where [x] + == max(0. x). Our goal is to design algorithms with V o (T)). To achieve such goal, we only need to assume that the problem is well posed, as follows:
1a
where P is the transition function of the MDP and Pa the one induced by q (see below).
Assumption 2.2. There is occupancy measure g", called feasible solution, such that G' qp S a.
Notice that any valid occupancy measure q induces a tran- sition function pa and a policy 79, with (*(''(a,a) q(z, a, a,,z)))))))) x1//g(z, a) and (a(z)) = q(z, a)/q(z).
2.2.2. GUARANTERING SAFETY
In this setting, our goal is to design algorithms ensuring that the following safety property is met:
2.2. Online learning with hard constraints
Definition 2.3 (Safe algorithm). An algorithm safe if and only if G qe S a for all / [7].
Our baseline for evaluating the performances of the learner is defined through a linear programming formulation of the (offline) learning problem in constrained MDPs. Specifi- cally, given a constrained MDP M ;= (X, A, P. e, G, characterized by a loss vector E [o, x| a cost matrix G E [0, x| xm, and a threshold vector a E [0, Li such problem consists in finding policy minimizing
As shown by Bernasconi et al. (2022), without further as- sumptions, it is not possible to achieve Rt = o(T") while at the same time guaranteeing that the safety property holds with high probability, even in simple stochastic multi-armed bandit instances. To design safe learning algorithms, we
3

---

Learning Adversarial MDPs with Stochastic Hard Constraints
need the following two assumptions. The first one is about the possibility of strictly satisfying constraints.
the following, given any d E (0, we refer to the event defined in Lemma B.2 as (8).
Assumption 2.4 (Slater's 's condition). There is an occupancy measure qº: G q < a. We call 4 strictly feasible solu- tion. while a x induced by qº a strictly feasible policy.
Similarly, we define confidence sets for the transition function of CMDP, by exploiting suitable concentra- tion bounds for estimated transition probabilities. By let- ting M1 a, x') be the total number of episodes up to E [T] in which (x, a) E X x A is visited and the environment transitions to x' E X, the estimated transi- tion probability for (æ, a, z') is defined as P, (x' |x,a)= = M,(x,a,x') Then, at episode & E (7]. the confidence set [ for the transitions is P. = ((x.0 (o,o,2")XXXxxx Phiaaaa with (1 a) - P,(x'11,, x0 a)l S ( 0.
The second assumption is related to learner's 's knowledge about a strictly feasible policy.
Assumption 2.5. Both the policy x and its costs / = (81.-...8mm] == G qp are known to the learner.
Intuitively, Assumption 2.5 is needed to guarantee that safety holds during the first episodes, when the leaner's uncertainty about the costs is high. Assumptions 2.4 and 2.5 are often employed in CMDPs (see, e.g., (Liu et al., 2021)), as they are usually met in real-world applications of interest, where it is common to have access to a "do-nothing" policy resulting in no constraint being violated.
pr.ax' = (: (F: P(='1zz
where we let ex a, = 2/ Prta')zz max (I
+ 3 mmax(11 N,,,, for some confidence 8 E (0, 1). It is well known that, with probability at least 1 - 46, it holds that the transition function P belongs to Pe for all t E [T] (see (Jin et al., 2020) and Lemma G. for the formal state- ment). At each [7]. given a confidence set P,, it is possible to efficiently build a set A(P,) that comprises all the occupancy measures that are valid with respect to every transition function P E P.. For reasons of space, we defer the formal definition of A(P:) to Appendix G. Lemma G.1 implies that, with high probability, the set (M) of valid occupancy measures is included in all the "estimated" sets A(P:). for every t E [T]. In the follow- ing, given any confidence ō E (0, 1), we refer the event that A(M) C. Neerzy A(P:) as (6), which holds with probability at least - 40 thanks to Lemma G.I.
141m(T|X|14166)
2.2.3. GUARANTEEING CONSTANT VIOLATION
In this setting, we relax Assumption 2.5, and we only as- sume Slater's condition (Assumption 2.4). We show that it is possible achieve constant violation, namely Vr is upper bounded by constant independent of T. while attaining similar regret guarantees compared to the second setting. Our results depend on the Slater's parameter p E [0, L). which is defined as p = (MM) minje[m] [a: - 9. 9. with qº = arg m(x) [m] [m] [a; 9. q] being its associated occupancy. Given Bg == g. qº. we have p min:g/m) [a; - -... By Assumption 2.4, it holds p > O.
Finally, for ease of presentation, given E (0, 1) we define a clean event (6) under which all the concentration bounds for costs and transitions correctly hold. Formally, ga.a (8) := (6) n g (8), which holds with probability at least 1 - 56 by a union bound (and Lemmas B.2 and G.
3. Concentration bounds
In this section, we provide concentration bounds for the estimates of unknown stochastic parameter of the CMDP. Let Nz(2, a) be the number of episodes up to & E [T] in which the state-action pair (I,, a) E X x A is visited. Then, (z, a)= == E.ery (x..)) with 1 a} = 1 if and only if (z, a) is visited in episode t, is an unbiased estimator of the expected cost of constraint i E [m] for (z,a), which we denote by (1, a) := Ea-glgr.az, a)]. Thus, by applying Hoeffding's 's inequality, it holds, with probability at least - ó that (0,, a) (z, a)l < (x(x, a). where we let the confidence bound (x a) == min(1, [T A||]|//m///// (1, NN(ax,))) }}}} (refer to Lemma B.2 for the formal result). For ease of notation, we let G, E [0, XXIXXXXXXXXX be the matrix of the estimated costs "r,((x,a). Moreover, we denote by & E [0, x| the vector whose entries are the bounds (1r, a), and we be a matrix built by concatenating vectors & in such a way that the statement of Lemma B.2 becomes: GG,- - G 3 E, holds with probability at least 1 5, where and A are applied component wise. In
4. Guaranteeing sublinear violation
We start by designing the SV-OPS algorithm, guaranteeing that both the regret Ry and the positive constraints violation Vr are sublinear in T. To get this result, we only need the existence of a feasible solution (Assumption 2.2). Dealing with adversarial losses while limiting positive constraints violation begets considerable challenges, which go beyond classical applorationeexplotttiiin trade-offs faced in uncon- strained settings. On the one hand, using state-of-the-art algorithms for online learning in adversarial, unconstrained MDPs would lead to sublinear regret, but violation would grow linearly. On the other hand, naïve approach that randomly explores compute set of policies satisfying the constraints with high probability can lead to sublinear vi- olation, at the cost of linear regret. Thus, clever adaptation of the techniques for unconstrained settings is needed.
let E, E [0, x|
4

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Algorithm 2 SV-OPS
Intuitively, uy (19,, (g)) represents the maximum probability with which (Ing, ag) is visited when using policy *e. given the confidence set for the transition function built so far. The upper occupancy bounds are combined with the exploration factor y to compute optimistic loss estimator (zx a) for every state-action pair (z, Q) E X x A (see Line 9), After that, SV-OPS updates all the counters given the path traversed in Algorithm (Lines 11 11-12), it builds the new confidence set Pt. and it computes the matrices G, and E, of estimated costs and their bounds, respectively, by using the feedback (Line 14). To choose a policy 71+1, SV-OPS first computes an unconstrained occupancy measure gt+1 accord- ing to an unconstrained OMD update (Orabona, 2019) (see Line 15). Then, a++1 is projected onto suitably-defined set of occupancy measures that optimistically satisfy the con- straints. Next, we formally define the projection (Line 16).
Require: X, A, o. 7.7
I: for E [0... I 11, (,, E Xx x Ax X6+1 do
2: No(2, + 0; Mo(2, +0
3:
(x,a,,x) + //
4: end for
5: mi <- =
6:
for L [T] do
7: Choose N. in Algorithm 1 and receive feedback
8: Build upper occupancy bounds for l E [0... L 1):
( as) f- max PEP J F (3),
9: Build optimistic loss estimator for (r, a) E x A:
4(2.0) (x
=1 =1
E(( () +
otherwise
10:
for k E 10...L-11 do
Ce, arg min D(gl((++1) gEA(P)) s.t. ( (2)
11:
Ne(IE, ax) + NN (xx, 0n) +1 Me(xs,, ak, T2+1)) t M ok, T241) + 1
12:
13:
end for
14:
Build Pc, Ge, and E, as in Section 3
15:
Build unconstrained occupancy for all (x, a, x
where D(qllge+11 is the unnormalized KL-divergence be- tween q and 0t+1 Problem (2) is cenetry-constrained convex mathematical program, and, thus, it can be solved ef- ficiently, that is, in polynomial time, for an arbitrarily approximate solution. 3 Intuitively, Problem (2) performs a projection onto the set of g E A(P)) that additionally T satisfy (G, E,) g S a, where lower confidence bounds
@+,122,0, 2e a (ila)))
16:
PRPOO Gr, Bc, is feasible then #++1= + PROI(@ E., P.) P.)
17:
18:
else
19:
9++1 + any q E A(P:)
G, E, for the costs are used in order to take an optimistic approach with respect to constraints satisfaction. Finally, if Problem (2) is feasible, then the next episode SV-OPS selects the g induced by solution T to Problem (2) (Line 17), otherwise it chooses policy induced by any q E ((P)) (Line 19).
20:
end if
21:
T 7
22:
end for
Our calld Sublinear Violation Optimistic Pol- icy Search (SV-OPS)-wort by selecting policies derived from set of occupancy measures that optimistically sat- isfy cost constraints. This ensures that the set is always non-empty with high probability and that it collapses to the (true) set of constraint-satisfying occupancy measures as the number of episodes increases, enabling SV-OPS to attain sublinear constraints violation. The fundamental property preserved by SV-OPS is that, even though the "optimistic" set changes during the execution of the algorithm, it always subsumes the (true) set of constraint-satisfyin occupancy measures. This crucially allows SV-OPS to employ classi- cal selicy-selection methods for unconstrained MDPs.
The optimistic approach adopted in Problem (2) crucially allows to prove the following lemma.
Lemma 4.1. Given confidence ö E (0, 1). Algorithm 2 ensures that PROJ( G., Pt) is feasible at every episode t e [T] with probability at least 1 58.
Lemma 4.1 holds since, under the event gG. (8), projection is performed on set subsuming the (true) set of constraints- satisfying occupancies. Lemma 4.1 is fundamental, as it allows to show that SV-OPS attains sublinear VT and Rr.
4.1. Cumulative positive constraints violation
Algorithm 2 provides the pseudocode of SV-OPS. At each episode E [T], SV-OPS plays policy ne and receives feed- back as described in Algorithm (Line 7). Then, SV-OPS computes an upper occupancy bound u, (1 (4) for every state-action pair (zg, a&) visited during Algorithm 1, by us- ing the confidence set for the transition function Pi-1 com- puted in the previous episode, namely, it sets (Ix,, ax) == maxTeP.., P.a (z, a) for every & E [O... I 1] (Line 8).
To prove that the positive constraints violation achieved by SV-OPS is sublinear, we exploit the fact that the concen- tration bounds for costs and transitions shrink at a rate of (1/VT).. This allows us to show the following result.
As customary in adversarial MDPs, we assume that an optimal solution Problem (2) be computed efficiently. Otherwise, we can still derive all our results up to small approximations.
5

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Theorem 4.2. Given 8 E (0,1), Algorithm attains VT X
Algorithm 3 S-OPS
O
with prob. at least 1 1686.
Require: X, A. a, T. 6, n, π .8
I: for k [0... L 11, [I, a, x. E Xx x Ax Xx+1 do
2: No(a, t 0; Mo(a, a, x') +
4.2. Cumulative regret
3: Φ (2,a,z²) F |x Xe+1
The crucial observation that allows to prove that the re- gret attained by SV-OPS grows sublinearly is that the set on which the algorithm perform its projection step (Prob- lem (2)) always contains the (true) set of occupancy mea- sures that satisfy the constraints, and, thus, it also always contains the best-in- -inhinddsght constraint constraint-satisfiing occu- pancy measure q². As result, even though cost estimates may be arbitrarily bad, SV-OPS is still guaranteed to select policies resulting in losses that are smaller than or equal to those incurred by q² This allows us to show the following:
4: end for
w. probability Ao == ma
L-ai
5: m
L-
probability 1 1 Ào
6: for t E [T] do
7: Select n, in Algorithm and receive feedback
8: Build upper occupancy bounds for E [0... 1]:
Ut (IL, ax) + max PEP ạ Pite (12k, as)
9:
Build optimistic loss estimator for (x, 0) E X A:
f((raa))) ue(2o)
a1 =
Theorem 4.3. Given 8 E 10, by setting
Eí(2, a)
otherwise
7 = / Algorithm 2 attains Ry 1 0 L /Xl///// (TX with prob. at least 1 - 106.
10:
for ls E [O... - 1] do
11:
(a as) e- N (ax, as) +
12:
Mi (k: IE+1) <- Mi-1 ( ax. rx+1) 1 +1
5. Guaranteeing safety
13:
end for
14:
Build P., Go and E, as Section
We design another algorithm, called S-OPS, attaining sub- linear regret and enjoying the safety property with high prob- ability. To do this, we work under Assumptions 2.4 and 2.5. Designing safe algorithms raises many additional challenges compared to the case studied in Section 4. Indeed, adapting techniques for adversarial, unconstrained MDPs does not work anymore, and, thus, ad hoc approaches are needed. This is because safety extremely limits exploration.
15: Build inconstrained occupancy for all (x, a, x'):
@1,1 a,, +- (t, a, de) Mila
16:
if ((++1 (10,, P.) is feasible then
17:
@+11 + (ROI( Gr, E., P.)
18:
Ret1 t 7
19:
Build ue41 E [0, x so that for all (z, (z)
Our algorithm- Safe Optimistic Policy Search (S-OPS)- builds on top of the SV-CFS algorithm developed in Sec- tion 4. Selecting policies derived from the "optimistic" set of occupancy measures, as done by SV-OPS, is not sufficient anymore, as it would clearly result in the safety property be- ing unsatisfied during the first episodes. Our new algorithm circumvents such an issue by employing, at each episode, a suitable randomization between the policy derived from the "optimistic" set (the one SV-OPS would select) and the strictly feasible policy 9 Crucially, we show next, such a randomization accounts for constraints satisfaction by taking pessimistic approach, namely, by considering upper confidence bounds on the costs characterizing the constraints. This is needed in order to guarantee the safety property. Moreover, having access to the strictly feasible policy T and its expected costs 3 (Assumption 2.5) allows S-OPS to always place a sufficiently large probability on the policy derived from the "optimistic" set, so that suffi- cient amount of exploration is guaranteed, and, in its turn, sublinear regret is attained. Notice that S-OPS effectively selects non-Markovian policies, as it employs randomiza- tion between two Markovian policies at each episode.
(041(2, + max q
Pites (x a)
(in(((r. 1et1 |
20:
maxie|m]
min (tt)) Be41
de oo if E [m] (Gr,s + E.) /u4t > 0ii
21:
if E [m] (Gt, + Ee) ui+1 S an
22: else
23: @o+1 +- take any g E A(P:): A +
24: end if
with probability de
25: Re+1
n
with probability - A
26: end for
from SV-OPS the policy selected at the first episode is ob- tained by randomizing a uniform occupancy measure with TO (Line 5). The probability Åg of selecting ' is chosen pessimistically. Intuitively, in the first episode, being pes- simistic means that D must guarantee that the constraints are satisfied for any possible choice of costs and transitions, and, thus, Ao := maXic[m] (L-a//L-..). Thanks to As- sumptions 2.4 and 2.5, it is always the case that À < 1. Thus, Ti * x with positive probability and some explo-
Algorithm 3 provides the pseudocode of SOPS.. Differently
6

---

Learning Adversarial MDPs with Stochastic Hard Constraints
ration is performed even in the first episode. Analogously to SV-OPS, at each i [T], S-OPS selects a policy म and receives feedback as described in Algorithm 1, it computes optimistic loss estimators, it updates the confidence set for the transitions, and it computes the matrices of estimated costs and their bounds. Then, as in SV-OPS, an update step of unconstrained OMD is performed. Although identical to the update done in SV-OPS, the one in S-OPS uses loss estimators computed when using randomization between the policy obtained by solving Problem (2) and the strictly feasible policy X. Thus, there is a mismatch between the occupancy measure used to estimate losses and the one com- puted by the projection step. The projection step performed by S-OPS (Line 16) the same as the one in SV-OPS. S. Specifically, the algorithm projects the unconstrained oc- cupancy measure q onto an "optimistic" set by solving Problem (2), which, if the problem is feasible, results in oc- cupancy measure tt+1. However, differently from SV-OPS, s, when the problem is feasible, S S-OPS does not select the policy T i derived from I but it rather uses a random- ization between such a policy and the strictly feasible policy T (Line 25). The probability de of selecting лO is chosen pessimistically with respect to constraints satisfaction, by using upper confidence bounds for the costs and upper oc- cupancy bounds given policy g (Lines 19 and 21). Such a pessimistic approach ensures that the constraints are satis- fied with high probability, thus making the algorithm safe with high probability. If Problem (2) is not feasible, then any occupancy measure in A(Pt) can be selected (Line 23).
Algorithm 4 CV-OPS
Require:
Anytime adversarial MDPs regret minimizer A", on- line linear optimizer A
1:
for E [2' do
2: Select n. AA
3: Select di + A
4: Play ia and observe feedback as prescribed in Algorithm 1
5:
Feed faz, ax. Lie[m: 0e, (90, 0x) 7 )1 to A
6: Feed {-
--EE (g,, a2) ]emm to A
7:
if maxxe[mm] Ere( E (2x, ax) + 2
2C /C2)(ln(()) v 21 2 + 202 vT then
8:
Go to Line 11
9: end if
10: end for
11: X - max
ge. (12, -a) rE k=1
Σ
2T. /2 In 1/6
1m|m
12: # + nt, with probability 1/t, for T [t]
13: Run S-OPS with B.
a. - p for all E [m]] and x 7
ability Xe can be exploited to overcome such a challenge. Indeed, we show that each d can be upper bounded by the initial Ao and, thus, loss estimator from feedback received by using a policy computed by an OMD-like update is avail- able with probability at least 1 - Ao. This observation is crucial in order ot prove the following result:
Theorem 5.2. Given E (0,1). by setting 17 = 7 = /11I4[II144/////XXI11 Algorithm attains RT S O V /VITIXIV/A/T (TIXIIA(m/8) with prob. at least 116, where == [mx] (ann)((a-8)).aa -.)))).
5.1. Safety property
We show that S-OPS is safe with high probability.
The regret bound in Theorem 5.2 is in line with the one of OPS in the bounded violation setting, with an addi- tional 2 factor. Such a factor comes from the mismatch between loss estimators and the occupancy measure chosen by the OMD-like update. Notice that ti depends on the vio- lation gap min,e[m] (ar- - 33,, which represents how much the strictly feasible solution satisfies the constraints. Such a dependence is expected, since the better the strictly feasible solution (in terms of constraints satisfaction), the larger the exploration performed during the first episodes.
Theorem 5.1. Given a confidence 5 E (0, 1), Algorithm 3 safe with probability at least 1 56.
Intuitively, Theorem 5.1 follows from the way in which the randomization probability d is defined. Indeed, X relies on two crucial components: (i) a pessimistic estimate of the costs for state-action pairs, namely, the upper confidence bounds 9.,, + ε.. and (ii) a pessimistiic choice of transition probabilities, encoded by the upper occupancy bounds de- fined by the vector ūt Notice that the max4e[m] operator allows to be conservative with respect to all the constraints.
6. Guaranteeing constant violation
In this section, we provide an algorithm that attains con- stant cumulative positive violation. To achieve this goal, we only need that a strietly feasible policy exists (Assump- tion 2.4). Algorithm provides the pseudocode of Con- stant Violation Optimistic Policy Search (CV-OPS). The key idea of CV-OPS is to estimate, in a constant num- ber of episodes, a strictly feasible policy and its associ- ated violation, and then run S-OPS with such estimates.
5.2. Cumulative regret
Proving that S-OPS attains sublinear regret begets chal- lenges that, the best of our knowledge, have never been addressed before. Specifically, analyzing the estimates of the adversarial losses requires non-standard techniques in our setting, since the policy ne used by the algorithm and determining the feedback is not the one resulting from an OMD-like update, as it is obtained via a non standard ran- domization. Nevertheless, the particular shape of the prob-
Algorithm 4 needs access to two anytime no-regret algo- rithms, one for adversarial MDPs with bandit feedback
7

---

Learning Adversarial MDPs with Stochastic Hard Constraints
that learns an estimated strictly feasible policy and one for the full-feedhack setting on the simplex, which learns the most violated constraint. Specificallyy, CV-OPS employs an anytime regret minimizer for adversarial MDPs called the primal algorithm - attains, with probability at least 1 - Cgô, for all 5 E [T].9 E ((M), and for any sequence of loss functions the following regret bound Ei (q. 9) < C where Cº encompass constant terms. This kind of guarantees are attained by state-of-the-arr algorithms for adversarial MDPs (e.g.. (Jin et al., 2020)) after applying standard doubling trick (Latt timore & Szepesvári, 2020). Algorithm 4 also employs an anytime online linear optimizer- called the dual algo- rithm -hatt attains for all r E (7) E Am, and for any sequence of loss functions the following regret bound Ei= E. (dr o) S CRVT, where C2 encompasses con- stant terms. This bound can be easily obtained by an online gradient descent algorithm (Orabona, 2019).
show that Algorithm 4 estimates strictly feasible policy whose constraints margin is in [7, pl. as follows.
Lemma 6.2. Given any 5 E (0, 1), Algorithm 4 guarantees
p S min (a:; 9, q ) S p with prob. at least 1 28.
Finally, we provide the result in term of cumulative positive constraints violation attained by our algorithm.
Theorem 6.3. Given ō E (0,, 1). Algorithm 4 altains Vr S
OL//(C2 + LV In 1/ + C22 + L)+) with probability at least 1 - (Cp + 7)o.
Theorem 6.3 is proved by employing Lemma 6.1 to bound the episodes in the estimation phase and Lemma 6.2 to state that S-OPS with p. HO is safe with high probability.
6.2. Cumulative regret
We provide the theoretical guarantees attained by Algo- rithm 4 in terms of cumulative regret. To do so, we show that p is not too small. This is done in the following lemma.
At each episode & E [T], Algorithm 4 requests a policy and a distribution over the m constraints to AA and AA", respectively (Lines 2-3). Thus, the algorithm plays the pol- icy received by A and observes the usual bandit feedback for CMDPs (Line 4). Next, the loss functions for both the primal and the dual algorithm are built. Specifically, A² receives the violation attained by the policy Te where any constraint is weighted given oe (Line 5), while A receives the negative of the violation attained for all i E [m]] (Line 6). The estimation phase stops when the violation attained by the algorithm exceeds twice the regret bounds attained by both the primal and the dual algorithm plus the uncertainty on the estimation (Line 7). This condition is suitably cho- sen to ensure that the number of episodes are sufficient to estimate an approximation of T while still being constant. After the estimation, Algorithm 4 computes pessimistically the estimated Slater's parameter z as the average violation attained during the estimation phase minus quantity as- sociated with the uncertainty of the estimation (Line 11). Finally, CV-OPS computes the strictly feasible solution the uniform policy with respect to all the policies played in the estimation phase (Line 12) and runs S with 3; = a, P, for all E [m]] and n = 7o in input (Line 13).
Lemma 6.4. Given any 5 E (0, 1), Algorithm 4 guarantees P 2 p/2 with probability at least 1 - (CB + 2)6.
Finally, we state the regret attained by CV-OPS.
Theorem 6.5. Given any ô E (0. 1). with n = y =
V [L (1///// Algorithm 4 attains regret Ri S (TIXIIAlm/s) + [C + L +
D(OL*IXIVTATT
O + ))) with probability at least 1 - (Cp + 13)6, where we let = (mminpp.p")
As Theorem 6.3, Theorem 6.5 is proved by employing Lemma 6.1 to bound the episodes in the estimation phase. Then, the result follows from the regret guarantees of S OPS and Lemma 6.4 for 1/P < f/p. Differently from S-OPS, the bound of CV-OPS scales as the inverse of the Slater's ' parameter p. not as the (possibly smaller) margin of a generic strictly feasible policy. Thus, the bound of Algo- rithm is asymptotically smaller than the one of SOPPS.
6.3. Lower bound on the regret
6.1. Cumulative positive constraints violation
We conclude by showing that a dependency on the feasi- bility of the strictly feasible solution in the regret bound is unavoidable to guarantee violation of order of o(VT), which is the case of both the second and third setting.
First, we show that the stopping condition at Line 7 allows to run the estimation phase for no more than a constant number of episodes. This is done in the following lemma.
This is done by means of the following lower bound.
Lemma 6.1. Given any E (0, 1), the episodes that Al- gorithm 4 uses to compute p and 7o are < 1//0(3C +
Theorem 6.6. There exist two instances of CMDPs (with single state and one constraint) such that, if in the first instance an algorithm suffers from a violation V7 = o( (T) probability at least 1 - nō for any E (0, 1) and n > O. then, in the second instance, it must suffer from a regret Rr S2( VT) with probability 3/4 nō.
10L Inf 1/2 + 3C + L)a, with prob. at least 1 - (C + 2)o.
The bound could be reduced to i 1///3C + 10L In } + 3C + L)2 with access to a no-regret algorithm without the logarithmic dependence on T in the bound. Next, we
8

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Notice that this lower bound holds for any algorithm at- taining violation bound that is o(vT), thus, it is still applicable to settings where the violations are allowed to be much larger than the ones attained by Algorithm 3 and Algorithm
Learning Research, pp. 1854-1873. PMLR, 17-23 Jul 2022. URL.https:/prrcceedinn .ml........ p.resss// v162 #162/bernascon:22a. html.
Bura, A., HasanzadeZonuzy, A., Kalathil, D., Shakkottai, S., and Chamberland, J.-F. Dope: Doubly optimistic and pessimistic exploration for safe reinforcement learning. Advances in neural information processing systems, 35: 1047-1059, 2022.
Acknowledgments
This paper is supported by the Italian MIUR PRIN 2022 Project "Targeted Learning Dynamics: Computing Efficient and Fair Equilibria through No-Regret Algorithms", by the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEUU program within the PNRR-PE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainability, No. 101120237).
Cesa-Bianche N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
Chen, K., Cai, K., Huang, L., and Lui, J. C. Beyond the click-through rate: web link selection with multi-level feedback. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 3308-3314, 2018.
Ding, Y. and Lavaei, J. Provably efficient primal-dual rein- forcement learning for emdps with non-stationary objec- tives and constraints. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 37, pp. 7396-7406 2023.
Impact Statement
This paper presents thcoretical results and has the goal of advancing the field of Machine Learning. There are no potential societal consequences of our work which we feel must be highlighted here.
Efroni, Y., Mannor, S., and Pirotta, M. Exploration- exploitation in constrained mdps, 2020. URL https: / //aaxivvoog//aaall..a.a abs 22003.003300 02189.
References
Even-Dar, E., Kakade, S. M., and Mansour, Y. Online markov decision processes. Mathematics of Operations Research, 34(3):726-736 2009.
Altman, E. Constrained Markov Decision Processes. Chap- man and Hall, 1999.
Auer, P. Jaksch, T., and Ortner, R. Near-optimal re- gret bounds for reinforcement learning. In Koller, D., Schuurmans, D., Bengio, Y., and Bottou, L. (eds.), Advances in Neural Information Pro- cessing Systems, volume 21. Curran Associates, Inc., 2008. URL https: / /ttp///pccceegg...///e/./. neurips.com /ctppp///c/pppee0/00/////e/// 016222ccb33333550000000033888883 pdf.
Guo, H. Liu, X., Wei, H. and Ying, L. Online convex opti- mization with hard constraints: Towards the best of two worlds and beyond. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 36426-36439, Curran Associates, Inc., 2022.
He, Y., Chen, X., Wu, D., Pan, J., Tan, Q. Yu, C., Xu, J., and Zhu, X. A unified solution to constrained bidding in online display advertising. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2993-3001, 2021.
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.
Isele, D., Nakhaei, A., and Fujimura, K. Safe reinforcement learning on autonomous vehicles. In 2018 IEEE/RSJ In- ternational Conference on Intelligent Robots and Systems (IROS), pp. 1-6. IEEE, 2018
Bai, Q. Aggarwal, V., and Gattami, A. Provably sample- efficient model-free algorithm for mdps with peak con- straints. Journal of Machine Learning Research, 24(60): 1-25, 2023.
Jin, C., Jin, T., Luo, H., Sra. S., and Yu, T. Learning adver- sarial Markov decision processes with bandit feedback and unknown transition. In III. H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Mu- chine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4860 4869. PMLR, 13-18 Jul 2020. URL https: http::///o/ooeeeeeeeeee mlr. press/ v1 v119/gin22 html.
Bernasconi, M., Cacciamani, F., Castiglioni, M., March- esi, A., Gatti, N., and Trovò, F. Safe learning in tree- form sequential decision making: Handling hard and soft constraints. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Pro- ceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cam- bridge University Press, 2020. ISBN 9781 108486828. URL https:/ //tps/////ooo.o//// google it/ttokssissi bYdXZAEACAAJ.
Rosenberg, A. and Mansour, Y. Online convex optimization in adversarial Markov decision processes. In Chaud- huri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learn- ing, volume 97 of Proceedings of Machine Learning Research, pp. 5478-5486. PMLR, 09-15 Jun 2019b. URL ptattp::/pproceedingge. .ww..mlrr.......... mlr.press/v97. rosenberg1 html.
Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. Learning policies with zero or bounded constraint viola- tion for constrained mdps. Advances in Neural Informa- tion Processing Systems, 14:17183-17193 2021.
Shi, M., Liang, Y., and Shroff, N. A near-optimal algorithm for safe reinforcement learning under instantancous hard constraints. arXiv preprint arXiv:2302.04335. 2023.
Müller, A., Alatur, P., Cevher, V., Ramponi, G., and Hc, N. Truly no-regret learning in constrained mdps. In Forty-first International Conference on Machine Learn- ing, 2024.
Singh, A., Halpern, Y., Thain, N., Christakopoulou, K., Chi, E., Chen, J., and Beutel, A. Building healthy recom- mendation sequences for everyone: A safe reinforcement learning approach. In Proceedings of the FAccTRec Work- shop, Online, pp. 26-27, 2020.
Neu, G. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
Neu, G., Antos, A., György, A., and Szepesvári, C. On- line markov decision processes under bandit feedback. Advances in Neural Information Processing Systems, 23, 2010.
Stradi, F. E., Germano, Genalti, G., Castiglioni, M.. Marchesi, A., and Gatti, N. Online learning in CMDPs: Handling stochastic and adversarial constraints. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Pro- ceedings of the 41st International Conference on Ma- chine Leurning, volume 235 of Proceedings of Ma- chine Learning Research, pp. 46692-46721, PMLR, 21- 27 Jul 2024a. URL https: http://oceeeddeec ngs. mmlr. html.
Orabona, F. A modern introduction to online learning. CoRR, abs/1912.13213,, 2019. URL http://arxixs org/abs/ /11///bb//1911..111..
Pacchiano, A., Ghavamzadeh, M., Bartlett, P., and Jiang, H. Stochastic bandits with linear constraints. In Interna- tional conference on artificial intelligence and statistics, pp. 2835. PMLR, 2021.
press/v235/strasse
Stradi, F. E., Lunghi, A., Castiglioni, M., Marchesi, A., and Gatti, N. Learning constrained markov decision processes with non-stationary rewards and constraints, 2024b. URL https: : http://xx...gg///aaae///
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Qiu, S., Wei, X., Yang, Z., Ye, J., and Wang, Z. Up- per confidence primal-dual reinforcement learning for emdp with adversarial loss. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15277-15287. Curran Asso- ciates, Inc., 2020. URL https: / /tettps:/pproceedings. cc / pttipssscc//pper//22//1/111 ae 4e922666770665551111266666633330 pdf.
Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Optimal strong regret and violation in constrained mdps via policy optimization. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025, 2025.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018
Wei, H., Ghosh, A., Shroff, N., Ying. L., and Zhou, X. Prov- ably efficient model-free algorithms for non-stationary emdps. In International Conference Artificial Intelli- gence and Statistics, pp. 6527-6570, PMLR, 2023.
Rosenberg, A. and Mansour, Y. Online stochastic shortest path with bandit feedback and unknown transition function. In Wallach, H., Larochelle, H., Beygelzimer, A., d Alché-Buc, F., Fox, E., and Gamett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019a. URL https: //pppcceeedngs... neurips.cm httpppp..cc/appee///1///eee 008226635cclc2250778388888 pdf.
Wei, X., Yu, H., and Neely, M. Online learning in weakly coupled markov decision processes: A convergence time study. Proc. ACM Meas. Anal. Comput. Syst., 2(1), apr 2018. doi: 10. 145/3119/93 URL https: /ooi. org / 10. 11 3194515
Wen, L., Duan, J., Li, S. E., Xu, S., and Peng, H. Safe reinforcement learning for autonomous vehicles through
10

---

Learning Adversarial MDPs with Stochastic Hard Constraints
parallel constrained policy optimization. In 2020 IEEE 23rd International Conference on Intelligent Transporta- tion Systems (ITSC), pp. 1-7. IEEE, 2020.
Wu, D., Chen, X., Yang. X., Wang, H., Tan, Q., Zhang. X., Xu, J., and Gai, K. Budget constrained bidding by model- free reinforcement learning in display advertising. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 1443- 1451, 2018.
Zheng, L. and Ratifff, L. Constrained upper confidence rein- forcement learning. In Bayen, A. M., Jadbabaie, A., Pap- pas, G., Parrilo, P. A., Recht, B., Tomlin, C., and Zeilinger, M. (eds.), Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 Proceedings of Machine Learning Research, pp. 620-629. PMLR, 10- 11 Jun 2020. URL https: / ptpppeeeeedngg.... , mlr. press/v1200 20 20/zhng22a html.

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Appendix
The appendix is organized as follows:
In Appendix A, we provide the complete discussion on related works.
In Appendix B, we provide the omitted proofs related to the analysis of the clean event.
In Appendix C, we provide the omitted proofs related to the performances attained by Algorithm 2, namely, the one which guarantees sublinear violation.
In Appendix D, we provide the omitted proofs related to the performances attained by Algorithm 3, namely, the one which guarantees the safety property.
In Appendix E, we provide the omitted proofs related to the performances attained by Algorithm 4, namely, the one which guarantees constant violation.
In Appendix F, we provide the lower bound associated to both the second and the third setting.
In Appendix G, we provide useful lemmas from existing works.
A. Related Works
Online learning (Cesa-Bianchi & Lugosi, 2006; Orabona, 2019) in MDPs has received growing attention over the last years (see, e.g., (Auer et al., 2008: Even-Dar et al., 2009; Neu et al., 2010)). Two types of feedback are usually investigated: full feedback, with the entire loss function being observed by the leaner, and bandit feedback, where the learner only observes losses of chosen actions. Azar et al. (2017) study learning in episodic MDPs with unknown transitions and stochastic losses under bandit feedback, achieving (VVT) regret, matching the lower bound for these MDPs. Rosenberg & Mansour (2019b) study learning under full feedback in episodic MDPs with adversarial losses and unknown transitions, achieving (VVT) regret. The same setting is studied by Rosenberg & Mansour (2019)) under bandit feedback, obtaining a suboptimal O(T3/1) regret. Jin et al. (2020) provide an algorithm with an optimal Ö ((VT) regret, in the same setting.
Online learning in CMDPs has generally been studied with stochastic losses and constraints. Zheng & Ratliff (2020) deal with fully-stochastic episodic CMDPs, assuming known transitions and bandit feedback. The regret of their algorithm is OTT3/1), while its cumulative constraints violation is guaranteed to be below threshold with a given probability. Bai et al. (2023) provide the first algorithm that achieves sublinear regret with unknown transitions, assuming that the rewards are deterministic and the constraints are stochastic with particular structure. Efroni al. (2020) propose two approaches to deal trade-off in episodic CMDPs. The first one resorts to linear programming formulation of CMDPs and obtains sublinear regret and cumulative positive constraints violation. The second one relies on a primal-dua formulation of the problem and guarantees sublinear regret and cumulative (positive/negative) constraints violation, when transitions, losses, and constraints are unknown and stochastic, under bandit feedhack. Liu et al. (2021); Müller et al. (2024); Stradi et al. (2025) study stochastic hard constraints; however, the authors only focus on stochastic losses. Bura et al. (2022) focus on our second scenario and develop a pessimist algorithm for the stochastic setting only. In this work, the strictly safe policy is played for certain amount of time, after which a good estimate on constraints costs and transitions is available. This allows the pessimistic set to be large enough to to be used. We underline that, optimizing over the pessimistic decision space cannot be done in our setting, since adversarial no-regret algorithms do not work in increasing decision spaces. Recently, Shi et al. (2023) study stochastic hard constraints on both states and actions. As concerns adversarial settings, Wei et al. 2); Qiu et al. (2020); Stradi et al. (2024a) address CMDPs with adversarial losses, but they only provide guarantees in terms of soft constraints. Moreover, Wei et al. (2023); Ding & Lavaei (2023); Stradi et al. (2024b) consider non-stationary losses/constraints with bounded variation. Their results do not apply to general adversarial losses.
with the iitoorattionxxplotttttto
Hard constraints have also been studied in online convex optimization (Guo et al., 2022), and in stochastic settings with simpler structure (Chen et al., 2018; Pacchiano et al., 2021; Bernasconi et al., 2022). Our results are much more general than those, we jointly consider adversarial losses, bandit feedback, and an MDP structure.
B. Omitted proofs for the clean event
In this section, we report the omitted proof related to the clean event. We start stating the following preliminary result.
12

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Lemma B.1. Given any fax E [m], 1 (T) and (x, a) X x A, it holds, with probability at least 6:
()) (x) (,
ln(2/8) where (xx = (N, and (2, a) the true mean value of the distribution.
Proof. Focus on specifics E [m]. t [2] and (x, E X A. By Hoeftding's inequality and noticing that constraints
values are bounded in [0, 1]. it holds that:
2c
P - a)( 2 a)(
2eep
(2, a)
Setting 8 = exx
(-
2+ (-Ne(z.a) (e,aa))
and solving find proper value of concludes the proof.
Now we generalize the previous result in order to hold for every E [m]] t [T] and (2,a) E X x A at the same time.
Lemma B.2. Given a confidence 8 (0,1). 1). with probability ar least 6, for every i [m]. episode [T].
and pair (Ir,a) X x A, it holds [r, a) (,( ()), where let the confidence bound (x(x, a)
Proof. From Lemma G.I, given 8' e (0, 1), we have for any E [m]. t [2] and (z, a) X A:
|onito.)) ()) al( ax) s a)( 2 21-8
P
Now, we are interested in the intersection of all the events, namely,
n {panle,a) - 2,(2,a) s sllosat)
m,a,m,t
Thus, we have:
P
n
s -,,(())))))(0,0))
- 9,(2,
z,a,m,t
- - P
( -x(a, s (e(
u.a.m.t
>
Σ
{ ( -D((x,)) s {G((z,
(3)
2.a.m,
1 - X|| mT88
where Inequality (3) holds by Union Bound. Noticing that 9t, (2, a) < 1, substituting 8' with 8 = 8'/1X||A in G(x,, a)
with an additional Union Bound over the possible values of Ne(a, a), and thus obtaining (x a), concludes the proof.
C. Omitted proofs for sublinear violation
In this section we report the omitted proofs of the theoretical results for Algorithm
13

---

Learning Adversarial MDPs with Stochastic Hard Constraints
C.1. Feasibility
We start by showing that Program (2) admits feasible solution with arbitrarily large probability.
Lemma 4.1. Given confidence ā E (0, 1), Algorithm 2 ensures that PROI( G,, Pt) is feasible every episode E [ with probability at least 1 56.
Proof. To prove the lemma we show that under the event (6), which holds the probability at least 1 56, Program (2) admits feasible solution. Precisely, under the event (6), the true transition function P belongs to Pe at each episode. Moreover, under the event (6), we have, for any feasible solution gD the offline optimization problem, for any E [7],
(G.- of = T o = a,
where the first inequality holds by the definition of the event. The previous inequality shows that if q satisfies the constraints with respect to the true mean constraint matrix, satisfies also the optimistic constraints. Thus, the feasible solutions the offline problem are all available at every episode. Noticing that the clean event defined as the intersection between g (6) and (5) (5) concludes the proof.
C.2. Violations
We proceed bounding the cumulative positive violation as follows.
Theorem 4.2. Given å E (0, 1), Algorithm 2 attains VT S O (LIXIV A (FIx]AA()))) with prob. at least 1 - 86.
Proof. The key point of the problem is to relate the constraints satisfaction with the convergence rate of both the confidence bound on the constraints and the transitions.
First, we notice that under the clean event (5),, all the following reasoning hold for every constraint i [m]. Thus, we focus on the bound of single constraint violation problem defined as follows:
Vr
q: a
By Lemma 4.1, under the clean event the (G), the convex program is feasible and it holds:
g - 25. = 9i - &
Thus, multiplying for the estimated occupancy measure and by construction of the convex program we obtain:
- 2 qe I (ā--1 E1-1) qe aa
Rearranging the equation, it holds:
g J क S a + 2
Now, in order to obtain the instantaneous violation definition proceed follows,
g a + 4
h 4t S a 2T
from which we obtain:
q q: a < g (gt @ -E,__1 -.
< lg loo 11 - क la 2
where the last step holds by the Hölder inequality. Notice that, since the RHS of the previous inequality is greater than zero, it holds,
T qc - al+ & 11.. adlli + 2
which leads to V/= S ΣT l1q. -ul1 +2 + q. where the first part of the equation refers to the estimate of the transitions while the second one to the estimate the constraints. We will bound the two terms separately.
14

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Bound on Σi= ll gelli- The term of interest encodes the distance between the estimated occupancy measure and the real one chosen by the algorithm. Thus, it depends the estimation of the true transition functions. To bound the quantity of interest, we proceed as follows:
Σ
1
2:
1111
(T) go (x)
TXXILAI)
S 0
LIXI A In
(4)
where Inequality (4) holds since, by Lemma G.2, under the clean event, with probability at least - 25, we have 21=1 En,a @r a) (a, a))l s (XXXV/ | In [2IXITA) when q. E A(P.). Please notice that the condition Ts E A(P)) is verified since the constrained space defined by Program (2) is contained in A(P.).
Bound on Et=1 17- This term encodes the estimation of the constraints functions obtained following the estimated occupancy measure. Nevertheless, since the confidence bounds converge only for the paths traversed by the learner, is necessary to relate & to the real occupancy measure chosen by the algorithm. To do so, we notice that by Hölder incquality and since (x( a) S 1, holds:
T 0
T
T
Σ 1=1
<
St-19
19t
+
Σ
1 - -c
t=1
t=1
5t-19t +
Σ
| 10
-0ll22
1=1
t=1
T
1
qell1
The second term of the inequality is bounded by the previous analysis, while for the first term proceed follows:
T
T
1-19
Σ &
1=1
t=1
2,0
1 8 L 27
(Z,
L 1=1 2,
(5)
1=1
4
|| A/m
1,(2,a] + L +1 2T
1
5
max (1 a))
T T| |||m
S 3 4 hn
v NT((, L 21 In
(6)
8
aa
S 6
4|
LL 2T 5'
where Inequality (5) follows from Azuma inequality and noticing that E (1, a)q((z, a) < L (with probability Ei t < 2VT + 5 3vT and Inequality (7) follows from Cauchy-Schwarz
least 1 0), Inequality (6) holds since
inequality and noticing that / Emm, Nr(2, S LT.
We combine the previous bounds as follows:
VT < Σ
Ige Tell l
+
c 4
15

---

Learning Adversarial MDPs with Stochastic Hard Constraints
|1 ))
0
1xx|i1
||
8
The results holds with probability at least at least 86 by union bound over the clean event, Lemma G.2 and the Azuma-Hoeflding inequality. This concludes the proof.
C.3. Regret
In this section, we prove the regret bound of Algorithm Precisely, the bound follows from noticing that, under the clean event, the optimal safe solution included the decision space for every episode E [T].
Theorem 4.3. Given 5 (0,1), by setting " 7 / Algorithm 2 attains Ri S
O (4XI////7TI(XXIIA/// with prob. least 105.
Proof. We first rewrite the regret definition as follows:
T
T 4 q
Ry
Σ
-
-4
4
1=1
1=1
T
T
T
T
Σ t=1
4. (gt 3)) >
E
(4:
--")
+
Σ (4
2g T q
+ > (2 T q'
1=1
Precisely, the first term encompasses the distance between the true transitions and the estimated ones, the second concerns the optimization performed by online mirror descent and the last ones encompass the bias of the estimators.
Bound on 1. We start bounding the first term, namely, the cumulative distance between the estimated occupancy measure and the real one, as follows:
(g: qr)
2.6
Σ
where the Inequality (8) holds by Hölder inequality noticing that || 1 for all t [T]. Then, noticing that the projection of Algorithm 2 is performed over subset of A(P)) and employing Lemma G.2, obtain:
(TIXIAA)) ))
Oso LXXII
A|T
(9)
8
with probability at least 26, under the clean event.
Bound on 2 To bound the second term, we underline that, under the clean event EG,A the estimated safe occupancy belongs (PP.) and the optimal safe solution q" is included in the constrained decision space for each t [T]. Moreover we notice that, for each E [T', the constrained space is convex and linear, by construction of Program (2). Thus, following the standard analysis online mirror descent (Orabona, 2019) and from Lemma G.6, we have, under the clean event:
Lln (1X|2 [AD)
Σ ()xx,))
2,2,0
16

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Thus, to bound the biased estimator, we notice that (z (x, a)² I (((a.a)
al(2.a)t7 (1(2,0) 0) I El a). We then apply
Lemma G.3 with ar(z,a) a) 2y and obtain Ei, (z (Z) a)² s that, under the clean event, gr (2r, a) S ue (zt, a), obtaining, with probability least 1 6:
Σ Lt, ue(a.a)
q((ea) (12 a) Lim +t Finally, notice
L In (II)
ILLn(L/0)
+ X
27
Setting
we obtain:
TX
SSO (
[XII (IIXIIIII
(10)
with probability at least - 8, under the clean event.
Bound on 3- and setting 7
The third term follows from Lemma G.5, from which, under the clean event, with probability at least 1
35
[n we obtain:
TXX
TIXIIA
I o LIXIy
LIXIVIAIT
|
(11)
Bound on 4
We bound the fourth term employing Corollary G.4 and obtaining,
T
l 1
Σ9 gz
(le(z,a) (((2,a))
1,a,a
g' a) In [IIIA
(1(2z, a) ue(x,, a)
Σ
(1,
- 1
27
Ye (x( a) ux( a)
L In [I]II]
Σ (z,,))l((z,)
2n
2,0.0
Noticing that, under the clean event, ge (x, a) S ut (z, a) and setting y v least. 1 5:
L (n(()) X IA 18) we obtain, with probability at T|X[|A|
TIXIIA|)
① 0 L I
(12)
Final result. Finally, combining Equation (9), Equation (10), Equation (11) and Equation (12) and applying union bound, we obtain, with probability at least - 108,
Pr 5 (LIXIN A (TX]|AA) ))
D. Omitted proofs when Condition 2.5 holds
In this section we report the omitted proofs of the theoretical results for Algorithm
D.1. Safety
We start by showing that Algorithm 3 safe with high probability.
17

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Theorem 5.1. Given a confidence ò E (0, Algorithm is safe with probability least 56.
Proof. We show that, under event ( the non-Markovian policy defined by the probability Ae satisfies the constraints. Intuitively, the result follows from the construction of the convex combination parameter A Indeed. X is built using pessimist estimated of the constraints cost, namely, ft., + Le. Moreover, the upper occupancy bound ūn introduces pessimism in the choice of the transition function. Finally, the maXie[m] operator allows to be conservative for all the constraints.
We split the analysis in the two possible cases defined by X namely, d = 0 and X E (0, 1). Please notice that X < 1, by construction.
Analysis when A =0 When X 0, it holds, by construction, that Vi E [m] : (0t-1, + Ec-1) Th S 0s. Thus, under the event g., (6), holds, vi [m]]
0 2 (ūt- + (1-1) 0t
2 (#--1 1, + 5--1) 1) T 9
(13)
17-1, + ((-1) TT:
2 g. q:
(14)
where Inequality (13) holds by definition of üe and Inequality (14) by the pessimistic definition of the constraints.
Analysis when d E (0.1). We focus on a single constraint i E [m], then we generalize the analysis for the entire set of constraints. First we notice that the constraints cost, for single constraint i [m]. attained by the non-Markovian policy Te, is equal to 11 dº + (1 \1-1) q _ Thus, it holds by definition of the known strictly feasible x²,
Ae-19, de + (1 \x q p. Ac-18; + (1 Ac-1) P.a..
(15)
Then, consider both the cases when L (ō1-1, + { in (first case) and L (0i-1, + E6-1) un (second case). If the two quantities are equivalent, the proof still holds breaking the ties arbitrarily.
First case. It holds that:
X--18 + (1 \x-1) R..
S AB-1B:+ + (1 X
(16)
I,
L B, (B: L) + L
0x I
(B: L) + L
3. - L
an
where Inequality (16) holds by definition of the constraints.
Second case. It holds that:
1 1i+(11 1--1) 11 P.a.
$ 1
B, + (1 - \ (0:- 1,0 + 1 T p.a.
(17)
A- Bi + (1 - x1-1) (1 + Er-1) T +r
(18)
~1133 x-1 (9t-1, 1,1 + {(-1) T u, + (gi-1,, + E(-1) 0
1 (0-11 + 1--1
T ūt) + (ā.-1, 1, + {--1 1) T ūz
(0-1, + {-1) 01 - a:
(B: @0-1, + 1(-1 úe) + (ā--1, + Ec-1) ai
(0.-1, + 1 Q2 - B,
04 (0-1, + 11)
T ū1
(B: (0 + Em-1) T me) (0--15 + Eo-1) it
B, 0--1 + 1-11
0; 00-1, + E--1
Th + 11 + {t-1)² Tt
18

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Ol
where Inequality (17) holds by the definition of the event and Inequality (18) holds by the definition of Te.
To conclude the proof, underline that d is chosen taking the maximum the constraints, which implies that the more conservative X (the one which takes the combination nearer to the strictly feasible solution) is chosen. Thus, all the constraints are satisfied.
D.2. Regret
We start by the statement of the following Lemma, which is generalization of the results from (Jin al., 2020). Intuitively, the following result states that the distance between the estimated non-safe occupancy measure q and the real one reduces as the number of episodes increases, paying policy ne (sce Algorithm 3). policy ūt + qe is played with probability A--1-
A factor. This is reasonable since, from the update of the non-Markovian
Lemma D.I. Under the clean event, with probability at least 1 28, for any collection of transition functions 2 such that P E Pu and for any collection of } used to select policy T(+1, have, for all
Σ
T
Σ
1 (F, - g P. (x, so =0
A
TIXIAA
5
mEA,aEA
Proof. We will refer as of to gf and as Th" to S Moreover, we define:
Rt,
P (z a) In TXX|A11
In TIXIIA
max (1, (x,
max (1, (2, a))
Now following standard analysis by Lemma G.2 from (Jin al., 2020), we have that,
T
Σ
A-1)
Σ
$ Pt. PP a) P a)
P.
zEX,EEA
Σ
Σ de (2m+1 Tm am)q ( pite (2m, am) + |X|
Σ Σ (1 Ac-1)-
OSmeneL t.wm
Eo (#m+1 Dm. am) of li (Ims am) & (2hae1 2hh, ah)) up (1'h ah Im+z),
where Wm (I' amyy 1m.
Bound on the first term.
To bound the first term we notice that, by definition of q R holds:
Σ Σ de 1e-1) (Fm-1 [mm, a. 0g P (Im,, am)
Osm<ke 1,8m
Σ Σ
( am) (a ( am) - de- P.t0
Po (Im, Um)
osm ke L N.W
Σ Σ
El (2 E amd P
Pise (Ims am)
oSmekeLL N.W
TXIA
0 LIXIN
where the last step holds following Lemma G.2 from (Jin et al., 2020).
19

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Bound the second term. constants),
Following Lemma G.2 from (Jin et al., 2020), the second term is bounded by (ignoring
TIXIA
P (Tm+1 I'm am) In
Σ
Σ
(1 -
8
max {1, No (Im am)
osmcchl 1,0m
P (ahh11 4/2 o/n In
T T
q pi (Ims am)
R. (2//1 dh xm+1)
max {1, No (2/, a/))
Pe (rm: amy) In TIXIIA
3 (1- A (1-
E
Σ
max {1, N₂ (Im, am)}
0S SEmeheLi 1,WW,
TA g p.t (z/2 a/2) In
Σ
max {1, No (2/2 (,,)) Σ (1-
5
0smch<L f.Wm.ub
The last two terms are bounded logarithmically in T, employing the definition of P. and following Lemma G.2 from (Jin et al., 2020), while, similarly, the first term is bounded by:
(1 - 11-1)1 (Im, am) max {1, (Z:m: am))
(1 de- P (1/) d/p) max (1, N, (2//2) 0/,,)
Σ
Im++l
Σ amm
|
Σ
OSmcheL
which is upper bounded by:
(Imm aey) max {1, No (Ims am)
le (1/ o/,) max (1, (a% a/,}
Xm+al
Σ
|
Σ
O.m
Employing the same argument as Lemma G.2 from (Jin et al., 2020) shows that the previous term is bounded logarithmically in T and concludes the proof.
We are now ready to prove the regret bound attained by Algorithm 3. Theorem 5.2. Given 5 E 10, by setting = 7 /LLILLXXIAA/////IIIIIA, Algoritium 3 attains Rr <
O v W/A/T (T1x11Alm/6) with prob. at least 1 118, where Ti == maxig[m] (a:
Proof. We start decomposing the R= = =T Cf (g: 9²) definition as:
T
T
[ g Po +
eT
Phiste - Pr.)e) +
9"
T
T
T
la -
q
(7 -
where P; is the transition chosen by the algorithm at episode 4. Precisely, the first term encompasses the estimation of the transition functions, the second term concerns the optimization performed by the algorithm, the third term encompasses the regret accumulated by performing the convex combination of policies and the last two terms concern the bias of the optimistic estimators.
We proceed bounding the five terms separately.
20

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Bound on !
We bound the first term as follows:
Σ 4 (qt -0-- -
le a) (9e(x, - (1,
2,a
where the last inequality holds by Hölder inequality noticing that |1Co|oo I for all E [T]. Then we can employ Lemmas G.2, since my is the policy that guides the exploration and P. E Pt, obtaining:
o LIXIY
T|XIAA|
A|
(19)
with probability at least - 26, under the clean event.
Bound on 2 The second term bounded similarly to the second part of Theorem 4.3. Precisely, we notice that under the clean event (G.A (5), the optimal safe solution q² is included in the constrained decision space for each E [7]. Moreover notice that, for each [T]. the constrained space is convex and linear, by construction of the convex program. Thus, following the standard analysis of online mirror descent (Orabona, 2019) and from Lemma G.6, have, under the clean event:
L In (IX191A) + n Σ P.m (z, (z, (2,))
G,,a
Guarantecing the safety property makes bounding the biased estimator more complex with respect to Theorem 4.3. Thus, L-aq and by definition of ne, proceed as follows:
noticing that d maxie[m]
L
7 Σ Pt (z, (2)
11 Σ (1
max rE(m]
ai
B
(
10-19 Pa (x, -
max m
Or Bi
t,z,a
I
(x,
max
1
VE m
ai Bg
t,z,a
The previous result is intuitive. Paying an additional max;e[m] policy that guides the exploration, namely, ne- Thus, following the same steps as Theorem 4.3 we obtain, with probability 1 8, under the clean event:
L - f factor allows to relate the loss estimator &g with the
Lln (IX19AA)
1 LnLn/()))
n//X|AA
max iE ml
max (E(m]
0g Bg
Bg
2
Setting 7)
L ln(L|X AI/8) A
we obtain:
[XPII]]
max iElm
L I|
(20)
a; Bg
with probability at least
5, under the clean event.
21

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Bound on 4 In the following, we show how rewrite the third term so that the dependence the convex combination parameter explicit. Intuitively, the third term is the regret payed to guarantee the safety property. Thus, we rewrite the third term follows:
T
q _
-9
Σ
l
11-11 Pox +11- - Ar-1) f. -9 g
1=1
T
X X-1 0-16/gP00 -:
1=1
L
Xt-1
t=1
where we used that ef P < L for any & E [T]. Thus, we proceed bounding E Az-1-
We focus on a single episode E [T'. in which we assume without loss of generality that the i-th constraint the hardest to satisfy.
Precisely,
A min {(rr, &t) Uc+1, L)- a4
min (@t.. + {t) 11141 1}- - 3r
(it, + E,) TT++1= -
( + {t) ii+11 - -Ba
( {t) Me+1 Ozi
(21)
04- - Bi
(+. () TT+1 + 22, uc+1 Ccs
0i Bi
G0, 6) T++11 (īt,i
(.)(((++1))))) T(+1) -
Me+1 Ox
a; - Bi
(Tr 6.) g0+1
To+1 D1. (ū+41 ( + 2cT 2
ūz+1 aj
0₁- Bi
3., (u+41 - (0+1) + 25,1 ut+1
(22)
04 84-8 Bi
g..1( (ū++1 - p:tm)))) ) + TT
11 P: 9 P+t1 + 26, De+1
04 3--B 33
@ 0 q P + 11 P88 P ||I + 2ET 8.+1
a; B,
1يس+1 - q p 111 + 119 18 - - 111 + +2, 24-1
L(1 Ae)
p || + L(1 - A.)lg - g 111 + 2L(1 A
(23)
min {(a, Bi), (a, 3,)23
where Inequality (21) holds since, for the hardest constraint, when X 0, (āt. (.) u441 TT)TT > 0g, Inequality (22) holds since, under the clean event, (Ør.: - & TT 0++1 S and Inequality (23) holds since X < L-a, Intuitively, Inequality (23) shows that, to guarantee the safety property, Algorithm 3 has to pay a factor proportional to the pessimism introduced on the transition and cost functions, plus the constraints satisfaction gap of the strictly feasible solution given as input to the algorithm.
We need to generalize the result summing over f, taking into account that the hardest constraints may vary. Thus, we bound
22

---

Learning Adversarial MDPs with Stochastic Hard Constraints
the summation follows,
2L
A-1 max re[m]
min {(a; - Be), (a; - -3,)
Σ (1- (1 - P 1| + 11 -9-
52_1 U+
+
The first two terms of the equation are bounded applying Lemma D.I, which holds with probability at least 26, under the clean event, while, to bound Σ (1 Xx-1)51-1 Uhe proceed follows:
T 11 11-A-1166 14 =
T
T Σ 1=1
-
Σ (1 (1- (1-
Xx-1))t-1 (Th q (.a )
where the second term is bounded employing Hölder inequality and Lemma D.I. Next, we focus on the first term, proceeding as follows.
Σ 11 - (1-
19 P.ã.
5t-19t 91
(24)
Σ (t-1(,,a))((,, / 27
(25)
1=1 3,a
T
4lm
max(1, N₁ (z, 1e(x, + 2 2
8
T|X A|m
2T 2T 1
S 6
XII Σ
(z + L
(26)
5
5
2,a
1
6
IA
+
2T In L
5
where Inequality (24) follows from the definition of Ne. Inequality (25) follows from Azuma-Hoeffding incquality and Inequality (26) holds since Ei J 2VT + 1 < 3vT and Cauchy- -eehwar- inequality.
Thus, we obtain,
1 A|T [1A
max iE|m]
(27)
min ((a: BB), (a: 3,)2]
with probability at least 36, under the clean event.
Bound on 4 We first notice that presents additional challenge with respect to the bounded violation case. Indeed, since म. the policy that drives the exploration, &s cannot be directly bounded employing results from the unconstrained adversarial MDPs literature. First, we rewrite the fourth term as follows,
T
Σ
4 21)
P... Σ
(E
Eo)
9 PE
((4
Σ t=1
P....
where [.[:] is the expectation given the filtration up time t. To bound the first term we employ the Ezuma-Hoeffding inequality noticing that, the martingale difference sequence is bounded by:
L
T P.. < max
2
T
Ac-1)g Pa...
m
B,
23

---

Learning Adversarial MDPs with Stochastic Hard Constraints
L
T
de- 10 P(.r))
max
Bg
L
max
m
Bg
L
max m
0% B, $ L.
where the first inequality holds since A S Ap. Thus, the first term is bounded by ma | LV 22 J. bound the second term, we employ the definition of n. and the upper-bound to λ proceeding follows:
To
4 Belil) gfr.3A.
Σ Riit (x, ( (z,a)),(axaa (1
E, [1, u1(2, a) +7
t,2,0
((
Σ 6,0,0
Piik (I, ( (x))
(1- +7
az(I,a)+
(x, ())((2 (1- (0(
< max :[|m]
Σ (1- 2 11-
(z, R
Ri.tt
Oii 3i
u1 a) -
1,r,a
T,
q P. (1,0))(( (1 20(2,a))
4)( +7) (1)
S max :E|m]
ai3 - 3
L
g Peitee (x,a) (2,
(uo(z, ax( +7)
sE/m]
042 B
Ue (z, a) +7
T
L
}
0
max iE/m]
X | B
+ max rE[m
a4 B,
where the last steps holds by Lemma G.2. Thus, combining the previous equations, we have, with probability at least - 35, under the clean event:
1
TIXIAA|
O
max ie[m]
I
(28)
B
8
Bound on 5 The last term is bounded in Theorem 4.3. Thus, setting
L /
obtain, with probability
TX A
at least 1 - 6, under the clean event:
3 0 I |XIAATI
T
(29)
Final result Finally, we combine the bounds on 1. ②, 3 4 and ② Applying union bound, we obtain, with probability least 1 116,
1 min ((a: 3.), (a; - 8,)
||
R
max iElm)
12p1// |A|T
8
which concludes the proof.
E. Omitted proofs for constant violation
In this section, we show how is possible relax Condition 2.5 and still achieving constant cumulative positive violation.
24

---

Learning Adversarial MDPs with Stochastic Hard Constraints
E.1. Slater's parameter estimation
We start by showing that the number of episodes necessary to Algorithm 4 estimate the Slater's parameter are upper bounded by constant term. This is done by means of the following lemma.
Lemma 6.1. Given any E (0, 1), the episodes that Algorithm 4 uses compute and @o are i s 1/0 + 10L In 1 + In
3C'2 + Ly², with prob. at least 1 (Cpp 2)
Proof. By the no-regret property of Algorithm AP, it holds:
Σ
Ve (gi,11: -90) ( sCDViin(),
ml]
with probability at least - CpO.
Thus, applying the Azuma inequality, we get:
t
,0, - -a:L)) S CCRvEll(
L 2f
01, a1/L) dp
1=1 [m]
[=1 (E(m)
CRitil(()) L
2f
v1 3i)
iE(mi
< <Ci/lll( + L 2F -t min (as rE(m)
32)
=C\vTIn()) L 27 Tp,
with probability (CP, + 1)6, by Union Bound. Similarly, applying the Azuma inequality, it holds:
aa//)) S C. C (l)(( + 21 25 1 Ep.
EE (m)
k=1
with probability at least (C$ + 2)5.
By the no-regret property of Algorithm AP, it holds:
Σ
Σ di
(x), ax) -
It. (I) ax) au
SCRV
sc/m]
where 1" arg maxie(m)
Ei k= (o0, -
from which we obtain, with probability at least 1 - (C$ +
Σ (1,((z, aas sch 2L 2F CRVE-ip tp.
max E [m]
By the stopping condition of Algorithm 4, it holds max ml Σt= Ek
(gt, (2 (x))at) a//L) 2 20% vtl((t) +
/ 2t 2n 1/2 + 2C Vi, which implies:
2-14-1
ΣΣ
(g,, ax) aa/L) 20 lnn(t 1) + 7L 2F 11m + +02 V
1E mm)
1=1
S 20 Vil((t) + V
2F 8
+ +2C
25

---

Learning Adversarial MDPs with Stochastic Hard Constraints
and
max ΣE
- -2 /iln((( 8L, 2ł 8 20
-0//1))
Thus, we get the following inequality:
2t 1
-2C2// - 8L 2f 20 - <CIVEln() + 2L
8 + CCRVE ip.
Hence,
10330% /Fl((t) VFl((()
10L, 2F 8
+ +3C2VE+1
I
< 30 -10
2
g
f3/4
+ 3C + LP14
which implies:
3CR + 10L,
21n + +C2 + L.
i <
0z
This concludes the proof.
Thus, show that the estimation of the Slater's parameter is upper bounded by the true A similar reasoning holds for the estimated strictly feasible solution. The result is provided in the following lemma.
Lemma 6.2. Given any 5 (0, 1), Algorithm 4 guarantees p minge[m] 9. q P..0) S p with prob. at least 26.
Proof. It holds:
gt. (r, - -0/L) + / 25 1
7
(E(m) t=1
1
min
a
(x, ax) + 2
kE[m]
min
(z 04) LV
28 In σ 2L
2t 2f
k=1
min
a:
Σ
g. qt 2L 2f
+
+2
2f
1E
min
+
1
Σ
J. q: + 2L
2F ln
1
2
2L
2f In
1
<E|m]
8
8
1=1
min
(a:
3.)
<E|m]
P:
where the first steps hold with probability least 1 25 by Azuma inequality and a Union Bound and the last inequality holds by definition of a
To prove the second result we first notice that, by definition of 9º:
min (a+ J. J. P. <
min (a: [T 1E(m]
min (a: B,) p. k6(m)
km(m)
26

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Furthermore, by definition of 7., it holds:
1=1
Hence,
min (a; D. -.'0"' ==:²)) im(m)
min iE [m]
a;
i
1
Σ
Di q
T
1-1
(1,( ax) + + 2f 1 )
Σ
2 min im|m]
02
i
p,
where the first inequality holds with probability at least 1 26 employing the Azuma inequality and a union bound. This concludes the proof.
Finally, we show that is not small, namely, it is lower bounded by p/2. The result is provided in the following lemma.
Lemma 6.4. Given any 8 E (0, 1), Algorithm 4 guarantees p 2 p/2 with probability at least (Cp + 2)ō.
Proof. Similarly to Lemma 6.1, we get, with probability at least (C$ + 2)6
Σ (e.((x:aa) as 2-c22-CVNN 2T, 2 1 -CRVi+ 8
xE[m]
Thus, notice that, by the stopping condition of Algorithm 4, it holds:
9r.1 ( ax) - oz) 0z) - C.VVElnn Eln(() 4Lg 25 5
- CRVi
max mm
max 2 (E(m)
ge,
Σ 9r. (T, -n) -0s) -CRVThi() 4T,
2h
1
cCVi
ie [m
max 2 DE (m(m)
(x, ax) - -
C CIVinn(() C Vil((()) + 41,
27 5
4h
2
+
C-Vi - C
1 max
Σ
Σ ge, ax) Oa
2 (m(m
Hence,
max 15[m]
ge. (Ik: ax) - -a/L2
+ +2L 2
- 2 22 1
max (E[m]
(I ax) -
-a//L 02/L
+ vtl - 4L
21 + C Vi
t=1
1 max
ge.s g (Ik, ax) - az
+ + 4L
2F In x
I
+ +C Vi -211/ 26
2 iE mm)
P
2'
This concludes the proof.
27

---

Learning Adversarial MDPs with Stochastic Hard Constraints
E.2. Violations
In this section, we provide the theoretical guarantees attained by Algorithm 4 in terms of cumulative positive violation. This is done by means of the following theorem.
Theorem 6.3. Given 8 (0, 1), Algorithm attains VT S 50 + + I + + +))) with probability least 1- (Cp 7)6.
Proof. We split the violations between the two phases of Algorithm as:
Vr v max iE m
T 01 ạt
as]
[o qi ai]
E mm]
< LF + max iE[m]
[o_ ai oss
L C C Iy In CR +1)²
T Σ 1=1+1
0
+ max (E[m)
J. qt - as)
p²
where the last step holds with probability least 1 (Cp + 2)8 by Lemma 6.1.
In the following we show that, after 7 episodes, Algorithm is safe with high probability. Similarly Theorem 5.1 there are two possible scenarios defined by Xe, namely, A = 0 and x (0, 1). When A 0, applying the same reasoning of Theorem 5.1 gives the result.
In the following analysis we consider generic constraints i E [m]] Thus, we notice that the constraints cost attained by the non-Markovian policy ne, is equal to Ac-19, " + - -1-1). ....
Then, we consider both the cases when L < (# + E _ ū, (first case) and L > (#r-1,x + E1-1) T io (second case). If the two quantities are equivalent, the proof still holds breaking the ties arbitrarily.
First case. holds that:
A1-19, T -5 + (1 Ac-1)7,
T
L -
g -
L) +
L 0i + p
0₁ L
(as - P - L) +L
(30)
0i p L
ag
where Inequality (30) holds with probability at least 1 - 20 thanks to Lemma 6.2.
Second case. Similarly to the first case, it holds that, under the clean event:
A 19- 9-d p
+(1 A- 19. p
< X 19 19, q p
+(1 - 1-11 (1- + Em-1)² T q P.
(31)
< \ 17 g
p
+(1 1) (0r-1,1 1,1 + E-11 T ūz
(32)
A- p.30
A-1 ( 01-1, 1, {1-1) T ūe + (ği-1,4 + {1-1) T Ti
A ( p,#
(gi-111 1. {(-1 )) ū.) + (0:-1,5 + 1 ūt
(0c-1,5 + E(-1)
ût - as
(as - p (ā--1. + {(-1) T ( + (9.-1,5 + Eo-1)² ae
1,6 + { ût - a; +p
04- (0-1, + 1 ū1
(as p (ā 1,5 + {1-1) T
7x) + (āt-1,5 + Ec-1) T ihe
a p 17-1, + E0-1) 11
as (, + E ) ū4 + (0
+ {-1) T T
28

---

Learning Adversarial MDPs with Stochastic Hard Constraints
where Inequality (31) holds by the definition of the event and Inequality (32) holds by the definition of Ue.
To conclude the proof, we underline that A is chosen taking the maximum over the constraints, which implies that the more conservative X (the one which takes the combination nearer to the strictly feasible solution) is chosen. Thus, all the constraints are satisfied and final union bound concludes the proof.
E.3. Regret
In this section, we provide the theoretical guarantees attained by Algorithm 4 in terms of cumulative regret. This is done by means of the following theorem.
Theorem 6.5. Given any d E (0, 1), with "f = /ULLIIAAA///XXII Algorithm 4 attains regret Rr S O (VOL"IXIV/ATTII (TIX))alm/)) + 4/0 + 1/8 CR + L)* with probability least 1 (C). + 13)6, where we ler θ p/
Proof. We split the regret between the two phases of Algorithm 4 as:
RT S Σ l (q
P
9')+ Σ e Pa -"9)
1=41
LE
Σ
C7 (g pm -q")
(g
1=f+1
1. CC + Ty In + C2 +
0o
+ Σ
(a - -4),
t=1+1
where the last step holds with probability least 1 (C). + 2) by Lemma 6.1.
To bound the second terms we follow the steps of Theorem 5.2 after noticing that, for all / E (T):
L - ai L aj
A S max iE|m]
< 1,
and that:
min { (@rr, + {x) ū4t1, 1 - a0
X min (Crr, + [x) u1+1, 1.} - 0' +
(ār,s + {x) "u4t ae
( + {t) M441 0' +
( + {x) (441- - ai
(33)
(+., - {t) T "o41 + 25, Uz41 - a0
@..1 -
TT)TT 9c+1 (
+ (ge. [e) (Tu0((1== (++1) + +2, u.41 04
@0., - TT) [T)
qi+1 + +T,,, ( 90-1) + 22, ū,
p
Dr. (te+1 @c+1) 22,, i4-1
(34)
I1.1 (0+41 -g R. + IT. ( P
P(111)))) + 2c, u+41
p
29

---

Learning Adversarial MDPs with Stochastic Hard Constraints
10, M441 - o P 112 + 00.sllool19 P qp P 1 11 + 2E, ue+1
|i+t1 - g 112 + Pl -q g ||1 + 25T u++1
P
L(1 A,) 9 p 1 + ((1-)))l
gf 11 + +L2(1 Ax)EE ūc+1 min (D.
(35)
4L Ae) q 8 112 1-441111 \o) \ Ri 9 Peti. 111 + +8L(1 Ne)ET T0+11
(36)
min (p,
where Inequality (33) holds since, for the hardest constraint, when X + 0. (ot.: + T L-ai and Inequality (36) holds
ū441 > 0g, Inequality (34) holds
since, under the clean event, (Tr. {x) To+1 S og Inequality (35) holds since X S Z-a.+p with probability at least (Cp. + 2) by Lemma 6.4. A final union bound concludes the proof.
F. Omitted proof of the lower bound
In this section, we provide the lower bound which holds both in the second setting, that is, when the objective is to guarantee the safety property for each episode and when the objective is to attain constant violation.
Theorem 6.6. There exist two instances of CMDPs (with a single state and one constraint) such that, if in the first instance an algorithum suffers from violation Vr = of (()T) probability least nô for any ò (0, 1) and n then, in the second instance, must suffer from regret Ry 52( L (T) with probability 8/4 nd.
P
Proof. We consider two instances defined follows. Both of them are characterized by CMDP with state (which is omitted for simplicity), two actions 01, 02, one constraint and 1/2. For the sake of simplicity consider CMDP with rewards in place of losses. Notice that this is without loss of generality since any losses can be converted to an associated reward. We assume that the rewards are deterministic while the constraints are Bernoulli distributions with means defined in the following. Specifically, instance and instance i² are defined as:
F(an) 2 g(a)) (F(22) = 0, g((2) 2 P
2 +
8 = F((1)) = 2, g(a)) = 2
F(a2) 0, A(a2) 1 ppp
where is a parameter to be defined later. Thus, since the algorithm must suffer of o(vT) violation, for any constant c >>> 0, holds:
{ ((((2)) c+p VT WE 21-n n.
pa
where ((2)) is the occupancy measure associated to action and pt is the probability measure of instance i which encompasses the randomness of both environment and algorithm. Thus we can rewrite the inequality above as:
T
pl
(12) 2T c+p
evT) 2 n.
By means of the Pinsker's inequality we can relate the probability measures Ipl and 1 as follows:
Σ qe (02) 2 T c - orT -V
Tp2 qe (02) 2 T e _T- c+p
cVT] PPl
c+p
where KL(i', ? is the the KL-divereence between the probability measures of instance in and iz.
Noticing that by standard KL-decomposition argument, KL(i", (12 s 2T, we have:
T
p
(w2) > T 6 t+p
cvT 2 n 8 - $V
30

---

Learning Adversarial MDPs with Stochastic Hard Constraints
We then notice that, since the rewards deterministic, the regret of the second instance R2. is bounded as:
T
R2
(a()))
2 t=1
T
VT
2 c+P 2
2 T' T
4p
1
2T cVT
16p
z
/2T,
32p
with probability 1 6, taking 1/ 7. and
v2
This concludes the proof.
G. Auxiliary lemmas from existing works
G.1. Auxiliary lemmas for the transitions estimation
First, we provide the formal result on the transitions confidence set.
Lemma G.1 (Jin et al. (2020)). Given confidence & E (0, 1), with probability at least - 48, it holds that the transition function P belongs to Ptfor all E [T].
Similarly (Jin al., 2020), the estimated occupancy measure space A(P:) characterized as follows:
Ak:
E
q (x),,x²) =1
Vk, Var,
Σ ( (x)) eEA,F'EX
Σ
(
A(P.) = Ak, (2,
(
Pr [x,0) + E (x' 22
E g(2,
yEXL+1
( 2 Px (x,a) e (x' (x,a)
E g(2,
yEXN+1
9 (x,
Given the estimation of the occupancy measure space, it possible to derive the following lemma. Lemma G.2. (Jin et al., 2020) With probability least 66, for any collection of transition functions {PT Jeex such that P Pt, we have, for all x,
Σ
T
Σ
Pe Pi (x, (z, a) 0 [|X]
A
T 8
1=1
DE X
underline that the constrained space defined by Program (2) a subset of A(P,). This implies that, in Algorithm holds के ((P:) and Lemma G.2 is valid.
G.2. Auxiliary lemmas for the optimistic loss estimator
will make use of the optimistic biased estimator with implicit exploration factor (see, (Neu, 2015)). Precisely, we define the loss estimator as follows, for all e [T]:
E(xxa) = (( a) (, ((x,a)
u11 a) +
where u.xx a) == maxper, g (x, Thus, the following lemmas hold.
31

---

Learning Adversarial MDPs with Stochastic Hard Constraints
Lemma G.3. (Jin al., 2020) For any sequence of functions 01,...., or such that ot [0, 27)xxx is Fe-measurable for all we have with probability at least 1 5,
ΣΣ a) ((((r,a)
(0(2,a) (((2)a)) & Lln
L 8
(1
Following the analysis of Lemma G.3, with az a) = 2211(xx a) and union bound, the following corollary holds. Corollary G.4. (Jin et al., 2020) With probability at least 6:
((x,a)
(e(2, a) u1 a)
(((2,))
in [X||A]]
2n
8
Furthermore, when n. + Tr. the following lemma holds.
Lemma G.5. (Jin et al., 2020) With probability at least 1 - 78.
Σ
l - E.)
To 00
LIXIV |A| In
T [A]
+
We notice that T. <- Te holds only for Algorithm 2, since in Algorithm 3, Te +- T with probability 1 A1-1-
G.3. Auxiliary lemmas for online mirror descent
We will employ the following results for OMD (see, Orabona (2019)) with uniform initialization over the estimated occupancy measure space.
Lemma G.6. (Jin al., 2020) The OMD update with क (I,, x') TxllIA|Xenaa for all k < L and (x,,,,x) X₂ A x N841, and
2e a D
2+1 arg min (EA(P.)
where (glld) Emsayr a (z, a²) In (x.,,,)) ((araa))
En.a. (1, (x, a'))) ensures
T
Lln (IX(3A))
Σ
E (ee - -
+ +1
Σ (1,
n
1,0,0
for any q E (Pi),, as long as (z, a) 2 ffr all t, x, a
32


Reviews:
[{"review_id": "oCOElMszMn", "reviewer": "Reviewer_39LP", "summary": "This paper introduces algorithms for constrained Markov Decision Processes (MDPs) with stochastic hard constraints, considering different assumptions and objectives for constraint violations. Specifically, it examines three key cases: (1) when constraints are feasible, (2) when constraints are strictly feasible with a known feasible policy, and (3) when constraints are strictly feasible but no strictly feasible policy is known beforehand. The paper establishes sublinear regret and constraint violation bounds for all three scenarios. The writing is clear, and the proofs are straightforward to follow. The core approach involves optimistically satisfying cost constraints in the first case and randomizing between an optimistic and a strictly feasible policy in the second.", "questions": "", "limitations": "", "rating": 3, "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 thank the Reviewer for the positive evaluation of the paper.\n\n> Question 1.\n\nWe thank the Reviewer for the opportunity to clarify this aspect. Indeed, there is no contradiction between [1] and our lower bound, since our lower bound holds for our second and third scenario only, namely, when we aim to guarantee a violation of order $o(\\sqrt{T})$, such as $0$ or constant violation. In our first scenario, we **do not assume Slater's condition** and we guarantee $O(\\sqrt{T})$ regret and violation, thus, there is no contradiction w.r.t. [1].\n\n> Question 2.\n\nWe agree with the Reviewer that experiments are always beneficial; nevertheless, we underline that both in the online CMDPs literature and the adversarial MDPs one, many works do not have experimental results (see e.g., Rosenberg et al. (2019b), Jin et al. (2020), Efroni et al. (2020), Stradi et al. (2024b) and many others). Despite the lack of experimental evaluation, many of the aforementioned works (and many others) have been published in top AI conferences, such as ICML.\n\n> Question 3.\n\nWe thank the Reviewer for the opportunity to clarify this aspect. Please notice that Eq. (2) is a convex program with linear constraints, which can be approximated arbitrarily well in polynomial time. We underline that solving this kind of projection is standard in the adversarial MDPs literature (see e.g., Rosenberg et al. (2019b), Jin et al. (2020)). Similarly, it is standard for adversarial online learning algorithms to require projections to be solved at each episode, even in easier single-state full-feedback settings (e.g., OGD and OMD algorithms).\n\nWe finally thank the Reviewer for the other comments and suggestions, we will surely update the final version of the paper taking them into account.", "claims_and_evidence": "The lower bound in Theorem 6.6 seems a bit puzzling to me. Please refer to the questions for the authors field below.", "methods_and_evaluation_criteria": "This is fine.", "theoretical_claims": "This is mostly fine.", "experimental_designs_or_analyses": "No experimental result has been provided.", "relation_to_broader_scientific_literature": "Please refer to the questions for the authors field below.", "essential_references_not_discussed": "[1] Sinha, Abhishek, and Rahul Vaze. \"Optimal algorithms for online convex optimization with adversarial constraints.\" Advances in Neural Information Processing Systems 37 (2025): 41274-41302.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Statements on Constraint Violation and Regret appear first in Theorems 4.2 and 4.3, but I could not find their formal definitions earlier in the paper. Clearly stating these definitions upfront would improve readability and help the reader follow the theoretical results more easily.", "questions_for_authors": "1.\tPrior work [1] demonstrated that $O(\\sqrt{T})$ regret and violation bounds can be achieved in online convex optimization with adversarial hard constraints without assuming Slater’s condition (i.e., when $\\rho=0$). Keeping this result in view, could the authors offer some intuition on why Slater’s condition assumption is necessary for online reinforcement learning with hard constraints? Specifically, why does the result in [1] not contradict the lower bound given in Theorem 6.6, given that the lower bound proof involves a single state MDP?\n\n2.\tThe paper does not include any numerical comparisons with prior algorithms in the MDP setting, making it difficult to assess the practical effectiveness of the proposed theoretical results.\n\n3.\tIn Equation (2), computing the projection may be computationally challenging. Can the authors provide an upper bound on its worst-case computational complexity?\n\nReferences:\n\n[1] Sinha, Abhishek, and Rahul Vaze. \"Optimal algorithms for online convex optimization with adversarial constraints.\" Advances in Neural Information Processing Systems 37 (2025): 41274-41302.", "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": "aRXCqWTqTZ", "reviewer": "Reviewer_jA7c", "summary": "This paper studies episodic Constrained Markov Decision Processes (CMDPs) with adversarial losses and stochastic hard constraints under bandit feedback. It is the first to address a setting that combines both adversarial losses and strict hard constraints, whereas prior work has either considered adversarial losses with soft constraints, allowing negative violations to cancel out with positive ones, or stochastic losses with hard constraints. The authors propose three algorithms tailored to different scenarios and under different assumptions: the first ensures sublinear regret while keeping cumulative constraint violations sublinear, the second guarantees that the constraints are satisfied at every episode assuming the learner knows a strictly feasible policy, and the third achieves constant violation regret assuming a strictly feasible policy exists but is not known to the learner.", "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 thank the Reviewer for the positive evaluation and for the interesting question. Indeed, this is an interesting future direction, nonetheless, we believe that it would be highly non-trivial to employ a primal-dual approach to solve any of the scenarios we study, due to the following reasons. For the first scenario, primal-dual methods generally require Slater’s condition to hold, which is not the case of our algorithm. Moreover, primal-dual methods generally fail to remove the $1/\\rho$ dependence in the regret and violation bound, thus achieving worse regret and violation guarantee than SV-OPS. Finally, notice that primal-dual methods developed for adversarial loss settings do not guarantee sublinear positive violation, but employ a violation definition where the cancellations are allowed (see, e.g., Stradi et al. (2024b)). As concerns the second and third scenario, we believe that the randomization with the strictly feasible policy requires an optimistic safe-set estimation, which is generally not employed in primal-dual methods. \n\nFinally we want to underline that solving this kind of projection is standard in the adversarial MDPs literature (see e.g., Rosenberg et al. (2019b), Jin et al. (2020)). Similarly, it is standard for adversarial online learning algorithms to require projections to be solved at each episode, even in easier single-state full-feedback settings (e.g., OGD and OMD algorithms).\n\nPlease let us know if further discussion is necessary.", "claims_and_evidence": "All theoretical claims are followed by proofs in the appendix.", "methods_and_evaluation_criteria": "As a theoretical paper, the algorithms make sense for the problem.", "theoretical_claims": "Proofs for theoretical claims seem correct.", "experimental_designs_or_analyses": "not applicable.", "relation_to_broader_scientific_literature": "This paper is the first to tackle the case of constrained MDPs when facing both the challenges of adversarial losses and hard constraints. Existing results so far would either treat adversarial losses with soft constraints, or stochastic losses with hard constraints. \n    \nHowever, the SV-OPS algorithm from Section 4 (the first algorithm proposed) primarily builds on existing ideas from the online MDP literature, introducing only minor generalizations. The algorithm follows the same OMD iterative scheme as in [Jin 2020]. But instead of projecting onto the space of occupancy measures that satisfy the dynamic constraints for any probability transition within a confidence set around the true transition, SV-OPS also projects onto the set of estimated constraints to ensure sublinear positive constraints violation. Projecting on the estimated constraints has already been introduced by [Efroni et al. 2020] in the set of stochastic losses.\n\nOn the other hand, the algorithm proposed in Section 5, which ensures safety in every episode, and the one proposed in Section 6, which guarantees constant violations, introduce novel ideas that may be of interest to the broader online C-MDP community.", "essential_references_not_discussed": "Related work is clear.", "other_strengths_and_weaknesses": "- **Strenghts**: First, the paper is well-written. Second, the extension of SV-OPS to scenarios that ensure safety at evert episode and guarantee constant violation appears novel and may be of significant interest to the online C-MDP community.\n\n - **Weaknesses**: For SV-OPS, the sublinear constraint violation is ensured due to the accurate estimation of $ G_t $ and the projection in Eq. (2). However, implementing this in practice would require access to a solver for a linear programming problem with at least $ \\Omega(XLA) $ decision variables and constraints, making it computationally expensive for frameworks with large state spaces.", "other_comments_or_suggestions": "No further comments", "questions_for_authors": "Regarding the concern raised above about the projection, could it be feasible to design a primal-dual algorithm (which performs well in practice) that employs a similar OMD iterative scheme to handle adversarial losses while achieving both sublinear regret and sublinear violations?", "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": "6Ly4hfoOPe", "reviewer": "Reviewer_Lzh6", "summary": "This paper studies online learning in constrained Markov Decision Processes with adversarial losses and stochastic hard constraints under bandit feedback. The authors introduce novel algorithms for three distinct scenarios of CMDPs, ensuring sublinear regret while managing constraint violations in different ways. The authors provide theoretical guarantees for the proposed algorithms.", "questions": "", "limitations": "", "rating": 3, "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 thank the Reviewer for the effort in evaluating our work.\n\n>  W1\n\nWe agree with the Reviewer that experiments are always beneficial; nevertheless, we underline that both in the online CMDPs literature and the adversarial MDPs one, many works do not have experimental results (see e.g., Rosenberg et al. (2019b), Jin et al. (2020), Efroni et al. (2020), Stradi et al. (2024b) and many others). Despite the lack of experimental evaluation, many of the aforementioned works (and many others) have been published in top AI conferences, such as ICML.\n\n> W2\n\nWe thank the Reviewer for the opportunity to clarify this aspect. Please notice that Eq. (2) is a convex program with linear constraints, which can be approximated arbitrarily well in polynomial time. We underline that solving this kind of projection is standard in the adversarial MDPs literature (see e.g., Rosenberg et al. (2019b), Jin et al. (2020)). Similarly, it is standard for adversarial online learning algorithms to require projections to be solved at each episode, even in easier single-state full-feedback settings (e.g., OGD and OMD algorithms).\n\n> W3\n\nWe thank the Reviewer for the opportunity to clarify these aspects. \n\nRegarding Lagrangian methods, state-of-the-art primal-dual algorithms are not suited to handle any of our scenarios. Broadly, these algorithms can be categorized into two main families: (i) primal-dual methods designed specifically for stochastic settings (e.g., [1], [2], [3]), and (ii) algorithms that address both stochastic and adversarial CMDPs (e.g., [4], [5]). All the algorithms in the first class assume that the losses/rewards are stochastic in nature, thus, their techniques and results are not applicable to our three scenarios. For the latter, [4], [5] achieve $\\sqrt T$ regret and violation when the constraints are stochastic and the losses adversarial. Nevertheless, notice that their violation definition allows per-episode violations to cancel out, thus they employ a weaker violation definition w.r.t. ours. Moreover, the aforementioned papers assume Slater’s condition to hold, which is not the case for our first scenario. Our second and third scenarios have never been tackled employing primal-dual methods even in simpler stochastic rewards settings.\n\nAs concerns model-based techniques, our work is the first to tackle adversarial losses. Additionally, our work is the first one to provide constant violation bounds (employing our positive violation definition) without assuming the knowledge of a safe policy, even considering stochastic settings. Finally, existing model-based algorithms tailored for stochastic versions of our second scenario do not work in adversarial settings, and cannot be easily extended due to a different randomization approach ([6], [7]). For further details on these aspects please refer to the next answer.\n\nWe will surely include this discussion in the final version of the paper.\n\n\n> W4\n\nWe thank the Reviewer for the opportunity to better discuss the algorithmic components of our techniques.\n\nSV-OPS employs the optimization approach of Jin et al. (2020) on optimistic safe decision spaces. Optimistic safe decision spaces were originally introduced by [1] in the context of stochastic CMDPs.\nThe idea behind S-OPS and its randomization approach is novel in the CMDPs literature. We acknowledge that there exist other forms of randomization which are suitable for stochastic CMDPs (see, e.g., [6], [7]), but they fail in working in adversarial settings. To see this, notice that the algorithms presented in [7], [8] play the safe policy for a fixed amount of rounds and then resort to pessimistic decision spaces which are increasing in $t$. It is well-known that adversarial online learning algorithms do not work on increasing decision spaces. Thus, their approach cannot be easily generalized to tackle adversarial loss.\nBV-OPS employs techniques which are completely novel in the literature.\n\nWe hope to have properly addressed the Reviewer concerns. Please let us know if further discussion is necessary.\n\n\n[1] Efroni et al (2020), “Exploration-Exploitation in Constrained MDPs”\n\n[2] Müller et al. (2024), “Truly No-Regret Learning in Constrained MDPs”\n\n[3] Stradi et al. (2024), “Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization”\n\n[4] Qiu et al. (2020), “Upper confidence primal-dual reinforcement learning for cmdp with adversarial loss.”\n\n[5] Stradi et al. (2024), “Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints” \n\n[6] Liu et al. (2021), “Learning policies with zero or bounded constraint violation for constrained mdps”\n\n[7] Bura et al. (2022), “DOPE: Doubly optimistic and pessimistic exploration for safe reinforcement learning.”", "claims_and_evidence": "The core theoretical claims (sublinear regret, constraint violation guarantees, and the lower bound) are well supported by clear mathematical proofs.", "methods_and_evaluation_criteria": "The regret and constraint violation are standard evaluation criteria for online CMDPs.", "theoretical_claims": "The theoretical claims are well-supported by the proofs, though I do not have time to check the details of the proofs.", "experimental_designs_or_analyses": "The paper does not include any experimental results.", "relation_to_broader_scientific_literature": "The paper is well-positioned in the literature on online CMDPs.", "essential_references_not_discussed": "I did not find any essential references missing.", "other_strengths_and_weaknesses": "### Strengths\n1. This paper is the first to study CMDPs with both adversarial losses and stochastic hard constraints, extending previous work on constrained RL.\n2. This work presents different algorithms tailored to distinct CMDP scenarios and provides rigorous theoretical guarantees for each.\n3. The paper establishes a lower bound, highlighting the fundamental trade-off between constraint satisfaction and regret minimization.\n\n### Weaknesses\n1. The paper lacks experimental results, making it difficult to assess the practical effectiveness and computational feasibility of the proposed algorithms.\n2. The paper could benefit from a more detailed discussion of the computational complexity of the proposed algorithms, for example, the KL-divergence-based projection in SV-OPS and S-OPS (Equation 2).\n3. The paper does not compare its work against alternative CMDP approaches, such as Lagrangian-based methods, which relax constraints using dual variables and model-based safe RL techniques that explicitly incorporate safety models. Moreover, a discussion on how existing methods fail to handle the hard constraints would help justify the novelty of the proposed approach.\n4. Distinguishing the new components from existing techniques in the algorithms would help clarify the novelty of the proposed methods.  For example, the upper occupancy bound, optimistic loss estimator, and OMD in SV-OPS appear similar to Jin et al. (2020) [1], which should be explicitly highlighted. Since I am not deeply familiar with the CMDP literature, it is unclear whether the constraint-handling components are new or adaptations of prior techniques.\n\n[1]. Jin et al., Learning adversarial Markov decision processes with bandit feedback and unknown transition. In ICML 2020.", "other_comments_or_suggestions": "I suggest adding a discussion on the computational complexity of the proposed algorithms and comparing them against alternative CMDP approaches. Moreover, a detailed comparison with existing methods and a clear exposition of the novel components in the algorithms would enhance the paper's clarity and impact.", "questions_for_authors": "NA", "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": "MActPBvqNV", "reviewer": "Reviewer_RDix", "summary": "This paper considers adversarial MDP problems with stochastic constraints. The paper seeks to bound both the regret and the violations (hard). The paper shows that $O(\\sqrt{T})$ regret and $O(\\sqrt{T})$ violations bound only when the Slater's condition is satisfied. The paper shows that $O(\\sqrt{T})$ regret and no violation when a strictly feasible policy is known. In fact, it also shows that it is possible to achieve constant violation and $O(\\sqrt{T})$ regret only when one does not know the strict feasibility parameter.", "questions": "", "limitations": "", "rating": 3, "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 thank the Reviewer for the effort in evaluating our work. \n\n> On the comparison with existing works and [W1]\n\n[A1] focuses on CMDPs with stochastic rewards and constraints, showing how it is possible to achieve $\\sqrt T$ regret and violation. The only technique proposed by [A1] which is of interest in our setting is the optimistic safe set estimation, which is employed by SV-OPS.\n\n[A2] and [A3] study the stochastic version of our second scenario. Their randomization techniques cannot work in our second scenario, since in adversarial settings, it is not possible to play the safe policy for a fixed amount of rounds and then switch to an adversarial online learning algorithm on a pessimistic decision space. To see this, notice that pessimistic decision spaces increase over time and that adversarial online learning algorithms do not work on increasing decision spaces in $t$. \n\nMoreover, notice that even if [A3] shows how to obtain constant violation, but this is done employing a weaker version of constraints violation (which allows for cancellations between episodes), thus they are not applicable to our third scenario.\n\nSimilarly to [A1], [A4] focuses on CMDPs with stochastic rewards and constraints, showing how it is possible to achieve $\\sqrt T$ positive regret and violation. Their techniques cannot be generalized to adversarial settings, since they assume that there exists an underlying reward distribution in their analysis. Moreover, notice that the algorithm proposed in [A4] has an exponential worst-case running time, while our algorithm is polynomial.\n\nTo conclude, our paper's main contributions are highlighted as follows. First, we study a novel CMDP setting, encompassing both adversarial losses and hard constraints. Specifically, we focus on three scenarios, which are all novel and cannot be tackled by existing algorithms. The first one is novel in terms of results, while we agree that we combine existing techniques to get our theoretical results. The second and third scenarios are instead novel both in terms of results and in terms of algorithmic techniques. Furthermore, the third scenario has never been studied even in simpler stochastic settings. Finally, we propose a novel lower bound which can be of independent interest, since it applies to the stochastic setting, too.\n\nWe will surely include this discussion in the final version of the paper.\n\n> [W2] \n\nWe agree with the Reviewer that studying CMDPs with infinite state-action spaces is an interesting future direction. Nevertheless, since this is the first work to tackle both adversarial losses and hard constraints, providing a large set of different results, we believe it is still of interest for the community.\n\n> [Q1] \n\nAs is standard in the adversarial MDPs literature, the performance metrics are computed taking the expectation over policies and transitions. Since S-OPS plays non-Markovian policies, the expected violation is computed taking into account the randomization selected by the algorithm (please refer to Theorem 5.1. for additional details).  \n\n> [Q2] \n\nOptimistic occupancy measures can be computed in $O(|X|^3|A|^2)$ steps (please refer to Jin et al. (2020) for the associated algorithm pseudocode). \n\n> [Q3] \n\n$\\lambda_t$ is proportional to the uncertainty the algorithm has on both constraints and transitions. Thus, $\\lambda_t$ is greater in the first episodes while converges to $0$ as the learning dynamic evolves. \n\nSince these are crucial aspects of our work, please let us know if further details are necessary. We would be happy to engage in further discussion.", "claims_and_evidence": "The paper is theoretical in nature. All the claims have been proved.", "methods_and_evaluation_criteria": "Not applicable as the paper's scopes are theoretical in nature.", "theoretical_claims": "I briefly checked the correctness which seems to be correct.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "This paper seeks to contribute in the space of adversarial MDP with stochastic constraints. The paper extends the adversarial MDP work to the CMDP setup with stochastic constraints. The paper achieves optimal regret and violation bound.", "essential_references_not_discussed": "The paper has not discussed with some of the major papers in the CMDP domain. While I agree that those papers did not consider adversarial rewards, however, in order to understand the technical contributions, one needs to understand the technical novelties required. In particular, why not combining all these approaches will not be enough to solve this problem?\n\n[A1]. Efroni, Yonathan, Shie Mannor, and Matteo Pirotta. \"Exploration-exploitation in constrained mdps.\" arXiv preprint arXiv:2003.02189 (2020).\n\n[A2]. Bura, A., HasanzadeZonuzy, A., Kalathil, D., Shakkottai, S. and Chamberland, J.F., 2022. DOPE: Doubly optimistic and pessimistic exploration for safe reinforcement learning. Advances in neural information processing systems, 35, pp.1047-1059.\n\n[A3]. Liu, T., Zhou, R., Kalathil, D., Kumar, P. and Tian, C., 2021. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34, pp.17183-17193.\n\n[A4]. Ghosh, Arnob, Xingyu Zhou, and Ness Shroff. \"Towards achieving sub-linear regret and hard constraint violation in model-free rl.\" In International Conference on Artificial Intelligence and Statistics, pp. 1054-1062. PMLR, 2024.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper is well written.\n\n2. The proof ideas seem to be correct. \n\nWeaknesses:\n\n1. The major weakness is that the technical novelties are not clear. CMDP setup is well studied. As I discussed, it is not clear what are the major technical innovations.\n\n2. The paper only considers tabular case.\n\n**Post Rebuttal:**\n\nThis work is solid and I am convinced about the contributions. I have raised my score.", "other_comments_or_suggestions": "Please see the questions", "questions_for_authors": "1. In the guaranteeing safety Algorithm (S-OPS Section 5), the paper utilizes a random exploration with a certain probability in the first episode, and also when the state-action occupancy found by the algorithm is not safe. However, is there any assumption which states that random exploration is safe? In general, such an exploration might not be safe. \n\n2. The algorithm relies on building optimistic state-action-occupancy measures, how easy (computationally) it is?\n\n3. What are the values of $\\lambda_t$? How they are refined with time $t$?", "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: We thank the authors for their submission.
The reviews appreciated the algorithmic techniques and the end results.
There are some issues mentioned in the reviews that should be clarified in the next version, for example:
- Detailed description of the novelty compared to prior work.
- Discussion of computational complexity of the proposed algorithms.
- Discussion on why existing methods fail under hard constraints.
Decision: Accept (poster)