Adaptive Exploration for Data-Efficient General Value Function Evaluations

Authors: arushi  jain
josiah p hanna
doina  precup
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 05:08:06

Abstract: General Value Functions (GVFs) (Sutton et al., 2011) represent predictive knowledge in reinforcement learning. Each GVF computes the expected return for a given policy, based on a unique reward. Existing methods relying on fixed behavior policies or pre-collected data often face data efficiency issues when learning multiple GVFs in parallel using off-policy methods. To address this, we introduce *GVFExplorer*, which adaptively learns a single behavior policy that efficiently collects data for evaluating multiple GVFs in parallel. Our method optimizes the behavior policy by minimizing the total variance in return across GVFs, thereby reducing the required environmental interactions. We use an existing temporal-difference-style variance estimator to approximate the return variance. We prove that each behavior policy update decreases the overall mean squared error in GVF predictions. We empirically show our method's performance in tabular and nonlinear function approximation settings, including Mujoco environments, with stationary and non-stationary reward signals, optimizing data usage and reducing prediction errors across multiple GVFs.

Main paper: 
 introduction: 
 The ability to make multiple predictions is a key attribute of human, animal, and artificial intelligence. Sutton et al. (2011) introduced General Value Functions (GVFs) which consists of several independent sub-agents, each responsible for answering specific predictive knowledge about the environment. Each GVF consists of a unique -policy, custom reward function called cumulant and state-dependent discount factor -to calculate the cumulative discounted cumulant. For example, a GVF can predict the expected number of times an agent will bump into the wall under a given policy (White et al., 2015; Schlegel et al., 2021; Sherstan, 2020) . In essence, GVFs generalizes the standard value function to address a wider range of predictive questions, making them a powerful tool for intelligent systems.Prior works have used either a fixed random behavior policy (Sutton et al., 2011) or pre-collected datasets (Xu et al., 2022) to update all GVFs in parallel using off-policy learning. However, these methods can result in large value estimation errors if the behavior policy significantly diverges from the GVF policies. Our work addresses this gap by focusing on the question of exploration for evaluating GVFs: how can we adapt an agent's behavior policy for data-efficient estimation of multiple GVFs in parallel? While exploration has been extensively studied in the context of optimal control in Markov Decision Processes (MDP), the question of constructing a policy that can learn multiple value functions in parallel has remained largely unexplored.To accurately evaluate multiple GVFs in parallel, we aim to design a behavior policy that minimizes the overall mean squared error (MSE) of their predictions. A natural approach might involve following each GVF's target policy for some period of time (e.g. one episode) in a round-robin manner while concurrently updating all GVFs off-policy. However, this approach can be highly data inefficient as actions are sampled according to given policies, potentially overlooking actions from states where the expected return is uncertain. To achieve better value estimation with fewer samples, it is essential to focus on state-action pairs with high variance in return, as these pairs would exhibit greater uncertainty in their mean return. Therefore, a behavior policy should visit such pairs more frequently to offset higher variance in return. Consider an analogy of a two-arm bandit problem: fewer samples are needed to accurately evaluate a constant reward arm, whereas an arm with a variable reward demands a greater number of samples to achieve the same level of certainty. We empirically support this claim by comparing round-robin and our approach later in this paper.With this motivation, we introduce GVFExplorer, that adaptively learns a behavior policy which minimize the total MSE across all GVF predictions. GVFExplorer leverages the existing off-policy temporal difference (TD) based estimator of variance in return distribution (Sherstan et al., 2018; Jain et al., 2021) to guide the behavior policy. The strategy is to frequently take actions that might have more unpredictable outcomes (high variance in return). By sampling them more, agent can estimate the mean return better with fewer interactions, thus effectively lowering the overall MSE in the GVF predictions.GVFExplorer optimizes the data usage and reduces the prediction error, offering a scalable solution for complex environments. This is particularly valuable for real-world applications like personalized recommender systems (Parapar & Radlinski, 2021; Tang et al., 2015) , where it can enable efficient evaluation of personalized policies based on diverse user preferences (reward functions) (Li et al., 2024) , leveraging shared knowledge for improved accuracy.Contributions: (1) We design an adaptive behavior policy that enables accurate and efficient learning of multiple GVF predictions in parallel [Algorithm 1]. (2) We derive an iterative behavior update rule that directly minimizes the overall prediction error [Theorem 4.1] . (3) We prove in the tabular setting that each iterative update to the behavior policy causes the total MSE across GVFs to be less than equal to one from the old policy [Theorem 4.2] . (4) We establish the existence of a variance operator that enables us to use TD-based variance estimation [Lemma 5.1]. (5) We empirically demonstrate in both tabular and Mujoco environments that GVFExplorer lowers the total MSE when estimating multiple GVFs compared to baseline approaches and enables evaluating a larger number of GVFs in parallel. 
related work: 
 Exploration in reinforcement learning (RL) has predominantly focused on improving policy performance for a single objective (Oudeyer et al., 2007; Schmidhuber, 2010; Jaderberg et al., 2016; Machado et al., 2017; Eysenbach et al., 2018; Burda et al., 2018; Guo et al., 2022) . Refer to Ladosz et al. (2022) for a detailed survey on exploration techniques in RL. While related to exploration, these works differ from ours, as they concentrate on optimizing policies for single objective rather than evaluating multiple GVFs (policy-cumulant pair) simultaneously.Our work is most closely related to other works on learning multiple GVFs. Xu et al. (2022) address a similar problem by evaluating multiple GVFs using an offline dataset, but our method operates online, avoiding the data coverage limitations of offline approaches. Linke et al. (2020) develops exploration strategies for GVFs in a stateless bandit context, which does not deal with the off-policy learning or function approximation challenges present in the full Markov Decision Process (MDP) context. In a single bandit problem, Antos et al. (2008) ; Carpentier et al. (2015) , show that the optimal data collection strategy to estimate mean rewards of arms is to sample proportional to each arm's variance in reward. Prior works like Hanna et al. (2017) learned a behavior policy for a single policy evaluation problem using a REINFORCE-style (Williams, 1992) variance-based method called BPS. This idea extends on the similar principles of using Importance Sampling in Monte Carlo simulations for finding optimal sampling policy based on variance minimization (Owen, 2013; Frank et al., 2008) . Metelli et al. (2023) extends this idea to the control setting. However, these methods are limited to single-task evaluation or control. Evaluating multiple policies simultaneously is more complex, requiring careful balance in action selection among interrelated learning problems. Perhaps the closest work to ours is by McLeod et al. (2021) , which uses the changes in the weights of Successor Representation (SR) (Dayan, 1993) as an intrinsic reward to learn a behavior policy that supports multiple predictive tasks. GVFExplorer approach is simpler, as it directly optimizes the behavior policy to minimize the total prediction error over GVFs, resulting in an intuitive variance-proportional sampling algorithm. We will compare the two approaches empirically as well.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Refer Sec. 8 for limitations, where we discuss the limitation with extra computation cost of the variance function, as compared to baselines which might just require value function.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminaries: 
 Consider an agent interacting with the environment to obtain estimates of N different General Value Function (GVF) (Sutton et al., 2011) . We assume an episodic, discounted Markov decision process (MDP) where S is the set of states, A is the action set, P : S × A → ∆ S is the transition probability function, ∆ S is the |S|-dimensional probability simplex, and γ ∈ [0, 1) is the discount factor.Each GVF is conditioned on a fixed policy π i : S → ∆ A , i = {1, . . . , N } and has a cumulant c i : S × A → R. For simplicity, we assume that all cumulants are scalar, and that the GVFs share the environment discount factor γ. This eases the exposition, but our results can be extended to general multidimensional cumulants and state dependent discount factor. Each GVF is a value functionV πi (s) = E πi,P [G i t |s t = s] where G i t = c i,t + γG i t+1 .Each GVF can be viewed as answering the question, "what is the expected discounted sum of c i received while following π i ?" We can also define action-value GVFs:Q πi (s, a) = c i (s, a) + γE s ′ ∼P(•|s,a) [V πi (s ′ )], with V πi (s) = E a∼πi(•|s) [Q πi (s, a)].At each time step t, the agent in state s t , takes an action a t and receives cumulant values c i,t for all i ∈ {1, . . . , N }, transitioning to a new state s t+1 . This repeats until reaching a terminal state or a maximum step count. Then the agent resets to a new initial state and starts again. The agent interacts with environment using a behavior policy, µ : S → ∆ A . The goal is to approximate values Vi corresponding to the true GVFs value V πi . We formalize the objective as minimizing the Mean Squared Error (MSE) under some state weighting d(s) for all GVFs:MSE(V, V ) = N i=1 s∈S d(s) V πi (s) -Vi (s) 2 .(1)In our experiments, we use the uniform distribution for d(s). This objective can be generalized to prioritize certain GVFs using a weighted MSE.Importance Sampling (IS). To estimate multiple GVFs with distinct target policies π i in parallel, off-policy learning is essential. Importance sampling (IS) is one of the primary tools for off-policy value learning (Hesterberg, 1988; Precup, 2000; Rubinstein & Kroese, 2016) , allowing estimation of value function under target policy π using samples from different behavior policy µ. In the context of off-policy Temporal Difference (TD) learning (Sutton & Barto, 2018) , the IS ratio, ρ t = π(at|st) µ(at|st) , is used to adjust the updates to ensure unbiased value estimates. The update rule is given asQ(s t , a t ) = Q(s t , a t ) + α c t + γρ t+1 Q(s t+1 , a t+1 ) -Q(s t , a t ), where α is the learning rate. This update rule ensures that estimated value function Q converges to correct value Q π under policy π, despite the samples being generated from a behavior policy µ.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: Refer App. A for complete assumptions and proofs.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
behavior policy optimization: 
 As described in the previous section, the goal of the agent is to minimize the total mean squared error (MSE) across the given GVFs (Eq. ( 1)). Note that MSE = Variance + Bias 2 . For the algorithm's derivation, we will use unbiased IS estimation for off-policy correction, which shifts the task of minimizing MSE to reducing the total variance across GVFs. Thus, the core problem is to design a behavior policy that collects data to minimize the variance in return across all GVFs in order to accurately estimate multiple GVF value functions.The problem of estimating a single target policy's value, V π , is well studied in the literature (see Sec. 2). In Monte Carlo sampling literature, it is well known that there exists an optimal sampling distribution (i.e., behavior policy) that provides optimal variance reduction compared to simply running the target policy Kahn & Marshall (1953) ; Owen (2013) . Unfortunately, the analytical solution of obtaining this optimal behavior policy, µ * , requires foreknowledge of V π , making it impractical when our overall purpose is to estimate V π . Nonetheless, in this work, we take inspiration from this earlier work and develop a practical method that iteratively solves for a single behavior policy that minimizes the total variance when estimating multiple general value functions in parallel.We propose GVFExplorer to address the above limitation and extend the problem to accurately estimate multiple GVF values. GVFExplorer takes as input the GVF target policies π i={1,...,N } , collects data from a single (non-stationary) behavior policy µ, and outputs the GVF estimates Vi={1,...,N} . Since our objective is to find a behavior policy that minimizes the variance in return across multiple GVFs, we use an existing off-policy TD-style variance estimator (Sherstan et al., 2018) . This estimator allows us to bootstrap the target values and iteratively update the variance function, making the solution scalable to complex domains.We define the variance function by M µ π (s), which measures the variance in the return of target policy π in a given state s when actions are sampled under a different behavior policy µ. We describe how to learn this function in Sec. 5. The variance function for a given state and a given state-action pair are defined respectively as:M µ π (s) = Var π (G t |s t = s, a ∼ µ) and M µ π (s, a) = Var π (G t |s t = s, a t = a, a ′ ∼ µ).Our objective is to find an optimal behavior policy µ * that efficiently collects a single stream of experience to minimize the sum of variances M µ π {1...N } under some state distribution d(s), as,EQUATIONWe solve the above objective function iteratively. At each iteration k, GVFExplorer produces a behavior policy µ k . The behavior policy interacts with the environment and gathers data. Using this data, any off-policy TD algorithm can be used to iteratively estimate the variance function M µ k π . This variance function is plugged into the optimization problem given in Eq. ( 3) to update to a policy µ k+1 that reduces variance. The iterative procedure is analogous to policy iteration, which alternates policy evaluation with policy improvement. Here, we alternate between the variance evaluation and the improvement of behavior policy to minimize the overall sum of variance across all given GVFs.Here, our aim is to iteratively improve behavior policy and decrease variance functions to estimate the GVF values V π i={1,2,...,N } with reducing MSE:µ 0 E -→ M µ0 πi=1,2,... I -→ µ 1 E -→ M µ1 πi=1,2,... . . . E -→ µ K ,where E -→ denotes variance estimation and I -→ denotes behavior policy improvement. Next, we present Theorem 4.1 which principally derives the behavior policy update from µ k to µ k+1 by solving the objective in Eq. ( 7). We demonstrate that the behavior policy update in Eq. (3) minimizes the objective by showing that µ k+1 is a better policy than µ k . The policy µ k+1 is considered as good as, or better than µ k , if it obtains lesser or equal total variance across all GVFs: i Mµ k+1 πi (s) ≤ i M µ kπi (s). The proof of behavior policy improvement is detailed in Theorem 4.2.Theorem 4.1. (Behavior Policy Update:) To find the behavior policy µ that minimize the variance objective across N given target policies {π i } N i=1 , we iteratively update µ by solving the objective in Eq. (2). Given state-action variance function M µ k πi (s, a), the solution to Eq. (2) at iteration k is:µ k+1 (a|s) = i π i (a|s) 2 M µ k πi (s, a) a ′ i π i (a ′ |s) 2 M µ k πi (s, a ′ ).(3)Proof. The proof is presented in App. A.1.Theorem 4.1 describes how to iteratively update the behavior policy µ k that minimizes objective in Eq. ( 2) by using the return variance M µ k πi . The policy µ k+1 selects actions proportional to their variance, meaning high-variance return (s, a) pairs are explored frequently. By visiting high-variance return pairs, policy gains informative samples and reduce the overall uncertainty. Consequently, this process improves the GVF value predictions and decrease the number of interactions needed for effective learning.Next Theorem 4.2 ensures that behavior policy µ k+1 either decreases or maintains the total variance across all GVFs relative to µ k , ensuring consistent progress towards minimizing the variance without oscillation. In simple terms, each policy update ensures the variance does not increase.Theorem 4.2. (Behavior Policy Improvement:) The behavior policy update in Eq.(3) ensures that the aggregated variances across all target policies {π i } N i=1 either decreases or remains unchanged at each iteration k. This non-increasing variance property demonstrates that each successive behavior policy µ k+1 is improvement over µ k in terms of reducing the total variance. Formally we have,N i=1 M µ k+1 πi (s) ≤ N i=1 M µ k πi (s), ∀k, ∀s ∈ S.Proof. The proof is in App. A.1.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We provide the exact proposed GVFExplorer in Algorithm 1 with all the parameters. The optimized hyperparameters for all algorithms are presented in Table 2 . The learning rate sensitivity graph is shown in Fig. 6 . We provided the code link in the paper. The environmental details and network architecture is described in App. B.3 and App. B.3.5. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
variance function: 
 The theorems provided in the previous section rely on the variance function M µ k πi . Here, we study this variance function in detail.What is the Variance Function M ? In an off-policy context [Sherstan et al. (2018) , Jain et al. (2021) ], introduced the variance function M µ π , which estimates the variance in return under a target policy π using data from a different behavior policy µ. We will directly use this function M µ π as our variance estimator and present it here for completeness. The function M µ π for a state-action pair under π, with an importance sampling correction factor ρ t = π(at|st) µ(at|st) , is defined as:EQUATION) Here, G t,π is the return at time t, and δ t = r t + γE a ′ ∼π [Q π (s t+1 , a ′ )] -Q π (s t , a t ) is the TD error. We use Expected Sarsa (Sutton & Barto, 2018) to compute δ t , eliminating the need for IS by using the expected value of the next state-action pair under π for bootstrapping, thus stabilizing the update and lowering the variance. M µ π (s, a) relates the variance under π from the current stateaction pair to the next, where actions are sampled under µ. This allows effective bootstrapping and iterative update using a TD-style method. The state variance function is defined as M µ π (s) = a µ(a|s)ρ 2 (s, a)M µ π (s, a). Note, the true Q π is required to compute the TD error δ t in Eq. (4). Following Sherstan et al. (2018) , we substitute the value estimate Q for the true function Q π to compute δ t in Eq. ( 4). Additionally, we use variance estimates M µ k π to update the next step policy µ k+1 instead of true variance in Eq. (3). This approach is similar to generalized policy iteration (Sutton & Barto, 2018) , which alternatively updates the value estimator and then improves the policy.Next, we prove the existence of M µ π in Lemma 5.1, which was not covered in Jain et al. (2021) . This proof establishes a loose upper bound on the IS ratio ρ, limiting the divergence of the behavior policy µ from the target policy π for effective off-policy variance estimation. This aligns with methods like TRPO (Schulman et al., 2015) and Retrace (Munos et al., 2016) , which stabilize policy updates by controlling divergence.Lemma 5.1. (Variance Function M Existence:) Given a discount factor 0 < γ ≤ 1, the variance function M µ π exists, if the below condition satisfies, E a∼µ ρ 2 (s, a) < 1 γ 2 for all states.Proof. Proof in App. A.2.Note, the optimal µ for the objective in Eq. ( 2), might violate the above constraint on ρ; we empirically clip ρ to mitigate this problem. Additionally, IS requires µ(a|s) = 0 when π(a|s) = 0. We empirically ensure µ(a|s) > ε << 1 for all actions. The same constraint is added for all the baselines for fair comparison.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: We present the code link in the paper: https://github.com/ arushijain94/GVFExplorer to produce all main and supplementary results. We don't use any dataset.Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: The work presented here proposes a data-efficient approach to evaluate multiple objectives (GVFs) and does not experiment with real-world data. In the passage before the Contributions section, we outline potential extension to real-world applications like personalized recommender systems. The proposed method can unlock positive societal impacts. By requiring less data for evaluation, it enhances user privacy and reduces computational footprint for a more sustainable future. Though this work offers benefits for individual users, applying it across users necessitates privacy-preserving approaches. This work opens exciting future directions integrating privacy-preserving approaches like federated learning or differential privacy with our method. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
algorithm: 
 We present GVFExplorer algorithm, detailed in Algorithm 1. Our approach uses two networks: Q θ for value function and M w for variance, each with N heads (one head for each GVF). Starting with a randomly initialized behavior policy, the agent observes cumulants for N GVFs at each step and updates Q θ using off-policy TD. We use Expected Sarsa (Sutton & Barto, 2018) for both Q and M , eliminating off-policy corrections. The target Q updates follow:EQUATIONWe use the TD error from Q-learning, δEQUATIONBoth networks are updated via an MSE loss. The behavior policy is iteratively updated using the new variance estimates for K steps, with learned Q values used for MSE metrics in Eq. (1).To ensure reliable estimates, we initialize M values to small non-zero constants and apply epsilon exploration, which decays over time, ensuring coverage of the state-action space. This guarantees that agents visit a broad range of state-action pairs early on, preventing issues of zero variance for unvisited pairs. We applied epsilon-exploration to both GVFExplorer and the baselines for fair comparison.We also use techniques like experience replay Lin (1992) Update Q θ using MSE loss (Q tar (s t , a t ) -Q θ (s t , a t )) 2 , where Q tar is Eq. (5). end if k%m == 0 then //Update the Variance M w network Sample mini-batch of size b of transition (s t , a t , s t+1 , c t ) ∼ D Update M w using MSE loss (M tar (s t , a t ) -M w (s t , a t )) 2, where M tar is Eq. ( 6). Behavior policy becomes:µ k+1 (a|s) = n i=1 πi(a|s) 2 M i w (s, a) a ′ ∈A n i=1 πi(a ′ |s) 2 M i w (s, a ′ ) , ∀s ∈ S, a ∈ A. end Returns GVFs Values V i (s) = a π i (a|s)Q i θ (s, a) for i = {1, . . . , n} 
experiments: 
 We investigate the empirical utility of our proposed algorithm in both discrete and continuous state environments. Our experiments are designed to answer the following questions: (a) How does GVFExplorer compare with the different baselines (explained below) in terms of convergence speed and estimation quality? (b) Can GVFExplorer handle a large number of GVFs evaluations? (c) Can GVFExplorer work with non-stationary GVFs which change with time? (d) Can GVFExplorer work with non-linear function approximations and complex Mujoco environments?1 Baselines. We use Off-policy Expected Sarsa updates for parallel GVF estimations for all the experiments (including baselines) for fair comparison. We benchmark against several different baselines:(1) RoundRobin: uses a round-robin strategy sampling episodically from all target policies (2) MixturePolicy: Aggregated policy sampling from all target policies; (3) SR: a Successor Representation (SR) method using intrinsic reward of total change in SR and reward weights to learn behavior policy (McLeod et al., 2021) . ( 4) BPS: behavior policy search method originally designed for single policy evaluation using a REINFORCE variance estimator (Hanna et al., 2017) ; we adapted it by averaging variance across multiple GVFs (similar to our objective). BPS results are limited to tabular settings due to scalability issues with it. ( 5) UniformPolicy: a uniform sampling policy over the action space. Implementation details and hyperparameters are in App. B. We conducted experiments in 20 × 20 gridworld with four cardinal actions and a tabular 20 × 20 FourRooms environment for added complexity. The discount factor is γ = 0.99, and the environment is stochastic with a 0.1 probability of random movement. The cumulants are zero everywhere except for at the goals. Episode terminates after 500 steps or upon reaching the goal. True value function for MSE computation is calculated analytically V π = (I -γP π ) -1 c π . Detailed description of target policies and cumulants is provided in App. B.3. Table 1 summarizes the below results for tabular experiments.In Two Distinct Policies & Identical Cumulants, we consider gridworld environment with distractor cumulant at top left corner with a reward drawn from normal distribution. Fig. 1a shows the averaged MSE across the two GVFs, with GVFExplorer showing much lower MSE compared to baselines.Next, in Two Distinct Policies & Distinct Cumulants, we consider two distinct distractor cumulant (with different mean) GVFs placed at top-left and top-right corner respectively. Fig. 2a shows GVFExplorer with reduced MSEs compared to baselines. Figs. 2b and 2c qualitatively analyze the average absolute difference between true and estimated GVF values across states,E i [|V ci πi - V ci πi |],showing smaller errors (duller colors) for GVFExplorer. Fig. 8 (in App. B.3.2) presents the individual variance and MSE for both GVFs in GVFExplorer. Further, we conduct an ablation study to experiment with how GVFExplorer performance changes with poorer feature approximations. Fig. 10 (in App. B.3.3) shows that MSE increases as the feature quality deteriorates, but GVFExplorer remains robust with moderately coarse approximations.For Non-Stationary Cumulant in FourRooms, we evaluate the performance in FourRooms (FR) environment (Sutton et al., 1999) with two distinct GVFs: stationary distractor cumulant and a nonstationary drifter cumulant which changes value over time. As shown in Fig. 1b , GVFExplorer reduces MSE faster than other baselines, even with the non-stationary cumulant. We use a continuous grid environment that extends the tabular experiments to a continuous state space (similar to McLeod et al. ( 2021)) and four discrete actions. For Non-Linear Function Approximation, we consider two distinct GVFs with distractor cumulants. An Experience ReplayBuffer with a capacity of 25K and a batch size of 64 is used for all experiments. Further details on computing true value functions using Monte Carlo and network architectures are in App. B.4.Prioritized Experience Replay (PER). We investigate the integration of PER (Schaul et al., 2015) with our algorithm. Unlike the standard Experience Replay Buffer, which uniformly samples experiences, PER assigns priorities based on the TD error magnitude in the Q-network. PER and GVFExplorer are complementary approaches: PER re-weights the collected data in replay buffer based on the priority, while GVFExplorer adjusts the behavior policy to influence data collection.Combining PER with GVFExplorer drastically lowers MSE compared to other baselines (even when compared to all baselines + PER). We use the absolute sum of TD errors across multiple GVF Q-functions as a priority metric for PER in all baselines, including GVFExplorer. Placing the priority on the TD error of the variance function in GVFExplorer yields less favorable results compared to priority on Q-function's TD error. In Fig. 3 , we present the MSE for both standard experience replay (solid lines) and PER (dotted lines) for all algorithms. PER generally reduces MSE, but its integration with GVFExplorer shows much lower MSE. This is likely as GVFExplorer could over-sample high variance return samples, causing a skewed buffer distribution. PER's non-uniform sampling maintains a balanced data distribution, which helps in stringent MSE reduction. For the SR baseline, using the TD error in SR predictions as a priority for PER led to performance degradation, suggesting non-stationarity in SRs' TD errors might mislead PER to prioritize less relevant states under the current policy. We use DM-Control (Tassa et al., 2018) based continuous state-action tasks to experiment with Mujoco environments, Walker and Cheetah domain. To expand the proposed method to continuous action environments, any policy-gradient (PG) based algorithm can be used. In our experiments, we use Soft Actor-Critic (SAC) algorithm (Haarnoja et al., 2018) as a base PG method to incorporate the proposed variance-minimization objective.A separate network for variance estimation is added to SAC. Further implementation details are provided in App. B.5. To experiment in Walker environment, we use two GVF tasks, namely 'walk' and 'flip'. Similarly, for Cheetah environment, we use 'walk' and 'run' GVF tasks. We also added KL regularize between the learned behavior policy and the given GVFs target policies to prevent divergence. We use MC to compute the true Q-value GVF estimates and compare the MSE between these MC values and the Q-critic network. We use the same Q-critic architecture for the baseline algorithms -UniformPolicy and RoundRobin -for fair comparison. In Fig. 4 we observe that GVFExplorer reduces MSE faster than the baselines.  
conclusion: 
 We addressed the problem of parallel evaluations of multiple GVFs, each conditioned on a given target policy and cumulant. We developed a method to adaptively learn a behavior policy that uses a single experience stream to estimate all GVF values in parallel. The resulting behavior policy update selects the actions in proportion to the total variance of the return across GVFs. This guides the policy to frequently explore less understood areas (high variance in return), which helps to better estimate the mean return with fewer samples. Therefore, our approach lowers the overall MSE in GVF predictions while reducing the number of interactions required. We theoretically proved that each behavior policy update reduces or maintains the total prediction error. Empirically, we showed that GVFExplorer scales effectively with an increasing number of distinct GVFs, robustly handles non-stationary cumulants in a tabular setting, and adapts well to non-linear function approximation. Additionally, we showcased its performance in complex continuous state-action Mujoco environments, showing that GVFExplorer can be seamlessly integrated with existing policy-gradient methods.Limitations and Future Work. One notable drawback of GVFExplorer is the increased time complexity, due to simultaneously learning two networks for value and variance estimation respectively. Additionally, GVFExplorer has not been evaluated in environments with significant difference in the cumulant value range. Such disparities could lead to varying variances, potentially resulting in oversampling areas with higher cumulant values. Calibration across cumulants may be necessary in these cases.In this work, we focused on minimizing the total MSE, but other loss functions, such as weighted MSE could also be considered. However, weighted MSE requires prior knowledge about the weighting of errors in different GVFs, which is not readily available. A potential future direction could be to use variance scales to automatically adjust these weights to provide uniform MSE reduction across all GVFs. Looking ahead, we are interested in testing our approach with multi-dimensional cumulants and general state-dependent discount factors, as well as, extending the applicability of GVFExplorer to control settings where the target policies are unknown. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The proposed work is more suited towards academic and research setting, posing no such described above risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: We use classical RL benchmark environments like FourRooms (cited them) and invented few environments. Our code link is added in the paper. We use existing EMDP library to extend the gridworld envs which uses MIT License. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: We provide the link to our codebase in the paper which has been properly anonymized. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A.1 Behavior Policy Update Theorems Theorem 4.1. (Behavior Policy Update:) To find the behavior policy µ that minimize the variance objective across N given target policies {π i } N i=1 , we iteratively update µ by solving the objective in Eq. (2). Given state-action variance function M µ k πi (s, a), the solution to Eq.(2) at iteration k is:µ k+1 (a|s) = i π i (a|s) 2 M µ k πi (s, a) a ′ i π i (a ′ |s) 2 M µ k πi (s, a ′ ).(3)Proof. We formulate Eq. ( 2) as a Lagrangian equation below to solve for the optimal behavior policy µ * .L(µ, λ s,a , w s ) = i s d(s)M µ πi (s) I part + s,aλ s,a µ(s, a) Solving I part. We will compute the gradient of M µ πi (s) in Eq. ( 4) w.r.t to given µ(s, a). Here, ρ(s, a) = π(a|s) µ(a|s) is IS weight. We expand M µ πi (s) relation with M µ πi (s, a) to derive the gradient,EQUATIONM µ πi (s) = ã µ(ã|s)ρ i (s, ã) 2 M µ πi (s, ã) ∇ µ(s,a) M µ πi (s) = ∇ µ(s,a) ã µ(ã|s)ρ i (s, ã) 2 M µ πi (s, ã) = ρ i (s, a) 2 M µ πi (s, a) + 2µ(a|s)ρ i (s, a) ∇ρ i (s, a) =- ρ i (s, a) µ(a|s) M µ πi (s, a) + µ(a|s)ρ i (s, a) 2 ∇ µ M µ πi (s, a) =IV part = ρ i (s, a) 2 M µ πi (s, a) -2ρ i (s, a) 2 M µ πi (s, a) = -ρ i (s, a) 2 M µ πi (s, a). The final term ∇ µ M µ πi (s, a) is difficult to estimate in an iterative off-policy setting. Hence, we drop the (IV part) from the above gradient, which is similar to Degris et al. (2012) [Sec 2.2], where the gradient of Q(s, a) was dropped while deriving the policy update.Solving for the Lagrangian Eq. ( 7) further by substituting the (I part), and taking derivation of II & III part and using the (1) KKT condition.EQUATIONFrom ( 2)KKT condition, we know that either λ s,a = 0 or µ(a|s) = 0. Following the arguments of IS, support for µ(a|s) can only be 0 when the support for target policy π(a|s) = 0. Solving for the case when support for target policy in non-zero, then let λ s,a = 0. We can simplify the gradient of Lagrangian in Eq. ( 8),w s = - i d(s)ρ i (s, a) 2 M µ πi (s, a) = - i d(s) π i (a|s) 2 µ(a|s) 2 M µ πi (s, a) µ(a|s) = i π i (a|s) 2 M µ πi (s, a) -w s /d(s) (9)We know that the numerator is always positive (variance M is positive), therefore w s < 0. Let y s = -w s /d(s). From condition (5), we know that a µ(a|s) = 1. Using Eq. ( 9) and summing over all the actions we get,a µ(a|s) = a i π i (a|s) 2 M µ πi (s, a) y s = 1 Hence, √ y s = a i π i (a|s) 2 M µ πi (s, a).Therefore, the update for optimal behavior policy becomes,µ(a|s) * = i π i (a|s) 2 M µ * πi (s, a) a i π i (a|s) 2 M µ * πi (s, a).As the optimal policy µ * appear on both the sides, this can be interpreted as an iterative update, where k denotes the iterate number.µ k+1 (a|s) = i π i (a|s) 2 M µ k πi (s, a) a i π i (a|s) 2 M µ k πi (s, a).Theorem 4.2. (Behavior Policy Improvement:) The behavior policy update in Eq.(3) ensures that the aggregated variances across all target policies {π i } N i=1 either decreases or remains unchanged at each iteration k. This non-increasing variance property demonstrates that each successive behavior policy µ k+1 is improvement over µ k in terms of reducing the total variance. Formally we have,N i=1 M µ k+1 πi (s) ≤ N i=1 M µ k πi (s), ∀k, ∀s ∈ S.Proof. Theorem 4.1 suggests, for any given µ k behavior policy, the next successive approximation µ k+1 minimizes the objective function Eq. ( 2), i.e.,EQUATION)We will omit writing d(s) and assume that s ∼ d(s). Further, we will use the notationρ i k (s, a) = π i (a|s) µ k (a|s)for ease of writing. From Eq. ( 10), we can establish the relation,EQUATIONNow, we will use Eq. ( 11) relation to further simplify the equation and establish that variance decreases with every update step k. We will use the notation ρ t:t+n = Π n l=0 ρ t+l to denote the products.i,sEQUATIONA.2 When does Variance Function Exists?Let c µ ∈ R |S×A| denote the pseudo-reward c µ (s, a) = s ′ P (s ′ |s, a)δ 2 (s, a, s ′ ) and Pµ ∈ R |S×A×S×A| represent the transition probability matrix Pµ (s, a, s ′ , a ′ ) = P (s ′ |s, a)µ(a ′ |s ′ )ρ 2 (s ′ , a ′ ). The matrix form of M µ π is:EQUATION)The existence of M µ π hinges on the invertibility of matrix (I -γ 2 Pµ ). Lemma 5.1 establishes the existence of the above inverse using Definition A.1 and Lemmas A.2 and A.3. Definition A.1. (Spectral Radius) The spectral radius of a matrix A ∈ R n×n is denoted by sr(A) = max(λ 1 , λ 2 , . . . , λ n ), where λ i denotes the i th eigenvalue of A.Lemma A.2. The spectral radius sr(A) of a matrix A ∈ R n×n follows the relation, sr(A) ≤ ∥A∥, where, ∥A∥ = max i j A(i, j) is the infinity norm over a matrix.Proof. Following the derivation from Bacon (2018) Ph.D. thesis and work of Watkins ( 2004), we use the eigenvalue of a matrix to show that sr(A) < ∥A∥. We can write λx = Ax, when λ is the eigenvalue of A. For any sub-multiplicative matrix norm, ∥AB∥ ≤ ∥A∥∥B∥. Using this property,∥λx∥ = |λ|∥x∥ = ∥Ax∥ ≤ ∥A∥∥x∥, |λ| ≤ ∥A∥.The above is true for any eigenvalue λ of A. So this must also be true for the maximum eigenvalue of A. Therefore, we can express, sr(A) ≤ ∥A∥.Lemma A.3. When the spectral radius of sr(A) < 1, then (I -A) -1 exits and is equal to,(I -A) -1 = ∞ t=0 A t .Proof. The proof for the Lemma is presented in Puterman ( 2014) [Proposition A.3 ].Lemma 5.1. (Variance Function M Existence:) Given a discount factor 0 < γ ≤ 1, the variance function M µ π exists, if the below condition satisfies, E a∼µ ρ 2 (s, a) < 1 γ 2 for all states.Proof. Following Lemma A.3, the existence of M hinges on the existence of inverse (I -γ 2 Pµ ) -1 .Further, (I -γ 2 Pµ ) -1 exists if spectral radius sr(γ 2 Pµ ) < 1. Further, from Lemma A.2, we know that for any given matrix A, spectral radius satisfies, sr(A) ≤ ∥A∥. Hence, using the above two lemmas, we can express,sr(γ 2 Pµ ) ≤ ∥γ 2 Pµ ∥ ≤ γ 2 ∥ Pµ ∥.Further, if spectral radius satisfies the below condition, then the inverse exists,sr(γ 2 Pµ ) ≤ γ 2 ∥ Pµ ∥ < 1.We expand the middle infinity norm term and getmax s,a s ′ ,a ′ Pµ (s, a, s ′ , a ′ ) < 1 γ 2 max s,a s ′ P (s ′ |s, a) a ′ µ(a ′ |s ′ )ρ 2 (s ′ , a ′ ) < 1 γ 2 .We can further express the above condition as E a∼µ ρ(s, a) 2 < 1 γ 2 , ∀s ∈ S.This section provides detail about the experiments in the main paper as well as additional experiments in the Appendix. All the experiments require less than 1GB of memory and have used combined compute less than total 4 CPU months and 1 GPU month.For all the experiments, we consider the two target policies with four cardinal directions left (L), right (R), up (U) and down (D) for the tabular and non-linear function approximation environments. These policies are specified as follows for every state s ∈ S: (1) RoundRobin: We used a round robin strategy to sample data from all given n target policies episodically. We used Expected Sarsa to estimate all GVF value functions in parallel when a transition is given as (s t , a t , s t+1 , c i={1,...n} ),Q i (s t , a t ) = Q i (s t , a t ) + α c i (s t , a t ) + γ a π i (a ′ |s t+1 )Q i (s t+1 , a ′ ) -Q i (s t , a t ))(2) MixturePolicy, UniformPolicy are also evaluated using Expected Sarsa. MixturePolicy is defined as,µ Mixture (a|s) = N i=1 π i (a|s) a ′ N i=1 π i (a ′ |s).(3) SR: Based on (McLeod et al., 2021) , SR uses the summation of weight changes in the Successor Representation (SR) and reward weights to obtain the intrinsic reward for behavior policy updates. We use Expected Sarsa to learn both the SR and the Q-value function from the intrinsic reward. The behavior policy is generated using a Boltzmann policy over the learned Q function, as it empirically performs better than a greedy policy. We apply simple TD Expected Sarsa updates instead of Emphatic TD(λ) as shown in Algo 2 in McLeod et al. (2021) . The learning rates for SR, reward weights, and behavior policy Q function are kept the same. µ(at|st) , as mentioned in the original paper. Since, the original work is only about single policy evaluation, we extended for multiple GVFs by updating behavior policy as summation over i IS(τ, π i ). The behavior policy weight θ is updated as: θ µ = θ µ + α n i=1 IS(τ, π i ) 2 T t=1 ∇ θ log µ θ (a t |s t ).We consider a tabular 20 × 20 grid environment with stochastic dynamics. We use the above target policies for the different experimental settings. The Table 1 summarizes the averaged MSE with the same 2 × 10 6 samples for different experimental settings. Hyperparameter Tuning: In our experiments, we use linearly decaying learning rates that starts with initial value of 1.0 and gradually decreased to an optimized minimum value within 500K steps of environmental interactions. We used different learning rates for value and variance function in GVFExplorer. The minimum learning rate parameter was swept within {0.1, 0.25, 0.5, 0.8, 0.9, 0.95} for both value and variance function. The optimal minimum learning rate was determined based on the one achieving the lowest average Mean Squared Error (MSE) after 800K sample interactions. This hyperparameter tuning approach was consistently applied for all algorithms including baselines. Fig. 6 shows the sensitivity analysis of varying learning rates for value functions (all baselines) and variance functions (our method) with the averaged MSE performance in Two Distinct Policies & Identical Cumulants. The learning rate resulting in the lowest MSE was selected as optimal. In Table 2 , we show the optimal hyperparameters for the four experimental settings discussed in the paper earlier (refer Experimental Settings in Sec. 7).(α Q = 0.25, α M = 0.8) (α Q = 0.1, α M = 0.8) (α Q = 0.5, α M = 0.95) (α Q = 5e -3, α M = 5e -3) (α Q = 0.5, α M = 0.In tabular 20 × 20 grid, we consider distinct target policies with identical distractor cumulant r = N (µ = 100, σ = 5). In Fig. 7 , we depict the individual MSE over 25 runs for both the GVFs (π 1 , c), (π 2 , c); showing decreased MSE for GVFExplorer compared to the baselines. more samples to converge. This outcome can be attributed to the near-greedy nature of the target policies, which inherently guides RoundRobin along goal directed trajectories, enabling it to achieve nearly accurate predictions with fewer samples. The optimal hyperparameters for RoundRobin, UniformPolicy and MixturePolicy is α Q = 0.95. We used α Q = 0.5, α M = 0.8 for ours GVFExplorer. Another baseline SR has α Q = 0.8 and BPS as α Q = 0.9 as optimal hyperparameters. We observe a slower convergence of GVFExplorer as compared to baselines like RoundRobin, MixturePolicy due to target policies being semi-greedy.In this section, we study the effect of using degraded approximations or feature quality on the performance metrics. We conducted an ablation study in a 20x20 grid with two distinct distractor GVFs with cumulants, c 1 = N (µ = 100, σ = 5) placed on the top-left corner and c 2 = N (µ = 50, σ = 5) on the top-right corner. We reduced the state space into 10x20 and 5x20 feature grids (grouping factors of 2 and 4, respectively), and compared results against the original setup (no approximation, factor = 1). As shown in Fig. 10 , the MSE increases as the feature quality deteriorates. Despite this, GVFExplorer outperforms RoundRobin and MixturePolicy, though with very poor approximations (factor = 4), the UniformPolicy performs better due to inaccurate variance estimates. These results demonstrate that GVFExplorer is robust with moderately coarse approximations but can degrade with significantly poor feature representations, as expected. Further, these results are strengthened by the performance of GVFExplorer in Mujoco environments Sec. 7.3. GVFExplorer outperforms baselines given a reasonable feature approximator.In complex FourRooms environment, we consider two distinct target policies in Eq. ( 14) and different cumulants -stationary distractor with N (µ = 100, σ = 2) in top-left room, non-stationary drifter signal of σ = 0.5 in top-right room. Figs. 11a and 11b shows the change in estimated variance M of GVFExplorer from early learning steps to later steps (vibrant color shows higher numerical value). We experimented with changing the value of σ of drifter cumulant to see the effect on MSE.In Fig. 11c we observe that MSE increases with increasing the value of driftness (σ) over time. We evaluate GVFExplorer ability to handle a large number of GVFs. We examine four target policies (π n∈1...4 ), each aligned with a cardinal direction, and ten cumulants (c m∈1...10 ), aiming to predict 40 GVF combinations (v c1 π1...4 . . . v c10 π1...4 ). Each GVF is associated with a state space region ("goal"), uniformly sampled and assigned constant cumulant value ranging [50, 100] , demonstrated in Fig. 12 . In this setting, we considered 4 target policies in the four cardinal directions, namely: In FourRooms environment with distractor and drifter cumulants (two distinct GVFs), we compare the following off-policy update styles: (1) Off-policy TD updates using IS ρ correction,Q(s t , a t ) = Q(s t , a t ) + α Q (c t + γρ t+1 Q(s t+1 , a t+1 ) -Q(s t , a t ) =δ Q ) M (s t , a t ) = M (s t , a t ) + α M (δ 2 Q + γ 2 ρ 2 t+1 M (s t+1 , a t+1) -M (s t , a t ) and (2) Expected Sarsa update in Eqs. ( 5) and ( 6). In Fig. 13 , we observe that Expected Sarsa leads to lower MSE, hence we use Expected Sarsa for all the TD updates in all the algorithms including baseline for further update stability. Continuous Environment. We extend the tabular GridWorld environment to a continuous state space, similar to the approach by McLeod et al. (2021) . The environment is a square of dimension 1 × 1 with four discrete actions. We evaluate two GVFs: the first GVF has a cumulant at the top-left corner, c 1 = N (µ = 100, σ = 5), and the second at the top-right corner, c 2 = N (µ = 50, σ = 5). The target policies are consistent with those used in the tabular environment. The agent receives a zero cumulant signal elsewhere and moves 0.025 units in the selected direction with added uniform noise U[-0.01, 0.01]. Episodes start randomly, excluding a 0.05 radius from the goal state, and end after 500 steps or upon reaching a 0.05 radius from the goal. Fig. 14 presents the individual MSE for both GVFs under standard Experience Replay and PER. Our method, GVFExplorer, consistently achieves lower MSE compared to baselines. Fig. 15 shows the absolute GVF value prediction error with PER for both the baseline RoundRobin and GVFExplorer. Fig. 16 illustrates the estimated variance from each GVF, underscoring the necessity for a sampling strategy that prioritizes high-variance return areas to reduce data interactions and ultimately reducing the variance and MSE. Fig. 17 depicts the trajectories sampled from baseline RoundRobin and GVFExplorer. Table 3 summarizes the performance of various algorithms in this continuous environment.Computation of True GVF Values. The true GVF values in a continuous environment are computed using a Monte Carlo (MC) method. The continuous state space is discretized into a grid, with an initial state sampled from each grid cell. We calculate the average discounted return over 200, 000 trajectories following policy π i with cumulant c i . The mean squared error (MSE) between the estimated and true GVF values is then computed using these discretized states, expressed asE i s V ci πi (s) -V ci πi (s)2 for all algorithms.Network Architecture. We use distinct deep networks for learning value Q and variance M . Both networks share a similar architecture, with a shared feature extractor for input states and separate output heads for each GVF, producing multidimensional outputs for both value and variance. The variance network includes a Softplus layer before each head's output to ensure positive numerical values. We conducted additional experiments using the DM-Control suite in the Mujoco environment, focusing on the Walker and Cheetah domains. For the Walker domain, we defined two distinct GVFs: walk and flip. In the Cheetah domain, we evaluated two GVFs: walk and run. To handle the continuous action space in these environments, we leveraged policy gradient methods, which are essential when working with continuous actions, as value-based methods like Q-learning are not directly applicable.(a) Avg V c i π i error(RoundRobin) (b) V c 1 π 1 error(RoundRobin) (c) V c 2 π 2 error(RoundRobin) (d) Avg V c i π i error(GVFExplorer) (e) V c 1 π 1 error(GVFExplorer) (f) V c 2 π 2 error(GVFExplorer)Our method can be incorporated with any policy gradient (PG) algorithm. For these experiments, we used Soft Actor-Critic (SAC) (Haarnoja et al., 2018) which provides stability in such settings. SAC uses an entropy regularizer to encourage exploration, where the regularization coefficient α is learned adaptively. This allows the agent to balance exploration and exploitation effectively. We present the SAC-GVFExplorer in Algorithm 2, a modified version of SAC designed to efficiently handle parallel estimation of multiple GVFs, each aligned with a specific target policy and cumulant.The first modification involves incorporating a separate variance network, M w d (s, a), which estimates the variance of returns and supports the behavior policy's objective to reduce mean squared error (MSE) in GVF estimation. This variance network, parameterized by weights w 1 and w 2 , updates alongside the Q-value critics to capture return variability more effectively.The Q-value target is calculated like in standard SAC algorithm, which uses double-Q trick and entropy term for enhanced exploration. A slight difference from standard SAC is sampling the next state action a ′ from the target policy π i (•|s ′ ).Q tar (s, a) = c + γ min d=1,2 Qθ d (s ′ , a ′ ∼ π i (•|s ′ )) -α log µ ϕ (ā|s ′ ) , ā ∼ µ ϕ (•|s ′ ),where α is the learned entropy coefficient and µ ϕ is the parametrized behavior policy. The variance target update, M tar , then incorporates the Q-value temporal difference (TD) error,δ Q = Q tar - min d=1,2 Q θ d (s, a), M tar (s, a) = δ 2 Q + γ 2 min d=1,2 M wd (s ′ , a ′ ∼ π i (•|s ′ )) -α log µ ϕ (ā|s ′ ) .To ensure the behavior policy does not diverge from target GVF policies π i , we introduce a KL regularization term that maintains alignment with each target policy by minimizing KL(µ ϕ (•|s) ∥ π i (•|s)).As computing exact Q-values is infeasible for continuous state-action domains, we approximate these values using Monte Carlo (MC) rollouts over 100 episodes for a fixed set of randomly selected 50 sampled state-actions. This MC approximation enables accurate computation of MSE by comparing learned Q-values with empirical MC estimates.Finally, the behavior policy µ ϕ is updated to minimize the MSE by focusing on areas of high variance, effectively improving estimation efficiency. Further, the entropy term is similar to standard SAC algorithm for improving the exploration. This update step, driven by the variance network, is computed as:∇ ϕ s∼D min d=1,2 M w d (s, ā) -α log µ ϕ (ā|s) + β N i=1 KL(µ ϕ (•|s) ∥ π i (•|s)) ,where action ā is sampled from µ ϕ (•|s). To support adaptive exploration, we update α by optimizing:-α log µ ϕ (•|s) + H,where H is the target entropy.With these adaptations, SAC-GVFExplorer effectively estimates GVFs values in continuous state-action domains, achieving lower MSE compared to baselines such as RoundRobin and UniformPolicy and performing well in complex Mujoco environments.We used TD3 to train target policies for each GVF and selected mid-level performing policies as target policies for the respective GVF tasks. This setup allows the behavior policy to efficiently gather data for parallel GVF estimation.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.38th Conference on Neural Information Processing Systems (NeurIPS 2024).The code is available on Github: https://github.com/arushijain94/GVFExplorer. 


Decision: The reviewers and I generally liked this paper. While the core algorithm is a bit obvious, the paper is well-written and makes a positive contribution to the RL literature on GVFs.  The paper has a nice mix of theory and empirical work, and addresses a problem that has not been previously studied, and provides proofs of correctness (never easy to do in an RL setting!).  The paper also provides a clear, well-written discussion of the issues surrounding GVFs.  Based on the alignment of all of these positive factors, I recommend acceptance.

Reviews: review: paper_summary: paper_summary: This paper presents a new algorithm for collecting data needed to learn multiple GVFs in parallel. By focusing data collection on high-variance (s,a) pairs, an agent is able to collect data that will reduce the variance of estimated GVFs. The authors contribute a sort of contraction-mapping proof that using their algorithm will result in non-increasing variances.
strength_weakness: strength_weakness: I have one minor-but-important quibble about the paper. In Thm. 4.2, the authors prove that aggregated variance is "<=" upon successive iterations. However, in the english description of the result, the authors state that the aggregated variances "decrease with each update step". 

This is NOT what you proved - you proved that aggregated variance "does not increase."  The same claim is made in the abstract, and again in the conclusion.  I think it's important to be clear on this point, so I would ask the authors to rephrase this.
questions: questions: I wonder if there are potential degeneracies in the algorithm. For example, if a behavior policy never tries a certain action, it seems like the M's for that action will be 0, and the new behavior policy will assign 0 probability to taking that action in the future, leading to a situation where you never get the data you need.  Similarly, if a certain state is never visited (in the tabular case), would the estimate of M be zero?

If so, does that imply that there is an unstated constraint on the initial behavior policy -- something about exploring states and actions sufficiently?

A related question: if the cumulant function is sparse, is it possible to not get enough non-zero data to get non-zero M estimates?

(by the way, it's these sorts of questions where I can kind of see that degeneracies may arise that will never get ironed by your algorithm, which is why the difference between "<" and "<=" in your proof is important)
limitations: limitations: It seems like a central limitation of the work is a disconnect between what was theoretically proven (which relies on a perfect knowledge of the variances M), and what will happen in practice (the M's must be estimated).

It would be nice if the paper outlined what happens to the algorithm as a function of the error in the estimates of M.
paper_summary: paper_summary: This paper propose a new algorithm to solve the general value function evaluations problem. In essence, GVFs can be seen as high dimensional value functions. The authors propose a temporal difference learning algorithm that minimizes the overall variance in the return distribution, in the hope to improve the behavior policy for better exploration, such that the samples the behavior policy produces better suffices for off-policy evaluations for each GVFs.
strength_weakness: strength_weakness: 1. The core idea behind this paper is to propose a solution to solve the data collection problem. This paper does answer the question of how to minimize the variance of the returns, but fail to convince me entirely why we should do that at the first place, either through proofs, or empirical investigation. I think this is the biggest weakness of the paper.
2.  The experiment section is nice and clear but the problem class is a bit simple (gridworld). For a paper without strong theoretical results, experiments are usually expected to have more materials. In this sense, the results are not very convincing.
questions: questions: Please see weakness above.
limitations: limitations: Yes.
paper_summary: paper_summary: This paper presents a novel method named GVFExplorer for efficiently evaluating multiple Value Functions with different policy (GVFs) in parallel using off-policy methods. It adaptively learns a single behavior policy that minimizes the total variance in return across GVFs, thus reducing required environmental interactions. The method uses a temporal-difference-style variance estimator and proves that each behavior policy update decreases the overall mean squared error in GVF predictions. The performance of GVFExplorer is empirically validated in various settings, including tabular and non-linear function approximation, with stationary and non-stationary reward signals.
strength_weakness: strength_weakness: - More experiments would help understand the behavior of the algorithm.
  - uniform policy being the best baseline does not seem to be a good baseline choice. Having some more competetive baselines, e.g. ablations, would have been much better.
  - experimented environments seem too synthetic. would like to see results on typical (and challenging) RL environments, e.g., mujoco.
questions: questions: - The paper starts with minimizing MSE, and argues that it uses unbiased IS estimation, leading to a policy that minimizes the variance of return. However, GVF in algorithm is estimated with $Q_\theta$, which has been learned with expected Sarsa, which is a baised estimate given that the target contains $Q_\theta$ instead of GT $Q^\pi$. How do we ensure that the analysis above also works in algorithm 1? What happens if our function approximator is crude so that the bias is large?

- Why does PER drastically improve the performance of GVFExplorer? If we have infinite number of data in our experience replay, GVFExplorer would have very similar effect as PER. In my opinion, it seems more natural to have reduced effect of PER as we are sampling hard states more with GVFExplorer, and it is what PER tries to do as well. (it also does not go well with the rest of the paper, as PER is about training efficiency where GVFExplorer is about the choice of behavior policy)
limitations: limitations: The authors adequately addressed the limitations.

Comments: title: Author response to Reviewer 3wne
Thank you for the response
Author's Response to Reviewer pomH
comment: Hello Reviewer, thanks for responding and raising the score.
Thanks for the response. I raised my score.
I thank the authors for the response. Judging from other reviews and the added experiments, I will keep the same score for now.
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.