Efficient Policy Evaluation with Safety Constraint for Reinforcement Learning
Authors: Claire Chen
Shuze Liu
Shangtong Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: Reinforcement Learning
Primary area: reinforcement learning

Abstract: In reinforcement learning, classic on-policy evaluation methods often suffer from high variance and require massive online data to attain the desired accuracy. Previous studies attempt to reduce evaluation variance by searching for or designing proper behavior policies to collect data. However, these approaches ignore the safety of such behavior policies---the designed behavior policies have no safety guarantee and may lead to severe damage during online executions. In this paper, to address the challenge of reducing variance while ensuring safety simultaneously, we propose an optimal variance-minimizing behavior policy under safety constraints. Theoretically, while ensuring safety constraints, our evaluation method is unbiased and has lower variance than on-policy evaluation. Empirically, our method is the only existing method to achieve both substantial variance reduction and safety constraint satisfaction. Furthermore, we show our method is even superior to previous methods in both variance reduction and execution safety.

Published as a conference paper at ICLR 2025
EFFICIENT OFF-POLICY EVALUATION WITH SAFETY CONSTRAINT FOR REINFORCEMENT LEARNING
Claire Chen"
Shuze Daniel Liu" Department of Computer Science University of Virginia shuzel wwwiviiiiinniii edu
School Arts and Science University of Virginia
clai rechen@ema wtt.://mmaww..iiiiiiaa.....
Shangtong Zhang
Department of Computer Science
University of Virginia shangtoong@virgin edu
ABSTRACT
In reinforcement learning, classic on-policy evaluation methods often suffer from high variance and require massive online data attain the desired accuracy. Pre- vious studies attempt to reduce evaluation variance by searching for or designing proper behavior policies collect data. However, these approaches ignore the safety of such behavior policies-the the designed behavior policies have no safety guarantee and may lead to severe damage during online executions. this paper, to address the challenge of reducing variance while ensuring safety simultane- ously, we propose an optimal variance-minimizing behavior policy under safety constraints. Theoretically, while ensuring safety constraints, evaluation method is unbiased and has lower variance than on-policy evaluation. Empirically, our method is the only existing method achieve both substantial variance reduc- tion and safety constraint satisfaction. Furthermore, we show our method is even superior previous methods in both variance reduction and execution safety.
INTRODUCTION
Recently, reinforcement learning (RL,, Sutton and Barto (2018)) has shown exceptional success in various sequential decision-making problems. For instance, the applications of RI algorithms have reduced energy consumption for Google's 's data center's cooling by 40% (Chervonyi et al., 2022), solved Olympiad-level geometry problems (Trinh et al., 2024), and designed general-purpose data center CPUs (Mirhoseini et al., 2021). In RL applications, policy evaluation enables RL practitioners estimate the performance of policy before committing its full deployment. In policy evaluation, conventional wisdom uses the on- on-policy method, in which a policy (i.e., the target policy) is evaluated by directly executing itself. However, this straightforward approach is crude since using the target policy itself as the data-collecting policy (i.e., the behavior policy) is proved to be suboptimal (Liu and Zhang, 2024; Liu al., 2024a;c), resulting evaluations with potentially high variance. Thus, the on-policy evaluation method may require massive online data achieve the desired accuracy.
Unfortunately, collecting massive online data in real-world interaction can be both expensive and slow (Li, 2019; Zhang, 2023). In Google's data center's cooling system, each interaction step in the actual deployment takes minutes (Chervonyi et al., 2022). Thus, the evaluation of a policy requiring millions of steps is prohibitively expensive. To reduce the reliance on costly online data collection, offline RL has been introduced as a possible solution. However, mismatches between the offline data distribution and the distribution induced by the target policy frequently arise, resulting in bias that is both uncontrolled and difficult to eliminate (Jiang and Li, 2016; Farahmand and Szepesvári, 201 1; Marivate, 2015). As a result, both online and offline RL practitioners still depend heavily on online policy evaluation techniques (Kalashnikov et al., 2018; Vinyals et al., 2019).
"Equal Contribution.

---

Published as a conference paper at ICLR 2025
To improve the online sample efficiency for policy evaluation, existing methods propose to reduce the evaluation variance by searching for or designing proper behavior policies (Hanna et al., 2017; Zhong et al., 2022; Liu and Zhang, 2024). However, all their approaches ignore critical issue: safety. In many real-world applications, neglecting safety in policy execution can result in serious consequences. For example, in Google's s data center cooling system, behavior policy that is tailored for variance reduction without considering safety constraints may unpredictably overheat the system, causing equipment damages or service disruptions. Therefore, besides reducing evaluation variance. it is crucial to guarantee execution safety.
In this paper, we address the challenge of reducing variance while ensuring safety simultaneously. We make the following contributions:
1. We propose an optimal variance-minimizingg behavior policy under safety constraints.
2. Theoretically, we show that our method gives an unbiased estimation. In addition to strictly satisfying the safety constraints, our method is proven attain lower variance than the classic on-policy evaluation method.
3. Empirically, we show that our method is the only existing method to achieve both substantial variance reduction and constraint satisfaction. Moreover, it is even superior to previous methods in both variance reduction and execution safety.
2 RELATED WORK
Safe RL. Safety in reinforcement learning, often framed as safe RL (Garcia and Fernández, 2015), has been an active research topic recently. Many recent works focus on safety in policy exploration and optimization (Brunke et al., 2022). For safe exploration, Moldovan and Abbeel (2012) present a method for ensuring safe exploration by keeping the agent within a predefined set of safe states during its learning process. However, their method is model-based approach, requiring explicit approximation of the transition function, which introduces challenges common to model learning, such compounding errors and the need for accurate model dynamics (Sutton, 1990; Sutton et al., 2008; Deisenroth and Rasmussen, 2011; Chua et al., 2018). In contrast, our approach does not rely on approximating the transition function (i.e., model-free), since parameters can be estimated by off-the-shelf offline policy evaluation methods (e.g. Fitted Q- Q-Evaluation, Le et al. (2019)). As for safe optimization, Berkenkamp al. (2017) propose ensure safety by keeping the agent within safe regions, which are characterized by Lyapunov function. However, they assume the environment to be deterministic, i.e., p(s'| ss a) for the successive state s', which is a significant limitation as most MDPs are stochastic. Their method is also model-based, requiring knowledge of the transition functions. In contrast, our approach copes well with stochastic environments and is model-free.
Safe reinforcement learning is often modeled as Constrained Markov Decision Process (CMDP) (Gu et al., 2022; Wachi et al., 2024; Liu et al., 2021), in which we need to maximize the agent reward while making agents satisfy safety constraints. Achiam al. (2017) enforce constant threshold to constrain the expected total cost. However, even though they adopt the trust-region method control policy updates, the expected total cost of the new policy can still exceed the safety threshold at each update step, leading to uncontrolled violations of the safety constraints over time. In contrast, our method inherently integrates safety constraints into the policy design, ensuring strict satisfaction of constraints throughout execution. Wachi and Sui (2020) propose method for safe reinforcement learning in constrained Markov decision processes (CMDPs) by using a Gaussian Process to model the safety constraints and guide exploration. Nevertheless, their approach needs to compute the covariance matrix between explored states throughout the execution, which is computationally expensive, especially in environments with large state spaces. In addition, they assume that the state transitions are deterministic, making their method highly restricted. In contrast, our algorithm does not rely on knowledge about the complicated covariances and copes with stochastic environments.
Variance Reduction. Variance reduction for policy evaluation in reinforcement learning (RL) is also widely explored. Since using the target policy as the data- colleccon policy (i.e., the behavior policy) for evaluating itself is not optimal (Owen, 2013). some recent studies focus searching for or designing a data-reducing behavior policy without considering safety. Hanna et al. (2017) formulate the task of searching for veriaice-reduction behavior policy optimization problem. They
2

---

Published as a conference paper at ICLR 2025
parameterize the behavior policy and use stochastic gradient descent to update the policy. However, in reinforcement learning, the stochastic method has been known to easily get stuck in highly suboptimal points in just moderately complex environments (Williams, 1992), where various local optimal and saddle points exist. Besides, they do not consider the safety of their obtained behavior policy, which might cause damage during execution. In contrast, our method directly learns the globally optimal behavior policy with safety guarantees. Moreover, to learn the behavior policy effectively, their method requires highly sensitive hyperparameter tuning, where the learning rate can vary by up to 10 times across different environments, as reported by Hanna et al. (2017). This sensitivity requires online tuning, which consumes online data. In contrast, we introduce an efficient algorithm learn our behavior policy with purely offline data. Furthermore, their methods need the online data to be complete trajectories. In contrust, our algorithm copes well with incomplete offline tuples, making it widely applicable.
Zhong et al. (2022) also design a pariance-reducing behavior policy for policy evaluation. They adjust the behavior policy to focus under-sampled data segments. However, their method requires the offline data to be in complete trajectories, and the data must be generated by known behavior policies that are highly similar to the target policy. These assumptions are strong. In contrast, our method effectively handles incomplete offline segments from potentially unknown and diverse behavior policies. Zhong et al. (2022) also ignore safety constraints in their behavior policy, leading to potential risks in executing the data-collecting behavior policy. In contrast, our method incorporates safety constraints into the search for the optimal variance-reducing behavior policy, ensuring safety throughout the execution.
Using the per-decision importance sampling estimator, Mukherjee et al. (2022) also propose a behavior policy to reduce variance. Nevertheless, they also do not consider the crucial safety problem. Besides, their results are restricted tree- rre-struct MDPs, which is a significant limitation. In contrast, our method is applicable on general CMDPs, extensions of the widely studied MDPs. Moreover, Mukherjee et al. (2022) also leverage a model-based approach. The current best method in behavior policy design is proposed by Liu and Zhang (2024), where they find an optimal and an lealial-lerrnalee behavior policy. However, all these approaches (Hanna et al., 2017: Zhong et al., 2022; Liu and Zhang, 2024) focus solely on reducing evaluation variance while neglecting critical issue: safety. Without integrating safety constraints into the design of the behavior policy, its online execution could cause unforeseen and severe damage. In contrast, we consider the variance minimization problem with safety constraints, obtaining a behavior policy that is safe throughout the execution, while simaltaneously achieving substantial variance reduction compared with the on-policy method.
3 BACKGROUND
A finite Markoy decision process (MDP, Puterman (2014)) includes a finite state space S, a finite action space A, reward function r S x A - RR a transition probability function p : S x S x A - [0, 1]. an initial state distribution Po : S + [0, 1]. and a constant horizon length T. In this paper, to impose safety constraints, we consider constrained Markov decision processes (CMDPs, Altman (2021)), which extends the MDPs with a cost function e: S x A- [0, oc). Without loss of generality, we consider the undiscounted setting for simplicity. Our method is compatible with the discounted setting (Puterman. 2014) as long as the horizon is fixed and finite. For any integer, we define a shorthand [n] = f0, 1,.....2, n2..
For any set X, we use |X| to denote its cardinality. We use A - to denote the (|X* -iddinnssia probability simplex, representing the set of all probability distributions over the set X
constrained Markov decision process (CMDP) begins at time step 0, where an initial state Sy is sampled from Po. At each time step t E [T [T'1] 1]. an action A, is sampled based on (- St). Here, ne : A x S > [0. 1] denotes the policy at time step t. Thereafter, a reward R = r(S,, and a cost C(+1 = c(St. As) is emitted by the environment. A successor state S.+1 is then sampled from p(- St, At). We define the abbreviation Tzj {mi; T++l, ,,,,,,,))) TT2) and л = T1.--1- At each time step t, the return for the reward r is defined as G. = Ei=141 R,, and the return for the cost
is G. T - C,. Then, we define the state-value and aclue functions for the reward r as (s) = E, [G, S, = s] and (s, a) = E, [G, S, = 8, A, = a] Similarly, the state-value and action-valus functions for the cost are defined (()) = E, [G St = s] and Le, (8, a) =
3

---

Published as a conference paper at ICLR 2025
E, [G] St = s, a]. We adopt the total rewards performance metric from Puterman (2014) to measure the performance of the policy т, which is defined as J(x) = Σ. Pu(5)Ur,o($) Likewise, In this paper, we Monte
also define the total costs of π (T) = Eg Po(s) Carlo methods, introduced by Kakutani (1945), for estimating the total rewards J(r). The most straightforward and prevalent technique among many of its variants is to draw samples of J(r) through the online execution of the policy As the number of samples increases, the empirical average of the sampled returns is guaranteed to converge to [T). This method is called on-policy learning (Sutton 1988) it estimates a policy ι by executing itself,
In this work, we focus on off-policy evaluation, in which the goal is to estimate the total rewards J J(r) of an interested policy æ. called the target policy by executing different policy p. called the behavior policy. We generate each trajectory {So, Ao. Ri, C1, Si, A1. R2, C2...., AT-1,AA-1 Rr. CT } by a behavior policy j with Sy ~ Pu. A₁ -)((-))). For simplicity, we use shorthand -E for trajectory generated by the behavior policy μ from the time step t to the time step T - 1 inclusively. - - = {St, Ar, R;+1; Cz+1 ST-1, 1 Rt, Cr}. In off-policy evaluation, defined as T:TT1
to give an estimate of (T), we adopt the importance sampling ratio to reweigh rewards collected by (A. We also
the behavior policy μ.. We define the importance sampling ratio at time / as Pr pz (A,
define the product of importance sampling ratios from time / L' 2 as Pe. I (. St) Various methods utilize importance sampling ratios within off-policy learning frameworks (Geweke, 1988; Hesterberg, 1995; Koller and Friedman, 2009; Thomas, 2015). In this paper, We study the per-decision importance sampling estimator (PDIS, Precup et al. (2000). The PDIS Monte Carlo estimator is defined as GPDIS the PDIS estimator as
[g(Ax15e)
ME.T - = T-1 Pesk Rk+1-
We also use the recursive expression of
Pt (Re-1 + PDDS (144-11) GPDIS (TT
E T 2], 1= 1
(e
With the classic policy coverage assumption (Precup et al., 2000; Maci, 2011: Sutton al., 2016; Zhang, 2022; Liu et al., 2024b) Vt, s. [a)s)) = =0 - (a|s)) = 0, GPDIS provides an unbiased estimation for ((x), i.e., E DGGPDis (To:T-1)) = ((=) Since the PDIS estimator is unbiased, reducing its variance is sufficient for improving its sample efficiency. We achieve this variance reduction by designing and learning proper behavior policies.
4 CONSTRAINED VARIANCE MINIMIZATION FOR CONTEXTUAL BANDITS
In this section, we focus on variance minimization in policy evaluation under safety constraints in contextual bandits. These discussions provide the foundation for the more complicated optimization problems in sequential reinforcement learning settings, which we explore in Section 5. Notations defined in this section are independent of the rest of the paper.
We consider contextual bandits as one-step CMDPs, where the trajectories are in the form of (s, a, r, c).
To estimate the performance of the target policy π, Eo-z<r a)), with data collected by a behavior policy μ. we adopt the importance sampling ratio (Rubinstein, 1981) to reweigh the reward collected by μ.. That is, use Eu- (((a)s)((( a) an estimator, where p(a|s) a(als)-
*(als) Recall A l is
the probability simplex representing all probability distributions over the set A. To ensure that this off- off-policy evaluation is unbiased, a classic choice by Rubinstein (1981) searches for in
[ul Vs, a, (als)) = π (aa (s) = 0 A Vs, ((-1s) E A11
In this work, we search in an enlarged space A (Owen, 2013; Liu and Zhang, 2024), where
{1 Vs, a, u(als) = 0 ((al))((s,)))))))))))))())))))() a) = 0 Vs, m( (- (s) E A
Although a behavior policy in A may not cover the target policy a still gives unbiased estimation in statistics. In the following lemma, we show that searching for μ in this enlarged space A guarantees unbiasedness in the contextual bandits setting.
Lemma 1. Vp E A, Vs.
E Eang ([())))ss))( = (r=z(((ss
4

---

Published as a conference paper at ICLR 2025
Its proof is in Appendix A.I. Our goal is search for auriance-minimize behavior policy μ. Except for the unbiasedness guaranteed by the search space A, we also require μ to satisfy safety constraints which will be defined later. We formulate the variance minimization objective as, Vs.
min HEA
a)).
Then, with the unbiasedness in Lemma 1, we can further decompose the objective in (3) as
V Va-u(p(als)r(s, a)) Le-Baallo(aaassr a))² Ea-a [p(a) ((aas))(sss)] a}² (a.x(r(s.a))
(4)
(By Lemma 1)
Since the second term is constant and is unrelated to μr, it suffices solve
min PEA
Eazz La(a ((()))))()))((s)))
(5)
Next, to ensure the safety of executing the behavior policy μ., we incorporate a safety constraint into the variance minimization problem. Since measuring safety by the expected cost is common approach the safety RL community (Berkenkamp et al., 2017: Achiam et al., 2017; Chow et al., 2018), 8). require that the expected cost of μs remains within threshold related to the expected cost of æ. Given a safety parameter E [0, xc), define a cost threshold
(s) = (1 + ++) a [c(s, a)]-
We impose the following constraint to the optimization problem (5)
(6) This constraint requires that the expected cost of the designed behavior policy should be smaller than the multiple of the expected cost of the target policy æ. By satisfying this constraint, we maintain desired level of safety during the execution of the behavior policy μ.. This safety is defined with respect to the target policy n, which executed in the classic on-policy evaluation method. By setting = 0, behavior policies satisfying this constraint guaranteed to be safer than the target policy.
Ea-ulc(s, a)] & 6,(s), Vs.
Notably, another line of research focused on policy safety chooses a constant threshold for the expected cost. We can simply modify (6) into tonssant-threshold constraint by replacing the threshold function (s) with a constant ò. However, such absolute thresholds may make optimization problems infeasible. Strong assumptions
environments and policies have to be made to guarantee
the existence of feasible solutions under absolute threshold (Achiam et al., 2017). In this paper, impose the safety constraint with respect the target policy æ. because our goal is design a safe behavior policy to address the high variance associated with classic on-policy evaluation methods. The parameter in our threshold allows RL practitioners adjust safety tolerance based on the specific requirements of the problem, as safety constraints are often highly (Achiam al., 2017). Section 7, we demonstrate our method in sequential reinforcement learning with harsh threshold, c = 0, achieving both variance and cost reduction compared to the on-policy method.
We formally define our optimization problem and prove its convexity and feasibility in the following theorem.
Lemma 2. For all and s, the following optimization problem is convex and feasible.
min
E...)lp(a(s)3r(s..
s.f.
En-ple(s, a)] < (s).
(8)
Its proof is in Appendix A.2. Use p. to denote the optimal solution of the above optimization problem. We have the following lemma.
Lemma 3. For all e and s, let 4t be the optimal solution of optimization problem (7), we have Va-u- (p(a)s)r(s, a)) & (a>z(r(s,a))
Proof. We first show that the target policy π is always in the feasible set of the optimization problem (7). We define the set of feasible policies as
F = (ur E A Ve, 8, Farnpc((s, S (s)).
(9)

---

Published as a conference paper at ICLR 2025
Because [0, oo), for the safety constraint, we have
I Rawn [c{8, a)] - (1 + e) [ (x).
By the definition of A (2), x E A. Thus, E F. Because
p argmin IE Bawz (anp MEF
(10)
the optimal solution, have
V Vanw (p(als)r(s,a))
-
= Ea- [palss)r(ss Eu (r(,
(by (4))
< E EBa-lppa/s (la=s - Eo
(by (10))
= - Enwn
Vane (r(,a))
In Section 5, we expand Lemma 2 and Lemma from contextual bandits to sequential reinforcement learning in Theorem I and Theorem 2. We show that with recursive expression of the estimation variance, we can reduce the sequential problem into bandits in each time step t, and thereafter obtain the optimal behavior policy μ² that minimizes variance under safety constraints.
5 CONSTRAINED VARIANCE MINIMIZATION FOR SEQUENTIAL REINFORCEMENT LEARNING
In this section, we extend the techniques from contextual bandits to the sequential reinforcement learn- ing setting. We seek to find an optimal behavior policy that reduces the variance V (GPDI under safety constraints. Before defining the optimization problem, we first define the policy space we search for the behavior policy to ensure the unbiasedness of the PDIS estimator. Conventional methods search μ in the set of all policies that cover the target policy π (Sutton and Barto, 2018), i.e.
(T ))
A_ {u Vt, 8, a, (als) = 0 = Te (als) = A Vt. s, (r(ss) E AlA--)).
In this paper, similar to the bandits setting (2), we search in an enlarged set A, which is defined as
A { Vt, s, (als) 0 = Tr 8 (s, a) = 0 A Vt, s, mr(-s) E AlM-1)) (11)
The following lemma from Liu and Zhang (2024) ensures the unbiasedness of the off-policy estimator with the behavior policy E A. Lemma 4. Vp E A. Vt, Vs.
E CDIS ( | = =] (s.((s)
Its proof is in Appendix A.3, A natural idea do variance minimization under safety constraints with safety parameter e [0, oo) is to solve the following optimization problem
min NEA
V (G (Ton==)))
(12)
(U < (1+)))((T),
where (2) = Po is the expected cost of the behavior policy μ.. Solving this problem directly is very challenging. When designing a policy at a time step t, we need to consider not only the immediate reward generated by this action but also the future consequences. Hanna et al. (2017) try to solve this problem without safety constraints by directly optimizing the hehavior policy y with gradient descent. However, this approach requires online data optimize y and struggles in even moderately complicated environments as shown in Zhong et al. (2022) and Liu and Zhang (2024).
In this paper, we therefore propose to solve this problem in backward way while ensuring safety constraints. Given an e, use
(s) = (1 (s)
(13)

---

Published as a conference paper at ICLR 2025
to denote the safety threshold. We define an extended reward function (s, a) and behavior policy Jx". They are defined in the order of 1fr-1,/7-11 Pr (2:-: No, 140 Denote the variance of the state value for the next state given the current state-action pair (s, a) as Vs, (5, a). We have
t = T - 1. E [T 2/.
(s, a)
Seys (14,++(((411) S,
A =a)
Then, the extended reward function is defined as
a)) = [T,,((8,0) a)²
t= T 1,
(x,,(8, + (8) Es V (GPDIS
PiL (T411--1)
| 8,
LE [T 2] (14)
The behavior policy μ is defined as the optimal solution to the following problem. Vt,
min
Eawny (s:
P.EA
s.t.
Earpa Gr, E a)) S 6c,((s).
We have the following theorem showing the convexity and feasibility of (15), thus ensuring the existence the hehavior policy μ²*
Theorem 1. Ve 2 O, Vt. Vs, the following optimization problem is convex and feasible.
min
En-ny Cer-ulliiree (e.Fe(s.)))
(15)
EA
S.T. Eorpi Ie. a)] S (s)
(16)
Its proof in Appendix A.4. We notice that the constrained optimization problem (15) is similar to (7), which is the optimization problem introduced in Section 4. In the contextual bandit setting (7), optimize the objective with respect to the reward function r, ensuring variance reduction (Lemma 3).
In sequential reinforcement learning (15), optimize with respect to the extended reward function r, achieving variance reduction (Theorem 2 and (17)), while simultaneously guaranteeing safety (18). This observation provides key insight: the step-wise optimization problem in sequential reinforcement learning can be viewed as reduced optimization problem in one-step contextual bandits, where the reward is F. In Section 6, further propose an efficient algorithm to learn without directly addressing the complicated trajectory variance V (GPDIS P (((1)))) |S+11). making long-horizon RL problems more tractable.
Theorem 2. The behavior policy μe' reduces variance compared with the on-policy evaluation method. VI,s, V C -iT
S: (H
<
(
Its proof is in Appendix A.5. We also present the following theorem to demonstrate variance reduction and safety guarantee with respect the original constrained optimization problem (12).
Theorem 3. For all O, the corresponding behavior policy μ² has the following property
V (GPDIS (UPDI((TOTTT))) ( < (GPDIS (T.-T")
(17)
J²((") (1+
(18)
Its proof is in Appendix A.6. Notably, (18) shows that our step-wise safety-constraint (16) is stricter than the original constraint (12).
LEARNING THE OPTIMAL BEHAVIOR POLICY
In this section, we propose efficient algorithm to learn F with previously logged offline data, and sub- sequently derive the optimal behavior policy μ under safety constraints. We notice that learning 7 by (14) is inefficient since we need to approximate the complicated variance V (GPDIS (1r"ttrrr))) SS)). which involves the entire future trajectory. To tackle this challenge, we present a recursive expression of F in the following lemma.
7

---

Published as a conference paper at ICLR 2025
Algorithm 1: Cantty-Constrainee Optimal Policy Evaluation (SCOPE)
Input: target policy x. an offline dataset 'D = {(4,, 0i, di, 6,)/
2: Output: a behavior policy Jr"
3: Approximate fa,t: F from D
4: for = to 0 do
5: Approximate i. from D by Lemma 5
6: Approximate 14, (a]s) following (15)
7: end for
8: Return: the approximated behavior policy je*
Lemma 5. Vs, a, when t. - ()) (r),(8,)) When E [T 2).
fr a) 28,, rs) 2 E (aa))a / 7 a')]
Resi 60)
Its proof is in Appendix A.7. With this lemma, we can learn recursively without approximating the complicated trajectory variance. Then, by (33) in the appendix, we can also decompose the widely interested variance target in succinct form
PDIS
Pir-1) St =)) = Eawzyllii (etr) (s)( CT
Vs
(19)
(b)
This succinct form offers a way to approximate the complicated trajectory variance term (a) from (b) and (c), which do not contain any variance term themselves. This is surprising result because previously the best simplification of the variance for off-policy estimator (a) still depends on state- value variance terms (Jiang and Li, 2016; Liu and Zhang, 2024). With (19), we can approximate the variance of the off- off-policy estimator in a model-free way with only segmented offline data.
For broad applicability, et al., 2019), where the offline data has m previously logged data tuples in the form of {(t;, 8t, a,, ri, C2, < These data tuples behavior policies, and they are not required to form a complete trajectory. In the i-th data tuple, t; is the time step, s; is the state at time step t., 0g is the action taken, 7; is the observed reward, c, is the observed cost, and sf is the successor state. In this paper, we learn F from previously logged offline data. Previously logged offline data are cheap and readily available compared with online data. This makes them great engine for improving policy evaluation in the online phase. Compared with gradient-based methods (Hanna al., 2017; Zhong et al., 2022) which need complete online trajectories, our method does not require a long online warm-up time to find good behavior policy because we are able to utilize offline data. Subsequently, the optimal variance-reducing behavior policy μ² under safety constraints is approximated through standard convex optimization solvers (Nocedal and Wright, 1999; Agrawal et al., 2018).
adopt the behavior policy-agnostic offline learning setting (Nachum
be generated by
more possibly unknown
EMPIRICAL RESULTS
In this section, we demonstrate the empirical results comparing our methods against three baselines: (1) the on-policy Monte Carlo estimator, (2) the robust on- on-policy sampling estimator (ROS, Zhong al. (2022)). and (3) the offline data informed estimator (ODI, Liu and Zhang (2024)). To ensure our method attains lower cost and is thus even safer than the on-policy estimator, we choose 0 in the threshold & (13). All methods learn their required parameters from the same offline dataset to ensure fair comparisons. Given previously logged offline data, method learns the optimal behavior policy under safety constraints using Algorithm 1.
We name our algorithm Cansty--onst Optimal Policy Evaluation (SCOPE) to emphasize that safety constraints are inherently considered the design of the seriance-minimizing behavior policy, unlike previous methods that overlook safety concerns. A metaphor for SCOPE is that it builds bridge focused on efficient transportation (evaluation efficiency) while simultancously ensuring traffic safety (satisfying safety constraints).
8

---

Published as a conference paper at ICLR 2025
- 1,000
$120 27,000
.220 1,000
500- 27.000
1.5
Dut
Eelieatie Eieer
876
KIX
Extimetire Erier
0.6
0.5
0,6
0.0
0.0
0.0
10
10
10
10
10f
10
10
10
10f
10'
107
30 100
101
107
10
Episodes
Episodes
Cost Sudget
Cost Bugget
Figure I: Results on Gridworld with episodes as x-axis. Each curve is averaged over 900 runs (30 target policies, each having 30 independent runs). Shaded regions denote standard errors and are invisible for some curves as they are too small.
Figure 2: Results on Gridworld with cost budget as x-axis. Cost budget is the total cost of execu- tion. Each curve is averaged over 900 runs (30 target policies, each having 30 independent runs). Shaded regions denote standard errors.
Env Size
On-policy MC
Ours
ODI
ROS
1,000
1.000
0.861
1.602
1.083
27,000
1.000
0.849
1.590
1.067
Table I: Average trajectory cost on Gridworld. Numbers are normalized by the cost of the on-policy estimator. ODI and ROS have much larger costs because they both ignore safety constraints. Our method is the only method achieving both variance reduction and constraint satisfaction.
Gridworld: We first conduct experiments in Gridworld with n² states. Each Gridworld is grid with the time horizon also being n. Gridworld environments offer a great tool to test algorithm scalability, because the number of states scales cubically with n. Gridworld in our experiments have n2 = 1, 000 and n 27, 000 number of states, which are the largest Gridworld environments tested among related works (Zhong et al., 2022: Liu and Zhang, 2024). We test all methods on target policies with various performances. The offline data is generated by many different policies to simulate previously logged offline data. In Figure 1, we report the estimation error against episodes. The estimation error for any line is the absolute error normalized by the absolute error of the on-policy estimator after the first episode. Thus, the estimation error of the on-policy estimator starts from In Figure 2, we report the estimation error against the total cost of execution.
If considering solely variance reduction, Figure I shows our method outperforms the on-policy estimator and ROS by large margin. Admittedly, ODI (Liu and Zhang, 2024) is slightly better than our method in terms of variance reduction. However, this slight advantage comes with a huge offe of safety. As shown in Table 1, ODI has much larger cost than on-policy evaluation method (more than 1.5 times) and our method (almost twice as much). This addresses the underestimated fact-solely reducing variance without safety constraints leads to high-cost (unsafe) methods.
To further demonstrate the superiority of balancing variance reduction and safety cost of our method, we provide Figure 2 to compare the variance reduction each method achieves with the same cost bud- get. Since our method SCOPE is optimal for safety-constrained variance minimization, it consistently outperforms all baselines in Figure 2, as shown by the lowest blue line. This means that compared with existing best best-performing methods, SCOPE needs less cost to achieve the same level of accuracy. From Figure 2, we compute that to achieve the same accuracy that the on-policy estimator achieves with 1000 costs (each on-policy episode has expected cost by normalization), ODI costs 880 and SCOPE costs only 425. Following this computation, our method saves 57.5% of costs compared to the on-policy method, and 50% compared to ODI. This reinforces the underestimated fact from the opposite direction-ensurinng safety constraints along with the variance minimization leads to low-cost method. Also, notably, our estimator outperforms the on-policy and ROS estimators in reducing both variance and cost.
MuJoCo: Next, conduct experiments in MuJoCo robot simulation tasks (Todorov et al., 2012). MuJoCo is a physics engine with a variety of stochastic environments The goal is to control a robot to achieve different behaviors such walking, jumping, and balancing.

---

Published as a conference paper at ICLR 2025
Unddll
shodlo
21200
Estnabie Ento
0.5
10
361
107
30
127
107
10f
107
10
10f
12'
10
10
13'
30
Cost Budget
Cost Budget
Cost Budget
Cost Budges
Cost Budget
Figure 3: Results on MuJoCo. Cost budget on the x-axis the total cost of execution. Each curve is averaged over 900 runs (30 of target policies, each having 30 independent runs). Shaded regions denote standard errors and are invisible for some curves because they are too small. Results with a larger x-axis range are in the appendix.
On-policy MC
Ours
ODI
ROS
Saved Cost Percentage
Ant
1000
746
1136
1063
(1000 746)/1000 = 25.4%
Hopper
1000
552
824
1026
(1000 - 505))1500000000 = 44.8%
I. D. Pendulum
1000
681
1014
1003
(1000 - 681)/1000 =31.9%
1. Pendulum
1000
425
615
890
57.55
Walker
1000
694
1031
960
(1000 694)/1000- -3066%
Table Cost needed to achieve the same estimation accuracy that on-policy Monte Carlo achieves with 1000 episodes on MuJoCo. Each curve is averaged over 900 runs. Standard errors are plotted in Figure 3.
As confirmed in Table and Table in the appendix, our method the only method consistently achieving both variance reduction and safety constraint satisfaction. Figure 3 again indicates that our method consistently outperforms all baselines on reducing variance under the same cost budget. This advantage is observed across all five environments, demonstrating the stableness of our method in balancing variance reduction and cost management. Numerically, in Table 2, we show that our method, SCOPE, saves up to 57. .5% cost achieve the desired evaluation accuracy. More experiment details are Appendix B. It worth mentioning that our method is robust to hyperparameter choices- all hyperparameters in our method tuned offline and stay the same across all environments.
CONCLUSION
In reinforcement learning, due the sequential nature, policy evaluation often suffers from large variance and thus requires massive data to achieve the desired level of accuracy. In addition, safety is critical concern for policy execution, since unsafe actions can lead to significant risks and irreversible damage. In this paper, we address these two challenges simultaneously: we propose an optimal lilance-minimizing behavior policy under safety constraints.
Theoretically, we show that our estimate is unbiased. Moreover, while simultaneously satisfying safety constraints, our behavior policy is proven to achieve lower variance than the classic on-policy evaluation method (Theorem 2, Theorem 3). We solve the constrained optimization problem without approximating the complicated trajectory variance (Lemma 5), pointing out promising direction for addressing long-horizon sequential reinforcement learning challenges.
Empirically, compared with existing best-performing methods, we show our method the only one that achieves both substantial variance reduction and constraint satisfaction for policy evaluation in sequential reinforcement learning. Moreover, it is even superior to previous methods in both variance reduction and execution safety.
Admittedly, as there is no free lunch, if the offline data size is too small small- pellaapperapps containing merely single data tuple-the learned behavior policy in our method may be inaceurate. In this case, for safe backup, we recommend the on on-policy evaluation method. The future work of our paper is to extend the constrained variance minimization technique temporal difference learning.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work is supported in part by the US National Science Foundation (NSF) under grants III-2128019 and SLES-2331904.
REFERENCES
Achiam, J., Held, D., Tamar, A., and Abbeel, P. (2017). Constrained policy optimization. In Proceedings of the International Conference on Machine Learning.
Agrawal, A., Verschueren, R., Diamond, S., and Boyd, S. (2018). A rewriting system for convex optimization problems. Journal of Control and Decision.
Altman, E. (2021). Constrained Markov decision processes. Routledge.
Berkenkamp. F., Turchetta, M., Schoellig. A., and Krause, A. (2017). Safe model-based reinforcement learning with stability guarantees. In Advances in Neural Information Processing Systems.
Boyd, S., Boyd, S. P., and Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016). OpenAl Gym. ArXiv Preprint.
Brunke, L., Greeff, M., Hall, A. W., Yuan, Z., Zhou, S., Panerati, J., and Schoellig, A. (2022). Safe learning in robotics: From learning- bassed control to safe reinforcement learning. Annual Review of Control, Robotics, and Autonomous Systems.
Chervonyi, Y., Dutta, P., Trochim, P., Voicu, O., Paduraru, C., Qian, C., Karagozler, E., Davis, J. Q.. Chippendale, R., Bajaj, G., et al. (2022). Semi-analytical industrial cooling system model for reinforcement learning. ArXiv Preprint.
Chow, Y., Nachum, O., Duenez- Guzman, E., and Ghavamzadeh, M. (2018). A lyapunov-base approach safe reinforcement learning. In Advances in Neural Information Processing Systems.
Chua, K., Calandra, R., McAllister, R., and Levine, (2018). Deep reinforcement learning in handful of trials using probabilistic dynamics models. In Advances in Neural Information Processing Systems.
Deisenroth, M. P. and Rasmussen, C. E. (2011). PILCO: A model-based and data-efficient approach to policy search. In Proceedings of the International Conference on Machine Learning.
Farahmand, A. and Szepesvári, C. (2011). Model selection reinforcement learning. Machine Learning.
Garcia, and Fernández, F. (2015). comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research.
Geweke, J. (1988). Antithetic acceleration of monte carlo integration in bayesian inference. Journal of Econometrics.
Gu, S., Yang, L., Du, Y., Chen, G., Walter, F., Wang, J., and Knoll, A. (2022). A review of safe reinforcement learning: Methods, theory and applications. ArXiv Preprint.
Hanna, J. P., Thomas, S., Stone, P., and Nickum, S. (2017). Data-efficient policy evaluation through behavior policy search. In Proceedings of the International Conference Machine Learning.
Hesterberg, (1995). Weighted average importance sampling and defensive mixture distributions. Technometrics.
Huang, S., Dossa, R. F. J. Ye, C.. Braga, J., Chakraborty, D., Mehta, K., and Araújo, J. G. (2022). Cleanrl: High qualttyulity single-file implementations of deep reinforcement learning algorithms. Journal of Machine Learning Research.
11

---

Published as a conference paper at ICLR 2025
Jiang, N. and Li, L. (2016). Doubly robust off off-policy value evaluation for reinforcement learning. In Proceedings of the International Conference on Machine Learning.
Kakutani, S. (1945). Markoff process and the dirichlet problem. In Proceedings of the Japan Academy.
Kalashnikov, D., Irpan, A., Pastor, P., Ibarz, J., Herzog, A., Jang, E., Quillen, D., Holly, E., Kalakr- ishnan, M., Vanhoucke, V., et al. (2018). Scalable deep reinforcement learning for vision-based robotic manipulation. In Proceedings of Conference Robot Learning.
Kingma, D. P. and Ba, (2015). Adam: method for stochastic optimization. Proceedings of the International Conference Learning Representutions.
Koller, D. and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. Mit Press.
Le, H. M., Voloshin, C., and Yue, Y. (2019). Batch policy learning under constraints. Proceedings of the International Conference on Machine Learning.
Li, L. (2019). perspective on off-policy evaluation in reinforcement learning. Frontiers of Computer Science.
Liu, S., Chen, C., and Zhang, S. (2024a). Doubly optimal policy evaluation for reinforcement learning. ArXiv Preprint.
Liu, S., Chen, S., and Zhang, S. (2024b). The ODE method for stochastic approximation and reinforcement learning with markovian noise. ArXiv Preprint.
Liu, S., Chen, Y., and Zhang. S. (2024c). Efficient multi-policy evaluation for reinforcement learning. ArXiv Preprint.
Liu, S. and Zhang, S. (2024). Efficient policy evaluation with offline data informed behavior policy design. In Proceedings of the International Conference on Machine Learning.
Liu, Y., Halev, A., and Liu, X. (2021). Policy learning with constraints in model-free reinforcement learning: A survey. In Proceedings of the International Joint Conference on Artificial Intelligence.
Maei, H. R. (2011). Gradient temporal-differenee learning algorithms. PhD thesis, University of Alberta.
Marivate, V. N. (2015). Improved empirical methods in reinforeement-leamiing evaluation. Rutgers The State University of New Jersey, School of Graduate Studies.
Mirhoseini, A., Goldie, A., Yazgan, M., Jiang, J. W., Songhori, E., Wang, S., Lee, Y.-J., Johnson, E., Pathak, O., Nazi, A., al. (2021). A graph placement methodology for fast chip design. Nature.
Moldovan, T. M. and Abbeel, P. (2012). Safe exploration in markov decision processes. ArXiv Preprint.
Mukherjee, S., Hanna, J. P., and Nowak, R. D. (2022). Revar: Strengthening policy evaluation via reduced variance sampling. In Proceedings of the Conference in Uncertainty Artificial Intelligence.
Nachum, O., Chow, Y., Dai. B., and Li. L. (2019). Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems.
Nocedal, J. and Wright, S. J. (1999), Numerical optimization. Springer.
Owen, A. B. (2013). Monte Carlo theory, methods and examples. Stanford.
Precup, D., Sutton, R. S., and Singh, S. P. (2000). Eligibility traces for off off-policy policy evaluation. In Proceedings of the International Conference on Machine Learning.
12

---

Published as a conference paper at ICLR 2025
Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
Rubinstein, R. Y. (1981). Simulation and the Monte Carlo Method. Wiley.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. ArXiv Preprint.
Sutton, R. S. (1988). Learning to predict by the methods temporal differences. Machine Learning.
Sutton, R. S. (1990). Integrated architectures for learning, planning, and reacting based on approx- imating dynamic programming. In Proceedings of the International Conference Machine Learning.
Sutton, R. S. and Barto, A. G. (2018), Reinforcement Learning: An Introduction (2nd Edition). MIT press.
Sutton, R. S., Mahmood, A. R., and White, M. (2016). An emphatic approach the problem of off-policy lemporal-difference learning. Journal of Machine Learning Research.
Sutton, R. S., Szepesvári, C., Geramifard. A., and Bowling, M. H. (2008). Dyna-style planning with linear function approximation and prioritized sweeping. In Proceedings of the Conference in Uncertainty in Artificial Intelligence.
Thomas, P. S. (2015). Safe reinforcement learning. PhD thesis, University of Massachusetts Amherst.
Todorov, E., Erez, T., and Tassa, (2012). Mujoco: physics engine for model-based control. In Proceedings of the International Conference on Intelligent Robots and Systems.
Towers, M. Kwiatkowski, A., Terry, J., Balis, J. U., De Cola, G., Deleu, T., Goul-ao, M., Kallinteris, A., Krimmel, M., KG, A., et al. (2024). Gymnasium: A standard interface for reinforcement learning environments. ArXiv Preprint.
Trinh, T. H., Wu, Y., Le, Q. V., He, H., and Luong, (2024). Solving olympiad geometry without human demonstrations. Nature.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H.,
Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang, A., Sifre, L., Cai, T., Agapiou, J. P.. Jaderberg, M., Vezhnevets, A. S., Leblond, R., Pohlen, T., Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine, T. L., Gülçehre, Ç., Wang, Z., Pfaff, T., Wu, Y., Ring, R., Yogatama, D., Wünsch, D., McKinney, K., Smith, O., Schaul, T., Lillicrap. T. P., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D. (2019). Grandmaster level in starcraft II using multi-agent reinforcement learning. Nature.
Wachi, A., Shen, X., and Sui, Y. (2024). A survey of constraint formulations in safe reinforcement learning. ArXiv Preprint.
Wachi, A. and Sui, Y. (2020). Safe reinforcement learning in constrained markov decision processes. In Proceedings of the International Conference on Machine Learning.
Williams, R. (1992). Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine Learning.
Zhang, S. (2022). Breaking the deadly triad in reinforcement learning. PhD thesis, University of Oxford.
Zhang, S. (2023). A new challenge in policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence.
Zhong, R., Zhang, D., Schäfer, L., Albrecht, V., and Hanna, J. P. (2022). Robust on-policy sampling for data-efficient policy evaluation in reinforcement learning. In Advances in Neural Information Processing Systems.
13

---

Published as a conference paper at ICLR 2025
A PROOFS
A.1 PROOF OF LEMMA I
Proof. Vs, VHEAA A.
mlals) {(ass)
Bn=sup(dls)((s.00]
E
m(als) r(s,a)
mE (=(
Σ
{(als)r(s,a)
((c)))((s,)+
{(als)r(s,a)
(u A)
at [E(a/((a)))=0)
Σ (((d)))r(s.a)
E Eawal (r(s,
A.2 PROOF OF LEMMA 2
Proof. To prove Lemma 2, we express the objective function as
T((.))))s..0)
Baw [p(,)s)))((ssa))]]
Σ
p(a
[E(alt(a)))20
To prove the problem convex, we begin by examining the feasible of each constraint separately. In the first constraint of A (2),
ss, 0, (((ls)
(alss)(ss,)) 0.
(20)
The feasible set of (20) a linear subspace of R |A4 defined by set of linear equations. Thus, this feasible set is convex.
Next, we decompose the other constraint of (2), (1|ss) A Vs, into two subconstraints:
Σ p(ass) = 1,
(21)
Va, (()s)) 2.
(22)
For all s, the feasible set in (21) can be written in the vector form
4T 1,
(23)
where 1 E IR Al is the vector of ones defined as
and p E RIAI is defined as
u(ails) (s)
p. =
Since (23) linear, the constraint (21) is affine and thus convex (Boyd et al., 2004).
For all s, the feasible set of (22) is the non-negative orthant, defined as
T A|| = (u(-1s) E R!4 [u(aas) 2 0, va).
14

---

Published as a conference paper at ICLR 2025
Since the non-negative orthant forms convex and is known to be convex set (Boyd et al., 2004), we conclude that this constraint's feasible set convex.
Next, we define the vector of costs for all as
c(s,a a1)
C2
cls, [())
Then, for all and s, the safety constraint (8) can be rewritten as
c, p S 6s(s)
which is linear inequality in p. Thus, its feasible set is in convex half-space. Because all the constraints are convex, we conclude that the feasible set F in (9) convex.
Finally, examine the minimization objective (7), where and fixed and independent of the behavior policy For all we express the objective function as
r(c)s))r(s.a}
Eaw ((sala))ss(ssa)))
Σ (E(alu(a)))>00 m(a)s)
Then, for each a, we decompose the objective function as
fa(u(a(s)) ((s,s))rss,a)² m(a
(24)
Taking the first and second derivatives of fas get
fd((aa))) T(aas)2r(s a)²
m(aas)2
("(((a(s)) 2n (a(ss)) a)
p(a
Since Vs, a, fd (p(als)) 2 know that (24) convex for all a. Then, summation of convex functions, (7) is also convex. In conclusion, by the convexity of the feasible set F and the objective function (7), we obtain the convexity of the constrained optimization problem Lemma 2.
For feasibility. note that by Lemma 3, π E F. which is the feasible set. Thus, we confirm the feasibility in Lemma 2.
A.3 PROOF OF LEMMA 4
Proof. We proceed via induction. For = T' 1, we have
E G
PDIS
St =E 3 [p, Re+1
St] = E[p SS]
(B1 (S,, St]
(Lemma 1)
-S.)
For 1 [ -2], we have
E G PDIS (T -1) S,
-E |pcRe11 + G.G PDIS -(et))=11) SS]]
-F (peRet
S.] E G (111: St]
-EE [pe
St] + E EA. 150
[ [p.
(T PDIS (141:T11
St, Ar, S.+1] Ss]
(Law of total expectation)
-F (p
St] EA (55)
[ [ PDIS (T
S [t]]
(Conditional independence and Markov property)
15

---

Published as a conference paper at ICLR 2025
= [p:Re+1 Si] (19 (1 St]] -EALnAi(- (91))) [prqm, (St,, Ar) St]]
(Inductive hypothesis)
(Definition of gm,z)
(11))(((()) ( Sil (S,),
(Lemma 1)
which completes the proof.
A.4 PROOF OF THEOREM 1
Proof. We first define the set of feasible policies as
F {n E A Ve, t, 8, Earp, (s), S (s))
(25)
We begin by examining each constraint, In the first constraint of A (11);
Vt, (4
(,(als)gm, a) 0.
(26)
The feasible set of (26) a linear subspace of |A| defined by set of linear equations. Thus, this feasible set is convex.
Next, we decompose the other constraint of A (11,, (1((11s) E 414-1 into two constraints:
Σ [e(als) 1,
(27)
Va, Me (a(s)) 0.
(28)
For all and s, in (27), the feasible set be written
1 Ma. 1,
(29)
where 1 E IR Al is the vector ones and pad E RIAI is defined as
(<(ass))
Pel
[o(a|A||ss]
Since (29) linear, the feasible set constraint (27) affine and thus convex (Boyd et al., 2004).
For all and the feasible set for the constraint in (28) is the non-negative orthant, defined as (-1(-1)) E RI4
| 2 0, Va).
Since the non-negative orthant forms a convex cone and known to be a convex set (Boyd et al., 2004), conclude that this constraint is convex.
Next, we define the vector the state-action value function for the cost e for each as
(s,())))))
qu.t
(u, (A)))
Then, for all e, and the safety constraint (16) can be rewritten
N. < (s,,
which is linear inequality in 14- Thus, its feasible set is convex half-space. Because all the constraints' feasible sets are convex, we conclude that the feasible set F in (25) is convex.
To prove Theorem 1, we express the objective function
Tr(a)s))((ssa))
Egyn, (s)
Σ
Mc(als)
[E(c]ue(ols)>0)
16

---

Published as a conference paper at ICLR 2025
where 7 in (14) is defined
(s, a)²
t= t= --11,
as) = ()) + (=,( + Esi V
GPDDS
Pi-1--11 (411T-1)
(ee11) s
t [T 2]
Here, Pr can be learned with logged offline data, as detailed in Algorithm 1, and it is unrelated to pa. Then, for each a, we decompose the objective function as
fa(H((a(s)) = (=(als)(((ss.a)) Me(als)
(30)
Taking the first and second derivatives of fas get
(a(e((a)))) T=(als)F((ssa) (a(s))
(((((a))s) [T<(al))"F(ssaa
[r(al8)3
Notice that the extended reward F defined in (14) is non-negative, since all the summands are negative. Thus, Vt, a, 5" (1 (als)) 2 O, and we know that (30) is convex for all a. Then, as a summation of convex functions, (15) is also convex. In conclusion, by the convexity of the feasible set FF and the objective function (15), we obtain the convexity of the constrained optimization problem in Theorem
For feasibility, we show that the set of feasible policies (25) is non-empty. Because e E 00), for the safety constraint, have
Ba [o [e],(s]] S (1++ c) ( (i,
(s).
By the definition of (11), Vl, मं E A. Therefore, the set of feasible policies (25) is non-empty. Thus, the constrained optimization problem in Theorem I is feasible.
A.S PROOF OF THEOREM 2
To prove Theorem 2, we first restate recursive expression of the variance V (GPDIS for μ E A from Liu and Zhang (2024), and present its proof for completeness.
(TT-1) Si)
Lemma 6. For any μ for 1,
V PD (-==))) S:) EAro, (S. Ad) St]] v (S))
for T [-2) -2].
(GPDIS
MeT-1)
(T:TT1
-EArpi [p] (Es V (G PDIS
(+(1))))))) (.)) St, Ai] + Vr,( A.) + (r, At)) S
- (S).
Proof. For completeness, we provide the proof from Liu and Zhang (2024). We proceed via induction. When T 1, have
V PDIS -err-') Ss))
=V (per(Se, Ar) St))
=V (S))
-EA, [p (S,, A,) | St Ux (St)2,
When E [T 2), we have
W PDIS ( St)
(31)
=EA V PDIS (DDS
St, At) S + VA, (E PD (T 1) St,, |
(Law of total variance)
17

---

Published as a conference paper at ICLR 2025
=BA, LPEV (r(S,,A)) + GPDIS
(T(41--11) (T
St. Ar) | |St]
+ VA, (prB [r(St, Ar) + GDDIS (T+11T-11) St, A.] | |St)
(By (1)
-EA, [pîV (G PGP (T(4TT-1) St. Ar) St] + V.. (prB [r(S Ar) + GPIS (411--1 St As]
St)
(Deterministic reward
-EA, V (G ( St A.) S.] + AA (prda, (St, At) S.))
Further decomposing the first term, we have
V (GPDIS (+117-1) A.)
(32)
=Es V (GPDIs ((-))-)) S A,, S(+1) | Se: Ad]
+ V [E [GPDI ( St, A,, S4t1l
St, At)
(Law of total variance)
-Es [ (G PDIS (T-1TT-1 S(41) Sr, St, A.] +s (E [GrDiS ( ()) S441] St At)
(Markov property)
-Bs V (G
PDIS T ------1) S(41
St. St, A.] + Vsu (Vz,t41 St, As)- (Lemma 4)
Then, plugging (32) back to (31) yields
S.)) =B -BA, [ot (Es.. [V (G ( Si+1) | |t,,, Ar] + (U,, St s, a)) |t] (T+11T-1)
V (GPDIS Per
+ VA. (pig (S,, At) S:)
EA. [et (Es.11 V (C S4+1 S, A.] + V (V=, St 8, A, a)) St
+ EA, ( A, 8.] - (EA, Pe e (S,, Az) SS))
=B -AA. lot (Es.. V (G PDIS (-( St+1 Az] + Vs (S St = A, = a)) St
+ BA. [p A,)2 St] (S,)
(Lemma 1)
=EA, [p (Est+1 VV (GPDIS (7411=11) Se+1) St At] (r,, Ar) + (0,, A.) |
(S.)2
(Definition of v)
which completes the proof.
Then, with the extended reward (14) defined as
(5, a)²
1 1= T - 1, tE [T 2].
fe(s, a)
(x, + (s, + Es... v (G (i-17-1)
Set1) s (T4+1T-1)
we can express the variance in a succinct form
PPISS -ir-") S: =s) =Boul(?((ss) un,(s)) Vs,t.
(33)
Now, we restate Theorem 2 and present its proof.
Theorem 2. The behavior policy μ² reduces variance compared with the on-policy evaluation method.
vt,s, V (PDDS (T 1S
St =)) S (GP (s,
In Appendix A.4, we show that Vt, Te F, where in (25) is the set of feasible policies for the constrained optimization problem in Theorem 1. Recall that μı is defined as the optimal solution to the problem (15), i.e.,
P = argmin Egryy (s)
(34)
P4EF
18

---

Published as a conference paper at ICLR 2025
Thus, Vt, 5,
V CDIS ( ( St =
Earwi (p, a)] Un (
(By (33) )
I Bawn [p) - (s)
(By (34) and ne E F)
=V (GPDI (TT-11 St = 8)
(By (33)
which completes the proof.
A.6 PROOF OF THEOREMS 3
Proof.
We first prove the variance reduction property.
V C
Es.
V
PPDIS (T))-T))
| S
+ Vs. [E [GDDS (PPDis(T0TT=1) |Su
(Law of Total Variance)
B.s
Mb.T V GPDIS
(To:T-1)
( |6
+ Vs (vx))(So))
(By Lemma 4 and μ E A)
<Bso
[V (GPDIS (To:T
-1) [o)] + Vso (v (Un))(So))
(Theorem 2)
=Es.
V
PGPDIS
(To:T-1)
[b)] + Vs (E [G PDIS (To-T-1) Sol)
(By Lemma 4 and т E A)
=V (GPDIS (Taar11
(Law of Total Variance)
Next, we prove the safety constraint satisfaction.
Σ Coo(s)u
Σ Po(s))Eanuã lo
$ Σ po(s)),,0ss)
(Theorem 1)
Σ Po(s)(1 + c)
(By (13))
=(1 c) Σ (
=(1 (())))
which completes the proof.
A.7 PROOF OF LEMMA 5
Proof. Vs, a, when = =T 1, = r=, a)?, as defined in (14). For t E [ - 2].
ac)
=V),(s,a) 2x, ( (3) (00+))2BB Esu. [v (T 1 |s
(By (14))
=,) (x,1 (8,
+ Σ p(ss|ss,0) a) EA (phn (Bsip2 v (T (it2m-1) S2t2) SS41, Act1]
tu Ast2) + (S44, SS41 = 881 (s)41
(By Lemma 6)
=n,)(s,)) + (s, + E ((5(1s,)) [BAe ( A
St+1 = sf]
(By (14))
19

---

Published as a conference paper at ICLR 2025
=Vx,(o,a) +x, +
vo 15)))
=Vmm (VT,+1(( St = A, = a) + (8)
p(ss'(s,a)) PL+10t ((')s(() 7,,+111('',, (7,441(5522
(Definition of 2))
d'a'
EEs ((+++(((++)) S = =, = a| Es |um S = s, Ar = a]?
+ (0) ( (x (7.0-1(8')
p(s'ls, (166) (p..(s, r(s, ()s, (m,a)))+mm,,.saaa
+ [=(6lss))))amm1111))))) -
a'a'
- + Σ me
s'
Te+1(a'|s')
44421 xx od))
B EXPERIMENT DETAILS
B.1 GRIDWORLD
Environment Size
On-policy MC
Ours
ODI
ROS
1,000
1.000
0.547
0.460
0.953
27,000
1.000
0.575
0.484
0.987
Table 3: Relative variance for estimators on Gridworld. The relative variance is defined as the variance of each estimator divided by the variance of the on-policy Monte Carlo estimator. Numbers are averaged over 900 independent runs (30 target policies, each having 30 independent runs). Standard errors plotted in Figure 1.
Env Size
On-policy MC
Ours
ODI
ROS
Saved Cost Percentage
10
1000
472
738
1035
(1000 472)/1000 = -52.8 %
30
1000
487
765
1049
(1000 - 487)/1000 = =51.3%
Table Cost needed to achieve the same estimation accuracy that on-policy Monte Carlo achieves with 1000 episodes Gridworld. Each number is averaged over 900 runs. Standard errors plotted Figure 2.
We conduct experiments on Gridworlds with n 1, 000 and n 27, 000 states, where for Gridworld with size n², we set the width, height, and time horizon T all be n. The action space contains four different possible actions: up, down, left, and right. After taking action, the agent has a probability of 0.9 to move accordingly and a probability of 0. to move uniformly at random. When the agent runs into boundary, it stays in its current position. We randomly generate the reward function r(s, a) and cost function c(s, a). We consider 30 randomly generated target policies with various performances. The ground truth policy performance is estimated by the on-policy Monte Carlo method, running each target policy for 10 episodes. We experiment two different sizes of the Gridworld with number of 1, 000 and 27, 000 states.
The offline dataset each environment contains a total of 000 episodes generated by 30 policies with various performances. The performance of those policies ranges from completely random
20

---

Published as a conference paper at ICLR 2025
initialized policies well-trained policies in each environment. For example, in Hopper, the performance those 30 policies ranges from around 18 to around 2800. We let offline data be generated by various policies to simulate the fact that offline data from different past collections.
We learn functions fr.e: 1 and fT, using Fitted Q- Q-Evlluation algorithms (FQE, Le et al. (2019)) by passing data tuples in D,, from T (FQE, Le et al. (2019)) is a different algorithm from Fitted Q-Improvement (FQI). Importantly, Fitted Q-Evaluation is prone overestimate the action-value function qn,t because it does have any max operator and does not change the policy. All hyperparameters are tuned offline based on Fitted Q-learning loss. We leverage
O. It is worth noticing that Fitted Q-Evaluation
see-hidden-layee neural network and test the neural network size with [64, 128, 256]. We then choose 64 as the final size. We also test the learning rate for Adam optimizer with [1e le- 1e-3 2 and finally choose to use the default learning rate le- learning rate for Adam optimizer (Kingma and Ba, 2015). For the benchmark algorithms, we use their reported hyperparameters (Zhong al., 2022; Liu and Zhang, 2024). Each policy has 30 independent runs, resulting in total of 30 30 900 runs. Thus, each curve in Figure 1, Figure 2 and each number Table 1, Table 3 and Table 4 are averaged from 900 different runs over wide range policies, demonstrating strong statistical significance.
B.2 MuJoCo
Figure 4: MuloCo robot simulation tasks (Todorov et al., 2012). Pictures are adapted from (Liu and Zhang, 2024). Environments from the left to the right are Ant, Hopper, InvertedDoubleeendulum InvertedPendulum, and Walker.
On-policy MC
Ours
ODI
ROS
Ant
1.000
0.835
0.811
1.032
Hopper
1.000
0.596
0.542
1.005
D. Pendulum
1.000
0.778
0.724
0.992
1. Pendulum
1.000
0.439
0.351
0,900
Walker
1.000
0.728
0.696
0.908
Table 5; Relative variance of estimators MuJoCo. The relative variance is defined as the variance of each estimator divided by the variance of the on on-policy Monte Carlo estimator. All numbers are averaged over 900 independent runs (30 target policies, each having 30 independent runs).
On-policy MC
Ours
ODI
ROS
Ant
1.000
0.897
1.397
1.033
Hopper
1.000
0.930
1.523
1.021
D. Pendulum
1.000
0.876
1.399
1.012
Pendulum
1.000
0.961
1.743
0.990
Walker
1.000
0.953
1.485
1.061
Table Average trajectory cost on MuJoCo. Numbers are normalized by the cost of the on-policy estimator. ODI and ROS have much larger costs because they both ignore safety constraints. Our method the only method consistently achieving both variance reduction and safety constraint satisfaction.
21

---

Published as a conference paper at ICLR 2025
101
choalo M.
10
Estration Entrr
15%
10-
20-1
10'
107
107
10
10"
1.0
107
3.2
1.0
301
122
3D1
307
301
127
107
307
10'
10'
301
Cost Budget
Cost Budget
Cost Budget
Cost Budget
Cost Buddpt
Figure 5: Results on MuJoCo with log-scale y-axis to show the error does not converge. Each curve is averaged over 900 runs (30 target policies, each having 30 independent runs). Shaded regions denote standard errors and are invisible for some curves because they are too small.
MuJoCo is physics engine with various stochastic environments, in which the goal is to control a robot to achieve different behaviors such as walking, jumping, and balancing. We construct 30 policies in each environment, resulting a total of 150 policies. The policies demonstrate a wide range of performance generated by the proximal policy optimization (PPO) algorithm (Schulman et al., 2017) using the default PPO implementation Huang et al. (2022). Original MuJoCo environments are Markov decision processes (MDP) and do not have cost functions. We enhance it with cost functions to make it constrained Markov decision processes (CMDP). Specifically, the cost of the MuJoCo environments is built the control cost of the robot. The control cost is the L2 norm of the action and is proposed by OpenAl Gymnasium (Brockman et al., 2016). This control cost is motivated by the fact that large actions in robots induce sudden changes in the robot's state and may cause safety issues.
We set each environment in MuJuCo to have fixed time horizon 100 in OpenAI Gymnasium (Towers et al., 2024). Because our methods are designed for discrete action space, we discretize the first dimension of the MuloCo action space. The remaining dimensions policies and are deemed as part of the environment. The offline dataset for each environment contains 000 episodes generated by 30 policies with various performances, following the same method as in the Gridworld environments. Functions (r,1, lr, and f are learned using the same way as in Gridworld enviromments. Notably, our algorithm robust on hyperparameters, in Algorithm/ 1 are tuned offline and are the same across all MuJoCo and Gridworld experiments. Each policy in MuloCo has 30 independent runs, resulting total of 30 x 30 = 900 runs. As result, curves in all figures are averaged from 900 different runs with wide range of policies, showing a strong statistical significance.
then controlled by the PPO
all hyperparameters
22


Reviews:
[{"review_id": "g9hBUJ8GCI", "reviewer": "Reviewer_92mj", "summary": "This paper provides an on-policy evaluation method that aims to reduce evaluation variance while also ensuring safety. This is done in the context of contextual bandits, sequential RL, and offline RL. Via theoretical results, this method is shown to be feasible, unbiased, and variance-reducing. Empirical results on GridWorld and MuJoCo demonstrate that under different cost budgets, the proposed method is able to improve performance (variance reduction) over baselines.", "questions": "* What are the implications of considering the undiscounted setting, as opposed to the discounted setting?\n* See \"Weaknesses\"", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* This work is well-motivated in terms of aiming to reduce variance while also _ensuring safety_ during on-policy evaluation.\n* The proposed method is simple, and theoretical results demonstrate that the method is feasible, unbiased, and variance-minimizing.\n* The experimental demonstration is solid, with improved performance (variance reduction) over baselines under any given cost budget. The authors demonstrate good experimental practices, including averaging over many runs and comparing against strong baselines.", "weaknesses": "More discussion could be included on the specific form of the safety constraint. In what settings is it sufficient to ensure that \"the expected cost of the designed behavior policy $\\mu$ should be smaller than the multiple of the expected cost of the target policy $\\pi$\"? In what settings might this form of safety constraint be insufficient?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L8To4gFuPw", "reviewer": "Reviewer_HUVe", "summary": "This paper addresses high variance in on-policy evaluation in reinforcement learning by proposing a behavior policy that minimizes variance under safety constraints. Unlike previous methods that ignore safety, this approach provides unbiased, low-variance evaluation while ensuring safe execution. Empirical results show it outperforms prior methods in both variance reduction and safety compliance.", "questions": "1. From my understanding, the algorithm proposed in this paper aims to learn a behavior policy that minimizes variance while satisfying safety constraints. However, I don’t see a clear connection in the theoretical results to the offline dataset used. Could you clarify this? Specifically, if the dataset lacks sufficient coverage, is it still possible to obtain a reliable behavior policy?\n\n2. In the experimental section, the paper compares the proposed method to the Monte Carlo (MC) approach, which seems straightforward but rather basic. Could the authors also consider comparing with online bootstrapping methods, as they might provide more efficient solutions for online policy evaluation?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The study addresses the new and intriguing problem of incorporating safety constraints in policy evaluation.\n2. The paper is well-organized and easy to follow.\n3. It provides comprehensive support with both theoretical and empirical evidence.", "weaknesses": "1. While addressing safety constraints is novel, the approach to variance minimization under these constraints lacks significant innovation.\n2. In the experimental section, the paper could benefit from comparisons with a broader range of work in safe reinforcement learning to better demonstrate its advantages.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WG74b7sKQi", "reviewer": "Reviewer_J4Sc", "summary": "This paper studies the problem of policy evaluation under constraints and proposes an algorithm that reduces the policy evaluation variance while satisfying the constraint.", "questions": "Is the transition from (12) to (13) too conservative? As (12) requires the total cost to be smaller than the threshold but (13) makes the feasible set smaller. What if the optimization problem (13) has an empty feasible set? How to derive Theorem 3 when (13) is too conservative, as the policy $\\pi$ will not satisfy this conservative constraint?\n\nHow is the proposed method applied to continuous state-action space?\n\nThe mainstream policy evaluation uses a one-step method, such as the TD method. Can the proposed method be applied to these methods?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The proposed solution is derived by formulating and solving an optimization problem, which has support from the theoretical results.\n\nThe literature review is thoughtful and complete.", "weaknesses": "In the experiment, the performances of the constrained RL algorithm under different policy evaluation methods should be compared.\n\nSee **Questions**", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "czQpVrS27X", "reviewer": "Reviewer_MExc", "summary": "This paper proposes an optimal variance-minimizing behavior policy to guarantee the satisfaction of safety constraints. Theoretically, the authors prove that their proposed method is unbiased and with lower variance. Empirical experiments show that their proposed method achieves variance reduction and safety guarantee.", "questions": "- Q1: I could not understand (12). Why is the safety threshold $(1+ \\epsilon)$? In other words, could you tell me the reason why RHS in (12) does not depend on $\\pi$? Perhaps is this a typo?\n- Q2: The original MuJoCO environment does not have a notion of safety cost. How did the authors introduce safety costs?\n- Q3: How was the offline dataset generated? Could you tell me the details? I know there is some statement in the Appendix, but it is critical for understanding the actual performance of the algorithm.\n- Q4: Could you show me the experimental results or figures illustrating how the performance of each algorithm is affected by the number of offline datasets?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors address a very important and interesting problem where safety constraint is considered in RL policy evaluation.\n- The motivation behind the problem formulation is well-presented while using an example of Google's data center.\n- The background section is well-written and easy to follow.\n- I think it is a good idea to provide theoretical results and key ideas in the case of contextual bandit.\n- Theoretical results are nice and proofs are well-presented.\n- The empirical experiments are overall well-conducted.\n- The authors' proposed method performs well in Grid-world and MuJoCO.", "weaknesses": "- In the Related Work section, the literature review of safe RL can be written in a more organized way. There are several survey papers on safe RL, so the authors may want to refer to how to comprehend safe RL.\n    - Brunke, Lukas, et al. \"Safe learning in robotics: From learning-based control to safe reinforcement learning.\" Annual Review of Control, Robotics, and Autonomous Systems 5.1 (2022): 411-444.\n    - Liu, Yongshuai, Avishai Halev, and Xin Liu. \"Policy learning with constraints in model-free reinforcement learning: A survey.\" In IJCAI. 2021.\n    - Gu, Shangding, et al. \"A review of safe reinforcement learning: Methods, theory and applications.\" arXiv preprint arXiv:2205.10330 (2022).\n    - Wachi, Akifumi, Xun Shen, and Yanan Sui. \"A Survey of Constraint Formulations in Safe Reinforcement Learning.\" In IJCAI (2024)\n- Readers cannot know that this paper deals with off-policy evaluation until line 160. Please clearly mention that in the Abstract or Introduction. It may be better to add \"off-policy\" in the title. \n- I think lines 309-369 are hard to follow. I understand that (12) is challenging to handle, but it is unclear whether the authors' transformation is reasonable or not. I think it is better to discuss the theoretical relations between (12) and (15, 16), e.g., equivalent, conservative approximation, etc. \n- I think readers cannot identify the magnitude of variance for each algorithm from Figures 1 or 2. There should be a table including the actual variance numbers (at least in the Appendix) like Tables 3 or 4.\n- I am also wondering whether the variance of on-policy MC in Tables 3 or 4 is large. I agree with the authors that the proposed method achieves lower variance, but I am not fully convinced of how important are the differences in real applications.\n- I think the reproducibility of this paper is rather low given there is no source code attached and there is little information on the experimental setups. It is problematic as a research paper that even basic information is not mentioned for reproducing experimental results.\n\n### Typos\n- In (3), $\\mathbb{V}$ --> $\\mathbb{V}_{a \\sim \\mu}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)