Doubly Optimal Policy Evaluation for Reinforcement Learning

## Abstract

Abstract Policy evaluation estimates the performance of a policy by (1) collecting data from the environment and (2) processing raw data into a meaningful estimate. Due to the sequential nature of reinforcement learning, any improper data-collecting policy or data-processing method substantially deteriorates the variance of evaluation results over long time steps. Thus, policy evaluation often suffers from large variance and requires massive data to achieve the desired accuracy. In this work, we design an optimal combination of data-collecting policy and data-processing baseline. Theoretically, we prove our doubly optimal policy evaluation method is unbiased and guaranteed to have lower variance than previously best-performing methods. Empirically, compared with previous works, we show our method reduces variance substantially and achieves superior empirical performance.

## 1 Introduction

Reinforcement learning (RL, Sutton and Barto, ()) has achieved remarkable success in various sequential decision-making problems. For example, RL algorithms have reduced energy consumption for Google data centers’ cooling by $40\%$ (Chervonyi et al.,, ), predicted protein structures with competitive accuracy (Jumper et al.,, ), and discovered faster matrix multiplication algorithms (Fawzi et al.,, ).
When applying RL algorithms, policy evaluation plays a critical role
to allow practitioners to estimate the performance of a policy before committing to its full deployment and test different algorithmic choices.
A commonly used approach among RL practitioners for policy evaluation is the on-policy
Monte Carlo method, where a policy (i.e., the target policy) is evaluated by directly executing itself. However, using the target policy itself as the behavior policy is not optimal (Hanna et al.,, ; Liu and Zhang,, ), leading to evaluation with high variance. This suboptimality of on-policy evaluation results in extensive needs for collecting online samples to achieve a desired level of accuracy.

In many scenarios, heavily relying on online data is not preferable, since collecting massive online data through real-world interaction is both expensive and slow (Li,, ; Zhang,, ). Even with a well-developed simulator, complex tasks like data center cooling take $10$ seconds per step (Chervonyi et al.,, ), making the evaluation of a policy requiring millions of steps prohibitively expensive.
To address the expensive nature of online data,
offline RL is proposed to mitigate the dependency on online data. However, there are often mismatches between the offline data distribution and the data distribution induced by the target policy, leading to uncontrolled and ineliminable bias (Jiang and Li,, ; Farahmand and Szepesvári,, ; Marivate,, ). As a result, a policy with high performance on offline data may actually perform very poorly in real deployment (Levine,, ). Consequently, both online and offline RL practitioners still heavily rely on online policy evaluation methods(Kalashnikov et al.,, ; Vinyals et al.,, ).

Improving the online sample efficiency for policy evaluation by reducing the variance of estimators is thus a critical challenge in the RL community.
In this paper, we tackle this challenge by decomposing policy evaluation into two phases: data collecting and data processing. Our contributions are summarized as follows:

- 1.
We design a doubly optimal estimator by proposing an optimal data-collecting policy and an optimal data-processing baseline. They are carefully tailored to each other to guarantee both unbiasedness and substantial variance reduction.
- 2.
Theoretically, we prove our method has guaranteed lower variance than the on-policy Monte Carlo estimator, and is superior to previously best methods (Jiang and Li,, ; Liu and Zhang,, ). Moreover, such superiority grows over the time horizon as ensured by rigorous mathematical analysis.
- 3.
Empirically, we show that our method reduces variance substantially
compared with previous works and achieves state-of-the-art performance across a broad set of environments.

## 2 Related Work

Reducing the variance for policy evaluation in reinforcement learning (RL)
has been widely studied.
One rising approach is variance reduction by designing a proper data-collecting policy, also known as the
behavior policy. Noticing that the target policy itself is not the best behavior policy, Hanna et al., () formulate the task of finding a variance-reduction behavior policy as an optimization problem.
They use stochastic gradient descent to update a parameterized behavior policy. However, the stochastic method has been known to easily get stuck in highly suboptimal points in just moderately complex environments, where various local optimal points exist (Williams,, ). By contrast, our method directly learns the globally optimal behavior policy without doing a policy search.
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.
By 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. By contrast, our method copes well with incomplete offline tuples, which is widely applicable.

Zhong et al., () also aim to reduce the variance of policy evaluation through designing a proper behavior policy. They propose adjusting the behavior policy to focus on under-sampled data segments. Nevertheless, their method necessitates complete offline trajectories generated by known policies and assumes a strong similarity between the behavior and target policies, limiting the generalizability. By contrast, our method effectively uses incomplete offline segments from unknown and diverse behavior policies. Moreover, the estimates made by Zhong et al., () lack theoretical guarantees of unbiasedness nor consistency.
By contrast, we theoretically prove that our estimate is inherently unbiased.
Another approach by Mukherjee et al., () investigates behavior policies aimed at reducing variance in per-decision importance sampling estimators. However, their results are limited to tree-structured MDPs, a significant limitation since most problems do not adhere to tree structure.
By contrast, our method works on general MDPs without any restriction on their inherent structures. Moreover, Mukherjee et al., () explicitly require the knowledge of transition probability and, therefore, suffer from all canonical
challenges in model learning (Sutton,, ; Sutton et al.,, ; Deisenroth and Rasmussen,, ; Chua et al.,, ). By contrast, our approach is model-free and can use off-the-shelf offline policy evaluation methods (e.g. Fitted Q-Evaluation, Le et al., ()).
The current state-of-the-art method in behavior policy design is proposed by Liu and Zhang, (), where they find an optimal and offline-learnable behavior policy with the per-decision importance sampling estimator. However, all these approaches (Hanna et al.,, ; Mukherjee et al.,, ; Zhong et al.,, ; Liu and Zhang,, ) only consider optimality in the data-collecting process, while ignoring the potential improvement in
data-processing steps. By contrast, we model the variance reduction as a bi-level optimization problem, where the behavior policy is optimized with a baseline function. This fundamental difference makes our method superior in a broader context, as theoretically and empirically demonstrated in Section 5 and Section 7.

Besides behavior policy design, another popular approach for reducing the variance in policy evaluation is using the baseline functions. Jiang and Li, () propose a doubly robust estimator by incorporating a baseline function into the plain per-decision importance sampling estimator. However, their method assumes that the behavior policy is fixed and given, but does not discuss how to choose a proper behavior policy.
Ignoring the choice of behavior policy loses the opportunity to save online samples manyfold.
By contrast, our method achieves optimality in both the design of behavior policy and the choice of baseline, thus outperforming the estimator of Jiang and Li, () both theoretically and empirically. Thomas and Brunskill, () extend the method of Jiang and Li, () into the infinite horizon setting, proposing a weighted doubly robust estimator. However, their method introduces bias into the estimator, potentially leading the estimation to systematically deviate from the true return of the target policy.

## 3 Background

In this paper, we study a finite horizon Markov Decision Process (MDP, Puterman, ()). This MDP consists of 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$.
For simplifying notations.
we consider the undiscounted setting without loss of generality.
Our method naturally applies to the discounted setting as long as the horizon is fixed and finite (Puterman,, ).
We define a shorthand $[n]\doteq\quantity{0,1,\dots,n}$ for any integer $n$.

The MDP process 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$.
Then, a finite reward $R_{t+1}\doteq r(S_{t},A_{t})$ is emitted and a successor state $S_{t+1}$ is sampled from $p(\cdot\mid S_{t},A_{t})$.
We also define abbreviations $\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 is defined as
$G_{t}\doteq\sum_{i={t+1}}^{T}R_{i},$
which allows us to define the state-value and action-value functions 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].$
We use the total rewards performance metric (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)$.
In this paper, we use Monte Carlo
methods, as introduced by Kakutani, (), for estimating the total rewards $J(\pi)$.
The most straightforward Monte Carlo
method 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, ).

Moving forward, we focus on off-policy evaluation, where the goal is to estimate the total rewards $J(\pi)$ of an interested policy $\pi$, which is called the target policy. Data for off-policy evaluation are collected
by executing a different policy $\mu$,
called the behavior policy.
In off-policy evaluation, we generate each trajectory
$\textstyle\quantity{S_{0},A_{0},R_{1},S_{1},A_{1},R_{2},\dots,S_{T-1},A_{T-1},
R_{T}}$ by a behavior policy $\mu$ with
$A_{t}\sim\mu_{t}(\cdot|S_{t}).$
We use a shorthand $\tau^{\mu_{t:T-1}}_{t:T-1}\doteq\quantity{S_{t},A_{t},R_{t+1},\dots,S_{T-1},A_
{T-1},R_{T}}$ for a trajectory generated by the behavior policy $\mu$ from the time step $t$ to the time step $T-1$ inclusively.
In off-policy learning, we use the importance sampling ratio to reweight rewards collected by the behavior policy $\mu$, in order to give an estimate of $J(\pi)$.
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})}.$
There are several ways to use the importance sampling ratios in off-policy learning
(Geweke,, ; Hesterberg,, ; Koller and Friedman,, ; Thomas,, ).
In this paper,
we investigate the per-decision importance sampling estimator (PDIS, Precup et al., ()) and leave the investigation of others for future work.
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) $$

Under the classic policy coverage assumption (Precup et al.,, ; Maei,, ; Sutton et al.,, ; Zhang,, ) $\forall t,s,a,\mu_{t}(a|s)=0\implies\pi_{t}(a|s)=0$, this off-policy estimator $G^{\text{PDIS}}(\tau^{\mu_{0:T-1}}_{0:T-1})$ provides an *unbiased* estimation for $J(\pi)$, i.e., $\mathbb{E}\quantity[G^{\text{PDIS}}(\tau^{\mu_{0:T-1}}_{0:T-1})]=J(\pi).$

In off-policy evaluation, a notorious curse is that the importance sampling ratios can be extremely large, resulting in infinite variance (Sutton and Barto,, ).
Even with the PDIS method, this fundamental issue still remains if the behavior policy significantly differs from the target policy, particularly when the behavior policy assigns very low probabilities to actions favored by the target policy. Moreover, such degeneration of important sampling ratios typically grows with the dimensions of state and action spaces as well as the time horizon (Levine et al.,, ).
One way to control for the violation in important sampling ratios is to subtract a baseline from samples (Williams,, ; Greensmith et al.,, ; Jiang and Li,, ; Thomas and Brunskill,, ). Using $b$ to denote an arbitrary baseline function, the PDIS estimator with baseline is defined as

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

where

$$ $\displaystyle\bar{b}_{t}(S_{t})\doteq\mathbb{E}_{A_{t}\sim\pi}\quantity[b_{t}( S_{t},A_{t})].$ (3) $$

The variance of (2) highly depends on the importance sampling ratio $\rho_{t}=\frac{\pi_{t}(A_{t}|S_{t})}{\mu_{t}(A_{t}|S_{t})}$ and the choice of baseline function $b$.

## 4 Variance Reduction in Reinforcement Learning

We seek to reduce the variance $\mathbb{V}(G^{b}(\tau^{\mu_{0:T-1}}_{0:T-1}))$
by designing an optimal behavior policy and an optimal baseline function at the same time.
We solve the bi-level optimization problem

$$ $\displaystyle\min_{b}\min_{\mu}$ $\displaystyle\quad\mathbb{V}(G^{b}(\tau^{\mu_{0:T-1}}_{0:T-1}))$ (4) s.t. $\displaystyle\quad\mathbb{E}\quantity[G^{b}(\tau^{\mu_{0:T-1}}_{0:T-1})]=J(\pi),$ (5) $$

where the optimal behavior policy $\mu^{*}$ and the optimal baseline function $b^{*}$ are carefully tailored to each other to guarantee both unbiasedness and substantial variance reduction.

Our paper proceeds as follows. In Section 4, we solve this
bi-level optimization problem in closed-form. In Section 5, we mathematically quantify the superiority in variance reduction of our designed optimal behavior policy and baseline function, in comparison with cutting-edge methods (Jiang and Li,, ; Liu and Zhang,, ).
In Section 7, we empirically show that such doubly optimal design reduces the variance substantially compared with the on-policy Monte Carlo estimator and previously best methods (Jiang and Li,, ; Liu and Zhang,, ) in
a broad set of environments.

To ensure that the off-policy estimator $G^{b}(\tau^{\mu_{0:T-1}}_{0:T-1})$
is unbiased, the classic reinforcement learning wisdom (Precup et al.,, ; Maei,, ; Sutton et al.,, ; Zhang,, )
requires that the behavior policy $\mu$ covers the target policy $\pi$.
This means that they
constraint $\mu$ to be in a set

$$ $\displaystyle\Lambda^{-}\doteq$ $\displaystyle\{\mu\mid\forall t,s,a,\pi_{t}(a|s)\neq 0\implies\mu_{t}(a|s)\neq 0\}$ (6) $\displaystyle=$ $\displaystyle\{\mu\mid\forall t,s,a,\mu_{t}(a|s)=0\implies\pi_{t}(a|s)=0\},$ (7) $$

which contains all policies that satisfy the policy coverage constraint in off-policy learning (Sutton and Barto, ). By specifying the policy coverage constraint,
the optimization problem (4) is reformulated as

$$ $\displaystyle\min_{b}\min_{\mu}$ $\displaystyle\quad\mathbb{V}(G^{b}(\tau^{\mu_{0:T-1}}_{0:T-1}))$ (8) s.t. $\displaystyle\quad\mu\in\Lambda^{-}.$ (9) $$

In this paper, compared with the classic reinforcement learning literature, we enlarge the search space of $\mu$ from this set $\Lambda^{-}$ to a set $\Lambda$. To achieve a superior and reliable optimization solution,
we require $\Lambda$ to have two properties.

- 1.
(Broadness) $\Lambda$ must be broad enough such that it includes all policies satisfying the classic policy coverage constraint (Precup et al.,, ; Sutton and Barto,, ). Formally,
$\displaystyle\Lambda^{-}\subseteq\Lambda.$
(10)
- 2.
(Unbiasedness)
Every behavior policy in $\Lambda$ must be well-behaved such that the data collected by it can be used by the off-policy estimator to achieve unbiased estimation for all state $s$ and time step $t$. Formally, $\forall\mu\in\Lambda$,
$\displaystyle\forall t,\forall s,\quad\mathbb{E}\left[G^{b}(\tau^{\mu_{t:T-1}}
_{t:T-1})\mid S_{t}=s\right]=v_{\pi,t}(s).$
(11)

The space $\Lambda$ that satisfies those two properties will be defined shortly.
We now reformulate our bi-level optimization problem as

$$ $\displaystyle\min_{b}\min_{\mu}$ $\displaystyle\quad\mathbb{V}(G^{b}(\tau^{\mu_{0:T-1}}_{0:T-1}))$ (12) s.t. $\displaystyle\quad\mu\in\Lambda.$ (13) $$

Compared with the classic approach (8), our bi-level optimization problem (12) searches for $\mu$ in a broader space $\Lambda$ such that $\Lambda^{-}\subseteq\Lambda$.
Thus, the optimal solution of our optimization problem must be *superior* to the optimal solution of the optimization problem with the classic policy coverage constraint.
To solve our bi-level optimization problem (12), we first give a closed-form solution of the inner optimization problem

$$ $\displaystyle\min_{\mu}$ $\displaystyle\quad\mathbb{V}(G^{b}(\tau^{\mu_{0:T-1}}_{0:T-1}))$ (14) s.t. $\displaystyle\quad\mu\in\Lambda$ (15) $$

for any baseline function $b$.
Notably, this baseline function $b$ does not need to be any kind of oracle. We design the optimal solution of (14) for this baseline function $b$ without requiring any property on $b$.
Now, we decompose the variance of our off-policy estimator $G^{b}(\tau^{\mu_{0:T-1}}_{0:T-1})$. By the law of total variance,
$\forall b,\forall\mu\in\Lambda$,

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{0:T-1}}_{0:T-1})\right)$ (16) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{0}}\left[\mathbb{V}\left(G^{b}(\tau^{\mu_{0:T-1}}_ {0:T-1})\mid S_{0}\right)\right]+\mathbb{V}_{S_{0}}\left(\mathbb{E}\left[G^{b} (\tau^{\mu_{0:T-1}}_{0:T-1})\mid S_{0}\right]\right)$ (17) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{0}}\left[\mathbb{V}\left(G^{b}(\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 ( 11 )) (18) $$

The second term in (18) is a constant given a target policy $\pi$ and is unrelated to the choice of $\mu$.
In the first term,
the expectation is taken over $S_{0}$ that is determined by the initial probability distribution $p_{0}$.
Consequently, given any baseline function $b$,
to solve the problem (14),
it is sufficient to solve

$$ $\displaystyle\min_{\mu}\quad$ $\displaystyle\mathbb{V}(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s)$ (19) s.t. $\displaystyle\mu\in\Lambda$ (20) $$

for all $s$ and $t$.
If we can find one optimal behavior policy $\mu^{*}$ that simultaneously solves the optimization problem (19) on all states and time steps, $\mu^{*}$ is also the optimal solution for the optimization problem (14).
Denote the variance of the state value function for the next state
given the current state-action pair as $\nu_{\pi,t}(s,a)$.
Recall the notation $[T-2]$ is a shorthand for the set $\quantity{0,1,\dots,T-2}$.
We have $\nu_{\pi,t}(s,a)\doteq 0$ for $t=T-1$, and $\forall t\in[T-2]$,

$$ $\displaystyle\!\!\!\!\!\!\!\!\!\!\!\nu_{\pi,t}(s,a)\doteq\mathbb{V}_{S_{t+1}} \left(v_{\pi,t+1}(S_{t+1})\mid S_{t}=s,A_{t}=a\right).$ (21) $$

Given any baseline function $b$, we construct a behavior policy $\mu^{*}$ as

$$ $\displaystyle\mu_{t}^{*}(a|s)\propto\textstyle\pi_{t}(a|s)\sqrt{u_{\pi,t}(s,a)}$ (22) $$

where
$u_{\pi,t}(s,a)\doteq\quantity[q_{\pi,t}(s,a)-b_{t}(s,a)]^{2}$ for $t=T-1$, and $\forall t\in[T-2]$,

$$ $\displaystyle u_{\pi,t}(s,a)\doteq\quantity(q_{\pi,t}(s,a)-b_{t}(s,a))^{2}+\nu _{\pi,t}(s,a)+\textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a)\mathbb{V}\left(G^{ b}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{\prime}\right)}.$ (23) $$

Notably,
$u_{\pi,t}$ and $\mu^{*}_{t}$ are defined backwards and alternatively,
i.e.,
they are defined in the order of $u_{\pi,T-1},\mu^{*}_{T-1},u_{\pi,T-2},\mu^{*}_{T-2},\dots,u_{\pi,0},\mu^{*}_{0}$.
We now break down each term in $u_{\pi,t}(s,a)$.

- 1.
$\quantity(q_{\pi,t}(s,a)-b_{t}(s,a))^{2}$ is the squared difference between the state-value function $q_{\pi,t}$ and the baseline function $b$. This term is always non-negative because of the square operation. Its magnitude is mainly controlled by the baseline function $b$.
- 2.
$\nu_{\pi,t}(s,a)$ defined in (21) is the variance of the value for the next state. This term is always non-negative by the definition of variance. Its magnitude is mainly controlled by the stochasticity of the environment (i.e. transition function $p$).
- 3.
$\textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a)\mathbb{V}\left(G^{b}(\tau^{\mu^{
*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{\prime}\right)}$ is the expected future variance given the current state $s$ and action $a$. This term is always non-negative by the definition of variance. Its magnitude is jointly controlled by the choice of behavior policy $\mu^{*}$, the baseline function $b$, and the transition function $p$.

$u_{\pi,t}(s,a)$ is non-negative because it is the sum of three non-negative terms.
Therefore, $\sqrt{u_{\pi,t}(s,a)}$ is always well-defined.
In (22),
$\mu_{t}^{*}(a|s)\propto\pi_{t}(a|s)\sqrt{u_{\pi,t}(s,a)}$
means

$$ $\displaystyle\textstyle\mu_{t}^{*}(a|s)\doteq\frac{\pi_{t}(a|s)\sqrt{u_{\pi,t} (s,a)}}{\sum_{b}\pi_{t}(b|s)\sqrt{u_{\pi,t}(s,b)}}.$ (24) $$

If $\forall a,\pi_{t}(a|s)\sqrt{u_{\pi,t}(s,a)}=0$,
the denominator is zero.
In this case, we use the convention to interpret $\mu_{t}^{*}(a|s)$ as a uniform distribution, i.e., $\forall a,\mu_{t}^{*}(a|s)=1/{|\mathcal{A}|}$.
We adopt this convention for $\propto$ in the rest of the paper to simplify the presentation.
Now, we define the enlarged space $\Lambda$ as

$$ $\displaystyle\Lambda\doteq$ $\displaystyle\quantity{\mu\mid\forall t,s,a,\mu_{t}(a|s)=0\implies\pi_{t}(a|s) u_{\pi,t}(s,a)=0}.$ (25) $$

We prove that this policy space $\Lambda$ defined above satisfies the broadness (10) and the unbiasedness (11) by the following lemmas.

###### Lemma 1 (Broadness) .

$\forall b$, $\Lambda^{-}\subseteq\Lambda.$

Its proof is in Appendix A.1.

###### Lemma 2 (Unbiasedness) .

$\forall b,\forall\mu\in\Lambda$, $\forall t,\forall s$,
$\mathbb{E}\left[G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right]=v_{\pi,t}
(s).$

Its proof is in Appendix A.2. After confirming the broadness and unbiasedness of the space $\Lambda$, we now prove that the behavior policy $\mu^{*}$ is the optimal solution for the inner optimization problem.

###### Theorem 1 .

For a baseline function $b$,
the behavior policy $\mu^{*}$ defined in (22) is an optimal solution to the optimization problems $\forall t,s$,

$$ $\displaystyle\min_{\mu}$ $\displaystyle\quad\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}= s\right)$ (26) s.t. $\displaystyle\quad\mu\in\Lambda.$ (27) $$

Its proof is in Appendix A.3.
Theorem 1 proves that $\forall b$, the behavior policy $\mu^{*}$ (22) is the closed-form optimal solution for all $t$ and $s$.
With Theorem 1, for any $t$ and $s$, we reduce the bi-level optimization problem

$$ $\displaystyle\min_{b}\min_{\mu}$ $\displaystyle\quad\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}= s\right)$ (28) s.t. $\displaystyle\quad\mu\in\Lambda$ (29) $$

to a single-level unconstrained optimization problem

$$ $\displaystyle\min_{b}\quad$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{t}=s \right).$ (30) $$

In this unconstrained optimization problem, we design a function $b$ that influences both the data processing estimator $G^{b}$ (2) and the optimal behavior policy $\mu^{*}$ (22). Notably, the optimal behavior policy $\mu^{*}$ depends on the baseline $b$ because it is tailored to a baseline function $b$ in Theorem 1.
Unless otherwise noted, we omit explicitly writing this dependency in the notation of $\mu^{*}$ for simplicity.
We show that although both $G^{b}$ and $\mu^{*}$ depend on $b$, through the mathematical proof in the appendix,
the optimal baseline function $b^{*}$ has a concise format.
Define $\forall t,s,a$,

$$ $\displaystyle b^{*}_{t}(s,a)\doteq q_{\pi,t}(s,a).$ (31) $$

###### Theorem 2 .

$b^{*}$ is the optimal solution to the optimization problems $\forall t,s$,

$$ $\displaystyle\min_{b}\quad$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{t}=s \right).$ (32) $$

Its proof is in Appendix A.4. By solving each level of the optimization problem, we show $(\mu^{*},b^{*})$ is the optimal solution for the bi-level optimization problem by utilizing Theorem 1 and Theorem 2.

###### Theorem 3 .

$(\mu^{*},b^{*})$ is the optimal solution to the bi-level optimization problems $\forall t$, $s$,

$$ $\displaystyle\min_{b}\min_{\mu}$ $\displaystyle\quad\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}= s\right)$ (33) s.t. $\displaystyle\quad\mu\in\Lambda.$ (34) $$

###### Proof.

$\forall b,\forall\mu\in\Lambda$, we have $\forall t,\forall s$

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (35) $\displaystyle\geq$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (Theorem 1 ) $\displaystyle\geq$ $\displaystyle\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{ t}=s\right).$ (Theorem 2 ) $$

Thus, $(\mu^{*},b^{*})$ achieves the minimum value of $\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ for all $t$ and $s$.
∎

###### Lemma 1 (Broadness) .

###### Lemma 2 (Unbiasedness) .

###### Theorem 1 .

###### Theorem 2 .

###### Theorem 3 .

###### Proof.

## 5 Variance Comparison

Theorem 3 shows $(\mu^{*},b^{*})$ is the optimal behavior policy and
baseline function.
This means $(\mu^{*},b^{*})$ is superior to any other choice of $(\mu,b)$. In this section, we further quantify its superiority.
We quantify the variance reduction in
reinforcement learning. We show that the variance reduction compounds over each step, bringing substantial advantages.
Specifically, we provide a theoretical comparison of our method—the doubly optimal estimator—with the following baselines: (1) the on-policy Monte Carlo estimator, (2) the offline data informed estimator (Liu and Zhang,, ), and (3) the doubly robust estimator (Jiang and Li,, ).
We use $u^{b^{*}}_{t}$ to denote $u_{t}$ (23) using $b^{*}$ as the baseline function.
First, we compare our off-policy estimator with the on-policy Monte Carlo estimator (ON).

###### Theorem 4 .

$\forall t,s$,

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S _{t}=s\right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_ {t}=s\right)$ (36) $\displaystyle=$ $\displaystyle\textstyle\underbrace{\mathbb{V}_{A_{t}\sim\pi_{t}}\quantity( \sqrt{u^{b^{*}}_{t}(S_{t},A_{t})}\mid S_{t}=s)}_{\hypertarget{4.1}{(4.1)}}+ \underbrace{\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t})\mid S_{t }=s\right)}_{\hypertarget{4.2}{(4.2)}}+\underbrace{\delta^{\text{ON, ours}}_{t }(s)}_{\hypertarget{4.3}{(4.3)}},$ (37) $$

where $\delta^{\text{ON, ours}}_{t}(s)\doteq 0$ for $t=T-1$ and $\forall t\in[T-2]$, $\delta^{\text{ON, ours}}_{t}(s)\doteq$

$$ $\displaystyle\!\!\!\!\!\!\!\textstyle\mathbb{E}_{A_{t}\sim\pi_{t},S_{t+1}} \left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t +1}\right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S _{t+1}\right)\mid S_{t}=s\right].$ (38) $$

Moreover, we prove $\forall t,s,\delta^{\text{ON, ours}}_{t}(s)\geq 0$ meaning the variance reduction in future steps is compounded into the current step.

Its proof is in Appendix A.5.
In Theorem 4, we show that the variance reduction of our method includes three sources.
First, a part of the future variance (4.1) is eliminated by choosing an optimal behavior policy $\mu^{*}$.
Second, the variance of the $q$ function (4.2) is eliminated by the optimal baseline function $b^{*}$. Third, the variance reduction in the future step (4.3) is compounded into the current step.

Next, the following theorem quantifies the variance reduction of our method compared with the offline data informed (ODI) method in Liu and Zhang, ().
Because the behavior policy $\mu^{*}$ is tailored for the baseline function $b$,
we use $\mu^{*,b}$ to denote $\mu^{*}$ with a baseline function $b$ and $\mu^{*,\text{PDIS}}$ to denote $\mu^{*}$ with no baseline function (i.e., the plain PDIS estimator considered in offline data informed (ODI) method (Liu and Zhang,, )).

###### Theorem 5 .

$\forall t,s$,

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*,\text{PDIS}}_{t:T-1} }_{t:T-1})\mid S_{t}=s\right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t :T-1}}_{t:T-1})\mid S_{t}=s\right)$ (39) $\displaystyle\geq$ $\displaystyle\underbrace{\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left( \rho_{t}q_{\pi,t}(S_{t},A_{t})\mid S_{t}\right)}_{\hypertarget{5.1}{(5.1)}}+ \underbrace{\delta^{\text{ODI, ours}}_{t}(s)}_{\hypertarget{5.2}{(5.2)}},$ (40) $$

where $\delta^{\text{ODI, ours}}_{t}(s)\doteq 0$ for $t=T-1$ and $\forall t\in[T-2]$, $\textstyle\delta^{\text{ODI, ours}}_{t}(s)\doteq$

$$ $\displaystyle\textstyle\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t},S_{t+1}} \left[\rho_{t}^{2}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*,\text{ PDIS}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)-\mathbb{V}\left(G^{\text{PDIS} }(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\right]\mid S_{t }\right].$ (41) $$

Moreover, we prove $\forall t,s,\delta^{\text{ODI, ours}}_{t}(s)\geq 0$ meaning the variance reduction in future steps is compounded into the current step.

Its proof is in Appendix A.6.
The variance reduction of our estimator includes two sources. First, the variance of the $q$ function (5.1) is eliminated. Second, the variance reduction in the future step (5.2) is compounded to the current step.

We also quantify the variance reduction of our estimator with the doubly robust (DR) estimator defined in Jiang and Li, (). Since Jiang and Li, () does not specify any candidate behavior policy, we leverage the conventional wisdom, supposing they use the canonical target policy $\pi$ as the data-collecting policy.

###### Theorem 6 .

$\forall t,s$,

$$ $\displaystyle\mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S_{t}=s \right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (42) $\displaystyle=$ $\displaystyle\underbrace{\mathbb{V}_{A_{t}\sim\pi_{t}}\quantity(\sqrt{u^{b^{*} }_{t}(S_{t},A_{t})}\mid S_{t}=s)}_{\hypertarget{6.1}{(6.1)}}+\underbrace{ \delta^{\text{DR, ours}}_{t}(s)}_{\hypertarget{6.2}{(6.2)}},$ (43) $$

where $\delta^{\text{DR, ours}}_{t}(s)\doteq 0$ for $t=T-1$ and $\forall t\in[T-2]$, $\delta^{\text{DR, ours}_{t}}(s)\doteq$

$$ $\displaystyle\!\!\!\!\!\!\!\textstyle\mathbb{E}_{A_{t}\sim\pi_{t},S_{t+1}} \left[\mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1} \right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t +1}\right)\mid S_{t}\right].$ (44) $$

Moreover, we prove $\forall t,s,\delta^{\text{DR, ours}}_{t}(s)\geq 0$ meaning the variance reduction in future steps is compounded into the current step.

Its proof is in Appendix A.7. Similarly, there are two sources of the variance reduction for our method. First, with an optimal behavior policy $\mu^{*}$, we eliminate a part of the future variance (6.1). Second, the variance reduction in the future steps (6.2) is compounded to the current step.

###### Theorem 4 .

###### Theorem 5 .

###### Theorem 6 .

## 6 Learning Closed-Form Behavior Policies

Figure: Algorithm 1 Doubly Optimal (DOpt) Policy Evaluation

In this section,
we present an efficient Algorithm 1 to learn our doubly optimal method including the optimal behavior policy $\mu^{*}$ and the optimal baseline function $b^{*}$. Specifically, we learn $(\mu^{*},b^{*})$ from offline data pairs.
By definition (31), we can apply any off-the-shelf offline policy evaluation methods to learn $b^{*}_{t}(s,a)\doteq q_{\pi,t}(s,a)$ (e.g., Fitted Q-Evaluation (Le et al.,, )).
By (22), $\mu_{t}^{*}(a|s)\propto\textstyle\pi_{t}(a|s)\sqrt{u_{\pi,t}(s,a)}$, where $u$ is defined in (23) as

$$ $\displaystyle\!\!\!\textstyle u_{\pi,t}(s,a)\doteq\quantity(q_{\pi,t}(s,a)-b_{ t}(s,a))^{2}+\nu_{\pi,t}(s,a)+\textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a) \mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{ \prime}\right)}.$ (45) $$

Learning $u$ from this perspective is very inefficient because it requires the approximation of the complicated variance term $\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{
\prime}\right)$ regarding future trajectories. To solve this problem, we propose the following recursive form of $u$.

###### Lemma 3 (Recursive form of $u$ ) .

With $b=b^{*}$, when $t=T-1$, $\forall s,a$,
$u_{\pi,t}(s,a)=0$, when $t\in[T-2]$, $\forall s,a$,

$$ $\displaystyle u_{\pi,t}(s,a)=\textstyle\nu_{\pi,t}(s,a)+\sum_{s^{\prime},a^{ \prime}}\rho_{t+1}p(s^{\prime}|s,a)\pi_{t+1}(a^{\prime}|s^{\prime})u_{\pi,t+1} (s^{\prime},a^{\prime}).$ (46) $$

Its proof is in Appendix A.8.
This lemma allows us to learn $u$ recursively without approximating the complicated trajectory variance.
Subsequently, the desired optimal behavior policy
$\mu^{*}$ can be easily calculated using (22).
To ensure broad applicability, we utilize the behavior policy-agnostic offline learning setting (Nachum et al.,, ), in which the offline data consists of $\quantity{(t_{i},s_{i},a_{i},r_{i},s_{i}^{\prime})}_{i=1}^{m}$,
with $m$ previously logged data tuples. Those tuples can be generated by one or multiple behavior policies, regardless of whether these policies are known or unknown, and they are not required to form a complete trajectory. In the $i$-th data tuple, $t_{i}$ represents the time step, $s_{i}$ is the state at time step $t_{i}$, $a_{i}$ is the action executed, $r_{i}$ is the sampled reward, and $s_{i}^{\prime}$ is the successor state.
In this paper, we learn $(\mu^{*},b^{*})$ from cheaply available offline data using Fitted $Q$ -Evaluation (FQE, (Le et al.,, )), but our framework is ready to integrate any state-of-the-art offline policy evaluation technique.

###### Lemma 3 (Recursive form of u 𝑢 u italic_u ) .

## 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 offline data informed estimator (ODI, Liu and Zhang, ()), and (3) the doubly robust estimator (DR, Jiang and Li, ()).
In the doubly robust estimator, because they do not design a tailored behavior policy, we leverage the conventional wisdom to use the target policy $\pi$ as the behavior policy.
Given previously logged offline data, our method learns the optimal behavior policy and the optimal baseline tuple $(\mu^{*},b^{*})$ using Algorithm 1. All related methods
learn their required quantities from the same offline dataset to ensure fair comparisons.
Then, we use the behavior policy $\mu^{*}$ for data collection and the baseline $b^{*}$ for data processing. Because our method reduces variance in both the data-collecting and the data-processing phases, we name our method doubly optimal (DOpt) policy evaluation. Our implementation is made publicly available to facilitate future research(^1^11Link available upon publication.).

Figure: Figure 1: Results on Gridworld. 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: x1.png

Gridworld:
We first conduct experiments in Gridworld with $n^{3}$ states,
i.e., an $n\times n$ grid with the time horizon also being $n$.
The number of states in this Gridworld environment scales cubically with $n$, offering a suitable tool to test algorithm scalability. We choose Gridworld with $n^{3}=1,000$ and $n^{3}=27,000$, which are the largest Gridworld environment tested among related works (Jiang and Li,, ; Hanna et al.,, ; Liu and Zhang,, ).
We use randomly generated reward functions with $30$ randomly generated target policies.
The offline data is generated by various unknown policies to simulate cheaply available but segmented offline data.
Because MC methods use each episode as one empirical return sample, we view each episode as one online sample.
We report the *relative error* of the four methods against the number of online samples.
This relative error is the estimation error normalized by the estimation error of the on-policy Monte Carlo estimator after the first episode.
Thus, the relative error of the on-policy Monte Carlo estimator starts from $1$.

Figure 1 shows our method outperforms all baselines by a large margin.
The blue line in the graph is below all other lines, indicating that our method requires fewer samples to achieve the same accuracy.
This is because our designed $(\mu^{*},b^{*})$ substantially reduces estimation variance.
In Table 1, we quantify such variance reduction, showing our method reduces variance by around $75\%$ in both Gridworld with size $1,000$ and $27,000$.
One observation is that DR performs slightly better than ODI in smaller Gridworld but is slightly worse in larger Gridworld, which shows that there might be no dominating relationship between those two methods. Meanwhile, our method is superior to both approaches because the variance reduction of our method comes from both data-collecting and data-processing.
More experiment details are in Appendix B.

Figure: Figure 2: Results on MuJoCo. 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: x2.png

**Table 2: Episodes needed to achieve the same of estimation accuracy that on-policy Monte Carlo achieves with $1000$ episodes. Standard errors are plotted in Figure 2.**
|  | On-policy MC | Ours | ODI | DR | Saved Episodes Percentage |
| --- | --- | --- | --- | --- | --- |
| Ant | 1000 | 492 | 810 | 636 | (1000 - 492)/1000 = 50.8% |
| Hopper | 1000 | 372 | 544 | 582 | (1000 - 372)/1000 = 62.8% |
| I. D. Pendulum | 1000 | 426 | 727 | 651 | (1000 - 426)/1000 = 57.4% |
| I. Pendulum | 1000 | 225 | 356 | 439 | (1000 - 225)/1000 = 77.5% |
| Walker | 1000 | 475 | 705 | 658 | (1000 - 475)/1000 = 52.5% |

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.
Figure 2 shows our method is consistently better than all baselines in various MuJoCo robot environments.
Table 2 shows our method requires substantially fewer samples to achieve the same estimation accuracy compared with the on-policy Monte Carlo method. Specifically, our method saves 50.8% to 77.5% of online interactions in different tasks, achieving state-of-the-art performance in policy evaluation.

It is worth mentioning that our method is robust to hyperparameter choices—all hyperparameters required to learn $(\mu^{*},b^{*})$ in our method are tuned offline and stay the same across all environments.

## 8 Conclusion

Due to the sequential nature of reinforcement learning, policy evaluation often suffers from large variance and requires massive data to achieve the desired level of accuracy.
In this work, we design an optimal combination of data-collecting policy $\mu^{*}$ and data-processing baseline $b^{*}$.

Theoretically, we prove our method considers
larger policy space (Lemma 1), and is unbiased (Lemma 2) and optimal (Theorem 3).
Further, we mathematically quantify the superiority of our method in variance reduction compared with existing methods (Theorem 4, 5, 6).

Empirically, compared with previous best-performing methods, we show our method reduces variance substantially in a broad range of environments, achieving state-of-the-art performance in policy evaluation.

One limitation is, as there is no free lunch, if the offline data size is too small—perhaps consisting of just a single data tuple—the behavior policy and baseline approximated by our method may be inaccurate. In this case, we recommend on-policy evaluation. The future work of our paper is to extend the variance reduction 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.

Given any baseline function $b$, $\forall\mu\in\Lambda^{-}$, $\forall t,s,a$,

$$ $\displaystyle\mu_{t}(a|s)=0$ (47) $\displaystyle\implies$ $\displaystyle\pi_{t}(a|s)=0$ (Definition of $\Lambda^{-}$ ) $\displaystyle\implies$ $\displaystyle\pi_{t}(a|s)u_{\pi,t}(s,a)=0.$ (48) $$

This shows $\mu\in\Lambda$. Thus, $\Lambda^{-}\subseteq\Lambda$.
∎

###### Proof.

### A.2 Proof of Lemma 2

To prove Lemma 2, we first prove the following auxiliary lemma.

###### Lemma 4 .

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

$$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}(\cdot\mid S_{t})}\left[\rho_{t} \quantity[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_ {t}=s\right]=\mathbb{E}_{A_{t}\sim\pi_{t}(\cdot\mid S_{t})}\left[q_{\pi,t}(S_{ t},A_{t})\mid S_{t}=s\right].$ (49) $$

###### Proof.

We fix any baseline function $b$. Because $\mu\in\Lambda$, $\forall t,s,a$,

$$ $\displaystyle\mu_{t}(a|s)=0$ (50) $\displaystyle\implies$ $\displaystyle\pi_{t}(a|s)u_{\pi,t}(s,a)=0$ (51) $\displaystyle\implies$ $\displaystyle\pi_{t}(a|s)\quantity[\quantity(q_{\pi,t}(s,a)-b_{t}(s,a))^{2}+ \nu_{\pi,t}(s,a)+\textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a)\mathbb{V}\left( G^{b}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{\prime}\right)}]=0$ (By ( 23 )) $\displaystyle\implies$ $\displaystyle\pi_{t}(a|s)\quantity(q_{\pi,t}(s,a)-b_{t}(s,a))^{2}=0$ ( $\nu_{\pi,t}(s,a)$ and $\textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a)\mathbb{V}\left(G^{b}(\tau^{\mu^{ *}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{\prime}\right)}$ are non-negative) $\displaystyle\implies$ $\displaystyle\pi_{t}(a|s)\quantity(q_{\pi,t}(s,a)-b_{t}(s,a))=0.$ (52) $$

Then, we have

$$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}(\cdot\mid S_{t})}\left[\rho_{t} \quantity[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_ {t}=s\right]$ (53) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}(\cdot\mid S_{t})}\left[\frac{\pi_{t} (A_{t}|S_{t})}{\mu_{t}(A_{t}|S_{t})}\quantity[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{ t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_{t}=s\right]$ (54) $\displaystyle=$ $\displaystyle\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\mu_{t}(a|s)\quantity[\frac {\pi_{t}(a|s)}{\mu_{t}(a|s)}[q_{\pi,t}(s,a)-b_{t}(s,a)]+\bar{b}_{t}(s)]$ (55) $\displaystyle=$ $\displaystyle\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\pi_{t}(a|s)[q_{\pi,t}(s,a) -b_{t}(s,a)]+\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\mu_{t}(a|s)\bar{b}_{t}(s)$ (56) $\displaystyle=$ $\displaystyle\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\pi_{t}(a|s)[q_{\pi,t}(s,a) -b_{t}(s,a)]+\bar{b}_{t}(s)\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\mu_{t}(a|s)$ (57) $\displaystyle=$ $\displaystyle\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\pi_{t}(a|s)[q_{\pi,t}(s,a) -b_{t}(s,a)]+\bar{b}_{t}(s)$ (58) $\displaystyle=$ $\displaystyle\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\pi_{t}(a|s)[q_{\pi,t}(s,a) -b_{t}(s,a)]$ (59) $\displaystyle+\sum_{a\in\quantity{a|\mu_{t}(a|s)=0}}\pi_{t}(a|s)[q_{\pi,t}(s,a )-b_{t}(s,a)]+\bar{b}_{t}(s)$ (By ( 52 )) $\displaystyle=$ $\displaystyle\sum_{a}\pi_{t}(a|s)[q_{\pi,t}(s,a)-b_{t}(s,a)]+\bar{b}_{t}(s)$ (60) $\displaystyle=$ $\displaystyle\sum_{a}\pi_{t}(a|s)q_{\pi,t}(s,a)-\bar{b}_{t}(s)+\bar{b}_{t}(s)$ (By ( 3 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A\sim\pi}\quantity[q_{\pi,t}(S_{t},A_{t})\mid S_{t}=s ].x$ (61) $$

∎

Now, we are ready to prove Lemma 2.
See 2

###### Proof.

Fix any baseline function $b$.
We proceed via induction.

For $t=T-1$, $\forall\mu\in\Lambda$, $\forall s$,
we have

$$ $\displaystyle\mathbb{E}\left[G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right]$ (62) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}(\cdot|S_{t})}\left[\rho_{t}[R_{t+1}- b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_{t}\right]$ (63) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}(\cdot|S_{t})}\left[\rho_{t}[q_{\pi,t }(S_{t},A_{t})-b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_{t}\right]$ (64) $\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 4 ) $\displaystyle=$ $\displaystyle v_{\pi,t}(S_{t}).$ (65) $$

For $t\in[T-2]$,
assuming that Lemma 2 holds for $t+1$,
we have $\forall\mu\in\Lambda$, $\forall s$,

$$ $\displaystyle\mathbb{E}\quantity[G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{ t+1}=s]=v_{\pi,t+1}(s).$ (66) $$

Then, $\forall t$,

$$ $\displaystyle\mathbb{E}\left[G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right]$ (67) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\rho_{t}\left(R_{t+1}+G^{b}(\tau^{\mu_{t+1:T-1}}_ {t+1:T-1})-b_{t}(S_{t},A_{t})\right)+\bar{b}_{t}(S_{t}))\mid S_{t}\right]$ (By ( 2 )) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\rho_{t}(R_{t+1}-b_{t}(S_{t},A_{t}))+\bar{b}_{t}( S_{t})\mid S_{t}\right]+\mathbb{E}\left[\rho_{t}G^{b}(\tau^{\mu_{t+1:T-1}}_{t+ 1:T-1})\mid S_{t}\right]$ (68) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\rho_{t}(R_{t+1}-b_{t}(S_{t},A_{t}))+\bar{b}_{t}( S_{t})\mid S_{t}\right]$ (69) $\displaystyle+\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^{b}(\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 Iterated Expectation) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\rho_{t}(R_{t+1}-b_{t}(S_{t},A_{t}))+\bar{b}_{t}( S_{t})\mid S_{t}\right]$ (70) $\displaystyle+\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^{b}(\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}-b_{t}(S_{t},A_{t}))+\bar{b}_{t}( S_{t})\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} \quantity[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{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 4 ) $\displaystyle=$ $\displaystyle v_{\pi,t}(s),$ (71) $$

which completes the proof.
∎

###### Lemma 4 .

###### Proof.

###### Proof.

### A.3 Proof of Theorem 1

To prove Theorem 1, we first characterize the variance of the off-policy estimator in a recursive form.

###### Lemma 5 .

$\forall b$, $\forall\mu\in\Lambda$,
for $t=T-1$,

$$ $\displaystyle\mathbb{V}\left(G^{b}(\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}(S_{t},A_{t})-b_{t} (S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t})]^{2};$ (72) $$

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

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}\right)$ (73) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{ S_{t+1}}\left[\mathbb{V}\left(G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})+[q_{\pi,t}(S_{t},A_{t})-b _{t}(S_{t},A_{t})]^{2}\right)\mid S_{t}\right]$ (74) $\displaystyle-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t})]^{2}.$ (75) $$

###### Proof.

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

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}\right)$ (76) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\mathbb{V}\left(G^{b}(\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^{b}(\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[\mathbb{V}\left(\rho_{t}\quantity[r(S_{t} ,A_{t})+G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})-b_{t}(S_{t},A_{t})]+\bar{b}_{t}( S_{t})\mid S_{t},A_{t}\right)\mid S_{t}\right]$ (77) $\displaystyle+\mathbb{V}_{A_{t}}\left(\mathbb{E}\left[\rho_{t}\quantity[r(S_{t },A_{t})+G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})-b_{t}(S_{t},A_{t})]+\bar{b}_{t} (S_{t}))\mid S_{t},A_{t}\right]\mid S_{t}\right)$ (By ( 2 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\mathbb{V}\left(G^{b}(\tau^{ \mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right)\mid S_{t}\right]$ (78) $\displaystyle+\mathbb{V}_{A_{t}}\quantity(\rho_{t}[r(S_{t},A_{t})+\mathbb{E} \left[G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right]-b_{t}(S_{t} ,A_{t})]+\bar{b}_{t}(S_{t})\mid S_{t})$ ( $r(S_{t},A_{t}),b_{t}(S_{t},A_{t}),\bar{b}_{t}(S_{t})$ are constant given $S_{t},A_{t}$ ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\mathbb{V}\left(G^{b}(\tau^{ \mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right)\mid S_{t}\right]$ (79) $\displaystyle+\mathbb{V}_{A_{t}}\quantity(\rho_{t}[r(S_{t},A_{t})+\mathbb{E} \left[v_{\pi,t+1}(S_{t+1})\mid S_{t},A_{t}\right]-b_{t}(S_{t},A_{t})]+\bar{b}_ {t}(S_{t})\mid S_{t})$ (Lemma 2 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\mathbb{V}\left(G^{b}(\tau^{ \mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right)\mid S_{t}\right]$ (80) $\displaystyle+\makebox[337.86465pt]{$\displaystyle\mathbb{V}_{A_{t}}\quantity( \rho_{t}[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_{ t}).$\hfill(Defintion of $q_{\pi,t}$)}$ (81) $$

For the inner part of the first term, we have

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A _{t}\right)$ (82) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b}(\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]$ (83) $\displaystyle+\mathbb{V}_{S_{t+1}}\left(\mathbb{E}\left[G^{b}(\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^{b}(\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^{b}(\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^{b}(\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 2 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b}(\tau^{\mu_{t+1:T- 1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t}).$ (By ( 21 )) (84) $$

For the second term, we have

$$ $\displaystyle\nu_{t}(S_{t},A_{t})$ (85) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}}\quantity(\rho_{t}[q_{\pi,t}(S_{t},A_{t})-b_{t} (S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_{t})$ (By ( 21 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\quantity(\rho_{t}[q_{\pi,t}(S_{t},A_{t}) -b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t}))^{2}\mid S_{t}\right]$ (86) $\displaystyle-\left(\mathbb{E}_{A_{t}}\left[\rho_{t}[q_{\pi,t}(S_{t},A_{t})-b_ {t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_{t}\right]\right)^{2}$ (87) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\quantity(\rho_{t}[q_{\pi,t}(S_{t},A_{t}) -b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t}))^{2}\mid S_{t}\right]-v_{\pi,t}(S_{t}) ^{2}.$ (Lemma 4 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{t},A_{t})-b_{t} (S_{t},A_{t})]^{2}\mid S_{t}\right]+2\bar{b}_{t}(S_{t})\mathbb{E}_{A_{t}}\left [\rho_{t}[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]\mid S_{t}\right]$ (88) $\displaystyle+\bar{b}_{t}(S_{t})^{2}-v_{\pi,t}(S_{t})^{2}$ (89) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{t},A_{t})-b_{t} (S_{t},A_{t})]^{2}\mid S_{t}\right]+2\bar{b}_{t}(S_{t})\mathbb{E}_{A_{t}}\left [\rho_{t}[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_ {t}\right]$ (90) $\displaystyle-2\bar{b}_{t}(S_{t})^{2}+\bar{b}_{t}(S_{t})^{2}-v_{\pi,t}(S_{t})^ {2}$ (91) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{t},A_{t})-b_{t} (S_{t},A_{t})]^{2}\mid S_{t}\right]+2\bar{b}_{t}(S_{t})v_{\pi,t}(S_{t})$ (92) $\displaystyle-\bar{b}_{t}(S_{t})^{2}-v_{\pi,t}(S_{t})^{2}$ (Lemma 2 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{t},A_{t})-b_{t} (S_{t},A_{t})]^{2}\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}.$ (93) $$

Plugging (84) and (93) back to (81) gives

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}\right)$ (94) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\mathbb{V}\left(G^{b}(\tau^{ \mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t},A_{t}\right)\mid S_{t}\right]$ (95) $\displaystyle+\mathbb{V}_{A_{t}}\quantity(\rho_{t}[q_{\pi,t}(S_{t},A_{t})-b_{t }(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_{t})$ (By ( 81 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{S_{t+1}} \left[\mathbb{V}\left(G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right) \mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\right)\mid S_{t}\right]$ (96) $\displaystyle+\mathbb{V}_{A_{t}}\quantity(\rho_{t}[q_{\pi,t}(S_{t},A_{t})-b_{t }(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_{t})$ (By ( 84 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{S_{t+1}} \left[\mathbb{V}\left(G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right) \mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\right)\mid S_{t}\right]$ (97) $\displaystyle+\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{t},A_{t})-b_{t }(S_{t},A_{t})]^{2}\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}$ (By ( 93 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{S_{t+1}} \left[\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1} \right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})+[q_{\pi,t}(S_{t},A_{t})-b_ {t}(S_{t},A_{t})]^{2}\right)\mid S_{t}\right]$ (98) $\displaystyle-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t})]^{2}.$ (99) $$

When $t=T-1$, we have

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}\right)$ (100) $\displaystyle=$ $\displaystyle\mathbb{V}\left(\rho_{t}[r(S_{t},A_{t})-b_{t}(S_{t},A_{t})]+\bar{ b}_{t}(S_{t})\mid S_{t}\right)$ (By ( 2 )) $\displaystyle=$ $\displaystyle\mathbb{V}\left(\rho_{t}[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t} )]+\bar{b}_{t}(S_{t})\mid S_{t}\right)$ (101) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{t},A_{t})-b_{t} (S_{t},A_{t})]^{2}\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2},$ (By ( 93 )) $$

which completes the proof.
∎

We now restate Theorem 1 and give its proof.

See 1

###### Proof.

Fix a baseline function $b$. $\forall t,s,a$,

$$ $\displaystyle\mu^{*}_{t}(a|s)=0$ (102) $\displaystyle\implies$ $\displaystyle\pi_{t}(a|s)\sqrt{u_{\pi,t}(s,a)}=0$ (By ( 22 )) $\displaystyle\implies$ $\displaystyle\pi_{t}(a|s)u_{\pi,t}(s,a)=0.$ (103) $$

Thus, $\mu^{*}\in\Lambda$.

$\forall t$, $\forall\mu\in\Lambda$, we have an unbiasedness on $\sqrt{u_{\pi,t}(s,a)}$.

$$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}\sqrt{u_{\pi,t}(S_{t}, A_{t})}\mid S_{t}=s\right]$ (104) $\displaystyle=$ $\displaystyle\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\mu_{t}(a|s)\frac{\pi_{t}(a |s)}{\mu_{t}(a|s)}\sqrt{u_{\pi,t}(s,a)}$ (105) $\displaystyle=$ $\displaystyle\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\pi_{t}(a|s)\sqrt{u_{\pi,t} (s,a)}$ (106) $\displaystyle=$ $\displaystyle\sum_{a\in\quantity{a|\mu_{t}(a|s)>0}}\pi_{t}(a|s)\sqrt{u_{\pi,t} (s,a)}+\sum_{a\in\quantity{a|\mu_{t}(a|s)=0}}\pi_{t}(a|s)\sqrt{u_{\pi,t}(s,a)}$ ( $\forall\mu\in\Lambda,\mu_{t}(a|s)=0\implies\pi_{t}(a|s)u_{\pi,t}(s,a)=0$ by ( 25 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u_{\pi,t}(S_{t},A_{t})} \mid S_{t}=s\right].$ (107) $$

We prove the optimality of the behavior policy $\mu^{*}$ via induction.

When $t=T-1$, $\forall\mu\in\Lambda$, $\forall s$, the variance of the off-policy estimator has the following lower bound

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (109) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{t},A _{t})-b_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S _{t}))^{2}$ (Lemma 5 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}u_{\pi,t}(S_{t},A_ {t})\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}$ (By ( 23 )) $\displaystyle\geq$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}\sqrt{u_{\pi,t}(S_{t}, A_{t})}\mid S_{t}\right]^{2}-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}$ (By Jensen’s Inequality) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u_{\pi,t}(S_{t},A_{t})} \mid S_{t}\right]^{2}-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}.$ (By ( 107 )) $$

For any state $s$, the variance of the off-policy estimator with the behavior policy $\mu^{*}$ achieves this lower bound by the following derivations.

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (110) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{ t},A_{t})-b_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{ t}(S_{t}))^{2}$ (Lemma 5 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}u_{\pi,t}(S_{t },A_{t})\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}.$ (By ( 23 )) $$

For the first term, we have

$$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}u_{\pi,t}(S_{t },A_{t})\mid S_{t}\right]$ (111) $\displaystyle=$ $\displaystyle\sum_{a}\frac{\pi_{t}(a|S_{t})^{2}}{\mu^{*}_{t}(a|S_{t})}u_{\pi,t }(S_{t},a)$ (112) $\displaystyle=$ $\displaystyle\sum_{a}\pi_{t}(a|S_{t})\sqrt{u_{\pi,t}(S_{t},a)}\sum_{b}\pi_{t}( S_{t},b)\sqrt{u_{\pi,t}(S_{t},b)}$ (By ( 22 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u_{\pi,t}(S_{t},A_{t})} \mid S_{t}\right]^{2}.$ (113) $$

Plugging (113) back to (110), we obtain

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (114) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}u_{\pi,t}(S_{t },A_{t})\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}$ (115) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u_{\pi,t}(S_{t},A_{t})} \mid S_{t}\right]^{2}-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}.$ (116) $$

Thus, the behavior policy $\mu^{*}$ defined in (22) is an optimal solution to the optimization problems

$$ $\displaystyle\min_{\mu}\quad$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (117) s.t. $\displaystyle\mu\in\Lambda$ (118) $$

for $t=T-1$ and all $s$.

When $t\in[T-2]$, we proceed via induction. The inductive hypothesis is that the behavior policy $\mu^{*}$ is an optimal solution to the optimization problems

$$ $\displaystyle\min_{\mu}\quad$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t}=s\right)$ (119) s.t. $\displaystyle\mu\in\Lambda$ (120) $$

for all $s$.

To complete the induction,
we prove that the behavior policy $\mu^{*}$ is an optimal solution to the optimization problems

$$ $\displaystyle\min_{\mu}\quad$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (121) s.t. $\displaystyle\mu\in\Lambda$ (122) $$

for all $s$.

$\forall\mu\in\Lambda$, $\forall s$, the variance of the off-policy estimator has the following lower bound

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (123) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{ S_{t+1}}\left[\mathbb{V}\left(G^{b}(\tau^{\mu_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})+[q_{\pi,t}(S_{t},A_{t})-b _{t}(S_{t},A_{t})]^{2}\right)\mid S_{t}\right]$ (124) $\displaystyle-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t})]^{2}$ (Lemma 5 ) $\displaystyle\geq$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{ S_{t+1}}\left[\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_ {t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})+[q_{\pi,t}(S_{t},A_{t })-b_{t}(S_{t},A_{t})]^{2}\right)\mid S_{t}\right]$ (125) $\displaystyle-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t})]^{2}$ (Indutive Hypothesis) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}u_{\pi,t}(S_{t},A_ {t})\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}$ (By ( 23 )) $\displaystyle\geq$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}\sqrt{u_{\pi,t}(S_{t}, A_{t})}\mid S_{t}\right]^{2}-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}$ (By Jensen’s Inequality) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u_{\pi,t}(S_{t},A_{t})} \mid S_{t}\right]^{2}-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}.$ (By ( 107 )) $$

For any state $s$, the variance of the off-policy estimator with the behavior policy $\mu^{*}$ achieves the lower bound by the following derivations.

$$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (126) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}\left(\mathbb{E}_{ S_{t+1}}\left[\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_ {t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})+[q_{\pi,t}(S_{t},A_{t })-b_{t}(S_{t},A_{t})]^{2}\right)\mid S_{t}\right]$ (127) $\displaystyle-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t})]^{2}$ (Lemma 5 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}u_{\pi,t}(S_{t },A_{t})\mid S_{t}\right]-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}$ (By ( 23 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u_{\pi,t}(S_{t},A_{t})} \mid S_{t}\right]^{2}-(v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t}))^{2}.$ (By ( 113 )) $$

Thus, the behavior policy $\mu^{*}$ defined in (22) is an optimal solution to the optimization problems

$$ $\displaystyle\min_{\mu}\quad$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (128) s.t. $\displaystyle\mu\in\Lambda$ (129) $$

for $t$ and all $s$.

This completes the induction.
∎

###### Lemma 5 .

###### Proof.

###### Proof.

### A.4 Proof of Theorem 2

In this proof, to differentiate different $\mu^{*}$ with different baseline functions $b$, we use $\mu^{*,b}$ to denote the corresponding $\mu^{*}$ when using a function $b$ as the baseline function. $G^{b}$, $u^{b}_{\pi,t}$, and $\Lambda^{b}$ are defined following the same convention.
We first present an auxiliary lemma.

###### Lemma 6 .

$\forall b$, $\forall\mu\in\Lambda^{b}$, $\forall t$,

$$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{t},A _{t})-b_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S _{t})]^{2}$ (130) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu_{t}}\left(\rho_{t}[q_{\pi,t}(S_{t},A_{t} )-b_{t}(S_{t},A_{t})]\mid S_{t}\right)$ (131) $$

###### Proof.

$\forall b$, $\forall\mu\in\Lambda^{b}$, $\forall t$,

$$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{t},A _{t})-b_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S _{t})]^{2}$ (132) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu_{t}}\left(\rho_{t}[q_{\pi,t}(S_{t},A_{t} )-b_{t}(S_{t},A_{t})]\mid S_{t}\right)+\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho _{t}[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]\mid S_{t}\right]^{2}$ (133) $\displaystyle-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t})]^{2}$ (134) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu_{t}}\left(\rho_{t}[q_{\pi,t}(S_{t},A_{t} )-b_{t}(S_{t},A_{t})]\mid S_{t}\right)+\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho _{t}[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]\mid S_{t}\right]^{2}$ (135) $\displaystyle-[\mathbb{E}_{A_{t}\sim\mu_{t}(\cdot\mid S_{t})}\left[\rho_{t} \quantity[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]+\bar{b}_{t}(S_{t})\mid S_ {t}\right]-\bar{b}_{t}(S_{t})]^{2}$ (Definition of $q_{\pi,t}$ , Lemma 4 ) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu_{t}}\left(\rho_{t}[q_{\pi,t}(S_{t},A_{t} )-b_{t}(S_{t},A_{t})]\mid S_{t}\right)+\mathbb{E}_{A_{t}\sim\mu_{t}}\left[\rho _{t}[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]\mid S_{t}\right]^{2}$ (136) $\displaystyle-\mathbb{E}_{A_{t}\sim\mu_{t}(\cdot\mid S_{t})}\left[\rho_{t} \quantity[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{t},A_{t})]\mid S_{t}\right]^{2}$ (137) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu_{t}}\left(\rho_{t}[q_{\pi,t}(S_{t},A_{t} )-b_{t}(S_{t},A_{t})]\mid S_{t}\right).$ (138) $$

∎

We now restate Theorem 2 and give its proof.
See 2

###### Proof.

We prove this by induction on the time step $t$.

When $t=T-1$, $\forall s,$ the optimization problem (32) has the following lower bound

$$ $\displaystyle\mathbb{V}(G^{b}(\tau^{\mu^{*,b}_{t:T-1}}_{t:T-1})\mid S_{0}=s)$ (139) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b}_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S _{t},A_{t})-b_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t})-\bar{b} _{t}(S_{t})]^{2}$ (Lemma 5 ) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu^{*,b}_{t}}\left(\rho_{t}[q_{\pi,t}(S_{t} ,A_{t})-b_{t}(S_{t},A_{t})]\mid S_{t}\right)$ (Lemma 6 ) $\displaystyle\geq$ $\displaystyle 0.$ (Variance non-negativity) $$

When using $b^{*}$ as the baseline, we achieve this lower bound.

$$ $\displaystyle\mathbb{V}(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t:T-1}}_{t:T-1})\mid S_ {0}=s)$ (140) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left[\rho_{t}^{2}[q_{\pi, t}(S_{t},A_{t})-b^{*}_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t}) -\bar{b}^{*}_{t}(S_{t})]^{2}$ (Lemma 5 ) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left(\rho_{t}[q_{\pi,t}(S _{t},A_{t})-b^{*}_{t}(S_{t},A_{t})]\mid S_{t}\right)$ (Lemma 6 ) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left(\rho_{t}[q_{\pi,t}(S _{t},A_{t})-q_{\pi,t}(S_{t},A_{t})]\mid S_{t}\right)$ (Definition of $b^{*}$ ( 31 )) $\displaystyle=$ $\displaystyle 0.$ (141) $$

When $t\in[T-2]$, we proceed via induction. The inductive hypothesis is that the baseline function $b^{*}$ is an optimal solution to the optimization problems

$$ $\displaystyle\min_{b}\quad$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu^{*,b}_{t+1:T-1}}_{t+1:T-1})\mid S _{t}=s\right)$ (142) $$

for all $s$.
Notice that we have

$$ $\displaystyle\Lambda^{b}\subseteq\Lambda^{b^{*}}.$ (143) $$

This is because $\forall s,a$,

$$ $\displaystyle u^{b}_{\pi,t}(s,a)$ (144) $\displaystyle=$ $\displaystyle\quantity(q_{\pi,t}(s,a)-b_{t}(s,a))^{2}+\nu_{\pi,t}(s,a)+ \textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a)\mathbb{V}\left(G^{b}(\tau^{\mu^{ *,b}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{\prime}\right)}$ (By ( 23 )) $\displaystyle\geq$ $\displaystyle\nu_{\pi,t}(s,a)+\textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a) \mathbb{V}\left(G^{b}(\tau^{\mu^{*,b}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{ \prime}\right)}$ (145) $\displaystyle\geq$ $\displaystyle\nu_{\pi,t}(s,a)+\textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a) \mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }=s^{\prime}\right)}$ (Inductive Hypothesis) $\displaystyle\geq$ $\displaystyle u^{b^{*}}_{\pi,t}(s,a).$ (146) $$

Thus, $\forall\mu\in\Lambda^{b}$, we have $\forall s,a$

$$ $\displaystyle\mu(a|s)=0$ (147) $\displaystyle\implies$ $\displaystyle\pi(a|s)u^{b}_{\pi,t}(s,a)=0$ (148) $\displaystyle\implies$ $\displaystyle\pi(a|s)u^{b^{*}}_{\pi,t}(s,a)=0.$ (149) $$

This shows

$$ $\displaystyle\Lambda^{b}\subseteq\Lambda^{b^{*}}.$ (150) $$

$\forall b$, the optimization problem (32) has the following lower bound

$$ $\displaystyle\mathbb{V}\quantity(G^{b}(\tau^{\mu^{*,b}_{t:T-1}}_{t:T-1})\mid S _{0}=s)$ (151) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b}_{t}}\left[\rho_{t}^{2}\left( \mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b}(\tau^{\mu^{*,b}_{t+1:T-1}}_{t+ 1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\right) \mid S_{t}\right]$ (152) $\displaystyle+\mathbb{E}_{A_{t}\sim\mu^{*,b}_{t}}\left[\rho_{t}^{2}[q_{\pi,t}( S_{t},A_{t})-b_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t})-\bar{b }_{t}(S_{t})]^{2}$ (Lemma 5 ) $\displaystyle\geq$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b}_{t}}\left[\rho_{t}^{2}\left( \mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T -1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t}) \right)\mid S_{t}\right]$ (153) $\displaystyle+\mathbb{E}_{A_{t}\sim\mu^{*,b}_{t}}\left[\rho_{t}^{2}[q_{\pi,t}( S_{t},A_{t})-b_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t})-\bar{b }_{t}(S_{t})]^{2}$ (Inductive hypothesis) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b}_{t}}\left[\rho_{t}^{2}\left( \mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T -1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t}) \right)\mid S_{t}\right]$ (154) $\displaystyle+\mathbb{V}_{A_{t}\sim\mu^{*,b}_{t}}\left(\rho_{t}[q_{\pi,t}(S_{t },A_{t})-b_{t}(S_{t},A_{t})]\mid S_{t}\right)$ (Lemma 6 ) $\displaystyle\geq$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b}_{t}}\left[\rho_{t}^{2}\left( \mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T -1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t}) \right)\mid S_{t}\right]$ (Variance non-negativity) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b}_{t}}\left[\rho_{t}^{2}u^{b^{*}}_{ \pi,t}(S_{t},A_{t})\mid S_{t}\right]$ (By ( 23 )) $\displaystyle\geq$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b}_{t}}\left[\rho_{t}\sqrt{u^{b^{*}}_ {\pi,t}(S_{t},A_{t})}\mid S_{t}\right]^{2}$ (Jensen’s inequality) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{\pi,t}(S_{t}, A_{t})}\mid S_{t}\right]^{2}$ (By ( 107 ) and ( 143 )) $$

When setting $\forall s,\forall a,b^{*}_{t}(s,a)\doteq q_{\pi,t}(s,a)$ as the baseline, we achieve this lower bound.

$$ $\displaystyle\mathbb{V}\quantity(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t:T-1}}_{t:T-1 })\mid S_{0}=s)$ (155) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left[\rho_{t}^{2}\left( \mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T -1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t}) \right)\mid S_{t}\right]$ (156) $\displaystyle+\mathbb{E}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left[\rho_{t}^{2}[q_{\pi ,t}(S_{t},A_{t})-b^{*}_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t} )-\bar{b}^{*}_{t}(S_{t})]^{2}$ (Lemma 5 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left[\rho_{t}^{2}\left( \mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T -1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t}) \right)\mid S_{t}\right]$ (157) $\displaystyle+\mathbb{V}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left(\rho_{t}[q_{\pi,t}( S_{t},A_{t})-b^{*}_{t}(S_{t},A_{t})]\mid S_{t}\right)$ (Lemma 6 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left[\rho_{t}^{2}\left( \mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T -1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t}) \right)\mid S_{t}\right]$ (158) $\displaystyle+\mathbb{V}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left(\rho_{t}[q_{\pi,t}( S_{t},A_{t})-q_{\pi,t}(S_{t},A_{t})]\mid S_{t}\right)$ (Definition of $b^{*}$ ( 31 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left[\rho_{t}^{2}\left( \mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T -1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t}) \right)\mid S_{t}\right]$ (159) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left[\rho_{t}^{2}u^{b^{*} }_{\pi,t}(S_{t},A_{t})\mid S_{t}\right]$ (By ( 23 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{\pi,t}(S_{t}, A_{t})}\mid S_{t}\right]^{2}$ (By ( 22 )) $$

Thus, $b^{*}$ is the optimal solution to the optimization problem

$$ $\displaystyle\min_{b}\quad$ $\displaystyle\mathbb{V}\left(G^{b}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (160) $$

for all $t$ and $s$.

∎

###### Lemma 6 .

###### Proof.

###### Proof.

### A.5 Proof of Theorem 4

###### Proof.

Use $u^{b^{*}}_{t}$ to denote $u_{t}$ (23) using $b^{*}$ as the baseline function. Then, by (23), for $t=T-1$,

$$ $\displaystyle u^{b^{*}}_{t}(s,a)=\quantity[q_{\pi,t}(s,a)-b_{t}(s,a)]^{2}=0.$ (161) $$

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

$$ $\displaystyle u^{b^{*}}_{t}(s,a)$ (162) $\displaystyle=$ $\displaystyle\quantity(q_{\pi,t}(s,a)-b_{t}(s,a))^{2}+\nu_{\pi,t}(s,a)+ \textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a)\mathbb{V}\left(G^{b^{*}}(\tau^{ \mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{\prime}\right)}$ (By ( 23 )) $\displaystyle=$ $\displaystyle\nu_{\pi,t}(s,a)+\textstyle{\sum_{s^{\prime}}p(s^{\prime}|s,a) \mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }=s^{\prime}\right).}$ (By ( 31 )) (163) $$

The variance of $G^{b^{*}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})$ has
$\forall s$, for $t=T-1$,

$$ $\displaystyle\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{ t}=s\right)$ (165) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}[q_{\pi,t}(S_{ t},A_{t})-b^{*}_{t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t})-\bar{ b^{*}}_{t}(S_{t})]^{2}$ (Lemma 5 ) $\displaystyle=$ $\displaystyle 0$ (Definition of $b^{*}$ ( 31 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}u^{b^{*}}_{t}( S_{t},A_{t})\mid S_{t}\right]$ (By ( 161 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{t}(S_{t},A_{t })}\mid S_{t}\right]^{2}.$ (By ( 113 )) $$

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

$$ $\displaystyle\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_{ t}=s\right)$ (166) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}\left(\mathbb{ E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1} )\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})+[q_{\pi,t}(S_ {t},A_{t})-b_{t}(S_{t},A_{t})]^{2}\right)\mid S_{t}\right]$ (Lemma 5 ) $\displaystyle-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t})]^{2}$ (167) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}\left(\mathbb{ E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1} )\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\right)\mid S_ {t}\right]$ (168) $\displaystyle+\mathbb{V}_{A_{t}\sim\mu^{*}_{t}}\left(\rho_{t}[q_{\pi,t}(S_{t}, A_{t})-b^{*}_{t}(S_{t},A_{t})]\mid S_{t}\right)$ (Lemma 6 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}\left(\mathbb{ E}_{S_{t+1}}\left[\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1} )\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\right)\mid S_ {t}\right]$ (By ( 31 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*}_{t}}\left[\rho_{t}^{2}u^{b^{*}}_{t}( S_{t},A_{t})\mid S_{t}\right]$ (By ( 163 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{t}(S_{t},A_{t })}\mid S_{t}\right]^{2}.$ (By ( 113 )) $$

The variance of $G^{\text{PDIS}}(\tau^{\pi_{t:T-1}}_{t:T-1})$ has
$\forall s$, for $t-T-1$,

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S _{t}=s\right)$ (169) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[q_{\pi,t}(S_{t},A_{t})^{2}\mid S _{t}\right]-v_{\pi,t}(S_{t})^{2}$ (Lemma 5 with $b=0$ and on-policy) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t})\mid S_{ t}\right)$ (Lemma 6 with $b=0$ and on-policy) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[u^{b^{*}}_{t}(S_{t},A_{t})\mid S _{t}\right]+\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t})\mid S_{t }\right).$ (By ( 163 )) $$

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

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S _{t}=s\right)$ (171) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1} \right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})+q_{\pi,t}(S_{t},A_{t})^{2} \mid S_{t}\right]$ (172) $\displaystyle-v_{\pi,t}(S_{t})^{2}$ (Lemma 5 with $b=0$ ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1} \right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\mid S_{t}\right]$ (173) $\displaystyle+\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t})\mid S_ {t}\right)$ (Lemma 6 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\mid S_{t}\right]$ (174) $\displaystyle+\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t})\mid S_ {t}\right)$ (175) $\displaystyle+\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1} \right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1}) \mid S_{t+1}\right)\mid S_{t},A_{t}\right]\mid S_{t}\right]$ (176) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[u^{b^{*}}_{t}(S_{t},A_{t})\mid S _{t}\right]$ (177) $\displaystyle+\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t})\mid S_ {t}\right)$ (178) $\displaystyle+\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1} \right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1}) \mid S_{t+1}\right)\mid S_{t},A_{t}\right]\mid S_{t}\right].$ (By ( 163 )) $$

Thus, for $t=T-1$, their difference is

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S _{t}=s\right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_ {t}=s\right)$ (179) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[u^{b^{*}}_{t}(S_{t},A_{t})\mid S _{t}\right]-\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{t}(S_{t},A_{t} )}\mid S_{t}\right]^{2}$ (180) $\displaystyle+\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t})\mid S_ {t}\right)$ (By ( 165 ) and ( 169 )) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\pi_{t}}\quantity(\sqrt{u^{b^{*}}_{t}(S_{t}, A_{t})}\mid S_{t})+\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t}) \mid S_{t}\right).$ (181) $$

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

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S _{t}=s\right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t:T-1}}_{t:T-1})\mid S_ {t}=s\right)$ (182) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[u^{b^{*}}_{t}(S_{t},A_{t})\mid S _{t}\right]-\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{t}(S_{t},A_{t} )}\mid S_{t}\right]^{2}$ (183) $\displaystyle+\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t})\mid S_ {t}\right)$ (184) $\displaystyle+\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1} \right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t +1}\right)\mid S_{t},A_{t}\right]\mid S_{t}\right]$ (By ( 166 ) and ( 171 )) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\pi_{t}}\quantity(\sqrt{u^{b^{*}}_{t}(S_{t}, A_{t})}\mid S_{t})$ (185) $\displaystyle+\mathbb{V}_{A_{t}\sim\pi_{t}}\left(q_{\pi,t}(S_{t},A_{t})\mid S_ {t}\right)$ (186) $\displaystyle+\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1} \right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t +1}\right)\mid S_{t},A_{t}\right]\mid S_{t}\right].$ (187) $$

We use induction to prove $\forall t,s,\delta^{\text{ON, ours}}_{t}(s)\geq 0$.
For $t=T-1$,

$$ $\displaystyle\delta^{\text{ON, ours}}_{t}(s)=0\geq 0.$ (189) $$

For $t\in[T-2]$, the induction hypothesis is $\forall s$,

$$ $\displaystyle\delta^{\text{ON, ours}}_{t+1}(s)\geq 0.$ (190) $$

This implies $\forall s$,

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1}) \mid S_{t+1}=s\right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1: T-1})\mid S_{t+1}=s\right)$ (191) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t+1}\sim\pi_{t+1}}\quantity(\sqrt{u^{b^{*}}_{t+1}( S_{t+1},A_{t+1})}\mid S_{t+1}=s)$ (192) $\displaystyle+\mathbb{V}_{A_{t+1}\sim\pi_{t+1}}\left(q_{\pi,t+1}(S_{t+1},A_{t+ 1})\mid S_{t+1}=s\right)+\delta^{\text{ON, ours}}_{t+1}(s)$ (193) $\displaystyle\geq$ $\displaystyle 0.$ (194) $$

Thus, $\forall s$,

$$ $\displaystyle\delta^{\text{ON, ours}}_{t}(s)$ (195) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t},S_{t+1}}\left[\mathbb{V}\left(G^{ \text{PDIS}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)-\mathbb{V} \left(G^{b^{*}}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{ t}=s\right]$ (196) $\displaystyle\geq$ $\displaystyle 0.$ (by ( 194 )) (197) $$

Thus, $\forall t,s,\delta^{\text{ON, ours}}_{t}(s)\geq 0$.

∎

###### Proof.

### A.6 Proof of Theorem 5

###### Proof.

The variance of $G^{\text{PDIS}}(\tau^{\mu^{*,\text{PDIS}}_{t:T-1}}_{t:T-1})$ has
$\forall s$, for $t=T-1$,

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*,\text{PDIS}}_{t:T-1} }_{t:T-1})\mid S_{t}=s\right)$ (198) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2}q_ {\pi,t}(S_{t},A_{t})^{2}\mid S_{t}\right]-v_{\pi,t}(S_{t})^{2}$ (Lemma 5 and $b=0$ ) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left(\rho_{t}q_{\pi ,t}(S_{t},A_{t})\mid S_{t}\right)$ (By ( 131 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2}u^ {b^{*}}_{t}(S_{t},A_{t})\mid S_{t}\right]+\mathbb{V}_{A_{t}\sim\mu^{*,\text{ PDIS}}_{t}}\left(\rho_{t}q_{\pi,t}(S_{t},A_{t})\mid S_{t}\right)$ (By ( 163 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{t}(S_{t},A_{t })}\mid S_{t}\right]^{2}+\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left( \rho_{t}q_{\pi,t}(S_{t},A_{t})\mid S_{t}\right).$ (By ( 113 )) $$

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

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*,\text{PDIS}}_{t:T-1} }_{t:T-1})\mid S_{t}=s\right)$ (199) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2} \left(\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*, \text{PDIS}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+ \nu_{t}(S_{t},A_{t})+q_{\pi,t}(S_{t},A_{t})^{2}\right)\mid S_{t}\right]$ (200) $\displaystyle-v_{\pi,t}(S_{t})^{2}$ (Lemma 5 with $b=0$ ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2} \left(\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*, \text{PDIS}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+ \nu_{t}(S_{t},A_{t})\right)\mid S_{t}\right]$ (201) $\displaystyle+\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left(\rho_{t}q_{ \pi,t}(S_{t},A_{t})\mid S_{t}\right)$ (Lemma 6 with $b=0$ ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2} \left(\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*,b ^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}( S_{t},A_{t})\right)\mid S_{t}\right]$ (202) $\displaystyle+\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left(\rho_{t}q_{ \pi,t}(S_{t},A_{t})\mid S_{t}\right)$ (203) $\displaystyle+\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2} \left(\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*, \text{PDIS}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)-\mathbb{V}\left(G^{\text {PDIS}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t} ,A_{t}\right]\right)\mid S_{t}\right]$ (204) $\displaystyle\geq$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left[\rho_{t}^{2}\left( \mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*,b^{*}}_ {t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t}, A_{t})\right)\mid S_{t}\right]$ (205) $\displaystyle+\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left(\rho_{t}q_{ \pi,t}(S_{t},A_{t})\mid S_{t}\right)$ (206) $\displaystyle+\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2} \left(\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*, \text{PDIS}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)-\mathbb{V}\left(G^{\text {PDIS}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t} ,A_{t}\right]\right)\mid S_{t}\right]$ ( $\forall\mu^{*,\text{PDIS}}_{t}\in\Lambda_{t}$ , $\mu^{*,b^{*}}_{t}$ achieves the minimum value of the first term in $\Lambda_{t}$ ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\mu^{*,b^{*}}_{t}}\left[\rho_{t}^{2}u^{b^{*} }_{t}(S_{t},A_{t})\mid S_{t}\right]$ (207) $\displaystyle+\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left(\rho_{t}q_{ \pi,t}(S_{t},A_{t})\mid S_{t}\right)$ (208) $\displaystyle+\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2} \left(\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*, \text{PDIS}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)-\mathbb{V}\left(G^{\text {PDIS}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t} ,A_{t}\right]\right)\mid S_{t}\right]$ (By ( 163 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{t}(S_{t},A_{t })}\mid S_{t}\right]^{2}$ (209) $\displaystyle+\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left(\rho_{t}q_{ \pi,t}(S_{t},A_{t})\mid S_{t}\right)$ (210) $\displaystyle+\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2} \left(\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*, \text{PDIS}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)-\mathbb{V}\left(G^{\text {PDIS}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t} ,A_{t}\right]\right)\mid S_{t}\right].$ (By ( 113 )) $$

Thus, for $t=T-1$,

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*,\text{PDIS}}_{t:T-1} }_{t:T-1})\mid S_{t}=s\right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t :T-1}}_{t:T-1})\mid S_{t}=s\right)$ (211) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left(\rho_{t}q_{\pi ,t}(S_{t},A_{t})\mid S_{t}\right).$ (By ( 165 ) and ( 198 )) $$

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

$$ $\displaystyle\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*,\text{PDIS}}_{t:T-1} }_{t:T-1})\mid S_{t}=s\right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t :T-1}}_{t:T-1})\mid S_{t}=s\right)$ (212) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left(\rho_{t}q_{\pi ,t}(S_{t},A_{t})\mid S_{t}\right)$ (213) $\displaystyle+\mathbb{E}_{A_{t}\sim\mu^{*,\text{PDIS}}_{t}}\left[\rho_{t}^{2} \left(\mathbb{E}_{S_{t+1}}\left[\mathbb{V}\left(G^{\text{PDIS}}(\tau^{\mu^{*, \text{PDIS}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)-\mathbb{V}\left(G^{\text {PDIS}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)\mid S_{t} ,A_{t}\right]\right)\mid S_{t}\right].$ (By ( 166 )and ( 199 )) $$

The proof of $\forall t,s,\delta^{\text{ODI, ours}}_{t}(s)\geq 0$ is similar to (197) and is omitted.

∎

###### Proof.

### A.7 Proof of Theorem 6

###### Proof.

We begin the proof by manipulating the variance of $G^{b^{*}}(\tau^{\pi_{t:T-1}}_{t:T-1})$.
$\forall s$, for $t=T-1$,

$$ $\displaystyle\mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (214) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[[q_{\pi,t}(S_{t},A_{t})-b^{*}_ {t}(S_{t},A_{t})]^{2}\mid S_{t}\right]-[v_{\pi,t}(S_{t})-\bar{b^{*}}_{t}(S_{t} )]^{2}$ (Lemma 5 and on-policy) $\displaystyle=$ $\displaystyle 0$ (Definition of $b^{*}$ ( 31 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[u^{b^{*}}_{t}(S_{t},A_{t})\mid S _{t}\right].$ (By ( 163 )) $$

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

$$ $\displaystyle\mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S_{t}=s\right)$ (215) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right) \mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})+[q_{\pi,t}(S_{t},A_{t})-b_{t}(S_{ t},A_{t})]^{2}\mid S_{t}\right]$ (216) $\displaystyle-[v_{\pi,t}(S_{t})-\bar{b}_{t}(S_{t})]^{2}$ (By Lemma 5 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right) \mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\mid S_{t}\right]$ (217) $\displaystyle+\mathbb{V}_{A_{t}\sim\pi_{t}}\left([q_{\pi,t}(S_{t},A_{t})-b^{*} _{t}(S_{t},A_{t})]\mid S_{t}\right)$ (Lemma 6 ) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right) \mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\mid S_{t}\right]$ (By ( 31 )) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }\right)\mid S_{t},A_{t}\right]+\nu_{t}(S_{t},A_{t})\mid S_{t}\right]$ (218) $\displaystyle+\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)- \mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }\right)\mid S_{t},A_{t}\right]\mid S_{t}\right]$ (219) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[u^{b^{*}}_{t}(S_{t},A_{t})\mid S _{t}\right]$ (220) $\displaystyle+\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)- \mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }\right)\mid S_{t},A_{t}\right]\mid S_{t}\right].$ (By ( 163 )) $$

Thus, for $t=T-1$, their difference is

$$ $\displaystyle\mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S_{t}=s \right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t:T-1}}_{t:T-1})\mid S_ {t}=s\right)$ (221) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[u^{b^{*}}_{t}(S_{t},A_{t})\mid S _{t}\right]-\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{t}(S_{t},A_{t} )}\mid S_{t}\right]^{2}$ (By ( 165 ) and ( 214 )) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\pi_{t}}\quantity(\sqrt{u^{b^{*}}_{t}(S_{t}, A_{t})}\mid S_{t}).$ (222) $$

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

$$ $\displaystyle\mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t:T-1}}_{t:T-1})\mid S_{t}=s \right)-\mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t:T-1}}_{t:T-1})\mid S_ {t}=s\right)$ (223) $\displaystyle=$ $\displaystyle\mathbb{E}_{A_{t}\sim\pi_{t}}\left[u^{b^{*}}_{t}(S_{t},A_{t})\mid S _{t}\right]-\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\sqrt{u^{b^{*}}_{t}(S_{t},A_{t} )}\mid S_{t}\right]^{2}$ (224) $\displaystyle+\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)- \mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }\right)\mid S_{t},A_{t}\right]\mid S_{t}\right]$ (By ( 166 ) and ( 215 )) $\displaystyle=$ $\displaystyle\mathbb{V}_{A_{t}\sim\pi_{t}}\quantity(\sqrt{u^{b^{*}}_{t}(S_{t}, A_{t})}\mid S_{t})$ (225) $\displaystyle+\mathbb{E}_{A_{t}\sim\pi_{t}}\left[\mathbb{E}_{S_{t+1}}\left[ \mathbb{V}\left(G^{b^{*}}(\tau^{\pi_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}\right)- \mathbb{V}\left(G^{b^{*}}(\tau^{\mu^{*,b^{*}}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1 }\right)\mid S_{t},A_{t}\right]\mid S_{t}\right].$ (226) $$

The proof of $\forall t,s,\delta^{\text{DR, ours}}_{t}(s)\geq 0$ is similar to (197) and is omitted.

∎

###### Proof.

### A.8 Proof of Lemma 3

See 3

###### Proof.

When $t=T-1$, $\forall s,a$,

$$ $\displaystyle u_{\pi,t}(s,a)$ (227) $\displaystyle=$ $\displaystyle\quantity(q_{\pi,t}(s,a)-b^{*}_{t}(s,a))^{2}+\nu_{\pi,t}(s,a)$ (By ( 163 )) $\displaystyle=$ $\displaystyle 0.$ (By ( 31 )) $$

When $t\in[T-2]$, $\forall s,a$,

$$ $\displaystyle u_{\pi,t}(s,a)$ (228) $\displaystyle=$ $\displaystyle\nu_{\pi,t}(s,a)+\sum_{s^{\prime}}p(s^{\prime}|s,a)\mathbb{V} \left(G^{b}(\tau^{\mu^{*}_{t+1:T-1}}_{t+1:T-1})\mid S_{t+1}=s^{\prime}\right)$ (By ( 163 )) $\displaystyle=$ $\displaystyle\nu_{\pi,t}(s,a)+\sum_{s^{\prime}}p(s^{\prime}|s,a)\left[\mathbb{ E}_{A_{t+1}\sim\mu^{*}_{t+1}}\left[\rho_{t+1}^{2}u_{\pi,t+1}(S_{t+1},A_{t+1}) \mid S_{t+1}=s^{\prime}\right]\right.$ (229) $\displaystyle\left.-[v_{\pi,t+1}(s^{\prime})-\bar{b}^{*}_{t+1}(s^{\prime})]^{2 }\right]$ (Lemma 5 ) $\displaystyle=$ $\displaystyle\nu_{\pi,t}(s,a)+\sum_{s^{\prime}}p(s^{\prime}|s,a)\mathbb{E}_{A_ {t+1}\sim\mu^{*}_{t+1}}\left[\rho_{t+1}^{2}u_{\pi,t+1}(S_{t+1},A_{t+1})\mid S_ {t+1}=s^{\prime}\right]$ (By ( 31 )) $\displaystyle=$ $\displaystyle\nu_{\pi,t}(s,a)+\sum_{s^{\prime},a^{\prime}}\rho_{t+1}p(s^{ \prime}|s,a)\pi_{t+1}(a^{\prime}|s^{\prime})u_{\pi,t+1}(s^{\prime},a^{\prime}).$ (230) $$

∎

###### Proof.

## Appendix B Experiment Details

We utilize the behavior policy-agnostic offline learning setting (Nachum et al.,, ), in which the offline data consists of $\quantity{(t_{i},s_{i},a_{i},r_{i},s_{i}^{\prime})}_{i=1}^{m}$,
with $m$ previously logged data tuples. Those tuples can be generated by one or multiple behavior policies, regardless of whether these policies are known or unknown, and they are not required to form a complete trajectory. In the $i$-th data tuple, $t_{i}$ represents the time step, $s_{i}$ is the state at time step $t_{i}$, $a_{i}$ is the action executed, $r_{i}$ is the sampled reward, and $s_{i}^{\prime}$ is the successor state.

In this paper, we first learn the action-value function $q_{\pi,t}$ from offline data using Fitted Q-Evaluation algorithms (FQE, Le et al., ()), but our framework is ready to integrate state-of-the-art offline policy evaluation techniques.
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.

Then, by the following derivation

$$ $\displaystyle\nu_{\pi,t}(s,a)$ (231) $\displaystyle=$ $\displaystyle\mathbb{V}_{S_{t+1}}\left(v_{\pi,t+1}(S_{t+1})\mid S_{t}=s,A_{t}= a\right)$ (By ( 21 )) $\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}$ (232) $\displaystyle=$ $\displaystyle\mathbb{E}_{S_{t+1}}\left[v_{\pi,t+1}(S_{t+1})^{2}\mid S_{t}=s,A_ {t}=a\right]-(q_{\pi,t}(s,a)-r(s,a))^{2},$ (233) $$

the first term is an expectation of $S_{t+1}$. Because we have $(t_{i},s_{i},a_{i},r_{i},s_{i}^{\prime})$ data tuples, we construct $\nu$ using $s_{i}^{\prime}$ in $(t_{i},s_{i},a_{i},r_{i},s_{i}^{\prime})$ data tuples as the sample of the first term
and compute the rest quantity using the learned action-value function $q_{\pi,t}$ and reward data $r_{i}$.
Therefore, we construct $\mathcal{D}_{\nu}\doteq\quantity{(t_{i},s_{i},a_{i},\nu_{i},s^{\prime}_{i})}_{
i=1}^{m}$.
Finally, by passing data tuples in $\mathcal{D}_{\nu}$ from $t=T-1$ to 0 0, we fit the function $u_{\pi,t}$ using FQE in a dynamic programming way with respect to the recursive form of $u_{\pi,t}$ derived in Lemma 3.
For each time step, we take a copy of the neural network as an approximation to function $u_{\pi,t}$ at time step $t$. After learned function $u_{\pi,t}$ and $q_{\pi,t}$, we return the learned behavior policy
$\mu^{*}_{t}(a|s)\propto\pi_{t}(a|s)\sqrt{u_{\pi,t}(s,a)}$ and the learned baseline function $b^{*}_{t}(s,a)=q_{\pi,t}(s,a)$.
The pseudocode of this procedure is presented in Algorithm 1.

Figure: Figure 3: 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/5897894/figure/mujoco/ant.jpg

### B.1 GridWorld

For a Gridworld with size $n$, its width, height,
and time horizon $T$ are all set to $n$.
The number of states in this Gridworld environment scales cubically with $n$, offering a suitable tool to test algorithm scalability. We choose Gridworld with $n^{3}=1,000$ and $n^{3}=27,000$, which are the largest Gridworld environment tested among related works (Jiang and Li,, ; Hanna et al.,, ; Liu and Zhang,, ).
There are four possible actions: up, down, left, and right. After taking an action, the agent has a $0.9$ probability of moving accordingly and a $0.1$ probability of moving uniformly at random.
If the agent runs into a boundary,
the agent stays in its current location.
The reward function $r(s,a)$ is randomly generated.
We consider $30$ randomly generated target policies.
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.
To learn functions $q_{\pi,t}$ and $u_{\pi,t}$, we split the offline data into a training set and a test set. We
tune all hyperparameters offline
based on Fitted Q-learning loss on the test set. 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 (Jiang and Li,, ; Liu and Zhang,, ).
Each policy has 30 independent runs, resulting in $30\cdot 30=900$ total runs.
Therefore, each curve in Figure 1 is averaged from 900 different runs over a wide range of policies indicating strong statistical significance.

### B.2 MuJoCo

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.
Environments in Figure 3 from the left to the right are Ant, Hopper, InvertedDoublePendulum, InvertedPendulum, and Walker.
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., ().
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}$ and $u_{\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, each curve in Figure 2 and each number in Table 2 are averaged from 900 different runs over a wide range of policies indicating strong statistical significance.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: My main question is what I have listed in the weaknesses part: what is the pipeline of the proposed method? If the pipeline is same as what I write in the weaknesses part, then what is meaning to reduce the variance of the estimator.
soundness: 3
strengths: 1. It is an interesting problem to study that to evaluate a given policy, what is the best behavior policy to collect samples.
summary: This paper studies the policy evaluation problem. Given a policy $\pi$ to evaluate, the authors adopted the classic importance-weighting estimator with baseline function. By optimizing the variance of this estimator, they derived an optimal behavior policy and baseline function. They show that the variance of the importance weighting estimator equipped with their optimal behavior policy and baseline function is smaller than three existing estimators including the on-policy estimator and the doubly robust estimator. Additionally, they implemented experiments on practical tasks to show the effectiveness of their doubly optimal evaluation method.
weaknesses: The pipeline of their proposed method is that: First, calculating an optimal behavior policy and baseline function by solving an optimization problem; Second, using the derived behavior policy to collect samples and use importance-weight estimator on these samples. 
1. However, in the first stage, in order to calculate the optimal behavior policy and baseline function, lots of samples are needed and I think the samples needed in this stage are much more than the second stage (since the definition of $u(s,a)$ needs lots of information e.g. the transition function). In this case, it is meaningless to reduce the variance of the estimator.
2. And the optimal baseline function is found to be the q-value function of the target policy. If we already figure out an optimal baseline function, i.e. the q-value of the target policy, then it is done. No need to do importance-weighting any more. Therefore, again it is meaningless to reduce the variance of the estimator.

The above is the biggest weakness. It is not clear what is achieved by their method theoretically or practically. 

Besides, there are also other problems which make their theory fragile.

3. The set $\Lambda$ of feasible behavior policies seems weird to me. It contains behavior policy $\mu$ such that $\mu(a|s)=0$ while $\pi(a|s)>0$ ($q(s,a)=0$). In this case, the importance weighting estimator goes to infinity, let alone control the variance. One solution is to assume non-negative rewards, since with non-negative rewards $q(s,a)=0$ indicates zero rewards by playing $a$ at state $s$ which can make the importance weighting estimator be zero. However, in the paper, they don't discuss it and make any assumptions.

---

confidence: 3
contribution: 3
initial_rating: 3
presentation: 3
questions: 1. Please address my concerns in the weakness.

2. According to algorithm 1, will the offline dataset affect the performance? In the experiments these offline datasets are collected by random policies. I wonder what if it is collected by an expert policy or other more sophisticated behavior policies, like in most RL settings? This is important to demonstrate the applicability of the proposed method on datasets with different expertise levels.
soundness: 2
strengths: + The paper is quite well-written and easy to follow. The motivation and the key idea of the method are clearly presented. The differences between the proposed method and prior work have been clearly discussed in the related work section.
+ The authors provide a detailed and comprehensive theoretical proof to support the proposed method, though there seem to be some errors in the proof of theorem 1.
+ The experiments show performance improvement over existing methods.
summary: This paper aims to enhance the sample efficiency of online reinforcement learning algorithms by reducing the variance of estimation of the total rewards. To achieve this, the authors introduce a bi-level optimization method with both optimal data-collecting policy and data-processing baseline. The paper provides detailed proof showing a guaranteed lower variance of the proposed method than those from the state-of-the-art methods. The empirical results on MiniGrid and tasks from the Mujoco environment conducted in this paper further demonstrate the effectiveness of the proposed method, outperforming existing methods in these tasks.
weaknesses: - A potential error in the proof:

In equation (23), the second equal sign does not make sense. By equation (12) that 

${\mu}^{*}_t (a|s) \propto \pi _ t (a|s) \sqrt{u _ { \pi, t} (s,a)}$.

We should have 

$\sum_{a} \frac{\pi _ t(a|S_t)^2}{\mu^{*}_t (a|S_t)} u _ {\pi, t}(S_t,a)$

$= \sum_{a} \pi _ t (a|S_t)\sqrt{u _ {\pi, t} (S_t, a)}$

However, in the paper the author seems to give the wrong result as 

$\sum_{a} \frac{\pi _ t(a|S_t)^2}{\mu^{*}_t (a|S_t)} u _ {\pi, t}(S_t,a)$

$=\sum_{a}\pi_t(a|S_t)\sqrt{u _ {\pi, t}(S_t, a)} \sum_{b}\pi_t(S_t, b)\sqrt{u _ {\pi, t}(S_t, b)}$.

Unless I'm missing something, this seems to be an error that may invalidate the optimality of the proposed behavior policy, as the results is used in subsequent analysis and proofs. The proof also contains typos and minor issues, such as the following. All of these cast doubt on the soundness of the analysis.
	
After the second equal sign in equation (18), there's an extra ")" after $\bar{b_t}(S_t)$; 

At the start of equation (20), $\nu_t(S_t, A_t) =$ should be removed; 

In page 17, the $\mu^{*}_t$ after the third equal sign should be $\mu_t$.

- Figure 3 looks exactly the same as the Figure 3 in the following paper [1], however without citing the source. This is a major concern.

[1]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.

- While the experiments show good improvement of baseline algorithms, I would suggest the experiments be expanded to more environments such as Atari (RL with visual input) and more tasks in MuJoCo, where the sampling are generally less efficient.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. In your formulation your assume that Q_{\pi} is learned from the offline data, one would expect that a basic estimator of V(S0) in this case would be \sum_a \pi(a|S0) Q(a, S0) you should explain why it is not an appropriate estimator and add it to some of your empirical evaluations.

2. Based on your arguments in Section 4 (Lines 190-230) you require unbiasedness in every state not just s0, how does it reconcile with your argument that you enlarge the state space?

3. Figure 1 shows similar patterns for sample counts of 1000 and 27000. Can the authors clarify why similar accuracy requires the same number of samples for differently scaled problems?

4. Including a background on DR and ODI in the background section could enhance reader comprehension, as these are central to the analytical comparisons made.

5. Details on estimating \ni in practical settings should be incorporated into the main text. Without this information, readers may struggle to understand the algorithm’s practical execution.
soundness: 3
strengths: The related work section is comprehensive, contextualizing the paper within current literature and algorithms. The paper is generally clear and accessible, a crucial feature given the depth of theoretical content. The theoretical analysis rigorously establishes DOPT's optimality over on-policy, DR, and ODI baselines.
summary: This paper studies the problem of efficient policy evaluation: designing a behavioral policy to collect data in order to estimate a target policy s.t. It requires as little as possible policy rollouts in order to evaluate the target policy performance for a given confidence level. 

The authors cast this problem as a double step minimization problem of the variance of the importance sampling corrected reward traces (termed the G^PDIS), where the components to minimize are the behavioral policy \mu and a baseline function b that can reduce the overall variance of G^PDIS, while maintaining unbiasedness s.t. E[G^PDIS] converges to the target policy performance.

The authors develop an algorithm, named DOPT, inspired by two established methods for policy evaluation: (1) DR which uses the optimal baseline function and (2) ODI which do not take into account a baseline function, but solves for the optimal behavioral policy that minimizes the variance of G^PDIS (again without inserting a baseline function).

The authors show theoretically that if one adds both the optimal baseline function and solves for the optimal policy given the baseline we obtain a stronger estimator that minimizes the variance terms with respect to both DR and ODI (which are both superior over the on-policy case, where one uses rollouts from the target policy to approximate its performance).

The paper then continues with the practical implementation of how to estimate the theoretically justified behavioral policy and it concludes with an experiment section where it is shown that DOPT outperforms both ON (on-policy), DR and ODI in terms of evaluation steps with respect to the relative error (the difference between the estimated performance to the real performance scaled by this difference for on-policy evaluation after one episode). The experiments are executed in a synthetic grid-world and in the Mujoco physics simulator.
weaknesses: While optimal theoretically, in practice DOPT requires off-policy estimation of (1) the Q-function q(s,a), (2) the next state value variance \ni(s, a) and (3) the amplification factor u(s,a) (how much should the probability of an action be amplified for a given s,a pair). Specifically, u is learned based on a Bellman operator with \ni as a reward and with an important sampling correction term (Lemma 3). Both \ni and u are not required by previous schemes: DR and ODI and both can introduce errors. Specifically, u which uses Bellman operator that can potentially add bootstrapping errors and importance sampling term with high variance. Although empirical results support DOPT’s advantage, further analysis of these considerations is warranted for a complete evaluation. The authors should do a better job in analyzing and presenting these considerations.

Meta-review: In this paper, the authors propose a method to find a behavioral policy that can be used to estimate the value of a given target policy for a confidence level with small amount of data generation (policy rollouts). By optimizing the variance of the classic importance-weighting estimator with a baseline, they derive their behavior policy and baseline. They show that the variance of the importance weighting estimator with these behavior policy and baseline is smaller than three existing estimators, including the on-policy and doubly robust estimators. Finally, they empirically evaluate their proposed method.

Here are positives and negatives of the paper from the reviews: 
(+) The paper is well-written. The motivation and key ideas are clearly presented. The related work is properly listed. The proposed results have been properly put in context with respect to the existing literature. 
(+) The proposed method is well-supported by detailed and comprehensive theoretical results.
(+) The proposed method is empirically evaluated against existing methods.
(-) The extra complexities of the proposed method (compared to the existing methods) are not properly highlighted.

Decision: Accept (Poster)