Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces
Authors: Amirhossein Roknilamouki
Arnob Ghosh
Ming Shi
Fatemeh Nourzad
Eylem Ekici
Ness Shroff
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning
Episodic Linear MDP
Constrained RL
Safe RL
Non-Convex RL
Covering number
Primary area: theory->learning_theory
TL;DR: This is the first paper that achieves sub-linear regret with zero violation for linear MDP with non-convex feature space

Abstract: In Reinforcement Learning (RL), tasks with instantaneous hard constraints present significant challenges, particularly when the decision space is non-convex or non-star-convex. This issue is especially relevant in domains like autonomous vehicles and robotics, where constraints such as collision avoidance often take a non-convex form. In this paper, we establish a regret bound of $\tilde{\mathcal{O}}((1 + \tfrac{1}{\tau})  \sqrt{\log(\frac{1}{\tau})  d^3 H^4 K})$, applicable to both star-convex and non-star-convex cases, where $d$ is the feature dimension, $H$ the episode length, $K$ the number of episodes, and $\tau$ the safety threshold.  Moreover, the violation of safety constraints is zero with high probability throughout the learning process. A key technical challenge in these settings is bounding the covering number of the value-function class, which is essential for achieving value-aware uniform concentration in model-free function approximation. For the star-convex setting, we develop a novel technique called *Objective–Constraint Decomposition* (OCD) to properly bound the covering number. This result also resolves an error in a previous work on constrained RL. In non-star-convex scenarios, where the covering number can become infinitely large, we propose a two-phase algorithm, Non-Convex Safe Least Squares Value Iteration (NCS-LSVI), which first reduces uncertainty about the safe set by playing a known safe policy. After that, it carefully balances exploration and exploitation to achieve the regret bound. Finally, numerical simulations on an autonomous driving scenario demonstrate the effectiveness of NCS-LSVI.

Provably Efficient RL for Linear MDPs under
Instantaneous Safety Constraints in Non-Convex Feature Spaces
Amirhossein Roknilamouki Arnob Ghosh? 2 Ming Shi
Fatemeh Nourzad Eylem Ekici" Ness B. Shroff
Abstract
LSVI), which first reduces uncertainty about the safe set by playing a known safe policy. After that, it carefully balances exploration and exploitation to achieve the regret bound. Finally, numerical simulations on an autonomous driving scenario demonstrate the effectiveness of NCS-
In Reinforcement Learning (RL), tasks with in- stantaneous hard constraints present significant challenges, particularly when the decision space is non-convex or con-star-conver This issue is especially relevant in domains like autonomous vehicles and robotics, where constraints such as collision avoidance often take non-convex form, and the state-space may be large. In this paper, we establish a regret bound of Ō((1 + +) (o applicable to both star- convex and non-star-convex cases, where d is the feature dimension, H the episode length, A the number of episodes, and 7 the safety threshold for linear MDP setting. Moreover, the violation of safety constraints is zero with a high probability throughout the learning process. A key technical challenge in these settings is bounding the cover- ing number of the value-function class, which is essential for achieving value-aware uniform con- centration in model-free function approximation. For the star-convex setting, we develop novel technique called Uojective-Constrrin Decompo- sition (OCD) to properly bound the covering num- ber, and resolves an eггor in a previous work on the constrained RL. In non-star-conve scenarios, where the covering number can become infinitely large, we propose two-phase algorithm, Non- Convex Safe Least Squares Value Iteration (NCS-
1. Introduction
Safe Reinforcement Learning (RL) has emerged as a pow- erful framework for safe online learning, enabling agents to learn autonomously from their environments while re- specting safety constraints (Tessler et al., 2018; Ghosh et al., 2022b). In many safety-critical applications -scch au- tonomous driving, healthcare, and financial planning-it is imperative that the agent not only maximizes cumula- tive rewards but also maintains safety at every step of the decision-making process (Shi et al., 2023; Amani et al., 2021). These applications often feature instantaneous hard constraints, which must be satisfied at each time step to pre- vent catastrophic outcomes (e.g., avoiding collisions in au- tonomous driving). Unlike constraints that allow violations in expectation across entire trajectory, instantancous hard constraints demand adherence strictly at every decision point, highlighting the need for RL methods that can explore and exploit without compromising immediate safety.
Amani et al. (2021) tackled this challenge by introducing strategy for Safe RL with instantaneous hard constraints in star-convex decision spaces within linear MDPs. Amani et al. (2021) assume that at every state, there exists an initial safe action that is known to the RL agent. The agent begins interacting with the environment using this initial safe ac- tion, subsequently constructing and refining an estimated safe set of actions that remain within the actual safe set of actions. However, as described below, their analysis to prove sublinear regret is not correct (with further details provided in Section 5.1). The key issue arises in bounding the covering number for the value function, crucial step for achieving value-aware uniform concentration in model- model-free function approximation. Their Theorem relies on results from unconstrained RL (Lemma D.6 in Jin et al. (2020)), where the value function obtained by maximizing the
'Department of Electrical and Computer Engineering. The Ohio State University, Columbus, OH, USA. 'Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ, USA Department of Electrical Engineering University Buffalo, Buffalo, NY, USA *Department of Computer Science and Engincering, The Ohio State University, Columbus, OH, USA.. Correspondence to: Amirhossein Roknilamouki <roknilamouki. @ @osu.edu>> Arnob Ghosh <arnob.ghosh@ aamoob.hosi@@nniledd>>>>> njit.edu>>, Ming Shi <mshh244@uffalo.ddu Fatemeh Nourzad <nourzad. @osu.edu>. Eylem Ekici <ckici.2@osu.cde Ness B. Shroff <shroff. @ @ssu.edu>>
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Q-function over fixed action set. In such cases, a cov- ering of the Q-function automatically induces a covering of the value function, thanks to the contraction property of the max operator. However, in the constrained RL frame- work of Amani et al. (2021); the value function is computed by maximizing the Q-function over an estimated safe set that depends on the random historical data. Consequently, even when the Q-function remains the same, differences in the corresponding safe sets can lead to drastically different value functions. This invalidates the direct application of unconstrained RL's eevering-number bounds, and the analy- sis in Amani et al. (2021) must be significantly revised to account for the dynamic nature of the safe set.
this phase, the estimated safe set remains stable with high probability, enabling tighter covering-number bounds.
Having established this stable safe set, the agent then pro- ceeds to an exploration exploration-exploitttionn phase, refining its pol- icy under a bounded covering-number number framework. As our second contribution, we show that NCS-LSVI achieves a + सेz) with
regret bound of Ø( 4) high probability, nearly matching the regret in convex and star-convex cases while also respecting instantaneous hard constraints. Here, d represents the feature space dimension, H the episode length, K the number of episodes, and T a safety related parameter. The bounded constant parameters and e are related to our Local Point Assumption (3.2). To the best of our knowledge, this is the first result for non-star- convex settings. Additionally, we conduct numerical exper- iment on a merging scenario in autonomous driving, where the safe set is non-star-conver due to collision-avoidanee constraints. The results demonstrate sublinear regret, con- sistent with the theoretical upper bound, and highlight the practical potential of our two-phase framework.
As our first main contribution, we show how to correctly bound the covering number when the feasible action set is updated over time in the star-convex case. Specifically, we identify that stav-convexity provides a form of smooth geom- etry-small variations in the safety parameters do not cause drastic changes in the estimated safe set. Consequently, if two Q-functions are close, the corresponding value func- obtained by maximizing each Q-function over these slightly different feasible sets-also remain close. Lever- aging this property, we introduce the novel OCD (Objec- twe-CContraint Decomposition) technique, which replaces the unconstrained covering- ewerbnggnuumber argument with a re- fined bound that includes an additional term of the form O (Vlog()) ). where is the safety threshold. This fac- tor reflects how tighter safety requirements (i.e., smaller T) make bounding the covering number more challenging, offering a fresh perspective on the cost of satisfying instan- taneous constraints (See Remark 6.1).
Pure exploration has also been studied in the context of safe linear bandits by Amani et al. (2019), where it was specifi- cally designed to ensure that the optimal point is included in the estimated safe set at the end of the exploration phase. In comparison, linear bandits are simpler than RL, as they do not involve estimating a value function or managing the covering number. In our work, the safe pure exploration phase serves different purpose: it is specifically designed to control the covering number in the second phase of our algorithm, enabling near-optimal performance even in non- star-convex spaces.
While star-convex geometry can be gentle on covering- number bounds, real-world problems such as autonomous driving and robotics often induce non-star-convex or highly irregular safe decision spaces- e.g., disjoint regions due to obstacles or kinematic constraints. In these settings, as detailed in Section 5.2, the covering number can become arbitrarily large, rendering existing star-convex-based meth- ods insufficient and highlighting the necessity of developing new methods for non-slar-conve environments.
Altogether, our work highlights the pivotal role of the de- cision space's geometry in shaping the complexity of safe RL. While this study focuses on linear function approxi- mation and local connectivity, the broader takeaway is that additional mechanisms beyond those used in unconstrained RL are crucial for maintaining tight covering numbers un- der instantaneous hard constraints. This insight opens up promising directions for future research, particularly in deep RL, where nonlinear representations often create irregular feature spaces. These complexities further underscore the importance of understanding how the geometry of the fea- ture space impacts overall performance.
Motivated by these observations, we propose a new two- phase algorithm for non-star-conver scenarios that satisfy our Local Point Assumption (see Section 3), which we refer to as Mon-CCnvex Safe Least Squares Value Iteration (NCS- LSVI). Drawing from our insight in star-convex analysis, we observe that controlling drastic changes in the estimated safe set under small variations in constraint parameters is a key strategy for bounding the covering number. Based on this, NCS-LSVI includes a pure-safe exploration phase, where the agent samples randomly from safe actions in a small neighborhood of the initial safe policy (whose existence is guaranteed by the Local Point Assumption). By the end of
Other related works. RL problems with cumulative con- straints are studied (Wu et al., 2016; Achiam et al., 2017:
Tessler et al., 2018; Yang et al., 2019; Efroni et al., 2020; Qiu et al., 2020; Ding et al., 2021: Bai et al., 2022; Wei et al., 2022; Paternain et al., 2022; Ghosh et al., 2022b; Vaswani et al., 2022; Ghosh et al., 2022a; Ding & Lavaei, 2023; Ghosh & Zhou, 2023; Huang et al., 2023; Ghosh et al., 2024). This line of work focuses on ensuring the expected
2

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
cumulative cost remains below a threshold, unlike instanta- neous constraints that must be satisfied with high probability at each time step. Another relevant direction is explored in Berkenkamp et al. (2017), which explicitly considers stability- safety guarantees using Lyapunov methods within model-based reinforcement learning to certify policy safety during exploration.
Instantaneous hard constraint. In each episode k and at each step h, the learner is required to adhere to a hard constraint: ch c af) S T, where is known positive constant that serves as the safety threshold. For each state 8 E S, the corresponding safe set of actions is given by (s) = {a E A en (3. a) S 7). Our framework natu- rally extends to settings involving multiple constraints by defining the estimated safe set as (5 = N A (s).
Bandits with instantaneous hard constraints: Bandits with instantaneous constraints have been studied in Amani et al. (2019); Khezeli & Bitar (2020); Moradipari et al. (2020a;b; 2021); Pacchiano et al. (2021); Zhou & Ji (2022); Deng et al. (2022); Pacchiano et al. (2024); Hutchinson et al. (2024); Afsharrad et al. (2024). Unlike RL, Bandits do not require the estimation of a value function, and therefore the problem of covering number does not arise in this setting. This distinction significantly simplifies the analysis and al- gorithm design in the context of Bandits compared to RL with instantaneous hard constraints.
where each A (s) represents the safe action set associated with the j-th constraint.
Safe policy. A deterministic policy is defined as a mapping T( h)) S x [M] - A. Thus, a policy ı is called safe, if, for every state s E and time step h, it satisfies the instan- taneous constraint. Therefore, the set of all safe policies is defined by IT (=(- : <(s,h) E A (s), ((s, h)
8 x [-]-
Performance metric. Given policy ग,, the corresponding
V-value and the Q-value are defined as follows: (s) s]. and (7(s,a) =
RL with instantaneous hard constraints: Problems with unsafe states in a star-convex setting have been studied in Shi et al. (2023). However, this setting focuses on the linear mixture model, which is fundamentally different from our setting, as explained in Section 2. Lastly, work in Wei et al. (2024) relaxed the assumption that a prior safe action is given to the algorithm, instead allowing sublinear constraint violation. Thus, none of the above works have studied RL with instantancous hard constraints for non-star-convex decision spaces.
rn - (5w rTh" ,84, ()ss "x (Sw, T , .52.)
)){s = 8, ag a]. Assume that each episode starts with a fixed initial state 81 E S. The agent, at each episode E [K], employs the policy n² to interact with the environment. We then evaluate the performance of the set of policies {**) Jk=1 by the well-studied regret metrie, defined as Regret(K) IR (s1) Vf" (s1)]. Note that x is the optimal safe policy that maximizes V-value function, while remaining safe x² [ssafe
2. Problem formulation
Linear MDP. To handle the large and potentially infinite number of states and actions, we concentrate on linear MDPs. This choice enables us to employ linear function approximation methods to solve our problem effectively.
In this study, we focus on an episodic constrained MDP, denoted as A, H, I,, r, e), operating in an online setting over K E N episodes. Here, S represents the state space, which may contain an infinite number of states; A denotes a continuous action space; and H e N determines the number of steps within each episode. Additionally, (IP) A= fr (=) and {c)[_ correspond to the state transition probability ker- nel, reward function, and cost function at each step, respec-
Assumption 2.1. (Linear MDP (Ghosh et al., 2022b), (Jin et al., 2020)) Consider an episodic constrained MDP de- noted as (S, A, H, P, r, r)), which is assumed to be linear MDP with a feature function Specifically, for each h E [H]. there exist d unknown mea- } sures in = [M), ................................ M1 over the state space S and un- known vectors 6% %% E IRd such that for any (s, s') E S x A x S, the transition probabilities, cost function, and re- ward function are given by: Px(s'|s, a) = (d(s, a), (s))), rn (,, a) = (o(s, a), 8%)). and cn a) = (Ø(s, a). 7,). re- spectively. Additionally, we assume without loss of gen- erality that for all (s, a) E S A, we have [|obs,, a)l S L for some L E (0, 1J. and max(Ilu(S)) (S)I,, |0% (i S Vd. where d is the dimension of the feature space.
S x A + F Rd
tively. During episode k E [K] and time step l E [M], the learner is in state & E S. interacting with the environment by selecting an action a E A. Subsequently, the learner ob- serves a noisy reward P (s), a = rr (sh at) + v/. where r.)()) : S x A + [0 represents an unknown function, and n/f denotes zero-mean
sub--Gusssian random vari- able. In addition, it observes a corresponding noisy cost (ss),, (%x = c, (st, a + where c.))): S SxA-1 + Jo, 1] is an unknown cost function, and ÇK is a zero-mean o-sub-
Gaussian random variable as well. Finally, the transition to the next state, s/+41 under the action at at state st. deter- mined by an unknown transition probability kernel denoted as PA (-1st; a.)) The episode terminates step H 1.
Assumption 2.1 encapsulates the linear relationship of the transition probabilities, costs, and rewards with the feature map. It is important to note that despite the linearity, the feature map s(.) itself may potentially be non-linear or even non-convex. Note that, the linearity of the transition
3

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
probabilities, results in the fact that all features points are located on d 1 dimensional hyper plane as explained in the following proposition:
Proposition 2.2. (Proposition A. from Jin et al. (2020)) Let J. A {o(s, a) E I | a E A}, and F - {Ø(s, a) E Fd (a. E x S). Then, there exists a vector p² Rd
such that Fs C C H. where H is a d -1 dimensional hyper plane determined by H a {x E Red (2, 1}.
32
Initial safe action. Designing a safe RL algorithm that achieves sublinear regret requires at least one known safe action per state s S, as shown in Theorem of (Shi et al., 2023). This assumption is often valid in real-world scenarios where a known, albeit suboptimal, safe strategy exists (Amani et al., 2019; 2021; Khezeli & Bitar, 2020). In this study, we also adopt a similar assumption as stated bellow.
Figure I. An illustrative example of Assumptions 3.2 and 3.1. The left figure demonstrates the Local Point Assumption, where a sphere exists around the initial safe point. The right figure depicts Star-Convex Set, where all points are connected to the initial safe point by a line segment.
decision (Figure 2). The car can either (i) drive slowly to let oncoming traffic pass or (ii) accelerate rapidly to merge before other vehicles arrive. These two action modes induce disjoint feasible regions, violating Assumption 3.1 because no straight line connecting the points in the slow mode to the points in high accelcration mode resides entirely in the decision space. Note that these distinct action subsets naturally emerge from collision avoidance constraints and results in a non-convex decision set.
Assumption 2.3. For each state E S, there exists a safe action af. that incurs zero cost, i.e., (o(s, 1%) = O. Remark 2.4. We highlight that for problems where the ini- tial action results in a non-zero cost Tu. the original problem can be converted to an equivalent one that satisfies Assump- tion 2.3 through a simple translation. In the new problem, the safety threshold is adjusted to To-
Notations. For any positive semi-define matrix A and vec- tor v, the operator ||li|a defines the weighted norm as ||el| A VoT The symbol ||-|| denotes the 12 norm. Also, we define PA The ball (v) represents the set of all points within distance ffom v.
To address the limitations of star-convex spaces, we in- troduce new class of non-convex sets, termed the Local Point Assumption, which satisfies conditions relevant to au- tonomous vehicles and robotics. These sets feature localized properties around Φ(s, ag) and near constraint boundaries within the feature space, while allowing arbitrary structures outside these regions.
(s, a) _ Ex--P.(-)s..)) V (s').
3. Non-Convex Feature Spaces
Assumption 3.2. (Local Point Assumption) Let H. be the (d didiennsioa hyperplane containing F. There exists (0, Ja such that (o (()) H c F, for all e S. Moreover, for any (s, h), if r - 1 U a).s,a).2tt mh S T for some & < T, then (s, a) + (1 - v) o(s a²) v E
Non-convexity often occurs in real-world problems due to non-convex constraints such as traffic rules, collision avoid- ance, and kinematic restrictions in autonomous vehicles, as well as in feature selection and function approximation in modern RL methods. Here, we define two key assumptions in the feature space F=-star-convexin and the Local Point Assumption-commontt found in these applications and will later provide near-optimal solutions for them. To start, we define the notion of star-convexity, introduced in Amani al. (2021):
(p(s.a)m)) 11} C FF.
Comparison with Assumption 3.1. The key difference between Assumption 3.1 and Assumption 3.2 is that star- convexity imposes global requirements on all points in F., whereas the Local Point Assumption focuses solely on local properties. Intuitively, the Local Point Assumption demands that we can slightly perturb the initial safe action ai and still remain safe, enabling sampling from small neighborhood around ag. For instance, in the autonomous driving scenario described earlier, if a particular speed vu is considered safe, then speeds within the interval (Vo e, vo must also be safe. Furthermore, the second condition in the Local Point Assumption requires local connectivity near the con- straint boundary: if an optimal action 2 lies exactly at the constraint boundary, then actions in the range [v* (0"-1, 1, w*)
Assumption 3.1. (Star-Conver Sets) For each s E S, the feature space F. is star-convex around Φ(s, ).). That is, for all x E F, and a E [0, 1]: ax + (1 - a) d(s a E F..
Although star-convexity simplifies the theoretical analysis, many real-world inncluuig autonomous driy- ing ing-cannot satisfy this assumption as we explain the fol- lowing example:
Example (Autonomous Driving): Consider an autonomous vehicle approaching an intersection and facing a merging
4

---

end for Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
must also remain within the safe region. However, the Local Point Assumption is not always less restrictive, it requires the existence of hypersphere on the plane H. condition not mandated by star-convexity. In practice, though. it is an effective assumption for handling complex decision spaces, particularly in applications such as autonomous vehicles and robotics. For an illustrative example of star-convex sets, see Figure Consequently, these structural differences lead to distinct regret bounds under the two assumptions (see Section 5).
Algorithm I Non-Convex Safe Least Square Value Iteration (NCS-LSVI)
Require: 6, K", K, V, 81 1: Pure safe exploration
2: for h = 1, ..... K' do
3: for h = 1,.., H do
4: At state take action randomll from (*(s) according to Eq. (1). 5: end for
end for
Safe exploitation-exploaaiii
8: for episode k K' + 1,..., K do
9: for step h = H
1 do
10: Compute h
k. , ,A7 The wp according to
yakis acceliittoon
Eqs. (2-3)
11: Compute estimated safe set, S
64
(a) - (a E A: (6(8,a) - (0 (2),1h)
+ a) ols, a 7 S TT
5-axis acceleration
12:
Compute (%,ss == (0(s, a), w/)) + (8, a).
13: Take action of. - argmar a AM (o) 2
Figure 2. Left figure: The green car (G) must decide whether to stop at the intersection for the approaching orange car (O) or accelerate to pass before arrives. Right figure: The green car's decision space, where the red region is inaccessible due to the collision avoidance module.
14:
end for
15:
for step h 1 to Hl do
16:
Play al, and observe its reward r and cost cj.
17:
end for
18:
4. Our Approach
all actions during the pure exploration phase are safe, i.e., D (s) C Ar.l (s).
We now describe our proposed algorithm, Non-Convex Safe Least Square Value Iteration (NCS-LSVI), detailed in Algo- rithm 1. This algorithm extends the standard SLUCB-QVI from (Amani et al., 2021) to address safe RL problems in non-star-convex environments. A key feature of our ap- proach the ability to handle large covering numbers in non-star-convex environments using the pure exploration phase. The algorithm consists of two main phases: pure safe exploration and safe exploittion-expllration, imple- mented over K episodes. At a high level, NCS-LSVI en- sures safe learning by leveraging a Recursive Least Squares (RLS) framework to construct an estimated safe set Ali (s). Subsequently, employs an optimistic Q-function estima- tion to guide policy updates. Detailed explanations of the algorithm's components are provided below.
Role of pure exploration. In non-convex environments, small changes in constraint parameters can dramatically alter the estimated safe set, leading to large covering num- bers (as shown by our toy example in Section 5.2). How- ever, once the pure exploration phase is complete, under the Local Point Assumption (Assumption 3.2), the safe set near the constraint boundary becomes smooth and stable. Consequently, minor perturbations no longer cause drastic changes, allowing to control the covering number effec- tively. Under Stav-Convexity (Assumption 3.1), this global smoothness and stability is inherent, we prove that the pure exploration phase is not needed to achieve a bounded cover- ing number (see Section 6).
Lines 1- - 6 (Pure safe exploration). In this phase the agent samples uniformly from a set D' (s) defined as follows:
Lines 7-14 (Safe opplotatioo-ceplloaatoo))) Once the pure exploration phase has been finished, we start the safe exploitation exploitation-exploraiio exploration which contains two main stages: Safe set construction and Q- function estimation.
D' (s)) {a E A| | a) o(s, af)ll = =}. (1)
According to Assumption 3.2, (s) represents the bound- ary of (o(s 0 H. Note that given Assumption 2.3 and the linearity of the problem (Assumption 2.1), the inequality can be applied to confirm that
Safe-set estimation. We use Recursive Least Squares (RLS) for safe-set construction, with the modification that we con- sider the difference in features relative to the initial starting point. In fact, to satisfy the safety condition, it crucial to
5

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
determine how far we can deviate from the initial starting point. Therefore, we formulate the following RLS problem:
5. Analysis
In this section, we first present our main theoretical results for star-convex cases. Then, we explain that ( quite interest- ingly), in contrast to the unconstraned RL, the geometry of the decision set, i.e. Fs, can affect the covering number of the class of value functions in constrained RL.
7 A - (x4) + +
Nh =
whereæy _ - d Note that Considering Assumption 2.3, then Theorem 2 from Abbasi- Yadkori al. (2011) demonstrate that for any ā (0, 1), the choice of
5.1. Star-Convex Results
Theorem 5.1. Regret in Star-Convex Spaces (Refined version of Theorem I in Amani et al. (2021)) Under assumptions 2.1, 2.3, and 3.1, there exists a constant Cg > 0 such that for any E (0, (0,3), by setting K' 0, 31 cgdH I Vlog( dk ).
14 22+2X
82 v dloog
+ v Ad ensures that (s) c
A safe holds with probability of at least 1 5.
Q-function estimation: According to Proposition 2.3 in Jin et al. (2020), for a linear MDP, the Q-value of the optimal policy n can be expressed as Q% (s, a) = (ō(s, a), w ). Thus, in line 12 of Algorithm I, we utilize Regularized Least Squares (RI.S) to estimate w% as follows:
2 and X 1,
78
with the probability of at least - 35 Algortihm I re- mains safe, (s) C (s), v(h, k) E [H] x [K]. Moreover, with probability at least 1 35, Algorithm I achieves: Regret( S &2H KH log( d(
(3
- = k.
af)
(3)
38, /2d(k) log(1+ + dx)
T I.
where 3h Q.Q =
+ Vh (s
Comparison with Theorem 1 in Amani et al. (2021).
+ XI, and
Compared to our Theorem 5.1, the regret bound in Theo- rem 1 of Amani et al. (2021) lacks the / /log(t) factor. This omission arises due to a mistake in their Theorem 2, which govering-number argument designed for uncon- strained RL (Lemma D.6 in Jin et al. (2020)), an approach that is not valid in our setting under instantaneous hard constraints. To clarify, note that a k-covering of the value functions ensures that every possible V/2 can be approxi- mated to within K. For the unconstrained setting, Jin et al. (2020) demonstrated that k-covering of the Qu-functions directly induces k-covering of the V, -fncctinnon This is because V/A is obtained by maximizing Qf: over fixed ac- tion set A, and the contraction property of the max operator ensures that small changes in Q% lead to small changes in V (Ghosh et al., 2022b). In our setting, however, Vř is defined by maximizing Oh over a data-dependent safe set A Consequently, covering of the Q -ff-cuncsions does not directly imply a covering of the V/fffuncions, as changes in A can cause significant differences in V/A. To resolve this issue, we develop a novel technique called OCD for bounding the covering number in the star-convex setting (see Section 6). Specifically, we show that when F, star- convex, the changes in Af, can be controlled by variations in the safety parameters 7/ and R.y enabling an effec- tive bound on the covering number. Once this bound is established, we provide corrected version of Theorem in Amani et al. (2021) for the event &g, which now includes the missing v (+) term, detailed below: Theorem 5.2 (Corrected covering-number number result). Un- der the setting of Theorem 5.1, for any fixed policy
W+1 A min minnmax,..4t (s. H).
Bonus design and geometric assumptions. Following Amani et al. (2021), we include a bonus term in Step 5 to encourage exploring unexplored safe actions: bf a) & 31l1o(s, a) )- dard exploration bonus from unconstrained RL (Jin et al., 2020), and the second term is defined as follows:
relies
a), where the first term is a stan-
t ()) - 1
(3210((s Ms, ((,.a))la)))))) H.
(4)
sf., accounts for the distance between the optimal action h)) and the estimated safe set (s). Under star-convex sets (Assumption 3.1), Amani et al. (2021) show that there exists a scaling factor such that a 2 (1- "+282ll0(0. (s.1)) (tt0)) Ts(s, (s, + (1 - ap) E d(s, (x))) In non-star-convex settings satisfying our Local Point Assumption 3.2, we show that this property holds for k 2 K'ii.. after the pure exploration phase. This ensures that gi.,, compensates for the remaining distance between arb(s, T" (s, hi) + (1 - a))(s, a²) and Ø(s, (x, h)), while encouraging the algorithm to expand the estimated safe set toward the optimal action.
Lines 15-17 (Environment interaction). Finally, in steps 15-17, the algorithm plays the selected actions and observes their corresponding rewards and costs, which are stored for use in the next round. The steps 8-17 is repeated for K-X K' iterations.
6

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
T, le the event Eg be defined as follows: Eg (Ww,, 0(s, a)) - (s) + Pn (V V (s) S <Bllo(s, a 0) V(a,s, h, Ax
Regret(K) - KK'H+111 (K (K- K'H log( d.K- K'H 2( + 12
5 1) for all
T )H
V 2(KK -K')d dd+2KL3 Ad
where B1 = cgdH / /log( 45) for some constant cg. Then, the event & holds with the probability of at least 1 - 6.
K' m
Sd log(
dH ) ( -)),, where and & are
2 1602
defined in Assumption 3.2.
5.2. The Challenge of Covering Numbers in Non-star-Convex Safe RI.
Comparison with Star-Convex Case. The regret depen- dence on K in Theorem 5,4 is Ö(VK). The key distinc- tion between Theorems 5.4 (non- star-conve)) and 5.1 (star- convex) arises due to the necessary pure exploration phase in the non-star-convex setting, Specifically, while Theo- rem 5.1 achieves a regret of Ō(vK) without an explicit exploration phase (K' = 0), Theorem 5.4 introduces a pure exploration phase with length K" = O e4,2 stems from the Local Point Assumption and reflects the added complexity of non-star-conve settings compared to star-convex ones. This term also appears explicitly in the regret bound, capturing the cost of ensuring safe exploration in such environments.
Now, we can illustrate why a dedicated pure exploration phase is critical for controlling the covering number when F. is not star-convex. Suppose we remove the pure- exploration component from Algorithm and start the sec- ond phase of the algorithm, The immediate issue, in contrast star-convex settings, is that we would require a large k-covering of the value functions. The key distinction between these two settings lies in the inability to control changes in Af, through variations in the safety parameters 7/ and 7 In non-star-convex settings, even small variations in these safety parameters can drasti- cally alter A%t leading to substantial shifts in Vi- Thus, we cannot bound the covering number in the same way as in star-convex settings. In fact, the following formalizes this phenomenon in simple one-dimensional example, show- ing that the covering number can grow at least as large the number of states, which can be prohibitively large in environments with very large or continuous state spaces.
log(K)) which
6. Outline of the Proof
The proof steps presented here hold for both Theorem 5.4 and Theorem 5.1, albeit with different choices of K'. For Theorem 5.4, K' corresponds to the termination of the pure exploration phase, while for Theorem 5. K' can be set to O as no pure exploration phase is needed in the star-convex case. Our proof involves three main steps: (1) decomposing the sum of regret and ensuring the constraint satisfaction, (2) bounding the covering number of the value function class, and (3) applying uniform concentration tools to achieve sublinear regret. The key challenge lies in controlling the covering number of the value function class, which critically depends on how the geometry of the decision space.
Lemma 5.3. (Covering number in non-star-conver settings) Consider a one-dimensional setting where Q(s, a) a for a EE R. with a finite state space S = U {i) C N. Define the class of parameterized functions functioon V A (V, |h 1)),
where (s) A (a a(s,a), and (s) A {a E [0, U13 1], 7-5- S J.. Now, for an arbitrary pos- itive real number is- < 1. let the set Vx C V be k-covering for the function class V. Then, the following inequality holds: |S| $ [Vx].
Step 1: Decomposition. Following a similar approach as in Ghosh et al. (2022b), we first establish a decomposition that upper bounds the sum of regret: Regret (K) S K' H + K
Despite the fundamental challenge highlighted in Lemma 5.3, we show that under the Local Point Assump- tion 3.2, the pure exploration phase in Algorithm 1 enables us to control the covering number during the second phase of Algorithm 1. This is because, by the end of the pure exploration phase, the agent's 's estimated safe set remains stable under small variations in the safety parameter with high probability. Below, we present our main result:
K
(Vo (5o) - Vot +
(Vo - Vo (so))
K
Ti To control Ti and Tz, we need to carefully compare the estimated value functions V² produced by our algorithm at each episode & with the corresponding value functions V induced by a given policy т. A critical challenge is dealing with the adaptive nature of the learning process, where the chosen actions depend on previously observed transitions and rewards. This adaptivity can make standard self-normalized concentration inequalities inapplicable, as the future sample distribution depends on the current value estimates. To address this, we rely on allue-aware uniform concentration arguments. By fixing a suitable function class V of candidate value functions in advance and ensuring
Ta
Theorem 5.4. (Regret under Local Point Assumption) Under assumptions 2, 2.3, and 3.2, there exists a con- stant cg > 0 such that for any ō E (0, 4), by setting 3 cædH g /logt 4x and u 2 and X 1, with the probability of at least 1 - 35 Algortihm remains safe. (s)ss) C A (s). v(h, k) E [H] x [K]. More- over, with probability at least 35, Algorithm achieves
7

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
that each V belongs to V. we leverage the polynomial log-covering number of V to obtain high-probability bounds uniformly over all functions in the class. Concretely, for each (ke h)) E [K] x [H], we aim to show that, with high probability:
V+(+) (V(()) H). where:
Vī((s) max a), mi) + (ló(s, + (34,,(85,a)
"EA s.t. (0(s, - of a 12) + +1 a) - -(s e?)ll S T.
(7)
Now, we have: (
(
Σ
(sh
Pr, (5%% [
(s())). This inequality represents decomposition of the dis- lance between V1 and V2 into contributions from differences in objectives and constraints. Specifically, V1 and V3 differ only in their objective parameters, while V/2 and V33 differ in their constraints. Now, since 1/2 and V/3 share the same con- straint parameters (12; A2), they are maximizing over the same feasible action set. Thus, bounding |V/- - V/3 reduces to scenario akin to the unconstrained case, where com- paring two linar-quadraate forms over the same domain is straightforward. On the other hand, bounding \V1 V/l is more challenging because V1 and V/3 have different feasible decision sets.
(AE)
S O(dylog
(5) where Ph is the transition operator at stage h. Achieving such a bound ensures that our estimated value functions are stable and close to the true policy-based value functions, facilitating the desired sublinear regret guarantees.
Step 2: Controlling the Covering Number. We begin by defining our class of value functions V. Consider parameters 0,7 E Rd and positive semi-definite matrices A, A', with bounded norms (e.g.. ||0|| < vd, Ir S Vd, || S vān² and r| < va(=")) Given these parameters, the value function can be written (s)) viin( H). where:
Bounding [V Val in Star-Convex Setting, When F₂ is star-convex, we prove that small perturbations in y or A' do not cause large, discontinuous changes in the feasible action set (see Lemma B.7 in the Appendix). Specifically, we show that if 01 is feasible for V1, then there exists a scalar og E [-=x 1] and an action 0g feasible for Va3 such that as) = azy ((s, a1) + (1 11-o0 (1-as) ø(s, o?), where -ul
('(s) = max w) + |o[ss a)ll - 94' (s,
s.t. ()( - dls a.)) >) + (0(8,)) 0(8, l ST,
A = lh12 - rlll= + VII - -b As A approaches zero, (ss, as) converges to Φ(s,, a1), implying that every feasible feature of Vi has close counterpart in V/2 and vice versa, with the difference controlled by A. Consequently, VVi V/ll can also be controlled by A. Hence, constructing a polynomial cover of the parameter space induces a corresponding cover for the value function class V.
where (s, a) & 2 fl)o(s - (s. lar We col- lect all such value functions into the following class:
+
V A (Van.,, ||||| S I.., |1 S vd, /AAle S
A .|A''| S VaLB"), In contrast to unconstrained RL, where the value function V(.) is determined by max- imizing the objective over the entire action space A, our setup in Eq. (6) introduces constraints through the param- eters (7, A"), which directly affect the feasible decision set. This distinction highlights the need to consider both the objective and the constraints when constructing a log- polynomial-sized covering for V, as we discuss next.
vas²
A
Remark 6.1. When T is small, a smaller A is required to ensure that a3 E [ 1] remains close 1, which in turn ensures that ø(s, 43) stays sufficiently close to 6(s, 01). As a result, larger covering net is needed to account for smaller variations in the parameter space. This additional
complexity is reflected in the vlog(?) term in Theorem 5.2.
OCD: Snteetive-Constrainn Decomposition. Here we introduce our novel idea for bounding the covering num- ber. Consider two arbitrary value functions Vi2 =
Non-Star-Conve setting. In non-star-convex settings, our OCD technique cannot be directly applied without a pure exploration phase, as small changes in the safety parame- ters or A' can cause drastic shifts in the feasible action sets, leading to significant differences in Vi and V/8 (see Lemma 5.2). To understand why this occurs in non-star- convex settings, note that when F, is not star-convex, we cannot guarantee that a o(s, + (1 a) ő(s, o?) E F. for a E [=,,,]] 1]. This is the main reason why our ap- proach for the star-convex case does not extend directly to the non-star-convex setting. However, once V, = V/ where V is the value function generated by Algorithm I after the pure exploration phase, we show that when A
min(V((ss), H} and 1/2 = (V)()), H} from our class V, where:
(s)) = max max (), w.) + (1 a) + ( (s,,
aed
s.t. (d(s, o(s, ((s,a.), m) + () - o6s a 1l) ST,
(6)
for all i E (1. To relate Vi and Vi, we introduce an intermediate value function V/3 with objective parameters from Vi and constraint parameters from V/2 Specifically,
8

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
is sufficiently small, with high probability, all actions in Al (s) = {a AA ()(s,a), 7/ S 1) are feasible for both Vi and V3. Moreover, under the Local Point Assump- tion, any feasible action of V1 outside Ai has close feasible counterpart in V/3 within a A-neighborhood, and vice versa (see Lemma B.3 in the Appendix). This closeness of the feasible sets of Vi and V/3 enables us to reapply the ideas underlying OCD and effectively bound the covering number in the second phase of Algorithm 1.
K -300
1300
-2030
30009
25000
20000
15000
10000
Final assembly. With these log nog-polynomial bound for the covering number in achivech we can apply standard self-normalized concentration inequalities. Thus, we can prove the following I Lemmas:
Step 3:
5000
0-
10000
20000
300Co
40000
Episade
Lemma 6.2. (Optimism) With probability of at least 1 & we have: T S O.
2
Figure 3. Regret vs. episodes for NCS-LSVI in an autonomous vehicle merging scenario.
Lemma 6.3. (Bounding T2) With the probabil- ity of at least 1
S Ekzk' Σm= Ennnch Sh +
6
To
2'
Ek Ki Emm 231 23111 ailllaat
+ shish af),
A key challenge in these settings is bounding the covering number of the value-function class, which is critical for achieving value-aware uniform concentration in model-free function approximation. For the star-convex setting, we introduced a novel technique, OCD, to effectively bound the covering number. This result also resolves an error previ- ous work on constrained RL. For non-star-convex scenarios, proposed new two-phase algorithm. NCS-LSVI, which effectively addresses the challenge of bounding the covering number in these settings, Our analysis demonstrates that our methods attain Ó(V K) regret with zero safety violations in both the star-convex and non-star star-convex settings. Numeri- cal simulations on an autonomous driving scenario demon- strated the practical effectiveness of our method. While our regret bound for the non-star-convex setting under the Local Point Assumption includes a dependence of order zेz. it remains an open question whether this dependence is funda- mental, and resolving it is an important direction for future work. Additionally, future research will focus on moving beyond linear-MDD structures, relaxing assumptions such as the local-point condition, and designing algorithms capa- ble of maintaining safety and near-optimal regret in more complex, nonlinear environments.
where th+1 A Pn(Vit
Va (oh ah) - ohtt1 and
h+1
6/+11 A (s - (t))
Now, combining the last two steps and upper bounding the normalized term obtained in step 3. we can apply Lemma 11 from Abbasi-Yadkort et al. (2011) 1) derive the final result. Additionally, Theorem 2 from Abbasi-Yadkon et al. (2011) can be applied to show that our approach ensures high- probability safety.
7. Experiment
We consider an autonomous-vehicle path-planning task in merging scenario (Figure 2) where the goal is to navigate safely and efficiently (see Section 3 for details). A trained module (Collav) handles collision avoidance by masking infeasible actions, so the RL agent focuses on satisfying lane-keeping constraints. Given an initial safe policy π saee the feature space is non-star-conver due to Collav but still satisfies the Local Point Assumption. Our objective to learn an optimal safe policy with sublinear regret. We imple- ment NCS-LSVI (Algorithm 1) with different values of K' and report the resulting regret in Figure 3. For K' = 2000, regret remains sublinear, indicating successful learning of the optimal safe policy after sufficient pure exploration. Moreover, across all K, our algorithm never violates the safety constraint, ensuring lane-keeping is always satisfied. See Appendix A for further details and additional baseline comparisons.
A Acknowledgments
This work has been supported in part by the U.S. National Science Foundation under the grants: NSF AI Institute (AIEDGE) 2112471, 2312836, 2106933, NJIT start-up fund index number 172884, Army Research Office W91 INF- 24-2-0205, and was sponsored by the Army Research Lab- oratory under Cooperative Agreement Number W91 INF- 23-2-0225. The views and conclusions contained in this document are those of the authors and should not be inter- preted as representing the official policies, either expressed
8. Conclusion
In this paper, we studied Safe RL with instantancous hard constraints in both star-convex and non-star-conve settings.

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
or implied, of the Army Research Laboratory the U.S. Government. The U.S. Government is authorized re- produce and distribute reprints for Government purposes notwitbstanding any copyright notation herein. The authors are also grateful to Dr. Xingyu Zhou for pointing out an error in the analysis by Amani et al. (2021).
Ding, D., Wei, X., Yang. Z., Wang. Z.., and Jovanovic, M. Provably efficient safe exploration via primal-dual policy optimization. In International Conference Artificial Intelligence and Statistics, pp. 3304-3312. PMLR. 2021.
Ding, Y. and Lavaei, J. Provably efficient primal-dua rein- forcement learning for emdps with non-stationary objec- tives and constraints. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 37, pp. 7396-7404 2023.
Impact Statement
This paper contributes the advancement of Machine Learning and Learning Theory by addressing fundamental technical challenges. While the societal impacts of our work align with those typically associated with progress in these fields, we do not foresee any immediate or unique ethical concerns that require specific attention in this context.
Efroni, Y., Mannor, S., and Pirotta, M. Exploration- exploitation in constrained mdps. arXiv preprint arXiv:2003.02//8 2020.
Ghosh, A. and Zhou, X. Achieving sub-linear regret in infinite horizon average reward constrained mdp with linear function approximation. ICLR, 2023.
References
Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Ghosh, A., Zhou, X., and Shroff, N. Achieving sub-linear regret in infinite horizon average reward constrained mdp with linear function approximation. In The Eleventh Inter- national Conference on Learning Representations, 2022a.
Achiam, J., Held, D., Tamar, A., and Abbeel, P. Constrained policy optimization. In International conference on ma- chine learning, pp. 22-31. 1. PMLR, 2017.
Ghosh, A., Zhou, X., and Shroff, N. Provably efficient model-free constrained rl with linear function approxima- tion. Advances in Neural Information Processing Systems, 35:13303-1333 13315, 2022b.
Afsharrad, A., Moradipari, A., and Lall, S. Convex methods for constrained linear bandits. In 2024 European Control Conference (ECC), pp. 2111-2118. IEEE, 2024.
Ghosh, A., Zhou, X., and Shroff, N. Towards achieving sub- linear regret and hard constraint violation in model-free rl. In International Conference on Artificial Intelligence and Statistics, pp. 1054-1062. PMLR, 2024.
Amani, S., Alizadeh, M., and Thrampoulidis, C. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019.
Huang, R., Yang, J., and I Liang, Y. Safe exploration incurs nearly no additional sample complexity for reward-free rl. In International Conference on Learning Representations, 2023.
Amani, S., Thrampoulidis, C., and Yang, L. Safe rein- forcement learning with linear function approximation. In International Conference on Machine Learning, pp. 243-253. PMLR, 2021.
Hutchinson, S., Turan, B., and Alizadeh, M. Directional optimism for safe linear bandits. In International Confer- ence on Artificial Intelligence and Statistics, pp. 658 666. PMLR, 2024.
Bai. Q. Bedi, A. S., Agarwal, M., Koppel, A., and Ag- garwal, V. Achieving zero constraint violation for con- strained reinforcement learning via primal-dual approach. In Proceedings of the AAAI Conference on Artificial In- telligence, volume 36, pp. 3682-3689, 2022.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably effi- cient reinforcement learning with linear function approxi- mation. In Conference on learning theory, pp. 2137-2144 PMLR, 2020.
Berkenkamp, F., Turchetta, M., Schoellig, A., and Krause, A. Safe model-based reinforcement learning with stability guarantees. Advances in neural information processing systems, 30, 2017.
Khezeli, K. and Bitar, E. Safe linear stochastic bandits. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 34, pp. 10202-10209, 2020.
Deng, Y., Zhou, X., Ghosh, A., Gupta, A., and Shroff, N. B. Interference constrained beam alignment for time-varying channels via kemnelized bandits. In 2022 20th Interna- tional Symposium on Modeling and Optimization in Mo- bile, Ad hoc, and Wireless Networks (WiOpt), pp. pp.25-31 25-32. IEFE, 2022.
Moradipari, A., Alizadeh, M., and Thrampoulidis, C. Linear thompson sampling under unknown linear constraints. In ICASSP 0020-2020 IEEE International Conference on Acoustics. Speech and Signal Processing (ICASSP), pp. 3392-3396. IEEE, 2020a.
10

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Moradipari, A., Thrampoulidis, C., and Alizadeh, M. Stage- wise conservative linear bandits. Advances in neural information processing systems, 33:11191-11201, 2020b.
Wu, Y., Shariff, R., Lattimore, T., and Szepesvári, C. Conser- vative bandits. In International Conference Machine Learning, pp. 1254-1262. PMLR, 2016.
Moradipari, A., Amani, S., Alizadeh, M., and Thram- poulidis, C. Safe linear thompson sampling with side information. IEEE Transactions on Signal Processing, -76775 2021.
Yang, T.-Y., Rosca, J., Narasimhan, K., and Ramadge, P. J. Projection-based constrained policy optimization. In International Conference Learning Representations, 2019.
Pacchiano, A., Ghavamzadeh, M., Bartlett, P., and Jiang, H. Stochastic bandits with linear constraints. In Interna- fional conference artificial intelligence and statistics, pp. 2827-288.... PMLR, 2021.
Zhang. T., Ren, T., Yang, M., Gonzalez, J., Schuurmans, D., and Dai, B. Making linear mdps practical via contrastive representation learning. In International Conference on Machine Learning, pp. 26447-26466. PMLR, 2022.
Pacchiano, A., Ghavamzadeh, M., and Bartlett, P. Contex- tual bandits with stage-wise constraints. arXiv preprint Stti:24001080106 2024.
Zhou, and Ji, On kernelized multi-armed bandits with constraints. Advances in neural information processing systems, 35: 35:14-26, 2022.
Paternain, S., Calvo-Fullana, M., Chamon, L. F., and Ribeiro, A. Safe policies for reinforcement learning via primal-dual methods. IEEE Transactions on Automatic Control, (3()):332111366 2022.
Qiu, S., Wei, X., Yang. Z., Ye, J., and Wang, Z. Upper confidence primal-dual reinforcement learning for emdp with adversarial loss. In Larochelle, H., Ran- zato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15277-15287. Curran Associates, Inc., 2020. URL https::/procc...ngg....mm neuriss oo co.paper_fileseeecc /cc/ppeerfflle//pperr////////1
Paper.
pdf.
Shi, M., Liang, Y., and Shroff, N. A near-optimal algorithm for safe reinforcement learning under instantaneous hard constraints. In International Conference on Machine Learning, pp. 31243-31268. PMLR, 2023.
Tessler, C., Mankowitz, D. J., and Mannor, S. Reward con- strained policy optimization. In International Conference Learning Representations, 2018.
Vaswani, S., Yang, L., and Szepesvári, C. Near-optimal sample complexity bounds for constrained mdps. Ad- vances in Neural Information Processing Systems, 35: 3110-3122, 2022.
Wei, H., Liu, X., and Ying, L. Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and constraint violation. In Interna- tional Conference Artificial Intelligence and Statistics, pp. 3274-3307. PMLR, 2022.
Wei, H., Liu, X., and Ying, I.. Safe reinforcement learning with instantaneous constraints: The role of aggressive exploration. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 21716, 2024.

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
The appendix is organized follows. Appendix A contains the simulation details presented in the main part of the paper. Appendix B includes the proofs for bounding the covering number in both star-convex and non-star-convex settings, stated in Theorems 5.4 and 5.1. Appendix C contains the detailed proof steps for Theorem 5.4 in the non-star-convex setting. Finally, Appendix D provides the proof steps for Theorem 5.1 in the star-convex setting.
A. Experiment Details and Star-Convex Simulations
A.1. Detailed Setup for Section 7 Experiments
Problem Statement We consider a merging scenario at an intersection where an autonomous vehicle must navigate safely and efficiently. The intersection consists of main road with another vehicle already traveling on and merging lane where autonomous vehicle starts. The autonomous vehicle needs to decide whether to wait for the car the main road to pass to accelerate and merge into the main road before the other car arrives. Please see Figure 2 for sketch of the scenario. The objective of the autonomous vehicle is to maximize the traversed path toward a goal point within finite time horizon while adhering to the following constraints: 1. Avoid collisions with the car on the main road. Keep the vehicle within the lane boundaries. In our experiment we assume that, the car includes a trained collision avoidance module (referred to as Collav), which identifies infeasible actions that could lead to collisions, threfore the RL agent does need learn collision avoidance constraint. However, lane-keeping is a constraint that the RL agent must learn during its interaction with the environment. Please see Figure 5 for brief diagram of our problem.
Accelerating to merge into the main road is the optimal choice in this scenario, as it allows the vehicle to traverse a greater distance toward the goal point within the finite time horizon. However, due to the unknown dynamics of the car, the RL agent must adopt a conservative strategy, denoted as safe, to avoid losing control when accelerating.
Vehicle Dynamies
The vehicle's dynamics are governed by following equations:
F++1
+ o + u ef flu + a tau f( + +azu))
yr41
(8)
where Ft, Vt represent the vehicle's position, and vi, of are its velocities. The control inputs ut; uy affect the velocity through unknown parameters a1 ag. The function f()) models nonlinear dynamics, which are linear in most regions but saturate car's speed limits as illustrated Figure 4. For simulation purposes, we set (a1, 02) = (0.5, 0.5).
Dynamics function
0.4
0.2
R60
0.0
-0.2
-0.4
-1.00
-0.75
-0.50
-0.25
0.00
0.25
0.50
0.75
1.00
x
Figure 4. Plot of fxx showing the dynamics function behavior.
12

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Lane-Keeping Constraint The lane-keeping constraint ensures that the vehicle remains within the lane boundaries:
Rlanes {(r, y) R?? ymin S y ymax), where ymin -0.3 and ymax 3 This ensures that the vehicle does not drift out of the lane.
Collision Avoidance The collision avoidance module Collav restricts unsafe actions the start of each episode (h = 0), Specifically, actions that result speed within 1 jog + + S 1 are prohibited. For other timesteps (h E [M], the module does not impose any restrictions. At 0, the resulting restricted action space is shown in Figure 2. The time horizon for the simulation is H = 3.
16
Initial Safe Policy. The initial safe policy, safe is defined as: x (x))
1
where yf 0.001 is
small conservative reference speed, and Ni 100000 and K2 0.5 determine the reaction strength deviations.
Algorithm Implementation We implement Algorithm 1 for this setup using the feature vector: ø(s, a) = (x., y, u", UM, "M,"" w", u²]T. and express the lane-keeping constraint as: yin < (d(s,a), < max where 7" is an un- known parameter vector. The total number episodes set to K 1000, with 0.1 chosen to satisfy Assumption 3.2. The pure exploration parameter K' is selected from {1, 300, 2000). We discretize the action space into grids of size address optimization challenges the non-convex setup. However, our state space is continueous. Moreover, in order speed-up Algorithm, update the Q-function's 's parameter (w)) every 2 epochs.
Results Figure demonstrates that after an initial exploration phase, the agent converges to the optimal policy, achieving sublinear regret. Additionally, Figure 3 shows that the y/ values remain within the lane boundaries throughout both exploration and exploitation phases.
13

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Agent
Lane
Collay
keeping
Observed Cost
Environment
Safe Set
Observed Reward & Next state
Decision Making
Next action
Figure The diagram of autonomous vehicle example: Agent interacts with the environment and observe feedbacks on its location and speed. It utilizes the feedback imporove the estimation of lane keeping. Then, using lane keeping and trained collav module it provides the safe set of actions. The decision making module uses the feedback to enhance the estimation on Q function, and then utilizes the saf set make the next decision. Note that the Collav block is trained prioir and not learning it, but lane keeping and Decision Making are the blocks that RI. agent needs to learn.
14

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
optimel Poliy
35000
K' =2000
30000
42020
25000
30000
Negret
20000
15000
20003
10000
5000
Episode
Epsicee
Figure Regret our method (NCS-LSVI) over more episodes. showing sublinear behavior for K' 2000.
Figure 7. Regret sub-optimal but safe baseline that stays within an e-neighborhood of the initial safe policy.
Cumnuaaivve Cunsrant Vidittin
2300
1000
1340
38000
20000
20000
20000
40200
Tpeea::
Erisade
Figure Regret of LSVI-UCB (Jin al. 2020), which achieves low regret but violates constraints.
Figure 9, Cumulative constraint violations LSVI- UCB, showing linear growth. The other two methods have zero violations, so no violation plots are included.
A.2. Baseline comparisons.
Figure 6 shows the regret of NCS-LSVI over more episodes, demonstrating sublinear growth for K' = 2000. Figure 7 shows the regret of sub-optimal but safe baseline constrained to e-neighhorhood of the initial policy.
Figure shows the regret of LSVI-UCB (Jin et al., 2020), which achieves lower regret but violates constraints, as shown in Figure 9, where cumulative violations grow linearly. The other two methods have zero violations, so no violation plots are included. We will add these results the final version.
15

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
A.3. Experiment in the Star-Convex Setting
Based on Lemma 5.3, observe that in non-star-convex settings, without pure exploration phase, the covering number is lower bounded by the cardinality of the state space. However, Theorem 5.1 establishes that in star-convex settings, the covering number can be properly bounded without a pure exploration phase, ensuring sublinear regret. To validate this argument, we conduct numerical experiments in our autonomous vehicle setting, where the state space is continuous and has infinite cardinality.
retain the same setup as in the non-star-convex scenario but remove the collision avoidance module, making the decision space star-convex. Specifically, we assume that the red car Figure is no longer present. According Theorem 5.1, we expect that skipping the pure exploration phase in Algorithm (i.e., setting K' 0) will still allow the RL agent to achieve sublinear regret. The regret graph in Figure 10 confirms this expectation, showing that Algorithm successfully attains sublinear regret. Moreover, the agent consistently satisfies the safety constraint, never deviating from its lane throughout leamning
8000
7000
5000
Regret
4000
3000
2000
1000
2000
4000
6000
8000
10000
12000
Figure Regret vs. episodes NCS-LSVI an star-convex autonomous vehicle merging scenario.
16

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
A.4. Effectiveness of Linear MDPs in Practice
Linear MDPs are widely studied and effective in practice. Zhang al. (2022) demonstrate state-of-the-art performance on MuJoCo and DeepMind Control benchmarks, and Jin al. (2020) show that linear MDP solutions offer regret guarantees when the true MDP is nonlinear. Also, safe sub-optimal policy often be identified offline using domain knowledge (Amani et al., 2019; Khezeli & Bitar, 2020; Shi et al., 2023).
B. Bounding Covering Number in Theorems 5.4 and 5.1
In Appendix B.1, we present our results for bounding the covering number of the function class of individual value functions in the non-star-convex setting defined in Theorem 5.4. Similarly, Appendix B.2 contains results for the star-convex setting defined in Theorem 5.1. Appendix B.3 provide proof for Lemma 5.3. Additionally, Appendix B.4 provides proofs for auxiliary lemmas used in the previous sections.
Before presenting the proof, we define the function class value functions used in our work below.
Definition B.1. Let V denotes a class of functions, (i,, where V(.) mapping from & to IR with the following parametric form:
V(s) e min(max((6(()))) w) (() +A- a), H} aeA
(9)
s.:: (0(8, ((,,, ()) o(s ((s, S
where the parameters (w, n, B, satisfy ||m||| s Lw I s Vd, Amin (A) 2 A, B E [0, B}. and 8r E B". Also,
9A-1,8 g is defined follows:
IA-1 (s & (3110(s,) -f(s,0")lAa-
(10)
B.1. Covering Number in Linear MDPs with Instantaneous Hard Constraints under Local Point Assumption
Now we state the next Lemma that provide proper upper bound for Nº:
Lemma B.2. (Covering number in linear MDPs with instantaneous hard constraints under Local Point Assumption). Consider the setting of Theorem 5.4, and let K < Then there exists finite set of functions Vn V such that for all k > K", there exists V VR such that (Vst(V, V Moreover, let No be the cardinality for V.c. then with probability
of at least 1 5, will have the following:
8( S vX
log(Na) s d log(1 + 4Tw log(1
+H) + H)
RT
(11)
32vdB²
32Vd(B')2
at +
3H)²
d² log(1+ + dx² log(1 +
VA
2r2
Proof: We equivalently define A 32A-1 and A' g22 A and reparameterize the class function V as follows:
V() min (ma (0,x a), w) w) (1o(,,a)l:: + (,,,,,, H}
(12)
8.1 ()(,,a) ((,,a))((,a)))) )(,aa),))) + |1l0 - o(. ((.a)))lx)) S r,
B² where ||||| < X and ||Al|| < (B')² x
Now, for & 2 K', let V1 = v be the value function generated by Algorithm 1 during the
phase
(secon phase), and V2 an arbitrary function V. Then, there exist parameters (w1, M, A1, A1) and (w2, 72, A2, Ab) such
17

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
that:
(s(s) min ( a)), w1) + (lo(s. + H aEd
s. : (o(s, a) (") m) + (l((s, 00s ((s,,)))l4; S
(13)
Va(() beg
0),
944,
H) H}
8.1: (o(s, ((8, 12) 12) (1((s 0(s a,)l T
Now, define V/3 as follows:
Vi(() = min miinmax w1) w1) + (lo(s. + g a), H} aEA
(14)
s.l: (0(8, ob (88 a 12) + (l)(s,)) ((s, (3))las))) S
Now, using triangle inequlity, for all E S, we have:
[+) - V2(()] S -V(()) +V2(s)))
Va(+))+
V3(()
(15)
Now, applying the triangle inequality for all E S, we have:
(i(() - (2() S [V((s) - V3(()) + (V2(s) - Va(s)).
To bound (s) - V2(5) suffices to separately bound Vi((s) - V=( and (V2(s) - Va(5)), Notably, V/2 and V/3 share the same constraint parameters, resulting in identical feasible sets. Therefore, their difference can be bounded by the difference in their objective parameters. On the other hand, Vi and V3 have differing constraint parameters, leading to different feasible decision sets. In the following, we provide bounds for each of these terms.
Bounding (V( V3) Note that (i(s) Vi after pure exploration phase of Algorithm i.c., k 2 K'. Thus, show that if the differnce between the constraint parameters of V1 and V/3 are small enough then their feasible set also does not change drastically as explained in the following Lemma:
-A2-- where ||-Ile denotes the Frobenius norm for matrices, and assume A I 2-- For each s E S, let ((8,G)) represent the solution of the constrained optimization problem associated with V1 = Vi for k 2 K'. Then, with probability of at least - ô, there exists 03 E I, 1] such that asglls, (s, a + (1 a3)((s, a feasible for the constrained optimization problem associated with Vz. Specifically, there exists an action 0g E A such that ø(8, ((8,03) = a30(1, a7) + -3))(1 a²), and the following holds:
Lemma B.3. (No dramatic changes in the estimated action set). Let A = -11l
((b(s, 03) o(s, a(),a)), 12) + 10(s, a3) - (65, al)l ST
The proof of the above Lemma is provided in Section B.4.
Using the above lemma, we can immediately derive the following result: Lemma B.4. For each S, with the probability of at least 5, the following inequality is satisfied:
A
Vi(() Vz(()
H VIAAiII))
The proof of this lemma can be found in Section B.4.
Now, simliar steps can be applied to get (s(s)) Vi(8) S F+
[H + A1lle) Thus, we will have:
И + | | < H VilAille).
(v) Va(s) < A
(16)
where the last inequality obtained by the fact that (16(1 we will have:
A <
Now, substituiting A = Im -1ll22l +
VIIA A' in
++
18

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
di B VX
1 + v Ai A.
[V((s) V3(8)] <
H
-
(17)
where we used the fact that ||||| S van²
vx
Bounding [2((s) - Va(s)]
To bound (V2(s) Va(5)), we follow a similar approach to Lemma D.6 in (Jin et al., 2020):
(V((s) V3(s)]
sup aed
(d(s, wi) + a|)(,, (8,,)(0,a)
- (o(s, a), | - gag.1
(18)
<1w w'll + VIA A2l1e + sup 99,; (s, a) 9az, 18,, aEA
where the first inequality follows from the fact that V2 and V3 are maximized over the same action space (see Equations (13) and (14)), and the optimal solution the constrained problem upper bounded by the optimal solution to the unconstrained problem.
Now, it remained to bound Su (s, a) (s,,1 a)). Thus, we state the following helpful Lemma:
Lemma B.5, Given PSD matrices A1 and Aly. the following inequlity holds:
2H VIAA -21lr
sup 19, (8, S
8,0
Proof:
The proof of the above Lemma is provided in Section B.4.
Now, by applying Lemma B.5 to Equation (18), we can bound [V((s) Vs((s) as follows:
2H
(2)))) Va(s) || w2ll VI
A2
V |4 Abll
(19)
Bounding Vi(s) - V=(s)]: Combining Eq. (17) and Eq. (19). with the proability of at least - 6, we have:
(s(s) Vi(()) < [v)(s) V3(()) + V2(s) Vs((s)
s H d B
1m 72ll / A 1/2lF
2H VIAA Ablle (20)
+ ||w well
VIA
Azlle
V
Final step. Let C,, be -cver for (w E Rd ||l|||
L and C, be
RT
cover for { E Rd || S Vd).
4 vx +1))
x² Also, let CA be the -over for (A e Raxd ||||| s vas² }. and let Ca. be the 16
R²T"
-cover for (A'
16
VA +3H)²
Rdxdl ||'l|| S vdB²), ). By Lemma D.5 in (Jin et al., 2020), we have:
8( d
C..l < (1+
8L
|C,1 (1
vx
+ H)
)d
KT
(21)
32VdB²
32 32vd(B') 2
d
+ 3H)
CAl 5 (1+
CAl $ (1+
vX
)d
2
19

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Now, by Eq. (20), for any V Vi generated by Algorithm and k 2 K', there exist w2 E C. 72 Cy. A2 CA. and
A/2 Car such that:
dis V2) sup (Vi(s) V2(s)] s
Hence, it holds that N₂ - 1c [Cy] [Cal [C which yields:
log(Na) S lo.l( + log([C,() + (log((Ca)) + log( Carl)
8( 8122B + H)
s d log(1 + 8L ) ) + log(1 +
VA
)]
KT
32) (d 2 +3H)² vx
32vdB² Ax² ) log(1 +
d [og(11
Xr
B.2. Covering Number in Linear MDPs with Instantaneous Hard Constraints under Star-Convexitt Assumtion (Theorem 5.1)
Here, bound the covering number for star-convex cases. The main difference from proof for the Local Point Assumption lies in Lemma B.3, where we show that in the star-convex case, even when K' = 0, the estimated safe set remains stable under small variations in the safety parameters.
Lemma B.6. (Covering number in linear MDPs with instantaneous hard constraints under Star-Convex Assumption). Consider the setting of Theorem 5.1. Let be a positive number. Then there exists a finite set of functions Vx V such that for all k E [K] there exists V Vn such that dist(V V, Vih) S Moreover, let No. be the cardinality for Vno then we will have the following:
J VA
log(Na) s d log(1 + 4Lw _ ) log(1
8(
+ H)
(22)
32vd(B') d
d² log(1 + 32v log(1
+ +HH
Vx
An?
2r
Proof: We equivalently define A 52A and A' 322 -1 and reparameterize the class function V as follows:
V(.) min ( (axxmaxxxx)0m (0(., w) + (|((, (.,, H) aEA
(23)
s.t ()(. -(, + (lo(..a) - o(., a(..)))) S
8² X and ||A'|| < (B') where ||||| S
Now, let Vi V be the value function generated by Algorithm during the exploration-exploitaiio phase, and V22 an arbitrary function in V. Then, there exist parameters (w1, 71, A1, and (w2, 72, A2, Ab) such that:
(i(s) = min(max(6(s. a), + [|o(s, a)lla, + (4,,1ss,0) ()))), H}
s.t (o(s,a), + [| ST
(24)
V/(() min(max(((ss))) + ((o(s,)))lad) (s,,,, H)
s.t (o(s, m2) + | a)}la; TT
Now, define V3 as follows:
Vs(s) A min(max(((s.d))) mn) ||o(s, aEA
al)a, l((ss (8,,1 H)
(25)
s.t (0(s, a), 22) + || a))l1;)115))) T
Similar to our Proof for Lemma B.2, we can write V(((s) - Vs(s) < V1((s) - Vi(()) + (V((s) Va(s)]. Thus, to bound
VV (s) V2(s)), suffices to separately bound (s) Vs((s) and V2(s) Vs(s)).
20

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Bounding [V((s) V-(+)]- Now, provide the counter part of the Lemma B.3 for the Star-Convex setting stated below:
Lemma B.7. (No dramatic changes in the estimated safe set under Star-Convexity). Let - Ih2 1ıl- V A2lla
where II-Ile denotes the Frobenius norm for matrices. For each E S. let Ø(s, ai) represent the solution of the constrained optimization problem associated with V1 = = for E [K] Then, there exists 0x E [ such that ago( ai) (1
0'y) (s, ag) is feasible for the constrained optimization problem associated with V3. Specifically, there exists an action
ag E A such that (88, da) = a30(8, ai) + - (8)) a²), and the following holds:
(Ø(s, 0s) - 0(s, (aa,),)) 72) + (lo(s, az) a(s,a,)lA,, ST
(26)
The proof of the above Lemma is provided Section B.5.
Remark B.8. The key difference between Lemma B.7 and Lemma B.3 lies in their applicability: Lemma B.7 holds for all k E [ whereas Lemma B.3 is valid only for k 2 K" with high probability. This distinction is the primary reason why the
Pure Exploration phase in Algorithm is unnecessary in star-convex settings.
The remaining steps are identical to the proof steps outlined in Lemma B.2. In fact, using Lemma B.4 we will have:
diB
In - 72 + VIA Ab
[+((s) - va(+)] S
(27)
7
Bounding [V((s) - Va())] Now, applying Lemma B.5 on Eq. (18) we get the following:
2H [2((s) V3(()) [w] w2ll + VIAI A
T V 11A A211
(28)
Bounding [V((s) [=(s)]: Combining Eq. (27) and Eq. (28), have:
(((()) V2(()] S (s) Vz(() + [s( Vs(())
< H di B
1l - -22ll v V AgllF
2H
VIIAA Abble (29)
+ || w2ll VIIA - A2l1F +
VX
Final step. Let C.n be the --cover for (w E Rd ||m|||
S L. and C., be the
KT 1 +
cover for (r E Rdl || S vdJ.
L Also, let CA be the i6 -over for {A E Rdxd |||||= I
van" x ). and let CA be the
R²7² -over for {A' e
16(44 4381²
vdB², }. By Lemma D.5 in (Jin et al., 2020), we have: Rdxd ||'l| I A
d + H
8.m Cw S (1+ +
1C +1
vx
jd
K
KT
(30)
32
32 3 2 dt
+ 3H)
CAl S (1+
vx
dR?
2r
Now, by Eq. (29), for any V1 V2 generated by Algorithm and A E [K], there exist w2 E Cw. 72 E Cy, A CA. and
A/2 C.' such that:
dis, V22) (V V2(5)| S k
Hence, it holds that N₂. S |Cmml [C,] [Cal [Carl, which yields:
21

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
1og(Nx) S log((Cw.)) + log([c,() +og log((Crrl)
8( y +
s d log(1 + 8L _ + log(1 +
H1)
VA
)]
d log((1 32vdB²
(") +HH)
+ log(1 +
vx
Ax²
2r
B.3. Proof of Lemma 5.3
Proof: Let V" - fey E V E (-r( Firsly, show that for all u/, v/ E V" with of + vy, we have supses [s((s) - (>))
2 3. To prove this, note that there exists i, E N such that vf" t and vy vg. Now, without
loss of generality assume that i < Thus, for j we will have: v (i) but ()) = Thus,
2
1 3 3
Yel 1/2 E V" such that of + m/ sup lu
2 (s)
(31)
sEB
Now, to complete our proof, we use a contradiction strategy. Assume that V is k-covering for V such that [V*| S | 1 and x < Since V" is k-covering, for all v" E v", there exists a v' E V such that
sup sE3
(s" - (()) < k K
However, since V has one fewer element than V", there must exist two functions 8/i vy E V" and one function 11 E V such that
(s) r1) K
and
suplo"(s) 2s),(5)) s
.E3
s53
However, this implies:
sup (s) v8) SES
sup sEB
(s) - 2s, + (v),(()) - (s))
(32)
S sup (s) (5)) sup (s)(s) 21)) s 2x <
SEB
Thus, combining Equations 31 and 32 we will have:
1
S sup (s))s (5 <
3
se8
which is contraditction and it completes the proof D
B.4. Proof of Lemmas B.3 -B.5
Before we delve into the proof state the following helpful lemma: Lemma B.9. For any 8 (0, 1), let K' > Sd for all (s, a), and k > K':
log( Hd). Then, with probability least 1 8, the following inequality holds
2
(0(s,a) 6(s (1))
o(s, S xt A (lo(s, o(s,a
Using Lemma B.9 we can immdiately prove the following Lemma as well.
Lemma B.10. Let K' = max Edd log( dH 2d 1692
})}. and define A3 Al 16) ST- 5..
- For all
K K', with probability at least 5, we have A (s) C ()(s).
22

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
The proof of Lemma B.10 is provided in Appendix C.4.
Now, we ready for the main proof:
Proof of Lemma B.3
Bounding difference between safety values
First of all, we want to bound the safety values of Vi and V3:
((s,a) ((((s,)) p(s
|0(s, a) - 0(s, (9 (0(s, a) o(s, m) + (l0((,))) ((s,a))llay (10(s, - o() 72 -2-7)) m1) + [|| a) ((s,, dl)l (1)(s, ((s,aa))1.. 1.)
$ a) 0(s, Ill (lh7 - 721l + / || - AQll)
(33)
2 11 - -21l + v ||4 - A/ll = 22
where the last inequality obtained by Assumption 3.2 that ||+||| S 1.
Existence of the feasible feature for Vg:: Let (s) - fa A (,(s,)), 1h) <T-1) t). Then, we decompose the proof into two sub-cases:
Case 1: af E (s),,, then we show that of is feasible for the optimization problem of V/. Using (3. we will have:
(ø(s, az) ((s, 12) + (l az) - ols, a,)l S (0(s, (o(s,at)-(ss,. - o(s, a() 71) + llo(s, az) o(s, ((s,))))l4; + A
(34)
Now, on the event E, since V1 is the estimated value function computed by Algorithm (recall that 1/1 V%,,, we have:
(0(s, aj) - -(s a(s,a)), m) + (l)((s - 66s, 1,),, + + S (ő(s,aï) - o(s, (,), 21loos, o(s, e + 24 (35)
But by Lemma B.9, for all K 2 K' we will have:
(0(s, Mss a4), ()) + 2[]o(s, aj) - o(s, + < (6(8,at) - 0(s, (2) + + +A
(36)
Now, by the Assumption of Lemma B.3, we have A < 1.z using Assumption 2.3, and since aj E Ai (s) we will have:
(6(s, af) o(s a²), m) + 21lo(s, aj) - dss,a")ll;; + +AST + L + =T
(37)
2 2
Now, combining Equations (34-37) yields:
aj E Ai, (s)
(o(s, o(s, d(s,a"), 12) + (lo(s, at) - ((s, ,,ll, ST ST
(38)
which implies that 0g = aj is feasible for the constrained optimization problem for Va8 and completes the proof for case
Case 2: Now, we only need to show the proof for the case that oj E (+) n ($)... where (Ar, (s)) is the complement of the set Ai (s), and (s() the feasible set for the optimization problem for V (recall that V1 V/A) Note that of (A) (z)) O AA (s) implies that
T-e (Ø(s, ai), 7h) r, which implies (To..a)))))) d( 7%
Then, by Assumption 3.2 we have añ(s, at) (1 ()((s, a E F.. where (o(a.a))nn)) i.e. there exists
23

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
a' such that ((s,a') = ad(ss ai) + (1 a))((s Now, since a' Af), from Case 1 (Eq. (38)) we have that:
(o(s, a') (s a.), 72) + 1lo(s, a') - o(s. d T,
(39)
which implies that a' is feasible for the constrained optimization problem of V33
On the other hand, let a' r+A then we will have:
(('')(s,aj) + (1 ('))((ss)))))))) aj)) ais, 72) + at) + -[00)(()s)))00000()==))=====)))) -(s
a()))))))))))) 72) -0) (lo(s, ai} o( a.)) A/
(40)
<a'((((s, ai) o(s -²) m) + (1, aj) o(s, ()),;"))a;; + A) ST
where the last ineuqlity obtained by the fact that oj is feasible for the constrained problem of V,, and a' = =fI..
Now, let 03 = max(a, a'). Since (
S 0g 1, we can apply Assumption 3.2 find that 0g0(s, 8, aï) +
(1 ( aQ) F,, i.c. there exists an a3 A such that o(s, 03) azd(ss, as) + (1 a3))(ss a²). From (39) and (40), it follows that a(s, 0z) is feasible for the constrained problem of Vg, i.e. (Ø(s, as) ((), 72) + [lo(s,ag) ag) - 0(8 al)l ST.
Proof of Lemma B.4 Using Lemma B.3, there exists an action as which is feasible for V3(.). and Ø(s, as) = a330(s, aï) + (1-oa)0(8, a?) for some E 1743, 1]. Thus, we have:
Va(s)= 2 min (d(s, as), w1) + [o AAl + I a2), H}
= =min (aac((s + (1 (2))))))00)0) 2),, w1) + |lagd(s af) + (1 (g))((s,))))1..
+ +1[(a30(s,a)) (1 ag)d(s, a.)) - ols, Mll H}
(41)
min (as(( ( a + 6(8 at (1 as))ll((ssss m}
I min (as((((s ai), wi) (lo(s, al) 6l. a alll;) m} (1 aa))lo(s,
N (s) ( dl)
where the last inequality obtained by the fact that 0g S 1. Thus:
(s) Vs(s) S (1 - (6d6_
(42)
Now, since V1 S we can continue E42) as follows:
A
A
vi(s) V3(s)
(H [(((s,)))la,)
<
HH V(AlF)
(43)
T
where |A 1 is the Frobenius norm of the matrix Aj.
Proof of Lemma B.5: Consider an arbitrary pair (s, a), then we have:
2H (1o(s, a) (oss,a)))ss,,))) a?)laa || a)
al) -
2H |1
1
(44)
(s,, 0) -
T
where, the last incquality is obtained by the fact that |/z vol S V x y for any x, y 2 0. Now, using the fact that Frobenius norm is larger than matrix-norm we can continue:
VII A2ll
2H /IA - -
Ig (s,a) - (s, < 2H
(45)
7
The last inequality completes the proof. 0
24

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
B.5. Proof of Lemma B.7
Proof:
Bounding difference between safety values
First of all, we want to bound the safety values of V1 and V3:
V(s,a): ( + ||o(s a) - o(s, ((s,a])ll,; (ō(s, a) o(s, m) + (lo(s, a) o(s, 1441
$ (()(s, (ll..,)))(ss..)))) m) + (Il((s,)) a) 0(s. (.s.a ( 0(s a(s
(46)
s (11((,,0) a) - o(s a Ill (lm - 72ll + VIIAi - A2l1)
< 21h1 - 7211 + V || - A22 = 2A
where the last inequality obtained by Assumption 3.2 that ||o||| S 1.
Existence of the feasible feature for Vg:: By Assumption 3.1 we have a o(s, (1 (1-a))((s E Fs, where a = 7+A
i.e., there exists an a' E A such that o(s, a') - col(,, at) + (1 a))(s,a)) ag). Now, we show that a' is feasible for the constrained problem Vg. In fact, we have:
(ø(s, a') (ss a.),, 72) + (1 a') (ss a a9)1, (l6(s, a)) 72) + llo(s, ol. (?)))a))))
(47)
Now, using (46) we can continue (47) as follows:
(0(8,a'), 72) + [1 a') Ia, = a ((0(s, ai) ((8 ag), 12) + [lo aT) ((. 1 a (((ss ai) - ((5 an), 7i) + llo(s, añ) 0(s, dg)l + A)
(48)
T+ (T + A) =
where the last incuqlity obtained by the fact that af is feasible for the constrained problem of V1, and a - Thus, (ő(s, a') 72) + () a') IlA,,, S r. which implies that a' is feasible for the constrained problem of V3. Now, setting 43 al and 03 a' concludes the proof. D
C. Proof Steps of Theorem 5.4
We start with the following definition:
Definition C.I. For any fixed policy, the event Eg defined
&g A (Ko(ss, a), w (T,(,a) Eg ( (V7 V (s)(ss) 3:ll0(s, a))(a))))))))) 4,
(49)
V(a,s, s, EAX (MI x [K]]
where 31 C/3 d.H, / log( 2dT and Cj is constant.
Lemma C.2. Under the setup defined in Theorem 5.4, for all K 2 K', there exists a constant c3 >> 0, such that for any fixed 8 E (0,1), the event & holds with probability at least 1 8.
Proof:
Similar to the proof steps of Lemma B.4. in (Jin et al., 2020) we will have:
(d(s, a), w - (7, a) (6(s, a), w w
(d(s,a). -(AA)) - w + (o(s, (A
Σ 2h
PA PAVK (5%,
(50)
02
(d(s,a), (Af)) (A Σ Pr (Vh+1 Vi+1) (sh.a)))
93
25

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
We start with bound ing |92/. which is the term related to the covering number.
Bounding [42| For our problem,w we cannot directly utilize Lemma B.2 from (Jin et al., 2020) to bound (g2). since in our case Value function is obtained by optimization over (s) instead of A, and Af (s) varies over the time. This makes bounding the covering number challenging. Thus, we first utilize Theorem D.4 from (Jin et al., 2020) to bound [gal in terms of the covering number of Value function in our problem, then, we apply Lemma B.2 to get the counterpart result of Lemma B.2 from (Jin et al., 2020).
We start by applying Lemma D.4 from (Jin al., 2020) on (42). |. to get that with the probability least _ we will have:
[22l < (1((s, ())))
hh Vh+ (+h+1)
Ph V/+ (5% aR]]I
(51)
d
k k+
+ log 2.
8k k² A
6(s $ Vos (M))) a) (4H²
log
where, N₁ is the cardinality of the set of pre-fixed functions Vx C V defined in Lemma B.2. Now, considering the fact that Lemma B.2 from (Jin et al., 2020) implies that || I 2H v dk follows:
Thus, using Lemma B.2 we can continue Eq.(5 as
X
l02l S 0(8 (N
d 1H²
2 log(
+
+
8H dk log(1 +
K V x
+ log(1 +
8((2
X
1)H +
32v dB² (2H
dk
B
3H)
}] + log (2) +
8A22
+ d log(1 + Ax² ) + log(1+
2r
(52)
where h: 2 K' 2 2dH Thus, by choosing k = dH
S 1 2
and taking B = 31 = c3dH v log( 2d2
br ). and B' = B2
k
O(log(1 kl) we will have:
1 < CdH log 2(cs + 1) dkH H
V (( a),
(53)
8r
where C' is a constant.
Bounding qı and 9s:
Similar to Lemma B.4 from (Jin et al., 2020) we can bound terms qı and ga as follows:
((0(s, a), whth - Q7 (s, a) Pn (Vi+ - Vi+ta) (s)
(54)
d2H V (At) + 1921-
Final step
Combining Equations 53 and 54 yields the following:
(o(s, a), w - Q7 - Pr (V.t - VHTti (s)
dKH 87 1)
(55)
22HVXx+ A + CdH v log (2(c3 +
Now, by Lemma B.1 from (Jin et al., 2020), have || vd.d. Therefore, there exists absolute constant cæ such that the following holds:
2dT 8f
((((s, w - (T, - Pr. (V/+1 - vitt (s, a)l S c3 dHl log(
ols (
(56)
Now, we define another important event that ensures safety, i... guarantees with high probability that the estimated safe set by the agent lies within the actual safe set:
26

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Definition C.3. The event & defined & = (s) A (8) v(h, k) [M] [K]].
Our intersts lies in the events that both event & and &g holds, i.c., the actual safe set and value function are approximed properly. Therefore, we provide the following important Lemma:
Lemma C.4. Under Assumption 2.1, for all K K", there exists a constant cg O, such that for any fixed 8 (0, }) the event & = & n Eg holds with probability at least 1 - 22..
Theorem 2 from (Abbasi-Yadde et al., 2011) can be directly applied to our case to show that the event & holds with probability of at least - 5. Similarly, Lemma C.2 establishes that the event &g holds with probability of at least 1-d 8. By applying the union bound, the final result follows. D
Proof:
C.1. Proof of Lemma 6.2 (Optimism)
Having Lemma C,4 in hand, we are ready to prove that Algorithm 1 satisfies the optimism property stated in Lemma 6.2, which is an essential step in the final proof of regret's upper upper bound. We first provide helpful lemma in C.I.I, then in C.1.2 we provide the main proof.
C.1.1. HELPFUL LEMMAS
Lemma C.5. Let k 2 K', where K' is specified in Theorem 5.4, Then, there exists an action a' (s) such that d(s,a') ablss, az)) (1 a))(1, d2), ( for some [7423 - ((a,))) (A 1..
Proof: Condionted on the event E, when ag E A (s), then by Lemma B.10 we find that a" E (s) c Ah().. which completes the proof. Thus, remains to only prove the case that E (A (+)) n (s). Let us assume that a" As) Then,
verify that max (d(e,a)))))) 7+2921 ((s.at)))))))))))))))))))()))))) -(s.a)))(()))))) ( E (1000177) 1).
--
Thus, by Assumption 3.2 we can argue that there exists an action a' such that o(s, a') = ap(s, at) + (1 -a))oss
Now, we need to show that a' E (s) as well. Note that, when a = (((aa)))))))
r-t
then:
(o(s,a'), Th = (0(s, a.), mi) + (1 a)) (o(s)) a()) = a ) wi 0
(57)
where in the second equality used Assumption 2.3, and the last equality is obtained by substituting To(s,ag)
Now, Equation (57) implies that E A (s), and by Lemma B.10 we have E (x). Now, for the other case that ++2 ++2292l0(ss.. ( ((s,8))) 7- conditioned on the event & = E1 n Ez, we can follow the below steps:
0 ~ (0(s, o(s.0"), 0 7h) + o(s a. ollaaa
a((0(s, o(s,0)), + +)) + - ols a (l(.)))((
(58)
< (a(((s,, - (ss nh + 232 ols ol .)
where the last inequality obtained by conditioning on the event & c Now, substituting a with 7423 (a)7))) (58) yields:
S (6(s,a') - ((,,0))))))))) ag), + 32110(8, o(s (...0))))
(59)
5 + 23 22210(ss ann) ((8 a9) 1 (10(s, (a 23 (EW))l
Now, since dh the optimal safe solution, it should be feasible as well, i.e., (6(s, a a.,)); 71t S T. Thus, we can continue
27

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Eq. (58) follows:
0 S (0(s, 6(s, (0)) + 32110(,, ((,, (.)laaa))
(60)
<b a ( 232llo(s, o2,n) -(s, (l,,a))(a ST
T
The last inequality implies that a' E A This, completes the proof of this Lemma.
C.1.2. MAIN PROOF OF LEMMA 6.2
Proof: We employ an induction strategy to establish this lemma. Initially, we define the value functionn at time H as V v (s) 0 for any state s S, confirming the optimism for step H Then, by the induction hypothesis, we assume that for an arbitrary h E [H] 1 I (s) holds for all states s E S. We now need to prove that V (s) V also holds for all states E S.
Consider the case where H S ma (o(s, a), w + (s, a). Then, (s) (s) S H = min (ol,(((s) w +
(s, a), H} = Vi (s) holds, which completes the proof for this case.
remains prove the result for the case where max (0(8, a), w/t (8, H, which implies V7((s) A (s, a) ma (o(s, a), w + by a).
This brings us to analyze two sub-cases. First of recall the definition of Af, & fa A (6(ss,))))) S T -1), then we will have the following sub-cases:
Sub-case one: a E AA, (s)
For this case, by Lemma B.10, we will have: or E Ai(s) c (s). which implies that a²,₁ E (f for all K'. Now, have:
(s) = max (h(s,a) 00(s) = (Ø(s, a5(s) wht + by or,
(61)
(E)
Then, conditioned on the event Eg we have:
(o(s, a..) + (f, af,h)) Q (s, + Es-ra [V 1 (8') ( Bi Billo(s, (t + Ufi at,))
(62)
2 OT (s, (,)) + E. ES (s') - (s')
where the last inequality obtained by the fact that by (8, ahth)) = Billo(s, a Mla + (o, a;, and g 2 Now, by induction hypothesis, for all 8, we have: Vhti (s) 2 V (s). Thus, we can continue Equation follows:
(0(s, a.,)), w w QR (s. + E. PF [Vi (s') V QF' (s, (s, VTT (s)
(63)
Equations 61 and 63 together complete the proof for sub-case one.
Sub-case two: ai E (s)) n Asal In this case by Lemma C.5, there exists an action a' E At(ss) such that 6(s,a') ad(s, a for some a E 7+28%| - ( 1]. Thus we will have:
(s)
max ( (8 (o(s,)d), w/) (s,
(64)
(E))(s))
28

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Then, conditioned on the event &g we have:
(o(s, a') w (s,
2 2h d') + PP V (s)) - - + (s,
(65)
2 2% (s, + - (5') (i + (s,a')
+ 2 Q% (s, + (
where in the last inequality we utilized the induction hypothesis that 1 2 Vit11)) (.). By considering the fact that 6(8, = ar(ss az) we can continue Equation (65) as follows:
(s) (0(5, a)), wht + (') 2 alo(s,0)), wx + (h
(66)
Now, according to the Equation (4) we will have:
(x()aa')= = x (22ll(ss - o(s, ( H (av) (Ballo(s, - o(s, a(),a)))k H
(67)
Now, by setting
continue Eq. (67) as follows:
7
a's) v 1 (1-110=+2)206666 (++2gll0(s 1
H 2 (1 o)
(68)
6(s 6((.))))
Now, combining Equations (68) and (66), and considering the fact that V** < H, we obtain the following:
(+) 2 (o(s,a') w + (s, 2 a(ols, a.), wp + (1 (1- a) 2 V (s),
(69)
where in the second inequality used the fact that when rewards non-negative, then according to Proposition 2.3 from (Jin et al., 2020) we will have: 0 < Q as,a%) (ø(s, a²), w The Equation (69) completes the proof. D
Final Step: Now, according to the sub-case and sub-case 2, we have VØ"" S Vi with the probability of at least 1 8. Therefore, we can say with the probability of at least 1 - the following holds:
T = K
Vot (so) (50) S O.
R= K
C.2. Proof of Lemma 6.3 (Bounding T2):
Lemma C.6. Conditioned on the event E, the following inequality holds:
K
H
K
H
K
H ( at)),
Ta
<
23
(ss
+
(70)
k=
K"
h=1
K=
h=1
K
h=1
Ta.1
T2.2
T2.3
where Sh41 : (P. at)
[ [V
(s')
(
h and 1 = (/((
V (s)))
Proof:
First, by the definition of V and Q we have:
oh = (s(t) - V (s = min min ah),
H) Q (sh. at)
< (s di) - º (sh a
(71)
(p(s); at), w 31110(5h Mll 1 + ( a Q, (s).
29

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Then, the event &, have:
(0(s)) of), w/)) + 1ill0(sh a ( + gh at) Q (sh a
R. (P at) 1 (s')
(72)
0 + ch+ + 23 (1((s at (())laap)-1 + gh at)
Now, note that we have:
K T2 = Σ
k
(+ - VÍ (01) = Σ
8f-
(73)
k=K
k=K
Note that Lemma 6.2 ensures that on the event &, 0 S 8% holds. Consequently, by applying Equations (72) and (73), we can conclude:
K
H
K
H
K
H
T2
S
ch
+
2/1
Σ
Σ
+
Σ
Ih (
(74)
R= K
h=1
R=
KC h=1
A=1
C.3. Proof of Theorem 5.4
Proof of Theorem 5.4 We start by bounding the term To: Bounding T2
To bound the term Tz. Applying Lemma 6.3 we will have:
T2 S
K
H
+
23
Σ
K
H
1005h, + 232H
)
K
Σ
H
(75)
== K''
h=1
k=
K'
1=1
A= K'
h=1
In order bound the first term on the right hand side of Equation (75) note that t forms a martingale difference sequence with bounded norm, 16
H. Thus,
apply Aruma-Hoeflding's inequality:
K
H
d(K K'DH )) 2 1
Σ
Σ
s 2H (K K')H log
(76)
5
K=
k=1
Therefore, with a probability of at least g we have:
K
H
2H (K K`HH log( d(K K'HH
Σ
ch
s
(77)
I=
h=1
Now, to bound the rest of the right hand side of Equation(75) we can Follow the steps outlined the proof of Theorem in (Abbasi- Yadkori et al., 2011), as follows:
232H H
2
Σ
lo(s
+
j at) - (( o.e Ma
K'
H
K
232H
1
K
= 28
( a 11.. +
[1 aft) - p(sti 0 o 1(a
#=1 K=
1=1 k=
K (K- K")
23yH
2,1
(K K') Σ
| at) oss a.t
k=K
(78)
30

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
By Assumption 2.1, given that L 1 and À in Algorithm 1, be shown that ll a
and
( a < dx 1 S Consequently, the following inequality holds:
| a (A, 0)- 2 | a osh ( 2log [+|l0(s) E a - o(5 o.k
a (l)) .).
(79)
Thus, by Equations(78) and (79) we have:
H
a/ () + 232H1
K
28
(K K)
a
(K - K²)
110(s a - 50t (eaton
h=1
k=k
k= K'
N Σ
$ 23
2(K K")
Σ
log(1+110(s), a()
h=1
k=
(80)
13 H
H
K
(K - K")
Σ
log
[1+11(s a/t - 21
h=1
k=
"
2(KK - ('ogleedet((A k.O)) log({4)) + 282H H
231
Σ h=1
2(K - (Lg((dddee) (()) - log((A))
where the last inequality is obtained by Lemma 11 from (Abbasi AbbbasiYaddkori Yadkori al., 2011). Now, considering that |10( a 11,) 1 L, it follows that the trace A is upper bounded by dA + KL2,, and the trace A K- upper bounded by dd 2K Since A K.Q and A, K.A are positive definite matrices, the determinant of them can be bounded as follows:
det(A (.0) < (race(A) K.Q d
dd (K)L?
d dd 2( )d d
K.7) del(A trace(A (A
d
Combining all together yields:
2(K - K")(lg((e) log({d)) 23
2,31
V 2(K - (logldee)) log()d))
r
h=1
h=1
dA + KI2 )d) - log(An)) + 2 H
dd 2X22 )d) log(Ad))
< 23
Σ
V 2(K K'')(lo(((
2(KK - (K')oo(((
d
d
hm1
hml
82H
dd 2KL2 (LK-K))llggl
32Hl
dd + 2KL2 )) Ad
< 2(1
Σ
) =) +
)H 2(K K')dlog((
Ad
(81)
Given that = and utilizing the Equations (78) through (81), we conclude that:
K
H
( a 1i 232H
K
231
10 at) - M(s alt )l
k= K' h=1
R= K'
A=1
(82)
H2H
dA 2KI2 ))
< 2(31 +
H 2(K - -K')dlo((
Xd
31

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Now, by integrating the bounds from Eq. and Eq. (82), we establish the desired upper bound on T2:
T2 S 2H (K (K-RV H')H log( d(K - KOH
B2 H H 2(K (')dlog( dA + 2K
2(3 +
(83)
Ad
Final step follows:
Note that by Lemma 6.2, we have Ti S 0. Thus, by applying union bound we will have the desired result as
Regret(K) K'H + T2 T T2
d(K d(K-K)) KK)H ) 2 > 2(K ( K')dlog(
dd 2X+2KL2
K'H 2H / (K (()K log(
Ad
Safety
The safety of our method is guaranteed by Theorem 2 from Abbasi- Abbasi-Yadkori et al. (2011), stated below:
Lemma C.7. (Theorem 2 in (Abbasi- Yadkori et al., 2011)) Let d E (0, H) Then, with probability at least -H8, the chosen actions by Algorithm satisfy the safety constraints for all episodes. other words, for all (h, k) E [M] [K] (s) C sufe (s).
C.4. Proof of Lemmas B.9 and B.10 Definition C.8. Let A_ -
Proof of Lemma B.9: Our main strategy is to project the problem into R (Recall that is d dimensional hyper plane and then we apply Lemma 1 from (Amani et al., 2019) to achieve the final result.
Reltation of the higher dimensional problem to the lower dimensional space, i.e., IR Recall that in Algortihm 1 the agent samples uniformly from the set of safe actions Dr (s) that we rewrite its definition here for the convenience of the reader:
(*(s) 2 {a E A ||l a) ((s, a?)l =].
(84)
According to Proposition 2.2, by Assumption 3.2, we can define the image of the set (s(s) under the feature transformation ((s,.) .Jas follows:
1
(x, (x)) A (0(8, a +ex
2 o ai E RR)
(85)
where {v:) are orthonormal vectors such that F, o(s, + Span (= (Note that {r]][=] are naturaly orthogonal the vector f² defined in Proposition 2.2). Thus, random sampling from D*((s ) is equivalent random sampling from the following set:
W A (w E Rd-1 ||w||2 = cf
(86)
Equivalency of the result in lower dimensional space
Considering the (q,)S we have: o at) d0s), a +
xx Ei-1 =1 a A.h v, and Φ(s, a) = o(s, o)) +ex E a U; Now, considering the fact that A & -i=1(055)) 07)
6(5%, " (108%, a - (68%, a) + XI, we will have:
32

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
(d(8,a) - ((()))))) A A (d(s,a) d-1
((),a2)) =
d-1
d-1
d-1
(87)
et
XV XI+
n.ll
vt)
ni 0x)
a
2 v.).
f=1
==1
Now, since (1;) dd-1 are orthonormal, we can continue (8. as follows:
(((.,))-((s..))) A N.2 (d(s, u) o(s, a of ) (w==0T
Ala11 Σ (wh) (wg)T
(wara)
(88)
n=1
where in the last inequality, la-1 is the identitiy matrix in Rdd1xd-1, and was E Rd-1, and the i-th element of it is w = =c0,"" and simularly wa E W, and its i-th element is w. ca;
n.h
Applying Lemma from (Amani al., 2019). Let A A & Ma-1+ En= (wx) (wx) T. where wg picked randomly from W. Therefore, using Lemma from (Amani et al., 2019) have:
A_
(w Ah Ahh.-i(w""
1100
Thus, using (88) we have:
(b(s, cls, o(s,aa))) (b(s, - ((s,a))) 2 A
110
(89)
= =(^+ A_ 2 (1)(s,)) 6(s, 2
Final Step. Now, note that AA is Positive Definite matrix. Also, n² (defined in Proposition 2.2) is an an eigen vector of Ah. and the rest of the eigen vector of A%, lies on the hyper- plane H. Thus, using Eq.(89) we will have the following:
()(s,a)- o(s TT) (A**)* (ø(s, a) - ((),,))) s
llo(s, Ó(s 2
(90)
A +
Proof of Lemma B.10 Setting K' 2 max 3d log( (H 24 1682
{)), then by applying Lemma B.9 will have:
82) o(s, ((,,)9)1 s
(91)
Therefore, conditioned on the event & we have:
(0(8,a) 6(8, (.))):n + 32l10(s, ((s, S (0(8,a) ((s, mh) + 222ll1((s,a) o(s, ((s,a))l(a))))- S ()( (1, ((),0)), vh) +
(92)
where the last ineuqality implies that for all a E Ai)s), we will have: (6(s,a) o(s, ( B2llo(s,a) ő(s, ((lls))) S which implies that E A O
D. Proof of Theorem 5.1
Note that our main contribution in Star-Convex cases is bounding the covering number as provided in Lemma B.6. Once we have the result of Lemma B.6, we can apply the proof steps of Theorem in (Amani et al., 2021) to obtain the desired result. However, for sake of completeness we provide the proof steps here as well.
Lemma D.1. Under the setup defined in Theorem 5.4, for all K E [K], there exists a constant cg > O, such that for any fixed 8 E (0, 1), the event &g holds with probability at least 8.
33

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Proof: Similar to the proof steps of Lemma B.4. in (Jin al., 2020) will have:
(0(s, a), w - (s, (o(s, a), w
wx
k-1
(o(s, a). -((A)) - + (0(8, a). (A Σ
2h [V (6/+11))))))))))))))))))))) - Pn P
(93)
R-
(0(s, a). (AR)
Σ
Ph (Vi+t - vi+1) (5% oT))
We start with bound ing [92/, which is the term related to the covering number.
Bounding 122l For our problem, we cannot directly utilize Lemma B.2 from (Jin et al., 2020) to bound l4z). since in our case Value function is obtained by optimization over (s) instead of A, and A (s) varies over the time. This makes bounding the covering number challenging. Thus, we first utilize Theorem D.4 from (Jin et al., 2020) to bound |gal in terms of the covering number of Value function our problem, then, we apply Lemma B.6 to get the counterpart result of Lemma B.2 from (Jin al., 2020).
We start by applying Lemma D.4 from (Jin al., 2020) on (42|. to get that with the probability at least 1 - 2 will have:
102l s (1d(s (A
[V
(8h+1))
Pa.
(8%, af]]
(94)
k+
2.
8k2
$ (A a) (4H²
log
+ log
2
A
A
where, No. is the cardinality of the set of pre-fixed functions Vx C V defined in Lemma B.6. Now, considering the fact that Lemma B.2 from (Jin et al., 2020) implies that || $ 2H follows:
V dk X
Thus, using Lemma B.6 continue Eq.) as
8((2 dk X + 1)H +
B vx
leal S v ((s, (A2)
4H²
d
log(
+ x>)
log(1 +
8H
dk K V X
+ log(1 +
}]
2
A
+ d +[(log(1= log(1 + 32VdB²
dx² ) log(1
32 d2 2H
VX
3H)²
}] + log( 3) +
842
2r2
(95)
Thus, by choosing x == dH k. and setting B = :1 = =cddH log(
2dT
ot ). and B' = 33 O(log(1 (1 + kH)) we will have:
122 & CdH log 2(ca + 1) dKH
(96)
where C' is constant.
Bounding Qı and gs: Similar to Lemma B.4 from (Jin et al., 2020) we can bound terms 91 and ga as follows:
((((, a). whth - (8, Ph (v/t - viTi) (s)
(97)
$ (2 vAllwa (T -1 a) + 1
34

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Final step Combining Equations 96 and 97 yields the following:
(o(s, a), w (T, Ph (V vit+i) (s.a)
2HVdx+ V + CdH log (2(c3 + d
))
(98)
(AF))
85
Now, by Lemma B.I from (Jin et al., 2020), we have || s 2Hvd. Therefore, there exists an absolute constant de such that the following holds:
2dT 87 > ( -A)
(((s, a), a), w - ()) - In (Vi+1 - VT+1) (8, a)l S eg dH
(99)
Our intersts lies in the events that both event & and Eg holds, i.c. the actual safe set and value function are approximed properly. Therefore, we provide the following important Lemma:
Lemma D.2. Under Assumption 2.1, there exists constant cg 0, such that any fixed 8 (0, (0, the event & == El n holds with probability at least - 28.
Proof: Theorem from (Abbasi- Yadkori et al., 2011) can be directly applied to our case to show that the event E holds with probability at least - 8. Similarly, Lemma D.1 establishes that the event &g holds with a probability of least 1 8. By applying the union bound, the final result follows. D
D.1. Optimism Star-Convex eases
Here we prove that Algorithm satisfies the optimism property for the setting of Theorem 5.1, which an essential step in the final proof of regret's upper upper bound. We first provide a helpful lemma in D.1.1, then in D.1.2 we provide the main proof.
D.1.1. HELPFUL LEMMAS (STAR-CONVEX)
Lemma D.3. Consider the setting stated in Theorem 5.1. Then, there exists an action a' E (s) such that 6(s, a')
aΦ(s,a)) at) + (1- a)@(s, d.), ( for some E (=228_l0(0.:2)) (
Proof: Let T+203 (0(,,, -(a, ( Then, conditioned on the event E, we can follow the below steps:
S (0(8, a') o(s, a.), mh + 32l1o(s, a) Φ(s, a ( a((6(s, a.) - (0s 4.), n + Belo(ss, - <(> a (
(100)
I a(o(s, (ss aa),))a) m. + 232 ø(s. a )
where the last inequality is obtained by conditioning on the event &, c E. Now, substituting with
1223:10(sa))-000aa ( in (100) yields:
0 < (0(s,a') o(s a.),,, thh B2llo(s, - o(s, ".)a)llla
(101)
$ + 2+228((((s,0,,,) - lls o?)l (10(s, ai, a"s. Mi 2821lo(s, at,)) o(s, ((s,a)llaato)
Now, since di is the optimal safe solution, it should be feasible as well, i.e., (ø(s, at,)), mh S T. Thus, using Assump- tion 2.3, we can continue Eq. (101) as follows:
0 < (0(s, d') Ó(s a²), th) + B21lo(s, a) o(s, (2).
(T + 2,221 a ((s, ()l(())))))) S
+ 23211 ai - ((s, a l
The last inequality implies that a' E A (s). This, completes the proof of this Lemma.
35

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
D.1.2. MAIN PROOF OF OPTIMISM IN STAR-CONVEX CASES
Lemma D.4. (Optimism): Under the setting of Theorem 5.1, conditioned on the event &, the inequality V (s) S
(s), h(s S x [H), and l [K] holds.
Proof: We employ an induction strategy to establish this lemma. Initially, we define the value functions at time H as V #++ (+) ( = 0 for any state S, confirming the optimism for step H Then, by the induction hypothesis,
we assume that for an arbitrary h E [ V (s) I (s) holds for all states $ E S. We now need to prove that Vi (s) s (s) also holds for all states E S.
Consider the case where H S (a) (o(s, a), wx) + (8, a). Then, (s) s H = min((d(s a), w +
(s, a), H)- V (s) holds, which completes the proof for this case.
remains prove the result for the case where max,EAA(()) (0(s, a), w/)) (8, H, which implies Vs) (a (8, = (a) (d(s, a), wh) + (s, a).
By LemmaD.3, there exists an action a' (s) such that o(s, a + (1 a))(s, a.) for some
(+20a]lo(s.;)) -( 7-1= 1]. Thus will have:
(s) = max (h(s,a) ah( (0(8, a'), w (s,
(102)
aEAt(s)
Then, conditioned on the event Eg we have:
(o(s, wh) + al)
2 º% (s,a') F ( 1 (8') - V (5') - (' +
(103)
2 Q (s, d') + Es (. (s') - V 9t (s, 2 Qh (s, + of
where in the last inequality we utilized the induction hypothesis that V ()) 2 V (.). By considering the fact that o(s, a') = addss a.) + (1 - as)(s, a²), we can continue Equation 103 as follows:
(s) 2 (o(s, wh) + th (s, d') 2 alo(s, w ) + (1 - ()(( (ss,,')
(104)
Now, according to the Equation (4) we will have:
(h a') = v x (32lló(s, a') - (ss a MiMl H = (av) x (ello(s;0)-dd6s::)l0aa0=--
(105)
Now, by setting
2. r. we can continue Eq. (105) follows:
gh(s,a')= = (1-7+ + 2/2 ( az) G(s, a(s,a9)llaa
T
H 2 (1-a)1
(106)
Now, combining Equations (106) and (104), and considering the fact that S V < H, we obtain the following:
(+) 2 (o(s,a'), w + (s, a') 2 a(((s, wp + (1 H) V (s),
(107)
where in the second inequality we used the fact that when rewards are non-negative, then according to Proposition 2.3 from (Jin et al., 2020) we will have: 0 < Q (s, a²) (d(s, aς), w The Equation (107) completes the proof. 0
D.2. Regret decomposition in Star-Conver cases
Lemma D.5. Conditioned on the event E, the following inequality holds:
36

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
K
H
K "
M Co ah)))
Regret(K) K) -
Σ
Σ
ch + 2
Σ
Σ
a a (A)) +
(108)
k= h=1
k=K' h=1
k= h=1
where Sh+11 = B (V
h+t (s (s')1 h+1 and h+1 == (s) VT=² (s))
Proof:
First, we can decompose the regret as follows:
K Σ
Regret(K) K)
(Vo (80) - V/ (80))
Σ (Vo (80) (s0)) + -Vo) (80))
(so))
1=1
k=1
(109)
K
(vo vo² (so))
1=1
where, the last inequlity obtained by Lemma D.4. Now, by the definition of VI and Qh have:
o - Vi - Vi (s = min ab), H3 Q (s ah)
I (sh ah) - 2 (s)
(110)
( ah), w Billo(sh A ( Q (
Then, on the event E, we have:
(osh a wht) + Billo(sh a (1) ( ath Q (sh at
E PP at) [V (s') - Vitt(ss)
(111)
t + +h + 23 10(ss (()g(11))-1 + g ah:.
Also, one can find that the following holds:
K
K
Σ
(* - Vi (s
Σ
5t.
(112)
Note that Lemma 2 ensures that on the event E, 0 0 6% holds. Consequently, by applying Equations (109), (111) and (112), we can conclude:
K
H
Regret( K)
ch
2/
10(s ()) + Σ
(113)
1= 1m
k= 1=1
D.3. Main Proof of Theorem 5.1
Proof: Applying Lemma D.5 we will have:
"
232H1 7
K
H
Regret ()) < Σ
Σ
ck + 231
Σ Σ
a 0l) +
Σ
[0(s) at)
1==1
k=1k= 1=
(114)
In order to bound the first term on the right hand side of Equation (114) note that çă: forms martingale difference sequence with bounded norm, 1ch1 < H. Thus, we can apply Azuma-Hoeffdiin inequality:
K
H
d(K)H 2H (K)H log( 8 )) 2 21-8
IP
ch <
(115)
37

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
Therefore, with probability of at least - ô have:
K
I 52H (K)H log( d(K)H 8
ch
(116)
Now, to bound the rest of the right hand side of Equation(1144 14) we can Follow the steps outlined in the proof Theorem in (Abbasi- Yadkoii et al., 201 1), as follows:
k
h
282H
K
H
2/
(ss a (14.99-1 +
1 a - 19th (1l
7
1=
k=1
H
H
2
( a (1
1+ (
1 att
o(s a..aa.l))
(117)
k=1
K
2B2 H
H
K
$ 2/
1 a (4 +
Σ
K
[o( att - 0(s% a% (
h=1
Ar
By Assumption 2.1, given that L < 1 and À in Algorithm 1, it can be shown that |1 a (n 1, and | a @shh d 1 2. Consequently, the following inequality holds:
( a 11 9 2 log( (1 af (f)
(118)
| a p(s a )1 m 2log (1+10((h) att - o(sh ('th,o%))l ((
Thus, by Equations (117) and (118) we have:
23tH
2
K
(
(1t:0)
K
| at) O6 a al)))
T
h=1
S 2,
2K
log(1+ a ((
(119)
282 H
K
log (1+1|0(hh at) (1 d2
al) )1
T
2K (log(deetAA (QQ)) log(>d)) 282H H
28, Σ
2K (log(det(A ((-1) log(Ad))
(K.)))
h=1
where the last inequality is obtained by Lemma 11 from (Abbasi- L, it follows that the trace K.Q upper bounded by dA KL2. and the trace of k upper bounded by dA 2K L Since A K.Q and A K,7 are positive definite matrices, the determinant of A K.Q and A Ri7 can be bounded by:
al., 2011). Now, considering that [|o(( at || <
det(A)k.0) trace(A K.Q
dd + (K)L2 )d
d
trace(A K.7)
d) 2(K)
det(A <
)d <
)d
d
d
Combining all together yields:
38

---

Provably Efficient RL for Linear MDPs under Instantancous Safety Constraints in Non-Convex Feature Spaces
+ 232H1 "
23
Σ
2K (log(det(A (A - Iog(A"))
2K (A - -log(A4))
h=1
h=1
dA + KT2
2,32 H
H
dd + 2K12
$ 2
2K (log(
Ma) log(Ad)) +
2K
y4) log((()))))
(120)
d
h=1
h=1
B2H
Dd + 2KL2 2Kdlog((
32H
dd 2KL2
2(11
))
2(3
HH
2Kd
Ad
Ad
Given that À = and utilizing the Equations (117) through (120), we conclude that:
K
H
1 a (1) + H8²H
K
H
23
l0(s ahi - 6(5 (2)))
Am
Am1
Am 1 Pam
(121)
H H
dd + 2KL2
- 2(31 +
2Kdl
Ad
Now, by integrating the bounds from (116) and Eq. (121), we establish the desired upper bound on T2:
Regret(K)> s 2H (K)H log d(K)H 8
282H )H 2K (aaA + 2K12
(2
Ad
Safety The safety of our method is guaranteed by Theorem from Yadkori al. (2011), stated below:
Lemma D.6. (Theorem in (Abbasi- Yadkori al., 2011)) Let 8 E (0, H) Then, with probability least -88 the chosen actions by Algorithm I satisfy the safety constraints for all episodes. In other words, for all (h, k) [H] [K]. (+) C Anale (s).
39


Reviews:
[{"review_id": "POkpl4Sxgk", "reviewer": "Reviewer_eWaW", "summary": "The paper addresses the challenge of safe reinforcement learning (RL) under instantaneous hard constraints in an episodic Linear MDP setting. The focus is on scenarios where the set of safe actions can be non-convex (or non-star-convex) – for example, safe actions might form disjoint or irregular regions due to obstacles, as in autonomous driving​. In such tasks, the agent must never violate safety requirements at any time step (as opposed to constraints in expectation or over an episode)​. This strict requirement is critical in domains like robotics and autonomous vehicles (e.g., always avoiding collisions) and makes exploration challenging.\n\nContributions: The paper’s primary contributions are: (1) Provable performance guarantees for safe RL in both star-convex and more general non-convex safe spaces. It derives a regret bound on the agent’s performance: roughly $\\tilde O!\\Big((1+\\frac{1}{\\tau})\\sqrt{\\ln(\\frac{1}{\\tau})},d^3H^4K\\Big)$ (ignoring constant/log factors), where $d$ is the feature dimension, $H$ the episode length, $K$ the number of episodes, and $\\tau$ is the safety threshold​. This bound indicates that the cumulative reward regret grows sublinearly in $K$ (i.e. slower than $O(K)$) under certain conditions, meaning the algorithm learns an optimal safe policy over time. Crucially, safety is never violated with high probability throughout training​ – the algorithm maintains zero constraint violations at all times with overwhelming probability. (2) The paper introduces a novel analytical technique called Objective–Constraint Decomposition (OCD) to handle the complication of a changing safe action set during learning​. OCD provides a way to bound the covering number of the value-function class even when the feasible action set varies over time, which is essential for proving uniform convergence and regret bounds. This technique leverages the geometry of star-convexity, essentially showing that if the safe set is nicely shaped (star-convex), small changes in constraint parameters won’t drastically change the optimal value function​. Using OCD, the authors correct a flaw in a prior analysis from Amani et al. (2021) – an earlier work on safe RL in linear MDPs – by properly accounting for the dynamic safe set in the theoretical guarantees​. (3) For the more difficult non-star-convex case, the paper proposes a new two-phase learning algorithm called Non-Convex Safe LSVI (NCS-LSVI)​. In the first phase, NCS-LSVI performs safe exploration using a known initial safe policy: the agent stays in a local neighborhood of this baseline policy, exploring only actions believed to be safe to gradually expand its knowledge of the safe region​. Once the safe set is sufficiently well-estimated (stabilized with high confidence), the algorithm enters the second phase of normal exploration–exploitation (optimistic value iteration) but restricted to the now-established safe set. This carefully structured approach allows the authors to handle even infinitely large covering numbers by ensuring the effective policy class remains well-behaved. They prove that NCS-LSVI achieves the same order of regret as in the star-convex case (up to constant terms)​, marking the first provably efficient safe RL result for non-convex safe action spaces.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful feedback. We respond to each of your comments below.\n\n**Q1** Is the regret bound $\\tilde{O}(d^3 H^4 K + \\text{const})$ optimal, or can a bound of $\\tilde{O}(\\sqrt{K})$ be achieved?\n\n**A1** Please note that the regret is already $\\tilde{O}(\\sqrt{K})$. The actual  the regret bound is given by  $\\tilde{\\mathcal{O}}((1 + \\frac{1}{\\tau}) \\sqrt{\\log(\\frac{1}{\\tau}) d^3 H^4 K} + \\frac{1}{\\epsilon^2 \\iota^2}),$ as stated in Theorems 5.1 and 5.4. This is already sublinear in $K$, and  the dependence on $d$ and $H$  is under the square root, which matches the unconstrained regret in Jin et al. (2020) up to additional terms accounting for instantaneous constraints and non-star-convexity. We're happy to address any further questions.\n\n\n\n\n\n**Q2** How important is it to know the exact value of $\\tau$?\n\n**A2** In many applications, $\\tau$ is known. For example, in lane keeping, the car can measure its distance from lane boundaries, and in financial or power systems, $\\tau$ corresponds to budget or power limits. When $\\tau$ is unknown, a conservative estimate can be used, and our algorithm and regret bound continue to hold. While this may lead to a slightly higher regret, the dependence on $K$ remains $\\tilde{\\mathcal{O}}(\\sqrt{K})$. The regret’s dependence on $\\tau$ is inherent, as established by the $\\Omega(1/\\tau^2)$ lower bound in Theorem 20 of Pacchiano et al. (2024).\n\n\n**Q3** How would you extend your approach to multiple constraints?\n\n**A3** Our framework extends to multiple constraints by defining $\\mathcal{A}^k_h(s) = \\cap_{j=1}^M \\mathcal{A}^{k,j}_h(s)$ in Line 11, where each $\\mathcal{A}^{k,j}_h(s)$ is the estimated safe set for constraint $j$.  Hence, our approach is readily applicable to multi-constrained settings. We will include the above discussion in the final version.\n\n\n**Q4**  Is the method limited by the connectivity of the initial safe region?\n\n**A4** Unlike star-convexity, which requires global connectivity, the Local Point Assumption only imposes local conditions near the initial safe action and constraint boundary, making it suitable for disconnected decision sets. Our method, NCS-LSVI, is specifically designed to handle such environments.\n\n\n**Q5** Limited Empirical Evaluation\n\n**A5**  Please see our response to Reviewer sJHh, Comment A2.\n\n\n**Q6** How should K′ be chosen in NCS-LSVI?\n\n**A6**  Based on Theorem 5.4, in non-star-convex settings, $K'$ should be $O(\\log(K)/(\\epsilon^2 \\iota^2))$. In star-convex cases (Theorem 5.1), $K' = 0$, so no pure exploration is needed. The choice of \\(K'\\) only affects regret and does not impact the safety guarantee or cause stability issues.\n\n\n**Q7** Can the OCD technique be extended to nonlinear settings?\n\n**A7** ​​ The key insight of OCD, decoupling the effect of Q-function estimation from that of the estimated safe set, naturally extends to nonlinear settings. In these settings, the policy is still recovered over an estimated safe set, so controlling both sources of error remains essential. With appropriate smoothness assumptions, our covering number analysis can be adapted. \n\n**Q8** The method relies on strong assumptions, such as linear MDPs and a prior safe policy.\n\n**A8** Linear MDPs are widely studied and effective in practice. Zhang et al. (2022) demonstrate state-of-the-art performance on MuJoCo and DeepMind Control benchmarks, and Jin et al. (2020) show that linear MDP solutions offer regret guarantees even when the true MDP is nonlinear. Also, a safe sub-optimal policy can often be identified offline using domain knowledge (Amani et al., 2019; Khezeli & Bitar, 2020; Shi et al., 2023).\n\n\n\n\n**Q9** NCS-LSVI may be computationally expensive. How is the estimated safe set computed?\n\n**A9**  As we explained in Appendix A, to improve computational efficiency, our implementation updates the $Q$-function estimates every $2^n$ episodes rather than at each episode.  \nRegarding the complexity of maintaining the estimated safe set and computing UCB-based values, in some cases we can skip the explicit computation of lines 11 and 12 in Algorithm 1 and directly solve the constrained optimization in line 13. Since the $Q$-function is linear in $\\phi$, the maximum lies on the boundary of $\\phi(s, \\mathcal{A}_h^k)$. When the safe set has a favorable structure (e.g., unions of convex sets), this is tractable. In complex or nonlinear cases, we use discretization, heuristics, or nonconvex solvers. We will add this to Appendix A.\n\n\n**Q10** The related works, omits Berkenkamp et al. (2017).\n\n**A10** We will move the related work to the main text and include Berkenkamp et al. (2017) in the final submission.\n\n\n\n\n\n\n\n**References**\n\nZhang et al. (2022), Making Linear MDPs Practical via Contrastive Representation Learning, International Conference on Machine Learning (ICML), pp. 26447–26466. PMLR.", "claims_and_evidence": "Provable Regret Bound: The authors claim a specific $\\tilde{O}(d^3 H^4 K)$ regret bound (with additional dependence on the safety threshold $\\tau$) for their algorithms​. This claim is backed by rigorous proofs outlined in the main text and detailed in the appendices. They present formal theorems for both the star-convex case (Theorem 5.1) and the non-convex case (Theorem 5.4), each establishing the stated regret upper bound. The structure of the proof is clearly sketched: by developing high-probability confidence bounds and using the OCD technique, they derive uniform concentration results that lead to the regret guarantee.\n\nZero Constraint Violations: A standout claim is that the algorithm incurs no safety violations with high probability during learning​. This is a strong claim (ensuring safety at all times, not just asymptotically or on average) and is supported by clear reasoning. The authors ensure this by design: the agent always acts within an estimated safe set that is initialized with a known safe action and expanded cautiously. They provide a theoretical guarantee (with high probability) that the estimated safe set is a subset of the true safe set at every step, which directly implies no constraint violation occurs.\n\nEffectiveness of OCD (Objective–Constraint Decomposition): The authors claim that OCD is a novel technique that properly bounds the covering number in the star-convex scenario and “resolves an error in a previous work”. This refers to correcting the analysis of Amani et al. (2021). They give a detailed explanation of the previous error: in prior work, the value function’s covering number was treated like in standard RL, but in safe RL the feasible action set depends on past data, invalidating a direct application of covering arguments​.", "methods_and_evaluation_criteria": "Proposed Methods: The paper proposes two main methods: the analytical OCD technique and the algorithmic framework NCS-LSVI. Both are well-motivated and appropriate for the problems they target. The OCD technique is essentially a novel analytical lens that decomposes the problem of bounding the value function class into objective and constraint parts​. This method is highly appropriate for the star-convex safe RL problem – it directly addresses the core difficulty of a changing feasible action set. The NCS-LSVI algorithm is also well-designed for the given problem. Safe exploration is notoriously hard when the safe region is not a single nice set. The two-phase approach – first conservative exploration using a safe policy, then optimistic exploitation/exploration within the enlarged safe set – is a sensible strategy.\n\nBenchmark Evaluation (Datasets/Environments): The paper’s primary experimental evaluation is on a custom autonomous driving simulation (vehicle merging scenario). In this scenario, the agent must learn to merge lanes while obeying a lane-keeping constraint; a separate module (called “Collav”) filters out obviously unsafe (collision-causing) actions, making the remaining safe set for lane-keeping non-convex (because the safe actions at each moment can be split by the removed unsafe ones)​. This setup is a reasonable and relevant benchmark for the problem. It’s not a standard benchmark from prior literature, but safe RL scenarios often require custom environments to test specific constraints. \n\nWhile the chosen scenario is appropriate, one could assess whether the range of experiments is sufficient. The paper appears to present only this one primary scenario in the main text (though they mention additional details and experiments in Appendix A​). The merging scenario provides one data point of success. It would have been beneficial to see the algorithm tested on a variety of environments or constraints – for example, a different robotics task or a synthetic grid-world with a complicated safe region – to further validate generality.", "theoretical_claims": "Core Analytical Approach: The authors adapt the optimism in the face of uncertainty approach (common in RL theory) to the constrained setting. They maintain confidence intervals for the estimated model or value function and define an optimistic value function that the agent uses to choose actions. This standard approach is complicated here by the safety constraint, which limits the action set. The authors identify that the usual uniform convergence arguments (which rely on fixed function classes) need refinement because the feasible action set is history-dependent​. Their analysis via the OCD technique splits the problem: one part deals with the usual uncertainty in the $Q$-function approximation, and another part deals with how errors in constraint estimation can affect the value function. This decomposition is conceptually sound – it acknowledges that even if two $Q$-functions are similar, their induced policies could differ if their feasible actions differ, and it bounds that difference by leveraging star-convexity​.\n\nSoundness of Theoretical Results: The regret bounds derived are high-level plausible given the problem difficulty. For star-convex safe sets, the authors essentially reclaim a sublinear regret guarantee similar to unconstrained RL (with some extra factors for safety).\n\nAssumptions and Their Restrictiveness: The theoretical results do rely on several assumptions, which are explicitly stated. It’s important to assess if any of these are too restrictive or unrealistic:\n\nLinear MDP assumption: The paper assumes the MDP’s dynamics and rewards can be embedded in a linear feature space of dimension $d$. This means essentially that $Q^*$ functions lie in a known $d$-dimensional linear span (or the transition kernel is linear in features).\n\nKnown initial safe action/policy: The authors assume that at each state (for star-convex case, as in Amani et al. 2021) or at least at the start of learning (for non-convex case via the Local Point Assumption), the agent has some action it knows is safe​. In the non-convex scenario, the Local Point Assumption (detailed in Section 3.2) likely means that from any state reachable by the initial safe policy, there exists a safe action “not too far” in feature space from the initial safe action – ensuring a locally connected safe region. This is a critical assumption for safety: it essentially provides a foothold to begin exploring without any risk. If no initial safe action is known, then ensuring zero violations from scratch is generally impossible (unless the agent is extremely conservative or gets external guidance).\n\nSafety threshold $\\tau$ and cost function: The problem formulation involves a cost function $c(s,a)$ and a threshold $\\tau$ such that actions are safe if $c(s,a)\\le \\tau$ (presumably)​. They likely assume $c(s,a)$ is known or at least can be observed (the agent can tell if it violated the constraint or measure the cost feedback). Possibly, $c(s,a)$ might also be linear in the features or share the linear structure (the paper doesn’t explicitly say, but many constrained RL works assume a linear structure for cost if they assume it for reward).\n\nIn terms of how these assumptions affect applicability: the most limiting one is perhaps the need for an initial safe action/policy and local safe connectivity.", "experimental_designs_or_analyses": "Soundness of Design: The experiment is designed to mirror the paper’s problem setting: an autonomous driving merging scenario is chosen to exemplify an MDP with an instantaneous hard constraint (stay in lane) and a non-convex action feasibility due to an external collision-avoidance system.\n\nClarity of Goals and Metrics: The goal in the experiment is for the agent to learn an optimal policy (presumably merging efficiently without leaving its lane) and the metrics used are regret and safety violations which are suitable in this context.\n\nResults and Analysis: The results (as described) show that with a sufficiently long pure exploration phase ($K'=2000$ episodes of safe random exploration), the algorithm achieves sublinear regret growth, indicating it successfully learns the optimal policy.\n\nThis analysis is correct but minimal – it states the key observation (successful learning with sublinear regret) and doesn’t delve into much more detail. For instance, they didn’t explicitly say what the optimal policy’s performance was or how quickly the algorithm approached it in absolute terms.\n\nMissing baselines: No baseline algorithm is compared. It would be informative to compare NCS-LSVI with, say, the initial safe policy (which would have zero violation but likely higher regret, essentially a flat line of regret increasing linearly if it never learns). Or compare with a naive RL algorithm that ignores safety (which would likely achieve lower regret initially but incur violations). Such comparisons could illustrate the trade-off between safety and performance. The absence of baselines means we only see that the algorithm works, but not how much better it is than “do nothing” or how much worse it might be than an unsafe method. Including at least the “Initial Safe Policy” as a baseline regret (which would accumulate regret if that policy is suboptimal) would contextualize the results. \n\nLack of multiple scenarios: It would be nice to see another environment – perhaps a different type of constraint or a different shape of safe region – to confirm the algorithm’s versatility.", "relation_to_broader_scientific_literature": "The paper positions its contributions in the context of existing literature on safe reinforcement learning and constrained MDPs, particularly those with theoretical guarantees.\n\nSafe RL with Instantaneous Constraints: Prior to this work, Amani et al. (2021) tackled a very similar problem – safe RL in linear MDPs with per-step (instantaneous) constraints under the assumption of a star-convex safe action set​. Amani et al. introduced the idea of maintaining an estimated safe set and guaranteed safety by always acting within that set. However, as noted in the paper, their theoretical analysis claiming sublinear regret was flawed. The current work directly builds on and corrects Amani et al.’s approach. The OCD technique in this paper fixes the analytical gap, enabling a correct proof of sublinear regret in the star-convex case.", "essential_references_not_discussed": "There are possibly a few key missing references. Berkenkamp et al. (2017) – Safe Model-Based Reinforcement Learning with Stability Guarantees. This work deals with safe exploration in continuous state spaces using control-theoretic (Lyapunov) methods. The idea of slowly exploring to expand the region of safe actions is explored in this paper. It would be nice if the author's include a discssuion re this method.", "other_strengths_and_weaknesses": "Strengths:\nThe paper tackles a crucial problem in reinforcement learning – ensuring safety at every step of learning.\nThe work makes original contributions in theory. The introduction of the Objective–Constraint Decomposition (OCD) is a novel analytical technique that advances understanding of how to handle dynamic feasible sets in RL​.\nA major strength is that the paper provides strong theoretical guarantees – provably sublinear regret (meaning the agent approaches optimal performance efficiently) while incurring zero safety violations (with high probability)​.\nThe paper demonstrates a deep understanding of prior work by identifying and correcting a mistake in earlier research (Amani et al. 2021).\n\nWeaknesses:\n\nRestrictive Assumptions: One of the paper’s weaknesses is that the results rely on strong assumptions that may limit direct real-world applicability. The linear MDP assumption (linear function approximation with known feature map) is a simplification that might not hold in complex environments where one would truly need safe RL (e.g., driving with raw images, robotics with complex dynamics). Similarly, the requirement of a known initial safe action/policy and the Local Point Assumption mean the method requires prior knowledge to get started and that the safe region is nicely connected. If the environment’s safe space is disconnected or if no baseline policy is known, the current approach wouldn’t apply. These assumptions, while necessary for theoretical guarantees, weaken the generality of the results.\n\nThe derived regret bound, $\\tilde{O}(d^3 H^4 K(1+1/\\tau)\\sqrt{\\ln(1/\\tau)})$, has quite large polynomial factors ($d^3 H^4$) and a linear dependence on $K$ (for the leading term)​. This suggests that the worst-case sample complexity could be high. In simpler terms, the algorithm might require a large number of episodes to reach near-optimal performance, especially if the feature dimension or horizon is long.\n\nLimited Empirical Evaluation: The experimental evaluation, although positive, is quite limited. Only one primary scenario (autonomous merging) is presented in the main paper. There is no comparison to any baseline methods or ablation of algorithm components. This makes it hard to gauge how robust or effective the approach is relative to alternatives or in different conditions.\n\nScope of Safety Consideration: The paper deals with a single constraint (like one cost with threshold $\\tau$). In many real applications, there could be multiple constraints (e.g., joint torque limits, collision avoidance, battery usage all at once). The current framework is not explicitly extended to multiple constraints.\n\nAlgorithm Complexity and Practicality: The algorithm NCS-LSVI is conceptually sound, but it may be complex to implement in practice. It likely requires maintaining large confidence sets, computing optimistic value functions via some form of extended value iteration at each episode, and carefully managing two phases. For high-dimensional problems or ones requiring function approximation beyond linear, this could be challenging.\n\nAnother minor weakness in presentation is that the related work discussion is largely deferred to the appendix. This can make it a bit difficult for a reader of the main paper to immediately see how this fits with prior efforts.", "other_comments_or_suggestions": "Clarity – Definition of the Local Point Assumption: The paper introduces a “Local Point Assumption” for the non-convex case (mentioned around Section 3). While the general idea can be inferred (it ensures some local connectivity of the safe set around the initial policy), it would benefit the reader to have a very clear definition in the main text\n\nIn the description of OCD’s results, the text says “(See Rmark 6.1)”\n\n“scaler $\\alpha_3$” in Appendix (it should be “scalar” I think)", "questions_for_authors": "1. The regret bound derived is $\\tilde O(d^3 H^4 K + \\text{const})$. Do you believe this dependence on $K$ (essentially linear) and on $d, H$ is order-optimal for safe RL, or could it be improved? In particular, is it possible to achieve a $\\tilde O(\\sqrt{K})$ regret (as in unconstrained linear RL) while still guaranteeing zero violations, or is the linear-in-$K$ growth a fundamental cost of imposing instantaneous safety?\n\n2. The bound has factors $(1+1/\\tau)\\sqrt{\\ln(1/\\tau)}$ indicating slower learning for smaller $\\tau$. How critical is knowing the exact threshold value $\\tau$ for the algorithm?\n\n3. How would you extend your approach to multiple simultaneous safety constraints (e.g., constraints $c_1(s,a)\\le \\tau_1$ and $c_2(s,a)\\le \\tau_2$ that must both hold)?\n\n4. The Local Point Assumption essentially assumes a connected safe region around the initial safe policy. Suppose in an environment the safe state-action space actually consists of two disjoint regions, A and B. The initial safe policy lives in region A, but the globally optimal safe policy is in region B (which is not reachable following safe actions from A). In that case, your algorithm would never discover region B (since it can’t safely get there). Is my understanding correct that the method is limited to the connectivity of the initial safe region? And if so, do you have thoughts on strategies to deal with such situations?\n\n5. In NCS-LSVI, the length of the pure exploration phase $K'$ is a crucial parameter. How should one choose $K'$ in practice? The experiments tried a few fixed values (like 2000) – was this based on a theoretical formula (e.g., a function of $\\epsilon,\\iota,d,H$) or more from empirical intuition? If $K'$ is chosen too small, what failure mode do you observe – is it that the safe set hasn’t stabilized and thus the algorithm remains overly cautious or incurs regret due to a small feasible action space? Conversely, if $K'$ is very large, aside from more exploration cost, does it ever hurt the stability (maybe by over-exploring)?\n\n6. You mention interest in exploring “Deep Safe RL” with nonlinear function approximation. Do you foresee the OCD technique extending to certain classes of nonlinear function approximators (for example, kernel methods or neural networks with particular architectures)?\n\n7. In your algorithm, you maintain an estimated safe set of actions at each state. How is this represented and updated in implementation? For example, in the driving scenario, is the safe set represented implicitly via upper confidence bounds on the constraint function $c(s,a)$? Do you discretize actions or use some parametric form to check which actions are safe?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kfYFM6LwoT", "reviewer": "Reviewer_2AKc", "summary": "This paper studies the theoretical problem of online reinforcement learning with instantaneous hard constraint in the context of *non-star-convex* decision space, which better characterizes some critic domains requiring safety than the existing star-convex counterpart. The authors propose the Non-Convex Safe Least Square Value Iteration (NCS-LSVI) algorithm which achieves sub-linear online regret for two setups: (i) star-convex decision space, where the results refines the mistake of a previous work; (ii) non-star-convex decision space with the local point assumption. The theoretical results are further demonstrated by some numerical experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing the constructive review. Please see our responses to your questions below.\n\n**Q1**  How should we interpret the regret bound as the constraint threshold $\\tau$ decreases, especially as $\\tau \\to 0$, where always choosing the known safe action yields linear regret?\n\n\n**A1**  We implicitly consider the upper bound $\\tilde{\\mathcal{O}}(\\min(KH, (1 + \\frac{1}{\\tau}) \\sqrt{\\log(\\frac{1}{\\tau}) d^3 H^4 K} + \\frac{1}{\\epsilon^2 \\iota^2}))$, ensuring linear regret in the worst case (we will clarify this in the final version). Intuitively, smaller $\\tau$ corresponds to tighter budgets, limiting safe exploration opportunities. Theorem 20 in Pacchiano et al. (2024) formalizes this by proving a lower bound of $\\Omega(1/\\tau^2)$, showing the $\\tau$-dependence is information-theoretically necessary. As $\\tau \\to 0$, the regret becomes linear, and the policy remains sub-optimal, as the only policy we may be able to play without violating the constraint is the prior safe policy.\n\n\n**Q2** Why model cost values with sub-Gaussian noise? \n\n**A2** Measurements are often inaccurate due to sensor errors, environmental uncertainties, or modeling errors. For example, sensor readings in robotics or medical applications are noisy. Assuming observed cost values include sub-Gaussian noise effectively captures these uncertainties. The sub-Gaussian assumption is particularly useful as it models noise with light tails, which is common in practice (e.g., Abbasi-Yadkori et al., 2011).\n\nRegarding the non-star-convex challenge, while randomness in cost and reward observations can add complexity, the primary source of hardness lies in the **environment dynamics** (state transition kernel in the MDP). If the dynamics were independent of the chosen actions, the problem would reduce to a contextual bandit setting, and we could remove the pure-exploration phase (even for non-star-convex decision sets), merely adjusting the exploration-exploitation bonus for near-optimal performance. Thus, the noise in costs and rewards is **not** the main contributor to the problem’s hardness; however, we have included the randomness to make our analysis complete.\n\n**Q3** The non-star-convex results lack explanation and are only stated theoretically.\n\n**A3** Due to rebuttal character limits, we provide a brief version below and will elaborate fully in the final paper: \nThe regret dependence on $K$ in Theorem 5.4 is $O(\\sqrt{K})$. The key difference between Theorems 5.4 and 5.1 lies in the need for a pure exploration phase: while Theorem 5.1 requires none (i.e., $K' = 0$), Theorem 5.4 uses $K' = O(\\log(K)/(\\epsilon^2 \\iota^2))$, which stems from the Local Point Assumption and reflects the added complexity of non-star-convex settings compared to star-convex ones. This term also appears explicitly in the regret bound, capturing the cost of ensuring safe exploration in such environments.\n\n\n**Q4** The lower bound is unknown and not discussed.\n\n**A4** Since linear bandits are a special case of our setting, Theorem 20 of Pacchiano et al. (2024) and Theorem 3 of Shi et al. (2023) imply a lower bound of $\\tilde{\\Omega}(\\max(\\frac{1}{\\tau^2}, d H \\sqrt{K}))$ in the star-convex case, indicating that the $\\tau$-dependence in constrained RL is unavoidable. Our regret bound is $O((1 + 1/\\tau)\\sqrt{\\log(1/\\tau)}\\sqrt{K})$, which matches the unconstrained regret in Jin et al. (2020) up to additional terms accounting for instantaneous constraints and non-star-convexity. Our goal was to design an algorithm with sublinear regret that remains safe in both star-convex and non-star-convex environments. Deriving a tight lower bound is beyond the scope of this paper.\n\n\n**Q5** The Local Point Assumption is hard to parse and would benefit from a more intuitive explanation.\n\n**A5** Thank you for the suggestion. In the final version, we will add the following intuition to clarify Assumption 3.2: This assumption requires that we can perturb the initial safe action $a^0_s$ slightly, i.e., we can safely sample from a small neighborhood around it, with radius determined by $\\epsilon$. For example, in the autonomous driving setup in Section 3, if speed $v_0$ is safe, then speeds in $[v_0 - \\epsilon, v_0 + \\epsilon]$ should also be safe. The second part of the assumption requires local connectivity property in the small neighborhood around the constraint boundary,  e.g., if $ v^*$ is optimal and exactly at the constraint boundary, then speeds in $[v^* - \\iota, v^*]$ must be safe.", "claims_and_evidence": "Yes, most of the claims made in the submission supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed methods make sense for the problem this paper study.", "theoretical_claims": "Yes, the reviewer is able to briefly check the proofs of the theoretical results.", "experimental_designs_or_analyses": "Yes, the reviewer checks the validity of the numerical experiments.", "relation_to_broader_scientific_literature": "The paper contributes to the line of works on online RL theory under safety constraints. Especially, the paper identifies and refines a theoretical analysis error in a previous work [1] and considers another setup (non-star-convex decision space with local point assumption).\n\n**References:**\n\n[1] Amani, S., Thrampoulidis, C., and Yang, L. Safe reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 243–253. PMLR, 2021", "essential_references_not_discussed": "To the best knowledge of the reviewer, there is no lacking essential references.", "other_strengths_and_weaknesses": "**Strengths:**\n1. The paper considers a more realistic decision space model which is non-star-convex.\n2. The paper identifies and refines an error in existing results for online RL under safety constraints\n3. The theoretical results for online regret bounds in the non-star-convex case is also solid and sound.\n\n**Weaknesses:**\n1. Despite interesting, the local point assumption is somehow hard to parse. More intuitive explanations of the assumption could be included.\n2. The lower bound of the problem studied is unknown and not discussed.\n3. The new results for the non-star-convex setups are not well discussed. There is only the theoretical guarantee but without any explanations and discussions.", "other_comments_or_suggestions": "Please see the question part below.", "questions_for_authors": "1. How to understand that the online regret of the problem gets worse when the constraint threshold $\\tau$ is decreasing? Especially, the results mean that when $\\tau=0$, the algorithm will have no guarantee. If $\\tau=0$, we know that the safe action $a_0$ is valid and a baseline policy is to always choose the safe action which in the worst case results in a linear regret. So how to understand the behavior of the upper bound when $\\tau$ is approaching zero?\n2. What is the reason to consider observed cost values that are also random (there is a sub-Gaussian noise part in the cost value)? What are typical real-world scenarios for such considerations? Technically, does this also contribute to the hardness of the handling of the non-star-convex decision space?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZKK7jUkLWu", "reviewer": "Reviewer_yoBb", "summary": "This paper investigates safe reinforcement learning (RL) with instantaneous safety constraints and linear function approximation, where the objective is to ensure zero violations at each step. The authors first identify a technical error in previous work (Amani et al., 2021) and introduce a novel approach, OCD, to address this issue. They then propose a new assumption on the linear structure, termed the \"Local Point Assumption,\" which is more realistic than the star-convexity assumption in Amani et al. (2021). By incorporating an additional pure exploration phase, they prove that the algorithm achieves sublinear regret while maintaining zero violations. Experimental results further validate their theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your comments and have addressed your points individually below.\n\n**Q1**  Can the covering number be bounded by the union of the covering number of Q_h^k at each step? It will only induce an acceptable log⁡K factor in the final term.\n\n**A1**  We thank the reviewer for this insightful question. However, this suggested approach does not work in our case due to the unique structure of constrained RL with data-dependent safe sets. We elaborate below.\nWhile the $Q_h^k$ functions in our setup are linear and their covering number is easy to bound, this is not sufficient for constrained RL. In the unconstrained case, $V_h^k$ is computed as a maximum over a fixed decision set $\\mathcal{A}$, where the max operator acts as a contraction. Hence, a covering over $Q$-functions directly implies one over $V$-functions. In contrast, in constrained RL, the maximization is performed over the data-dependent estimated safe set $\\mathcal{A}_h^k(s)$. Since this set varies with the data, even identical $Q$-functions can induce very different $V$-functions if the estimated safe sets differ significantly. As a result, bounding only the $Q$-function class is not enough to ensure uniform convergence of the value functions. We address this issue in Section 5 by using OCD to decompose the effects of the estimated safe set and the $Q$-function on the covering number.\n\n**Q2**  In the driving example, the action set seems continuous, so star-convexity may still hold. Could the authors clarify why it fails here, and why the local point assumption applies instead?\n\n**A2**  We agree that the original action space in autonomous driving may appear star-convex. However, in our setup, a pre-trained Collision Avoidance (Collav) module masks out unsafe actions before the RL agent makes decisions. This results in a non-star-convex feasible set. The reason is that collision avoidance itself is inherently non-convex—since it requires the autonomous vehicle to avoid entering a region (typically a ball) around another vehicle. This introduces gaps in the feasible set. So, while the raw action space might be star-convex, the effective decision set seen by the RL agent is not. \n\nTo illustrate this concretely, suppose $a_s^0$ is the initial safe action and $ a_s^*$ is the optimal safe action (e.g., moving quickly before the other car arrives). While their convex combination $\\alpha \\phi(s, a_s^0) + (1 - \\alpha)\\phi(s, a_s^*)$ might still satisfy the lane-keeping constraint, for some intermediate $ \\alpha \\in [\\epsilon, 1-\\iota]$, the resulting action may fall into the collision region, i.e., the car neither waits long enough nor moves fast enough to avoid the other vehicle at the intersection. This violates the collision avoidance constraint and breaks star-convexity.\n\nThat said, the Local Point Assumption still holds. Around the initial safe action (e.g., stopping), small perturbations (e.g., low speeds in [0, ε]) remain safe, as they allow the other vehicle to pass. Further, high speeds beyond a threshold $v'$ (up to $v^*$) can also be safe. This assumption only requires local structure and is well-suited for disjoint or irregular safe sets.\n\nNote that, even when $\\mathcal{A}$ is star-convex in different applications, the transformed space $\\mathcal{F}_s = \\phi(s, \\mathcal{A})$ may not be star-convex, especially when $\\phi$ is nonlinear. \n\n**Q3**   The covering number appears to add only a $\\log(K)$ factor, making the correction to the prior proof seem minor.\n\n**A3**  The regret analysis in Amani et al. (2021) is incorrect because it applies unconstrained RL covering-number arguments, ignoring that data-dependent safe sets may significantly alter feasible actions across episodes. A naive union bounding approach would only add a log(K) factor, but it fails once the safe set shifts over time. Our OCD technique explicitly separates Q-function estimation (objective) from safe-set complexity (constraint), yielding an additional term $\\mathcal{O}(\\sqrt{\\log(\\frac{1}{\\tau})})$ (Lemmas C.2 and C.6). This shows how tighter constraints (smaller $\\tau$) inflate the covering number, making our correction nontrivial rather than a minor log(K) overhead.\n\n\n**Q4**  Regret seems linear; more episodes may improve the experiment.\n\n\n**A4**  Our regret is sublinear; please see Figure [a] at the anonymous GitHub link: https://anonymous.4open.science/r/ICML-Safe-RL-figures-CE2D.", "claims_and_evidence": "The theoretical claims made in the submission are supported by clear proof.", "methods_and_evaluation_criteria": "The evaluation criteria are the cumulative regret and the violation, which is common and reasonable in the safe RL.", "theoretical_claims": "I check most of the proof in the paper. It is correct to me. However, the covering number seems to be bounded by the union of the covering number of $V_h^k$ at each step. Hence, it will only induce an extra $\\log(K)$ factor in the final regret, making the contribution of correcting the previous theoretical proof somewhat unclear.", "experimental_designs_or_analyses": "The experiment is conducted on an autonomous vehicle path-planning task. However, the results in Figures 3 and 6 do not exhibit a clear sublinear regret pattern. (Even for $K'=2000$, after 2000 episodes, the regret seems still linear and get 6000 regret for 10000 episodes). The authors should run additional episodes to better demonstrate the sublinear regret behavior.", "relation_to_broader_scientific_literature": "The key contribution is (a) finding a technical error in an essential paper for safe linear MDP with instantaneous constraint and overcoming it by bounding the covering number using additional tricks, and (b) changing the star-convexity assumption to a more realistic local-point assumption.", "essential_references_not_discussed": "I don't find any essential additional references that need to be discussed.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written. The presentation about the previous technical error is clear and easy to understand. \n\n2. The theoretical contribution is essential. [Amani et al. 2021] is an important paper on safe RL with linear function approximation, and identifying and correcting its error represents a big contribution.\n\nWeaknesses:\n\n1. The intuition why the local-point assumption is better than the star-convexity assumption seems unclear. The paper does not contain a convincing example to illustrate that the local-point assumption is reasonable. The example provided just states the unreasonableness about the star-convexity. \n\n2. The experiment result is unsatisfying: First, the author does not clarify why the local-point assumption holds in their experiment setup.  Also, the regret looks linear in the number of episodes. The author should perform more episodes to enhance the quality of the experiment.", "other_comments_or_suggestions": "See the questions part.", "questions_for_authors": "1. In the given autonomous driving example, I believe the star-convexity assumption still holds. The feasible region remains continuous, while actions corresponding to the inaccessible region are unsafe. In fact, the star-convexity assumption only imposes a continuity structure on the action set, not necessarily on the safe action set. Hence, I think it is a reasonable assumption in real-world scenarios. Could the authors clarify the example further to illustrate why the star-convexity assumption fails in this case? Also, in this case why the local-point assumption hold?\n\n2. Can the covering number be bounded by the union of the covering number of $Q_h^k$ at each step? It will only induce an acceptable $\\log K$ factor in the final term. I am happy to increase the score if the author explains why this approach fails.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AClaUff54N", "reviewer": "Reviewer_sJHh", "summary": "This paper establishes a regret bound applicable to both star-convex and non-star-convex cases. Moreover, the violation of safety constraints is zero with high probability throughout the learning process. A key technical challenge in these settings is bounding the covering number of the value-function class, which is essential for achieving value-aware uniform concentration in model-free function approximation. For the star-convex setting, this paper develops a novel technique called Objective–Constraint Decomposition (OCD) to properly bound the covering number. This result also resolves an error in a previous work on constrained RL. In non-star-convex scenarios, where the covering number can become infinitely large, this paper proposes a two-phase algorithm, Non-Convex Safe Least Squares Value Iteration (NCS-LSVI), which first reduces uncertainty about the safe set by playing a known safe policy. After that, it carefully balances exploration and exploitation to achieve the regret bound. Finally, numerical simulations on an autonomous driving scenario demonstrate the effectiveness of NCS-LSVI.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful feedback. We respond to each of your comments below.\n\n**Q1** My main concern is on the unique challenges and technical novelty compared to prior works on safe RL, especially [Amani et al. 2021].\n\n**A1**   Below we highlight our unique contributions and technical challenges in two parts.\n\n**1. Identifying and Fixing a Key Proof Gap in Amani et al. [2021]**  \n\nWe first note that the proof in Amani et al. (2021) is incorrect because they directly apply covering-number arguments from unconstrained RL. In the unconstrained case, $V_h^k$ is computed as a maximum over a fixed decision set $\\mathcal{A}$, where the max operator acts as a contraction. Hence, a covering over $Q$-functions directly implies one over $V$-functions. In contrast, in constrained RL, the maximization is performed over the data-dependent estimated safe set $\\mathcal{A}_h^k(s)$. Since this set varies with the data, even identical $Q$-functions can induce very different $V$-functions if the estimated safe sets differ significantly. As a result, bounding only the $Q$-function class is not enough to ensure uniform convergence of the value functions.\n\n To address this issue, we develop a novel Objective–Constraint Decomposition (OCD) technique, explicitly separating the complexities of estimating the $Q$-functions (objective) and estimating the safe set  (please see Section 6).  Our key insight leverages the mild geometric structure provided by star-convexity: small variations in the safety parameters do not drastically alter the feasible set, ensuring two close $Q$-functions yield close value functions despite the evolving safe set. This resolves the proof gap in Amani et al. [2021] and our analysis yields an additional factor of $O(\\sqrt{\\log(\\frac{1}{\\tau})})$. This shows how tighter constraints (smaller $\\tau$) inflate the covering number. Thus, our contribution significantly advances the theoretical understanding of constrained RL.\n\n**2. Algorithmic and Theoretical Contributions for Non-Star-Convex settings.**\n\nOur next main contribution involves both algorithmic and theoretical advancements. On the algorithmic side, we developed the novel NCS-LSVI algorithm, which differs from the SLUCB-QVI algorithm in Amani et al. [2021], and is designed for non-star-convex safe RL environments, common in applications like autonomous driving and robotics, where obstacles or constraints create disjoint or irregular safe regions. On the theoretical side, we provide a regret analysis of our method. We elaborate below.\n\n**The Challenge of Non-Star-Convex Problems.**\n\nLemma 5.3 shows that, unlike the star-convex case, small variations in the safety parameter can drastically change  the decision set, leading to an arbitrarily large covering number in non-star-convex scenarios. Thus, in these cases, the algorithm proposed for star-convex settings cannot attain a proper covering bound using our OCD technique, indicating the inadequacy  of previous star-convex-based methods and highlighting the need for novel approaches.\n\n\n **A Two-Phase Algorithm for Non-Star-Convex Environments**\n\nMotivated by these limitations, we propose NCS-LSVI, a two-phase algorithm designed for non-star-convex feature spaces under our Local Point Assumption. Drawing on the insight that large shifts in the safe set complicate the analysis, NCS-LSVI begins  with a pure-safe exploration phase that samples from a small neighborhood around the initial safe policy.By the end of this phase, the estimated safe set stabilizes in the sense that small changes in the safety parameter lead to bounded changes in the value function with high probability, enabling more tractable covering-number bounds. In Theorem 5.4, we show that by characterizing the number of episodes in the pure exploration phase,  NCS-LSVI achieves sublinear regret, specifically $O(\\sqrt{K})$, along with an additional $O(\\frac{\\log(K)}{\\epsilon^2 \\iota^2})$ term that stems from the pure exploration phase. This extra term reflects the fundamental complexity of non-star-convexity, making the result nontrivial. \n\n\n**Q2** The font in Figure 3 is too small. Can more baseline or adaptation algorithms be added for comparison?\n\n**A2**  We will revise the font size in Figure 3 for the final submission. To address the baseline comparison, we provide additional simulation plots at this anonymous link https://anonymous.4open.science/r/ICML-Safe-RL-figures-CE2D. Figure [a] shows the regret of NCS-LSVI over more episodes, demonstrating sublinear growth for $K' = 2000$.  Figure [b] shows the regret of a sub-optimal but safe baseline constrained to an \\(\\epsilon\\)-neighborhood of the initial policy. Figure [c] shows the regret of LSVI-UCB (Jin et al., 2020), which achieves lower regret but violates constraints, as shown in Figure [d], where cumulative violations grow linearly. The other two methods have zero violations, so no violation plots are included. We will add these results in the final version.", "claims_and_evidence": "The claims made in this paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense.", "theoretical_claims": "The theoretical results look reasonable, but I didn’t go through every proof.", "experimental_designs_or_analyses": "The experiments look reasonable.", "relation_to_broader_scientific_literature": "This paper is relevant to the literature.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths:\n\n1. This paper is well executed. It designs an algorithm and establishes regret bounds for safe RL with non-convex feature spaces.\n2. Empirical evaluations are provided to demonstrate the effectiveness of the proposed algorithm.\n3. This paper is well written overall.\n\nWeaknesses:\n\n1. My main concern is on the unique challenges and technical novelty compared to prior works on safe RL for linear MDPs, especially [Amani et al. 2021]. The proposed algorithm and theoretical analysis in this paper looks similar to [Amani et al. 2021]. More discussions on the challenges brought by non-convex feature spaces are needed.\n2. The font in Figure 3 is too small. Is there any more baseline algorithm or adaptation algorithm which can be included for comparison in empirical evaluations?\n\nReference:\nAmani, S., Thrampoulidis, C., and Yang, L. Safe rein forcement learning with linear function approximation. In International Conference on Machine Learning, pp. 243–253. PMLR, 2021.", "other_comments_or_suggestions": "Please see the weaknesses above.", "questions_for_authors": "Please see the weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces


Paper-Summary: The paper presents a new algorithm and theoretical analysis for safe reinforcement learning (RL) in settings with instantaneous hard safety constraints, particularly when the feasible action space is non-convex. The authors propose a novel regret-minimizing algorithm called Non-Convex Safe Least Squares Value Iteration (NCS-LSVI), designed for linear MDPs where the geometry of the safe decision space may be star-convex or non-star-convex. For the star-convex case, they introduce a new Objective–Constraint Decomposition (OCD) technique to bound the covering number of value functions, correcting a key mistake in prior work.  Their regret analysis explicitly characterizes the dependence on the safety threshold and problem dimensions. Additionally, simulations validate the effectiveness of their algorithm and theoretical claims.


Review and feedback: We received 4 expert reviews, with scores, 3, 3, 3, 4, and the average score is 3.25.  

The reviewers are generally positive about this paper. Reviewers noted that this paper fills a key gap in the literature by providing a correct and general regret analysis for safe RL under linear MDPs. The OCD technique proposed is novel and it elegantly resolves the analytical challenge of history-dependent feasible sets, and helps to characterize the regret bound. Reviewers have also appreciated the innovation and presentation style of the NCS-LSVI algorithm that leverages a two-phase learning protocol (safe exploration followed by optimistic planning). They particularly noted that this is the first paper to guarantee zero safety violations in a non-star-convex setting with high probability. Although limited in scope, the experiments are well-aligned with the theoretical setting. 

Reviewers have also made suggestions for improvement. Most reviewers have asked for more detailed experimental evaluation and comparison with other baseline algorithms. More than one reviewer has asked for more explanation/justification about the assumptions used and intuitive proof sketches. Please address these comments/suggestions while preparing the final submission.
Decision: Accept (poster)