acceptodds
Under review as a conference paper at ICLR 2027

Instance-Dependent Regret for CMDPs with Step-Wise Constraints

Abstract

We study online learning in episodic tabular constrained Markov decision processes with *step-wise safety constraints*. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose *Safe Variance-Adaptive Exploration* (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order over episodes, where is the horizon of a single episode, while and are the numbers of states and actions, respectively. Here, is the maximum return variance among safe policies, is the variance accumulated before the first unsafe action is encountered, and captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in . Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable.

Primary area:
learning theory
Keywords:
safe reinforcement learning, step-wise constraints, safe subgraph

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_7azcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies online reinforcement learning in episodic tabular CMDPs with step-wise safety constraints. The authors propose Safe Variance-Adaptive Exploration (SVAE), which combines optimistic safe-subgraph identification with variance-adaptive value iteration. They introduce two variance measures and a safety-identification complexity C to characterize the difficulty of learning under unknown constraints. The main result is an instance-dependent regret bound involving these quantities, together with sublinear cumulative constraint violation. The paper also provides regret lower bounds and numerical experiments illustrating the effects of safety constraints on return variance and exploration.

Critical strengths
  1. Instance-dependent learning guarantees. The paper establishes instance-dependent regret and sublinear cumulative constraint violation bounds, while characterizing how step-wise safety constraints influence return variance and the difficulty of learning.

  2. Supporting lower bounds. The paper also establishes regret lower bounds involving return variance and safety-identification complexity, providing partial evidence for the tightness of the proposed upper bound.

Critical weaknesses
  1. Limited algorithmic and technical novelty. SVAE mainly combines existing safe-subgraph identification techniques (Xiong et al., 2023; Shi et al., 2023) with variance-adaptive planning from MVP-V (Zhou et al., 2023b). The theoretical analysis also largely relies on standard concentration and variance-based techniques. Although adaptations are needed for the present setting, the overall algorithmic and technical novelty appears limited.
  • Xiong, N., Du, Y., and Huang, L. (2023). Provably Safe Reinforcement Learning with Step-wise Violation Constraints. NeurIPS 2023.
  • Shi, M., Liang, Y., and Shroff, N. (2023). A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints. ICML 2023.
  • Zhou, R., Zhang, Z., and Du, S. S. (2023). Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments. ICML 2023.
  1. Nonmatching regret bounds. The safety identification term has linear dependence on SS and H3/2H^{3/2} dependence on HH, while the lower bound has square-root dependence on both SS and HH. This leaves a gap of HSH\sqrt{S}. Moreover, the variance-dependent lower bound only covers a restricted variance range. Thus, the optimality of the proposed regret bounds remains unclear.

  2. Potentially conservative safety identification complexity. The proposed complexity C\mathcal C does not account for cost observation variance or reward relevance. For example, its inverse-squared cost-gap dependence may be conservative when costs are deterministic. Moreover, the regret lower bound does not fully establish the necessity of the recursive rare-successor component of C\mathcal C.

  3. Limitations of the experimental evaluation. The hyperparameter tuning procedure in Appendix H.6 uses ground-truth safety information to select eligible configurations, which is unavailable in practical settings. Moreover, the tuned bonus multipliers are much smaller than the theoretical values, raising questions about whether the guarantees apply to the experimental configurations. The experiments are also limited to small tabular CMDPs, and it remains unclear whether the improvements persist for larger SS and HH.

Questions for authors
  1. Can the authors clarify whether a similar variance-dependent bound holds for strong regret, where positive and negative regrets cannot cancel across episodes?

  2. What are the main technical challenges beyond combining existing safe-subgraph identification techniques with variance-adaptive planning? Which parts of the algorithm or analysis are fundamentally new?

  3. Can the dependence on SS and HH in the safety identification term be improved? Can the necessity of the recursive rare-successor component of C\mathcal C be established for general learning algorithms?

  4. Can the safety identification complexity C\mathcal C be improved by incorporating cost observation variance or reward information? In particular, is the inverse-squared cost-gap dependence necessary when cost observations are deterministic?

4 comments

We thank the Reviewer for their time and careful reading of the paper, for recognizing the value of our instance-dependent guarantees and supporting lower bounds, and for their positive assessment of the paper’s soundness. Below, we address your questions, which cover the Weaknesses raised, and present additional experiments motivated by your suggestions. The revised parts of the manuscript are colored in blue, and changes addressing your comments are marked with “@7azc” in red. We hope that your constructive feedback and our responses will help strengthen the paper.

Q1. Variance-dependent bounds for strong regret.

Yes. Under the same assumptions, the bound in Theorem 2 also holds for strong regret:

R+(K):=∑k=1K[V1⋆(s1)−V1πk(s1)]+≤O~!(SAHmin⁡VΣ,KVar⋆+SAH3min⁡K,C+S2AH2)R_+(K):=\sum_{k=1}^K \left[V_1^\star(s_1)-V_1^{\pi^k}(s_1)\right]_+ \le \widetilde O\\!\left( \sqrt{SAH\min\\{V_\Sigma,K\mathrm{Var}^\star\\}} +S\sqrt{AH^3\min\\{K,\mathcal C\\}} +S^2AH^2 \right)

with probability at least 1−δ1-\delta.

Specifically, the proof of Proposition C.2 bounds each episode’s value gap by the nonnegative quantity E[Yk∣F1k]\mathbb E[Y_k\mid\mathcal F_1^k], which therefore also bounds its positive part. Summing these inequalities and applying the subsequent residual bounds gives the same guarantee, without relying on cancellation across episodes. We thank the Reviewer for prompting this clarification and have explicitly included the strong-regret guarantee in Section 5.1 (line 442) and its proof in Appendix C.4 (line 1334).

Q2 (W1). Algorithmic and technical contributions.

Our main contribution is to characterize how step-wise safety constraints affect learning through two distinct mechanisms: restricting feasible behavior can reduce reward uncertainty, while identifying that restriction creates an additional exploration burden. We establish an instance-dependent regret guarantee that separates these effects through safe-policy return variance and safety identification complexity.

SVAE builds on recursive safety filtering and variance-adaptive planning. The additional challenge is that the learned safety filter can retain unsafe actions, so exploratory policies can have large return variance even when every safe policy has zero return variance. The following developments allow us to obtain guarantees governed by the unknown safe region.

  • Beyond Xiong et al. (2023): quantifying recursive identification effort. SUCBVI already learns recursive safety sets and controls cumulative violation. However, an action can satisfy its immediate cost constraint and rarely reach a state with no safe continuation. It can therefore be executed many times while incurring little violation. Our witness-tree analysis converts downstream cost-observation requirements into upstream execution bounds, accounting for cost gaps and rare transitions through C\mathcal C (Lemmas C.2–C.3). This provides the identification control needed for our regret analysis.

  • Beyond Zhou et al. (2023b): adapting to safe-policy variance during unsafe exploration. MVP-V’s variance measures and guarantees concern the unconstrained MDP. We construct a safe comparison policy that agrees with exploration before the first unsafe action, and develop stopped-trajectory variance bounds that control the resulting boundary terms and subsequent exploration (Lemma C.6 and Lemmas C.8–C.10). Together with the identification counts, these arguments yield the min⁡K,C\sqrt{\min\\{K,\mathcal C\\}} dependence while retaining adaptation to variance within the safe region.

  • Distinction from Shi et al. (2023). Their method uses known successor supports and a known seed safe subgraph to ensure safety throughout exploration. Our setting provides neither. We instead learn optimistic candidate sets that may contain unsafe actions and jointly control their identification effort, reward-learning uncertainty, and cumulative violation.

The resulting guarantee is polylogarithmic in KK on fixed instances with zero safe-policy return variance, even when the full MDP is stochastic. Our structural variance results and supporting lower bounds further explain the roles of reward uncertainty and safety identification. We have made these contributions and their relationship to the existing techniques more explicit in Remark 3 (line 443).

Q3 (W2). Dependence on S,HS,H and necessity of the rare-successor component.

Our bounds establish the same min⁡K,C\sqrt{\min\\{K,\mathcal C\\}} dependence in the safety identification term, while leaving an HSH\sqrt S gap in the dimensional factors. Sharpening these factors remains open. The variance-dependent lower bound also applies within its stated variance range. We have clarified the scope in Appendix G.1 (line 2169).

The recursive rare-successor component is supported by the identification lower bound in Appendix G.2. On the specified tree-structured families, Lemma G.3 shows that any δ\delta-valid permanent elimination rule requires Ω(κh(s,a)log⁡(1/δ))\Omega(\kappa_h(s,a)\log(1/\delta)) expected executions of an unsafe action. This captures the unavoidable effort needed to reach informative downstream states and distinguish their costs from the threshold. For disjoint trees, these requirements aggregate to a lower bound involving C\mathcal C.

Thus, the recursive component is necessary for valid elimination on these families. Establishing a corresponding regret lower bound for general learning algorithms remains open. We have clarified this distinction in Appendix G.2 (line 2268).

Q4 (W3). Cost variance, reward relevance, and deterministic costs.

Cost variance can sharpen the safety identification complexity when observations have low variance. A natural refinement uses the tighter of Hoeffding and empirical-Bernstein cost confidence bounds, giving a local identification requirement of order \widetilde O\\!\left( \min\left\\{ 1/\Delta^2, \sigma_c^2/\Delta^2+1/\Delta \right\\} \right) denotes the cost observation variance and Δ>0\Delta>0 is the gap above the safety threshold. Incorporating this requirement into the recursion offers a route to a variance-sensitive refinement of C\mathcal C. Reward information may also sharpen the regret-relevant identification complexity. The main challenge is determining which actions are suboptimal, since their long-term values depend on which future actions are safe.

For deterministic costs, we agree that inverse-squared gap dependence is unnecessary. If determinism is known, each observation reveals the mean cost exactly. Without this prior knowledge, variance-aware confidence bounds can still improve the local dependence to inverse-linear in the gap. Our current analysis covers general stochastic costs, for which identifying whether the mean exceeds the threshold can require Ω(Δ−2)\Omega(\Delta^{-2}) observations in the worst case. This discussion has been added to Appendix C.8 (line 1649).

W4. Experimental evaluation.

Thank you for these helpful suggestions. We have strengthened the evaluation in three ways.

  • Tuning without ground-truth safety information. We added comparisons using a tuning procedure based only on observed rewards and costs, with the same number of hyperparameter configurations evaluated for each method. These experiments address the reliance on ground-truth safety information.

  • Evaluation with theoretical bonus coefficients. We also evaluated SVAE with both bonus multipliers set to 1 across six settings with different safe-policy return variances and cost gaps, each with K=100,000K=100{,}000. SVAE achieves lower strong regret than both SUCBVI (Xiong et al., 2023) and its Hoeffding-bonus ablation in all six settings. These experiments demonstrate the benefit of variance adaptation using the prescribed bonuses.

  • Larger and more diverse CMDPs. The expanded evaluation includes navigation tasks with up to 225 states and horizon 40, alongside controlled studies of safe-subgraph topology, transition stochasticity, and identification difficulty. For S=100S=100 and H=40H=40, SVAE reduces mean strong regret by 36.44% and cumulative violation by 45.46% relative to SUCBVI over K=10,000K=10,000 episodes. For S=225S=225, the corresponding reductions are 40.07% and 30.08%. Its mean strong regret is also substantially lower than MVP-V’s (Zhou et al., 2023b): 69,022 versus 132,160.

Together, these additions provide broader empirical support for the proposed mechanisms and SVAE’s performance. These experiments have been added to Appendices H.2–H.6 (lines 2393–2685) in the revised manuscript.

Thank you again for your constructive feedback. We welcome further questions and hope our responses strengthen your evaluation of the paper.

Reviewer_7azcOpenReview ↗

Response to the Rebuttal

Thank you for the detailed response and revision. The rebuttal clarifies the technical contributions and addresses my question regarding strong regret. However, I still have concerns about the algorithmic novelty, as the overall framework remains largely built on existing safe-subgraph identification and variance-adaptive planning techniques.

My other main concern is the relatively large gap between the upper and lower bounds. In particular, the safety-identification terms still differ by a factor of HSH\sqrt{S} in their dependence on SS and HH, and the variance-dependent lower bound only covers a restricted range. Thus, the sharp dependence on the problem parameters remains unclear.

Overall, while the revision addresses some of my questions, these two concerns remain substantial. I therefore maintain my rating.

Thank you very much for considering the revision and clarifying your remaining concerns. We are glad that the rebuttal clarifies the technical contributions and addresses your question regarding strong regret.

Regarding novelty, the central result is that regret can adapt to variance within the true, unknown safe region, even while exploration executes unsafe policies whose variance may be much larger. Establishing this requires connecting recursive identification effort to a stopped-trajectory variance analysis. The resulting guarantee is polylogarithmic in KK on fixed instances with zero safe-policy return variance, even when unsafe policies have stochastic returns. The cited safe-subgraph and variance-adaptive guarantees do not establish this property. We see this characterization and its supporting analysis as the principal contribution, with SVAE providing a computationally efficient realization.

Regarding tightness, within the stated parameter ranges, the upper and lower bounds match in their square-root dependence on KK in the variance term and on min⁡K,C\min\\{K,\mathcal{C}\\} in the safety identification term. They establish that both contributions are necessary. We agree that the remaining HSH\sqrt{S} gap leaves sharp parameter dependence, and hence full minimax optimality, open. We have clarified this scope in the revision. This is not unusual: a substantial part of the online learning literature is based on first developing algorithms whose bounds are not necessarily tight in every parameter (see [1–5]), and, to the best of our knowledge, our paper provides the first instance-dependent regret bound for CMDPs with step-wise constraints.

We appreciate your engagement and hope this clarifies the contribution’s significance and the remaining open questions for the community.

References

[1] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is Q-Learning Provably Efficient? NeurIPS, 2018.

[2] Y. Bai, T. Xie, N. Jiang, and Y.-X. Wang. Provably Efficient Q-Learning with Low Switching Cost. NeurIPS, 2019.

[3] S. Qiu, X. Wei, Z. Yang, J. Ye, and Z. Wang. Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss. NeurIPS, 2020.

[4] M. Shi, Y. Liang, and N. Shroff. A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints. ICML, 2023.

[5] A. Müller, P. Alatur, V. Cevher, G. Ramponi, and N. He. Truly No-Regret Learning in Constrained MDPs. ICML, 2024.

Reviewer_kTwsOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies episodic tabular CMDPs with unknown transitions and costs under step-wise safety constraints. The key idea is that safety constraints induce a safe subgraph that affects both reward uncertainty and the difficulty of identifying feasible actions.

The paper introduces instance-dependent quantities capturing safe-policy return variance and safety-identification complexity, and proposes Safe Variance-Adaptive Exploration (SVAE), which combines safe-subgraph learning with variance-adaptive optimistic planning. The authors derive instance-dependent regret and cumulative constraint-violation bounds, including improved guarantees for low-variance instances and polylogarithmic violation under a positive cost gap. They also provide lower bounds showing that dependence on both reward variance and safety-identification complexity is unavoidable.

Critical strengths
  1. The paper provides a meaningful instance-dependent characterization of learning under step-wise constraints. Separating reward-learning difficulty from safety-identification complexity gives a useful view of how the safe subgraph affects regret.

  2. The theoretical results are fairly comprehensive. The paper provides an efficient algorithm, variance-dependent regret guarantees, constraint-violation bounds, and matching lower-bound arguments showing that the main instance-dependent quantities are necessary.

Critical weaknesses
  1. The resulting regret bound is quite complicated and its improvement over worst-case guarantees is somewhat instance-specific. In particular, the benefit depends on both low safe-policy variance and manageable safety-identification complexity. It would be useful to better characterize how broad the practically favorable regime is.

  2. The setting is relatively specialized. The results focus on finite-horizon tabular CMDPs with step-wise mean-cost constraints, and the algorithm relies heavily on the induced safe-subgraph structure. This limits how directly the results extend to more general CMDP formulations or function approximation.

Questions for authors
  1. Can the authors give a simpler characterization of the regimes in which the proposed regret bound strictly improves over the best existing worst-case CMDP bounds?

  2. How essential is the particular step-wise safety formulation to the analysis? Could the variance/safety-identification decomposition extend to other constraint formulations, such as cumulative episodic constraints?

  3. The identification complexity CC can become large due to small cost gaps or rare unsafe successors. Are there natural classes of CMDPs where CC can be bounded substantially better than its worst-case scaling?

4 comments

We thank the Reviewer for their constructive feedback and positive assessment of the paper’s soundness and theoretical contributions. The revised parts of the manuscript are colored in blue, and changes addressing your comments are marked with “@kTws” in green. Below, we address the weaknesses and questions raised, and hope these clarifications further strengthen your assessment of the paper.

Q1 (W1). Regimes of improvement over worst-case regret bounds.

Our bound recovers the worst-case regret rate O~(SAH3K)\widetilde O(S\sqrt{AH^3K}), matching the leading rate of OMDPD (Zhu et al., 2025). A simple sufficient condition for improvement is

K≳max⁡SC,S3AH,K\gtrsim\max\\{S\mathcal C,S^3AH\\},

under which the safety identification and additive terms are at most of order SAH3K\sqrt{SAH^3K}. The overall bound then attains the worst-case minimax rate for finite-horizon tabular RL (Zhang et al., 2025). Furthermore, when

\qquad \min\\{V_\Sigma/K,\operatorname{Var}^\star\\}\ll H^2,$$ the bound improves upon this worst-case minimax rate on the corresponding instances, up to logarithmic factors. Intuitively, this requires sufficiently low reward uncertainty within the safe region and enough interaction to make safety identification a smaller contribution. It includes low-variance safe policies and trajectories that encounter little local variance. Easier safety identification allows these gains to emerge sooner. We have added these sufficient conditions to **Section 5.1 (line 438)**. **Q2 (W2). Role of step-wise constraints and possible extensions.** Step-wise safety constraints are widely studied in safe RL (Amani et al., 2021; Xiong et al., 2023; Shi et al., 2023; Wei et al., 2024). Their key role here is recursive feasibility: a safe action satisfies the current cost threshold and permits safe continuation from every possible successor. This enables a safe comparison policy that agrees with exploration before its first unsafe action, separating safe-policy variance from the identification effort captured by $\mathcal C$. For expected cumulative constraints, the broader decomposition could separate reward learning from identifying feasible policies. If a strictly feasible baseline is available, one possible approach is to mix it with an exploratory policy, with the feasibility margin and budget excess determining the mixing required. Extending the guarantee would require controlling both the reward loss and additional variance introduced by mixing, alongside cumulative-cost estimation. McMahan’s (2025) budget-augmentation framework offers another promising route by introducing artificial budgets and allocating continuation budgets across successors. These approaches suggest avenues for extending the decomposition, while requiring new analysis. Function approximation is also a natural direction. The recursive characterization extends conceptually to continuous spaces through viable sets, preserving the distinction between safe-policy variance and safety identification. Linear-mixture models provide a concrete starting point, supported by work on safe subgraphs (Shi et al., 2023) and variance-adaptive learning (Zhao et al., 2023). Extending our guarantees would require efficient representations of viable sets and an identification complexity accounting for information sharing through features. We hope our structural perspective provides a foundation for these developments and have added this discussion as future work in **Appendix C.8 (line 1663)**. **References** - S. Amani, C. Thrampoulidis, and L. F. Yang. *Safe Reinforcement Learning with Linear Function Approximation*. ICML, 2021. - J. McMahan. *Polynomial-Time Approximability of Constrained Reinforcement Learning*. ICML, 2025. - M. Shi, Y. Liang, and N. Shroff. *A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints*. ICML, 2023. - H. Wei, X. Liu, and L. Ying. *Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration*. AAAI, 2024. - N. Xiong, Y. Du, and L. Huang. *Provably Safe Reinforcement Learning with Step-wise Violation Constraints*. NeurIPS, 2023. - Z. Zhang, Y. Chen, J. Lee, and S. S. Du. *Settling the Sample Complexity of Online Reinforcement Learning*. Journal of the ACM, 2025. - H. Zhao, J. He, D. Zhou, T. Zhang, and Q. Gu. *Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency*. COLT, 2023. - J. Zhu, K. Yu, D. Lee, X. Liu, and H. Wei. *An Optimistic Algorithm for Online CMDPs with Anytime Adversarial Constraints*. ICML, 2025.

Q3. CMDP classes with lower safety-identification complexity.

Yes. The recursion in Equation (7) gives three useful sufficient conditions. Let M≤SAHM\le SAH count unsafe actions at vertices reachable under safe policies, and assume every positive cost gap is at least Δc>0\Delta_c>0.

(i) Immediate violations. If all MM unsafe actions exceed the immediate cost threshold, their own cost observations suffice for exclusion: C≤M/Δc2\mathcal C \le M/\Delta_c^2. There is no dependence on downstream transition probabilities. This includes CMDPs with a feasible action at every state and step (Wei et al., 2024).

(ii) Short identification paths. Suppose recursive exclusion reaches direct cost violations within at most dd transitions along every branch, and each successor used for exclusion has probability at least p0>0p_0 > 0. Then C≤M(A/p0)d/Δc2\mathcal C \le M(A/p_0)^d/\Delta_c^2. The depth dd is local to safety identification and can be much smaller than HH. Related bounded time-to-failure assumptions also appear in safe control (Massiani et al., 2023).

(iii) Limited branching. Suppose the relevant transitions are deterministic and each downstream state with no safe continuation has at most one action satisfying the immediate cost threshold. Other actions can be excluded locally, leaving a single continuing chain. If this chain spans at most dd transitions, then C≤M[1+(A−1)d]/Δc2\mathcal C \le M[1+(A-1)d]/\Delta_c^2. Thus, identification complexity grows only linearly with depth, even when violations occur several steps later.

These classes illustrate how local detectability, short identification paths, and limited branching keep C\mathcal C manageable. We have added these examples in Appendix C.7 (line 1622) to clarify the favorable regimes.

References

H. Wei, X. Liu, and L. Ying. Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration. AAAI, 2024.

P.-F. Massiani, S. Heim, F. Solowjow, and S. Trimpe. Safe Value Functions. IEEE Transactions on Automatic Control, 2023.

Dear Reviewer,

Thank you again for your thoughtful questions and suggestions. We have provided further analyses and clarifications in our rebuttal and carefully revised the manuscript in light of your comments. We hope that our response has sufficiently addressed the concerns you raised.

As the discussion deadline approaches, we would be very grateful if you could take a look at our reply. We would be happy to discuss any further questions or suggestions you may have.

Thank you for your time and consideration.

I thank the authors for the clarification. I maintain my positive rating.

Reviewer_aAesOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies online learning in episodic tabular CMDPs with step-wise constraints. An action is considered safe if its mean cost is below a threshold and every possible next state still has a safe action. The authors propose SVAE, which estimates the safe actions using optimistic cost estimates and observed next states, and then plans within these actions using variance-aware exploration bonuses. The regret bound has two main terms: one depends on the return variance of safe policies, and the other depends on a new quantity C\mathcal{C} that measures how hard it is to rule out unsafe actions. The paper also gives step-wise violation bounds, a lower bound, and small synthetic experiments.

Critical strengths

The paper provides an interesting perspective on how safety constraints can reduce learning difficulty through the structure of the safe subgraph. The separation between safe-policy return variance and safety identification complexity is insightful. The theoretical results are meaningful. The proposed algorithm achieves instance-dependent regret bounds while controlling cumulative step-wise constraint violations. The lower-bound results further support the significance of the proposed complexity measures.

Critical weaknesses
  1. The paper focuses on tabular CMDPs with finite state and action spaces. While this setting allows a detailed theoretical analysis, it would be interesting to discuss whether the proposed safe-subgraph characterization and variance-dependent guarantees can be extended to large-scale MDPs with function approximation.

  2. The proposed complexity C\mathcal C is interesting, but it is not clear whether its definition provides the tightest characterization of safety identification difficulty. For example, Equation (7) only considers the immediate cost gap when ch(s,a)>τc_h(s,a)>\tau, even if an unsafe successor may provide a much easier way to eliminate the action. Moreover, the summation in C\mathcal C may overestimate the identification difficulty when different actions share downstream states and observations. It would be helpful to clarify whether a sharper complexity measure is possible.

  3. While the experiments provide useful illustrations of the theoretical findings, they are primarily conducted on a small gridworld and carefully constructed synthetic CMDPs. A wider variety of experimental settings would strengthen the evaluation. In particular, it would be helpful to consider larger and more complex CMDPs, different safe-subgraph topologies, and environments with varying levels of transition stochasticity and safety-identification difficulty.

Questions for authors

Please see weakness.

2 comments

We thank the Reviewer for their careful review and positive feedback. Below, we address the three points raised in the Weaknesses section. The revised parts of the manuscript are colored in blue, and changes addressing your comments are marked with “@aAes” in orange. We hope these clarifications address your concerns and strengthen your assessment of the paper.

W1. Extension to function approximation.

We agree that this is an important direction. Our recursive safety characterization extends conceptually to continuous state and action spaces through viable sets: an action satisfies the immediate mean-cost constraint and reaches states admitting safe continuation almost surely. The distinction between safe-policy return variance and safety identification difficulty therefore remains relevant. Linear-mixture models offer a promising starting point, with existing work on safe subgraphs under function approximation (Shi et al., 2023) and variance-dependent regret (Zhao et al., 2023). Extending our guarantees would require efficient representations of viable sets and an identification complexity accounting for information sharing through features. We hope our structural perspective provides a foundation for these developments. Following your suggestion, we have added this discussion to Appendix C.8 (line 1663) as a direction for future work.

W2. Tightness of the safety-identification complexity C\mathcal C.

Thank you for pointing this out. Our C\mathcal{C} provides a tractable characterization supporting the regret guarantee, rather than the tightest complexity for every instance. As you note, taking the cheaper of immediate-cost and downstream non-viability evidence could sharpen the local complexity, while accounting jointly for shared downstream observations could improve its aggregation. Our lower bounds establish that safety identification contributes unavoidable difficulty, with an Ω(Clog⁡(1/δ))\Omega(\mathcal{C}\log(1/\delta)) elimination bound on the disjoint-tree families specified in Appendix G.2. These results are consistent with sharper bounds when observations can be shared. We have clarified this scope in Appendix G.2 (line 2268) and discussed these points in Appendix C.8 (line 1658).

W3. Evaluation on larger and more diverse CMDPs.

Our theoretical results characterize how safe-policy return variance and safety identification difficulty jointly govern learning. The experiments complement this contribution by testing these mechanisms and evaluating SVAE’s performance. Following your suggestion, we have expanded the evaluation to navigation tasks with up to 225 states and horizon 40, alongside structured CMDPs with more reachable states and decision stages.

For navigation with S=225S=225, H=40H=40, and K=10,000K=10{,}000, evaluated across 10 seeds, SVAE reduces mean strong regret and cumulative violation by 40.07% and 30.08%, respectively, relative to SUCBVI, and by 47.77% and 69.18% compared with MVP-V. We also added controlled studies addressing the three dimensions you highlighted:

  • Transition stochasticity: SVAE achieves lower mean strong regret than its worst-case-variance ablation across all six tested conditions.

  • Safe-subgraph topology: Holding rewards and transitions fixed, we vary costs to induce safe trees and DAGs with merging paths. SVAE reduces mean strong regret relative to the same ablation by 9.1% and 9.9% in the two settings.

  • Safety identification difficulty: We vary successor reachability, cost gaps, identification depth, and the number of unsafe actions. Rarer non-viable successors require more root-action executions while leaving the required successor cost samples nearly unchanged, consistent with our complexity characterization. Across four additional environments with high-reward unsafe branches, recursive propagation reduces cumulative violation by 85.16%–97.09% relative to local cost filtering.

These additions provide broader empirical support for the theoretical findings. We thank the Reviewer for encouraging this expanded evaluation. These experiments have been added to Appendices H.2–H.6 (lines 2393–2685) in the revised manuscript.

References

M. Shi, Y. Liang, and N. Shroff. A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints. ICML, 2023.

H. Zhao, J. He, D. Zhou, T. Zhang, and Q. Gu. Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency. COLT, 2023.

Dear Reviewer,

Thank you again for your constructive feedback. We have provided additional experiments, analyses, and clarifications in our rebuttal and carefully revised the manuscript in light of your comments. We hope that our response has addressed the concerns you raised.

As the discussion deadline is approaching, we would be very grateful if you could take a moment to read our reply. We would be happy to discuss any further questions or suggestions you may have.

Thank you for your time and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Contributions and Findings

Dear Reviewers and Area Chair,

Thank you for the time and care devoted to evaluating our paper. We would like to briefly highlight its central contribution and the clarifications made during rebuttal.

Our paper studies variance-adaptive learning in tabular safe RL, where the safe region is initially unknown. We ask whether the learner can exploit low return variance within the true safe region while simultaneously identifying which actions are safe. The main findings are:

  1. Regret adapts to uncertainty within the safe region. Our bound separates safe-policy return variance from safety identification complexity. On fixed instances with zero safe-policy return variance, regret is polylogarithmic in the number of episodes, even when exploratory policies have high variance. The revision makes explicit that the same guarantee holds for strong regret (Theorem 2 and Proposition C.2).

  2. Safety can simplify reward learning while creating a distinct identification burden. Holding rewards and transitions fixed, changing costs can reduce transition-induced reward uncertainty. Conversely, an action satisfying its immediate cost constraint may rarely reach a state with no safe continuation. Identifying it as unsafe can therefore require substantial exploration even when cumulative constraint violation is small.

  3. The analysis connects these two effects. A safe comparison policy and stopped-trajectory variance bounds connect exploration to safe-policy variance. A recursive witness-tree argument controls the effort needed to identify unsafe actions. Supporting lower bounds show that both reward learning and safety identification can contribute unavoidable regret (Theorem 4 and Appendix G.2). To the best of our knowledge, our paper provides the first instance-dependent regret bound for CMDPs with step-wise constraints.

Our algorithm, SVAE, implements these ideas efficiently. Following the reviewers’ suggestions, we expanded our evaluation to larger CMDPs and a more diverse set of experiments varying the safe-subgraph structure, transition stochasticity, and difficulty of safety identification (Appendices H.2–H.6). These additions provide broader empirical support for our findings.

We hope our findings provide a useful perspective on when safety constraints simplify learning and the exploration required to realize that benefit.

Thank you for your consideration.

The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.