acceptodds
Under review as a conference paper at ICLR 2027

PAC Sample Complexity of CVaR-Constrained Reinforcement Learning

Abstract

High-stakes and safety-critical applications, such as financial investment and robotics, require sequential decision making that controls tail risk while optimizing average performance. Motivated by this fact, this paper studies Conditional Value-at-Risk (CVaR)-constrained reinforcement learning (RL) in the PAC setting. The goal is to minimize the expected cumulative performance cost subject to a CVaR constraint on the cumulative risk cost. We first prove the existence of an optimal policy that is stochastic and Markovian on the augmented state space. Based on this property, we propose an efficient and three-phase algorithm CVaR-PDS. This algorithm first solves linearly-constrained RL subproblems indexed by a grid of Value-at-Risk (VaR) candidates, and estimates a global model for subproblem solution evaluation, and then carefully performs post-hoc feasibility filtering and policy selection. We establish an sample complexity guarantee for algorithm CVaR-PDS, where is the constraint threshold, is the risk level, and is the Slater margin, together with an sample complexity lower bound. To the best of our knowledge, our work provides the first non-asymptotic (finite-sample) results for CVaR-constrained RL.

Primary area:
learning theory
Keywords:
Constrained Reinforcement Learning, Risk-Sensitive Reinforcement Learning, Conditional Value-at-Risk (CVaR), PAC Learning, Sample Complexity

Reviews

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

This work investigates CVaR-constrained reinforcement learning in the PAC setting. The authors propose a three-phase algorithm, CVaR-PDS. Phase I performs primal-dual learning for a collection of fixed-VaR subproblems; Phase II employs reward-free exploration to learn a global empirical model; and Phase III uses this model for post-hoc policy evaluation and selection. This design requires strong primal-dual guarantees only for the unknown fixed-VaR subproblem corresponding to the VaR of the optimal policy on the discretized MDP, rather than for all subproblems. The authors further establish both upper and lower bounds on the sample complexity of CVaR-constrained RL.

Critical strengths

This paper provides a rigorous theoretical analysis. Its results cover key aspects of the problem, with detailed proofs of suboptimality and constraint-violation transfer, as well as upper and lower bounds on sample complexity. Furthermore, the careful design of the three-stage algorithm avoids requiring Slater’s condition for every VaR subproblem; the condition is needed only for the subproblem associated with the VaR of an optimal policy in the discretized MDP.

Critical weaknesses

Although the paper’s main contributions are theoretical, the experimental section is rather limited, consisting of a single small-scale instance and a brief discussion. More importantly, even for this instance, the experimental implementation departs from the theoretically prescribed parameters and stopping rule. The authors explicitly state in the appendix that “This fixed segment in Phase II is an engineering budget rather than the theoretical stopping time KstopK_{\mathrm{stop}}” and that “The displayed Λ\Lambda, learning rates, KPDK_{\mathrm{PD}}, and bonus scale are frozen empirical choices. They are not the theorem’s parameter schedule. The frozen empirical bonus profile also differs from the bonuses in Algorithms 1 and 2.” Consequently, the experimental implementation is not directly covered by the PAC guarantee in Theorem 6.1, leaving a gap between the theoretical analysis and the empirical evaluation. These deviations, even on a small-scale instance, raise questions about the practical feasibility of the algorithm under its theoretically prescribed settings.

More detailed reporting of the theoretically required versus actual sample budgets, particularly the number of episodes needed to satisfy the Phase II stopping criterion, would help clarify this gap. Results on additional benchmarks and sensitivity analyses of key hyperparameters would also strengthen the empirical evaluation and help assess the method’s practical applicability.

Questions for authors
  1. Could the authors explain why the experiments use a fixed Phase II budget and empirical choices for Λ\Lambda, the learning rates, KPDK_{\mathrm{PD}}, and the bonus scale and profile, rather than the stopping rule and settings prescribed by the theoretical analysis? Are the theoretically prescribed settings overly conservative in practice, even for the small-scale instance evaluated in the paper?

  2. Although the paper avoids requiring Slater’s condition for every VaR subproblem, Assumption 5.2 still needs further explanation. Strict CVaR feasibility does not appear to imply that Assumption 5.2 necessarily holds. Could the authors provide further explanation of Assumption 5.2 and explain how to determine a valid positive value of ζξ\zeta_\xi required by Algorithm 1 when νj∗\nu_{j^*} is unknown?

5 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer 6rHP (Part 1/2)

Thank you for your helpful comments! We will incorporate the simplified algorithm without requiring Assumption 5.2 (Slater's condition) or the Slater margin ζξ\zeta_{\xi}, new experiments, and clarifications presented below into our revision.

Q2 (Simplified algorithm and removal of Slater's condition and the Slater margin ζξ\zeta_{\xi}): Thank you for your insightful question, which prompted us to improve our algorithm and remove unnecessary assumptions.

Our algorithm can be simplified into a two-phase framework, i.e., Reward-Free Exploration (RFE) followed by planning (referred to as CVaR-CP, CVaR-Constrained Planning). Specifically, CVaR-CP reparameterizes the augmented state by (νi−yh)+(\nu_i-y_h)^+, where νi\nu_i is the VaR candidate and yhy_h is the cumulative risk cost prior to step hh. This allows the same Bellman recursion to be used for all VaR candidates, and thus for a given Lagrange multiplier, a single shared backward dynamic programming evaluates the optimal policies for all VaR candidates.

Since CVaR-CP drops the original online primal-dual learning phase (Phase I) and performs optimal policy planning for all VaR candidates together, it achieves an improved sample complexity of O~(S2AH2αε2+SAH3αε3)\widetilde{\mathcal{O}}(\frac{S^2AH^2}{\alpha\varepsilon^2}+\frac{SAH^3}{\alpha\varepsilon^3}). In particular, by allocating a small fraction of ε\varepsilon as the planning slack parameter, the Lagrange multiplier can be upper bounded by O(Hε)\mathcal{O}(\frac{H}{\varepsilon}) without relying on strong duality, and thus CVaR-CP does not require Slater's condition or the Slater margin ζξ\zeta_{\xi}.

W1, W2, Q1 (Experiments, stopping rule, and sensitivity): We evaluated the simplified algorithm CVaR-CP against the baselines on the MDP described in Appendix A.1 under the same 400000-episode cap. We implemented our algorithm according to the theoretically guaranteed procedure, including the RFE stopping rule, to show its practical performance. Each algorithm was evaluated over 10 independent runs. Joint success means that both suboptimality and CVaR violation are at most ε=0.1\varepsilon=0.1. The results are reported as mean ±\pm standard deviation over 10 runs:

AlgorithmSuboptimalityCVaR violationJoint successRunning time (s)
CVaR-CP (ours)−0.03485±0.00062-0.03485\pm0.000620.05258±0.004320.05258\pm0.0043210/1010/1038.20±0.3338.20\pm0.33
PG-CVaR [Chow et al., 2018]2.40285±0.211952.40285\pm0.211950.10128±0.002360.10128\pm0.002360/100/10122.24±18.53122.24\pm18.53
CVaR-CPO [Zhang et al., 2025]1.01948±0.030951.01948\pm0.030950.06370±0.003970.06370\pm0.003970/100/10471.18±33.98471.18\pm33.98
OptPrimalDual-CMDP [Efroni et al., 2020]−0.03820±0.00077-0.03820\pm0.000770.11423±0.003590.11423\pm0.003590/100/10221.65±0.84221.65\pm0.84

CVaR-CP succeeds in all 10 runs using less running time than all baselines. CVaR-CPO and PG-CVaR pass the ε\varepsilon-feasibility test in 10 runs and 4 runs, respectively, but they fail to achieve joint success due to high suboptimality. OptPrimalDual-CMDP does not attain ε\varepsilon-feasibility in all runs, since it fails to handle the risk constraint.

AuthorsOpenReview ↗

Rebuttal to Reviewer 6rHP (Part 2/2)

Additional results on a larger MDP: We also evaluated all algorithms on a larger MDP with continuous risk costs under a 550000-episode cap. In this experiment, S=296S=296, A=16A=16, H=50H=50, ε=0.1\varepsilon=0.1, α=0.05\alpha=0.05, and τ=0.35\tau=0.35. We conduct 10 independent runs for each algorithm, and report the results as mean ±\pm standard deviation over 10 runs:

AlgorithmSuboptimalityCVaR violationJoint success
CVaR-CP (ours)−0.02655±0.00849-0.02655 \pm 0.008490.04026±0.010770.04026 \pm 0.0107710/1010/10
PG-CVaR0.16485±0.005160.16485 \pm 0.005160.05457±0.016630.05457 \pm 0.016630/100/10
CVaR-CPO0.27038±0.002360.27038 \pm 0.00236−0.19246±0.00164-0.19246 \pm 0.001640/100/10
OptPrimalDual-CMDP0.12961±0.000010.12961 \pm 0.000010.25850±0.000030.25850 \pm 0.000030/100/10

Across all 10 runs, CVaR-CP achieves both ε\varepsilon-feasibility and ε\varepsilon-optimality, whereas PG-CVaR and CVaR-CPO attain ε\varepsilon-feasibility but miss the ε\varepsilon-optimality target.

Sensitivity of key parameters: Following the reviewer's suggestion, we varied the accuracy parameter ε∈0.05,0.1,0.2\varepsilon \in \\{0.05,0.1,0.2\\} and the risk level α∈0.01,0.05,0.1\alpha \in \\{0.01,0.05,0.1\\} separately to validate the practical performance of our algorithm. We report the results as mean ±\pm standard deviation over 3 independent runs:

εαSuboptimalityCVaR violationJoint success
0.200.200.050.05−0.04405±0.00037-0.04405 \pm 0.000370.10117±0.003040.10117 \pm 0.003043/33/3
0.100.100.050.05−0.03489±0.00045-0.03489 \pm 0.000450.05489±0.001690.05489 \pm 0.001693/33/3
0.050.050.050.05−0.02127±0.00033-0.02127 \pm 0.000330.02672±0.001200.02672 \pm 0.001203/33/3
0.100.100.100.10−0.00022±0.00034-0.00022 \pm 0.00034−0.04356±0.00144-0.04356 \pm 0.001443/33/3
0.100.100.010.01−0.02245±0.00049-0.02245 \pm 0.000490.04741±0.000410.04741 \pm 0.000413/33/3

Across all settings, CVaR-CP achieves 3/3 joint success. As ε\varepsilon varies from 0.20.2 to 0.050.05, the CVaR violation of CVaR-CP steadily decreases from 0.101170.10117 to 0.026720.02672. In addition, as α\alpha ranges from 0.10.1 to stricter 0.010.01, CVaR-CP consistently satisfies both ε\varepsilon-optimality and ε\varepsilon-feasibility.

Thank you again for your time. If our response addresses your concerns satisfactorily, we would like to kindly ask you to consider raising your rating. Certainly, we are more than happy to answer any follow-up questions.

References:

  • Chow et al. Risk-Constrained Reinforcement Learning with Percentile Risk Criteria. JMLR, 2018.
  • Zhang et al. CVaR-Constrained Policy Optimization for Safe Reinforcement Learning. IEEE TNNLS, 2025.
  • Efroni et al. Exploration-Exploitation in Constrained MDPs. arXiv:2003.02189, 2020.
AuthorsOpenReview ↗

Dear Reviewer 6rHP, we were wondering if our response resolved your concerns?

Dear Reviewer 6rHP,

As the discussion period (authors + reviewers + AC) is nearing its deadline, we are eager to learn whether our responses have addressed your concerns. If you have any further questions, we would be more than happy to answer them.

Thank you!

Best regards,
Authors

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

This paper studies finite-sample learning in episodic tabular MDPs, minimizing expected cumulative performance cost subject to a CVaR constraint on cumulative risk cost. The alogorithm combines discretization, primal-dual learning and RFE. It establishes a PAC guarantee and a sample-complexity upper bound, together with an lower bound.

Critical strengths

The paper makes a theoretical contribution by establishing a finite-sample guarantee for CVaR-constrained RL. The analysis contains novel elements, including a useful discretization transfer argument. Overall, the paper is clearly written and well organized.

Critical weaknesses
  1. The gap between upper and lower bounds is large in their dependence on accuracy, horizon, and risk level. Even though the authors argue that this is the first lower bound result in this setting, this large gap limits their contribution.
  2. The paper provides limited justification for the three-phase design. Could one instead perform RFE once and then solve relaxed fixed-VaR CMDPs? More explanation and evidence are needed.
  3. The distinction from RL with risk-sensitive objectives could be better explained. What additional challenges arise when CVaR is used as a constraint rather than an objective, and when should practitioners prefer one formulation over the other? Or when we should use this algorithm?
Questions for authors
  1. Given Lemma D.15, why not first perform RFE and then minimize empirical performance over policies and VaR candidates subject to g^i(π)≤εest/α\widehat g_i(\pi)\le\varepsilon_{\mathrm{est}}/\alpha? Can Uniform evaluation bound the selected policy's violation?
  2. A few notation conventions could be made more explicit. In Theorem 5.1, the definition of g is not clear to me.
2 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer moeA

Thank you very much for your insightful comments! We will include the simplified algorithm, tightened bounds, and clarifications presented below in our revision.

W1, W2, Q1 (Simplified algorithm, tightened bounds, and upper-lower bound gap): Thank you for your insightful suggestion. We agree that Phase I (online primal-dual learning) can be removed, and our algorithm can be simplified into a two-phase framework, i.e., Reward-Free Exploration (RFE) followed by planning (referred to as CVaR-CP, CVaR-Constrained Planning), on the discretized MDP. Instead of solving separate linearly constrained MDP planning per VaR candidate, CVaR-CP reparameterizes the augmented state by (νi−yh)+(\nu_i-y_h)^+, where νi\nu_i is the VaR candidate and yhy_h is the cumulative risk cost prior to step hh. This allows the same Bellman recursion to be used for all VaR candidates, and thus for a given Lagrange multiplier, a single shared backward dynamic programming evaluates the optimal policies for all VaR candidates. For this simplified algorithm, the planning phase takes O(S2AH4ε2+SAH5ε3)\mathcal{O}(\frac{S^2AH^4}{\varepsilon^2}+\frac{SAH^5}{\varepsilon^3}) arithmetic operations with zero extra environment interaction.

Allocating a small fraction of ε\varepsilon as a planning slack parameter and appropriately setting an exploration tolerance parameter and an acceptance threshold (i.e., the exploration tolerance parameter plus the planning slack parameter), guarantee near-optimality and near-feasibility without requiring Slater's condition. The resulting sample complexity is O~(S2AH2αε2+SAH3αε3)\widetilde{\mathcal{O}}(\frac{S^2AH^2}{\alpha\varepsilon^2}+\frac{SAH^3}{\alpha\varepsilon^3}). The proof contains three steps:

  1. Retaining the discrete optimal policy: With high probability, RFE estimates the objective values for all policies and the fixed-VaR constraints for nearly feasible policies within the exploration tolerance parameter. This ensures that the optimal feasible policy on the discretized MDP remains approximately feasible under the empirical model.
  2. Controlling empirical performance and risk: The planning slack parameter provides an O(Hε)\mathcal{O}(\frac{H}{\varepsilon}) upper bound on the Lagrange multiplier used in planning. The planner returns a policy whose empirical performance cost is within the slack parameter of the best policy in the empirical feasible set and whose empirical constraint value meets the acceptance threshold.
  3. Transferring to the original MDP: Combining these RFE evaluation guarantees with the discretization transfer (Theorem 5.1) in our paper yields a suboptimality of at most ε2\frac{\varepsilon}{2} and a CVaR violation of at most ε\varepsilon on the original MDP.

Upper and lower bound gap: Under the simplified RFE-then-planning framework, our sample complexity improves to O~(S2AH2αε2+SAH3αε3)\widetilde{\mathcal{O}}(\frac{S^2AH^2}{\alpha\varepsilon^2}+\frac{SAH^3}{\alpha\varepsilon^3}). This result removes Slater's condition and the dependence on the Slater margin, and improves the dependence on the risk level from α−2\alpha^{-2} to α−1\alpha^{-1}. Compared to our lower bound Ω(SAH2αε2)\Omega(\frac{SAH^2}{\alpha\varepsilon^2}), the first and second terms in the upper bound have only additional factors of SS (arising from the RFE transition model estimation) and Hε\frac{H}{\varepsilon} (stemming from the discretized risk-cost grid), respectively, up to logarithmic factors.

W3 (CVaR constraint versus objective): CVaR-objective RL optimizes tail performance. In contrast, CVaR-constrained RL optimizes average performance while controlling the tail risk within a threshold.

The CVaR-feasible set can be nonconvex in occupancy measures, so standard convex-CMDP guarantees do not apply directly. In addition, even when the problem is decomposed into linearly constrained RL subproblems indexed by VaR candidates, VaR can take infinitely many values under continuous risk costs. Moreover, the use of discretization for CVaR-constrained RL requires accounting for its effects on both objective values (optimality) and CVaR constraint values (feasibility). These challenges significantly complicate the algorithm design and analysis.

CVaR-constrained RL is more suitable when practitioners still aim to optimize average performance but also seek to limit the cost in worst-case scenarios within a threshold. For example, in portfolio selection, we want to maximize expected return while keeping the CVaR of cumulative loss below a capital limit.

Q2 (Notation):: We have defined g(π):=CVaRα(Cπ)−τg(\pi):=CVaR_\alpha(C^\pi)-\tau in Section 3. We will add a reminder before Theorem 5.1 in our revision.

Thank you again for your time. If our response resolves your concerns satisfactorily, we would kindly ask you to support our paper. We are more than happy to answer any follow-up questions.

Thank you for clarifying and explaining the new simplified algorithm. Looks like substantial changes are still needed. I will keep my score.

Reviewer_Y7YUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents CVaR-PDS, a method for learning a policy that minimizes expected cumulative performance cost subject to a CVaR constraint on cumulative risk cost in finite-horizon tabular MDPs. The method augments the state with accumulated risk cost and discretizes risk costs to obtain finitely many candidate VaR values. For each candidate, it runs optimistic primal-dual learning, then learns a shared model through reward-free exploration and uses that model to evaluate and select a policy. Under a Slater condition at the VaR of an optimal discretized policy, the paper establishes a finite-sample guarantee for near-optimality and approximate constraint satisfaction, and also derives a sample complexity lower bound. A numerical experiment compares an empirical implementation against constrained RL baselines.

Critical strengths

This paper gives the first finite-sample guarantee relative to a globally optimal policy for CVaR-constrained RL. The reductions are careful: the discretization error transfers to the original MDP with only a one-sided increase in constraint violation, and the post-hoc selection needs Slater's condition for only one subproblem instead of all of them.

Critical weaknesses
  1. The paper does not show why Phase I is needed. The proof sketch of Theorem 6.1 says that the model learned in Phase II controls the estimation error for any policy, not only for the candidate solutions. Then one could skip Phase I and, for each VaR candidate, solve the constrained planning problem directly on this model, with the empirical risk constraint relaxed by its estimation-error bound. The selection step in Phase III could then use the same error-control argument, since the optimal policy on the discretized MDP would remain feasible for its own empirical subproblem after this relaxation. This alternative would need neither Slater's condition nor the Slater margin as an input. Section 6 also says that the third term of the bound, which depends on the Slater margin, comes from primal-dual learning in Phase I. So, if this reasoning holds, the main technical difficulty addressed by the paper is avoided by Phase II alone.

  2. The experiments do not test the algorithm that the paper analyzes. They use a single small MDP. Appendix A says that all bonuses are scaled by a factor of 0.000003, that Phase II runs a fixed budget of 200 episodes instead of the stopping rule, and that the other settings are not the theorem's parameter schedule. So Figure 2 reports a tuned variant of CVaR-PDS, not the algorithm in Theorem 6.1. Also, the hyperparameters of the two policy-gradient baselines seem chosen on a different MDP, not on the one used in the reported experiments. Finally, there is no explore-then-plan baseline that plans on the Phase II model without Phase I. So the experiments do not show that Phase I is needed.

Questions for authors
  1. How does this paper's sample complexity result relate to reward-free approaches to constrained RL, such as [1]? After state augmentation and risk-cost discretization, which parts of the sample complexity analysis require new arguments specific to the CVaR constraint, beyond learning a model and planning under expected-cost constraints?

  2. The algorithm takes the Slater margin of the discretized MDP at the optimal VaR candidate as an input (Algorithm 1). This margin depends on the target accuracy through the discretization step. Can it be bounded by a margin of the original MDP, and what happens when it is misspecified?

  3. Consider a one-step problem with two actions. The first has performance cost zero and deterministic risk cost 0.5. The second has performance cost one and risk cost zero. Let the CVaR budget be 0.5 and assume that 0.5 is on the VaR grid. The original problem is strictly feasible because of the second action, while the optimal policy chooses the first action and has VaR 0.5. At that VaR, however, the constraint in Eq. 5 is zero for every policy, so Assumption 5.2 fails. Is this problem excluded by the main theorem?

  4. Appendix A.2 uses bonuses scaled by 0.000003 and a fixed 200-episode Phase II budget instead of the theoretical stopping rule. How sensitive are the results to these choices? Could the authors also add a baseline that uses reward-free exploration followed by constrained planning, under the same total episode budget? Finally, the policy-gradient baselines were not tuned on the same MDP instance. Tuning all methods on the same instance with comparable budgets would make the comparison more informative.

3 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer Y7YU (Part 1/2)

Thank you for your constructive comments! We will include the simplified algorithm and its guarantees, new experiments, and the clarifications on implementation and analytical novelty in our revision.

W1, Q2, Q3 (Algorithm simplification and removal of Slater's condition): Thank you for your insightful suggestion. We agree that Phase I (online primal-dual learning) can be removed, and our algorithm can be simplified into a two-phase framework, i.e., Reward-Free Exploration (RFE) followed by planning (referred to as CVaR-CP, CVaR-Constrained Planning), on the discretized MDP. Instead of solving separate linearly constrained MDP planning per VaR candidate, CVaR-CP reparameterizes the augmented state by (νi−yh)+(\nu_i - y_h)^+, where νi\nu_i is the VaR candidate and yhy_h is the cumulative risk cost prior to step hh. This allows the same Bellman recursion to be used for all VaR candidates, and thus for a given Lagrange multiplier, a single shared backward dynamic programming evaluates the optimal policies for all VaR candidates. For this simplified algorithm, the planning phase takes O(S2AH4ε2+SAH5ε3)\mathcal{O}(\frac{S^2AH^4}{\varepsilon^2}+\frac{SAH^5}{\varepsilon^3}) arithmetic operations with zero extra environment interaction.

Allocating a small fraction of ε\varepsilon as a planning slack parameter and appropriately setting an exploration tolerance parameter and an acceptance threshold (i.e., the exploration tolerance parameter plus the planning slack parameter), guarantee near-optimality and near-feasibility without requiring Slater's condition. The resulting sample complexity is O~(S2AH2αε2+SAH3αε3)\widetilde{\mathcal{O}}(\frac{S^2AH^2}{\alpha\varepsilon^2}+\frac{SAH^3}{\alpha\varepsilon^3}). The proof contains three steps:

  1. Retaining the discrete optimal policy: With high probability, RFE estimates the objective values for all policies and the fixed-VaR constraints for nearly feasible policies within the exploration tolerance parameter. This ensures that the optimal feasible policy on the discretized MDP remains approximately feasible under the empirical model.
  2. Controlling empirical performance and risk: The planning slack parameter provides an O(Hε)\mathcal{O}(\frac{H}{\varepsilon}) upper bound on the Lagrange multiplier used in planning. The planner returns a policy whose empirical performance cost is within the slack parameter of the best policy in the empirical feasible set and whose empirical constraint value meets the acceptance threshold.
  3. Transferring to the original MDP: Combining these RFE evaluation guarantees with the discretization transfer (Theorem 5.1) in our paper yields a suboptimality of at most ε2\frac{\varepsilon}{2} and a CVaR violation of at most ε\varepsilon on the original MDP.

For Q3, under our simplified algorithmic framework, Assumption 5.2 can be removed, and the problem instance that the reviewer constructed is covered by our updated theoretical guarantees.

W2, Q4 (Revised experiments, RFE stopping, and baselines): We evaluated the simplified algorithm CVaR-CP against the baselines on the MDP described in Appendix A.1 under the same 400000-episode cap. We implemented our algorithm according to the theoretically guaranteed procedure, including the RFE stopping rule. The baselines PG-CVaR [Chow et al., 2018] and CVaR-CPO [Zhang et al., 2025] are adapted from their original infinite-horizon setting to the finite-horizon setting, and the parameter settings of all algorithms are determined on the same MDP instance. Each algorithm was evaluated over 10 independent runs. Joint success means that both suboptimality and CVaR violation are at most ε=0.1\varepsilon=0.1. The results are reported as mean ±\pm standard deviation over 10 runs:

AlgorithmSuboptimalityCVaR violationJoint successRunning time (s)
CVaR-CP (ours)−0.03485±0.00062-0.03485 \pm 0.000620.05258±0.004320.05258 \pm 0.0043210/1010/1038.20±0.3338.20 \pm 0.33
PG-CVaR [Chow et al., 2018]2.40285±0.211952.40285 \pm 0.211950.10128±0.002360.10128 \pm 0.002360/100/10122.24±18.53122.24 \pm 18.53
CVaR-CPO [Zhang et al., 2025]1.01948±0.030951.01948 \pm 0.030950.06370±0.003970.06370 \pm 0.003970/100/10471.18±33.98471.18 \pm 33.98
OptPrimalDual-CMDP [Efroni et al., 2020]−0.03820±0.00077-0.03820 \pm 0.000770.11423±0.003590.11423 \pm 0.003590/100/10221.65±0.84221.65 \pm 0.84
AuthorsOpenReview ↗

Rebuttal to Reviewer Y7YU (Part 2/2)

Q1 (Comparison with reward-free linearly constrained RL):

The sample complexity of our simplified algorithm is O~(S2AH2αε2+SAH3αε3)\widetilde{\mathcal{O}}(\frac{S^2AH^2}{\alpha\varepsilon^2}+\frac{SAH^3}{\alpha\varepsilon^3}), while the sample complexity for reward-free linearly constrained RL [Miryoosefi and Jin, 2022] is O~(SAH4ε2)\widetilde{\mathcal{O}}(\frac{SAH^4}{\varepsilon^2}). Our result has a lighter dependence on HH and additional factors of Sα\frac{S}{\alpha} and 1αε\frac{1}{\alpha \varepsilon}. The dependence on 1α\frac{1}{\alpha} is inevitable in risk-constrained RL problems, as supported by our lower bound. The additional dependence on SS and 1ε\frac{1}{\varepsilon} arises from the RFE transition estimation with state augmentation and discretized risk-cost grid. (We could not find the reference [1] in your review, and thus compare with the representative work [Miryoosefi and Jin, 2022] on reward-free linearly constrained RL.)

Beyond standard model learning and planning, our analysis involves these new techniques: (1) To overcome the challenge that CVaR amplifies the constraint estimation error by 1α\frac{1}{\alpha}, we exploit the small tail-risk term of any policy that is near-feasible under the true or empirical model to establish tighter bounds on constraint estimation errors. (2) We carefully handle the O(Hε)\mathcal{O}(\frac{H}{\varepsilon})-sized risk-cost grid to ensure that the optimal feasible policy remains eligible for comparison and the additional CVaR violation for the selected policy is bounded. These techniques yield a sample complexity bound comparable to that for reward-free linearly constrained RL, despite the additional challenges of state augmentation, discretization, and nonconvexity introduced by CVaR constraints.

Thank you again for your time. If our response addresses your concerns satisfactorily, please consider raising your rating. We are more than happy to answer any follow-up questions.

References:

  • Chow et al. Risk-Constrained Reinforcement Learning with Percentile Risk Criteria. JMLR, 2018.
  • Zhang et al. CVaR-Constrained Policy Optimization for Safe Reinforcement Learning. IEEE TNNLS, 2025.
  • Efroni et al. Exploration-Exploitation in Constrained MDPs. arXiv:2003.02189, 2020.
  • Miryoosefi and Jin. A simple reward-free approach to constrained reinforcement learning. ICML 2022.
AuthorsOpenReview ↗

Dear Reviewer Y7YU, we were wondering if our response resolved your concerns?

Dear Reviewer Y7YU,

As the discussion period (authors + reviewers + AC) is nearing its deadline, we are eager to learn whether our responses have addressed your concerns. If you have any further questions, we would be more than happy to answer them.

Thank you!

Best regards,
Authors

Reviewer_9prhOpenReview ↗
Rating
3(+1)
Confidence
3(+1)
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies reinforcement learning with an expected cumulative performance-cost objective subject to a Conditional Value-at-Risk (CVaR) constraint on cumulative risk costs. The authors establish an augmented-state Markov policy reduction and propose CVaR-PDS, a three-phase algorithm combining VaR discretization, optimistic primal-dual learning, reward-free exploration, and post-hoc policy selection. They derive finite-sample PAC guarantees for approximate optimality and feasibility, together with an information-theoretic sample-complexity lower bound. Experiments on a synthetic tabular MDP demonstrate favorable performance relative to several constrained RL baselines.

Critical strengths
  • Meaningful theoretical contribution to risk-constrained RL: They are addressing an important distinction between optimizing CVaR and minimising the expected cost subject to a CVaR constraint.

  • Well-motivated reduction and careful policy-class treatment: The augmented-state Markovization result preserves both expected performance and the distribution of cumulative risk costs, allowing the analysis to accommodate stochastic, history-dependent policies.

  • Nontrivial handling of feasibility across VaR-indexed subproblems: A noteworthy contribution is the post-hoc selection procedure, which avoids requiring Slater's condition for every fixed-VaR subproblem.

  • Complementary lower-bound analysis. The lower-bound construction embeds difficult policy-identification problems into trajectories contributing to the CVaR tail, providing a useful characterization of the dependence on the risk level, state-action space, horizon, and target accuracy.

Critical weaknesses
  • I think my most important concern is that the three-phase algorithm may be unnecessarily complicated. I suggest that the authors to run the reward-feww exploration phase to obtain a uniformly accurate empirical model and also to directly solve the CVaR-constrained planning problem in that empirical model, allowing a small constraint relaxation. For each fixed VaR candidate, the empirical planning problem is linear in augmented-state occupancy measures and can be solved using a linear program.

  • The large gap between upper and lower sample-complexity bounds needs to be justified. This is a major concern.

  • To me, it seems that the experiments do not evaluate the theoretically guaranteed algorithm. Appendix 2 reveals that the experimental implementation differs materially from the algorithm analyzed in the paper.

Questions for authors

NA

5 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer 9prh (Part 1/2)

Thank you for your constructive comments! We will incorporate the simplified algorithm, tightened bounds, and new experiments presented below into our revision.

W1 (Algorithm simplification and removal of Slater's condition): Thank you for your insightful suggestion. We agree that Phase I (online primal-dual learning) can be removed, and our algorithm can be simplified into a two-phase framework, i.e., Reward-Free Exploration (RFE) followed by planning (referred to as CVaR-CP, CVaR-Constrained Planning), on the discretized MDP. Instead of solving separate linearly constrained MDP planning per VaR candidate, CVaR-CP reparameterizes the augmented state by (νi−yh)+(\nu_i - y_h)^+, where νi\nu_i is the VaR candidate and yhy_h is the cumulative risk cost prior to step hh. This allows the same Bellman recursion to be used for all VaR candidates, and thus for a given Lagrange multiplier, a single shared backward dynamic programming evaluates the optimal policies for all VaR candidates. For this simplified algorithm, the planning phase takes O(S2AH4ε2+SAH5ε3)\mathcal{O}(\frac{S^2AH^4}{\varepsilon^2}+\frac{SAH^5}{\varepsilon^3}) arithmetic operations with zero extra environment interaction.

Allocating a small fraction of ε\varepsilon as a planning slack parameter and appropriately setting an exploration tolerance parameter and an acceptance threshold (i.e., the exploration tolerance parameter plus the planning slack parameter), guarantee near-optimality and near-feasibility without requiring Slater's condition. The resulting sample complexity is O~(S2AH2αε2+SAH3αε3)\widetilde{\mathcal{O}}(\frac{S^2AH^2}{\alpha\varepsilon^2}+\frac{SAH^3}{\alpha\varepsilon^3}). The proof contains three steps:

  1. Retaining the discrete optimal policy: With high probability, RFE estimates the objective values for all policies and the fixed-VaR constraints for nearly feasible policies within the exploration tolerance parameter. This ensures that the optimal feasible policy on the discretized MDP remains approximately feasible under the empirical model.
  2. Controlling empirical performance and risk: The planning slack parameter provides an O(Hε)\mathcal{O}(\frac{H}{\varepsilon}) upper bound on the Lagrange multiplier used in planning. The planner returns a policy whose empirical performance cost is within the slack parameter of the best policy in the empirical feasible set and whose empirical constraint value meets the acceptance threshold.
  3. Transferring to the original MDP: Combining these RFE evaluation guarantees with the discretization transfer (Theorem 5.1) in our paper yields a suboptimality of at most ε2\frac{\varepsilon}{2} and a CVaR violation of at most ε\varepsilon on the original MDP.

W2 (Upper and lower bound gap): Under the simplified RFE-then-planning framework, our sample complexity improves to O~(S2AH2αε2+SAH3αε3)\widetilde{\mathcal{O}}(\frac{S^2AH^2}{\alpha\varepsilon^2}+\frac{SAH^3}{\alpha\varepsilon^3}). This result removes Slater's condition and the dependence on the Slater margin, and improves the dependence on the risk level from α−2\alpha^{-2} to α−1\alpha^{-1}. Compared to our lower bound Ω(SAH2αε2)\Omega(\frac{SAH^2}{\alpha\varepsilon^2}), the first and second terms in the upper bound have only additional factors of SS (arising from the RFE transition model estimation) and Hε\frac{H}{\varepsilon} (stemming from the discretized risk-cost grid), respectively, up to logarithmic factors.

AuthorsOpenReview ↗

Rebuttal to Reviewer 9prh (Part 2/2)

W3 (Experiments): We evaluated the simplified algorithm CVaR-CP against the baselines on the MDP described in Appendix A.1 under the same 400000-episode cap. We implemented our algorithm according to the theoretically guaranteed procedure, including the RFE stopping rule. Each algorithm was evaluated over 10 independent runs. Joint success means that both suboptimality and CVaR violation are at most ε=0.1\varepsilon=0.1. The results are reported as mean ±\pm standard deviation over 10 runs:

AlgorithmSuboptimalityCVaR violationJoint successRunning time (s)
CVaR-CP (ours)−0.03485±0.00062-0.03485 \pm 0.000620.05258±0.004320.05258 \pm 0.0043210/1010/1038.20±0.3338.20 \pm 0.33
PG-CVaR [Chow et al., 2018]2.40285±0.211952.40285 \pm 0.211950.10128±0.002360.10128 \pm 0.002360/100/10122.24±18.53122.24 \pm 18.53
CVaR-CPO [Zhang et al., 2025]1.01948±0.030951.01948 \pm 0.030950.06370±0.003970.06370 \pm 0.003970/100/10471.18±33.98471.18 \pm 33.98
OptPrimalDual-CMDP [Efroni et al., 2020]−0.03820±0.00077-0.03820 \pm 0.000770.11423±0.003590.11423 \pm 0.003590/100/10221.65±0.84221.65 \pm 0.84

CVaR-CP succeeds in all 10 runs using less running time than all baselines. CVaR-CPO and PG-CVaR pass the ε\varepsilon-feasibility test in 10 runs and 4 runs, respectively, but they fail to achieve joint success due to high suboptimality. OptPrimalDual-CMDP does not attain ε\varepsilon-feasibility in all runs, since it fails to handle the risk constraint.

Thank you again for your time. If our response resolves your concerns satisfactorily, please consider raising your rating. Certainly, we are more than happy to answer any follow-up questions.

References:

  • Chow et al. Risk-Constrained Reinforcement Learning with Percentile Risk Criteria. JMLR, 2018.
  • Zhang et al. CVaR-Constrained Policy Optimization for Safe Reinforcement Learning. IEEE TNNLS, 2025.
  • Efroni et al. Exploration-Exploitation in Constrained MDPs. arXiv:2003.02189, 2020.
AuthorsOpenReview ↗

Dear Reviewer 9prh, we were wondering if our response resolved your concerns?

Dear Reviewer 9prh,

Thank you again for your effort in reviewing our paper!

As the discussion period (authors+reviewers+AC) is nearing its deadline, we would appreciate knowing if our response resolved your concerns. Should there be any further questions, we are more than happy to address them. Thank you!

Best regards,
Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.