Efficient Policy Evaluation with Safety Constraint for Reinforcement Learning

## Abstract

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.

## 1 Introduction

In recent years, reinforcement learning (RL, Sutton and Barto, ()) has shown exceptional success in various sequential decision-making problems. For instance, RL algorithms have reduced energy consumption for Google’s data center’s cooling by $40\%$ (Chervonyi et al.,, ), solved Olympiad-level geometry problems (Trinh et al.,, ), and designed general-purpose data center CPUs (Mirhoseini et al.,, ).
In RL applications, policy evaluation
enables RL practitioners to estimate the performance of a policy before committing to its full deployment. In policy evaluation, conventional wisdom uses the on-policy method, in which a policy (i.e., the target policy) is evaluated by directly executing itself. However, this straightforward approach is crude because using the target policy itself as the data-collecting policy (i.e., the behavior policy) is proved to be suboptimal (Hanna et al.,, ; Liu and Zhang,, ), resulting in evaluations with potentially high variance. Thus, the on-policy evaluation method may require massive online data to achieve the desired accuracy.

Unfortunately, collecting massive online data through real-world interaction can be both expensive and slow (Li,, ; Zhang,, ). In Google’s data center’s cooling system, each interaction step in the actual deployment takes $5$ minutes (Chervonyi et al.,, ). 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,, ; Farahmand and Szepesvári,, ; Marivate,, ). As a result, both online and offline RL practitioners still depend heavily on online policy evaluation techniques (Kalashnikov et al.,, ; Vinyals et al.,, ).

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.,, ; Zhong et al.,, ; Liu and Zhang,, ). However, all their approaches ignore a critical issue: safety. In many real-world applications, neglecting safety in policy execution can result in serious consequences. For example, in Google’s data center cooling system, a 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-minimizing 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 to 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

Safety Constraints.
Safety in reinforcement learning, often framed as safe RL (Garcıa and Fernández,, ), has been an active research topic recently.
Moldovan and Abbeel, () 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 a model-based approach, requiring an explicit approximation of the transition function, which introduces challenges common to model learning, such as compounding errors and the need for accurate model dynamics (Sutton,, ; Sutton et al.,, ; Deisenroth and Rasmussen,, ; Chua et al.,, ). 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-Evaluation, Le et al., ()).
Berkenkamp et al., () propose to ensure safety by keeping the agent within safe regions, which are characterized by a Lyapunov function. However, they assume the environment to be deterministic, i.e., $p(s^{\prime}|s,a)=1$ for the successive state $s^{\prime}$, 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.

Achiam et al., () models this research problem as a constrained Markov decision process (CMDP), where safety is measured by a cost function, and they enforce a constant threshold to constrain the expected total cost.
However, even though they adopt the trust-region method to 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, ()
propose a 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-collecting policy (i.e., the behavior policy) for evaluating itself is not optimal (Owen,, ), some recent studies focus on searching for or designing a data-reducing behavior policy without considering safety.
Hanna et al., () formulate the task of finding a variance-reduction behavior policy as an optimization problem. They 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,, ), 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, their method requires highly sensitive hyperparameter tuning to learn the behavior policy effectively. Specifically, the learning rate can vary by up to $10^{5}$ times across different environments, as reported in the experiments of Hanna et al., (). This extreme sensitivity requires online tuning, consuming massive online data.
In contrast, we propose an efficient algorithm to learn our optimal behavior policy with purely offline data. Furthermore, Hanna et al., () constrain the online data to be complete trajectories. In contrast, our method copes well with incomplete offline tuples, making it widely applicable.

Zhong et al., () also propose to design a variance-reducing behavior policy for policy evaluation. They adjust the behavior policy to focus on 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., () 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., () also propose a behavior policy to reduce variance. Nevertheless, they also do not consider the crucial safety problem. Besides, their results are restricted to tree-structured MDPs, which is a significant limitation.
In contrast, our method works on general CMDPs, extensions of the widely studied MDPs. Moreover, Mukherjee et al., () also leverage a model-based approach.
The current state-of-the-art method in behavior policy design is proposed by Liu and Zhang, (), where they find an optimal and an offline-learnable behavior policy.
However, all these approaches (Hanna et al.,, ; Zhong et al.,, ; Liu and Zhang,, ) focus solely on reducing evaluation variance while neglecting a 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 simultaneously achieving substantial variance reduction compared with the on-policy method.

## 3 Background

A finite Markov decision process (MDP, Puterman, ()) includes a finite state space $\mathcal{S}$, a finite action space $\mathcal{A}$,
a reward function $r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$,
a transition probability function $p:\mathcal{S}\times\mathcal{S}\times\mathcal{A}\to[0,1]$,
an initial distribution $p_{0}:\mathcal{S}\to[0,1]$,
and a constant horizon length $T$. In this paper, to impose safety constraints, we consider constrained Markov decision processes (CMDPs, Altman, ()), which extends the MDPs with a cost function $c:\mathcal{S}\times\mathcal{A}\to[0,\infty)$.
Without loss of generality,
we consider the undiscounted setting for simplicity.
Our method is compatible with the discounted setting (Puterman,, ) as long as the horizon is fixed and finite. For any integer,
we define a shorthand $[n]\doteq\quantity{0,1,\dots,n}$. For any set $\mathcal{X}$, we use $|\mathcal{X}|$ to denote its cardinality. We use $\Delta^{|\mathcal{X}|-1}$ to denote the $(|\mathcal{X}|-1)$-dimensional probability simplex,
representing the set of all probability distributions over the set $\mathcal{X}$.

A constrained Markov decision process (CMDP) begins at time step 0 0, where
an initial state $S_{0}$ is sampled from $p_{0}$.
At each time step $t\in[T-1]$,
an action $A_{t}$ is sampled based on $\pi_{t}(\cdot\mid S_{t})$. Here, $\pi_{t}:\mathcal{A}\times\mathcal{S}\to[0,1]$ denotes the policy at time step $t$.
Thereafter, a reward $R_{t+1}\doteq r(S_{t},A_{t})$ and a cost $C_{t+1}\doteq c(S_{t},A_{t})$ is emitted by the environment. A successor state $S_{t+1}$ is then sampled from $p(\cdot\mid S_{t},A_{t})$.
We define the abbreviation $\pi_{i:j}\doteq\quantity{\pi_{i},\pi_{i+1},\dots,\pi_{j}}$ and $\pi\doteq\pi_{0:T-1}$.
At each time step $t$, the return for the reward $r$ is defined as
$G_{t}\doteq\sum_{i={t+1}}^{T}R_{i},$
and the return for the cost $c$ is $G^{c}_{t}\doteq\sum^{T}_{i={t+1}}C_{i}$. Then, we define the state-value and action-value functions for the reward $r$ as
$v_{\pi,t}(s)\doteq\mathbb{E}_{\pi}\left[G_{t}\mid S_{t}=s\right]$ and $q_{\pi,t}(s,a)\doteq\mathbb{E}_{\pi}\left[G_{t}\mid S_{t}=s,A_{t}=a\right].$
Similarly, the state-value and action-value functions for the cost $c$ are defined as
$v^{c}_{\pi,t}(s)\doteq\mathbb{E}_{\pi}\left[G^{c}_{t}\mid S_{t}=s\right]$ and $q^{c}_{\pi,t}(s,a)\doteq\mathbb{E}_{\pi}\left[G^{c}_{t}\mid S_{t}=s,A_{t}=a
\right].$
We adopt the total rewards performance metric from Puterman, () to measure the performance of the policy $\pi$,
which is defined as
$J(\pi)\doteq\sum_{s}p_{0}(s)v_{\pi,0}(s)$.
Likewise, we also define the total costs of $\pi$ as
$J^{c}(\pi)\doteq\sum_{s}p_{0}(s)v_{\pi,0}^{c}(s)$.
In this paper, we use Monte Carlo
methods, as introduced by Kakutani, (), for estimating the total rewards $J(\pi)$.
The most straightforward and prevalent technique among many of its variants is to draw samples of $J(\pi)$ through the online execution of the policy $\pi$.
The empirical average of the sampled returns converges to $J(\pi)$ as the number of samples increases.
Since this method estimates a policy $\pi$ by executing itself, it is called on-policy learning (Sutton, ).

In this work, we focus on off-policy evaluation, where the goal is to estimate the total rewards $J(\pi)$ of an interested policy $\pi$, called the target policy
by executing a different policy $\mu$,
called the behavior policy.
We generate each trajectory
$\textstyle\quantity{S_{0},A_{0},R_{1},C_{1},S_{1},A_{1},R_{2},C_{2},\dots,S_{T
-1},A_{T-1},R_{T},C_{T}}$ by a behavior policy $\mu$ with
$S_{0}\sim p_{0},A_{t}\sim\mu_{t}(\cdot|S_{t}).$
We use a shorthand $\tau^{\mu_{t:T-1}}_{t:T-1}$ for a trajectory generated by the behavior policy $\mu$ from the time step $t$ to the time step $T-1$ inclusively. It is defined as
$\tau^{\mu_{t:T-1}}_{t:T-1}\doteq\quantity{S_{t},A_{t},R_{t+1},C_{t+1}\dots,S_{
T-1},A_{T-1},R_{T},C_{T}}.$
In off-policy evaluation, to give an estimate of $J(\pi)$, we adopt the importance sampling ratio to reweigh rewards collected by the behavior policy $\mu$.
We define the importance sampling ratio at time step $t$ as
$\textstyle\rho_{t}\doteq\frac{\pi_{t}(A_{t}\mid S_{t})}{\mu_{t}(A_{t}\mid S_{t
})}.$
The product of importance sampling ratios from time $t$ to $t^{\prime}\geq t$ is then defined as
$\textstyle\rho_{t:t^{\prime}}\doteq\prod_{k=t}^{t^{\prime}}\frac{\pi_{k}(A_{k}
|S_{k})}{\mu_{k}(A_{k}|S_{k})}.$
Various methods utilize importance sampling ratios within off-policy learning frameworks (Geweke,, ; Hesterberg,, ; Koller and Friedman,, ; Thomas,, ).
In this paper,
We investigate the per-decision importance sampling estimator (PDIS, Precup et al., ()).
The PDIS Monte Carlo estimator is defined as $\textstyle G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\doteq\sum_{k=t}^{T-1}
\rho_{t:k}R_{k+1},$
which can also be expressed recursively as

$$ $\displaystyle G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})=$ $\displaystyle\begin{cases}\rho_{t}\left(R_{t+1}+G^{\text{PDIS}}(\tau^{\mu_{t+1 :T-1}}_{t+1:T-1})\right)&t\in[T-2],\\ \rho_{t}R_{t+1}&t=T-1.\end{cases}$ (1) $$

With the classic policy coverage assumption (Precup et al.,, ; Maei,, ; Sutton et al.,, ; Zhang,, )

$$ $\displaystyle\forall t,s,a,\quad\mu_{t}(a|s)=0\implies\pi_{t}(a|s)=0,$ (2) $$

$G^{\text{PDIS}}$ provides an *unbiased* estimation for $J(\pi)$, i.e.,

$$ $\displaystyle\mathbb{E}\quantity[G^{\text{PDIS}}(\tau^{\mu_{0:T-1}}_{0:T-1})]= J(\pi).$ (3) $$

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 $\pi$, $\mathbb{E}_{a\sim\pi}[r(s,a)]$, with data collected by a behavior policy $\mu$, we adopt the importance sampling ratio (Rubinstein,, ) to reweigh the reward collected by $\mu$. That is, we use $\mathbb{E}_{a\sim\mu}[\rho(a|s)r(s,a)]$ as an estimator, where $\rho(a|s)=\frac{\pi(a|s)}{\mu(a|s)}$.
Recall $\Delta^{|\mathcal{A}|-1}$ is the probability simplex representing all probability distributions over the set $\mathcal{A}$.
To ensure that this off-policy evaluation is unbiased,
a classic choice by Rubinstein, () searches for $\mu$ in

$$ $\displaystyle\Lambda_{-}\doteq\quantity{\mu\mid\forall s,a,\mu(a|s)=0 \Rightarrow\pi(a|s)=0\wedge\forall s,\mu(\cdot|s)\in\Delta^{|\mathcal{A}|-1}}.$ (4) $$

In this work, we search in an enlarged space $\Lambda$ (Owen,, ; Liu and Zhang,, ), where

$$ $\displaystyle\Lambda\doteq\quantity{\mu\mid\forall s,a,\mu(a|s)=0\Rightarrow \pi(a|s)r(s,a)=0\wedge\forall s,\mu(\cdot|s)\in\Delta^{|\mathcal{A}|-1}}.$ (5) $$

Although a behavior policy $\mu$ in $\Lambda$ may not cover the target policy $\pi$, $\mu$ still gives unbiased estimation in statistics. In the following lemma, we show that searching for $\mu$ in this enlarged space $\Lambda$ guarantees unbiasedness in the contextual bandits setting.

###### Lemma 1 .

$\forall\mu\in\Lambda$, $\forall s$,

$$ $\displaystyle\mathbb{E}_{a\sim\mu}[\rho(a|s)r(s,a)]=\mathbb{E}_{a\sim\pi}[r(s, a)].$ (6) $$

Its proof is in Appendix A.1. Our goal is to search for a variance-minimizing behavior policy $\mu$. Except for the unbiasedness guaranteed by the search space $\Lambda$, we also require $\mu$ to satisfy safety constraints which will be defined later.
We formulate the variance minimization objective as, $\forall s$,

$$ $\displaystyle\min_{\mu\in\Lambda}\quad\mathbb{V}(\rho(a|s)r(s,a)).$ (7) $$

Then, with the unbiasedness in Lemma 1, we can further decompose the objective in (7) as

$$ $\displaystyle\mathbb{V}_{a\sim\mu}(\rho(a|s)r(s,a))$ (8) $\displaystyle=$ $\displaystyle\mathbb{E}_{a\sim\mu}[(\rho(a|s)r(s,a))^{2}]-\mathbb{E}_{a\sim\mu }[\rho(a|s)r(s,a)]^{2}$ (9) $\displaystyle=$ $\displaystyle\mathbb{E}_{a\sim\mu}[\rho(a|s)^{2}r(s,a)^{2}]-\mathbb{E}_{a\sim \pi}[r(s,a)]^{2}.$ (By Lemma 1 ) (10) $$

Since the second term is a constant and is unrelated to $\mu$, it suffices to solve

$$ $\displaystyle\min_{\mu\in\Lambda}\quad$ $\displaystyle\mathbb{E}_{a\sim\mu}[\rho(a|s)^{2}r(s,a)^{2}].$ (11) $$

Next, to ensure the safety of executing the behavior policy $\mu$, we incorporate a safety constraint into the variance minimization problem. Since measuring safety by the expected cost is a common approach in the safety RL community (Berkenkamp et al.,, ; Achiam et al.,, ; Chow et al.,, ), we require that the expected cost of $\mu$ remains within a threshold related to the expected cost of $\pi$.
Given a safety parameter $\epsilon\in[0,\infty)$, define a cost threshold

$$ $\displaystyle\delta_{\epsilon}(s)\doteq(1+\epsilon)\mathbb{E}_{a\sim\pi}[c(s,a )].$ (12) $$

We impose the following constraint to the optimization problem (11)

$$ $\displaystyle\mathbb{E}_{a\sim\mu}[c(s,a)]\leq\delta_{\epsilon}(s),\quad \forall s.$ (13) $$

This constraint requires 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$.
By satisfying this constraint, we maintain a desired level of safety during the execution of the behavior policy $\mu$. This safety is defined with respect to the target policy $\pi$, which is executed
in the classic on-policy evaluation method.
By setting $\epsilon=0$, behavior policies satisfying this constraint are guaranteed to be safer than the target policy.

Notably, another line of research focused on policy safety chooses a constant threshold for the expected cost. We can simply modify (13) into a constant-threshold constraint by replacing the threshold function $\delta_{\epsilon}(s)$ with a constant $\delta$.
However, such absolute thresholds may make optimization problems infeasible. Strong assumptions on environments and policies have to be made to guarantee the existence of feasible solutions under absolute threshold (Achiam et al.,, ).
In this paper, we impose the safety constraint with respect to the target policy $\pi$, because our goal is to design a safe behavior policy to address the high variance associated with classic on-policy evaluation methods.
The parameter $\epsilon$ in our threshold allows RL practitioners to adjust safety tolerance based on the specific requirements of the problem, as safety constraints are often highly problem-dependent (Achiam et al.,, ). In Section 7, we demonstrate our method in sequential reinforcement learning with a harsh threshold, $\epsilon=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 $\epsilon$ and $s$, the following optimization problem is convex and feasible.

$$ $\displaystyle\min_{\mu\in\Lambda}\quad$ $\displaystyle\mathbb{E}_{a\sim\mu}[\rho(a|s)^{2}r(s,a)^{2}],$ (14) s.t. $\displaystyle\mathbb{E}_{a\sim\mu}[c(s,a)]\leq\delta_{\epsilon}(s).$ (15) $$

Its proof is in Appendix A.2.
Use $\mu^{*}$ to denote the optimal solution of the above optimization problem. We have the following lemma.

###### Lemma 3 .

For all $\epsilon$ and $s$, let $\mu^{*}$ be the optimal solution of optimization problem (14), we have

$$ $\displaystyle\mathbb{V}_{a\sim\mu^{*}}(\rho(a|s)r(s,a))\leq\mathbb{V}_{a\sim \pi}(r(s,a)).$ (16) $$

###### Proof.

We first show that the target policy $\pi$ is always in the feasible set of the optimization problem (14). We define the set of feasible policies as

$$ $\displaystyle\textstyle\mathcal{F}\doteq\{\mu\in\Lambda\mid\forall\epsilon,s, \mathbb{E}_{a\sim\mu}[c(s,a)]\leq\delta_{\epsilon}(s)\}.$ (17) $$

Because $\epsilon\in[0,\infty)$, for the safety constraint, we have

$$ $\displaystyle\mathbb{E}_{a\sim\pi}[c(s,a)]\leq(1+\epsilon)\mathbb{E}_{a\sim\pi }[c(s,a)]=\delta_{\epsilon}(s).$ (18) $$

By the definition of $\Lambda$ (5), $\pi\in\Lambda$.
Thus, $\pi\in\mathcal{F}$.
Because

$$ $\displaystyle\mu^{*}\doteq$ $\displaystyle\mathop{argmin}_{\mu\in\mathcal{F}}\textstyle\mathbb{E}_{a\sim\mu }[\rho(a|s)^{2}r(s,a)^{2}]$ (19) $$

is the optimal solution, we have

$$ $\displaystyle\mathbb{V}_{a\sim\mu^{*}}(\rho(a|s)r(s,a))$ (20) $\displaystyle=$ $\displaystyle\mathbb{E}_{a\sim\mu^{*}}[\rho(a|s)^{2}r(s,a)^{2}]-\mathbb{E}_{a \sim\pi}[r(s,a)]^{2}$ (by ( 10 )) $\displaystyle\leq$ $\displaystyle\mathbb{E}_{a\sim\pi}[\rho(a|s)^{2}r(s,a)^{2}]-\mathbb{E}_{a\sim \pi}[r(s,a)]^{2}$ (by ( 19 )) $\displaystyle=$ $\displaystyle\textstyle\mathbb{E}_{a\sim\pi}[r(s,a)^{2}]-\mathbb{E}_{a\sim\pi} [r(s,a)]^{2}$ (21) $\displaystyle=$ $\displaystyle\mathbb{V}_{a\sim\pi}(r(s,a)).$ (22) $$

∎

In Section 5, we expand Lemma 2 and Lemma 3 from contextual bandits to sequential reinforcement learning in Theorem 1 and Theorem 2. We show that with a 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 $\mu^{*}$ that minimizes variance under safety constraints.

###### Lemma 1 .

###### Lemma 2 .

###### Lemma 3 .

###### Proof.

## 5 Constrained Variance Minimization for Sequential Reinforcement Learning

In this section, we extend the techniques from contextual bandits to the sequential reinforcement learning setting. We seek to find an optimal behavior policy $\mu$ that reduces the variance $\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{0:T-1}}_{0:T-1})\right)$ 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 $\mu$ in the set of all policies that cover the target policy $\pi$ (Sutton and Barto,, ), i.e.,

$$ $\displaystyle\Lambda_{-}\doteq\{$ $\displaystyle\mu\mid\forall t,s,a,\mu_{t}(a|s)=0\Rightarrow\pi_{t}(a|s)=0 \wedge\forall t,s,\mu_{t}(\cdot|s)\in\Delta^{|\mathcal{A}|-1}\}.$ (23) $$

In this paper, similar to the bandits setting (5), we search in an enlarged set $\Lambda$, which is defined as

$$ $\displaystyle\Lambda\doteq$ $\displaystyle\{\mu\mid\forall t,s,a,\mu_{t}(a|s)=0\Rightarrow\pi_{t}(a|s)q_{ \pi,t}(s,a)=0\wedge\forall t,s,\mu_{t}(\cdot|s)\in\Delta^{|\mathcal{A}|-1}\}.$ (24) $$

The following lemma from Liu and Zhang, () ensures the unbiasedness of the off-policy estimator with the behavior policy $\mu\in\Lambda$.

###### Lemma 4 .

$\forall\mu\in\Lambda$, $\forall t$, $\forall s$,

$$ $\displaystyle\mathbb{E}\left[G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S _{t}=s\right]=v_{\pi,t}(s).$ (25) $$

Its proof is in Appendix A.3.
A natural idea to do variance minimization under safety constraints with a safety parameter $\epsilon\in[0,\infty)$ is to solve the following optimization problem

$$ $\displaystyle\min_{\mu\in\Lambda}\quad$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{0:T-1}}_{0:T-1})\right),$ (26) s.t. $\displaystyle J^{c}(\mu)\leq(1+\epsilon),$ (27) $$

where $J^{c}(\mu)\doteq\sum_{s}p_{0}(s)v_{\mu,0}^{c}(s)$ is the expected cost of the behavior policy $\mu$. 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., () try to solve this problem without safety constraints by directly optimizing the behavior policy $\mu$ with gradient descent. However, this approach requires online data to optimize $\mu$ and struggles in even moderately complicated environments as shown in Zhong et al., () and Liu and Zhang, ().

In this paper, we therefore propose to solve this problem in a backward way while ensuring safety constraints.
Given an $\epsilon$,
use

$$ $\displaystyle\delta_{\epsilon,t}(s)\doteq(1+\epsilon)v^{c}_{\pi,t}(s)$ (28) $$

to denote the safety threshold.
We define an extended reward function $\tilde{r}_{t}(s,a)$ and a behavior policy $\mu^{*}$.
They are defined in the order of $\quantity{\tilde{r}_{T-1},\mu^{*}_{T-1},\tilde{r}_{T-2},\mu^{*}_{T-2},\cdots,
\tilde{r}_{0},\mu^{*}_{0}}$. Denote the variance of the state value for the next state
given the current state-action pair $(s,a)$ as $\nu_{\pi,t}(s,a)$.
We have

$$ $\displaystyle\textstyle\nu_{\pi,t}(s,a)\doteq$ $\displaystyle\begin{cases}0&t=T-1,\\ \mathbb{V}_{S_{t+1}}\left(v_{\pi,t+1}(S_{t+1})\mid S_{t}=s,A_{t}=a\right)&t\in [T-2].\end{cases}$ (29) $$

Then, the extended reward function is defined as

$$ $\displaystyle\textstyle\tilde{r}_{t}(s,a)\doteq$ $\displaystyle\begin{cases}r_{\pi,t}(s,a)^{2}&t=T-1,\\ \nu_{\pi,t}(s,a)+q_{\pi,t}(s,a)^{2}+\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left( G^{\text{PDIS}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid s,a \right]&t\in[T-2].\end{cases}$ (30) $$

The behavior policy $\mu_{t}^{*}$ is defined as the optimal solution to the following problem. $\forall t,s$,

$$ $\displaystyle\min_{\mu_{t}\in\Lambda}\quad$ $\displaystyle\mathbb{E}_{a\sim\mu_{t}}[\rho_{t}^{2}\tilde{r}_{t}(s,a)],$ (31) s.t. $\displaystyle\mathbb{E}_{a\sim\mu_{t}}[q^{c}_{\mu,t}(s,a)]\leq\delta_{\epsilon ,t}(s).$ (32) $$

We have the following theorem showing the convexity and feasibility of (33), thus ensuring the existence of the behavior policy $\mu^{*}$.

###### Theorem 1 .

For all $\epsilon$, $t$, and $s$, the following optimization problem is convex and feasible.

$$ $\displaystyle\min_{\mu_{t}\in\Lambda}\quad$ $\displaystyle\mathbb{E}_{a\sim\mu_{t}}[\rho_{t}^{2}\tilde{r}_{t}(s,a)],$ (33) s.t. $\displaystyle\mathbb{E}_{a\sim\mu_{t}}[q^{c}_{\mu,t}(s,a)]\leq\delta_{\epsilon ,t}(s).$ (34) $$

Its proof is in Appendix A.4. We notice that the constrained optimization problem (33) is similar to (14), which is the optimization problem introduced in Section 4.
In the contextual bandit setting (14), we optimize the objective with respect to the reward function $r$, ensuring variance reduction (Lemma 3).
In sequential reinforcement learning (33), we optimize with respect to the extended reward function $\tilde{r}$, achieving variance reduction (Theorem 2 and (36)), while simultaneously guaranteeing safety (37).
This observation provides a key insight: the step-wise optimization problem in sequential reinforcement learning can be viewed as a reduced optimization problem in one-step contextual bandits, where the reward is
$\tilde{r}$.
In Section 6, we further propose an efficient algorithm to learn
$\tilde{r}$
without directly addressing the complicated trajectory variance $\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)$, making long-horizon RL problems more tractable.

###### Theorem 2 .

The behavior policy $\mu^{*}$ reduces variance compared with the on-policy evaluation method.

$$ $\displaystyle\textstyle\forall t,s,\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{ *}_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)\leq\mathbb{V}\left(G^{\text{PDIS}}( \tau^{\pi_{t:T-1}}_{t:T-1})\mid S_{t}=s\right).$ (35) $$

Its proof is in Appendix A.5.
We also present the following theorem to demonstrate variance reduction and safety guarantee with respect to the original constrained optimization problem (26).

###### Theorem 3 .

For all $\epsilon$, the corresponding behavior policy $\mu^{*}$ has the following property

$$ $\displaystyle\text{1.}\quad\textstyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{{ \mu}^{*}_{0:T-1}}_{0:T-1})\right)\leq\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi _{0:T-1}}_{0:T-1})\right)$ (36) $\displaystyle\text{2.}\quad J^{c}(\mu^{*})\leq(1+\epsilon)J^{c}(\pi)$ (37) $$

Its proof is in Appendix A.6.

Figure: Algorithm 1 Safety-Constrained Optimal Policy Evaluation (SCOPE)

###### Lemma 4 .

###### Theorem 1 .

###### Theorem 2 .

###### Theorem 3 .

## 6 Learning the Optimal Behavior Policy

In this section, we propose an efficient algorithm to learn $\tilde{r}$ with previously logged offline data, and subsequently derive the optimal behavior policy $\mu^{*}$ under safety constraints.
We notice that learning $\tilde{r}$ by (30) is inefficient since we need to approximate the complicated variance $\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t}\right)$, which involves the entire future trajectory. To tackle this challenge, we present a recursive expression of $\tilde{r}$ in the following lemma.

###### Lemma 5 .

$\forall s,a$, when $t=T-1$, $\tilde{r}_{t}(s,a)=r_{\pi,t}(s,a)^{2}$. When $t\in[T-2]$,

$$ $\displaystyle\textstyle\tilde{r}_{t}(s,a)=2q_{\pi,t}(s,a)r(s,a)-r(s,a)^{2}+ \mathbb{E}_{s^{\prime}\sim p,a^{\prime}\sim\pi}\quantity[\frac{\pi_{t+1}(a^{ \prime}|s^{\prime})}{\mu^{*}_{t+1}(a^{\prime}|s^{\prime})}\tilde{r}_{\pi,t+1}( s^{\prime},a^{\prime})].$ (38) $$

Its proof is in Appendix A.7. With this lemma, we can learn $\tilde{r}$ recursively without approximating the complicated trajectory variance. Then, by (100) in the appendix, we can
also decompose the widely interested variance target in a succinct form

$$ $\displaystyle\underbrace{\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*}_{t:T-1} }_{t:T-1})\mid S_{t}=s\right)}_{\hypertarget{a}{(a)}}=\underbrace{\mathbb{E}_{ a\sim\mu}[\rho_{t}^{2}\tilde{r}_{t}(s,a)]}_{\hypertarget{b}{(b)}}-\underbrace{ v_{\pi,t}(s)^{2}}_{\hypertarget{c}{(c)}},\quad\forall s,t.$ (39) $$

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 a 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,, ; Liu and Zhang,, ).
With (39), we can approximate the variance of the off-policy estimator in a model-free way with only segmented offline data.

For broad applicability, we adopt the behavior policy-agnostic offline learning setting (Nachum et al.,, ), where the offline data has $m$ previously logged data tuples in the form of $\quantity{(t_{i},s_{i},a_{i},r_{i},c_{i},s_{i}^{\prime})}_{i=1}^{m}$. These data tuples can be generated by one or multiple possibly unknown behavior policies, and they are not required to form a complete trajectory. In the $i$-th data tuple, $t_{i}$ is the time step, $s_{i}$ is the state at time step $t_{i}$, $a_{i}$ is the action taken, $r_{i}$ is the observed reward, $c_{i}$ is the observed cost, and $s_{i}^{\prime}$ is the successor state.
In this paper, we learn $\tilde{r}$ from previously logged offline data.
Previously logged offline data are cheap and readily available compared with online data. This makes them a great engine for improving policy evaluation in the online phase.
Compared with gradient-based methods (Hanna et al.,, ; Zhong et al.,, ) which need complete online trajectories, our method does not require a long online warm-up time to find a good behavior policy because we are able to utilize offline data.
Subsequently, the optimal variance-reducing behavior policy $\mu^{*}$ under safety constraints is approximated through standard convex optimization solvers (Nocedal and Wright,, ; Agrawal et al.,, ).

###### Lemma 5 .

## 7 Empirical Results

In this section, we show the empirical results comparing our methods against three baselines: (1) the on-policy Monte Carlo estimator,
(2) the robust on-policy sampling estimator (ROS, Zhong et al., ()), and
(3) the offline data informed estimator (ODI, Liu and Zhang, ()). To ensure our method attains lower cost and is thus even safer than the on-policy estimator, we choose $\epsilon=0$ in the threshold $\delta_{\epsilon,t}$ (28).
All methods
learn their required parameters from the same offline dataset to ensure fair comparisons.
Given previously logged offline data, our method learns the optimal behavior policy
under safety constraints
using Algorithm 1.

We name our algorithm Safety-Constrained Optimal Policy Evaluation (SCOPE) to emphasize that safety constraints are inherently considered in the design of the variance-minimizing behavior policy, unlike previous methods that overlook safety concerns. A metaphor for SCOPE is that it builds a bridge focused on efficient transportation (evaluation efficiency) while simultaneously ensuring traffic safety (satisfying safety constraints).

Figure: Figure 1: 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.
Refer to caption: x1.png

**Table 1: 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.**
| 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 |

Gridworld:
We first conduct experiments in Gridworld with $n^{3}$ states. Each Gridworld is an $n\times n$ 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 $n^{3}=1,000$ and $n^{3}=27,000$ number of states, which are the largest Gridworld environments tested among related works (Zhong et al.,, ; Liu and Zhang,, ).
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 2, 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 $1$. In Figure 2, we report the estimation error against
the total cost of execution.

If considering solely variance reduction, Figure 2 shows our method outperforms the on-policy estimator and ROS by a large margin.
Admittedly, ODI (Liu and Zhang,, ) is slightly better than our method in terms of variance reduction. However, this slight advantage comes with a huge trade-off of safety. As shown in Table 1, ODI has a 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 budget. 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-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 $1$ 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—ensuring safety constraints along with the variance minimization leads to a low-cost method. Also, notably, our estimator outperforms the on-policy and ROS estimators in reducing both variance and cost.

MuJoCo:
We also conduct experiments in MuJoCo robot simulation tasks (Todorov et al.,, ).
MuJoCo is a physics engine containing various stochastic environments, where the goal is to control a robot to achieve different behaviors such as walking, jumping, and balancing.

As confirmed in Table 3 and Table 4 in the appendix, our method is 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 to achieve the desired evaluation accuracy.
More experiment details are in Appendix B. It is worth mentioning that our method is robust to hyperparameter choices—all hyperparameters in our method are tuned offline and stay the same across all environments.

Figure: Figure 3: Results on MuJoCo. Cost budget on the x-axis is 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.
Refer to caption: x3.png

**Table 2: Cost needed to achieve the same of estimation accuracy that on-policy Monte Carlo achieves with $1000$ episodes on MuJoCo. Standard errors are plotted in Figure 3.**
|  | 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 - 552)/1000 = 44.8% |
| I. D. Pendulum | 1000 | 681 | 1014 | 1003 | (1000 - 681)/1000 = 31.9% |
| I. Pendulum | 1000 | 425 | 615 | 890 | (1000 - 425)/1000 = 57.5% |
| Walker | 1000 | 694 | 1031 | 960 | (1000 - 694)/1000 = 30.6% |

## 8 Conclusion

In reinforcement learning, due to the sequential nature, policy evaluation often suffers from large variance and requires massive data to achieve the desired level of accuracy. In addition, safety is a 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 variance-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 a promising direction for addressing long-horizon sequential reinforcement learning challenges.

Empirically, compared with existing best-performing methods, we show our method is 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—perhaps containing merely a single data tuple—the learned behavior policy in our method may be inaccurate. In this case, for a safe backup, we recommend the on-policy evaluation method. The future work of our paper is to extend the constrained variance minimization technique to temporal difference learning.

## 9 Acknowledgements

This work is supported in part by the US National Science Foundation (NSF) under grants III-2128019 and SLES-2331904.

## Appendix A Proofs

### A.1 Proof of Lemma 1

###### Proof.

$\forall s$, $\forall\mu\in\Lambda$,

$$ $\displaystyle\mathbb{E}_{a\sim\mu}[\rho(a|s)r(s,a)]=$ $\displaystyle\sum_{a\in\{a|\mu(a|s)>0\}}\mu(a|s)\frac{\pi(a|s)}{\mu(a|s)}r(s,a)$ (40) $\displaystyle=$ $\displaystyle\sum_{a\in\{a|\mu(a|s)>0\}}\pi(a|s)r(s,a)$ (41) $\displaystyle=$ $\displaystyle\sum_{a\in\{a|\mu(a|s)>0\}}\pi(a|s)r(s,a)+\sum_{a\in\{a|\mu(a|s)= 0\}}\pi(a|s)r(s,a)$ ( $\mu\in\Lambda$ ) $\displaystyle=$ $\displaystyle\sum_{a}\pi(a|s)r(s,a)$ (42) $\displaystyle=$ $\displaystyle\mathbb{E}_{a\sim\pi}[r(s,a)].$ (43) $$

∎

###### Proof.

### A.2 Proof of Lemma 2

###### Proof.

To prove Lemma 2, we express the objective function as

$$ $\displaystyle\mathbb{E}_{a\sim\mu}[\rho(a|s)^{2}r(s,a)^{2}]=\sum_{a\in\{a|\mu( a|s)>0\}}\frac{\pi(a|s)^{2}r(s,a)^{2}}{\mu(a|s)}.$ (44) $$

To prove the problem is convex, we begin by examining the feasible set of each constraint separately.

In the first constraint of $\Lambda$ (5),

$$ $\displaystyle\forall s,a,\mu(a|s)=0\implies\pi(a|s)r(s,a)=0.$ (45) $$

The feasible set of (45) is a linear subspace of $\mathbb{R}^{|\mathcal{A}|}$ defined by a set of linear equations. Thus, this feasible set is convex.

Next, we decompose the other constraint of $\Lambda$ (5), $\mu(\cdot|s)\in\Delta^{|\mathcal{A}|-1}$ $\forall s$, into two subconstraints:

$$ $\displaystyle\sum_{a}\mu(a|s)=1,$ (46) $\displaystyle\forall a,\mu(a|s)\geq 0.$ (47) $$

For all $s$, the feasible set in (46) can be written in the vector form as

$$ $\displaystyle\mathbf{1}^{T}\overrightarrow{\mu_{s}}=1,$ (48) $$

where $\mathbf{1}\in\mathbb{R}^{|\mathcal{A|}}$ is the vector of ones defined as

$$ $\displaystyle\mathbf{1}\doteq\begin{bmatrix}1\\ \vdots\\ 1\end{bmatrix},$ (49) $$

and $\overrightarrow{\mu_{s}}\in\mathbb{R}^{|\mathcal{A}|}$ is defined as

$$ $\displaystyle\overrightarrow{\mu_{s}}\doteq\begin{bmatrix}\mu(a_{1}|s)\\ \vdots\\ \mu(a_{|\mathcal{A}|}|s)\end{bmatrix}.$ (50) $$

Since (48) is linear, the constraint (46) is affine and thus convex (Boyd et al.,, ).

For all $s$, the feasible set of
(47) is the non-negative orthant, defined as

$$ $\displaystyle\mathbb{R}_{+}^{|\mathcal{A}|}\doteq\{\mu(\cdot|s)\in\mathbb{R}^{ |\mathcal{A}|}\mid\mu(a|s)\geq 0,\forall a\}.$ (51) $$

Since the non-negative orthant forms a convex cone and is known to be a convex set (Boyd et al.,, ), we conclude that this constraint’s feasible set is convex.

Next, we define the vector of costs for all $s$ as

$$ $\displaystyle\mathbf{c}_{s}\doteq\begin{bmatrix}c(s,a_{1})\\ \vdots\\ c(s,a_{|\mathcal{A}|})\end{bmatrix}.$ (52) $$

Then, for all $\epsilon$ and $s$, the safety constraint (15) can be rewritten as

$$ $\displaystyle\mathbf{c}_{s}^{\top}\overrightarrow{\mu_{s}}\leq\delta_{\epsilon }(s),$ (53) $$

which is a linear inequality in $\mu$. Thus, its feasible set is in a convex half-space. Because all the constraints are convex, we conclude that the feasible set $\mathcal{F}$ in (17) is convex.

Finally, we examine the minimization objective (14), where $\pi$ and $r$ are fixed and independent of the behavior policy $\mu$. For all $s$, we express the objective function as

$$ $\displaystyle\mathbb{E}_{a\sim\mu}[\rho(a|s)^{2}r(s,a)^{2}]=\sum_{a\in\{a|\mu( a|s)>0\}}\frac{\pi(a|s)^{2}r(s,a)^{2}}{\mu(a|s)}.$ (54) $$

Then, for each $a$,
we decompose the objective function as

$$ $\displaystyle f_{a}(\mu(a|s))\doteq\frac{\pi(a|s)^{2}r(s,a)^{2}}{\mu(a|s)}.$ (55) $$

Taking the first and second derivatives of $f_{a}$, we get

$$ $\displaystyle f^{\prime}_{a}(\mu(a|s))=-\frac{\pi(a|s)^{2}r(s,a)^{2}}{\mu(a|s) ^{2}},$ (56) $\displaystyle f^{\prime\prime}_{a}(\mu(a|s))=\frac{2\pi(a|s)^{2}r(s,a)^{2}}{ \mu(a|s)^{3}}.$ (57) $$

Since $\forall s,a$, $f^{\prime\prime}_{a}(\mu(a|s))\geq 0$, we know that (55) is convex for all $a$. Then, as a summation of convex functions, (14) is also convex.
In conclusion, by the convexity of the feasible set $\mathcal{F}$ and the objective function (14), we obtain the convexity of the constrained optimization problem in Lemma 2.

For feasibility, note that by Lemma 3, $\pi\in\mathcal{F}$, which is the feasible set. Thus, we confirm the feasibility in Lemma 2.

∎

###### Proof.

### A.3 Proof of Lemma 4

###### Proof.

We proceed via induction.
For $t=T-1$,
we have

$$ $\displaystyle\mathbb{E}\left[G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S _{t}\right]=$ $\displaystyle\mathbb{E}\left[\rho_{t}R_{t+1}\mid S_{t}\right]=\mathbb{E}\left[ \rho_{t}q_{\pi,t}(S_{t},A_{t})\mid S_{t}\right]$ (58) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}(\cdot\mid S_{t})}\left[q_{\pi,t}(S_{ t},A_{t})\mid S_{t}\right]$ (Lemma 1 ) $\displaystyle=$ $\displaystyle v_{\pi,t}(S_{t}).$ (59) $$

For $t\in[T-2]$,
we have

$$ $\displaystyle\mathbb{E}\left[G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S _{t}\right]$ (60) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\rho_{t}R_{t+1}+\rho_{t}G^{\text{PDIS}}(\tau^{\mu _{t+1:T-1}}_{t+1:T-1})\mid S_{t}\right]$ (61) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\rho_{t}R_{t+1}\mid S_{t}\right]+\mathbb{E}\left[ \rho_{t}G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t}\right]$ (62) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\rho_{t}R_{t+1}\mid S_{t}\right]+\mathbb{E}_{A_{t }\sim\mu_{t}(\cdot\mid S_{t}),S_{t+1}\sim p(\cdot\mid S_{t},A_{t})}\left[ \mathbb{E}\left[\rho_{t}G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_ {t},A_{t},S_{t+1}\right]\mid S_{t}\right]$ (Law of total expectation) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\rho_{t}R_{t+1}\mid S_{t}\right]+\mathbb{E}_{A_{t }\sim\mu_{t}(\cdot\mid S_{t}),S_{t+1}\sim p(\cdot\mid S_{t},A_{t})}\left[\rho_ {t}\mathbb{E}\left[G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1} \right]\mid S_{t}\right]$ (Conditional independence and Markov property) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\rho_{t}R_{t+1}\mid S_{t}\right]+\mathbb{E}_{A_{t }\sim\mu_{t}(\cdot\mid S_{t}),S_{t+1}\sim p(\cdot\mid S_{t},A_{t})}\left[\rho_ {t}v_{\pi,t+1}(S_{t+1})\mid S_{t}\right]$ (Inductive hypothesis) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}(\cdot\mid S_{t})}\left[\rho_{t}q_{ \pi,t}(S_{t},A_{t})\mid S_{t}\right]$ (Definition of $q_{\pi,t}$ ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}(\cdot\mid S_{t})}\left[q_{\pi,t}(S_{ t},A_{t})\mid S_{t}\right]$ (Lemma 1 ) $\displaystyle=$ $\displaystyle v_{\pi,t}(S_{t}),$ (63) $$

which completes the proof.
∎

###### Proof.

### A.4 Proof of Theorem 1

###### Proof.

We first define the set of feasible policies as

$$ $\displaystyle\textstyle\mathcal{F}\doteq\{\mu\in\Lambda\mid\forall\epsilon,t,s ,\mathbb{E}_{a\sim\mu_{t}}[v^{c}_{\mu,t}(s)]\leq\delta_{\epsilon,t}(s)\}.$ (64) $$

We begin by examining each constraint.
In the first constraint of $\Lambda$ (24),

$$ $\displaystyle\forall t,s,a,\mu_{t}(a|s)=0\implies\pi_{t}(a|s)q_{\pi,t}(s,a)=0.$ (65) $$

The feasible set of (65) is a linear subspace of $\mathbb{R}^{|\mathcal{A}|}$ defined by a set of linear equations. Thus, this feasible set is convex.

Next, we decompose the other constraint of $\Lambda$ (24), $\mu_{t}(\cdot|s)\in\Delta^{|\mathcal{A}|-1}$, into two constraints:

$$ $\displaystyle\sum_{a}\mu_{t}(a|s)=1,$ (66) $\displaystyle\forall a,\mu_{t}(a|s)\geq 0.$ (67) $$

For all $t$ and $s$, in (66), the feasible set can be written as

$$ $\displaystyle\mathbf{1}^{\top}\overrightarrow{\mu_{s,t}}=1,$ (68) $$

where $\mathbf{1}\in\mathbb{R}^{|\mathcal{A|}}$ is the vector of ones
and $\overrightarrow{\mu_{s,t}}\in\mathbb{R}^{|\mathcal{A}|}$ is defined as

$$ $\displaystyle\overrightarrow{\mu_{s,t}}\doteq\begin{bmatrix}\mu_{t}(a_{1}|s)\\ \vdots\\ \mu_{t}(a_{|\mathcal{A}|}|s)\end{bmatrix}.$ (69) $$

Since (68) is linear, the feasible set of constraint (66) is affine and thus convex (Boyd et al.,, ).

For all $t$ and $s$, the feasible set for the constraint in (67) is the non-negative orthant, defined as

$$ $\displaystyle\mathbb{R}_{+}^{|\mathcal{A}|}\doteq\{\mu_{t}(\cdot|s)\in\mathbb{ R}^{|\mathcal{A}|}\mid\mu_{t}(a|s)\geq 0,\forall a\}.$ (70) $$

Since the non-negative orthant forms a convex cone and is known to be a convex set (Boyd et al.,, ), we conclude that this constraint is convex.

Next, we define the vector of the state-action value function for the cost $c$ for each $s$ as

$$ $\displaystyle\mathbf{q}_{\mu,t}\doteq\begin{bmatrix}q^{c}_{\mu,t}(s,a_{1})\\ \vdots\\ q^{c}_{\mu,t}(s,a_{|\mathcal{A}|})\end{bmatrix}.$ (71) $$

Then, for all $\epsilon$, $t$ and $s$, the safety constraint (34) can be rewritten as

$$ $\displaystyle\mathbf{q}_{\mu,t}^{\top}\overrightarrow{\mu_{s,t}}\leq\delta_{ \epsilon,t}(s),$ (72) $$

which is a linear inequality in $\mu_{t}$. Thus, its feasible set is a convex half-space. Because all the constraints’ feasible sets are convex, we conclude that the feasible set $\mathcal{F}$ in (64) is convex.

To prove Theorem 1, we express the objective function as

$$ $\displaystyle\mathbb{E}_{a\sim\mu_{t}}[\rho_{t}^{2}\tilde{r}_{t}(s,a)]=\sum_{a \in\{a|\mu_{t}(a|s)>0\}}\frac{\pi_{t}(a|s)^{2}\tilde{r}_{t}(s,a)}{\mu_{t}(a|s)},$ (73) $$

where $\tilde{r}$ in (30) is defined as

$$ $\displaystyle\textstyle\tilde{r}_{t}(s,a)\doteq$ $\displaystyle\begin{cases}r_{\pi,t}(s,a)^{2}&t=T-1,\\ \nu_{\pi,t}(s,a)+q_{\pi,t}(s,a)^{2}+\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left( G^{\text{PDIS}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid s,a \right]&t\in[T-2].\end{cases}$ (74) $$

Here, $\tilde{r}_{t}$ can be learned with logged offline data, as detailed in Algorithm 1, and it is unrelated to $\mu_{t}$.
Then, for each $a$,
we decompose the objective function as

$$ $\displaystyle f_{a}(\mu_{t}(a|s))\doteq\frac{\pi_{t}(a|s)^{2}\tilde{r}_{t}(s,a )}{\mu_{t}(a|s)}.$ (75) $$

Taking the first and second derivatives of $f_{a}$, we get

$$ $\displaystyle f^{\prime}_{a}(\mu_{t}(a|s))=-\frac{\pi_{t}(a|s)^{2}\tilde{r}(s, a)}{\mu_{t}(a|s)^{2}},$ (76) $\displaystyle f^{\prime\prime}_{a}(\mu_{t}(a|s))=\frac{2\pi_{t}(a|s)^{2}\tilde {r}(s,a)}{\mu_{t}(a|s)^{3}}.$ (77) $$

Notice that the extended reward $\tilde{r}$ defined in (30) is non-negative, since all the summands are non-negative.
Thus, $\forall t,s,a$, $f^{\prime\prime}_{a}(\mu_{t}(a|s))\geq 0$, and we know that (75) is convex for all $a$. Then, as a summation of convex functions, (33) is also convex.
In conclusion, by the convexity of the feasible set $\mathcal{F}$ and the objective function (33), we obtain the convexity of the constrained optimization problem in Theorem 1.

For feasibility, we show that the set of feasible policies (64) is non-empty.
Because $\epsilon\in[0,\infty)$, for the safety constraint, we have

$$ $\displaystyle\mathbb{E}_{a\sim\pi_{t}}[v^{c}_{\mu,t}(s)]\leq(1+\epsilon) \mathbb{E}_{a\sim\pi_{t}}[v^{c}_{\mu,t}(s)]=\delta_{\epsilon,t}(s).$ (78) $$

By the definition of $\Lambda$ (24), $\forall t$, $\pi_{t}\in\Lambda$.
Therefore, the set of feasible policies (64) is non-empty. Thus, the constrained optimization problem in Theorem 1 is feasible.
∎

###### Proof.

### A.5 Proof of Theorem 2

To prove Theorem 2, we first restate a recursive expression of the variance $\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}\right)$ for all $\mu\in\Lambda$ from Liu and Zhang, (), and present its proof for completeness.

###### Lemma 6 .

For any $\mu\in\Lambda$, for $t=T-1$,

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S _{t}\right)=\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}q_{\pi,t}^{2}(S_{t} ,A_{t})\mid S_{t}\right]-v_{\pi,t}^{2}(S_{t}),$ (79) $$

for $t\in[T-2]$,

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S _{t}\right)$ (80) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{ S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1}) \mid S_{t}\right)\mid S_{t},A_{t}\right]+\nu_{\pi,t}(S_{t},A_{t})+q_{\pi,t}^{2 }(S_{t},A_{t})\right)\mid S_{t}\right]$ (81) $\displaystyle-v_{\pi,t}^{2}(S_{t}).$ (82) $$

###### Proof.

For completeness, we provide the proof from Liu and Zhang, ().
We proceed via induction.
When $t=T-1$, we have

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S _{t}\right)=$ $\displaystyle\mathbb{V}\left(\rho_{t}r(S_{t},A_{t})\mid S_{t}\right)$ (83) $\displaystyle=$ $\displaystyle\mathbb{V}\left(\rho_{t}q_{\pi,t}(S_{t},A_{t})\mid S_{t}\right)$ (84) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}q_{\pi,t}(S_{t},A_{t})^{2} \mid S_{t}\right]-v_{\pi,t}(S_{t})^{2},$ (85) $$

When $t\in[T-2]$, we have

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S _{t}\right)$ (86) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu _{t:T-1}}_{t:T-1})\mid S_{t},A_{t}\right)\mid S_{t}\right]+\mathbb{V}_{A_{t}} \left(\mathbb{E}\left[G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t},A_ {t}\right]\mid S_{t}\right)$ (Law of total variance) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\mathbb{V}\left(r(S_{t},A_{t} )+G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right)\mid S _{t}\right]$ (87) $\displaystyle+\mathbb{V}_{A_{t}}\left(\rho_{t}\mathbb{E}\left[r(S_{t},A_{t})+G ^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right]\mid S_{t }\right)$ (By ( 1 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\mathbb{V}\left(G^{\text{PDIS }}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right)\mid S_{t}\right]+ \mathbb{V}_{A_{t}}\left(\rho_{t}\mathbb{E}\left[r(S_{t},A_{t})+G^{\text{PDIS}} (\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right]\mid S_{t}\right)$ (Deterministic reward $r$ ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\mathbb{V}\left(G^{\text{PDIS }}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right)\mid S_{t}\right]+ \mathbb{V}_{A_{t}}\left(\rho_{t}q_{\pi,t}(S_{t},A_{t})\mid S_{t}\right).$ (88) $$

Further decomposing the first term, we have

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1}) \mid S_{t},A_{t}\right)$ (89) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{ \mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t},S_{t+1}\right)\mid S_{t},A_{t}\right]$ (90) $\displaystyle+\mathbb{V}_{S_{t+1}}\left(\mathbb{E}\left[G^{\text{PDIS}}(\tau^{ \mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t},S_{t+1}\right]\mid S_{t},A_{t}\right)$ (Law of total variance) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{ \mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\mathbb{V} _{S_{t+1}}\left(\mathbb{E}\left[G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1} )\mid S_{t+1}\right]\mid S_{t},A_{t}\right)$ (Markov property) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{ \mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\mathbb{V} _{S_{t+1}}\left(v_{\pi,t+1}(S_{t+1})\mid S_{t},A_{t}\right).$ (Lemma 4 ) $$

Then, plugging (89) back to (86) yields

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S _{t}\right)$ (91) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{S_{t+1}} \left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t +1}\right)\mid S_{t},A_{t}\right]+\mathbb{V}_{S_{t+1}}(v_{\pi,t}(S_{t+1})\mid S _{t}=s,A_{t}=a)\right)\mid S_{t}\right]$ (92) $\displaystyle+\mathbb{V}_{A_{t}}\left(\rho_{t}q_{\pi,t}(S_{t},A_{t})\mid S_{t}\right)$ (93) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{S_{t+1}} \left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t +1}\right)\mid S_{t},A_{t}\right]+\mathbb{V}_{S_{t+1}}(v_{\pi,t}(S_{t+1})\mid S _{t}=s,A_{t}=a)\right)\mid S_{t}\right]$ (94) $\displaystyle+\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}q_{\pi,t}(S_{t},A_{t})^{2} \mid S_{t}\right]-\left(\mathbb{E}_{A_{t}}\left[\rho_{t}q_{\pi,t}(S_{t},A_{t}) \mid S_{t}\right]\right)^{2}$ (95) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{S_{t+1}} \left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t +1}\right)\mid S_{t},A_{t}\right]+\mathbb{V}_{S_{t+1}}(v_{\pi,t}(S_{t+1})\mid S _{t}=s,A_{t}=a)\right)\mid S_{t}\right]$ (96) $\displaystyle+\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}q_{\pi,t}(S_{t},A_{t})^{2} \mid S_{t}\right]-v_{\pi,t}(S_{t})^{2},$ (Lemma 1 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{S_{t+1}} \left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t +1}\right)\mid S_{t},A_{t}\right]+\nu_{\pi,t}(S_{t},A_{t})+q_{\pi,t}(S_{t},A_{ t})^{2}\right)\mid S_{t}\right]$ (97) $\displaystyle-v_{\pi,t}(S_{t})^{2},$ (Definition of $\nu$ ) $$

which completes the proof.
∎

Then, with the extended reward $\tilde{r}$ in (30) defined as

$$ $\displaystyle\textstyle\tilde{r}_{t}(s,a)\doteq$ $\displaystyle\begin{cases}r_{\pi,t}(s,a)^{2}&t=T-1,\\ \nu_{\pi,t}(s,a)+q_{\pi,t}(s,a)^{2}+\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left( G^{\text{PDIS}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid s,a \right]&t\in[T-2],\end{cases}$ (99) $$

we can express the variance in a succinct form

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1}) \mid S_{t}=s\right)=\mathbb{E}_{a\sim\mu}[\rho_{t}^{2}\tilde{r}_{t}(s,a)]-v_{ \pi,t}(s)^{2},\quad\forall s,t.$ (100) $$

Now, we restate Theorem 2 and present its proof.
See 2
In Appendix A.4, we show that $\forall t$, $\pi_{t}\in\mathcal{F}$, where $\mathcal{F}$ in (64) is the set of feasible policies for the constrained optimization problem in Theorem 1. Recall that $\mu_{t}^{*}$ is defined as the optimal solution to the problem (33), i.e.,

$$ $\displaystyle\mu^{*}_{t}\doteq$ $\displaystyle\mathop{argmin}_{\mu_{t}\in\mathcal{F}}\textstyle\mathbb{E}_{a \sim\mu_{t}}[\rho^{2}_{t}\tilde{r}(s,a)].$ (101) $$

Thus, $\forall t,s$,

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1}) \mid S_{t}=s\right)$ (102) $\displaystyle=$ $\displaystyle\mathbb{E}_{a\sim\mu^{*}_{t}}[\rho_{t}^{2}\tilde{r}_{t}(s,a)]-v_{ \pi,t}(s)^{2}$ (By ( 100 ) ) $\displaystyle\leq$ $\displaystyle\mathbb{E}_{a\sim\pi_{t}}[\rho_{t}^{2}\tilde{r}_{t}(s,a)]-v_{\pi, t}(s)^{2}$ (By ( 101 ) and $\pi_{t}\in\mathcal{F}$ ) $\displaystyle=$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S _{t}=s\right),$ (By ( 100 ) ) $$

which completes the proof.

###### Lemma 6 .

###### Proof.

### A.6 Proof of Theorem 3

###### Proof.

We first prove the variance reduction property.

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*}_{0:T-1}}_{0:T-1})\right)$ (103) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{0}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu ^{*}_{0:T-1}}_{0:T-1})\mid S_{0}\right)\right]+\mathbb{V}_{S_{0}}\left(\mathbb {E}\left[G^{\text{PDIS}}(\tau^{\mu^{*}_{0:T-1}}_{0:T-1})\mid S_{0}\right]\right)$ (Law of Total Variance) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{0}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu ^{*}_{0:T-1}}_{0:T-1})\mid S_{0}\right)\right]+\mathbb{V}_{S_{0}}\left(v_{\pi, 0}(S_{0})\right)$ (By Lemma 4 and $\mu^{*}\in\Lambda$ ) $\displaystyle\leq$ $\displaystyle\mathbb{E}_{S_{0}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi _{0:T-1}}_{0:T-1})\mid S_{0}\right)\right]+\mathbb{V}_{S_{0}}\left(v_{\pi,0}(S _{0})\right)$ (Theorem 2 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{0}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi _{0:T-1}}_{0:T-1})\mid S_{0}\right)\right]+\mathbb{V}_{S_{0}}\left(\mathbb{E} \left[G^{\text{PDIS}}(\tau^{\pi_{0:T-1}}_{0:T-1})\mid S_{0}\right]\right)$ (By Lemma 4 and $\pi\in\Lambda$ ) $\displaystyle=$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{0:T-1}}_{0:T-1})\right).$ (Law of Total Variance) $$

Next, we prove the safety constraint satisfaction.

$$ $\displaystyle J^{c}(\mu^{*})$ (104) $\displaystyle=$ $\displaystyle\sum_{s}p_{0}(s)v^{c}_{\mu^{*},0}(s)$ (105) $\displaystyle=$ $\displaystyle\sum_{s}p_{0}(s)\mathbb{E}_{a\sim\mu^{*}_{0}}[q^{c}_{\mu^{*},0}(s ,a)]$ (106) $\displaystyle\leq$ $\displaystyle\sum_{s}p_{0}(s)\delta_{\epsilon,0}(s)$ (Theorem 1 ) $\displaystyle=$ $\displaystyle\sum_{s}p_{0}(s)(1+\epsilon)v^{c}_{\pi,0}(s)$ (By ( 28 )) $\displaystyle=$ $\displaystyle(1+\epsilon)\sum_{s}p_{0}(s)v^{c}_{\pi,0}(s)$ (107) $\displaystyle=$ $\displaystyle(1+\epsilon)J^{c}(\pi),$ (108) $$

which completes the proof.
∎

###### Proof.

### A.7 Proof of Lemma 5

###### Proof.

$\forall s,a$, when $t=T-1$, $\tilde{r}_{t}(s,a)=r_{\pi,t}(s,a)^{2}$, as defined in (30). For $t\in[T-2]$,

$$ $\displaystyle\tilde{r}_{t}(s,a)$ (109) $\displaystyle=$ $\displaystyle\nu_{\pi,t}(s,a)+q_{\pi,t}(s,a)^{2}+\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }\right)\mid s,a\right]$ (By ( 30 )) $\displaystyle=$ $\displaystyle\nu_{\pi,t}(s,a)+q_{\pi,t}(s,a)^{2}$ (110) $\displaystyle+\sum_{s^{\prime}}p(s^{\prime}|s,a)\left[\mathbb{E}_{A_{t+1}\sim \mu^{*}_{t+1}}\left[\rho_{t+1}^{2}\left(\mathbb{E}_{S_{t+2}}\left[\mathbb{V} \left(G^{\text{PDIS}}(\tau^{\mu^{*}_{t+2:T-1}}_{t+2:T-1})\mid S_{t+2}\right) \mid S_{t+1},A_{t+1}\right]\right.\right.\right.$ (111) $\displaystyle\left.\left.\left.+\nu_{\pi,t+1}(S_{t+1},A_{t+1})+q_{\pi,t+1}(S_{ t+1},A_{t+1})^{2}\right)\mid S_{t+1}=s^{\prime}\right]-v_{\pi,t+1}(s^{\prime}) ^{2}\right]$ (By Lemma 6 ) $\displaystyle=$ $\displaystyle\nu_{\pi,t}(s,a)+q_{\pi,t}(s,a)^{2}+\sum_{s^{\prime}}p(s^{\prime} |s,a)\left[\mathbb{E}_{A_{t+1}\sim\mu^{*}_{t+1}}\quantity[\rho_{t+1}^{2}\tilde {r}_{\pi,t+1}(S_{t+1},A_{t+1})\mid S_{t+1}=s^{\prime}]\right.$ (112) $\displaystyle\left.-v_{\pi,t+1}(s^{\prime})^{2}\right]$ (By ( 30 )) $\displaystyle=$ $\displaystyle\nu_{\pi,t}(s,a)+q_{\pi,t}(s,a)^{2}+\sum_{s^{\prime},a^{\prime}}p (s^{\prime}|s,a)\quantity[\rho_{t+1}\pi_{t+1}(a^{\prime}|s^{\prime})\tilde{r}_ {\pi,t+1}(s^{\prime},a^{\prime})-v_{\pi,t+1}(s^{\prime})^{2}].$ (113) $\displaystyle=$ $\displaystyle\mathbb{V}_{S_{t+1}}\left(v_{\pi,t+1}(S_{t+1})\mid S_{t}=s,A_{t}= a\right)+q_{\pi,t}(s,a)^{2}$ (114) $\displaystyle+\sum_{s^{\prime},a^{\prime}}p(s^{\prime}|s,a)\quantity[\rho_{t+1 }\pi_{t+1}(a^{\prime}|s^{\prime})\tilde{r}_{\pi,t+1}(s^{\prime},a^{\prime})-v_ {\pi,t+1}(s^{\prime})^{2}]$ (Definition of $\nu$ ) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{t+1}}\left[v_{\pi,t+1}(S_{t+1})^{2}\mid S_{t}=s,A_ {t}=a\right]-\mathbb{E}_{S_{t+1}}\left[v_{\pi,t+1}(S_{t+1})\mid S_{t}=s,A_{t}= a\right]^{2}$ (115) $\displaystyle+q_{\pi,t}(s,a)^{2}+\sum_{s^{\prime},a^{\prime}}p(s^{\prime}|s,a) \quantity[\rho_{t+1}\pi_{t+1}(a^{\prime}|s^{\prime})\tilde{r}_{\pi,t+1}(s^{ \prime},a^{\prime})-v_{\pi,t+1}(s^{\prime})^{2}]$ (116) $\displaystyle=$ $\displaystyle\sum_{s^{\prime}}p(s^{\prime}|s,a)v_{\pi,t+1}(s^{\prime})^{2}-(q_ {\pi,t}(s,a)-r(s,a))^{2}+q_{\pi,t}(s,a)^{2}$ (117) $\displaystyle+\sum_{s^{\prime},a^{\prime}}p(s^{\prime}|s,a)\rho_{t+1}\pi_{t+1} (a^{\prime}|s^{\prime})\tilde{r}_{\pi,t+1}(s^{\prime},a^{\prime})-\sum_{s^{ \prime}}p(s^{\prime}|s,a)v_{\pi,t+1}(s^{\prime})^{2}$ (118) $\displaystyle=$ $\displaystyle 2q_{\pi,t}(s,a)r(s,a)-r(s,a)^{2}+\sum_{s^{\prime},a^{\prime}}p(s ^{\prime}|s,a)\rho_{t+1}\pi_{t+1}(a^{\prime}|s^{\prime})\tilde{r}_{\pi,t+1}(s^ {\prime},a^{\prime})$ (119) $\displaystyle=$ $\displaystyle 2q_{\pi,t}(s,a)r(s,a)-r(s,a)^{2}+\mathbb{E}_{s^{\prime}\sim p,a^ {\prime}\sim\pi}\quantity[\frac{\pi_{t+1}(a^{\prime}|s^{\prime})}{\mu^{*}_{t+1 }(a^{\prime}|s^{\prime})}\tilde{r}_{\pi,t+1}(s^{\prime},a^{\prime})].$ (120) $$

∎

###### Proof.

## Appendix B Experiment Details

### B.1 GridWorld

We test Gridworlds with $n^{3}=1,000$ and $n^{3}=27,000$ states. For a Gridworld with size $n^{3}$, we set its width, height, and time horizon $T$ all to be $n$. The action space contains four 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.1$ to move uniformly at random. When the agent runs into a boundary, it stays in the 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 using the on-policy Monte Carlo method by running each target policy for $10^{6}$ episodes.
We test two different sizes of the Gridworld with a number of $1,000$ and $27,000$ states.
The offline dataset of both environments contains $1,000$ episodes generated by a set of random policies.
We learn functions $q_{\pi,t},q^{c}_{\pi,t}$, and $\hat{r}_{\pi,t}$ using Fitted Q-Evaluation algorithms (FQE, Le et al., ()) by passing data tuples in $\mathcal{D}_{\nu}$ from $t=T-1$ to 0 0.
Notably, Fitted Q-Evaluation (FQE, Le et al., ()) is a different algorithm from Fitted Q-Improvement (FQI). Fitted Q-Evaluation is not prone to overestimate the action-value function $q_{\pi,t}$ because Fitted Q-Evaluation does not have any $\max$ operator and does not change the policy.
We tune all hyperparameters offline
based on Fitted Q-learning loss. We choose a one-hidden-layer neural network and test the neural network size with $[64,128,256]$ and choose $64$ as the final size.
We test the learning rate for Adam optimizer with $[1\text{e}^{-5},1\text{e}^{-4},1\text{e}^{-3},1\text{e}^{-2}]$ and choose to use the default learning rate $1\text{e}^{-3}$ as learning rate for Adam optimizer (Kingma and Ba,, ).
All benchmark algorithms are learned using their reported hyperparameters (Zhong et al.,, ; Liu and Zhang,, ).
Each policy has 30 independent runs, resulting in $30\cdot 30=900$ total runs.
Therefore, each curve in Figure 2, Figure 2 and each number in Table 1 are averaged from 900 different runs over a wide range of policies indicating strong statistical significance.

### B.2 MuJoCo

Figure: Figure 4: MuJoCo robot simulation tasks (Todorov et al.,, ). Environments from the left to the right are Ant, Hopper, InvertedDoublePendulum, InvertedPendulum, and Walker.
Refer to caption: extracted/5909165/figure/mujoco/ant.jpg

Figure: 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.
Refer to caption: x4.png

**Table 3: Relative variance of estimators on MuJoCo. 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).**
|  | On-policy MC | Ours | ODI | ROS |
| --- | --- | --- | --- | --- |
| Ant | 1.000 | 0.835 | 0.811 | 1.032 |
| Hopper | 1.000 | 0.596 | 0.542 | 1.005 |
| I. D. Pendulum | 1.000 | 0.778 | 0.724 | 0.992 |
| I. Pendulum | 1.000 | 0.439 | 0.351 | 0.900 |
| Walker | 1.000 | 0.728 | 0.696 | 0.908 |

**Table 4: 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 is the only method consistently achieving both variance reduction and safety constraint satisfaction.**
|  | On-policy MC | Ours | ODI | ROS |
| --- | --- | --- | --- | --- |
| Ant | 1.000 | 0.897 | 1.397 | 1.033 |
| Hopper | 1.000 | 0.930 | 1.523 | 1.021 |
| I. D. Pendulum | 1.000 | 0.876 | 1.399 | 1.012 |
| I. Pendulum | 1.000 | 0.961 | 1.743 | 0.990 |
| Walker | 1.000 | 0.953 | 1.485 | 1.061 |

MuJoCo is a physics engine containing various stochastic environments, where 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) with a wide range of performance generated by
the proximal policy optimization (PPO) algorithm (Schulman et al.,, ) with the default PPO implementation in Huang et al., ().
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).
We set each MuJoCo environment to have a fixed time horizon $100$ in OpenAI Gymnasium (Towers et al.,, ).
Since our methods are designed for discrete action space,
we discretize the first dimension of MuJoCo action space.
The remaining dimensions are controlled by the PPO policies and are deemed as part of the environment.
The offline dataset of each environment contains $1,000$ episodes generated by a set of policies with various performances.
Functions $q_{\pi,t},q^{c}_{\pi,t}$, and $\hat{r}_{\pi,t}$ are learned the same way as in Gridworld environments.
Our algorithm is robust on hyperparameters.
All hyperparameters in Algorithm 1 are tuned offline and are the same across all MuJoCo and Gridworld experiments.
Each policy in MuJoCo also has 30 independent runs, resulting in $30\cdot 30=900$ total runs.
Therefore, curves in all figures are averaged from 900 different runs over a wide range of policies indicating strong statistical significance.

## Peer Reviews

confidence: 2
contribution: 4
initial_rating: 8
presentation: 4
questions: * What are the implications of considering the undiscounted setting, as opposed to the discounted setting?
* See "Weaknesses"
soundness: 4
strengths: * This work is well-motivated in terms of aiming to reduce variance while also _ensuring safety_ during on-policy evaluation.
* The proposed method is simple, and theoretical results demonstrate that the method is feasible, unbiased, and variance-minimizing.
* 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.
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.
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?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
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?

2. 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?
soundness: 3
strengths: 1. The study addresses the new and intriguing problem of incorporating safety constraints in policy evaluation.
2. The paper is well-organized and easy to follow.
3. It provides comprehensive support with both theoretical and empirical evidence.
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.
weaknesses: 1. While addressing safety constraints is novel, the approach to variance minimization under these constraints lacks significant innovation.
2. 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.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
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?

How is the proposed method applied to continuous state-action space?

The mainstream policy evaluation uses a one-step method, such as the TD method. Can the proposed method be applied to these methods?
soundness: 3
strengths: The proposed solution is derived by formulating and solving an optimization problem, which has support from the theoretical results.

The literature review is thoughtful and complete.
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.
weaknesses: In the experiment, the performances of the constrained RL algorithm under different policy evaluation methods should be compared.

See **Questions**

---

confidence: 5
contribution: 3
initial_rating: 8
presentation: 3
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?
- Q2: The original MuJoCO environment does not have a notion of safety cost. How did the authors introduce safety costs?
- 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.
- 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?
soundness: 3
strengths: - The authors address a very important and interesting problem where safety constraint is considered in RL policy evaluation.
- The motivation behind the problem formulation is well-presented while using an example of Google's data center.
- The background section is well-written and easy to follow.
- I think it is a good idea to provide theoretical results and key ideas in the case of contextual bandit.
- Theoretical results are nice and proofs are well-presented.
- The empirical experiments are overall well-conducted.
- The authors' proposed method performs well in Grid-world and MuJoCO.
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.
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.
    - 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.
    - Liu, Yongshuai, Avishai Halev, and Xin Liu. "Policy learning with constraints in model-free reinforcement learning: A survey." In IJCAI. 2021.
    - Gu, Shangding, et al. "A review of safe reinforcement learning: Methods, theory and applications." arXiv preprint arXiv:2205.10330 (2022).
    - Wachi, Akifumi, Xun Shen, and Yanan Sui. "A Survey of Constraint Formulations in Safe Reinforcement Learning." In IJCAI (2024)
- 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. 
- 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. 
- 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.
- 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.
- 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.

### Typos
- In (3), $\mathbb{V}$ --> $\mathbb{V}_{a \sim \mu}$.

Meta-review: The paper provides an on-policy evaluation method that aims to reduce the variance while satisfying safety constraints.
The problem is an important one and the reviewers are generally positive about the paper. The experiments are also well executed, and I encourage the authors to open source their code.

Decision: Accept (Poster)