Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization
Authors: Francesco Emanuele Stradi
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Venue: ICLR 2025 Poster (2025)
Keywords: CMDP
strong regret
strong violations
primal-dual
Primary area: reinforcement learning

Abstract: We study online learning in constrained MDPs (CMDPs), focusing on the goal of attaining sublinear strong regret and strong cumulative constraint violation. Differently from their standard (weak) counterparts, these metrics do not allow negative terms to compensate positive ones, raising considerable additional challenges. Efroni et al. (2020) were the first to propose an algorithm with sublinear strong regret and strong violation, by exploiting linear programming. Thus, their algorithm is highly inefficient, leaving as an open problem achieving sublinear bounds by means of policy optimization methods, which are much more efficient in practice. Very recently, Muller et al. (2024) have partially addressed this problem by proposing a policy optimization method that allows to attain $\widetilde{\mathcal{O}}(T^{0.93})$ strong regret/violation. This still leaves open the question of whether optimal bounds are achievable by using an approach of this kind. We answer such a question affirmatively, by providing an efficient policy optimization algorithm with $\widetilde{\mathcal{O}}(\sqrt{T})$ strong regret/violation. Our algorithm implements a primal-dual scheme that employs a state-of-the-art policy optimization approach for adversarial (unconstrained) MDPs as primal algorithm, and a UCB-like update for dual variables.

Published as a conference paper at ICLR 2025
OPTIMAL STRONG REGRET AND VIOLATION IN CONSTRAINED MDPs VIA POLICY OPTIMIZATION
Francesco Emanuele Stradi
Matteo Castiglioni
Politecnico di Milano
Politecnico di Milano
franceeccomanuelle. stradi @pol imi. it
matteo. cast ioni 8po1 imi itt
Alberto Marchesi
Nicola Gatti
Politecnico di Milano
Politecnico di Milano
alberto. marchesi@polimi
nicola, peattippoliin imi
ABSTRACT
We study online learning in constrained MDPs (CMDPs), focusing on the goal of attaining sublinear strong regret and strong cumulative constraint violation. Differently from their standard (weak) counterparts, these metrics do not allow negative terms to compensate positive ones, raising considerable additional chal- lenges. Efroni et al. (2020) were the first to propose an algorithm with sublinear strong regret and strong violation, by exploiting linear programming. Thus, their algorithm is highly inefficient, leaving as an open problem achieving sublinear bounds by means of policy optimization methods, which are much more efficient in practice. Very recently, Müller et al. (2024) have partially addressed this prob- lem by proposing policy optimization method that allows to attain (T70.93) strong regret/violation. This still leaves open the question of whether optimal bounds are achievable by using approach of this kind. We answer such ques- tion affirmatively, by providing an efficient policy optimization algorithm with Õ(VT) strong regret/violation. Our algorithm implements primal- scheme that employs state-of-the-an policy optimization approach for adversarial (un- constrained) MDPs as primal algorithm, and a UCB-like update for dual variables.
INTRODUCTION
Markov decision processes (MDPs) PPuterman 2014) have emerged as the most natural way of mod- eling learning problems in which an agent sequentially interacts with an (unknown) environment. In MDPs, the goal is to learn action-selection policy that maximizes learner's 's cumulative rewards. However, in many real-world applications of interest, there are some additional requirements that the learner has meet while learning. For instance, in autonomous driving one has to avoid colliding with obstacles (Wen et al. 2020 Iscle et al. 2018). in ad auctions the allocated budget must not be depleted (Wu al. 2018 He et al. 20021. ), while recommendation system offending items should not be presented to users (Singh et al. 2020). In order to capture requirements of this kind, con- strained MDPs (CMDPs) have been introduced (Altman 1999). These models augment classical MDPs by adding agent's 's costs that the learner is constrained to keep below some given thresholds.
In this paper, we study online learning problems in funite-horizae episodic CMDPs. In such settings, the learner's goal is twofold. On the one hand, they aim at minimizing their cumulative regret, which measures how much they lose over the episodes compared to always playing an optimal (i.e., reward- maximizing) policy that satisfies the constraint. On the other hand, the learner also wants to ensure that cost constrains are satisfied during lcarning. This is measured by means the cumulative constraint violation (or simply violation for short), which measures by how much agent's costs exceed their respective thresholds, cumulatively over the episodes. Ideally, the learner would like that both regret and violation grow sublinearly in the number of episodes T of the CMDP.
The classical notions of regret and violation are usually called weak, due to the fact that they allow for negative terms cancel out positive ones. In CMDPs, this means that the (weak) regret can

---

Published as a conference paper at ICLR 2025
be easily controlled by using policies achieving large rewards without satisfying the constraints. Similarly, the (weak) violation can be controlled by adopting policies satisfying cost constraints by large margin. However, this behavior is most of the times unacceptable in real-world applications. For instance, in autonomous driving, the learner does not have the option of being overly safe in some episodes as compensate for crashes occurred in previous episodes.
The strong regret and the strong constraint violation are much more reasonable metrics compared to their weak counterparts, as they do not allow negative terms to cancel out positive ones. However, achieving sublinear strong regret/violation in CMDPs is much more challenging.
Efroni et al. (020) were the first to provide learning algorithm with (optimal) Ö(VT) strong regret/violation in general CMDPs. However, their algorithm works by solving linear programs de- fined over the space of occupancy measures, a task that is highly inefficient in practice. Ideally, one would like learning algorithms that avoid dealing with occupancy measures, by directly optimizing over the policy space. Such policy optimization algorithms are much more efficient and desirable in practice. By leveraging a primal-dual scheme, Efroni et al. (2020) designed a first policy optimiza- tion algorithm for CMDPs, though it only achieve sublinear weak regret and weak violation, leaving as an open problem whether an analogous result achievable for the strong metrics.
Very recently, (Mäller et al. 2024) partially addressed this problem by proposing primal-dual policy optimization algorithm attaining (TT.983) strong regret and strong violation. However, the bounds achieved by such an algorithm remain largely suboptimal, leaving big gap that still needs be closed.
In this paper, we answer the following question left open by (Efroni et al. 2020 Müller et al.
2024)
Is it possible to achieve optimal (vTT) bounds on the strong regret and the strong constraint violation in CMDPs by using an efficient primal-dual policy optimization algorithm?
We answer the question above affirmatively. To do so, design a learning algorithm that exploits a novel primal-dual scheme. Specifically, our algorithm adopts, as primal regret minimizer, a state- of-the-art policy optimization algorithm for adversarial (unconstrained) MDPs, while it leverages an approach based on upper confidence bounds in order to build dual regret minimizer. Crucially, the updates of dual variables performed by our algorithm do not resort to optimizing over the space of occupancy measures, making our algorithm fully policy optimization approach, and, thus, efficient.
2 RELATED WORKS
Online learning (Cesa- Bianchi & Lugosi 2006 Orabona 2019) MDPs has received considerable attention over the last decade. Specifically, ly, online MDPs have been studied both in stochastic set- tings, namely, when the rewards are sampled from a fixed distribution (see, e.g., (Auer et al. 2008 Even-Dar et al. 2009)) and in adversarial ones, i.e., when no statistical assumption is made on the
rewards (see, e.g., (Neu et al. 2010 Rosenberg & Mansour 2019b a Jin et al. 2020
Online learning in CMDPs has generally been studied in settings with stochastic rewards and con- straints. Zheng & Ratlifi (2020) deal with stoly-stochastic episodic CMDPs, assuming known transi- tions. EEfoni al. (2020) propose two approaches (and four algorithms) to deal with the exploration- exploitation trade-off in episodic CMDPs. The first approach (i.e., the first two algorithms) resorts linear programming formulation of CMDPs and obtains sublinear strong regret and strong con- straint violation. The second approach (i.e., the last two algorithms) relies on primal-dual (or dual) formulation of the problem, guaranteeing sublinear (weak) regret and (weak) constraint vio- lation, i.e., allowing for cancellations. Finally, very recently Müller et al. (2024) proposed the first primal-dual method capable of achieving sublinear strong regret and strong constraint violation. The algorithm employs policy optimization update and regularized Lagrangian formulation of CMDPs in order to attain (TT0.33 strong regret and strong violation bounds.
Finally, it is worth remarking that online CDMPs have also been addressed in adversarial settings. Precisely, (Wei et al. 2018: Qiu et al. 2020 Stradi et al. 2024b) address CMDPs with adversarial losses, but they only provide guarantees in terms of (weak) constraint violations, thus allowing for cancellations. Very recently, Stradi al. (2024a) study CMDPs with adversarial losses and provide
2

---

Published as a conference paper at ICLR 2025
guarantees strong constraint violation. Nevertheless, their approach is nor primal-dus and their algorithm has to (inefficiently) solve a convex program at each episode.
Due to space constraints, refer the reader to Appendix A for further details related works.
PRELIMINARIES
In this section, we introduce notation and all the definitions needed in the rest of the paper.
3.1 CONSTRAINED MARKOV DECISION PROCESSES
CMDP Altman 1999) is defined as tuple (X, A, M, a,),, where:
X and A are finite state and action spaces, respectively.
E Nso is the number of constraints.
P: x A X + 10, 1] is transition function, with P(x' g. a) denoting the probability going from state x E X to E X by taking action a E A
E 10 is reward vector, whose component r(z, a) encodes the reward obtained by the learner when taking action a in state X.
G E [0, 1]|XxA A is cost matrix stacking a cost vector 9i E [0, 1||XXAI for each con- straint [m]]] The component (z a) of 9i encodes the cost associated with the i-th constraint incurred by the learner when taking action E A in state E X.
a E [0, LI is a threshold vector, whose component a, is for constraint E [m].
We study CMDPs where rewards and costs are stochastic, namely, they are randomly sampled ac- cording some probability distributions R and Gú whose expected values are and 9t. respectively. Specifically, a reward vector F [0, 1]]XXx4 XAA is sampled according to a probability distribution R. supported on [0, X|IX with Ex [F] Similarly, for every constraint i [m]], random cost vec- tor 91 [0, X| is sampled from distribution G; supported on [0, 1] xxAA with Eg, [ gi-
The learner interacts with the CMDP by employing a policy æ X A - [0, I]. which defines probability distribution over actions at each state. For ease of notation, we denote by T(-aæ)) the probability distribution for a state æ e X. with ग ({a denoting the probability of action a e A. In the following, we denote by II the set of all the possible policies the learner can choose from.
Algorithm depicts the CMDP interaction process, when the learner uses π X x A - [0, 1] and sampled reward and cost vectors are E [0, 1]]1 and g. E [0, 1] X A) for i E [m]. respectively.
Algorithm Learnee-EEvvirommen Interaction
Require: Policy X x A [0, F jo, 1] D. E [0, x| for E [m]
1: Environment initializes state to mig E Xo
2: for == 0...., L do
3: Learner plays 4 ~ (((()))
4: Learner gets reward F(Trk, ag)
5: Learner incurs cost (Z ax) for E [m]
6:
Environment evolves to T&+1 P(. [Tk ox)
Given transition function P: XxXxX [0, 1). policy X [0, 1), and a generic vector
E [0, x|xX indexed on state-action pairs, we introduce value function V=.P (-Io) X - |0, L]
W...o.g.. in this paper we assume to work with loop-free CMDPs. Formally, this means that X is partitioned into layers Xo... X1 such that the first and the last layers singletons. i.e. {r0) and X { and that P(z'Izz, a) > 0 only if x' X8+1 and Xg for some horizon CMDP with horizon that not loop-free can he cast into a loop-free one by suitably duplicating the state space H times, i.e., state is mapped to set of new states (r, k), where E {1,.... .H). In this paper, we denote with [n] = (1....,7) n the of all the integers from E Nyo-
{0, .., L 1). Notice that any finite-
3

---

Published as a conference paper at ICLR 2025
that is defined follows, for every lo E {0,............ L - 1) and x Xx:
VT.P (x, 1) = E
Σ u( ax) Dk
Moreover, we define V*h (v) == V*. (Ir,, v). Notice that V= and VT (+19)) encode the value functions for the rewards r and the costs Ii of some constraint [m], respectively. In the following, we sometimes omit the dependency of (-Iu) on P. when this is clear from context.
3.2 OFFLINE OPTIMIZATION IN CMDPs
The goal of the learner in a CMDP is to maximize expected rewards, while at the same time ensuring that all the constraints are satisfied, namely, expected constraint costs are below thresholds. CMDP characterized by a reward vector E [0, x|]XXXA] and cost matrix G [0, 1|lXXxX xxAxmm such a goal can be formulated by means of the following optimization problem parametrized by r and G:
OPT,,G maxxen (T(r) s.t. (T(g) S as Vi E [m].
In this paper, we assume work with CMDPs that satisfy the following assumption, which is common in the literature on CMDPs (see, egg. (Efroni et al. 2020)).
Assumption (Slater's 's condition). There exists a strictly feasible policy T : x A + [0, 1] such that V (g.) < for every constraint E [m].
We also need introduce the Lagrangian function of Problem I which is defined as follows.
Definition 1 (Lagrangian function). Given a CMDP with reward vector []xx] and cost matrix G E [o, x][xxA|xx the Lagrangian function L. II Rgo -> R of Problem is defined as follows, for every policy क E II and vector of Lagrange multipliers À Rgo-
(lo(=,A)=VVTT
Σ Na (VV((g)) az). sE(m]
Finally, we also introduce problem-specffee parameter & E [0, L]. strictly related the feasibility of Problem (T). and in particular to "how much" Slater's condition is satisfied. Formally:
max min (a; (g)))
Ell [m]
The policy leading to the value of p is denoted by .. Intuitively, represents the "margin" by which the "most feasible" strictly feasible policy satisfies the constraints.
3.3 ONLINE LEARNING IN EPISODIC CMDPs
We study episodic CMDPs in which the interaction in Algorithm i repeated over T episodes. At each episode 1. E [T), the learner chooses a policy म. X x A + [o, 1]. while some reward/cost vectors V2 R and 9r. G, for E [m]] are sampled by the environment. Then, the interaction goes as in Algorithm | with π Te, F Tt, and g. = 9t.s for all which the learner has bandit feedback, namely, they only observe the rewards and costs for the state-action pairs visited during the episode. Specifically, at the end of each episode t E [Z'], the learner receives as feedback from the environment the sampled rewards r' (at, 0g) and the sampled costs It, (IT. )2), for every k E (O....,Zo L- 1} and E [m]. Let us remark that the learner does not know anything about reward/cost distributions, as well as the transition function P.
[m]. We study the case
In episodic CMDPs, the performance of the learner is measured by means of the two metrics intro- duced in the following. The (cumulative) strong regret over T episodes is defined as:
T
RT
OPT - [r]
4

---

Published as a conference paper at ICLR 2025
where 1:] max(0, }. Intuitively, the regret measures how much the learner loses with respect to always playing an optimal policy. This a policy solving Problem ① and it is denoted by T². Thus, since O,T,,G V (r), write the regret Rr Ei= V (r) V (r))
The (cumulative) strong constraint violation over T episodes is defined as:
VT = max imlml
(g)) -a;]"
Intuitively, it measures how much the constraints are violated during the learning process.
The goal of the learner is select policies TH X A 0, 1), for each E [7], that both Rr and Vr grow sublinearly in the number of episodes T, namely, Rt o(T') and VT o(T).
4 PARAMETERS ESTIMATION
Let (x, a) be the number of episodes up to & E [T] in which the pair (ar, a) E X x A is visited. with 1, a) E {0, being equal to if and only if (æ, a) visited in episode т, is an unbiased estimator of the expected reward r(z, a). This immediately follows from the fact that Fr(2, a) is defined as the empirical mean of observed rewards for the state-action pair (2r, a). Thus, by applying Hoeffding's inequality, the following lemma holds.
Then, (2, a) = eyy (z,,)
max(1, (q.aa)
Lemma 1. Given confidence parameter ô (0, 1), with probability least 8, the following holds for every episode t E [I] and state-action pair (xr, a) E X x A:
Fa(ssaa) r(z,, a0 ()) where (e(x,, a) = min {I.V
max m (x..a)
Similarly, T0, a) == Erero I (1.a))
(s..)) is clearly an unbiased estimator of the expected cost
ge(2; a). Thus, by applying Hoeffding's inequality, it is possible to show the following lemma.
Lemma 2. Given confidence parameter 8 E (0, 1), with probability at least 1 - 6, the following holds for every i E (m], episode t E [T], and state- cate-action pair (I. a) E X x A:
(,,,,,))-((zaa))) (2, where (((x, = min {I.
4ln(7 X 1mm36)
max 1. (N,,)
Moreover, by letting Me( a, be the total number of episodes up to [T' in which the state- action pair (I,a) a) X x visited and the environment evolves to the new state x' E X, the (,,a,.z)) estimated transition probability for the triplet (ax a²x²) is Pt (z'|x, a) (c.. We refer to Appendix D.2 for additional details and results related to transition probabilities estimation.
Compact notation introduce F; E [0, x|AA to denote the vector whose components are estimated rewards (r, a). Moreover, we denote by Φ, E [0, x|IX the vector whose entries are the bounds de (z( a). Similarly, we introduce Jt.; E [0, x| to denote the vector of estimated costs (2, a), while we denote by & E [0, [0,1] XXxx the vector of the bounds (e a). Finally, we let T Fr dt. Ta f; 6r. It.; 9t,i + E., and g 92,1 &
5 A NOVEL PRIMAI-DUAL ALGORITHM
Next, we introduce a novel primal-dual algorithm, called constrained primal-dual policy optimiza- tion (CPD-PO), which allows to efficiently achieve Ö(VT)) strong regret and strong violation.
5.1 THE CPD-PO ALGORITHM
Algorithm shows the pseudocode of CPD-PO. employs an instance of the policy optimization with dilated bonus (PO-DB) algorithm by Luo et al. (2021), which is the state-of-the-art algorithm
5

---

Published as a conference paper at ICLR 2025
Algorithm 2 Constrained Primal-Dual Policy Optimization (CPD-PO)
Require: number of rounds T N>u. problem problem-specifie parameter p [0, L), confidence á (0,1)
1: mi f- first policy prescribed by PO-DB
2: Initialize all the estimators, counters, and bounds
3: for for11,, 1,....,? do
4: Interact as in Algorithm | with nr, F= rr, and 9. gt. for i [m]]
5: Observe (æg, ag), Tr (Zt, ag), and (Tx. a&) for every & E {O...., K 1 and i [m]]
as feedback from the interaction Algorithm
6: Build estimators Fi, Ie,i, Φt. Et, and Pt as prescribed in Section
7: Ae,i + arg max (0, = > (gg.)) as)) Vi [m]]
8: Build artificial loss for every pair (Ik ax) received feedback:
(e(2k, ak)
(L+ + 1)m
(((xk.a))
Σ
de. (TK, ax) 03)
p
(Eim]
9: Update policy 1 PD-DD ((()))((()))))))) ax), (o ax) km))
for learning adversarial (unconstrained) MDPs under bandit feedback. Notice that this algorithm employs a policy optimization approach, by efficiently optimizing state by state. Thus, PO-DB does not resort to any optimization step performed over the space of occupancy measures.
Algorithm 2 initializes an instance of PO-DB as prescribed in (Luo et al. 202T), and it immediately Furthermore, initializes the estimators Fi, 9t.;
uses it to get the policy T1 to be used at to vectors of zeros and all the counters Nr(rr, a), M,, (ar, a,x') zero (Line 2 Then, at every episode E (T), the algorithm plays policy ne (Line 4 and observes the feedback associated with the traeectory traversed during the episode (Line 5). The estimators and the confidence bounds then updated as shown in Section 4 (Line 6). The update of dual variables (Line 7 performed as binary choice between two values, namely zero and 1+1/pp for each E [ma] The value zero is selected when the optimistic estimation of the i-th constraint is not violated by the selected policy n (with respect to the estimated transition Pt). In such a case, in the next primal update, the algorithm will not focus on minimizing that specific constraint violation. On the contrary, the optimistic estimation of the i-th constraint is not satisfied, then the dual update selects the value L+1//. This quantity is chosen be large enough to guarantee that, with respect the deterministic Lagrangian game defined by the true reward and cost distributions, any policy cannot gain more than OPT, r,
(see Section 6.1 for further discussion on these aspects). We remark that the value V (g..)) in Line of Algorithm Saarthhm@aannnncc be efficiently computed by means of simple dynamic programming procedure. The primal update performed by the policy update of PO-DB. Notice that PO-DB is tailored for adversarial MDPs (in which no-statistical assumption is made on the loss functions) with bandit feedback. Thus, for every t E [T'. the primal algorithm expects to receive a loss value for any state-action traversed by the policy previously chosen (and the trajectory itself). We feed PO-DB by building a Lagrangian loss, employing the Lagrangian vector selected in Line 7 Notice that the estimated Lagrangian is subtracted and scaled by the state-action maximum (negative) loss (L+1)m/p since PO-DB is tailored for positive loss (see Line 8). Finally, the Lagrangian loss and the trajectory are given the PO-DB instance (Line Pp. We remark that PO-DB minimizes the loss function by employing state- state-by-stan by-tt optimization updates. Thus, it is computationally much more efficient than algorithms resorting to a projection on the occupancy measure space.
5.2 ALGORITHM COMPARISON WITH (EFRONI ET AL.
2020 AND MULLLER ET AL.. 2024
In the following, highlight the main differences between Algorithm 2 and the primal-dual for- mulations employed by Efroni et al. (2000) and Müller et al. 2024)
Efroni et al. 2020) were the first to introduce online primal-dual methods that achieve sublinear regret and sublinear constraint violation in CMDPs (allowing for cancellations). Müller et al. (2024) were the first achieve sublinear strong regret and strong violation via primal-dual methods.

---

Published as a conference paper at ICLR 2025
Efroni et al. (2020) propose two primal-dual algorithms The first algorithm (OptDual-CMDP) performs a UCB-like primal update given an optimistic estimation of the Lagrangian func- tion. Such estimation shares some similarities with ours. As concerns the dual update, Opt.ual-CMMD performs a gradient descent update on the optimistie Lagrangian. The second algorithm PeottPrmmalDaa 1CMDP) employs
of update for the pri- mal update. Precisely, this update is performed in closed form given the Lagrangified action-value function as objective. The dual update is gradient-descent-lik. with the additional modification that the Lagrangian multipliers space is bounded (similarly to our work) since the primal regret minimizer needs the loss/reward functions to be bounded.
Müller al. (2024) employ similar primal and dual regret minimizers as Opt
namely, multiplicate weights for the primal and gradient descent for the dual. Differently from Efroni et al. (2020). Müller et al. (2024) employ regularized scheme to define the under- lying Lagrangian game played by the primal and the dual regret minimizers. Indeed, the algorithm employs regularized Lagrangian formulation in order to make the primal objective strictly concave (in the state-action visit distribution) and the dual one strongly convex (in the Lagrangian variable). The strict concavitylstrong convexity is necessary converge in last-iterate the optimal values of the Lagrangian game and, thus, to attain sublinear strong regret and strong violation. In our work, do not resort any regularization scheme, thus simply employing the standard Lagrangian for- mulation of CMDPs. The main difference between our algorithm and those in (Efroni et al., 2020) Müller al. 2024) lies in the dual update. Indeed, the black-box primal update employed in our work is multiplicative weight like as the works described above") Differently, in the dual update, we use UCB-like update, thus not resorting to any adversarial regret minimizers. The UCB-like kind of update is performed between the minimum and the maximum reasonable value for the Lagrange variables. This modification allows us play the adversarial primal regret minimizer on the de- terministic Lagrangian game (up to confidence terms factor) associated with the "best" Lagrangian variable for the violations previously attained. Moreover, notice that our algorithm, since we em- play adversarial primal regret minimizer and differently from algorithms that employ UCB-IT -ike updates on the primal (such as DogtDuul-CMDPP may choose non-deterministic policies, which often optimal in online constrained problem.
THEORETICAL ANALYSIS
In the following section, we discuss the theoretical guarantees attained by Algorithm 2 Specifically, in Section 6. we provide fundamental results on the Lagrangian formulation employed by CPD PPO In Section 6.2 we discuss the guarantees attained by the primal algorithm. Finally, in Section 6.3
state the regret and violations guarantees attained by Algorithm
6.1 RESULTS ON THE LAGRANGIAN FORMULATION
In this section we state some useful preliminary results attained by Algorithm 2 following results concern the primal-dual scheme employed by CPD-PC. For the related omitted proof we refer to Appendix C.I] We start by showing that the dual variables decision space is well- defined. Indeed, it is fundamental to show that, given any policy selected by the black-box primal algorithm, the dual decision space is sufficient to upper-bound the Lagrangian function value with the constrained optimum. This is done by means of the following lemma.
Specifically, the
Lemma 3. Given a CMDP with reward vector r E [0, 1] x|AA and cost matrix G E [0, x|
for every policy II, the the following holds:
V=(r)=
Ae (V*(()) as) 5 OPT..G. Σ xE(m)
max XE O,
m
II is important highlight that apsDDualcMDD is often referred to dual method since the primal only updated given a UCB-like procedure the Lagrangian. Nevertheless, since the difficulty in attaining strong regret and violation holds for dual methods, too, we will refer to this kind algorithms as primal-dual. *eevertheless, it is an enhanced version with exploration honus, which allows to have independent adver- sarial regret minimizer guarantees (see [Luo (02T) for further discussion)
7

---

Published as a conference paper at ICLR 2025
As previously specified, Lemma B states that it is not convenient for the primal algorithm instantiated by Algorithmm to play non-safe policies in order to gain more rewards than the one possibly attained by safe policies. Again, this is true given the dual update performed by CPD-PO.
is important to notice that Lemma B holds for an optimization problem where rewards, constraints and transitions are known a-priori. Indeed, this is not the case in online learning setting, where all the aforementioned parameter are unknown and must be estimated in an online fashion. Specifically, if the dual algorithm were aware of the unknown distributions mentioned above, the dual update of A Algorithm combined with Lemma 3 would lead to:
L 2 (T,,
(2)
for all L [7]. Equation would be crucial to prove strong regret guarantees, since, it shows that the policy chosen by the algorithm cannot outperform æ², thus, making the standard regret definition (on the Lagrangian) to collapse to the strong one. Nevertheless, previously specified, Equation ( cannot be attained without complete knowledge of the environment. To overcome this issue, we prove the Equation (2) holds up sublinear term, which depends on the uncertainty the environment estimation. This is done in the following lemma.
Lemma 4. With probability at least 6, Algorithm
2 guarantees that, for every episode t [T];
41m (E.
8Tm
L, Ae) 2 (Te,(Te,))))
P P mEX,aAA
Σ
P P(,
P
The interpretation of Lemma 4 is the following: Equation holds up to two terms. The first term 4tmm/p- V* (Ex) encompasses the uncertainty on the constraints. Indeed, it is the expectation over policy Ta and transitions of the confidence intervals the costs. This quantity decreases as the algorithm collects cost samples, thus it is sublinear in T when summed over the episodes (we refer to Appendix C.2 for the concentration result). Similarly, the term
87m
Σ
P (x, a) P(,
P
REX,aEA
where (r, (z. is the state-action visit distribution given policy æ and transition P. encompasses the uncertainty related to the transitions. This term is sublinear in T when summed over the episode (we refer to Appendix [D.2 for the concentration result). Finally, remark that the uncertainty about the rewards does not affect the dual update, thus, Lemma completely independent on that.
6.2 PRIMAL ALGORITHM
In the following section we state the theoretical guarantees attained by the primal algorithm em- ployed by Algorithm 2 Precisely we have the following guarantees.
Lemma 5. Given any (0. the instance of PO-DB employed by Algorithm 2 guarantees that, for every policy E II, the primal regret (6.(T)) defined as:
Xe, (v -ai) oz)
Σ de. (v"()
-aa
Σ
(T((Ft) Σ
FE(m)
iE(ml
bounded as follows:
L (L'm
x ATT + L'm
Rf(TT) <Ō
with probability at least 1 - 1(8)))
5 obtained by the following considerations. First of all, the analysis employs the no-regret guarantees of PO-DB (refer to Appendix D.I and (Luo et al.) 2021) for further discussion). Indeed, possible to recover the (T)( definition by the loss function fed into PO-DB by Algorithm 2 Moreover, notice that the no-regret property of PO-DB cannot be directly applied to our setting, since the range of the losses is clearly different. Indeed PO-DB is tailored for standard episodic MDPs where the losses are bounded in [o, L). This is not true for the Lagrangified MDPs where the losses are bounded in [0, (L(L+))m/p] Nevertheless, it is sufficient to multiply the original bound for (Lm/p) factor to obtain the result.
by simple computation and using the linearity of expectation,
8

---

Published as a conference paper at ICLR 2025
6.3 REGRET AND VIOLATION
In the following section, we provide the cumulative strong regret and cumulative strong violation guarantees attained by Algorithm 2
We start showing that regret of order (VVT) is attainable by employing primal-dual method which does not optimize over the occupancy measure space. This is done in the following theorem.
Theorem 1, Given any E (0, 1), Algorithm attains:
L L'm m
L'm
Rr s
X VAITATT
AT
+
P
with probability at least 1 - (()).
Theorem 1 is proved by combining Lemma and Lemma Specifically, start from the theoret- ical guarantees attained by PO-DB, that is, using the bound provided in Lemma Next, employing the optimism of the confidence bound, we recover the true Lagrangian function, excluding sublinear terms. As previously specified, given Lemma 4 it is then possible to recover the cumulative strong regret definition on the regret formulated with respect the Lagrangian function. Finally, get the final bound, it is sufficient to notice that the optimal solution x is safe and that:
40m
Σ Ne, (V* - a.)
Σ =EX,uEA
P (2, (T,,,(,,
P
8E[m]
We underline that, from regret bound perspective, our result obtains the optimal regret order in T, while Müller et al. (2024) achieves a suboptimal 70.93 only. Furthermore, our bound not worse than the one in (Müller et al. 2024) w.r.t. the dependency on p. m and L.
We conclude by stating the result related to the cumulative strong violations. Even in this case, we show that the (vT)) order is attainable.
Theorem 2. For any E (0, 1), Algorithm
2 attains:
Vr s ① (1'I 1.5m).
with probability at least (8).
To prove the result, we proceed similarly to Theorem L namely, we employ Lemma and we apply the following equality
de. (T (g,,) - (2.))
T
Σ Ars (g.) aa)+ -os)) Σ yo. -
L +1
[E[m]
3E|m]
to retrieve the strong violation definition (up confidence terms). Notice that, given the I/r.+1 factor which allows us to retrieve the strong violation term, it is not possible to directly apply Lemma anymore. Nevertheless, is indeed possible to prove similar inequality. Specifically, it holds:
2Lm V
41m
Lr, x1) (m, /c/+)1))
Σ
P (2, -Pr,,((,,a)
P
P
=EX,aEA
Indeed, the inequality above can be employed to bound sublinearly the following quantity:
T
T
Cro d Ac4/2+1)
Σ Cr. Ad),
which in turn allows to bound sublinearly ET (V**( osl+ once excluded the sublinear terms associated to the confidence bounds. Finally, simplifying in the PO-DR regret bound the 1/o factor associated to the violation term gives the desired result.
Comparing our violations result with the one in Müller et al. (2024), Agorithm@aaate attainn the optimal ((VT) order in T, while Müller al. 2024) achieves suboptimal 0.993 For the violations, bound is not worse than the one in (Müller et al. (2024) w.r.t the dependency on m and L. Moreover, do not have the dependency on the Slater's parameter p.

---

Published as a conference paper at ICLR 2025
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 Arti- ficial Intelligence Research) project, funded by the NextGeneration program within the PNRR- PE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of Al for Sustainability, No. 101 101120237).
REFERENCES
E. Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for re- inforcement learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou (eds.), Advances in Neural Information Processing Systems, volume 21. Curran Asso- ciates, Inc., 2008. URL bttt:s:s/pproceedins..oo httpar/ss..ccpppp/////////////// http://///ooeeooo.oooor///s////0
pdf
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Qinbo Bai, Vaneet Aggarwal, and Ather Gattami. Provably efficient model-free algorithm for mdps with peak constraints. arXiv preprint arXiv:2003.0555. 2020.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Yuhao Ding and Javad Lavaei. Provably efficient primal-dual reinforcement learning for cmdps with non-stationary objectives and constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 7396-7404 2023.
Yonathan Efroni. Shie Mannor, and Matteo Pirotta. Exploration-exploitaaion in constrained mdps, www.aa////00022000
2020. URLEttps. / arxiv.
Eyal Even-Der Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, 34(3):726-77 2009.
Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Towards achieving sub-linear regret and hard con- straint violation in model-free RL. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, vol- ume 238 of Proceedings of Machine Learning Research, pp. 1054-1062. PMLR, 02-04 May 2024. URL https: http:://rooceddiee www.eedding...... pttss.....ss/...p/peeeeaea
html
Yue He, Xiujun Chen, Di Wu, Junwei Pan, Qing Tan, Chuan Yu, Jian Xu, and Xiaoqiang Zhu. A unified solution to constrained bidding in online display advertising. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2993-3001, 2021.
David Isele, Alireza Nakhaei, and Kikuo Fujimura. Safe reinforcement learning on autonomous vehicles. In 2018 JEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pp. 1-6. IEEE, 2018
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 (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4860 4869. PMLR, 13-18 Jul 2020. URL http:////ppoeecennnssm...eeeeese
Haipeng Luo, Chen- Yu Wei, and Chung- Wei Lee. Policy optimization in adversarial mdps: Im- proved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34: 22931 2021.
Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. Truly no-regret learning in constrained mdps. In Forty-first International Conference Machine Learning, 2024.
10

---

Published as a conference paper at ICLR 2025
Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online markov decision pro- cesses under bandit feedback. Advances in Neural Information Processing Systems, 23, 2010.
Francesco Orabona. A modern introductionn to online learning. CoRR, abs/1912. 13213, 2019. URL
http://arxiv www.aaiwww...oaaaaoaaaaaaooeeeee http//bb/119222 13213
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. Up- per confidence primal-dual reinforcement learning for emdp with adversarial loss. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15277-15287. Curran Asso- ciates, Inc., 2020. URL 2e522662//2155111112666666622222 Papero
www.eeeee....................... cc wttp:ccppppppppeee pttpppppppp///1leee
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and un- known transition function. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019a. URL https: /tttps::prroceeedngg neurips. htt..ips.cc/pppee/20000 ceee///0822cccbbccccccccco 3f Paper pdf
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5478 5486. PMLR, 09-15 Jun 2019b. URL
caainnsmmml. .mlr.
press/ v9 wow.nbergegbggooooooooe 9a. html
Ashudeep Singh. Yoni Halpern, 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, pp. 26-27, 27, 2020.
Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning ad- versarial mdps with stochastic hard constraints. arXiv preprint arXiv:2403.0367 2024a.
Francesco Emanuele Stradi, Jacopo Germano, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Online learning in CMDPs: Handling stochastic and adversar- ial constraints. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller. Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, www.iinnnsmll..........
pp. 46692 46721. PMLR, 21-27 Jul 2024b. URL 2 2 ltmm
.ml.
Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning constrained markov decision processes with non-stationary rewards and constraints, 2024c.
2405 14372
Honghao Wei, Amob Ghosh, Ness Shroff, Lei Ying, and Xingyu Zhou. Provably efficient model- free algorithms for non-stationary cmdps. In International Conference on Artificial Intelligence and Statistics, pp. 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. URL htRtsttss: /oo.. www/orrgr0000. 141/11/341111
Lu Wen, Jingliang Duan, Shengbo Eben Li, Shaobing Xu, and Huei Peng. Safe reinforcement learning for autonomous vehicles through parallel constrained policy optimization. In 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), pp. 1-7. IEEE, 2020.
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 Pro- ceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 1443-1451, 2018
11

---

Published as a conference paper at ICLR 2025
Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Alexan- dre M. Bayen, Ali Jadbabaie, George Pappas. Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger (eds.), Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pp. 620-629. PMLR, 10-11 Jun 2020. URL httpptt:: / /pwocedd ngs. ml www.srrsssvvv.... /0/ http:///11122////2222//a2/ html
12

---

Published as a conference paper at ICLR 2025
APPENDIX
The appendix is structured as follows:
In Appendix
A
we provide additional related works.
In Appendix B we provide the omitted proofs related to the confidence intervals.
In Appendix we provide the omitted proofs of the theoretical guarantees attained by
Algorithm 2
Specifically, in Appendix C.1 we provide the results which extend the strong
duality ones in constrained Markov decision processes. In Appendix C.2 we provide the results related to the regret bound. In Appendix C.3 We provide the results related to the violations bound.
In Appendix D we provide auxiliary technical lemmas from existing works. Precisely, in Appendix D.I we provide the regret bound of our primal regret minimizer and in Ap- pendix D.2 we further discuss the transition functions confidence intervals.
A RELATED WORKS
In the following section, we provide further discussion the works which mainly related to ours. Specifically, we will focus on online learning in unconstrained MDPs, on stochastic online CMDPs and finally adversarial online CMDPs.
Online learning in MDPs The literature on online learning problems in MDPs is wide. In such settings, two types of feedback are usually studied: in the full feedback model, the entire reward/loss function is observed after the learner's choice, while in the bandit feedbuck model, the learner only observes the reward given the chosen action. Azar et al. (017)) study the problem of optimal ex- ploration in episodic MDPs with unknown transitions and stochastic lossee, under bandit feedback.
The authors provide an algorithm whose regret upper bound is O(VT), thus matching the lower bound for this class of MDPs and improving the previous result by Auer et al. (2008). Rosenberg & Mansour (019b) study the online learning problem in episodic MDPs with ad 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 ((TT). The same set- ting is investigated by Rosenberg & Mansour (2019a) when the feedback is bandit. In such case, the authors provide regret upper bound of the order of Ö(T3/4), which is improved by Jin et al. 2020 by providing an algorithm that achieves in the same setting a regret upper bound of (VTT). Finally, [uo et al. (2021) provide the first policy optimization algorithm capable of matching the result of (Jin et al. 2020), while avoiding the convex projection on the occupancy measure space.
For the stochastic setting, Zheng & Ratlifi (2020) 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 OTT3/4), while the cumulative constraint violation is guaranteed to be below threshold with given probability. [ai 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 con- straints are stochastic with a particular structure. Efroni et al. (2020) propose two approaches to deal with the exploration-expllitttionn dilemma in episodic CMDPs. These approaches guarantee sublinear regret and constraint violation when transition probabilities, rewards, and constraints are unknown and stochastie, while the feedback bandit. Precisely, their I.P based methods guaran- tee Õ(VT) cumulative strong regret and cumulative strong constraints violations. Differently, their primal-dual (or dual) algorithms attain Õ(VT) weak regret and violations. Müller et al. (2024) provide the first primal-dual procedure capable achieving sublinear cumulative strong regret and cumulative strong constraints violations. Finally, [Goos et al. (2024) propose model-free primal- dual algorithm for the linear MDP setting. Their algorithm attains Õ(VT) strong violation if it allowed to take (2d ( log([A)) computational steps in every episode. Differently, we focus polynomial-tine algorithms that attain strong regret and violation guarantees.
Online learning in stochastic CMDPs
13

---

Published as a conference paper at ICLR 2025
Online learning in adversarial CMDPs In the adversarial setting, Wei et al. (0188) deal with adversarial losses and stochastic constraints, assuming the transition probabilities are known and the feedback is full. The authors provide algorithm that guarantees upper bound of the order of (VTT) both regret and constraint violation. Qiu al. (020)) provide a primal-dual ap- proach based on optimism. This work shows the effectiveness of such an approach when dealing with episodic CMDPs with adversarial losses and stochastic constraints, achieving both sublinear regret and constraint violation with full-information feedback. [Stradi et al. (2024b) provide the first hest-of-both-worlds algorithm for CMDPs, under full feedback. |eii al. (2023) Ding Lavaei (023) (tradi et al. (2024c) consider the case in which rewards and constraints are non-stationary, assuming that their variation is bounded. Preciscly, all the works mentioned above focus on con- straints violation which allows for cancellations. This is not true for Sttadi al. (2024c), where strong constraints violation guarantees are provided. Nevertheless, their algorithm is computation- ally more expensive than primal-dual procedure, since a linear program must be solved at each episode. Similarly, Stradii et al. (2024a) study the setting with adversarial losses, stochastic con- straints and bandit feedback, achieving sublinear regret and sublinear strong constraints violations. Again, their algorithm is less efficient than the one we propose in our work, since a convex program must be solved for each episode.
B CONFIDENCE INTERVALS
In this section, we report the omitted proof related to the confidence interval employed by our algorithm to deal with the uncertainty the environments.
Lemma 6. Given any ò E 10, i [m). t [I] and (x,a) E X A, it holds, with probability at least 8:
Fo(zza) - r(x,a) a(z))) s az)
Similarly, with probability least 1 5, it holds:
[0.(2, a) 9. a(x,a),
where 4x(x, a)
ln(2/8]
2Na(n,a)
Proof. Focus on specifics & [T] and (x, a) X A. By Hoeffding's inequality and noticing that rewards values are bounded in [0, 1], it holds that:
P
( r(z.a))
(((x.a)-((a)) r((,)))
2cxp (-
(-N((,,)))
2ca
No(z,a)
Setting 8 = 2 exx function.
202 (r(x,a)
and solving to find a proper value of gives the result for the reward
Focusing on specifics i E [m], t E [T] and (z E X x A and following the previous reasoning applied to the constraints functions concludes the proof.
B. REWARDS
Lemma 1. Given confidence parameter 8 (0, 1), with probability least 1 - 8, the following holds for every episode 1 E [T] and state-action pair (x, a) E X x A:
Pi(x,a)-r(aa)
()), where de a) min {1,
max max(1, (a.n))
Proof. From Lemma 6 given 8' e (0, 1), we have for any E [I] and (æ, e x
P Fr a) r(x, a)) s u(( 2 21-8.
14

---

Published as a conference paper at ICLR 2025
Now, interested in the intersection of the aforementioned events:
r((,,) (( P
n
s su(or0))
2,0,3
Thus, have:
P
n ( s a(0
=1 P
U
s su(vaa)
x,0,t
2 1
Σ
-M(,a)) su(o,
-((,a))
k,a,t
2 1 - [
where Inequality (3) holds by Union Bound. Noticing that ra a) 1, substituting 8' with ó = ///x|| in 41 a) with an additional Union Bound over the possible values of (2, a), and thus obtaining de (2, a), concludes the proof.
B.2 COSTS
Lemma 2. Given confidence parameter 8 E (0,1), with probability at least 1 - 6, the following holds for every? i (m], episode t [T), and state-action pair (x, a) X A:
Bis(x, a) gi(x, a) Ex a)), where Ee(x, a) = min {1, V
/An(T) (Alm/6) m. f
Proof. The proof is analogous to the one of Lemma with an additional Union Bound over the m constraints.
C PROOFS OMITTED FROM SECTION 6
C.I STRONG DUALITY
We start by proving that, when Slater's condition holds (Assumption D. in optimal solution the vector of Lagrange multipliers bounded.
Lemma 7. Given a CMDP with reward vector E [0, 1] x|xxx. Al and cost matrix G E [0, 1] X it holds:
min XERT MERT:IAAILE Nell
max (n.a(T, = max #ell xeRp-
min
C,, OPT,,.
Proof. We start by proving the following result:
max (T, min max C, A). xERT:
min
AeR sell
To do so, let first notice that, for every X E R Rno such that |A/l2 L/p:
max Nell
Cr.o C, (
Σ A V (gi) as) 2 ||alip>>>> L,
(E/m]
where we recall that T" == arg max min (a; (gi)). Moreover:
min XERT:IAAllEjjo///
max fr. (T, A) max L, (,, = .max VT S L.
Tell
mell
This implies that:
min max (T, A) = min
min
max Cr,a(T,
min
max (n,
xxxm
#ell
(0,%// wEll
>| sell
15

---

Published as a conference paper at ICLR 2025
min max (T,,
MER":||AlLE00444 well
In conclusion,
OPT, max min (T,
fell AER
20
max min
xel xERT-INliEt0.40 (T, A)
min
max ((T,
A (11 xell
min max (T, A Fell
OPT,..
where the second inequality above holds by the max-min inequality and the last equality by strong
duality in CMDPs (refer to (Altman 1999)). This concludes the proof.
Now we extend the result showing that, depending on whether an occupancy is safe or not, there exist values of À such that the optimal value of the Lagrangian coincides with the optimum of Program (T).
Lemma 8. For every reward vector r E 0, 00,1]IXxA1, constraint cost matrix G E [0, 1j and threshold vector E [0, Ll" and π E II s.t. V (g:) I a4 Vi E [m], it holds:
(,, < OPT.a-
Proof. The proof directly follows from the definition of OPT, induced by Program
Lemma 3. Given CMDP with reward vector E [0, xxxX and cost matrix G' E [0, 1] Xx for every policy π E II, the following holds:
(=(r)=
Σ SE/m]
d (V a:) S OPT,,-
AE
Proof. We analyze separately the case in which satisfies the constraints (i) and the case π is not safe (ii).
(i). We start analyzing π s.t. V (g:) I or for all i E [m]] In such a case, it is easy to check that arg m L Eie(m] À (V* (g.) a,) Q: thus, employing Lemma 8 gives the result.
(ii). We then consider the case is not safe. In such case, π may either partially sat- isfy the constraints or violating all the them. First of all we notice that, such a scenario, arg argmaxxe xe (o, = Eie(m] ); (V* (0:) a.) = X where À is the Lagrangian vector composed by 0 values for the constraints which are violated and L+1/p values for the others.
Indeed, holds:
L (T. = V - Σ As (V: -03)
rElm]
L+1 1
max V (T(r)
(V aa,
(4a)
rell
iE|m)
max V (r) HEll
[V (g:) - azl +
P {Eim]
max
min sell [A
Σ
X [V= -as
sE/m]
min
max V" (r)
Σ [v (0:) -as]
(4b)
well
16

---

Published as a conference paper at ICLR 2025
min
max Lr. ()
||l well
O.T,.G.
(4c)
where the Inequality 4ap holds by definition of X, the Inequality (4b) holds by the max-min inequal- ity and Inequality (4c) follows from Lemma 7 This concludes the proof.
Finally, we show that the sequence of Lagrangian vector A selected by Algorithm 2 guarantees that the value of the Lagrangian attained by n, is always upper bounded by the value of the Lagrangian attained by the optimum ' to "confidence bound" terms.
Lemma 4. With probability at least 8, Algorithm guarantees that, for every episode L [T];
C, Ad) 2 Cr,a(Te
4Lm V (E:)
8Lm
Σ
P, (z, a) P PL,
p
EEEE
Proof. First of all, we notice that, when A = D. L Ao) = OPT,,G by definition. Furthermore when d is the L+1 vector, it holds that Cr,a(T", Ax) 2 OPT,,G since n is feasible. Same reasoning /
holds when de is any vector in {o. L+1 1 Thus, it always the case that L, Ax) 2 OPT,,G- p
Thus, proceed follows:
(Te, Xd)
V= (r)
Σ A1.
(TT( (VT((ge)) (ge -as)
(5a)
iE|m
(T) Σ
de.
| (g+,)) -a,) -a)= 1 Σ de,
( - -as)
mE|m)
iE/m]
P. [g. - -as) + 4Ta
s <V - Σ A
P 1 ( - P(.
(5b)
iE/m)
=EX.eEA
-V=((r)
Σ > ((,))((0,)) as
max
xe 00. 1-1
im(m)
4Lm
+ P =EX,aEd
P (1, - ((,
< (r((r))
max
Σ iE(m)
As
(pTnP (g: - 25x) - as
a 1
4Lm
P (
- ((,.. (5c)
P *EX,
(r)
max
Σ \i ( (g:-261 - aii
xE fo. L- m
iE(m)
4Lm
P Fr (I, -P ((r
a)) +
Σ (V=L (gs -26,) o4))
max
p xEX,
xefo,
8E/me
< (T)
max xE fo, 1
Σ (V=L (g. 2E,) -0s)
=E/m]
8Lm
+ P REX
P - P(,
(5d)
4Lm
Σ (V=L (g:) - ai) +
(T)(E))
max XE f0. L=1 m
+ 8Lm
P (,, - PF.,
(5e)
P =EX,aEA
17

---

Published as a conference paper at ICLR 2025
Ai (ai) ai) + 4Lm (Et(
(T)
Σ
max 0.
1c(m]
8Lm
+
P (1, - P(,
=EX,aEA
OPT,, G + 4Lm (EI)
8Lm
Σ
P P. (z,a) - Px),
(5f)
P
REX,aE
where Inequality (5a) holds with probability at least by Lemma 2 Inequality (5b) holds by
Hölder inequality, Inequality (5c) holds with probability least 5 by Lemma Inequality (5d)
holds by Hölder inequality, Inequality (5e) holds by definition of A, and Inequality (5t holds by
Lemma
Thus, it holds:
f 2 OPT,,G
4Lm 2 (Te,
8Lm Σ
v (C))
P (1, P(,
P
=EX,aEA
which concludes the proof.
Lemma 9. With probability at least ô, Algorithm 2
guarantees, for all t [T]:
C, Ar) 2 fr (Te, A14/2+1))
2Lm V (Ex)
4Lm
Σ
P P. (x,a) - P P(, a)
=EX,
Proof. Similarly to Lemma we notice that G,," Ax) 2 OPT,,G
Thus, following the same steps in Lemma
we proceed follows:
f 111/1+1)
d L
2Lm
(r)
max d=1 m
(V**(a)) - -a;)
V=l (Ex)
Ae
P
=E(m]
4Lm
Σ
P.. (I, -Pr,,(),,))
=EX,aEA
(T)
max
Σ
A,L (V* -a;)= +
2Lm
(E((E))
AE ا
m
L+1
sE(m]
4Lm
Σ
PP
P a) P p(, a)
P
*EA
2Tm
Av (9:) ass) +
max AE [. E/mi
4Lm
+
P & (2, - (aaaa)-a..ppee -P,,,(Z,,))
p
2mm
< max
(=(()-
max
Σ (V" - 03)
+
p (Et)
#ell
xe
iE[m]
4Lm
Σ
IP R. (x, a) -P P(. a)
p
*EX,0EA
2Lm
< max MENI
V=(r)
max
Σ (o -ss)
+
V (Er)
E.. 41 :E|m]
p
18

---

Published as a conference paper at ICLR 2025
4Lm
+ P
IP (e, - -P P.,,
xEX,aEA
OPT, N + 2Lm (Et) +
4Lm
P (c, a) (0 -PT,,(()))))
(6)
xEX
where Inequality 66 holds by Lemma 7
Thus, it holds:
fr,o(0" .2)) 2 OPT,,G
2Lm
41m Σ =EX,EA
2 (T,, ALb/111)
V (Ei)
P ( - -Pa, P(,
p
P
which concludes the proof.
C.2 REGRET
We first show the regret bound attained by PO-DB on the Lagrangian loss built by Algorithm Precisely, it holds the following result.
Lemma 5. Given any d E (0, 1). the instance of PO-DB employed by Algorithm 2 guarantees that, for every policy II, the primal regret (f((T) defined as:
(T. Exe: (v"(g.)) -0:)
Σ
Vhe
Σ iE(m)
Xe,
(g.e) -as)
(E(m)
bounded as follows:
( IIIV + L
L'm
RT((T) 20
p
with probability at least 1 0(8)-
Proof. We first notice that, by simple computation, it holds:
V
(L + 1)m
T
V=((F)) Σ
V
(2,
04
T.
P
sE/m]
V
(T.
1)m²
Σ
T
VT(TT) Σ
Ne.VV
(2es (i)
P
iE|ml
T
V=((T() Σ Ve
(g,5
g
a's
+
(T((T)
Σ
\v.V
(g.s )
L
t=1
1E/ml
1=1
iE|m)
T
V*((T)) - Σ des ( (2, -aa)
-
(T((F))
Σ No.
( (g. as)
=E|m
mE|m]
where the first step holds since (L+1)m// is constant for any state-action pair and the second step holds since (*(a//)) Us.
Then, we notice that, any regret minimizer algorithm A, which attains ε regret upper-bound when the losses are bounded in J0, 1] (or in [0, L] for MDPs), may achieve C'EEA regret upper-bound when the range of the losses is C' and it is known to the algorithm. The result is intuitive, since it is always possible to apply affine transformation to the losses received and, thus, to scale them in J0. 1]. Then, the algorithm can be fed with the scaled loss as expected, but it will suffer a loss multiplied by C' factor, attaining the aforementioned C ΣA bound.
Noticing that the loss vector received by PO-DB is multiplied by an additional O p) factor given by the definition of the Lagrangian variable in Algorithm 2 employ the standard regret
19

---

Published as a conference paper at ICLR 2025
bound PO-DB (see Lemma 12 with the additional O(Lm/p) factor. Thus, it holds, with probability at least 1 - (():
T
T
v (Fr)
Σ Aes
V (g - os)
Σ
V
Σ An.
-cis)
-
:E|ml
/E/ml
T
V
(I. (I+ 1)m
Σ (Ti((t)
Σ
Ve, 21, L
(i)
p
1=1
sEfml
Σ v*
(L (L+ 1)m
Σ
T
(T(T))
Σ
Nest I -2,
iE(m)
<ō
mm @ P
XIIAT
L'm))
which concludes the proof.
Then, we show the concentration rate of the confidence intervals.
Lemma 10. With probability at least 1 - 8, it holds:
TIX
vT (ot) S 4 4X
+ L 2T'n
8
Proof. We first notice the following bound,
v (oe S L.
Thus, we can employ the Azuma inequality to bound the following Martingale difference sequence
as
T
T
Σ (o) - Σ [o((x,a))(fz.0 s LV 2T in 8'
1=1 a,
which holds with probability 1 - 8. Thus can bound the quantity of interest follows,
Σ vh (xx)
Σ
dh (1 (1) I 27 27
1 J
||
max max N,, Te(x,a) + T. /n 27
1
4
8
j
(=1 a,a
T|X||
2
4ln
VNr(x, L 27
(7)
8
(TIXIIA)
LI
+ +L
2T
(8)
where Inequality holds since Σt 1 < 2 and Inequality (8) follows from Cauchy-Schwarz
inequality and noticing that v En,o (r S VLT. This concludes the proof.
Lemma 11. With probability least 1 6, it holds:
(TIXIIAmm)
VE) AV ||
L 2T
Proof. The proof follows the one of Lemma TO replacing Φi with &
20

---

Published as a conference paper at ICLR 2025
We now ready to prove the regret bound of Algorithm 2 Theorem 1. Given any E (0, 1), Algorithm 2 attains:
L
Ldm
Rr S δ
X
A/T
+
with probability at least 1 - (()).
Proof. We first notice that, by Lemma we have that:
fr,a(T", 2 (Te, As) 4Lm Vm (Et)
SLm
Σ
P (E, - ap
e E
P
zEX,aEA
with probability at least 1 - and where n' is the optimal solution corresponding to OPT,, Thus, we have that an upper bound on:
41m G A1) - Cr.
8Tm (Ee) +
Σ zEX,aEd
IP F (I, - P P.. (2,
P
P
enforces the same bound on
Σ C Ae) (Te, Aa) 4Lm V (E: +
SLm
Σ =EX,aEA
| (s. - P(,
p
since the term in the summation always non-negative.
Now, we employ Lemma which implies that with probability at least - O()), for any E II:
(T(T)) Σ ded (VT(e)))
Σ
V=((T.) Σ
des
-o:)
mm(m)
iE(m)
L'm
L'm
I Ö
X
+
(10)
which implies the same bound for x²
We now show that the left-hand side of the aforementioned equation reduce to Equation sublinear terms. By Lemma Tith probability at least 8, it holds:
up to
Tt-
Thus, taking the expectation over policy and transition we obtain:
("(r) < V (r.).
Thus, Equation 10p can be rewritten as:
ya (r)
Σ Ae,i (V"'(e,) (g, --a))
Σ
v=*(r.) Σ No. (g - -ai)
iE|m]
1=1
iE|m]
Lim
L
x |AAT
Similarly, it holds that Pr I + te which implies:
vx (r) - Σ des (vx' (o -ai) -o:)
T Σ
(a - Σ de,s
/Ke (1,)) as
:E(m)
1=1
xE(ml
L3m
T
<
X A +
+2 >
V (bt).
t=l
21

---

Published as a conference paper at ICLR 2025
We apply Lemma
10 to obtain, with probability at least 1 - O()), by Union Bound:
T
T
v (r)
Σ de, ( (2,.)-aa) an)
Σ t=1
(=
Σ
Xu, (vmL
(2..) as
-
[E|m]
SE sm(m]
I.2m
I.Om)
|Xlv A
+
P
We proceed similarly for the constraints cost noticing that 2 I gin and gi 2h 1 21, for all i [m]. Thus, we have:
T
021)
-
v (r)
Σ de, ('* (9:) (0:))
Σ
(=((r) - Σ
Ae, (gi) ai)
t=1 mm(m)
t=1
[E(m]
L.m Ō
L'm
T
XIIIIATT+
2m
V (Et).
P
t=1
Finally, employing Lemma
11 we have that the regret defined over the Lagrangian is bounded by.
) Σ V=((r)
Σ de. ( (VT(())) (1t)) -0)) (1)))))))))
v (r)
Σ
Ae.
(V=
as))
(E(m)
sE[m]
T.3m
1.5m
X
A
Now, we notice the following inequality,
V (r) (r)
Σ Ae, 1x (gi) (0))) -aa)
(P(( - Σ
Ne, (V - -as)
EE [m]]
iE(m)
4Lm (E(( +
8Lm
P P. (I, - -pr) -Pmnplzaaa))
p
xEX
L
x XI + L'mm)
which implies the following chain of inequalities,
yz (T) (r)
d (x" (gt) -ai)
(TT - Σ
des (V (g.) - as)
AE|m]
sE|m]
4Lm
VT(
+
8Lm
(2, - Prop(tnaa) (o,
P
P
=EX,aEA
L'm X
L'm
T
4Lm
< Ō
|A +
+
V (Ex)
t=1
T
8Lm
P (x, - -Pn, a)
1=1
xEA
L.
L P
| T
where in the last step employed Lemmal [ and Lemma 14
We then employ Lemma 4 to get the following bound:
T
Ar) + 4Lm V= (E+)
8Lm
Cnol ..e) (r.o(Te.
+
(2, PR, Pr, (z,
p
P
22

---

Published as a conference paper at ICLR 2025
1 <ō L.3m
+ I.m
x V
which, since 2 (Ex) and implies:
8Lm P
(z, a)
IP xx p(t are non-negative by construction,
"
nx.
T
Σ
V V= (r) - E de, (V=' (gi) (4i) -ai) (+) - Σ de, (g:)) - -as)
=E(m]
ic(m]
L'm
L
S θ
AT +
P
To get the final bound, we first notice that, by definition of the constrained optimum n², the quantity V (g:) a; is always non- non-positive for every i E [m]. Moreover, by the Lagrangian update of Algorithm we have that:
Σ
de, (V (gi) az)
vE(m)
de,
V (ge,) -as)
iE [m]
Σ X
V (=((g,,) - -ai) + Σ de, (VTc.P( (g.))
-as) ai)
ic/m]
sE|m]
A
Vee.Pe Pt
((gg, (ge,) -Ok)
4Lm
Σ
iE[m]
zEX,EEA
4Lm
P (e,,((1,0)) -P ((2,a)
P
xEX.aEA
Thus, following the reasoning above, we bound the positive cumulative regret as follows:
4" (r) - (r)-v=((r) (T)
RT
/* (r) (r) Σ des (V= (g.) (0)))ai)
(x(())- Σ
Ne. (V= -a;)
[E(m]
tE(m)
4Tm
P (,,, - (RIP((1,))
P
sEX,CAA
V (r) - Σ Ne. (v=(())= -as))
(g:)
(=((r)- - Σ
Ne. (V= -cs) ass)
kE/m)
4Tm
(2, - - -p,
*EX,EAA
I 5 I.
I.mm)
T
4Lm
x
V
+
+
Σ
P ( - (ar.a)-Pm.pP2.00 P(,
P
1=1
zEX,aEA
L'm
L'm P
<
XIVIA|T+
which holds with probability - 06) by Lemma 14 and Union Bound. This concludes the proof.
23

---

Published as a conference paper at ICLR 2025
C.3 VIOLATIONS
Theorem 2. For any ò E (0, 1), Algorithm Lattanns:
Vr s Ō [ VIAIT +
with probability at least (6)).
Proof.
We first notice the following equations:
Σ de,i
(yTTs, (gr.) (gg.))
ai)
*E(m]
L
de,
(V (gee) - (1))
Σ ded
(ged)
I
Tc(m]
iE(m)
L de,i
(v ai)
+
1 Σ
(g..)
as
(1I)
P re(m)
[E(m]
where Equation
holds by definition Xe-
Employing similar steps to Theorem
holds, with probability at least 1 ((())
)
v (r)
Σ
de. V (0:) (0:)))a)) Σ (=l(r)
Σ A
(g) -as)
(E(m
iE|m]
L
L
P
Adding and subtracting the estimated violation the following inequality holds:
Σ ( A1))
vTa
(r)
de.
-a)
V=
-a)
Σ de, (g..)) as)
1=1
mE/m)
iE mm]]
T.²m)
X VIAT+
p
which by Hölder inequality and Lemma
14
14implies:
Σ C (tt
Σ (=((r)-
Σ de, (vma.Di(g.n) as
(c(m)
L.m σō
- |X|v |A/T + LPm
(12)
Thus substitute Equation
11 in Inequality 12 obtain,
Σ C A1)
Σ (T(
L
Σ N
( (gg,)((gg,) -as)
L+1 5c/m]
Pe Pe (2, - ail aa]")
P
mm(m)
L (L' XIVITT
L.m p
+
To get back to the Lagrangian function of the offline problem, we notice that:
Σ Ne. (ym.PP ((,.) 0z;
L+1
(E(m)
24

---

Published as a conference paper at ICLR 2025
L
Σ
(VT...s
- ais)
ic(m)
L
Σ
d
(V=((g))
-as)
2Lm (Et(
2Lm
Σ =EX,0EA
P (T, a) - Pa (t,
and we employ Lemma 11
Lemma
14 to obtain:
T Σ L ,7)
T Σ
T +
P - ai]
L A1/1+1)++++
1=1
1=1 iE(mi
LLmm
+ L'm
XIVIAAT++
p
Thus, similarly to the steps above, we notice that:
ya. Po ( cij
+
sE/m]
Va (gi- 25t) Oi
+
[m]
2m V* (Ex)
2m Σ
V (gi) a;)]
P
xE/m]
=EX,aEA
Employing Lemma
11 and Lemma 14 we obtain:
T
T
Σ
Cr Σ
L Ac1/ +
ΣΣ
(r:( aas*
1=1
1=1
1=1 [m[m
L L'm
L
X
ATT
which can be rewritten
V (gi) a,]+
t=1 mm/m]
L X AT +
L'm
> Cn /L1/1+1) Σ Cn, de)).
p
p
Thus, we employ Lemma with Lemma aannd Lemma to obtain:
1
- (gx) ass+ so
(1
Limm X V |T| + Lim
iglm
p
from which we obtain the final bound:
VT max mEmm]
V (g:) as}*
V (g:) - -ad*
[= ic(m)
T
(g:())) - -as*
p
[E(m)
+''m)
with probability at least O(8), by Union Bound. This concludes the proof.
25

---

Published as a conference paper at ICLR 2025
D TECHNICAL LEMMAS
D.1 POLICY OPTIMIZATION WITH DILATED BONUSES
In this section, we present the regret bound attained by PO-DB.
Lemma 12 (uo et al. (2021)). For any sequence of losses le such that le E [0, 10.11xxal and any valid occupancy measure E 11, PO-PPO-DD--0 DB attains:
Σ V*(())
with probability at least 0(8).
D.2 TRANSITION ESTIMATIONS
In the following section, we show how the estimated state action visit TP ne,Pe (-) concentrates to the true one p())
To do so, we first provide some discussion on the transitions confidence set.
D.2.1 CONFIDENCE SET
We introduce confidence sets for the transition function CMDP, by exploiting suitable concen- tration bounds for estimated transition probabilities. By letting Mz(2, a, x²) be the total number of episodes up to E [T] in which the state-action pair (z, a) E X A is visited and the en- state x' E X, define the estimated transition probability at t for the triplet (z, a, 2') as Pe (x' | xx, ax = M,(2,,.)) Then, the confidence set at E [T] is (IM(1.)))
vironment evolves to the
P. ((x==)EXXxXX Piraa where:
Peaa P:
(a'1z, (x,a) s0()),
with ((xx,, a, equal to:
P [x'1x, a) In T|X||a|
14In TIXII11
2 max {1, Ne(2, a) 13 3 max (1, Ne(1, a) - 13
for some confidence parameter 5 E 10,
The next lemma establishes P. is a proper confidence set.
Lemma 13 (Jin et al. (2020). Given a confidence parameter ö (0, 1), with probability at least - 48, it holds that the transition function P belongs to for all E [T].
D.2.2 CONCENTRATION RESULTS
Given the confidence set of the transition, it is possible to derive the following lemma.
Lemma 14 (Lemma 4,Jin et al. (2020). ) With probubility at least transition functions [Pe] such that PF E Pt, we have, for all
68, for any collection of
T
(LXI /
/IATII
TIXIIA
Σ
Σ DEX.aEA
PP, p(,,))))) So
|
As final remark, we underline that the empirical transition function Pj belongs to Pi by construction. Thus, the aforementioned lemma immidiately holds for P..
26


Reviews:
[{"review_id": "HXVlSfmUEp", "reviewer": "Reviewer_v2RE", "summary": "This paper studies efficient online policy optimization in \"*loop-free*\" constrained MDPs (CMDPs) that slightly generalizes finite-horizon episodic CMDPs, where by \"efficient\" it refers to avoiding any optimization over the space of occupancy measures. In the *bandit-feedback* setting, it proposes $\\texttt{CPD-PO}$, a primal-dual policy optimization algorithm built upon $\\texttt{PO-DB}$ that achieves $\\tilde{\\mathcal{O}}(\\sqrt{T})$ *strong* regret/violation bounds.", "questions": "Since loop-free MDPs are only a slight generalization of episodic MDPs, the dependency on $H$ also matters. Is $\\tilde{\\mathcal{O}}(L^5)$ the optimal dependency we can expect here (where $L$ is the horizon length)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper studies a known open problem in literature that is of theoretical interest. The idea to consider *strong* versions of regret and constraint violation is reasonable and well justified.\n2. The proof is checked to be correct, and the results do advance the theoretical understanding of policy optimization in CMDPs to a certain level.\n3. I like Section 5.2 that compares the proposed algorithm against known algorithms.", "weaknesses": "1. This paper only deals with finite-horizon episodic MDPs with *bandit feedback*, which is a more restrictive setting than Efroni et al. (2020) and Müller et al. (2024). It seems a little unfair to directly compare against those algorithms that do not require bandit feedback.\n2. The algorithmic contribution is limited since $\\texttt{CPD-PO}$ largely builds upon $\\texttt{PO-DB}$, only adding a simple binary dual update scheme.\n3. Despite the theory-oriented approach of this paper, it is still helpful to include at least some simulation results to illustrate the applicability of the proposed algorithm.\n4. The paper does not discuss about its limitations and future directions.\n    * For example, the algorithm seems intractable since it requires the exact value of $\\rho$, which is generally unavailable in practice. It would be much better if it can work with only an upper/lower bound of $\\rho$, which does not seem to be the case here.\n5. Suggestions on writing:\n    * Avoid squeezing key formulations (i.e., the *loop-free* MDP setting) into the footnote, even given the page limit.\n    * Clearly convey your message and ideas in the explanatory paragraphs following any mathematical results. For example, the paragraphs following Lemma 3 can be improved (What's the \"aforementioned parameters\"? Why does eq. (2) hold?). \n    * The constants in Lemma 1 & 2 seem inconsistent from those in Lemma 6, up to a numerical factor.\n6. Minor typesetting issues:\n    * There are a few typos in the paper: $K$ should be $L$ in line 5 of Algorithm 2; missing $i$ in $i \\in [m]$ in line 904; etc.\n    * I would personally avoid using $\\verb|\\nicefrac|$ or anything similar to it because it makes fractions hard to read, esp. when you have something like $A+B+C / D+E+F$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xZP9z6sCt3", "reviewer": "Reviewer_sekc", "summary": "The paper studies an online learning problem in constrained MDPs. The authors propose a new constrained online learning algorithm that leverages an existing unconstrained policy optimization oracle. The authors prove that this method has the optimal regret and constrained violation bounds in a strong sense. This improves the state of the art bound of online learning in constrained MDPs.", "questions": "- What is the role of the probability distributions in line 129 in algorithm? \n\n- How large the margin $\\rho$ is? What is the practical implication when it is infinitely small?\n\n- Is it efficient to run the adversarial policy optimization oracle? \n\n- Can the authors point out the new analysis that avoids the oscillation issue in typical primal-dual methods or compare their key analysis ideas?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- It is crucial to characterize stronger regret and constraint violation in online constrained MDPs since the transitional average performance metrics may obscure policy cancellation that is not permitted in safe policy learning. \n\n- The authors provide an optimal regret and constraint violation bound by only considering the non-negative terms. This improves the previous suboptimal bound in the online constrained learning setting. \n\n- The authors propose a new primal-dual online learning algorithm, which is different from the previous work that studies the strong regret and constraint violation. Rather than using regularization, the authors introduce several changes to the standard primal-dual methods: (1) binary dual update; (2) synthetic loss for policy optimization; (3) optimize policy through an existing adversarial policy optimization oracle.", "weaknesses": "- The authors focus on the basic tabular case of constrained MDPs. This method needs further generalization to extend beyond the tabular case.\n\n- It would be helpful if the authors could clarify the motivation behind the techniques used in the proposed algorithm. Notably, the standard primal-dual policy optimization suffers the oscillation issues, potentially causing linear strong regret and constraint violation.  \n\n- The proposed algorithm employs an existing adversarial policy optimization oracle to update the policy. The policy optimization oracle is designed in the adversarial setting, while the constrained MDP problem assumes stochastic rewards, costs, and fixed transitions. It would be helpful if the authors could explain the rationale behind this choice. \n\n- The adversarial policy optimization oracle minimizes the average type regret. It would be helpful if the extra technique to obtain a tighter regret bound can be highlighted.\n\n- To illustrate the practical utility and verify the algorithm's performance, it would be helpful if the authors provided experimental results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bajY1Th6tv", "reviewer": "Reviewer_fbBG", "summary": "This paper studies online learning in constrained MDPs with strong regret and strong violation, where the negative terms are not allowed to compensate for positive ones. For this problem, this paper’s algorithm uses a primal-dual approach with UCB-like updates on the dual variables. The method achieves optimal $O(\\sqrt{T})$ strong regret/violation, which improves the $O(T^{0.93})$ bound in the state-of-the-art works.", "questions": "Please see the weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "+ The concept of strong constraint violation is more relevant for safe-critical applications. It is also more challenging and technical than the conventional violation.\n\n+ The paper proposed a primal-dual algorithm with an interesting dual design. The theoretical performance on regret and violation is also provided.", "weaknesses": "- The paper missed a few important related references (e.g., [1] and [2]), where the strong violation has been investigated and better results than this paper have been established. In [1], the OptPess-LP algorithm can satisfy the constraints instantaneously, which seems better than $O(\\sqrt{T})$ strong violation.  In [2], the paper proposed a model-free method to achieve $O(\\sqrt{T})$ strong violation. It would be better to discuss these papers in detail and highlight the differences. \n\n- The algorithm requires Slater's condition and the knowledge of Slater's constant $\\rho$, which is usually not practical in most critical applications. Besides, the regret is in the order of $O(1/\\rho),$ it could be problematic when $\\rho$ is close to zero. \n\n- I understand it is a theory paper; however, including numerical experiments to validate the proposed algorithm would be beneficial. For example, the baselines could be Efroni et al. (2020), [1] and [2]. \n\n[1] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained MDPs. NeurIPS 2021.\n\n[2] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Towards Achieving Sub-linear Regret and Hard Constraint Violation in\nModel-free RL. AISTATS 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Y2FIsyj58", "reviewer": "Reviewer_QEvP", "summary": "This paper studies learning constrained tabular MDPs with strong regret and violation guarantees. Prior works in this setting are either computationally inefficient or highly suboptimal. This work provides the first computationally efficient policy optimization algorithm with optimal $\\sqrt{T}$ regret. The authors achieve this by leveraging the advance of adversarial MDPs for the primal update and an optimistic estimation for the dual update.", "questions": "1. Could the authors provide more technical reasons why $\\rho$ is required in this paper? Does this factor also appear in previous papers?\n2. Is there any regret lower bound in this setting that is related to the number of constraints $m$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem studied in this paper is well-motivated and the strong regret/violation metric is reasonable.\n2. The author successfully improves the regret bound in this setting from $T^{0.93}$ to the optimal $\\sqrt{T}$ for computationally efficient algorithms. This is a huge improvement.\n3. The writings are clear and discussion about previous works are sufficient.", "weaknesses": "1. This paper's algorithm and regret bound rely on a problem-dependent factor $\\rho$, which could be small and lead to worse regret.\n2. This paper does not have an empirical comparison. Although this is typically not necessary for a theoretical paper, simulation results like Muller et al. [2024] could be helpful.\n3. A conclusion and discussion section is lacking.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)