Doubly Optimal Policy Evaluation for Reinforcement Learning
Authors: Shuze Liu
Claire Chen
Shangtong Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: Reinforcement Learning
Primary area: reinforcement learning
TL;DR: Our method substantially improves the efficiency of policy evaluation in reinforcement learning.

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.

Published as a conference paper at ICLR 2025
DOUBLY OPTIMAL POLICY EVALUATION FOR REINFORCEMENT LEARNING
Shuze Daniel Liu Department of Computer Science University of Virginia shuzeliue burzellluvue weg.iiiiiiiniiinnnn rewiniiinn..mmmm edu
Claire Chen
School of Arts and Science
University of Virginia
cla rechen@ema 1. rwwiniiina.... edu
Shangtong Zhang
Department of Computer Science University of Virginia
shangtoong@vi edu
ABSTRACT
Policy evaluation estimates the performance of a policy by (1) collecting data from the environment and (2) processing raw data into 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, design an optimal combination of data-collecting policy and data sata--pocessing baseline. Theoretically, prove 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.
INTRODUCTION
Reinforcement learning (RL, Sutton and Barto (2018)) has achieved remarkable success in various sequential decision-make problems. For example, RL algorithms have reduced energy consumption for Google data centers' cooling by 40% (Chervonyi al., 2022), predicted protein structures with competitive accuracy (Jumper et al., 2021), and discovered faster matrix multiplication algorithms (Fawzi et al., 2022). When applying RL algorithms, policy evaluation plays a critical role to allow practitioners to estimate the performance of 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 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., 2017: Liu and Zhang, 2024: Liu al., 2024b; Chen al., 2024), 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, 2019; Zhang, 2023). Even with a well-developed simulator, complex tasks like data center cooling take 10 seconds per step (Chervonyi al., 2022), 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 offfine data distribution and the data distribution induced by the target policy, leading to uncontrolled and ineliminable bias (Jiang and Li, 2016; Farahmand and Szepesvári, 201 Marivate, 2015). As a result, a policy with high performance offline data may actually perform very poorly in real deployment (Levine, 2018). Consequently, both online and offline RL practitioners still heavily rely on online policy evaluation methods( Kalashnikov al., 2018; Vinyals et al., 2019).

---

Published as a conference paper at ICLR 2025
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 doubly optimal estimator by proposing optimal data-collecting policy and an optimal proc-ssons 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, 2016; Liu and Zhang, 2024). 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.
RELATED WORK
Reducing the variance for policy evaluation in reinforcement learning (RI.) has been widely studied. One rising approach is variance reduction by designing proper data-collecting policy, also known as the behavior policy. Noticing that the target policy itself not the best behavior policy, Hanna et al. (2017) formulate the task of finding a variance-reduction behavior policy as optimization problem. They use stochastic gradient descent to update 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, 1992). By contrust, our method directly learns the globally optimal behavior policy without doing policy search. Morcover, their method requires highly sensitive hyperparameter tuning to learn the behavior policy effectively. Specifically, the learning rate can vary by up to 10s times across different environments, reported in the experiments of Hanna et al. (2017). This extreme sensitivity requires online tuning, consuming massive online data. By contrast, we propose an efficient algorithu to learn our optimal behavior policy with purely offline data. Furthermore, Hanna et al. (2017) constrain the online data to be complete trajectories. By contrast, our method copes well with incomplete offline data tuples, which is widely applicable.
Zhong et al. (2022) also aim to reduce the variance policy evaluation through designing 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. (2022) lack theoretical guarantees of unbiasedness nor consistency. By contrast, we theoretically prove that our estimate is inherently unbiased. Another approach by Mukherjee et al. (2022) investigates behavior policies aimed at reducing variance in per-decision importance sampling estimators. However, their results are limited tree-structured MDPs, a significant limitation since most problems do not adhere tree structure. By contrast, our method works on general MDPs without any restriction on their inherent structures. Moreover, Mukherjee et al. (2022) explicitly require the knowledge of transition probability and, therefore, suffer from all canonical challenges in model learning (Sutton, 1990; Sutton et al., 2008; Deisenroth and Rasmussen, 2011: Chua al., 2018). By contrast, our approach model-free and can use off-the- shelf offfine policy evaluation methods (e.g. Fitted Q- D-Evlluation, Le et al. (2019)). The current state-of-te of-te-of-theaare art method in behavior policy design proposed by Liu and Zhang (2024), where they find an optimal and offline-learnalle behavior policy with the per-decision importance sampling estimator. However, all these approaches (Hanna et al., 2017; Mukherjee et al., 2022; Zhong et al., 2022; Liu and Zhang, 2024) only consider optimality in the data-collecting process, while ignoring the potential improvement in data- cata-processing steps. By contrast, we model the variance reduction as a bi-level optimization problem, where the behavior policy is optimized with 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 eval- uation is using the baseline functions. Jiang and Li (2016) propose doubly robust estimator by
2

---

Published as a conference paper at ICLR 2025
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 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 (2016) both theoretically and empirically. Thomas and Brunskill (2016) extend the method of Jiang and Li (2016) 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.
BACKGROUND
In this paper, study finite horizon Markov Decision Process (MDP, Puterman (2014)). In this MDP, there is a finite action space A, a finite action space A, a transition probability function p S S x A + [0, 11. a reward function r S x A - IR, initial state distribution po : 8 - [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, 2014). We define shorthand [n|] = 10.1,...,,1 n2 for any integer n.
The MDP process begins at time step O, where an initial state So is sampled from Po. At each time step t - 1], an action A, is sampled based on TT(- St). Here, T. : A S - [o, 1] denotes the policy at time step t. Then, a finite reward R = r(,,, is given by the environment and a suc- cessor state S1+1 is obtained based on p(- SS,,, At). We use abbreviations may = {TT, T T4+1, m.+1,...., m and π - To:r-1- At each time step t, the return is defined as G. = -/=41 R₁ Then, we de- fine the state-value and action-value functions as (8) = E. [G+ St = s] and g=,(s,0) = E,z [G, S. = 8, A₁ = a). We adopt the total rewards performance metric (Puterman, 2014) for the measurement of the performance of policy r, which is defined as [(xr)== = Σ. (o())(x,0()) this work, we use Monte Carlo methods, as introduced by Kakutani (1945), for estimating the total rewards (TT) The most straightforward Monte Carlo method is to draw samples of ((T) through the online execution of the policy я. The empirical average of the sampled returns converges to ((x) as the number of samples increases. Since this method estimates a policy by executing itself, it is called on-policy learning (Sutton 1988).
In
Moving forward, we focus off-policy evaluation, where the goal is to estimate the total rewards ((x of an interested policy ग, which is called the target policy. Data for off- policy evaluation are collected by executing a different policy μa, called the behavior policy. In off-policy evaluation, we generate each trajectory (So, Ao, R1, S1, AI, Ro..... ST Ar R by behavior policy μ with A, ~ 1 (-)S)). We use a shorthand #uT-1 - { A,, R ................................ ST-1, Ar R for a trajectory TtT-1
generated by the behavior policy from time step t to T - -1 inclusively. We use the importance sampling ratio to reweight the rewards obtained by the behavior policy μr, in order to give an estimate
(e(AA1S.)) Then, the product of (Tr). We define the importance sampling ratio at time step as (A.
of importance sampling ratios from time t to t' 2 is defined Pt:er = II mu (Aa( In off-policy learning, there are several ways to use the importance sampling ratios (Geweke, 1988: Hesterberg, 1995; Koller and Friedman, 2009; Thomas, 2015). In this paper, we investigate the per-decision importance sampling estimator (PDIS, Precup et al. (2000) and leave the investigation of others for future work. We define the PDIS Monte Carlo estimator as GPDIS (T = EiEt Ret11 which can also be expressed recursively as
(Ax
[ Pt (Re+1 + PDIS ((TT)))) p. Re+1
E [ - 2], t= T - 1.
PDIS (
Under the classic policy coverage assumption (Precup al., 2000; Maei, 2011; Sutton al., 2016; Zhang, 2022; Liu et al., 2024a) Vt, s, (als) = 0 + Te (als) = O. this off-policy estimator GPDIS (TOTTT1) provides an unbiased estimation for J(m), i.e., E E PDIS (- )] = J(T).
In off-policy evaluation, notorious curse is that the importance sampling ratios be extremely large. resulting in infinite variance (Sutton and Barto, 2018). Even with the PDIS method, this fundamental issue still remains if the behavior policy significantly differs from the target policy,
3

---

Published as a conference paper at ICLR 2025
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 al., 2020). One way control for the violation in important sampling ratios is to subtract a baseline from samples (Williams, 1992; Greensmith et al., 2004; Jiang and Li, 2016; Thomas and Brunskill, 2017). Using denote an arbitrary baseline function, the PDIS estimator with baseline is defined as
Pi (Re-1 + G ("( by (Se. Ad)) (5t) Pe (Re+1 (St, A,) + (S.))
EE [T -22. 2],
G (TTT-
== T
where
(s,)) = EA (br Ac)].
(2)
(S)))) and the choice The variance of (1) highly depends on the importance sampling ratio Pr (r S.) of baseline function b.
4 VARIANCE REDUCTION IN REINFORCEMENT LEARNING
We seek to reduce the variance (TG (T by designing an optimal behavior policy and an optimal baseline function at the same time. We solve the bi-level optimization problem
min min 1
V(G (T
s.t. E (of==)) = J(.).
where the optimal behavior policy je 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, 2016; Liu and Zhang, 2024). 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, 2016; Liu and Zhang, 2024) in a broad set of environments.
To ensure that the off-polic estimator Go (orTT11) is unbiased, the classic reinforcement learning wisdom (Precup et al., 2000; Maci, 201 I: Sutton et al., 2016; Zhang, 2022) requires that the behavior policy f covers the target policy и. This means that they constraint f be set
A [ I Vt, s, a, (als)) # = Me s) + 0}
[1 Vl, 8, a, (4((as)) = 0 = my (a 0}.
which contains all policies that satisfy the policy coverage constraint in off-policy learning (Sutton
and Barto 2018). By specifying the policy coverage constraint, the optimization problem (3) is reformulated as
min min
V(G
(4)
S.L. MEAT
In this paper, compared with the classic reinforcement learning literature, we enlarge the search space of μ from this set A to set A. To achieve superior and reliable optimization solution, we require A have two properties.
1. (Broadness) A must be broad enough such that it includes all policies satisfying the classic policy coverage constraint (Precup al., 2000; Sutton and Barto, 2018). Formally,
A- C A.
(5)
2. (Unbiasedness) Every behavior policy in A must be well-behaved such that the data collected by it can be used by the off- off-policy estimator to achieve unbiased estimation for all state and time step t. Formally, Vμ E A,
VI, Vs,
E [ (TET-11) 1) St s] (s)
4

---

Published as a conference paper at ICLR 2025
The space A that satisfies those two properties will be defined shortly. We now reformulate bi-level optimization problem as
min min ((G
S.t. M.
Compared with the classic approach (4), our bi-level optimization problem (7) searches for j in broader space A such that A C A. 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 (7), we first give closed-form solution of the inner optimization problem
min ((G"(ToT-T))
S.L. μEA
for any baseline function Notably, this baseline function does not need to any kind of oracle. We design the optimal solution of (8) for this baseline function b without requiring any property on Now, we decompose the variance of our off-policy estimator G (ToTT1)") By the law of total variance, vb, Vu E A,
V (C
=1ss [V (G ( [6]] Vs (E [G (~ So])
(9) The second term in (9) is constant given a target policy и and is unrelated to the choice of In the first term, the expectation taken over So that determined by the initial probability distribution po- Consequently, given any baseline function b, to solve the problem (8), it is sufficient to solve
-Es V (-02-11 So)] + Vs, (V,,o(So)).
(by (6))
min V(G (T (S
(10)
s.t. μEA
for all s and t. If we can find one optimal behavior policy Je that simultaneously solves the optimization problem (10) on all states and time steps, μ² is also the optimal solution for the optimization problem (8). Denote the variance of the state value function for the next state given the current state-action pair as (,, Recall the notation [ 2) is a shorthand for the set {0, 1 T 2). We have Ux,0(8, a) = 0 for /. T - 1, and 14 E [T 2]. (s, = Vssr (S+4)) S, A, a).
(11)
Given any baseline function b, we construct behavior policy μ² as mā(als) x ne(als) u a)
(12)
where Un (s, = (q,, a) be(s. a)) fort T 1, and Vt E - (s, = (gm.e(s, - b)(s,)))² + as) + p(s'ls (c S:41 s¹)
(13)
Notably, un,t and i are defined backwards and alternatively, i.e., they are defined in the order of Ux 11 -7-1: Mr.T -2 for ... Ux H We now break down each term in (s)
1. (gn.(s, a) (s a))² is the squared difference between the state-value function aa, and the baseline function b. This term always non-negative because of the square operation. Its magnitude is mainly controlled by the baseline function b.
2. Vn, (s, a) defined in (11) is the variance 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. Σ. p(s"|s, a) (G (""i))))))) | S41 = is the expected future variance given the current state and action This term is always non-negative by the definition of variance. Its magnitude is jointly controlled by the choice of behavior policy μ*, the baseline function
b, and the transition function p.
5

---

Published as a conference paper at ICLR 2025
(s, a) is non-negative because it is the sum of three non-negative terms. Therefore, v // a) is
always well-defined. In (12), p (als) or Te(als) V (s, means μn (a|s) mx(ale)y un. E. (
If Va, me (als) / a a) = 0, the denominator is zero. In this case, we use the convention to
interpret yu (als) s) as uniform distribution, i.e.. Va, μt (a|s) 1/ We adopt this convention for
x in the rest of the paper to simplify the presentation. Now, we define the enlarged space A as
A {p Vt, 8, a, (e((s)) 0 = re(als))ux,(( a) 0}-
(14)
We prove that this policy space A defined above satisfies the broadness (5) and the unbiascdness (6) by the following lemmas. Lemma (Broadness). vb, A A.
Its proof is in Appendix A.I. Lemma 2 (Unbiasedness). Ab, Vp E A. Vt, E (G"(TTTTT) S = = = (
Its proof is in Appendix A.2. After confirming the broadness and unbiasedness of the space A, we now prove that the behavior policy μ is the optimal solution for the inner optimization problem.
Theorem 1. For baseline function b, the behavior policy μº defined in (12) is an optimal solution the optimization problems Vt, s,
min 1
V
s.t. μEA.
Its proof is in Appendix A.3. Theorem I proves that vb, the behavior policy μ (12) is the closed-form optimal solution for all & and s. With Theorem for any and s, we reduce the bi-level optimization problem
min min V (G St =
P
s.t. E
to single-level unconstrained optimization problem
min v (T"TT))))
In this unconstrained optimization problem, we design function b that influences both the data processing estimator G (1) and the optimal behavior policy μr" (12). Notably, the optimal behavior policy y depends on the baseline b because is tailored to baseline function b in Theorem 1. Unless otherwise noted, we omit explicitly writing this dependency show that although both Go and μ² depend on b, through the mathematical proof in the appendix, the optimal bascline function 6" has concise format. Define Vt, S, a.
the notation of J for simplicity. We
by (s, a) - 9r,1(s,a) a).
(15)
Theorem 2. b* is the optimal solution to the optimization problems Vt, (Gor)))--1)) V (TTTTTT))) | S(=s)
min b
(16)
Its proof is in Appendix A.4. By solving each level of the optimization problem, we show (n², b²) is the optimal solution for the bi-level optimization problem by utilizing Theorem I and Theorem 2.
Theorem 3. (p") (p",b") is the optimal solution the bi-level optimization problems Vt, s.
min min P
(ET St V (T
S.t. μEA.
Proof. Vb, Vu A, we have Vt. Vs
v (G S: = s)
>V (c"()()T)))
S: =
(Theorem 1)
2V (6 (arr-)))
S: =
(Theorem 2)
Thus, (p"", (0) achieves the minimum value of V 1) |S, =s) for all and

---

Published as a conference paper at ICLR 2025
5 VARIANCE COMPARISON
Theorem shows (fa","") bn) is the optimal behavior policy and baseline function. This means (1² .b) superior to any other choice of (H, In this section, we further quantity 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- the following baselines: (1) the on-policy Monte Carlo estimator, (2) the offline data informed estimator (Liu and Zhang. 2024), and (3) the doubly robust estimator (Jiang and Li, 2016). We use u denote ut (13) using b as the baseline function. First, we compare our off-ppolicy estimator with the on-policy Monte Carlo estimator (ON).
Theorem 4. Vt, 8,
V (GrDIS
NUT S: =) -V (G (T St = FTT
VA Vullt At) St = 8 + V AAnee (Se, Ar) SSt = + .eN ours (s).
(4.2)
(1.3)
(1.1)
where SQN, SQN.ours()) (s) = 0 for = - and Vt E [T'- - 2]. 88 ours (s)
EA (C
S1+1) - -V (G (- I Sct1) | =
Moreover, prove Vl, 8, 6eN, ours (s) 2 0 meaning the variance reduction in future steps is com-
pounded into the current step.
Its proof is in Appendix A.5. In Theorem 4, show that the variance reduction of method includes three sources, First, a part of the future variance (4.1) is eliminated by choosing an optimal behavior policy μ², Second, the variance of the q function (4.2) is eliminated by the optimal baseline function 6* 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 (2024). Because the behavior policy μ² is tailored for the baseline function we use y** to denote μ² with bascline function and μ PP to denote μ² with no baseline function (i.e., the plain PDIS estimator considered in offline data informed (ODI) method (Liu and Zhang, 2024)).
Theorem 5. VI, 8,
PDIS MET
PDDS
1 15==8) V (C (T St =
(TTTI1
V Acnn pass ( At) |S:) + oe JDD,
(5.1)
(5.2)
where 5ODI, gDDI.ouss( (s) = 0 0 t. IT and Vt E [T- - -2]. 50DI, owss (s) =
p v [v(
(
| -w -
(( Son1 |.s
E B M00
Se-t
Moreover, we prove Vt, 60 ours (s) > 0 meaning the variance reduction in future steps is com-
pounded 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 15. 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 (2016). Since Jiang and Li (2016) does not specify any candidate behavior policy, we leverage the conventional wisdom, supposing they use the canonical target policy π as the data-collecting policy.
7

---

Published as a conference paper at ICLR 2025
Theorem 6. vt,
V Ge (TE--T1) (0p))Ss St =8) [[==8
(TT (17-1
(iT-11
1S =8)
Vul' (Si, (ii, Se = + 8 ours (s).
ourz
(6.2)
(6.1)
where DR. own (s) = 0 t and Vt E [T - -2), 8RR, owns (s) =
A V (--1T1 |1+1) -v (v (THTT1)) S441) 1
Moreover, prove Vt, s, 6... owrs (s) 2 meaning the variance reduction in future steps is com-
pounded 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 y=,, we eliminate a part of the future variance (6.1). Second, the variance reduction in the future steps (6.2) compounded to the current step.
LEARNING CLOSED-FORM BEHAVIOR POLICIES
Algorithm 1:
Doubly Optimal (DOpt) Policy Evaluation
Input: target policy x.
an offline dataset D = {(ti, Si, ai, Ti, s
2: Output: behavior policy μ².
a baseline function b*
3: Approximate Qu from D using offline RL methods (e.g. Fitted Q-Evaluation)
4: Construct VT,1 from D by (38)
5: Construct D, {tt, 8;, a,, Vi, s()
6: Approximate Wz,t from D, by Lemma
7: Return: μu (als) x (als)) (T, a). (7(s, a) (s,e(s,a)
In this section, we present efficient Algorithm to learn our doubly optimal method including the optimal behavior policy 'º and the optimal baseline function b*. Specifically, we learn (4", b*) from offline data pairs. By definition (15), we can apply any off-the-shelf offline policy evaluation methods to learn by (s, a) - (n,(s, a) (e.g., Fitted Q-Evlluation (Le et al., 2019)). By (12), pl (als) x Te (alas) () / Un, (s, (s, a). where is defined in (13)
(n, a) = (1T,1(s, a) a))) vs, E.
(T((ii))))))) S441 = =s/)
Learning from this perspective is very inefficient because it requires the approximation of the complicated variance term V (T( S.+1 = s') 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 f T 1, Vs, a, (s, 0. when t e [ - Vs,a. a,
Un (n () = Vn, a) Ev Pc+ 1 a) (
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 μ can be easily calculated using (12). To ensure broad applicability, we utilize the behavior policy-agnostic offline learning setting (Nachum et al., 2019), in which the offline data consists of [t,, 8,, a, ri, $ with m previously logged data tuples. Those tuples can be generated by various unknown behavior policies, and they are not required form complete trajectory. In the i-th data tuple, ( represents
8

---

Published as a conference paper at ICLR 2025
the time step, s; is the state at time step f,, a, is the action executed, r; is the sampled reward, and s is the successor state. In this paper, we learn (μ²,b*) from cheaply available offline data using Fitted Q -Evaluation (FQE, (Le et al., 2019)). but our framework is ready to integrate any tate-of-the-an offline policy evaluation technique. As for constructing v, we use the learned @ function and ri, sf from the data tuples, according the derivation (38) in Appendix B.
7 EMPIRICAL RESULTS
In this section, we show the empirical comparison between our methods and three baselines: (1) the on-policy Monte Carlo estimator, (2) the offfine data informed estimator (ODI, Liu and Zhang (2024)), and (3) the doubly robust estimator (DR, Jiang and Li (2016).. In the doubly robust estimator, because they do not design a tailored behavior policy, we leverage the conventional wisdom to use the target policy æ as the behavior policy. Given previously logged offline data, we learn our optimal behavior policy and the optimal baseline tuple (n²', bb)) using Algorithm 1. All baseline methods learn their required quantities from the same offline dataset to ensure fair comparisons. We use the behavior policy μ for data collection and the bascline 6" for data processing. Since method reduces variance in both the cata-collecting and the data kata-processing phases, we name our method doubly optimal (DOpt) policy evaluation. More experiment details are in Appendix B.
2.0
Be402h Eveer
0.2
Env Size
On-policy MC
Ours
ODI
DR
0.4
1,000
1.000
0.274
0.467
0.450
27,000
1.000
0.283
0.481
0.541
10'
1.2
10a
1.0
100
10a
10a
Samples
Table 1: Relative variance of estimators on Grid- world. The relative variance is defined as the vari- ance of each estimator divided by the variance of the on-policy Monte Carlo estimator. Numbers are averaged over 900 independent runs (30 tar- get policies, each having 30 independent runs).
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.
Gridworld: We begin by conducting experiments in Gridworld with n² states, i.e., an X n grid with n as the time horizon. 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² = 1, 000 and n = 27, 000, which are the largest Gridworld environment tested among related works (Jiang and Li, 2016; Hanna et al., 2017: Liu and Zhang, 2024). 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 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 shows our method outperforms all baselines by a large margin. The blue line in the graph below all other lines, indicating that our method requires fewer samples to achieve the same accuracy. This is because we quantify such variance reduction, showing our method reduces variance by around 75% in both Gridworld with size 1, 000 and 27, 000.
designed (μ²' b²) substantially reduces estimation variance. In Table I,
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 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.

---

Published as a conference paper at ICLR 2025
Unidle
Shodlo
2h300 M.
Natatra Erte
0.5
19
10
107
10a
107
121
107
10
302
307
10
102
100
361
102
10
10
127
10
10
Samples
Stmmptes
Samples
Samplies
Samplees
Figure 2: Results on MuJoCo. Each curve is averaged over 900 independent 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.
On-policy MC
Ours
ODI
DR
Saved Episodes Percentage
Ant
1000
492
810
636
(1000 -92)/1000 =50.8%
Hopper
1000
372
544
582
(1000- -372)/1000 = -62.8%
D. Pendulum
1000
426
727
651
=57.4%
I. Pendulum 1000
225
356
439
(1000 - 225)/1000 = =77.5%
Walker
1000
475
705
658
(1000 4775)10000 =52.5 %
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. Each number is averaged over 900 independet runs.
MuJoCo: We also conduct experiments in MuJoCo robot simulation tasks (Todorov al., 2012). MuloCo is a physics engine containing various stochastic environments, where the goal is to control robot achieve different behaviors such walking, jumping. and balancing. Figure 2 shows method is consistently better than all baselines in various MuloCo robot environments. Table 2 shows our method requires substantially fewer samples 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
different tasks, achieving state-of-the-ard performance in policy evaluation.
It is worth mentioning that our method is robust to hyperparameter choices-ail hyperparameters required to learn (μ* b*) ) in our method 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. this work, we design an optimal combination of data-collecting policy μ 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, mathematically quantify the superiority of our method in variance reduction compared with existing methods (Theorem 4, 5, 6).
Empirically, compared with previous best- west-performing methods, show method reduces variance substantially in 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 saalllpprhhaps consisting of just single data tuple-the the behavior policy and baseline approximated by our method may be inaccurate. this case, we recommend on-policy evaluation. The future work of our paper is to extend the variance reduction technique temporal difference learning.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work is supported in part by the US National Science Foundation (NSF) under grants III-2128019 and SLES-2331904.
REFERENCES
Chen, C., Liu, S., and Zhang, (2024). Efficient policy evaluation with safety constraint for reinforcement learning. ArXiv Preprint.
Chervonyi, Y., Dutta, P., Trochim, P., Voicu, O., Paduraru, C., Qian, C., Karagozler, E., Davis, J. Q., Chippendale, R., Bajaj, G., et al. (2022). Semi-analytical industrial cooling system model for reinforcement learning. ArXiv Preprint.
Chua, K., Calandra, R., McAllister, R., and Levine, S. (2018). Deep reinforcement learning in a handful of trials using probabilistic dynamics models. Advances in Neural Information Processing Systems.
Deisenroth, M. and Rasmussen, C. E. (2011). PILCO: model-based and data-efficient approach to policy search. In Proceedings of the International Conference on Machine Learning.
Farahmand, A.m. and Szepesvári, C. (2011). Model selection in reinforcement learning. Machine Learning.
Fawzi, A., Balog, M., Huang, A., Hubert, T., Romera-Paredes, B., Barekatain, M., Novikov, A.. R Ruiz, F. Schrittieser,, J., Swirszez, G., al. (2022). Discovering faster matrix multiplication algorithms with reinforcement learning. Nature.
Geweke, J. (1988). Antithetic acceleration of monte carlo integration in bayesian inference. Journal of Econometrics.
Greensmith, E., Bartlett, P. L., and Baxter, J. (2004). Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research.
Hanna, J. P., Thomas, S., Stone, and Nickum, S. (2017). Data-efficient policy evaluation through behavior policy search. In Proceedings of the International Conference on Machine Learning.
Hesterberg, T. (1995). Weighted average importance sampling and defensive mixture distributions. Technometrics.
Huang, S., Dossa, R. F.J., Ye, C., Braga, J., Chakraborty, D., Mehta, K., and Araújo, J. G. (2022). Cleanrl: High-quality single-file implementations of deep reinforcement learning algorithms. Journal of Machine Learning Research.
Jiang, N. and Li, L. (2016). Doubly robust off off-policy value evaluation for reinforcement learning. In Proceedings of the International Conference on Machine Learning.
Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Zidek, A., Potapenko, A., et al. (2021). Highly accurate protein structure prediction with alphafold. Nature.
Kakutani, S. (1945). Markoff process and the dirichlet problem. In Proceedings of the Japan Academy.
Kalashnikov, D., Irpan, A., Pastor, P., Ibarz, J., Herzog, A., Jang, E.,, Quillen, D., Holly, E., Kalakr- ishnan, M., Vanhoucke, V., et al. (2018). Scalable deep reinforcement learning for vision-based robotic manipulation. In Proceedings of Conference on Robot Learning.
Kingma, D. P. and Ba, J. (2015). Adam: A method for stochastic optimization. In Proceedings of the International Conference on Learning Representations.
Koller, D. and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT Press.
11

---

Published as a conference paper at ICLR 2025
Le, H. M., Voloshin, C., and Yue, Y. (2019). Batch policy learning under constraints. In Proceedings of the International Conference on Machine Learning.
Levine, S. (2018). Reinforcement learning and control probabilistic inference: Tutorial and review. ArXiv Preprint.
Levine, S., Kumar, A., Tucker, G., and Fu, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives open problems. ArXiv Preprint.
Li, L. (2019). perspective on off-policy evaluation in reinforcement learning. Frontiers of Computer Science.
Liu, S., Chen, S., and Zhang, S. (2024a). The ODE method for stochastic approximation and reinforcement learning with markovian noise. ArXiv Preprint.
Liu, S., Chen, Y., and Zhang, S. (2024b). Efficient multi-policy evaluation for reinforcement learning. ArXiv Preprint.
Liu, S. and Zhang, S. (2024). Efficient policy evaluation with offline data informed behavior policy design. In Proceedings of the International Conference on Machine Learning.
Maei, R. (2011). Gradient temporal-diffeeent learning algorithms. PhD thesis, University of Alberta.
Marivate, N. (2015). Improved empirical methods in reinforcemenntllcurinng evaluation. Rutgers The State University of New Jersey, School of Graduate Studies.
Mukherjee, S., Hanna, J. P., and Nowak, R. D. (2022). Revar: Strengthening policy evaluation via reduced variance sampling. In Proceedings of the Conference in Uncertainty in Artificial Intelligence.
Nachum, O., Chow, Y., Dai, B., and Li, L. (2019). Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems.
Precup. D., Sutton, R. S., and Singh, S. P. (2000). Eligibility traces for off-policy policy evaluation. In Proceedings of the International Conference Machine Learning.
Puterman, M. I.. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. ArXiv Preprint.
Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning.
Sutton, R. S. (1990). Integrated architectures for learning, planning, and reacting based approx- imating dynamic programming. In Proceedings of the International Conference on Machine Learning.
Sutton, R. S. and Barto, A. G. (2018), Reinforcement Learning: An Introduction (2nd Edition). MIT press.
Sutton, R. S., Mahmood, A. R., and White, M. (2016). An emphatic approach the problem of off-policy remporal-differene learning. Journal of Machine Learning Research.
Sutton, R. S., Szepesvári, C.. Geramifard, A., and Bowling, M. H. (2008). Dyna-style planning with linear function approximation and prioritized sweeping. In Proceedings of the Conference in Uncertainty in Artificial Intelligence.
Thomas, P. S. (2015). Safe reinforcement learning. PhD thesis, University of Massachusetts Amherst.
Thomas, P. S. and Brunskill, E. (2016). Data-efficient off policy policy evaluation for reinforcement learning. In Proceedings of the International Conference Machine Learning.
12

---

Published as a conference paper at ICLR 2025
Thomas, P. S. and Brunskill, E. (2017). Policy gradient methods for reinforcement learning with function approximation and action-dependent baselines. ArXiv Preprint.
Todorov, E., Erez, T., and Tassa, Y. (2012). Mujoco: A physics engine for model-based control. In Proceedings of the International Conference on Intelligent Robots and Systems.
Towers, M., Kwiatkowski, A., Terry, J., Balis, U., De Cola, G., Deleu, T., Goul-ao, M., Kallinteris, A., Krimmel, M., KG, A., et al. (2024). Gymnasium: A standard interface for reinforcement learning environments. ArXiv Preprint.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H.,
Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang. A., Sifre, L.,, Cai, T., Agapiou, J. P., Jaderberg, M., Vezhnevets, A. S., Leblond, R., Pohlen, T., Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine, T. L., Gülçehre, Ç... Wang, Z., Pfaff, T., Wu, Y., Ring, R., Yogatama, D., Wünsch, D., McKinney, K., Smith, O., Schaul, T., Lillicrap, T. P., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D. (2019). Grandmaster level in starcraft II using multi-agent reinforcement learning. Nature.
Williams, R. J. (1992). Simple statistical gradient-followee algorithms for connectionist reinforce- ment learning. Machine Learning.
Zhang, S. (2022). Breaking the deadly triad in reinforcement learning. PhD thesis, University of Oxford.
Zhang, S. (2023). A new challenge in policy evaluation. In Proceedings of the AAAI Conference Artificial Intelligence.
Zhong, R., Zhang, D., Schäfer, L., Albrecht, S. V., and Hanna, J. P. (2022). Robust on-policy sampling for data-efficient policy evaluation in reinforcement learning. In Advances Neural Information Processing Systems.
13

---

Published as a conference paper at ICLR 2025
A PROOFS
A.1 PROOF OF LEMMA 1
Proof. Given any baseline function b, Vp A- 81,80,
[a(as))
(e(ass) 0
(Definition of A
[(s =.
This shows ja A. Thus, A S A.
A.2 PROOF OF LEMMA 2
To prove Lemma 2, we first prove the following auxiliary lemma.
Lemma 4. Ab, Vu E A,, 8.
AAceuel-)..) [pelan,(S,, A,) - (S,, A.)] + b.(s.) S. = s] = (A (S,,(Si, Ar) St s].
Proof. We fix any baseline function Because j E A, Vl, 8, a,
(alss) = 0
mi (s) =0
Tr(als) (0) b)(s,a))² + E. p(51s,a) (G( S411 $
(By (13))
(3) be(s, a))==
(Ur,(8, and Ev p(s'(s, (τ( S4+1 = 8¹) are non-negative) m b,(s,a)) 0.
(17)
Then, we have
E (1
[pel (St, b, + |S: =
Ti(A, St)
(s, A.) - (.s,, A.)] + b.(s)) | S. =
Ve(AA155 (S))
Te(als)
Σ
pr(a|s)
[r(als) ( - (, a)) + b(s))
"E uE(alui(al))=0)
Σ
(r(c))) be a))
Σ
(e(als)b((s)
(E(a)p((a/))20}
aE(a (=())))00)
Σ
((lls) (. a)) bs(s)
Σ
pe(als)
(E(a)p((o))))0)
Σ
(8) (8) b,(s)
Σ
(ala))(u bx
(als)(
Σ
(al)))(um,((s,)) - by (s, a)] b,(s)
(By (17))
aEfalme(a o)
Ti(als) gn, (s,))) (( (s)s
Σ Tr(als)) - br()) + (.())
(By (2))
14

---

Published as a conference paper at ICLR 2025
=E = (S, St = s).
Now, ready prove Lemma 2.
Lemma 2 (Unbiascdness). Ab, Vp A. vt, Vs. E (G"(T=-TT) St = s) (s).
Proof. Fix any baseline function 6. We proceed via induction.
Fort t = T 1, Vp E A, Vs, we have
[ (Te--1
1 = [}]
E (-15))
Pp Re+1 - b,( A.)] (s.) S..]
E (115)
Pa (S:: br(S., A.)] + (..)) [s
= -a
(St,, Az) [S.]
(Lemma 4)
(S.).
Fort E [T -2], 2]. assuming that Lemma 2 holds for + 1, we have 4/ E A, Vs.
((G S1+1 = s] (x).+((s).
Then, VI,
E G (T Sy s]
=E Dr (Re+1 + ( - b,(S, A.)) + b,())) St:]
(By (1))
=E [Pe b,(S,, A.)) + (..) S.] + +E (T( S.]
=E [p be(S,, A.)) + (S.) S.]
(18)) (..AA.) [E. [pe LT 1)| St, A., S |
(T
(Law of Iterated Expectation)
-E [p be(S A.) (S,) S
+ (-18)
[p [G (-( s-1] [s]
(Conditional independence and Markov property)
S:] + E -BArva((-ss.) A.) - (S., A.)] + b.(S.) St]
=E [p[p(RRr+ by A,)) + (.()))
[peVa,t41 S.]]
(Inductive hypothesis)
(Definition of qm,,)
-BA (S, A,) S.]]
(Lemma 4)
=s),(s),
which completes the proof.
A.3 PROOF OF THEOREM 1
To prove Theorem 1, we first characterize the variance of the off-policy estimator a recursive form.
Lemma 5. Yb. Vp E for = -1
V ( S.)) = EAra (S Ad) (.. Ss]] - - (s.))
Fort t [T'-]]
V (T Si)
=EAr Ipt (Bs.,1 VV (G (T"LLLTTT S.11) St, Ar] + MS,, At) (um, A.) -b,(S, A.)]?) St
(S)
- (s.)).
15

---

Published as a conference paper at ICLR 2025
Proof. When t [T 2/, we have
v (T)TT')))))))) St)
=EA ( (G* (T (
St, At) [Ss] + VA, (8 (E[G"( St, At |St)
(Law of total variance)
=EA, (C bs,, A.) + (..) St, (t, A,) [S]
A))
+ +AA A))
A.)
(5, Ad) + b.())) S,, St) (I))
EA, [RŽV (T Sr, Ar) |
+ +AA (Polr(S Ab) + E G (1417-11
S.) (r(S,, br), A.), (S:) are constant given A,)
St. A,]
-EA, [ptV (G' ( S,, St]
(Pil Ad) + [U+,,+1+(((111 St, Ar] - bs( A.) + (((s)) | Ss))
(Lemma 2)
-EA, [PtV (-(1T--)) Sr, A,) St]
+AA (pelgr,e (S,, - (S, A,]
((.) Si).
(Defintion of (r,1) (18)
For the inner part of the first term, we have
v (G" S,,
=Bs.n [V (G (-(TTT))) 8,, A., S(+1) Sc. Ar]
Vsm (E (T" S,, A,, S41]
Se, At)
(Law of total variance)
-Es. V (G(T)))))) S41) Sr, + +S (E (T/41.1))) S141]
|S,
(Markov property)
-Bs.41 [V (TG"(TTTT-)) S(+1) S, A.] + VSu, ( (S,
(Lemma 2)
-Bs441 [ (G S41)
St, A.] (1 Ar).
(By (11))
(19)
For the second term, we have
(r As)
-VA (polun, (S,, Ad) (S, A.] + b,(S,) 8t)
(By (11))
-EA, [AAllt, A1) (, A.)] + ( |s.]
(EA. [pilppl (St, A,) b, A,)] (.() |s.])²
-EA. [AAll,, (S., A1) - 6, A.)] + (S.))) [s.] (.:)
(Lemma 4)
-EA, [PÊ (St. A₂) (S., 1. S.] + (S. Iee ( As) - be(s,, A.)] S.
+ (S,)² (S.)²
= EA. [pīlqm. (S. Ad) by (S,, AD) [s]] + (S))EA [p.lam, -
- b.(S,, + +,())) St]]
- -2,) + (8))) 8 (S)2
-EA. [or((n, (St, (s),A) At) (Se, A:]]² |S:] + 25.
-b,(S))3 (S,)²
(Lemma 2)
-EA, [p?(gr, Ar) be (S., A.) s.] -S..(())))((S))))) 2..)))
(20)
Plugging (19) and (20) back to (18) gives
V ( |
=EA [ (G ( (M St, A.) S.]]
+ VA, (St, A.) b,. A.) + (..)) (.))
(By (18))
16

---

Published as a conference paper at ICLR 2025
EA. let (Es V (T(411)))) S(+1) | At] (s,, |Si]
+ Va. (pelax, A.) (S,, A.] + (S,) St)
(By (19))
EA. [oî (Es..) (V (T++11)- S(+1) | As + -V(( A,)) S.]]
+ BA, [ A1) b, Ar] |S:]] - (Vr,( - (S.))
(By (20))
=BA
[0]
[Est12
V ( (+(1)=))))) |Sc+1) |t,
A.))) (S( Ad) + (.), si
(Su,, b(()))
When -T- - 1, we have
(T St)
(prrr((s At) - (s, A+)] + (,()) | S.))
(By (1))
-V A.) (S, A,] b,),,,((s)))) St))
-EA, (pi (St, - (S, A,) St (()..()))-b(())) b(S)))
which completes the proof.
We now restate Theorem 1 and give its proof.
Theorem 1. For a baseline function b, the behavior policy μ defined in (12) an optimal solution to the optimization problems Vt,
min V (G |S =
S.t. μEA.
Proof. Fix a baseline function b. Vt,saa 8, a.
(als)) 0
= (als)) ()) = -0
(By (12))
((alss)u 0.
Thus, n E A.
Vt, An A, have unbiasedness on / (8, a).
PLy PLy ( A,) SS =
BAraas
(e(ss) (als)
(E(a)u((a)s)20) (r(als) V ())
Σ
Σ [E(a)ur(a)))>0)
ne(a|s)y as,
Σ
no(als) a))
Σ ne(als) una(s,a)
dE(a|ur(al=)>0)
(Vu E ((las) = = m((a)))m,,(,,))=== 0 by (14))
=EANNR Venn.(SeAAA) St =
(21)
We prove the optimality of the behavior policy n² via induction.
When = T - 1, 1, E A, Vs, the variance of the off oof-po estimator has the following lower bound V (G' S
17

---

Published as a conference paper at ICLR 2025
ppt I (S), [.)] [s]] - (Ux,(()) - b(()))
(Lemma 5)
-BA
| (St, A.) [S.] (Ur, (St) b,())))
(By (13))
Pc (U Aa) S (Ux, - ((.)))
(By Jensen's Inequality)
=BA
V Vur.eSS,, At) | St (Vn,((St) b.())))
(By (21))
For any state 8, the variance of the off-policy estimator with the behavior policy jr achieves this lower bound by the following derivations.
(G ( St =)
(22)
=AA Te (St, (St, A²) - be((S, St] (Vx,((S)) (S,))
(Lemma 5)
-BAire [p] e At) |S:] (U,,((S)) b(())))?
(By (13))
For the first term, we have
EArpy [ppun, Ad) St]
(e(a|s)) Ux (St,a)
(a)(s)
Σ Te((alS)\ " a) Σ Te(S,, 6) (S., b)
(By (12))
A
V ( St
(23)
Plugging (23) back (22), we obtain
(G -ir-))) S =
(T
EAyont (p:u,, Ar) [. - (Vn,(Si) - b((S))))
2
-EA
VurlS Se - (Vr,(S.)) - b(()))) b,,
Thus, the behavior policy 4= defined (12) is an optimal solution to the optimization problems
min V (T =
S.t. DEA
fort and all s.
When t E [T - 2], we proceed via induction. The inductive hypothesis is that the behavior policy μt² an optimal solution the optimization problems
min
V (
= =s)
DEA
for all s.
To complete the induction, we prove that the behavior policy f² is an optimal solution to the optimization problems
min v (G =
s.t. μЕΛ
for all
18

---

Published as a conference paper at ICLR 2025
Vy E A, Vs, the variance of the off-policy estimator has the following lower bound
V (TET-1)) St =s
B Bemmm [pt (Bs:41 IV (7 S4+1) St, Ar] + vr(Ss, Ar) (s,, b,( A.)]3) St)
- (5n)
(Leemaa 5)
BBArM [0ž (EsL. // ( |S41) St Ar) + 1v(S, As) + I0,, Ar) - be (S A:]l²) S...
- (S), - ((()))
(Indutive Hypothesis)
-AAMME [ At) ss:] - (v,, bS()))
(By (13))
2
Pe /VVu,a(Se Ar) St
BANcHs
- (Ur, - ((.)))
(By Jensen's Inequality)
Vum.c(Se.A)) Ad) S 2
= =BArNT
(Vn,((S:) -
(By (21))
For any state 8, the variance of the off-policy estimator with the behavior policy μ achieves the lower bound by the following derivations.
V (o'
(TE-TT 1
[BS-- V [
( Hinz
( ((+1)) S8,, Ar] + ve(e,, A.) + (0,, Ad) be A.])²) (s,, |.t
E BAC
(741:-11)
- (S.)
- (x.)))
(Lemma 5)
=BArNEE
( Ar) Si] (Un,((S)) - b.())))²
(By (13))
-EANNT
(um,I(Se.A)) At) S: (U,,((S)) - b
(By (23))
Thus, the behavior policy μ² defined in (12) is an optimal solution to the optimization problems
min V (T S.
#
s.t. PEA
for and all
This completes the induction.
A.4 PROOF OF THEOREM 2
In this proof, differentiate different μ² with different baseline functions 1²² denote the corresponding μ* when using a function b as the baseline function. G¹, 2/. and A are defined following the same convention. We first present an auxiliary lemma.
Lemma 6. Vb. Vp A Vt,
EE EArrp [pilg,, (Sc, Ad) - (s, Az) S..] - - 2S. V VAnm (p: (p:(9 At) (S, At)] S.)
(24)
Proof. Vb, E A Vt.
EAwape (0 (st b.((S, A,) S (S,, be()))]2
-VArnp (pe 1oi.m.e(S5 (St, - -b,(S,, A,)
S)) + Exrra Ipo19m. Ar) - bs( S&)
(S.r.(SS.) - (S.))
-VAin (Pe 17, (Se, At) -br(S,, A.) S.)) EA,a (el AA) b. A.) (s.)
19

---

Published as a conference paper at ICLR 2025
(e (sc, Ac) b.(S., b.(s.) St)
-S.)2
(Definition of 2x,t. Lemma 4)
-Va (Pe An. (S, A1) (St, A.)] 5t) BA,rar (Se, At) by (St, A:)] 1s))
(sss) ( - (St. A,)) S|]²
V VArm An As) )- (5,,,, A+)] St).
We now restate Theorem 2 and give its proof. Theorem 2. 6* is the optimal solution to the optimization problems Vt, 8,
min b
v ( s(=ss
(16)
Proof. We prove this by induction on the time step L.
When T - 1, Vs, the optimization problem (16) has the following lower bound
V(G (TETTT) So = s)
E Amant [pt 1n Ad) - (S, A:)]² St] [U,,((S)) - (S.))² Acmit ( b, A,)l S))
(Lemma 5)
(Lemma 6)
20.
(Variance non-negativity)
When using b* as the baseline, we achieve this lower bound.
V(G" ( s)
Amagg ( As) (5. A.]]² S.] - [Sn. (S:))²
(Lemma 5)
=V om (pelax, (S, (, A.) S))
(Lemma 6)
Acmeii (S, A,) - (S, A,) 5.)
(Definition of b" (15))
-0.
When E [ - 2]. we proceed via induction. The inductive hypothesis is that the baseline function 1 is an optimal solution to the optimization problems
V (G
min
for all s. Notice that we have
A A
(25)
This is because Vs, a,
a))
((n.(s,a)-b(ssd))) +zz)(s,a) + Er P(s|s,,)))) (c(("i+trr))) S = ss
(By (13))
22r,((s, + p(s
G ((
S41 =s)
2V,,(88,)) + p(s's,,,))) (( 20)
(-17-11
S41 = =s
(Inductive Hypothesis)
Thus, Vy E Ab, we have Vs, a
m(lss)
20

---

Published as a conference paper at ICLR 2025
= ((d =
= x(als)u =
This shows
A C
vb, the optimization problem (16) has the following lower bound
PET Go (TE.T-11)
(T:TT
150
=E Armui
pt EES V
((((++))))) SS+1
(i
St A
(S,, S:
+ E Anmpe
(p) (Se, At) - As)) |
(U,,
b(()))1
(Lemma 5)
> A Almpiih [PEla,, Ae) (Se, Ab)]² | (U,,(())
Pi
Esets 1/ ((*""
G (G (G (( St+1
|S A4
+ (s(S,, St
(S.))
(Inductive hypothesis)
E Ammut pi (Esui v (c("
(+ Sc+1 | Ag
+ (c A.) St
+ V Aumpi (prl (e,S,,440 At)l St)
(Lemma 6)
2B A
V
(C*
Gh
(イ
..6"
S4+1
S1, Ag
+ vs,,,, A,) Se
(Variance non non-negativity)
E A
1 (Se,, Ac) |s:]
(By (13))
>B A, b
Pe Pevi 1 (Se, As) |.
(Jensen's 's inequality)
=EAiNY
u (Sc St
(By (21) and (25))
When setting Vs, (3, a) = (n a) the baseline, we achieve this lower bound.
(TT=TT))
So =
E Ammpgii
Esu
V
600
m.bb' (
Se+1
|S,, A
+ 12 A.)
|S
E Aampy
[ (S Ar)
(S Ac)]² [s:]
(Sx,
(S:))
(Lemma 5)
(C""
=B -E -BAinn
Esi W
ch'² -it1s-11 Se+1
| Ar
+ +s.,
S
(pelum. Ar)
(5 Ad) S))
(Lemma 6)
=E As-ap
p (Bsit]
G
6D"
(T+11-11)
Se+1
|St, A
+ (s S.
V A
(pelor,e(Se, Ar)
(Se, At) St)
(Definition of 6" (15))
E 2,-03.00
p Bsits V
(14117-11)
Ss+1 1Sc, Ar
+ 4v A.))
S
E 20
pi
[S|
(By (13))
2
Vulia(Se Ar) |S
=EAINRI
(By (12))
21

---

Published as a conference paper at ICLR 2025
Thus, 6* is the optimal solution to the optimization problem
(T min V (G"TTE)))) St =
for all and 8.
A.5 PROOF OF THEOREM 4
Proof. Use of to denote (13) using b* the baseline function. Then, by (13), for / 1
df (s. a) (g,,((,,)) bs(s.a)) O.
(26)
For L E [T -2). 2/.
u (s)
m.b" =(m,,(s, a) - be(s,a))² + vn, P(sls,,,)) (6"
(((TT=)) S411 =s')
(By (13))
Ex G (T Sp+1 =8)
(By (15))
(27)
The variance of GO¹ (1 has Vs,
(G (1 SS =)
(28)
b,, (Si,
Si] (v,,((S)) (S))))
(Lemma 5)
=0
(Definition of b* (15))
prul (St, As) S
(By (26))
2
=EANTT
u8/ (Sr, Ar)
(By (23))
Fort E [T' - 2).
v (a" ( S₁ =s)
(29)
EANNE
p (Es V "C |
SS411) Sc, + +v(s,, + (s,, Ar) (s, A.)) |s.
(Lemma 5)
- -S), b((()))2
-
-EANHi
12 (Ese.] V (V(6" (T(1)T))) | Sa+1)) Se, Ao] + (((s, Se
+ A (p)lg,,(S(,,AA) (7,S,, (5(S),A)) AJ) (]] St)
(Lemma 6)
-AACH
o Esse
(h' (T( St+11 Sr. An] + vr Ai)) St
(By (15))
-EAINEE
poul"" (St,
(By (27))
/u (St, Ar) St
=EA,NT
(By (23))
The variance of PDIS ( has Vs, for 1,
V (GPDIS TTT--11 S, =
(30)
=EA,T
[4, A,)² St] Ux " (S))²
(Lemma 5 with b 0 and on-policy)
22

---

Published as a conference paper at ICLR 2025
- AinTE (Sr,(((e,Ai) St)
(Lemma 6 with b = 0 and on on-policy)
= =
uy (St, |ss] + VANT (Sr, (s) St).
10
(By (27))
Fort E [T -2), -2].
V (GPDIS (TT=-1)) St =
(31)
=BArN Esit1 [V (G (417--11 St-1) Ai) + 11(s,, Ab) + (S, A,)² St]
(S,))
(Lemma 5 with 0)
BANNT
Es... V (GPDIS (T+1T-1) S(-1) Ai. + (m((s,AA) [
+ V VAnNs
At) S()
(Lemma 6)
BA
Esc+i
V/ Gb
(T+TT-))) S1+1 S1 + +M((s, A,) 1
+ VANTT (St, At) |.S.)
(GPDDS (T S411 - 70" ((" (4411 Sr. Ar St
+ BACWRT
E Esi+1
V
= -EAINT
u4 (Se, Ae) |
+ V Kimir
(1T, At) (S))
V (GDD (G ( ( SS+1) -w (0* (( ((it)))) ((4)))))))))))))))))))))) Se, Ar Se
+ EAcest
Esi+
(By (27))
Thus, for T 1, their difference
(G PDIS FeT-1) 1S, -V) (T" ( |Sa= =8)
EANTT " b" Ac) 15 -RAINT [Vatt (St, Ai) S
+ V VANN (St, (Si)
(By (28) and (30))
=V AAnan
Vut (S
(St,
Ai) Si + V VALNTe (S,, SS))
Fort E [T 2).
V (OPDIS
TTT-11 [S= -V "0"0 (T |St = 8)
(T
b' (St, Ax) |S: - -RAATT V Vul (St, Ar) || Ste 2
= EA
"
VAine
(S |S))
Es++1 EANnT
PGDDS (- (441)-17 (c" " (1 |St1) St, St,
[s.
(By (29) and (31))
(Wift (Su
=VANo
(St, Ar) | (S
+VAn (St, Ar) (s)
V (T S442) -V -V(C"( | (442))
St, Ag [
-EANT
Esat1
23

---

Published as a conference paper at ICLR 2025
We induction to prove vt, s, JON, ours
2 0. Fort T T-1 1,
ON, ours (s) 0 2 0.
For E [T 2). the induction hypothesis Vs,
0 0+1
ouns
(s) 20. 0.
This implies Vs.
(GPDIS (T+1T-11 S4+1 = =s)- -V 7((0 ( S441 =8)
A (Vatiz (uliz(Sit2, S1+1 =
+ V Aesimaiia (Sr,4 Ac+1)
Se+1 + --0t11 ouns (s)
20.
(32)
Thus, Vs,
ON, ours ())
V
(T St41) - -V 7600 ((ft)==))) S4+1) |S: =s]
= -A Se+1
20.
(by (32)) (33)
Thus, Vt, s, 0z
ON, ours (s) 2 0.
A.6 PROOF OF THEOREM 5
Proof. The variance of PDIS
(T "iT
(T::T-1") has Vs, fort= = T 1,
PDIS
TTT (TT-T))
S =
(34)
(St, A,) |S:]] (S,)
(Lemma 5 and 0)
=V Aimpi
(Si
(S)
(By (24))
-E A .un
piut (St,Ar) Ar)
St
+ + A mas (pegr, S.)
(By (27))
2
Vull /uf (i), St
-AA
A mos (Sc. Ss).
(By (23))
Fort E [ - 2].
2015
V
PDIS
Sc =
(35)
E A Pois
o
[ssy v
..P0s PDIS
(T
-t------1) Se+1 ) |
|s,, An + vr(S,, At) + (m, An)²) S.
(St)
(Lemma 5 with 0)
E Ammii mas
oo Bsit2
PDIS v
(PDIS
P1-12-11 (- Se+1 AS + vr(S,, Ao) S
..P06
+ V Aampy PDus (pig
(c)
(Lemma 6 with 0)
=B Arnu, mas pe
Esi12
V
(
(T4+1:7-1) (TD
GPDIS
Sct11 St, Ao + Ar) 1t
+ V Aampp,000 (PIgr.((S(,AA)) St)
24

---

Published as a conference paper at ICLR 2025
+ E Ae Aemus 1o1s pf [Ss [
( ( (T++1.--1)) ) 14+1 -V GGDIS ( (f++1:T-1) ( 11+11
GPDIS
1e,, A1 1) St
2 E Ammpp
Pr Besti
(
(GDDIS(T "iir (1++1--1) S111
GPDIS
Se, A1 + ust, (() St
+ V Aimpe mos (PeRRee (St: St)
+ E Aimua H015 pt Ess4
v
GPDIS
(F (41:7-11 S.+1
Mi
Pas
-V - -V(cuDs
( Set1 ) (...A.))) St
(4p4
PDis E Aes Mr
achieves the minimum value of the first term in AA)
=E Acrugii [Prut As)
+ V Aemma ros (Pel (St; Ac) (s))
+ E A rus p [Esi+1 (
V
GPDDS
((11T-1) S441 V
(
(T+11T-1)
Si41 (Ss.AA)) |s|
(By (27))
2
-A Vul (Se. Ad) Se
(Se
+ V Aemmg ross
(pelT,((Se (St;
Ar) St))
1) |St
+ E A mms p Esitt1
V/ (
(G
(741:1-1) |S41 V (GDDIstTH
Se+1 1 (s,
(1+11-11)
(By (23))
Thus, fort = 1
2015 PDIS
(TTT11 S: =
HET-1)
Gb ( St =
V Am 2ois (Pe9T, (St; At) (S))
(By (28) and (34))
Fort t E [ -
2015
V PDIS (
St 58 - -V 6b" (-) St SS.= =6)
V A nos ( (Sc,A)) (
+ E A
rois
Pi
Escss
V
PDIS
PDIS (T #++1-T-1)
1.."" Si+1 -V (GHDIS
Si+1
St A1
1)) s
(By (29)and (35))
The proof of Vt. s, JDI ours (s)
is similar to (33) and is omitted.
A.7 PROOF OF THEOREM 6
Proof. We begin the proof by manipulating the variance of Gh' (T"TET") Vs, for = T 1,
V (Ctt ( =8)
(36)
-EANT (St,, At) - (S,, St] - [V.,((S:) (S)))
(Lemma 5 and on-policy)
(Definition of (15))
= =EANNE
1/ Ai) si]
(By (27))
Fort [ -22- 2].
V (6'² () St = 8)
(37)
25

---

Published as a conference paper at ICLR 2025
BA
Bsa+1
V (C"" (T+tTT-)))
(S411) |Sc,Al] + +u((,, + (sx, by A()]? St
- (Sn,)((t) b(():)12
(By Lemma 5)
-EANNT
Bs+t1
V (G""TT (T+IT-11) (44) |Se, + +v,(
+ VANT
(117, Ac) (S,, A.)] (t))
(Lemma 6)
-BA
Ess11
Gh (Λ S1+1 |St, Ar
+ (S,, At)
(By (15))
-ANNT
Esa
V Gh
(MAT))))) S(+1 A|
+M(S., 1
+ EAANNe
Es V v(C" ( (++1)=)) |S41] -V
(" -
-v
-.66
|S(41) 1
Se, Sc, Ao
S
=RAiNN
ul (Se, Ae) 1
+ EAINRi
Est
V (( (T+N)=)) |Stn)))))))))))))))))))))))))|
[S -V 6t' (0
(+ff)==))) S1411
m..6
Se, A
S
(By (27))
Thus, for T 1, their difference is
v c (T St =s) =) -V
(at (1 St =s)
1
EANT
up (s),
Vull (Sr, (s) Ss
(By (28) and (36))
=VAINT (Vul 1// (S (Se,AA) |S:) 1s.)
Fort E [ 22..
V lb' (TTETT) |S,= - -s:==)>v((c (c))
-.6"
(T ( =8
2
Vul (Se, Ar) 15c
ug (St, At) St -EANNT
+ EANNTe
Esi+. 1 7("' (T++1))1)) 11 -v -W (v('"((ttr))))
| Ss A 1 St
(By (29) and (37))
(Valz (St, (V
-VAnn
Sss
EANTE Es.11 V ( (+TT)))))) [841) -V (ct ( 18((1))))) | S6 A |S
The proof of Vt. s, 6 ours (s) 2 0 is similar to (33) and is omitted.
A.8 PROOF OF LEMMA 3
Lemma 3 (Recursive form of u). With b = b*, when t = T - 1, Vs, (n,((s,)) = 0, when
t t T 2]. a.
Un (8, a) (s Er a Pe+ 10(s ( (a'ls')uu,,t (8', a').
26

---

Published as a conference paper at ICLR 2025
Proof. When thent=12 = T Vs
(x
= (s, + (n)
(By (27))
=0.
(By (15))
When E [T- 2). Vs
(7,((8,0)
(,,,((8,0) - Ep(olos.aW G (((()))))))) S141 = =d)
(By (27))
-Vm,(88,0) = Σ p(sslss.a EA (St A(t1) S =s]
-(0x,4+((5') (
(Lemma 5)
(8,,(8,0)) + Σ plsl1s, A.nAiii P UT Acti) Se41 =d]
(By (15))
=Va,e(s,a) - Pet1pp(s (
3'
B EXPERIMENT DETAILS
We utilize the behavior policy-agnostic offline learning setting (Nachum et al., 2019), in which the offline data consists of ((4, 8;, a;, ri, s() ">>"" with m previously logged data tuples. Those tuples can be generated by one multiple behavior policies, regardless of whether these policies are known unknown, and they are not required form a complete trajectory. In the i-th data tuple, t, represents
the time step, is the state at time step f; is the action executed, т; is the sampled reward, and s/ the successor state.
In this paper, first learn the action-value function 9r,t from offline data using Fitted Q-Evaluation algorithms (FQE, Le et al. (2019)), but our method can integrate state-of-the of-the-art offline policy evaluation techniques. Notably, Fitted Q-Evaluation (FQE, Le al. (2019)) is different algorithm from Fitted Q-Ipprovmennt (FQI). Fitted Q-Evaluation is not prone to overestimate the action-value function a, because Fitted Q-Evaluation does not have any max operator and does not change the policy.
Then, by the following derivation
(s, a)
=Vs (V (0,,4(((S(4))) St = A, a)
(By (11))
-Es ( ) $|S 8, A, = a] Es,n (1 5; A, == a)²
=Es,1 (Vr,e-1
S: = 8, A, = a] - (8) r(8, a))
(38)
the first term is expectation of S Because have (li, 8i, Qi (i, ri, 8)) data tuples, we construct using sy in (t,, St. a;, T4, st{) data tuples as the sample of the first term and compute the rest quantity using the learned vadion-valle function fx.t and reward data rú. Therefore. we construct Finally, by passing data tuples in D, from t = T 1 to O, we fit the
D, = [(t,, 8i, aj, Vi, s{)), function U,,( using FQE in a dynamic programming way with respect to the recursive form of u, derived in Lemma 3. For each time step, we take copy of the neural network as an approximation of function Un, at time step I. After learning the functions Ur, and (T,,, we return the learned behavior policy μ (a|s) x (a(a)s) ( a) and the learned baseline function by (s, a) = (n,1(8, a). The pseudocode of this procedure is presented in Algorithm 1.
B. GRIDWORLD
For Gridworld with size n, we set its width, height, and time horizon all to be n. The number of states in this Gridworld environment scales cubically with n, offering suitable tool to test algorithm
27

---

Published as a conference paper at ICLR 2025
Figure 3: MuJoCo robot simulation tasks (Todorov et al., 2012). The pictures are adapted from (Liu and Zhang, 2024). Environments from the left the right are Ant, Hopper, InvertedDoubleeendduuu InvertedPendulum, and Walker.
scalability. We choose Gridworld with n. 1, 000 and n²3 27, 000, the largest Gridworld environment tested among related works (Jiang and Li, 2016; Hanna et al., 2017; Liu and Zhang, 2024). There are four possible actions: left, right, up, and down. After the agent takes an action, has a probability of 0.9 to move accordingly and a probability of 0. to move uniformly at random. If 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. We generate the ground truth policy performance using the on-policy Monte Carlo method, running each target policy for 10 episodes. We test two different environment sizes of the Gridworld, The offline dataset of both environments contains 1, 000 episodes generated by a set of random policies. To learn functions dr.t and Ur,t, we split the offline data into a training We tune all hyperparameters' offline based on Fitted Q-learning loss on the test set. We choose a mee-hideen-layrr 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 [le 1e "l -3 3, -] and choose use the default learning rate -3 as learning rate for Adam optimizer (Kingma and Ba, 2015). All benchmark algorithms are learned using their reported hyperparameters (Jiang and Li, 2016; Liu and Zhang, 2024). Each policy has 30 independent runs, resulting in 30 30 = 900 total runs. Therefore, each curve in Figure 1 is averaged from 900 different runs over wide range of policies, showing strong statistical significance.
with 000 states and 27, 000 states.
and
set.
B.2 MuJoCo
MuJoCo is physies engine containing various stochastic environments, where the goal is control robot to achieve different behaviors such as walking, jumping, and balancing. Environments in Figure 3 from the left the right are Ant, Hopper, InvertedDoubleeendulue
InvertedPendulum, and Walker. We construct 30 policies in each enviromment (resulting total of 150 policies), incorporating wide range of performance generated by the proximal policy optimization (PPO) algorithm (Schulman et al, 2017). We use the the default PPO implementation in Huang et al. (2022). We set each MuloCo environment to have a fixed time horizon 100 in OpenAl Gymnasium (Towers et al., 2024). As our methods are designed for discrete action space, discretize the first dimension of MuJoCo action space. The remaining dimensions are controlled by the PPO policies, and they 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 9r,1 and Ux,4 are learned the same way as in Gridworld environments. Our algorithm is robust hyperparameters. All hyperparameters in Algorithm are tuned offline and are the same across all MuloCo and Gridworld experiments. Each policy in MuJoCo also has 30 independent runs, resulting in 30 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.
900 total runs. Therefore, each
28


Reviews:
[{"review_id": "E121iOJ6Fm", "reviewer": "Reviewer_Zj5D", "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.", "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.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. It is an interesting problem to study that to evaluate a given policy, what is the best behavior policy to collect samples.", "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. \n1. 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.\n2. 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.\n\nThe above is the biggest weakness. It is not clear what is achieved by their method theoretically or practically. \n\nBesides, there are also other problems which make their theory fragile.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "I0tIZ0iNr2", "reviewer": "Reviewer_EiDc", "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.", "questions": "1. Please address my concerns in the weakness.\n\n2. 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.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "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.\n+ 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.\n+ The experiments show performance improvement over existing methods.", "weaknesses": "- A potential error in the proof:\n\nIn equation (23), the second equal sign does not make sense. By equation (12) that \n\n${\\mu}^{*}_t (a|s) \\propto \\pi _ t (a|s) \\sqrt{u _ { \\pi, t} (s,a)}$.\n\nWe should have \n\n$\\sum_{a} \\frac{\\pi _ t(a|S_t)^2}{\\mu^{*}_t (a|S_t)} u _ {\\pi, t}(S_t,a)$\n\n$= \\sum_{a} \\pi _ t (a|S_t)\\sqrt{u _ {\\pi, t} (S_t, a)}$\n\nHowever, in the paper the author seems to give the wrong result as \n\n$\\sum_{a} \\frac{\\pi _ t(a|S_t)^2}{\\mu^{*}_t (a|S_t)} u _ {\\pi, t}(S_t,a)$\n\n$=\\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)}$.\n\nUnless 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.\n\t\nAfter the second equal sign in equation (18), there's an extra \")\" after $\\bar{b_t}(S_t)$; \n\nAt the start of equation (20), $\\nu_t(S_t, A_t) =$ should be removed; \n\nIn page 17, the $\\mu^{*}_t$ after the third equal sign should be $\\mu_t$.\n\n- 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.\n\n[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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1ITRRuf0ms", "reviewer": "Reviewer_c89B", "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. \n\nThe 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.\n\nThe 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).\n\nThe 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).\n\nThe 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.", "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.\n\n2. 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?\n\n3. 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?\n\n4. Including a background on DR and ODI in the background section could enhance reader comprehension, as these are central to the analytical comparisons made.\n\n5. 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.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 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.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)