Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach
Authors: Riccardo Poiani
Nicole Nobili
Alberto Maria Metelli
Marcello Restelli
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Policy Evaluation
Budget Optimization
Monte Carlo
TL;DR: We propose a theoretical grounded and adaptive method for optimizing the interaction with the environment in Monte Carlo Policy Evaluation.

Abstract: Policy evaluation via Monte Carlo (MC) simulation is at the core of many MC Reinforcement Learning (RL) algorithms (e.g., policy gradient methods). In this context, the designer of the learning system specifies an interaction budget that the agent usually spends by collecting trajectories of *fixed length* within a simulator. However, is this data collection strategy the best option? To answer this question, in this paper, we consider as quality index the variance of an unbiased policy return estimator that uses trajectories of different lengths, i.e., *truncated*. We first derive a closed-form expression of this variance that clearly shows the sub-optimality of the fixed-length trajectory schedule. Furthermore, it suggests that adaptive data collection strategies that spend the available budget sequentially might be able to allocate a larger portion of transitions in timesteps in which more accurate sampling is required to reduce the variance of the final estimate. Building on these findings, we present an *adaptive* algorithm called **R**obust and **I**terative **D**ata collection strategy **O**ptimization (RIDO). The main intuition behind RIDO is to split the available interaction budget into mini-batches. At each round, the agent determines the most convenient schedule of trajectories that minimizes an empirical and robust estimate of the estimator's variance. After discussing the theoretical properties of our method, we conclude by assessing its performance across multiple domains. Our results show that RIDO can adapt its trajectory schedule toward timesteps where more sampling is required to increase the quality of the final estimation.

Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach
Riccardo Poiani
Nicole Nobili
DEIB, Politecnico di Milano riccardo, poiani @polimi..... poianippolmmi it
DEIB, Politecnico di Milano www.iliimmmaal 1aail10maal..... polipilliii..
nicole a.cole.nobilln
Alberto Maria Metelli DEIB, Politecnico di Milano htt.rommrrr.mmeeeliill........o. it
Marcello Restelli DEIB, Politecnico di Milano
rarcello..esttell@@o....... it
Abstract
Policy evaluation via Monte Carlo (MC) simulation is at the core of many MC Reinforcement Learning (RL) algorithms (e.g., policy gradient methods). In this context, the designer of the learning system specifies an interaction budget that the agent usually spends by collecting trajectories of fixed length within a simulator. However, is this data collection strategy the best option? To answer this question, in this paper, we consider as quality index the variance of an unbiased policy return estimator that uses trajectories of different lengths, i.c., truncated. We first derive a closed-form expression of this variance that clearly shows the sub-optimality of the fixed-length trajectory schedule. Furthermore, it suggests that adaptive data collection strategies that spend the available budget sequentially might be able to allocate a larger portion of transitions in timesteps in which more accurate sampling is required to reduce the variance of the final estimate. Building on these findings, present alaptive algorithm called Robust and Iterative Data collection strategy Optimization (RIDO). The main intuition behind RIDO is to split the available interaction budget into mini-batches. At each round, the agent determines the most convenient schedule of trajectories that minimizes an empirical and robust estimate of the estimator's variance. After discussing the theoretical properties of our method, we conclude by assessing its performance across multiple domains. Our results show that RIDO can adapt its trajectory schedule toward timesteps where more sampling is required to increase the quality of the final estimation.
Introduction
In Reinforcement Learning (RL, /Sutton and Barto 2018 agent acts in unknown, partially known, enviromment to maximize/estimate the infinite expected discounted sum of an external reward signal, i.e.. the expected return. Monte Carlo evaluation [MC, Owen 2013) is the core of many successful RL algorithms. Whenever a simulator with reset possibility is available to the learning systems designer, a large family of approaches (Williams 1992, Baxter and Bartlett] 2001 Schulman et al. 2015 2017 Cobbe et al.) 2021] that can be used to solve the RI. problem relies on MC simulations estimating performance or gradient estimates on the task to be solved. In this scenario, since the goal is to estimate the expected infinite sum of rewards, the designer usually specifies sufficiently large estimation horizon T, along with a transition budget = QT, so that the agent
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

interacts with the simulator, via MC simulation, collecting batch of Q episodes of length T In this sense, the agent spends its available budget A uniformly along the estimation horizon.
In the context of MC policy evaluation, where the goal lies in estimating the performance of a given policy via MC simulations, (Poiani et al. (2023) have recently shown that, given the discounted nature of the RL objective, this
budget allocation strategy may not be the best option. The core intuition behind their work is that, since rewards are exponentially discounted through time, early interactions weigh exponentially more than late ones, and, consequently, a larger portion of the available budget A should be dedicated to estimating the initial rewards. To theoretically validate this point, the authors designed non-adaptive budget allocation strategy which, by exploiting the reset possibility of the simulator, leads to the collection of trajectories of different lengths, i.e.. truncated. They show that this approach provably minimizes Höeffddingllike confidence intervals [Boucheron et al. 2003] around the empirical estimates of the expected return. Remarkably, this implies robustness w.r.t. the uniform strategy that holds for any pair of environment and policy to be evaluated, thus, clearly establishing the theoretical benefits of the proposed method.
Nevertheless, it has to be noticed that although minimizing confidence intervals around the expected return estimator comes with desirable theoretical guarantees (e.g.. PAC-bound improvements (Even- Dar et al. 2002)) the resulting schedule of trajectories is computed before the interaction with the environment (being determined by the discount factor). Consequently, as the usual uniform- n--the-horizon scheme, it fails to adapt to the peculiarities of the problem at hand, and, ultimately. might not produce a low error estimate. For the sake of clarity, we illustrate this sub-optimality of pre-determined schedule of trajectories with the following extreme examples.
Example 1. Consider an environment where the reward is gathered only at the end of the horizon T (e.g., a goal-based). In this scenario, any strategy that truncates trajectories is infuitively sub-optimal, and we expect that an intelligent agent will spend all its budget according to the uniform schedule.
Example Conversely, consider a problem where the reward is different from O in the first interaction step only (e.g. in the case of highly sub-optimal policy that immediately reaches the "zero reward region" of an environment); the uniform schedule wastes a significant portion of its budget collecting samples without variability, and, to reduce the estimation error, we would like the agent to spend all of its interaction budget estimating the reward of the first action.
Abstracting away from the previous examples, we realize that the main issue of existing approaches arises from the fact that determining a schedule of trajectories before interacting with the environment does not allow the agent to adapt it to the environment peculiarities, allocating more samples where this is required to obtain a high-quality estimate. For this reason, in this work, we focus on designing adaptive data collection strategies that aim directly at minimizing the error of the final estimate. Our main intuition lies in splitting the available budget A into mini-batches and adapting online the data collection strategy of the agent based on the previously collected information.
Original Contributions and Outline After introducing the necessary notation and backgrounds (Section 2. we consider the problem of maximizing the estimation quality of a policy expected return estimator using trajectories of different lengths collected via MC simulation with a finite budget A of transitions (Section 3) More specifically, since we use unbiased return estimator, we consider its variance as a quality index, of which we derive a closed-fomm expression and analyze it for every possible schedule of trajectories. Then, we define the optimal trajectories schedule as the one that attains the minimum variance subject to the available budget constraint. As expected, computing this optimal data collection strategy requires knowledge of the underlying environment (e.g., the variance of the rewards at each timestep), which is not available to the agent prior to the interaction. Nevertheless, as we shall see, all the quantities that define the optimal strategy can be estimated from the data. These facts confirm our intuition about the weakness of non-adaptive schedules of trajectories and suggest that algorithms that spend the available budget A iteratively might be able to dynamically allocate their budget to minimize the variance of the final estimate. Building on these findings, in Section 4 we present novel algorithm, Robust and Iterative Data collection strategy Optimization (RIDO), which splits its available budget A into mini-batches of interactions that are allocated sequentially minimize an empirical and robust estimate of the
'hile another large class of RL algorithms is based on Temporal Difference [TD, Sutton and Barto 2018 learning. which do not require the finite horizon nor the reset possibility, Monte Carlo simulation approaches hes continue to be extensively adopted. Indeed, unlike TD methods. they can be applied effortlessly to non- non- MaMakovvn environments, which is common occurrence in worldw problems.
2

---

objective function of interest, i.e., the variance of the estimator. Furthermore, we perform a statistical analysis on the behavior of RIDO, and we derive theoretical guarantees expressed as upper bounds on the variance of the policy return estimator. Our result shows that, under favorable conditions, the variance of the return estimator computed by RIDO is of the same order as the one of the oracle's ss baseline. To conclude, in Section | we conduct an experimental comparison between RIDO and non-adaptive schedules. As we verify, our method achieves the most competitive performance across different domains, discount factor values, and budget, thus clearly highlighting the benefits of adaptive strategies over pre-determined ones.
2 Backgrounds and Notation
This section provides the notation and necessary backgrounds used in the rest of this document.
Markov Decision Processes A discrete-time Markov Decision Process IMDP, Puterman 2014 is defined as tuple M := (S, Rt P. v),, where S is the set of states, A is the set of actions,
R: S A + [0, 1] is the reward function the specifies the reward R(s, a) received by the agent upon taking action a in state s. : S x - ASS the transition kernel that specifies the probability distribution over the next states P(-|s, a), when taking action a in state s, 7 E (0, 1) is the discount factor, and E ASS) is the distribution over initial states. The agent's 's behavior is modeled by a policy æ S + AAA), which for each state s, prescribes a distribution over actions π (-|s). A trajectory Th of length h is sequence of states and actions (su, 4u, $1.... Sh-1. Oh-10 $1.) observed by following æ for steps, where 50 ~ v, Ot ~ T(](+), and 8e41 ~ P(-[st, ae) for L h. The return of trajectory is defined as G(T))) = En 7 RR, where RG is shortcut for R(st, qz). The agent that following policy is evaluated according expected cumulative discounted sum of rewards over an estimation horizon T namely (T) = Ex ETD y'ee where the expectation is taken w.r.t.
the stochasticity of the policy, the transition kernel, and the initial state distribution.
Data Collection Strategy Poiani et al. 2023 formalized the concept of Data Collection Strategy (DCS) to model how the agent collects data within an environment. More specifically, given an interaction budget A E N such that A mod T 0, a DCS is defined as a 7 7-dimensional vector m (m1,.... my) where my N and Σ hh= m,, A. Each element m, specifies the number of trajectories of length that the agent collects in the environment while following a policy π. Given DCS m, it is possible to compute the total number of steps n = (Mo.--.. -.--- that will be gathered by the agent at any step I; more specifically, the following relationship holds: fr- = mr, and n4 = 14+11 M4+11 for t < T 1. For this reason, in the rest of the paper will adopt the most convenient symbol depending on the context. For any DCS m such that mr 2 holds, it is possible to build the following unbiased estimator of (TT):
T my
Jm (x) =
74
A=l
The two external summations in Equation ( sum over the collected trajectories of different lengths a rescaled empirical trajectory return, where the reward at step t is divided by the number of samples collected at step In the case the budget A is spent uniformly, i.e., m (O....,,, A
Equation
reduces to the usual Monte Carlo estimator of J(T), namely A EVVT Σ *
Robust Data Collection Strategy Optimization Leveraging the estimator of Equation 2. Poiani et al. 2023] investigated alternatives to the usual wiwffoommii-tth-hooiii perspective of confidence intervals (Boucheron et al.] 2003). More specifically, given m such
DCS from the worst-case
that mr 1, the estimator of Equation (1) enjoys the following generalization of the Höeffding
Given a set X. we denote with ((X) the set of probability distributions over X.
3 As common in Monte-Carlo simulation [see e.g.. Papini et al. 2022) we approximate the infinite horizon
MDP model with finite estimation horizon T. Indeed, if 7 is sufficiently large, i.e., T O I log )). the expected return computed with horizon e close to the horizzo one Kakade 2003
'Rescaling by nu prevents the estimate from being biased towards time steps for which more samples are available.
3

---

confidence intervals holding with probability at least 1 - 5:
T T-1
((x) - Jm = log
(2)
t= Thz
2"(''47"11-27" controls the relative importance of samples gathered at step f. Poiani 1-7
where de
al. 2023] designed closed-form DCS that provably minimizes the bound of Equation 2 Since
di is decreasing function of time whose decay speed is governed by the discount factor 7 the aforementioned DCS gives priority to the collection of experience earlier time steps, i.e., truncates the trajectories. Note that the smaller 7, the higher the number of samples reserved for earlier time steps. We refer the reader for Theorem 3.3 and Theorem B. of their work for the exact expressions of the resulting robust DCS. However, we remark that the resulting schedule is non-adaptive (i.e., it is computed before the interaction with the environment takes place) and its shape depends exclusively on A, 7, and T.
3 Toward Adaptive Data Collection Strategies
In this section, we lay down the theoretical groundings behind optimizing data collection strategies that directly aim at minimizing the final estimation emror. We stick to methods that adopt the estimator of Equation (I), which has simple interpretation and desirable theoretical properties. More specifically, since the estimator is unbiased, the Mean Squared Error (MSE) simply reduces to proper baseline for DCS optimization (i.e., optimal strategy
the variance. For this reason, according to the MSE), we first analyze the variance of the estimator of Equation (T) for an arbitrary DCS m. The following Theorem (proof in Appendix (A) summarizes our result.
Theorem 3.1. Consider generic DCS m such that mt 2 then:
T-1
T-1
T-1 ft
Varm [mm(TT]
= Σ t=
1 The
Re) +2
Σ 1'
y 4t' Cov Re))
= Σ t=
(3)
Theorem 3.1 expresses, in closed form, the variance of the estimator of Equation T when adopted with an arbitrary DCS that guarantees the estimation to be unbiased (i.e., my 2 1). From Equation (3), we can see that this variance results in a summation, over the different time steps, of x. i.e., the reciprocal of the number of samples collected under m at step t, multiplied by the variance of the reward at step plus the covariances between R, and the rewards gathered at future steps. For brevity, we shortcut this term with ft. Furthermore, Theorem 3.1 leads to direct formulation of an optimal DCS baseline for our setting. More specifically, given a budget A, we define the optimal DCS n' for the estimator in Equation as the solution of the following optimization problem:
T-1
min n
2t (Rt) +2
Σ M=#+1
H+t Cov Re)
s.t.
Σ The I A t=0
(4)
n4 2 M1+1,
Vt E {0. ,o....,TT 2}
T -}
n4 N+, Vt (0. (O....,TT T 1}.
where the constraints nu 2 n4+1 directly encode the sequential nature of the interaction with the environment. At this point, some comments are in order. First of all, we notice that the above optimization problem nicely captures the intuitive examples of Section I
Example 1 (cont.). When the reward is different from in the last interaction step only, the objective
function reduces to 2(T-1) Var [Rr- which is clearty minimized for the uniform strategy.
AT Example 2 (cont.). Conversely, when the reward is different from 0 in the first step only, we obtain
Var Ro. meaning that the entire interaction budget should be dedicated to estimate Ro-
1kg

---

Algorithm 1 Robust and Iterative DCS Optimization (RIDO).
Require: Interaction budget A, batch size b, robustness level 9. policy
1: Collect D using policy π and Åbo = ....... +)
2: Set = : and initialize empirical estimates Vari [Ra] and Cov [Re, Ri.]
3: for i 1, ..... K do
4: Collect D; using policy æ and f.g, where is computed solving problem 5
5: Update empirical estimates v (aar [R.] and Cov, [R., Rt]] using D, and set D DUD,
6:
end for
Furthermore, the formulation of problem (4) highlights the pitfalls of non-adaptive data collection strategies. Indeed, consider, for the sake of clarity, the two examples mentioned above. Before executing policy х. the agent has no way of distinguishing between the two different objective functions, i.e., - 2(3-1) Var [RT--]] and Var[Rol, and, consequently, any pre-determined schedule fails Ar-1 to adapt to the actual objective function. More generally, this is because the optimal strategy resulting from the optimization problem (4) can be computed prior the interaction with the environment only by an oracle that knows in advance the underlying reward process induced by the agent's policy и in the MDP. Nevertheless, we note that all the terms appearing in the objective function, i.e. the only unknowns in optimization problem 4 can be estimated if some interactions with the environment are available to the agent. This suggests that strategies that sequentially allocate the available budget might successfully adapt their DCS to minimize Equation B3. i.e., the variance of the return estimator.
nig
4 Robust and Iterative DCS Optimization
Given the findings of Section 3 we now present our algorithmic solution that aims at avoiding the highlighted pitfalls of pre-determined DCSs. Our approach is called Robust and Iterative Data collection strategy Optimization (RIDO), and its pseudocode available in Algorithm [ The central intuition behind RIDO lies in splitting the available budget A into mini-batches of interactions that the agent will allocate sequentially. At each iteration, the agent will compute the most convenient schedule of trajectories that optimizes an empirical and robust version of the objective function presented in (4) whose quality improves as the agent gathers more data.
We now describe in-depth the behavior of the algorithm. For simplicity of exposition and analysis, we suppose that the size of the mini-batch is such that mod T = 0 and 2 2T. At the beginning (Lines 2 in Algorithm 1), the agent spends the first mini-batch âo at collecting & trajectories of length T (i.e., the uniform approach). This preliminary collection phase is starting round in which some initial experience is gathered to properly initialize estimates of relevant quantities used throughout the algorithm. More specifically, at each iteration i, the agent maintains empirical estimates of the unknown quantities that define the variance of the estimate, i.e., the standard deviation
of the reward step namely VVars [Re]. and the covariances between rewards at different steps, namely Cov: Rr). Then, each round (Lines 4 in Algorithm 1. the DCS of the current mini-batch â. is computed solving the optimization problem (5) whose objective function a robust estimate of the objective function of the original optimization problem More specifically, at each round i, the agent aims at solving the following problem:
T-1
T-1
20
(VVar,(R) + C.,,1) +2
Σ r'#+1
gete' (Cov,(R,,Ry) Rv) + Citsr)
min
t=0
T-1
Σ 14 <
(5)
s.t.
t=0
n4 M4+1,
Vt (0, ... T T- 2}
n4 N4,
Vt .o.....7 T 1}.
5

---

where C and C 1 y are exploration bonuses for variances and covariances respectively, defined as:
2 log (3)
2 log (8)
C22
Cia =3 V
(6)
V j= Rj.t
where 3 is a hyper-parameter that specifies the amount of exploration used solve the optimization problem, and ft is the number of samples collected by RIDO during phase j at time step We now provide further explanations on the optimization problem (5) and Equation (6). First of all, we notice how each term in the original objective function, namely ft. is replaced with its relative empirical estimation plus exploration bonuses, each of which is directly related to components
within St, e.g., Var (Re) is replaced with (V Var, - Chatt and Cov (Re, Rv) is replaced with
Cov; (Re, Ci, Intuitively, the purpose of the exploration bonus is consider the uncertainty that arises from replacing exact quantities with their empirical estimation. This introduces in RIDO a source of robustness w.r.t. the noise that intrinsically present in the underlying estimation process. At this point, concerning the shape of Equation (6). focus for the sake of exposition on C,, First of all, we notice that the hyper-paramett 3 governs the robustness which is taken into account while replacing Var (Re) with its empirical estimate. Larger values of 3, correspond, indeed, to larger C² and, consequently, higher level of robustness w.r.t. the uncertainty. Furthermore, as we can notice, C²2, decreases with the number of samples collected in the previous iterations at step 1, i.e., Σj1 f. This quantity coincides with the number of samples that are used to estimate
V Var, [Re] This formulation captures the following aspect: more data is available to the agent to estimate Var (Re). the more accurate its estimate will be, and, consequently, its exploration bonus will shrink to 0. As one can expect, with this approach, the quality of the objective function used in RIDO increases with the number of iterations. Consequently, the agent will progressively adapt the mini-batch DCS toward time steps where more data is required to minimize Equation (3), i.e., the variance of the return estimator. We conclude with two remarks. First, we notice that RIDO can be applied with 7 = 1, as it does not deeply rely on the property of discounted sums. Secondly, the optimization problem (5) is a complex integer and non-linear optimization problem. Before diving into the statistical analysis of RIDO, we discuss how to solve (5) in the next section.
4.1 Solving the Empirical Optimization Problem
As noticed above, directly solving problem (5) requires significant effort since it is an integer, non-linear optimization problem. In this section, we discuss how to overcome these challenges.
We first perform a continuous relaxation, replacing the integer constraint ni, E N_ with n, 2 1. Once a solution n to the relaxed optimization problem is found, it is possible to obtain a proper (i.e., integer) DCS by flooring each ni and allocating the remaining budget uniformly. As we shall see, this approximation introduces constant terms in the theoretical guarantees of RIDO only. At this point, the resulting optimization problem is non-linear problem that, unfortunately, is generally non-convex. This issue occurs when the following condition is verified for some time step f:
ft 16=72' 1==>(( > (VPand()))) + +C +2
T-1
Σ e==+1
70v (Covi(Re,, Re) + Clae) O.
To solve this challenge and make RIDO computationally efficient, we develop approach based on a hidden property of the original optimization problem 44) More specifically, we start by noticing that even the continuous relaxation of ( is non-convex since fi < O might occur, for some t E {o,.... T' ".....,--- 2}, in the presence of negative covariances with future steps. In this case, however, since ET- Le represents a proper variance, which is always non-negative, there always exists L' > I such that Ei ft 2 O. Furthermore, it is possible to show that the optimal solution of the relaxed optimization problem uniform in the interval {f....,t') ,'), namely ni n
n. (proof in
SSimilar comments apply C,,,.' well. The only difference stands in the fact that estimate the empirical covariance between two subsequence steps t and t'. samples up to time 1' are required. For this reason. the denominator implies the summation of the number of samples gathered at i' over the previous iterations.

---

fu
fr+1 f1++1
fi'
fr-1
Ylo
Ry
fu VRo
Food f
fr-1
Figure I: Visualization of the transformation between the optimization problems. The first row shows the objective function the original optimization problem, while the second one its transformation.
Appendix Aj. For this reason, it is possible to define a transformation of the optimization problem that preserves the optimal solution, in which the variables ",....,, The are replaced with a single variable y. The objective function is modified accordingly, namely ft +.... fe' is replaced with nz
fet in the objective function. visualization of the transformation is proposed in Figure By repeating the procedure for all the negative ft, we obtain transformation of the original problem which is now convex. Once the solution to this convex transformed optimization problem is found, one can quickly recover the relaxed DCS in its T-dimensional form.
Building on these results, we apply in RIDO a similar procedure that transforms the relaxed version of (5) into new problem where the negative time steps (i.e., steps in which Equation 7 holds) are "grouped" with future time steps as long as the total summation is positive. In this way, (i) the resulting optimization problem is convex and (ii) as our analysis will reveal, this procedure has no impact on the theoretical properties of RIDO (i.e., the result is the same as assuming access to an oracle that can solve non-linear and non-convex problems). As concluding remark, we refer the reader to Appendix A for formal description of the above-mentioned procedure.
4.2 Theoretical Analysis
We now present theoretical guarantees the performance of RIDO. More specifically, derive high-prohee probabbbbbbiltty guarantees on the variance of the estimator of Equation ( when used with the data collected by RIDO. Before diving into the presentation of results, we highlight some critical challenges behind the result. First, in our analysis, we do not assume access to an oracle that solves (5) but consider the modifications discussed in Section 4.1 that make the computation tractable. This introduces a first level of challenges in the analysis (e.g.. dealing with the roundings that arise from the relaxation and the peculiar strategy that overcomes the non-convexity of the optimization problem). Secondly, we notice that none of the optimization problems ( and (5), and the ones obtained by relaxing the integer constraints, admit a closed-fol form solution (further details are provided in Appendix A). This clearly results in an additional challenge in our analysis. At this point, we are ready state our main theoretical result (proof in Appendix A)).
Theorem 4.1. Let n² be the optimal solution of problem (4, f. as in Equation
b b 2T and 6(T+T2)AK Consider the DCS computed by Algorithm Then, with probability at least 8 1 8 it holds that:
Vara [Ja(T)] < 192
log (3)
T + 4Wamm
Σ
7'
2
Jnn (T)
+
2b A
[ft
(8)
t:fic0
Equation (8) comprises three terms which we now discuss in detail. The former is directly responsible for taking into account the cumulative eтror computed during each phase i. This term shrinks to zero with rate δ ((*) log A). We notice that this gets smaller as we decrease b, thus suggesting to use small batch sizes. This should come as no surprise; indeed, using smaller batch sizes intuitively improves the adaptiveness of the algorithm, since a larger portion of the budget A will be allocated following more precise estimates of the quantities of interest. In this sense, there exists trade-off between theoretical guarantees and computational requirements, since the number of iterations (and, thus, the number optimization problems to solved) grows linearly as the batch size decreases. The second term, instead, is the variance of the optimal DCS computed as in 4 and shrinks with
7

---

rate that is at most 4 Et=o ft. This term, as we shall show below, represents a particularly desirable À property. Finally, the last component of Equation ( is related to the negative terms possibly present in the objective function, and, among the three terms, it is the one with the worst dependence on A. Currently, we are unsure whether this term is an artifact of the analysis, a sub-optimality of the algorithm, or a key challenge of the setting. We leave closing this gap to future work. At this point, we highlight a particular relevant property of Equation (8). Suppose that ft 2 0 holds for all time steps & (so that the last component is not present). In this case, under the mild assumption that Ek Se (i.e., the variance is different from 0), for sufficiently large budget of A, we have that (formal statement and proof in Appendix A):
Vara
[m()))] 5aar (m))
Thus, in this scenario, the variance of the returned DCS computed by RIDO is proportional to the optimal one. Note that this sort of result is not possible for the uniform strategy, nor for the robust one of Poiani et al. 2023). Further details on this point are provided in Appendix A
Numerical Validation
In this section, we propose numerical validations that aim at assessing the empirical performance of RIDO. More specifically, we focus on the comparison between our approach, the classical uniform- in-the-horizon strategy, and the robust DCS by Poiani et al. [023]] We report the results across multiple domains, values of budget A, and discount factor 7. As performance index, all experiments measure the empirical variance of the estimator in Equation [ at the end of the data collection
process. Before discussing our results in detail, we describe our experimental settings in depth.
Experimental Setting In our experiments, we consider the following four domains. We start with the Inverted Pendulum [Brockman et al. al.] (016)), a classic continuous control benchmark, where the agents' goal is to swing up a suspended body and keep it in the vertical direction. We, then, continue with the Linear Quadratic Gaussian Regulator [LQG, [LQG,]Curtain 1997]. where the agent controls a linear dynamical system with the objective of reducing total cost that is expressed
quadratic function. Then, we consider a 2D continuous navigation problem, where an agent starts at the bottom left corner of room and needs to reach a goal region in the upper right corner. The agent receives reward 0 everywhere except inside the goal area, where the reward is positive and sampled from a Gaussian distribution. Finally, we consider the Ant environment from the MuJoCo [Todorov et al. 2012 suite, where the agent controls a four-legged 3D robot with the goal of moving it forward. Further domain details are provided in Appendix B Concerning the policy that we evaluate for the Inverted Pendulum and the Ant, we rely on pre-trained deep RL. agents made publicly available by Raffin [2020]. For the LQG, instead, we evaluate the optimal policy that is available in closed form by solving the Riccati equations, and, finally, for the 2D navigation task, we roll out a hand-designed policy that minimizes the distance of the agent's 'ss position w.r.t. to the center of the goal region. Regarding the performance index, as already anticipated, we report the variance of the empirical policy return at the end of the data collection process. Given budget and a DCS, for single run, we estimate this empirical variance using 100 simulations. We then average the results over 100 runs and report the empirical mean together with 95% confidence intervals. We notice that for each considered value of A, the experiment is repeated (i.e., we do not use data collected with smaller A A's). To conclude, we refer the reader to Appendix for further details on the experiments (e.g., ablations, additional results, experiments with 1, hyper-parametery, visualizations of the resulting DCSs).
Results Figure reports the results varying the discount factor and the available budget. The second row is obtained under the same experimental setting as the first one, but with lower values of 7. Let us first focus on the sub-optimality of the non-adaptive DCSs (i.e.. the uniform strategy and the robust one of Poiani et al. (2023)). Indeed, as suggested by Theorem 331 being computed prior to the interaction with the environment, these algorithms cannot adapt the collection of samples minimize the variance of the return estimator. This is clear by looking, for instance, at the results of Continuous Navigation and the LQG. Indeed, in the Continuous Navigation domain, the reward is sparse and received close to the end of the estimation horizon T. In this scenario, the robust DCS blindly truncates trajectories, thus, avoiding the collection of experience in the most relevant timesteps. Conversely, in the LQG experiments, the optimal policy that arises from the Riccati equation pays
8

---

Pendulum 0,995, T
LQG 0.99, 100)
Novigation 0.99, 100)
Ant
500)
5.000
Aog. Verianen
200
0.5
6,000
6000
4.000
200
0.2
0.2
2,200
Hudgee
-104
Budget
1104
Budget
-104
Budget
1104
Paniulum
0.90,
LQG
0.9.
Navigation
0.95,
Avg. Variance
300
0.5
2013
100
200
0.3
Budgget 1of
Budget
Budget
-104
Buskge
-104
Uniform
Robust
RIDO
Figure 2: Empirical variance (mean and 95% confidence intervals over 100 runs) on the considered domains and baselines. The first row considers higher values of y w.r.t. the second one.
stochastic control cos at the beginning of the estimation horizon to bring the state of the system close to stability, after which the reward will remain almost constant. this case, the uniform DCS results in highly sub-optimal behavior most of the estimation uncertainty is related to the initial interaction steps. RIDO, on the other hand, thanks to its adaptivity, able to obtain the best results in both domains. Indeed, in the Continuous Navigation problem, achieves the same performance level as the uniform strategy, while in the LQG it even outperforms the robust DCS of Poiani et al. [2023] The reason is that[Polant et al. 2023 truncates trajectories solefy depending
the value of 7 and, therefore, it might waste a portion of its budget in trajectories of sub-optimal length, while RIDO, since aims minimizing the variance of the final estimation, able to focus the collection of data in the most convenient way. Similar comments to those made for the LQG hold for the Pendulum domain well. Concerning the Ant environment, instead, we notice that for 7 0.999 there is no significant difference between any of the presented schedules. Interestingly. however, as soon as we decrease y to 0.99, we can appreciate the sub-optimality of the uniform strategy, which wastes portion of its budget in gathering samples that are significantly discounted, and, therefore, their weight the estimator's 's variance shrinks to 0. On the other hand, the robust strategy and RIDO avoid this pitfall thanks to the exploitation of the discount factor, thus obtaining reduced variance estimates. Finally, we remark that RIDO has achieved the most competitive performance across various domains, values of the discount factor, and budget, thus clearly highlighting the benefits of adaptive strategies w.r.t. pre-determined ones.
Related Works
We now present comprehensive analysis and discussion of previous works that are closely connected to our own research. First of all, our work focuses on estimating policy's performance in given MDP [Sutton and Barto 2018 Considering the significance of this task, reducing the variance, or more generally, the error of the return estimator, is problem that has received significant attention in the literature. vast family of approaches that can be used to solve this problem deeply exploits the Markovian properties of the environment by relying on Temporal Difference [TD,, see, e.g., (Sing) and Sutton 1996, [Sutton] 1988 Lee and He| 2019) Riquelme al. 2019 Qu al. 2019 learning. On the other hand, our work focuses purely on Monte Carlo simulation, which can be transparently applied to Mon-Markovian environments. Another relevant line of work deals with optimizing the
'The uncertainty, in this case, arises both from the noise of the system together with the stochasticity of the initial state distribution.

---

agent's policy to collect data within an environment (i.e.. behavioral policy) to reduce the variance of unbiased estimator for the return of different targer policy [Hanna al. 2017 Zhong et al.)
2022 Mukherjee et al. 2022]. These techniques are referred to as off- off-policy evaluation methods and usually rely on Importance Sampling [e.g, Hesterberg 1988 Owen 2013] techniques to guarantee the unbiasedness of the resulting estimate. However, these studies significantly differ from ours in that, instead of aiming for a behavior policy that reduces the estimator variance, our goal is to directly exploit the properties of Monte Carlo data collection to reduce the on-policy estimator variance.
In the context of RL. exploration bonuses are widely adopted in control (where the goal learning an optimal policy) to tackle the ssporation-explloiee
dilemma [e.g.. Brafman and Tennenholtz] 22002 Zanette and Brunskill
Auer et al. 2008, Tang et al.) 2017 Jin et al. 2018 O' D'onngguue et 2 2019]. Imitialyy when the agent has limited knowledge about the environment, the exploration bonuses drive to explore widely. As the agent's s knowledge improves, the exploration bonuses decrease, and the agent can shift towards exploiting its learned policy more. In our work, instead, we use exploration bonuses to introduce source of robustness w.r.t. the objective function that we are interested in, i.e., the variance of the return estimator for given data collection strategy.
Finally, the work that is most related ours is Poiani et al. 2023 where, the concept of truncating trajectories has been analyzed in the context of Monte Carlo RL. More specifically, the authors derived a non non-adaptive schedule of trajectories that provably minimizes confidence intervals around the return estimator. In this work, on the other hand, we have shown the sub uutoomtmall of pre-determined schedules, and we designed an adaptive algorithm that aims at minimizing the variance of the final estimate. The concept of truncating trajectories has also received some attention in other fields of research such as model-basee
policy optimization [Nguyen al., 20188 Janner et al., 2019 Bhatia et al. 2022 Zhang et al. 2023), multi-task RL [Farahmand et al. [016] and imitation learning [Sun ct al. 2018). However, in all these works, the motivation, the method, and the analysis completely differ w.r.t. what has been considered here. Finally, the concept of truncating trajectories in Monte Carlo RL drew inspiration from a recent work in the field of multi-fidelity bandit [Poiani et al. 2022], where the authors considered the idea of cutting trajectories while interacting with the environment to obtain a biased estimate of the return of a policy in planning algorithms such as depth-fire first search.
7 Conclusions and Future Works
In this work, studied the problem of allocating budget A of transitions in the context of Monte Carlo policy evaluation to reduce the error of the policy expected return estimate. Leveraging the formalism of Data Collection Strategy (DCS) to model how an agent spends its interaction budget, we started by analyzing, in closed form, the variance of an unbiased return estimator for any possible DCS. Our result reveals that DCSs determined prior to the interaction with the environment (e.g.. the usual uniform-in in- thhe-horzoon one and the robust one of Poiani et al. (2023)) fail to satisfy the ultimate goal of policy evaluation, i.c., produce low error estimate. Furthermore. also suggests that algorithms that spend the available budget A iteratively might successfully adapt their strategy to minimize the variance of the return estimator. Inspired by these findings, we propose an adaptive method, RIDO, that, by exploiting information that has already been collected, can dynamically adapt its DCS to allocate larger portion of transitions in time steps in which more accurate sampling is required to reduce the variance of the final estimate. After conducting a theoretical analysis on the properties of the proposed method, we present empirical studies that confirm its adaptivity across a different number of domains, values of budget A, and discount factors 7-
Our study offers exciting possibilities for future research. For example, it would be interesting to extend our ideas to policy search algorithms (c.g.. Williams [992]). ). with the goal of finding DCSs that minimize the variance of the empirical gradient that is adopted in the update rule. Furthermore. we notice that, since our approach is purely based on MC simulation, it does not fully leverage the Markovian properties of the underlying MDP. Combining TD techniques [Sutton and Barto 2018) with mechanisms that truncate trajectories is a challenging and open research question that could lead to further improvements in the efficiency of RL algorithms.
Acknowledgements
This paper is supported by PNRR-PE-AI FAIR project funded by the NexiGeneration EU program.
10

---

References
Peter Auer, Thomas Jaksch, and Ronald Ortner.
Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Jonathan Baxter and Peter I. Bartlett. Infinite-horizon policy-gradinn estimation. Journal of Artificial Intelligence Research, 15:319-350, 2001.
Abhinav Bhatia, Philip Thomas, and Shlomo Zilberstein. Adaptive rollout length for model-based rl using model-free deep rl. arXiv preprint arXiv:2206.022. 02380, 2022.
Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 208-240. Springer, 2003.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213322 2-1,,, 2002.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Karl W Cobbe, Jacob Hilton, Oleg Klimov, and John Schulman. Phasic policy gradient. In Interna- tional Conference on Machine Learning, pages 2020-2027. PMLR, 2021.
Ruth Curtain. Linear-quadratic control: An introduction, 1997.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour, Pac bounds for multi-armed bandit and markov decision processes. In COLT, volume 2, pages 255-270. Springer, 2002.
Amir-massoud Farahmand, Daniel Nikovski, Yuji Igarashi, and Hiroki Konaka. Truncated approx- imate dynamic programming with task-dependent terminal value. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Josiah P Hanna, Philip S Thomas, Peter Stone, and Scott Nickum. Data-efficient policy evaluation through behavior policy search. In International Conference on Machine Learning, pages 1394- 1403. PMLR, 2017.
Timothy Classen Hesterberg. Advances importance sampling. Stanford University, 1988.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. Advances in neural information processing systems, 32, 2019.
Nan Jiang and Lihong Li. Doubly robust off- off-policy value evaluation for reinforcement learning. In International Conference Machine Learning, pages 222-661. PMLR, 2016.
Chi Jin, Zeyuan Allen Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-leaming provably efficient? Advances in neural information processing systems, 31, 2018.
Sham Machandranath Kakade. On the sample complexity reinforcement learning. University of London, University College London (United Kingdom). 2003.
Donghwan Lee and Niao He. Target-based temporal-differenn learning. In International Conference on Machine Learning, pages 3713-3722. PMLR, 2019.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion, 2009.
Subhojyoti Mukherjee, Josiah P Hanna, and Robert D Nowak. Revar: Strengthening policy evaluation via reduced variance sampling. Uncertainty in Artificial Intelligence, pages 1413-1422. PMLR,
2022.
Nhat M Nguyen, Abhineet Singh, and Kenneth Tran. Improving model-based with adaptive rollout using uncertainty estimation. 2018.
Art B Owen. Monte carlo theory, methods and examples. 2013.

---

Brendan O' D'Doogguee, lan Osband, Remi Munos, and Volodymyr Mnih. The uncertainty bellman equation and exploration. In International Conference on Machine Learning, pages 3836-3845, 2018.
Matteo Papini, Matteo Pirotta, and Marcello Restelli. Smoothing policies and safe policy gradients. Machine Learning, pages 1-57,20 2022.
Riccardo Poiani, Alberto Maria Metelli, and Marcello Restelli. Multi-fidelity best-arm identification. Advances in Neural Information Processing Systems, 35:17857-17870, 2022.
Riccardo Poiani, Alberto Maria Metelli, and Marcello Restelli. Truncating trajectories in monte carlo reinforcement learning, 2023.
Doina Precup. Eligibility traces for off off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
Chao Qu, Shie Mannor, and Huan Xu. Nonlinear distributional gradient temporal-different learning. In International Conference on Machine Learning, pages 5251-5260. PMLR, 2019.
Antonin Raffin. RI baselines3 zoo. htttp:://githube com/ htw//rlbaaeeinnnee maes3-nne3--e -000 2020.
Carlos Riquelme, Hugo Penedones, Damien Vincent, Hartmut Maennel, Sylvain Gelly, Timothy A Mann, Andre Barreto, and Gergely Neu. Adaptive temporal-difference learning for policy evalua- tion with per-state uncertainty estimates. Advances in Neural Information Processing Systems, 32, 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pages 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1rX1v:1707.06337, 2017.
Satinder P Singh and Richard Sutton. Reinforcement learning with replacing eligibility traces. Machine learning, 1231-3):123-158, 1996.
Wen Sun, Andrew Bagnell, and Byron Boots. Truncated horizon policy search: Combining reinforcement learning & imitation learning. arXiv preprint 1rXiv:1805.11240, 2018.
Richard S Sutton. Learning to predict by the methods of temporal differences. Muchine learning, 3:
9-44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. exploration: A study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
Philip Thomas and Emma Brunskill. Data-efficient off-police policy evaluation for reinforcement learning. In International Conference on Machine Learning, pages 2139-2148. PMLR, 2016.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026-5033. IEEE, 2012.
Ronald J Williams. Simple statistical gradient algorithms for connectionist reinforcement learning. Machine learning, 8(3):229 256, 1992.
Andrea Zanette and Emma Brunskill. Tighter -eobeemddepeedentt regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
12

---

Junjie Zhang, Jiafei Lyu, Xiaoteng Ma, Jiangpeng Yan, Jun Yang, Le Wan, and Xiu Li. Uncertainty- driven trajectory truncation for model-based offline reinforcement learning. arXiv preprint arXiv:2304.04660, 2023.
Rujie Zhong.
Duohan Zhang, Lukas Schäfer, Stefano Albrecht, and Josiah Hanna. Robust on-policy sampling for data-efficient policy evaluation in reinforcement learning. Advances in Neural Information Processing Systems, 019333366-73388 2022.
13


Reviews:
[{"review_id": "MbxAcfiGuR", "reviewer": "Reviewer_ZDY9", "summary": "* This paper studies online policy evaluation in RL using monte carlo methods.\n* A standard evaluation approach when there is access to a simulator is running rollouts of a given policy with some time horizon, and computing the average return over these. \n* However, this approach for evaluation isn't necessarily optimal, since it may make sense to collect variable length trajectories to evaluate a policy (given that the discount factor downweights future rewards). \n* Closely related prior work to this paper identified that collecting truncated rollouts/trajectories is a policy eval strategy with attractive theoretical properties. \n* However, this prior work proposes a non-adaptive collection strategy that is computed prior to evaluation, based only on the discount factor. This non-adaptive strategy does not work as well in practice (as shown in expts) because it does not adapt to specifics of the problem at hand (for example, the specific nature of the rewards induced by the policy being followed, based on the underlying MDP).\n* The present work proposes a collection strategy for how to adaptively sample trajectories such that one can evaluate the policy with the lowest estimation error. \n* The proposed algorithm proceeds by allocating the total evaluation budget into acquiring minibatches of trajectories with a some starting horizon. Then at each iteration, the algorithm uses the already collected trajectories to compute the number of trajectories to gather at the next horizon length, where this number is deduced based on how to obtain the lowest variance policy evaluation estimate.\n* The paper provides theoretical justification for the proposed algorithm, including that it provably is low variance. \n* In experiments, the proposed algorithm is used to evaluate effective policies in different benchmarks: inverted pendulum, linear quadratic regulator, 2D continuous navigation, and Ant (from Mujoco). When compared to the algorithm from prior work (that precomputes the collection strategy based on the discount factor) and a uniform monte carlo scheme, the proposed method does significantly better.", "questions": "See above.", "limitations": "Limitations  are alluded to but having a subsection/paragraph would be good.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Problem is very well framed and articulated. Examples as to where existing methods fail was very clear\n* Overall notation is easy to understand and well presented, helping to make the contributions clearer\n* Problem tackled is original -- it's clear what gap in the literature that it tackles.\n* To the best of my knowledge (did not go in depth into the proofs), the proposed algorithm is (1) theoretically sound (in terms of variance guarantees) and (2) empirically effective compared to baselines. \n\n", "weaknesses": "* From a writing perspective, it might help to break up big paragraphs of text (particularly in the expts section) -- these are hard to parse. Using bullet points/subsectioning would help a lot to make it easier to read. \n* My main comments on areas to improve are related to experiments:\n   * The evaluation focuses on policies that are optimal, or near-optimal. Can you demonstrate how it performs on more suboptimal policies?\n   * What is the motivation for the specific discount factors chosen in the experiments? Since the discount factor is an important property of the method, can you demonstrate (maybe just for one domain) how the estimation quality varies as a more fine-grained function of the discount factor and evaluation budget? (or maybe at a fixed eval budget, to save computation time).\n   * Similar to above, but related to the horizon length T?\n   * Can you comment on computational cost of running your algorithm instead of the Robust strategy and the Uniform strategy?\n* Small point, but the appendix has a lot of interesting experiments -- would be nice to summarize what these are in the main text (particularly related to ablation on $\\beta$, and additional environment experiments from Mujoco.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **Can you demonstrate (for one domain) how the estimation quality varies as a more fine-grained function of the discount factor**.\n2. **Similar to above, but related to the horizon length T?**\n\nWe thank the reviewer for highlighting these interesting experimental setups. **In the attached PDF, the reviewer can find results for each setting** (experimental setting 1). As suggested by the reviewer, we selected one domain (LQG) and kept the budget fixed. Here, we have used the same policy as for the experiments in the main text. \n\nConcerning (1), we have run the algorithms with $\\Lambda = 3000$ and $T=100$, and different $\\gamma$'s. RIDO outperforms both baselines for any chosen value of the discount factor (and, especially, for values that are significant for the horizon $T=100$). Interestingly, we notice that as the discount factor increases, the sub-optimality of the robust strategy of Poiani et al., 2023 increases as well. Indeed, as $\\gamma \\rightarrow 1$, this DCS tends to the uniform one.    \n\nConcerning (2), we considered $\\Lambda = 1500$, $\\gamma = 0.99$, and different $T$'s. In this case, we notice that for small values of $T$, all methods perform similarly. Indeed, in this case, they all allocate a significant amount of data in the first transition steps (i.e., the most relevant for the LQG and the given policy). Interestingly, as $T$ increases, the sub-optimality of Poiani et al., 2023 and the uniform DCS increases. Focus for a moment on the uniform DCS; in this case, since $\\Lambda$ is fixed, the number of samples allocated to the first interaction steps decreases as $T$ increases. Similar comments also hold for Poiani et al., 2023. However, in this case, the performance decreases more slowly since their DCS implicitly puts more focus on the first interaction steps.\n\nAs a summary, **both experiments strengthen the importance of adapting to the underlying estimation process and highlight the ability of RIDO to reduce the variance of the return estimator**.\n\nTo conclude, similarly to Poiani et al., 2023, the chosen value of the $\\gamma$ we used in the main text where chosen to benchmark the methods against different values of $\\gamma$ that highlight different properties of the methods. \n\n\n3. **Can you demonstrate how it performs on more suboptimal policies?**\n\nWe thank the reviewer for raising this interesting point. The reviewer is correct in mentioning that our evaluation focuses on policies that perform optimal/near-optimal. Nevertheless, in our work, our choice is mainly motivated by the fact that, for these policies, at least for some environments (e.g., LGQ, Navigation), it is possible to provide a straightforward interpretation of the obtained result. \n\nIndeed, we remark that **in the theory we developed, the performance index of the evaluated policy $\\pi$ does not play any role**. Indeed, what matters are variances and covariances of the Markov reward process induced by the policy $\\pi$ on the MDP at hand. From a theoretical perspective, it is indeed easy to construct MDPs and policies that suffer from identical variances for any possible DCSs but whose performance indexes $J$ completely differ. Furthermore, to empirically demonstrate this point, **we included a new set of experiments** (experimental setting 2) on the LGQ domain that the reviewer can find in the attached PDF. More specifically, we propose the evaluation of $3$ different sub-optimal policies:\n- $\\pi_1$: the optimal action is perturbed by an additive Gaussian noise with mean $100$ and std $0.01$. \n- $\\pi_2$: a random policy that samples actions uniformly in [0,1]\n- $\\pi_3$: the optimal action is perturbed by a $0$ mean Gaussian additive noise with std $100$\n    \nThe three considered policies all lead to sub-optimal behaviors. In all cases, however, **RIDO is always competitive against the other baselines, thus confirming the importance of building adaptive DCSs that adapt to the underlying Markov reward process.** To conclude, we notice that these experiments confirm that what matters is not the level of optimality of a certain policy, but only the underlying Markov reward process that is induced on the MDP.\n\n4. **Can you comment on computational cost of running your algorithm?**\n\nTo answer the question, we have made some experiments in which we timed the execution. \n\nMore specifically, we have run all algorithms on Ant and HalfCheetah with $\\Lambda = 4000$ and $T = 500$.  For RIDO we have used a batch size of $b=1000$. For the Ant, RIDO took roughly $27$ seconds, while the baselines $20s$. In the HalfCheetah, RIDO took $23s$, while the baselines $15s$. As soon as we increase $\\Lambda = 8000$ (keeping $b=1000$), we obtain $47s$ for RIDO, and $29s$ for the baselines (Ant). For HalfCheetah, instead, $37s$ for RIDO, and $20s$ for the baselines. At this point, increasing $b=2000$, RIDO obtains $41s$ in the Ant, and $31s$ in the HalfCheetah.  \n\nOverall, RIDO requires some additional computational overheads, however, the running time is still comparable. Furthermore, we also notice that the code of our algorithm has not been specifically optimized for time efficiency. Finally, in our experiments, we rely on open-source solvers available within the cvxpy library. Relying on commercial solvers might increase the computational efficiency.\n\nAll these additional results will be included in the final version of this paper.\n\n5. **It might help to break up big paragraphs of text (particularly in the expts section)**\n6. **The appendix has a lot of interesting experiments -- would be nice to summarize what these are in the main text**\n\nWe thank the reviewer for these suggestions, and we are happy that the reviewer appreciated our additional experiments. Unfortunately, due to space constraints, we had to make some choices in the presentation of our results. Nevertheless, we are happy to take these modifications into account for the final version of our work using the additional page that is available for camera-ready.\n\n"}, {"review_id": "pVL9tge2bw", "reviewer": "Reviewer_scHF", "summary": "This paper studies minimizing the variance of an unbiased policy return estimator that uses trajectories of different lengths, i.e., truncated trajectories. They consider the finite budget setting  of budget $\\Lambda$ transitions. They only consider an unbiased return estimator, and therefore were able to derive a closed-form expression and analyze it for every possible schedule of trajectories. Then, they define the optimal trajectories schedule as the one that attains the minimum variance subject to the available budget constraint. Then they present their algorithm, Robust and Iterative Data collection strategy Optimization (RIDO), which splits its available budget $\\Lambda$ into mini-batches of interactions that are allocated sequentially to minimize an empirical and robust estimate of the variance of the estimator. They derive upper bounds on the variance of the policy return estimator which is of the same order as oracle baseline (under sufficient condition). Finally they empirically validate the performance of RIDO in pendulum, LQG, continuous navigation, and ANT environment.", "questions": "See weakness section.", "limitations": "See weakness section.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1) The problem is well motivated as the problem of data collection adaptively and non-uniformly by truncating trajectories seems relevant.\n2) The proposed solution is analyzed theoretically showing that the upper bounds on the variance of the policy return estimator which is of the same order as oracle baseline .\n3) They provide a computationally feasible solution. First, they show that directly solving the original optimization in (5) id computationally difficult as it is an integer, non-linear optimization problem and use a continuous relaxation to solve it.\n4) They empirically validate their algorithm in several well-known environments.", "weaknesses": "1) The writing needs significant improvement. For example in Figure 2 put the legends in plots. I had to search for the legends. Also the significance of this work compared to [Poiani 2023](https://arxiv.org/pdf/2305.04361.pdf) is not clear. The [Poiani 2023](https://arxiv.org/pdf/2305.04361.pdf)  looks into the same setting but under a non-adaptive data collection strategy. Can the authors should clarify more clearly how this works improve over  [Poiani 2023](https://arxiv.org/pdf/2305.04361.pdf)?\n\n2) Some definitions are missing or confusing. I could not find a formal definition of $\\operatorname{Var}\\left(R_t\\right)$ and $\\operatorname{Cov}\\left(R_t, R_{t^{\\prime}}\\right)$. It will be good to define these quantities formally. Also some definitions are very notation heavy, for example in $\\hat{J}\\_{\\boldsymbol{m}}(\\pi)=\\sum\\_{h=1}^T \\sum_{i=1}^{m_h} \\sum\\_{t=0}^{T-1} \\frac{\\gamma^t}{n_t} R_t^{(i)}$ I am confused between the outer $T$ and inner $T-1$. Can the authors clarify this in detail?\n\n3) After eq (2) it is said that $d_t=\\frac{\\gamma^t\\left(\\gamma^t+\\gamma^{t+1}-2 \\gamma^T\\right)}{1-\\gamma}$ controls the relative importance of samples gathered at round $t$. No further explanation given regarding this. Is there an easy way to understand the implication of this statement?\n\n4) The integer non-linear optimization in (5) and makes sense to me. However, I am concerned with the approach of continuous relaxation of flooring each $\\bar{n}_t^*$ and allocating the remaining budget uniformly. I think this might lead to creeping approximation error. Can the authors justify this approach? Is this standard in literature?\n\n5) One of the main claims by the paper is that their approach adapts to the underlying problem setting.  However, it is not clear from the theorem 4.1 how this shows up in the bound. I could not find and problem dependent complexity parameter in the upper bound of $\\operatorname{Var}_{\\hat{\\boldsymbol{n}}}\\left[\\hat{J}_{\\hat{\\boldsymbol{n}}}(\\pi)\\right]$. Can the authors clarify this?\n\n6) Why no oracle baseline in the experiments? It's a easy way to show how fast RIDO decreases average variance. Also can you describe the key aspects of Robust [Poiani 2023](https://arxiv.org/pdf/2305.04361.pdf) (robust to what?)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the interesting questions and directions for improvements (e.g., clarity).\n\n1. **Can the authors should clarify more clearly how this works improve over Poiani 2023?**\n\nWe will make the legend easily visible in the final version. We now comment on the significance of our work compared to Poiani 2023.\n\n**On Poiani 2023**  \nThe authors propose a **fixed** DCS that is obtained by minimizing confidence intervals around the policy return estimator. Although this DCS has nice statistical properties, it is **computed prior to interacting with the environment**. Consequently, as the usual uniform DCS, it fails to adapt to the peculiarities of the problem at hand and, ultimately, might not produce a low error estimate **We remark that achieving low-error estimates is the usual goal in policy evaluation problems.** \n\n**On the sub-optimality of previous works (contribution 1)**  \nIn our work, we **directly tackle the problem of variance minimization** for policy evaluation. To this end, we first derive, in closed form, the expression of the variance of the return estimator for any DCS (Theorem 3.1). This expression makes a major theoretical contribution to the study of truncating trajectories. Indeed, since it depends on quantities that are unknown to the agent (e.g., variance and covariance), it implies that any pre-determined DCS will fail at minimizing this quantity. Consequently, **it formally shows the sub-optimality of the approach presented in Poiani 2023**.\n\n**On adaptive methods (contribution 2)**  \nWe then exploit Theorem 3.1 to derive an algorithm (RIDO) that **adapts** to the peculiarity of the underlying process. The algorithm enjoys favorable theoretical properties, such as Theorem 4.1, which guarantees that, under favorable conditions, the upper bound on the variance of the return estimator is of the same order as the oracle baseline. As shown by Proposition B.14 and B.15, this result (which required an involved theoretical study) is impossible for the uniform DCS and that of Poiani 2023. \n\n**Experiments (contribution 3)**  \nThe failure of existing and fixed DCSs to adapt to the underlying process has been verified empirically across several domains, values of $\\gamma$ and budget $\\Lambda$. This shows light on the importance of building strategies that directly minimizes the error of the return estimator.  \n\nWe believe that contributions 1, 2, and 3 represent significant advancements (both theoretical and empirical). We will include this in-depth comparison in the final version.\n\n2. **Some definitions are missing or confusing**\n\nWe will add a table in the appendix with the definition of all the symbols used in the paper. \n\nConcerning variances and covariances, we note that $R_t$ is the r.v. we defined in Sec 2 and their symbols are, as usual, w.r.t. to the stochasticity induced by the policy, the transition kernel, and the initial state distribution. Concerning $\\hat{J}(\\pi)$ there is a typo we have now fixed. The correct expression is $\\hat{J}(\\pi) = \\sum_{h=1}^{T} \\sum_{i=1}^{m_h} \\sum_{t=0}^{{\\color{red}\\mathbf{h-1}}} \\frac{\\gamma^t}{n_t} R_t^{(i)}$. As explained in Section 2, the two external summations iterate over the collected trajectories of different lengths the rescaled empirical trajectory return. \n\n3. **Explanation of $d_t$**\n\nIn Eq. 2, $n_t$ always appears for a fixed $t$ in combination with $d_t$, ie $\\frac{d_t}{n_t}$. Thus, for any DCS, $d_t$ directly weighs the reciprocal of the number of samples collected at $t$ (i.e., their relative importance). Finally, since $d_t$ is a decreasing function of $t$, this implies that to minimize Eq. (2), more samples should be allocated to the initial steps.\n\n4. **I am concerned with the approach flooring each and allocating the remaining budget uniformly.**\n\nLemma B.5 shows that this rounding strategy introduces only a constant multiplicative factor of 2 in Theorem 4.1. A similar argument is also used in Poiani 2023. However, this kind of reasoning (Lemma B.5) exploits the structure of the specific objective function. Thus, using this reasoning within the analysis is problem-dependent and has to be studied case by case. \n\n5. **I could not find and problem dependent complexity parameter in the upper bound**\n\nWithin our context, the problem lies in learning a DCS that can successfully minimize the variance of the return estimator. In this sense, the most relevant problem-dependent quantity for our setting is the **variance of the return estimator under the optimal DCS** defined as in Eq. (4), ie $\\mathrm{Var}_{n^*}[\\hat{J}]$.\n\nThis quantity captures the problem-dependent features of the underlying process induced by the policy $\\pi$ on the MDP. For these reasons, the effort behind Theorem 4.1 is in deriving an upper-bound that directly depends on $\\mathrm{Var}_{n^*}[\\hat{J}]$. Since the optimal DCS does not admit a closed-form expression retrieving this sort of result requires significant technical effort.\n\n6. **Why no oracle baseline? Can you describe the key aspects of Poiani 2023?**\n\nWe note from Eq. 4 that computing the oracle baseline requires (i) exact knowledge of Var and Cov at each $t$ and (ii) solving an NP-hard problem. Concerning (i), in the settings we consider, this information is not available. One might object that it is possible to estimate Var and Cov using a large amount of data and then use such estimates to build the oracle. However, (a) this still requires solving an NP-hard problem, and (b) to avoid introducing correlation between different runs, the estimation of Var and Cov and the computation of the NP-hard problem should be repeated for each run, environment, and value of the budget. To conclude, this baseline is not present because it is not available / cannot be computed efficiently.\n\nKey aspects of Poiani 2023 were remarked in point 1. \"Robust\" is the name we have chosen to denote their DCS since their schedule comes with tighter confidence intervals w.r.t. the uniform DCS. "}, {"review_id": "VI242ectqE", "reviewer": "Reviewer_ccYJ", "summary": "This paper tackles the problem of optimally allocating data in Monte Carlo policy evaluation.\nIt proposes an adaptive approach for setting trajectory lengths.\nBuilding on the Data Collection Strategy (DCS) [Poiani et al. 2023], the authors derive a closed-form variance of an unbiased estimator of the on-policy return. It reveals that a uniform horizon is sub-optimal, and that the optimal method should allocate data adaptively taking into account the variance of the reward, and the covariance of the rewards across time steps. \n\nThe authors develop an algorithm, RIDO, which optimizes the DCS based on the data. \nThe original optimization problem,  a nonlinear integer problem, is transformed into a linear continuous optimization problem that preserves the optimal solution. \nFurther, an upper bound is established for the variance estimated by RIDO.\nThe experimental results validate the efficacy of RIDO, demonstrating that it outperforms the non-adaptive approach proposed by Poiani et al. 2023.\n", "questions": "Please refer to the discussion in the weakness section.", "limitations": "The authors discussed the limitations in Section 6. \nHowever, as outlined in the weaknesses section, there are additional limitations that are not addressed in the paper.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The adaptive Data Collection Strategy is well-motivated \n- The paper presents solid theoretical analysis, which aligns well with the synthetic examples.\n- The experimental results, including comprehensive ablations, validate the efficacy and robustness of the approach (though there is a concern as noted in the weakness section).\n", "weaknesses": "My primary concern lies in the comparison made with the non-adaptive approach from Poiani et al. (2023). The presentation of the comparison is such that it obscures the contributions of the adaptive strategy proposed in this paper. It would be beneficial if the authors could clarify the following points.\n\n1. Theoretical Analysis: Theoretical analysis of the non-adaptive approach was performed for both on-policy and off-policy settings in the referenced work. However, the current paper only provides an analysis in the on-policy setting. Are there specific challenges that preclude analysis in the off-policy setting for the proposed method?\n\n2. Application Scope: In addition to policy evaluation, the non-adaptive approach was applied to policy optimization settings in Poiani et al. (2023). They even developed an algorithm and performed experiments for the latter. However, the current paper does not address the policy optimization setting at all, which reduces its comprehensiveness.\n\n3. Evaluation Environments: Poiani et al. (2023) evaluated their non-adaptive approach in three primary environments (Dam, Reacher, and Supply Chain) and included two additional environments in their appendix specifically for policy evaluation. For an effective comparison of the two approaches, it would be logical to test the proposed method in these same environments. However, the authors evaluated their approach in four different environments that do not overlap with those used in the previous work, making it challenging to accurately assess the contribution of their work.\n\nAnother concern is regarding the performance of the adaptive approach, on the discrepancy between the theory and experiment result as seen in example 1 (Fig. 4). \nAs noted in the paper, the DCS returned by the proposed approach incorrectly allocates more data towards the beginning of episodes and also does not exhibit a preference for a smaller batch size, contradicting the theory. Although the paper attributes this discrepancy to potential numerical instabilities, it is concerning, particularly as it occurs in one of the two illustrative examples. Also, in the limiting case where gamma approaches 1, the non-adaptive approach would return a uniform DCS as suggested by Poiani et al. (2023), thereby outperforming the adaptive approach.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **Theoretical Analysis: Are there specific challenges that preclude analysis in the off-policy setting for the proposed method?**\n\nWe thank the reviewer for touching upon this point. Extending our result to the off-policy setting requires significant and non-trivial effort, and represents an exciting line for future research. One of the main issues lies in deriving an equivalent of Theorem 3.1 (i.e., deriving a closed-form expression of the variance as a function of $\\boldsymbol{n}$ that holds with equality). Indeed, the importance sampling weights that would appear within the equations, significantly complicate dealing analytically with variances of the truncated returns. Indeed, they would become variances of importance-weighted truncated returns rather than variances of truncated returns.\n\nWe notice that, in Poiani et al., 2023, dealing with confidence intervals for the off-policy case required simple modifications w.r.t. the proofs of the on-policy setting. Analytically, this is simpler since the confidence intervals that they developed rely on *upper bounds* on the variance of the truncated returns (the reviewer can refer to the proof of Theorem B.15 in Poiani et al., 2023). These reasonings, however, cannot be applied to the more complex problem of variance minimization. Indeed, as soon as we upper-bound such quantities, we implicitly lose the adaptivity w.r.t. the underlying Markov reward process (i.e., we are no longer aiming at minimizing the variance). This is, indeed, one significant technical challenge behind our analysis.\n\n2. **Application Scope: the current paper does not address the policy optimization setting.**\n\nThe reviewer is correct in stating that we do not tackle the policy optimization setting. Our work's focus lies in the policy evaluation problem; i.e., **the optimization aspect is outside the scope of the current work**. We remark that policy evaluation represents, in itself, a fundamental problem of Reinforcement Learning. Furthermore, it is also a key component in several RL algorithms that uses policy evaluation as a building block. Therefore, since our theoretical effort directly tackles this relevant problem, we preferred to disentangle the contribution by presenting experiments that tackle the evaluation setting. We do believe that theoretical and empirical advancements in the performance of policy evaluation algorithms are of interest to the community.\n\n3. **Evaluation Environments: Poiani et al. (2023) evaluated their non-adaptive approach in three primary environments (Dam, Reacher, and Supply Chain).**\n\nWe thank the reviewer for proposing this experimental setting. **The reviewer can now find in the attached PDF the performance of RIDO, Poiani et al., 2023, and the uniform DCS across the Dam, Reacher and Supply Chain** (experimental setting 3). As the reviewer can verify, all the comments made in the main text also directly extend to these situations. In other words, **our results confirm (i) the importance of building DCSs that can adapt to the underlying structure of the estimation process and (ii) the ability of RIDO to achieve low variance estimates thanks to its adaptivity**.\n\nTo conclude, we take the chance to remark that further experiments and domains are already presented in the appendix (i.e., HalfCheetah and Swimmer). To summarize, we have experimented on 1) several MuJoCo environments (i.e., Ant, HalfCheetah, Swimmer, Reacher), 2) Operation Research environments (Dam and Supply Chain), 3) Control-theory benchmarks (LQG), 4) Navigation environments.\n\nWe will include these results in the final version of the manuscript.\n\n\n4. **Another concern is regarding the performance of the adaptive approach in example 1 (Fig. 4).**\n\nWe hope that the following discussion can solve the doubts raised by the reviewer. \n\n**On the numerical instabilities**\nWe have verified that that are indeed numerical instabilities within the convex solver. To verify this point, we have run the optimization procedure with $T=5$ and the various $f_t$ equal to $(0, 0, 0, 0, 1)$. In this context, with a budget $\\Lambda = 200$, the optimal allocation is clearly $(40, 40, 40, 40, 40)$ (i.e., the uniform strategy). Nevertheless, the solution returned by the optimizer sometimes contains values of $(40.00000192, 40.0000002, 39.99999935, 39.99999878, 39.99999836)$. When flooring, the values shink down to $(40, 40, 39, 39, 39)$, and, allocating the remaining budget uniformly, we obtain $(41, 41, 40, 39, 39)$. Therefore, by increasing the number of iterations, this effect will be reduced since this rounding effect appears less frequently. Nevertheless, we notice that with our rounding strategy, the resulting DCS changes at most by a factor of $1$. As a consequence, for instance, by keeping the ratio $\\Lambda/b$ constant, and increasing the budget $\\Lambda$ the difference in performance nullifies. Finally, we remark that this is not a weakness of our method, but it only depends on the implementation of the open-source convex solver we used.  \n\n**On $\\gamma = 1$ in Example 1**\nFinally, concerning the fact that when $\\gamma \\rightarrow 1$, the reviewer is correct in stating that Poiani et al., 2023 would be uniform and thus optimal in Example 1. However, the main benefit of building adaptive strategies is that they can indeed adapt to the underlying Markov reward process. Indeed, if we consider the opposite case in which the reward is gathered only in the first step (Example 2), the uniform strategy is the DCS with the worst possible variance. RIDO, on the other hand, as shown across several environments, can adapt to the underlying domain.  \nThus, we believe that this phenomenon is an acceptable price to be paid for obtaining the adaptivity of the approach.\n"}, {"review_id": "dtKLdLWLNy", "reviewer": "Reviewer_Fu4w", "summary": "This work proposed a new Monte Carlo (MC) policy evaluation scheme that can adaptively decide the length of the trajectories being sampled.\nThe authors claim this approach can reduce the variance of the final estimate given a fixed interaction budget.\nThis work is primarily theoretical but they also have some empirical validation on a set of continuous control tasks.", "questions": "In Figure 2, top right corner, the Ant experiment with $\\gamma$=0.999 RIDO has a similar performance with the baselines. This is somewhat alarming to me. Because one can interpret this as RIDO only bring benefits for easier tasks. Do you have alternative interpretations or further experiments?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* This work focuses on a rather fundamental problem of reinforcement learning, that is, MC-based policy evaluation. While such methods have been deprecated for quite a while in most RL algorithms, recently, they've been applied again in some sequence modelling methods. So if this approach indeed works well, it can bring benefits to a wide spectrum of downstream algorithms.\n* The write-up of the paper is clear.\n", "weaknesses": "* This paper lacks a related work section. MC estimation for a fixed policy is, for example, relevant to the Markov Chain literature. It's hard to believe there is no related work at all.\n* To apply this approach, some additional assumptions should be made. So the major one is we can actually terminate the episode and use the \"budget\" to restart a new episode. Another one is the initial states should be similar if not exactly the same. These assumptions can undermine the practical value of the proposed method.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **This paper lacks a related work section. MC estimation for a fixed policy is, for example, relevant to the Markov Chain literature. It's hard to believe there is no related work at all.**\n\nWe remark that Appendix A presents and discusses several works that are related to ours. For the sake of presentation, in the main text, we have chosen to delve more deeply into the details of the paper (i.e., Poiani et al., 2023) that bears the closest resemblance to the work we presented.\n\nConcerning Monte Carlo Chain, they are discussed within the work \"Monte Carlo Theory, methods and examples\" Owen 2013, which we cite in our work. We will include additional book references on Markov Chains (e.g., \"Markov Chain and Mixing Times\", Levin and Peres, 2017) in the related work section. Nevertheless, to the best of our knowledge, we are not aware of adaptive approaches that are based on truncating trajectories.\n\n\n\n2. **To apply this approach, some additional assumptions should be made. So the major one is we can actually terminate the episode and use the \"budget\" to restart a new episode. Another one is the initial states should be similar if not exactly the same. These assumptions can undermine the practical value of the proposed method.**\n\nWe thank the reviewer for touching upon these points. In the following, we address each of the limitations raised by the reviewer. We hope that the following discussion can solve the points raised by the reviewer. \n\n- *\"The major one is we can actually terminate the episode and use the \"budget\" to restart a new episode\"*  \nAs mentioned in the introduction, the availability of the simulator that can be exploited to reset the environment, is at grounding core of the entire strand of Reinforcement Learning algorithms that rely on Monte Carlo (MC) simulation to estimate performance/gradients on the task being solved. Despite the availability of alternative methods, like Temporal Difference (TD) ones, which do not necessitate a reset option, a significant number of successful RL approaches continue to depend on MC evaluation (e.g., policy search methods). Indeed, MC-based approaches can be easily applied to non-Markovian environments (which are frequently encountered in real-world domains). This peculiar and favorable property of MC-based methods is directly inherited by our method as well; indeed, although, for simplicity, we formalized the setting using the MDP tool, **our method and all the derived theoretical results do not require a Markovian transition model**.\n- *\"Another one is the initial states should be similar if not exactly the same\"*  \n**Our algorithm, the whole theoretical analysis, and the experiments do not require this assumption**. Indeed, all the expectations (and, consequently, also variances and covariances) are taken w.r.t. the stochasticity of the policy, the transition kernel, and the initial-state distribution. We notice, furthermore, that in all the standard benchmarks (e.g., Pendulum, MuJoCo), the reset method that is available within the classical environments has not been modified (i.e., each time a new trajectory begins, the initial state is sampled according to the random initial distribution of the corresponding domain). \n\n3. **In Figure 2, top right corner, the Ant experiment with =0.999 RIDO has a similar performance with the baselines. This is somewhat alarming to me. Because one can interpret this as RIDO only bring benefits for easier tasks. Do you have alternative interpretations or further experiments?**\n\nYes, we do have alternative interpretations and, also, further experiments.  \n\nWe first proceed with the interpretation. We notice that the performance metric of each algorithm is the variance of the return estimator (i.e., Equation (3)). Equation (3) only depends on the underlying Markov reward process induced by policy $\\pi$ in the MDP at hand. Consequently, the performance metric is **not affected** by the complexity of the domain and by how difficult it is to learn a good policy within the environment.\n\nFor the sake of clarity, consider the 2D Navigation domain we presented in the main text. The same environment could be replaced with one whose state-space are images taken from a camera. Nevertheless, if the reward function remains unchanged and the agent still deploys the same policy, the underlying Markov reward process would be the same, and the performance of all algorithms would be left unchanged.\n\nConcerning the experiments, instead, in the attached PDF, the reviewer can see that RIDO outperforms all methods in the Reacher domain with $\\gamma=0.999$, and significantly outperforms the robust schedule of Poiani et al., 2023 in the Swimmer domain for $\\gamma=0.998$ (Figure 8 in the Appendix), and also in the Supply Chain for small values of $\\Lambda$ (whose state space dimension is $33$, more than the Ant, that is $27$-dimensional)"}, {"review_id": "7295MeXljo", "reviewer": "Reviewer_Acm2", "summary": "This paper looks at the problem of designing truncated trajectory lengths to be used in policy evaluation in a reinforcement learning context. It builds on the work [R. Poiani, A. M. Metelli, & M. Restelli, _Truncating Trajectories in Monte Carlo Reinforcement Learning_, ICML 2023], which, instead of using the fixed trajectory lengths that are common in practice, provides a trajectory length selection scheme to minimize confidence interval width around empirical estimates of the expected return of a policy. The paper under review proposes an alternative scheme for selecting trajectory lengths, called RIDO, that focuses on minimizing the variance of the reward estimate. Unlike [Poiani et al., 2023], the proposed scheme is adaptive in the sense that it divides the total interaction budget into mini-batches and iteratively selects intra-batch trajectory length schemes to minimize running estimates of the reward estimate variance. Challenging proxy optimization problems for performing trajectory length sequences are formulated, a transformation to a tractable problem is given, and theoretical results are provided assuring that the resulting reward estimate variance is upper bounded by the best-case reward estimate variance plus error terms that decay as $O(1/\\Lambda)$, where $\\Lambda$ is the interaction budget. Experimental results are provided indicating that the proposed method achieves lower variance than fixed-length trajectory schemes and the selection scheme proposed in [Poiani et al., 2023].", "questions": "* Why is your estimator (1) unbiased? In general, such a finite-horizon approximator will be biased due to the infinite-horizon setting under consideration (this is acknowledged in footnote 3 on page 3). The unbiasedness statement appears to be inherited from [Poiani et al., 2023], but it would be helpful to see this made explicit in the current paper, since it is critical for the rest of the analysis.\n* What is the effect of policy selection on performance of RIDO versus [Poiani et al., 2023]'s method? You appear to have considered optimal policies when performing policy evaluation. What differences might we expect to see when evaluating policies encountered during training, for example?\n* What are the main challenges to using RIDO to perform policy evaluation in a policy search scheme?", "limitations": "The authors have adequately addressed the limitations of the present work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The general topic of the paper is timely and well-motivated, as truncating trajectories to make more efficient use of a limited interaction budget is an important problem with many applications. The proposed adaptive scheme, RIDO, provides another tool for deciding trajectory lengths in addition to that from [Poiani et al., 2023], and the new adaptive scheme appears to provide advantages in certain types of problems (e.g., with delayed rewards). The objectives of the problem formulations (see equations (4) and (5)) provide interesting alternatives to the objective considered in [Poiani et al., 2023], and the convex reformulation of problem (5) and the corresponding analysis in the appendix (which I skimmed, but did not check thoroughly) behind Theorem 4.1 are fairly involved. Finally, the experiments indicate that RIDO enjoys some advantages over that of [Poiani et al., 2023] in terms of return estimate variance minimization.", "weaknesses": "I have some concerns about the clarity and significance of this work. Specific concerns include the following:\n* Though the proposed method provides an alternative to the selection scheme of [Poiani et al., 2023], aside from the intuitive examples provided on lines 155-158 and the experiments in Figure 2, it remains unclear from the main paper why RIDO is either convincingly superior or on precisely what classes of problems it should be preferred. It seems likely that the ambiguity is due to the fact that the objectives considered in both are closely related: in [Poinani et al., 2023], the objective is to minimize confidence interval width (defined in terms of variance via standard deviation) for the estimated return; in the present work, the objective is to minimize variance of the return estimate. Both objectives seek lower variance.\n* In light of the foregoing, a theoretical comparison of the two methods would be very helpful in determining their fundamental differences, but this is absent in the main paper (though Proposition B.15 in the appendix does provide some insight). In addition, the experimental results do suggest that RIDO enjoys lower variance on some problems, but much of the time RIDO and [Poinani et al., 2023]'s method appear to experience roughly the same variance. A more in-depth analysis of the differences between the two methods could reveal the issue here. Inclusion of Proposition B.15 and an expand discussion in the main paper may be helpful in this regard.\n\nIt is possible that with additional clarification/expansion the above issues can be resolved. In it's current form, however, its precise contribution, significance, and potential impact remain unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **I have some concerns about the clarity and significance of this work**\n\nIn the following, we discuss the concerns raised by the reviewer. We hope that the following clarification can solve the raised doubts.\n\nIt is of primary importance to remark that a crucial difference between our work and Poiani et al., 2023 lies in the metric used while building alternative DCSs. Indeed, while Poiani et al., 2023 seek strategies that minimize confidence intervals, we directly tackle the more involved problem of variance minimization in our work. In this sense, **minimizing confidence intervals around the return estimator is not equivalent to minimizing the variance**. Indeed, while minimizing confidence intervals can be interpreted as minimizing a worst-case variance (i.e., an upper bound on the actual variance), in our work, we aim to build DCSs that minimize the actual variance. In other words, **we aim to minimize the estimator's error, which is the usual goal in policy evaluation problems.** \n\n\nFurthermore, we notice that the difference in the chosen metric has a crucial implication in the context of truncating trajectories. Indeed, as a direct consequence of minimizing confidence intervals, **the resulting DCS of Poiani et al., 2023 is fixed prior to interacting with the environment.** Nevertheless, as we show in Theorem 3.1, **any schedule that is fixed apriori fails at minimizing the variance of the return estimator**. This formally shows the sub-optimality of prior work. In other words, **the schedule of Poiani et al., 2023 does not seek for lower variance** (i.e., it does not minimize the estimator's error). RIDO, on the other hand, takes the results of Theorem 3.1 directly into account, and it aims at building an adaptive schedule that minimizes the estimators' error. \n\n\nConcerning the experiments, the fact that Poiani et al., 2023 fails at minimizing the error of the estimator is evident. Indeed, we notice **Poiani et al., 2023 underperforms significantly RIDO** in all the following cases:  LQG ($\\gamma=0.99$), in the Navigation (both $\\gamma=0.99$ and $\\gamma=0.95$), in the Swimmer (Appendix, both $\\gamma=0.998$ and $\\gamma=0.99$ and $\\gamma=0.998$), in the Reacher (see attached PDF, $\\gamma=0.999$), in the Supply Chain for small values of $\\Lambda$ (see attached PDF, $\\gamma=0.999$), in the Dam (see attached PDF, $\\gamma=0.95$), which are a significant amount of domains. **This sub-optimality is directly dependent on the fact that Poiani et al., 2023 do not seek lower variance by adapting to the feature of the underlying Markov reward process but naively deploys a pre-determined DCS.**\n\n2. **Why is your estimator (1) unbiased?**\n\nWe notice that what we state in Section 2 is that Estimator (1) is an unbiased estimate of $J(\\pi) = \\mathbb{E} [ \\sum_{t=0}^{T-1} \\gamma^t R_t]$, i.e., the discounted sum of rewards up to time $T$. As the reviewer suggests, and as we state in our paper, this still introduces a bias w.r.t. the infinite horizon MDP model. Nevertheless, for sufficiently large $T$, this bias is at most $\\epsilon$. This procedure, which is commonly adopted in the literature (e.g., \"Truncating Trajectories in Monte Carlo Reinforcement Learning, Poiani et al., ICML, 2023, \"Smoothing Policies and Safe Policy Gradients\" Papini et al., Machine Learning, 2022), serves to justify the approximation of the infinite horizon MDP model with a finite horizon one. \n\nTo conclude, we take the chance to remark that our study directly extends to the finite horizon setting, and particularly the case $\\gamma=1$. Poiani et al., 2023 did not consider the $\\gamma=1$ case.\n\n3. **What is the effect of policy selection on performance of RIDO versus [Poiani et al., 2023]'s method? What differences might we expect to see when evaluating policies encountered during training, for example?**\n\nWe thank the reviewer for raising this interesting point. Reviewer ZDY9 has asked to experiment with sub-optimal as well. Therefore, we defer the reviewer to our in-depth response to Reviewer ZDY9 (see point 3). In short, **in the theory we developed, the performance index of the evaluated policy does not play any role**. Indeed, what matters are variances and covariances of the Markov reward process induced by the policy on the MDP at hand. We have also verified this point empirically in a new set of experiments. \n\nGiven the discussion we presented (see Reviewer ZDY9) and the additional experiments, what happens in policies encountered during training only depends on the variance and covariances of the underlying Markov reward process, which is entirely problem dependent. RIDO, for all policies and MDPs, will always seek to truncate trajectories to minimize the estimation error. Other pre-determined DCSs, instead (e.g., uniform and Poiani et al., 2023), will blindly allocate trajectories according to some fixed schedule that ignores the underlying structure of the problem. \n\n\n4. **What are the main challenges to using RIDO to perform policy evaluation in a policy search scheme?** \n  \nFirst of all, we notice that, in principle, any data collection strategy can be employed in any policy search scheme. Nevertheless, we notice that extending an algorithm to properly incorporate a new DCS is algorithmic dependent. Indeed, consider the case of POIS (\"Policy Optimization via Importance Sampling\", NeurIPS 2018) that has been extended in Poiani et al., 2023 for their robust DCS. In that case, the extension required proving a theorem to properly incorporate the new DCS within the loss function. For some simple algorithms, such as Cross-entropy methods, any DCS can be incorporated directly to evaluate each candidate in the population using the Estimator of Equation (3). For more complex ones (e.g., POIS), the problem can involve some effort, that, however, depend on the algorithm at hand. "}]

Author rebuttal:
We thank the reviewers for their effort in reviewing our paper. We are happy that the reviewers have recognized that "the problem tacked is original" (Reviewer ZDY9) and "well-motivated" (Reviewer scHF, ccYJ, Acm2), that the "limited interaction budget is an important problem with many applications" (Reviewer Acm2), that the paper presents "solid theoretical analysis" (Reviewer ccYJ), and the method is "empirically effective against the baselines" (Reviewer ZDY9). In the following, we address the concerns raised by the reviewers.

We attach a PDF containing additional experiments that were requested by Reviewer ZDY9 and ccYJ.

Meta-review: Monte Carlo policy evaluation is a fundamental problem in RL and this paper studies how it can be made more data efficient by adaptively truncating trajectories. The key novelty is to estimate the variance of the reward at different time-steps and adaptively set the sample budget per time-step to focus on acquiting more samples at time-steps where variance is high. Theoretical and numerical studies show the benefit of this approach compared to a fixed horizon truncation scheme or not truncating. 

Main strengths: Given the fundamental importance of the Monte Carlo estimator to RL, this paper makes a contribution that could have widespread impact in different RL methods. The work proposes a novel method (adaptive trajectory truncation) and provides theoretical analysis of its benefits and policy evaluation experiments showing a reduction in mean squared error. Overall the combination of theoretical and empirical analysis is strong.

Main concerns: Main concerns about the paper were 1) how novel it was relative to a paper from earlier this year on non-adaptive trajectory truncation and 2) the fact that the method relies on a "reset" function which is an unrealistic assumption in many real world settings. A minor comment is that in the camera ready I would encourage the authors to discuss related work in the main paper body as I had questions about novelty initially that the section that is currently in the appendix helped clarify. Another reviewer also had this concern.

Overall the paper presents a novel method with intuitive justification, theoretical analysis of potential benefit, and empirical analysis complementing theory. While a couple of limitations are noted, I believe the paper is sufficiently novel relative to the older work and, even if many RL environments lack reset functions, there are also many environments where resets are practical. The widespread use of Monte Carlo sampling in RL means the work has potential broad impact and so I recommend acceptance.
Decision: Accept (poster)