Avoiding Undesired Future with Minimal Cost in Non-Stationary Environments

Authors: wen-bo  du
tian  qin
tian-zuo  wang
zhi-hua  zhou
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 13:28:17

Abstract: Machine learning (ML) has achieved remarkable success in prediction tasks. In many real-world scenarios, rather than solely predicting an outcome using an ML model, the crucial concern is how to make decisions to prevent the occurrence of undesired outcomes, known as the *avoiding undesired future (AUF)* problem. To this end, a new framework called *rehearsal learning* has been proposed recently, which works effectively in stationary environments by leveraging the influence relations among variables. In real tasks, however, the environments are usually non-stationary, where the influence relations may be *dynamic*, leading to the failure of AUF by the existing method. In this paper, we introduce a novel sequential methodology that effectively updates the estimates of dynamic influence relations, which are crucial for rehearsal learning to prevent undesired outcomes in non-stationary environments. Meanwhile, we take the cost of decision actions into account and provide the formulation of AUF problem with minimal action cost under non-stationarity. We prove that in linear Gaussian cases, the problem can be transformed into the well-studied convex quadratically constrained quadratic program (QCQP). In this way, we establish the first polynomial-time rehearsal-based approach for addressing the AUF problem. Theoretical and experimental results validate the effectiveness and efficiency of our method under certain circumstances.

Main paper: 
 introduction: 
 Machine learning (ML) models have found extensive application in prediction tasks [25] . However, in contrast to a sole emphasis on prediction, it is preferred in many real-world scenarios to further explore effective decisions if the predicted outcomes are undesired. For instance, imagine that a factory manager has trained an ML model on features X (e.g., economic indicators) to predict the outcome Y (e.g., monthly sales). Suppose at the beginning of a month, Y is predicted to be undesired, i.e., the predicted sales of the month are lower than expected. In this case, the manager usually wants to take action by altering some intermediate variables Z during the month to avoid this undesired outcome happening, e.g., modifying the discount to attract more customers. The problem of how to find effective actions in such situations is known as avoiding undesired future (AUF) [63] .It is worth noting that AUF tasks often involve limited opportunities for interaction with the decision environment [63] . For instance, in the aforementioned example, the factory manager can only adjust the selling strategy once per month. Therefore, decision-making algorithms that depend on numerous interactions, such as conventional reinforcement learning (RL) methods [4] , are not well-suited for the AUF problem [40] . Additionally, fundamentally vital decisions need to be made with human judgment, and therefore, it is desired to enable human decision-makers to understand why and how some actions can change the outcome. Due to these challenges, the structural relations among variables, which contain fine-grained information and are usually interpretable, are worth being considered to make decisions [36, 40] . [63] .Causation is such a type of structural relation [36] , which has been leveraged for some decision-making problems [5, 24, 42, 43] . Although causal relations can assist to some extent, identifying them is challenging and generally relies on some untestable assumptions [49, 44, 28] . Besides, causation should not be viewed as a prerequisite for decision-making problems, as humans can usually make good decisions without a thorough causal understanding [63] . Recognizing that correlation used in prediction is inadequate for decision-making whereas causation is too luxurious to be relied on, Zhou [63] emphasized the necessity of an intermediate relation that is stronger than correlation but less demanding than causation; this relation was subsequently called influence relation [64] . The relationship among correlation, influence, and causation is illustrated in Fig. 1 .Based on the influence relations, Qin et al. [40] developed the first rehearsal learning framework, which can effectively suggest good decision actions for the AUF problem in stationary environments. In practice, however, the method by Qin et al. [40] may lose its power when different decision actions are associated with different costs or when the decision environment is non-stationary where quantitative influence relations can vary. For example, modifying the discount into different levels results in different expenses, and the quantitative influence relation between pricing and sales can change seasonally for products such as the coat. Besides, it is worth mentioning that exact solutions are intractable with any polynomial-time algorithm when considering decisions on multiple variables in the previous work [40] , thus exploring more efficient approaches is necessary for the decisionsuggestion problem in the AUF problem.To tackle these issues, in this paper, we propose the AUF-MICNS approach for the AUF problem with minimal cost in non-stationary environments. AUF-MICNS considers a multi-round decision-making process where it suggests decisions and collects feedback data during and after each decision round. Note that although multiple decision rounds are allowed, the limited number of rounds may still render RL methods ineffective [40] . In contrast to Qin et al. [40] , we consider the non-stationary fact that influence relations may vary over decision rounds, and therefore, treating the round-wise collected data as i.i.d. samples for determining the influence relations is inappropriate. To this end, we present a sequential approach to maintain dynamic influence relations in non-stationary environments, and further propose an online-ensemble-based [60] sequential algorithm to deal with the unknown degree of non-stationarity. In addition, we design a cost function to quantify the costs of different decision actions. The cost function takes into account not only (a) different unit costs associated with different variables, but also (b) the distinct costs involved in altering a single variable to varying extents. Further, we expect that the suggested decisions can efficiently avoid undesired outcomes with a relatively high probability. Rather than using the sampling-based method that cannot be solved with any polynomial-time algorithm [40] , we reveal that finding decision suggestions for AUF with minimal action cost can be modeled as a convex quadratically constrained quadratic program (QCQP), which is solvable in polynomial time O(|V| 3 ) with respect to the number of variables |V|. Combining the parts above, we prove that our proposed approach can (a) accurately capture the dynamic influence relations with errors bounded by an exponentially decreasing term, and (b) efficiently suggest effective decision actions with minimal cost for the AUF problem.Our main contributions are summarized as follows. 1. We try to tackle the AUF problem with minimal cost in non-stationary environments. Our modeling approach considers, for the first time, the decision action cost and the non-stationary fact that influence relations can vary over time in the AUF problem. 2. We present a novel sequential methodology to maintain dynamic influence relations. Theoretical results guarantee that the estimate error can be bounded by an exponentially decreasing term, as well as a fixed small value related to the problem difficulty. 3. We develop the AUF-MICNS algorithm, which is the first polynomial time rehearsal-based approach that can suggest effective decision actions for the formulated AUF problem. Our experimental results validate the effectiveness and efficiency of the method.Organization. In Sec. 2, we review basic concepts and introduce our notation. In Sec. 3, we provide the formulation of AUF problem and provide the AUF-MICNS algorithm for solving the problem, together with theoretical guarantees. In Sec. 4, we introduce some related studies. In Sec. 5, we show the experimental results. At last, we discuss the limitations and conclude our work in Sec. 6. X Z 3 Y 1 Y 2 Z 2 Z 1 X Z Y (a) rehearsal graph G X Z 3 Y 1 Y 2 z 2 Z 1 X Z Y (b) G Rh(Z 2 =z 2 ) X z 3 Y 1 Y 2 Z 2 Z 1 X Z Y (c) G Rh(Z 3 =z 3 ) X z 3 Y 1 Y 2 z 2 Z 1 X Z Y (d) G Rh(Z 2 =z 2 , Z 3 =z 3 ) 
preliminaries: 
 A novel probabilistic graphical model called structural rehearsal model (SRM) is proposed by Qin et al. [40] to characterize influence relations among variables in the AUF problem. The SRM consists of a set of rehearsal graphs and corresponding structural equations { G t , θ t } t (t denotes the decision round). The detailed definition of SRM is listed in Appendix B.1.A rehearsal graph, denoted by G = (V, E), models the qualitative influence relations among variables. Specifically, the vertices V denote the variable set of the AUF problem and the edges E denote the influence relation among vertices. There are two types of edges in the rehearsal graph, the directional edge X → Y means that X influences Y , and the bi-directional edge X ↔ Y means that X and Y are mutually influenced. Additionally, the corresponding structural equations of variable V j s can be parameterized byEQUATIONwhereV j ∈ V denotes the j-th vertex in G t , PA Gt j {u | u → V j in G t } represents the parents of V j in G t ,and the noise ε j,t follows the distribution N (0, σ j2 ) for all t. Note that on one hand, causal relations are not always necessary in real world decision-making problems [63] ; on the other hand, causal models are sometimes insufficient for capturing the full scope of relationships between variables. For instance, the pressure and the temperature within a fixed volume of ideal gas are mutually influenced, as changes in either one of them affect the other. Such bi-directional influence relations are not well-represented by causal models, but can be naturally expressed by SRM [40] .Besides, finding suitable alterations is involved in addressing the AUF problem. An alteration ξ means a decision action that is specified by human decision-makers, denoting by a set of vertex-value pairs, e.g., ξ = {Z 2 = z 2 } in Fig. 2(b ). Meanwhile, rehearsal operation, denoted as Rh(•), represents executing a certain alteration, which changes the original graph structure as illustrated in Fig. 2 (b)-Fig. 2(d ). Specifically, rehearsal operation breaks original influence links that point into any vertices contained in ξ, and fixes the values in ξ to their associated vertices; while this operation maintains influence relations among other vertices in the associated alteration graph G. Since alteration and rehearsal operations are always considered together in the AUF problem, for simplicity, we will use the term alteration exclusively throughout the paper, unless otherwise specified. 
the proposed approach: 
 This section is dedicated to addressing the aforementioned AUF problem. In Sec. 3.1, we provide the probelm formulation. In Sec. 3.2, we propose the AUF-MICNS method for AUF. Later in Sec. 3.3, theoretical results are provided to ensure the effectiveness of our approach.This paper focuses on suggesting decisions to avoid undesired futures when an undesired outcome is predicted by an ML model. Since effective prediction models are widely applied in various domains [25] and work well even in non-stationary environments [62] , we consider the case that the predictive ML model is always available and are not concerned about how to train it.We formulate the AUF problem with minimal cost in non-stationary environments as a multi-round online decision-making process, where the decision-maker should perform round-wise alterations to avoid undesired outcomes. In each decision round, there are two essential time points, the time that the ML prediction is made, and the time just before the generation of the concerned outcome Y. As separated by the two time points, the variables fall into three consecutive time segments: X, Z, and Y as illustrated in Fig. 2 (a). In t-th round, a decision-maker first observes variables X t = x t , and an ML model provides a prediction Ŷt as the outcome subsequently. Denote the desired region of Y t as S, if Ŷt ∈ S, the decision-maker would perform alterations on Z t (only once) based on the whole historical data, and the true Y t will occur after the alteration.It is worth mentioning that in decision round t, two crucial concerns for making decisions are (a) how to perform effective alterations that make Y t ∈ S with high probability; and (b) how to minimize the alteration cost as much as possible. For the former, we seek to ensure that P (Y t ∈ S | θ t , x t , Rh(ξ t )) ≥ τ ; where ξ t is the selected alteration, and τ is the expected probability that the alteration can successfully avoid the undesired outcome. For the latter, we generalize a continuous cost function from the discrete cost measure [61] to quantify the cost for different alterations. The cost function is defined as the sum of the respective costs associated with each altered variable, and follows the increasing marginal cost property (see Appendix B.2 for details) in economics [32] , properly measuring the alteration cost. Given the expectation that the future outcome will likely fall into S after performing the alteration, the decision maker consistently prefers the alteration with the least alteration cost. Thus, the AUF problem can be ideally formulated as follows in practice:EQUATIONwhere w i > 0 represents the cost coefficient for each intermediate variable Z i ∈ Z, Z ξt i represents the values of Z i after alteration ξ t while Z 0 i is the datum point that associates with the minimum alteration cost relatively. Besides, ϑ t = arg min ϑ E ε ϑθ t is the ideal estimation of θ t since θ t is not available in practice. Note that w i s and Z 0 i s are user-specified because the cost of the same decision alteration can vary for different decision-makers.In the following, we focus on a basic but essential class of the AUF problem, where the structural equations f t in Eq. ( 1) are linear but dynamic, the desired set S in Eq. ( 2) is a convex polytope, and the rehearsal graph G is known and fixed (i.e., G t G) for a convenient illustration. Letd ∈ R s , M ∈ R s×|Y| , β j ∈ R |PA G j |×1, dynamic structural equations and the desired region can be formulated as:EQUATIONNote that ϑ t in Eq. ( 2) is usually not available as discussed later in Sec. 3.2.1, thus finding surrogate estimations θt with bounded error E ε θtθ t is necessary. Noticing that the noise distributions for ε j,t s in Eq. (3) do not change over time, the variances of ε j,t s can be estimated by various Bayesian learning methods [6] . Thus, we mainly focus on estimating influence parameters β j,t s in what follows, and we use θ t to represent {β j,t }s only unless otherwise specified. Another challenge lies in how to efficiently solve the optimization Eq. ( 2) under the probabilistic constraint, since the sampling method used in the previous work has been proven to be time-consuming [40] . In Sec. 3.2, we propose the AUF-MICNS algorithm to tackle the aforementioned two challenges. AUF-MICNS can maintain the dynamic influence relations accurately and suggest alterations to avoid undesired outcomes effectively, and the performance can be guaranteed by theoretical results in Sec. 3.3.In this subsection, we propose the AUF-MICNS algorithm to address the AUF problem as formulated in Eq. (2). AUF-MICNS consists of two components, influence maintenance and alteration suggestion. We first introduce the components respectively, then we discuss how to combine them together.As illustrated in Eq. ( 2), the precondition for making effective decisions in the AUF problem lies in the accurately estimated θ t s. Specifically, to accurately estimate the parameter vector β j,t ∈ θ t in t-th decision round, we would like to minimize the expected squared lossE εj V j -β j,t PA j 2 ,where V j is the j-th vertex in rehearsal graph, and PA j denotes the parents of V j . Ideally, according to the law of large numbers (LLN), if we could obtain sufficient i.i.d. samples in time t, we can estimate β j,t by minimizing the empirical error j,t (β j,t ) as a substitute:EQUATION)where n is the number of samples that we can obtain in round t, and the superscript k means that it is the k-th sample. It can be guaranteed in lemma C.3 that this estimation converges to the true value as n increases. However, in real-world cases, we can only obtain a single sample after each decision round, so it is inappropriate to calculate the parameters as above, since the solution to Eq. ( 4) is far from accurate in this data-limited situation, where the surrogate loss is:EQUATION)Besides, mixing the round-wise selected {V j,t , PA j,t } T t=1 to estimate parameter β j,t as the classic empirical risk minimization (ERM) [34] methods do is inappropriate as well, because data selected in different rounds possibly obeys different distributions in non-stationary environments. Fortunately, in the field of online learning [52, 14, 17] , there exist many types of algorithms to estimate parameters sequentially with limited samples. Online gradient descent (OGD) [65, 47] is a typical class of online learning algorithms, which takes advantage of the gradient descent idea to handle the round-wise selected data. Once the selection of the step size (learning rate) in OGD is tailored to the varying speed of the environment, i.e., employing a larger step size for rapid changes and a smaller one for gradual changes, parameters can be effectively updated with limited data after each round. We customize OGD for estimating quantitative influence relations βj,t ∈ θ t sequentially in Algorithm 1. Receive (PA j,t , V j,t ) and send to eachE η Output: estimated { βj,t } T t=1To avoid this risk, we turn to use online-ensemble [60] based methods. Online ensemble is a type of algorithm that combines the idea of ensemble and sequential updating, maintaining multiple base learners and ensembling them together. Specifically, as illustrated in Algorithm 2, we maintain N j base estimators with a weight vector w. After each round, all experts update their estimates by the collected data, and the weight vector w will be updated as well by different losses related to different experts. By ensembling all experts with the weight w, we can obtain the final estimator.In t-th decision round, since we can obtain the estimation θt for true θ t by Algorithm 2, then we substitute ϑ with θt in Eq. (2). To suggest alterations efficiently and effectively, another crucial aspect is finding ways to delineate the feasible domain of the probabilistic constraint in Eq. ( 2). We first present a supporting result in Lemma 3.1 as follows, which is needed in our method to find the alteration that can make Y t ∈ S with an expected probability τ .Lemma 3.1 (Qin et al., 2023) . Given x t , θ t , it holds that:  and z ξ t are intermediate variables with alteration ξ. Recall from Eq. ( 2) that we want to find alterations that satisfy P(Y t ∈ P | θ t , x t , Rh(ξ t )) ≥ τ . Recognizing that solving optimization with probabilistic constraint is generally intractable and the previous sampling method is time-consuming, we attempt to construct a surrogate deterministic constraint that can be handled efficiently to replace the probabilistic constraint. Fortunately, this idea is feasible because Lemma 3.1 shows that once the alteration is selected, the randomness of Y t only arises from ε t , since x t has been observed and A, B, C are constant matrices given θ t . Thus, the probability density function (PDF) of Y t is available and we can directly analyze the PDF to find probability regions as in Prop. 3.2, which aids in constructing the surrogate deterministic constraint.Y t = Ax t + Bz ξ t + Cε t , where A, B, C are constant matrices of appropriate shapes based on θ t , ε t = [ε 1,t , . . . , ε |V|,t ] ∼ N (0, Σ),Proposition 3.2. The following probability region P satisfies P(Y t ∈ P | θ t , x t , Rh(ξ t )) = τ :P = µ yt + χ -1 (τ )CΣC 1 2 u u 2 ≤ 1 ,where µ yt = Ax t + Bz ξ t , u is an arbitrary point in the unit sphere in R |Yt| , and χ -1 (•) denotes the quantile function of the χ 2 distribution with degrees of freedom λ = |Y t |.The proof of Prop. 3.2 is provided in Appendix C.4. We raise the power of 1/2 to the matrix because it is always positive semi-definite since χ -1 (•) ≥ 0 and CΣC 0 (Σ is the covariance (a) Samples from Fy t (b) Probability region P Figure 3 : An example of estimated P with τ = 0.9 matrix). In practical scenarios where Σ is not available, the estimation Σ can be used as replacements. Let F yt denote the cumulative distribution function (CDF) of Y t , Fig. 3 illustrates a 2-dimensional example of samples from F yt , together with the estimation of the associated region P. It illustrates that P can properly draw the probabilistic region of F yt with expected probability τ .Moreover, recognizing that the desired region S defined in Eq. ( 3) is a convex polytope, i.e., S = y ∈ R |Y| | My ≤ d , we utilize the defined probability region P in Prop. 3.2, and use a deterministic constraint to replace the original probabilistic constraint in Eq. ( 2). In this case, the alteration-suggestion method can be formulated as follows:EQUATIONwhereP = χ -1 (τ )CΣC 1 2 ,• 2,row means an operator that takes 2-norm for each row of the matrix thus outputs a row-dimensional vector. The objective to be minimized is the vector representation of the cost function as explained in Eq. ( 2), where W = diag(w 1 , . . . , w |z ξ t t | ) is positive definite since the cost is non-negative, i.e., w i > 0 for ∀i.Note that W is positive definite and the constraint is linearly associated with z ξt t , thus Eq. ( 6) is a convex QCQP, which can be cast as a second-order cone program [35, 30] By combining the influence maintenance step and the alteration suggestion step, our proposed approach for addressing the AUF problem with minimal cost in non-stationary environments is formulated in Algorithm 3, which attempts to avoid undesired outcomes in each decision round. Specifically, in t-th round, the algorithm first receive X t = x t , then if the predicted outcome Ŷt ∈ S, the algorithm performs the suggested alteration ξ t on Z t by solving Eq. ( 6). Subsequently, true Y t = y t occurs, and the algorithm collects {x t , z ξt t , y t } to update influence relations by Algorithm 2. By using this algorithm, one can tackle the formulated AUF problem with the suggested alterations.In this subsection, we present the theoretical analysis of our proposed method. All proofs are given in Appendix C. First, we can determine the dynamic influence relations in non-stationary environments with theoretical guarantees. Specifically, by using Algorithm 1 to estimate β j,t ∈ θ t , the error gap between the estimate and the true parameter value (E εj βj,tβ j,t2 ) is proved to be bounded by an exponentially decreasing term, as well as a fixed value related to the choice of step size and the inherent problem difficulty. It reveals that the performance of Algorithm 1 depends on the choice of step size η heavily, and is detailed in Thm. 3.3, where { j,t (•)} T t=1 s are defined in Eq. ( 4). Theorem 3.3. Let β j,t (j ∈ [|V|]) denote the true parameter value of β j in time t, and choose η j ∈ (0, 1/2L j ] as the step size used in Algorithm 1, then it can be bounded that:E βj,t -β j,t 2 (1 -µ j η j ) t m βj,0 -β j,0 2 + δ j with δ j = m∆ j µ j η j 2 + η j σ 2 µ j ,where µ j and L j are the minimal and maximal eigenvalues of { j,t (•)} T t=1 's Hessian matrices, σ 2 upper-bounds the variance of ĝj,t , ∆ j ≥ max t β j,t+1 -β j,t upper-bounds the varying speed of the environment, and m is the longest continuously altered rounds of V j , for most of the V j s, m = 1.In Thm. 3.3, it holds that µ j η j ∈ (0, 1/2], which derives that (1 -µ j η j ) ∈ [1/2, 1). This shows that as time progresses, the OGD estimator βj,t will gradually converge towards the true value β j,t in the expected sense. Specifically, (a) the convergence speed depends on the choice of the initial point βj,0 , and is limited by the inherent difficulty of the problem implied in µ j /L j ; and (b) the convergence result will suffer a δ j gap from the true value, depending on the varying speed of the environment (∆ j ) and the choice of step size η j . If η j is appropriately chosen, the gap δ j will be small, e.g., if all hyperparameters are available and∆ j = 0, choosing η j = min{1/2L j , 3 √ 2( m∆j √ µj σ ) 2 3} can achieve the smallest δ j . Meanwhile, the hyperparameter m appears in the bound according to the properties of alterations shown in Fig. 2 . If V j is continuously altered in m rounds, all incoming arrows of V j will be removed and the parameters associated with the arrows will not be updated in those rounds. Because only a part of vertices in Z t might be altered in any rounds, m = 1 holds for most of the V j s.In practice, we do not know exact parameters such as ∆ j , thus η is not pre-available. Recognizing that the random choice of η leads to unstable estimations, we turn to use Algorithm 2 to estimate βj,t s. Though we do not know η as well, by using the online-ensemble-based Algorithm 2, we can get more stable estimations as guaranteed by the following regret bound in Prop. 3 by choosing α = ln N j /T in Algorithm 2, where N j is the number of base-learners, β η j,t is the estimation from any expert η in expert set H j in Algorithm 2.Prop. 3.4 shows that the cumulative loss of the estimation obtained by Algorithm 2 is comparable with the best expert in H j , thus by Thm. 3.3, though θt may be far from θ t at the first few rounds, it will converge towards θ t . Meanwhile, in some certain cases, the best step size η j in Thm. 3.3 can be included in H j with N j = O(log T ) [60] . Due to these, Algorithm 2 provides more stable estimates for the influence relations, which can further aid in making decisions to address the formulated AUF problem. As to the decision-making processes, AUF-MICNS can suggest alterations with theoretical guarantees. Specifically, the suggested alterations are guaranteed by Thm. 3.5.Theorem 3.5. By using the suggested alterations ξ t from Eq. ( 6), it can be guaranteed that:P Y t ∈ S | θt , x t , Rh(ξ t ) ≥ τ.Thm. 3.5 illustrates that the suggested alterations ξ t by the AUF-MICNS algorithm can effectively avoid the undesired outcomes as the formulated AUF problem expects, under the distribution conditioned on estimation θt rather than true θ t . Note that it is guaranteed in Thm. 3.3 and Prop. 3.4 that θt is not far from θ t . Meanwhile, we provide the experimental analysis in Sec. 5 to show that P (Y t ∈ S | θ t , x t , Rh(ξ t )) ≥ τ holds practically. Besides, this method achieves a super-exponential improvement over the time complexity of the previous method [40] as discussed in Sec. 3.2.2.4 Related work RL Methods. RL approaches have demonstrated success in numerous domains [51] , particularly in game-playing [33] and autonomous control [21] . However, the Markov Decision Process (MDP) formalism in RL abstracts decision-making processes into states, actions, and rewards, potentially overlooking useful fine-grained structural information. While hybrid online and offline RL methods have been introduced [48, 37] , they overlook fine-grained structural information as well and require large offline datasets in practice. Moreover, it is worth noting that a fundamental limitation of applying RL to the AUF problem is that RL methods require a substantial number of interactions, which may be too luxurious or simply not tolerated in many real-world applications.Causality. Identifying causal systems from observational and interventional data has been extensively studied [44, 50, 7, 58, 9] , but these methods typically do not actively select interventions. Furthermore, significant research has focused on identifying causal structures or effects in interactive environments [18, 22, 53, 55, 39, 54, 57, 41] , which predominantly aim to identify causal structures or effects. To incorporate additional utilities for decision-making, causal bandits and causal RL methods have been proposed to determine where to intervene [5, 24, 46, 26, 59, 12, 31] . The aforementioned methods generally rely on causal modeling, which may be luxurious or restrictive in some real-world decision-making cases [63, 40] . As identifying causations rely on some strong restrictions or assumptions, it is possible that we cannot find a feasible alteration. Conversely, correlation, which underpins most ML models, falls short of providing a solid foundation for making decisions. As a middle ground between causation and correlation, the influence relations form a more practical basis for decision-making [63] . Building on this concept, we employ the SRM developed by Qin et al. [40] , which can adapt to dynamically evolving decision systems. In particular, our approach incorporates the context x t into decision-making, and can sugggest decision alterations effectively even when the parameters of the system are non-stationary and the actions come with varying associated costs.Other related topics. Our approach builds upon several classic ML techniques. The action cost measure employed in our method generalizes principles from cost-sensitive learning [13, 61] . Additionally, we adapt the online ensemble methodology [60] to update the SRM parameters. Online emsemble framework has been used in several areas, such as online convex optimization [56] , online label shift [38] , and reinforcement learning [27] . Further exploration and advancements in these techniques hold the potential to enhance our approach as well. Value of (1) CO2 and (1)True Value (1) CO2, tEstimation (1) CO2, t  
experimental result reproducibility: 
 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: The code and data for the main experimental results are provided in the supplemental material. Dataset and experimental details are introduced in Sec. 5 and Appendix D.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. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (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. 
experiments: 
 We evaluate the proposed AUF-MICNS algorithm on two datasets and focus on four aspects including (a) success frequency for Y t ∈ S; (b) average alteration cost; (c) average executing time; and (d) mean square error of the estimated parameters θt . For each dataset, we repeat experiments with 100 rounds 20 times. The observational dataset size is set to 10. We compare our proposed method with previous rehearsal learning approach (QWZ23 [40] ), and we also compare with several classic RL methods including DDPG [29] , PPO [45] , and SAC [15] . Experimental details and additional experiments are listed in Appendix D.Market-Managing Data. We abstract a dynamic SRM from a market-managing scenario, where a manager of the market needs to make decisions to promote the total profit (TPF) and the number of customers (NCT). We consider variables that may affect TPF and NCT, the pricing for the product (P), the pricing of the competitor market (E), the cost of raw materials (C), etc. We assume the manager can alter two variables, P and C. There exist mutually influenced variables in the scenario: If P is set to be small, then E will also be small to stay competitive on price; and vice versa. The sizes of X t , Z t , and Y t are 2, 4, and 2 respectively. The parameters of the dynamic structural equations are manually set according to the domain knowledge. For example, parameters associated with variable C vary over time with a periodic term, i.e., β C,t = βC (1 + a sin(wt)). The feasible alteration values are [-3, 3] for centralized P and C, associated with cost coefficients 1.0 and 2.0 respectively since altering P is easier than C. We want to maintain high TPF and high NCT at the same time, so the desired region S is set to be S = {TPF ≥ s 1 , NCT ≥ s 2 , TPF + NCT ≥ s 3 }, and more than 80% of the original data falls outside this range, as shown in Fig. 7(a) .Bermuda Data. This is an ecology dataset that records environment variables in Bermuda [10] , and the generation order of variables is available [3] . The sizes of X t , Z t , and Y t are 3, 7, and 1. The structural equations are obtained by fitting linear models on normalized data [40] , and we manually add the varying trend, e.g., considering the annual increase in CO 2 emissions, we posit that there is an increasing trend in the influence relation between temperature and CO 2 concentration, i.e., β CO2,t = βCO2,t • (1 -a e -wt ). We assume that 5 variables in Z t are actionable [1] and the feasible alteration values are [-1, 1] for each of them with different cost coefficients. The concerned outcome Y t represents the net coral ecosystem calcification (NEC) in Bermuda. To make the coral reef ecosystem healthy, a relatively large NEC is preferred, so the desired region S is set to be S = {0.5 ≤ NEC ≤ 2}, and more than 75% of the original data falls outside it, as shown in Fig. 7(b) . Fig. 4 shows the full experimental results. The desired probability is set to τ = 0.7. Two rows of figures denote the results of the Market data and the Bermuda data respectively. Specifically, the first column of Fig. 4 shows that (a) the success frequency of making the concerned outcome Y t falls into the desired region S; and (b) relative alteration cost among methods, i.e., the normalized cost among different methods. The proposed AUF-MICNS algorithm outperforms other competitors in both aspects. If we increase the interaction rounds T , RL methods can achieve satisfying performance, e.g., DDPG achieves 0.6955 average success frequency when T = 4000 on the Market data.The second column of Fig. 4 shows the mean-square error of estimates for β NCT in Market data and estimates for β CO2 in Bermuda data respectively. The exponential convergence speed and the convergence error (δ j ) in Thm. 3.3 are illustrated in these two figures. Specifically, for Marketmanaging data, the online-ensemble-based sequential method can achieve a similar convergence speed like OGD with η = 0.025 does when T ≤ 20, and it results in a smaller δ j as illustrated by the enlarged part (T ≥ 40). For Bermuda data, OGD with η = 2.5 outperforms other step sizes, since η = 1.0 converge slowly, and η = 5.0 suffers a notably bigger gap δ j . By using the online-ensemblebased sequential method, we can obtain a comparable performance with the best step size η = 2.5. These results illustrate that our proposed method mitigates the risk substantially, as the inappropriate choice of η will affect the practicality of the estimation and η is not available practically. Meanwhile, the third column of Fig. 4 shows true parameter values and the estimates by the online-ensemble-based method. The superscript (1)/(2) means the first/second dimension of the associated parameter vector.It shows that the error gap between βj,t and β j,t converges to a small value rapidly, which guarantees accurate estimates of the quantitative influence relations in possibly non-stationary environments. At last, the average whole-executing time of the 20-times experiments is recorded in Table 1 . We mainly focus on the comparison between AUF-MICNS and QWZ23 since both of them maintain influence relations other than purely suggesting decisions. It shows that our proposed method is more time-efficient than QWZ23.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: The code and data for the main experimental results are provided in the supplemental material. The dataset used in the experiments is also accessible from the link of the reference.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion: 
 Practically, different decision actions might correspond to different costs, and the influence relations might vary over time in non-stationary environments. In this paper, we try to tackle the AUF problem considering the aforementioned aspects. Specifically, we propose the AUF-MICNS algorithm that can capture the dynamic influence relations in non-stationary environments and suggest actions based on the influence relations. This method can suggest decision actions under polynomial time. Meanwhile, theoretical results show that the suggested actions can effectively avoid the undesired outcomes with probability larger than τ , and the suggested actions get more accurate as time progresses.Experimental results validate the effectiveness and efficiency of our proposed method.Our approach primarily focuses on scenarios where the influence relations among variables are linear and is currently not applicable to non-linear cases. Additionally, selecting the hyperparameter τ in existing frameworks remains a significant challenge, as an inappropriate τ may lead to the failure of solving Eq. ( 6). To address these limitations, we plan to develop methods that handle non-linear cases and reduce sensitivity to the hyperparameter τ in future work.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: Dataset and experimental setting are introduced in the core of the paper (Sec. 5). The full details are provided in Appendix D and the code contained in the supplemental material. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. Guidelines:• The answer NA means that the paper does not include experiments. • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The time of execution is denoted in Table 1 . Information on the computer resources is introduced in the first paragraph of Appendix D.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: The dataset used in the experiment is properly cited including a URL in reference. Meanwhile, the original papers of models used in the competitive experiment are properly cited.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. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: The code and model introduced in the paper are well documented, and the documentation is provided alongside the 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. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • 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: Two crucial points should be discussed in this approach, i.e., (a) dynamic influence modeling; and (b) the defined cost function for alterations. For the former, we consider a linear case with additive noise, and for more complicated scenarios than linear ones, one can modify the structural equations in Eq. ( 3) by using methods such as the kernel method [20] . Note that Theorem 3.3 always holds as long as the new loss functions j,t(•)s are still µ-strongly convex and L-smooth in those cases, similar to Eq. ( 4). For the latter, we use a quadratic cost function in this paper. Since the alteration cost is user-specified, in certain problems, if the quadratic cost is not appropriate, one can replace it with any other convex functions under the increasing marginal cost (IMC) property [32] . In those cases, the alteration selection method is a convex optimization as well, similar to Eq. ( 6). It is worth noting that our work mainly focuses on cases where samples are rare, thus only user-specified hyperparameters {wj, z 0 j } j∈[|V|] can be relied upon. If we can obtain a sufficient number of alteration, cost pairs, hyperparameters {wj, z 0 j } j∈[|V|] can be accurately estimated using quadratic fitting techniques [16] . Additionally, for the probabilistic constraint in Eq. ( 2), if the noise is not assumed to be normal anymore, one can analyze the CDF of the noise distribution to find a new probability region with a similar approach. This can further assist in constructing a substitute constraint. Moreover, there are instances where the feasible domain of the constraint in Eq. ( 6) may not exist due to its stringent nature, e.g., one aims to completely avoid undesired futures with 100% probability, or the desired region S is not practically achievable. In such cases, the decision-maker should consider verifying specified region S or reducing hyperparameter τ to some extent.Last but not least, though we mainly focus on the scenario where the graph structure is fixed and known, i.e., Gt = G, however, our approach can be straightforwardly adapted to the case where Gt = G but unknown as assumed in Qin et al. [40] as detailed in Appendix A.3. We also provide a simple comparable experiment on Bermuda data in the setting of Qin et al. [40] , as illustrated in Appendix D.1.The SRM and Rh(•) operations are similar to their counterparts in causal inference but have different applicating scenarios. The differences between rehearsal learning and causal learning are listed as follows:1 Most of the causal learning problems focus on structure or effect identification, while the decisionmaking process is not directly involved in the modeling. In contrast, rehearsal learning mainly focuses on a class of decision-making problems that specializes in the goal of avoiding undesired future using SRM-based modeling.2 Causal learning utilizes the SCM. In contrast, rehearsal learning uses the SRM (a new probabilistic graphical model [40] ) to model the influence relations between the variables toward addressing the AUF problem. The modeling granularity of SRM is more flexible, as the influence relationship can be evolved, and mutually influenced. Specifically,• Possible dynamic influence relationships. For instance, the influence relationship between pricing and sales of coats can vary cyclically and trend-wise over time. Thus, a given price may result in fewer sales during summer compared to winter. In addition, the coat's style may gradually become outdated, leading to reduced sales at the same price a year later compared to the present. • Possible mutually influenced relationships. For instance, the ideal gas law states that the pressure p, volume V , amount of substance n, and absolute temperature T obey the equation pV = nRT (R is the ideal gas constant). When a fixed volume V of an ideal gas is considered, with n and R held constant, the pressure p and volume V can be represented as a pair of mutually influenced variables within an SRM modeling.There are four possible cases of the graph structure, specifically:1 Gt fixed, known. It's the setting in our paper.2 Gt fixed, unknown. It's the setting in Qin et al. [40] . Our method can be straightforwardly adapted to this case. Technically, since the distribution P(G) is discrete, we can initialize and update the probability mass function (PMF) P(G) in the same manner as Qin et al. [40] . Thus, when we want to select decision alterations, the maintained PMF P(G) can be utilized to marginalize G fromP(Y ∈ S | G, • • • ).thereby the expectation of matrices A, B, C in Eq. ( 6) can be obtained and used. 3 Gt not fixed, known. Our method can be directly used because once the graph structure is known, G is not a stochastic component. Thus, matrices A, B, C in Eq. ( 6) can be obtained in the same manner. It is worth noting that the changing graph structure will lead to the birth of new parameters at each round. Therefore, though the method can be directly used in such case, establishing theoretical guarantees is difficult.4 Gt not fixed, unknown. In this case, neither θ nor PG can be accurately estimated as there is only one sample per round. Thus, dealing with such a case may need to additional assumptions. For example, consider there are a sufficient number of samples per round. In this case, our method can model θ and PG accurately, thereby suggesting good decisions.In this section, we present full definitions and discussions for the Structural Rehearsal Model (SRM), which is a probabilistic graphical model proposed by [40] to characterize the influence relations among variables.• Definition of the Rehearsal Graph Definition B.1 (Mixed graph, [40] ). Let G = (V, E) be a graph, where V denotes the vertices and E the edges.G is a mixed graph if for any distinct vertices u, v ∈ V, there is at most one edge connecting them, and the edge is either directional( u → v or u ← v ) or bi-directional (u ↔ v). Definition B.2 (Bi-directional clique, [40]). A bi-directional clique C = (V c , E c ) of a mixed graph G = (V, E) is a complete subgraph induced by V c ⊆ V such that any edge e ∈ E c is bi-directional.C is maximal if adding any other vertex does not induce a bi-directional clique.Definition B.3 (Rehearsal graph, [40] ). Let G = (V, E) be a mixed graph. Let {Ci} l i=1 denote all maximal bi-directional cliques of G, where Ci = (V c i , E c i ). G is a rehearsal graph if and only if:1. V c i ∩ V c j = ∅ for any i = j. 2. ∀i ∈ [l], if there is any edge pointing from some u ∈ V\V c i to some v ∈ V c i , then ∀v ∈ V c i , u → v.3. There exists a topological ordering for {Ci} l i=1 following the directions of directional edges between Cis.It can be found that the topological ordering for bi-directional cliques {Ci} l i=1 in the rehearsal graph reflects the time order of the generation process of variables.In this paper, we present the definition of dynamic structural equations in Eq. ( 1), which provides a quantitative computational formulation for the influence relations in non-stationary environments.In fact, the structural equations are defined among the bi-directional cliques {Ci} l i=1 as detailed in Qin et al. [40] . Specifically, the dynamic structural equations can be denoted as θt, which consists of the set of parameter matrices {βi,t} T t=1 and the covariance matrix Σi of each clique Ci in the rehearsal graph G. It is noteworthy that the quantitative influence relationship of a directional edge A → B for A ∈ Ca, B ∈ C b at time t is modeled in the parameter matrix β b,t since the topological ordering for bi-directional cliques reflects the time order of the generation process; while the quantitative influence relationship of a bi-directional edge D1 ↔ D2 for D1, D2 ∈ C d at time t is modeled in the covariance matrix Σ d since they are in the same bi-directional clique which is viewed as happening in the same time.We present a simplified version of the definition of dynamic structural equations in Eq. ( 1) for a convenient presentation, which defines the dynamic structural equations on the variable level rather than the clique level. Note that for each variable Vj ∈ Ci, the associated parameter vectors {βj,t} T t=1 can be directly found in the corresponding parameter matrices {βi,t} T t=1 ; while the variance σ 2 j of each variable Vj ∈ Ci can be derived from the corresponding covariance matrix Σi by marginalizing the desired dimension out, since the marginalization operator for multi-normal distribution is available.In this section, we introduce the increasing marginal cost (IMC) property. Increasing marginal cost (IMC), or rising marginal cost, is an important property in microeconomics [23, 32] . We first present a famous example in the field of microeconomics, called Thirsty Thelma's Lemonade Stand.Lemonade Stand is a business simulation game devised in 1973 by Bob Jamison under the Minnesota Educational Computing Consortium. It offers players the experience of managing a lemonade stand across multiple rounds. At the commencement of each round, players make decisions regarding their stock, pricing, and advertising based on their current financial standing. The outcomes in each round are determined by the player's choices; and are further influenced by random events like thunderstorms and street closures. After each round, a summary of the current status of the player is provided, and the game concludes after 12 rounds. In this game, an essential quantity is the total cost of lemonade per glass, which will increase in a quadratic way, as it has a linearly increasing derivative (named the marginal cost) as shown in Fig. 5 . This phenomenon is commonly observed in real-world scenarios, and the upward slope of the total cost curve reflects the property of the law of diminishing marginal product [32] . When Thirsty Thelma produces a small quantity of lemonade, her workforce is limited, and much of her equipment remains idle. The ease of utilizing these unused resources results in a substantial marginal product for an additional worker and a corresponding small marginal cost for producing an extra glass of lemonade. In contrast, as she increases lemonade production, her shop becomes crowded with workers, and most of her equipment is fully utilized. While additional workers can contribute to increased production, they must operate in crowded conditions and may face delays in equipment usage. Consequently, when the quantity of lemonade produced is already high, the marginal product of an extra worker diminishes, leading to a significant increase in the marginal cost of producing an extra glass of lemonade. It is a famous and widely used example in the field of microeconomics, and it has many similarities with the AUF scenario. In our proposed cost-minimal AUF problem, when the decision-maker decides to alter some variables in Zt, the cost associated with different alterations vary. For the same variable, the cost of altering it from a datum point should have a similar shape to the total cost curve in Fig. 5 , varying with an increasing derivative. That is how we define the cost function in this paper. The cost function could be replaced by any other convex function in different situations.In this section, we provide proof for claims in the main text.C.1 Proof for Proposition 3.2Lemma C.1. If Σ is a symmetric positive definite matrix, the following two sets are equivalent:x : x Σ -1 x ≤ 1 ⇔ x : x = Σ 1 2 u | u 2 ≤ 1 ,where x and u are vectors with a center at the origin of the coordinate system O.Proof. Assume P1 = x : x Σ -1 x ≤ 1 and P2 = x : x = Σ 1 2 u | u 2 ≤ 1 .Then what we need to prove is equivalent to:(1) Points contained in P1 have to be contained in P2.(2) Points contained in P2 have to be contained in P1.For (1), it holds that x Σ -1 x ≤ 1, which is equivalent to (Σ -1 2 x) (Σ -1 2 x) ≤ 1. Thus, let u = Σ -1 2x, it can be derived that x = Σ 1 2 u where u 2 ≤ 1, and (1) is proved.For (2), we replace x Σ -1 x with x = Σ 1 2 u, then it can be derived that:x Σ -1 x = u Σ 1 2 Σ -1 Σ 1 2 u = u u ≤ 1,which shows that points contained in P2 are also contained in P1, so (2) is proved. In conclusion, the lemma is proved.Proposition 3.2. The following set P is a probability region that satisfies P(Yt ∈ P | θt, xt, Rh(ξt)) = τ :P = µy t + χ -1 (τ )CΣC 1 2 u u 2 ≤ 1 ,where µy t = Axt + Bz ξ t , u is an arbitrary point in the unit sphere in R |Y t | , and χ -1 (•) denotes the quantile function of the χ 2 distribution with degrees of freedom λ = |Yt|.Proof. Recall from Lemma 3.1 that:εt ∼ N (0, Σ) , Yt = Axt + Bz ξ t + Cεt.From the property of multi-normal distributions, it holds that:Yt ∼ N Axt + Bz ξ t , CΣC .Let µy t = Axt + Bz ξ t , then we normalize the distribution above, it can be derived that:CΣC -1 2 (Yt -µy t ) ∼ N (0, I) .So it can be derived that:(Yt -µy t ) CΣC -1 (Yt -µy t ) ∼ χ 2 λ, where the χ 2 distribution has the degrees of freedom λ = |Yt|.Let χ -1 (•) denote the quantile function of the distribution χ 2 λ above, then P can be given as:P = γ : (γ -µy t ) CΣC -1 (γ -µy t ) ≤ χ -1 (τ ) ,which is equivalent to:P = γ : (γ -µy t ) χ -1 (τ )CΣC -1 (γ -µy t ) ≤ 1 ,By lemma C.1, it is equivalent to:P = γ : γ = µy t + χ -1 (τ )CΣC 1 2 u u 2 ≤ 1 ,where µy t = Axt + Bz ξ t , and u is an arbitrary point in the unit sphere in R |Y t | .C.2 Proof for Theorem 3.3Lemma C.2 (Theorem 3 of Cutler et al. [11] ). Consider a sequence of stochastic optimization problems min β ft(β) indexed by time t ∈ N. Let ĝt denote the estimation for the gradient of ft, and β t denote the minimizer of the L-smooth and µ-strongly convex function ft. Suppose it holds that maxt ĝt ≤ σ 2 < ∞ and maxt E β t+1 -β t ≤ ∆ < ∞. Then the produced {βt} T t=0 with iterates βt+1 = ΠB(βt -ηĝt) (B = R |β| ) and constant learning rate η ≤ 1/2L satisfies:E βt -β t 2 (1 -µη) t β0 -β 0 2 optimization + ησ 2 µ noise + ∆ µη 2 drift . Lemma C.3 (Convergence of LSE).Let βj,t denote the true parameter value of βj in time t, and βlse j,t denote the estimation according to Eq. (4). For ∀ψ > 0, ∃n > 0 that holds:E βlse j,t -βj,t 2 2 ≤ ψ Proof. Let Pj,t = PA 1 j,t . . . PA n j,t and vj,t = V 1 j,t , . . . , V n j,t. Then the optimization in Eq. ( 4) is equivalent to: arg minβ j,t vj,t -Pj,tβj,t 2 2 .Since PAj represents the true parents of the generation process for variable Vj, Pj,t is guaranteed to have full column rank. For ∀n ≥ |PAj|, the solution to the optimization above is:βlse j,t = P j,t Pj,t -1 P j,t vj,t.Because vj,t = Pj,tβj,t + εj where εj ∼ N 0, σ 2 j In according to Eq. ( 3), we have:βlse j,t = βj,t + P j,t Pj,t -1 P j,t εj.Due to the linear combination property of the Gaussian distribution, it holds that:βlse j,t -βj,t ∼ N 0, σ 2 j P j,t Pj,t -1Thus, it can be derived that:EQUATION= tr σ 2 j P j,t Pj,t-1 = σ 2 j | PA j | i=1λi λis are eigenvalues of P j,t Pj,tEQUATION• P j,t Pj,t 2 ≤ P j,t Pj,t -1 P j,t Pj,t 2 = 1, we have:EQUATIONLemma C.4 (Positive-definite Property). Consider a set of m-dimensional vectors {vi} n i=1 , n ≥ m. If it contains at least one set of basis vectors in space R m , then the following matrix is positive-definite:M = n i=1 viv i Proof. Let {u k } mk=1 ⊆ {vi} n i=1 denote a set of basis vectors, and let x ∈ R m denote an arbitrary mdimensional points in the same space as vis. Then it can be derived that:x Mx = n i=1 x vi 2 ≥ m k=1 x u k 2 > 0,because there at least exists one basis vector u h that holds x u h = 0. So M is positive-definite (thus M is full-rank).Theorem 3.3. Denote the true parameter of βj in time t as βj,t (j ∈ [|V|]) and choose ηj ∈ (0, 1/2Lj] as the step size used in Algorithm 1, it can be bounded in G that:E βj,t -βj,t 2 (1 -µjηj) t m βj,0 -βj,0 2 + δj with δj = m∆j µjηj 2 + ηjσ 2 µj ,where µj and Lj are the minimal and maximal eigenvalues of { j,t(•)} T t=1 's Hessian matrices respectively, σ 2 upper-bounds the variance of ĝj,t used in Algorithm 1, ∆j ≥ maxt βj,t+1 -βj,t upper-bounds the varying speed of the environment, and m is the longest continuously altered rounds of Vj, for most of the Vjs, m = 1.Proof. For Eq. ( 4), the Hessain matrix of j,t(•) can be derived that: Proof. Following previous studies [8] (Theorem 2.2 and Exercise 2.5), we define:Hj,t = ∇ 2 j,t = 1 n n k=1 PA k j,t PA k j,L η t = t i=1ˆ j,i β η j,i , and Wt =η∈H j w η 1 e -αL η t .From the updating rule in Algorithm 2, it is easy to verify that:EQUATIONFirst, it can be derived that:EQUATIONNext, the related quantity ln (Wt/Wt-1) can be bounded as follows when t ≥ 2:EQUATION= ln   η∈H j w η t e -α ˆ j,t( β η j,t )   .When t = 1, it holds that ln W1 = ln η∈H w η 1 e -α ˆ j,1( β η j,1 ) , thus it can be derived that:EQUATIONwhere the inequality in the second line is due to Lemma C.5, and the inequality in the second line is due to Jensen's inequality. By combining Eq. ( 8) and Eq. ( 9), it can be derived that:EQUATIONSince we choose w η 1 = 1 N j in Algorithm 2, thus for η ∈ Hj, by choosing α = ln Nj/T , it holds that: Theorem 3.5. By using the suggested alterations from Eq. ( 6), it can be guaranteed that:P Yt ∈ S | θt, xt, Rh(ξt) ≥ τ.Proof. Recall that Eq. ( 6) suggests alterations as follows:min z ξ t t z ξ t t -z 0 t W z ξ t t -z 0 t s.t. MAxt + MBz ξ t t + MP 2,row ≤ d,whereP = χ -1 (τ )CΣC 1 2, and • 2,row means an operator that takes 2-norm for each row of the matrix thus outputs a row-dimensional vector. We omit the subscript 2 of the norm in the following discussions. In this section, we provide details about the Bermuda data. The Bermuda data is an environment dataset that involves some environmental variables in Bermuda [10] . The variables included in the generation process are:• Light: Light levels at the bottom;• Temp: Temperature at the bottom;• Sal: Sea surface salinity;• DIC: Dissolved inorganic carbon of seawater;• TA: Total alkalinity of seawater;• ΩA: Saturation with respect to aragonite in seawater;• Chla: Chlorophyll-a at sea surface;• Nut: PC1 of NH4, NiO2 + NiO3, SiO4;• pHsw: pH of seawater;• CO2: PCO 2 of seawater;• NEC: Net ecosystem calcification.The rehearsal graph for the variables is illustrated in Fig. 8 . The presumed actionable variables that can be altered by the decision-maker are DIC, TA, ΩA, Chla, and Nut according to Aglietti et al. [1] , Qin et al. [40] .The hyperparameters associated with the cost function are set as Z 0 DIC = Z 0 TA = Z 0 Ω A = Z 0 Chla = Z 0 Nut = 0.0; and wDIC = 10.0, wTA = 8.0, wΩ A = 3.0, wChla = 5.0, wNut = 10.0. The desired region S is shown in Fig. 7(b) . We shade dynamic edges with red color. • All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.• 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. 


Decision: This paper studies an interesting setting that bridges predictions and causality. The authors pose a problem where the decision-maker can intervene to avoid undesired future outcomes, and wishes to due so with minimal cost. In contrast to prior work, the proposed algorithm can handle non-stationary environments—varying action costs and dynamic influence relations between variables over time. The main algorithm estimates the dynamic influence relations, based on which actions/decisions are taken. The reviewing team has provided helpful feedback, and I encourage the authors to revise the submission in order to maximize clarity. In particular, it is strongly recommended that they provide a candid discussion of the limitations of the proposed algorithm in the camera-ready version.

Reviews: review: paper_summary: paper_summary: The authors formulate the Avoiding Undesired Future (AUF) problem in real-world scenarios of decision-making, especially in non-stationary environments, and propose a method to avoid undesired outcomes with minimal costs. Here the non-stationarity majorly comes from the different costs corresponding to different actions, and the varying influence relations over time. They also provide theoretical guarantees of their method and empirical results demonstrate the effectiveness and efficiency of the proposal.
strength_weakness: strength_weakness: I think my major concerns have been settled by the Supplementary Materials. So I have no other comments about the weaknesses.
questions: questions: For the differences between SRM in the rehearsal graph and SCM in causality:
- In the linear cases, it is easy to define the coefficients as the influences. When in the nonlinear cases, how to define the influences in the rehearsal graph? Is it the same as in causation, e.g., definitions of causal influence or causal effects? 
- Can the influence in rehearsal graphs (SRM) represent the bi-directional edge information? If not, I am confused what are the differences between such bi-directional relations in rehearsal learning and causality. Though in [35], the bidirectional edges are often due to common causes between two variables, there also exist some works that use causality to represent mutually influenced relationships[1*]. A causal graph can also include cycles.
- The operators in Figure 2 seem identical to the Intervention operator in causality.

[1*] Vimaleswaran K S, Berry D J, Lu C, et al. Causal relationship between obesity and vitamin D status: bi-directional Mendelian randomization analysis of multiple cohorts[J]. PLoS medicine, 2013, 10(2): e1001383.

There are other minor typo errors:
- It seems that in Eq.(1) or Eq.(3), it is better to add $t$ as a subscript for $V_j$ and $\varepsilon_j$?
- In line 181, "ound" might be "round".
limitations: limitations: Not applicable.
paper_summary: paper_summary: In this paper, the authors address decision-making problem that sufficient interactions are not available. In this case, RL is not suitable. The authors model the structure among the observed variables, and use the structure to help the decisions. Compared to the previous studies [Qin et al. 37], the method can be used in a dynamic environment and can efficiently find the suggested decision (in polynomial time). To deal with the dynamic environment, they introduce the online learning method (Alg. 2). To efficiently find the suggested decision, they convert the optimization problem to a QCQP problem, which can be implemented in polynomial time. The experimental results verify the effectiveness.
strength_weakness: strength_weakness: Some discussion about the offline RL are missing. See Questions for the details.

Given the results of theorem 3.5: I do not know where $\tau$ is reflected in your algorithm. It seems that $\tau$ is never mentioned in Section 3.3. It is a bit wired, and needs more illustrations.

The writing could be improved. There are some weird sentences. I suggest the authors carefully revise the paper. For example, "We provide the theoretical guarantees of our method, and experimental results validate the effectiveness and efficiency of the method." -> "We provide the theoretical guarantees for our method. Experimental results validate the effectiveness and efficiency of the method."
questions: questions: I agree that RL is not suitable for the setting. However, I am wondering why offline RL cannot be used instead? Relevant discussions are missing.

I can understand that the problem is hard in the non-linear case. Could authors have some discussions for the case that the data is non-linear?
limitations: limitations: No limitations.
paper_summary: paper_summary: The paper studies the non-stationary setting in avoiding undesired future (AUF) problems, where environmental shifts can cause the failure of existing AUF methods. It introduces an optimization problem for AUF with minimal action cost in non-stationary environments, formulated as a convex quadratically constrained quadratic program (QCQP) in each interaction. The paper also proposes a rehearsal-based algorithm to solve this problem, providing theoretical guarantees and numerical validations.
strength_weakness: strength_weakness: (1) The provided algorithms lack a regret bound (or other theoretical guarantees) on the cost (i.e., the objective function), although it guarantees effective alterations (i.e., the constraint). Since the aim of this work is to avoid an undesired future with minimal cost, a regret bound analysis is, in my opinion, important.

(2) In Theorem 3.3, the estimation error depends on the minimum eigenvalues of  the empirical error functions' Hessian matrices, which in turn depends on the previously taken alterations. This raises a concern about the exploration-exploitation tradeoff when making alterations. An extreme case is making uninformative alterations (e.g., setting 0 for all nodes), leading to no update by Algorithm 1 and rendering the error bound in Theorem 3.3 meaningless (since $\mu_j$=0 in this case if I understand correctly). It is unclear how Algorithm 3 addresses this tradeoff and how $\mu_j$’s can be bounded  below.
questions: questions: (1) How do algorithms handle the exploration-exploitation tradeoff (if explorations are needed)?

(2) Is it possible to establish a regret bound for the cost? If not, what are the challenges?
limitations: limitations: See weaknesses.

Comments: comment: Dear Reviewer w1Mx,

Thanks for your positive feedback. We are glad that our responses addressed your concerns and contributed to your evaluation.

Best Regards,

Authors
These responses address my concerns and questions well, and thus further solidify my rating. Thanks.
Dear Reviewer weAS,

We are pleased to be able to address your concerns. Once again, thanks for the time and effort you dedicated to reviewing our work.

Best Regards,

Authors
Thank you for your response. It addresses my concerns and I have raised the score.