Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation
Authors: Toshinori Kitamura
Arnob Ghosh
Tadashi Kozuno
Wataru Kumagai
Kazumi Kasaura
Kenta Hoshino
Yohei Hosoe
Yutaka Matsuo
Venue: NeurIPS 2025 spotlight ()
Keywords: Reinforcement Learning Theory
Primary area: theory
TL;DR: We propose the first provably efficient and episode-wise safe RL algorithm for linear constrained MDPs.

Abstract: We study the reinforcement learning (RL) problem in a constrained Markov decision process (CMDP), where an agent explores the environment to maximize the expected cumulative reward while satisfying a single constraint on the expected total utility value in every episode. While this problem is well understood in the tabular setting, theoretical results for function approximation remain scarce. This paper closes the gap by proposing an RL algorithm for linear CMDPs that achieves $\widetilde{\mathcal{O}}(\sqrt{K})$ regret with an episode-wise zero-violation guarantee. Furthermore, our method is computationally efficient, scaling polynomially with problem-dependent parameters while remaining independent of the state space size. Our results significantly improve upon recent linear CMDP algorithms, which either violate the constraint or incur exponential computational costs.

Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation
Toshinori Kitamura
Arnob Ghosh
The University of Tokyo
New Jersey Institute of Technology New Jersey, USA
Tokyo, Japan
toshinori-keweblade t.w.oyy...... ac.
Tadashi Kozuno
Wataru Kumagai
Kazumi Kasaura OMRON SINIC X Tokyo, Japan
OMRON SINIC X. NexaScience
OMRON SINIC X, NexaScience Tokyo, Japan
Tokyo, Japan
Kenta Hoshino"
Yohei Hosoe
Yutaka Matsuo
Kyoto University Kyoto, Japan
Kyoto University
The University of Tokyo Tokyo, Japan
Kyoto, Japan
Abstract
We study the reinforcement learning (RL) problem in a constrained Markov deci- sion process (CMDP), where an agent explores the environment maximize the expected cumulative reward while satisfying a single constraint on the expected total utility value in every episode. While this problem well understood in the tabular setting, theoretical results for function approximation remain scarce. This paper closes the gap by proposing an RL algorithm for linear CMDPs that achieves ((VK) regret with an episode-wise zero-violation guarantee. Furthermore, our method is computationally efficient, scaling polynomially with problem-dependent parameters while remaining independent of the state space size. Our results sig- nificantly improve upon recent linear CMDP algorithms, which either violate the constraint or incur exponential computational costs.
Introduction
Safe decision-making is essential in real-world applications such plant control and finance [19]. Constrained Markov decision process (CMDP) is a mathematical framework for developing decision- making algorithms with formal safety guarantees [2]. This paper studies the reinforcement learning (RL) problem in finite-horizon CMDPs, where an agent explores the environment to maximize the expected cumulative rewards while satisfying single constraint on the expected total utility value.
Safe exploration has been established in the tabular CMDP settings. Several works [27, 8, 47] achieve episode-wise zero-violation RL with Ö(VK) regret for K number of episodes, ensuring constraint satisfaction in every episode. Their approach consists two phases: deploying a known strictly safe policy -= and then updating policies via linear programs (LPs), which optimizes an optimistic objective while satisfying a pessimistic constraint. Deploying rf is necessary to ensure feasible solutions for the LPs once enough environmental information is collected.
"Current affiliation: Institute of Science Tokyo, Tokyo, Japan, and DENSO IT Laboratory, Tokyo, Japan.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Representative CMDP results with --dependent regrets. See Section 3 for CMDP notations.
Paper
Epi.-Wise Sale?
Comp. Efficient?
Regret
Tabular
Yu et al. [47]
Yes
| dependent
O O VIS
H))
Ghosh et al. [18]
No
No
O(V
Linear
Roknilamouki et al. [36]
Instantaneous
Yes
OPSE-LCMDP (Ours)
Yes
Yes
Bandit lower bound [32]
Yes
N/A
12(max VIAIK,
+ Thee regnets of [47] ours include additional Ö(c 3) constant. We omii them from due to space limitations. [36, 32,
avoid the constant by assurning access to safe action vector. but they are limited to instanianeous constraints (see Section 2.1). Including ours, existing safe algorithms [27. 8, 4., 36, 3, 32, 22] incur Ö(g /V) regret. Whether this can be improved to Ö(v K) remains open.
While safe exploration is well-established in tabular CMDPs, extending it to large-scale CMDPs remains a major challenge. LP-based methods are impractical at scale due to their state-dependent computational cost.? 2 As result, even in linear CMDPs, where value functions have linear structure, episode-wise safe RL. has not been achieved. The state-of-the-art linear CMDP algorithm [18), which achieves the ((VK) violation regret, è incurs an exponential computational cost of K where H the horizon. Several studies achieve safe RL under instantaneous constraints [4, 36).* special sub- class of the episode-wise wise safety that can be overly conservative (e.g.. in drone control, temporary high energy consumption is tolerable, but full battery depletion is not). Table summarizes representative algorithms, with additional literature in Appendix B. In short, a fundamental open question remains:
Can we develop a computationally efficient linear CMDP algorithu with sublinear regret and zero episode-wise constraint violation?
Contributions. We propose Optimistic- Aptimistii-Pessimistiic Softmax Exploration for Linear CMDP (OPSE-
LCMDP), the first algorithm for linear CMDPs that achieves D(VK) and episode-wise safety. Our approach builds on the pppimisti--pessmmsste exploration framework with two key innovations for large-scale state-space problems: (i) a new deployment rule for n= and (ii) a computationally efficient method to implement optimism for the objective and pessimism for the constraint within the softmax policy framework [16, 18).
Section 2 first analyzes the linear constrained bandit problem as a "warm-up" for linear CMDPs (H = with an expected instantaneous constraint), highlighting the key role of the na deployment rule in avoiding linear regret. Previous instantaneous constraint literature limits na deployments by representing the safe action as a vector a E Rdd [32, 33, 22, 3, 4]. However, extending this approach to episode-wise safety is non-trivial, as the constraint is imposed on policies rather than actions, and policies may be nonlinear functions (c.g., softmax mapping from value functions) rather than single vectors. We overcome this challenge by showing that if T= is deployed only when the agent is less confident in T safety, the number of deployments is logarithmically bounded (Theorem 1).
Section 3 then extends the bandit result to RL in CMDPs. To enable pptimistic-pessimisst exploration in linear CMDPs, OPSE-LCMDP employs the composite softmax policy (Definition 3), which adjusts optimism and pessimism by controlling a variable X. OPSE-LCMDP efficiently searches for the best À through bisection search, achieving a polynomial computational cost in problem parameters, independent of state-space cardinality (Remark 2). Overall, our techniques-the novel .- deployment rule and softmax- based optimistic-pessimisti exploration -chieve the first episode-wise safe RL with sublinear regret and computational efficiency in linear CMDPs.
Mathematical notations. The set of probability distributions over a set S is denoted by (S). For integers a < b, let [a. bl = {a.....b) b). and [a. b] = @ if b. For x E RN its n-th element is Xn or x(n). The clipping function cxip(x, a, b} returns x' with x² = min ( (max (x,, a) b} for each i. We define 0 = O0....,)'' and 1 == (I,..., .).,.)) T)T, with dimensions inferred from the context. For positive definite matrix A E Idd and x E Rd, we denote |x|| A vxT Ax. For positive sequences } and {b..} with n = 1,2,..., we write a, = (b.)) if there exist C > 0 and N e N
"While some works (e.g.. 30) proposed LP methods for unconstrained linear MDPs, they remain unsuitable for exploration setting still incur state-dependent computational costs (see Appendix B). 'Violation regret denotes the total amount of constraint violation during exploration.
4 Inst. constraint requires un (+ (k)) 2 b Vh, & E [1, H] x [1, K] (see Section 3 for notations).
An algorithm comp. efficient if its cost is polynomial with problem parameters, excluding the state space.

---

such that an I Cb2 for all n 2 N, and on = (bb,)) for the reverse inequality. We use (-)) and i2(-) to further hide the polylogarithiie factors. Finally, for x E R2 we denote its softmax distribution as (oftMax(x) E ([L, dI) with its i-th component Maxx = exp(x,)/(Ex exp(xx)
2 Warm Up: Safe Exploration in Linear Constrained Bandit
To better illustrate the core ideas of our CMDP algorithm, this section introduces contextual linear bandit variant based on Pacchiano et al. [32]. All the proofs this section are provided in Appendix D.
Let A C Rd be the action space, compact generality, we assume ||a||2 2/2 < for any E A. At each round k; the agent selects policy x(()
of bounded d-dimensional vectors. Without loss of
(AA, samples an action (*) ~ (*), and observes the reward (A) = a,aa()) + +,, and utility
(k) Here, 0,, Au TRd are vectors unknown to the agent such that ||0,12,, ||0=/la S B. and of (k) are T-sub-GGaussia random noises. For any policy a and 9 E {r; u), let y == Ra-= (0 a)]. We consider constraint such that the expected utility must be above the threshold b E IR. Formally, let IT == { M² 2 b) denote the set of safe policies. The agent's goal is to achieve sublinear regret while satisfying the expected instantaneous constraints defined as follows:
(R)) = 0 a (k) +ea
Regret (gr (K) = Σ k= P.r (w) (K) such that xr (*) II Wk K],
(1)
where nt' E arg gf Tn- A sublinear regret exploration is efficient, as its averaged reward approaches the optimal value, i.c., lim (*) + rg.. Finally, we assume access to a strictly safe policy in I1 as deploying arbitrary policies without this assumption risks violating constraints
Assumption (Safe policy). We have access to n- IIIs and & > O such that Uggt b 5
2.1 Technical Challenge:
with a Safe Policy
The key to efficient and safe exploration is the ceiimistic-pessimisit exploration, which constructs (k) an optimistic reward Fa 2 T= and a pessimistic utility uz < Uz, and then computes a policy by:
(k)
7x (k) such that
(k) U 2 b
max
Here, =! and ut are designed to quickly approach Tn and un as data accumulates for efficient exploration [1]. However, although Equation (2) can have feasible solutions when 2 Ug the pessimistic constraint may not have any feasible solution in the early stages of exploration.
To ensure that (2) always has solution, common bandit approach assumes access to a safe action as A such that 0 a 2 b + ç. and then ensures the feasibility of (2) by leveraging the vector representation of af E Rd. For example, [32, 33, 3] designed wh using the orthogonal direction (a=t) = a- at /|| af l1 while [22] assume af = 0 E A with a negative constraint threshold b < O. Both approaches ensure that policy playing a with probability is always feasible in (2).
However, extending this safe action technique to episode-wise safe RL is non-trivial. as the episode- wise constraint is imposed on policies rather than actions, and policies in lincar CMDPs may be nonlinea functions (e.g., softmax mappings from value functions) rather than single vectors. To ad- dress this challenge, first develop safe bandit algorithm without relying on safe action techniques.
2.2 Algorithm and Analysis
We summarize the proposed Optimistic- Optimistic-Pessimistie Linear Bandit with Safe Policy (OPLB-SP)
in Algorithm 1, which follows the standard linear bandit framework (see Abbasi-Yadkori Yadkori al.
[1]). Throughout this section, we analyze Algorithm 1 under the parameters listed in its Input line. (()() and 0.. (k)
Let 0 (k)
= (A) kk1 a (()( denote the regularized least equatesquares estimates of 0, and On. respectively, where A (k) pl Σk=1 (0) (a))T. Let
= (A
((k) T
= Ea T and us Eava 0 be the estimated reward and utility functions.
'The knowledge of is for simplicity. If fuuknoww,, can estimate by deploying n" with little overhead.
3

---

Algorithm 1: Optimistic-Pessimisiee Linear Bandit with Safe Policy
Input: Regression coefficient 1, bonus scalers Cu = B + Rv In 4K6-1 and C C₂(1 + ++-2B(--) safe policy x" and iteration length K E
for .....: Kdd do
Let (n Fa and T be bonus, estimated reward and utility, respectively (see Section 2.2)
Cu
then (k) xzi
/+ Deploy лo it nt is unconfident */
else x (4) E arg max F + C. such that ur Cu. 2 b
Sample an action a (h) ~ x (k) and observe reward ((() and utility (*))
Using the bonus function 3 = Em- (A() 1, with the well-established elliptical confidence bound argument for linear bandits [1], the following confidence bounds hold:
Lemma (Confidence bounds). For any and ki with probability (w.p.) at least
Tx + 2
pik) C.. 2 Tr and Uz
U
(1)) CCu Un 2C,,9
Based on Lemma 1, Algorithm solves the following optimistie-pessimiiss (Opt-Pes) problem. The optimistic objective promotes efficient exploration, while the pessimism enforces the constraint satisfaction:
Opt-Pes (Line 4) (Aa) E arg max
(() + C,B such that (k) C., 2 b. (3)
This is convex optimization problem when the set AA satisfies certain structural assumptions, such as being discrete or ellipsoidal (see, e-g., Section 19.3 of Lattimore and Szepesvari [26]). To emphasize our approach to the technical challenge in Section 2.1, this section omits the computational details of (3) and focuses instead on the core technique for efficient exploration under episode-wis wise safety.
2.2.1 Zero- Violatiol and Logarithmic Number of क Deployments
Since (k) is either rf or the solution to Opt-Pes (if feasible), all deployed policies in Algorithm 1 satisfy the constraint with high probability due to the pessimistic constraint. However, as noted in Section 1, the pessimistic constraint may render Opt-Pes infeasible, requiring Line 4 to wait until the bonus k shrinks sufficiently. Yet, waiting too long overuses the suboptimal n" leading poor regret. Thus, exploration must keep the number of iterations where Equation (2) is infeasible bounded.
The core technique of Algorithm 1 lies in the nf deployment trigger based the confidence of *f Specifically, we solve the we correct the data by deploying œ (see Line 3). Under this trigger, the following Theorem 1 ensures that the number of nh deployments grows logarithmically with the itcration length K.
pessimistic optimization whenever g(t)
qaa S 2C.,' otherwise,
Definition of unconfident iterations). Let 2/ be the of iterations when Algorithm unconfi- dent in Th i.e., U == (k E [1, K]]
((k)
gas (/CC)) Let C = [1, K] 4 be its complement.
Theorem 1 (Logarithmic [ bound). It holds w.p. at least 1 5 that / s -(dC)g-2Im/ ln(KK-)))
The proof utilizes the well-known elliptical potential lemma [1]. Intuitively, it ensures that the confidence bounds shrink on average, thereby limiting the number of iterations where the algorithm remains unconfident in π& He et al. [21], Zhang et al. [50] employed similar technique in linear bandits to ensure the suboptimality of policies after sufficient iterations.
Moreover, combined with Lemma the following Lemma 2 ensures that, after logarithmic iterations, policies around of will become feasible solutions to Opt-Pes and Line
8-20_g(t 5 g-20,, and +2C,,
Lemma (Mixture policy feasibility). Consider c Let (k)
For any
[0, a (,), the mixture policy na (1 a) + ax" satisfies Un..
-0,,, 2 b.
(1)
Note that the mixture policy Ra is introduced only to ensure the feasibility of Opt-Pes; does not need to be computed in the algorithm.

---

Finally, Lemma and Lemma 2 directly imply the following zero-violation guarantee:
Algorithm satisfies x x(k) II for any k. Corollary (Zero-violation), W.p. at least
2.2.2 Regret Analysis
The remaining task is to ensure sublinear regret. By Theorem and Lemma 1, the regret is decomposed as:
Regret(K) s ( 3C, ERENd k 1 EmEuO (Tx- p(k) x(k)
C,.
Using the elliptical potential lemma [1]. we can bound I S Ō(C,VdK).
For the term @ when there is no constraint in Opt-Pes, the common strategy is bounding ② using
Ty- - .((k) 3 < 0, leveraging the optimism due to Lemma I with the maximality x (k) in Opt-Pes (see, e.g., Abbasi-Yadkori Yadkori et al. [1]. However, due to the pessimistic constraint in Opt-Pes, T may not solution to Opt-Pes, necessitating a modification to this approach.
Recall from Lemma that, for l uh, the mixture policy Ta( == (1 (x (k)) satisfies ((k) 2C ((N) 2 b. For this ( the following optimism with respect to x holds:
UF (0))
Lemma (T.))) optimism). For any k E Euu, holds Tx xx00)) + (2BCa5- (K) 2 Tat
Using Lemmas and with C. Cu 2BE have
SS EkEWD Pr Pr + C2
(k) x(6)
C,
S
(4)
where the second inequality holds since Tm is feasible solution to Opt-Pes and (() is its maximizer. This optimism via mixture policy technique is adapted from tabular CMDPs [27, 8] to the linear bandit setup. By combining all the results, Algorithm archives the following guarantees:
Theorem 2. OPOLB-S is run with the parameters listed in its Input line, w.p. least 1 5,
π E II for any E [1, and Regret () S Ō(dBCB5 + V,VdK).
When R= L, the regret bound simplifies to Ö(d 2 2+ <
In summary, OPLB-SP relies three components: (i) uptimistic-pessimistie updates (Opt-Pes), (ii) a logarithmic number of n deployments (Theorem 1), and (iii) compensation for the pessimism (Lemma 3). Building on these components, the next section develops a linear CMDP algorithm.
Safe Reinforcement Learning in Linear Constrained MDP
A finite-horizon CMDP is defined tuple (S,A, P, u, b, 81), where S is the finite but potentially exponentially large state space, AA is the finite action space ((AA) = A)," 7 И e N is the episode horizon, E [0, H] the constrained threshold, and sı is the fixed initial state. The reward and utility functions un (s, a) when taking action a at state s in step h. Finally, (()) [1, H] x S [0. 1] denotes the transition kernel, where (s
[1, HI] x S x A + [0, 1] specify the reward (s, a) and constraint utility
a)) denotes the state transition probability to new state s' from a state when taking an action step h. With slight abuse of notation, for functions
V S + R and Ph, we write (PrV (2,)) a) Eyes Pn xx,a).
Policy and (regularized) value functions. A policy is defined as n. (-1-)) [1, H] xxxxxx-- 1), where ny (a 8) gives the probability of taking an action a at state 8 in step h. The set of all the policies denoted as II. With an abuse of notation, for any policy æ and Q S x A R. let Ti be an operator such that (s)))(s) = Enss F (a $ (s a). For a policy ग, transition kernel P.
"While Section 2 permits infinite actions, we here restrict to the finite case. Even then, episode-wise wise safe exploration in linear CMDP non- convtrivial, and infinite actions would further complicate the regret analysis.
5

---

reward function g: [1. H] x S x A + R, and entropy coefficient k 2 0, let QPA :S x A + and V [k] S ++ R denote the entropy-rrgullarized value functions at step h satisfying:
Q [+] gh. + (P. (t,, [m]), Vr [<s = Te (Q7: - K In m and V 1 -.
For 0, we omit K, e.g.. P.A = p.A [0]. We denote hig == h(1 + In A) for h [1, H]]
For h [1, HI let 1., E A(S x A) denote the occupancy measure of in P at step h such that
(8,a) (s = s, an a P) V (h, E [1, x 8 x A,
(5)
where the expectation is taken over all possible trajectories, in which as ~ Tn(. 8b) and 8h+1 ~ Pr[. 8h an). With slight abuse of notation, we write w),, = EeEA w (s,
Learning Setup. An agent interacts with the CMDP for K episodes using policies x(1) n (K) E
II. Each episode k starts from 51. At step h in episode k; the agent observes a state 8/= selects
(k)
an action (4) ~ (1) s/ ). and transitions to $b+1 ~ Ph(-1 (8) (k)). The algorithm lacks
knowledge of the transition kernel P. while r and u are known for simplicity. Extending our setting
to unknown stochastic reward and utility is straightforward (see, e.g., Efroni et al. [13)).
To handle potentially large state space, we consider the following linear MDP assumption:
Assumption 2 (Linear MDP). We have a known feature map Φ S x A - Rd satisfying: there exist unknown d (signed) measures 24 = (4),..... ........ (4)) E R such that Pa s.a) u (s") (bs,, a). and known vectors 0% 0% E Rd such that rn (n a) = (0%) (bs, a) and un uz a) = ((s.a) We assume sups,allo(s (1 a)llz I and ||V pull2 S vd for any V E RS such that I $1. 1.
(0%)
Let x* E arg max V be the optimal policy, where II = { |
P11 (31) 2 b} is the
set of safe policies. The goal is to achieve sublinear regret under episode-wise constraints:
Regret = Ek= (s1) vol" "(81) o(K) such that (1)) E I
vk E [K] (6)
Finally, we assume the strictly safe policy similar to Section 2.
Assumption 3 (Safe policy). We have access to nf E III and & > 0 such that V (s1) - b 626
3.1 Technical Challenge: Optimistic-Pessimiss Optimization in Linear CMDP
Our linear CMDP algorithm builds on OPLB-SP in Section 2: deploying an aptimistic-pessimeee policy when confident in πF; otherwise, it uses πー We will logarithmically bound the number of nt deployments, similar to Theorem 1, and ensure optimism through a linear mixture of policies, as in Lemma 2. However, computing an similar to Opt-Pes, presents a non-trivial challenge. This section outlines the difficulties.
policy in the linear CMDP setting,
Following standard linear MDP algorithm frameworks (e.g., Jin et al. [23], Lykouris et al. (R) [I ((())) be the bonus, where A
(28]). for each h k, let Ph (k)
(a()))- , h (0s)) ( and p > 0. For any V : S + R, let p(K) be the next-step
(s,a)
eI + Ei=1 ((s) (i) (9)
value estimation defined as: (Pil) () a) = ((x, a)T (A - o(sh a (()))) We construct the following optimistic and pessimistic value functions for reward and utility, respectively:
Definition (Clipped value functions). Let C,,, C.,, C₁, By > O. For each ks, h, n, and is 2 O, define 5.t (N), ((R), t 27A), SS A + R and V (x), (k), ((R)A S + R such that:
The [x] == rh clip(C. (k) + P( V
(1),4+1 [x]. 0, H hr),
Vi [k] == Th Tn(Qis klnm)))
Q(),, B1BB + MippCr,8 (k) + P
p(k) valt
(k), 0, B2 -h)]
Vist (R).A -K)(K)
n.t
(K), un + clipt C,.p (k) + (()) yu.u ++)
0, H H-h), and
VTL ThQTT (K),A
We set V..
(1)H411(k) [k]] = V.
(k),H+1 = V (K)
O. For k = 0. omit K. e.g., T7ii, == -Qi5,

---

Algorithm 2: Optimistic-Pessimitti Softmax Exploration for Linear CMDP
Input: Regr. coeff. 1. bonus scalers C, - O(dH), Cv = O(dH), C - H(
B = δ {d ") entropy coeff. & = 1 K K--.5). search length T' = OHH).
A-threshold Cs = ((dH* safe policy n² and iter. length K E N
l..... K
Let Vina be value function (Definition 2) and ((). be softmax policy (Definition 3)
x* n² trigger is 1mpl implictlyy tied to =" confidence (hemma 5)
if - (00,)00
(16),1 ( < b then Set (1) == nd
else 1,x10),0, " (s1) 2 b then Set ( x (4),0
_(k),a
clse /+ Do bisection-searcae
to find safe n ((0.) with small X
Set (4.11 = 0 and (k.1) = Cx. Let ((h,)) = (2 + 2/2
for l I,..., T do
if v (K),1 "((i) 2 b then ((,(1)) = 2000) and X (B(t)) = ((4A
else (0.411 = (000) and (k++1) = x
Set (A) = (2).
10
Sample trajectory (0 (8)
(K) (K) ,
8 O0 by deploying ((a)
We will utilize (R),, and V (k).a h to compensate for the pessimism, similar the bandit proof in u. (4). Entropy regularization in [k) is for the later analysis. The clipping operators are essential to avoid the propagation of unreasonable value estimates [48].
Using these value functions, one might consider extending Opt-Pes to linear CMDPs by solving:
max Vil (8). (51)
Vist (k),, (1),1(1)) such that (()), ($1) 2 b.
However, solving this (7) is challenging due to (i) the large state space in the linear CMDP setting F..
((8) >> 1) and (ii) the clipping operators in ((k), L(k), and (R),N)
In tabular CMDPs with small (S), Liu et al. [27] and Bura et al. [8] used linear programming (LP) to solve similar the computational cost of LP scales with |8], making impractical for linear CMDPs.
optimization problems, achieving zero violation. However,
Another option is the Lagrangian method, which reformulates the constrained optimization as (16.1 + (k), + A(V (s1) 6). When min-max optimization: minA>o max TT
the value functions are exact, i.e., Vil) A V (A), + [(k),, V B,g00) +Au this min-max is (R),
equivalent to (7), and the inner maximization reduces to a standard policy optimization [2]. Both favorable properties arise due to the linearity of the value function in the occupancy measure (see, e.g., Paternain et al. [34]). However, due clipping, the value functions in Definition 2 may not be representable via occupancy measures, making the Lagrangian approach inapplicable.
To address this large-scale optimization challenge, instead of directly solving (7), we realize optimism and pessimism through a novel adaptation of the recent softmax policy technique for linear CMDPs [18, 16], combined with the xf deployment technique from Section 2.
3.2 Algorithm and Analysis
We summarize the proposed OPSE-LCMDP in Algorithm and analyze it under the parameters in its Input line. All formal theorems and proofs in this section are in Appendix E. A key component of our algorithm is the composite softmax policy, which balances optimism and pessimism via À >
"Icreasiin Cr and thi-thrrshold could offer similar compensation, but separated values simplify analysis.

---

Definition 3 (Composite softmax policy). For X 02 x > 0, let v (4),A II be policy such that ( (1), (s,.)+ ( (N]((s,)) (a 1 ((s,))
(A),a SoftMax Thi
π (k).A can be computed iteratively in backward manner for = H,..., 1. For this x (8).2, using the Lipschitz continuity of SoftMax(.) (see Ghosh et al. [16]), the following confidence bounds hold:
Lemma 4 (Confidence bounds). For any (k, A E [x),
{I(M), Th wip. at least 1 8,
PAA (6), S Vz.r+2Crg(()
Ven V2,B,
S VV
(k), s Vp (20
P/ Vi 20
V. S P,b
Using Lemma 4, analogous to Section 2.2.1, we next establish the zero-violation guarantee.
3.2.1 Zero- Violation and Logarithmic Number of x Deployments
In the softmax policy (Definition 3), À balances optimism and pessimism: a small À promotes exploration, while a large prioritizes constraint satisfaction. Building on this, Algorithm conducts bisection search to find the smallest feasible À while ensuring the pessimistic constraint holds (Line to Line 10). If a large À = C2 fails to satisfy the constraint, the algorithm assumes no feasible pessimistic policy exists and deploys nh (Line 3). Since the softmax policy is only deployed for À satisfying (k),1 (s1) 2 b, Lemma 4 implies the following zero-violation guarantees:
Corollary 2 (Zero-violatin violatiio... W.p. at least 6, Algorithm 2 satisfies x (R) E II for any k.
Next, we bound the number of nh deployments to achieve sublinear regret. To this end, similar to the bandit warm-up (Section 2), we relate n- deployment to π uncertainty level and logarithmically bound the number of uncertain iterations. The following Lemma 5 ensures that, if Algorithm is confident хΩ and runs with appropriate C'x and ii, then æa is not deployed.
Definition (== unconfident iterations). Let 2/ be the iterations when Algorithm is unconfident in .908)
sf i.e., (A: [1, K]
(a1) &..). Let = [1, K] \ 24 be complement.
PM
Lemma 5 (Implicit Th deployment trigger). When C₃ 2 (H and K S 32H then
holds that V CM, (s1) ) 2 b for all k c
w.p. at least
(k).1
Essentially, the proof of Lemma 5 relies the following monotonic property of the value function for the softmax policy: if the value estimation is exact, increasing À monotonically improves safety. Lemma 6 (Softmax value monotonicity). For X O. let x be softmax policy such that n Then, V (s1) is monotonically increusing in X. a) Soft (07% + XQTH
While the true value function enjoys this monotonicity, the estimated value (r "((1) may not,
as F(()V can take negative values even when V is positive. This complicates the proof of Lemma 5. To address this, we leverage Lemma 4, which sandwiches the estimated values by some true values. We prove Lemma by showing that, for sufficiently large Cx. any sandwiched value satisfies the constraint under pessimism, implying that the estimated value also satisfies it. This novel result enables bisection search adjust X, making OPSE-LCMDP more computationally efficient than Ghosh et al. [18]. The detailed proofs of Lemmas 5 and 6 are provided in Appendix E.4.1.
Finally, the following theorem ensures that the number of श deployment scales logarithmic to K, as in Theorem 1. The proof follows from extending the bandit's proof of Theorem to CMDPs.
Theorem 3 (Logarithmic [ bound). It holds w.p. at least 8 that [4| <
3.2.2 Regret Analysis
The remaining task is to ensure sublinear regret. By Theorem and Lemma 4, the regret is decomposed as:
Regret K) s 5
HH
Σ
va(l),
(81)
+ Σ (A)) (00.1110
*KKH In A.
heue
keut

---

where the last term arises from the entropy regularization (VP.1 (s1)[k) -VPi I KH In A). Using the elliptical potential lemma for linear MDPs [23], we obtain ① S VVK).
We now bound 2) Note that for any k E L4c due to Lemma 5, x(() is the softmax policy by Line 10. To bound 2 following similar approach to Lemma 3 in the bandit, replace x² with mixture policy that satisfies the pessimistic constraint. To this end, we utilize the following lemmas.
Definition 5 (Mixture policy). For [0,1], let x" be mixture policy such that, for any h, WP,A- = (1 - a' + + Such a x is ensured to exists for any a E [0, 17].
Lemma 7 (Safe and optimistic mixture policy). Let (1
&
Bf 1C then
(+2V7) $+2V7222cs0 20ush) (01)
for any E uc, holds (i) Vpa V 20-20,0(k) (81) 2 b and (ii) Vpa ,+B,306
(81) 2 Vp (81).
We note that the mixture policy x is introduced only for the regret analysis; it is not required in the (k)
actual algorithm. Since (R.77 is chosen to satisfy L(k),1 " (s1) < and S Vi1
(00)
(81)
holds by Lemma 7,
2 ΣxEVo (ver -B,0(0)
(81) + Vei "ski((s)) + 2 (a.) Voa . 20-20.000) D(A) (51)
- -V (81) - (4) (w)(s) - x 14: yott) (81))
+ C2 Exere (K (s1) - (()i1
*KEEN (6),1 (s1)
((11)
Using Lemma 4, similar to C, we have 4 S Ö (B, + +G)HVaK). The term (5 is controlled
Ō((,
by the bisection search width (A (R.T) - 1 ()) and the following sensitivity of V. (B).
(k),1 "(s1) to
Lemma 8. For any is and X E [0, Cx), we have 00)A (8),1
(s1)
((s1) S ()
(R).1
Ghosh et al. [18] also derived a similar exponential bound (see their Appendix C). Due to the update
rule of the bisection search, setting the search iteration to T = O(H) ensures that 5 < O(1)
For 3 using a modification of the so-called value-differenee lemma [40], we have
3 = EREEO Ver s (si) ( s² (81) - x (k:T) vol (k) 20,
(81),
(8)
where |2, [11 H
x S x A - TR are functions such that, for any h,
R== 18 (K) -a())
Quii + t
woch (4) lang (2)
+Nxx (4) lxx
(9,,, and f2= (el PA ( [x] +xtt.T) un (u.tR (M -ihh""""
(ir, (8) B,000 vall
Our use of the softmax policy with entropy regularization is crucial for bounding 3. Since
the analytical maximizer of the regularized optimization max EeEA (x)(((()) - - In (())
is given by (xxMaxxxxx())). it follows that f' is non-positive, implying P.P
I' ((1)) 0.
Additionally, applying Lemma 4, we derive f 2 - (k.T) 2 2C,,3()). which leads to X (l:T) (k) (20, (s1) S 0. By substituting these bounds into Equation (8), we obtain 3 S 0.
v .² (s(s)-
p.
P.I
By combining all the results, Algorithm 2 achieves the following guarantees:
Theorem 4. If OPSE-LCCM is run with the parameters listed in its Input line, w.p. at least 1 - 6,
x (())
II vk [1, and Regret(K) < V(H²V + (n) + H (11)
Notably, Theorem 4 is the first linear CMDP result achieving zero episode-wise constraint violations and sublinear regret. We conclude this section by discussing the regret bound quality and computational cost of OPSE-LCMDP.

---

Remark 1 (Can we do better?). Without the constraint- removing (ii) and (ii)) bound matches the O d3 K) regret of the fundamental LSVI-UCB algorithm [23]. The g-2 term in (ii)
is unavoidable [32]. The 5-1 dependence in (ii) remains unresolved, yet appears in all the existing safe RL literature [27, 8, 47, 36, 3, 32, 22]. These observations suggest that the bound is tight in in and K. As for d and H, the term (iii) introduces an extra dHf² factor over (i). Similar deterioration has been observed in tabular CMDPs [27, 42] and partially mitigated via Bernstein-type bonus analysis [47]. While improvement may be possible, it is unclear whether our v d H dependence is overly loose when compared with existing CMDP regret bounds (e.g.. dd H by Ghosh et al. [18]), since none of the existing results achieve episode-wise safe exploration. In general, regret or sample complexity bounds under different safety requirements are not directly comparable, even if the problem settings appear similar. For example, Vaswani et al. [42] shows that the sample complexity lower bound for tabular CMDPs exhibits worse dependence on the horizon under strict safe policy requirement than when small violations are allowed. Establishing formal regret lower bound for our setting would be necessary to assess the tightness of our result, but this is beyond the scope of the current paper.
Remark 2 (Computational cost). Algorithm 2 requires up to T value evaluations (Definition 2) and policy computation (Definition 3). Using the bisection search, we bound T = (H), reducing the computational cost per-iteration to Ö(H [value & policy comp.])- As this cost scales polynomially with A, H, and [28], OPSE-LCMDP runs in polynomial time- an improvement over recent Ghosh et al. [18], which achieves Ö( violation regret but incurs an exponential K" cost.
Conclusion
This paper proposed OPSE-LCMDP, the first RL. algorithm achieving both sublinear regret and episode-wise constraint satisfaction in linear CMDPs (Theorem 4). Our approach builds on optimistic- pessimistic exploration with two key innovations: (i) a novel deployment rule for π and (ii) a softmax-based approach for efficiently implementing optimistic-pessimitte policies in linear CMDPs.
Experiments. We numerically evaluate PPSE-LCMDP on several linear CMDP environments to support our theoretical results. We compare OPSE-LCMDP with the prior ofte-offtthe-at linear CMDP algorithm of Ghosh et al. [18] and the tabular algorithm called DOPE [8]. Across all environments, OPSE-LCMDP achieves sublinear regret with zero constraint violation, while Ghosh et al. [18] shows positive violation regret. These results empirically validate Theorem 4. While DOPE also achieves zero violation, its use is limited to the tabular settings where S is small. This highlights the computational tractability of our OPSE-LCMDP in large S, which supports Remark 2. All the results and details are deferred Appendix F.
Limitation and future work. OPSE-LCMDP achieves computational efficiency by the bisection search over x E [0, Cx). which works in the single-constraitt setting thanks to the monotonicity in Lemma 6. However, extending our method to the multi-constraint setting is non-trivial, as X becomes vector, requiring a vectorized version of the monotonicity lemma. Nonetheless, all theoretical results in Table 1 are also limited to single-constraint settings, meaning our work still advances the state of the art in safety. An efficient and safe algorithm for multi-constraint settings remains open for future work.
Another future direction is to extend the analysis to adversarial initial states 81. This extension is non- trivial, as our core techniques rely the fixed-state assumption. For example, we control the number y=a"5_g(* ,g((3)
of safe policy deployments by evaluating the bonus-return function PP1 (s1) (Definition 4), which explicitly depends on $1- The bound on the number of - deployments (Theorem 3) and the existence of optimistic pessimistic policies (Lemma 7) also depend on this initial state. Extending these anal- optimistic-pessimssiic yses to handle adversarial s would entail non-trivial technical challenges and left for future work.
Acknowledgments and Disclosure of Funding
This work is supported by JST Moonshot R&D Program Grant Number JPMJMS2236. AG acknowl- edges NJIT Start-up fund indexed number 172884.
10

---

References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved Algorithms for Linear Stochastic Bandits. In Advances in Neural Information Processing Systems, 2011.
[2] Eitan Altman, Constrained Markov Decision Processes, volume 7. CRC Press, 1999.
[3] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear Stochastic Bandits under Safety Constraints. In Advances in Neural Information Processing Systems, 2019.
[4] Sanae Amani, Christos Thrampoulidis, and Lin Yang. Safe Reinforcement Learning with Linear Function Approximation. In International Conference on Machine Learning, 2021.
[5] Joan Serrano Sebastian Curi, Andreas Krause, and Gergely Neu. Logistic Q-Learning In International conference artificial intelligence and statistics, 2021.
[6] Dimitri P Bertsekas. Nonlinear Programming. Journal of the Operational Research Society, 48 (3):334-334, 1997.
[7] Vivek S Borkar. Convex Analytic Approach to Markov Decision Processes. Probability Theory and Related Fields, 78(4):583-602, 1988.
[8] Archana Bura, Aria HasanzadeZonuzz, Dileep Kalathil, Srinivas Shakkottai, and Fran-Francois Chamberland. DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning. In Advances in Neural Information Processing Systems, 2022.
[9] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning. In Advances in Neural Information Processing Systems, 2017.
[10] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably Efficient Safe Exploration via Primal-Dual Policy Optimization. In International Conference on Artificial Intelligence and Statistics, 2021.
[11] Dongsheng Ding, Chen- Yu Wei, Kaiqing Zhang, and Alejandro Ribeiro. Last-Iterate Conver- gent Policy Gradient Primal- Dual Methods for Constrained MDPs. In Advances in Neural Information Processing Systems, 2024.
[12] Supriyo Dutta and Shigeru Furuichi. On Log-Sum Inequalities. Linear and Multilinear Algebra, 72(5):812-827) 12-1122-272202 2024.
[13] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-Exploitttio in Constrained MDPs. arXiv preprint arXiv:2003.0m 021.9, 2020.
[14] Germano Gabbianelli, Gergely Neu, Matteo Papini, and Nneka M Okolo. Offline Primal-Dual Reinforcement Learning for Linear Mdps. In International Conference on Artificial Intelligence and Statistics, 2024.
[15] Matthieu Geist, Bruno Scherrer. and Olivier Pietquin. A Theory of Regularized Markov Decision Processes. International Conference on Machine Learning, 2019.
[16] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Provably Efficient Model-Free Constrained RL with Linear Function Approximation. In Advances in Neural Information Processing Systems, 2022.
[17] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Achieving Sub-linear Regret in Infinite Horizon Average Reward Constrained MDP with Linear Function Approximation. In International Conference on Leurning Representations, 2023.
[18] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Towards Achieving Sub-linear Regret and Hard Constraint Violation in Model-free free RL. In International Conference on Artificial Intelligence and Statistics, 2024.
[19] Shangding Gu, Long Yang. Yali Du, Guang Chen, Florian Walter, Jun Wang, Yaodong Yang, and Alois Knoll. A Review of Safe Reinforcement Learning: Methods, Theory and Applications. arXiv preprint 22Xiv:2205.10333 2022.

---

[20] Aria HasanzadeZonuzy. Archana Bura, Dileep Kalathil, and Srinivas Shakkottai. Learning with Safety Constraints: Sample Complexity Reinforcement Learning for Constrained MDPs, In AAAI Conference on Artificial Intelligence, 2021.
[21] Jiafan He, Dongruo Zhou, and Quanquan Gu. Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation. In Advances in Neural Information Processing Systems, 2021.
[22] Spencer Hutchinson, Berkay Turan, and Mahnoosh Alizadeh. Directional Optimism for Safe Linear Bandits. In International Conference on Artificial Intelligence and Statistics, 2024.
[23] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably Efficient Reinforcement Learning with Linear Function Approximation. In Conference on Learning Theory, 2020.
[24] Toshinori Kitamura, Tadashi Kozuno, Masahiro Kato, Yuki Ichihara, Soichiro Nishimori, Akiyoshi Sannai, Sho Sonoda, Wataru Kumagai, and Yutaka Matsuo. A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees. arXiv preprint 17X1v:2401.17780, 2024.
[25] Chandrashekar Lakshminarayanan, Shalabh Bhatnagar, and Csaba Szepesvári. A Linearly Relaxed Approximate Linear Program for Markov Decision Processes. IEEE Transactions on Automatic control, 63(4): 180-119811111111 2017.
[26] Tor Lattimore and Csaba Szepesvari. Bandit Algorithms. Cambridge University Press, 1st edition, 2020.
[27] Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs. In Advances in Neural Information Processing Systems, 2021.
[28] Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption-Robus Explo- ration in Episodic Reinforcement Learning. In Conference on Learning Theory, 2021.
[29] Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. Truly No- Regret Learning in Constrained MDPs. In International Conference on Machine Learning, 2024.
[30] Gergely Neu and Nneka Okolo. Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization. In International Conference on Algorithmic Learning Theory, 2023.
[31] Gergely Neu and Ciara Pike-Burke. A Unifying View of Optimism in Episodic Reinforcement Learning. In Advances in Neural Information Processing Systems, 2020.
[32] Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic Bandits with Linear Constraints. In International Conference Artificial Intelligence and Statistics, 2021.
[33] Aldo Pacchiano, Mohammad Ghavamzadeh, and Peter Bartlett. Contextual Bandits with Stage-wise Constraints. arXiv preprint arXiv:2401.08016 2024.
[34] Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained Reinforcement Learning Has Zero Duality Gap. In Advances in Neural Information Processing Systems, 2019.
[35] Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1994.
[36] Amirhossein Roknilamouki. Amob Ghosh, Ming Shi, Fatemeh Nourzad, Eylem Ekici, and Ness Shroff. Provably Efficient RI. for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces. arXiv preprint arXiv:2502.1 18655, 2025.
[37] Aviy Rosenberg, Alon Cohen, Yishay Mansour, and Haim Kaplan. Near- Regret Bounds for Stochastic Shortest Path. In International Conference Machine Learning. 2020.
12

---

[38] Igal Sason and Sergio Verdú. f-divergence Inequalities. IEEE Transactions on Information Theory, 62(11):5973-6006, 6006, 2016.
[39] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[40] Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic Policy Optimization with Bandit Feedback. In International Conference on Machine Learning, 2020.
[41] Ming Shi, Yingbin Liang, and Ness Shroff. A Near-Optimal Algorithm for Safe Reinforcement Learning under Instantaneous Hard Constraints. In International Conference on Machine Learning, 2023.
[42] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-Optimal Sample Complexity Bounds for Constrained MDPs. In Advances Neural Information Processing Systems, 2022.
[43] Roman Vershynin. Introduction to the Non-Asymptotic Analysis of Random Matrices. arXiv preprint arXiv:1011.3027. 2010.
[44] Honghao Wei, Xin Liu, and Lei Ying. A Provably-Efficient Model-Free Algorithm for Con- strained Markov Decision Processes. arXiv preprint arXiv:2/006015577, 2021.
[45] Honghao Wei, Xin Liu, and Lei Ying. A Provably-Efficient Model-Free Algorithm for Infinite- Horizon Average-Rewand Reward Constrained Markov Decision Processes. In AAAI Conference on Artificial Intelligence, 2022.
[46] Donghao Ying, Yuhao Ding, and Javad Lavaei. A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization. International Conference on Artificial Intelligence and Statistics, 2022.
[47] Kihyun Yu, Duksang Lee, William Overman, and Dabeen Lee. Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism. arXiv preprint arXiv:2410.10158, 2024.
[48] Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist Regret Bounds for Randomized Least-Squares Value Iteration. In Interna- lional Conference on Artificial Intelligence and Statistics, 2020.
[49] Sihan Zeng, Thinh Doan, and Justin Romberg. Finite-Time Complexity of Online Primal-Duue Natural Actor-Critic Algorithm for Constrained Markov Decision Processes. In Conference on Decision and Control, 2022.
[50] Weitong Zhang, Jiafan He, Zhiyuan Fan, and Quanquan Gu. On the Interplay Between Misspecification and Sub-Optimality Gap in Linear Contextual Bandits. In International Conference on Machine Learning, 2023.
13

---

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]
Justification: Theorem 4, Table 1, and Remark
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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]
14

---

Justification:
Assumptions 2 and 3 and corresponding proofs in Appendix E
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide 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 be properly referenced.
4. Experimental result reproducibility
Question: 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 whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Implementation details in Appendix F and the submitted supplementary code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a 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 clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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?
15

---

Answer: [Yes]
Justification:
We provide the experimental code as supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https: /ttppss///iipp./eeeeeeeees cc/
publ public/ deid CoodeSuomi i ss assiooolll icy) 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: //niss. cc/ cc/pps pwppppplcc.ooo /wwpi/gus////////ie//oe /Coeee////eeaeee CodeS SuteeSubiiiee as ssi cioooiioyyy 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: [Yes]
Justification: Implementation details in Appendix F. 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Figure
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.
16

---

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: [Yes]
Justification: Appendix F
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 https: https:////euiiispe https///c.c.cccc/tiiiniiiiieeee.
Answer: [Yes]
Justification:
No NeurIPS code of ethics were violated.
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: This work is a primarily theoretical study on the safe reinforcement learning. The social impact of this research is not likely to be significant.
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.
17

---

The conference expects that many papers will be foundational research and not tied to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: No model or data is released.
Guidelines:
The answer NA means that the paper poses no 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 to 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. Licenses 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: We do not use any existing code assets, except for standard Python libraries (e.g., NumPy).
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset 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 (e.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 the package should be provided. For popular datasets, papersw's thoode com/ dat aset 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.
18

---

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:
We do 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:
No crowdsourcing or 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:
No crowdsourcing or 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
19

---

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 core of this research is unrelated to LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: : / /t///neerppppp// cc//onferences / 2025/ LLM) for what should or should not be described.
20

---

Contents
1
Introduction
2 Warm Up: Safe Exploration in Linear Constrained Bandit
2.1
Technical Challenge: Zero- Violation with Safe Policy
2.2
Algorithm and Analysis
2.2.1
Zero-Violation and Logarithmic Number of ाt Deployments
2.2.2
Regret Analysis
3
Safe Reinforcement Learning in Linear Constrained MDP
3.1
Technical Challenge: Optimistic-Pessimistie Optimization in Linear CMDP
3.2
Algorithm and Analysis
3.2.1
Zero-Violation and Logarithmic Number of क Deployments
3.2.2
Regret Analysis
4
Conclusion
10
List of Symbols
22
Related Work
24
B.1 Related Algorithms
24
B.2 Related Safety Types
24
Useful Lemmas
25
D Regret Analysis (Linear Constrained Bandit)
28
Regret Analysis (Linear CMDP)
30
E.1
Definitions and Useful Lemmas
30
E.2 Function Classes and Covering Argument
32
E.3 Good Events and Value Confidence Bounds for Lemma 4 Proof ................................
36
E,4
Proofs for Zero- Violation Guarantee (Section 3.2.1)
38
E.4.1 Proof of Lemma 5 and Lemma 6
38
E.4.2
Proof of Theorem 3
41
E,5
Proofs for Sublinear Regret Guarantee (Section 3.2.2)
42
E.5.1
Mixture Policy Decomposition
42
E.5.2
Optimistic Bounds
43
E.5.3
Bounds for Bisection Search
44
E.5.4
Proof of Theorem 4
46
F Numerical Experiments
47
21

---

A List of Symbols
The next list describes several symbols used within this paper.
Mathematical Notations
(SS)
Set of probability distributions over set
[a, 6] Set of integers defined by {a.....b)
clip (x, a. b) Clipping function which returns x' with x/ min mx; b} for each i
0,
Vectors such that 0 (0....,0) ,)T and 1 (0....,,)'
| For positive definite matrix A E Bdxd and E IR, we denote ||x||a vx Ax
an = 0 (b,)) There exist constants C > 0 and N E N such that an I Cb, for all n 2 N
Ō() Hide the polylogarithmic factors from O(-)
SoftMax(x) Softmax distribution satisfying SoftMax(x); exp(x:) exp(x.))
dist.o Distance metric for functions Q, 8 A IK V, V.V" : (see Definition 7)
dist,
Distance metric for two functions n' S + (LA) (see Definition 7)
Constrained Bandit
A C Rdd Set of actions
K
Round length of the bandit problem
r (k)) (A)
Reward and utility at k-th round
0,, O, E ERd Unknown vectors for reward and utility
Eri Eu
R-sub-Gaussian random noises
Ya: Up
Or = Ea-- (0g. a)] for both E fr, u}
Set of safe policies { Uv 2 6}
sf
Safe policy
0
Safety of . such that Ug - bb 2
(K)
Gram matrix defined by A (k) = pl + Σ ===1 a (a
(k)
0
Estimates of 0, and e..
((k)
Bonus function
Cr, Cv.
Bonus scalers for reward and utility, respectively
Set of iterations when Algorithm is unconfident in х (see Definition 1)
Constrained MDP
K
Number of episodes of the CMDP problem
И
Horizon
S,A
State space and action spaces
P
Transition kernel
r,
Reward and utility functions
81
Initial state
[x]
Regularized state value function for reward function y with entropy coefficient k
P.N
QT [k]
Regularized action value function for a reward function g with an entropy coefficient k
he
Shorthand of h(1 In A)
Occupancy measure of in P at step h
22

---

5 x A - R Rd Feature map of the linear CMDP (see Assumption 2)
d-signed measures specifying the transition probabilities (see Assumption 2)
0 0 E I2
Known vectors specifying the reward and utilitiy functions (see Assumption Set safe policies { (
II"
(s1) 2 b}
Safe policy
<>0
0
Safety of nd such that Vpi (m²l) b 2
(k)
Gram matrix defined by A = pl + Σ 0(0) , (() )
A
Next value estimation: V) a) = ( a)
- ((5 ((00
Q [Kt), L(k), U(H), Clipped value functions defined in Definition
Cr, Cu., Ct. B3 Bonus scalers used in Definition 2
N
E-cover of a certain set Set of iterations when Algorithm 2 is unconfident in श- (see Definition 4)
Th
(1),A
Softmax policy with a parameter À (see Definition 3)
A
Parameter to balance optimism and pessimism of %h 1k).2 (see Definition 3)
C
Maximum value of À
[A (R.0)
Search space the bisection search at iteration t in episode (see Algorithm 2)
Iteration length of the bisection search (see Algorithm 2)
Q", Q", Qf Function classes for Q-functions defined in Definition 10
Q"
Function class for the composite of Q-functions defined in Definition 11
Class for softmax policies defined in Definition 12
Vr, V", vi Function classes for V-functions defined in Definition 13
gx.u g5.1 (A)
Discrepancies between the estimated and true Q-functions (see Definition 14)
(k) (k)
(K)
(k)
8T, 8TT (k) Function classes for (8) (k) (k) (see Definition 14)
23

---

B
Related Work
B.1
Related Algorithms
Building the seminal work of Efroni et al. [13], numerous safe RL algorithms for CMDPs have been developed, broadly categorized into linear programming (LP) approaches and Lagrangian- approaches.
Linear programming. LP approaches formulate CMDPs as linear optimization problems [2]. solving them using an estimated transition kernel. Efroni al. [13] introduced a basic sublinear regret algorithm, while HasanzadeZonuzz et al. [20] provided (e, 6)-PAC guarantees, ensuring the algorithm outputs near-optimal policy. However, these methods permit constraint violations during exploration, making them unsuitable for safety-critical applications. Liu et al. [27] and Bura et al. [8] developed LP-based algorithms that achieve sublinear regret while maintaining episode-wise zero-violation guarantees by incorporating optimistic pessstiiiic estimation into the LP formulation.
LP-based approaches tabular settings, however, suffer from computational costs that scale with the size of the state space, making them impractical for linear CMDPs. While several studies propose LP algorithms for linear MDPs [31, 5, 30, 25, 14], these methods either use occupancy measures as decision crrrables-whiee can be exponentially large for large state spaces- or require set of feature vectors that sufficiently cover the state space, which may not be feasible in our exploration settings. Moreover, described in Section 3.1, the estimated value functions in linear CMDPs with exploration require clipping operators, further complicating the use of eccupancy-measure approaches like LP methods in our setting.
Lagrangian approach. Lagrangian approaches reformulate the constrained optimization
max, (f( ((()) 2 0} as min-max optimization minx20 max (f(() (m- + Ah(Tr) }. and simultane- ously optimize both π and X. When an algorithm gradually updates π and then adjusts À incrementally, it is referred to as a primal-dual (PD) algorithm [11]. In contrast, if updated only after fully optimizing ı in the inner maximization, it is known as a dual approach [46]. Since the inner maximization reduces to standard policy optimization, Lagrangian methods integrate naturally with
scalable methods such as policy gradient and value iteration.
For the tabular settings, Wei et al. [44], Müller al. [29] develop model-free primal-dual algorithms with sublinear regret, while Wei et al. [45] extends this approach to the average-reward setting. Zeng al. [49], Kitamura et al. [24] propose (e, -PC primal-dual algorithms, and Vaswani et al. [42] achieved the PAC guarantee via dual approach.
Beyond tabular settings, Ding et al. [10] propose PD algorithms with linear function approximation, achieving sublinear regret guarantees. Ghosh et al. [17] extend this to the average-reward linear CMDPs. Ghosh et al. [16] take a dual approach, also attaining sublinear regret in the finite-horizon settings.
These PD and dual algorithms, however, do not ensure episode-wist zero violation. Intuitively, the key issue lies in their A-adjustment strategy, which updates À only incrementally. For example, the basic PD and dual algorithms by Efroni et al. [13] updates À using (A=1)) ( where a is small learning rate. Since À controls constraint satisfaction, if the current policy fails to satisfy constraints adequately, À should be increased sufficiently before the next policy deployment.
[violation],
Following this principle, Ghosh et al. [18] propose a dual approach that searches for an appropriate À within each episode, leading to tighter violation regret guarantee than Ghosh et al. [16]. However, due to the lack of pessimistic constraint estimation, their method does not ensure episode-wise safety and allows constraint violations. Like Ghosh et al. [18], our OPSE-LCMDP searches for the best in each episode. However, unlike their approach, OPSE-LCMDP controls À with pessimism, ensuring zero violation, and guarantees the existence of feasible À by deploying a sufficient number of .
B.2 Related Safety Types
Instantaneous safety. Unlike our episode-wise safety, instantaneous safety defines exploration as safe if it satisfies (* (K) aa
(k)) 2 for all and [32, 33, 22, 41, 4]. other words, states and actions must belong predefined safe sets, Sat x Asr. Instantancous safety is special case of the
24

---

episode-wise constraint. Indeed, by defining 4n (s, a) (s) Sat x Ast) and setting = 0, an episode-wise safe algorithm safeties the instantaneous constraint for all h and k.
Cancel Safety. Cancel safety another common safety measure in CMDP literature Wei al. [44], Ghosh et al. [16]. It allows a strict constraint satisfaction in one episode to compensate for violation in another. Formally, cancel safety ensures that the following cumulative cancel violation regret remains non non-positive:
ViOcancel (K)
Σ
Vall ((81).
Note that the "hard" violation regret Viohard (K) = Σ max vp " "(11),0 which con- siders violations each individual episode [18, 13, 29], always upper-bounds the cancel regret. This means cancel regret is weaker measure. Since episode-wit wise safety ensures Viouard our OPSE-LCMDP always satisfies cancel safety, but cancel safety does not necessarily guarantee episode-wise safety.
C Useful Lemmas
Definition 6. For set of positive values {anIn=y write polylog (a1...., ax) if there exists an absolute constants (bn) > and (cn) > 0 such that x S bo + bi (In (1)))) +...+ by (In "**
Definition 7 (Distance metrics). Let dist be the distance metric such that, for two functions Q Q' S x A + I, do (') sup sup(s.a)ssxal (((s, a) Q'(s, a)}. Similarly, for functions V,V" S R. dist (V, V*) sup (s) V'(s).. Finally, dist, denotes the distance metric such that, for two functions n, n'' S + ( dist (T,, m²) supseslla(( () (-))-=( (-11))
Definition 8 (s-cover). Let θ (0 e Rd |0| S R} be ball with radius R. Fix an E. An e-net M, C. ② is finite set such that for any 0 θ, there exists 0' E M, such that dist 0 0') S for some distance metric dist(.,.). The smallest s-net is called c-cover and denoted as No. The size of the e-net called the E-covering number.
Lemma (Lemma 5.2 in Vershynin [43]). The E-covering number of the ball = {0 Rd ||0||2 S R} with the distance metric ||-11, is upper bounded by (1 (1+ 2R/e)².
Lemma 10 (Danskin's 's Theorem [6]). Let f IR" x Z + R be continuous function where Z E R a compact set and g(x) == max,ez f(I, 2).
Let Zz(z) = {ol f(x,, 2) m f(z,2) be the maximizing points of f(x, z). Assume that fx, 2) convex x for every E 2. Then, 9(x) is convex. Furthermore, if Zu(z) consists of single element ž, i.e., (x( = (:), it holds that Og(z) 0f(z.2)
Or
dx
Lemma 11 (Lemma D.4 in Rosenberg et al. (37]). Let (x (= be sequence random variables
with expectation adapted to the filtration (F(R)) k=0 Suppose that O < x < B almost surely.
Then, with probability at least the following holds for all k simultaneouslyy
k
(i) [((-11
<
x + 4BInn
Lemma 12 (Lemma 11 in Abbasi-
Abbasi-Yadkori Yadkori al. [1], Let {x(1) bin be sequence in R.d. Let
(k) =pI+ E (0) x00 (x()) T. [x)
112 S for all
min {1, |x(x)|/² | < 2d
pdd KB2 pd2
(1:00)
pd
25

---

Additionally, if x/|x(00 1l S 1 for all k and 2 19, we have
Σ
K
((a (A/r)) S 2d
(pd (pdtt1) K
pd
Lemma 13 (Theorem 2 in Abbasi- Yadkori et al. [T]) Let {F(h) be filtration. Let be a real-valued stochastic process such that e(h) -maasurrall and e(k) is con-
(s(h) 2o ( k=1
ditionally R-sub-Gaud Gaussian for some R 2 O. Let { {alth) J=1 be Ra-valued stochastic pro- cess such that (0 is F(k-1) measurable and (| (8) 12 S for all k. For any k 2 O, define
Yk -o= ((()) + for some O E Rd such that |101|2 S B. ( = p E.= 800 (8(( and
(k) -(A11) (A Σ i=1 (1)) Then for any 8 0. with probability least 1 8, for all ls 2 0.
we have
0 (k)
0
S
p2
B RV dh
1+ 1+111/P
A(5)
Lemma 14 (Lemma D.4 in Jin et al. [23]). Let {s(H))
k-1 be stochastic process state space S be an IR -aavulued stochastic process where k=O
with corresponding filtration (F(R) 20
Let { (k)
k=o
and let V be class of real-valued function over the state space S such that sup, [V(s) < B for B > O. Let be the e-cover of V with respect the distance distie. Then for any with probability at least
(h)) is -eessul-eassurblllee and [B(0|
$1 Lei
pl - (6k) (ab(2) T
Ek=
Ny NY
1 - 6, for all K 2 O, and any V E V, we have:
K
(k) v (s(()
E [V( (s!)) (
S <4B² (A(O)-+
In 2
K K+p)
+ In
W
8K262
Lemma 15 (Lemma A.1 in Shalev-Shwart. and Ben-David (39]). Let a > 0. Then, x 2 nn(a) yields a ln(x). follows that necessary condition for the inequality S a In(x) to hold is that x S 2a (n)..
Lemma 16. For any positive real numbers Tı, T2, ................................ Tne Σ
VT VT VV E
Proof. Due to the Schwwrz inequality, we have root of the inequality proves the claim.
E
Taking the square
Lemma 17 (Lemma 1 in Shani et al. [40]). Let म, π be two policies, P be a transition kernel, and be a reward function. Let V S - IR be function such that
(s)
Σ REA
Fala (s,
for all h E [1, with some function Qn [[. X - Then, for any (h, s) E [[, H] X
V (s) V (8) V (s) + VT.g² (s)
where g² and 92 are reward functions such that
gi (s, a) = (an((a - ()))@(())s))) and gh, a) = Qn (8, gh (8, (PnVitz) (Paaiitz)(o.a.. (s,a).
aEA
"The second argument follows since ||x|| S Fmax (A-1) |x|12 p- 5 where T (A -1) denotes the maximum eigen value of A
26

---

Lemma 18 (Regularized value difference lemma). Let K. 2 0 be a non-negative value, n, n' be two policies, P be transition kernel, and 9 be reward function. Let V [m] S - IR be a function such that
V [m](s)) = Σ (a 8) (Ōn(s,a) (a s))
aEA
for all h E [1, H] with some function Qn [1. H] x x A + R. Then, for any (h, E E HJ [], x
[w]ss) V [w](s) V (s) + V (s) (s)
where f and f are reward functions such that
(1 u) = Σ (n(a| (
8) Tn(a 8) @n(s, -llma(aaa) 8))
aEA
and fa(s,a)= = Qn a) - gn (s, - ( (s,a)
Proof. Since
(x]ss) = Σ Tn(al T)(als) (Qh(s,a) - - and V [x]][]((s) = VT.2 x lu (s)
aEA
using Lemma 17, we have
(V VTJg (s1) + V
where o² and r² are reward functions such that
a))
Σ
(an s) (a - s))
aEA
Σ (a s) (Q)(s, - x x 8)) - an(a 8) -)) xInnaaaa s))
aEA
Ta(a (s) kn 8))
aEA
= and
- gn (s, - (it (0, Inln 8) + (all (6)
The claim holds since the terms (a) and (b) are canceled out in V. (s) + VP (s).
Lemma 19. Let Q Q A - IR be two functions. Let 0 be a positive constant. Define two softmax distributions 7 (AA) such that = SoftMax Q and गे SoftMax 2
Then,
x
|| म| - = = 2
Proof. It holds that
1
π - #|1
< 2 Σ
(9)
(())la In (a)) < 2 max (n In ln)
2
aEA
2 max
- ((a)=
1
Q((a) In Σ exp
L ((1))
In Σ exp
1 o(a))
K
K
A
1
1 e(())
1 Q(a)) K
< 2 max
((a)= ((a)
22 Σ exp
- In Σ exp
Eexp
K
R
R
((a) 1 Q(a) K
4 max
K
where (a) uses Theorem 17 in Sason and Verdú [38] and (b) uses the fact that In E, exp(x:) In Σ; exp(y:) S max,(x; - ys) (see, e.g., Theorem in Dutta and Furuichi [12]). This concludes the proof.
27

---

D Regret Analysis (Linear Constrained Bandit)
Lemma 20 (Good event 1). Suppose Algorithm 1 is run with p Let E (0, 11. Define EN as the event where the following inequality holds:
K (k)
(A(E))-1 + +4In 2K
B a (0)
||a| (ACO)) -
8
Then, ((61)21-1
Proof. The claim immediately follows from Lemma 11 with ||al|2 S and p 1.
Lemma 21 (Good event 2). Define Eg as the event where the following two hold: For any π E II,
k E [1,
p()) - rr S and
(2(k) ur S C. C..
Then, if Algorithm 1 is run with p 1 and the value of C. 2 B + Ry
4k 8. it holds that
P(O) 2 -.
Proof. Using Lemma 13 with p 1, with probability at least 1 - ô, for any & E [1, K] and for both g E ur, we have
0g
0 9
0,
||a|| (A:9))
A(4)
(o)
2(1 K)
R
dln
|a ||al( ((ar)))-
B R d 4K
<
||ll| (Am))
where (a) uses Lemma 13, The claim holds by Ft g E (r,u).
(N)
go S E Eaws
T (0))) - 0g) for
L
Σ 3(8)
Lemma 22 (Cumulative bonus bound). Suppose &1 holds.
Then,
VK / (2 + 2) + 41n 2K 5
Proof. It holds that
K
K
K
g(k)
K
E
2
K
E
||a||
||al|/200 (A(t))+
(k)
1=1
k=1
A=
K
(4) 2K
K 1
2K
VK.
2
( a
(1
4 8
VK
2d
+ 4 In
d
5
1m
where (a) and (b) use Cauchy-
Cauchy-Schwarz Schwarz inequality, (c) is due to E1, and (d) uses Lemma 12.
Lemma 23 (Restatement of Lemma 1). Suppose &g holds. Then, for any π E II and k E [1, K]. + 2C,,g(k) 2 ((k)
Cu 2 Tr and u 2 T(h)
Ca 2 UT 2C,,
Proof. We have
Ur 2 x(())
(K) Un
(k)
((. > x(()))
- ((k) Un
g 2 Ux 20,
Similarly,
Fr + +2C,,(h))
> p(k) +
[()) Fr
+ ((k)()))
2 p(k)
+ CC,
2 (())
[(k) rmm
2 rT
28

---

5-20 net
Lemma 24 (Restatement of Lemma 2). Consider Uc For any a E
8-20,, +20
mixture policy Ta (1 a)) ax satisfies uno 2C ((1)) Proof. For any and a E [0, 1], we have
2 b.
Una - 2C g(k) = (1 a) (U - b) +a (U
- -a) 2C
28
20
2 (1 (l-aa) (a--a)(-2Cuul
(k, (20 nr1
2aC
To make (1- (1 22Cmn 20 g(t) 2 sufficient condition is
{ 20 xz
2C (b) xx 2C
where the right hand side is non-negative since Uc This concludes the proof.
Lemma 25 (Restatement of Theorem 1). Suppose Algorithm I is run with p 1. Assume the event E1 holds. Then, [4] & 32dC --2 1n(2K8-1)
Proof. We have
K
Σ
E (t) (+)
|
[al((rr0)
Σ E (aall) (A(ai) kell
2² 1
E (lanits)laal
4C2
keM
-(0(t))
since (k) x
where (a) is due to Jensen's 's inequality, and (b) is due to Definition 1. Due to 6,, we have
K
K
(A())) + 4ln 2K
Σ
1 w ||a|] (A (2)))) $
(8)
k=
Using Lemma 12 and since ||a||2 S and p = 1, the first term is bounded by: S 2d 4) Thus,
2² 4C2
K d
2K
2K
u S
2d
1
+4
S
8dln
8
S2K The claim holds by rearranging the above inequality.
Lemma 26 (Restatement of Lemma 3). For any is E 2c, aats satisfies Fr
2BC,
(1 rzt.
Proof. Let (k) E- (02
and C' == 2BC, Note that I-a
(k)
$-20,,
aff We have,
8-20,00hh oa +20.
20.0
Tx ( (1)
= (k)) 7 + (8) C(1 a (8) ()))
+ (C(()) g(k)
Tul
((A)
2 (k)
(t) Tx- + + (1 (1- (+) g(k) + a (k) glk)
sufficient condition to have (k) n. + + a (ki)
g(kb) grr + a (k) g
2 rn- is, since r.
Em-z. [0,aa)] < ||a|| S B,
(k)
((k) 7pt
g(k)
<
C
+
- (kT
=c
g(k)
qut
+
20,
1
5
g(k)
npt
S C
20
S
Therefore, when C² 2BC,
we have TT,
(1)
(k)
Tx.
29

---

Theorem 5 (Restatement of Theorem 2). Suppose that Algorithm run with p = 1,
4K dln
and C. Cu Ci((1 2B
C B R
8
Then, with probability at least 1 - 20, the following two hold simultaneously:
7(h) 11 for any [K]
Regret(KK) v 6 In (2Kō + 4C, / 2d + 4) 4 26
Proof. Suppose the good events 61 to Opt-Pes in & E Zz Since Opt-Pes is ensured have feasible solutions by Lemma 24 for & E uP the first claim follows immediately.
62 hold. Recall that (1)) is either x- in & E U or the solution
We will prove the second claim. It holds that
K
Regret K)
Txx
(M))
Σ
(1) +
Σ k@l
I'm
(T((k
k=1
kELf
(k)
is computed by Opt-Pes Pes
u +
I' (x(A))
Aigh
In
Σ
Fx
p(k) 7(4)
Cx.(k)) 21())
((l)) mr()
Cr(g(K) 71()
xx(0))
where (a) uses the bound of | (Lemma 25). Using Lemma 23, the term 2 is bounded by I Engu 3C, 3
200) On the other hand, ! is bounded by
2BC g(k)
C,,g(k) m(()
+
7(K)
(k) (K)
+
(() (1)))
2BC
g(k)
(k)
[(k)
#(6)
g,g(()
0
where (a) uses the optimism of mixture policy (Lemma 26), uses Lemma 23, and (c) uses C, (1 2BC,E-1)C, and since Ta0 is feasible solution to Opt-Pes due to Lemma 24,
Finally, by combining all the results, we have
Regret(K) <
3C,
Σ
g(k) (T
kgu
K 1+
2K 8
s 6A 3C
2d
In
+ 4 In
d
where the second inequality uses Lemma 22. Since the good event 61 n occurs with probability at least 1 - due Lemmas 20 and 21, the claim holds.
E Regret Analysis (Linear CMDP)
E.1 Definitions and Useful Lemmas
Definition 9 (u-estimator). Let e(s) e S denote a one-hot vector such that only the element at
E S is and otherwise 0. In Algorithm for all h and k define μ (k) Sxd and c (k) _ such
30

---

that
k-1
P4 = -e e (0 (50% [0 )
(M)
(A
and 6h e/ = el
(h)
e(ontt) (8h+1)
(/) ,a/aa p (10)
p(.10% (8)
We remark that () (s, = ((s, a)T (1h (1))
T
V for any V YERS.
Lemma 27. For all k and h, holds that:
1b - (A
k-1
i
/hhh)) T
(A
Ph
h
Φ
hh
1=1
Proof. Due to the definition of 14 we have
(l)
(3)
e 5h+1
2 (5
(6)
0
(K)
k-1
.aa (
Sh
(k)
+ c/2
(1)
) 1 (3)% (1 T
) (A )²
-1
i=1
(k)
( (K))
sh a
+ ch
sh
Σ
M4 Φ
8/ a
(k)
(K)
A
+ Σ
c
(1)
( (1)
(A(t))
nn
(A
(k)
pl)
(1)
(k)
AA
(K)) -1
k-
(A
+
c
(k)
Φ
h
(1)
(A()))=
==1
Lemma 28. Let V be class of real-valued function over the state space S such that sup,, (V)) S B
for a B > Let N₂ be the e-cover V with respect to the distance dist In Algorithm 2, for all k. h, 8, o, for any V E V. with probability at least 1 - 8, we have
((P) - Ph.) v)) (s.a)
< (
VVopB + 2B
In
1: +
+ 2B
In
W
+
4ks
8
vp
Proof. Using Lemma 14 and due to the definition of A (k) in Algorithm with probability least 1 - 8, for all k, h, we have
(k) Σ Φ 8h 2hh
(k)
(VTc(")
<V
|B2
In
1: + P
+ In
Wel
+
81:222
2
(A(r))-1
d
1: + P
N
4k
< 2B
In
2B
In
P
8
VP
31

---

where the second inequality uses va+bs va+ Vb. By inserting this to Definition 9, we have
(P/ h - -P.) (s.
(s) (1h -ma) V
b(s,a)
(1))) (a()))² (-oth
-1 + Σ Φ
8h
(
an
(1)
A (1)
-1
5p {p)(s))) (A -1 (pm)TT + Φ(s,a) TTTTT)()))) (AA
(A(1)
(8)
-1 k-1
Σ Φ
V (v
#
k-1
(mwW) [1 (1
Σ +
(3)
(3)
V
-
8h
: u
(A!h))-
SB by Assumption 2
<(1b(s,a)l(a Vd 2 d
k kktp"
W
4kg
2B
p
vp
E.2 Function Classes and Covering Argument
Definition 10 (Q function class). For any h and for a pair of (w, A), where w E IR and A E Raxd,
define Ohr (r,r S A + R. Of (w, S x A + R. and Q/ (w.A). S x A + R such that
a) Q (l.. a) (s, clp(
Q (w,A))r (8, a) rs a) +
((s 0, H₂ - hr3
((s,a), 0, H- - h} Q (i (8,a) a) B a) ^- (ll w T (6 a), 0, B+(H - [[]-
where Ki Cr,, Cu. By: O O. We denoted h2 111 + for h [1, H1. Let 2h 2 2 denote function classes such that
0 { Q (w,,rr
|w|l2 S KHN, m (A) 2 1
0 = o (,,,)
||wl22 S KH, miiu (A) 2 1
and O = { Qh
Aw)t)
|wll < KHB,, amin (A) 2 1]
We let No . and No be the e-covers of 2i, 2j, and O with the distance metric dist.
Lemma 29 (Q covers). When Algorithm 2 is run with p 1, it hold that:
ii) For all k, h and any π E II, [k) E 27 2(A), E 24 and Q(1), E O%
(ii) In IN S ddmm(1 + AKH.
In
Sv7C2 1+
(d, = (dd)) polylog (d, K, HA, Cr, E1),
2²
In [
0 S dln(1 [1 4KH + d2 In
+ SvdCa
= ((d) polylog(1) (d, K, H. Cu, 111.
and In
<
din(1
dln
11+
4K
+
d² In 1+ svac?
(dP) polylog(d, K, B,, 0-1)
Proof. The statements in (ii) immediately follow from the proof of Lemma D.6 in Jin et al. [23].
32

---

We prove the first claim (i). For (k),k we have
((k),|[== =r + clip C, + p( (H), O, (H - 1:)(1 + xln
=rh + clip Cr Cypols,a) ((s,,)) (A) Φ(s,a) +
a(s,a) +(s,a) (hh (k)
((0, O, (H h) + xs xx)))
According to the definition of Qh (. (Definition 10), the claim immediately holds by showing
the 1.2 bound of (11
[x]]. For any h E [1, H| and & E [1, K], we have
(11f+) T V (1))
V
(6),
[x]] ph+1 S 8h m
A h
(8)
-1
2
i=1
2
(n) <
(k)
(1)
Hx
S KH
where (a) uses || I 1 with p 1 and 0 S V a.P
(k) [x] s Hn:
The remaining claims for L(h), (s, a) 2% and Q (s, O) can be similarly proven.
Definition 11 (Composite Q function class), For each h, let 22 denote a function class such that
2 {0- + Q' + +Q" Ql 2h Q' E 2h Q" 2% and X [0, [O.
where C2 > 0. We let N. be the e-cover of 23 with the distance metric distxx-
Lemma 30 (Composite Q cover). When Algorithm 2 is run with p 1, the following statements hold:
(i) For all h). for any π E II, and for any E C2). Q(b), + ((R), [x] + +2Q70), E Qi
(ii) In eal = (dd)) polylog(d, K, Hn, Cr, Cu, Bt, CG C
Proof.
The claim (i) clearly holds by Lemma 29 and Definition 11.
We prove the second claim (ii). Let Na be the e-cover of a set {A|> A E [0, CXI) with the distance
metric I1-11p- Let Eu Ex
be positive sealars. Consider Qt E Ne Q" e N 2 and À E.A. For any Q 2h Q" E 2/ Q" E 2% and [0, Cx), have
Qu E N
dist
Q1 + Q" +xQ" @1 + Q" + +XQ")
Q (s, @T +sup sa
Q" (s, a) - (s,,a)
< sup sa
Set
Str
Auuu
(Q"((sa)-(""(( (²"(saa) + suup (2 2) ())a(a))))
5C25a
H H
Et te Er + CxEu +
where (a) appropriately chooses Q',@' T", X. By replacing Et with e/4, Er with e/4, en with 1/4C,, and εx with e/4H, the above inequality is upper bounded by E. Thus,
In 2i
in N3
+ In We s//cc In 1 8/4
+ In No 8/4
2/14
<d()) polylog( dd, K, HA, Cr, Cu, By, C., Cx )) where the second inequality uses Lemma 9 and Lemma 29.
33

---

Definition 12 (Policy class). î = II, x ... x Hy denotes softmax policy class such that
ïI = [TQ E -I E Oi where no6: | 8) = SoftMax ( ((( Vs s
where & > O. We let N be the E-cover of HI with the distance metric dist1
Lemma 31 (x()),) cover). When Algorithm 2 is run with -1 and 0, for all h, the following statements hold:
ii) For all (ki, h) and E [0, Cx] in Algorithm 2, Th E II,
(k),²
(ii) In N (cP) polylog d. K, Hy: Cr, Cue B, Cj,
Proof. The claim (i) immediately follows from Lemma 30 and Definition 3.
We prove the second claim. For Q S A + IR, let no be softmax policy such that ne(:
s) SoftMax ((s.) Consider Q from No 2x
Then, for any Qh have
8 dist (0. 88
dist TQq Tσ
where (a) uses Lemma 19 and (b) appropriately chooses Q from Noe Therefore,
In N where the second inequality uses Lemma 30.
& In N
ei KE/8 s O(d) polylog(d, K, H Cr, Cu. Bd, Ct. Cx, x1
Definition 13 (V function class). Let VT, Vb and Vi denote value function classes such that
V/ V5lk) R
n m M. (m)) and Q E 2
VX : R
T f1 (कX) and Q e 0%
and V { [1800 R
m T TT (x and Q E 0
where v([n](s)= Σ m)als) <ln 8)) vs S
We let No .e and N be the e-covers of V%, Va, and V/ with the distance metric dist Lemma 32 (V covers). When Algorithm is with p and 0, for all h, the following statements hold:
i1) For all (ks, h), for any
E [0, Cx), and for both ग = (K).A and π = T8 we have:
((), E Vr,
Vu.a
E Vb, and V (k),h V/.
(K).
(ii) In W (d²)) polylog (d, K, Hy. C, B,, C,, Cx,E! 0x,E-1,,=1)
In No (dd) polylog (d, K, H4, C, Cn, By, Ct, 11,
and In N =Odd) polylog( (d, K, H Cr, Cu. By, Cx. xK-1)
Proof. The condition (i) immediately follow from Lemma 29 and Lemma 31 with Definition and Definition 3.
34

---

We prove the second claim (i). Let Q 2% and @ No where Ex 0. For any two
T, nt AT:S- + 9 (A), for any s, we have
Σ
((al))(Q(s,)))) =Int(als))
Σ m(a (Q(e,))))
-
DEA
aEd
Σ
r (({
Σ [ Σ
s)Q(s,a)
T(a s))(s, Σ
aEA
aEd
aEA
oEA
+ k
Σ
T(a 8) InT((aa)) x(a (n
aEA
= (F)
S Σ x(a (s) ((+,((s))) - a) +1|-(-1 #( (1)1) @ (x(
aEA
Se"
SHe
SE" + H.ll (s)( -T( s1)1 + (T) (())
where the second inequality chooses appropriate Q We defined entropies of a and म as (x) = Enea T(a 8) In s) and (#) == EnEA ((a 8) In in |3), respectively.
The remaining task to bound H (- 8) #- +)] + ((H - (=)). When π = n2, choosing ग = π trivially bounds this term by 0. Thus, we only consider the case when I,, i... (. s) = SoftMax (2 (s,,)s
-)) with Q E 2i We also consider T 8) = SoftMax [ (s..).
with Q E No0 where E > O. For the entropy gap, we have (T) (T)
Σ aEA
M(a 8) In r(a 8) - F(a 8) In (aaaaaa 8)
Σ (T s) - (() In + Σ F(a F((a|s(lnT(() () - In s))
aEA
<| (8) 7(- s))1 maxin 8) + max T 8) - In |)
1A3 IA.
|)( (-
maxinx(a max
Q @0
max. (2.a T (s,aa] by Lemma 19
Sea
(SmaxIn (x) +
where (a) utilizes a decomposition similar to the proof of Lemma 19, and (b) chooses appropriate Qo. Finally, In x (a s) can be bounded as
max (a s) max (s, a) - In Σ exp (spp('00 ('0r(s,0)) <
B.H + H, + C.H
K
where the last inequality is due to Definition 11. Therefore, have
8 (B 2H, + C2H)
H- s) #(-1s)]l - Sea 2
k
Finally, by setting e" = and 00 =e/27, In 12 is bounded as: In v < In [ e/22 + + In LV 8/2H. (dF)) polylog(d, (d, K, Hr, Cr, Cus By, Ct Ex x1x=))
35

---

where the second inequality is due Lemma 29 and Lemma 30. The claims for In N
and
In Ne 2
can be similarly proven.
E.3
Good Events and Value Confidence Bounds for Lemma 4 Proof
Lemma 33 (Good event 1). Define &1 as the event where the following inequality holds:
E
(8)
a
(A())-1
8/2 a
(k)
(k)
(k)
k=
2
K
H
(
(R)
a/ (k))
12
+
4H In
2KH
t/
(A))t)
k=
If Algorithm 2 is run with p 1, P(6)) 2 5
Proof. The claim immediately follows from Lemma 11 with ||0112 S 1 and p= 1.
Lemma 34 (Good event 2). Define Eg as the event where the following condition holds:
For all k, h and for any V E Vh++ V E Vh+i and V E Vh+1
((k) (( h
Pn. VM) (s,
- CC (8, V(h,8,0) E [1, H] x A
(( Ph) vu) (s, 2)
s C (s,a) v(h, E [L, H] x S A
and ((D(t) Pr. vl a)
S (0 (s)a) v(h,s,a) E [1, H x S x A.
If Algorithm 2 is run with p C. Ö(dH,), C, O(HH), and C Ö B4), we have ((2) 2 1-28. 28.
Proof. Using Lemma 28 with Ni/ke' Vi+1
with probability at least 1 6, for any (k. h, a),
(( h
(P( Ph) vM (r)
N
Phis J
1 *1(0(s,))) (1)5)-1 (1))))
VddH* VdHx + +HH V2 In(2K) + 2H, \
d
1/K
+
E| (1)(s,a)l(( a)ll
(A ()l((
(9) .(dHH,) 2 (6(s,,))((ss)) -Cr
where (a) sets = = 1/K to 2 and uses Lemma 28, (b) uses Lemma 29, and (c) set sufficiently large C. Ö(dH)) and uses Lemma 15. The claim for Vh+ and V1411 can be similarly proven. O
Lemma 35 (Remove clipping oie-side). Under E2 for any (ke, h, a), and for any X E [0, Cxl. for both π = ( and π = n we have
Cf + (P V (1) (8, (Pa (PAVTH)AHIKK)) (s, 20,
- -C,uf(t) (s,a) (p(l)
yau ((t),
(s,0)) (s)a) (PaKTTy (s) S 11 h,
and (H) + (p (2) ) (s) > (P.Vii) (1),6+)) (s,0)20 20
36

---

Proof. We have
Cr
(K) (s. + V (iinttlli (s,
2 PR P((b) (W ( (4) (xi (s.
w
2 Pr - P/(h) (M),
P (1) (s,a)
h
Ps V (k),
(s, 20,
where (a) is due Eg with Lemma 32 and (b) is due to 2 0 and by the definition of V
(k).
The claim for V (k),6+1 can be similarly proven.
For V +1) we have
C (s) + (P/ LTo L(k),t+1 ) (s,a)
(p())
h - Pn.) [kb)iie+1 (s,
) + LTh
((),,++)/ (v)
S (pi)) - -Ph) V Visee (6),411 (8, + (p(k) VTe. (k), (8,a)
Ps Ph (k),h+1 (8, a) S h,
where (a) is due to &g with Lemma 32 and (b) is due to u S 1 and by the definition of V
(R),,+1'
Definition 14 (Q estimation gap). For any h k and II, define 85. (K),,)) (k), SSx A R be functions such that:
8th (k).i clipf CriRht + V 0, Hr - Hn hm
8T. ( (P.Ltt),nt1) clipp -Cug(h) + +(/h (1/ [ - -i)
(K),A
and 8 clipp (c/.8h)) + (F% ((A ((lAa1) ,, BH - -n]} -H - (Ph (in)(()))+))
(k).A
It is clear that these functions satisfy, for any (Tt, k),,
[he = Qp,h
T. (A)
[x],
2 = Pp.
(K)
and Ti6) QPA.A
a. 8,0,0000
(11)
Additionally, let A (k)
A (k)
and
(k)
be function classes such that:
(A) 8 [1, H x A
R
8 S min ((, , H 1in vh the [1, m1
(kk = {8: ::[11, x S x A R
0 < 8, S min
(kk) 1 - hn vh E [1, 2C h
and A == [8: x S A
R
0 < 6n < min
2 8 (k) B (H - h)) vh E [1, m1
Lemma 36. Under E2, for any k and for any X E [0, C3). for both π = n (b),} and . = ntl, it holds that 87.5 (K), E (A)
(K) 8T.u E Aa!)
(k) and 5t.1 E A (k)
(k),
Proof. (k), (s. a) S H - h clearly holds. Additionally, we have
(s,)) (c)
PAVTA (K)) (s,a) max{
+ (p (Mj (s,0),))
P (hnLth) (s,0) + ( ( (p( (in, (3,a)
@ (CuBb(1) (1) (s) + (Pn ((0)) Vinu (R),4+1 (s.na= (3,00) S
2C,, (1k)
// (8,a)
37

---

where (a) is due to Lemma 35 and (b) is due to e.. Finally, note that
on (5,)) (k), (8, a) - max { -Cn (s. + (phhl [id)imn)) (o, a), }}
Ch (s, + (P (s, - (P/h)) V (innntt) (5, 20.
20 by 62
This concludes the proof for 8 (k),b, The claims for 8 6 and 8T.1 can be similarly proven.
Lemma 37 (Restatement of Lemma 4). Suppose &g holds. For any and for any X E [0, Cxl. both π = (16), and = nd, we have
VV VV.r+2C.B6M)
PpPh S Q(),, I SQph 2
P.h S (R).b P.h
V..BB,000)
ni S VV
(k), S Pp
+2,
S {Q(K), S Qpp
V VTN-2CC,30)
V (K).A
V Ph
I 2QE S Q (k),h
P.h.
Proof. The inequalities for Q functions directly hold by Equation (11) and Lemma 36. For the utility V function,
Vall V-T( (b),A (s)
P.A.A
(s)
Σ
(a(als)
(a s)
(k),
(a s)Q
(s) 0,
aEA
where (a) uses Equation (11) and (b) uses Lemma 36. Similarly,
V..u (R), (s)
Vihh VT.u-2C,8(4
Σ
T. (a 8)
(s, (TT - (k),
-Q7a 1T.U-2Cungty (s,
=
aE
1 +20,,0(1)
Ta pp
(s) 2 0,
aEA
where (a) uses Equation (11) and (b) uses Lemma 36. The claims for r and f can be similarly proven.
E.4 Proofs for Zero- Violation Guarantee (Section 3.2.1)
E.4.1 Proof Lemma and Lemma
Lemma 38 (Restatement of Lemma 6). Let f.g: [1, H] S A -> TR be functions and let > Given X 2 0, let x be a softmax policy such that
A s) = SoftMax (
Then, V - (s1) is monotonically increasing in A.
Proof. Let W- (wp. [1, x A [0, 1] E II} be the set of all the occupancy
sures. Let L -RRW- R be function such that:
wn(s, a)),.)) (g)(s, kwn(s, In Wa(s, L
L(,,w)
Σ
En'e Wh (s,
We first show that L strictly concave in W. Let
wp(s,
# : w E W
Σ
wi (8. In Σ En'AA EveAwhhs, a)(s,ad)
[.8.EE1.H)
38

---

be the function representing the second term of L. Then, 10
He (aw' + - (1-a)ww²
(w a) + (1 - a)
Σ (arw) (8, + (1-a) log a wh (8, + (1 (x) La Wh (8,
1,8,a
(w))(s,))
(1 0 / 18,
Σ Eaw (8, log a aa wh (s,
Σ(1- log (1 a Eo w (s
b,s,a
h,e,a
a (w + a) (whh)
for any w¹, 2 E W and a E [0, 1], where (a) is due to the log sum inequality (E, x;) In E 1 Σ, x, In x: for non-negative x, and yı. Since (a) takes equality if and only if w w² H is strictly concave. Consequently, (),, w) = h...see (n(8, ()a((s + (g, - k. K. (ww) is also strictly concave in W.
Let WA arg wax W (A, w), which is unique maximizer due to the strict concavity. Define (()) = max L(A, (A, w). Using Danskin's theorem (Lemma 10), L()) is convex 0A Lt. x w/ ()))(s Since L()) is convex, its derivative is
and (A5
non-decreasing. Therefore,
(2) ax2
0
E
(9 2 0.
(12)
Ox
Since T is the softmax policy, combined with the one-to-one mapping between occupancy measure and policy [35], the well-known analytical solution of regularized MDP [15] indicates that w corresponds to the occupancy measure of π Thus, due Equation (12), it holds that
0
0 VP V (s1)
0
Σ
wA (s. Ox
ax
This concludes the proof.
Definition 15 (Softmax policy with fixed 8). For any k E E = (8",8",8t E 1 XA! (1) XA
(2)
and À 2 0, let 6. E II be a policy such that
8.2 (. 8) SoftMax Th
( (0.0ii, 1, +at (8. Qph r+8" (1)(ss) + XQP 50 (8, (6.)))
(0p%) K
Lemma 39 (Existence of feasible A). Suppose K I B For any and for any e
(k)
A (k)
x A there exists a 2 E [o, +1) such that, v u- (s1) 2 b holds for
any À 2 1
Proof. Throughout the proof, we use shorthand و = Byg((k) + 5t + r + 8". Consider the following entropy-regularized max-min optimization problem:
max min nell A20
P.i [k](s]) +
V.1. V. (s1) - b-
+ x² {
min max P.I [<](s)) + X fell
VPI. Vita=5 (s1) -
+ == x²
(13)
where the equality holds by the strong duality of regularized CMDPs (see, e.g., Appendix C.1 in Ding et al. [11]). Let (7, X) be saddle point of the problem, which is ensured be unique thanks to the regularization. We first show the analytical forms of (7, A).
1hTis proof is based of Lemma 14 from Ding al. [11]
39

---

Analytical forms of (T. x). Due to the strong duality, we have
Vei A(u-8") (s1( v A(a 8") [x](s))
max
nell
Since the left-hand side an entropy-regularizee optimization problem in an MDP, the well-known analytical solution of regularized MDP indicates that [15]:
f- 8) = SoftMax (OpA [e](s,)) + AQ (0.p=""(s.))) (s.:))
Th
(14)
where the last equality is due to the definition of A.d. Additionally, due to the strong duality,
À E arg min VPn [s1( +
v P1 (s1) -
5 )
+ Ki x2.
A
4
2
Since the right-hand side is a quadratic equation on X, we have 5 Vū.u- (81)
b
(15)
4
p2
upper bound. Next, we will show that À is upper bounded by constant. We have
2B +1)
vp.i [m](ss)
1 5
b+
V - (s1)
2x
4
20
vpl [x]( 2
Vp:
(81) -
5
+
2
xx²
4
vz"l"" [x](ss) +7
1p,,1 V N--6"
(51) b 5
+ X2
2
2 X
Vp. ((1)) -
5
vas 20
(81)
1
P.1
23E/4
SE/2 since kELL
where (a) is since (b) is due to Equation (15), (c) uses Equation (13). By reformulating the inequality,
||
((K) + 5t + 5r
< B₁ B,H+1+ (H+ 1)(B +1),
AS 8H2(B +1)
(16)
Constraint violation of n 6.A Finally, we will show that for any À 2 X, 8.6 guarantees zero constraint violation. Due to Equations (14), (15), and (16), we have
b + 5 5.7 uu-0" (51) I H (B+ +1) Vp.
x
4
E
which ensures the small violation of ह, when < 1. Since V
(ss) y="",,"-8"(s is monotonically 8elf (B, Therefore,
8.. (s1) 2 bb
increasing in À due to Lemma 38, for any 2 X, Vp1 P.1
{
by setting S +1] we have Vp. S. ,--5"
(s1) b.
8H2 (B +1)
Lemma 40 (Restatement of Lemma 5). If Algorithmm 2 is run with p 1, C2 >
and
K < +11) under &g, it holds Vx00, . (s1) 2 for any C
(k),1
Proof. Due to 6g. it holds that
8 = (o)))
(k), (K),
E A (k) x (A)) x A (k)
(k)
According to Equation (11), this 8 satisfies 5,0s o (A),Oa where 5.0x is defined in Definition 15. Therefore, using Lemma 39, V (K)
((81) > b. This concludes the proof.
(R),1
40

---

E.4.2 Proof of Theorem
Lemma 41 (Bonus summation bound). If Algorithm is run with p 1, under 61 and E2, it holds that
K
V (ggh), (si)) < 2112dln 1+ 1+ ②) + 411 In
2KH
8 = (
R=1
and
Vir (A), ,gth0
(81) s H 2dln (inn1+++
1+
K)
4ln
2KH
Ō (Haa))
8
Proof. We have
K
K
H
y 00
(81)
E
(k)
(sh, an)
sh. an n: x(10]
P.1
Rm
E (1)00) (5% (sh, and
sh sh an ~ r(lil) 2
H
k=
H
( (b an)l (astt) (n)))(
8h, ~ (())
-1
k=1
2H
((5h))
(K) (1)
Oh
4H2 - In 2KH -
112 (A!
4
8
K
2KH
2d In
4H2 In
d
where (a) is due to Jensen's 's inequality, (b) is due to E1, and (c) uses Lemma 12. The second claim follows by:
K
K
Σ
Valu 1000 (51) 09
H HvK 2d In
1+
K
4
2KH
where (a) uses Cauchy-Sehwarz inequality and (b) uses the first claim.
Lemma 42 (Restatement of Theorem 3). Suppose Algorithm 2 is run with p 1 and &1 and Eg hold.
Then,
64C2Hdd C
2KH
|4| <
In
=
8
where the last equality sets C, = (dH))
Proof.
Using Lemma 41 and Definition we have
20,000) (si)) s 80H (1+ K) 4) + 160 In 2KH
[
kEZ
Therefore, have
32C H2d
K)
64
2KH
64C2H2d /2KH
In
1
+
In
<
In
d
22
5
22
41

---

E,5
Proofs for Sublinear Regret Guarantee (Section 3.2.2)
Suppose the good events n &g hold. We decompose the regret as follows:
Regret (K)
K
Vp1 V (81) - -Vp [ (81))
VP1 (81) - -VPl" (T(()
+ Σ
VP - V (51))
kEU
kELlo
SUIH+ +
Σ
vor) V(ky, ((lss"))(())))
kENO
kEwO
=0(d8 + Σ
(k),2
(2)
[n:((s))
Vpl "110((1))
+ Σ
V V - Valli " (n)(s))) + *KKH A
kEUc
kEVO
2ō(CH' ?) + 2C, Σ
vp .000)
(s1)+ +
Σ
(s1) - V V(s),1 (k),1 [n]((s)) tNKHIAA
keuro
kEllc
(17)
where (a) uses Lemma 42 and (b) is due to Lemma 37 with &s. Under & n 82, ! can be easily
bounded by Lemma
I S C,O(HVaK) S (HH.81/2K
(18)
where the last equality inserts C, O(dH,).
E.5.1 Mixture Policy Decomposition
We upper bound ② in Equation (17) by the mixture policy technique.
Lemma 43 (Mixture policy's feasibility). Let (k)
For any le U and
*+2V,, 20.8th (o1)
E [0, (+)) x" defined in Definition 5 satisfies V v==,u-2C.,"" (s1) 2 b.
Proof. We have
(51) b
=(1 a) Vp.1 R (81) - b) + a (- (61)-1)
21 a) + a - (81)
where the last inequality holds because Pp ye" 20, (s1) b 2 0 holds when P.1
20x
(8)) I
due to k E 40. Thus,
a S
E + 2V 2V222
20 gik)
(s1)
P.I
Lemma 44 (Mitture policy's optimism). Let B, > H. Lemma 43 satisfies,
For any k E 40, T with a from
Ç
(k())) .t g1,0) (s1) 2 (s1) and VP,.
v=uul) n 2(1
(s1) 2 b.
P.1.
42

---

Proof. The sufficient condition that pp1
(51) 2 vp11 (s1) to hold is
(1- a) (irj (V ( - Vijl (81) ,005)
V 1t (81) - Vp-"(si (81)
B₁ 2
P.1
V ,866)
(51)
a- P,1
g(8) (81) + a aV P.1 (81)
P,1
P.1 *r (81) - Vpr"" it ($11
V ,80k) P,1
(81) +
a
Var .(k)
(81)
I-a P.1
By inserting (A)
into a, i.c.
<+2y P.
20u8(1)
(s1)
I-a
21 p1
sCulkk) (51)
1r (31) Vir (51)
40
V it (8)) - V (s1)
B
P.
Vaa ,00)) p,1
($1) +
V
,80))
(81)
p1, 2V g(0
(51) +
4C. P11
(01)
Thus, when B₁ 2 HC,H it holds that ( from Lemma 43.
(k) r+
(81) 2 Vp (81). The second claim follows
P,1
We are now ready decompose
2 Using Lemmas 43 and 44, we have
(s1) - ( ((J)i (x)
Σ
P11
kEU
_B,,800)
(81) + Vpl [[n[(s)) - ( ((())""(
P,1
kezl0
Σ kEUOo
BBB(0))
(81) + Vp,1 Veulh) (b)
"[n](s]) + x (R.7) yoult) - 20-00 (81)
Vpl
P.1
(19)
(k),1 (81) (81) - Va " [n](ss) (x(s)) - (R.T) yo ($1)
(A),1 (si) + Σ x (K.T)
ya u (s1)
V a 20200 (81)
VP1
kelc
keue
where X (kT) is defined in Line 10. Using Lemma 37, the term 4 is bounded as
S (A), ((B +2;
(s1)
Using Lemma 41, holds that
S SB 2C, 20,)
[ ((
(20)
where the last equality inserts B₁ C C. Ö(dH), and C Ö(HH We will bound and 55) separately.
E.5.2 Optimistic Bounds
Lemma 45 (Optimism in composite value function). Suppose Eg holds. Then,
(t) (si) + Vil "[x[(s)) + x (k,T) yon a- 20, (8i)
3 Σ kELLo
( BBg(()) (11(3)
(K).1 (81) V (
[=](s))))))))))))))))<))))))[[ - x (k:T)) ) (82) S 0.
43

---

Proof. Using Lemma 18, for any & E uP we have
vith (K)
B,a(k)
(51) + V 1
(0),1 (x](s)))))))))))))))))))) + (4:T)
(k),1
[(b),1
(81)
BBD
(81) - ygale
"[K](81) - (1:T7)
yoall)) 20-00.00)
(81)
P1
P.1
PV
(() (4)
(s1) + p,
(4) S ($1) + x Vp1
20,
(51)
P,1
where /: [1, x A + R and f 11, x x A +
R are functions such that
()(8,a)= = Σ
(a) (a {s)
a) + x (k.T)
Q (+) " x =nn (a (a s)
Th
aEA
Qii) (1,),
(s, a) + (h Q o (s, (s, - klu (a s)
Th (al
(k).
aEA
( (1)
x (
(k)
is well-known that the analytical maximizer of max D(EAT(a)(x) xlll(aa) is
SoftMax(xx())). Therefore, the function f is non-negative and thus V S (s1) 2 0. On the other hand, using Lemma 36, we have
(s a) = gmth) , (R.T) 50 N (6) (k),
2 2C
(k),
Therefore, it holds that
VPn
(4)
82 (s1) + x (k.T)
Vp 20, (s1) 2 0.
By combining all the results, we have 5 O.
E.5.3 Bounds for Bisection Search
Using Lemma 43, 5 is further bounded by
5 Σ (k.T)
(x((t) (x),1 (s1) Vx (u-20 (81)
kELLO
Σ (k:2))
(s1) -b) CA Σ
keu
kENl
We bound the last term using the bisection search Algorithm 2. Note that we focus only the case y- (2).0,
(k),1 (((1) < b and Va (M),0xxx
(k),1 ((s1) 2 b due to Line 4 and Line 3 in Algorithm 2. Due the definitions of X (k:1) and X (k.t) in Algorithm 2.
((s)) < and (a (k),1
((s)) 2
(K),1
hold for any E [[,7]. Therefore,
vall)as (R),1 (s))
5 SC Σ
((si)
(K),1
REZLO
To bound the right-hand side, we derive the sensitivity of Vt
.e (s1) with respect to X.
(6).1
Lemma 46 (Restatement of Lemma 8). Let X = x(1+ + and Y =
8(H., + B, H+H) For any and [0, Cx), it holds that
ya ya 1 (81) - 1000011 10 ((s1) S H22H.. (k),1
(6),1
44

---

Proof. The proof is based on Lemma 2 from Ghosh et al. [18]. For notational simplicity, we denote == (k)), and n'= == (K),a++ Additionally, we use shorthand:
uf ==
% =
Pieh [xc]
- T(R) [n]]
Vitiia 11.-
% Qie), -Q(1),
U
(K),N
((k).
For any h, we have
0/i = Th Q (k),h, [x] - The -TS
S HNllITA - r/-l1 + 4
of S B₁ H Th - -1/1l1 + tgh
o I =| - x/ll12 + oh
Since Th and T/K are softmax policies, using Lemma 19,
|T Aill 5 8 K. (()), + [(G),[(]] + 2Q
Thi J (2 + +
9h + oh + Cxah + +
Additionally,
sh <
((k)
Ph
Vi (1),++1k] - ((AiAtil))
|I
S Kob+1
x
a% S
p(k))
(vrst
(k6,,441 (R),441- - Volit
S Krb41
h
(16).++))
(VT.
σk <
h
(k),b4+1 (K),
< Kuht1
where we used the fact that, for any V: S + R.
k-1
pr (5,a) = 0(s, a) T (A (k)
Σ (s5) ((
k-1
x (A (k) -1
Φ h
0
(1)
|
s k
2
By combining all the results,
2% S K
8H
+1
+1)
wht1
+ K K
8H 1/111
SH KK 1h41
8H eH K
0/ < K
8B+H
1/1t1
+ K
88B
+1) p/111
+1)oh11
+
8B,
1h+1
8B, eHH k 8H
8H
K 8H +
8H +1 Cx +K
2/ < K
1/41
+ eH. k
k
K
Let = K (1
S(1+0X(H, + B, H+)
and Y == 8(H, H H+H) Then,
x
2% + 0/ + 2x < X( + thet + v + Y
< (2 + w/42 18(42) + XY He + YHe
< (x +...+ X + 1)YHe
45

---

We are now ready to bound ( Applying Lemma 46 to 5 we obtain the following lemma. Lemma 47. When -HH). it holds that
(=
( ((s1)
C Σ
(((1) Õ(1).
(H),1
(k)1
Proof. Due the bisection search update rule, x (k.T) (1::3) =2 Thus,
v (k),1
( "((1)) X X"CCKHHY2-
CC
Σ
((1) (k),1
where the inequality uses Lemma 46 with X and Y defined in Lemma 46. Thus, 2 5 O holds by setting T H polylog H.Y). This concludes the proof.
are now ready to prove Theorem The proof under the parameters of: p= 1, O(Udf, C = OdHH), C = (3 B = (dH = -(< O(H), and Cx =(
E.5.4 Proof of Theorem
We condition the proof with the good events 61 n & which holds with probability at least - 36
by Lemmas 33 and 34.
In Algorithm/ 2, the deployed policy switches between лo E ITst and the softmax policies. Since
Algorithm deploys the softmax policies only when v "(s1) b, due Lemma 36 and the
(k),1
good events, all the deployed policies satisfy n IT for all k [1, KJ. This concludes the proof of the zero-violation guarantee.
Next, we derive the regret bound. Recall from Equation (17) that
Regret () S 9) +KHHh s () +0+ +0+ OV(K),
where the second inequality is due the value of s.
Using Equation (18),
1 D 16001
Using Equation (19), ② can be decomposed as:
5
Each term can be bounded as:
< by Lemma 45
H (/5/25-1VK by Equation (20),
s 01) by Lemma
Finally, by combining all the results, we have
Regret K) < (d  + (
This concludes the proof of the sublinear regret guarantee.
46

---

F Numerical Experiments
This section presents empirical results supporting Theorem 4, which guarantees VK regret and episode-wise safety of OPSE-LCMDP. We also evaluate how often OPSE-LCMDS deploys the safe policy x², a key technique for achieving sublinear regret (Theorem 3). All experiments were conducted within 30 minutes using eight Intel Core CPUs and 32 GiB of RAM.
The source code for the experiment is available at https: /gghtuttubb......gg com/ conn/matsullaa Mpisode-Wise- Laliiss-Saae--iee-----e Linear-CHDP.
We compare OPSE-LCMDP against the previous state-of-the-ar linear CMDP algorithm by Ghosh et al. [18] and the tabular CMDP algorithm called DOPE [8]. Ghosh al. [18] achieves
Ō(VK) bounds for both regret and violation regret, and DOPE achieves Ō(VK) regret with zero episode-wise violation.
For sequence of policies {TT ]EE[L,K], the violation regret is defined as:
Vio(K)= = Ek= max {
(b- Vr.1 /= (x1). 0)
(21)
Clearly, all the policies satisfy ((k) II= the violation regret is zero.
Additionally, we also report the performance of a uniform policy defined by TT.. [8) = 1/A for all h, s, to highlight the sublinear regret of our algorithm.
Implementations of Ghosh et al. [18] and DOPE. Ghosh et al. [18]'s algorithm can be implemented similarly ours, with few modifications: remove the πh deployment trigger, eliminate the pessimism compensation bonuses by setting Cj B = 0, and apply an optimistic constraint bonus instead of our pessimistic one (i.e., use negative sign for C.). We use C, and Cu to denote the bonus scaling parameters for Ghosh et al. [18]. See Algorithm I of Ghosh et al. [18] for further implementation details.
The DOPE algorithm can be implemented in tabular environments with a moderately small state space. computes the policy ((k) by solving the following optimistic problem:
T (h) E max max V #EIl P(EPIk)
VEr++,,0t ($1) such that -u P
(s1) bb,
(22)
where (/()) (s, a) denotes the bonus at step the state-action pair (s, a) and p(k) denotes the confidence for the transition kernel. Specifically, using the visitation count'! (k) Σ [(s
nh (s. =
(k) 0i a, sh4 s'), the bonus and the confidence set are defined as
(()) (s' s, a) ((()) (s' s,
( (s.a) = Σ
Nh (s, s') where Tn (s,
(K)
(s,
S'ES
n (1) (s, n (2) (s,
(k) (x, a) = Σ
Th (k) (s, and (00) [8,a)=
Th
S'ES
For simplicity, omit absolute constants and logarithmic factors, and use this simplified form in all experiments. Further implementation details can be found in Bura et al. [8].
For each environment, we select the hyperparameters of each algorithm using heuristic adjustments to balance exploration and exploitation. To ensure numerical stability, we assign relatively small values to these parameters. The detailed values are provided below.
Synthetic tabular environments. To evaluate the exact regret values, we conduct experiments on tabular CMDPs with a small state space size. Tabular CMDP is the special case of linear CMDP with = [S] and allows us to compute the optimal policy x by linear programming.
"1[E] [b] equals 1 if the event E is true, and 0 otherwise, For two scalars a and 6, we use shorthand a V b max(a,b). b}.
47

---

We instantiated CMDPs with = 3.) 4, employing a construction strategy akin to that
of Dann et al. [9]. For all 8, a, h, the transition probabilities P& (- s, a) were independently sampled from (0 0.1). This transition probability kernel is concentrated yet encompasses non-deterministic transition probabilities.
The reward values for the objective (s a) are set to 0 with probability 0.1 and to otherwise. The utility values for the constraint un (s, a) are assigned in the same way. The initial state s1 is randomly chosen from S and fixed during the training. The constraint threshold is set as b = 0.6 max+en Vp11 (s1).
We choose the hyperparameters of the algorithms as follows:
OPSE-LCMDP: C, = C. = Ca = 1.0, C₂ = 300, B, 1.0, and K = 0.1.
Ghosh al. [18]: C, C₁ 1.0 and 0.1.
DOPE [8]: C, = C. = 1.0.
Media Streaming CMDP Environments. As a realistic environment, we also evaluate algorithms on the media streaming environment from Bura et al. [8]. In the environment, a wireless base station (agent) transmits media to a device using either a fast or slow service option, each incurring different and 2, respectively.
costs. The slow and fast services correspond actions
The fast service succeeds with probability f41, and the slow one with (42 = 1 independent Bernoulli distributions. At each environment construction, 141, where both follow randomly sample 141 from [0.5, 0.9). Packets received at the device are stored in a media buffer and played out according Bernoulli process with parameter p. We sample p uniformly from 0.4].
Let Ap, BA E 1) denote the number of arriving and departing packets, respectively. The media buffer length represents the state, and transitions 8h+1 = min max (0, Sh, + AA, B }. L} where denotes the maximum buffer length. We set = 5. |S| = + 1, and H = 4. The initial state is set to $1 0.
The objective to deliver enough packets the buffer while limiting the use of the fast service. Accordingly, the agent receives a reward (s, = {s 2 0.3L.) and incurs a constraint utility ua(;,a) 1 (a- = 1). The constraint threshold set as b 0.6 max Vp,11 (s1).
We choose the hyperparameters of the algorithms as follows:
OPSE-LCMDP: C, C, C.- = 2.0, C2 = 300, B, = 1.0, and 0.1.
Ghosh al. [18]: C, C, = 2.0 and k 0.1.
DOPE [8]: C, C. = 1.0.
Synthetic linear environments. Building on the experiment by Amani et al. [4], we randomly construct linear CMDPs in which the number of states is larger than the feature map dimension. We test the algorithms on environments with 5 = 100, A = 3, d = 5, and H = 4. This setup has a relatively large state space while still allowing us to analytically compute the optimal policy and exact regret.
For each (s, a) E S x A, the feature vector (bs, a) E Rd is sampled from Dirichlet 0.1). Recall from Assumption 2 the definition of μa = (4) m4) E RSd For each (h, E [| x [1, we sample μi, from Dirichlet(O.1,, (p(s
0.1). With these μ and Φ. (- s, = 1 becomes we set Pa((s) s, = (s)TTss(((s a). This construction ensures that (, valid probability distribution for any (h, 8,a).
For the reward and utility functions, we sample both 0% and 0% from a uniform distribution over [0, _]d The reward and utility functions are then constructed such that ( a) = (0%) ((s a) and (s. a) (0%) ((s.a).
The initial state 8ı is randomly chosen from S and fixed during the training. The constraint threshold is set as b- 0.68 maxxem V7 (s1).
48

---

Synthetic Tabular
OPSE-UMMDP (Oun))
OPSE-LEMDP (OUSI
Choch at (9824)
Ghoch at (2021)
Total number of of deploymentt
10.
+
+-
Unitm Felley
DOPE
Violation Reggret
-+- DOFE
+
Unturm Folley
10-
25-
Regnet
0.4
15
0.0
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
5.0
1.0
102
Episode
K1P
Episode
K10
Media Streaming Env
Total number ot deployments
Unifomm
Vielation Regret
Regfet
2.5
3.5
10-
0.0
0.2
0.6
0.6
0.0
0.6
1.0
10*
121
12
10
Episode
Episode
Ecisode
Synthetic Linear Env
K10F
+207
CPII-LCMDP (Oun)
OPSI-LINEP (Dunt)
Total number of mmmm deploymeent
800
Choah et (2024)
Shoan et at (2024)
+
Unitomm Policy
1.2
Unitorm Pallcy
Viciation Regret
600
1.0
Regret
500
300
0.4
100
0.0
0.2
0.4
0.6
0.5
3.0 0.0
2.2
0.6 0.0
1.0
1.2
104
Episode
x10
Episode
x10
Eplsade
Figure 1: Numerical comparison of the algorithms the synthetic tabular environment (Top), the media streaming environment (Middle), and the synthetic linear environment (Bottom). We do not run DOPE in the linear CMDP environment due its computational intractability (see Remark 3). Left: regret (Equation (6)), Middle: violation regret (Equation (21)), and Right: total number of sf deployments in OPSE-LCMDP.
Remark 3. We do not run the DOPE algorithm in this linear environment due to its heavy compu- tational cost. Using the extended LP technique introduced by Efroni al. [13], the optimization problem in (22) can be reformulated as the following standard LP problem:
minx
c T such that Ax b and Gx h
where parameters are defined appropriately. This LP involves HS2 A decision variables and more than H A number of constraints (see [13] for more details). Therefore, in our synthetic linear CMDP experiment, the matrices A and G require at least 10t0 entries, which is computationally intractable in practice.
Figure shows the performance of the algorithms, averaged over 10 random seeds, with regret plotted on the left, violation regret the middle, and the total number of deployments on the right.
Results.
Across all settings, both OPSE-LCMDP and the algorithm by Ghosh al. [18] exhibit sublinear regret. However, while OPSE-LCMDP maintains zero constraint violation throughout, Ghosh al. [18] con-
49

---

sistently violates the constraint, leading to increasing violation regret. These results empirically val- idate Theorem 4, confirming the ((VK) regret and episode-wise safety guarantees of our algorithm.
While DOPE achieves sublinear regret with zero-violation, is limited the tabular settings where S is small, as described in Remark 3. This highlights the computational tractability of our OPSE-LCMDP in large S, which supports Remark 2.
Finally, the right plot shows that OPSE-LCMDE explores the environment using nf primarily during the early stages of training, and stops deploying it after approximately 10 episodes. This behavior supports Theorem 3.
50


Reviews:
[{"review_id": "4Cr7dBzo0S", "reviewer": "Reviewer_YdzS", "summary": "This paper investigates the constrained MDP problems with zero-violation guarantee. The main contribution are the algorithms for linear bandit and linear CMDPs based on the linear function approximation and the optimism-pessimism exploration method. The novelty of the algorithm lies in the a new deployment rule and the composite softmax policy. The algorithms are also computationally efficient, achieving a polynomial computational cost in parameters and independent of the state space. The authors further prove that the algorithm is the first result achieving zero-violations and sub-linear $\\tilde O(\\sqrt{K})$ regret.", "questions": "Can authors add the comparison with Roknilamouki's algorithm? It seems that their algorithm has similar theoretical results and also zero-violation.", "limitations": "See the Weakness in **Strengths And Weaknesses** part.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n1. The algorithm is novel and is the first result that achieving $\\tilde O(\\sqrt{K})$ regret and zero-violation.\n2. The algorithm achieves the polynomial computational cost on the parameters and is independent of state-space.\n3. Numerical experiments further validate the performance of the algorithms.\n\n**Weaknesses**:\n1. The algorithm is only suitable for the one-constraint setting; there are often multiple constrains in real problems\n2. The computational time is still dependent on action space, and the algorithm will still be computationally inefficient when meets the large or infinite action space; Bisection search may also time-consuming when the space is large.\n3. The regret has higher dependence on parameters $d,H$ compared to other similar algorithms.\n4. The paper could be clearer; it's a bit messy", "was_revised": true, "final_justification": "I appreciate the authors' efforts in the rebuttal and they have addressed my concerns. I think this paper should be accepted, although it has some limitations", "rebuttal": "Thank you very much for the valuable comments. We here answer the weaknesses and the question raised by the reviewer. We would also be happy to provide further clarifications if suitable.\n\n## Weaknesses\n\n>*The algorithm is only suitable for the one-constraint setting; there are often multiple constrains in real problems*\n\n* **We remark that even under a single constraint, no prior work achieves episode-wise safety in linear CMDPs.** Even in the single constrained setting, existing approaches are inapplicable to ensure episode-wise safe exploration as discussed in Sections 2.1 and 3.1.\n* Note that one can certainly apply grid search for multiple constraints to search over multiple dual-variables; of course, the computational complexity will increase as the binary search approach might not work.\n\n* Whether our single-constraint limitation is fundamental or merely a consequence of current techniques remains an open question. Given that even slight changes to the CMDP formulation can render the CMDP problem computationally intractable [Feinberg 2000], it is possible that this limitation is inherent to the episode-wise safe linear CMDP setting.\nAddressing this open question requires further research, which is beyond the scope of this paper.\n\n* [Feinberg 2000] Constrained Discounted Markov Decision Processes and Hamiltonian Cycles\n\n---\n\n>*The computational time is still dependent on action space, and the algorithm will still be computationally inefficient when meets the large or infinite action space; Bisection search may also time-consuming when the space is large.*\n\n* To discuss computationally efficient algorithms for continuous action spaces, we need to make careful assumptions about the structure of the action space. Indeed, even in the unconstrained bandit setting, solving the optimistic problem becomes non-trivial when moving beyond finite action spaces [see, e.g., Lattimore 2020].\n* **Since episode-wise safe exploration is already a non-trivial challenge in the finite action setting, introducing additional assumptions for continuous actions would further complicate the regret analysis.**\nMoreover, much of the existing literature on linear CMDPs also focuses on finite action spaces [e.g., Ghosh 2024; Ding 2021; Ghosh 2022]. For these reasons, the continuous action setting is beyond the scope of this paper. We will add this discussion in the final version.\n\n* [Lattimore 2020]: [Bandit Algorithms Section 19.3.1](https://tor-lattimore.com/downloads/book/book.pdf#page=254)\n* [Ghosh 2024] Towards Achieving Sub-linear Regret and Hard Constraint Violation in Model-free RL\n* [Ding 2021] Provably Efficient Safe Exploration via Primal-Dual Policy Optimization\n* [Ghosh 2022] Provably Efficient Model-Free Constrained RL with Linear Function Approximation\n\n---\n\n>*The regret has higher dependence on parameters $d,H$ compared to other similar algorithms.*\n\n* We note that none of the existing safe CMDP literature achieves episode-wise safety in linear CMDPs, which is the main contribution of our paper. **As a result, our regret bounds are not directly comparable to existing results.**\n* More broadly, regret or sample complexity bounds under different safety requirements are generally not comparable, even if the problem settings appear similar. For instance, [Vaswani 2022] shows that the sample complexity lower bound for tabular CMDPs scales as $(1-\\gamma)^{-3}$ when small constraint violations are allowed, but increases to $(1-\\gamma)^{-5}$ when a strictly safe policy is required. This highlights how even a slight change in safety requirements can significantly impact the theoretical lower bounds.\n* Deriving a formal regret lower bound for our setting would be necessary to assess the tightness of our result, but this is beyond the scope of the current paper. While that analysis lies outside the scope of this paper, we will highlight it as an important direction for future work in the final version.\n\n* [Vaswani 2022] Near-optimal sample complexity bounds for constrained MDPs\n\n\n## Question\n\n>*Can authors add the comparison with Roknilamouki's algorithm? It seems that their algorithm has similar theoretical results and also zero-violation.*\n\nWe think that the Roknilamouki's algorithm refers to this paper: [Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces](https://arxiv.org/abs/2502.18655).\n\nTheir algorithm is designed for **instantaneous safety constrained** settings. Specifically, the instantaneous constraint considers that, for any step $h \\in [H]$ and episode $k \\in [K]$, \n\n$$\n\\text{(Instantaneous Constraint)} \\quad u_h(s_h^{(k)}, a_h^{(k)}) \\geq b\n$$\n\nwhere $u_h$ denotes the utility function for the safety constraint. On the other hand, we consider the **episode-wise constrained setting**. For any episode $k \\in [K]$, it requires that\n$$\n\\text{(Episode-wise Constraint)} \\quad V^{\\pi^{(k)}, u}_{P, 1}(s_1) \\geq b \n$$\nAs we show in Appendix A.2, **the instantaneous constraint is a special case of the episode-wise constraint.** Therefore, our algorithm can handle a more general constraints compared to Roknilamouki's algorithm.\n\nAdditionally, we remark that the instantaneous constraint can be overly conservative. For example, consider designing a drone controller that must avoid depleting its battery during an episode:\n* The instantaneous constraint restricts the controller from consuming more than a fixed percentage of the battery at each control step (e.g., 1% per minute). \n* In contrast, the episode-wise constraint only requires that the total battery consumption does not exceed 100% over an entire episode. This allows the controller to use more than 1% per minute as long as the overall limit is respected.\n\nFurthermore, while Roknilamouki's algorithm requires the set of features $\\{\\phi(s, a) \\mid a \\in \\mathcal{A}\\}$ to be star-convex (see their Assumption 3.1), **our algorithm does not require the star-convexity**. In addition, our **safe policy** assumption (Assumption 1) is weaker than their **safe action** assumption (Assumption 2.3) which assumes that there exists a safe action $a_s$ for each state $s$ such that $u_h(s, a_s) \\geq b$.\n\nIn summary, our algorithm is more general than Roknilamouki's algorithm for the following reasons:\n1. $\\text{Instantaneous Constraint (Roknilamouki)} \\subset \\text{Episode-wise Constraint (Ours)}$. Moreover, the instantaneous constraint can be overly conservative.\n2. Our method does not require the star-convexity assumption on the feature map.\n3. Our safe policy assumption (Assumption 1) is weaker than their safe action assumption."}, {"review_id": "JGtcG35fG1", "reviewer": "Reviewer_fTDU", "summary": "This paper investigates policy optimization methods where the policy must satisfy the constraint for all iterations in a linear CMDP.\nGiven access to a policy that strictly satisfies the constraints, the author proposed a method that achieves $O(\\sqrt{d^5 H^8 K}$ regret with high probability. To achieve this, the author add standard exploration bonuses to the rewards and utilities but provides a novel condition when to switch to $\\pi^{\\text{sf}}$. Additionally, the authors conduct experiments in the tabular setting to support their theoretical results.", "questions": "1. Is it a strict requirement that the initial state $s_1$ is fixed, or can the results be extended when $s_1$ may be chosen adversarially? \n2. In Figure 1, the average number of $\\pi^{\\text{safe}$ deployments appears consistent across different random seeds initially, but then begins to diverge around the midpoint of training as shown by the widening shaded confidence intervals (I'm guessing that this is what the shaded regions depict). What could explain this pattern of initial convergence followed by increasing variance between seeds?\"\n3. In Line 4 of Algorithm 1, how it be guaranteed to a $\\pi^{k}$ to always exist? It wasn't clear to me why Lemma 24 implies this fact.", "limitations": "Yes, the authors sufficiently address the limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n1. This paper provide solid theoretical results for a challenging problem instance and even recover similar regret bounds to prior work in the absence of constraints.\n2. The paper is well organized, and it was to first consider the problem in a simpler bandit setting before moving to CMDPs.\n3. The empirical experiments validate the theoretical results on (a bit simplistic) environments.\n\n**Weakness**\n1. While tabular CMDPs are linear CMDP,  it would be great to see experiments for linear CMDP. Otherwise, it would be interesting to see how the OPLB-SP compares to DOPE [1] in the tabular setting. I would strength my score for either addition.\n2. It seems like the parameters of Algorithm 2 appear to be specified only up to big-O notation. It would be helpful to clarify what aspects of the analysis prevents the exact values to be known.\n\n[1] Bura, A., HasanzadeZonuzy, A., Kalathil, D., Shakkottai, S., & Chamberland, J. F. (2022). DOPE: Doubly optimistic and pessimistic exploration for safe reinforcement learning. Advances in neural information processing systems, 35, 1047-1059.", "was_revised": true, "final_justification": "I recommend to accept this paper. I'm happy with the promise of linear CMDP experiments. Although, they are using episode-wise safety rather instantaneous constraints, it seems common in prior work to only conduct experiments in the tabular setting. All other questions were addressed during the rebuttal.", "rebuttal": "Thank you very much for the valuable comments. \nWe answer the weaknesses and questions raised by the reviewer. We would also be happy to provide further clarifications if suitable.\n\n---\n\n**Weakness**\n\n>*While tabular CMDPs are linear CMDP, it would be great to see experiments for linear CMDP. Otherwise, it would be interesting to see how the OPLB-SP compares to DOPE [1] in the tabular setting. I would strength my score for either addition.*\n\nThank you for the suggestion. In response to the comments by fTDU and R4du about the lack of a *linear* CMDP experiment, we are conducting an experiment on linear CMDPs based on [Amani 2021], but adapted to the episode-wise safety rather instantaneous constraint. \n* Specifically, we randomly construct linear CMDPs in which the number of states is larger than the feature map dimension. Currently, we are doing experiments with $|\\mathcal{S}| = 300$ and $d = 20$, but the detailed parameters may change by the camera-ready version. This setup has a relatively large state space while still allowing us to analytically compute the optimal policy and exact regret. With additional adjustments to the experimental setup, we plan to include the results in the camera-ready version. *We also note that several fundamental linear CMDP papers (e.g., [Ghosh 2022, 2024]) achieve empirical results only for the tabular settings*.  We thus only focus on tabular settings for comparison with the state-of-the-art approaches for empirical results. \n\n- [Amani 2021] Safe Reinforcement Learning with Linear Function Approximation\n- [Ghosh 2022] Provably Efficient Model-Free Constrained RL with Linear Function Approximation\n- [Ghosh 2024] Towards Achieving Sub-linear Regret and Hard Constraint Violation in Model-free RL\n\n\nRegarding the comparison with DOPE, during the rebuttal period, we have conducted an experiment under the same setting and parameters as the DOPE paper (i.e., the streaming environment).  \n* **(Results)** Our algorithm achieves sublinear regret  $(\\tilde{\\mathcal{O}}(\\sqrt{K}))$   with zero constraint violations, similar to Figure 2 in the DOPE paper. After $4\\times 10^5$ episodes, our algorithm obtains a regret value of approximately $4 \\times 10^5$, whereas DOPE incurs around $6\\times 10^5$ regret. **This suggests that our algorithm achieves a lower regret than DOPE in this experiment.** Additionally, we remark that DOPE needs to solve an LP which can be computationally intensive for large state, whereas our approach does not.\n* For completeness, our camera-ready version will include an additional comparison with DOPE in the tabular settings.\n\n---\n\n>*It seems like the parameters of Algorithm 2 appear to be specified only up to big-O notation. It would be helpful to clarify what aspects of the analysis prevents the exact values to be known.*\n\n* The reason is due to our careful analysis of the covering arguments and Good Events. \n* In Appendix D.2, we derive covering numbers for several function classes, starting with the Q-function classes $\\mathcal{Q}^r, \\mathcal{Q}^u, \\mathcal{Q}^\\dagger$ (Definition 10). These results are then extended to the composite function class $\\mathcal{Q}^\\circ$ (Definition 11), and subsequently to the policy class $\\widetilde{\\Pi}$ (Definition 12). These covering numbers play a crucial role in the detailed analysis of Good Events in Appendix D.3.\n* Specifying exact coefficients would make the analysis significantly more cumbersome and prone to proof errors, as even minor mistakes could propagate and distort the final results. We ensure that the analysis remains both correct and readable using the big-O notation defined in line 62. This is also a standard practice in literature. Nevertheless, the exact constants can be found in Appendix D. \n\n**Questions**\n\n>*Is it a strict requirement that the initial state $s_1$ is fixed, or can the results be extended when $s_1$ may be chosen adversarially?*\n\n* *The initial state need not be fixed, and can be drawn from some probability distribution.*\n* Extending our setting to an adversarial one is an interesting direction for future work. However, this extension is non-trivial, as our core techniques rely on the assumption of a fixed initial state.\n* For example, we control the number of safe policy deployments by evaluating the return of the bonus function $V^{\\pi^{\\text{sf}}, \\beta^{(k)}}_{P, 1}(s_1)$ (see Definition 4), which depends on the initial state $s_1$. We bound the number of $\\pi^{\\text{sf}}$ deployments using Theorem 3. \nSimilarly, the existence analysis of optimistic-pessimistic (Opt-Pes) policies established in Lemma 7 depends on the initial state $s_1$. \n* To handle adversarial initial states, these analyses would need to be extended to account for adversarial $s_1$ choices. Doing so poses non-trivial technical challenges and is beyond the scope of this work.\n\n>*In Figure 1, the average number of $\\pi^{\\text{safe}}$ deployments appears consistent across different random seeds initially, but then begins to diverge around the midpoint of training as shown by the widening shaded confidence intervals (I'm guessing that this is what the shaded regions depict). What could explain this pattern of initial convergence followed by increasing variance between seeds?\"*\n\n* Since the agent has no prior knowledge of the environment, it initially deploys the safe policy for all random seeds (note that the $x$-axis in Figure 1 is on a logarithmic scale). After a sufficient number of episodes, the agent gathers enough information to switch from the safe policy to the trained policy. The exact timing of this transition may vary slightly across random seeds, resulting in the observed divergence.\n\n>*In Line 4 of Algorithm 1, how it be guaranteed to a $\\pi^k$ to always exist? It wasn't clear to me why Lemma 24 implies this fact.*\n\nRecall from Definition 1 that $\\mathcal{U}^c$ denotes the set of iterations when line 4 is triggered, i.e., $\\mathcal{U}:=\\\\{k \\mid C_u \\beta_{\\pi^{\\text{sf}}}^{(k)}>\\xi / 2 \\\\}$. Our Lemma 2 (or Lemma 24) together with Lemma 1 ensures that, when line 4 is triggered (i.e., $k \\in \\mathcal{U}^c$), at least the safe policy $\\pi = \\pi^{\\mathrm{sf}}$ satisfies the constraint:\n\n\n$$ \\hat{u}\\_{\\pi} - C_u \\beta_{\\pi} \\geq u_{\\pi}-2 C_u \\beta_{\\pi} \\geq b  $$\n\nHere, the first constraint is due to Lemma 1 and the second constraint is due to Lemma 2. Therefore, whenever line 4 is triggered, line 4 is guaranteed to have a feasible solution and thus $\\pi^k$ exists."}, {"review_id": "GNijLs0sPE", "reviewer": "Reviewer_R4du", "summary": "This paper studies constrained RL problem where it maximizes the reward subject to a constraint. The settings considered in this paper are episode-wise safety and linear function approximation. It designs a computationally efficient algorithm and proves that with high probability the algorithm incurs $\\tilde{O}(\\sqrt{K})$ regret with an episode-wise zero-violation guarantee.", "questions": "Could you be more specific about the claim on “while safe exploration is well-established in tabular CMDPs, extending it to large-scale CMDPs remains a major challenge”? Given existing work with optimistic–pessimistic exploration techniques and safe algorithms with linear function approximation, could you articulate the specific challenge your paper resolves? This is a solid work but the novelty is not yet clear to me.\n\nSome minor suggestions:\n\nProviding a table of content would improve readability.\n\nA small typo in Assumption 2: \\mu_h(s’) should be replaced with (\\mu_h)", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\nWhile prior works established such episode-wise safety with sublinear regret in tabular settings, extending these guarantees to function approximation remained open. Previous work use LP based methods which is computationally inefficient with large state space. This work design and analyze an algorithm which is computationally efficient under the linear setting.\n\nWeaknesses:\n\n-Although the regret is optimal in its dependence on K, the dependence on both d and H deviates a lot from the optimal dependence. Given existing results on episode-wise constrained RL and hard-constrained linear RL, the main advance seems to be computational rather than statistical (since it sacrifices on the sample complexity). Although the authors mentioned that adapting Bernstein-type bonus can improve it, but this improvement (H) is not enough to cover the loss.\n\n-There are many existing work on constrained/safe RL with good convergence rates. Although the episode-wise safety setting considers a stricter case, it relies on an unrealistic assumption on having access to a known baseline policy that is strictly safe. Note that this assumption is not common in other constrained RL settings. This limits the practical impact of the guarantees.\n\n-This paper studies linear function approximation setting, which is common for large state-action space RL problem. However, the empirical experiments are done in a small size CMDP.", "was_revised": true, "final_justification": "The authors' response addresses my major concerns therefore I increased the score from 3 to 4.", "rebuttal": "Thank you very much for the valuable comments. We answer the weaknesses and questions raised by the reviewer. We would also be happy to provide further clarifications if suitable.\n\n## Weaknesses\n\n>*Although the regret is optimal in its dependence on K, the dependence on both d and H deviates a lot from the optimal dependence. Given existing results on episode-wise constrained RL and hard-constrained linear RL, the main advance seems to be computational rather than statistical (since it sacrifices on the sample complexity). Although the authors mentioned that adapting Bernstein-type bonus can improve it, but this improvement (H) is not enough to cover the loss..*\n\n\n* The reviewer appears to be mistaken on this point. **We note that none of the existing safe CMDP literature achieves episode-wise safety in linear CMDPs, which is the main contribution of our paper.** Prior works that achieve regret bounds typically consider relaxed notions of episode-wise safety or impose instantaneous constraints instead. As a result, our regret bounds are not directly comparable to existing results. We will add the discussion in the final version. \n\n* More broadly, regret or sample complexity bounds under different safety requirements are generally not comparable, even if the problem settings appear similar. For instance, [Vaswani 2022] shows that the sample complexity lower bound for tabular CMDPs scales as $(1-\\gamma)^{-3}$ when small constraint violations are allowed, but increases to $(1-\\gamma)^{-5}$ when a strictly safe policy is required. This highlights how even a slight change in safety requirements can significantly impact the theoretical lower bounds.\n\n* Deriving a matching lower bound for episode‑wise safety in linear CMDPs would be the next logical step toward understanding the tightness of our upper bound; we leave this important direction to future work. We will mention the above discussion in the final version. \n\n* [Vaswani 2022] Near-optimal sample complexity bounds for constrained MDPs\n\n>*There are many existing work on constrained/safe RL with good convergence rates. Although the episode-wise safety setting considers a stricter case, it relies on an unrealistic assumption on having access to a known baseline policy that is strictly safe. Note that this assumption is not common in other constrained RL settings. This limits the practical impact of the guarantees.*\n\n* **The assumption of a strictly safe policy is, in fact, necessary for episode-wise or instantaneously safe exploration.** [Pacchiano 2021] shows that without strictly safe policies, the regret lower bound becomes infinite, indicating that a strictly safe policy is necessary for efficient exploration. \n* Additionally, in practice, it is common to have a strictly safe policy. For instance, in many real-world decision-making systems, simply remaining idle or taking no action constitutes a strictly safe policy. A self-driving car that always remains stationary, or a dialogue system that remains silent, cannot cause harm to humans.\n\n* [Pacchiano 2021]: [Stochastic Bandits with Linear Constraints](https://proceedings.mlr.press/v130/pacchiano21a.html)\n\n\nFor further reference, the following papers assume the existence of a strictly safe policy:\n\n* Linear CMDP with instantaneous safety: [Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces](https://arxiv.org/abs/2502.18655)\n* Tabular CMDP with episode-wise safety: [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://arxiv.org/abs/2112.00885)\n* Linear bandit with constraint: [Stochastic Bandits with Linear Constraints](https://proceedings.mlr.press/v130/pacchiano21a.html)\n\n\n>*This paper studies linear function approximation setting, which is common for large state-action space RL problem. However, the empirical experiments are done in a small size CMDP.*\n\n* In response to the comments by fTDU and R4du about the lack of a *linear* CMDP experiment, we are conducting an experiment on linear CMDPs based on [Amani 2021], but adapted to the episode-wise safety rather instantaneous constraint. Specifically, we randomly construct linear CMDPs in which the number of states is larger than the feature map dimension. Currently, we are doing experiments with $|\\mathcal{S}| = 300$ and $d = 20$, but the detailed parameters may change by the camera-ready version. This setup has a relatively large state space while still allowing us to analytically compute the optimal policy and exact regret. With additional adjustments to the experimental setup, we plan to include the results in the camera-ready version. *We also note that several fundamental linear CMDP papers (e.g., [Ghosh 2022, 2024]) achieve empirical results only for the tabular settings*.  We thus only include empirical results for the tabular settings for comparison. \n* We again remark that our main contribution is theoretical. **This is the first linear CMDP algorithm that establishes sublinear regret while being episodewise-safe**. In order to achieve that, we have to apply novel tools and techniques, as described in Section 2.1 and 3.1. Having said that, for completeness, we are conducting the experiments described above, which we will add to the final version. \n\n* [Amani 2021] Safe Reinforcement Learning with Linear Function Approximation\n* [Ghosh 2022] Provably Efficient Model-Free Constrained RL with Linear Function Approximation\n* [Ghosh 2024] Towards Achieving Sub-linear Regret and Hard Constraint Violation in Model-free RL\n\n## Questions\n\n>*Could you be more specific about the claim on “while safe exploration is well-established in tabular CMDPs, extending it to large-scale CMDPs remains a major challenge”? Given existing work with optimistic–pessimistic exploration techniques and safe algorithms with linear function approximation, could you articulate the specific challenge your paper resolves? This is a solid work but the novelty is not yet clear to me.*\n\nOur paper highlights the technical challenges in the following sections (We will also add this in the final version):\n\n* **Section 2.1 (Technical Challenge: Zero-Violation with a Safe Policy)**: Here, we discuss why the techniques for instantaneously safe linear CMDPs are difficult to apply to our episode-wise safety setting.\n  * Basically, the instantaneous safe algorithms utilizes the vector representation of actions and assume $a = \\text{[zero vector]}$ as the safe action. However, extending this safe action technique to episode-wise safe RL is non-trivial, as the episode-wise constraint is imposed on policies rather than actions, and policies in linear CMDPs may be nonlinear functions (e.g., softmax mappings from value functions) rather than single vectors. Further, as we discussed in response to Reviewer YdzS [here](https://openreview.net/forum?id=rgoSyTCTkn&noteId=1PsVpAwIQD), only satisfying instantaneous constraints can be sub-optimal for the episode-wise safety. \n\n* **Section 3.1 (Technical Challenge: Optimistic-Pessimistic Optimization in Linear CMDP)**: This section explains why the optimistic-pessimistic (Opt-Pes) exploration technique in linear CMDPs is more difficult than the tabular setting. \n    * In the tabular CMDP setting, the Opt-Pes problem can be efficiently solved using linear programming. However, in linear CMDPs with large state spaces, linear programming becomes computationally expensive and thus is inapplicable.\n    * Given that the Opt-Pes problem is a constrained problem, an alternative approach is to apply the Lagrangian method, which reformulates the constrained problem as a min-max optimization. **However, using this approach for the Opt-Pes problem is non-trivial.** Indeed, to the best of our knowledge, no existing work applies the Lagrangian method to solve the Opt-Pes problem. The main difficulty lies in the clipping operators within the Opt-Pes formulation (see Definition 2), which complicate establishing min-max duality in the Lagrangian framework. This, in turn, makes it difficult to derive performance guarantees.\n    * We address these challenges by introducing a novel adaptation of the recent composite softmax policy technique [Ghosh 2024; see our Definition 3], and by efficiently balancing the optimistic and pessimistic terms inside the softmax via bisection search.\n\n[Ghosh 2024]: Towards achieving sub-linear regret and hard constraint violation in model-free rl\n\n**Minor suggestions**\n\n> Providing a table of content would improve readability.\n\nDue to the page limitation, our paper provides the table of contents in the beginning of Appendix (page 13)."}, {"review_id": "FHvlDVJWCy", "reviewer": "Reviewer_JT6p", "summary": "The paper studies linear Constrained Markov Decision Processes (CMDPs) in the function approximation setting. Concretely, the authors present two algorithms with sublinear regret which is guaranteed to never violate the constraints, one for the bandit setting and one for the general reinforcement learning setting. This is achieved by using a known safe policy to select actions whenever the confidence bounds exceed a given threshold. Otherwise the algorithm plays a policy whose occupancy measure mixes that of the safe policy and that of the estimated best policy. The authors show that the number of episodes playing the safe policy is logarithmically bounded, ensuring sublinear regret.", "questions": "How does Algorithm 1 solve the optimistic-pessimistic problem? This does not seem trivial due to the constraint.\n\nA policy with a given occupancy measure is guaranteed to exist, but how easy it is to compute such a policy?", "limitations": "I do not think that there are any major limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is mostly well written and the authors attempt to explain all steps of the analysis. According to the authors, theirs is the first known algorithm with sublinear regret and zero violation in the linear CMDP setting. I believe the algorithm and the analysis are novel, particularly the way that the known safe policy is used to achieve a mixture policy that is guaranteed to be safe. The authors also bound the number of times that the safe policy is played on its own, which is sufficient to ensure sublinear regret.\n\nThe analysis is somewhat difficult to follow at times, though I have done my best to ensure that the proofs are correct. A couple of algorithmic concepts are not well explained, e.g. how to solve a given optimistic-pessimistic problem efficiently when constraints are involved, and how to produce a policy that matches a certain occupancy measure. However, overall I am happy with the paper and assuming that all results are correct I think the contribution is significant enough for publication at NeurIPS.", "was_revised": true, "final_justification": "The authors addressed my concerns and I am satisfied with the responses. In my view, the most important outstanding point is to add a discussion about the tractability of the optimistic-pessimistic problem.", "rebuttal": "Thank you very much for the valuable comments. We answer the question raised by the reviewer in the following. We would also be happy to provide further clarifications if suitable.\n\n---\n\n>*How does Algorithm 1 solve the optimistic-pessimistic problem? This does not seem trivial due to the constraint.*\n\nRecall the Opt-Pes problem in the bandit setup (Equation (3)):\n\n$$\n\\max_{\\pi} E_{a \\sim \\pi} \\left[f(a) \\right] \\text { such that } \\mathbb{E}_{a \\sim \\pi} \\left[g(a) \\right] \\geq b\\;,\n$$\nwhere we simplified the notations to render the equation with Markdown properly.\n\nThis is an optimization problem with a linear objective and a constraint.\nIn general, not much can be said about the computational tractability without assumptions on $\\mathcal{A}$.  **When $\\mathcal{A}$ is finite, which is the focus of the linear CMDP section (Section 3), in this case, the problem reduces to a convex optimization problem and can be solved efficiently using linear programming, the Lagrangian method, or our softmax-policy approach with the bisection search (Section 3.2).**\n\nSince Section 2 aims to illustrate our $\\pi^{\\text{sf}}$ deployment trigger technique and its role in efficient exploration, we omit computational details and focus on the core ideas behind the regret analysis.\n\nWe also note that the optimistic problem becomes computationally challenging beyond the finite action setting [Lattimore 2020]. Specifying what condition on $\\mathcal{A}$ makes the Opt-Pes problem in the linear bandit efficiently solvable is beyond the scope of Section 2. We will add the above discussion to the final version.\n\n\n- [Lattimore 2020]: [Bandit Algorithms Section 19.3.1](https://tor-lattimore.com/downloads/book/book.pdf#page=254)\n\n---\n\n>*A policy with a given occupancy measure is guaranteed to exist, but how easy it is to compute such a policy?*\n\nWe believe the reviewer is referring to the discussion around Lemma 7. In our algorithm, we do not need to compute the policy of the corresponding mixed occupancy measure.\n\nLemma 7 ensures the existence of a policy $\\pi$ that is optimistic while satisfying the pessimistic constraint such that\n\n$$\nV_{P, 1}^{\\pi, r+B_{\\dagger} \\beta^{(k)}}\\left(s_1\\right) \\geq V_{P, 1}^{\\pi^{\\star}, r}\\left(s_1\\right)\n\\quad \\text{and}\\quad\nV_{P, h}^{\\pi, u-2 C_u \\beta^{(k)}}  \\geq b\\;.\n$$\nAs we show in Lemma 7, the existence is ensured by the technique of mixed occupancy measures. We use this mixture policy $\\pi$ to establish the regret upper bound for term ② around line 264. *Notably, this mixture policy appears only in the regret analysis of $\\pi^{(k)}$ obtained via bisection search; it is not required in the actual algorithm.*"}]

Author rebuttal:

Meta-review: This work introduces the first algorithm achieving both sublinear regret and zero-constraint violation in the linear CMDP setting, extending guarantees beyond the tabular case. As noted by all reviewers, the analysis is both novel and rigorous. The paper is clearly written and well structured, beginning with the bandit case before moving to CMDPs, which provides readers with an intuitive understanding of the analysis. Experiments (Appendix E), though conducted on relatively simple environments, support the theoretical claims and validate the algorithm’s effectiveness. I am happy to recommend acceptance of this work to NeurIPS.
Decision: Accept (spotlight)