acceptodds
Under review as a conference paper at ICLR 2027

A Variance-Optimal Replay Framework for Safe Off-Policy Reinforcement Learning

Abstract

Existing off-policy safe reinforcement learning methods inherit replay sampling strategies developed for unconstrained settings. Consequently, replay sampling remains optimized for reward rather than safety, compromising constraint satisfaction. Methods that prioritize transitions using safety-related heuristics reshape the sampling distribution without correction, inadvertently shifting the very solution that the agent is meant to reach. In this work, we treat the replay sampling distribution as a control variable to improve the agent's safety and learning performance. We prove that importance-weighted replay sampling preserves the expected constrained policy update, while affecting only its variance. We further show that reducing this variance lowers the probability of unsafe updates during training. Building on this result, we derive a closed-form replay sampling strategy that achieves the minimum possible variance across minibatches and reduces safety violations. At convergence, it asymptotically approaches the optimal policy of the underlying Constrained Markov Decision Process. Our sampling method is compatible with a wide range of gradient-based safe reinforcement learning algorithms and demonstrates consistent improvements over existing replay sampling methods on the Safety Gymnasium benchmark suite.

Primary area:
reinforcement learning
Keywords:
Safe Reinforcement Learning, Replay Buffer Prioritization

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_jNNgOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes VOSR, a replay-sampling module for off-policy safe reinforcement learning. It treats the replay distribution as a control variable and uses importance weighting to correct both replay-prioritization changes and, in the idealized analysis, state and action distribution mismatch. The authors derive a sampling distribution proportional to the baseline probability times a weighted magnitude of each transition's projected reward and cost-gradient contributions. They prove that this distribution minimizes a weighted sum of two scalar gradient-estimation variances, bound the probability of selecting an incorrect branch of a piecewise-linear safe optimizer, and argue that the ideal sampler preserves the optimizer's constrained stationary set. VOSR is integrated with SAC-Lagrangian, CRPO, and PCRPO and compared with uniform, TD-error, safety-oriented, and uncertainty-oriented replay on Safety Gymnasium tasks.

Critical strengths
  1. The motivation is well targeted. Replay sampling is usually designed for reward or critic learning, even though safe policy optimizers depend on both reward and cost gradients. The proposed objective directly reflects this conflict and gives a principled explanation for why a transition with a large contribution to a safety-relevant gradient may deserve higher sampling probability.

  2. The paper combines analysis with broad empirical testing. The importance-corrected estimator and the derivation (q^*(i)\propto b(i)\sqrt{(s_i^c)^2+\kappa(s_i^r)^2}) provide a meaningful baseline for designing safety-aware replay. Across three base optimizers and multiple Safety Gymnasium tasks, VOSR reports lower cost-gradient variance and lower training violation fractions while maintaining comparable returns. For an engineering-oriented replay method, these empirical results are important evidence.

Critical weaknesses
  1. The theoretical guarantees do not directly characterize the implemented VOSR sampler. Theorem 1 derives the minimizer of the unconstrained weighted variance objective, (q^*(i)\propto b(i)\sqrt{(s_i^c)^2+\kappa(s_i^r)^2}). The practical algorithm instead uses (q_\epsilon(i)\propto b(i)\exp(\rho_i/\eta)), which is the solution of a different KL-constrained linear-priority objective, not the original variance objective with a KL constraint. In addition, the ideal unbiasedness argument assumes exact state-visitation and action ratios and untruncated importance weights, whereas the implementation estimates the state ratio and clips weights to [0.1, 10]. The priority scores are computed from noisy current-gradient estimates and only within a candidate pool. Consequently, the claims that the practical sampler is variance-optimal, leaves the expected optimizer update unchanged, and preserves the constrained stationary set should be stated as idealized claims unless the effects of these approximations are analyzed. In particular, unbiased gradients do not by themselves imply an unbiased update for branch-switching or projection-based nonlinear optimizers.

  2. The method's computational and scalability costs are not evaluated, although they are central to the proposed replay framework. Standard prioritized replay can maintain TD-error priorities over a large buffer with a tree data structure, whereas VOSR's priority depends on the current actor score, both critics, global reward/cost directions, importance ratios, and a learned state-density ratio. These quantities change as the policy and critics are updated, so maintaining accurate priorities over the entire buffer would require repeatedly computing per-transition gradient projections. The implementation therefore scores only a candidate pool of 512 transitions before sampling the training minibatch. This reduces cost but introduces another sampling approximation and can miss high-value transitions elsewhere in a large buffer. The paper reports neither wall-clock or throughput overhead nor the effect of candidate-pool size, density-ratio refresh frequency, or fixed-compute comparisons. Moreover, the appendix changes effective safety margins and SAC multiplier settings between VOSR and some baselines, which makes it difficult to attribute improvements solely to replay sampling. These omissions are particularly consequential for an engineering contribution whose practical value depends on whether the safety gains justify the additional computation.

Questions for authors
  1. Please clarify the exact status of the practical sampler relative to Theorem 1. What is the theoretical objective optimized by the exponential KL-tempered distribution, and how do state-ratio estimation error, weight clipping, priority estimation from a candidate pool, and nonlinear branch selection affect unbiasedness and stationary-set preservation? A comparison between the ideal (q^*), the KL-tempered sampler, and the implemented sampler would help delimit the guarantees.

  2. What is the end-to-end computational cost of VOSR? Please report wall-clock time, update throughput, memory, and additional backward passes relative to each replay baseline, together with candidate-pool-size and density-ratio-refresh ablations. Under identical safety margins, multiplier hyperparameters, and a fixed compute budget, does VOSR retain its reward and violation improvements? These comparisons are needed to assess whether the method scales beyond the relatively small candidate pool used in the implementation.

3 comments

Question 1: Status of the practical sampler relative to Theorem 1 and its guarantees

Response. The practical sampler is a smoothed approximation of the ideal sampler of Theorem 1, not its exact solution. Since the correction b(i)/q(i)b(i)/q(i) in Eq. (3) keeps the gradients unbiased for every sampler (Lemma 1), the sampler can only change their variance. Theorem 1 minimizes this variance in Eq. (5) and gives the exact sampler q⋆(i)∝b(i)ζiq^\star(i)\propto b(i)\zeta_i. However, q⋆q^\star can place most of its probability on a few high-score transitions, so each minibatch keeps repeating the same samples and ignores most of the replay buffer, which reduces replay diversity. Adding the KL constraint of Eq. (5) prevents this concentration, but then the problem has no closed-form solution. Proposition 2 therefore solves a simpler problem. It maximizes the expected score ∑iq(i)ζi\sum_i q(i)\zeta_i subject to KL(q∥b)≤ϵ\mathrm{KL}(q\Vert b)\le\epsilon, which gives the exponential KL-tempered sampler qϵ⋆q_\epsilon^\star of Eq. (6). This sampler still favours high-score transitions while staying close to uniform replay, but it needs exact scores, which depend on the true gradient directions and action values that are unknown during training. Therefore, the deployed VOSR uses the form of Eq. (6) with estimated scores. These scores are clipped to remove outliers and standardized within a candidate pool, so that their scale stays similar throughout training (Section 4.2). Table 8 shows that, relative to Uniform Replay, the cost-score variance is 0.320.32 for q⋆q^\star, 0.460.46 for qϵ⋆q_\epsilon^\star, and 0.520.52 for the deployed sampler, while the deployed sampler uses the most diverse set of transitions.

The approximations do not remove the guarantees that matter (Appendix A.1.5). Scoring a candidate pool adds variance but no bias (Lemma 2). Weight clipping and state-ratio error shift the mean gradients by the same small amount for every sampler (Proposition 3, Table 9), so all samplers keep one shared stationary set (Theorem 3). For nonlinear branch selection, Theorem 2 shows that wrong branches do not depend on the sampler, while wrong-direction steps grow with variance, which VOSR reduces (Table 10). Table 2 summarizes which claims hold for each sampler. For viewing Table 2, Table 8, Table 9 and Table 10, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.1 (Table 2) and Appendix A.3 (Table 8, Table 9 and Table 10) of the paper.

Question 2: End-to-end computational cost and comparison under a fixed compute budget

Response. VOSR has a higher computational cost per step, but provides better safety and performance than baseline samplers. It takes 91–96% more wall-clock time per environment step than Uniform Replay and uses 0.34–0.37 GB more GPU memory than Uniform Replay (refer to Table 11, and Table 12). Its computational cost depends on the candidate-pool size rather than the replay buffer size, so increasing the buffer does not increase this overhead. Larger pool size of 1024 and 2048 increase runtime without improving performance over the default size of 512. Refreshing β\beta every 250 steps gives the best results (Table 13). We also compare all samplers under the same wall-clock time and optimizer settings (Table 14). The baselines complete 4.6–5.9 million steps compared with 3 million for VOSR. Despite fewer steps, VOSR achieves a higher return (1262.4 versus 1052.4), lower cost (2.9 versus 7.5), and fewer training violations (0.025 versus 0.182). These results show that VOSR improves safety through better replay sampling that requires more computation. For viewing Table 11, Table 12, Table 13 and Table 14, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.3 of the paper.

Thank you for the clarifications. I find the revised distinction between the idealized analysis and the implemented VOSR helpful, and I appreciate the additional analysis of the practical approximations. Some gap between the theoretical analysis and the implemented method remains. While the revisions clarify which results apply under the practical approximations, the claims should be carefully scoped to distinguish guarantees for the idealized sampler from those established for the deployed implementation. VOSR also incurs substantial runtime overhead, but given the reported improvements in return, cost, and constraint violations under a matched wall-clock budget, I consider this trade-off worthwhile. I have updated my rating to 3.

We agree that the guarantees for the idealized sampler must be kept separate from those for the deployed implementation. In the submitted revised version of the paper, Table 2 (in the Appendix/supplementary material) summarizes which claims hold in each setting, and the main text (Sec. 4.2, Theorem 3, and the Conclusion) maintains the same distinction, with the relevant text marked in blue.

Reviewer_ckPBOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary
  • replay sampling is useful for off-policy safe RL, however it was designed for optimizing reward
  • using concepts from importance sampling applied to SGD, one can treat the replay sampling distribution as a control
  • a variance-optimal sampler can preserve the constrained policy update, and reducing the variance reduces unsafe updates
  • minimizing this variance will approach the optimal policy
Critical strengths
  • The premise of this paper makes a lot of sense. The importance-correction concept is solid and considering action and state-visitiation ratios is a good approach. The paper should be clear about applying concepts from importance sampling from SGD to project reward and cost
  • The code is provided anonymously, which is very nice.
Critical weaknesses
  • My main concern might be a misunderstanding, but it looks like the safety margin used differed between the proposed algorithm and the baselines. If you use a more restrictive safety margin, of cousre it will have safer results. Please reassure me that you are comparing apples to apples.

some other points claude pointed out that I thought were relevant:

  • The training budgets are very short. Velocity tasks run 32k steps and navigation tasks 20k (Table 3). Safety Gymnasium experiments typically run for hundreds of thousands to millions of steps. At this scale, agents have barely started learning; the Ant returns in Fig. 4 are negative, for example. In velocity tasks, cost comes from moving too fast, so near-zero cost early in training may just mean the agent hasn’t learned to move. This also means the convergence claims (Theorem 3, “asymptotically approaches the optimal policy”) are untested.
  • The implemented sampler is not the variance-optimal sampler. Theorem 1’s minimizer is q*(i) ∝ b(i)ρᵢ. The implemented sampler (Eq. 6, Proposition 2) is q_ε(i) ∝ b(i)exp(ρᵢ/η). Proposition 2 derives it from a different objective: maximizing the linear score Σq(i)ρᵢ under a KL constraint, not minimizing variance. The appendix even admits the KL-constrained variance problem has no closed form. The main text then states that “a small η gives the minimum-variance sampling distribution,” but the paper’s own appendix says that as η → 0, q_ε concentrates on argmax ρᵢ (greedy prioritization), which is not q*. In addition, the implementation standardizes ρᵢ within the pool and clips scores by MAD. So Theorems 1–2 and Corollary 1 describe a sampler that isn’t the one run in the experiments. Corollary 1 is stated for a = q_ε, but its proof uses Theorem 2’s result for q. -Theorem 2’s key step is asserted, not proven. The “flip” event is defined as the estimated gradients leaving the region R*. The bound then assumes a flip happens only if Zᶜ ≤ 0 or Zʳ ≤ 0. For CRPO, though, the branch is chosen by whether the estimated cost exceeds the budget, not by the sign of a gradient projection. The paper never shows these events are related.
Questions for authors

highest priority:

  • Why is the safety margin 0.15-0.8 for VOSR (table 5), but the safety margin is 25 for the baselines? Am I misreading that? If so, of course VOSR is safer. Can you please rerun the baselines with identical optimizer settings (margin, multiplier rate, cap), or rerun VOSR with the baselines’ settings?
  • Can you please reconcile the issue between the variance-optimal sampler and the sampler used in practice?
  • can you provide a talbe of final return, cost, and violation per environment?

Medium priority:

  • Why are the multiplier rates so different (e.g. 0.01 vs 0.0001?) and the multiplier cap (none for baseline, 30 for VOSR)? Again let's try to keep them the same if possible for comparison.
  • Can you rerun for longer training horizons?
  • Why do some of the plots seem to show VOSR's return being lower (e.g. Point button 1)?

Low priority:

  • Include hopper in section 5's setup
  • why does table 1 have only 8 environments?
  • in figure 5, why is kappa = 1.5 (used in paper) but then in the paper it is not?
4 comments

Question 1: Different safety margins for VOSR and the baselines

Response. We thank the reviewer for pointing this out. The earlier comparison did use different optimizer settings for VOSR and the baselines, and we have now corrected this by using identical settings for all five samplers. Setting S1 gives every sampler the former baseline settings, namely a safety margin of 1.0, a multiplier rate of 10−210^{-2}, and no multiplier cap. Setting S2 gives every sampler the former VOSR settings, namely the tighter margins, a multiplier rate of 10−410^{-4}, and a multiplier cap of 30. The settings are listed in Table 5 in Appendix A.2, and the results are reported in Tables 15–23 in Appendix A.4. Under both settings, VOSR has the lowest violation fraction in every environment–optimizer pair. It also has the lowest final cost in every pair except Walker2d with CRPO under S2, where all samplers stay far below the budget. For viewing Table 5 and Tables 15–23, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.2 (Table 5) and Appendix A.4 (Tables 15–23) of the paper.

Question 2: Reconciling the variance-optimal sampler with the deployed sampler

Response. We have now clearly separated the exact theoretical sampler from the sampler used in practice. Theorem 1 gives the exact closed-form sampler q⋆q^\star, which minimizes the variance. Equation (6) and Proposition 2 give the tempered sampler qϵ⋆q_\epsilon^\star, which solves a different objective that favours high-score transitions while a KL constraint keeps it close to uniform replay. The deployed VOSR sampler uses this tempered form, with scores that are estimated, MAD-clipped, and standardized within a candidate pool. Section 4.2 and Appendix A.1.4 explain these differences. Table 8 in Appendix A.3 compares all three samplers on the same data and shows that the deployed sampler keeps most of the variance reduction of q⋆q^\star while using a more diverse set of transitions. Table 2 in Appendix A.1 states which theoretical claims hold for the deployed sampler. For viewing Table 2 and Table 8, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.1 (Table 2) and Appendix A.3 (Table 8) of the paper.

Question 3: Per-environment table of final return, cost and violation

Response. We have added complete per-environment results, with the final return, final cost, and training violation fraction, each given as the mean and 95% confidence interval over five seeds. Tables 15–20 in Appendix A.4 cover all eleven environments and three optimizers under Setting S1, and Tables 21–23 cover the same environments under Setting S2. For viewing Tables 15–23, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.4 of the paper.

Question 4: Different multiplier rates and multiplier caps

Response. We agree, and the multiplier settings are now identical for all samplers within each comparison. In Setting S1, every sampler uses a multiplier rate of 10−210^{-2} without a cap. In Setting S2, every sampler uses a multiplier rate of 10−410^{-4} with a cap of 30. Table 5 in Appendix A.2 lists these settings, and Tables 15–23 in Appendix A.4 give the corresponding results. For viewing Table 5 and Tables 15–23, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.2 (Table 5) and Appendix A.4 (Tables 15–23) of the paper.

Question 5: Longer training horizons

Response. Yes. We have increased training from 20,000–32,000 steps to 3 million steps for every environment, sampler, and optimizer, in both Setting S1 and Setting S2. Table 4 in Appendix A.2 lists the training budgets and is reproduced at the end of this response. Since VOSR takes more time per step, we also added an equal-wall-clock comparison in Table 14, where each baseline is trained for the same time as VOSR and therefore reaches 4.6–5.9 million steps. Even with these extra steps, VOSR keeps the highest return and the lowest cost. The final results are in Tables 15–23 in Appendix A.4. For viewing Table 4, Table 14 and Tables 15–23, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.2 (Table 4), Appendix A.3 (Table 14) and Appendix A.4 (Tables 15–23) of the paper.

Question 6: Lower VOSR return in some plots such as PointButton1

Response. The earlier plots came from short training runs with different optimizer settings for VOSR and the baselines. We have rerun all experiments for 3 million steps with the same optimizer settings for every sampler. With this longer training, VOSR reaches the highest return on PointButton1 under all three optimizers, at 0.6±0.10.6\pm0.1 with SAC-Lagrangian, 1.1±0.11.1\pm0.1 with CRPO, and 0.7±0.10.7\pm0.1 with PCRPO. It also keeps the lowest cost and violation fraction. The updated learning curves are shown in Figure 3, and the final values are given in Tables 18, 19, and 20 in Appendix A.4. These tables can be viewed at the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md, so the return can be read together with the cost and violation fraction.

Question 7: Including Hopper in the Section 5 setup, Only eight environments in Table 1, Inconsistent value of kappa in Figure 5

Response. Thank you for noticing this issue. We have added Hopper to the list of velocity environments in Section 5, under “Setup.”

Table 1 now includes all eleven environments, matching Section 5 and Tables 15–20. It also includes a new last row with the average training violation fraction of each sampler.

All reported VOSR runs use κ=1.5\kappa=1.5 and η=1.0\eta=1.0, in every environment and for every optimizer, and the paper now states this consistently. In Figure 5, the η\eta ablation is run with κ=1.5\kappa=1.5, the κ\kappa ablation is run with η=1.0\eta=1.0, and the default values are marked with ∗^\ast.

The required tables related to these are provided in the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md.

Other Comments: Connection between the CRPO/PCRPO branch conditions and the sign events

Response. Regarding the connection between the CRPO/PCRPO branch conditions and the sign events, we agree that the earlier proof missed a case. CRPO and PCRPO select their branch by comparing J^c\hat J_c with dd, so a wrong branch can occur even when both Zˉc\bar Z^c and Zˉr\bar Z^r are positive. We have corrected this by defining R⋆R^\star as the region where both the branch and update direction are correct. The correct branch requires J^c\hat J_c and the true cost to lie on the same side of dd (gradients lie inside R⋆R^\star), while the correct policy update direction requires Zˉc>0\bar Z^c>0 for a cost step or Zˉr>0\bar Z^r>0 for a reward step. Thus, a flip occurs through either a wrong branch or a wrong direction, giving P(flip)≤P(wrong branch)+P(Zˉc≤0)+P(Zˉr≤0)P(\text{flip})\le P(\text{wrong branch})+P(\bar Z^c\le0)+P(\bar Z^r\le0). Theorem 2(b) bounds the wrong-branch probability, which depends only on J^c\hat J_c estimated from training episodes and is the same for all samplers. Theorem 2(c) bounds the wrong-direction probabilities using gradient variances, which VOSR reduces. Table 10 confirms this, showing that VOSR reduces the wrong-direction rate from about 0.30 with Uniform Replay to about 0.20 across all three optimizers.

For viewing Table 10, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. Table 10 is presented in Appendix A.3 of the paper.

Reviewer_ckPBOpenReview ↗

Post Rebuttal Comment

Thank you for the thorough rebuttal and the substantial new experiments, which directly address my main concern. I am happy to raise my score. Below I go through my original questions in order and note what remains open.

Highest priority

  1. Different safety margins between VOSR and the baselines. Thank you for confirming the discrepancy and rerunning all five samplers under two matched settings. I think the S1 results should be integrated into the main paper. The main-text figures and Table 1 should reflect the matched comparison. The rebuttal reports a training violation fraction of 0.042 for VOSR versus 0.352–0.386 for the other samplers. The original submission reported 0.080 versus roughly 0.105. This is now a roughly ninefold gap. Yet the proposed mechanism, as measured in Table 10, is a reduction in wrong-direction updates from about 0.30 to about 0.20. Could you explain how a one-third reduction in wrong-direction updates leads to a roughly ninefold reduction in violations?

  2. Reconciling the variance-optimal sampler with the deployed sampler. Thank you for separating the exact sampler q*, the tempered sampler, and the deployed sampler, and for the comparison in Table 8 and the summary of claims in Table 2. This resolves my question. Please make sure the abstract and introduction are scoped to match. Phrases such as “achieves the minimum possible variance” and “asymptotically approaches the optimal policy” describe the idealized analysis, not the deployed method.

  3. Per-environment results table. Thank you for adding complete per-environment results with confidence intervals!

Medium priority

  1. Multiplier rates and cap. Resolved by the matched S1/S2 settings.

  2. Longer training horizons. Thank you for extending training to 3M steps and for adding the equal-wall-clock comparison!

  3. Lower VOSR return on PointButton1. Resolved.

Low priority

  1. Hopper in Section 5. Resolved.

  2. Table 1 covering only 8 environments. Resolved.

  3. The κ value. Thank you for the clarification that all VOSR runs use κ = 1.5 and η = 1.0. However, the original appendix (Table 5) listed per-tier κ values of 0.15, 0.35, and 0.70. Could you confirm which κ values were used in the experiments of the original submission? Is κ = 1.5 a change made for the rerun, or did the original appendix misdescribe the experiments?

HIGHEST PRIORITY

Response to Question1: We agree with the reviewer regarding the matched S1 results and have included them as the main results in the submitted revised paper. Figs. 3–4, Table 1, and Tables 15–20 all use Setting S1, where all samplers have the same safety margin, multiplier learning rate, and multiplier cap (Sec. 5 and Table 7).

The new results (0.042 vs. 0.352–0.386) cannot be directly compared with the original results (0.080 vs. about 0.105) for three reasons. First, the revised paper measures the fraction of training episodes whose cost exceeds d=25d=25, while the original paper measured the fraction of training steps with violations (Appendix A.2). We made this change because this is the setting used by the baselines, and counting such episodes directly measures violations of the CMDP cost constraint Jc≤dJ_c \le d (Sec. 3 and Appendix A.2). Second, the revised Table 1 reports the average training violation fraction across all 11 environments and three optimizers, while the original submission included only 8 environments. The three added environments are PointGoal2, CarButton1, and CarGoal1, which are among the hardest tasks for the baselines. Third, each run now uses 3×1063\times10^6 training steps instead of 32k/20k.

VOSR reduces the variance of the cost and reward gradient estimates. Theorem 2(c) bounds the probability of a wrong-direction update by this variance reduction, so lower variance lowers the bound. To achieve this, VOSR first samples transitions according to their cost and reward gradient scores, which measure each transition's contribution towards cost reduction and reward increase along a direction where they do not conflict (Sec. 4.2). As a result, VOSR has the lowest measured cost-gradient variance (Table 1) and the lowest wrong-direction update rate (Table 10). With fewer wrong-direction updates, more cost updates are aligned with the true cost gradient, so the cost eventually decreases during training and violations become less frequent. The reduction in wrong-direction updates and the reduction in violations are therefore related, but we have not quantified their exact relation, as it varies across environments and their minibatch samples.

Response to Question 2: We agree with the reviewer. Both phrases appeared in the original abstract and have now been removed. The abstract in the revised submitted version states that we "derive in closed form the replay sampling strategy that minimizes this variance, and we deploy a smoothed trust-region version of it in practice." It also clarifies that the optimizer's stationary points remain unchanged only "in the idealized setting with exact gradients." Similarly, Contribution 1 in Sec. 1 states that we use a tempered version of the sampler. Sec. 4.2 (after Eq. 6) clarifies that the deployed sampler "is a surrogate, not the exact q⋆q^\star". The Conclusion also makes this distinction clear.

LOW PRIORITY

Response to question 9: The value κ=1.5\kappa=1.5 was introduced in the revised experiments. In the original submission, the main VOSR experiments used different κ\kappa values for different environments, as reported in the original Table 5. Specifically, κ=0.15\kappa=0.15 was used for PointButton1, PointPush1, PointGoal2, CarButton1, CarGoal1, and Swimmer, κ=0.35\kappa=0.35 for Ant and HalfCheetah, and κ=0.70\kappa=0.70 for Hopper, Humanoid, and Walker2d. All experiments used η=1.0\eta=1.0. The statement in the original Sec. 5 that κ=1.5\kappa=1.5 provides a good balance referred only to the ablation experiments. We apologize for this confusion. In the revised paper, we removed the environment-specific tuning. All VOSR experiments now use κ=1.5\kappa=1.5 and η=1.0\eta=1.0 across all environments and optimizers (Table 6).

Reviewer_iBFuOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper treats the replay sampling distribution in off-policy safe RL as a control variable. Transitions are reweighted by b(i)/q(i) together with a state-visitation and action likelihood-ratio correction. The paper argues that, under exact importance weighting, the reward and cost gradient estimators have expectations independent of the replay sampler q (Lemma 1). It then defines scalar projections of per-sample cost and reward gradients and derives the standard variance-minimizing importance-sampling proposal q(i)∝b(i) √((s_i^c )^2+κ(s_i^r )^2 ) For practical use, it instead deploys a KL-regularized softmax sampler. The paper further bounds an update-deviation quantity through a proposed “branch-flip” probability, and integrates the method with SAC-Lagrangian, CRPO, and PCRPO on Safety Gymnasium tasks.

Critical strengths

The central framing is clean and potentially useful: replay prioritization for safe RL should consider both reward and cost information, and, ideally, should reduce estimator variance without changing the target constrained problem. The optimizer-agnostic formulation is appealing, and comparing with Uniform Replay, TD-PER, Safety-PER, and Uncertainty-PER is appropriate. The paper also makes a useful distinction between reward-related and safety-related gradient information.

Critical weaknesses

The empirical comparison does not isolate the effect of the sampler The main empirical claim is that VOSR improves safety without sacrificing return. However, the appendix changes more than the replay sampler. In Tables 4 and 5, VOSR uses environment-tier-specific safety margins of 0.15, 0.5, or 0.8, whereas all baselines use margin 1.0. Since the effective budget is d_eff=d∙margin, a margin of 0.15 changes the training budget from 25 to 3.75. This alone could plausibly explain why VOSR drives costs close to zero and has fewer violations of the evaluation budget of 25. For SAC-Lagrangian, VOSR also uses a different multiplier learning rate (10^(-4) rather than 10^(-2) and a multiplier cap of 30, while baselines have no cap. These optimizer-level changes are substantial confounders. The reported gains therefore cannot be attributed specifically to variance-optimal replay sampling. The training budgets are also short for several tasks, especially Humanoid, and the paper provides only selected “showcase” curves rather than a complete table of results across all environments and all base optimizers. There are also inconsistencies in the listed environment sets: Section 5, Table 1, and the appendix do not appear to report the same collection or count of environments. Because the practical benefit is the paper’s main evidence of relevance, this issue is central rather than cosmetic.

  1. The variance-optimality guarantee does not apply to the deployed method Theorem 1 derives the classical optimal importance-sampling proposal for a fixed variance objective. This result is mathematically correct but closely follows standard variance-optimal importance sampling arguments, including work cited by the paper such as Katharopoulos and Fleuret (2018). The potential novelty is its safe-RL-specific choice of projected reward and cost scores, rather than the optimization result itself. More importantly, the deployed method is not the minimizer from Theorem 1. Proposition 2 explicitly replaces the original variance-minimization problem with a different linear priority-maximization objective under a KL constraint, yielding q_ε (i)∝b(i)exp(ρ_i/η) The appendix states that the KL-constrained version of the original variance objective has no closed-form solution. Thus, the practical softmax sampler should be presented as a heuristic or surrogate motivated by the variance objective, not as the variance-optimal solution itself. The implementation additionally performs score standardization within the candidate pool and MAD clipping, neither of which is covered by Theorem 1. There is also a mismatch between theory and implementation because the scores depend on g_c, g_r, and g_r^+, which are themselves estimated from a candidate minibatch. The analysis treats these quantities and the sampling proposal as fixed, while the implementation constructs a data-dependent proposal using the replay data. It is unclear whether the stated importance-sampling properties continue to hold under this adaptive procedure.

  2. The unbiasedness and stationary-set claims do not hold as stated for the implemented algorithm Lemma 1 relies on exact state-visitation and action-ratio importance weights. In the implementation, the combined weight is clipped to [0.1,10] and the critics are learned approximations. Clipping an importance ratio generally introduces bias. Therefore, the implemented gradient estimator is not guaranteed to be unbiased, and the paper cannot directly use Lemma 1 to conclude that the implemented algorithm preserves the same KKT stationary set as the base optimizer. A more limited claim could be defensible: under exact, unclipped density ratios and exact critic quantities, changing q does not change the first moment of the individual reward and cost gradient estimators. But this is weaker than the paper’s claim that replay prioritization “can never shift the CMDP solution.” For piecewise or nonlinear optimizers, unbiased component gradients do not imply an unbiased policy update: Ε[F(g ̂_r,g ̂_c )]≠F[Ε(g ̂_r ),Ε(g ̂_c )] in general. Indeed, the paper’s own Theorem 2 studies how sampling variance changes the expected realized update through branch changes. Thus, even in the idealized unclipped setting, the sampler may change finite-sample expected updates and learning dynamics. The distinction between preserving the exact-gradient stationary set and preserving the behavior of the stochastic implemented algorithm needs to be made explicit.

  3. The proposed branch-flip analysis is not clearly connected to CRPO/PCRPO decisions Theorem 2 bounds a “flip” event through the signs of Z_c and Z_r, which are projections onto the cost-gradient and conflict-free reward-gradient directions. However, CRPO’s branch selection depends on whether the estimated constraint is satisfied relative to the budget, e.g., J ̂_c versus d, not simply on the signs of these projected gradient estimators. It is therefore not clear that a wrong CRPO/PCRPO branch implies Z_c≤0 or Z_r≤0, or conversely. The paper needs a formal connection between the actual optimizer switching condition and the proposed sign-test events. Without it, the claimed bound on wrong optimizer branches and per-step safety is not established for the algorithms evaluated.

Questions for authors

Please report VOSR with exactly the same base-optimizer settings as the baselines: margin 1.0, identical multiplier learning rate, and identical multiplier cap. Conversely, please report the baselines under the VOSR optimizer settings. This is necessary to identify the contribution of the sampler. Please provide a complete table of final return, final cost, violation fraction, and uncertainty statistics for every environment and each of the three base optimizers. Longer training budgets would also help assess asymptotic behavior. Is the variance reported in Table 1 measured using the exact deployed procedure, including clipped importance weights, learned β, candidate-pool score estimation, MAD clipping, and the softmax sampler? Please specify the estimator and evaluation protocol. How are the per-sample scores s_i^c and s_i^r computed efficiently? Do they require per-sample actor gradients over a candidate pool? Please report wall-clock, memory, and update-frequency overhead relative to Uniform Replay. Can the authors quantify the bias introduced by importance-weight clipping and learned state-visitation ratios? Which theoretical claims remain valid under these approximations? Can the authors formally connect the actual CRPO/PCRPO branch conditions to the sign events Z_c≤0 or Z_r≤0? What is the precise novelty of Theorem 1 relative to prior variance-optimal importance sampling for stochastic gradient methods? The safe-RL score construction may be novel, but the theorem itself appears to be a direct specialization of a known result.

5 comments

Question 1: Matched base-optimizer settings for VOSR and the baselines

Response. We have rerun the comparisons using the same optimizer settings for all five samplers (Uniform Replay, Safety-PER, TD-PER, Uncertainty-PER, and VOSR). In Setting S1, which uses the baseline optimizer settings, all samplers use a safety margin of 1.0, a multiplier learning rate of 10−210^{-2}, and no multiplier cap. In Setting S2, which uses the VOSR optimizer settings, all samplers use tighter safety margins, a multiplier learning rate of 10−410^{-4}, and a multiplier cap of 30. Table 5 in Appendix A.2 of the paper provides these settings (also provided in this response). The results are reported in Tables 15–20 for S1 and Tables 21–23 for S2. Under Setting S1, VOSR achieves the lowest cost and violation fraction. Under Setting S2, VOSR achieves the lowest violation fraction and the lowest final cost in most cases. The only cost exception is Walker2d under CRPO, where all samplers remain below the safety budget.

For viewing Table 5 and Tables 15–23, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.2 (Table 5) and Appendix A.4 (Tables 15–23) of the paper.

Question 2: Complete per-environment results and longer training budgets

Response. We have added complete results for all eleven environments, three optimizers, and five samplers. Tables 15–17 in Appendix A.4 show the velocity tasks, and Tables 18–20 show the navigation tasks under the S1 setting. Tables 21–23 provide the additional results for the S2 setting for all eleven environments. Each result includes return, cost, and violation fraction with a 95% confidence interval over five seeds. We have also increased training from 30 thousand to 3 million steps per environment, with the results for 3 million steps shown in Table 4 of Appendix A.2. Throughout these experiments, we have observed that VOSR achieves the lowest cost and violation fraction in all environments under Setting S1. Under Setting S2, VOSR achieves the lowest violation fraction in all environments and the lowest cost in most environments. Therefore, the safety improvement is primarily due to the proposed sampler rather than the lower safety budget. We have also included all the relevant tables in this response.

For viewing Table 4 and Tables 15–23, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.2 (Table 4) and Appendix A.4 (Tables 15–23) of the paper.

Question 3 : Whether the Table 1 variance uses the exact deployed procedure

Response. Yes. The variance in Table 1 is measured using the complete VOSR procedure, including clipped importance weights, the learned state ratio β\beta, candidate-pool scores, Median Absolute Deviation (MAD) clipping, and softmax sampling.

We measure the variance at four training checkpoints (25%25\%, 50%50\%, 75%75\%, and 100%100\%), corresponding to 0.750.75, 1.51.5, 2.252.25, and 33 million environment steps. At each checkpoint, we freeze the policy, both critics, and β\beta. We then use 20,00020{,}000 uniformly sampled replay transitions to compute reference cost and reward gradients with the same clipped weights used during training. These give the unit cost direction g~c\tilde g_c and the unit conflict-free reward direction g~r+\tilde g_r^{+}. For each sampler, we repeat the sampling process 100100 times. Each repetition uses a fresh candidate pool of 512512 transitions, applies scoring, MAD clipping, and softmax sampling, and selects a minibatch of 256256 transitions. We compute the cost projection Zˉc=⟨g^c,g~c⟩\bar Z^c=\langle\hat g_c,\tilde g_c\rangle and reward projection Zˉr=⟨g^r,g~r+⟩\bar Z^r=\langle\hat g_r,\tilde g_r^{+}\rangle for each minibatch.

We calculate the sample variance of Zˉc\bar Z^c across the 100100 repetitions. The results are averaged over 100 repetitions, four checkpoints, five seeds, and three optimizers. The values in Table 1 represent the variance of different samplers relative to that of the uniform sampler. Values below 1.001.00 indicate lower cost-gradient variance than Uniform Replay. Table 1 in the paper reports the results for all environments. Table 8 in the paper compares the exact sampler q⋆q^\star (Theorem 1), the sampler qϵ⋆q_\epsilon^\star based on a KL constraint (Eq. (6), Proposition 2), referred to as the tempered sampler, and the deployed sampler (Eq. (6), using MAD-clipped and pool-standardized scores). The table is also provided in this response. All three samplers are evaluated using the same checkpoints and candidate pools. For each sampler, Table 8 reports the variance of the cost and reward estimates relative to Uniform Replay (Var(Zˉc)\mathrm{Var}(\bar Z^c), Var(Zˉr)\mathrm{Var}(\bar Z^r)), the distance from uniform replay (KL(q∥b)\mathrm{KL}(q\Vert b)), and the replay diversity (ESS/∣P∣\mathrm{ESS}/|\mathcal{P}|, the effective sample size as a fraction of the pool size P\mathcal{P}). The exact sampler has the lowest variance (Var(Zˉc)=0.32\mathrm{Var}(\bar Z^c)=0.32) but the least diversity (ESS/∣P∣=0.43\mathrm{ESS}/|\mathcal{P}|=0.43), whereas the deployed sampler maintains the variance reduction (Var(Zˉc)=0.52\mathrm{Var}(\bar Z^c)=0.52) with higher diversity (ESS/∣P∣=0.69\mathrm{ESS}/|\mathcal{P}|=0.69).

Note that Table 8 and Table 13 measure Var(Zˉc)\mathrm{Var}(\bar Z^c) differently. Table 8 swaps only the sampling distribution at the same frozen checkpoints of the main VOSR runs, a one-step comparison on identical data, whereas the "Sampler form" rows of Table 13 come from separate runs trained with each sampler from the start, so their variance also reflects how that sampler changes the learned policy and critics. This is why the raw tempered sampler and q⋆q^\star look better in Table 8 (0.460.46 and 0.320.32) than in Table 13 (0.820.82 and 0.940.94).

For viewing Table 1 and Table 8, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in the main text (Table 1) and Appendix A.3 (Table 8) of the paper.

Question 4: Efficient computation of per-sample scores and the resulting overhead

Response. VOSR computes two scalar scores, sics_i^c and sirs_i^r, for each transition and combines them into a single priority ζi\zeta_i, without storing separate actor-gradient vectors. The cost score is computed as sic=wiQc(si,ai)⟨∇θlog⁡πθ(ai∣si),g~c⟩s_i^c = w_i Q_c(s_i,a_i)\langle\nabla_\theta\log\pi_\theta(a_i\mid s_i),\tilde g_c\rangle, where the inner product measures how the log-policy changes along the fixed cost-gradient direction g~c\tilde g_c. This allows the scores of all 512 candidate transitions to be computed together without storing individual gradient vectors. The reward score sirs_i^r is computed similarly using the conflict-free reward direction g~r+\tilde g_r^{+}.

Concretely, ⟨∇θlog⁡πθ(ai∣si),g~c⟩\langle\nabla_\theta\log\pi_\theta(a_i\mid s_i),\tilde g_c\rangle is the directional derivative of log⁡πθ(ai∣si)\log\pi_\theta(a_i\mid s_i) along the fixed direction g~c\tilde g_c, so it is obtained for all 512512 candidates at once with a single batched forward-mode Jacobian-vector product of the actor, and likewise for g~r+\tilde g_r^{+}, with no per-sample backward passes. These products are included in the extra passes per update reported in Table 11.

Both reference directions (g~c\tilde g_c and g~r+\tilde g_r^{+}) are computed once per update from a separate batch of 256 transitions drawn from the replay buffer. We first estimate the mean reward and cost gradients grg_r and gcg_c, then remove the component of grg_r along gcg_c to obtain the conflict-free reward gradient gr+g_r^{+}. We normalize gcg_c and gr+g_r^{+} to obtain the unit directions g~c\tilde g_c and g~r+\tilde g_r^{+}. Using a separate reference batch ensures that the candidate transitions are scored using directions estimated independently of them.

Table 11 in Appendix A.3 reports that VOSR requires 9191–96%96\% more wall-clock time per step and approximately 0.340.34–0.380.38 GB of additional GPU memory compared with Uniform Replay, mainly due to candidate-pool scoring. Table 12 reports GPU hours for each environment. All samplers use the same update frequency of one update every four environment steps (Table 3), while Table 14 compares their performance under equal wall-clock time. The results show that although the other samplers complete more training steps than VOSR within the same time, VOSR achieves higher returns and lower costs than the other samplers. The required tables are also provided with this response.

For viewing Table 3, Table 11, Table 12 and Table 14, kindly visit the link https://anonymous.4open.science/r/variance-optimal-replay-0606/README.md. These tables are presented in Appendix A.2 (Table 3) and Appendix A.3 (Table 11, Table 12 and Table 14) of the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.