Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Authors: Francesco Emanuele Stradi
Anna Lunghi
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Venue: ICML 2025 poster (2025)
Keywords: CMDPs
Online Learning
Primary area: theory->online_learning_and_bandits

Abstract: We study online learning in constrained Markov decision processes (CMDPs) in which rewards and constraints may be either stochastic or adversarial. In such settings, stradi et al. (2024) proposed the first best-of-both-worlds algorithm able to seamlessly handle stochastic and adversarial constraints, achieving optimal regret and constraint violation bounds in both cases. This algorithm suffers from two major drawbacks. First, it only works under full feedback, which severely limits its applicability in practice. Moreover, it relies on optimizing over the space of occupancy measures, which requires solving convex optimization problems, an highly inefficient task. In this paper, we provide the first best-of-both-worlds algorithm for CMDPs with bandit feedback. Specifically, when the constraints are stochastic, the algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and constraint violation, while, when they are adversarial, it attains $\widetilde{\mathcal{O}}(\sqrt{T})$ constraint violation and a tight fraction of the optimal reward. Moreover, our algorithm is based on a policy optimization approach, which is much more efficient than occupancy-measure-based methods.

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Francesco Emanuele Stradi
Anna Lunghi
Matteo Castiglioni Alberto Marchesi Nicola Gatti
Abstract
requirements. For instance, in autonomous driving one has to avoid crashing with other cars (Isele et al., 2018), in ad auctions one must not deplete the allocated budget (He et al., 2021), while in recommendation systems offending items should not be presented to the users (Singh et al., 2020). In order capture such requirements, constrained MDPs (CMDPs) (Altman, 1999) have been introduced. These augment classical MDPs by adding costs that the agent is constrained to keep below some given thresholds.
We study online learning in constrained Markov decision processes (CMDPs) in which rewards and constraints may be either stochastic or ad- versarial. In such settings, Stradi et al. (2024b) proposed the first best-of--otthwworlds algorithm able to seamlessly handle stochastic and adver- sarial constraints, achieving optimal regret and constraint violation bounds in both cases. This algorithm suffers from two major drawhacks. First, it only works under full feedback, which severely limits its applicability in practice. More- over, relies on optimizing over the space of occupaney measures, which requires solving con- vex optimization problems, an highly inefficient task. In this paper, we provide the first best-of- both-worlds algorithm for CMDPs with bandit feedback. Specifically, when the constraints are stochastic, the algorithm achieves Õ(VT) regret and constraint violation, while, when they are ad- versarial, attains (vT)) constraint violation and a tight fraction of the optimal reward. More- over, our algorithm is based on policy optimiza- tion approach, which is much more efficient than meaauure occupancy measure- peassure-based methods.
Over the last years, online learning problems in episodic CMDPs have received growing attention (see, e.g. (Efroni et al., 2020) for a seminal work in the field). These are problems in which the learner repeatedly interacts with the CMDP environment over multiple episodes. In such set- tings, the learner's s goal is to minimize the regret of not always selecting a best-in- -iiddis-iinnsghtt policy that satisfies cost constraints, while at the same time ensuring that the cumula- tive violation of cost constraints does not grow too fast over the episodes. Ideally, one would like that both the regret and the constraint violation grow sublinearly in the number of episodes T.
In online learning in episodic Markov decision processes, two different assumptions on how rewards and costs are determined at each episode are possible. They can be se- lected either stochastically according to fixed (unknown) probability distributions or adversarially, meaning that no statistical assumption is made.
1. Introduction
Very recently, Stradi et al. (2024b) proposed the first best- of of-bothh-orlls worlds learning algorithm for online learning in episodic constrained MDPs. Such an algorithm is able to seamlessly handle stochastic and adversarial constraints, achieving optimal regret and violation bounds in both cases. However, suffers from two major drawbacks. First, only works under full feedback, meaning that the learning agent needs observe rewards and costs defined over the whole environment after each episode. This is extremely unreasonable in practice, where only some feedback along the realized trajectory is usually available. Moreover, the algorithm works by optimizing over the space of occupancy measures, which requires solving a convex problem at every episode, an highly inefficient task.
Most of the learning tasks arising in real-world scenarios involve an agent sequentially interacting with an unknown environment. Markov decision processes (MDPs) (Puter- man, 2014) have emerged as the most natural models for such interactions, as they allow to capture the fundamental goal of learning an optimal (i.e., wwwwrwdwdaaaee maximmzixxiii action- selection policy for the agent. However, in most of the real- world applications, the learner has to satisfy some additional
'DIIB Politecnico di Milano, Milan, Italy. Cor- respondence to: Francesco Emanucle Stradi <trancescoe- manuele.stradió @ polimi.itz.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
1.1. Original Contributions
learning dynamics. Guaranteeing the no-interval regret property in bandir settings harder than standard multi- armed bandits was open problem in the literature. Fixed share update in Markov decision processes. To design a primal regret minimizer for MDPs with bandit feedback having the no-interval regret property, we employ a policy optimization approach with a fixed- share update. which was originally introduced by Cesa- Bianchi et al. (2012). Specifically, the fixed-share up- date performs at each episode a combination between the solution to the per-episode optimization problem and the "uniform" solution on the decision space. How- ever, applying the fixed share update in the space of the occupancy measures is problematic, since the re- sult of the interpolation may lie outside the space of the estimated occupancy measures. Hence, techniques such as the one in (Stradi et al., 2024b) are not gen- erally applicable in bandit settings. To overcome this problem, we design primal algorithm that is policy- based, where the combination is clearly meaningful. Employing fixed-share updates in policy optimization algorithms for MDPs requires a novel analysis, which we fully report in Appendix D.
We provide the first best-of-both-worlds algorithm for online learning in episodic CMDPs with bandit feedback. This means that, after each episode, the algorithm only needs to observe the realized rewards and costs along the trajectory traversed during that episode, as it is the case in most of the real-world applications. Moreover, our algorithm is based on a primal-dual policy optimization method, and, thus, it is arguably much more efficient than the one by Stradi et al. (2024b), it does not require solving convex programs.
When the costs are stochastic, our algorithm attains Ö(VT) regret and constraint violation, while, when they are ad- versarial, it achieves Ö(VT) violation and a fraction of the optimal reward. These results match those of the full- feedback algorithm by Stradi et al. (2024b) and are provably tight. We also analyze the performances of our algorithm with respect to a parameter p measuring by "how much" Slater's 's condition is satisfied. Specifically, if p is arbitrarily small, our algorithm can still guarantee ((T%/4) regret and violation in the stochastic setting.
Crucially, similarly to the algorithm by Stradi et al. (2024b), ours does not require any knowledge of the Slater's pa- rameter p. In order to obtain this result, we show that the Lagrangian multipliers the learning dynamics, by employing the no-intervul-regre property of our primal and dual regret minimizers. Indeed, we develop the first algorithm for unconstrained MDPs with intervall-rerret, under bandit feedback. We believe that this result may also be of independent interest.
Addressing the dependence on the primal loss range. A key challenge in designing an effective primal al- gorithm is controlling how the primal regret bound depends on the range of the losses. Notice that this is not a trivial task, since the magnitude of the losses is unknown a-priori. Thus, by employing a standard approach, the regret would scale quadratically in the Lagrangian multipliers, as it depends on the square of the loss magnitude. To mitigate this and ensure the regret dependence on the Lagrangian multipliers is only linear, we introduce an episode dependenn learn- ing rate. This parameter is dynamically adjusted to be proportional to the highest value of the Lagrangian multipliers observed up to the current episode.
automatically bounded during
Finally, differently from Stradi et al. (2024b), we show that our algorithm may achieve sublinear regret and violation in the adversarial setting, by using weaker baseline that has to satisfy the constraints at every round. Specifically, when p is large enough our algorithm attains Ö(VT) regret and violation, while it still achieves ((3344) regret and violation when is arbitrarily small.
1.3. Related Works
1.2. Technical Challenges
In the following, we highlight the works that are mainly related to ours. Due to space constraints, we refer to Ap- pendix A for a complete discussion about related works.
To achieve book--oddoth-wordds guarantees in CMDPs with bandit feedback when the Slater's parameter is unknown, this work faces several challenges, and it introduces novel approaches to overcome them. Specifically, the main techni- cal challenges are highlighted in the following:
Online learning in MDPs has been widely studied both un- der stochastic settings (Auer et al., 2008) and adversarial ones (Neu et al., 2010). In adversarial settings, two feed- backs are usually investigated. In the full-feedback setting, the reward function (or loss) is entirely revealed at the end of the episode. In this case, Rosenberg & Mansour (2019b) show that it is possible to achieve optimal Õ(VT) re- gret bound. In the more challenging bandit feedbbck setting, with rewards revealed along the traversed trajectory only, Jin et al. (2020) show that the optimal bound is still attainable.
Bounding the Lagrange multipliers. Bounding the Lagrange multipliers during the learning dynamics is necessary to guarantee that the primal regret minimizer has low regret, since any regret bound scales as the payoff range. This is done by employing no-interval regret algorithms for both primal and dual. Notice that the no-interval regret property is stronger than the classical no-regret one and requires a smoother
2

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
As concerns MDPs with constraints, online learning has been studied mainly in the stochastic setting (see Efroni et al. (2020) for seminal work on the topic). As concerns adversarial settings, namely, when the constraints are not assumed to be stochastic, there exists an impossibility re- sult from Mannor et al. (2009) that prevents from attaining sublinear regret and violation when the optimal solution computed with respect a policy that satisfies the con- straints on average. Thus, many works focused achieving O(VT) regret and violation for adversarial rewards and stochastic constraints (Qiu et al., 2020) or non-stationary en- vironments with bounded non-stationarity (Ding & Lavaei, 2023; Wei et al., 2023; Stradi et al., 2024c).
free CMDPs. Formally, this means that X is partitioned into H layers Xu, Nu.-..,- Xx such that the first and the last layers are singletons, i.e., Xo { and X = { and that P(z'|a |a, a) > 0 only if x' E Xx+1 and z E X,, for some h E [0 H - 1]. Any episodic CMDP with horizon H that is not loop-free can be cast into a loop-free one by suitably duplicating the state space H times. {r+}²- is a sequence of vectors describing the rewards at each episode [T], namely ra E [0, 1]|XxAl, xAI, We refer to the reward of a specific state-action pair & E x,a E A for an episode E [T] as (x( a). Rewards may be either stochastic, in that case ra is a random variable distributed according to a distribution R. for every t E (T), or chosen by an adversary. (GrY is sequence of constraint matrices describing the m constraint violations at each episode E [T', namely G, E [-1,1] 1| |XX x where non non-positive violation values stand for satisfaction of the constraints. For i E [m], we refer to the violation of the i-th constraint for specific state- action pair x E X, a E A at episode / [T] as It, a). Constraint violations may be stochastic, in that case G. is random variable distributed according to a probability distribution G for every 1 E [7]. or chosen by an adversary.
Recently, Stradi et al. (2024b) showed the first best-of- both-worlds (with respect to the constraints) algorithm for CMDPs. Precisely, the authors propose a primal-dual al- gorithm that optimizes over the occupancy measure space, under full feedback. When the constraints are stochastic, the algorithm achieves Ó( (T) regret and violation, both in the case in which rewards are adversarial and the one where they are stochastic. Contrariwise, in the adversarial setting, the algorithms attains OVVT) violatios, and the no-a-regret property with a = #/(H+p), where p is suitably-defined Slater's parameter. Notice that this result is in line with the of wooldds results in the single-state online constrained settings, e.g., (Castiglioni et al., 2022b).
The learner chooses a policy т : : + ((A) at cach episode, defining a probability distribution over actions at each state. We denote by (-|z)) the probability distribution for state E X, with (alar) being the probability of action E A. In Algorithm I we provide the interaction between the learner and the environment in a CMDP. Fur- thermore, we assume that the learner knows X and A, but they do not know anything about P. Notice that the interac- tion between the learner and the environment is with bandit feedback, namely, the rewards and the constraint violations are revealed for the traversed trajectory only.
2. Problem Setting
2.1. Online Constrained Markov Decision Processes
Algorithm 1
Interaction
1: for t = 1,...,TT T do
2: and G2 are chosen stochastically or adversarially
3: The learner chooses a policy Te. : X x A + [0
Occupancy Measures Given a transition function P and policy x, the occupancy measure & E [0, induced by P and x is such that, for all Xn, E A, and x' E X with h E [0.. H - 1], it holds
XXXXXXXX
4: The state is initialized to 20
5: for 1b=0,... O..,,..., H - do
6: The learner plays an ~ (T(()
7:
The learner observes re( an) and gt. on)
q - (x, =P (Mr = xx 0n 0, = x' x'IP,
for all E [m]
8:
The environment evolves to Tn+11 ~ P(: P(. an)
Moreover, we let ( = ExeXIs 8 ax, a. x²) and (x) E.EAATT ( Then, the set of valid occupancy measures can be characterized as follows (Rosen- berg & Mansour, 2019b). A vector & E [0, 1] x AAxX| is a valid occupancy measure of an episodic loop-free MDP if and only if the following three conditions hold:
9:
The learner observes TA-1
10: end for
11: end for
An online episodic constrained MDPs (CMDPs) (Alt-
man, 1999) tuple M == A, (ra) - {G,)" )). Specifically, T' is the number of episodes, with t [T] de- noting specific episode. X, A are finite state and action spaces, respectively. P : X x A + A(X) is the transi- tion function. We denote by P(x' [x, a) the probability of going from state x E X to state x' E X by taking action E A. Notice that, w.l.o.g., in this work we consider loop-
ΣΣ
Σ
(x,,,x))=1 =1 Vh (0...., H -1]
zeXi dE x'E
(ii) Σ Σ
((1,0,2)= = Σ Σ q(x'
Eq(a's a
ac A 2
x'EX, 1
Yh Vh [1..... .......... H - 1], Va E X
3

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
(181) pa_ P,
We refer to an optimal occupancy measure, i.e., feasible one achieving value OPT q². Thus, we can rewrite
where P is the transition function of the MDP and 1s is the one induced by Indeed, any valid occupancy measure q induces a transition function P4 and a policy x², defined as (* (2'12, a) = ((x,,,²)) and (a(x) == {(a,a) ((x,))
the regret definition Rr Σi= - - " Notice that, in the adversarial setting, the regret is computed with respect to an optimal feasible strategy in hindsight. Indeed, an optimal solution is not required to satisfy the constraints at every episode t E [T].
g(x)
2.2. Offline CMDPs Baseline
Next, we define the performance measure related to con- straints: the cumulative constraint violation.
In the following, we introduce the offline CMDP optimiza- tion problem, which is needed define proper baseline to evaluate the performances of online learning algorithms. Specifically, we introduce the following linear program pa- rameterized by a reward vector and a constraint matrix G:
Definition 2.4 (Constraint violation). The cumulative con- straint violation up to episode T is defined as:
VT == max mm[m]
G P=)
MaX)EA(M)
rgg G 9
OPT, T
(I)
s.t.
Learning algorithms perform properly when they are capa- ble of keeping both the quantities defined above sublinear in T, namely, Rr o(T) and V o(T).
where q [0, || is an occupancy measure and A(M) is the set of valid occupancy measures.
For the sake of simplicity, in the rest of the paper, we will refer to ph as qt, omitting the dependence on transition unction P and policy π
Furthermore, we state the following well-known condition on the offline CMDP problem.
Condition 2.1 (Slater's condition). Given a constraint ma- trix G, the Slater's 's condition holds when there is a strictly feasible solution dº such that G dp < <0.
2.4. Feasibility
We introduce problem-specific parameter of Problem (1), called E [0, H). which identifies by "how much" Slater's condition is satisfied. Formally:
Notice that, in this work, we do not assume that the Slater's condition holds. Indeed, our algorithm still works when a strictly feasible solution does not exists. We refer to Section 2.4 for further details on this. Finally, we define the Lagrangian function of Problem (1), as follows.
When the constraints are selected stochastically, namely, they chosen from fixed distribution, the parameter p is defined as
Definition 2.2 (Lagrangian function). Given a reward vec- tor r and a constraint matrix G, the Lagrangian function R. of Problem (1) is defined as: G.G : (M) x R -R
T q..
p = max min
(EA(M) sE[m]
When the constraints are chosen adversurially, namely, no statistical assumption is made, the parameter p is defined as
Lr,la 1): =
(G q).
2.3. Online Learning Problem
P == max min min (EA(M) [E[ 3E|m]
[GT g),
As it is standard in online learning (Cesa-Biue Bianchi & Lugosi, 2006), we evaluate the performance of learning algorithms by means of the notion of cumulative regret.
Furthermore, denote the occupancy measure & A(M) leading to the value of p by q Intuitively, P represents the "margin" by which the "most feasible" strictly feasible solution (i.e., q²) satisfies the constraints. Finally, we state the following condition on the parameter p. which will guide the analyses of the performances of our algorithm.
Definition 2.3 (Regret). We define the cumulative regret up to episode T as follows:
T RT OPT
Σ TT
Condition 2.5. It holds that p 2 3 HV12mm.
Remark 2.6. Notice that, it is standard in the literature of primal-dual methods to assume thut p is constant in- dependent of T and directly include in the regret bound the dependence on 1/p (see, e.g. (Efroni et al., 2020; Liu et al., 2021; Wei et al., 2022; Müller et al., 2024)). Never- theless, when p is too small, this could result in suboptimal
where F. == Ey-R(F] if the rewards are stochastic, while :== = 1 Ei-re if they are adversarial, and G := Ba-gl [G]
if the constraints are stochastic, while G = 1 ET= Ge if they are adversarial.

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Algorithm 2 PDB-PS
tialized as the zero vector, the loss scaling factor to 1, the loss range 2, and, finally, the dual space is instantiated as [0. T1/4 (see Line 3). We underline that we force the dual space to be bounded in [0, TV/41" t only to deal with degenerate cases where Condition 2.5 does not hold. When Condition 2.5 holds, our algorithm guarantees that the Lagrangian variables are automatically bounded during learning. Furthermore, the algorithm keeps track of the max- imum loss range observed by the primal algorithm E, up to episode /. E [T], since the primal regret minimizer needs to dynamically update its belief on the loss range, in order to attain optimal regret bounds. The algorithm plays policy Te and observes the bandil feedback depicted in Algorithm I (see Line 5). Given the observed feedback, PDB- PS builds re-scaled Lagrangian loss for each layer h E [Ht] as:
Require: State space X, action space A, number of episodes T, confidence parameter 5 E (0, 1)
1: T [a|z)) f A
v(z,a) E x A
2: A1 - 0, 1
2
3: K + [
. +
II /AAV
4: fort= T do
5: Play policy T,, observe trajectory { an) O rewards (r, a;) and constraint violations
(gr,( M- for all i [m]
6: for h = 0, .,.,.,, H do
7: (x (S-0 an) H-H
m
8:
end for
9:
T++1 t Call FS-PODB UUD.AE((((E),CCCCC
(la(Th, an) ())) -,)
Act1 f lkk \x + n > k=o G. anl
111
10:
(1 :=) - Σ A,, an) - re re( 04). (2) ==1
11:
F'41 + 1+ M
12:
Ex41 + max { 2
13: end for
Notice that the loss built in Equation (2) can been seen as the Lagrangian suffered by Te for state-action pair (z, a), scaled by re to guarantee that the losses are always positive (see Line 7). This loss is properly built to feed the primal policy optimization procedure. Moreover, we underline that the feedback given the primal algorithm encompasses the trajectory and the maximum loss range observed, be- sides the loss built in Equation (2). Policy T++1 is returned by the primal algorithm (Line 9). We refer the reader to the next section for further discussion on the primal opti- mization algorithm. Algorithm/ 2 updates the Lagrangian multipliers using an online gradient descent update with loss -Eh En=o Ge(za, an. in the bounded dual space [0, /
regret bounds. In this paper, take different approach by providing bounds for any value of p. that is, whether Condition 2.5 holds or not.
3. A Policy Optimization Primal-Dual Approach
In this section, we provide the description of our algorithm. We resort to primal-dual formulation of the CMDP prob- lem, and we employ different regret minimizers to optimize over the primal space (namely, the policy space) and the dual one (that is, the Lagrangian variables space). Furthermore, our primal algorithm based on policy optimization ap- proach. Thus, the learning update is not performed over the occupancy measure space, but state-by-state along the MDP structure. This allows us to avoid solving a convex program at each episode (as it is the case in the algorithm by (Stradi et al., 2024b)). As concerns the dual, we employ online gra- dient descent (OGD). We remark that our algorithm does not require any knowledge of the Slater's parameter p. Indeed, as we further discuss in the rest of this work, can show that the Lagrangian multipliers automatically bounded given specific no-regret properties of the primal and dual regret minimizers.
H-1 G. anl
Aet1 + II A +
Σ h=
where Il is the euclidean projection over the space I.C and Gr[zn, as] is the m-dimensional vector composed by the violations of any constraint for the state-action pair (k))aa) (Line 10). Thus, the current loss scaling factor is computed as Te+1 + + || I|1 (Line 11). Finally, the maximum observed loss range E,+1 updated as E441 + max (E,, 21++1 since the range of losses observed by the primal depends on the Lagrangian multipliers (Line 12).
3.2. Primal Regret Minimizer
In Algorithm 3, we provide the pseudocode of fixed share policy optimization with dilated bonus UPDATE), (TSPOODB.UDDATE) namely, the update performed by the primal regret minimizer employed by Algorithm 2. Al- gorithm 3 builds on top of the state-of-the-ar policy opti- mization algorithm for adversarial MDPs (see (Luo et al., 2021)), equipping it with fixed share update (Cesa- Bianchi
3.1. Meta-Algorithm
In Algorithm 2, we provide the pseudocode of primal-duar bandit policy search (PDB-P3) PSS.
Algorithm initializes the policy uniformly over the space (see Line 1). Moreover, the Lagrangian variables are ini-
5

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
al., 2012). This modification allows to achieve the no- interval regret property, which, to the best of our knowledge, has never been shown for adversarial MDPs with bandit feedback. Thus, we believe that the theoretical guarantees of Algorithm 3 are of independent interest.
Algorithm 3 FS-PODB. UPDATE
Require: Observed trajectory {( ab) h==
H-- observed losses (L((Ts, (=)) loss range upper bound E,
1: if t = then
2: Pi f set of all possible transitions
Specifically, Algorithm 3 requires in input the trajectory traversed during the dearmer-nnirromment interaction, the in- curred loss functions, and the maximum loss range observed for any [T].' During the first episode, the algorithm initializes the estimated transitions space as the set of all possible transition functions (Line 2). Thus, at each episode the algorithm defines a dynamic learning rate x VTZ, (Line 4), where E, is the upper bound on the range of the loss functions up to t. This is done to control the differ- ent scales of the loss, due to the Lagrangian multipliers choice of the dual algorithm. Then, Algorithm builds an optimistic estimator of the state-action value function as:
3: end if
4: 1)t f 2HE,OVT 7 + CVT o 0 7
5: For all h - ....., H lnd (I, X x A:
H-1
Lup Σ (g)
5-h
Lth
a)(1,))+ t (, a) +9 [1(2.
where we let (,(2), u) = maxpeR g (2,, a) and 1e a) 1(IL 0r, = a}
For all (2,0) E X x A:
LeA
Qr(2,a)== == (.(2, a) +7 le(x,a).
3yHE HE (7, T (z, +7
(x(x) E (-1r(
where (1( = 1f a, = o} and Lrh Ej=n az) is the loss incurred by the algorithm at episode t starting from layer h. Indeed, since (1 = maxper, q 8.5 (xx ax), a and y is a positive quantity, Q1 a) results in an optimistic estimator of the state-action value function (Line 5). The optimistic estimator is employed to control the variance of the loss estimation and, thus, in order to achieve high-probability results. Finally, notice that the state-action value function (as the estimated one) is com- monly used in policy optimization as allows optimize efficiently state-by-state In addition to the estimated state- action value function, Algorithm 3 defines a dilated bonus similar to the one introduced by Luo et al. (2021), which is then incorporated in the final objective of the optimization update. The bonus is defined as:
Br(x,a) t- bb())+
(1 H PEP.
max E P(12)(1) Bawnelll [Ba(z', (00xz',') a')l
where we let q, (I. = min minper, q ( and Be(xH, a) == 0 for all a A
7: For all (2, E X A:
(a+1()(x) + (1 o)wr(()z)) - (Qi(t,,)) (Ql
wi(d'(z)e wi(d'lr)e- ((((e))) Be(,'o)))
+ A
a'EA
(x+1(a(x))
(a41) Ev'Es We+1 (a'(z)
Be(r, a) == be(x)+
1 max (1) Bawa, (e (2 ,a)),
1
H
PEP.
P1+1 - CPANIIONNNDDATE((A an) MH
where the term (x) depends on the uncertainty on the transitions estimation and the range of the losses, while the term (1 + +)) attributes more weight to the deeper layers, so to incentivize exploration (Line 6). The weights asso- ciated to any action are computed employing the so called fixed share update (Cesa-Bianche et al., 2012); specifically,
the weights are computed as the convex combination be- tween the uniform weight and the solution to optimization step x wy (alzr)) (nQ. (x...). The policy is simply computed as normalization between weights (see Line 7). Notice that the convex combination mentioned above is cru- cial to bound the regret for each interval (that is, to attain the no-interval regret property). Indeed, it guarantees lower bound for the value taken by the policy in each available ac- tion at each episode, and, thus, for all intervals [t, tol C [T], it allows to find a nice upper bound for the Bregman diver- gence D (T (a); Te, (-la),, for all policies n. Finally, the
'While the input of Algorithm 3 may seem different from the standard bandit feedback received in adversarial MDPs, this is nor the case. Indeed, it is sufficient to set E. = 1 for all & e [2'] to achieve the same guarantees attained by Algorithm 3, in the Lagrangian formulation of CMDPs, in standard adversarial MDPs.
"As shown in (Jin et al., 2020). (z, a) can he computed efficiently by means of dynamic programming.
6

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
estimation of the transitions is updated given the trajectory traversed in the MDP (Line 8). This estimation is standard in the literature. Thus, we refer to (Rosenberg & Mansour, 2019b) for further discussion on the use of counters and epochs to estimate a superset of the transition space Pt.
86, Algorithm FS-PODB allains:
, SO (En. + Et, vT
l 30-1 41
where the regret can be computed with respect to any policy function π. X - A(A).
3.3. No-Interval Regret Property
As it is standard for online learning algorithms, Reg scales as the loss range, shown by the dependence on Et ,ta that is, the maximum possible range of losses in the interval.
When the Slater's parameter p is known, the only necessary requirement for the primal and the dual regret minimizers is to be no-regret. Thus, is sufficient to bound the Lagrangian space so that ||^ح v (H//)) to attain sublinear regret and violation. Nevertheless, knowing p is generally not possible in real-world scenarios. In order to relax the assumption the knowledge of p. we require our primal and dual regret minimizers to have the no no-interval regret property.".
3.4. Bound on the Lagrangian Multipliers Dynamics
Next, we show that, given the no-interval regret property of the primal and the dual regret minimizers, it is possible to show that the Lagrangian multipliers are automatically bounded during learning. Notice that this bound is necessary since any adversarial regret minimizer needs the loss to be bounded to achieve the no-regret property. Thus, since the rewards {re)ī=1 and the constraints {G,)T=1 are assumed to be bounded for all episodes, the problem of bounding the loss suffered by the primal algorithm becomes the problem of bounding the Lagrangian multipliers {
First, we introduce the interval regret as follows.
Definition 3.1 (Interval regret). Given an interval of consec- ulive episodes [l,,..., [2] S [1....,, Ti, the interval regret with respect to general occupancy q (and the associated policy T) and a sequence of loss functions { with 4 x x A + [0, K]. with K > 0, is
Theorem 3.4. Under Condition 2.5, any 8 (0, 1). with probability at least 1 - 116, it holds:
f2
R (1) = Σ
l, (gt 9)-
|el SA [T+]+
In the following, we omit the dependence on the general occupancy measure when is clear from the context. Thus, given Definition 3.1, we are able to introduce the no-interval regret property, as follows.
where A
112mH p²
The general idea behind the proof is to compare, for every interval [t] C [T]. the upper bound to - - ef g: obtained through the regret of the dual algorithm with the lower bound to the same quantity obtained through the pri- mal interval regret, where we define the non-scaled La- grangian loss Ef as the vector composed by
Definition 3.2 (No-interval regret property). An algorithm attains the no-interval regret property when for any interval of consecutive episodes [f1....,1) 12] C [1 and with respect to any valid occupancy (and the associated policy T), it holds
= Σ Sesgna a) re((x,
R S SŌ(T)).
for all (z, a) E X x A and for all t E [T]. The resulting inequality leads, by contradiction, to the desired bound. In this sense, a fundamental requirement for the proof is that the regret guarantees for both the primal and the dual algorithm hold for all subsets of episodes.
Intuitively, the no-interval regret property guarantees a more stable learning dynamics over the episodes.
When full feedback is available, as for the dual algorithm, it is sufficient to employ OGD-like updates to attain the de- sired result. This is not the case when the feedback is bandit. Nevertheless, given that we use a policy optimization proce- dure and the fixed share update, we build the first algorithm for adversarial MDPs with no-interval-regret. We state the result in the following theorem.
4. Theoretical Analysis
In this section, we prove the best-of-both borh-world guarantees attained by Algorithm 2.
Theorem 3.3. For any 8 E (0, 1), with probability at least
4.1. Stochastic Setting
What require is generally known in the literature the weak no-interval regret property. For the sake of simplicity, in our work, we introduce only the weak property.
We first study the performance of Algorithm when the constraints are stochastic.

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
In such a setting, algorithm handle two scenarios, In both of them, employing a primal-dual analysis shows that both the regret and the violations are bounded with order ((VT) times the maximum value taken over all episodes of the Lagrangian multipliers, i.e. max) wel1- In the first scenario, Condition 2.5 holds and thus we can apply Theo- rem 3.4 to show that the Lagrangian multipliers are bounded. In such case, mr) Aella can be easily bounded by A. When Conditions 2.5 does not hold, need to resort to the bound of Lagrangian multipliers derived by the instantia- tion of OGD decision space, leading to (TT3/1) regret and violations bounds.
In such setting, can show the following result. Theorem 4.3. Suppose Condition 2.5 holds and the con- straints are adversarial. Then, for any 8 E (0, 1), Algo- rithm 2 attains:
T
P 1222 D+H -
OPT.T),
OPT
V1 5
with probability at least 145 when the rewards are stochastic, and with probability at least 138 when the rewards are adversarial.
4. 4.2.1. A WEAKER BASELINE
Specifically, when Condition 2.5 holds, the Lagrangian mul- tipliers are nicely bounded by A.
In this section, show that the impossibility result by Man- nor et al. (2009) can be circumvented by adopting different baseline in the regret definition. Precisely, we compute the weaker baseline as the solution to the following linear pro- gram:
Theorem 4.1. Suppose that Condition 2.5 holds and the constraints generated stochastically. Then, for any 8 E (0, 1), Algorithm attains:
RT S ( VT 15 (A(TT)
FTg G Vt [T].
max s.t.
OPT
with probability at least 1 146 when the rewards are stochastic, and with probability at least 1 138 when the rewards are adversarial.
Notice that, in the previous sections, we allow the opti- mal policy q²' to satisfy the constraints on average, i.e. -t=1 G, q"' I O. In such case, the set of feasible policies is much smaller than the one associated with the weaker baseline, that is, when feasible policy must satisfy the constraints at each episode. Given the new baseline, can rewrite the regret as R₃ == TOPT -E=," q:
When Condition 2.5 does not hold, can still use the bound forced by Algorithm 2 on the dual space. Therefore, the Lagrangian multipliers are bounded by m/ leading to the following result.
Theorem 4.2. Suppose that Condition 2.5 does not hold and the constraints are generated stochastically. Then, for any ò (0, 1), Algorithm 2 attains:
When the regret is computed w.r.t. the weaker baseline, we can recover the same theoretical results of the stochastic setting. Precisely, when Condition 2.5 holds we have the following result.
Rr S Ō (T%
Vr S Vo=00(T)) (T
Theorem 4.4. Suppose that Condition 2.5 holds and the constraints are generated adversarially, Then, for any 8 e (0,1), Algorithm 2 attains:
with probability at least 1 - 116 when the rewards are stochastic, and with probability at least 1 108 when the rewards are adversurial.
Rr S (Ō(AT))
VT S 5
4.2. Adversarial Setting
with probability at least 135 when the rewards are stochastic, and with probability least 1 125 when the rewards are adversarial.
We then study the performance of Algorithm 2 when the constraints are adversarial.
Notice that, in such setting, there exists an impossibility result from (Mannor et al., 2009) that prevents any algorithm from attaining both sulinear regret and sublinear violations. algorithms in constrained settings focus on attaining sublinear violations and fraction of the optimal rewards (see e.g., (Castiglioni et al., 2022b; Stradi et al., 2024b))
We conclude the section by analyzing the scenario in which Condition 2.5 does not hold.
Thus, ofst-of-both-woee
Theorem 4.5. Suppose that Condition 2.5 does not hold and the constraints are generated adversarially. Then, for any g E (0, 1), Algorithm 2 allains:
Rr S Ō (T% VT (T(
*Attaining the no-a-regret property, that is, being no-regret w.r.t. fraction of the optimum, achieving competitive ratio, and guaranteeing fraction of the optimal rewards are used as syn- onyms in the literature, since any of the aforementioned guarantces can derived by the others.
with probability at least 125 when the rewards are stochastic, and with probability at least 1 118 when the rewards are adversarial.
8

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Intuitively, Theorems 4.4 and 4.5 can be proved by the fact that playing the optimal policy guarantees small violations independently on the episode the optimum is chosen. This is not the case for the stronger baseline, since playing the optimum in some episodes may lead to arbitrarily large constraint violations.
23 Jul 2022a. URL httpt:ttppooceeeeeeeeeeee
mmlr.
press/ svassvvll 62/ woccastigglonii222222. html.
Castiglioni, M., Celli, A., Marchesi, A., Romano, G., and Gatti, N. A unifying framework for online optimization with long-term constraints. Advances in Neural Informa- tion Processing Systems, 35:33589-33666 2022b.
Acknowledgments
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
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 NexIGenerationEU 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 Al for Sustainability, No. 101120237).
Cesa-Bianchi, N., Gaillard, P., Lugosi, G., and Stoltz, G. Mirror descent meets fixed share (and feels no regret). Advances in Neural Information Processing Systems, 25, 2012.
Ding, D., Wei, X., Yang, Z., Wang. Z., and Jovanovic, M. Provably efficient safe exploration via primal-dual policy optimization. In International conference on artificial intelligence and statistics, pp. 5304-3312 PMLR, 2021.
Impact Statement
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-7404, 2023.
This paper presents theoretical results and has the goal of advancing the field of Machine Learning. There are no potential societal consequences of our work which feel must be highlighted here.
Efroni, Y., Mannor, S., and Pirotta, M. Exploration- exploitation in constrained mdps, 2020. URL https: / //aaxivvorgg/aaeeee 2200..000302 02189.
References
Altman, E. Constrained Markov Decision Processes. Chap- man and Hall, 1999.
Even-Dar, E., Kakade, S. M., and Mansour, Y. Online
markov decision processes. Mathematics of Operations Research, 34(3):726 2009.
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: httpsss///ccceee.......m neurips ww/ppapee/00///ELL.... 0aa6222cobb624435400000000000000 pdf.
Ghosh, A., Zhou, X., and Shroff, N. Towards achieving sub- linear regret and hard constraint violation in model-free RL. In Dasgupta, S., Mandt, S., and Li, Y. (eds.), Proceed- ings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 1054-1062, PMLR, 02- 04 May 2024. URL https: pttp///erceeee...eeecee//oe.. mllr. press/v22 38 ghw.h24..222. html.
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.
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.
Bai, Q., Aggarwal, V., and Gattami, A. Provably efficient model-free algorithm for mdps with peak constraints. arXiv preprint arXiv:2003.05555, 2020.
Isele, D., Nakhaei, A.. and Fujimura, K. Safe reinforcement learning on autonomous vehicles. In 2018 IEEE/RS In- ternational Conference on Intelligent Robots and Systems (IROS), pp. 1-6. IEEE, 2018.
Castiglioni, M., Celli, A., and Kroer, C. Online learning with knapsacks: the best of both worlds. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Confer- ence on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 2767-2783. PMLR, 17-
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.).

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Proceedings of the 37th International Conference on Ma- chine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4860-4869. PMLR, 13-18 Jul 2020. URL httpp:: wttpltttttpppcceedeiaeeeee /ttppceeeednggs..cp// mwr ptw...ggggs.....sss///.//. v11 v119/jin20c. html.
Rosenberg. A. and Mansour, Y. Online stochastic shortest path with bandit feedback and unknown transition function. In Wallach, H., Larochelle, H., Beygelzimer, A., d Miché-Buc, F., Fox, E.. and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019a. URL https://proceeddiin neurips. https//aappee/os//i..... a 08 00472cc5i5cc44c22277733388888883 pdf.
Liakopoulos, N., Destounis, A., Paschos, G., Spyropoulos, T., and Mertikopoulos. P. Cautious regret minimization: Online optimization with long-term budget constraints. In International Conference on Machine Learning, pp. 9944-3952. PMLR, 2019.
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 htttts::/proceeteeee rosenbergl9a. html.
Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. Learning policies with zero bounded constraint viola- tion for constrained mdps. Advances in Neural Informa- fion Processing Systems, 14:11333-7799, 2021.
Luo, H., Wei, C.-Y., and Lee, C.-W. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931-22942, 2021.
mll wwt.mm.................
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.
Mannor, S., Tsitsiklis, J. N., and Yu, J. Y. Online learn- ing with sample path constraints. Journal of Machine Learning Research, (0(20))569-590 2009, URL http: s/jmlr.ome www.a/r.rrgpppprr//eeeee pwppps/pplllllaea 00a00/mmmnooroommmm 0 9a html.
Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Learning adversarial mdps with stochastic hard con- straints. arXiv preprint 2:Xiv:2403.0362 2024a.
Müller, A., Alatur, P., Cevher, V., Ramponi, G., and He, N. Truly no-regret learning in constrained mdps. In Forty-first International Conference on Machine Learn- ing, 2024.
2024a.
Stradi, F. E., Germano, J., Genalti, G., Castiglioni, M., Marchesi, A., and Gatti, N. Online learning 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 Learning, volume 235 of Proceedings of Ma- chine Learning Research, pp. 46692-46721, PMLR, 21- 27 Jul 2024b. URL https: / /ptpceeeccceeeeneeeeeeeee mllr. pzess/v235/strad// html.
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.
Orabona, F. modern introduction to online learning. CoRR, abs/1912. 2019. URL httt:://axxii org/abs 11t.:./991..111111
Stradi, F. E., Lunghi. A., Castiglioni, M., Marchesi, A., and
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Gatti, N. Learning constrained markov decision processes with non-stationary rewards and constraints, 2024c. URL abs / / 14372.
ht /tap::///arxiii
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: uttpsssss//proeeeiiggg /ptp/eeeecce..... cc houripps.ccpaper//20///eee. ae me5236227776555e9ccc2266.. 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.
Wei, H., Liu, X., and Ying, L. Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In Camps- Valls, G., Ruiz, F. J. R., and Valera, (eds.), Proceedings
10

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
of The 25th International Conference on Artificial In- telligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 3274-3307. PMLR, 28- 30 Mar 2022. URL https: /ptpcceeccceggssse//ee//////s.se mllr. press/ve /v13svv155 51 we 22a html.
Wei, H., Ghosh, A., Shroff, N., Ying, L.,, and Zhou, X. Prov- ably efficient model-frec algorithms for non-stationary cmdps. In International Conference on Artificial Intelli- gence and Statistics, pp. 6527-6570. PMLR, 2023.
Wei, X., Yu, H., and Neely, M. J. Online learning in weakly coupled markov decision processes: A convergence time study. Proc. ACM Meas. Anal. Comput. Syst., 2(1), apr 2018. doi: 10. 10.1145/3179415. URL https: / /doi. org 3179411
Zheng. L. and Ratliff, 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: https::/ppocteeeeeeeeeee /ttp///rroeeensss.c/////////s/se mlr. press/v1201 2heng20a html.

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Appendix
The Appendix is structured as follows:
In Section A, we provide additional related works.
In Section B, we provide additional notation employed the rest of the appendix.
In Section C, provide the events dictionary.
In Section D we provide the theoretical guarantees attained by Algorithm 3. Precisely, we provide the complete version of the primal algorithm (see Algorithm 4), and analyze the related performances.
In Section E, we provide the theoretical guarantees attained by the dual algorithm.
In Section F, we provide the analysis to bound the Lagrange multipliers during the learning dynamic.
In Section G, we provide the theoretical guarantees attained by Algorithm when the constraints are stochastic.
In Section H, we provide the theoretical guarantees attained by Algorithm 2 when the constraints are adversarial.
In Section we provide the theoretical guarantees attained by Algorithm when the constraints are adversarial and the baseline is computed w.r.t. the policies that satisfy the constraints at each episode.
In Section we provide technical lemmas employed in our work.
In Section K, we provide auxiliary lemmas from existing works.
A. Related Works
In this section we provide further discussions the works closely related to ours. We first provide some works in the field of unconstrained online MDPs (see (Auer et al., 2008; Even-Dar et al., 2009; Neu et al., 2010) for some initial results on the topic). The setting studied in these works generally differentiates the problem based on the nature of the losses (either stochastic or adversarial), the knowledge of the transition probability, and the nature of the feedback. Usually two types of feedback are considered: in the full-informn information feedback model, the entire loss function is observed after the learner's choice, while in the bandit feedback model, the learner only observes the loss due to the chosen action.
Azar al. (2017) study the problem of optimal exploration in episodic MDPs with unknown transitions, stochastic losses and bandit feedback. The authors improve the previous result by Auer et al. (2008) designing an algorithm whose upper bound on the regret match the lower bound for this class, Ö(VT). Rosenberg & Mansour (2019b) studies the setting of episodic MDPs with adversarial losses, unknown transitions, and full information feedback. In this case the authors present an online algorithm exploiting entropic regularization and providing a regret upper bound (VTT). The same setting is investigated when the feedback is bandit by Rosenberg & Mansour (2019a) who attain a regret upper bound the order of O(1%/4). which is improved by Jin et al. (2020) by providing an algorithm that achieves in the same setting regret upper bound of ((VT). Finally, Luo et al. (2021) provide optimal policy optimization algorithm for adversarial MDPs with bandit feedback.
In case of constrained problem, an fundamental result is presented by Mannor et al. (2009), who show that it is impossible to attain both sublinear regret and constraints violations when both the losses and constraints are adversarial. To overcome such an impossibility result, Liakopoulos et al. (2019) study a class of online learning problems with long-term budget constraints that can chosen by an adversary and they define a new notion of regret. The new learner's 's regret metric introduces the notion K-benchmark, i.e., comparator that meets the problem's 's allotted budget over any window of length K. Castiglioni et al. (2022a;b) the first to provide pesst-of-both-worr/ algorithm for online learning problems with long-term constraints, being the constraints stochastic or chosen by an adversary.
Constrained problems have been also studied in the context of CMDPs; however almost all previous works focus on the setting where the constraints are chosen stochastically. Wei et al. (2018) study the case of episodic CMDPs with known transition proabability, full-feedback, adversarial losses and stochastic constraints. The algorithm presented by the authors attains an upper bound both for constraints violation and for the regret of the order of ((VT). Zheng Ratliff (2020)
12

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
present, in the setting of stochastic losses and constraints, where the transition probabilities known and the feedback is bandit, upper bound on the regret of their algorithm of the order of O(T9/t), while the cumulative constraint violations is guaranteed to be below threshold with given probability. Bai et al. (2020) provide the first algorithm to achieve sublinear regret when the transition probabilities are unknown, assuming that the rewards are deterministic and the constraints are stochastic with a particular structure. Efroni et al. (2020) study the case where transition probabilities, rewards, and constraints are unknown and stochastic, while the feedback is bandit. The authors propose two approaches to deal with the dilemma episodic CMDPs guaranteeing sublinear regret and constraint violations. Qiu et al. (2020) provide primal-dual approach based on optimism in the face of uncertainty. This work shows the effectiveness of such an approach when dealing with episodic CMDPs with adversarial losses and stochastic constraints, achieving both sublinear regret and constraint violation with full-information feedback. Liu et al. (2021) study the case where the rewards and the constrained are stochastic with sub- gaussian form, and it achieves regret ((VT) regret and zero violation when a strictly safe policy exists and it is known and a bounded violation when the strictly safe policy exists but it not known a priori. Ding et al. (2021) design a primal-dual policy optimization no-regret algorithm for CMDPs with stochastic rewards and stochastic constraints. Wei et al. (2022) design model-free, simulator-free reinforcement learning algorithm for CMDPs that achieves regret of order O(T*)s with zero constraints violation, assuming the number of episodes to be exponentially large in 1/p. Wei et al. (2023), Ding & Lavaei (2023) and Stradi al. (2024c) consider the case in which rewards and constraints are non-stationary, assuming that their variation is bounded. Thus, their results not applicable to general adversarial settings. Ghosh et al. (2024) attain sublinear regret and sublinear strong constraint violation, that is, not allowing for cancellations. Their algorithm works when both the rewards and the costs are stochastic; thus, these results are not applicable to our stochastic setting, as we allow the rewards to be adversarial. Similarly, Müller et al. (2024) study the harder problem of bounding the regret and the constraints violation without allowing cancellation between episodes. They were the first to prove a sublinear regret guarantee without error cancellations for an efficient primal-dual algorithm in the online setup. Stradi et al. (2025) attains optimal bounds in the same setting. However the whole analysis of both works is structured considering the feasibility parameter p as a constant. Stradi et al. (2024a), in the setting with adversarial losses, stochastic constraints and partial feedback, achieve sublinear regret and sublinear positive constraints violations. Finally, Stradi et al. (2024b) propose the first best-of- both-worlds algorithm for CMDPs, assuming full feedback on the rewards and constraints.
exploration-explottan
B. Additional Notation
In the following section, we introduce some useful notation from policy optimization. First, define the value function V (z f), for policy æ, state and generic function f that assumes values for each state E X and for each action a E A. Formally,
H Σ
T x: f) :
(x,, ~ (()2)), ~ P(-10)-1, )=
where h(()) is the layer such that x E Xn. Notice that the value function can be written using the occupancy measure qT generated by the policy and the transition probability P V (zo: f) Σx,a g az,,) a). We introduce also a Q-function of a generic function f as:
Q(2 = f(z, a) + -ErAP()))) [V* {
v²(x;)) = Bawn(112) (x;,a)))) ("(HH:f)= 0
In addition we will use the notation Qe(2, a) to indicate the Q-function computed with respect to the function &, Lee. Q(xaa;)))
C. Dictionary
In the following, we provide the definition of different quantities which will be employed in the rest of the appendix. This is done for the ease of presentation.
13

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Quantity E
(12 (2-4++1) CVT
U3Et, 1
11222 U,, CVV
+ VT,
CVT
where:
U1 = 6H In
- U2 = 9H A
Us H. In
HT
U4 = 30 2
2|A|| in TIX
-
With probability at least
46 it holds Ry
bn W1, (T) 1 14 < 12 < T by Theorem 3.3.
Quantity 8 (0):
(Q)):
(0 = D |
D2n - ti + +1),
where:
Di 1
D2 m 2
It holds R.P R..,,(0)) s (0) (0)) Vh E [T] 1t S T by Theorem E.I.
Quantity 0g.
= BB (t2 - t1+11 -1),
where:
Bi 2H 2H 2 V In )
Given a E A(M), with probability at least 1 5 it holds case of stochastic constraints Eis gGTT--G' 9) s EG by Azuma-Hue Mouna--ooffdiigg inequality.
Quantity El
Eh = =Fi - 41 +1,
where:
Fi H 2 2m
(-).
With probability at least 1 8 it holds Lt=h, Ex, (x, < tg and with probability at least 1 8 it holds Eie,, (9 a) I,(xaa) a)) s El Eg,t by Azema-Hoefiding inequality.
Quantity C::
C = 252 A|H
Quantity D:
84672mH1 2
=3
14

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
D. Omitted Proofs for The Primal Algorithm
this section we study the guarantees attained by the primal procedure, namely Algorithm 4.
Algorithm 4 FS-PODB
Require: X, A, = J.C. C
1: Pi + set of all possible transitions
2: (a| = TAT EXxA
3: E 1
4: 7 CVT
5: for = ....., T do
.....,Tor 6: Play Te, observe { an) )==)
H-1 losses (Le(Tn, an) M and E,
7: TK 2HE,CVT
8: For all h = ..... HI 1 and (x,a) Xy x A:
H-1
Lr
Σ j=h
(( an)
Luh
(1( = [1(2,0) 0) +
11 (1
where (2, a) = -maxq
P.me P a) and (.(x, a) 11x2,11 = 2, 0r, = =a).
PEP:
9: For all (I, E X A:
3yH + HE, (x a) - 2 (0,
bx(x) = (- (-Ia)
(1 +7
Bx(x,a) = B((x,a)=b(()) bb(x))
1 1 max - BawT, (on [Bel'', ,a)]
H)
PEP.
where 2, min P. P. ( (x, and B((HH,)) for all a.
PEP.
For all ax) E X A:
(2+1(a/z) (1 - o)wr(alr)e (il-ooooddd)eeem((aa)a---------
Σ
wr(a'|z)e (Q(l)))))
[A
Wr+1
(t+1(a/+)= = Eore (a'1)
11: PH+1 <-TRNNSTTTON.UPDDTE((II.. an)
12: end for
Theorem D.I. For any 8 E (0, 1), Algorithm 4 attains, with probability at least 1 48 and for all [t,,..., tal C [T]:
Σ g" (x)
(T((a))) - (alx)) (x, (x(x
t=11
ta v (e) Σ q (1)
((T)
aol all 12 E (T] s.1. 154 S ta S T and where Eni 2 max max,,a (xx
15

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Proof. In the of the proof, we will refer L, to maxfeld maxлe[H] Lr, and L1,,2 max..( maX b7 therefore, by definition it holds L2 I HE, for all t [T]. As first step, we decompose En o (x) ties:
Ea (Te(a]z)- - =a(ax)) (Q7 (z, Be(r, a)) in three different quanti-
(g((2) (x)
(Te((a/))) (
(Q7 (I, (QF
(x,,
t=(=
tg
Σ q (x)
( - क (a|z)) (Q((z, a) - (((
1=
Σ (x)
Te (a(a)) (Qf (x, (2))
t=11
Σ
(x)
"t (u/x) ())(z,a) - Q7" (z,
tm
which we proceed to bound separately.
Bound on ! The quantity of interest can be bounded after noticing that Algorithm employs a slightly modified version of OMD. In fact, recalling the definition of TT, we can write:
w (a/
<<41(a|x)
Ev Wo+1(a' (1)
(1 - o))e(alz)e m (l(ta))B + [ En'es -iddal))m((i (1
EvEA Sre'li(a ne (Q)(z,aa)) (((,a")) Bz(z,a))
(Q(()))) En (x(a( (( (Q((.,)))) + 0 A
= (1
From now on we will refer to se(alz)e (
E [a(((zz)e (2t as 1 (2, a). Thus,
(a|=) (1- ( o |A]
Calling v--)) the negative entropy function defined as (x(((+z)) = Ea ((a[=)) In (I(ala)), by standard analysis (e.g. (Orabona, 2019)), it holds:
E (Q - Be( m(lax)) 1 1 (D
#+1(--= arg min
x(I))E((A)
where Do is Bregman divergence w.r.t the negative entropy function v()) Thus, for all T(-2x) it holds nc E. (z) B, (z a)) (π(a|z) - (2) + (Vo(+++(((1)) (=((x(()))) x(1=)) #+1(++z) 2 0. So, for
all (-|2r) the following holds:
n.(Qr(,,)) -) - B,(x, Te - T-112))
= ( - (x. + V V #+1((+))) -(1x))
n (2,,)) :) - B,(x, :), Te (+(x)) - #+)))1=))
16

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
+ -V (+|x) 7 (-1a))
s (n Bx(,))) me --1))) (+1(112)))
+ -(V(((+1((1))) (((
$ ( - (z) - DD (
+ + .) - Bz ), ne (.1x) (-+1(111)))
(3)
(D((((())::m((11))) (1) + m Σ ((((x,a)-B((xa)a) (a(2)))
(4)
where Inequality (3) and Inequality (4) are based on the proofs of Lemma 6.6. and Lemma 6.9. in (Orabona, 2019).
Additionally we can show that for all E [T]: ( D (
S o In(IA]). Indeed,
Do (T((11)) - De (x(()x);
D (T<()));;( (1 (-)x(-12)) + omid)) Do (1((11);;(((11))))
S oD (T((IZ); DD (e(la));(((ll)))
S In(())),
where the last inequality holds since D (-<(-²)) (+ 2 and
T(alx)
D (-]====;==
Σ (alz)) In aEA
π -| (a)x)
< Σ <a|l:) In
π गंل (al xr)
<a|x:) In ([4))
In([Al).
Notice that with we refer r T to the vector strategy in [0, 1] 1| with all elements equal [Ą--
Moreover we bound D& (TT( Te, (-1z)) since Te, (a|æ) = (1 o )ee, (a|z) + o ( 2 T as follows:
(aax))
()) = Σ T (a|z))
Te, (a)xx
< (alp:) In
Te, (alx))
||A]
S Σ
(al In
aEA
[A]
Putting everything together we have that:
① Σ (x)
(al()) (alx)) Ba(a,a))
(1(r)) (112:)
l2
( (111))
- Σ (x)
m
m
M++1
x
1=
17

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
+
Σ q
Lh 2
()((,,a) Bi,,,)) Te Te(alx)
(5a)
x
t=
( (+1))
-
$
(o()
71.
1=1+1
Σ
q
(x)
1/t
(Q((z,a)-B(() a)) 2
TT(a/x)
(5b)
2
z
t=
In
[Al
1/
In([Al)
+ [g(())
(x)
12 Σ
1/t
(Qi(o,a) -B((o,)) Te(alz)
(5c)
M/2
1=
|A]
In
oT (Inn(IA)
Eg((T)
42
11
(Qalr,a)-B((e)) - <e(alz)
T]t
1/12
2
t=
In (IA[T)
In((Al)
(x)
Σ
12
Th 2
2 (ōr(r;a) Bi( Te(a(z),
Th
Th
where 7. Inequality (5a) holds by Inequality (4). Inequality (5b) holds since 7:12 mh for all t E [2]. and Inequality
2
(5c) holds since 7t, S t7 for all t in [ti + 1....,tt) tz). Focusing now on the last part of the right term, with probability at least
1 25 the following holds:
Σ
Tt (Q((z,))-B((e -)( <<(a/z)
2
$
11t
9" (1)
+ Σ n ΣΣ
a
(1)
(6a)
1=0
1=1
Σ " ΣΣ
q" (a)ma(a)))
Te(2,a) +
Σ T1e ΣΣ
1 (0)
(6b)
(q,(1,a) +7)
t=
t=
12
((x)) [x
12
< L
Σ
mL
7t Σ Σ
(1
q
(6c)
(1, (2, +7
1=11
1=11
a
1/
(a))) (I,
Loe In
1T
5 2H
(x,
(5, a) +7
2
8
t=
m1 Σ
Σ
q
(x)
(6d)
t=
+ ILnnle In
HT
<
9" (x)xe(a(z)
(17 a) + 7)
2
8
t=1
2
1
9 (a)m((
(6e)
2H
t=
E
Be a)
I
HT 8
3Σ Σ 1= 2
9 (z)x(())))
+
In
(I,
a) 77)
2H
2
where Inequality (6a) holds since (a- - 6)2 < 2a² + 262, for all a, E R, Equality (6b) holds by definition of Q( a). Inequality (6c) is motivated by the fact that Lr, S L by its definition, Inequality (6d) holds with probability least {(())_((a=))
1 - 8 by applying Lemma J.4 and taking (z, g (=)m(aa))) since 9.12,a)7 < 1 and considering that by definition n) E = 2/ and finally Inequality (Ge) holds since g, (2, a) 2 (x a), ((x E X A, E [11 ...))))] with probability
9.2z,))7
18

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
least 1 à by Lemma K.2 and by Lemma J.1. Setting 7 2n, H we can conclude that, with probability least 2d, is bounded as:
4HE 11 In([A[T)
H In +7 2
HT 8
- 2(q a) +
Be a) 2H
>E 1=1
(2)))((())
Bound on ④ To bound ② we employ the same approach as in (Luo et al., 2021). First we define V, as Y, = q- (z) (alz))( a), for E [T]. Now since Ei= Y, is a martingale sequence, we apply Freedman's 's inequality. First notice that under the event P E Pt(t) for all t e [
E E|y
S E,
Σ
9 (0000
Σ q (()m)
$ E,
HE,
Σ l (m)(0)))
L2,n (7, a) + 7)2 at (2,
(a)
HL²
d (a)
aF a) +y
Thus, thanks to Lemma J.3, since |Y/ S H supp (z) < for all 1,,22 <<4 4
HL, with probability at least 1 - 5 it holds simultaneously
< l2 < T:
f2 [Y]
HL. +
H log
(2
Y) < H t=f
ΣΣΣ
q (x)m
(. +7
8
:=11
We notice also the following result with probability at least 1 for all t E [T]:
B[y]]
ΣΣ (1)
-E
(x
E E (((
1
7, (3, (1)
(e 4) (z, a) +7
(())))
(e a) +7
(7, a) - 2, (2, a)) +7
Σ E (H)
7, 7 t)
Finally we can bound ? with probability least 25 as follows.
Σ q
Σ (a(=))
12
12
[Y] Yi)= + Σ
ΣΣ
q (4) E[Yi]
t=
x
19

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
1/
(7,(2,a) (
2z a)) 2g
H
T
q
+
In
ax) +
8
1=41
Bound on
With probability at least 1 - 28 it holds:
11 to
HT²
Σ q (x)
Σ x" (alz) (Q1(2,0) (Q)(2.0)-Q)((2 (x,
In
2y
by Corollary J.5.
Conclusion of the proof
Finally we notice that, with probability at least 48, we have the following result.
(#((a)))
x" (alx)) (QT (I) Ba(r, a))
!
t=
H t2
HT2
6H In
H A
$ 7
In
+
5
t
[,,3 + ((, a) 2, (2,,)))) Be(x, a)
+
Σ
(a/a)
+
(1, +7
H
2.0
This concludes the proof.
Theorem 3.3. For any d E 10, with probability at least - 86, Algorithm FS-PODB altains:
R1 S Ō (En.sVVT VT E 12-t1 t1
VT )
where the regret can be computed with respect to any policy function w : X + A(A).
Proof. By means of Theorem D.1 and by Lemma J.2 we have that with probability at least 46:
HEn,2
HT
6H
H|A[
R S 2
+
m (xo: bz).
We can bound ΣT= Te (xo bi), with probability at least 46, as:
mi bt)
(2, (x( 33E
Piie (r.
(,(,,a)+7
2.a
H3, (v((2,a)-g((6 a)) +37)
(z, - a)) + 3E, 7H(2 - 11 + -1+1)X111
tm 3.a
H
TIXPA
4H 2
2n
+ GE H |
2T ATI In
1 |||||| - +1,,
20

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
where the second inequality holds under the event q ( (xr, a) S @ (z, a) all (x, a) X and for all t (7) and the last inequality uses Lemma J.6. Thus, with probability least 1 86, holds:
R
HT
6H 11
T
" 2
In
+
In
+ ,, |X| |T| In
+
7
8
5
+ +
H (t2 -1 +1
HE .2 In
HT
+ +6H 2 111.2C
2C T
8
(TIX[AA
(12 11 + CVT
+-30 H 1X12 12
9H XIAA
(t2 - 1 1)
1
UV
Ug
+ U
CVT
CVT
=E :4
which concludes the proof.
E. Omitted Proofs for the Dual Algorithm
Theorem E.1. When employed by Algorithm 2, online projected gradient descent (OGD) attains:
l2 20- X.)
1r - + [t2 + 1)mH².
R
(A)
Σ G,(on, ap)
21
t=h
Proof. We proceed to prove the theorem following (Orabona, 2019). Indeed, it holds:
H-
12 (A)
(A
Ac)
G. Ge an)
t=
h=0
|r,
A113
fo
Ge an)ll
21
2
t=th
h=0
1r
2112
7
t2
11
Gellenaah) an)
2n
2
t=
|A
A113
la
Σ
mH²
2n
2 t=t
17
211
(12 - 4 1)mH²
21j
This concludes the proof.
Lemma E.2. When employed by Algorithm 2, online projected gradient descent (OGD) guarantees for all t E [T]:
||e41l11 || S mlin.
Proof. It holds:
A41, = min max { 0. 0. te + Σ
#-1
h=0
21

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
I max
0, A +
Σ
St,a (x, an)
h=0
{ Nen +1
1-1
S max
Σ
A=0
A, + nH,
which concludes the proof when we take the sum over all E [m]]
F. Analysis on Lagrangian multipliers
Lemma F.I. The loss given the primal algorithm at episode E [T], which is defined as le(x; a) T +
Eielm ( rr( a), is such that, considering the Lagrangian loss function ff a) = Eiiiml )e, a)
re(x, a). it holds:
4 -") =
(q: TT 9¹),
and udditionally, & assume values in the bounded interval [0, =.].
Proof. By simple computation, holds:
{ (1 - 9²) sL.T (g: - -²)
Σ (1( (²
12 (x,
2,a
VE RE(m] a,a
Σ a0
21,0
ΣΣ A0, (x, (x, Er(lx, x- (=()aa))
[E/m) a,a
Σ
ax)
F.a
[H H)
0,
where the last steps hold since I, is constant and by the definition of valid occupancy measures. In addition it holds:
(lr,a)=T,- Σ
(:s ||all
Σ
No.1- 0,
vE(m)
iE|ml
and similarly,
(xx,a)=I,+ Σ -21
ST++ Σ - E.
sE[m]
sE(m]
This concludes the proof.
Theorem 3.4. Under Condition 2.5, for any 8 E (0, 1), with probability at least 1 118, it holds:
Della SA Vt +1,
where A 112mH² g²
22

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Proof. Let M > be a constant. By absurd suppose 312
[T] s.t.
2HM
2HM p²
vt S to
|
S
A
P²
and let 4 < l2 s.t.
2H
2H
| S
2 A W:: MInsi |elll
P
By construction
<<
2M p < Aell <
2HM p² for all i S S l2, and it holds if 1f S
2H
4H
Dalll & 11 + mnnl S + mnnl S
(8)
Notice also that by construction, calling Ae,,, maxxe(ti...t))) |1 it holds:
2HM
4HM
1< X
1
(9)
p
In the stochastic setting the following holds by Azuma-Hoefiding inequality with probability at least 6:
42
1/
N G q 2 Σ -N d¹ -2
EG
2 X (to - t1 + 1)p - X1, .2 L1 122
2 (te - t 1)2H A1,, 1
where Eg, = BB (t2 - +1] 211 I/ 2
(6)
112 (tz - t + 1). Instead, in the adversarial setting, it holds;
G. dp 2
Ae. []]
t=
t= 1=1
12 m
0
A
Σ |
t=
2 (tz t1 1)2H.
Generalizing the result, it holds, both for the stochastic and the adversarial setting, the following inequality with probability equal to in the adversarial case and with probability at least 1 ò in the stochastic case:
t
NJ G.G. d 2 (12 - 4 + 1)2H Ce
Thank to this result we can find a lower bound for Eie,, e &e with probability at least 1 98 in the stochastic setting and with probability least 1 88 in the adversarial case, employing Theorem 3.3..
t2
T
4
(T AG.
Σ
(q:
9º)
la
l2
N -X G.. qd Σ
cC,
(q: - 9¹)
(10)
4
t=
t=
> 2H2
t1 + 1)
,
cG ep
E
(11)
23

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
r where Inequality (10) holds since r qº 2 O, for all E [T], and Inequality (11) is derived using the bound the primal interval regret given by Theorem 3.3 and defined E. and by Lemma F.1. At the same time, it is possible to define also an upper bound for the same quantity - Eisn, ff with probability at least 1 - 26:
l
t
#-1 +
tg
#-1
H
Σ
(G q:
Σ G((zn)aa)
0
Xe)
Σ
G.(
t=
1=
h=
1=
h=0
< - 1 + 1) + X1n12
((( (((1))))
+ E + (0)
2,a
S H12 41 + + 22 + 12 (0),
CD
where Ed = Fi / (12 - 4 +1) H 2 (T (12 - t + 1) and (Q) = D1 1 ll
111-2-11-1 +1) D2n(122 [1Ar, 12 +
"
2 11(12 - 1 + 1). Thus, combining the two bounds we get with probability least 1 108 in the adversarial case and 1 116 in the stochastic case the following bound,
mH²
(t - t - 1) - Xe E1.t2 - -ri, S H122 - t1 +1+1. 1) + Ee + E (0)
which can be reordered as
H(12 11 11 + A cG + 22 + E. (0) + E1.ts"
We recall here the definitions of the bounds &G
f2,22 12,22 11.12 (0) and CP f
El ED
= Bi B (12 - t t 1),
where B₁ = 2H VIn In (++).
&/1
Fi Fi (t2 - t1 1),
where Fi H /2 (22)
| 1/
(1) D1
+ D2n(112 11 + 1),
where D1 = 2, D2 mH² 2
E/1,, Ui UiEr, CVT U, (12- 11 +1+ + UgEn, CVT CVT
+ U
/2 22 In [TI]IAI)
where U1 = 6HH In
[|AAT2 6
( Un
UU2 = 91 U3 # In HT
and U, [X /
Thus, we can write:
Hitz - t1 11 S (F1 + Bi) (to - t + + U2 t2 -1
CVT
1
Ug CVT
U CVT + Dan(12 11 +1) 1)
24

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
1e
+ D1
U
To conclude the proof by absurd it is sufficient to prove that all 1, ② with at least one being strictly smaller.
are smaller or equal to M[ 44 +1
7
Prove !
41+
If n S 14m(Fr BBT then !
H(t2-11
holds. Indeed:
7
H(t - ti +1
HM
(12a)
7
7p2mm
2HM
(Fi + BIVVT
(12b)
p
An. + B
(12c)
1, (Fi + B1 - +1,
where Inequality (12a) holds by Lemma K.1, Inequality (12b) is equivalent to condition 1) S (12c) is true by Assumption (7).
14 and Inequality
Prove 2
H +1)
If C 2 56
MU holds, then ② < PVT
H(t--t+11) also holds. Indeed:
(t t +1
[HHM p²
12 t + +1 OVT l/ 11-1 +1
2U2
(13a)
7
U22(1 + (e
(13b)
CVT
h2 11 +1
U2 CVT
(13c)
where Inequality (13a) is equivalent to the condition C 2 56 MUs (13c) is true since ,t, I 2(1 + (2)
Inequality (13b) holds by Inequality (9) and Inequality
p²VT
Prove
(1a +1)
If S
CVT holds then also 2
M(ta-t+11) holds. Indeed:
56ml5
H(l2 11 11
HM
(14a)
7p2mn
2 U22 AHM
(14b)
P² CUT
1
2 U32(1 + dttita)
(14c)
CVT
2 U33r,02 CVT
(14d)
where Inequality (14a) hold by Lemma K.1, Incquality (14b) holds if condition 17 < CVT 56m07
holds, and Inequality (14c) and
Inequality (14d) follow the same reasoning as Inequality (13b) and Inequality (13c).
Prove ④
(1g +1) If 1 50mU1oVT holds then also 1(1a-f1+1) holds. Indeed:
H(12 - 1 11)
HM
>
7
mm
U A CVT
(15)
p²
25

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
U12(1 CVVT
2 U
where Inequality (15) holds when condition 7) S SamU,cy also holds, and the rest of the inequalities follow similar reasoning to the one used to bound 3
Prove 3 x
H(te +1)
It is immediate to see that if 17 S
H 7D2
holds, then it holds also that:
( t +1)
D2n(t22 -1 t + 1) <
7
H(ts +1)
Prove
the condition M 2 112D, Hm satisfied than the inequality c
H(t2-44+ 7
holds too. Indeed:
Hit₂ t
HM
(16a)
mp
16
D
(16b)
p²
|e, IP?
D
(16c)
1
Le,
2
D
where Inequality 16a holds by Lemma K.1, Inequality (16b) holds when the condition M 2 112D, Hm is satisfied and Inequality (16c) holds by Inequality (8).
Prove y
+1+
If the condition 17 < 56mU.vT is satisfied then ? < H(12-(111) also holds. In fact
H(12 - 11 + 1)
HM
(17a)
7
7 7p2ma mn
U22 4HM
VT
(17b)
p²
U,2 + .VT
2 U.E
where Inequality (17a) holds by Lemma K. and inequality (17b) holds if condition 1) < 50mU.vT
also holds.
Conclusion of the proof
Thus, we have the following 3 conditions:
First condition:
M 2 112D Hm
112 Hm 2 56/lm.
Second condition:
C 2 56 MU₂
V²VT
M9H A
56
VTVT
26

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
Third condition:
CVT
H
7 min
14m(Fi + Bi)VT
56mU33
56mU,cv/ 7D22 56mLAVT)
Thus, we set M as M = m, and consequently, under Condition 2.5 we set C -22 X ||
H since
C 252 A
> 252 X|
112mH
X|I
p VT
(56Hm)9HH
56
P2vT
A 56
9MH X
PVT
Notice that the inequality is deduced directly by Condition 2.5. In fact if p T- 112m then it is also true that
112mH
ST
As final remark, choose 252 X [|| H value of C instead of the smaller value 252 252 X|AA), which is useful for Lemma
J.1. Finally study the condition 77.
CVT
H 56mU, CVT 7D2
min
14m(Fi + Bi)
56ml's
56mUs
252)
X|AATV
2 min
14m
4H In (
/T
56m
In
1
H
56m
2 In
(252)X][A|HH)
VT 7 m2
1
56m
30
2|
(TixIe Al
X 14
/T
Thus, the proof is concluded taking 1) 84672m./F(x((]]A|lla IA 1X VT'
Lemma F.2. If Condition 2.5 holds, for all E [T] and for each constraints E [m], it holds:
d 2 DD-11.
where Vr, Et-r
Proof. First observe that with t = we have that Vz-1, is the sum of zero elements and as such, it is equal to zero. This means that for = 1 the inequality do,i 2 n/ii11 equivalent
A 2 0,
27

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
which is true by construction. We finish the proof by induction. Suppose X v/-11, is true for & [7]. show that it also holds for + 1, indeed:
H
A411, max Ae, + 17
Σ
91, (n)
h=0
maxx A 11 Σ gello, ()
A1, 17 Σ (gs(e,
2,0
n 7 + Σ
(x,
Σ (T) + tc,l (2,
(r, (
nu..
This concludes the proof.
Lemma F.3. If Conditiio 2.5 holds, referring as i" to the element in [m]] such that it arg maxig[m) Et= [G] a Poxe] then with probability at least 1 - 8, it holds:
Vr S Vr,3- + 3
Proof. We observe with probability at least 1 - 8:
VT=
G q [m]]
Σ Ir.s (z, a) (a(()) ()) ΣΣ De. (x, a)Te(
9t.s- (I, a) (g((z, a) Le a)) + Vr,
1=1 22.0
S -d + VT,**
This concludes the proof.
Lemma F4. When Condition 2.5 does not hold, with probability at least 1 106 in case of stochastic costs and - -88 in case of adversarial costs it holds for all i E [m]:
47 Vr.a I
7
Proof. Recall the definition of Vr, as Vi, = Et En, I1. (2, (It a).
We first focus on the stochastic setting. Thus,
with probability at least 8, it holds:
T
T qt Σ
T
T
Σ
A.G.T q =
Σ
TT > +
Σ ST T4 - -4)
t=1
t=1
T > Σ
x x.G. qº X + Σ f. (q -t)
t=1
tm1
28

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
3 m c T ( - -b)-
On the other hand, in case of adversarial constraints, it holds:
Σ r.a q:
Σ
No G q: Σ dd LN + 4 (4 -4)
t=1
Σ 4
T (q -q).
Define vector À E [0,T as xj = 0ff + i and X3 = T if j = i. Simultaneously with probability at least - 5 it
holds:
T
Σ
TTu Σ
tm1
Σ g/
Σ X
Σ
((t,a))((,a)) Σ(- Xc) = (x), + A
T
Σ 2/a q:
Σ X Σ (( + (Q)) + m
t=1
HT - V
+ (x) + m
where in the first equality used the definition of Et, in the first inequality we used the definition of the dual space [0, m2 mM to bound \I,T as mT and the last inequality we used the definition of X. We can then compare the lower and the upper bound for Ei= ri q: Ei= XT G. obtaining the following inequality, which holds with probability at least 1 - with adversarial constraints and with probability at least 1 - 25 with stochastic constraints:
T
-
4:) HT y +
from which write the following inequality that holds with probability least 96 with adversarial constraints and 1 106 with stochastic constraints:
T S (E -E,) + E + &P(() (2) + HT.
(18)
We proceed now to bound each element of the right side of the inequality.
To bound gd we use the fact that E S (1 >I.T)= & 11+ml' and the definition of 1 as following:
VT Ef = [UICVT+U, U2
C +U CVT
UUVT
# In HTT
< 2(1 221 mI
1512H |XIA| In
2
9H X
+
2
252 X|IA
252 [X
TIXPIA
<T3002 X
2|A In
8
(H|ATT
22 (TIXPI/A)
T VT60566 X|| In
+
+T330H XX|2
< ST 7T61116HFmm1X111111
8
29

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
T 7
To bound EP we use Theorem E.I, the fact that by its definition | (T#) 2 A1 0 and the definition of 7y in the following way:
VT, the initialization of the dual
212
(
-
7 T
21
|
+ "
THH
2n
2
VT
+ 2
TTHH2
2nj
VT
mH²T
21
[AA]IX]TT2
VT
VT
VT
VT
2n
2n
"
We proceed simply bound also mT+
(Ef E) through their definition:
T
T2
mI'
(Ef
Et)
mI VT
2H
In
H
2
T s
Finally bound HT HT < VT
Thus, Inequality (18) becomes
V S 1 (mI' + + & + HT T
4VT
47
T
which concludes the proof.
G. Analysis with Stochastic Constraints
Theorem 4.1. Suppose that Condition 2.5 holds and the constraints are generated stochastically, Then, for any E (0, 1).
Algorithm 2 attains:
R ō (AVT), VA 5
with probability at least 148 when the rewards are stochustic, and with probubility least 138 when the rewards are adversarial.
Proof. With probability at least 1 125 it holds:
Vr S Vr +
(19a)
17 +
(19b)
< -A + Et.
(19c)
30

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
where Inequality (19a) holds by Lemma F.3, Inequality (19b) holds by Lemma F.2 and Inequality (19c) holds by Theorem 3.4.
Then, with probability at least
128 we observe that:
T
T
T
T
T +
Σ
Σ
Σ
Σ
-
Σ
NT..
-9))
1=1
< 3 + (0) + XI,T +
Σ Ni TT
(20a)
=3- + (0) + A Σ (G, G) q" + E N
+0" N + A1,rE 3 + (0) + AE + A
(20b)
(20c)
where Inequality (20a) holds by Theorem 3.3 and by Theorem E.1, Inequality (20b) holds since in the stochastic constraint ?
qº case Σi=1 (Ge- -² I Ed with probability least 1 - 5 by definition of go and finally Inequality (20c) holds by Theorem 3.4. Finally we observe that in the stochastic case with probability at least 1 - 5:
T Σ
T
T OPT F.G -
r
90
Σ
- SE.
1=1
Thus, if the rewards are stochastic with probability at least 1 - 148 it holds:
Rr S 8 + + A + + Vr s - + E
")
and if the rewards are adversarial with probability at least 1 - 135 it holds:
Rr E +0 + A + AEE, VT s -A + g
which concludes the proof.
Theorem 4.2. Suppose that Condition 2.5 does not hold and the constraints are generated stochastically. Then, for any
E (0, 1), Algorithm attains:
R S sr ( 5
(T
with probability at least 1 - 118 when the rewards are stochustic, and with probability at least 105 when the rewards
are adversarial.
Proof. Similar to the proof of Lemma 4.1 it holds with probability at least 106:
T
T
T
Σ
Σ (TT - (T
(rT - GT
+ Σ
xJ NTT (g" gc)
1=1
t=1
S 3.. + (0)()) >1 Σ
N, G.
T
T q" + + .
= E8 + (P(()) + A +
Σ
x - -G, TT
< + (0) + E + t
therefore with probability least 1 108 following the reasoning of Lemma F.4 holds with adversarial rewards:
Σ
r 4h > T OPT न, 148 + gl - EP E.,
31

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
and with stochastic rewards with probability least 1 116:
T
Σ
re
- mT + m - (0) C.. -
Applying Lemma F.4 to bound the constraints violation concludes the proof.
H. Analysis with Adversarial Constraints
Theorem 4.3. Suppose Condition 2.5 holds and the constraints are adversarial. Then, for any (0, 1), Algorithm attains:
T aT.
OPT. (f
VrsōŌAVT))
p+H
1=1
with probability at least 1 - 148 when the rewards are stochastic, and with probability at least - 138 when the rewards are adversarial.
Proof. Thanks to Theorem 3.3, Theorem E.1 and Theorem 3.4 with probability at least -188 it holds for all E A(P):
T Σ
q
qt
1=1
1=1
T
L. 9 ++1
T. qt +
Σ
x
G. q
EM G.
T
T Σ
H-1
r
#-1
& +
N G. g+
X
Ge(Tn, an)
+
Σ
x
Σ
Gi and - G. qt
t=1
h=0
1=1
3 & + X1 +
A
m
S & + 87 Q + EΣ Σ
==1==
Consider now the occupancy measure q n + " For all i [m] and for all [Z]]
97,79
H "l. +
P
H + p (
H
Hp
Hp
Hp H H+p)
0,
given that "T. l1q 1/2 H, and 9T.9 s p by definition of 9º and by definition of p.
T
H H
Σ
9' +
T, &
1 p
p
t=1
1=1
P
Σ T
H P
32

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
since r. 2 0. Notice also that with adversarial rewards Ei= r T OPT R. while with stochastic rewards with probability least ö it holds Σi= r2 q- 2 T OPT E", by definition of e" and OPT प. for stochastic rewards. By reordering the terms get that with probability least 1 118
Σ
Er + Σ
1. E 8P(0) ( AE
we can proceed to bound the regret in both cases: adversarial rewards and stochastic rewards.
With probability at least 1 - 116 with adversarial rewards it holds:
= R1
4
t=1
t=1
$ Σ
9
P Dr o - -
Mg
H + 1=1
1=1
H
Σ
r + o + 8
( (0) NV
H + P
H T OPT
< H
P. 3 3 (0) E
cD
With stochastic rewards it holds with probability at least 1 - 11::
T
T
Σ
ET (0) - -,E
H+P
H
1=1
and with probability at least 1 - 125:
Er
T..OO TOPT H + 7 E & (0) 3E E"
To conclude the proof we observe that following the analogous reasoning to Theorem 4.1 in case of adversarial constraints also holds with probability at least 126:
1 VT S A + 8
7
I. Analysis with respect to The Weaker Baseline
In this section we will study the guarantees of Algorithm 2 when the regret is computed with respect to a policy g that respect the constraints at each episode, i.e. g: g" < 0 for all i E [m]] for all E [T'].
Theorem 4.4. Suppose that Condition 2.5 holds and the constraints are generated adversarially. Then, for any E (0, 1),
Algorithm 2 attains:
RT < =
VT 5 (AVT):
with probability at least 1 - 135 when the rewards are stochastic, and with probability at least - 128 when the rewards are adversarial.
Proof. The violation can be bounded as in Theorem 4.1. Also similarly to Theorem 4.1 it holds with probability - -22
T
T
Σ
IT Σ TT < Σ
e q
Σ
C.T q:
Σ
x7
G.
ENG.
t=1 tm1
[=1
t=l
1m1
33

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
H
T
n- 1
$ E +
0 Xx)
Σ
an) +
Σ
x
Σ
Gy an) G, 2:
h=D
t=1
4=0
S E + 8/ (0) A
I & + (0) + A
Finally with stochastic rewards with probability at least 6:
T OPT T.G
En SE.
t=1
Therefore, with adversarial rewards it holds with probability at least
128:
RT S E + E AE
V S - A + E
and with stochastic rewards it holds with probability at least - 130:
RT S E + +0 AE +8, V s -A E
which concludes the proof.
Theorem 4.5. Suppose that Condition 2.5 does not hold and the constraints are generated adversarially. Then, for any
5 E (0, 1), Algorithm 2 attains:
R =
Vr 5 (
with probability at least 1 128 when the rewards are stochastic, and with probability at least 118 when the rewards are adversarial.
Proof. The violation can be bounded thanks to Lemma F.2, as in Theorem 4.2. To bound the regret, notice that it holds with probability 1 1 96:
T
Σ
ri
4
Σ
1t gt
q
4
ENT
ENT
1=1
1=1
1=1
1=1
T
H-1
T
#-1 Σ
< E +
Ax)
GelEn, ond
+ Σ
x7
G.(on, an) - G.
h=0
1=1
< 3 + 8p (0) A
I & + 8 00 /4
Finally with stochastic rewards with probability at least - 8:
T OPT G
Σ TTT 8
Therefore, with adversarial rewards it holds with probability at least
118:
4/
Ri g +8 + mT Vr S
and with stochastic rewards it holds with probability at least 125:
4/
RT < 3. + E 00) m +E,, Vr S "1
which concludes the proof.
34

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
J. Auxiliary Lemmas
Lemma J.1 (Adapted from (Luo et al., 2021) Lemma C.4).
T1 (1) 1
1
(2, S 2H A
Proof. Recall 7 = 21, Thus, holds:
( < HH
m/ H 1
7
H1, 2
and 31): + - (,(z,a))
md a)
- H + + 27.
(,( ((,,,)++ +
Finally,
1 1
H
(B,, S H 1+
7) sup (,',', a z'
H
S 3H2
6H7
6H
C/T
6H
252 X
<
42H
$ 2H
This concludes the poof.
Lemma J.2 (Adapted from (Luo al., 2021), Lemma B.1). If the following inequality holds:
Σ (x)
(m<(a()) x (Q Be(xra))
t=
$ (T) +
(No: b.) + H Σ Σ (c)
(21)
1=4
1=4 2.0
with B, defined
1
(z = (z) +
1+
Ex Be [Bi(d',
Vi e
(22)
H
then it holds that:
12
R1, S (T) +3
Σ
Proof. The proof is analogous to the proposed by (Luo et al., 2021), Lemma B.1, since the proof is episode based and then the sum over / is taken.
Lemma J.3 (Adapted from (Luo et al., 2021). Lemma A.1). Let Fo....,FFy be a filrration and XI.... Xy be real random variables such that X, is F-meesurrbbl, [F) 0, |X,] s for all e (T) and Eiz,, E[X? S Ve for some
35

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
fixed VnL.2 > 0 and b > 0 for every 11, l2 [T] such that 1 S 4 S l2 S T. Then with probability least ô it holds
simultaneously for all [f,....: [
12 X
Ve,t2 + bog S
T2
1=
Proof. For all 8' E (0, by Lemma A.I (Luo et al., 2021) it holds:
f2
V4,l2 + blog / ))) So.
P
X₂
b
It is sufficient to consider the intersection of all events for all possible intervals [f1.-.., 12), that are less than T
Ve.ta 1 - T
8 w)})
X 2
+ bloog
b
11,82
1=h
To conclude the proof we take 8 as T288
Consider a loss function fi(2, a) E [0, Z), for all E [T], (z, E X x A, with Z > 0. Define another function where [[] a)] = ft(r, a), we can state the F. E [0, xAI, we define the estimator a(( 9,(2,))77 following result.
Lemma J.4 (Adapted from (Jin et al., 2020)). For every sequence of functions a1.... .r such that oi E [0, 1 x
Fe measurable for all E [T], we have with probability at least ô that simultaneously for all t,, 1, E [T] such that
1 < t S tz S T it holds:
(e a) Σ aelor a) [T(or.0) 2.
HT² 5
fe(x,a) (1, a)
S HIn
Proof.
(((x, a1
a) +
f((x,a)le(z,,
a1(x,)) + fela.o)
2
27 Filz,a)
27
q. a)
fala,a)
Le(x, a)
27 [q,(x.a)
27
fe(u,a)
1 + 7 (_,,
2 In
1 1 27 Le(2, a) F)
<
27
20,
For each layer h E [H] we define Sen = Exe XA, arlæ, (r(x,a)Si(x, u) and S.A == Exe aola, a) gizaa)
d,t, a) fe(r, a).
E, (eepp((S..)))
= E
exp
Σ
a((o,a)f((x;a))
rEXA.REA
E
exp
Σ
arlz, a) In
Z
1+ 27
[e (e.aa)((zz))))
2
27, (2,
TEX
36

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
1 Lex, ((i,,)) (e(2,a)
S
II
ax(z,a) a a(zzz) 1 Se
- 1+
Σ
((
rEXI.GEA
<exp(St,)
For each interval [4,....44 [2] C [T' it holds:
11
8' H
P
Σ 1=
S5 S1, 2 In
8
Taking the intersection event for all intervals
[t.....,ta) tol C [T7]
P
Sun Se, 2 In
H
}
T 8'
8'
H
t=
b= T288
and
f2
HT
}
SLch Sen) 2
H
t=
Finally we take the sum over E [
P
Σ Σ
(((2,a) ax( (f(oo.a)
ue u1(2, f((r.)) s Hin
HT2
8
A=t1
2.0
This concludes the proof.
Corollary J.5. Given 5 E (0, 1), it holds with probability at least 1 15t S2 S::
25 simultaneously for all 11, 12 E [T] such that
l2 ΣΣ (fl(z.a) fe(x,a))
2H In
HT
2
8
t=
Lemma J.6. Let (Te Y policies, then for any collection of transition
Ps E P.te) with probability at least 28,
HX
TIX
Σ 11g
Pite Pine
gPrintl11 22
2T In
+ 3H 2
21 A In
8
Proof. It holds:
T
T
lg Pime
Pit
P. (I, 0) (x,)
I=
2,a
T
Pite (I',a) - -f (2',a) a)l
2,8
T
P. (x', a) pT (x',)a)
1=1 z'
H|X
TT|X [|A
Σ
2H
X
In
2T| ln
8
8
37

---

Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints
(IXIH H +3HIX|
T (TXPP1A))
||
|
| 2n
(2T In
8
by Lemma K.3, taking the union bound over X (8'= - This concludes the proof.
K. Auxiliary Lemmas From Existing Works
Lemma K.1 (Stradi et al. (2024b) Lemma D.2). For rj S mH and
4, if Atg+1
2
o² and || 1l S holds:
M
(t2 11 +
pmmm
Lemma K.2 (Rosenberg & Mansour (2019b)), For any & E 10
2 2|Xn(a)41I In TIX]I
max Ne(x,
simultaneouslyJor for all (x, a) E X x A and for all epochs with probability at least 1 5. Lemma K.3 (Rosenberg & Mansour (2019b)). Let {Te)==1 policies and let {Pi)T= transition functions such that de E (P:()) for every E [T]. Then with probability at least - 26,
T
H 27
(T]XIIA) 5
Σ
11 Pate (1 S 2
(
+ 33 / 2T
38


Reviews:
[{"review_id": "mwwbV5XTaf", "reviewer": "Reviewer_fRky", "summary": "This paper considers policy optimization for the CMDP framework with stochastic and adversarial constraints. Compared to the existing works, this paper considers bandit feedback rather than full feedback. The paper uses a primal-dual-based policy optimization method to find the policy directly rather than the state-action occupancy measure. Hence, it is more suitable. The paper shows that one can achieve $O(\\sqrt{T})$ regret and violation  if the Slater's condition holds or $O(T^{3/4})$ regret and violation if the Slater's condition does not hold. The paper is the first one providing the best-of-both-the world result in the CMDP setting.\n\n###Update###\nAfter going over the paper and the responses again, I have decided to decrease my score. I have explained the reasons below:\n\nThe key contributions are the following:\n\n1. Relaxing the full-information setting information compared to Stradi et al.\n\n2. Obtaining results even when the Slater's condition does not hold (or,  the strict feasibility can be very small).\n\n3. Use a lower computational complexity approach to get rid of solving a convex optimization problem to find the occupancy measure over all the possible transition probability sets.\n\nWhile I agree that if someone combines all the tools in a novel way to show that it is not trivial, then we should certainly accept the paper. However,  I am not sure all these contributions are very novel. Let me elaborate on my points. If the paper is accepted, I will suggest the authors to consider the followings:\n\n1. Stradi et al. consider that the transition probability is unknown. Hence, I am not sure how much complexity it adds using the Bandit approach. As it is well known, most of the complexity comes from the unknown transition probability. In the adversarial setting, it may indeed affect, however, I am not sure that the tools are very novel. Perhaps, some other reviewers can convince me otherwise.\n\n2. I agree that the second claim is indeed a novel, however, as I pointed out there are other approaches that have already considered the setting in the Stochastic setting. Hence, I am not so sure about the contributions. In particular, we do not know the lower bound, hence, the tightness can not be commented here.\n\n3. The third contribution is interesting, however, it directly follows from Luo et al.. It is not clear whether extending it to the constrained case will be very complex.", "questions": "", "limitations": "", "rating": 2, "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.\n\n> On W1 and Q1.\n\nAs shown in [1], computing the maximum state-action occupancy measure among the possible transition probability sets (Line 5 in Algorithm 3) can be solved efficiently via a greedy algorithm. The same reasoning holds for the corresponding minimum and for the bonus quantity (see Luo et al.'21).\nWe finally remark that performing the OMD update over the occupancy measure space (as in occupancy-based methods) would require solving a convex program at each episode, which is considerably heavier than computing upper occupancy bound or bonus terms.\n\n\n> On W2 and Q2.\n\nThe algorithm from [Luo et al. ‘21] cannot be employed as our primal regret minimizer, as it is. \nIn particular, our primal regret minimizer must guarantee the no-interval regret property – in order to show that the Lagrangian multipliers are bounded during the learning dynamic –, which requires the introduction of a fixed-share update. To the best of our knowledge, our primal regret minimizer is the first to show no-interval regret property for adversarial MDPs with bandit feedback.\nFurthermore, we had to improve the dependence of the regret bound on the loss range, introducing a dynamic learning rate. This learning rate is used to improve the dependence on the payoff’s range from a quadratic dependence to a linear one. Indeed part of the complexity of designing the primal algorithm is that the range of the losses cannot be known a priori, as it is a lagrangian loss and therefore proportional to the problem-specific lagrangian multipliers.\n\n\n> On W3.\n\nWe agree with the Reviewer that extending the guarantees presented in this paper to model-free approaches scalable beyond tabular CMDPs setting would be of great interest. However, the results presented in this paper are novel even for the simplest tabular case, and we believe this work might be a good starting point for extending the results to more challenging scenarios in future works.\n\n\n> On W4.\n\nGuaranteeing positive violation requires the primal and the dual regret minimizers to attain convergence to the constrained optimum, namely, to have last-iterate convergence to the equilibrium of the Lagrangian game. To the best of our knowledge, no algorithm can guarantee convergence in last-iterate in the setting faced by the primal regret minimizer. Finally, notice that, if future works may find no-regret algorithms with last-iterate convergence on the settings faced by the primal and dual regret minimizers, sublinear positive violation (in the stochastic setting) would directly follow by the analysis of our primal-dual procedure.\nWe underline that the papers provided by the Reviewer focus on stochastic settings only, where it is possible to exploit confidence intervals to estimate both rewards and constraints. Indeed, it cannot be done in our setting, since it would prevent any algorithm to deal with adversarial settings.\n\n[1] Jin et al. 2020, \"Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition\".", "claims_and_evidence": "The claims are clearly supported by the proofs.", "methods_and_evaluation_criteria": "The paper is mainly theoretical in nature. The paper's claims are supported theoretically.", "theoretical_claims": "I briefly go over the proofs. There are no major concerns.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper has made a clear connection with the existing works.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1. This is the first result that achieves sub-linear regret and violation using bandit feedback. Hence, in terms of results, the paper's contributions are significant.\n\n2. The paper is relatively well-written, and the proofs are nice and clean. \n\nWeaknesses:\n\n1. Even though the paper talks about policy optimization, it still relies on the state-action occupancy measure. In particular, the paper relies on the computing the maximum state-action occupancy measure among the possible transition probability sets (line 5 in Algorithm 3). The proposed approach also needs to maximize the bonus term as well over the possible transition probability sets (line 6 in Algorithm 3). The paper did not talk about how easy or difficult to solve this problem.\n\n2. The paper heavily relies on Luo et al. '21. The paper did not explain the technical novelties.\n\n3. The approach is model-based and thus can not be applicable to large state-space (even with linear function approximation).\n\n4. The paper considers a weaker notion of the violation where the violations can cancel each other. In particular, one can have violation of +1, and then violation of -1, altogether violation is 0, however, it is still violating half of the episodes. Can the paper talk about a stronger notion of violation (cancelation free)? Recent works in CMDP have addressed the issue.\n\n[A1]. 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.\n\n[A2]. Müller, Adrian, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. \"Truly no-regret learning in constrained mdps.\" arXiv preprint arXiv:2402.15776 (2024).", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "1. Can the authors comment on Weakness 1?\n\n2. Can the authors point out the main technical novelties compared to Luo et al.'21. In particular, why not combine the results of Luo et al.'21 and the existing understanding of the CMDP works in enough to get these results?", "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": "vaByIL7C79", "reviewer": "Reviewer_ZveN", "summary": "This paper proposes the first best-of-both-world algorithm that can solve a CMDP only with bandit feedback and enjoys optimal regret and constraint-violation guarantees in both regimes. Furthermore, the proposed method does not require Slater's condition and employs a policy optimization approach, which is more efficient than occupancy-measure-based methods and amenable to neural network function approximation.\n\n## update after rebuttal\n\nI thank the authors for the rebuttal responses. I think it is a good contribution to proposing an algorithm for the bandit feedback setting, whose analysis is often non-trivial and sometimes requires interesting ideas, as explained in the rebuttal to Reviewer fRky.\n\nOn the other hand, the obtained bounds do not seem tight, or at least unclear if they are tight in other factors such as the state space size. Furthermore, the definition of constraint violation employed in this paper is a weak version, allowing violation cancellation. That said, this paper could be the first step towards an algorithm with completely zero-violation algorithm.\n\nWeighing these aspects, I decided to keep my original score of \"Weak Accept\".", "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. \n\n> On Ghosh et al., 2024.\n\nWe thank the Reviewer for the interesting point. First, we underline that we use the term best-of-both-worlds referring to the constraints definition. Thus, our algorithm achieves optimal regret guarantees when the constraints are stochastic (and the loss may be adversarial) and when the constraints are adversarial. Notice that our definition of best-of-both-worlds in constrained settings is standard in the literature (e.g., see [1]).\n(Ghosh et al. 2024) deals with the stochastic reward and constraints setting only, thus their algorithm does not admit adversarial loss as our stochastic setting. Finally, notice that sublinear results employing the positive regret and violation definition does not imply that a better rate can be obtained employing our metrics, thus, our dependence on the number of episodes is still optimal.\n\t\t\n\n> On the contribution.\n\nWe thank the Reviewer for the opportunity to clarify this aspect. In this work, we design a primal-dual algorithm that **does not require the Slater parameter $\\rho$ as input**, and in addition, it does not need any assumption on $\\rho$. Indeed, in the analysis, we study both the case where the Slater condition is verified (Condition 2.5 holds) and the case where the Slater condition is not verified (namely, either $\\rho=0$ or too small compared to the horizon). Nonetheless, while the lack of the Slater condition leads to weaker guarantees, most of the difficulties in our analysis arise from the lack of knowledge of the Slater’s parameter $\\rho$, which is considerably harder to tackle when the feedback is bandit. In particular the bandit feedback affects the design of the primal algorithm and requires some forms of additional regularization in the learning dynamic like the fixed-share update.\n\nWe will surely include a comparison table in the final version of the paper to clarify these aspects.\n\nSince these aspects are crucial, please let us know if further discussion is necessary.\n\nWe finally thank the Reviewer for the suggestions and we will surely implement them in the final version of the paper. \n\n\n[1] Castiglioni et al. 2022, “A Unifying Framework for Online Optimization with Long-Term Constraints”.", "claims_and_evidence": "The paper claims that their proposed algorithm is the first best-of-both-world algorithm that can solve a CMDP only with bandit feedback and enjoys optimal regret and constraint-violation guarantees in both regimes. As far as I know, it is indeed the first best-of-both-world algorithm under the considered setting. All proofs in the appendix seem to be well-written and correct.", "methods_and_evaluation_criteria": "Regret analysis is a reasonable technique for evaluating an algorithm from a theoretical perspective.", "theoretical_claims": "I have roughly read the appendix. All the derivation seems to be well-written and correct.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "Since reinforcement learning aims at solving various sequential decision making problems, deepening the theoretical understanding of RL algorithms in many settings has a broader impact on various fields. Reinforcement learning is also presumed to be implemented in the brain, and it is frequently used to model the decision making process of animals. Furthermore, this paper considers the constrained RL setting, which is gaining importance due to increasing use of RL in real life.\n\nThe bandit feedback setting is the most practical setting, and this paper solves an important problem. Furthermore, the analysis that does not require Slater’s condition seems also valuable for other CMDP regret analyses.", "essential_references_not_discussed": "I think the related work in the Appendix well covers important references.", "other_strengths_and_weaknesses": "**Strength**\n\n- The paper is well-structured and clearly written. The authors effectively present the algorithmic framework, motivation, and theoretical analysis, making it easy to follow.\n- The problem setting and the best-of-both-worlds contribution are important in the field of constrained MDPs.\n- Compared to prior work that relies on occupancy measures (and with full-information feedback), the proposed method is a policy-based* approach and amenable to neural-network-based implementations. Furthermore, the proposed method does not require Slater's condition, which many other algorithms need.\n - To deal with the lack of Slater’s condition, the author proposes several techniques to bound the Lagrange multipliers and loss for updating policies, which are of independent interest for other researchers too.\n\n**Main Weakness and concerns**\n\n- In the abstract, the authors claim that the regret bound is optimal. However, in CMDP settings, an existing algorithm achieves a $\\sqrt{T}$ strong violation regret without assuming Slater’s condition [(Ghosh et al., 2024)](https://proceedings.mlr.press/v238/ghosh24a/ghosh24a.pdf), which appears to provide a tighter bound than those stated in Theorems 4.4 and 4.5 of this paper. Would you explain differences of the obtained results from theirs?", "other_comments_or_suggestions": "**Main Question**\n\nMost of the technical challenges and algorithmic contributions in this paper seem to arise due to the absence of Slater’s condition rather than the bandit feedback difficulty. For instance, challenges such as **bounding the Lagrange multipliers, the fixed-share update, and the loss range issue** (as described on page 2) primarily arise due to the lack of Slater’s condition. While I understand the importance of handling CMDPs without assuming Slater’s condition, it is unclear how these challenges are inherently tied to the bandit feedback setting. Does the combination of **no Slater’s condition and bandit feedback introduce additional technical difficulties**? If not, it would be nice to clarifying the contribution for no-Slater’s condition in the title and abstract.\n\n**Minor weakness or Suggestions**\n\n- In line 3 of Algorithm 3, the phrase \"set of all possible transitions\" is somewhat unclear. Initially, I thought it as a set storing next states, but upon further reading, I found that it represents the confidence set of transition functions. To avoid confusion, I suggest rewording it as \"set of all possible transition functions.\"\n- The term \"loss\" in the introduction is ambiguous. To improve clarity, consider explicitly specifying it as \"loss used to update the policy\" or \"Lagrangian loss\" to help readers distinguish its role in the analysis.\n\nDue to the lack of important information (e.g., limitation, comparison table), I set the score to 3, but I’m happy to increase the score if all the concerns are addressed.", "questions_for_authors": "Please see the first question in the Other Comments Or Suggestions section.", "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": "Nr3oY9O9wB", "reviewer": "Reviewer_4Qhm", "summary": "This paper studies online constrained Markov decision processes with rewards and constraints that can be either stochastic or adversarial. It proposes the first algorithm for this approach with bandit feedback. Moreover, instead of considering a problem on occupancy measures, their method is based on a primal-dual policy optimization approach. The algorithm requires no knowledge of the Slater parameter. For this, they need a primal regret minimizer that satisfies the “non-interval-regret” property. To achieve this, the authors construct a policy-based algorithm with a fixed share update.", "questions": "", "limitations": "", "rating": 2, "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 novelty.\n\nWe thank the Reviewer for the opportunity to clarify this aspect. In the following, we better highlight the contribution of our work. Indeed, while our primal-dual scheme follows the one of [Stradi et al. 2024] and the primal regret minimizer builds on [Luo et al. 2021], we believe that the contribution of our work is valuable.\n\nSpecifically, our analysis and the one in [Luo et al., 2021] are substantially different in two fundamental aspects. First, we show that our algorithm works with a dynamic payoff range, paying a linear dependence only in the maximum range. While this dependence is standard in online algorithms, this happens since the payoff range is known a priori. This is not the case in our setting. To avoid a quadratic dependence on the payoff range, we had to suitably modify the learning rate. Moreover, our algorithm guarantees the no-interval regret property employing the fixed share update. While we agree that the fixed-share update has been shown to work in online convex optimization, we believe that extending this result to MDPs with bandit feedback is valuable. \n\nAs a second aspect, notice that all the primal-dual analysis in [Stradi et al. 2024] is designed to work under full-feedback. Indeed, the Lagrangian function given to both the primal and the dual in our work, captures less information that the one in [Stradi et al. 2024], namely, the Lagrangian is built for the path traversed only.\n\nFinally, notice that, differently from any prior work on CMDPs, we complement our analysis studying the regret w.r.t. an optimal solution which satisfies the constraints at each episode. While this baseline is weaker than the first one we propose, it has been largely studied in different settings w.r.t. ours, since it is the only one which allows to be no-regret when the constraints are adversarial. Specifically, this baseline has been studied in online convex optimization with constraints, thus, in single state environments with full-feedback (see, e.g., “Tight Bounds for Online Convex Optimization with Adversarial Constraints”, 2024]). Our results match theirs, showing that $\\sqrt{T}$ regret and violations are attainable when only bandit feedback is available and for an MDP structure of the environment. This analysis is novel and independent from prior works. \n\n> On the Slater's condition.\n\nThe Reviewer is correct, Condition 2.5 implies the Slater’s condition; however the focus of this work is the **lack of knowledge** of the Slater’s parameter $\\rho$ and not achieving theoretical guarantees when Slater does not hold –however, we provide sublinear bounds for this case, too, namely, when Condition 2.5 does not hold–. The motivation for this is that previous works in the literature with bandit feedback require the knowledge of $\\rho$ in advance and they assume $\\rho$ to be a constant, ignoring the case where $\\rho$ is very small (e.g. [1]).  \n\n\n> On policy optimization.\n\nThe point raised by the Reviewer is surely interesting. While a more rigorous analysis is required to precisely answer the question, our perspective is that technical challenges may arise when dealing with the biased loss estimator.\nFinally, notice the policy optimization approaches are generally preferred to occupancy measure ones, since occupancy measure based algorithms require convex programs to be solved at each episode. We believe that the aforementioned one is the main justification for policy optimization.\n\nFinally, we want to thank the Reviewer for the additional comments and suggestions. We will surely take them into account in the final version of the paper.\n\n[1] Castiglioni et al. 2022, “A Unifying Framework for Online Optimization with Long-Term Constraints”.", "claims_and_evidence": "All theoretical claims are followed by proofs in the appendix or the main paper.", "methods_and_evaluation_criteria": "As a theoretical paper, the proposed algorithm is well suited to the problem. However, as one of the main advantages, according to the authors, of using a policy optimization algorithm over an occupancy measure approach is its efficiency, some showcase experiments would be useful to illustrate the algorithm in practice.", "theoretical_claims": "I have checked the theoretical claims concerning the primal regret minimizer algorithm. The dual regret proof seems to follow from existing proofs in the literature such as in Stradi et al. (2024b), so I did not check them in detail.", "experimental_designs_or_analyses": "not applicable.", "relation_to_broader_scientific_literature": "This papers propose the first approach to tackle stochastic and adversarial rewards and constraints in CMDPs with bandit feedback. Most previous work focused on the case where rewards are adversarial and constraints are stochastic. Stradi et al (2024b) proposes an approach for stochastic and adversarial rewards and constraints but with full information feedback.", "essential_references_not_discussed": "All relevant references related to CMDPs seem to be discussed. As the paper also claims that they develop the first no-interval-regret (a.k.a., adaptive regret) algorithm for unconstrained MDPs under bandit feedback, the paper could benefit from a related work on existing approaches for adaptive regret on online learning and MDPs.", "other_strengths_and_weaknesses": "**Strengths**: \n- The paper is mostly well-written. \n\n- The paper presents the first primal-dual approach using policy optimization to deal with both adversarial and stochastic rewards and constraints with bandit feedback.\n\n**Weaknesses**: The main weaknesses of this paper appear to be the lack of technical novelties in both the algorithm and its analysis, as outlined below:\n            \n- Policy optimization is a Mirror Descent-like algorithm. Cesa-Bianchi et al. (2012) presents a general method for achieving adaptive regret in Mirror Descent approaches through a fixed-share update. Hence, it seems that applying this technique in this context is not novel.\n\n- The proof of Theorem 3.3 appears to be essentially the same as that of Theorem 4.1 from Luo et al. (2021), except for the fixed-share step, which is a standard technique for achieving adaptive regret in Mirror Descent approaches. \n\n- Once the primal and dual algorithms are designed to satisfy the no-interval-regret property, the bound on the Lagrange multiplier (Theorem 3.4) appears to follow in a very similar manner to Theorem 5.1 in Stradi et al. (2024b).\n\n- The challenge of handling bandit feedback instead of full information appears to be addressed using classical techniques from Online MDPs in the development of Algorithm 3 (see, for example, Luo et al. 2021).", "other_comments_or_suggestions": "Below, I provide some suggestions to clarify the paper's presentation for readers.\n\n- The authors could define better in the beginning of the paper what they mean by \"best-of-both-worlds\". Usually it means an algorithm that achieves the optimal regret for both stochastic and adversarial rewards. But in this paper the authors deal with stochastic and adversarial constraints.\n\n- I recommend that the authors define the \"no-interval-regret\" property earlier in the paper, as it plays a crucial role in the final result and strongly influences the algorithm's design, and the reader may be unfamiliar with this notion. Additionally, this property has been referred to by other names in the literature, such as \"adaptive regret,\" which could be worth mentioning to improve clarity for readers.\n\n- I would also advise the authors to give a proper mathematical definition of terms $\\Gamma_t$ and $\\Xi_t$ from Algorithm 2 to help the reader better understand their meaning in the proposed method.", "questions_for_authors": "I would appreciate hearing the authors' responses to the concerns regarding the weaknesses of the paper. I also have some questions to better understand their approach:\n\n- The authors state that they do not assume Slater's condition (the existence of a strictly feasible solution). However, does requiring condition 2.5 to hold not implicitly imply the existence of such a solution? I would appreciate it if the authors could clarify this point.\n\n- One of the authors justification for the use of policy optimization is that mixing the occupancy measure produced by an occupancy-measure algorithm with the uniform one (as in the fixed-share update) would not work. However, would it be feasible to instead mix the policy induced by the occupancy measure in an occupancy-measure-based approach with the uniform policy and then use the occupancy measure induced by this mixed policy? This could allow to achieve the same results (dealing with stochastic and adversarial rewards and constraints with bandit feedback) also with an occupancy-measure approach. I would be interested in the authors' perspective on this point.", "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": "RfvPAPPeK7", "reviewer": "Reviewer_KZyT", "summary": "The authors study constrained Markov decision processes (CMDPs) and they provide the first best-of-both-worlds algorithm for CMDPs with bandit feedback.", "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.\n\n> [1]\n\nWhile in classical RL literature, the only goal is to maximize a given reward function, in the constrained RL literature the problem becomes two-fold. Specifically, the agent has to additionally fulfill $m$ possible constraints while maximizing the reward function. This double objective strongly limits the possibility to explore the decision space.\n\n> [2]\n\nAs “episode-dependent learning rate” we mean a learning rate which changes over episodes. This is required to attain a linear dependence on the payoffs’ range in the primal algorithm regret bound. Notice that, while attaining a linear dependence on the payoffs’ range is trivial when the payoffs’ range is known, this is not the case when the aforementioned quantity is unknown.\n\n> [3]\n\nAlgorithm 1 does not have any input/output since it simply shows the interaction between the learner and the environment.\n\n> [4]\n\nCondition 2.5 is a condition on the Slater’s parameter of the offline problem $\\rho$. Αs is standard for primal-dual methods, when $\\rho$ is large enough, it is possible to achieve better regret guarantees, since the Lagrangian space can be bounded by a quantity which is “almost” independent of T.\n\n> [5]\n\nWe apologize with the Reviewer since Equation (2) contains a typo. The corrected version is $\\ell_t(x_h,a_h)=\\Gamma_t+ \\sum_{i=1}^m \\lambda_{t,i}g_{t,i}(x_h,a_h)-r_t(x_h,a_h)$, which is the definition of the lagrangian losses fed to the primal algorithm.\n\n> [6]\n\nAlgorithm 3 outputs a policy $\\pi_{t+1}$ , which is the policy that the primal algorithm suggests to play at the next episode based on the previous observed losses.\n\n> [7] \n\nOne of the main challenges of our work is to build an algorithm which does not require the Slater’s parameter $\\rho$ in input. Notice that, when $\\rho$ is known, it is sufficient to optimally bound the Lagrange multipliers decision space to $H/\\rho$ in order to have best-of-both-worlds guarantee. Differently, when $\\rho$ is not known, it is necessary to resort to different techniques to show that the Lagrange multipliers are bounded during the learning dynamic. We tackle this aspect employing the no-interval regret property of the primal and the dual regret minimizers.\n\n> [8]\n\n$OPT^\\mathcal{w}$ is an alternative baseline for the setting with adversarial constraints. This baseline is computed considering the optimal fixed policy which satisfies the constraints at each episode (and not only on average). The introduction of this weaker baseline is motivated by the fact that, when competing against $OPT^\\mathcal{w}$, it is possible to guarantee sublinear regret and constraints violation simultaneously.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, to some extent.", "experimental_designs_or_analyses": "Yes, to some extent.", "relation_to_broader_scientific_literature": "The main novelty is that the authors provide the first best-of-both-worlds algorithm for CMDPs with bandit feedback.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "N/A.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "Page 1:\nCan you please connect the study of constraint violation to the classical RL literature?\n\nPage 2:\nCan you please elaborate on the notion of episode-dependent learning rate?\n\nPage 3:\nIn Algorithm 1, what are the inputs and the outputs?\n\nPage 4:\nCan you please further explain Condition 2.5?\n\nPage 5:\nCan you please explain Equation (2)?\n\nPage 6:\nWhat is the output of Algorithm 3?\n\nPage 7:\nCan you please elaborate on Lines 334--336?\n\nPage 8:\nWhy are you defining OPT^\\mathcal{w} in this way?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies constrained MDPs with rewards and constraints that can be either stochastic or adversarially selected. They provide best-of-both worlds results with respect to the constraints (no logarithmic bound for stochastic regret).

Its main contributions are
1) Relaxing the full-information assumption on rewards/constraints compared to prior work
2) Obtaining results even when the Slater's condition does not hold (or, 
 can be very small).
3) Use a lower computational complexity approach to get rid of solving a convex optimization problem to find the occupancy measure over all the possible transition probability sets.

None of these in isolation is novel. Nonetheless combining all parts seems to be non-trivial. 

All reviewers who engaged in the discussion agree that the proofs are sound, but the technical novelty is somewhat limited.
Decision: Accept (poster)