- 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
-
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.
-
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
- 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.
-
Nonmatching regret bounds. The safety identification term has linear dependence on and dependence on , while the lower bound has square-root dependence on both and . This leaves a gap of . Moreover, the variance-dependent lower bound only covers a restricted variance range. Thus, the optimality of the proposed regret bounds remains unclear.
-
Potentially conservative safety identification complexity. The proposed complexity 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 .
-
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 and .
Questions for authors
-
Can the authors clarify whether a similar variance-dependent bound holds for strong regret, where positive and negative regrets cannot cancel across episodes?
-
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?
-
Can the dependence on and in the safety identification term be improved? Can the necessity of the recursive rare-successor component of be established for general learning algorithms?
-
Can the safety identification complexity 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
Q3 (W2). Dependence on and necessity of the rare-successor component.
Our bounds establish the same dependence in the safety identification term, while leaving an 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 -valid permanent elimination rule requires 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 .
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 is the gap above the safety threshold. Incorporating this requirement into the recursion offers a route to a variance-sensitive refinement of . 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 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 . 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 and , SVAE reduces mean strong regret by 36.44% and cumulative violation by 45.46% relative to SUCBVI over episodes. For , 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.
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 in their dependence on and , 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 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 in the variance term and on in the safety identification term. They establish that both contributions are necessary. We agree that the remaining 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.
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!(SAHminVΣ,KVar⋆+SAH3minK,C+S2AH2)
with probability at least 1−δ.
Specifically, the proof of Proposition C.2 bounds each episode’s value gap by the nonnegative quantity E[Yk∣F1k], 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 (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 minK,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 K 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).