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 propose as a quality index a surrogate of the mean squared error of a return estimator that uses trajectories of different lengths, i.e., \emph{truncated}. Specifically, this surrogate shows the sub-optimality of the fixed-length trajectory schedule. Furthermore, it suggests that adaptive data collection strategies that spend the available budget sequentially can allocate a larger portion of transitions in timesteps in which more accurate sampling is required to reduce the error of the final estimate. Building on these findings, we present an adaptive 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 version of the surrogate of the estimator's error. 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.
Paper
Similar papers
Peer review
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].
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: * 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. * 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. It 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.
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. * 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? * What are the main challenges to using RIDO to perform policy evaluation in a policy search scheme?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
The authors have adequately addressed the limitations of the present work.
Summary
This work proposed a new Monte Carlo (MC) policy evaluation scheme that can adaptively decide the length of the trajectories being sampled. The authors claim this approach can reduce the variance of the final estimate given a fixed interaction budget. This work is primarily theoretical but they also have some empirical validation on a set of continuous control tasks.
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. * The write-up of the paper is clear.
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. * 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.
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?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
Yes.
Summary
This paper tackles the problem of optimally allocating data in Monte Carlo policy evaluation. It proposes an adaptive approach for setting trajectory lengths. Building 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. The authors develop an algorithm, RIDO, which optimizes the DCS based on the data. The original optimization problem, a nonlinear integer problem, is transformed into a linear continuous optimization problem that preserves the optimal solution. Further, an upper bound is established for the variance estimated by RIDO. The experimental results validate the efficacy of RIDO, demonstrating that it outperforms the non-adaptive approach proposed by Poiani et al. 2023.
Strengths
- The adaptive Data Collection Strategy is well-motivated - The paper presents solid theoretical analysis, which aligns well with the synthetic examples. - 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).
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. 1. 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? 2. 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. 3. 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. Another 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). As 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.
Questions
Please refer to the discussion in the weakness section.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
The authors discussed the limitations in Section 6. However, as outlined in the weaknesses section, there are additional limitations that are not addressed in the paper.
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.
Strengths
1) The problem is well motivated as the problem of data collection adaptively and non-uniformly by truncating trajectories seems relevant. 2) 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 . 3) 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. 4) 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)? 2) 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? 3) 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? 4) 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? 5) 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? 6) 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?)?
Questions
See weakness section.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
See weakness section.
Summary
* This paper studies online policy evaluation in RL using monte carlo methods. * 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. * 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). * Closely related prior work to this paper identified that collecting truncated rollouts/trajectories is a policy eval strategy with attractive theoretical properties. * 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). * 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. * 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. * The paper provides theoretical justification for the proposed algorithm, including that it provably is low variance. * 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.
Strengths
* Problem is very well framed and articulated. Examples as to where existing methods fail was very clear * Overall notation is easy to understand and well presented, helping to make the contributions clearer * Problem tackled is original -- it's clear what gap in the literature that it tackles. * 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.
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. * My main comments on areas to improve are related to experiments: * The evaluation focuses on policies that are optimal, or near-optimal. Can you demonstrate how it performs on more suboptimal policies? * 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). * Similar to above, but related to the horizon length T? * Can you comment on computational cost of running your algorithm instead of the Robust strategy and the Uniform strategy? * 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.
Questions
See above.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Limitations are alluded to but having a subsection/paragraph would be good.
Thank you for your response!
I thank the authors for their detailed response -- These answer my questions!
Thank you!
We thank the reviewer for the acknowledgement. We are happy that all questions have been answered. The Authors.
Response to the rebuttal
I want to thank the authors for their rebuttal. Some of my questions have been addressed. I don't really buy the argument against the additional assumptions though. > As 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 I agree the idea of exploiting reset is an interesting one. But the need for a reset function can also be a huge burden if we want to apply RL in the physics world, or digital world with enough complexity. > 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). Sure, but these environments only have a Gaussian noise added to the initial state. How about Procedurally generated environments or, say, RLHF settings where the initial states are drastically different? I don't have enough expertise to tell the author's rebuttal on the theoretical results so I'll take their words for now. In general, I think this is an interesting work but unsure about its practical value. I'll keep the scores.
Additional Clarifications
We thank the reviewer for the answer, and we are glad that some concerns have been addressed. In the following, we present additional clarifications that we believe solve the remaining doubts. 1. **I agree the idea of exploiting reset is an interesting one. But the need for a reset function can also be a huge burden if we want to apply RL in the physics world, or digital world with enough complexity.** Although we agree with the reviewer that our study exploits a reset function, we remark that **this assumption is necessary and employed by a large number of works published at top-tier venues**. Here, we list a few (but many more could be cited) - "Simple statistical gradient-following algorithms for connectionist reinforcement learning", Williams, Machine Learning, 1992 - "Infinite-horizon policy-gradient estimation", Baxter and Barlett, Journal of Artificial Intelligence, 2001 - "Policy Optimization via Importance Sampling", Metelli et al., NeurIPS 2018 - "Importance Sampling Techniques for Policy Optimization", Metelli et al., JMLR, 2020 - "Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection", Papini et al., NeurIPS 2021 - "Kernel-Based Reinforcement Learning: A Finite-Time Analysis", Domingues et al., ICML, 2021 - "Confident Approximate Policy Iteration for Efficient Local Planning in $q^\pi$-realizable MDPs", Weisz et al., NeurIPS 2022 - "Smoothing policies and safe policy gradients", Papini et al., Machine Learning 2022 - "Truncating Trajectories in Monte Carlo RL", Poiani et al., ICML 2023 More generally, we remark that **both the policy search literature and the finite-horizon RL setting largely rely on the reset function**, (please, notice that our work, both theory and algorithms, extends as-is to the finite horizon setting as well; we have also experiments in the appendix that show the empirical success of RIDO in the setting in which $\gamma=1$). Finally, we mention that **many RL success stories relied on a simulator to achieve significant results across a broad spectrum of applications** (e.g., "Mastering the game of Go with deep neural networks and tree search", Silver et al., 2016, "A cooperative multi-agent reinforcement learning framework for resource balancing in complex logistics network", Li et al., AAMAS 2019, "Cooperative Policy Learning with Pre-trained Heterogeneous Observation Representations", AAMAS 2021, "Hindsight Learning for MDPs with Exogenous Inputs", Sinclair et al., ICML 2023; but many mores could be cited). **For all these reasons, we believe that the setting is of interest to the community.** 2. **Sure, but these environments only have a Gaussian noise added to the initial state. How about Procedurally generated environments or, say, RLHF settings where the initial states are drastically different?** **Our LQG experiment provides an example of an environment where initial states drastically differ.** More precisely, as the reviewer can verify in Appendix C.1, the initial state is sampled uniformly between $[-80, 80]$. Notice that, under the optimal policy considered in the main text, **this leads (for each distinct trajectory) to significantly different states, actions, and rewards in the first interaction steps.** This, in turn, generates significant stochasticity (i.e., variances) in the rewards of the initial interaction steps, which **are directly taken into account by RIDO**. Indeed, we notice that **RIDO is, significantly, the algorithm with the highest performance in this scenario.** This behavior is a direct consequence of the fact that all expectations are taken (also) w.r.t. the stochasticity of the initial state distribution. Indeed, since RIDO discovers the high variance of the rewards in the initial interaction steps, it successfully allocates more portion of the budget to estimate their rewards. To conclude, **both theoretical and empirical evidence support our claim: our work does not rely on this assumption**.
Thanks for your thorough response. Part 1 of your response clarified the merits of RIDO over existing methods, particularly that of [Poiani et al., 2023], which was my main concern. Parts 2 through 4 also provided useful additional context/clarification, and I have increased my score accordingly. Regarding part 1, I agree variance is technically distinct from previous objectives, the theoretical results provide support for why we might prefer RIDO, and the experiments illustrate that RIDO often outperforms previous methods w.r.t. minimizing variance. That said, I still highlight that RIDO and [Poiani et al., 2023] experience about the same variance on several domains -- I continue to think that this is due to the fact that minimizing confidence interval width is closely related to minimizing variance, and it again raises the question: on what classes of problems should RIDO be preferred over previous methods? I hope this can be addressed in the revision or future work.
Additional Clarification
We thank the reviewer for the response. We are glad that the main concern has been addressed and that the reviewer increased the score. We now follow up the reviewer's question to clarify the remaining doubt. We hope that the following can show further lights on the contributions of our work. In policy evaluation problems, where the **goal is obtaining a low error estimate** of the policy return, Theorem 3.1 clearly shows that the optimal DCS directly depends on the underlying Markov reward process induced by policy $\pi$ on the MDP at hand. As a direct consequence, to minimize the estimation error, **an algorithm with adaptivity properties is required in order to fulfill this goal**. At this point, we remark that RIDO shows the aforementioned adaptivity property both theoretically and empirically. The other available DCSs **(Poiani et al., 2023 and the uniform DCS) fail in being adaptive by definition.** In other words, since the agent is not aware of the underlying Markov reward process before interacting with the environment, **RIDO should be preferred to minimize the estimation error for all classes of problems.**
Further clarification on author's rebuttal
I thank the authors for their response. I have a few further queries which will help me to understand and place the paper in context: - "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" : Can the authors be more specific about this comment? Can you give a particular example where this happens and you outperform DCS (not just experiments, deeper insights/intuition)? - Thank you for clarifying the theoretical contribution w.r.t Poiani 2023 - Regarding the typo in $\hat{J}(\pi)$, does it affect any theoretical result? It is not exactly possible for me to dig deep, but would like clarification from the authors. - "Since the optimal DCS does not admit a closed-form expression retrieving this sort of result requires significant technical effort." Can you expand on this point? - When I was talking about Oracle baseline, I am talking like this, take the RIDO algorithm and replace the variance with true variance (calculated over many samples). I am not sure why this cannot be done. Plot your avg variance reduction against such an oracle baseline. If you are reducing close to it, it basically means that you are close to optimal. Can you clarify why this can't be done?
Additional Clarifications
We thank the reviewer for the response, and we are glad that some concerns, such as the theoretical contribution w.r.t. Poiani et al., 2023 have been clarified. In the following, we answer the additional questions. 1. **"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" : Can the authors be more specific about this comment? Can you give a particular example where this happens and you outperform DCS (not just experiments, deeper insights/intuition)?** We thank the reviewer for the question. We hope that the following discussion can clarify the doubt. First of all, **Example 1 provides an intuitive example of why this is the case**. We recall that in Example 1, the underlying Markov reward process induced by the policy $\pi$ gathers rewards **only** at the end of the estimation horizon $T$. In this scenario, to minimize the variance of the return estimator, we would expect an intelligent agent to spend the entire budget $\Lambda$ in collecting trajectories of length $T$ (i.e., the uniform DCS). However, since the schedule of DCS Poiani et al., 2023 blindly truncates trajectories prior to interacting with the environment (i.e., **the DCS is fixed and equal for all the possibles underlying Markov reward processes**), it fails to adapt to the peculiarities of the problem at hand (i.e., the fact that, in this case, rewards are gathered **only** at the end of the estimation horizon $T$), and consequently, it fails to minimize the variance of the return estimator (i.e., producing a low error estimate). Similar comments holds for Example 2, but replacing Poiani et al., 2023 with the uniform DCS. **Theorem 3.1, on the other hand, also provides a formal justification for the statement quoted by the reviewer**. Indeed, Theorem 3.1 shows that the **DCS that minimizes the variance of the return estimator directly depends on the underlying Markov reward process that is induced by policy $\pi$ for the MDP at hand**. For this reason, **all predetermined schedule** (and, consequently, also the one of Poiani et al., 2023) fails to minimize the variance of the return estimator (i.e., producing a low error estimate). 2. **Regarding the typo in $\hat{J}(\pi)$, does it affect any theoretical result? It is not exactly possible for me to dig deep, but would like clarification from the authors.** We thank the reviewer for stressing on this point. **The theoretical contribution are completely left unchanged. The typo was only in Equation (2).** 3. **Since the optimal DCS does not admit a closed-form expression retrieving this sort of result requires significant technical effort." Can you expand on this point?** We thank the reviewer for asking this question, as this highlights the analytical challenges behind our analysis. As mentioned, the problem is that Equation (4) does not admit a closed-form expression. We notice that this problem is also present in the empirical version of Equation (4) that RIDO exploits during each mini-batch. As a consequence, all the analysis to upper-bound the variance of RIDO with the one of Equation (4) deals with **unknown quantities** (i.e., solutions of non-linear optimization problems for which we do not have a closed-form expression), which requires careful manipulations. More precisely, our analysis relies on several transformations of optimization problems, together with sensitivity analysis, that formally describes how the solution of the empirical optimization problem relates to the oracle one provided in Equation (4). 4. **Can you clarify why this can't be done?** We try to clarify this point more precisely w.r.t. our previous answer. From the definition of the oracle baseline (Equation 4), we notice that computing the oracle baseline requires (i) exact knowledge of the underlying Markov reward process (i.e., variance and covariances at each interaction step, and (ii) the ability to solve an integer and non-linear optimization problem. Concerning (i), we remark that in the environments we considered, this information is not available. At this point, as suggested by the reviewer, one might be tempted to estimate $\mathbb{V}\mathrm{ar}(R_t)$ and $\mathbb{C}\mathrm{ov}(R_t, R_t')$ using a large amount of data, and then using such estimates to build the oracle baseline (i.e., solving the optimization problem defined in Equation 4). Nevertheless, (a) this still requires solving an **NP-hard problem**, and (b) to **avoid introducing correlation between different runs**, the estimation of $\mathbb{V}\mathrm{ar}(R_t)$ and $\mathbb{C}\mathrm{ov}(R_t, R_t')$, and the computation of the NP-hard **should be repeated for each run, for each environment and for each value of the budget** $\Lambda$, which, however, is computationally infeasible. We remark that this is the correct way of computing the performance of an **estimated** oracle baseline.
Dear Reviewer, Since the discussion period is coming close to its end, we would kindly ask you if the previous set of answers has helped in placing our paper into context. Thank you very much in advance for your time in revising our paper and engaging in the discussion. We remain available for further clarification. The Authors.
Response to authors
Thanks for your response and I have noted the additional clarifications as well. We will discuss these responses in the reviewer-area chair discussion period.
I appreciate the comprehensive rebuttal from the authors, which has addressed many of my concerns. However, I still find the breadth of the applicability of the work somewhat limiting. Specifically, after considering your response here and to Acm2, I’m not sure how well the proposed technique can be applied in a policy optimization regime. Also, there seems to be a lack of clarity as to the specific scenarios where the proposed method offers advantages over the non-adaptive approach proposed in Poiani et al., 2023. While both the intuition and the theoretical analysis lean towards the superiority of the adaptive approach, the empirical results from environments like the supply chain, and settings in Reacher, Dam, Ant, Swimmer and HalfCheetah, indicate comparable performance between the two methods. Given the above considerations, I have increased the score accordingly.
Additional Clarification
We thank the reviewer for the response. We are glad that our in-depth rebuttal solved many concerns and that the reviewer increased the score accordingly. In the following, we follow up on the reviewer's comment to clarify one crucial aspect regarding empirical performance. First of all, we would like to summarize precisely the performance of RIDO and Poiani et al., 2023. **RIDO and Poiani perform similarly in the following domains**: Supply Chain ($\gamma=0.95$), Reacher ($\gamma=0.95$), Dam ($\gamma=0.999$), Ant and HalfCheetah ($\gamma=0.95$ and $\gamma=0.999$), Pendulum ($\gamma=0.99$), and LQG ($\gamma=0.9$). **RIDO performs statistically significantly better than Poiani et al., 2023 in the following cases**: Reacher ($\gamma=0.999$), Dam ($\gamma=0.95$), Supply Chain ($\gamma=0.999$; notice that for small values of $\Lambda$ RIDO obtains half the variance of Poiani et al., 2023), Swimmer ($\gamma=0.99$ and $\gamma=0.998$ ), Navigation ($\gamma=0.99$ and $\gamma=0.95$), and LQG ($\gamma=0.99$). At this point, we agree with the reviewer that, in some experiments, the performance of RIDO and Poiani et al., 2023 are comparable. Nevertheless, as highlighted above, there are also cases in which we observe significant performance differences between RIDO and Poiani et al., 2023. We notice that **this is a direct consequence of the fact that RIDO is adaptive w.r.t. the underlying Markov reward process induced by the policy $\pi$ on the MDP hand**. On the other hand, **Poiani et al., 2023 is a fixed schedule blindly deployed before interacting with the environment.** In this sense, we acknowledge that there exist couples of environments and policies to evaluate in which the DCS of Poiani et al., 2023 obtains satisfying performance (usually significantly better than the uniform DCS). Nevertheless, there are also a significant number of cases in which this is not the case. The main point is that **RIDO can automatically discover when and how to truncate trajectories according to the underlying scenario, thus achieving competitive performance in all scenarios. On the other hand, the schedule of Poiani et al., 2023, does not enjoy this adaptivity property and can incur (as shown by our experiments) significant sub-optimal performance levels.**
I appreciate the authors' follow-up response. I have decided to keep the existing score.
Decision
Accept (poster)