Adaptive Exploration for Data-Efficient General Value Function Evaluations

Thank you for your detailed feedback and valuable experimental suggestions, which we have now incorporated into our rebuttal. Based on your input, we have also added results in Mujoco in the main comment (refer Fig 1 in PDF). We appreciate your recognition of the novelty of adaptively learning the behavior policy to efficiently evaluate multiple GVFs in parallel and acknowledgment of the systematic derivation of the algorithm. Detailed responses to your queries are provided below.

1. "How can Uniform sampling be a competitive baseline?"

   We use several baselines: uniform, mixture policy, round-robin policy, SR-based policy, and BPS. Learning a behavior policy for multiple GVFs is relatively unexplored, making it challenging to identify more baselines. Our empirical results indicate that the relative performance of these baselines can vary depending on target policy characteristics.

   For example, in Fig. 7 of the main paper, round-robin and mixture policies perform better when using semi-greedy fixed target policies. Conversely, the uniform policy can be advantageous when the target policies exhibit low goal-reaching probability, because it helps hit the goal by chance.

2. "Query: Show experiments in Mujoco"

   We have now expanded our algorithm to continuous actions and shown results in Mujoco. Please refer to Fig 1 in the attached PDF and the main comment for the graphs and explanation of the Mujoco experiments. We believe these additions significantly strengthen our paper and provide a more comprehensive evaluation of our proposed method.

3. "How does using an approximated Q in the target, rather than the true Q, affect our algorithm's analysis? What is the impact on MSE performance when the function approximator is crude?"

   All TD-based methods, including IS-TD, are biased because of bootstrapping. Only with MC return, IS is unbiased. We use the unbiased estimator as a motivation to reduce the problem to minimizing the variance. Empirically, we used TD-based methods in all experiments to approximate both value and variance, due to the better stability and efficiency of these estimators in large-scale problems.

   To better understand the impact of using a crude function approximator on MSE, we have now added experiments on this ablation study. Specifically, we examined the average MSE in a 20x20 grid with two distinct GVFs. We produced features by reducing the state space into a 10x20 feature grid (grouping factor = 2) and a 5x20 feature grid (grouping factor = 4). An approximation factor of 1 shows the result without any function approximation.

   In Fig 2 (PDF attached in main comments), as expected, the overall MSE increases with cruder approximations. Despite this, GVFExplorer outperforms round-robin and mixture policies. However, when the approximation is very crude (factor = 4), the uniform policy performs better due to poor variance estimates. These results suggest that GVFExplorer is robust with reasonable function approximators, but can degrade with extremely coarse ones, which is to be expected.

   Further, these results are also strengthened by the performance in the attached Mujoco environment (Fig 1 in PDF in main comments) where function approximators are used.

4. "How does PER improve GVFExplorer performance? How is PER different from our algorithm? Given infinite data in the replay buffer, would GVFExplorer have the same effect as PER?"

   PER complements GVFExplorer by enhancing data efficiency. While GVFExplorer optimizes the behavior policy to sample informative data, PER reweights the collected samples in the buffer according to priority, ensuring that the mini-batches sampled for gradient descent are selected efficiently. Please refer to lines 307-309 for reasoning on performance boosts of GVFExplorer with PER.

   With infinite data, the impact of both GVFExplorer and PER would diminish, and direct sampling from the target policies would suffice. However, in practical settings with limited data, GVFExplorer's ability to actively influence data collection provides a significant advantage.

   It is crucial to distinguish between GVFExplorer and PER. GVFExplorer adapts the behavior policy based on variance estimates, while PER reweighs the sampling of the existing data already collected within the buffer. We used PER with all algorithms, including baselines, as shown in Fig 3a of the main paper; all baselines, except the SR method, show improved performance with PER.

Thank you for the detailed review and positive feedback on our algorithm's rigorous derivation and analysis. Based on your suggestion, we have now added Mujoco experiments result in the main comment. We respond to each query below.

1. “Why did we choose to minimize variance of return as our objective”?

   We think there may be a misunderstanding regarding the question. Below, we have tried to clarify our rationale, but please let us know if further discussion would be beneficial.

   The primary objective is to identify a behavior policy that minimizes MSE when evaluating multiple GVFs. As outlined in lines 120-125, $\text{MSE} = \text{bias}^2 + \text{variance}$. Using the unbiased IS estimator, we reduce the problem to minimizing the variance, which is the core objective. Minimizing variance improves the accuracy of value estimates by reducing uncertainty. This ensures that the behavior policy collects the most informative samples, thereby reducing estimation error quickly.

   Furthermore, Owen et al. (2013) demonstrated that using a minimum-variance optimal behavior policy ($\mu^*$) for a single target policy ($\pi$) in scenarios with known dynamics can lead to performance improvements. The value obtained under $\mu^*$ is greater than under $\pi$, where the improvement is directly related to the variance reduction achieved. This indicates that the higher the variance reduction under $\mu^*$ policy, the more significant the performance improvement. We hypothesize that similar effects could be observed in multiple GVF policy “Control” scenarios, which we aim to investigate in future research. This work lays the foundations under the policy evaluation context.

   We will include this rationale in the camera-ready version to further substantiate our approach.

2. “Query regarding more experiments in Mujoco”

   We have now added the empirical results in the Mujoco environment with continuous actions. Please refer to the attached PDF and the main comment for the performance graphs and explanation on Mujoco experiments.

Thank you reviewer for your thoughtful and constructive feedback. We provide a detailed response to the asked questions below.

1. “Clarification regarding Theorem 4.2”

We appreciate your careful attention, you are correct that Theorem 4.2 demonstrates that the aggregated variance "does not increase" with each update, rather than strictly "decreases." due to "<=" sign in the proof. We will make the necessary revisions to the paper to accurately reflect this.

2. “Regarding question on potential degeneracies and exploration of algorithm”

Thank you for raising this important point. Just like in standard RL, to obtain reliable estimates—whether for Q-values or variances—it's important to have at least initial exploration of different areas of the state-action space. This can be achieved by incorporating any standard initial exploration technique.

In our work, the proposed algorithm assumes sufficient initial exploration to gather necessary data. We address this by initializing M values to a non-zero constant across all state-action pairs and also allowing epsilon exploration, where epsilon decays over time. This ensures agents visit a wide range of state-action pairs early on, preventing issues of zero variance for unvisited state-action pairs. We added epsilon-exploration for all algorithms including baselines.

3. “Effects on M with sparse cumulant”

In scenarios with sparse cumulants, the non-zero initialization of M ensures that all states are visited, providing a fair opportunity to correct M estimates over time.

4. “What happens to the algorithm as a function of the error in the estimates of M?”

Similar to any TD-based algorithm, the empirical version of our approach relies on initial estimates, which will be imperfect. If the initial M estimates are incorrect, the TD error will indicate this, either positively or negatively. The behavior policy update will then be influenced by these M estimates, leading the agent to gather new samples as it interacts with the environment. As agent collects more data, the M estimates will improve—either increasing or decreasing for specific states—allowing the behavior policy to adjust and correct its sampling strategy accordingly. If an M estimate is very small compared to its true value, the agent will first focus on states with higher M estimates, correct those values, and then revisit the poorly estimated states to update their M estimates. This iterative process is analogous to TD-based Q-learning updates in standard RL.

Additionally, if the target policies have non-zero probabilities, our behavior policy incorporates a small epsilon probability over those state-action pairs. This approach is also supported by Lemma 6.1 which requires a bounded difference between the behavior and target policies to ensure that the variance function remains well defined. For Mujoco experiments, we added KL term to limit this divergence.

We will include these explanations in the camera-ready version to provide a practical understanding of our algorithm.