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

Thank you for the thoughtful feedback. We respond to each of your comments below.

Q1 My main concern is on the unique challenges and technical novelty compared to prior works on safe RL, especially [Amani et al. 2021].

A1 Below we highlight our unique contributions and technical challenges in two parts.

1. Identifying and Fixing a Key Proof Gap in Amani et al. [2021]

We 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.

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.

2. Algorithmic and Theoretical Contributions for Non-Star-Convex settings.

Our 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.

The Challenge of Non-Star-Convex Problems.

Lemma 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.

A Two-Phase Algorithm for Non-Star-Convex Environments

Motivated 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.

Q2 The font in Figure 3 is too small. Can more baseline or adaptation algorithms be added for comparison?

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.

We appreciate your comments and have addressed your points individually below.

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.

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. While 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.

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?

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.

To 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.

That 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.

Note 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.

Q3 The covering number appears to add only a $\log(K)$ factor, making the correction to the prior proof seem minor.

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.

Q4 Regret seems linear; more episodes may improve the experiment.

A4 Our regret is sublinear; please see Figure [a] at the anonymous GitHub link: https://anonymous.4open.science/r/ICML-Safe-RL-figures-CE2D.

Thank you for the thoughtful feedback. We respond to each of your comments below.

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?

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.

Q2 How important is it to know the exact value of $\tau$?

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).

Q3 How would you extend your approach to multiple constraints?

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.

Q4 Is the method limited by the connectivity of the initial safe region?

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.

Q5 Limited Empirical Evaluation

A5 Please see our response to Reviewer sJHh, Comment A2.

Q6 How should K′ be chosen in NCS-LSVI?

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.

Q7 Can the OCD technique be extended to nonlinear settings?

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.

Q8 The method relies on strong assumptions, such as linear MDPs and a prior safe policy.

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).

Q9 NCS-LSVI may be computationally expensive. How is the estimated safe set computed?

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.
Regarding 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.

Q10 The related works, omits Berkenkamp et al. (2017).

A10 We will move the related work to the main text and include Berkenkamp et al. (2017) in the final submission.

References

Zhang et al. (2022), Making Linear MDPs Practical via Contrastive Representation Learning, International Conference on Machine Learning (ICML), pp. 26447–26466. PMLR.

We thank the reviewer for providing the constructive review. Please see our responses to your questions below.

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?

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.

Q2 Why model cost values with sub-Gaussian noise?

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).

Regarding 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.

Q3 The non-star-convex results lack explanation and are only stated theoretically.

A3 Due to rebuttal character limits, we provide a brief version below and will elaborate fully in the final paper: The 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.

Q4 The lower bound is unknown and not discussed.

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.

Q5 The Local Point Assumption is hard to parse and would benefit from a more intuitive explanation.

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.