Multiple-policy Evaluation via Density Estimation
Authors: Yilei Chen
Aldo Pacchiano
Ioannis Paschalidis
Venue: ICML 2025 poster (2025)
Keywords: Theoretical Reinforcement Learning; Policy Evaluation; Instance dependent results;
Primary area: theory->reinforcement_learning_and_planning

Abstract: We study the multiple-policy evaluation problem where we are given a set of $K$ policies and the goal is to evaluate their performance (expected total reward over a fixed horizon) to an accuracy $\epsilon$ with probability at least $1-\delta$. We propose an algorithm named CAESAR for this problem. Our approach is based on computing an approximately optimal sampling distribution and using the data sampled from it to perform the simultaneous estimation of the policy values. CAESAR has two phases. In the first phase, we produce coarse estimates of the visitation distributions of the target policies at a low order sample complexity rate that scales with $\tilde{O}(\frac{1}{\epsilon})$. In the second phase, we approximate the optimal sampling distribution and compute the importance weighting ratios for all target policies by minimizing a step-wise quadratic loss function inspired by the DualDICE objective. Up to low order and logarithmic terms CAESAR achieves a sample complexity $\tilde{O}\left(\frac{H^4}{\epsilon^2}\sum_{h=1}^H\max_{k\in[K]}\sum_{s,a}\frac{(d_h^{\pi^k}(s,a))^2}{\mu^*_h(s,a)}\right)$, where $d^{\pi}$ is the visitation distribution of policy $\pi$, $\mu^*$ is the optimal sampling distribution, and $H$ is the horizon.

Multiple-policy Evaluation via Density Estimation
Yilei Chen Aldo Pacchiano
Ioannis Ch. Paschalidis
Abstract
where prior to deploying a trained policy, thorough evalua- tion is imperative to ensure its safety and efficacy.
We study the multiple-policy evaluation prob- lem where we are given a set of K policies and the goal is to evaluate their performance (ex- pected total reward over a fixed horizon) to an accuracy with probability at least 1 6. We propose algorithm named CAESAR for this problem. Our approach is based on computing approximately optimal sampling distribution and using the data sampled from it to perform the simultaneous estimation of the policy values. CAESAR has two phases. In the first phase, we produce coarse estimates of the visitation dis- low order
Broadly speaking there exist two scenarios where the prob- lem of policy evaluation has been considered, known on- line and offline data regimes. In online scenarios, learner is interacting sequentially with the environment and is tasked with using its online deployments to collect helpful data for policy evaluation. The simplest method for online pol- icy evaluation is Monte-Carlo estimation (Fonteneau et al., 2013). One can collect multiple trajectories by following the target policy, and use the empirical mean of the rewards as the estimator. These on on-policy methods typically require executing the policy we want to estimate which may be unpractical or dangerous in many cases. For example, in a medical treatment scenario, implementing an untrustworthy policy can cause unfortunate consequences (Thapa et al., 2005). In these cases, offline policy evaluation may be preferable.
tributions of the target policies sample complexity rate that scales with O(-). In the second phase, we approximate the opti- mal sampling distribution and compute the im- portance weighting ratios for all target policies by minimizing a step-wise quadratic loss func- tion inspired by the DualDICE (Nachum et al., 2019) objective. Up low order and logarith- mie terms CAESAR achieves a sample complex- ity Ô ( where
In the offline case, the learner has access batch of data and is tasked with using it in the best way possible to esti- mate the value of a target policy. Many works focus on this problem leveraging various techniques, such as importance- sampling, model-based estimation, and doubly-robust esti- mators (Yin and Wang. 2020; Jiang and Li, 2016; Yin et al., 2021; Xie al., 2019; Li et al., 2015). In the context of offline evaluation, the theoretical guarantees depend on the overlap between the offline data distribution and the visita- tions of the evaluated policy (Xie et al., 2019; Yin and Wang, 2020; Duan et al., 2020). These coverage conditions, which ensure that the data logging distribution (Xie et al., 2022) adequately covers the state space, are typically captured by the ratio between the densities corresponding to the offline data distribution and the policy evaluate, also known as importance ratios.
1 E' maX Ex.a
(d) (s.a))² (1(().))
d= the visitation distribution of policy x, μ² is the optimal sampling distribution, and H is the horizon.
1. Introduction
This paper delves into the problem of policy evaluation, a fundamental problem in RL (Sutton and Barto, 2018) of which the goal is to estimate the expected total rewards of a given policy. This process serves as an integral component in various RL methodologies, such as policy iteration and policy gradient approaches (Sutton et al., 1999), wherein the current policy undergoes evaluation followed by potential updates. Policy evaluation is also paramount in scenarios
Motivated by applications where one has multiple policies to evaluate, e.g., multiple policies trained using different hyperparameters, Dann et al. (2023) considered multiple- policy evaluation which aims to estimate the performance of set of K target policies instead of single one. At first glance, multiple-policy evaluation does not pose chal- lenges beyond single-policy evaluation since one can always use K instances of single-policy evaluation to evaluate the policies. However, since the sample complexity of this
'Boston University, Boston, USA BBroad Institute of MIT and Harvard, Cambridge, USA. Correspondence to: Yilei Chen <ylchen9@bu.cc bu..uuu>
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Multiple-policy Evaluation via Density Estimation
procedure scales linearly as a function of K, this can be extremely sample-inefficiett as it neglects potential similar- ities among the K target policies.
the second phase, the samples generated from this behavior distribution are used to estimate the target policy values via importance weighting. Since the importance weights are not known to sufficient accuracy, we propose the IDES or Importance Density EStimation algorithm (see Algorithm 1) for estimating these distribution ratios by minimizing a se- ries of loss functions inspired by the DualDICE (Nachum et al., 2019) method (see Section 4.3). Combining these steps we arrive at our main algorithm (CAESAR) Coarse and Adaptive EStimation with Approximate Reweighing al- gorithm (see Algorithm 2) that achieves a high probability finite sample complexity for the problem of multi-policy evaluation.
Dann et al. (2023) proposed an online algorithm that lever- ages the similarity among target policies based on an idea related to trajectory synthesis (Wang et al., 2020). The basic technique is that if more than one policy take the same ac- tion at a certain state, then only one sample is needed that state which can be reused to synthesize trajectories for these policies. Their algorithm achieves an instance-depender sample complexity which gives much better results when target policies have many overlaps while it requires estima- tion of generative models as an intermediate step which can be unpractical.
We summarize our contributions as the following,
Different from Dann et al. (2023), in this work, we tackle multiple-policy evaluation problem from the offline perspec- tive'. In the context of single-policy evaluation, an offline dataset is typically given and assumed to provide good cover- age over the state space of the target policy. Nevertheless, in our scenario, such a dataset does not exist. To overcome this issue, we design our algorithm based on the idea of firstly calculating behavior distribution with enough coverage of the target policy set. Once this distribution is computed, independently and identically distributed (i.i.d.) samples from the behavior distribution can be used to estimate the value of the target policies using ideas inspired in the of- fline policy optimization literature. Briefly speaking, our algorithms consist of two phases:
We propose a novel, sample-efficient algorithm, CAFSAR, for the multiple-poliey evaluation problem which achieves non-asymptotic, instance-dependent sample complexity. CAESAR provides new results and valuable insights to the existing literature while sharing several advantages compared to existing ap- proaches (see Section 5).
We introduce the technique of coarse estimation and demonstrate its effectiveness in solving the multiple- policy evaluation problem. We believe this technique has potential applications beyond the scope of this work.
We propose an algorithm, IDES, as a subroutine of CAESAR to accurately estimate the marginal impor- tance ratios by minimizing a carefully designed step- wise loss function. IDES is a non-trivial extension of DualDICE to finite-horizon Markov Decision Pro- cesses (MDPs).
1. Build coarse estimators of the policy visitation distri- butions and use them to compute mixture policy that achieves a low visitation ratio with respect to all K policies to evaluate.
2. Sample from this approximately optimal mixture pol- icy and use these to construct mean reward estimators for all K' policies by importance weighting.
We propose a novel notion termed f-distance along with an algorithm MARCH, which achieves coarse estimation of the visitation distribution for all determin- istic policies, with a sample complexity scales polyno- mially in parameters such as the size of the state and action spaces, despite the fact of exponential number of deterministic policies.
Coarse estimation refers estimating a target value up to constant multiplicative accuracy (see Definition 4.1). We show that coarse estimation of the visitation distributions can be achieved at cost that scales linearly, instead of quadratically with the inverse of the accuracy parameter. This ensures that the sample cost in the first phase of our algorithm is of lower order and can therefore be considered negligible (see Section 4.1). We then show that estimat- ing the policy visitation distributions up to multiplicative accuracy is enough to find approximately optimal be- havior distribution that minimizes the maximum visitation ratio among all policies to estimate (see Section 4.2). In
2. Related Work
There a rich family of off-policy estimators for policy evaluation (Liu et al., 2018; Jiang and Li, 2016: Dai et al., 2020; Feng al., 2021; Jiang and Huang, 2020). But none of them is effective in our setting. Importance-sampling is a simple and popular method for off-polic evaluation but suffers exponential variance in the horizon (Liu et al., 2018). Marginalized importance-samplin posed to get rid of the exponential variance. However, ex- isting works all focus on function approximations which
has been pro-
We say offline here to emphasize that the final evaluation is conducted in an offline fashion rather than implying there is interaction with the environment.
2

---

Multiple-policy Evaluation via Density Estimation
only produce approximately correct estimators (Dai al., 2020) are designed for the infinite-horizon case (Feng et al., 2021). The doubly robust estimator (Jiang and Li, 2016; Hanna et al., 2017; Farajtabar et al., 2018) also solves the exponential variance problem, but no finite sample re- sult is available. Our algorithm is based on marginalized importance-sampling and addresses the above limitations in the sense that it provides non-asym con-asymptotic sample complex- ity results and works for finite-horizon Markov Decision Processes (MDPs).
to the specific tasks. Moreover, our coarse estimation re- sults are based on simple concentration inequalities and the multiplicative constant can be any value, leading to more flexible and elegant formulations.
Our algorithm also uses some techniques modified from other works which we summarize here. DuaIDICE is a technique for estimating distribution ratios by minimizing some loss functions proposed by (Nachum et al., 2019). We build on this idea and make some modifications to meet the need in our setting. Besides, we utilize stochastic gradient descent algorithms and their convergence rate for strongly-conver and smooth functions from the optimiza- tion literature (Hazan and Kale, 2011). Finally, we adopt the Median of Means estimator (Minsker, 2023) to convert in-expectation results high-probability results.
Another popular estimator is called model-based estima- tor, which evaluates the policy by estimating the transition function of the environment (Dann et al., 2019; Zanette and Brunskill, 2019). Yin and Wang (2020) provide a similar sample complexity to our results. However, there are some significant differences between their result and ours. First, our sampling distribution; calculated based on the coarse distribution estimator, is optimal. Second, our sample com- plexity is non-asymptotic while their result is asymptotic. Third, the true distributions appearing in our sample com- plexity can be replaced by known distribution estimators without inducing additional costs, that is, we can provide a known sample complexity while their result is always un- known since we do not know the true visitation distributions of target policies.
3. Preliminaries
Notations We denote the set 2, 21,2,...,NN
N] by [N]. E.| de-
(X, Jm represents the set i notes the expectation over the trajectories induced by policy π while E represents the expectation over the trajectories sampled from distribution μ.. Ó()) hides constants, logarith- mie and lower-order terms. We use V[X] to represent the variance of random variable X. Ilae is the set of all deter- ministic policies and conv(X') represents the convex hull of the set X. If not explicitly specified, Vs, a, h, k stands for Vs E S,a a E A, h E [H] k E [K]. Finally, Median(.) denotes the median of a set of numbers.
The work that most aligns with ours is Dann et al. (2023), which proposed an on-policy algorithm based on the idea of trajectory synthesis. The authors propose the first instance- dependent sample complexity analysis of the multiple- policy evaluation problem. Different from their work, our algorithm uses off-policy evaluation based on importance- weighting and achieves better sample complexity with simpler techniques and analysis. Concurrently, Russo and Pacchiano (2025) studied the multiple-policy evaluation problem in discounted settings from the lower bound per- spective.
Reinforcement learning framework We consider episodic tabular Markov Decision Processes (MDPs) defined by a tuple {S, H, (Pr) (ra) v/), where S and A represent the state and action spaces, respectively, with S and denoting the respective cardinality of these sets. H is the horizon which defines the number of steps the agent can take before the end of an episode. (r.--s, a) E AS is the transition function which represents the probability of transitioning to the next state if the agent takes action a at state s. And rn a) is the reward function, accounting for the reward the agent can collect by taking action a at state s. In this work, we assume that the reward is deterministic and bounded rn (s, a) E [o, 1]. which is consistent with prior work (Dann al., 2023). We denote the initial state distribution by AS.
Analogous to two-stage pipeline, Amortila et al. (2024) proposed an exploration objective for downstream reward maximization, similar to our goal of computing an optimal sampling distribution. However, our approximate objective, based on coarse estimation is easier to solve, which is a significant contribution while they need layer-by-layer in- duction. They also introduced a loss function to estimate ratios, similar to how estimate the importance densi- ties. However, our ratios are defined differently from theirs which require distinct techniques.
A policy क = {mx ) is a mapping from the state space to the probability distribution space over the action space. TA (als) denotes the probability of taking action a at state s and step h. The value function V (s) of a policy is the expected total reward the agent can receive by starting from step h, state s, and following the policy म, i.e., V (s) E, I>" ri]s]. The performance J(x) of a policy л is defined as the expected total reward the agent can obtain.
Several existing works have utilized estimates of visitation distributions up to multiplicative constant accuracy (Zhang and Zanette, 2023; Li et al., 2023). We formally formulate the technique of coarse estimation and present clean results that are ready to use in general scenarios while the existing results have more additional complex terms and are limited
3

---

Figure 1. The scheme of CAESAR. In Phase we collect (1/cc) trajectories for each target policies .i,..., TK and obtain coarse estimators of their visitation distributions d'1, ,...,." "..., Based the coarse estimator, can generate approximately optimal sampling dataset which has good coverage over the visitations of target policies. In Phase II, we sample data from the approximately optimal dataset and leverage the coarse estimators from Phase to perform importance density estimation for each target policies Multiple-policy Evaluation via Density Estimation
Phase
Phase II
1 kk
Estimation
2= ,,, n
IDES
IS-wiights
W 11
W T
Environment
Approximately optimal dataset
n t PTk
by implementing IDES.. With the estimated importance density úh ..... =x, we can output the final performance evaluators 1/51 ..... fA
By the definition of the value function, we have J(x) = ViT sl ~ v). For simplicity, in the following context, we use Vi to denote VP* (s|s ~~ v).
coarsely estimate the visitation distributions of target poli- cies at the cost of a lower-order sample complexity. Based on these coarse distribution estimators, we can build an approximately optimal sampling distribution by solving a convex optimization problem. Finally, utilize the idea of DuaIDICE (Nachum al., 2019) with some modifications to estimate the importance -ereihhtt- ratio.
The state visitation distribution (s) of policy æ repre- sents the probability of reaching state at step h if the agent starts from state sampled from the initial state distribution // at step I = 1 and follows policy π subse- quently, i.e., (s) = P(s. = s|$1 ~ v, v, Similarly, the state-action visitation distribution d7, a) is defined as (s, a) = dz (5) (als). Based on the definition of the vis- itation distribution, the performance policy и can also be expressed J(x) = VI" E Σea di (s, (s)
4.1. Coarse estimation of visitation distributions
It is well known that to estimate quantity up to e-accuracy, approximately Ō(22) samples are needed, e.g., as indicated by Hoeflding's 's inequality. However, it does not serve our need since it is too expensive terms of sample complexity. In other words, if we can estimate the visitations of target policies with e-accuracy, the value functions derived from these estimated visitations will already be sufficiently accu- rate. At the same time, designing sampling distribution that ensures good coverage of the target policy set requires certain knowledge about the visitations of the target policies. To that end, we introduce the concept of coarse estimators which defined below.
Multiple-policy evaluation problem setup In multiple- policy evaluation, we are given a set of known policies { and pair of factors {e, d). The objective is to evaluate the performance of these given policies such that with probability at least d, Yi E {** K J IVT -V < where V is the performance estimator.
4. Main Results and Algorithm
Definition 4.1 (Coarse Estimator). Given an accuracy c, estimator å is coarse estimator to the true value if it satisfies | x| max(e, |zl/c] where c constant.
In this section, we introduce our main algorithm, CAESAR step-by-step and present the main results. CAESAR is sketched out in Algorithm 2 as well as in Figure 1 for easy reference. We try to build single sampling dataset with good coverage over target policies, with which we can estimate the performance all target policies simultane- ously using importance weighting. To that end, we first
We next show that coarse estimation of the visitation distri- butions can be achieved by paying sample complexity of just Ō( which much cheaper compared to Ō( And we will show the next section that the coarse estimator pro-

---

Multiple-policy Evaluation via Density Estimation
vides enough information to construct an approximately optimal sampling distribution that minimizes the maximum visitation ratio among all policies to estimate.
d(ss, a) S 5e' is most 5. For simplicity of presentation, we can set di, (s) - (s, a) = 0 if (s, < Finally, we have coarse estimators of the visitations for target policies such that,
be
148
The idea behind the feasibility of computing these coarse es- timators is based on the following lemma which shows that estimating the mean value of a Bernoulli random variable up to constant multiplicative accuracy only requires (
|d] (s. dh (s, Th (s,a) Vs,
(I)
4
samples.
4.2. Approximately optimal sampling distribution
Lemma 4.2. Let Ze be i.i.d. samples Ze iidd Ber(p). Set- ting& t 2 Clog(C/co) for some known constant C > 0, it fol- lows that with probability at least 5, the empirical mean estimator ir- - Zee satisfies, live - pl S max(e, [):
In this section, we validate the claim from the previous section that the coarse estimator provides sufficient informa- tion (i.e., accurate enough) to construct an approximately optimal sampling distribution that minimizes the maximum visitation ratio among all policies to estimate.
Let {(s), a)); az) aa)........ ( )} denote trajectory collected by following policy Then the random variable Zi(h, a) defined below is a Bernoulli random variable
Suppose that we have a dataset with distribution {un from which we can sample trajectories {st, "i, $2 .q.....5 , a1z Ji=1, then we can evaluate the expected total rewards of target policies by importance weighting. Specifically,
such that Zi a) 'Ad Ber(d] ())
Zi 8, a) = =f1 0, otherwise.
=
= s,
1
X k E [K].
(2)
We can construct such random variables for each (h, s, s)). Together with Lemma 4.2, we able to coarsely estimate the visitation distributions of a policy by sampling Ö(!) trajectories.
where X." = > ward gained in trajectory. Note that the above estimators rely unknown quantity dī a), i.e., the true visita- tion distribution. In the next section, we will show how to accurately estimate these iuportance-weighting ratios.
pu(s),ah, Th ai) is the total re-
Proposition 4.3. With number of trajectories n 2
CK log) Ō(2), we can estimate d=² {cr 3
11=1
such that with probability at least 1 -5, 5, Idă (s,
It can be shown that the variance of the value function estimator X² is bounded by (see Appendix A.2),
di. (s, a)) S max(e, oh ((a)), ), Vs, a, h,,k
In Appendix B, we propose an algorithm, MARCH (Multi- policy Approximation via Ratio-based Coarse Handling), which computes coarse estimators of visitation distribu- tions for all deterministic policies with sample complexity Ö(p ())A(H ). This is a significant result since the num- ber of deterministic policies scales exponentially with the size of the state space and horizon. The result is achieved through a novel analysis based on our proposed notion named B disttance. Due to space constraints, we refer read-
H
dh (sh an) (M(sE, an)
Σ E h=1
(3)
We aim identify the optimal sampling distribution by minimizing the variance (3) of the value function estimator across all target policies, resulting in the following convex optimization problem:
arg min max (s, 8.8 (n(s
h E [ (4)
My, Econv (D,,) RE K]
ers to Appendix B for further details.
Before proceeding to the next section, notice that states and actions with low estimated visitation probabilities can be ignored without inducing significant errors based on the following lemma.
We constrain Ns in the convex hull of Dn. = (d) k [K]] since some cases, the optimal μ¹ may not be real- ized by any policy (see Appendix A.3). One can also set Dj [d7 E [lact) which allows any feasible distri- bution, ensuring a globally optimal sampling distribution at the cost of more computations towards solving the opti- mization problem. We denote the optimal solution to (4) as "x = E >k oid.."
Lemma 4.4. Suppose we have an estimator d(ss,) of d(s, a) such that (á(s,a) a) - d(ssa)) S max(c', d(s.a)) }.
If d(s,a) a) 2 5e', then maxfe', d(saa) d(s,a) and if d(s, a) S 5e', then d(s,a) Te.
It is impossible to solve (4) since the true visitations di are unknown to us. Therefore, we utilize the coarse estima- tors obtained in the last section to replace these unknown
Lemma 4.4 tells us if we replace é' by 1484 the error induced by ignoring those state-action pairs which satisfy
5

---

Multiple-policy Evaluation via Density Estimation
distributions which leads to the following approximate opti- mization problem,
Algorithm Importance Density Estimation (IDES)
Input: Horizon H, accuracy e, target policy т, coarse estimator {dī, } {Ag ) and dataset p
(d (s.a)) a))² (s
Define feasible sets (Pa)-= where D)(s,a)
p. = arg min
max MAN (D.) [E[R] 8,0
h E [H] (5)
[0, 2d (8, a)}.
Initialize wh = 0. h 1, l........ H. and set Ho an) 1, (o so, ao) = (sss,, w0 fio = 1.
where Dí- = =d= k E [K]]. We denote the optimal solu- tion (5) by 13 = -E== Ojdj dx." Consequently, our sampling distribution from which trajectories are sampled M Σk= azdh" And based on (1), we also have the relationship.
for h = 1 to H do
Set the iteration number of optimization, nn
Cn H s,a (ala,a)
22 Es (di(eaa)² + Mn- An-1(3.0)
(
where Ch.
is a known constant.
(M,(s,)) (A( ())
for i 1 to n do Sample (f) from pn and 16%-1:00/-11 from P4-1- Calculate gradient g(wh
(6)
4
Finally, we conclude this section by showing 1i, is approxi- mately optimal.
Lemma 4.5. The sampling distribution je is approximately optimal such that,
2 (s,a)
((w,
1(s) 8, ab a)
(n)5,
wn (8/- a 11-1)
(d (s, ())
(d as)
T (als)](sh = 8).
max [E]
max SC
Σ
M (8)
KE(K]
1% (5,
Update wf, = ProjwEDs tuch i- gug -1)r-1)}} ')}. end for Output the estimator úù EE E w/. end for
where C' is a constant and μ²' is the optimal solution to (4).
4.3. Estimation of wiportanne-weigghting ratios
In the previous section, constructed sampling dataset with distribution j", from which we can draw trajecto- ries. The remaining challenge is that estimating the value function using (2) requires knowledge of the importance- weighting ratios. To address this, we introduce an algorithm, IDES, outlined Algorithm I, for estimating these ratios. IDES is inspired by the idea of DualDICE (Nachum al., 2019). In DuaIDICE, they propose the following loss func- tion,
whereas DuaIDICE relies on a variable transformation based on Bellman's 's equation, which is only applicable to infinite- horizon MDPs. Second, IDES employs a step-wise ob- jective function, requiring sequential step-to-step optimiza- tion and analysis. whereas DualDICE formulates a single loss function. Third, although both IDES and DuaIDICE achieve a sample complexity of (CC/²), the value of C in DualDICE's s bound is not sufficiently tight for our purposes, which involve deriving instance- dependded guarantees. In contrast, we offer a precise analysis linking the value of C in IDES to the expected visitation ratios. Lastly, IDES pro- vides high-probabilij results for visitation ratio estimation, whereas DualDICE's 'ss results hold only in expectation.
1 Cs (Tww)= Bs,ana [w² (s, Es,andr [wr(s,a)) ()) (7)
The minimum of (-)) is achieved at w* (s, d" (a.a)
pls.a)
the importance weighting ratio. By applying variable trans- formation based on Bellman's 's equation, they derive final loss function that eliminates the need for on-policy samples in mafinite-horizon MDPs. The amportannce-eighting ratios are then obtained by optimizing this loss function.
Our step-wise loss function of a policy π at each step is defined as,
1 (w) = 2 By
(s)
We extend this approach to finite-horizon MDPs by propos- ing step-wise loss function, which we define below. It is important emphasize that IDES is not trivial exten- sion of DuaIDICE. While IDES adopts the quadratic loss function from DuaIDICE, it applies fundamentally different techniques and analyses.
(5,
wh (s',a') 2 (8 w(s (m)ls)
- E d'a'-
KK or is the sampling distribution, and P = -k= dr is the optimal solution to the approxi- mate optimization problem (5) (see Appendix 4.2). And for
where म7 = ki=l
First, IDES leverages coarse distribution estimators to ad- dress the on-policy limitation of the second term in (7),
6

---

Multiple-policy Evaluation via Density Estimation
notation simplicity, we set (5 0o) 1, Po(sso,, u(5), = 10 =
Algorithm 2 Coarse and Adaptive EStimation with
Approximate Reweighing for Multi-Policy Evaluation (CAESAR)
Although it may appear complex at first glance, it possesses favorable properties that allow us to derive importance- weighting ratios iteratively, as formalized the following two lemmas.
Input: Accuracy e, confidence 6, target policies
{T") Jk=1.
Coarsely estimate visitation distributions of all target poli- cies and get (d k E [K]].
Lemma 4.6, Suppose we have an estimator Wn-1 1 at step h 1 such that,
Solve the approximate optimization problem (5) and con-
struct the dataset ji* Implement IDES (Algorithm 1) to get importance- weighting ratios {w KKm
1h 1h- ( - 17.1(18,)) c,
Σ ph (s,
1 (8,0)
Build the final performance estimator (Vr )== by (9).
then by minimizing the loss function (T(()) at step h to ViVer (wn (s. a))l)) S. we have,
Output: (VT ]
(n a) - (s, 2c.
1. ( Σ 8,0
())))
4.4. Main results
We are now ready to present our main sample complexity re- sult for the multiple-policy evaluation problem, building on the findings from previous sections. Using the importance- weighting ratio estimator
Lemma 4.6 shows that the importance-weighting ratio es- timator from the previous step enables the estimation of the ratio at the current step, introducing only an additive error. Consequently, by optimizing iteratively, we can accu- rately estimate the importance-wiighting ratios at all steps, as formalized in the following lemma.
2g (s.a) we can evaluate the per- Mr, (i,
formance of the target policy n by,
H
(sh. a
Lemma 4.7. Implementing Algorithm I with x² we have the importance density estimator
(n(
aH)
(9)
0z (s.a) such that, (j,(),))
where {8%, of )i is drawn from our approximately optimal sampling distribution P.j.
17 a) D ()
E
Σ 8,0
d (s,
S
c
Vh.
(s)
4H'
The following theorem presents our main results on the sample complexity of CAESAR. We will leave the detailed derivation to Appendix A.8.
(8)
The above result holds in expectation. To obtain a high- probability guarantee, we introduce Median-of-Meanss (MoM) estimator (Minsker, 2023), formalized in the fol- lowing lemma, along with a data-splitting technique. To- gether, these methods enable us to transform (8) into a high-probability result (see Appendix A.8)
Theorem 4.9. Implementing Algorithm Then, with prob- ability least 6, for all target policies, we have that Ii - V S e. And the total number of trajectories sampled is,
H H
(dF (s.a))² 14((s,))
Lemma 4.8. Let z E R and suppose we have stochastic estinator such that Ella zI] S 4. Then, we generate N O (log(1 ())) i.i.d. estimators (i1, $2,...,. and choose 2 MoM- = Median($1 $2.............................. &N), we have with probability at least 1- 5.
n=
max RE[K]
(10)
8,0
where μř, is the optimal solution to (4) (refer to Section 4.2). Furthermore, the above bound still holds if replacing the unknown true visitation distributions {(d=" 1== by the coarse estimators (1d= " which can provide us concrete value of the sample complexity.
8.
1.MOM- z/ c.
Another noteworthy property of our loss function is that it is y-strongly convex and E-smooth where y (s.0)
We provide an instance-dependent result that characterizes the complexity of the multiple-policy evaluation problem based on the overlap of the visitation distributions of the target policies, aligning with intuitions. In the special case where all target policies are identical, i.c., single-policy eval- uation, our sample complexity is O( poly(H))) ), independent of S and A, which is consistent with the result of Monte
minz,a F3 ( = max,,o aa (s,a) From property (6), it
(s.s.a)
follows that y and & are bounded from both sides, as is their ratio E This property plays a crucial role in analyzing the 7/
sampling complexity of the minimization of the loss func- tion via stochastic gradient descent, which we discuss in Appendix A.6.
7

---

Multiple-policy Evaluation via Density Estimation
Carlo estimation. Furthermore, if the target policies are deterministic, we establish an instance-independee up- per bound on our sample complexity, formalized in the following corollary.
p is sufficiently small, the probability of reaching $2,1 is P Pls2.1 E < (1--1) pK.
According to the result (11) by Dann et al. (2023), the sample complexity in this scenario is (
K which depends on K. In contrast, since the visitation distribution at the second layer of all target policies is identical, our result provides a sample complexity of Ō (1) without dependency on K.
Corollary 4.10. If the target policies to be evaluated are deterministic, the sample complexity of CAESAR is always bounded by poiy(1)s*
Corollary 4.10 tells us that with most Ô P
Beyond sample complexity, our work tackles the problem from a different perspective, which complements the exsit- ing results. Our algorithm first constructs an approximately optimal dataset and then uses it to perform offline evaluation. In other words, we extend the offline evaluation framework to multiple-policy setting. In contrast, (Dann et al., 2023) evaluates policies in an online and on-policy manner.
trajectories, by implementing CAESAR, we can evaluate all deterministic policies up to accuracy under any reward which means we can identify an e- optimal policy for any reward. This is consistent with the result in Jin al. (2020), which proposes reward-free exploration algorithm with the same sample complexity of Ô poly(H))
5.2. Near-optimal policy identification
5. Discussions
Besides policy evaluation, CAESAR can also be applied to identify near-optimal policy. Fixing the high-probability factor, we denote the sample complexity of CAESAR by Ö ((5()) ). where II the set of policies to be evaluated and y is the estimation error. We provide simple algo- rithm based on CAESAR in Appendix D that achieves an dependet sample complexity Ö(max,2e ((Il.)) to identify a c optimal policy, where IT = {- V 1/T s 8y). This result is interesting as it offers a different perspective beyond the existing gap-dependent results (Sim- chowitz and Jamieson, 2019; Dann et al., 2021). Further- more, this result be easily extended to the multi-reward setting. Due to space constraints, we leave the detailed discussion to Appendix D.
In this section, first compare results with the existing work (Dann et al., 2023). Additionally, we explore the application of CAESAR to policy identification beyond policy evaluation.
5.1. Comparison with existing result
Dann et al. (2023) proposes an algorithm for multiple-policy evaluation based on the idea of trajectory stitching and achieved an instance-dependent sample complexity,
H 2
δ E
(11)
d (s)
where d))))(s) (s) = max d= (s) and K*h C S x A keeps track of which state-action pairs at step h are visited
6. Conclusion and Future Work
by target policies in their trajectories.
In this work, we consider the problem of multi-policy eval- uation. We propose an algorithm, CAESAR, based on computing an approximately optimal sampling dataset and using the data sampled from it to perform the simultaneous estimation of the policy values. The algorithm consists of three techniques. First, we obtain coarse distribution esti- mators at a lower-order sample cost. Second, based on the coarse estimator, we obtain an approximately optimal sam- pling dataset. Lastly, we propose a step-wise loss function to estimate the importance weighting ratios.
A significant issue with the result by Dann al. (2023) is the presence of the unfavorable 7 (5) which can induce an undesirable dependency on K.
To illustrate this, consider an example of an MDP with two layers: a single initial state $1,1 in the first layer and two terminal states in the second layer $2,1, $2.2. The transition function is the same for all actions, i.e., P($2.1/51,1,0 a) = p and p is sufficiently small. Agents only receive rewards at state $2,1, regardless of the actions they take. Hence, to evaluate the performance of policy under this MDP, it is sufficient to consider only the second layer. Now, suppose we have K target policies to evaluate, where each policy takes different actions at state $1,1 but the same action at any state in the second layer. Since the transition function at state $1.1 is the same for any action, the visitation distribution at state 82 of all target policies is identical. Given that
Beyond the results of this work, there are still some open questions of interest. First, our sample complexity has a dependency on H which is induced by the error propaga- tion in the estimation of the importance weighting ratios. We conjecture a dependency on H² is possible by consid- ering comprehensive loss function instead of step-wise loss functions. Second, considering a reward-dependent
8

---

Multiple-policy Evaluation via Density Estimation
and variance-aware sample complexity is also interesting direction. Third, it is still challenging problem to derive the lower bound for multiple-policy evaluation. Finally, we are interested to see what other uses the research community may find for coarse distribution estimation.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learn- ing. pages 1507-1516. PMLR, 2019.
Christoph Dann, Teodor Vanislavov Marinov, Mchryar Mohri, and Julian Zimmert. Beyond value-function gaps: Improved mistance-dependen regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 1-21-12, 2021.
Acknowledgements
This work was supported in part by funding from the Eric and Wendy Schmidt Center at the Broad Institute of MIT and Harvard, the NSF under grants CCF-2200052 and IIS-
1914792, the ONR under grants N00014-19-1-251 and N00014-21-1-2844, the NIH under grant IULITR001430, the DOE under grant DE-AC02-0SCH1123 the ARPA-E under grant and DE-AR0001282 and the Boston University Kilachand Fund for Integrated Life Science and Engineer- ing.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709. PMLR, 2020.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy eval- uation. In International Conference on Machine Learning, pages 1447-1456. PMLR, 2018.
Impact Statement
This work aims to advance the field of Machine Learning by providing new insights and methodologies for multiple- policy evaluation in reinforcement learning. Our contribu- tions enhance the theoretical understanding of policy eval- uation. While our research has broad implications, we do not identify any specific societal consequences that require particular emphasis at this time.
Yihao Feng, Ziyang Tang, Na Zhang, and Qiang Liu. Non-asymptotic confidence intervals of off-policy eval- uation: Primal and dual bounds. arXiv preprint arXiv:2103.05741, 2021.
Raphael Fonteneau, Susan A Murphy, Louis Wehenkel, and Damien Ernst. Batch mode reinforcement learning based the synthesis of artificial trajectories. Annals of opera- tions research, 208:383-411 2013.
References
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
Josiah P Hanna, Peter Stone, and Scott Niekum. Bootstrap- ping with models: Confidence intervals for off-policy evaluation. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 538- 546, 2017.
Philip Amortila, Dylan Foster, and Akshay Krishna- murthy. Scalable online exploration via coverability. arXiv preprint arXiv:2403.0657/ 2024.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelli- gence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 201
Elad Hazan and Satyen Kale. Beyond the regret minimiza- tion barrier: an optimal algorithm for stochastic strongly- convex optimization. Proceedings of the 24th Annual Conference on Learning Theory, pages 421 421-436. JMLR Workshop and Conference Proceedings, 2011.
Nan Jiang and Jiawei Huang. Minimax value interval for off- policy evaluation and policy optimization. Advances in Neural Information Processing Systems, 33:2747-2758, 2020.
Bo Dai, Ofir Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Coindice: Off-policy confidence interval estimation. Advances in neural infor- mation processing systems, 33:9398 9411, 0019398-9411, 2020. 2020.
Chris Dann, Mohammad Ghavamzadeh, and Teodor V Mari- nov. Multiple-polie high-confidence policy evaluation. In International Conference on Artificial Intelligence and Statistics, pages 9470-9487. PMLR, 2023.
Nan Jiang and Lihong Li. Doubly robust off- value evaluation for reinforcement learning. In International conference on machine learning, pages 652-661. PMLR, 2016.

---

Multiple-policy Evaluation via Density Estimation
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforce- ment learning. In International Conference Machine Learning, pages 4870-4877 PMLR, 2020.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in neural information processing systems, 32, 2019.
Gen Li, Wenhao Zhan, Jason D Lee, Yuejic Chi, and Yuxin Chen. Reward-agnostic fine-tuning: Provable statisti- cal benefits of hybrid reinforcement learning, Advances in Neural Information Processing Systems, 36:55582- 55615, 2023.
Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforce- ment learning. In The Eleventh International Conference on Learning Representations, 2022.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In International Conference Artificial Intelligence and Statistics, pages 3948 3958. PMLR, 2020.
Lihong Li, Rémi Munos, and Csaba Szepesvári. Toward minimax off- off-policy value estimation. Artificial Intelli- gence and Statistics, pages 608-616. PMLR, 2015.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 15567-1775. PMLR, 2021.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou Breaking the curse horizon: frfnite-horizon off off-policy estimation. Advances in neural information processing systems, 31, 2018.
Stanislav Minsker. Efficient median of means estimator. In The Thirty Sixth Annual Conference Learning Theory, pages 3923-5933. PMLR, 2023.
Andrea Zanette and Emma Brunskill. Tighter problem- dependent regret bounds in reinforcement learning with- out domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312 PMLR, 2019.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in neural information processing systems, 32, 2019.
Ruiqi Zhang and Andrea Zanette. Policy finetuning in re- inforcement learning via design of experiments using offline data. Advances in Neural Information Processing Systems, 36:59933-5999 2023.
Alessio Russo and Aldo Pacchiano. Adaptive exploration for multi-reward multi-policy evaluation. arXiv preprint arXiv:2502.02516. 2025.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforce- ment learning with function approximation. Advances in neural information processing systems, 12, 1999.
Devinder Thapa, In-Sung Jung, and Gi-Nam Wang. Agent based decision support system using reinforcement lear- ing under emergency circumstances. In Advances in Nat- ural Computation: First International Conference, ICNC 2005, Changsha, China, August 27-29, 2005, Proceed- ings, Part 1, pages 888-892, Springer, 2005.
Ruosong Wang, Simon S Du, Lin F Yang, and Sham M Kakade. Is long horizon reinforcement learning more difficult than short horizon reinforcement learning? arXiv preprint arXiv:2005. 00527, 2020.
10

---

Multiple-policy Evaluation via Density Estimation
A. Proof of theorems and lemmas in Section 4
A.1. Proof of Lemma 4.2
Our results relies on the following variant of Bernstein incquality for martingales, or Freedman's 's incquality (Freedman, 1975), as stated in e.g., (Agarwal et al., 2014; Beygelzimer et al., 2011).
Lemma A.1 (Simplified Freedman's 's inequality). Let XI...,, be a bounded martingale difference sequence with Xxl & R. For any 8' E (0, 1). and 17 E (0, 1/R), with probability at least 1 8',
T 1
Σ EX + log(1/8')
T
X
(12)
E=1
where [E[-]] is the conditional expectation induced by conditioning on X1, ,
Lemma A.2 (Anytime Freedman). Let {X be bounded martingale difference sequence with [X,] S f all E N. For any 8' E (0,1) 1), and E 1))), there exists universal constant C > 0 such that for all & E N simultaneously with probability at least - 8
8
Ex[x + C'lo((t88)
Xisn Σ
(13)
Em1
where Ex|-] is the conditional expectation induced by conditioning on X1, Xt-1.
Proof. This result follows from Lemma A.1. Fix a time-indes t and define 8, 12 Lemma A.1 implies that with
probability at least 1 - 6,
X2] + 10g(1/5))
Xx S 7
Ee
t=1
A union bound implies that with probability at least
Ela 8z 2 - 8'
log( 1262/8")
X
<
Er
8=1
1=1
(6)
C' Cologt//8
2 1)
[
17
E=1
holds for all E N. Inequality (i) holds because log(1212/85) /8) = O (log(18")).
Proposition A.3. Let 8' E 1), 3 E (0, 1] and Z ... Zr be an adapted sequence satisfying 0 0 Z: S B for all e N.
There is a universal constant C" > 0 such that,
Σ [d 2BC log (T
2BC log (T/8')
(1-3)
Z4 (1 3) Σ E, [Z.]
with probability at least 1 28' simultaneously for all T N.
Proof. Consider the martingale difference sequence X, Z; E, [z]. Notice that [X, < B. Using the inequality of
We will use this notation to denote conditional expectations throughout this work.

---

Multiple-policy Evaluation via Density Estimation
Lemma A.2 obtain that for all 1) E (0, 1/B3)
Clog(t/8')
X
S 17
Ee [X]] +
"
1=1
A=1
(1)
Er Er|Za] + C'log(t/8')
Bn
for all E N with probability least 1 8'. Inequality (i) holds because Ex[x?]
BBEIJA, s 22% for all e N.
Setting 17 2
e and substituting Σ/= (== Xe Σi= Ze E2 [Z]]
E. + 2B Clo(((()))))
Σ Ze S (1 3)
(14)
B
E=1
with probability at least 8' Now consider the martingale difference sequence X E[Z,] Zi and notice that [X]] s B². Using the inequality of Lemma A.2 we obtain for all 1) (0, 1/B²,
Eg [x) + C log(t//8)
Σ X
17
t=1
C Clog((/88)
$ Bm
By +
1
A Setting 7 2/22
and substituting Eis X = Eizn E[Zz]
Ze we have,
2 Clo((//))
(1- Σ E 7 Σ
7x
(15)
B
8=1
with probability at least 8'. Combining Equations 14 and 15 and using a union bound yields the desired result.
Let the Ze be i..dd samples Ze Lidd Ber(p). The empirical mean estimator, P. = E Ze satisfies,
2C' log(t/8")
2C" log(t/8")
(1 - B)p
p. S (1 + 3)p +
31
Bt
8C' log(t/8')
with probability at least - 28' for E N where C² > 0 a (known) universal constant. Given > 0 set >
Be
(notice the dependence of t on the RHS this can be achieved by setting / > Clog(C/Be6") for some (known) universal fc
constant C' > 0).
In this case observe that,
(1- 1-8 (1+ 3)p + c/8.
Setting 3 = 1/8,
7p/8- S < 9p/8 + t/88
so that.
p- D. S p/8 + t/8,
and
i - p < p/8 + e/8,
which implies
Pr pp s p/8 c/8 s 2 2max(p/8.c/8) = max(p/4,c/))
12

---

Multiple-policy Evaluation via Density Estimation
A.2. Derivation of the optimal sampling distribution Our performance estimator is,
H
dh (sh og) r ab), & E [K].
VI
Nh ( 4/)
Denote Ei=1 dh (s1.a%) (a()) estimator is bounded by,
nh (sh. ai)) by X,. And for simplicity, denote (( ai Jape by Ey, the variance of
27
H
dh (sh, ai) Pe ( aih)
E [ E,
I' (o ahh))
27
di (sh, agr) Un(s) ag))
$ E,
rn rh(s anh)
di (sh aih) (n app)
S B
H
11
di (sh, (s aph)
H
E
The first inequality holds by Cauchy Schwarz inequality. The second incquality holds due to the assumption (s, [0, 1].
dh ( [
Denote Σ Bug²
by Pu.k. Applying Bernstein's inequality, we have that with probability at least 1 -
and n samples, holds,
2H Pu,k log(1/8)
2M, log(1/8)
1²T" - VI
n
3n
d (an an) an) pa (n)
where M2 max,,
Ex=1
rh (sn, an).
To achieve an accuracy of evaluation, we need samples,
8H Pa log(1/6)
4M, log(1/6)
Ky.k
22
3e
Take the union bound over all target policies,
8. max Pa.k log (og(K/8)
4M log (K/)
ny v
2
3E
where M ma Ma-
We define the optimal sampling distribution 1² as the minimizing the higher order sample complexity,
ax (s,a)
14, arg min max Eyet (e.a)
PA
KE[K]
(an" (s,
arg min max
I,..,,
Ps.
KE[K]
8,8
a)(8,a)
13

---

Multiple-policy Evaluation via Density Estimation
A.3. An example of unrealizable optimal sampling distribution
Here, we give an example to illustrate the assertation that in some cases, the optimal sampling distribution cannot be realized by any policy.
Consider such a MDP with two layers, in the first layer, there is single initial state $1,1, in the second layer, there are two states 2, $2,2. The transition function at state $1,1 is identical for any action, F( 1 a) = 2 a) =
Hence, for any policy, the only realizable state visitation distribution at the second layer is (2( = d2 (02,2) = 2
Suppose the target policies take K 2 2 different actions at state $2,1 while take the same action at state $2.2.
By solving the optimization problem, have the optimal sampling distribution the second layer,
K² 1 K2 (2
1
15211
1+ K2
which is clearly not realizable by any policy.
A.4. Proof of Lemma 4.5
By property (1) and (6), we have d (8,a) S (s, S (s,
(s.a) and ()) (7 (0, a). Hence,
(d) (s,a))
25
(s,a)) (,
max KE[K]
(7)
12 kE[K
Remember μ² is of the form k==1 ard" Let μt be K feasible set Dr.- {dī²" k E [K]]. Since ji" is the optimal solution to the approximate optimization problem (5), we have,
agd Then we have |p' μ01 S max(e, # and μ² is in the
(dR (s. (s,
(oT (s, as)
25
(dF (s, a)) (s))
max AHE |E[K]
max KE[K]
max
(s,
(s,
12
KE(K]
5,0
The second inequality again based on the property of coarse estimators. Together, we have,
(as (s.
(d (8, ())
max KE(K]
max SC
Σ
(7)
KE[K] 8,0
A.5. Proof of Lemma 4.6
Proof. The gradient of (T[ (w) is.
Va(s,a ( (w) = (n(s,a) a) a)(ssa) u(s,a)=
Σ (s (()s))))())))((() (als)) wn (n_1('',a') a²) s'.a'
in- a')
Suppose by some SGD algorithm, we can converge to point úy such that the gradient of the loss function is less than e,
pn(ss a) (s, a) (s)(),))
Σ d' ( wn (8',aa) 8'.a'
(+m))) Σ
Sc.
p 1 a²)
14

---

Multiple-policy Evaluation via Density Estimation
By decomposing,
An(s,
10 (3, - - [(nls(( ((((s)) ")-r(s,,a))
(s)
('))
s'aa'
()((,a)
in-1 a')) (') "n-1(s',a)
w/ ()) - (s) + ds
Σ
(n(s,a)
-n-1(s',
s',a'
ia(s,
Wb (3)( - (3,
(T(,aa) - (ilaaa---nnilee id ((s))ss,')=xaap (')x(als)
wh- wh-1 154-
(s a)
i4-1 (8', a²)
8/.a'
jn(ssaa) a) ()(
d% (s)
a))
P(s|s', a (alss (h'- -mn-1(s',a)) wh wn-1(s',a))
p (
Hence, we have,
Σ (n(s,a) (n(s,a) ())
(8)
( d') - a²) Wh (6', (o' 1 a²)
S +
Σ
Σ
8,0
8'a'
dr 1 (s', a') f d)) w/ ( a²)
< c Σ
1 a')
,''"'
< 26.
A.6. Proof of Lemma 4.7
(s.a))) Proof. The minimum wf of the loss function (w) is (s,aa) property of the coarse distribution estimator, we have,
Jos (s.0) (s, a) if th-1 achieves optimum. By the
(7 uun (s a)
3 (s.
5 jun (s 3 - (s.a).
w a)
as)
(n a)
We can define a feasible set for the optimization problem, i.c. a) [0, Dn(s a)), Ds (d)
Next, we analyse the variance of the stochastic gradient. We denote the stochastic gradient as gn (w), {st .f..... sn an ... sy. a'y} trajectory sampled from pi=-1
trajectory sampled from jún and {s/, af..........5
(w, w(s.a) a) T(s), = s a) (5 0g
(ala))[(s) =).
(s)
Pn-1 (5-1(5__1,,__1
The variance bound becomes
(m) u(s.a) 2
)²
(s, 2 [b ( ( a)
([g] s Bllla(w))l91
+ (),-1(s,
An(s,
8,0
(dT(s, a)}
(d (8, (8,
o
Σ
(16)
1 a)
8.a
15

---

Multiple-policy Evaluation via Density Estimation
where the last inequality is due to the bounded feasible set for and the property of coarse distribution estimator ju (s, a) La as.a).
Based on the error propagation lemma 4.6, if we can achieve ( S TH from step h = 1 to step h = H,, then we have,
Σ (s) (s, ( (n(3,a)) a)
a)
d)(s,a) - 411
vh 1,2..... H,
which can enable us build the final estimator of the performance of policy with at most error c.
By the property smoothness, to achieve ( S Tæfh, we need to achieve (10)) - 07 (ww)) S 325 where & the smoothness factor, because,
(Tx))l (E() (wf)) S 16/44
Lemma A.4. For X- strongly conver loss function (w) satisfying ||w*|| S D for some known D, there exists stochastic gradient descent algorithm that can output v after T iterations such that,
2G
E[ - -(w")] X(T +1)
where G is the variance bound of the stochastic gradient.
Invoke the convergence rate for strongly-conver and smooth loss functions, i.e. Lemma A.4, we have that the number of samples needed to achieve f7 (mm) - 0% (wx) S 325H* is,
n
We have shown in Section 4.3 that < 5 this nice property helps us to get rid of the undesired ratio of the smoothness of the original loss function (7) which can be extremely bad. factor and the strongly-convexity factor, i.e. min.,. M(s,a Replacing G by our variance bound (16), we have,
3. a(s.a)
( H1
(s)
(d (s.))²
pn ( ))
n
0 o
Σ 8,0 (n)
For each step h, we need the above number trajectories, sum over h, we have the total sample complexity,
H 2
(d)(s,
(s)(s,))
8.a
To evaluate policies, we need trajectories,
H1
(d (s, a))²
n
max KE[K]
(s)
8,0
A.7. Proof of Lemma 4.8
Proof. By Markov's inequality, we have,
Bil ull
1
P( pl 22)
4
16

---

Multiple-policy Evaluation via Density Estimation
The event that liMOM belongs to the event where more than half estimators iú, outside of the desired range live > e, hence, have,
P(liasoos - ml > () S
T(AA - 14
N > >)>
2)
Denote I(A4 - 14 > c) by Z3 and E[Z,] = p.
N
P(JAMOM - x]
P
Zi 2 2
1=1
1 N
P( Σ
-) 22 -())
24 -
1
N
1=1
- e 2
Se v
where the first inequality holds by Hooffding's inequality and the second inequality holds due to p S 1. Set 8 e- we have, with N O(log(1/)) with probability least 1 - 5, it holds JĀMOM
fa] S e.
A.8. Proof of Theorem 4.9
Here, we explain how Theorem 4.9 is derived. We first show how the Median-of-Means (MoM) estimator and data splitting technique can conveniently convert Lemma 4.7 a version holds with high probability.
For step h, Algorithm can output solution wh such that E[e ply Lemma 4.8 on our algorithm which means that we can run the algorithm for N = O (log(1/6)) times. Hence, we will get N solutions {10,,1, 2h,2..... J. Set WM.MoM as the solution such that (Wp = holds
(,()) S
2² We can ap- 325H4
Median (1) f7 ((p,,))..... 2% (1). Based on Lemma 4.8, we have that with probability at least eg Moa, f (wx)) I 32SH*- With a little abuse of notation, we just denote MMM by üy in the following content.
Now we are ready to estimate the total expected rewards of target policies, With the importance weighting ratio estimator Mo (s.a) from Algorithm I, we can estimate the performance of policy x²,
(s.a)
Wh (5), al)) (sh, at,,,
(17)
Pun (s), a
where {s), Ji is sampled from pi..
Lemma A.S. With samples ò 0 [1 > maxke[k] Ex,
(dr" (s,a))2 (x(s,a)
we have with probability at least 8,
hm
IVT" VP 2, & e [K].
Proof. First, we can decompose the error IVT" VT 144² - BBiT" + B(VT"
VT E..o (d.t (s.a))²
5 187+
EEVT ] +
1E[ - Then, by Bernstein's 's inequality, with samples = Ô H2 E"
h= maxKe[K]
Aa(s,a)
we have,
1V7** - 1| 4. Based Lemma 4.7, we have, [E[(T"] VT S
Remember that in Section 4. we ignore those states and actions with low estimated visitation distribution for each target policy which induce at most & error. Combined with Lemma A.5, our estimator Vi*" finally achieves that with probability at least 1 - 6, Vir" vT < k E [K].
And for sample complexity. in our algorithm, we need to sample data in three procedures. First, for the coarse estimation of the visitation distribution, we need O( samples. Second, to estimate the importanne-weiihhing ratio, we need
17

---

Multiple-policy Evaluation via Density Estimation
samples θ
25 Ei= maxke[K] Es,a
[dh (s.a))²
Last, to build the final performance estimator (9), we need samples
Ph (f(a
H2
(dr. (s.a))² maxte[k] Ean (o(s,))
Therefore, the total trajectories needed,
h-
H
(d) (d) (s. a))²
[E[K]
RE
(8,
Moreover, notice that,
(d
(s,
(d) (s)
25
(d) (s. a))²
max KE[
(s,
max kEIK]
(s,
16
M (5,
(18)
8,0
where J is the optimal solution of the optimization problem (4), the first inequality holds due to ju is the minimum of the approximate optimization problem (5) and the second inequality holds due to di (s, a) R (s, a). Based on (18), we can substitute the coarse distribution estimator in the sample complexity bound by the exact one,
H
(d (s, a))² (8,aa)
n Ō
max KE(K]
A.9. Proof of Corollary 4.10
Let the sampling distribution 11, be 5A and 24 is a feasible solution, we have vh E H
1 Σ s.a df where us.a arg maxke(K] d% (s.u). Since M is the optimal solution
(d (s, as)
(dR (s. (8,
Σ
max RE
I max
())
kE[K] 5,
8.0
S SAA
Notice that there is a logarithm term log( K.) hidden in Ô notation. Remember K is the number of target policies. If they are deterministic, then K is bounded by ASH which leads to log( K) < SH log A).
Together, we have the sample complexity bounded by Ô poly(11)ss*)
18

---

Multiple-policy Evaluation via Density Estimation
B. Lower order coarse estimation
Algorithm 3 Multi-policy Approximation via Ratio-based Coarse Handling (MARCH)
Input: Horizon H, accuracy policy
Coarsely estimate d1 such that dist (d1,d1) d1) S where / 1 for h to H do
a)l S maxfé', pn(s, a)}, where e'= 2H and e 1. Coarsely estimate μa such that (s,
2. Sample {+), // (h+1)== from pa-
3. Estimate (s, a) by dst1(s, 1 Ei= I(s) =s) 2)) a/.)-
end for Output: {dr
In this section, first provide our algorithm MARCH for coarse estimation of all the deterministic policies and then conduct an analysis on its sample complexity.
MARCH is based on the algorithm EULER proposed by Zanette and Brunskill (2019).
Lemma B.1 (Theorem 3.3 Jin et al. (2020)), Based on EULER, with sample complexity Ö (.) we can construct
policy cover which generates a dataset with the distribution such that, with probability if d (s) 2 Sx then,
maz (s.a) a)
[n(3,00 a) 2
1:
(19)
2HSA
where draa (8) max, (s), dn (s,a) max, d7 as)
With this dataset, estimate the visitation distribution of deterministic policies by step-to-step importance weighting.
d (8, Σ Msh+t s).nn(sh.
where (sh, a + 1 are sampled from y and wn a) dr.ssa))
Pa (e.a)
We state that MARCH can coarsely estimate the visitation distributions all the deterministic policies by just paying a lower-order sample complexity which is formalized in the following theorem.
Theorem B.2. Implement Algorithm 3 with the number of trajectories Ö( (ol ), with probability least 1 5. it holds that for any deterministic policy ı,
d) S maxfe, (s a)
}. S, [H].
4
where d' is the distribution estimator.
Proof. Our analysis is based a notion of distance defined in the following.
Definition B.3 (i-distance). For x. y 2 0, we define the distannce as,
dist (z, v) = min |ar - y)-
aE
Correspondingly, for x, y E R"
dist (x, y) = Σ disl (r., y:).
Based on its definition, we show in the following lemma that distance has some properties.
19

---

Multiple-policy Evaluation via Density Estimation
Lemma B.4. The B- distance possesses the following properties for (x, Us 2, 2 0):
1. dist@ (yar, ydisst (x.
(20)
2. dist (I1 + +22, 9/1 + 1222 - dist (11, v1) + dist (x2, (2);
(21)
3. dist R2 (x, S dist (x, B2 + dist (y. 2).
(22)
Proof. See Appendix C.1.
The following lemma shows that if we can control the 3-distance between ., ar then we can show & achieves the coarse estimation of x.
Lemma B.5, Suppose dist +.8 (x. y) S c, then it holds that,
B 1 yl By + (1 1 g) s 22max
B )e, By)
Proof. See Appendix C.2.
The logic of the analysis is to show the 3-distance between d, and d, can be bounded at each layer by induction. Then by Lemma B.5, we show {dr [d achieves coarse estimation.
Suppose at layer h, we have du such that dist(! dx) dr) cn where B 1. For notation simplicity, omit the superscript и. The analysis holds for any policy.
We use importance weighting to estimate dr+1.
dnt1(s,0) a)
1 =-
Σ
M(sh+1 ()
11
where wn (8, a) Ar (s.a)
(s,a)
We also denote,
1)mrn d1+1(s,a) = E( 11 [1(h+1 = =s)un (sh. an)].
By (22) Lemma B.4, we have,
dist(1+0)*+2 (dr+1, s (is)(1+0) do+1) + 8y++1 + dist
(dx+1, dx+11
(23)
Next, show how can bound these two terms (A) and (B). Note that for (s, h) where dgaa < 5 the induced 3-distance error is at most Therefore, we can just discuss state-action pairs which satisfy Lemma B.1.
Bound of (A) We first show the following lemma tells us that the importance weighting is upper-bounded.
Lemma B.6. Based on the definition of μ. the importance weighting is upper bounded,
a)) whe (h a) (n(s,a) a)
(s) $ 2HSA
< 2HSA
d mmaz (s,a)
Hence, we can clip úù (s, (s,a) a) at 2HSA such that wn a) 5 2HSA
Let's define the random variable Z (s, T(sh+1 8)wh (8h, an), then ( = Er (8, a). Since wn (sh, as) is bounded by Lemma B.6, have,
VlZ (s, a)] 5 El 1 a) 2214
20

---

Multiple-policy Evaluation via Density Estimation
By Berstein's 's inequality, have with probability at least 1-d,
2V 7 2 (8, (1g()
2HS log(1/0)
(d,+1(8,0) a) (s,
+
n
3n
AH log(1/6)
2HS A log(1/6)
3n
to achieve the estimation accuracy |du+1(s, a) - B|dn+1(s,a)ll s maxfe, Elda+1 a)l}, we need samples
HSA
Based on the above analysis, we can achieve,
S maxfé', & (s
the cost of samples Ô
HSA 30
We now show dist + (dn+1, dn+1) S S'''. We discuss it in two cases,
1. |dh+ (s, a), dz+1 a) <
(24)
8
2. Idn+ (s, dn+ (8, a)l -
2 dn+1(s,a).
(25)
For those (s, a) which satisfies (25), since
8 2, 2, [ 143 1 + B]. by the definition of disttance we have,
dist * dxt1 a)) 0.
(26)
For other (s, a) which satisfies (24), we have,
dist +8 (d u), d S [dh+1(s, a), ( a)l S e'.
Since there are at most SA state-action pairs, the error in the second case is at most SAe'. Combine these two cases, we have,
dist ( (d++),)n+1) S SAC'
By setting e L.
SA. we have,
(A) = dist (dh+1, ( gy++1 s (11+3)) gghht
(27)
and the sample complexity is δ (HSA)²)
Bound of (B) Next show how to bound term (B). Denote un (8, a)
da(s,a) (n(aa)
by dn (s, a), we have,
(B) dist(1 (diti, dn+1)
Σ dist (1 (e)
Σ dist (1)
(l
8,a
s'
x Σ
(+
(s, d' (d, d'). Ph Ph (s. als (s'ss'')))
s,a 8'.0'
-Σ
PR (s, als', (1))) (da(s', d'), da(s',0) aa))
8'
(1 (dn, da),
21

---

Multiple-policy Evaluation via Density Estimation
where the first two equality holds by definition, the inequality holds by (21) in Lemma B.4, the third equality holds by (20) in Lemma B.4 and the last holds by En,a Ph (s, als' a') 1.
Now analyse dist(1+8)**) (dn,dh).
dn(s,a) da(o,a), in(ss p)(s,a)
dist( (dh, dn)
Emn(s, (()ss
8,a
By coarse estimation, we have ())(s, - Mh a)l I maxfc e pn(s,a)). Similarly, we discuss it in two cases,
1. us a)l S t',
(28)
2. (A a), (h S (n(s,a).
(29)
For those (s,a) which satisfies (28), by Lemma B.6, we have,
dist (1+)4+1 (s,,a) dn(s,a),
(s) (n())a) 1 ds(s,a) dx(s,a)
(s, (n(saa) S 2HSA
Hence, we have,
dn(s,a) dn(s,a)
dist(1-B)*+)
(dn
= (s, ())sst
(s( a) (s
2HSAe
2HS
c
where the last inequality holds by c. (. a) s Next, For those (s, a) which satisfies (29), we have,
(1 c) a)
pn(s,a) S (1+c) c)
(nn(s,a)
Set c 2. since
2. 1- 2] <14p: 1 + $). by definition of 3 distance, we have,
1
dist
()) ph(s,a) = 0.
(30)
And assume by induction that dist (19))* (dn(s, dn (s, S en. together with (30) we have,
dāst (1+0 ()) dn(s,a), S 6h
(31)
(n(ssa)) (s)(saa))
Combine the results of two cases together, we have,
(B) dist (1+0)) (dr, dr) S en + 52
Set c' 1 we have,
(B) S ch
(32)
the cost of samples ò = 12
Now we are ready to show the bound of 3-distance at layer h + 1. Plug (27)(32) into (23), we have,
(1 (dh+1, dh+1) s dist(1+0) (dn-1. dn+1)(1 + h++ + dist(1+ (dot1, dh+1)
< (1 h+1 +
22

---

Multiple-policy Evaluation via Density Estimation
Start from dist (d.,, S e, we have,
dist (dn, & he + e h-1
(1 + 3)an.
(33)
Remember that B = H and due to (1 + y S (1 S H), we have,
disl (dn, da) S H(1 + ee))..
(34)
Recall Lemma B.5, and based (34), we have.
(s, d=(s,a)] S 2max + e²),, - (s,n(s,a))
By just paying multiplicative constant, we adjust the constant above needs, i.e. in Theorem B.2.
23

---

Multiple-policy Evaluation via Density Estimation
C. Proof of lemmas in Section B
C.1. Proof of Lemma B.4
Proof. 1. The first property trivial.
dist (yx, = min layz 7v oE(3.9)
min yaz yl aElg
ydist (z. y).
Let aj be such that,
0,34 Wel, 1,2. dist 11+++0(00 (xi,
Notice that a3 = 01
21
+ 02
Za
satisfies ag [ai, arl | [] and a3(2) + x2) = a1 + a222, therefore,
dist (a1 z2, V1 + y2)
min aE(j.0)
|a(21 + x2) 51 1 y/2
|ag(I) +x2) y1 8/2
|aixi - 0242 y1 1/2
la101 51l + 02g22 y2l
dist (x1, v1) + dist (x2 1/2)
The first inequality holds due to the definition of 3 distancce The second inequality is the triangle inequality.
3. We prove the third property through a case-by-case discussion.
(1). Di35
z < = S 1,,33 32x. In this case, the result is trivial, since 91 (x, 2) and B disttance is always non-negative.
(2). B1325 2. Ify E x, then,
(1 S (x, S (y.
We are done.
If I y 3 then dist (z, v) 0, and 2 81822 2 B2y, hence,
dist (y, B2y -1822x dist 2).
We are done.
y > Bı = E ( Bey], then,
dist (2. + dist dist = -2(y - 31x))
= B1
dist 0 B0 (x, z).
We are done.
y > Bix, z 1 Say], then,
dist (x. + dist (v, 32(y 812)
B 32x dis B1 (x, 2).
We are done.
24

---

Multiple-policy Evaluation via Density Estimation
(3). 2 P1
A symmetric analysis can be done by replacing B1, B1 by Bi Bg
1 which gives the result,
(x, - dist 21 (I, y) 32
+ dist (y,2)
Since 82 2 and dist@: (x, 2 O. we have di (x,, y)
1 I dist (xr 3), hence,
Bz
dist 01 (x,, 2) v dist . (a, 3) + disl (y, z);
which concludes the proof.
C.2. Proof of Lemma B.5
Proof. We prove the lemma through case-by-case study.
(1). x S y. If ( v) = O. then x11 + 3) 2 2 x, therefore,
S Bx S By.
If dist (x. y)
0, then dist 29 (z, y) y- - (1 (1+) 3)x, therefore.
b- = - x dist (x, v) + Bx S c Br S c+ By.
(2). y < x. If d = O, then エ+タ S y < therefore.
-- y
x
sv(1+ B)(1
1 1+ B =By.
1
1+3
If dist (sr, y) > 0, then y S S y. Therefore.
2 I+3 S and dist
I+3 y. Moreover, since d v) S have
x - yi = =
dist ++8 (xx y) + (1 1 B )
dist! (I, 3
1 1+9 ,
3
Set +
6 + +By
1 B
8
(1
)c By..
1+
Combine the results above together, we have,
3
3
- 1-yl s By + (1+
1 )) s 21
1 g) ), By).
25

---

Multiple-policy Evaluation via Density Estimation
D. Discussion policy identification
In this section, we discuss on the application of CAESAR to policy identification problem, its instance-dependent sample complexity and some intuitions related the existing gap-dependent results.
We first provide simple algorithm that utilizes CAESAR identify c-optimal policy. The core idea behind the algorithm is can use CAESAR to evaluate all candidate policies up to accuracy, then can eliminate those policies with low estimated performance. By decreasing the evaluation error gradually, we can finally identify near-optimal policy with high probability.
For notation simplicity, fixing the high-probability factor, we denote the sample complexity of CAESAR by @(II) where IT is the set of policies to be evaluated and is the estimation error.
Algorithm 4 Policy Identification based on CAESAR
Input: Alg CAESAR, optimal factor c, candidate policy set IT.
for i = 1 to [log2 (4/e)] do
1. Run CAESAR to evaluate the performance of policies in II up to accuracy 7 = 2
2. Eliminate n² if 3x II, VT' V/r' >> 27, update IT.
end for
Output: Randomly pick x² from II.
Theorem D.1. Implement Algorithm 4, we have that, with probability at least 6, xO e optimal, i.e.
11" VT="
Sc
And the destanne-dependent sample complexity Ó(max,ze
((II.) 7/ where II, = { VI V S 87).
Proof. On the one hand, based on the elimination rule in the algorithm, by running CAESAR with the evaluation error the
optimal policy x² will not be eliminated with probability at least 1-5. Since ma Vi - - S +y- -7) $ 27.
On the other hand, if V - V/² > 4y, then n² will be eliminated with probability at least 1 - 6. Since max - -iT" > V 7 (VT' + +>)= > 2-
Therefore, by running Algorithm 4, the final policy set is not empty and for any policy in this set, it holds, VT - VT S
with probability at least 8. 8.
Next, we analyse the sample complexity of Algorithm 4. Based on above analysis, within every iteration of the algorithm, we have a policy set containing 8 optomal policies, and we use CAESAR to evaluate the performance these policies up to accuracy. By Theorem 4.9, the sample complexity is !III..) Therefore, the overall sample complexity is,
Σ (II.) 72
O(II,) 72c 22
S Ō 0max
This result is quite interesting since it provides another perspective beyond the existing gap-dependent results for policy identification. And these two results have some intuitive relations that may be of interest.
Roughly speaking, to identify an e-optimal policy for an MDP, the gap-dependent regret is described as,
H log K gapa (8 0)
h.s,a
where gapa a) = (s,
The value gap (a a) quantifies how sub-optimal the action is at state s. If the gap is small, is difficult to distinguish and eliminate the sub-optimal action. At the same time, smaller gaps mean that there are more policies with similar
26

---

Multiple-policy Evaluation via Density Estimation
performance the optimal policy, i.e. the policy set II, is larger. Both our result and gap-dependent result capture this intuition. We conjecture there exists quantitative relationship between these two perspectives.
An interesting proposition of Theorem D.1 is to apply the same algorithm to the multi-reward setting. A similar instance-
dependent sample complexity can be achieved O 7f ) with the difference that II contains policies which is 8y-optimal for at least one reward function. This sample complexity captures the intrinsic difficulty of the problem by how similar the near-optimal policies under different rewards are which is consistent with the intuition.
27


Reviews:
[{"review_id": "lskKlV18Jf", "reviewer": "Reviewer_HUdG", "summary": "Propose algorithm for off-policy estimation of a set of $K$ policies. To me, the main idea is to try to improve the linear dependence in $K$ in the naive $K / \\varepsilon^2$ sample complexity (where one simply estimates the visitations of all $K$ policies via Monte Carlo) by collecting samples from a covering distribution, then doing importance-weighted estimation. \n\nThe method is comprised of the following steps (Algorithm 2)\n- Estimate the visitation distributions of each policy up to constant accuracy -- the sample complexity here has a fast statistical rate $\\varepsilon^{-1}$, but I believe it scales as $\\text{poly}(K,S,A)$, see below\n- Compute the \"optimal sampling distribution\" $\\hat\\mu_h^*$, which is essentially the distribution that best covers the estimated distributions of the $K$ policies (in the sense of minimizing variance or expected coverage, aka $\\ell_1$ or $\\ell_2$-coverability ), and collect samples\n- Since the data is now off-policy, importance weights must be computed in order to estimate the policies' values (Algorithm 1)", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks the reviewer for the detailed comments on our work. We are confident that we can solve your concerns well. And we kindly request you to consider increasing your score based on our following elaboration.\n\nOne of your main concerns is about our optimization objective (5):\n> The problem (5) is hard to solve since the inner maximization is non-concave. The sample complexity of solving (5) is unclear.\n\nWe want to correct this comment since it is not true. Our opt objective is a well-formulated convex problem. Let's denote $\\sum_{s,a} \\frac{(\\hat d_h^{\\pi^k}(s,a))^2}{\\mu_h(s,a)}$ by $f_k(\\mu)$. It is trivial that $f_k(\\mu)$ is convex w.r.t $\\mu$, and we know the maximum of a bunch of convex functions is still convex, hence, our objective $\\max_{k\\in[K]} f_k(\\mu)$ is convex. It is ready to be solved by any convex optimization solver which means no sample is needed in solving (5).\n\n> Our opt problem (5) is identical to the one in Amortila et al. (2024).\n\nThe formulation same to the one in Amortila et al. (2024) is (4) instead of (5). (4) is common in many works since it is a standard formulation to describe the coverage property of a dataset. The emphasis of two works is different. We show that an up to constant optimal $\\mu$ is enough in our scenario, hence we use coarse estimators to approximate (4), leading us to (5) which is easy to solve. They want an exact optimizer to (4) which is not straightforward to solve since the true visitation distribution is unknown, and they have to reformulate the problem as a RL problem.\n\n> The sample complexity of coarse estimation for all policies depends on poly(K).\n\nIt is not true. We want to emphasize that our low order term for coarse estimation is always bounded by $\\tilde{O}(poly(H,S,A)/\\epsilon)$ without $poly(K)$ which is a non-trivial contribution. We achieve this by proposing MARCH algorithm along with novel theoretical analysis (utilizing our proposed $\\beta$-distance which possesses lots of nice properties). We briefly discussed it in Line 240-249 (left) in the main page. The detailed content is in Appendix B due to page limits. We will consider updating the paper to emphasize it more in the main page.\n \n> The complexity of estimating $\\hat w$ in IDES is unclear.  \n\nThe sample complexity of IDES is exactly the number of optimization iterations since we are using stochastic gradient. Specifically, in each iteration of optimization, one sample is used to estimate the stochastic gradient. The sample complexity of IDES is same as the one presented in Theorem 4.9, which is also presented in Algorithm 1 where the iteration number $n_h$ is specified.\n\n> Missing related works.\n\nWe appreciate it that you listed these related works which we didn't mention in the current version carelessly due to the massive amount of literature. We will definitely update our paper to include these works as well as the discussions on relations.\n\nWe also want to clarify here that the statement of \"Amortila et al. (2024) is a \"concurrent work\" (L144)\" is not dishonest. Our first draft version was made public in the same period as Amortila et al. (2024). But we understand reviewers have no information on our submission. We will update the expression to make it more appropriate for this submission.\n\n> The novelty of coarse estimation and other derivation techniques is limited.\n\nWe agree that low order sub-procedure is not new in the literature. And thanks for providing these related works. We will definitely include them in the updated version. However, we disagree that the existing results can imply our results on coarse estimation. The Lemma A.22 in Zhang and Zanette (2023) is based on estimation of transition functions, while we directly estimate visitations. And in our result, the constant (i.e. $c$ in Definition 4.1) can be any value (see Appendix A). Eq (45) in Li et al. (2023) is similar to our results,  however, our formulation is much cleaner and more elegant based on simple concentration inequalities while they have more additional complex terms. We formally formulate the technique as coarse estimation in this work and present results that are ready to use in other different scenarios.\n\nWe disagree with the comment that the contribution of our work is just simply combining existing techniques. We presented our contributions clearly in the end of introduction section. Multiple policy evaluation is a very challenging and under-studied problem, and we provide very nice theoretical results for this problem which is a significant step along with many useful side products which have many potential usages.\n\nAgain, we appreciate your efforts on reviewing our paper. Please let us know if our above rebuttal solves your concerns and we are happy to keep discussing if you have more questions.", "claims_and_evidence": "Overall, the analysis seems reasonable. However, some important claims have been misrepresented or are at the very least questionable, which belies the contributions of the paper. I believe that important parts of the analysis of CAESAR have been ignored or abstracted away, that may significantly increase the sample and computational complexity. In particular:\n\n- the sample complexity of coarse visitation estimation for all policies. \n\n- the cost of solving the optimization problem for the sampling distribution in Eq. (5)\n\n- analysis of the weight estimation algorithm (IDES)\n\n\nIn addition, I feel that comparisons to the most relevant works are inaccurate, in particular:\n\n- claimed differences with Amortila et al. (2024), e.g., that CAESAR's objective is easier to solve (L144-154, left)\n\n- the claimed novelty of the coarse visitation estimation results (Section 4.1)\n\n**Sample complexity of estimating visitation for all policies: dependencies on state space $S$ and policies $K$**\n\nThe abstract states that $\\tilde O(\\varepsilon^{-1})$ samples are required to estimate the visitation distributions of all policies, which is required in step 1 of CAESAR (Algorithm 2). Correct me if I'm wrong, but I believe that the sample complexity of step 1 is actually something like \n$$O\\left(\\frac{K S A}{\\varepsilon^{-1}}\\right).$$\nAs we often treat $S$ (and seemingly $K$ here) as being very large (potentially exponentially), this is not a lower-order term to be absorbed into the total sample complexity of CAESAR (Theorem 4.9) without further assumptions. None of this has been clearly stated in the main body nor discussed, and I believe that it warrants extended consideration as it does form a trade-off. \n\nI am also concerned that a large number of additional samples will be required to compute (5); this computed distribution is the foundation of the paper but has been completely abstracted away, see below. \n\n**Optimization problem seems expensive and difficult to solve**\n\nSince the sampling distribution computed from the optimization problem in (5) is central to the paper, I think it's necessary to provide evidence that it can be solved, and under what conditions it can be solved. I am concerned about this because\n- The inner maximization is non-concave as it is over a discrete set, and relaxations to convex hulls might incur larger sample complexities\n- The entire paper of Amortila et al. (2024) is about methods to solve (5), and I am not sure that any of them apply without relaxations of the objective and model access / online rollouts. Therefore the expense to solve (5) may dominate the total sample complexity of CAESAR, or fall outside the claimed problem setup (only one data collection phase). In addition, the the authors should probably discuss the robustness of the downstream methods (IDES etc) in the case that $\\hat \\mu^*$ is inaccurate. \n\n\n**Analysis of the weight estimation method (IDES)**\n\nThe gradient is estimated using samples from $\\mu$, but the sample complexity of estimating this gradient is not considered and is assumed away (as far as I can tell in the main body, since Lemma 4.6 simply assumes that we have an accurate $\\hat w$). It seems probable that this will incur worse dependencies in the total sample complexity of CAESAR. \n\n**Comparisons to Amortila et al. (2024)**\n\nIn L144-154 (left), the authors claim that the optimization problem in Eq. (5) is easier to solve than the one in Amortila et al. (2024); I think this simply may not be true given that the inner maximization in Eq. (5) is over a non-concave / discrete set, nor do the authors actually discuss how to solve Eq. (5). Also in general, stating that Amortila et al. (2024) is a \"concurrent work\" (L144) is simply dishonest, as it precedes this submission by 1 year, and deserves much greater credit in Section 4.2. \n\n**Novelty of coarse visitation estimation** \n\nZhang and Zanette (2023), which is not cited in the submission, has already demonstrated how to estimate visitations up to constant accuracy, and their Lemma A.22 is essentially the same result as Eq. (1). Although their setting is different, it's related in the sense that they use coarse estimation to get a fast rate and use coarsely estimated occupancies to explore. I think it is not fair to claim coarse estimation as a contribution in this submission, without at least heavily citing Zhang an Zanette (2023). \n\n**References**\n\nZhang, Ruiqi, and Andrea Zanette. \"Policy finetuning in reinforcement learning via design of experiments using offline data.\" Advances in Neural Information Processing Systems 36 (2023): 59953-59995.", "methods_and_evaluation_criteria": "As this work is theoretical in nature, I would say that the guarantees the authors have desired to prove make sense for the stated problem.", "theoretical_claims": "I did not check the proofs, but the high-level dependencies in the theoretical claims seem consistent with what one would expect and with those in existing work.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "The paper combines methods from previous literature on weight and policy visitation estimation, and reward-free exploration with visitations and weight estimation, to the setting of multiple policy off-policy evaluation. The goal is to reduce linear dependence in $K$ to a better coverage coefficient.", "essential_references_not_discussed": "Important references are missing and/or inadequately credited\n- As mentioned previously, Zhang and Zanette (2023) show how to coarsely estimate distributions, and show how to use them for exploration. Another highly relevant work along this vein is Li et al. (2023), who also estimate distributions up to constant accuracy, then use them to compute a covering distribution (for tabular MDPs, but they describe how to optimize the objective efficiently). \n- The optimization problem in Eq. (5) is identical to the one in Amortila et al. (2024) \n- Techniques behind gradient-based methods to estimate weights, and handling error propagation of estimated weights and visitations, have been utilized in in Huang and Jiang 2024; Kallus and Uehara 2020; Amortila et al. 2024; Huang et al. 2024\n\n**References** \n\nLi, G., Zhan, W., Lee, J. D., Chi, Y., & Chen, Y. (2023). Reward-agnostic fine-tuning: Provable statistical benefits of hybrid reinforcement learning. Advances in Neural Information Processing Systems, 36, 55582-55615.\n\nKallus, N., & Uehara, M. (2020, November). Statistically efficient off-policy policy gradients. In International Conference on Machine Learning (pp. 5089-5100). PMLR.\n\nHuang, A., & Jiang, N. (2024). Occupancy-based Policy Gradient: Estimation, Convergence, and Optimality. Advances in Neural Information Processing Systems, 37, 416-468.\n\nAmortila, P., Foster, D. J., Jiang, N., Sekhari, A., & Xie, T. (2024). Harnessing density ratios for online reinforcement learning. arXiv preprint arXiv:2401.09681.\n\nHuang, A., Chen, J., & Jiang, N. (2023, July). Reinforcement learning in low-rank mdps with density features. In International Conference on Machine Learning (pp. 13710-13752). PMLR.", "other_strengths_and_weaknesses": "I think that the technical contributions and conceptual insights of this paper are limited in novelty, in the sense that they are largely derived from existing papers and combined for the task of multiple policy off-policy evaluation. \n\nHowever, the observations that (a) one only needs to estimate the visitation distributions up to constant accuracy and (b) one can extract useful importance weights from this seem interesting and useful. At the same time, all of this relies on being able to solve Eq. (5), which to me, is the hardest part of the problem. \n\nI am recommending rejection because of the obfuscated presentation of results (sample complexity), the lack of consideration towards how to solve Eq. (5), and the improper acknowledgement of existing work from which many technical tools were almost surely derived.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "1. What is the sample complexity of step 1 of CAESAR, i.e., estimating the visitations of all policies? \n2. How can Eq. (5) be solved, and can you comment on the expected sample complexity?\n3. Since the gradient in IDES is estimated, can you comment on the expected complexity of learning $\\hat w$ via SGD?", "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": "nkjRvUWobW", "reviewer": "Reviewer_YEZA", "summary": "This paper tackles the problem of multiple-policy evaluation, by proposing an offline off-policy approach named “CAESAR”, in contrast to the online on-policy approach by Dann et al. 2023. \n\nThe proposed approach first performs a coarse estimate of the visitation distributions of the target policies. These estimates are then used to approximate the optimal sampling distribution and to compute the importance density ratio, drawing inspirations from DualDICE [Nachum et. al. 2019]. For estimating the visitation distributions of deterministic target polices, they also proposed an algorithm MARCH, leveraging a novel notion called $\\beta$-distance.\n\nFurthermore, the paper provides a detailed analysis of the sample complexity of CAESAR, presenting PAC bounds and show how they scale with key parameters such as horizon H, number of policies K, number of states S and actions A.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts on reviewing our paper. We appreciate your comments. And we kindly request you to consider increasing your score if we solve your concerns and questions.\n\n> The intuition behind $\\beta$-distance does not seem entirely clear.\n\nThe $\\beta$-distance is defined as follows $dist^{\\beta}(x,y)=\\min_{\\alpha\\in[1/\\beta, \\beta]} |\\alpha x - y|$. The $\\beta$-distance is zero as long as $\\frac{x}{\\beta} \\le y \\le \\beta x$ which means $x$ approximates $y$ up to multiplicative constant $\\beta$ error. The intuition behind $\\beta$-distance is that we want a metric that can measure the coarse estimation. $\\beta$-distance is such a metric. We showed that in  Lemma B.5, if $\\beta$-distance is smaller than $\\epsilon$, then we can show $x$ is a coarse estimator for $y$. With this metric, we can focus on analyzing the bound of $\\beta$-distance, $dist^{\\beta}(\\hat d, d)$, to show $\\hat d$ is a coarse estimator for visitation distribution $d$. Analyzing $\\beta$-distance is much more convenient than analyzing the formulation in Definition 4.1.\n\nThanks for the comment. The detailed elaboration of $\\beta$-distance and MARCH is in Appendix B. We will consider updating the paper to clarify $\\beta$-distance and MARCH more in the main page. \n\n> It would be better to include experiments that can show the $H^4$ dependency of sample complexity.\n\nWe do agree with the reviewer that having such an experiment will strengthen the paper, but practically, to show the dependency of $H^4$ in experiments would be extremely hard since it is just an upper bound with high probability. And we also want to reiterate that we consider the scope of our submission to be the advancement of our theoretical understanding of this problem. As such we hope to obtain a fair evaluation of our submission based on its merits to advance theoretical research in RL.\n\nWhat's more, same as most theoretical works in RL, we were concerned with achieving the sharpest S and K (for this specific problem) dependence, which given the large size of S in applications is typically considered more consequential than dependence on H. Our minimax upper bounds achieve the sharpest dependence on S and A.\n\n\n> Elaborate that a different loss function might address the sub-optimal dependency on $H$. And is there any other approach to address  it?\n\nThe loss function we defined to estimate the importance densities is a step-wise loss function (see L312-315 (right)). And we are adopting a step-by-step optimization procedure, i.e., we first get the estimator at step h-1 by minimizing the loss function $l_{h-1}(w)$, and then, utilizing it to get estimator at step $h$ by minimizing $l_h(w)$. Since the loss function at step $h$ depends on the estimator from last step, there is an additive error propagation which induces the $H^4$ dependency.\n\nWhat we are thinking is to propose a comprehensive loss function $L(w)$ that incorporates all steps utilizing some coarse knowledge of transition functions. By minimizing this loss function, we can get the importance density estimator for all layers at once which avoids the step-to-step error propagation thus gets rid of $H^4$ dependency.\n\nIt is a good question that if there are other approaches to solve multiple policy evaluation problems well with optimal dependency on $H$. Based on our pipeline, we think it is hard to do more beyond the method we described above but we are optimistic that there exists totally different methods that can achieve it. Multiple policy evaluation is a challenge and under-studied problem which is worth exploring.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the proof of the main results and did not identify obvious issues.", "experimental_designs_or_analyses": "There are no experiments in this paper.", "relation_to_broader_scientific_literature": "It extends prior work in multiple-policy evaluation from online, on-policy setting to an offline off-policy setting. And it adapts and extends the distribution ratio estimation technique from DualDICE (Nachum et al., 2019) to the finite horizon context, with a step-wise objective function.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "1. The paper introduced the notion $\\beta$-distance for analyzing the sample complexity of MARCH. However, the intuition behind $\\beta$-distance does not seem entirely clear. Additional discussions about that would enhance the clarity.\n2. Due to the $H^4$ dependence of sample complexity, it would strengthen the paper to include experiments that empirically verify that scaling.", "other_comments_or_suggestions": "No.", "questions_for_authors": "The sample complexity in Theorem 4.9 scales with $H^4$, compared to the $H^2$ scaling in Dann et.al (2023) has $H^2$. This higher order dependence on $H$ may limit the practical applicability of the proposed method.  You mentioned that this gap was induced by the error propagation and conjectured that a different loss function might address it. Can you elaborate on that point and discuss if there are other approaches that might reduce the dependence on $H$?", "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": "bIl0w6yQso", "reviewer": "Reviewer_S332", "summary": "This paper addresses the problem of evaluating the performance of multiple target policies in reinforcement learning (RL) using a sample-efficient algorithm called CAESAR. Existing methods for single-policy evaluation can be inefficient when applied separately to each policy, especially when policies are similar. CAESAR tackles this by first estimating coarse visitation distributions for all policies, then designing an approximately optimal sampling distribution that efficiently covers all target policies simultaneously. The sampled data is used to estimate policy values using importance weighting, with importance ratios estimated through a new technique called IDES, inspired by the DualDICE method. Compared to prior work, CAESAR offers a flexible offline evaluation framework, works for finite-horizon MDPs, and is applicable to both policy evaluation and near-optimal policy identification tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts on reviewing our paper. We really appreciate your positive feedbacks on our work. We agree that framing the task as 'offline' multiple-policy evaluation is kind of wired and may cause some unnecessary confusions. Thanks for pointing it out and we will consider reorganizing the language.", "claims_and_evidence": "The claims made in the paper are well supported with the theoretical results accompanied.", "methods_and_evaluation_criteria": "The proposed methods has strong theoretical backgrounds. It is not empirically evaluated, but it is evaluated with its sample complexity and compared with other algorithms with its order.", "theoretical_claims": "I was not able to fully check the correctness of theorems, but the proofs seem to be detailed enough to easily point out the issues, and I haven't found any issue.", "experimental_designs_or_analyses": "The paper is not performing any experiments.", "relation_to_broader_scientific_literature": "- This paper contributes to the less explored area of what policy should be used to effectively evaluate multiple policies. This paper seems to be one of a very few papers that provides theoretical results on this field. This may have some impact to practical algorithms who have similar goals.\n- This paper proposes IDES, a non-trivial extension of DualDICE to finite-horizon MDPs.", "essential_references_not_discussed": "I am not aware of any essential references that are not discussed in this paper.", "other_strengths_and_weaknesses": "- very detailed, easy to follow proofs\n- the paper is overall easy to follow\n- deals with an issue that have a number of practical applications\n- purely theoretic, no empirical analyses", "other_comments_or_suggestions": ".", "questions_for_authors": "I am not sure whether framing the task as \"offline multiple-policy evaluation\" is appropriate, because at a first glance it looks like a trivial problem, evaluating multiple policies with a given offline dataset. IMO, it would be easier to understand if the task was framed as computing a policy with least OPE error on multiple policies.", "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": "0phSQ2bT8t", "reviewer": "Reviewer_Qkrf", "summary": "The paper introduces CAESAR, an algorithm for efficiently evaluating multiple policies in finite-horizon MDPs to a desired accuracy and confidence level. CAESAR first obtains coarse estimates of the visitation distributions with low sample complexity, and then refines these estimates by computing importance weights using a step-wise quadratic loss inspired by DualDICE. Additional contributions include the IDES subroutine for improved importance ratio estimation and the MARCH algorithm, which, along with a new β-distance metric, enables efficient estimation even with exponentially many deterministic policies.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts on reviewing our paper. We are confident that we can solve your concerns and questions. And we kindly request you to consider increasing your score if you think we address your concerns.\n\n> The hybrid setting of online and offline is confusing.\n\nSorry to cause the confusion. The setting of our problem is online. Our problem formulation is: given a set of target policies and an unknown MDP, evaluate the performance of all these policies. No additional dataset is given, interactions with the environment are necessary, so it is definitely online.\n\nWe do mention in the paper that our method is implemented more like in an offline manner. Since for offline RL, an offline dataset is given and no more interaction is allowed, i.e. we can only sample data from this fixed given distribution. This is exactly the second phase of our algorithm, where we have a fixed sampling distribution/policy derived from the first phase, and use data from this fixed distribution to perform the evaluation.\n\n> The connection between our method and offline RL.\n\nIn offline RL, an offline dataset is given and usually is assumed to have good coverage over the state space. In our scenario, if we already have an offline dataset that has good coverage over the space of these target policies, then we can directly use methods from offline RL to do off-policy evaluation of these target policies. However, it is not the case. We don't assume such a good offline dataset which is always unpractical because we have multiple policies, and even if it exists, it may be super sub-optimal with respect to the policies at hand, e.g. a uniform offline dataset.\n\nWhat our method does is, we first interact with the environment to get some information of the target policies and then we can calculate  an approximately optimal sampling policy in terms of the coverage over the target policies. We successfully show that only low-order  samples are needed to construct such a sampling dataset/policy. In the second phase, we can just sample data using this fixed sampling policy to do policy evaluation just like offline RL.\n\n> Doubts on the reasonability of coarse estimation.\n\nThat's one of our contributions. In our work, we theoretically show the effectiveness of coarse estimation in multiple-policy evaluation problem. The coarse estimation has been proved reasonable. \n\nWe are not sure what exact concerns you have about coarse estimation. Are you concerned about how coarse estimation leads to final accurate performance evaluation? It is true that one can never achieve estimation up to $\\epsilon-$accuracy by just doing coarse estimation with $\\tilde{O(1/\\epsilon)}$ sample costs, the technique is that coarse estimation is only used to approximate an intermediate quantity in the whole procedure, e.g. the sampling distribution $\\hat \\mu^*$ in our scenario. In our setting, to evaluate the final performance accurately, the second phase is unavoidable.\n\nCoarse estimation is powerful since first, it only needs low-order samples which is negligible compared to the main order of sample costs, second, the multiplicative constant error it induces is acceptable. In other words, it enables us to approximate some useful intermediate quantities at an acceptable sample cost and error which serves an important role to achieve the ultimate goal. \n\n\n> The comparison with existing results is unclear which is better.\n\nWe already discussed the comparison of our sample complexity with the existing work in Section 5.1. It is unclear whether our sample complexity is universally better, however, our result is meaningful and significant by offering new insights for the problem and sharing many advantages. First, we solve the unfavorable dependency of $1/d^{max}(s)$ in existing results. Second, our work tackles the problem from a different perspective which is complementary to the existing method. Third, our sample complexity is cleaner and more  interpretable than the existing result. Finally, we can parallelize our method while the existing method can't since it relies on trajectory stitch which is a practical advantage.  \n\n> Why lower bound of MARCH need the assumption that policies are deterministic?\n\nIt is not an assumption. MARCH is our proposed algorithm to coarsely estimate all deterministic policies. Since we consider tabular MDPs, any policy can be expressed as a combination of deterministic policies. So it is enough to estimate all deterministic policies. \n\n> Why MoM is introduced? Why the bounded expectation in Lemma 4.7 does not directly indicate the high probability bound?\n\nA result holds in expectation usually does not imply that the result holds with high probability. In our scenario, we get our importance density estimators by Algorithm 1 which uses stochastic gradient descent.\n\n> Other comments\n\nThanks for the comment. We will consider updating our paper to make the setting clearer, include more related works in offline RL and implement some experiments.", "claims_and_evidence": "The theoretical results is  backboned by comprehensive proof.", "methods_and_evaluation_criteria": "The result is evaluated in terms of sample complexity.", "theoretical_claims": "I checked the prooffor Secton 4.1 and 4.2 briefly and it seems make sense.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "see below", "essential_references_not_discussed": "I think this paper is widely related to offline RL (instance-dependence bound), offline policy evaluation and I think the paper should add more dicussions related to these literature.", "other_strengths_and_weaknesses": "- The paper is well-organized and the main idea of the whole algorithm is well devided into several sections with detailed discussions\n- The idea is quite new and I think the problem fomulation itself in practice since it may be related to how to construct a shared dataset for policy evaluation\n- However, I'm quite confusion with the setting since it seems to be hibrid evaluation process since the coarse  estimation is estimated online and then the policy is evaluted, in an offline pattern, with a dataset collected by the chosen sampling policy based on the estimation attained online. Such a hybrid process is quite counteriintuitive to me and need more clarifications.\n- Also, the definition of coarse estimation seems new and I'm not sure whether it's reasonable.", "other_comments_or_suggestions": "- Add more clarifications on the setting and the definition\n- Since a new concept/measure is proposed, it would be better to use some experiment to show whether it's reasonable or not.", "questions_for_authors": "- Please clarify the weakness part.\n- Could author connect the proposed method more with offline RL literature and show what's the similarity and difference since the high-level idea seems really similar to me\n- The comparison with existing results is unclear to me which is better. Would it be possible to provide a more clear result in a specific setting?\n- Why MoM is introduced? Why the bouned expectation in Lemma 4.7 does not directly indicate the high probability bound?\n- Why lower bound of MARCH need the assumption that policies are deterministic? From my intepretation, it's a result for tabular MDP", "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:

Meta-review: The reviewers have raised several concerns, and the authors have addressed most of them. The paper has strengths and weaknesses:

**Strengths**

- Clarity: Well-organized, easy-to-follow proofs and a clear explanation of CAESAR.

- Novelty: Introduces IDES and MARCH, advancing offline policy evaluation, with results that do not depend on the number of policies.

**Weaknesses**

- No Empirical Validation: Lacks experiments to support the practical effectiveness.

- Coarse Estimation: The coarse estimation concept requires further justification and comparison with existing works.

Overall, although the paper has received mixed scores, I am more inclined towards acceptance.
Decision: Accept (poster)