Taming Adversarial Constraints in CMDPs
Authors: Francesco Emanuele Stradi
Anna Lunghi
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Venue: NeurIPS 2025 poster ()
Keywords: CMDP
Online Learning
Constraints
Primary area: theory

Abstract: In constrained MDPs (CMDPs) with adversarial rewards and constraints, a known impossibility result prevents any algorithm from attaining sublinear regret and constraint violation, when competing against a best-in-hindsight policy that satisfies the constraints on average. In this paper, we show how to ease such a negative result, by considering settings that generalize both stochastic CMDPs and adversarial ones. We provide algorithms whose performances smoothly degrade as the level of environment adverseness increases. In this paper, we show that this negative result can be eased in CMDPs with non-stationary rewards and constraints, by providing algorithms whose performances smoothly degrade as non-stationarity increases. Specifically, they attain $\widetilde{\mathcal{O}} (\sqrt{T} + C)$ regret and positive constraint violation under bandit feedback, where $C$ measures the adverseness of rewards and constraints. This is $C = \Theta(T)$ in the worst case, coherently with the impossibility result for adversarial CMDPs. First, we design an algorithm with the desired guarantees when $C$ is known. Then, in the case $C$ is unknown, we obtain the same results by embedding multiple instances of such an algorithm in a general meta-procedure, which suitably selects them so as to balance the trade-off between regret and constraint violation.

Taming Adversarial Constraints in CMDPs
Francesco Emanuele Stradi
Anna Lunghi
Politecnico Milano
Politecnico di Milano
francescoemanuele stradi @po iimi
anna. www.llunghhipp. @aaphh@@pllmmm. it
Matteo Castiglioni
Alberto Marchesi
Politecnico di Milano
Politecnico Milano
matteo. peaettiggioiioooliiimmo
alberto. mww.meaiiiiiooo mwtessippommmm..mmm
Nicola Gatti
Politecnico di Milano
cola. wataaaagttp@ppmmm.mm.mmm
Abstract
In constrained MDPs (CMDPs) with adversarial rewards and constraints, a known impossibility result prevents any algorithm from attaining sublinear regret and constraint violation, when competing against best-in-hindsighe policy that satisfies the constraints on average. this paper, we show how to ease such a negative result, by considering settings that generalize both stochastic CMDPs and adversarial ones. We provide algorithms whose performances smoothly degrade as the level environment adverseness increases. Specifically, they attain Ó(vT C) regret and positive constraint violation under bandit feedback. where measures the adverseness of rewards and constraints. This is C ( in the worst case, coherently with the impossibility result for adversarial CMDPs. First, we design an algorithm with the desired guarantees when C is known. Then, in the case C is unknown, we obtain the same results by embedding multiple instances of such algorithm in a general meta-procedure, which suitably selects them so as to balance the trade-off between regret and constraint violation.
Introduction
Reinforcement learning [Sutton and Barto. 2018 concerned with settings where learner sequen- tially interacts with environment modeled Markov decision process (MDP) [Puterman 2014). Most of the works in the field focus on learning policies that maximize learner's rewards. However, in most of the real-world applications of interest, the learner also has to meet some additional require- ments. For instance, bidding agents ad auctions must not deplete their budget [Wu et al. 2018 He et al. 2021]. J, users of recommender systems must not be exposed offending content [Singh et al. 2020]. and online companies must ensure a minimum number items are sold while maximizing the associated profits (Stradi et al., 2024a]. Requirements of this kind can be usually captured by means of constrained MDPs (CMDPs) Altman 1999], which generalize MDPs by specifying constraints that the learner has to satisfy while maximizing their rewards.
In this paper, we study online learning problems in episodic CMDPs (see, e.g., [Efroni et al. 2020 where the goal of the learner is twofold. On the one hand, the learner wants to minimize their regret, which measures how much reward they lost over the episodes compared to what they would have obtained by always using best-in-hindsight constraint-satisfying policy. On the other hand, the learner wants to ensure that the (cumulative) constraint violation is minimized during the learning
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

process. Ideally, one seeks to design algorithms with both regret and constraint violation growing sublinearly in the number of episodes T. A crucial feature distinguishing online learning problems in CMDPs is whether rewards and constraints are selected stochastically
adversarially. Most
of the works in the literature focus on the case in which constraints are stochastic (see, e.g., [Wei]
et al..) 2018 Zheng and Ratlifi] [220 Efroni et al., 2020, Qiu et al., 2020 Liu et al. [221] Bai et al. 2023 ). with only one exception addressing settings with adversarial constraints [Stradi et al. 2024b
2025c This is primarily motivated by well- impossibility result by Mannor et al. 2009
which prevents any learning algorithm from attaining both sublinear regret and sublinear constraint violation, when competing against best-in- hindsight policy that satisfies the constraints average. However, dealing with adverrsriially-seeeee selected rewards and constraints is of paramount importance to cope with real-world environments, which are typically non-stationary. For instance, adversarial reward and constraints are present in those settings where the environment encompasses other agents.
1.1 Original Contributions
The main contribution of this paper is to show how to ease the negative result by Mannor al. [209)] In order to do so, we consider non-stationary settings that generalize both stochastic CMDPs and adversarial ones. Specifically, we address CMDPs where rewards and constraints are selected from probability distributions that are allowed to change adversarially from episode to episode. Thus, our CMDPs bridge the gap between fully stochastocc and adversaadlll ones. We design algorithms whose performances-in terms of regret and constraint violation-smoothe degrade as a suitable measure of the adverseness of rewards and constraints increases. This is called (adversarial) corruption, and intuitively quantifies how much the distributions of rewards and constraints vary over the episodes with respect to some suitable "fictitious" non-corrupted counterparts.
We propose algorithms that attain Ö(VT + C) regret and constraint violation, where C' denotes the corruption of the setting. We remark that C = ( in the worst case, and, thus, our bounds are coherent with the impossibility result by Mannor et al. 2009]. Moreover, in stochastic CMDPs, our bounds reduce to -fate-of-the-art Ō( ( bounds Efroni et al. 2020). Notably, our algorithms work under bandit feedback, namely by only observing rewards and constraint costs of the state-action pairs visited during episodes. Moreover, they are able to manage positive constraint violation. This means that they do not allow for negative violation (i.e., constraint satisfaction) to cancel out positive one across different episodes. This a crucial for most of the practical applications. For instance, in autonomous driving, avoiding a collision does not "repair" a previous crash.
In the first part of the paper, we design an algorithm (NS-SOPS) that works assuming C is known. NS-SOPS achieves ÖVT + C) regret and positive constraint violation by using a policy search method optimistic in both reward maximization and constraint satisfaction. Specifically, NS-SOPS incorporates C in confidence bounds, so as to "boost" optimism and achieve the desired guarantees.
In the second part of the paper, we show how to embed the NS-SOPS algorithm in a meta-procedune that allows to achieve Ö(VT + C) regret and positive constraint violation when C is unknown. The meta-procedure works by instantiating multiple instances of an algorithm for the case in which C is known, each one taking care of a different "guess" on the value of C. Specifically, the meta-procedure acts as a master by choosing which instance to follow in order to select policy at each episode. To do so, it employs adversarial online learning algorithm, which is fed with losses constructed starting from the Lagrangian of the CMDP problem, suitably modified to account for positive constraint violation.
1.2 Related Works
CMDPs with stochastic rewards and constraints have been widely investigated. However, their adversarial counterparts are still largely unexplored. In the following, we discuss the works that are most related to ours, while A provides a comprehensive survey of related works.
Qiu et al. 2020 provide the first primal-dual approach to deal with episodic CMDPs with adversarial losses and stochastic constraints, achieving, under full feedback, both sublinear regret and sublinear (non-positive) constraint violation (i.e,, allowing for cancellations). Stradi et al. [2025a] are the first to tackle CMDPs with adversarial losses and stochastic constraints under bandit feedback, by proposing an algorithm that achieves sublinear regret and sublinear positive constraint violation. These works

---

do not consider settings where constraints may change over the episodes. Stradi et al. [202bb 2025c] study CMDPs with adversarial constraints: the former studies CMDPs with full feed the latter focuses on the bandit-feedhack setting. Given the impossibility result by Mannor et al. [2009] they propose algorithms that attain sublinear (non-positive) constraint violation (i.e., with cancellations allowed) and a fraction of the optimal reward, thus resulting in a regret growing linearly in 7. We show that sublinear regret and sublinear constraint violation can indeed be attained simultancously if one takes into account the corruption C. Moreover, let us remark that our algorithms deal with positive constraint violation, and, thus, they are much more general than those in [Stradi et al. 2024b 2025c].
The work is also closely related to corruption-robuct online learning, which, while estabbssallished in different settings, such as unconstrained MDPs with corrupted transitions, remains largely unexplored for CMDPs. Specifically, Lykouris et al. [022 are the first to establish sublinear regret guarantees for MDPs with corrupted rewards and transitions under bandit feedback, achieving O(CVT) regret without requiring prior knowledge of C. Chen et al. [202]] are the first provide regret bound that additively depends on C, namely of the order of O(VT + C²). This result is improved by Wei ct al. (002)). who show a regret bound of order Ö(VT + C) under the same conditions. Finally, very recently Jin et al. [2024] study MDPs with adversarial rewards and corrupted transitions, under bandit feedback and unknown corruption value, attaining regret Ö(VT + CP), where CP is the corruption associated with the transitions. While the techniques employed in these works share some similarities with ours, they cannot be easily extended to CMDPs. This is because CMDPs involve a dual objective: minimizing the regret while ensuring low constraint violation. This cannot be achieved through standard corralling techniques that are commonly used in the corruption-robust online learning AAgaral et al. 2017 as these are designed to deal with singlc-objective settings.
Finally, there is also a related literature that focuses on non- non-stationary CMDPs. While in such settings the learner-environment interaction closely resembles ours, the performance metrics are different from ours and not easily comparable. Specifically. Ding and Lavaei [023] and Wei al. (203)) consider the case in which rewards and constraints are non-stationary. assuming that their variation is bounded. Our work differs from theirs in multiple aspects. First, we consider positive constraint violation, while they allow for cancellations. As concerns the definition of regret, ours and that by Ding and Lavaei [2023) and Wei et al. [2023] are not comparable. Indeed, they employ dynamic regret baseline, which, in general, is harder than the static regret employed in our work. However, they compare learner's performances against a dynamic policy that satisfies the constraints every round. Instead, we consider a policy that satisfies the constraints on average, which can perform arbitrarily better than a policy satisfying the constraints every round. Furthermore, the dependence on T in their regret bound is much worse than ours, even when the non-stationarity is small, namely when it is a constant independent of T and does not affect our regret bound. Finally, we do not make any assumption on T, while the bounds in (Wei et al., 2023 only hold for large T.
2 Constrained Markov Decision Processes
We study episodic constrained MDPs (CMDPs) Altman 1999. in which learner interacts with an unknown environment over T episodes, with the goal of maximizing long-term rewards subject to some constraints. X is finite set of states of the environment, A is finite set of actions available to the learner in each state, while the environment dynamics is governed by transition function P X x A X - [0, 1], with P(a' [x, a) denoting the probability of going from state x e X to r' X by taking action a E A At each episode sampled according to a probability distribution R2, with ( a) being the reward of taking action a E A in state x E X at episode t. Moreover, a constraint cost matrix G, E [0, 1] X Xx X is sampled according a probability distribution G., with gt, (2, a) being the cost of constraint e [m] when
[T] a reward vector I'. [0, 1||XXA| is
'In this paper, we consider w.l.o.g. loop-free CMDPs. This means that is partitioned into layers No...., Xr. such that the first and the last layers are singletons, i.e., Xo = {zo] and Xt. = {II]. Moreaver, the loop-free property implies that (x'' a) > 0 only if x' E X and x E Xx for some & E L0..L-11 1]. Notice that any episodic CMDP with horizon L that is not loop-free can be cast into doop-free one by suitably duplicating the state space L times, i.e., a state x mapped to a set of new states (z, k)., where & [O... L).
II this paper, we denote by Ja... 6) the set of all the natural numbers from E N to E N (both included), while [b] = [1. ...... b] is the set of the first b NN natural numbers.
3

---

taking action E A in state E X at episode t. We also denote by 9t.s E [0, X||X the vector of all the costs It,, a) associated with constraint at episode Each constraint requires that its corresponding expected cost is kept below a given threshold. The thresholds of all the m constraints are encoded in a vector a E [0, T. with a, denoting the threshold of the i-th constraint.
We consider a setting in which the sequences of probability distributions {Re and {G are selected adversarially. Thus, reward vectors rt and constraint cost matrices G. are random variables whose distributions are allowed to change arbitrarily from episode to episode. In other terms, they exhibit non- con-stationarity. To measure how much such probability distributions change over the episodes, we introduce the notion of (adversarial) corruption. In particular, we define the adversarial corruption C, for the rewards as:
C ==
min rEfo,I]IXxal
Σ LE|T]
[ rl1
Intuitively, the corruption C, encodes the sum over all episodes of the distances between the means E|r:] of the adversarial distributions R. and a "fictitious" non-corrupted reward vector r. Notice that a similar notion of corruption has been employed in unconstrained MDPs to measure the non- stationarity of transition probabilities; see [Jin et al. 2024]. In the following, we let r E [0, 1]|XXA] be reward vector that attains the minimum the definition of C,- Similarly, we introduce the adversarial corruption CG for constraint costs, which is defined as follows:
Ca =
min GE(O.T]IXX AE(T] EE(m]
max
[E[g,.] -9il11,
where 9; is the i-th component of G. In the following, we let G [0, x|| be the constraint cost matrix that attains the minimum in the definition of Ca. Finally, the total adversarial corruption is defined C' max C.
Algorithm D summarizes how the learner interacts with the environment at episode
Algorithm 1 Learner-Environneen Interaction
t te {T. In particular, the learner chooses a
1: R2 and Gi are chosen adversarially
policy π X A [0, 1] each episode,
2: Choose a policy म, : X + [0, 1]
defining a probability distribution over ac-
3: Observe initial state
tions be employed in each state. For ease of notation, we denote by (-|xx) the prob- ability distribution for state X, with T (a(z) being the probability of selecting action A. Let us remark that we as-
4: for i = O.... 1-1do do
5:
Play ak (=((
6: Observe ri (z ax) and gt, (IK ax) for e [m]
7: Observe new state Tx+1 P P(-
sume that the learner knows X and A, but they do not know anything about P. Moreover, the feedback received by the learner after each episode is bandit, as they observe the realizations of rewards and costs only for the state-action pairs (IK, ax) actually visited during that episode.
Occupancy Measures Given a transition function P and a policy n, we let ppt E [] x [ be the occupancy measure induced by P and æ. For E Xx, A, x E XR41 with k E [0. [O... L-1]:
q Pxx (I, a, x') = P[I+ = x, a2 = a, Tx+1 = x I' T],
which is the probability that the learner reaches state x, plays action a, and gets to state x'. Moreover, x²x and (( = Enea Pix (x. a). Follow-
we also define y (xr, a) == Ex'exe
ing |Rosenberg and Mansour 2019b), we say that E [0, 1]lXXXxXX is a valid occupancy measure of an episodic loop-free CMDP if and only if satisfies the following three conditions:
ΣΣ
Σ
g(x, ((x,a,x')= =1 Vk 00... 1-....-1111. 1].
Xx DE A'
(ii) Σ Σ
g(z,a,x))= =
Σ
Eg ala' a,)) Vk E [1... 11, Xx.
aE x1E
x' VEXX-1REA
(ii)
P9 P.
where P is the transition function of the CMDP and PM is the one induced by (as outlined next). Notice that any valid occupancy measure g induces a transition function P and a policy л², which are defined as Pa (a' (x, a) = g(x,a.²)) and 2 (afxr) = 2(x.a)
((x,a)
[(m)

---

2.1 Performance Metrics
In order to define the performance metrics used evaluate our online learning algorithms, we need to introduce an offfine optimization problem. Given a CMDP with transition function P. we define the following parametric linear program (Program (3), which is parametrized by a reward vector r E [0, 1] XxA), a constraint cost matrix G E [0, x|XxAA|m and a threshold vector a E [0, L)
[maxgeAPP) rTy s.t. G
OPT,
where q E [0.1] is a vector encoding an occupancy measure, and (P) is the set of all valid occupancy measures given the transition function P. We say that an instance of Program (3) satisfies Slater's 's condition if the following condition holds.
Condition (Slater). There exists an occupancy measure qº E A(P) such that Go of a.
We also introduce a prrblemm-ppecifee feasibilityy parameter P [0, L] related to Program (3) defined as / == (PP) min [ G q), Intuitively, represents by how much feasible solutions to Program (3) strictly satisfy the constraints. Condition I is equivalent to say > O, and, whenever م 0, there is occupancy measure that strictly satisfies the constraints in Program (3)
Now, we introduce the notion of (cumulative) regret and (cumulative) positive constraint violation, which are the performance metrics used to evaluate algorithms. The regret over T episodes is
R OPT
Σ 6E[2]
E(r.l" P.
F.G.a
where = 1. ΣT B[rr] and and B|G.). In the following, we denote by q- an occupancy measure solving Program (3) instantiated with F, G. and a, while its corresponding policy is x". Thus, OPT,
T:
R.G.o OPT,,G.o = F
and the regret can be written as Ry = Ei= E[r.] (q* - ). Furthermore, the cumulative positive constraint violation over T episodes is defined as
4² ==4"
V
max 2EIm) LE|T]
[BG PiT. a] where we let [+] max +).
For ease of notation, we refer to g as qr, thus omitting the dependency on P and n.
Remark (Relation with addersarial/stoohastiic CMDPs). Our setting naturally encompasses both stochastic and adversarial CMDPs. Indeed, if the distributions Rr and G. do not change over the episodes, then we recover a CMDP with stochastic rewards and constraints. Moreover, when the supports Rf and G. are singletons (and, thus, mean values are fully revealed), our setting reduces to a CMDP with adversarial rewards and constraints, since R2 and G, are selected adversarially.
Remark 2 (Impossibility results carrying over from adversarial CMDPs), Mannor al. (2009) show that, in online learning problems with constraints selected adversarially it is impossible to achieve both regret and constraint violation growing sublinearly T. This result holds for regret definition that corresponds to ours. Thus, it carries over to our setting. This is why we look for algorithms whose regret and positive constraint violation scale as Ö(VT C), with a linear dependency on the adversarial corruption C. Notice that the impossibility result by Mannor et al.) al.) (2009) does not rule out the possibility of achieving such a guarantee, since regret and positive constraint violation are not sublinear when C grows linearly in T, as could be the case a classical adversarial setting.
3 Learning When C is Known: More Optimism is All You Need
We start studying the case in which the learner knows the adversarial corruption C. We propose an algorithm (called NS-SOPS, see Algorithm ( which adopts suitably-designed UCB-like approach encompassing the adversarial corruption C in the confidence bounds of rewards and constraint costs. This effectively results in "boosting" the optimism of the algorithm, and it allows to achieve regret and positive constraint violation of the order of Õ(VT + C). The NS-SOPS algorithm is a crucial building block to deal with the case in which C' is not known, as we show in the following section.
Given a vector z. we denote by [b], its i-th component.
5

---

3.1 NS-SOPS: Non-Stationary Safe Optimistic Policy Search
Algorithm 2 provides the pseudocode of the non-stationary safe optimistic policy search (NS-SOPS) algorithm. The algorithm keeps track of settabllydefined confidence bounds for transitions, rewards, and constraint costs. At each episode E [T]. the algorithm builds a confidence set P. for the transition function P by following the same approach as Jin et al. (2020) (see Appendix G for its definition). Instead, for rewards and constraint costs, the algorithm adopts novel enlarged confidence bounds, which are suitably designed to tackle non-stationarity.
Given any confidence parameter (0, by letting Ne a) be the total number of visits to the state-action pair (I, a) E X X A up to episode f, the confidence bound for the reward rz(zz, a) is In(2rix] (1 a) = min 1. 2max (2.a). + (F..))
C
C
while the bound for the constraint T
cost (r, a) is C)(z,a) min (1. 2 [...s (.x. + }]. Intuitively, the first term in the expressions above is derived from allows to deal with the non-stationarity of rewards and constraint costs, while the third term is needed to bound how much the averages and [G]; differ from their "fictitious" non-corrupted counterparts r" and [G*]. respectively. Algorithm aaaso computes empirical rewards and constraint costs. At each episode L E [T']. for any state-action pair (I, a) X x A and constraint E [m], such estimates defined (r
inequality, the second term
a) Σrsta (=(x,a))((z.a) and (z, a) Σ-enl [_(0.0))... max where I, a) = if and only if the pair (xc, a) is visited during episode т, while (z, = 0
max [ax[NN (N((2.)).)
otherwise, For case of notation, we let G. E [0, 1] x Alxm be the matrix with components (z, a). We refer to Appendix C for a detailed treatment of all the results related to confidence bounds.
Alg Algorithm Sorrtthm@xxlecte selects policies with an UCB-like ap- proach encompassing optimism in both rewards and constraints satisfaction, following an approach similar to that employed by Efroni al. [2020]. Specifically, at each episode i E [T]] and for any acteon pair (z,a) a) E X A, the algorithm employs an upper confidence bound for the reward (2 a). defined as Fz a)= == fz a) + Φe(2, a), while it uses lower confidence bounds for the con- straint costs (x, a), defined as (2, a) =
Algorithm 2 NS-SPPS
Require: C. E 1)
1: тi < select any policy
2: for L LE [T] do
3: Choose policy me in Algorithm I and
observe feedback from interaction
4:
Compute Pt, Fi, and G. + solution to OPT-CBA(P..FF.G.
5:
6:
if problem is feasible then
7:
q++1 4
(r, Ex a) for every constraint i E [m]] Then, by letting Fe [0, 1]|XAAl be the vector with components (1c, a) and G, be the matrix with en- tries g, (z., a), Algorithm 2 chooses the policy to
8:
else
9:
9++1 + take any E A(P:)
10: T++1 <- a0++1
be employed in the next episode + 1 by solving the following linear program:
aarg maX
F,4 q s.t. G 5/95a, a,
OPT-CBA(P))
where A(P,) is the set of all the possible valid occupancy measures given the confidence set P. (see Appendix G If OPT-CBA/P))...G.aaa is feasible, its solution is used to compute policy to be employed in the next episode, otherwise the algorithm uses any occupancy measure in A(P.).
3.2 Theoretical Guarantees of NS-SOPS
Next, we prove the theoretical guarantees attained by Algorithm proofs of the theorems and associated lemmas). First, we analyze the positive cumulative violation incurred by the algorithm. Formally, we can state the following result.
2
(see Appendix D for complete
Theorem 2. Given any E (0, 1), with probability at least - 85, Algorithm violation VT = O (L]X) / /A/T In (mT]a] A1/8) + -In(T))][AIIC)
2 attains positive
Intuitively, Theorem 2 is proved by showing that every constraint-satisfyine occupancy measure is also feasible for Program with high probability. This holds since Program confidence bounds for constraint costs. Thus, in order to bound Vr, it is sufficient to analyze at which
(4) employs lower

---

rate the feasible region of Program 4 concentrates to the tee one (i.e., the one defined by G in Program (3). Since by definition of (z, a) the feasibility region of Program concentrates as 1/v2- + C/t, the resulting bound for the positive violation Vr is of the order of O(VT CC.
The regret guaranteed by Algorithm D formalized by the following theorem.
Theorem 3. Given any å (0, 1), with probability at least 1 - 96, Algorithm attains regret
Ry =0 ( (TIXIAAA) + ln(T)|X]JA(C)
Theorem 3 is proved similarly to Theorem 2 Indeed, since every constraint-satisfying occupancy measure is feasible for Program (4) with high probability, this also holds for q", as it satisfies constraints by definition. Thus, since by definition of de (zx, a) the upper confidence bound for the rewards maximized by Program (4) concentrates as 1/v1 + C/t, the regret bound follows.
Remark (What if some under/overestimate of is available). We also study what happens if the learner runs Algorithm 2 with an under/overestimatee on the adversarial corruption as input. We defer to Appendix E all the technical results related to this analysis. In particular, is possible to show that any underestimate
C does not detriment the bound on VT, which remains the one in Theorem On the other hand, overestimate on C, say C C. results in bound on Vr of the order of O VT + +C), which is worse than the one in Theorem 2 Intuitively, this is because using an overestimate makes Algorithm to0 conservative. As a result, one could be tempted to conclude that running Algorithm with an underestimate of C as input is satisfactory when the true value of C is unknown. However, this would lead to a regret Rr growing linearly in T. since, intuitively, a regret-minimizing policy could be cut off from the algorithm decision space. This motivates the introduction of additional tools to deal with the case in which Ct is unknown, as we do in Section 4
4 Learning When C is Not Known: A Lagrangified Meta-Procedure
In this section, we go beyond Sec- tion by studying the more relevant case in which the learner does not know the value of the adversarial cor- ruption C. In order to tackle this chal- lenging scenario, we develop a meta- procedure (called Lag- FTRL, see Al- gorithm 3) that instantiates multiple instances of an algorithm working for the case which C' known, with each instance taking care of a different "guess" on the value of C. The Lag-FTRL algorithm is in- spired by the work of Aggaraal et al. (2017) in the context of classical (un- constrained) multi aaltid bandit prob- lems. Let remark that standard "coralling" techniques, such as the one proposed by AAarwal et al. [2017). cannot be easily generalized to our setting, since our objective is twofold: minimizing the regret while simulta- neously ensuring small constraint vio- lation. In this section, to deal with our non-stationary CMDP setting, we let Lag- Lag-FTRL instantiate multiple instances of the NS-SOPS algorithm in Section 3
Algorithm Lag-FFRL
Require: 8E (0, 1)
A Lm+1 M <- [log, T
2: 7 /m(D//O//TM, 11
2Am 2Am
3: for j E {M] do
4: Alg' + stabilized Algorithm 2 with C = 2
W1, +- 1/M for all j E [M]]
6: for t E [T] do
7:
Sample index jr ~ we
m? +- policy that Alg would choose
9: Choose policy T in Algorithm and observe
feedback from interaction
10: Let Alg" observe received feedback
11:
for [M/] do
12:
Build le.j as in Equation
5 6
13:
Build bt.j in Equation
14: We++1 +- arg min w T
Σ
(fe
b,)
weAM. *y21/r
TE(:]
JE[M]
Wj
4.1 Lag-PTRL: Lagrangified FTRL.
At a high level, the Lagrangified follow- hererreheeegggarize--eeeede (Lag-FTRL for short) algorithm works by instantiating several instances of Algorithm 2 suitably stabilized (see section H., with each instance Alg" being run for different "guess" of the (unknown) adversarial corruption value C.
7

---

The algorithm plays the role of a master by choosing which instance Alg' to use at each episode. The selection done by employing an FTRL approach with a suitable log-barrier regularization. In particular, at each episode & E [7], by letting Alg be the selected instance, the Lag-FTRL algorithm employs the policy nT!. prescribed by Alg" and provides feedback to instance Alg only.
The Lag-FTRL algorithm faces two main challenges. First. the feedback available to the FTRL procedure implemented at the master level is partial. This is because, at each episode t E [T]. the algorithm only observes the result of using the policy Tt' prescribed by the chosen instance Alg", and not those of the policies suggested by other instances. The algorithm tackles this challenge by employing optimistic loss estimators in the FTRL selection procedure, following an approach originally introduced by Neu [213]] The second challenge originates from the fact that the goal of the algorithm is to keep under control both the regret and the positive constraint violation. This is accomplished by feeding the FTRL procedure with losses constructed starting from the Lagrangian of the offline optimization problem in Program (3), and suitably modified manage positive violations.
The pseudocode of the Lag-FTRL algorithm is provided in Algorithm 3 At Line 4 it instantiates M = [log, I'| instances of Algorithm 2 with each instance Alg'. for [M receiving input a "guess" on the adversarial corruption C = 2). Notice that, to every instance of Algorithm 2 standard doubling trick and stabilization procedure is applied (see Algorithm 3 for additional details). This modification to Algorithm is necessary to guarantee that each instance j attains a regret and positive cumulative constraints violation which linearly degrade in Mry = 1/min,,trr wiy and C, when employed by the master algorithm. The algorithm assigns weights defining a probability distribution to instances Alg', with wr, [o, 1] denoting the weight of instance Alg' episode t E [T]. We denote by Wi E AM the weight vector at episode I, with AM being the M-dimensional simplex. At the first episode, all the weights W1j are initialized to the value 1/M (Line Then, each episode E [T], the algorithm samples an instance index je E [M]] according to the probability distribution defined by the weight vector (Line 7) and it employs the policy TT!" prescribed by Alg" (Line ) The algorithm observes the feedback from the interaction described in Algorithm [ and it sends such a feedback to instance Alg" (Line 10p. Then, at Line 12 the algorithm builds an optimistic loss estimator to be fed into each instance Alg'. In particular, at episode E (T] and for every j E [M], the optimistic loss estimator is defined as:
I(J 5) (1 L Σ Wi, + I!
o. - - )
ro(a ( Σ =E(m)
+A +A
(
(5)
where y is suitably-defined implicit exploration factor, (at af) is the state-action pair visited at layer ls during episode f, A is suitably- upper bound on the optimal values of Lagrangian multipliers 1 G is the matrix of empirical constraint costs built by the instance Alg' of Algorithm at episode t, while qf is the occupancy measure computed by instance Alg' of Algorithm 2 at t.
Finally, the algorithm updates the weight vector according to an FTRL update on a cut decision space with suitable bog-barrier regularization and bonus term b, defined
b
(mmA,3 + B2) + (v m 84
VT
(vi, - 12-1a))
(6)
where Vi.j = max, <i and the parameters 33 are linked to the performance of Algorithm (see
Line 13 and Section F.2. for additional details). See Line [4] the complete definition of the update. The bonus term purpose is to balance out the term related to the difference between the performance of Algorithm 2 Jupdated at each episode and the performance of its stabilized version, which works under the condition imposed by the master algorithm.
4.2 Theoretical Guarantees of Lag-FTRL
Next, prove the theoretical guarantees attained by Algorithm S (see Appendix F for complete proofs of the theorems and associated lemmas). As a first preliminary step. we extend the well-known strong duality result for CMDPs (Altman 1999 to the case of bounded Lagrangian multipliers.
'Notice that, in the detinition of A. p is the feasibility parameter of Program for the reward vector 7, the constraint cost matrix G. and the threshold vector a. In order to compute A. Algorithm 3 needs knowledge of p. Nevertheless, results continue hold even if Algorithm is only given access lower bound on p.
8

---

Lemma 1. Given CMDP with a transition function P. for every reward vector r E [0.1]1xx41
constraint cost matrix G E [0. 1 1|Ixx||xm and threshold vector E L). if Program satisfies
Slater's condition (Condition
min max TT 9 INI
Σ X1 G q --alg
a];;
max min r rT QEb(P) (A
- se[m]
A [ a]
OPT G,
where À Imm is vector of Lagrangian multipliers and p is the feasibility parameter of Program
Intuitively, Lemma [ states that, under Slater's condition, strong duality continues to hold even when restricting the set of Lagrangian multipliers to the X Rg having ||^l| bounded by 4/p. Furthermore, we extend the result in Lemma to the case of a Lagrangian function suitably-man moddifed to encompass positive violations. We call it positive Lagrangian of Program (3), defined as follows.
Definition 1 (Positive Lagrangian). Given a CMDP with a transitions P. for every reward vector r E [0, xxA constraint cost matrix E [0, 1| and threshold vector a E [0, Li the positive Lagrangian of Program
B
is defined a function & : BR4 A(P) - R such that for every B 2 0 and q E A(P).
C (3. q) = T 9 - 3 [m)(m] [ q
The positive Lagrangian is related to the Lagrangian of a variation of Program 3 in which the I:] operator is applied to the constraints. Notice that such a problem does not meet Slater's condition, since, by definition of [-] , it does not exist an occupancy measure qº such that [G =a < for every i E [m]] Nevertheless, we show that some sort of strong duality result still holds for C(4p,,)). when Slater's condition met by Program 33. This is made formal by the following theorem.
Theorem 4. Given CMDP with transition function P. for every reward vector r [0, x|
constraint cost matrix G E 00, x||XxxXxxx and threshold vector [0, L.m,, if Program 33 satisfies
Slater's s condition (Condition D. then the following holds:
((4p,9)) = max r (PA(P)
max
Σ xE|m]
[G
a] = OPT,,G.o
PEA(P)
where p is the feasibility parameter of Program
Theorem 4 intuitively shows that a L/p multiplicative factor the positive constraint violation is enough to compensate the large rewards that non-feasible policies would attain when employed by the learner. This result is crucial since, without properly defining the Lagrangian function optimized by Algorithm 3 the FTRL optimization procedure would choose instances with both large rewards and large constraint violation, thus preventing the violation bound from being sublinear. By means of Theorem 4 it is possible to provide the following result.
Theorem 5. If Program (3) instantiated with r, G and a satisfies Slater's 's condition (Condition then, given any 0 E (0, 1). with probability least 1 345, Algorithm 3 3ttaains positive constraint vi- olation V/2 O (m² L [ X //IA////oo (mn[xx|///2) ( 2ann2I. L| || log(T) 3 log (log(T)/a)=
mLL L log (
Intuitively, to prove Theorem 5 it is necessary to bound the negative regret attained by the algorithm, i.., how better Algorithm 3 can perform in terms of rewards with respect an optimal occupancy in hindsight q² Notice that this is equivalent to showing that the FTRL procedure cannot gain more than OPT r,G. a. by playing policies that are not feasible, or, equivalently, by choosing instances Alg' with large corruption guess, which, by definition of the confidence sets employed by Algorithm [ may play non-feasible policies attaining large rewards. This is done by employing Theorem { which shows that the positive Lagrangian does not allow the algorithm achieve too large rewards with respect q² Thus, the violations are still upper bounded by ÖVV
Finally, we prove the regret bound attained by Algorithm 3
Theorem If Program 33) instantiated with T, G and a satisfies Slater's condition (Condi-
tion D. then, given any 8 E 1), with probability at least 1 306, Algorithm 3 attains re- gret Ry Om L / MA[T (1TT)x1AA/8) IT)(T)? + m² m²L || log(T)² log (log(T)/6)
m [IAI

---

Bounding the regret attained by Algorithm reerihrerrrruureee different techniques with respect to bounding constraint violation. Indeed, strong duality not needed, since, even if A is set a too small value and thus the algorithm plays non-feasible policies, then the regret would still be sublinear. The regret bound is strongly related to the optimal value of the problem associated with the positive Lagrangian, which, by definition of [+]+ cannot perform worse than the optimum of Program (3) in terms of rewards gained. Thus, by letting j be the index of the instance associated with true corruption value C. proving Theorem reduces to bounding the regret and the constraint violation of instance Alg"". with the additional challenge of bounding the estimation error of the optimistic loss estimator. Finally, by means of the results for the known C case derived Section we are able to show that the regret most ((VT C)2 which the desired bound.
Acknowledgments
This paper is supported by the Italian MIUR PRIN 2022 Project "Targeted Learning Dynamics: Computing Efficient and Fair Equilibria through No-Regret Algorithms", by the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU program within the PNRR- PE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainability, No. 1011 (20237.
References
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling band of bandit algorithms. In Conference on Learning Theory, pages 12-38. PMLR, 2017.
E. Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learn- ing. In Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Informa- tion Processing Systems, volume 21. Curran Associates, Inc., 2008. https::///// neurips. http://pe....00oloeeeeeeeeeeee60
pdf
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference Machine Learning, pages 263-272. PMLR,
2017.
Francesco Bacchiocchi, Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Markov persuasion processes: Learning to persuade from scratch. arXiv preprint arXiv:2402.030077 2024.
Qinbo Bai, Vaneet Aggarwal, and Ather Gattami, Provably efficient model-free algorithm for mdps with peak constraints. arXiv preprint arXiv:2003.0555: 2020.
Qinbo Bai, Vaneet Aggarwal, and Ather Gattami. Provably sample-efficient model-free algorithm for mdps with peak constraints. Journal of Machine Learning Research, 24(60): 1-25,) 2023.
Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 2767-2783. PMLR, 17-23 Jul 2022a. httpst /ttp::/e//// mlr. www.ppresssveee perrss/v162/cee wwt.l///aaasiiiiioiiiaaa... html
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. A unifying framework for online optimization with long-term constraints. Advances in Neural Information Processing Systems, 35:33589-33602, 2022b.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Yifang Chen, Simon Du, and Kevin Jamieson. Improved corruption robust algorithms for episodic reinforcement learning. In International Conference on Machine Learning, pages 1 PMLR, 2021.
10

---

Yuhao Ding and Javad Lavaei. Provably efficient primal-dual reinforeement learning for cmdps with non-stationary objectives and constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 7396-7404, 2023.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-explotation in constrained mdps. 2020. URL http::////axxx..oorrgg org abs///0./..2/ 02189
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, 34(3):226-76. 2009.
Gianmarco Genalti, Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Data-dependent regret bounds for constrained mabs. arXiv preprint arXiv:2505.2000 2025.
Yue He, Xiujun Chen, Di Wu, Junwei Pan, Qing Tan, Chuan Yu, Jian Xu, and Xiaoqiang Zhu. A unified solution constrained bidding in online display advertising. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2993-3001, 2021.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4860-4869. PMLR, 13-18 Jul 2020. URL hwwp::ttttpp/oooeeee htttps:/pproeeednggs..u. mlr. prwss/essssseee ppwsssvv19//aapp/ v119/jin20c..hm
Tiancheng Jin, Junyan Liu, Chloé Rouyer, William Chang, Chen-Yu Wei, and Haipeng Luo. No- regret online reinforcement learning with adversarial losses and transitions. Advances in Neural Information Processing Systems, 36, 2024.
Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. In International Conference Machine Learning, pages 1944-3955 PMLR, 2019.
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34:17183-17193, 2021.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Coruption-robust exploration in episodic reinforcement learning. In Conference Learning Theory, pages 3242-3245. PMLR, 2021.
Shie Mannor, John N. Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Jour- nal of Machine Learning Research, 10(20):569 2009. URL http:://mml http:/imlrrrrr./////////.. org/papers. v10/mannor09a. html
Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL https:://pocceeee Paper pdf 4554556100FF3377011e00000...e
neurips. wwtpaper_fillleecee files/fffleepppee wtw.le//ppperr2////iiiee
Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online markov decision processes under bandit feedback. Advances in Neural Information Processing Systems, 23, 2010.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. Upper confidence primal-dual reinforcement learning for emdp with adversarial loss. H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15277-15287. Curran Associates, Inc., 2020. URLpsttss: p/proceess//ooordiiggg... neurips. cc 2020/ /t////illee//// http:///00000/lo//e....//////122 Paper. pdf

---

Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. In Wallach, H. Larochelle, A. Beygelzimer, d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019a. URL #0872ccbb6ca4cc255776666 3d868e 1bdf8 pdf
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5478-5486. PMLR, 09-15 Jun 2019b. URL https: http::://proceeding mlr
Ashudeep Singh, Yoni Halpem, Nithum Thain, Konstantina Christakopoulou, E Chi, Jilin Chen, and Alex Beutel. Building healthy recommendation sequences for everyone: A safe reinforcement learning approach. In Proceedings of the FAceTRec Workshop, Online, pages 26-27, 2020.
Francesco Emanuele Stradi, Filippo Cipriani, Lorenzo Ciampiconi, Marco Leonardi, Alessandro Rozza, and Nicola Gatti. A primal-dual online learning approach for dynamic pricing of sequen- tially displayed complementary items under sale constraints. arXiv preprint arXiv:2407.05791, 2024a.
Francesco Emanuele Stradi, Jacopo Germano, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Online learning in CMDPs: Handling stochastic and adversarial constraints. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 46692- mlr www..ppre.//..... h2tp://v3///sssa strdddiradd2444 24
46721. PMLR, 21-27 Jul 2024b. httttt:://ppcceeee html
Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning adversarial mdps with stochastic hard constraints. In Forty-second International Conference on Machine Learning, 2025a.
Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Optimal strong regret and violation in constrained mdps via policy optimization. In The Thirteenth International Conference on Learning Representationss 2025b.
Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Policy optimization for cmdps with bandit feedback: Learning stochastic and adversarial constraints. In Forty-second International Conference on Machine Learning. 2025c.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Chen-Yo Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pages 1043-1096. PMLR, 2022.
Honghao Wei, Arno Ghosh, Ness Shroff, Lei Ying, and Xingyu Zhou. Provably efficient model-free algorithms for non-stationary emdps. In International Conference on Artificial Intelligence and Statistics, pages 6527-6570. PMLR, 2023.
Xiaohan Wei, Hao Yu, and Michael J. Neely. Online learning in weakly coupled markov decision processes: A convergence time study. Proc. ACM Meas. Anal. Comput. Syst., 2(1), apr 2018. doi:
10.1145/3179415. https:t tttp///0oooo.//..oo// 1145/3179415
Di Wu, Xiujun Chen, Xun Yang. Hao Wang, Qing Tan, Xiaoxun Zhang, Jian Xu, and Kun Gai. Budget constrained bidding by model-free reinforcement learning in display advertising. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pages 1443-1451, 2018
Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Alexan- dre M. Bayen, Ali Jadbabaic, George Pappas. Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger, editors, Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 620-629. PMLR, 10-11 Jun 2020. URL httpps://proceeeee
mlr press/v120 201220///he2aa...m html
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction state all the main contributions made by the paper.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
All the assumptions are clearly stated in Section 2
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification: All the theoretical results clearly state their assumptions, while all their proofs are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuii wwwiiicgguie///eeeeeeeeic CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed, since the work is mainly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

Appendix
The appendix is structured as follows:
In Appendix
A
we provide the complete related works.
In Appendix B we provide the events dictionary.
In Appendix we provide the preliminary results on the confidence sets employed to
estimate the unknown parameters of the environment.
In Appendix D we provide the omitted proofs related to the theoretical guarantees when the corruption value is known by the learner, namely, the results attained by Algorithm
In Appendix we provide the omitted proofs of the theoretical guarantees attained by
Algorithm when& a guess on the corruption is given as input to the algorithm.
In Appendix
F
we provide the omitted proofs related to the theoretical guarantees when the
corruption value is not known by the learner, namely, the results attained by Algorithm
In Appendix
G we restate useful results from existing works.
In Appendix we provide the results related to stability a corruttion-robusness.
A Related works
In the following, we discuss some works that are tightly related to ours. In particular, we first describe works dealing with the online learning problem in MDPs, and, then, we discuss some works studying the constrained version of the classical online learning problem.
Online learning in MDPs The literature on online learning problems [Cesa- Bianchi and Lugosi 2006) in MDPs is wide (see [Auer et al. 2008 Even-Dar et al.) 2009 Neu et al.] [2010] for some initial results the topic). In such settings, two types of feedback are usually studied: in the full-information feedbbcck model, the entire loss function is observed after the learner's choice, while in the bundit feedback model, the learner only observes the loss due to the chosen action. Azar et al. [2017] study the problem of optimal exploration in episodic MDPs with unknown transitions and stochastic losses when the feedback is bandit. The authors present an algorithm whose regret upper bound is Õ(VT) thus matching the lower bound for this class of MDPs and improving the previous result by Auer et al. 2008
Online learning in non-stationary MDPs The literature on non-stationary MDPs encompasses both works on non non-stationss -tatiioio rewards and non-stationary transitions. As concerns the first research line, [Rosenberg and Mansour (2019b) study the online learning problem in episodic MDPs with adversarial losses and unknown transitions when the feedback is full information. The authors present an online algorithm exploiting entropic regularization and providing a regret upper bound of ((VT). The same setting is investigated by Rosenberg and Mansour [019a] when the feedback is bandit. In such case, the authors provide regret upper bound of the order of O(T3/4), which is improved by Tin et al. (2020) by providing an algorithm that achieves in the same setting a regret upper bound of O(VT). Related to the non-stationarity of the transitions, Wei et al. 2022 study MDPs with adversarial corruption on transition functions and rewards, reaching regret upper bound of order Ö(VT+ C) (where C is the amount of adversarial corruption) with respect to the optimal policy of the non-corrupted MDP. Finally, Jin et al. (0244] is the first to study completely adversarial MDPs with changing transition functions, providing a O + C') regret bounds, where C' is corruption measure of the adversarially changing transition functions.
Online learning with constraints A central result is provided by Mannor et al. 2009 who show that it is impossible suffer from sublinear regret and sublinear constraint violation when an adversary chooses losses and constraints. Liakopoulos et al. (2019) try to overcome such an impossibility result by defining a new notion of regret. They study a class of online learning problems with long-term budget constraints that can be chosen by an adversary. The learner's regret metric is modified by introducing the notion of K-benchmark, i.e., a comparator that meets the problem's allotted budget over any window of length K. Castiglioni et al. (2022a b) deal with the problem
20

---

of online learning with stochastic and adversarial losses, providing the first best-oo-both-worddd algorithm for online learning problems with long-term constraints.
Online learning in CMDPs Online Learning In MDPs with constraints is generally studied when the constraints are selected stochastically. Precisely, Zheng and Ratifi [020] deal with episodic CMDPs with stochastic losses and constraints, where the transition probabilities are known and the feedback is bandit. The regret upper bound of their algorithm is of the order of Ö(T3/4), while the cumulative constraint violation is guaranteed be below a threshold with given probability. Wei et al. (0188) deal with adversarial losses and stochastic constraints, assuming the transition probabiliitees are known and the feedback is full information. The authors present an algorithm that guarantees an upper bound of the order of Ö (VT) on both regret and constraint violation. Bai et al. [2020) provide the first algorithm that achieves sublinear regret when the transition probabilities are unknown, assuming that the rewards are deterministic and the constraints are stochastic with particular structure. Effoni et al. [2020) propose two approaches to deal with the exploration- exploitation dilemma in episodic CMDPs. These approaches guarantee sublinear regret and constraint violation when transition probabilities, rewards, and constraints are unknown and stochastic, while the feedback bandit. (Stadii al. (2025b] are the first to attain sublinear positive violation in stochastic CMDPs employing primal-dual method. Qiu et al. (2220) provide a 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, achicving both sublinear regret and constraint violation with full-information feedback. [Stradi et al.] [2025a] is the first work to tackle CMDPs with adversarial losses and bandit feedback. They propose an algorithm which achieves sublinear regret and sublinear positive constraints violations, assuming that the constraints constraints. Given the well-known impossibility result to learn with adversarial constraints, they propose an algorithm that attains sublinear violation (with cancellations allowed) and fraction of the optimal reward when the feedhack is full. Finally, Ding and Lavaei (2023) and WWi et al. [2023)
stochastic. (Stradi et al. [024b]] are the first to study CMDPs with adversarial
consider the case in which rewards and constraints are non-stationary, assuming that their variation is bounded, as in our work. Nevertheless, our settings differ in multiple aspects. First of all, we consider positive constraints violations, while the aforementioned works allow the cancellations in their definition. We consider static regret adversarial baseline, while Ding and Lavaci [2023] and Wei al. 2023] consider the stronger baseline of dynamic regret. Nevertheless, our bounds are not comparable, since we achieve linear regret and violations only in the worst case scenario in which C==T, while a sublinear corruption would lead to linear dynamic regret in their work. Finally, we do not make any assumption on the number of episodes, while both the regret and violations bounds presented in Wei et al. 2023 hold only for large T.
B Events dictionary
In the following, we introduce the main events which are related to estimation of the unknown stochastic parameters of the environment.
Event Ep: for all 1 E [7], P E P,. Ep holds with probability at least 1 - 45 by Lemma 18 The event is related to the estimation of the unknown transition function.
Event Eo: for all t [T), E [m], E X A:
Dn a)
1 T TE|T]
Σ
E Elur,(z, (x) S a).
Similarly,
(r,((r,)) 2 (x) S a))
where of E (0.1] = [G
Eg holds with probability at least - by Corollary 2 of the unknown constraint functions.
The event related to the estimation
21

---

Event E,: for all t E [T), (z. a) E X x A:
1
Σ T TE(T]
Bir, (z, a)l s (o,(z,
Similarly,
ar( r (2r, a) S ())
& holds with probability at least 1 by Corollary The event is related the estimation of the unknown reward function.
Event Eg for any P. E P::
ΣE g (f (x, - So (LXXI)
T||
A|
Eg holds with probability at least 1 65 by Lemma 19 The event is related to the convergence to the true unknown occupancy measure. Notice that P [Eg n 66 by construction.
C Confidence intervals
In this section we will provide the preliminary results related to the high probability confidence sets for the estimation of the cost constraints matrices and the reward vectors.
We start bounding the distance between the non-corrupted costs and rewards with respect to the mean of the adversarial distributions.
Lemma 2. For all i E fixing (I, a) E E x A, it holds:
Co T
g x a)
(g a)l S
SE(T]
Similarly, fixing (x, a) E x A, it holds:
r (x, a) T
1
Elra(r,
Cr < T
tE[T]
Proof. By triangle inequality and from the definition of Cg. it holds:
g (f a) T
Σ
Elgr, a)] =
(of (z, a) (x,
T
TT
[|[
1
<
9 (z, a) (2,
EE(T)
Ca
T
Notice that the proof holds for all E [ma] since CG defined employing the maximum over i [m]] Following the same steps, it holds:
+ Σ (x,
1
r (I,
(r'
Err((x, a)))
T
(E(TT)
TE(T
Σ
r", a) -E)r(x.
T
C₁
<
T
which concludes the proof.
22

---

In the following lemma, we bound the distance between the empirical mean of the constraints function and the true non-corrupted value.
Lemma 3. Fixing E [m]. (x,a) X A, e [or for any å (0, 1), it holds with probability at least 1 - 8:
2
CG
(t, - - (x, S 2 m
In
[ax
Proof. We start bounding the quantity of interest follows:
(x) a) (a.(x,))-)((a ()(1 = [Ereto L, (z. a)9r.((2,a) max((N((I,a)... 1}
Ie (2,
Σ
(r a) (Dra(1,, (lg a)])
max (NxxNN(zz, a),
rE(1]
EL, (looos) (2,
(7)
(xx, 13 reld
where we employed the triangle inequality and the definition of (r, a).
We bound the two terms Equation ( separately. For the first term, by Hoeffding's inequality and noticing that constraints values are bounded in [0, 1). it holds that:
P A
(- (xx
20
S 2xx
max (N,
where,
Erejp Ur (x, a)gr,))g (0n.))rr( (1) max (Nee(, a), 1}
Erreto Ir (z, a) max(NN(I, a). 13
A=
Setting& 8 2 exx
2c max (M., and solving to find proper value of get that with
probability at least 1 6:
1
1 E1, (0..(2, (o.1 - (x / $ m a).
In
max (NN rEld
Finally, we focus on the second term. Thus, employing the triangle inequality and the definition of Cc. holds:
max (oxx(Ne(I,),. I (E)g,,(2, a)] - oi (I,
TE.1
Σ
az, (lors(za)) oi (x,
max(NN( a), 1)
rE(e]
B Bl, a)] 2e (2,
max(NN(x, a) 1
TE(T]
CG
max
which concludes the proof.
We now prove similar result for the rewards function.
23

---

Lemma 4. Fixing (2,0) E X x A. E [T), for any å E (0, 1), it holds with probability at least
1- 6:
In (3)
2
C
(((z,))-((z,00))) S 2 (eaa(N((2,a))))))
max max (ex,
Proof. The proof is analogous the one of Lemma
We now generalize the previous results as follows.
Lemma Given any å (0, 1), for any (r, a) E EX x A, E [T], and [m], holds with
probability at least 8:
CG
De,(2r, a) - o6 (ar, a) V (z In
5
Proof.
First let's define Çe (x a) as:
2
Cc
(1 a) = V maxx(N a),
max(NN a).
From Lemma 3 given 8' (0, 1). we have, fixed any [m]. t [T] and (x, a) E X x A:
P
(0.(2, a) of (z, s (e(I,a) 21-88
Now, we are interested in the intersection of all the events, namely,
n (B,, a) (x) s ( M.0.i,
Thus, we have:
n (ou.lo.a) (z, s (((0,00)
a,a,i,
1-P P
U Ix,,i,,
- (((2,
>
Σ S,a,i,
s {G(2,a))
(8)
2 1 - [-|IX|A
where Inequality (8) holds by Union Bound. Noticing that (x, a) < 1, substituting 8' with 5 = 8'/|x| ||| in Ce(2,, a) with an additional Union Bound over the possible values of N2 a). have, with probability at least 6:
2mT 2m
Ca aN)
(2,(2, a) - of (x, (z,
S (a
8
which concludes the proof.
We provide similar result for the rewards function.
Lemma 6. Given any 8 E (0, 1). for any (I, a) E X x A, E [T], it holds with probability at least 1- 8:
1
2T|XIAA)
C2
fo a) - (2, s
In
+
2 2 a)
8
24

---

Proof. First let's define the (2, a) as:
C, ax),
V1(2,, a) == V m In +
From Lemma given 8' (0,1), we have fixed any E [2] and (x, E X x A
P Fz(z.a) - (x, s vr(2za) 21-8.
Now, we are interested in the intersection of all the events, namely,
P
n
Fe((x.)) - (2, s (v((,,))))
2,0,!
Thus, we have:
P
n
s ch(
U a,a,t
a s a)(1,a))
2 1
Σ F.0.t
( ( (1(2,a))
(9)
2 1 1- 1
where Inequality (9) holds by Union Bound. Noticing that r, a) S 1, substituting 8' with ò := || (2, a) with an additional Union Bound over the possible values of N2 a). we have, with probability at least - 6:
1
XT 5
C. max(Ni(z,e),1)
r -rr s
In
2 max
which concludes the proof.
In the following, we bound the distance between the empirical estimation of the constraints and the empirical mean of the mean values of the constraints distribution during the learning dynamic.
Lemma 7. Given 5 E (), for all episodes t E [T.. state-action pairs (x, a) E X x A and constraint [m],it it holds, with probability least 8:
(e, a)
Σ TE(T]
E Elg. (x, a)] $ ()
T
where,
(e(x,a) = min {1, (1 max{ (N,(x, a), In
22TTIXIIA|
CG max m (N,(,, 1]
Co T
Proof. We first notice that if (, 1, the results derived trivially by definition the cost
function. We prove now the non trivial case
max (N( In 2 + max(N.
Cc
Ca <1. Employing Lemma 2 and Lemma E [T] and for all i E [mn), it holds that:
with probability 8 for all (x, a) X A. for all
(2, a) 7 Σ
Elg,,(0, a)]
TE[T]
25

---

- - (2,
(1 a)
9
-
1
Σ
Blg (I,
T
tE(T]
|mITIX||A|
Cc
Ca
[iaxx(N(eer (Ni(1,))11
max (N, a),
where the first inequality follows from the triangle inequality. This concludes the proof.
For the sake simplicity, we analyze our algorithm with respect to the total corruption of the environment, defined the maximum between the reward and the constraints corruption. In the following, we show that this choice does not prevent the confidence set events from holding.
1...for for all episodes E [T], state-action pairs (xr, a) X x A and constraint E [m], with probability least 6, it holds:
Corollary Given a corruption guess Ö 2 Ca and 8 E (0.1).
g0,( a) a a)] S {c(o,a))
rE[T]
where,
a), 1} In 2m 2m
fx a) min { (1. 2 max (x,,a,
(ax a),
13
Proof. Following the same analysis of Lemma for δ 2 Cc. it holds
11, a)
Σ E E(g+, (x, a)]
T =E(r]
2mT|X||A1
CG
Ca
2 [axx[N(a, In
+
+
5
Max(NN(I,
a),
T
2mT
Ö
2 max (ax In
5
T
which concludes the proof.
Corollary 2. Taking the definition of employed in Lemma 7 and defining &g as the intersection event:
Ea = { (0,,(z, (x
- a)) s a) V(I,a) X A Vi, ml)) n
{ (mnu(1s.a) a)
1 Σ (2 < (((,)), V(z,a) E A [m] T TE(T]
it holds that P[Ec] 8.
Notice that by Corollary [ &g includes all the analogous events where & is built employing an arbitrary adversarial corruption Ō such that Ò 2 Cg.
In the following, we provide similar results for the reward function.
Lemma 8. Given 5 E (0, 1), for all episodes t (T] and for all state-action pairs (5, a) E X A.
with probability at least 5, holds:
oz(x,
1
Σ (fr & ())
T
rE/T
where,
@r(x, = min { 1
2T|X|1A|>
C,
Cr T
ln
+
2 max(NN( 1}
(x)
26

---

Proof. Employing Lemma 2 and Lemma 6 with probability at least 1 - 6, for all (z, E X x and for all t [T], it holds:
1 Σ T rE(M]
Fe(x, a)
(x,
x Fr () (F(, + r
1
Σ LE(T]
(i a)l
T
|T| 8
Cr max a),,,a))11 a)
+ C2
2 max a), In
T
where the first inequality follows from the triangle inequality. Noticing that, by construction,
(z,
Σ (r, a)] s 1,
T
FE/T
for all episodes E [T] and (z,0) E X A concludes the proof.
We conclude the section, showing the overestimating the reward corruption does not invalidate the confidence set estimation.
Corollary 3. Given corruption guess Č² Cr and ō E (0, 1). for all episodes t E [T] and for all state-action pairs (z, a) X A, with probability at least 6, holds:
1 T
a)
Σ TE[T]
(rr a)l s ())
where,
2T X|
(1(x,)) := min (T. 2 max (x; 1} In
+
+
5
max max(NNg (N,(2, a),
T
Proof.
The proof is analogous to the one of Corollary
Corollary 4. Taking the definition of Φt employed in Lemma g and defining E, as the intersection event:
E,
| (r s (z)
E =
n
Fe(I, T
Σ rE(T]
Eir (z, a)] s (,) V(z,a) E X A
it holds that P[E,] 2 1 8.
Notice that by Corollary 3 E, includes the analogous events where di is built employing an arbitrary adversarial corruption Ō such that θ 2 Cr-
D Omitted proofs when the corruption is known
In the following, we provide the main results attained by Algorithm 2 in term of regret and constraints violations. The following results hold when the corruption of the environment known to the learner.
We start providing preliminary result, which shows that the linear program solved by Algorithm 2 each t [T] admits feasible solution, with high probability.
Lemma 9. For any 5 E (0, 1), for all episodes t E [T], with probability at least - 56, the space defined by linear constraints E A(P.)
G. q S a admits feasible solution and it holds:
{u { aocC'ass ss c ((EA(P)) G. G. sa.
27

---

Proof. Under the event Ep. we have that A(P) _ A(Pi), for all episodes t E [T]. Similarly, under
the event Eg, it holds that q sible solution of the offline problem, is included in the optimistic safe set {a ( :
1 T tE|2]
Σ E s : a). This implies that any fea-
Taking the intersection event &p n Eg concludes the proof.
We now ready provide the violation bound attained by Algorithm 2
Theorem 2. Given any (0, 1), with probability at least 1 86, Algorithm violation VT O [|X] IA In (MTTxx Al/a) + ln(T))
attains positive
Proof. In the following, we will refer as Eq to the event described in Lemma 19 which holds with probability at least - 66 Thus, under Eg n Eq. , the linear program solved by Algorithm 2 has feasible solution (see Lemma 9 and it holds:
VT max
[BG.]] a: - =a
mm(m
tE(T]
(Blged 52) + o8 qi ai)
max
iE kE(TT]
[E(gr,al 9;) 9. ( + +6(111 T
< max
qt at;
(10a)
<[(m) hE(T]
a; 1
= max iElm [m)) kE[T]
[Bigrdl 9:) + 1, (q: - 4 + +2 -,
q: +
22, 19:
< max
[Bigr,l -9.) 9: + 1,
(q: @ +22,
(10b)
<E[m) EE(T
(B(...) - 41
2max
Σ [E[T]
g. g, (4: 7
T
(10c)
iE [m(m)
iE [ml
xE(m)
BE[T]
(E(T)
< max ve[m) 2E[T]
Σ
[| - 01 11, + 2max
ST19 + max
llee Tell
(10d)
vE(m)
LE(T)
EET
CG 2max
Σ 1L19 +
Σ 119. aell.. <E|21
(10e)
rE(m)
2ETT
where Inequality (Oaa) follows from Corollary 2 Inequality (Obb) holds since Algorithm 2 ensures,
for all E [T] and for all E [m]. that 2,, Th I ass. Inequality (Tec) holds since {a + b) S |a| + [b]
for all a, b E TR, Inequality [Tdd) follows from Hölder inequality since l|g,, (2r, a) s and
l1 a)llle lol < 1, and finally Equation (I0e) holds for the definition of CG.
To bound the last term of Equation 10c
notice that, under Eq. by Lemma 19 it holds:
Σ 11.e
Tell1 = o [|X] I
[E|T]
we proceed as follows. Under wiit probability at To bound the second term of Equation (Tee) 5, it holds:
least 1
Σ [E[2]
Σ
Σ
+ I 2T x
(1
LE(T] 2,a
Te a) (V
1
2mT]XX1a
+
maxx(NN11) (2,
5
2.a (E(T
28

---

Co max max a), 11
Co
+ L 2
(1lb)
T
2m X|IA|
In
T1(
8
max (N,,1 a),
2. [T
(1 a), ) L 2T in 2T
(x)
ΣΣ
(2
1
XIIA|LTII
+ (2
|X I I 2T
2
8
8
(11c)
2mT[X||AA]
$ 3/
II
(3 ((T) L 2T'nn
2
5
(VIIXIAALLTII In
mT |A|
8
where Inequality (Ta) follows from the Azuma-Hoeffding inequality and noticing that
Ex. (x, a)4, (x, a) S I. Equality (TIb) follows from the definition of & and finally, In-
equality I1c holds since + EtS1 (Nr(a.)) Vi Sist+ 1 2/, 1
S (2, since
1 1 Σ Ex
(x,,a.)) 1 < + In(T) and by Cauchy-Schwarz inequality. Finally, we notice that the t=1
intersection event &g Eg n EAzuma holds with the following probability.
P n Exruma]
= B3 U
EC
U E
2 1 (P [&]] + F [E]] + P [E)amm]]
2 1 - 85.
Noticing that, by Corollary [ what holds for a & built with corruption value Cc, still holds for higher corruption (by definition, C' CG) concludes the proof.
We conclude the section providing the regret bound attained by Algorithm 2
Theorem 3. Given any å (0, 1), with probability least 1 98, Algorithm 2 attains regret
R O [|X I| (TIIIA)7)) In(T))X]]AII))
Proof. First, we notice that under the event E, it holds that, for all (I, E X x A and for all / e [T]:
(x a) (2, a) S T
Σ B(re(a,a))-
1E|2
Let's observe that, by Lemma under the event &g n Ep. qe is optimal solution for Fz-1 in {&E (rEA(P.)) G. q sassa Thus, under Ea O Ep the optimal feasible solution g² is such that:
r_ T 2 -T_
Thus under the event E,, it holds:
Elr
q- < $T
T [E[]]
< <T_T
T
Σ
E(ra] + 20h-1
qe.
T
YE[T]
29

---

Thus, we can rewrite the regret (under the event &g n NEp) as,
Rr Σ
Blrd" (q" - gc)
TE(T]
Σ
Birr]" (0" -0)
Σ
(E(ra] - r) (9" - q()
T
1E[T]
rE[T]
rE[T]
Σ
Eirz] (q" q q qi) +
(E(rl] r + + -F (q"
7)
-4) 9t)
1E[T]
TE(l]
1E|2
Σ
E [r+]]
(q" (:)
+ Σ
alll +
Σ
[B[r - r +
Σ || r|1
T
1E[T]
TE127
1E/2]
te[2]
<E|2]
20, 9:
l
gell1 + 2C,..
[E[T]
E
By Lemma 18 with probability at least
65 under event Eg we can bound E
gell as:
Σ
ll
9ell1 = [1x1|11 I
(TX
[E
Finally with probability at least 8 holds:
Σ
Σ
Σ
Φ a)ll,, + L 27 In
(12a)
TE(T]
xE(T] æ.a
(V 2mxx N (x., ax, In
1
2T|
Te(ora)) a)
5
x, TT
C,
Cr
+ T
+ I 2T
(12b)
NNx (x, a).
[2T
1
In
a((
max (2,
(E[2]
[ax a), + 7) + LV 2n 8
[x(x,a) a)
5,0 2
2T|
< 3
XTI In
+ In()) + 4 2T In
(12c)
2
< 3
XIAALTI In
+ 1 LV 2n
2
T| A
=0
IXIAALTII
+ II(T))
where Inequality 12a) follows from Azuma-Hoeffding inequality, Equality (1b holds for the defini-
tion of de, and Inequality 12c holds since - ENr(a V < + 2 ( a) / Nr a).
1 + E/E (2, 1 < 2 + In()') and by Cauchy-Schweer inequality. Thus, we observe that with probability at least 1 - 95 it holds:
[TI
RT o L|X
|||TIn
+ II(T))
5
Employing Corollary 3 and the definition of C, which is at least equal to C,,, concludes the proof. G
30

---

E Omitted proofs when the knowledge of C' is not precise
In this section, focus the performances of Algorithm when guess the corruption value is given as input. These preliminary results are "the first step" to relax the assumption on the knowledge about the corruption.
First, we present some preliminary results on the confidence set.
Lemma 10. Given the corruption guess ČG. where CG EG + e, with e > O, and confidence & as defined in Algorithm using CG as corruption value, for any å E (0,1), with probability at least [T', state-action pair (z, a) X x A and constraint [m], the following
1- 8, for all episodes
result holds:
g (x, a) S (z, + (z + (2, a), (T)-
Similarly, recalling the definition of Go for all episodes t [T], state-action pairs (x, 0) EXXA and constraints [mm], it holds:
9i (x) De, (2, a) (2,
(max)((( a). ++)-
E
Proof. To prove the result, we recall that, by Corollary 2 with probability at least - ô, the following holds, for all episodes [2'], state-action pairs (x, a) X and constraints [m]]
Tr, a) (x, a)] S
1 2max(N 1}
2mTT (enT(X]IAA)
Co
Ca T
In
8
(2)
which can be rewritten as:
ax, (x, a)] s ac(
Max( a),
+ -
+
where,
2mT|X|IAA>
ŌG (x),
Co
a((x,a) = min (N, a), 1} In
8
T
and CG Ög + e, which concludes the proof.
We are now ready study the regret bound attained by the algorithm when the guess on the corruption an overestimate.
Theorem 7. For any å E (0, 1), Algorithum when instantiated with corruption value C which is an overestimate of the true value of C, i.e. C >> GG and Ö > C,, attains with probubility at leust 1 86:
ATTTI (TIXIIAI) + +II(T))X(AAC
Rr O
Proof. By Corollary [ it holds that the decision space of the linear program performed by Algorithm contains with high probability the optimal solution that respects to the constraints, Furthermore. employing Corollary 3 and following the proof of Theorem concludes the proof.
We proceed bounding the violation attained by algorithm when underestimate of the corruption given as input.
Theorem 8. For any å (0, 1), Algorithum
2 when instantiated with corruption value Ö which is an
underestimate of the true value of Cc. i.e. C Cc. attains with probability least 1 96:
mTT XI|A| + In(T))X|AA(C))
V/ = [|X]]
|
8
31

---

Proof. First, let's define e F such that e = Cg - Ö. Then, with probability at least 1 - 6:
Vr
E| gt a],
(13a)
i6 m
[E[T]
(Bigr,l 9.) a: + 9i q: 0j
T
max
ic [m]
tE(T]
- max i6 m
(Elga,1) -90) q: 1,
(at 4t) + +--1, 26%
tE|2"
+
Σ
+ 7) (((2,a) cs
(13b)
max (2-
2,0
S Cg + 2max
Σ
5--19 1t +
Σ
l1ge
ic/m tE[T]
1E/21
+
Σ *E[T]
max N (z, a), 13 qc( a) + eL,
(13c)
2.0
where Inequality 13b) follows from Lemma 10 and Inequality (3e is derived as the proof of
Theorem 2 and considering that |/ I, vt [T]. Now, employing the Azuma-Hoeffdiee
inequality, we can bound, with probability at least 1 the term Σ En,o (t. a) as follows:
tE[T] a,a (N, a), a) S L
E
27
+
ΣΣ
max ( (x(
TE[T]
x,a
L 2T +
d)lIII(1 In())),
where we applied Azume Hoeffding inequality and the fact that (N < 1 + (n Finally, following the steps of the proof of Theorem 2 to bound the first elements of Inequality (l3c) under Ej with probability at least - 5, and considering that e < CG and C < CG. it holds, with probability least 1 -95
V==
LIXIN/ A
In(T))XXIAACG)
8
which concludes the proof.
Finally, we provide the violation bound attained by Algorithm when overestimate of the corruption value given as input.
Theorem 9. For any 8 (0, 1), Algorithm when instantiated with corruption value Ò which is overestimate of the true value of Ca. i.e. C Cc. attains with probability at least 86:
V7 V7= = [XXI A| (TiXIIAI +II(T)/X]AAC)
Proof.
The proof follows by employing Corollary to the proof of Theorem
Omitted proofs when the corruption is not known
In the following section we provide the omitted proofs of the theoretical guarantees attained by Algorithm 3 The algorithm is designed work when the corruption value is not known.
32

---

F1 Lagrangian formulation of the constrained optimization problem
Since Algorithm is based on a Lagrangian formulation of the constrained problem, it is necessary to show that this approach is well characterized. Precisely, we show that strong duality-like result holds even when the Lagrangian function defined taking the positive violations.
First, we show that strong duality holds with respect to the standard I Lagrangian function, even considering a subset of the Lagrangian multiplier space.
Lemma 1. Given CMDP with a transition function P. foror every reward vector E [0. 1.11XxAA1
constraint cost matrix G E 10. 1]|x X A|xx> and threshold vector E [0, L|m", if Program 3 satisfies
Slater's 's condition (Condition 7
min max r Q A G a- aa]; [ (EA(P)
min rTg (EA(P) (MI
E Au G a), se[m]
max
<E(m]
OPT,,
where 12 is vector of Lagrangian multipliers and p is the feusibility parameter
parameeer of Program 3
Proof. The proof follows the one of Theorem 3.3 in Castiglioni et al. 2022b]. First we prove that,
given the Lagrangian function Q(), 9) = 9 DiEmm] X (G; q -0a). it holds:
min (O.L// (P)
max 2(2, 9) min max Q(A, 4), AER PEA(P)
with À R2 fact notice that for all X E RS such that ||a|| > Lip:
max 2(),g) 2 REA(P)
Σ A (G. 9- - -a.) 2 |Allia L.
{Elm]
where dº is defined qº :- arg (PP) m [a: G. g]. Moreover since
min max 2(v.g) < /
max gEA(P)
Q(0,g) max r
T 2'9 S.
gED(P)
holds:
g(),g)= min min max 2(),9), min max 2(4.0)) [IAILE(O,.L/o) (EP(P)
min XERR TEA(P)
max
min
max @().
[A]] (EP(P)
Thus,
OPT,G. = max min ((),g) (EA(P) AERT
min 2().g)
gEa(P) || 24/p
min max @(),g) /
min max (().g)
20 9EA(P)
OPT,,
where the second inequality holds by the max-min inequality and the last step holds by the well-known strong duality result in CMDPs [Altman] 1999]. This concludes the proof.
In the following, we extend the previous result for the Lagrangian function which encompasses the positive violations.
Theorem 4. Given a CMDP with a transition function for every reward vector r E [0, 1|AA,
constraint cost matrix G (0, 1 x A|xmm and threshold vector [0, L!m", Program 3 satisfies Slater's ' condition (Condition D. then the following holds:
L
mAX (EA(P)
L(4/p.9)
max T GEA(P)
G
g - a OPT ........
iE|m]
where p is the feasibility parameter of Program
3
33

---

Proof. Following the definition of Lagrangian function, we have:
((L/p.9) = max r (EA(P) iE
[G] q as]
PEA(P)
A1[. q - -
max (EA(P) [1
min
r q
sE(m)
min | (EA(P)
max
rTg q
Σ
ArG. q ailt
sE(m]
max r |/ GEa(P)
min
Σ
A (G] q at)
sc [m)
OPT G,
where A E I8 is the Lagrangian vector, the second inequality holds by the max-min inequality and
the last step follows from Lemma Noticing that for all q belonging to {q E A(P) G' 9 a). we have L(1/p.)) -rgg. which implies that maXgEA(P) L(1/p.g) 2 OPT,,G, concludes the proof.
F2 Preliminary results
In the following sections we will refer as:
P = Σ
Wir 5) Wr + y
h Di.s
03
(14)
JE
xE(m
to the estimated violation attained by the instances of Algorithm
Furthermore, we will refer as:
I( jr) W1
Vr--
Σ EE[T]
Σ
9
q
ai
(15)
+7 iE(m)
to the estimated violation attained by the optimal instance j", namely, the integer in [M] such that the true corruption C' E 122"
Furthermore, we will refer as of to the occupancy measure induced by the policy proposed by Alg' episode f, with j E [M], E [T], and we will refer as:
(x 0) Σren (a a)T(ir = (00
max M (N/ (x. a), 1}
to the estimate of the cost computed for j-th algorithm, where N2 (Ir, a) is counter initialize to 0 in t 0, and which increases by one from episode episode + 1 whenever L, a)ll(i j) 1.
F.2.1 Stability parameters
In the following sections, we will employ the stability parameters defined as follows:
31 o (1' [
TIXIIAI
B2 O (1X]21412 log]) log (log(T)/8)
3a O (In(T)(|X]1411
B4 O (I2)XT1AA) In (T (
As O (1X12 log(T)) log (18)(7)/8))
3o O (In(T)()X1441)
34

---

F.2.2 Omitted proofs and lemmas
We start providing some preliminary results on the optimistic estimator employed by Algorithm 3 Lemma 11. For any 6 E (0, 1), given r E R20 with probability at least holds:
R so o (TTLM FTLM++I'' 1/22 (6))
where RT = -iErn ESElM| (wed (L- (L- Blre] of)
",,,(i=0 Wisty
((st.af) (1- To (2tt d())
Proof.
We first observe that by construction:
E
Wr. = j)
Σ
(1 (1- (zk)
(1kr
Σ
wh. W 7
(L- Blri]' of)
Wej +7
(E(T]
(1)2
KE|TY JE[M]
Moreover, still by construction, for all episodes E [T], it holds:
Wr j)
Σ (1-r (2), aft) - Σ -G=
Σ (1- (th. s L.
Wh.t +7
JE[M]
(=)
JEM
(122441)
Thus, employing Azuma- Aoeffingg inequality, with probability at least 8, it holds:
ΣΣ JE(M
wi (I. [F(r)Tdd)-
(t) W4 W = j) Whi +
Σ
1 (1-r (r ab)) s s 2T (7)
Wt,j +
(0f a
Finally we notice that:
w
ΣE Wes (L- El-aarrTooh ot)
Σ Σ
Wt.j + (L (L- Brrel]e TT])
(EMM)
LE(T]JE(AN)
ΣΣ AE SE(T)JE[M S.L
Wr.
? (L- Bire]] gf
Wes +
Adding and subtracting IE (mE ΣjE(M)
We E(at .t (1 -1-18 ro (1k af]]] to the quantity of
interest and employing the previous bound concludes the proof.
We provide an additional result on the optimistic estimator employed by Algorithm 3
Lemma 12. For any 8 E (0, 1), given y E R220 with probability at least holds:
10i -²)= Σ (1 at))
Σ
(L (L-Elral of o
- in
1
5
Whi (z)
7
AE(T]
EE(T]
Proof. The proof closely follows the idea of Corollary
We define the loss E, Enet (z)
re( af)), the optimistic loss estimator E, = "..."
10,=)")
Eeagaag re(aft at)) and the unbiased
estimator & = I(}==") Eesg re af))
'',,"*
Employing the same argument as Neu 2015 holds:
7, T(jr = 5³) < T(j+ = j*)
L 2-/1/ We 1(j = =]²)
I - 27
In I+ 2%% (1))
Wt,j" +7 Wt.j" + t &,
27 1 + /
since
2-22 < In(1
2), R. Employing the previous inequality, holds:
2n Eg
22 L
1 277, 2x1))) Fr11 F
E
exp
Fi-1
SE
exp
L
L 27
35

---

27 l Ft-1
E
L
27E E
1(i+ j
Σ (1
re
at)) af)) Fe-1
W1,3
(xtiaf)
< 1 +
27
[ - Biri] d.
L
2
[L - B[re] Brr
of )
$ exp
where Fi-1 the filtration up to episode t. We conclude the proof employing the Markov inequality as follows:
P
Σ 1E|T)
y
Pt
Blre] (fr
2()
L
27 (Er (L- Elre] sh") 1)) exp(-e)
<
E
exp
Σ AE(T]
T.
S exp( ()
Solving 5 = exp(-<e for obtain:
IP
Σ [E[T]
Ee (1. E(ro] df'))) "TrTTTT
L In S 5.
24
This concludes the proof.
We are now ready to prove the regret bound attained by FTRL with respect to the Lagrangian underlying problem.
Lemma 13. For any 5 (0,1) and properly setting the learning rate n) such that n s
2Am (B2T++B224 +.s++++t+---BTT Algorithm 3 attains, with probability at least - 28:
Σ Elri] of
Σ
Wh. Blri) of + Lm +1 Vi
Lm + 1
ViJ
P
(E[T]
[E[T]JE[M)
m(ml. + 1)
$5 + B2 Vr + (Vō++ (m(li=+1) /Ba
VT
P
M T
< 0
+ m + M (T))m 12 + M (
17
L In (1/)) TT3 + T.3m4 M log(T) + TTM + T. T'n (1/6)
7
Proof. First, we define le.j. for all /. E [T], for all j E [M] as:
4, = I(j==)) = 5)
(1 - (1-re(x a()) + Lm +
getd qe' as aa]")
Σ
Wtst +Y
(x)
sE(m)
and beg for E (T), for all j [M] as:
br.j = ( m + 1)
As + 82) + (vB++ m(Lm+1) 1) VBa vT) (vr.) 11-1s);
P
p
with Vt.j = max+elt) Wi..
First prove that my /le, buoll 5 1/2 for all e [T]. [M]. to apply Lemma 16 It
36

---

holds that myte, Ga.i S ribpt +Tmm) S 2 for all j [M] for all i [T] long as S
3( -mm] S +LmJ which true if S 2Lm(Lm+1]] It also holds that
[ + 1)
3o + +1)) + ((Lmm 1)
mwr, |bع,] = n
B1
31
VT
(vt.3 1/-1.5)
P
m +1)
m ma(Imm+1 +1)
V VB+- VBi vT) (1
1,
S 1
$5 + 92
P
Vt.j
m[Lmm 1)
mmLm++ + 1)
1 1
Br + 92
VB4 + B VT
P
1
2'
where we used the fact that Ptjj # V--15 3 1/wcs = Vt.- Thus, if the previous conditions on hold, and notice that the second condition implies the first, Algorithm Jataanns,, by Lemma I6
if 7 S
Wii =)
Σ (1 (((k
I(js = Ways +7 (x)
Σ
Lm + Vr (1 (xk)
Whs +7
1E[T]
LJEMM
(z)
Mln
(MP
I?2m² Lmm²
+ 21
"1
12
( 2
m(mL + 1)
m + 1]
2m
35 82)
M In (T) + 2T
(BB++
VBa
M In(T)
P
P
Lm + V
Σ Σ
Wiybes Σ
(16)
NE(T)EE|M
SE(T]
where we used the following inequalities:
First inequality:
Σ (hes
2 Σ Σ
w Gi +2 2 E big
JE[M)
JE(M]
tE(T)JEiM
Second inequality:
Lm
TT qe' - as )1) x
(Lp LLm²² + Lm)
Σ (1 (1-r( at))
De.t
-ai]
P
p
(x)
*E(m)
Third inequality:
TM + 12 + +mm)²
ΣΣ wiflis S
p²
JE[M]
and that, it holds:
Σ Σ b2,
jE
Σ Σ (w))
JE(M)
m [
+ 1)
Bs + B22 31)= +
(m(Lm+1)
Ba v
B1
VT
Σ
(Vi. - v1-25))
Vis
xE(T]
(17a)
37

---

2
m(mL +
35 + +B2))
2
+2
mmLmm + 1)
VB VBi))
E
2
P
P
Ve.
JE CE[T]
2
m(mm. + +1) 35 82
2
+2
mm(Tm + 1)
VBA+ vB.)
E
E
1t-
P
P
Vt.j
JEIMI AE|T
2
m(ml. + +1)
$5 + 82)
2
+T
mm[mm+)
BB VBA)
Σ
Σ
In
Vr.5
P
P
V1-1.
JEIM] LE[T]
(17b)
2
m(mL- + 11
35 + $2)
2
+2
m(Lm+ 1)
BB + V31
2
Σ
In
Vu.i
P
P
Vz-
jE(M]
(E(T]
2
(m(ml. 1)
$5 + 82
2
2T
[m[[m + 1)
V + VBL
2
Σ
In
VTJ
P
P
Vo.5
JEIM
m(mL +
2
mmLm + 1)
2
2
36 + +32
27
B4 VBI
M In (T),
(17c)
P
P
where Incquality (7a) is true since V/jj Vt-1j * 0 only when wij = 1/m. by definition, Inequality (17b) holds since S - In a, and Inequality (17c) holds since by definition vry S and Vo.j = M. Notice also that, following a similar reasoning, holds:
Σ wi.be.. Σ br.5" NE[T]
KE[T]
=
-((m
B6 + 122) ((
+ +)
+
(m(Lm= + +1)
VB v VT
Σ
Σ
1
1/-1.
P
Vts
(E(T), JE(M]
m(Lm + +1
(m(Lm +1) ++))+m((mm++)))
35 + 12)2)
VBI+ + VBi VT
Σ
(vi.)
11-1.))
LE[T]
0 m² LBg log(T) + B2M log(T) + (V Lm² v B log(T))
m(Lm + 1)
33 + //2 + m(Lm 1) v B4 + /BI VT VT.*"
Thus, with probability at least 26, it holds:
Σ Eird" de
Σ Σ
Wr, Wr, Eire] dt + Lm + V/
EE[T]
(E(T)E[M
Σ
Σ
wis (L Err ot)
Σ (L- Elre] ofe + Lm + Vi
(18)
JE[M]
BE[T]
M I
0
+ n LATM + M L2 M ln
11
+ Lm +
+ TT1 + T.2m² T.2 log(T) ( +TTLM T. T'n (1/8) + In (1/6
Vrr
(m(mL + 1)
VT (vB) + (m(mm+ [1 v B4
P Bs + 32
VTVT...
(19)
where Equation (88) holds since EYE[M Wij 1, Vt [T], and Inequality 19) holds, with probability at least proof.
25, by Lemma II Lemma and Equation (16). This concludes the
38

---

In order to provide the desired bound Ry and Vr for Algorithm 3 it is necessary to study the relation between the aforementioned performance measures and the terms appearing from the FTRL analysis in Lemma 13
Thus, bound the distance between the incurred violation and the estimated one. Lemma 14. For any y E R20. given ò E (0, 1). with probability at least 106, it holds:
/LLIXII 10
VT - V
=0 -O
+ (A
8
Proof. We start defining the quantity Eo.s (z. a) - for all episode t E [T], for all state-action pairs (z. E X x A, for all instance E [M] as in Theorem 2 but using the true value of adversarial corruption C, considering that the counter N/ (zz a) increases and only if 1(j+ = j)L{(z,0) a) = 1, and by applying a Union Bound over all instances j E [M] namely,
unit from episode to t + 1,
1
22MMTXXIAAI 5
C
C
(z) := min (
2 max ( (1r, a) In
(1,
T
(20)
By Corollary 2 and applying Union Bound on instances j E [M] simultancously Vt E [T], Vi,
a) E X x A, E [M]. with probability at least 8, it holds:
(r, a) + E. (2, a) 2 ( a).
(21)
Resorting to the definition of Vr, we obtain that, with probability at least 1 - 8, under Egi
We.yI((i = j)
P = Σ
Fe.i % a:
We, +7
(E[T] JE[M]
kE(m)
Σ
Σ
I = 1)
Σ
(Gr.e T + E..Jd - -as) -a:)- -E.jot
F,, T (gf |7)]
Whj +
JE(M]
3E|m)
Σ
Σ
We.j We, = 1)
Σ
([G), + Ero)) TT dt - aa) --1a"== - E..J Fe. Ll {
(22a)
W +
TE(T] JE[M]
2E|m)
Wr = 5)
[OR of csl [=]+ -ET
Σ
Σ
-1lod cZ
(22b)
Whj +
ME(M)
mE|m)
Σ
Σ
I(i =
Σ
[[gg.s] gd -a]
aa]]
-a--- - -((jad
Σ
I(J = j)
We +
Wts + +
JE(M)
mE|m)
LE(T)SE[M
Σ kE(m)
(o ((g.,))))
of + - (mLIXX) |A|T In
[T
(22c)
where Inequality 22a holds since [a 61 [a] b, a Rzo, Inequality 22b follows
from Inequality (1) and since, by definition, Dr, a) S 1, a) X x A, Vi E [m]. Vt e
[T], Vi [M] and, finally, Inequality (22c) holds under event &g by Lemma 19 after noticing that
Eie(T) Eje(M] [(i=)
+7 Eie(m]lles C. ll S Exemy EjE(M] I(je- (w.
Eie(m) 11
/ 1 S m El ".'111.
We will bound the previous terms separately.
Lower-bound to EiEryy EjE(M] urs (ii6) Exe(m) Elgr,IT of -as] =x]" We
We bound the term by the Azuma-Hoeffdiin inequality. Indeed, with probability at least 6, it holds:
wi,g = 3)
Σ
Σ
Σ
Elg..) of as.
Wej + xE(m)
ME JE
39

---

wh.
as a=")
ΣE
Blgad
To -ai]
y 27 In
27
Wes
+
JE[M)
vE(m)
where we used the following upper-bound to the martingale sequence:
Σ
Wr, (ie j)
Σ
Elg.a]
df as
Σ
T(je =
Wi,j
Σ
Big "o
Wej +
Wh.j +?
sE[ad]
EE mm
jElM
Ke (mr)
Σ
T(je j)
Σ
l1
JE[M]
rc(m)
$ m ml14 lla
ml.
Moreover, we observe the following bounds:
Σ sE/m]
dl ai
Σ
B[ga de asj
Wesi JE[M]]
We. +
LE|T
I TT
and,
ΣΣ W (E[T]
Σ
of aij
max <E(m
Wey
Elgrnd ot -ai
iE|m)
jE[M]
(E(T]
Combining the previous results, we obtain, with probability at least 8:
We = =)
Σ (E(T] JE[M]
Σ [m)
el Tod - ai
Wt, +7
EE
(TTIm= + Lmy 27 (
Σ
Σ
E [[ge,]] of ai)
max mmmm]
Wts (E[T]
JEIMI
Upper-bound to Everr EjE[M
1e,, [(,=) 01.
Exelm)
T.
We bound the term noticing that, with probability at least 6, it holds:
Wi = j)
Σ
Wh +
JE(M
vE|m)
We.j I(j+ = () E.J
< Σ
m max 1m
Whi +
jE(M]
tE|T)
MIO T(Ji i) ( 1 1
Σ JE[M]
E tE(T)
:E(m)
(MMTIXIIAI
XXIAILTII
+ + I. Tin Tmm
5
where we employed the Azuma-Hoeffding inequality and where the last step holds following the proof Theorem
Upper-bound to EiE(ry Eje[M
Exe(m) (of E(ge,s)) of
We simply bound the quantity of interest as follows:
Σ
Ir = 5)
Σ
(0
E(ge.)) df
Wo + FE(m)
SE(T)S[[M
40

---

ΣΣ (E[T)E[[M]
I(ji أ)1 - -Egr,
S CCC.
Final result. To conclude we employ the Azuma-Hoefiding inequality on the violation definition, obtaining, with probability at least d:
VT Σ
Σ (E|T]
1' 5) Elgrrsl " -as]
max
iElm) JE(M]
Elge.] vp os]" + L 2//2111 (
Σ JE(M]
Σ
max
Wr.j
RE
m
(E|T)
Thus, plugging the previous bounds in Equation 22c obtain, with probability at least 105:
VT T
Wr,ilGi =
Σ max
Σ
I(j+ = 5) [Bgg,(] ot aij
Σ
Σ xE(m
D6,s T T ai
Wei +
jE[M]
tE[T]
RE KETTJEE|M
I(e = -)
Wi,y Ii =)
Et. T +
Σ
E
[ - E Elgc,e)) To
Whs +
Whst +7
T
4E[T) JEMM]
DELT)JELME
VE
TE(T]
1 8
(TIXIAA))
+ TTm + 21
2T
+
m
|||
8
mMT[X||IA
=0
mL)XX | In
+
+ HTLM
5
This concludes the proof.
We proceed bounding the estimated violation attained by the optimal instance j Lemma 15. For any 8 E (0,1), 1), with probability at least 1 165, it holds:
Vrg so so |A/TIm
m
In (
+ mBBC. + m mm(TT)xXIAAAC + Lm
8
27
+ mm BTTYTJ- + mBBUT3"
Proof. We start by observing that with, probability least under Eg. the quantity of interest is bounded as follows:
T(je j*)
Σ
Thes
ai
Wi,s +7
1E[21
=E|m]
Il = j*)
Σ
[ (Tl olh This Tof - EfJ-of - ai) + ETJ-oo
(23a)
We,j" + 5E(m]
1E|T
I[jee = j*)
Σ
[[ouil of - -as]
+ E. +
Wi.s" + 7
sE[m]
Ti of. - [[grd of""
+ +11 - od 11 l11)
(23b)
Iljee = jr)
Σ
Bloadd T of - -as" + E.J. + 11008 Blgr,)) of (t]]t)
Wr,3 +y
[E[T]
x5(m)
41

---

4 |A|T In [XX
+0
(23c)
where Inequality (33a holds since [a bj+ [a] + [b] Va, E and by the definition of
Se. (see Equation 20 which implies that all its elements are positive, Inequality (23b) holds with
probability at least ò by Corollary and by union bound over M, and since that 9r, Ir S 1 and
Inequality (23c) holds with probability at least 66 by Lemma
19
(6:=)") Upper-bound to ElE(T) wo,' Eie[m)
[of Elg..)) &
It is immediate bound the quantity of interest employing the definition of corruption C' and by Lemma 17 Indeed, with probability at least
11 j") Wh,j" +
Σ [m
[OF - Elgaa)) -Bga)) di ] s Lm L
27 ( + mC.
AC(TT
Upper-bound to Eve(r)
16==1") Wh,"" +7
Blg.d of aj [m
We bound the quantity of interest as follows. With probability at least 116, holds:
Σ
1(j+ = j³)
Σ
Elgr. of - as)
Whe +Y
TE(T]
iE(m)
In M
BITVT + mBsUT + 2mBB0 + Lm
(24a)
2
thank to Corollary 5 and Corollary 6
Upper-bound to E1e(T) wey++ +7 Eie(m) C2. T...
1(r=)")
First, notice that, with probability at least 8, it holds:
11 = j*)
T s 1n/20 21/2 (
o. of
Σ
We,j +
[m]]
1E|T]
where we employed Lemma
17
Now we observe that, with probability at least - 5, it holds:
Σ -- I(I = j²)
Σ
â- (z) (a. j²)
2.a
a- (z, a)l(jie jr) + Lu 2T In
1=1
(v |XIIA|LTIn
(MMTIXIIAI)
+
L Thn
5
where employed the same steps as in the proof of Theorem and only if (2, a)l(jj: = j*) 1.
2 considering that the counter increases
Combining the previous bounds concludes the proof.
F.3
Main results
In the following, provide the main results attained by Algorithm F terms of regret and violations. We start providing the regret bound and the related proof.
Theorem If Program (3) instantiated with т, G and a satisfies Slater's condition (Condi-
tion D. then, given any 8 1), with probability at least 1 306, Algorithm 3 attains re-
gret Ry O(m² L / M/ATTlog (1/T)x1AA/8) lT)( + m² 2 || log(T)) log (log(T)/6)
m [IA)
42

---

Proof. Employing algorithm
3
with probability at least 1 146, it holds:
RT = Σ q
Σ
(E(T]
:E[T]
Σ (E[T]
F (q' gf ) +
F
(gl
qc)
LE[T]
= =VB.Tur,- + Bevr,5- + +3,0 +
Σ
xT (of 96)
(25a)
Lm + 1 Py Lm + 1 Vrs
/B BiTUTg B 233C 2C
P m(ml + 1) $s
- -VVBi mmm + 1)
VBA) (32+
vrs
P
0 M hT + + M MIn(T)m LB 1 +18g
Lm In (2/6)
TT/ + 3
TLM + L. Thn
(2/6) Tl
(25b)
where Inequality (2a hold with probability at least - 115 by Corollary Inequality (256) holds with probability least 36 thanks Lemma and the following reasoning, which holds with
probability at least 1 6:
(4t
4)) Σ (7 17-EBp Elri)) (ot - a)) + Σ Birel] Tat" - 4t)
EE(T]
[E[2]
LE[2)
$
Σ |||
E(rellla + Σ B(ra]] T (at" 91
(26a)
(E|T]
NE[T]
- 2C
Σ 1
(q'" - 4t:
(26b)
1E/T]
S 20 + Σ
q."
Σ
Σ
wr Blrd oe + LV
2T 12//2T1nn11 In(1/)
(26c)
KE|TI
SETTIJEIM
where Inequality (26a) holds since lgc a) - of (z, a) S 1, V(z,a) e e x A, where Inequal-
ity (66) holds by definition of C, and where Inequality (6cc use Azuma-Hoe Hoefa-Hoeffding inequality.
We can apply Lemma 15 to bound VT with high probability. In fact we observe that with probability at least 1 165, it holds:
Lm +
VrJ"
P
m²I mmLL2xxly/ IA/TIn
NAMTIXIAAL
+m² +
+L'm In (4f
L²m²
8
27
(Im + 1)m BoUT m(Lm+ +1 VBTTVT...
P
Finally, combining the previous results and by Union Bound, with probability at least 1 305, holds:
Lan + 1
Rr
Vr P
I
< 0
m " L + M In(T)m L + + + (T + L2m 33m33)M log(T))
11
Lm In (1/8)
+ 7TLM + L (1/8)
MMT[X|IA)
+ m² L
IA
+ mLB B3C m 111
(27)
8
43

---

which concludes the proof after observing that Vr 2 0, by definition, and setting ?
V
/In(M/8)
TM
?) S 2Am +
We conclude the section providing the violations bound and the related proof.
Theorem 5. If Program
S instantiated with v. G and a satisfies Slater's 's condition (Condition
then, given any 6 E (0, 1), with probability least 1 346, Algorithm attains positive constraint vi-
olation VT (m2 T X V/ (ml]IIIAAA/) log ( | || log(T)) log (log(1)/8)
m Log (T)log((T))))))) (T]AA))
Proof. Starting from Inequality 27 in order to obtain the final violations bound, it is necessary to find an upper bound for Rr- We proceed as follows,
q" = OPT 7.G.a
(28a)
max GEA(P)
q
G q ozi
(28b)
sE(m]
L
2 r q
Qt
ai
kE(m)
where Equality 28a holds since g" is the feasible occupancy that maximizes the reward vector
and Equality 28h holds by Theorem 4 This implies r rTy at Moreover, holds:
-T=" x² S 4/2 Eig(m)
G 4: Oti
Σ Σ <E(T] 1m(m)
T a: as G
Blgr.d de aai]*
Σ
[GG Elgg.:)) "1]
(29a)
tE[T]
{e(m)
ml
[[gr.] T 4: -aa]"
G E(onill
(29b)
tE[T]
ke(m)
EE ml
Σ [E[T]
Elgnsl 4: -as
Σ (||:- 9ill 211 + +19 - Elg.alli))
[E[m)
1E [E[m]
S m/V 2mC,
(29c)
where Inequality (29a) holds since (a 6]+ [a] [6] R. R. Inequality (29b) holds
since qe(z, a) < Ivt E [T), a) E X A. and finally Incquality (9c holds by definition of
C' and Vi2 and noticing that max;e[m] a; 2 Exe(m] ai Vaa previous bounds we lower bound the quantity of interest as follows:
mmm Thus, combining the
RT + Lm VT
B[re]" T (q" q.) Lin +
VTT
P
P
tE|T
Im +
Σ
[E[rz] -
T) T (q" - ạt) + Σ FT (q- FT
- -4)+ +
Vr
<E[T]
(E(T]
Lm +
Σ (E[T]]
|[Err]] F|1 Σ
(q" q:)
Vir
(30a)
P
L (mVr + 2mC) + Lm + 1
2 2C
V/r
(30b)
P
2LmC
Lm +1 Lm
20
+ VT
44

---

1 Vr (2C+ 2LmC' p
(30c)
where Inequality (30a holds since n v-w 2 -11|||| Ve, E R N. and where In-
equality (30b) holds since r (4" qr) 2 - DiE G. q: ai 2 (m 2mC) and by
definition of C. Thus, rearranging Inequality (30c). we finally bound the cumulative violation as follows:
Vi I 2pC + 2LmC + pRy + (Lm + 1)
= =pc + 2LmC + (Lm+ 1) (Vr- Vr) + Ry +
Lin + 1
Vi
MI
s 0 m² m |A[T'n
m In(T))|X|AAIC + ymITL2
8
Lm +
+ O RT
Vi
P
where the last inequality holds by Lemma 14 with probability at least 48 under Eg. Employing
Equation (27) and a Union Bound, setting 7 = concludes the proof.
In(M/8) TM
and S 21m(V91++3t /4T
G Auxiliary lemmas from existing works
In the following section, provide useful lemma from existing works.
G.1 Auxiliary lemmas for the FTRL master algorithm
In the following, we provide the optimization bound attained by the FTRL instance employed by Algorithm
Lemma 16 (Jin et al. 2024 ). The FTRL algorithm over convex subset of the (M (M-1)-al -MM--11dmiensional simplex AM
Σ TE/1
Ef w Σ In
W++1 arg min wEll
W/y
]E[M]]
ensures for all Ωt
Σ [E[2]
(wi (wi -u) u)
MlnT
Σ Σ
wt,fee.
n
(E(M)
as long as mwrrless & 1/2 for all j.
G.2 Auxiliary lemmas for the optimistic loss estimator
In the following. we provide some results related the optimistic biased estimator of the loss function. Notice that, given any loss vector & E [0, 1 the following results are provided for
#7. Le.i. where j E [M]. f is the j-th component of the loss vector, L,(i) is the indicator functions which is when arm j is played and 7 defined as the following lemmas.
Eeg 3e(3)
Lemma 17 Neu 2015)). ). Let (7t) be fixed non-increasing sequence with 7t. 2 0 and let O4. be nonnegative F. measurable random variables satisfying at.j S 2ny, for all and j. Then, with probability at least 1 8-8. 8.
ΣΣ Ord (Pe.s {es) $ In JE(M
45

---

Corollary Neuu 2013)), ). Let = 2 0 for all t. With probability at least - 6,
In
Σ
(es - bes) -
27
te|2]
simultaneously holds for all j [M].
G.3 Auxiliary lemmas for the transitions estimation
Next, we introduce confidence sets for the transition function of CMDP, by exploiting suitable concentration bounds for estimated transition probabilities. By letting Mc(2, a, x') be the total number of episodes up to E [T] which (x, a) X visited and the environment transitions to state x' E X, the estimated transition probability at / for (2r, a, 0,,x) is:
(xx a,
Pe (x max {1, N.(2, a)}
Then, the confidence set for P at episode & E (7) is defined as:
P. = p: P. Pr (1|1,,,
P(x'lzx, a) S (1(la,,)))
V(r, E Xx x Ax XK+I, [o..L 11
where ex la, a) is defined as:
P. (r (T max N1 1} 3 max (1, (2,,
14hn (1/
((111z,)) 22
for some confidence 8 (0,1).
Given the estimated transition function space Pe, the following result can be proved.
Lemma 18 (Jin et al. 2020). With probability at least 1 - 48, we have P E Pi all / (T].
Notice that we refer to the event P E P. for all E [T] as Ep.
We underline that the estimated occupancy measure space by Algorithm
2 is the following:
Vk:
Σ g (2,,a,z))=1 =1
Aks Vo,
Σ (1,
E
(
aEA. (x,
r'Xe-i.
A(P.) = Vk, V (2,
[Pr (P + (I' x, x,
E q(I,
yEXe+:
(
[P (x' [x,a]]
E g(x,a,,)
MEXx11
( a
To conclude, restate the result which bounds the cumulative distance between the estimated occupancy measure and the real one.
Lemma 19 (Jin et al. (2020). ) With probability least 1 66, for any collection of transition functions (Pi Jaex such that P E PPr we have, for all x,
(2, - (1 a) s0 20(1111)
T 5
ΣΣ +E[T]=EX,0E>
H
Auxiliary lemmas for stability
In this section we state the results related to the stability of the arm-algorithms when is not known. The procedure is inspired by Jin et al. [2024] and Agarwal et al. [001), but adapted to the
46

---

case of Constrained MDP in high probability. We first give some important definitions. In these definitions we will use C, as the value of adversarial corruption at episode defined as C₁ == max C;),, which meets the requirement of upper bounding the adversarial corruption each considered episode. In addition it holds that EiEry C. S C. + Cg or equivalently
[T], where C₁ is
C.EE C2 S 2C', which does not influence the order of the analysis.
Definition 2. A CMDP algorithm is corruption-robus if it takes & (a guess on the corruption amount) as imput, and achieves for any random stopping time 1' S T, whenever Exeter C. < 0:
Σ tE(P
(a
(t) S
Bil + (B2 + 330) T((! 2 1); 15V
and
1 - az]* S Ball + (3s + 360) T((L 2 1).
max RE (72)
[E
Notice that Algorithm 2 is corruption-robus. after applying a doubling trick to make it work for any stopping time, with probability at least 1 - 96 thank to Theorem a Theorem9Fuuthermoo introduce the notion of o-stability. An algorithm is considered to be a-stable, if its regret under condition imposed by Algorithm is of order 2p Ô (Ry), where Ry is the upper bound on the regret attained by the algorithm if receives feedback each episode. In particular, we interested in the 1-stability.
Definition 3. An algorithm is 1-stable if. under the condition imposed by Algorithm 3 it holds:
Σ
TT (q- - 4t)) S 3.TT, + 92455T + BaC,
EE []
and
L ax] S V.TTU + 9 + BoC.
nax RE [m)]
EE(T]
We can use the procedure defined by Algorithm 4 and originally proposed by Jin et al. 2024 to transform a generic corruption robust algorithm to 1-stable algorithm. Differently from Jin let al. (0024). in our setting, we use the natural symmetry between regret and positive cumulative constraints violation stabilize both the regret and the positive cumulative constraints violation. We have a different bound for C2 (value of adversarial corruption at episode f): indeed, C2 < max{ r max,e[m]] [ - o [1] is bounded by [X]] Finally, we are interested in obtaining results that hold in high probability rather than in expectation. To do so, we focus on 1-stability guarantee rather than 1/a-stability as in Jin al. (2024) since removing the expectation prevents us from achieving the result above with lower coefficients. We can state the following result.
Lemma 20. Given an algorithm which is corruption robust according to Desinition 2 with pa- rameters (2,,3,,88 33, 34, As, Be) and 31 2 O(. log(T/8)), B4 2 O ((12log(T//) with probability at least 1 - p with E (0, 1), then, it is possible convert it to an 1-stable algorithm with prob- ability at least 1 - p 28 according to Definition 3 with parameters (8,, 80, 3g 34 8/. B6) as
8 O (31), 3, = O (82 + 83 || (log())(()//
3 O (3g log(T") 3 O (B1). P
O (33 + 3o X A log (16)) By = O (Bs log (T)). employing Algorithm
Proof. Suppose Algorithm 4 is initialized with the true value of adversarial corruption C. We will first prove the result for the regret. We will start by considering a generic in- stance algorithm & E [M]. Define the quantity de I[w, (2-k-1, *1) and h I[Istance receives feedback at episode t). We observe that with probability at least pp +
(UKE)ORS(T) (Ene(Ty Cede,hee > 0k)) it holds:
Σ TT (q' gedd, S 31 AE[T]
dr,che,k + (82 BB0) max dr,t, #E|T]
Σ
1E/T)
by the corruption-robust property of instance k. We study now the quantity (UREIM) (Eierry Med > 0zl).
Notice that Elbyx = 2 and since
47

---

dr.a is an indicator function then E[ de ded,k E |d. In addition, since EiE(T] C₁ S 2C, it holds:
Σ
CeElbee de dee 2-1
Σ
Cidr, S <2
:E[T]
SE[7]
and with probability at least 1 - (T) noticing that M = log2 (T):
Σ
hed
Σ
C,Elhe, Rdl
AE[T]
1E|T]
E.dd,.Elbe log (oog(
loga (T)
2
Σ
+ (X| log
(31a)
8
1E/2]
loga logg(T)
(ogg(T)
S 2 XIIII Σ
Cede, (de, log
| log
(31b)
8
8
tE(T]
logo (T)
$ Σ
C. ld,, + 2 || log
(31c)
8
xE(T]
where Inequality (31a) holds with probability at least 1 - (/lo((T) by Freedman inequality, Inequality
(31b) holds since C. A], and Inequality (31c holds by AM-GM inequality. Therefore, it holds simultaneously for all le E [M]:
loga (T)
Σ EE(T)
C,di,hhi
2
Σ C. + 2| log tE(T)
(T)) Os.
$ C 2 log
with probability at least 6, so P ( Cidexhee > 0v)) S 6. Moreover, notice that with probability least 1 25 thanks to the definition of corruption robust and Azuma-Hoeffiee inequality, holds simultaneously for all l:
(q - qr)
(E[2]
k- -d,k TJ (q" -2)2 -90)2-k11
2 2-
(E(T)
Σ BE(T
F (q" gr)d,.EThe.. de,kl
2- k-1
(qa 2t 11, (E de he,k) Σ TT (q" qe ).) hee
2-
EE(T]
tE(T]
(T)
5 2-
L 2
Σ de +
B1 Σ
de,k + (B2 + B30k) max de,t
1E(2)
(E(TT)
[E(T]
(VVi+ Li Log log
T (t)
50
VT max de, + (B2 + 320) max de. (E(T]
2 2
rE(T]
EE [hr de E [[/4,, O. since the expectation is taken w.r.t. the randomization of Algorithm and the distribution generated given the external probability of receiving feedback w..
noticing that E & (E [/r, de.
he.x)]
[dr,a] Elhe,
To conclude with probability at least 1 - 28:
(q" - IT w. w 1 -
Σ [E[T]
48

---

Σ E ME CE(T)
F (q" ge)dkk
$ 0 B1 max + (32 + 9s ( |lggl ((g((1)())6))) max
Bs log(TTC)
tE[2] Wi
tE|21 we
$ 0
VT :gC), B1T + (2)
with VB 2 (ogl/))))T))) Notice that the analogous reasoning can be applied to the positive cumulative constraints violation with parameters 84, Pg. 36-
Algorithm 4 Adapted STABILIZE Jin et al 2024
Require: C, 6 (0, 1)
1: Initialize M = (T')(T') (T)) instance of Algorithm 2 each instance &s E [M] initialized with corruption parameter:
02 0 C 2 log (Tgg((T)
2:
for E [T'] do
3:
Observe wt, probability of receiving feedback.
4: if we > then
5: Let ky be such that wy E (2- 2-k Choose as policy proposed by instance kr
6:
If the algorithm receives feedback send it to instance with probability -
7:
8:
if w/ S then Propose random policy
9:
Corollary 6. Being j such that E [2 then with probability at least 115 it holds:
Elgc.d of -ai /VBTTr +Brrr 2BcC,
max ME
1E(T)
with VB4 = O (I
Bs = [|A//|oooo(T log (og(T)/6))and Be
O (In(T)((XIIA))
Corollary 7. Being jr such that Ce -20"-1,20" then with probability at least 118 it holds:
IT(g - " BITUTS + 32 + 2,3C,
EET
where VBi O (L|X) (L || B2 = = (oxx)()((loo(()) log (log(T)/6)) and Bs O (In(T))/X]AAI).
49


Reviews:
[{"review_id": "TfdQPfHAaj", "reviewer": "Reviewer_a8oF", "summary": "Constrained MDPs have traditionally been studied under two separate settings: with either stochastic or adversarial rewards and constraints. This paper designs algorithms with bandit feedback that can handle both, allowing rewards and constraints to change non-stationarily across episodes. The degree of adversariality is characterized by what the authors call the adversarial corruption C (essentially, the L1 deviation of the expected rewards and constraints). The first part of the paper introduces an optimism-based algorithm achieving $O(\\sqrt T+C)$ regret when C is known. \nThe second part develops an FTRL-based meta-algorithm that achieves the same regret guarantees even when C is unknown, by running multiple instances of the optimistic algorithm for different candidate values of C.", "questions": "Some questions above.\n\n- Is there any tradeoff between regret and violation? In particular, if we do not have lower bounds $O(\\sqrt T + C) $, can we at least show that Algorithm 2 or 3 are Pareto-optimal?\n\n- In the introduction, I wasn’t sure how the second application about recommender systems (ensuring users are not exposed to offensive content) fits into this framework -- how are the constraints non-stationary?\n\nMinor comments:\n\np3 Section 2. Define formally $L$ as the length of each episode.\n\np4 l162. $X_k$ was only defined in the footnote, it would be preferable to have it defined formally in the main body.\n\np8 l326. At this point, $w_{t,j}$ was not yet introduced in the text.", "limitations": "Limitations discussed appropriately.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper is well written overall, and I appreciate how the authors point out relevant connections to existing work. Conceptually, this paper shows that one can handle positive constraints (that is, constraints cannot cancel each other at different times), and shows that one interpolate between stochastic and adversarial setups with a regret bound that is analogous to previous works on corruption robust online learning, which is of interest to the community.\n\nThe proof techniques build significantly over previous works, especially Jin et al. 2024. The proof of the first result when the corruption level C is known seems fairly standard (handling the corruption level is mainly done by constructing appropriate confidence intervals). The main technical contribution seems to be for the second result when C is unknown. The high-level procedure is quite simple: instantiate (log T) several algorithms for exponential scales of C and run some FTRL procedure on it, however the proof requires bounding the size of the dual variable to enforce constraints and using a stabilizing technique from Jin et al. 2024. Overall the novelty seems sufficient.\n\nOne area that could be strengthened is the motivation. The authors give concrete examples in introduction for constrained MDPs, which are relatively well established, but could spend some time motivating adversarial rewards and constraints for the examples for constrained MDPs. \n\nThe benchmark should also be further motivated, since it is not standard and not fully consistent with the algorithms. Specifically, the violation total cost $V_T$ counts each violation positively: $V_T = \\max\\_{i\\in[m]} \\sum_{t\\in[T]} [\\mathbb E [G_t]^\\top q_t-\\alpha]_{i}^{+}$,\n\n but the benchmark for the regret is a policy that only satisfies these constraints in a non-positive way (that is, cancellations are allowed): $R_T=\\sum_{t\\in[T]} \\mathbb E[r_t]^\\top (q^\\star - q_t)$ where $q^\\star$ is only constrained to satisfy $\\bar G^\\top q^\\star \\leq \\alpha$, where $\\bar G = \\frac{1}{T}\\sum_{t\\in[T]} \\mathbb E[G_t]$. This is of course a stronger benchmark that if we were to ask that $\\mathbb E[G_t]^\\top q^\\star \\leq \\alpha$ for all $t\\in[T]$ but it would seem natural to impose the latter (or similarly to agnostic-type bounds, count the violation of the benchmark in a positive way) and then perhaps achieve stronger bounds (if possible). In that case, is it possible to achieve better bounds? Does the linear regret T bound still hold in a fully adversarial case for this milder benchmark?\n\nLast, the paper would be strenghened by discussing further potential lower bounds. In particular is $O(\\sqrt T + C)$ regret and violation necessary? Are there any known lower bounds (e.g. reductions from corruption-robust online learning? What about the dependencies in terms of $|X|,|A|,m$, are these tight?", "was_revised": true, "final_justification": "I am satisfied with Authors' responses and decide to keep my original evaluation.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\n> One area that could be strengthened is the motivation. The authors give concrete examples in introduction for constrained MDPs, which are relatively well established, but could spend some time motivating adversarial rewards and constraints for the examples for constrained MDPs. In the introduction, I wasn’t sure how the second application about recommender systems (ensuring users are not exposed to offensive content) fits into this framework -- how are the constraints non-stationary?\n\nWe thank the Reviewer for the opportunity to further elaborate on this point. Adversarial constraints are present in all the settings in which the environment encompasses other agents. For instance, in a repeated auction with budget constraints, the budget consumption at a given round depends on the bids of all the other agents participating in the auction. Thus, in such a setting, the constraint violation is adversarially selected. Furthermore, imagine a setting where the rewards and the constraints are somehow dependent and market-related. Rewards could model the probability **more the one** item is purchased, since the algorithm deals with a multi-state environment, while the constraints could model the ROI a certain company aims to achieve. Since the market is stochastic but highly non-stationary, it is reasonable and efficient to model the problem with adversarial rewards and adversarial constraints. \n\nAs concerns the recommender system application, the non-stationarity of constraints may be due to the fact that the way in which users perceive recommendations changes over time as an effect of mutated environmental conditions (e.g., at the geopolitical level). Thus, what is perceived today as \"offensive'' by a user may be acceptable in the future.\n\nWe will surely include this discussion in the final version of the paper.\n\n> Is it possible to achieve better bounds? Does the linear regret T bound still hold in a fully adversarial case for this milder benchmark?\n\nWe thank the Reviewer for the interesting point. The impossibility result does not hold when the benchmark satisfies the constraints at each episode; thus, in this case, it is possible to achieve sublinear regret and sublinear violation. Similar results exist, for instance, in the online convex optimization literature (e.g., see [1]). Nonetheless, we remark the following. First, the weaker benchmark can be arbitrarily worse than the one employed in our work. Second, the aim of this work is mainly the one of easing the impossibility result of [Mannor et al., 2009]; thus, focusing on the stronger benchmark was the way to go. To conclude, we believe that both baselines are of interest and deserve to be studied, but the results in the different settings are not easily comparable.\n\n> On the tightness of the bounds.\n\nWe are not aware of a formal lower bound on the dependence of $C$. However, in the corruption robust literature, an upper bound of order $\\sqrt{T} + C$ is commonly accepted as state of the art result. \n    \nIndeed, while the problem of studying corrupted CMDPs is fairly unexplored, we can draw a parallelism between our work and the literature of corruption-robust unconstrained MDP with corrupted transitions, where a similar impossibility result holds when both the losses and the transitions are adversarial. To the best of our knowledge, the dependence $\\sqrt{T}+C$ is considered state of the art for the MDPs with corrupted transitions and for other similar settings (see, [2],[3],[4],[5]) and commonly accepted as an optimal result. \nFor what concern corrupted CMDPs, to the best of our knowledge, there are no works that achieve even a multiplicative dependence on the corruption, namely, a bound of order $C\\sqrt{T}$.\n\nFinally, given the lower bound in online stochastic unconstrained MDPs which is of the order $\\Omega(L\\sqrt{|X||A|T})$ (see, [6]), we can say that NS-SOPS is tight in $L, |A|$, while it has a linear dependence in $|X|$. Lag-FTRL is tight in $|A|$, while it has a linear dependence in $|X|$ and a quadratic dependence in $L$. \n    \nWe will surely include this discussion in the final version of the paper.\n\n[1] \"Optimal Algorithms for Online Convex Optimization with Adversarial Constraints\", Sinha et al. (2024)\n    \n[2] \"No regret online reinforcement learning with adversarial losses and transitions\", Jin et al. (2024) \n  \n[3] \"Stochastic linear bandits robust to adversarial attacks\", Bogunovic at al. (2021)\n    \n[4] \"Achieving near instance optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously\", Lee et al. (2021)\n\n[5] \"Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions\", He et al. (2022)\n\n[6] \"Is q-learning provably efficient?\", Jin et al. (2018)"}, {"review_id": "WSEhfcCHPK", "reviewer": "Reviewer_EY1f", "summary": "This paper studies a CMDP where both rewards and constraints can face adversarial corruptions, whose cumulative magnitudes are denoted by $C_r$ and $C_G$ resp. Under unknown-transition and bandit-feedback model, an occupancy-measure--based algorithm with regret & positive constr violation of order $\\tilde{\\mathcal O}(\\sqrt T+\\max(C_r,C_G))$ is proposed. When no corruptions are present, i.e., a classical stochastic CMDP instance, the bound translates to $\\tilde{\\mathcal O}(\\sqrt T)$; in the worst case when rewards and constraints are completely adversarial, the bound agrees with the $\\Omega(T)$ lower bound.", "questions": "See Weaknesses 1 -- 3.\n\nAdditional question: Does it matter to change $OPT_{\\bar r,\\bar G,\\alpha}$ to $OPT_{r^\\ast,G^\\ast,\\alpha}$ where $r^\\ast,G^\\ast$ are the argmin in defns of $C_r$ and $C_G$? I think no?\n\nAlso in Lag-FTRL -- why we don't need to dynamically maintain a Lagrangian during the algorithm, like a standard primal-dual--based online learning algorithm? That is, why an upper bound on the Lagrangian $\\Lambda$ would suffice?", "limitations": "Not really. But aside from the Weakness 3 which is a minor one, I do not see many obvious limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The paper is overall well-written, with a clear flow on related works, main technical challenges, and the two steps towards $(\\sqrt T+C)$ regret.\n2. The $(\\sqrt T+C)$-style results is tight (up to logs), which distinguishes itself from the typical $\\sqrt{C}$-style dependency in classical bandits/MDPs and highlights the difficulty of adversarialness in CMDPs, as pointed out by the $\\Omega(T)$ lower bound. \n3. The technical contribution regarding the extension of CORRAL is non-trivial -- while the online learning loss / updates in Eqs. (5) and (6) do not look pretty astonishing on their own, according to the authors there is no suitable CORRAL-variants that work for primal-dual--tyle problems. But I'm not fully certain that I understand this part correctly; please refer to Weakness 2.\n\nWeakness:\n1. For the known-$C$ case, the algorithm is more-or-less standard adaptation of a stochastic algorithm to its corrupted counterpart. Nevertheless, given the extension to unknown-$C$ case, I understand that Sec 3 is more like a building block rather than main contribution.\n2. The authors mentioned that Lag-FTRL can be of independent interest; however, the current algorithmic form and description lack sufficient explanations to allow a seamless extension. It would be much better if the authors could write something as \"suppose that we'd like to solve a primal-dual problem like xxx with primal objective aaa and dual objective bbb, then instead of standard CORRAL we can use a Lagrangian-based variant of CORRAL that does ... s.t. aaa and bbb are optimized\".\n3. The transitions must be stationary (but I understand that it would be substancially harder for occupancy-measure--based algorithms). Nevertheless, it would be very interesting to incorporate the non-stationary(--transition) MDP literature.\n\nMinor: Lines 68--73 don't read to different from CORRAL / its variants; it would be better to move Lines 100--104 earlier.\n\nBut overall, given the clearly-written draft, the strong regret guarantee, and the non-trivial technical contribution, I would love to recommend an acceptance.", "was_revised": true, "final_justification": "I am satisfied with Authors' responses and decide to keep my original evaluation.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\n> The authors mentioned that Lag-FTRL can be of independent interest; however, the current algorithmic form and description lack sufficient explanations to allow a seamless extension. It would be much better if the authors could write something as \"suppose that we'd like to solve a primal-dual problem like xxx with primal objective aaa and dual objective bbb, then instead of standard CORRAL we can use a Lagrangian-based variant of CORRAL that does ... s.t. aaa and bbb are optimized\".\n\nWe thank the Reviewer for pointing out this aspect. We state that our meta-algorithm is of independent interest since it can be applied to many constrained online learning scenarios. In these settings, all the other coralling techniques fail, since they are tailored for single-objective scenarios. For instance, if future works will manage to extend NS-SOPS (with the additional stabilization part) to the linear constrained MDPs setting (see [1] for the definition in unconstrained MDPs, [2] for the constrained one), the analysis for the unknown $C$ setting will follow by employing Lag-FTRL with only minor changes. \n\nWe will better clarify it in the final version of the paper.\n\n> The transitions must be stationary (but I understand that it would be substancially harder for occupancy-measure--based algorithms). Nevertheless, it would be very interesting to incorporate the non-stationary(--transition) MDP literature.\n\nWe thank the Reviewer for the suggestion. We will surely include more details on the MDPs with corrupted transitions literature in the final version of the paper.\n\n> On the change of the baseline.\n\nThe Reviewer is correct, our results still hold for $r^\\star, G^\\star$.\n\n> Also in Lag-FTRL -- why we don't need to dynamically maintain a Lagrangian during the algorithm, like a standard primal-dual--based online learning algorithm? That is, why an upper bound on the Lagrangian $\\Lambda$  would suffice?\n\nWe thank the Reviewer for the interesting question. From a high level perspective, the reason is twofold. First, Lag-FTRL is not directly learning how to satisfy the constraints. Indeed, it is in charge of selecting the optimal subroutine, which, instead, manages the constraints satisfaction. Secondly, the loss given to Lag-FTRL is not a simple Lagrangian function, as it is in standard primal-dual methods. Differently, it is a positive Lagrangian; thus, when safe policies are selected, the second part of the Lagrangian goes to $0$, thanks to the $[\\cdot]^+$ operator, and there is no need to reduce the Lagrangian value.\n\n\n[1] \"Online Learning in MDPs with Linear Function Approximation and Bandit Feedback\", Neu et al. (2021)\n    \n[2] \"Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model\", Liu et al. (2025)"}, {"review_id": "61OlT1wXRd", "reviewer": "Reviewer_K4ij", "summary": "The author studies a constrained Markov decision process (CMDP) setting in which both the rewards and constraints are sampled from probability distributions that may change adversarially across episodes. This setting differs from the standard CMDP framework, which usually assumes that these distributions are fixed or stationary. To address this more general and challenging setting, the author proposes an approach based on occupancy measures and provides theoretical performance guarantees. Specifically, the paper considers two distinct cases: one where the nature of the adversarial corruption is known, and one where it is unknown. For each case, a dedicated algorithm is developed to ensure valid and efficient decision-making under uncertainty.", "questions": "1. While it is common to use occupancy measures in discrete settings, they can also be applied in continuous state or action spaces. Can the proposed framework be extended to handle continuous CMDPs? If so, what are the main challenges or limitations in doing so?\n\n2. For CMDP problems, a practical way to evaluate the performance of an algorithm is to examine the level of constraint violation in the empirical results. In particular, it is useful to study the trade-off between the objective value and the degree of constraint violation in out-of-sample testing. Can the author provide experimental results to demonstrate this trade-off and compare the performance of the proposed method against relevant baselines?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "\\textbf{Strengths.} The paper is well-structured, and the theoretical analysis is solid and convincing. This work addresses a challenging setting in which both the rewards and constraints are sampled from probability distributions that may change adversarially across episodes. Such a setting is difficult to handle and is not supported by many existing approaches in the literature.\n\n\\textbf{Weaknesses.} Although the theoretical guarantees are strong, the paper would benefit from empirical results. Including experiments would help illustrate the practical performance of the proposed algorithms and provide a more direct understanding of their behavior in realistic settings.", "was_revised": true, "final_justification": "Keep score", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\n> While it is common to use occupancy measures in discrete settings, they can also be applied in continuous state or action spaces. Can the proposed framework be extended to handle continuous CMDPs? If so, what are the main challenges or limitations in doing so?\n\nWe thank the Reviewer for the interesting question. We believe that in order to extend our results to continuous settings, it is sufficient to build a learning algorithm tailored for continuous state-action spaces for the case where $C$ is known. Then, to generalize the results to the unknown $C$ setting, we believe that the approach employed in Lag-FTRL can still hold, with some minor changes.\n\n> For CMDP problems, a practical way to evaluate the performance of an algorithm is to examine the level of constraint violation in the empirical results. In particular, it is useful to study the trade-off between the objective value and the degree of constraint violation in out-of-sample testing. Can the author provide experimental results to demonstrate this trade-off and compare the performance of the proposed method against relevant baselines?\n\nWe agree with the Reviewer that experiments are always beneficial; nonetheless, we underline that in the online CMDPs literature, many works do not provide experimental results (e.g., [1], [2], [3], [4]).\n\n[1] \"Exploration-exploitation in constrained mdps\", Efroni et al. (2020)\n\n[2] \"Provably Eﬃcient Safe Exploration via Primal-Dual Policy Optimization\", Ding et al. (2020)\n\n[3] \"Upper confidence primal-dual reinforcement learning for cmdp with adversarial loss\", Qiu et al. (2020)\n\n[4] \"Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs\", Liu et al. (2021)"}, {"review_id": "T6E3MU7m5o", "reviewer": "Reviewer_ZeN4", "summary": "The paper studies RL for constrained MDP where both the rewards and the constraints are adversarial. The paper bound the regret and (positive) constraint violation in terms of the corruption budget $C$. There is a related corruption-robust work under unconstrained MDP, but the setting for constrained MDP is largely unexplored. The paper first presents an optimistic algorithm when the corruption budget is known in advance. Then, they introduce a meta algorithm, reminiscent of the corralling bandit algorithm, that runs a meta bandit algorithm over multiple optimistic algorithms tuned for different corruption budgets.", "questions": "Q1) The corralling bandit reduction idea in corruption setting seems to have been also used in Jin et al. 2024 (Algorithm 3 in their paper uses similar FTRL). Although Jin et al study a different setting (adversarial loss + corrupted transitions), I think it would be good to discuss their algorithm and highlight the novelty of your algorithm in comparison to their algorithm in detail. What is the main difference from their algorithm?\n\nQ2) The paper studies corrupted reward + corrupted cost setting. Have you considered extending to corrupted reward + corrupted cost + corrupted transition?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\nThe problem setup and result are novel. The presentation of their algorithm is clear and mostly easy to follow.\n\nWeaknesses:\n\nThe algorithm seems to be similar to the one introduced by Jin et al. (2024). Highlighting the difference in the main paper seems necessary.", "was_revised": true, "final_justification": "Authors have addressed my questions. I am maintaining my positive score.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\n> The corralling bandit reduction idea in corruption setting seems to have been also used in Jin et al. 2024 (Algorithm 3 in their paper uses similar FTRL). Although Jin et al study a different setting (adversarial loss + corrupted transitions), I think it would be good to discuss their algorithm and highlight the novelty of your algorithm in comparison to their algorithm in detail. What is the main difference from their algorithm?\n\nWe thank the Reviewer for the opportunity to clarify this aspect. Indeed, our algorithm for the unknown $C$ setting is inspired by Coralling techniques as the one of [Jin et al. 2024]. However, these meta-procedures are specifically designed to deal with unconstrained problems, namely, their goal is single-objective: minimizing the regret. In our setting, minimizing the regret is not the only objective, since we want to additionally keep the violations as small as possible. Thus, it is not possible to blindly apply Corrall-like techniques, as it would lead to arbitrarily big violations. \n\nIn our work, we propose a Lagrangian approach by building the meta-algorithm's loss as a positive Lagrangian function, which, to the best of our knowledge, is a novel tool in the online CMDPs literature. Furthermore, properly balancing the regret and the positive constraints violation requires a careful calibration of the Lagrangian multiplier. On the one hand, the Lagrangian multipliers must be large enough to guarantee that it is not possible to compensate large constraints violation with a regret sufficiently negative; on the other hand, since the FTRL regret bound depends on the Lagrangian loss range of values, the Lagrangian multiplier must be small enough not to prevent FTRL from being no-regret (see Section F.1 for additional details on these aspects). Moreover, the rest of the analysis presents various challenges derived from the constrained nature of the problem and the definition of positive constraints violation (e.g., Section F.3). Thus, while inspired by Corral for what concerns the stability results, our analysis is novel and independent from existing works in the field.\n\nWe will surely include this discussion in the final version of the paper.\n\n> The paper studies corrupted reward + corrupted cost setting. Have you considered extending to corrupted reward + corrupted cost + corrupted transition?\n\n We agree with the Reviewer that extending our results to the corrupted transitions case would be of great interest. Nonetheless, the aim of this work was mainly that of easing the impossibility result on learning with adversarial constraints. Thus, we did not take into consideration the extension to corrupted transitions, even if we consider it an interesting future research direction."}]

Author rebuttal:

Meta-review: This paper studies an intermediate regime in CMDPs, where the rewards and constraints are generally stochastic, but can be corrupted by a corruption budget. This allows to improve on prior impossibility results when the corruption is sublinear.

With known corruption budget C, the algorithm is fairly standard. The authors match the bound in the unknown C regime, which required some non-trivial work.

All reviewers agree that the paper contains solid contributions, though it could be clarified to what extent they introduce new technical novelties over prior work.
Decision: Accept (poster)