Avoiding Undesired Future with Minimal Cost in Non-Stationary Environments
Authors: Wen-Bo Du
Tian Qin
Tian-Zuo Wang
Zhi-Hua Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: decision-making
structural rehearsal model
non-stationary environment
alteration cost
Primary area: probabilistic_methods
TL;DR: We present the AUF-MICNS algorithm for suggesting appropriate decision actions to avoid undesired outcomes with minimal action cost in non-stationary environments

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.

Avoiding Undesired Future with Minimal Cost in Non-Stationary Environments
Wen-Bo Du, Tian Qin, Tian-Zuo Wang, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology. Nanjing University, China School of Artificial Intelligence, Nanjing University, China {duwb, qint, wangtz, zhouzh} (oldza)aaamda..... .nju. maju.edu.ccm edu. cn
Abstract
Machine learning (ML) has achieved remarkable success in prediction tasks. In many real-world scenarios, rather than solely predicting an outcome using an MI model, the crucial concern is how make decisions prevent the occurrence of undesired outcomes, known as the avoiding undesired future (AUF) problem. To this end, new framework called rehearsal learning has been proposed recently, which works effectively in stationary environments by leveraging the influence relations among variables. non non-stationary, where the influence relations may be dynamic, leading to the failure of AUF by the existing method. this paper, we introduce 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 sttatiootonrrt. We prove that in linear Gaussian cases, the problem can be transformed into the well-studied convex quadratically constrained quadratic pro- gram (QCQP). In this way, we establish the first polynomial-time rehearsal-bar based approach for addressing the AUF problem. Theoretical and experimental results validate the effectiveness and efficiency of our method under certain cireumstances.
real tasks, however, the environments are usually
Introduction
Machine learning (ML) models have found extensive application in prediction tasks (25). However, in contrast to sole emphasis 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 ML model on features X (e.g., economic indicators) predict the outcome (e.g., monthly sales). Suppose at the beginning of a month, is predicted to 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 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 meaiiinnnmmkingg. algorithms that depend numerous interactions, such as conventional reinforcement learning (RL) methods [4), are not well-suited for the AUF problem [40]. Additionally, fundamentally vital decisions need be made with human judgment, and therefore, it is desired to enable human decision-makeen 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 make decisions 36 40).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Causation is such type of structural relation [36,, which has been leveraged for some decision decision-making prob-
Correlation
Prediction
lems S 24
42 43
Although causal relations can assist
Influence
Decision
to some extent, identifying them challenging and gen- erally relies on some untestable assumptions [49 [4 28].
Actionable
Causation
Discovery
Besides, causation should not be viewed as a prereq- uisite 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- maaiinn whereas causation is too luxurious to be relied on,
Figure I: Relationship among correlation,
influence, causation [6]]
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. [
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 intractable with any polynomial-tine time algorithm when considering decisions multiple variables in the previous work [40], thus exploring more efficient approaches is necessary for the decision- suggestion 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 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-stations -tatiionon fact that influence relations may vary over decision rounds. and therefore, treating the round-wise collected data as i.idd samples for determining the influence relations is inappropriate. To this end, we present a sequential approach maintain dynamic influence relations in non-stationary environments, and further propose an online-ensemble-basee
[60) sequential algorithm to deal with the unknown degree of non-stationarity. In addition, we design cost function 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 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 campling-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 ((VV 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.
We try 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 еитог 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. Sec. 2. we review basic concepts and introduce our notation. In Sec. the formulation of AUF problem and provide the AUF-MICNS algorithm for solving the problem, together with theoretical guarantees. In Sec. we introduce some related studies. In See. we show the experimental results. At last, we discuss the limitations and conclude our work in Sec. 6
3 we provide

---

2 2 Zz
2 23
21 Zz
2 2
Yi
Z3
Z3
(a) rehearsal graph G
(b) G (2
(c) G 3
(d) G GRA77=m2 7amra)
Figure 2: Fig. 2(a) is a rehearsal graph, and Fig. 2(b)
Fig. 2(d) illustrate the corresponding alteration
graphs with different alterations. Note that when alteration occurs certain variables, all incoming arrows to those variables are removed while other graph structures are maintained.
Preliminaries
A novel probabilistic graphical model called structural rehearsal model (SRM) is proposed by Qin et al. 440 to characterize influence relations among variables in the AUF problem. The SRM consists of set of rehearsal graphs and corresponding structural equations {Gr, } (t denotes the decision round). The detailed definition of SRM is listed in Appendix [I.
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 + 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 Vjs can be parameterized by {B 13,3 IVI
3,13 j=1 C 0, that:
V=+== (PA9): :8,1) + Eg.t
where Vj= E denotes the j-th vertex in G., PA A {u u + Vg Gt} represents the parents of Vj in G,, and the noise εjtt follows the distribution o,,) 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 fixed volume of ideal gas 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 440
Besides, finding suitable alterations is involved in addressing the AUF problem. An alteration E means decision action that is specified by human decision-makers denoting by set of vertex-value pairs, e.g. { (Z- 22) in Fig. 2(b) Meanwhile, rehearsal operation, denoted as Rh(-). represents executing certain alteration, which changes the original graph structure illustrated in Fig. ((b) Fig. 2 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.
3
The proposed approach
This section dedicated addressing the aforementioned AUF problem. In Sec. 3.1 provide the probelm formulation. In Sec. Sec.3.2) we propose the AUF-MICNS method for AUF. Later in Sec. 3.3 theoretical results are provided ensure the effectiveness of our approach.
3.1 Formulation
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 MI model is always available and are not concerned about how to train it.
We formulate the AUF problem with minimal cost non-stationary environments as multi-round online decision decision-making process, where the fecision-maker should perform round-win wise alterations to
3

---

avoid undesired outcomes. In each decision round, there are two essential time points, the time that the ML prediction 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 f-th round, decision-makes maker first observes variables X; = x,, and an ML model provides a prediction Y, as the outcome subsequently. Denote the desired region of Y, as S. Y, & S, the decision makerr would perform alterations on Z, (only once) based on the whole historical data, and the true Y, will occur after the alteration.
is worth mentioning that in decision round i, two crucial concerns for making decisions are (a) how to perform effective alterations that make Y, E 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 PY, E S 0,, Xt, Rh(E:) 2 T; where & is the selected alteration, and is the expected probability that the alteration can successfully avoid the undesired outcome. For the latter, we generalize a con- tinuous cost function from the discrete cost measure [6]] 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:
2
min &
Σ Wi (Z) Z,E5
z
(2)
s.t. P(Y,ES) x4, Rh((E)) 2T,
where w; >> 0 represents the cost coefficient for each intermediate variable Z, E Z, 2 represents the values of Zi after alteration & while Z is the datum point that associates with the minimum alteration cost relatively. Besides, 0; arg ming | 0.l is the ideal estimation of i, since O, is not available in practice. Note that wys and 2 are user-specified because the cost of the same decision alteration can vary for different pecisinnmmkkers.
In the following, we focus on basic but essential class of the AUF problem, where the structural equations fe 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., G2 - G) for convenient illustration. Let d E R', M e Rax M1, 33 E R | dynamic structural equations and the desired region can be formulated as:
Vj,+ := 54. PA teJ. S {y E RI My S d)
(3)
Note that ,7 in Eq. ( is usually not available as discussed later in Sec. 3.2.1 thus finding surrogate estimations O, with bounded error E, 01 0: is necessary. Noticing that the noise distributions for Ej.08 in Eq. 3 do not change over time, the variances of E,,88 can be estimated by various Bayesian learning methods (6) Thus, we mainly focus on estimating influence parameters 3y.u8 in what follows, and we use 0, to represent {, }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. 333
3.2 Our proposed AUF-MICNS algorithm
In this subsection, we propose the AUF-MICNS algorithm to address the AUF problem as formulated in Fq. (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.
3.2.1 Dynamic influence maintenance
As illustrated in Eq. 2 the precondition for making effeective decisions in the AUF problem lies in the accurately estimated 0,s. Specifically, to accurately estimate the parameter vector B3,1 E 0,
in t-th decision round, would like to minimize the expected squared loss Es, [V-- - -3 PA,]

---

where V is the j-th vertex in rehearsal graph, and PA, denotes the parents of Vj. Ideally, according to the law of large numbers (LLN), we could obtain sufficient i.id. samples in time t, we can estimate By. by minimizing the empirical error (31,) as substitute:
arg min Rg.
1 2n
Σ
V -A.
(4)
k=1
where n is the number of samples that we can obtain in round f, and the superscript 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 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:
1 (Vae-B5, Bjee" PAA.)) L,e (8,,) = 2
(5)
Besides, mixing the round-wise selected (V PAJ,J estimate parameter 3J 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 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 larger step size for rapid changes and smaller one for gradual changes, parameters can be effectively updated with limited data after each round. We customize OGD for estimating quantitative influence relations 3,, E O2 sequentially Algorithm
By using the OGD-based approach in Algorithm [] we can obtain se- quence of estimates (.,,......, }
Algorithm OGD-based estimator for B,
Input: The step size 1)
j E [[V Roughly speaking, the quality of the estimates heavily de- pends on the choice of step size n). If we have full prior knowledge of the non-stationarity degree, such as the changing speed of the influence rela- tions, we can pre-determine an opti- mal step size 17" to achieve favorable estimates. However, in practical sce- narios, '7" is not available, and the random choice of the step size leads to unstable estimators. Since bad estimators of the influence relations will affect the accuracy of the estimated distribution P(Y, S 0,, (E.))), which will further affect the effectiveness of the suggested decisions for the AUF problem, thus the choice of the step size needs to be carefully considered.
I: Initialize 50 with any point in domain B
2: for t = to T do
3: Receive (PA VJ.1); Continue if V2, E &
4: Estimate gradient _3.1 [PA By. Vss1) PAga
5: Update 37
1T /3 199.1
Output: estimated (8%,)===
To avoid this risk, we turn to use online-ensemble [60] based methods. Online ensemble is a type of algo- rithm that combines the idea of en- semble and sequential updating, main- taining multiple base learners and en- sembling them together. Specifically, as illustrated in Algorithm 2 we main- tain N, 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 re- lated to different experts. By ensem- bling all experts with the weight w, we can obtain the final estimator.
Algorithm Online-ensemble-based estimator for B Input: base estimators' number N,. weight parameter
I: Set a set of learning rates Hi {n/ i i......,N N;)
2: Initialize weight vector w/ N, for each 17 H.
Activate estimators ESs for all r7 E Hi by OGD with n
4: for t = 1 to T do
5: Receive B% from each E"
6: Output 23.0 ΣnER, w 1/,
Update weights as wi'l EnEN, w² (app-aa,, 9: Receive (PA,e, Viy) and send to each E
7:
8:
w2t1 =
Output: estimated (8
5

---

3.2.2 Efficient alteration suggestion
In 1-th decision round, since we can obtain the estimation Ô, for true O, by Algorithm 2 then we substitute d with 0. 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 Lemma 3.T as follows, which needed our method to find the alteration that can make Y, E with an expected probability
Lemma 3.1 (Qin et al. 2023). Given X O,, it holds that:
Y, = Ax; Bzł + CEa,
where A, B, C are constant matrices of appropriate shapes based on O,, Et = (EI,,...,, N (0,E), and zi are intermediate variables with alteration &.
Recall from Eq. 2 that we want to find alterations that satisfy P(Y, E P 0., X4, Rh(Ei)) 2 т. Recognizing that solving optimization with probabilistic constraint generally intractable and the previous sampling method is cone-conuuning, we attempt to construct a surrogate deterministic constraint that be handled efficiently to replace the probabilistic constraint. Fortunately, this idea feasible because Lemma 3.1 shows that once the alteration is selected, the randomness of Y, only arises from Et, since x has been observed and A, B, C constant matrices given Or. Thus, the probability density function (PDF) of Y, is available and we can directly analyze the PDF to find probability regions as in Prop. 3.2 which aids constructing the surrogate deterministic constraint.
Proposition 3.2. The following probability region P satisfies P(Y, P Oz, Xx, Rt(E.))
p = {1y, + (x
|
||ul|2 s $1}.
where My, = Ax; + Bzi, u is an arbitrary point in the unit sphere in R|Ya,,, and x (-) denotes the quantile function of the x² distribution with degrees of freedom X = YY)
The proof of Prop. 3.2 provided in Appendix C.4
We raise the power of 1/2 to the matrix
because it is always positive semi- definite since x matrix). In practical scenarios where Σ is not available, the estimation E can be used replacements. Let Fy, denote the mulative distribution function (CDF) of Y,, Fig. Billustrates a 2-dimensional example of samples from Fy.. together with the estima- tion of the associated region P. It illustrates that P can properly draw the probabilistic region of Fy. with expected probability т.
0 and CEC
2 0 (E is the covariance
(a) Samples from Fy, (h) Probability region P
Figure An example of estimated P with 0.9
Moreover, recognizing that the desired region S defined in Eq. (3) is convex polytope, i.e.
{y E R x My < d). we utilize the defined probability region P in Prop. 3.2 and use deterministic constraint to replace the original probabilistic constraint in Eq. (2). this case, the alteration Ieraation-suggsttioo method can be formulated as follows:
min St
22 2
W
(6)
S.L. MAX, + MBZ, + MPP 2,ro S d.
where P P (C 11- means an operator that takes 2-norm for each row of the matrix thus outputs oow-dinensional vector. The objective to be minimized is the vector representation the cost function as explained in Eq. (2) where W diag(w) [tag(W)..... w 3 is
positive definite since the cost is non-negative, iee., w; > 0 for Vi.
Note that Win is positive definite and the constraint is linearly associated with 2 thus Eq. 66 is convex QCQP, which can be cast as second-order cone program [5] 30). Specifically, it can be solved in polynomial time O | L) by interior-poin method 22. where L is the iteration rounds

---

for solving the QCQP and is not associated with % Meanwhile, constructing matrices A, B, C needs an element-wise traverse thus O( ()) time and constructing the probability region P in Prop. 3.2 runs under ([VV because of the matrix multiplication, so the whole running time of alteration suggestion is ((V 3) | ((V)), |Y = =+(VV) and L is constant.
3.2.3 AUF-MICNS
By combining the influence mainte- nance step and the alteration sugges- tion step, our proposed approach for addressing the AUF problem with minimal cost in non-stationary en- vironments is formulated in Algo- rithm 3 which attempts to avoid unde- sired outcomes in each decision round. Specifically, in 1-th round, the algo- rithm first receive X = Xt, then the predicted outcome Y, & S, the algorithm performs the suggested alteration &r on Z, by solving Eq. O Subsequently, true Y, Y occurs, and the algorithm collects (x,, zl' yr} to update influence relations by Algorithm 2 By using this algorithm, one can tackle the formulated AUF problem with the suggested alterations.
Algorithm AUF-MICNS
Input: sequential coming data {x,, Zz. yo
Initialize { ) j=1 for Algorithm for to T' do
3: Select alteration & by solving Eq. 6
4: Receive y: and sent {x,, 25 yt ) to A Agorithm 2
5: Update { by Algorithm
Output: suggested alterations (6))_=)
3.3 Theoretical results
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 D to estimate B3, E 0,, the error gap between the estimate and the true parameter value (E,, 1| Bg.el??) ) is proved to be bounded by an exponentially decreasing term, as well as fixed value related to the choice of step size and the inherent problem difficulty. reveals that the performance of Algorithm [ depends on the choice of step size 7) heavily, and is detailed in Thm. 3.3 where ((),(-))) are defined in Eq. 44).
Theorem 3.3. Let B3, (j E [[V denote the true parameter value of B3 in time t, and choose My E 1/2,) as the step size used in Algorithm
then it can be bounded that:
E |3, 33.4 |= 51 p-))) th 13,0 B,ol + 8, with 8, =
-(m)) (mAj)
2
njo²
+
[4j
where μj and Lj are the minimal and maximal eigenvalues of (laa(-)TT= 's Hessian matrices, 0² popeerbbuudss the variance of 95.t. Aj 2 max, 118 -Byell upper-bounds the varying speed of the environment, and is the longest continuously altered rounds of Vj. for most of the Vjs, m 1.
In Thm. 3.3 it holds that pym E (0, 1/2], which derives that (1 - m3n))) E [1/2,
1). This shows that time progresses, the OGD estimator $3.. will gradually converge towards the true value 3j., in the expected sense. Specifically, (a) the convergence speed depends on the choice of the initial point 8 and is limited by the inherent difficulty of the problem implied in μı L,; and (b) the convergence result will suffer a ô, gap from the true value, depending on the varying speed of the environment (A,) and the choice of step size 775- If ny is appropriately chosen, the gap 6, will be small, e.g., if all hyperparameters are available and A * O, choosing 7/ min 2/2( mA.
can achieve the smallest dz. Meanwhile, the hyperparameter appears in the bound according to the properties of alterations shown in Fig. 2 V, is continuously altered in m rounds, incoming arrows of V, 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, might be altered in any rounds, m = 1 holds for most of the V,s.
vajo
In practice we do not know exact parameters such as Aj. thus n" is not pre-available. Recognizing that the random choice of 7) leads to unstable estimations, we turn use Algorithm to estimate
2
9r.s. Though we do not know 1y" as well, by using the online-ensemble-basee Algorithm get more stable estimations guaranteed by the following regret bound in Prop. 3.4
2
we can
7

---

Proposition 3.4. Assume (l is are bounded v3, E B and E [T]; then for any E Hg.
estimations B3.s from Algorithm satisfies that
E4
le (PP,)) E. -B
SO (O(TinN))
by choosing a //INN//T in Algorithm where N, is the number of base-learners, Sh is the estimation from any expert in expert set H. in Algorithm 2
Prop. 3.4 shows that the cumulative loss of the estimation obtained by Algorithm i comparable with the best expert Hj. thus by Thm. 3.3 though O, may be far from O, at the first few rounds, will converge towards θz. Meanwhile, in some certain cases, the best step size 77 in Thm. 3.3 can be included in Hj with N, = (log T) [60]. Due to these, Algorithm provides more stable estimates for the influence relations, which can further aid in making decisions to address the formulated AUF problem. As to the pecision-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 & from Eq. (6) can be guaranteed that:
P (Y.E EXESSI 0,,,,x,, 2
Thm. 3.5 illustrates that the suggested alterations & by the AUF-MICNS algorithm can effectively avoid the undesired outcomes as the formulated AUF problem expects, under the distribution con- ditioned on estimation 0g rather than true O,. Note that it is guaranteed in Thm. 3.3 and Prop. 3.4
that O. is not far from O,. Meanwhile, we provide the experimental analysis in Sec. 5 to show that P PY, E S 0r, Xt, Rh(G)) 2 holds practically. Besides, this method achieves super-exponential improvement over the time complexity of the previous method [4) discussed in Sec. 3.2.2
4 Related work
RL Methods. RL approaches have demonstrated success in numerous domains (51), particularly in game- same-playing [33] and autonomous control (2]]. However, the Markov Decision Process (MDP) formalism in RL abstracts decision 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 [8 37 they overlook fine-grained structural information as well and require large offline datasets practice. Moreover, it is worth noting that 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 exten- sively studied 44 50 7
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
58
54| 57 which predominantly aim 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
55
39
59 12 The afore- mentioned methods generally rely on causal modeling, which may be luxurious or restrictive in some As identifying causations rely on some strong restrictions
real-world eeciiioonmakingg cases 63 or assumptions, it is possible that we cannot find feasible alteration. Conversely, correlation, which underpins most ML models, falls short of providing solid foundation for making decisions. As a middle ground between causation and correlation, the influence relations form more practical basis for decision maainn (63]. Building on this concept, we employ the SRM developed by Qin et al. [40], which can adapt dynamically evolving decision systems. In particular, our approach incorporates the context x, into decision-menn makingg 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] 63].1]]. Ad-
ditionally, 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 these techniques hold the potential to enhance our approach as well.
8

---

Success and relative atteratio
MSE cifleren estimalions
influence estimation
0.31
AUF MICNS
Orinn Ersenbrc
13
Viluo Ale.
22.
DOPG
PPO
DA7223
8 0.0
1.2
QSD with 2.025
030 w/t shap size 1005
w3D stap 0.
17
Exiraor Ris.
5.4
SAC
14
Desired:
504
Sa7
1.4
Succese Frequeeey
RDPG
AJF MICNS
C/NZ23
00
0.
Orline Eneembin
OGD winh shop size 5000
DGD with shep eoe 1000
CGD with size 1500
Value of 000 and
Enammttio As..
04-
Destred
0.8
02
100
160
Relative Ateration Cost
Round
Round
Figure 4: Results of Market-managing data (row 1) and Bermuda data (row 2) respectively. Bars and bands depict the standard deviations.
5 Experiments
We evaluate the proposed AUF-MICNS algorithm two datasets and focus on four aspects including (a) success frequency for Y, E S; (b) average alteration cost; (c) average executing time; and (d) mean square error of the estimated parameters 0,. 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 [5]. Experimental details and additional experiments are listed in Appendix D
Market-Managing Data. We abstract dynamic SRM from a market-managing scenario, where 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 is set to be small, then E will also be small to stay competitive on price; and vice versa. The sizes of X,, Zz and Y, are 2, 4, and respectively. The parameters of the dynamic structural equations are manually set according to the domain knowledge. For example, parameters associated with variable vary over time with a periodic term, i.e., 9c,, = (1 + a sin( The feasible alteration values are [-3, 3) for centralized P and C, associated with cost coefficients 1.0 and 2.0 respectively since altering 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 2 $1. NCT 52. TPF NCT 2 $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 available 3. The sizes of Z, and Y, 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,, emissions, we posit that there is an increasing trend in the influence relation between temperature and CO2 concentration, i.e. Scog.1 = Bcog.t (1 - a -wt). We assume that 5 variables in Z, are actionable I and the feasible alteration values are [- for each of them with different cost coefficients. The concerned outcome Y, represents the net coral ecosystem calcification (NEC) in Bermuda. To make the coral reef ecosystem healthy, 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
Fig. shows the full experimental results. The desired probability is set to 7 0.7. Two rows of figures denote the results of the Market data and the Bermuda data respectively. Specifically, the first column of Fig. shows that (a) the success frequency of making the concerned outcome Y, 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 mean-square error of estimates for Pser in Market data and estimates for Sco, in Bermuda data respectively. The exponential convergence speed and the convergence error (6,) in Thm. 3.3 are illustrated in these two figures. Specifically, for Market- managing data, the online-ensemble-bee based sequential method can achieve similar convergence speed like OGD with 7) = 0.025 does when 7 < 20, and it results in smaller 6, as illustrated by the enlarged part (T' 2 40). For Bermuda data, OGD with 7 = 2.5 outperforms other step sizes, since 5.0 suffers notably bigger gap o5. By using the online-ensemble- based sequential method, we can obtain a comparable performance with the best step size vj = 2.5. These results illustrate that proposed method mitigates the risk substantially, choice of will affect the practicality of the estimation and 17" is not available practically. Meanwhile, the third column of Fig. shows true parameter values and the estimates by the caline-ensemble based method. The superscript (1)((2 means the first/second dimension the associated parameter vector. It shows that the error gap between 35. and 3コ converges to small value rapidly, which guarantees accurate estimates of the quantitative influence relations in possibly non- non-stationary environments.
? 1.0 converge slowly, and
the inappropriate
At last, the average whole-executing time of the 20-times experiments recorded in Table [ We mainly focus on the compar- ison between AUF-MICNS and QWZ23 since both of them maintain influence re- lations other than purely suggesting deci- sions. It shows that our proposed method is more time-efficient than QWZ23.
Table
Average running time (s).
Dataset
DDPG
PPO
SAC
QW723
MICNS
Market Bermuda
7.89
0.05
0.03
63.14
2.81
9.63
0.06
0.04
386.44
1.71
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 r 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 7 in future work.
Acknowledgements
This research was supported by Jiangsu Science Foundation Leading-edge Technology Program (BK20232003), and National Postdoctoral Program for Innovative Talent (BX20240162). The authors thank the anonymous reviewers for their helpful comments. We are also grateful to Long-Fei Li and Lue Tao for discussions.
References
[1] Virginia Aglietti, Xiaoyu Andrei Paleyes, and Javier González. Causal Bayesian optimization. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 3155 1164, 2020.
[2] Erling D. Andersen, Cornelis Roos, and Tam as Terlaky. On implementing a primal- -umall-uul interior-point method for conic quadratic optimization. Math. Program. 95(2):249 277, 2003.
[3] Andreas Andersson and Nicholas Bates. In situ measurements used for coral and scale calcification structural equation modeling including environmental and chemical measurements, and coral calcification rates in bermuda from 2010 to 2012 (BEACON project), 2018. beo htwp://wwwnnnoooogdd/dttss/////a
10

---

[4] Kai Arulkumaran, Marc Peter Deisenroth, Miles Brundage, and Anil Authony Bharath. Deep reinforcement learning: A brief survey. IEEE Signal Processing Maguzine, 34(6):26-38, 2017.
[5] Elias Bareinboim, Andrew Forney, and Judea Pearl. Bandits with unobserved confounders: A causal approach. In Advances Neural Information Processing Systems 28, pages 1342-1350, 2015.
[6] C Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
[7] Simon Buchholz. Goutham Rajendran, Elan Rosenfeld, Bryon Aragam, Bernhard Schölkopf, and Pradeep Ravikumar. Learning linear causal representations from interventions under general nonlinear mixing. In Advances in Neural Information Processing Systems 36, page appear, 2023.
[8] Nicolo Cesa- Bita-Biacchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[9] Wei Chen, Zhiyi Huang, Ruichu Cai, Zhifeng Hao, and Kun Zhang, Identification of causal structure with latent variables based on higher order cumulants. In The 38th AAAI Conference on Artificial Intelligence. pages 20353-20361, 2024.
[10] Travis A Courtney, Mario Lebrato, Nicholas R Bates, Andrew Collins, Samantha Putron, Rehecca Garley, Rod Johnson, Juan- Carlos Molinero, Timothy Noyes, Christopher L Sabine, et al. Environmental controls on modern scleractinian coral and seef-scale calcification. Science Advances, 1711366 2017.
[11] Joshua Cutler, Dmitriy Drusvyatskiy, and Zaïd Harchaoui. Stochastic optimization under distributional drift. Journal Machine Learning Research, 24(147):1-56, 2023.
[12] Arnoud A. W. M. de Kroon, Danielle Belgrave, and Joris M. Mooij. Causal discovery for causal bandits utilizing separating sets. CoRR, abs/2009.07916 2020.
[13] Charles Elkan. The foundations of cost-sensitive learning. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, pages 973-978, 2001.
[14] Yoav Freund and Robert E. Schapire. A Decision-thcoreti generalization of on-line learning and an application boosting. Journal of Computer and System Sciences, 55(1):119-139, 1997.
[15] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off off-poolcy maximum entropy deep reinforcement learning with a stochastic actor. Proceedings of the 35th International Conference on Machine Learning, pages 1861-1870, 2018.
[16] Trevor Hastie, Robert Tibshirani, Jerome Friedman, and Jerome Friedman. The elements of statistical learning: Data mining, inference, and prediction. Springer, 2009.
[17] Elad Hazan, Introduction to online convex optimization. Foundations and Trends Optimization, 2(3-4): 157-325, 2016.
[18] Yangbo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, NNov):2523-2547, 2008.
[19] Wassily Hoeffding. Probability incqualities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30) 1963.
[20] Thomas Hofmann, Bernhard Schölkopf. and Alexander J Smola. Kernel methods in machine learning. Annals of Statistics, 36(3): (06(3)::111--0 171-1220, 2008.
[21] Bahare Kiumarsi, Kyriakos G. Vamvoudakis, Hamidreza Modares, and Frank L. Lewis. Optimal and autonomous control using reinforeement learning: A survey, IEEE Transactions on Neural Networks and Learning Systems, 29(6)2202 2062, 2018.
[22] Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. Cost-optimal learning of causal graphs. In Proceedings of the 34th International Conference Machine Learning, pages 1875-1884, 2017.
[23] Kira Lancker and Martin F. Quaas. Increasing marginal costs and the efficiency of differentiated feed-in tariffs. Energy Economics, 83: 10:-114 2019.
[24] Finnian Lattimore, Tor Lattimore, and Mark D. Reid. Causal bandits: Learning good interventions via causal inference. In Advances Neural Information Processing Systems 29, pages 1181-1189, 2016.
[25] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553) 444, 2015.

---

[26] Sanghack Lee and Elias Bareiaboim. Characterizing optimal mixed policies: Where to intervene and what to observe. In Advances in Neural Information Processing Systems 33. pages 8565-8576, 2020.
[27] Long-Fei Li, Peng Zhao, and Zhi-Hua Zhou. Dynamic regret of adversarial linear mixture MDPs, In Advances in Neural Information Processing Systems 36, pages 60685-60711, 2023.
[28] Zihao Li, Hui Lan, Vasilis Syrgkanis, Mengdi Wang, and Masatoshi Uchara. Regularized deepiv with model selection, 2024. URL htttpa////axx orgg abs /ww.. 04236
[29] Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez. Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Proceedings of the 4th International Conference on Learning Representations, 2016.
[30] Miguel Sousa Lobo, Lieven Vandenberghe, Stephen Boyd, and Hervé Lebret. Applications of second- cone programming, Linear Algebra and its Applications, 284(1-3):195 228, 1998.
[3]] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Causal bandits with unknown graph structure. In Advances in Neural Information Processing Systems 34, pages 248 24817-24828, 2021.
[32] N Gregory Mankiw. Principles of Economics. Cengage Learning, 9th edition, 2020.
[33] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Joannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. CoRR, abs/1312.5602, 2013.
[34] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2nd edition, 2018.
[35] Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms convex programming. SIAM, 1994.
[36] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, 2nd edition. 2009.
[37] Vitchyr H Pong, Ashvin V Nair, Laura M Smith, Catherine Huang, and Sergey Levine. Offline meta- reinforcement learning with online self-supervision. In Proceedings of the 39th International Conference on Machine Learning, pages 17811-17829, 2022.
[38] Yu- Yany Qian, Yong Bai, Zhen-V Yu Zhang, Peng Zhao, and Zhi-Hua Zhou. Handling new class in online label shift. In Proceedings of the 23rd IEEE International Conference on Data Mining, pages 1283-1288 1288, 2023.
[39] Tian Qin, Tian-7uo Wang, and 7hi-Hua Zhou. Budgeted heterogeneous treatment effect estimation. In Proceedings of the 38th International Conference Machine Learning, pages 8693-8702, 2021.
[40] Tian Qin, Tian-Zuo Wang, and Zhi-Hua Zhou. Rehearsal learning for avoiding undesired future. In Advances in Neural Information Processing Systems 36, pages 80517-80542, 2023.
[41] Tian Qin, Long-Fei evolving environments. Machine Learning. 113 (336))365333377 2024.
Fei Li, Tian-Zuo Wang. and Zhi- Hua Zhou. Tracking treatment effect heterogeneity in
[42] Kangrui Ruan and Xuan Di. Learning human driving behaviors with sequential causal imitation learning. In Proceedings of the 36th AAAI Conference Artificial Intelligence, pages 4583 4592, 2022.
[43] Kangrui Ruan, Junzhe Zhang, Xuan Di, and Elias Bareinboim. Causal imitation learning via inverse reinforcement learning. In Proceedings of the 11th International Conference Learning Representations, 2022.
[44] Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEFE, 109(5): 612-634, 2021.
[45] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. CoRR, abs// 0034776777 2017.
[46] Rajat Sen, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Identifying best interventions through online importance sampling. In Proceedings of the 34th International Conference on Machine Learning, pages 3057-3066, 2017.
[47] Shai Shalev-Shwarte Yoram Singer, and Nathan Srebro. Pegasos: Primal estimated sub- gradient solver for SVM. In Proceedings of the 24th International Conference Machine Learning, pages 807-814, 2007.
12

---

[48] Yuda Song. Yifei Zhou, Ayush Sekhari. Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make efficient. In Proceedings the 11th International Conference on Learning Representations. 2022.
[49] Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, Prediction, and Search. MIT Press. 2000.
[50] Chandler Squires, Anna Seigal, Salil Bhate, and Caroline Uhler. Linear causal disentanglement via interventions. In Proceedings of the 40th International Conference on Machine Learning, pages 32540- 32560, 2023.
[51] Richard Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT Press, 2018.
[52] V. G. Vovk. Aggregating strategies. In Proceedings of the 3rd Annual Workshop on Computational Learning Theory, pages 371-386, 1990.
[53] Tian-Zuo Wang, Xi-Zhu Wu, Sheng-Jun Huang, and Zhi-Hua Zhou. Cost-effectively identifying causal effects when only response variable is observable. Proceedings of the 37th International Conference on Machine Learning, pages 10060-10069, 2020.
[54] Tian-Zuo Wang, Tian Qin, and Zhi- Zhou. Estimating possible causal effects with latent variables via adjustment. In Proceedings of the 40th International Conference on Machine Learning, pages 36308-36335, 2023.
[55] Tian-Zuo Wang, Tian Qin, and Zhi-Hua Zhou. Sound and complete causal identification with latent variables given local background knowledge. Artificial Intelligence, 322:10396: 2023.
[56] Yu-Hu Yan, Peng Zhao, and Hui-Hua Zhou. Universal online learning with gradual variations: A multi-layer online ensemble approach. In Advances in Neural Information Processing Systems 36, pages 37682-37715, 2023.
[57] Jiaqi Zhang, Louis Cammarata, Chandler Squires. Themistoklis P Sapsis, and Caroline Uhler. Active learning for optimal intervention design in causal models. Nature Machine Intelligence, pages 1-10, 2023.
[58] Jiaqi Zhang, Kristjan Greenewald, Chandler Squires, Akash Srivastava, Karthikeyan Shanmugam, and Caroline Uhler. Identifiability guarantees for causal disentanglement from soft interventions. In Advances in Neural Information Processing Systems 36, page to appear, 2023.
[59] Junzhe Zhang and Elias Bareinboim. Near-optimal reinforcement learning in dynamic treatment regimes. In Advances in Neural Information Processing Systems 32, pages 13401-13411, 2019.
[60] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and son-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98): 1-52, 2024.
[61] Zhi-Hua Zhou, Cost-sensitive learning. International Conference on Modeling Decisions for Artificial Intelligence, pages 18, 2011.
[62] Zhi-Hua Zhou. Open-enviroummnt machine learning. National Science Review, 9())nwac122 2022.
[63] Zhi-Hua Zhou. Rehearsal: Learning from prediction decision. Frontiers of Computer Science, 16(4):
1-3, 2022.
[64] Zhi-Hua Zhou. Rehearsal: Learning from prediction to decision. Keynote at the CCF Conference Al. Urumqi, China, 2023.
[65] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceed- ings of the 20th International Conference on Machine Learning, pages 928-936, 2003.
13

---

A Discussion
A.1 Discussion on the AUF-MICNS algorithm
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 lincar ones, one can modify the structural equations in Eq. (3) by using methods such as the kemee method (20) Note that Theorem 3.3 always holds long the new loss functions (-)s still ju-strongly convex and L-smooth in those cases, similar to Eq. { For the latter, we use a quadratic cost function in this paper. Since the alteration cost is user-specifidd, 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 convex optimization as well, similar to Eq. c It is worth noting that our work mainly focuses cases where samples are rare, thus only user-specified hyperparameters {wy, 2j bell[yi can be relied upon. If we can obtain a sufficient number of (alteration, cost) be accurately estimated using quadratic fitting techniques [16].
pairs, hyperparameters {we, 2, [Ev(vv))
Additionally. for the probabilistic constraint in Eq. (2) if the noise is not assumed be normal anymore, one can analyze the CDF of the noise distribution to find new probability region with similar approach. This can further assist in constructing substitute constraint. Moreover, there are instances where the feasible domain of the constraint in Eq. ( 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-make should consider verifying specified region S reducing hyperparameter 7
extent.
Last but not least, though we mainly focus the scenario where the graph structure is fixed and known, i.e. G. = G. however, our approach can be straightforwardly adapted to the case where G. G but unknown as assumed 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. 44), as illustrated in Appendix D.
A.2 Comparation with causality
The SRM and (-)-) 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:
Most of the causal learning problems focus on structure or effect identification, while the decision- making process is not directly involved 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, 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 eyclically and trend-wise over time. Thus, a given price may result fewer sales during summer compared to winter. In addition, the coat's style may gradually become outdated, Icading 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 volume V, amount of substance n, and absolute temperature T obey the equation pV = nRT (R is the ideal gas constant). When fixed volume V of an ideal gas is considered, with and R held constant, the pressure p and volume V can be represented as pair of mutually influenced variables within an SRM modeling.
A.3 Possible types of graph structures
There are four possible cases of the graph structure, specifically:
G, fixed, known. It's the setting in our paper.
G, 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) (CC) 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 from P(Y S G....). thereby the expectation of matrices A, B, C in Eq. 6 be obtained and used.
3 G2 not fixed, known. Our method can be directly used because once the graph structure is known, G is not stochastic component. Thus, matrices A, B, C in Eq. 6 can be obtained in the same manner. It
14

---

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 difficult.
4 G2 not fixed, unknown. In this case, neither nor Pe can be accurately estimated there is only one sample per round. Thus, dealing with such case may need to additional assumptions. For example, consider there sufficient numher of samples per round. In this case, method can model 0 and Pg accurately, thereby suggesting good decisions.
B
Definitions
B.1
Details about Structural Rehearsal Models
In this section, we present full definitions and discussions for the Structural Rehearsal Model (SRM), which a probabilistic graphical model proposed by (40] to characterize the influence relations among variables.
Definition of the Rehearsal Graph
Definition B.1 (Mixed graph, 44).. Let (V, E) be graph, where V denotes the vertices and the edges. G is a mixed graph if for any distinct vertices u, E V, there is at most one edge connecting them, and the edge is either directional ( u + or u < v or bi-directional (u ++ v).
Definition B.2 (Bi-directional clique, [40]., ). bi-directional clique = (V', EE) mixed graph
(V, E) is complete subgraph induced by V C V such that any edge e E E bi-directional. C maximal if adding any other vertex does not induce bi-directional clique.
Definition B.3 (Rehearsal graph, [40 ). Let G = (V, E) be mixed graph. Let (C:) denote all maximal bi-directional cliques of G, where C. (Vi. E,). G' is rehearsal graph if and only if:
1. Vi Vj 0 for any +
[1) there is any edge pointing from some u E V some e V then Ver E V u
3. There exists topological ordering for (C:) following the directions of directional edges between C.s.
It can be found that the topological ordering for bi-directional cliques (C.) in the rehearsal graph reflects the time order the generation process of variables.
Discussion of the Structural Equations
In this paper, we present the definition of dynamic structural equations in Eq. (1). which provides quantitative computational formulation for the influence relations non-stationary environments.
In fact, the structural equations are defined among the bi-directional cliques (Ci) as detailed in Qin et al. 40]. Specifically, the dynamic structural equations can he denoted as i,, which consists of the set of parameter matrices [fB.,);,_ ? and the covariance matrix E; of each clique C. in the rehearsal graph G. It noteworthy that the quantitative influence relationship of a directional edge A - B for A E C., B E C, at time f is modeled in the parameter matrix BB,, since the topological ordering for bi-directional cliques reflects the time order the generation process; while quantitative influence relationship of bi-directional edge D1 t> Da for D1, D2 E C. at time is modeled in covariance matrix Eg 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. IT for a convenient presentation, which defines the dynamic structural equations the variable level rather than the clique level. Note that for each variable V, E C: the associated parameter vectors (.3., can be directly found in the corresponding parameter matrices (B,,))?", while the variance a3 of each variable V, E C, can be derived from the corresponding covariance matrix Σ; by marginalizing the desired dimension out, since the marginalization operator for multi-normal distribution is availahle.
B.2 Increasing Marginal Cost with an Example
In this section, we introduce the increasing marginal cost (LMC) property. Increasing marginal cost (IMC), or rising marginal cost. is an important property in microeconomics (3 32). We first present famous example in the field of microcconomics. called Thirsty Thelma's Lemonade Stand.
15

---

Lemonade Stand is business simulation game devised in 1973 by Bob Jamison under the Minnesota Educational Computing Consortium. It offers players the experience of managing 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, summary of the current status of the player is provided, and the game concludes after 12 rounds. In this game, essential quantity is the total cost of lemonade per glass, which will increase in quadratic way, has linearly increasing derivative (named the marginal cost) as shown Fig.
Cost Curve Karginal Cost Curve
Conts coollare
Quantiy igls hour)
Figure 5: Thirsty Thelma's Total-Cost and Marginal Marginal-Cost Cost Curves
This phenomenon is commonly ohserved 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 small quantity of lemonade, her workforce limited, and much of her equipment remains idle. The of utilizing these unused resources results a substantial marginal product for an additional worker and 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 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 significant increase the marginal cost 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 mit-minimll AUF problem, when the decision-maie maker decides to alter variables in Z. the cost associated with different alterations vary. For the same variable, the cost of altering from a datum point should have a similar shape to total cost curve in Fig. varying with an increasing derivative. That is how we define the cost function this paper. The cost function could replaced by any other convex function in diffcrent situations.
C Proofs
In this section, we provide proof for claims in the main text.
C.1 Proof for Proposition 3.2
Lemma C.I. !f E is symmetric positive definite matrix, the following two sets are equivalent:
<x:x=='><s1 + xx:x= Σ²u ||ui|a $ 1).
where x and vectors with center at the origin of the coordinate system O.
Proof. Assume P. = fx x x D0'x 1 and P2 xx:x= v ||ui|2 $ 13. Then what we need to
prove is equivalent
(1) Points contained in have contained Pa.
(2) Points contained in Pa have to be contained in Pi.
For (1), it holds that x Σ -''x < 1, which is equivalent to (E xx) ( xx) S 1. Thus, let u Σ 1xx it can be derived that x Σ where ||u/||2 5 1, and (1) is proved.
For (2), we replace x Σ with x Σ u. then it can be derived that:
--1 - T - uTu Ju
16

---

which shows that points contained in P2 are also contained in Pi, so (2) is proved. In conclusion, the lemma is proved.
Proposition 3.2. The following set P is probability region that satisfies (P(Y: E P| Xi, xr, Rh(()) = T:
P - { My. + 10::+(xx'0 (T)) /uu | $1]
where My: Ax, + Bzi, is arbitrary point in the unit sphere in R Xel, and x (.) denotes the quantile function of the x² distribution with degrees of freedom = (Y)).
Proof. Recall from Lemma 3.1 that:
~ N Y, = Ax: + Bzf + Cee.
From the property multi- multi-normal distributions, it holds that:
Y, ~ NV (Ax + Bzf, C
Let My. = Ax: + Bzf, then we normalize the distribution above, it can be derived that:
(CEC7) - ~ ~N
So it can derived that:
(Y, (CECT)* -1 (Y: - My:) ~ Xa:
where the x2 distribution has the degrees of freedom À = Ye/.
Let x (.) denote the quantile function of the distribution x² above, then P can be given
== {7 (r -yy)) (CECT)" (r Myd xx
which is equivalent to:
P = {r: (7V--ut -bx) (2))(xxx(()) (x" " (t pyy
By lemma C11
it is equivalent to:
P = 7::7= =y: My: (x"
||u||2 |
where My:
Axi + Bzf, and is an arbitrary point in unit sphere R!
C.2
Proof for Theorem 3.3
Lemma C22 (Theorem 3 of Cutler et al. I1] Consider a sequence of stochastic optimization problems
ming f(() indexed by time E N. Let denote the estimation for the gradient of fú, and 3t denote the minimizer of the L-smooth and p-strongly convex function fa. Suppose holds that max; 9, S o² oc and max, B 3t l| S A <, co. Then the produced (3e YTzo with iterates B
[T 78.) (13 = R101)
and constant learning rate r 1/2T. satisfies:
E 1| - 1 (1-11)) 11.u -611 No²
pm
aptimization
drgg
Lemma C.3 (Convergence of LSE).
Let 33, denote the true parameter value of By time i, and Bie denote
the estimation according to Eq. 4
For Vol > 0, 3n > O that holds:
E Bhe B3.1
Proof. Let P = [PA], equivalent to:
PAP.] and VyJa [V]]..... V
Then the optimization Eq.
arg |[ P 13.
3/
17

---

Since РA, represents the true parents of the generation process for variable VG. P3. is guaranteed to have full column rank. For Vn [PAş], the solution the optimization above is:
BJ. = (PJ.P3.)) Pa
Because V,. = Ps. + where e, ~ N oīJ) according to Eq. 3 wC have:
f = B3. (PJ.P
P.J. J.
Due to the linear combination property of the Gaussian distribution, holds that:
3 - B3 ~ N No.0((00 (P).P...) -1)
Thus, can be derived that:
glae 33.1 tr (03 (P..PP.))
IPA,1
o3 Σ di A1s are eigenvalues of (P].PP.e) "
Amaz of |/pp1 (P
PAy1 PA
JT..P. - (PTTPP.))
Because
we have:
0f PAj
B B|1 B3.0
PA51 12
Y:s are eigenvalues of (T(P..:()))
s..
PAşl
PA 12
0f PA 1
031 PA, 12
tr
[P P..)
E
Pi
ming I|PA, 14a
So for V/b > 0, 3n o3 |
N min: (PA)
Pik) that holds || 83.1 sb.
Lemma C.4 (Positive-definite Property). Consider set of rn-dimensional vectors {va)== 2 m. If
contains at least one set of basis vectors in space 1em then the following matrix is positive-defiitt:
M Σ V.V.
Proof. Let {ue) S [v:)ī_ denote set of basis vectors, and x E R denote an arbitrary m- dimensional points in the same space as v,s. Then it can be derived that:
Mxx
x
v.
m
Uk
> 0,
because there at least exists one basis vector un that holds x un # O. So M is positive-detinite (thus M is full-rank).
Theorem 3.3. Denote the true parameter of By in time t Br (j E [[V[] and choose n, 10,1/2Lz] as step size used in Algorithm it can be bounded in G that:
B - & (1- (1-un)) 3
3,0
+ +5, with 5,
m4j
where and Ly are the minimal and maximal eigenvalues of (L 's Hessian matrices respectively, o² bounds the variance of 95.2 used in Algorithm 1 D, 2 max, [|, - .3.all bounds the varying speed of the environment, and m is the longest continiously altered rounds V₁. for most of the Vjs, L.
18

---

Prouf. For Eq. the Hessain matrix of (-) can be derived that:
H = 7 e3 Σ PA PA T
Since IPAyl and PAA,, s are discrete samples from continuous distribution, { contains set of basis vectors in space R PA.l with probability 1. By Lemma C.4 (Hz positive-definite
Let My denote min, À (Hz,)) and L, denote max; X (Hj,)) respectively, then (G),(-) are all Ly-smooth and -lr-snonggyy convex. By Lemma and consider alterations on V,, estimations |3.0 2-1 Algorithm hold that:
obtained from
B
B Binl 5 $1- |3,0 03a||
mā² Mym
"ia² +
H4
where o² upper-bounds the variance Øs.e used in Algorithm A 2 max, || F5,ll upper-bounds the varying speed of the minimizer of Ej.t, and m is the longest continuously altered rounds of V,. for most of
the VJs, m = 1. This holds because mā, 2 m max; ||55, 33,1l 2 max, E |188 - 2 max: f| 3,all. Note that if V, is continuously altered rounds, it can be viewed as its corresponding parameters updated per rounds.
Besides, since $/.5 A
37et1 in such case, let A, 2 max: 118],+1 - Blell. by Lemma C.3 it holds that E
Á x 4j. |3:0 3,0 -
|3,0
83.0
|13,e Bs,all* < th: and we have:
B BlBBrr
35.0
$ 03,e- "ل,l|
+ B +B113,, B5.e1l
(1 (ym) 1/m
|1050 3,00|
mm,
+ To
MyM
My
C.3 Proof of Proposition 3.4
Lemma C.5 (Hoefiding 1963.. Let X be a random variable with a S X S. b. Then, for any E RR
In [e*] S sE[X]
36 a)²
8
Proposition 3.4. Assume (G,())) are bounded for VB: E B and L [T]; then for any Hjj estimations B5.s from Algorithm 2 satisfies that
T
4u (3..) & (P.) S O (V(TIn,,)
by choosing / N//T in Algorithm 2 where N₂ is the number of buse-learners, 83,, is the estimation from any expert 1) expert set H, in Algardhm 2
Prouf. Following previous studies S (Theorem 2.2 and Exercise 2.5), we define:
L7
Σ 4.x (3%,) and W. Σ
w/e -
From the updating rule in Algorithm is easy verify that:
WHe o01
w Epex wffe -ale,- t2
(7)
First, it can be derived that:
In Wr In
Σ wffe -al7
2 In
max wie -013 NEH,
min
L
(8)
mc R2
w
nE
19

---

Next, the related quantity Iu (W,/Wi... can be bounded as follows when / 2 2:
SHEHwRe woe-aL -aL) EyER, w -alii
We
In
W
EHERY wife affe-aci -003..(03.)) ))
wif upe-al
In
Σ
nEN;
In
Σ
w ((se
nEw,
When = 1, holds
W (Enew wie
w/e (l=-)))(0)))) thus can derived that:
Σ w al5.0 NE
In WT W1
In
Wr-1
1=1
w Ea (8%,e) + a²o²
v aa Σ
(c constant as lg bounded)
ne,,
$ -al
a²c²
-al,, (3:0)
a²c²
MEN,
99)
where 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. combining Eq. (8) and Eq. (9). it can be derived that:
Σ eye (3,0)
min HER,
Σ ba (8%,)
In w² S
TTe
8
Since choose w" Nj
in Algorithm
thus for 17 Hlj by choosing
v Nj/T, it holds that:
T
Σ Ea (3g1)
Σ
by (8%,, S aT
1 la N₂ =0 11,,=NoVTTTun (VTTIuN,)
C.4 Proof for Theorem 3.5
Theorem 3.5. By using the suggested alterationss from Eg. (6) it be guaranteed that:
P P(Y: E 0 X1, HM(E)) t.
Proof. Recall that Eq. 6 suggests alterations follows:
min (2f 2!) W (2) -2)) Se
s.t. MAX: + MB + [MPI|2a0 2,,0 d.
where P (FC and || 11 means an operator that takes 2-norm for each row matrix thus outputs now-dimensional vector. We omit the subscript 2 of the norm in the following discussions.
20

---

Let denote the i-th row-vector of matrix MP and r denote the row-dimension of MP. then it can be derived that:
2 MAX: - MB2 + ||MP|| 2,00
MAX: MBZ, + (1 Il ... 1 -l)+-l))
2 MAx: MBZ + sup
I ||u| cos(mo u),
sup 1i
||> || cos( u)
MAX: MBZi
sup
(mi, u),
(Tr. w
||ll|
Iul 51
sup MAX: MB MPu
||
sup M My: +0,++(x000 (x")))=)))))) #
||u|S1
where My, = Axt + Bzz". Recall from Prop. 3.2 that p = -My. + (x (T) u is the probability
region that satisfies I Y, E x,, (k(E))
(since A, B. C generated from Ó. rather than O this case). Thus, Prop. 3.2 has been proved because (a) been derived that for Vy, E it holds that My:: and (b) the desired region defined Eq. 3 is S = E My & d
Experimental details
The experiments done by using macOS Monterey, Apple MI Pro. All algorithms running under the environment.
D.1 Comparison experiment in the setting of Qin et al.
40
We provide a comparison experiment in setting Qin 40) where G P(G) P(G) are unknown.
Results on Bermuda data provided in the following table show that our approach exhibits a comparable performance with the result under the scenario where G. G.
Success Frequency
Cost
Time (s)
G. G G ~ Pa
0.711 + 0.018
1.46 1 0.05
1.71
0.34
0.698 + 0.021
1.43 1 0.07
1.99
0.46
D.2 Market-Manage Data
In this section, we provide details about the Market-Manage data. The variables included in the generation process are:
Feature The feature used predict the cost of market;
Feature The feature used to predict raw cost competitor market;
Cour: The raw cost of our market;
Ceje: The cost of the competitor market;
Pour: The product price of our market;
Pope: The product price of the competitor market;
NCT: Customer numbers of our market;
TPF: Total profit of our market.
The rehearsal graph for the variables is illustrated in Fig. 6 The presumed actionable variables that can be altered by the manager Caur and P.ur. The hyperparameters associated with the cost function set Ze 0.75. Wc... = 2.0: and Zo = 0.0, 1.0. The desired region S is shown in Fig. 7(a) We shade dynamic edges with red color.
21

---

Cau
Feature
NCT
Pau
Pape
TPF
feature
Ci
X
Z.
Y,
Figure The rehearsal graph for market-manage data.
0:35
Oriinal Y Dillibutoon
0:00
Region
Naturaal NCT Value
6.25
0:00
6.15-
Original Y Eistribttion Region
Natural TPF Value
Natural NEC (V) Value
(a) in nature and region for Market data
(b) in nature and region S Bermuda
Figure 7: The desired regions Ss of two datasets.
D.3
Bermuda Data
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 the bottom;
Temp: Temperature at the bottom;
Sal: Sea surface salinity:
DIC: Dissolved inorganic carbon of seawater;
TA: Total alkalinity of seawater;
QA Saturation with respect to aragonite in seawater;
Chla: Chlorophyll-a at surface:
Nut: PC1 of NH,, NiO. + NiO,, SiO,:
pHsw: pH of seawater;
CO2: Pcoy of scawater;
NEC: Net ecosystem calcification.
22

---

The rehearsal graph for the variables is illustrated in Fig. 8 The presumed actionable variables that can be altered by the decision-makke DIC, TA, 42,, Chla, and Nut according Aglietti al. M. Qin et al. 40
hyperparameters associated with the cost function are as Zuse Zia Za, Z Z = 0.0: and
Wpic 10.0, WiA = 8.0, WRA 3.0, Wchh 5.0, WNat = 10.0. The desired region S shown in Fig. 7(b) We shade dynamic edges with red color.
Light
DIC
Chla
Nut
Temp
TA
pHsw
Sal
CO2
X,
Y,
Figure 8: The rehearsal graph for Bermuda data.
23

---

NeurIPS Paper Checklist
1. Claims
Question: the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Contributions of the paper are summarized in the abstract and listed in the last paragraph of Sec. Meanwhile, the scope is also introduced in Sec.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can he expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the work discussed in the separate "Discussion" section in as pointed out the first paragraph Sec.
Appendix A
Guidelines:
The answer NA means that paper has no limitation while the answer 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 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 the scope of the claims made, c.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-ter system might not be used reliably to provide closed captions for online lectures because 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, worse outcome might that reviewers discover limitations that aren't I 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.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are listed in Eq. 3 (with its contexts), and in each Theorenm/Poopsitionn. All proofs are given in Appendix C
Guidelines:
The answer NA means that the paper does not include theoretical results.
24

---

All the theorems, formulas, and proof' in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' 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 supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
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)?
Question:
Answer: [Yss]
Justification: The code and data for the main experimental results provided in the supplemental material. Dataset and experimental details are introduced in Sec. 3 and Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer to this question will not be perceived well by the
reviewers: Making the paper reproducible important, regardless whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on contribution, reproducibility can be accomplished various ways. For example, if the contrihution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others replicate the model with the same dataset, or provide access the model. general. releasing code and data often one good way to accomplish this, 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 model checkpoint, or other means that are appropriate to the rescarch performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility. which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily 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 a way to reproduce the model (e.g.. with open-source dataset instructions for how 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 source models, it may he that access to the model is limited in some way (e.g.. registered users), but it should be possible for other rescarchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does paper provide open access to the data 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 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 hattps://nips.cc/ppee for more details.
guides/Coon CodeSuooieeea boodeSubaissioonoliccoo
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 new open-source benchmark).
25

---

The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines btttps://nips.cc/pppi for more details.
The authors should provide instructions data access and preparation, including how 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 experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting Details
Question: Does the paper specify all the training and test details (c.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. S). 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 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.
7. Experiment Statistical Significance
Question: Does the paper report error hars suitably and correctly defined or other appropriate informa- tion about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars and error bands are provided in Fig. As introduced in the first paragraph of Sec. 5 we repeat the experiments 20 times (20 different random seeds).
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, overall run with given experimental conditions).
The method for calculating the error hars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors.
It should be clear whether the eтror bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful symmetric error bars would yield results that are out range (e.g. negative error rates). error bars reported in tables plots, The authors should explain in the text how they calculated and reference the corresponding figures or tables the text.
show in tables figures
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time execution) needed reproduce the experiments?
Answer: [Yes]
Justification: The time execution is denoted in Table Information on computer resources introduced in the first paragraph of Appendix
Guidelines:
26

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, every respect, with the NeurIPS Code of Ethics https///////ei.....p/a//a/a////a
Answer: [Ys]]
Justification:
The research conducted in the paper conforms with the NeurlPS Code of Ethics in every
respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make
preserve anonymity (e.g.. if there is special consideration due laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: Yes]
Justification:
The paper has discussed in Sec. | and Sec. that our proposed algorithm could be used to make decisions in certain cases, which may potentially lead to some positive societal impacts.
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 societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance). fairness considerations (e.g., deploy- ment technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will he 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 generate deepfakes for disinformation. On the other hand, it not needed point out a generic algorithm 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 tcchnology is being used 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 relcase models, providing defenses in addition attacks, mechanisms for monitor- ing misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have heen put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This work focuses on the methodology level and poses no such risks, because the datascts used in the paper are synthetic or have been used previous academic articles.
Guidelines:
27

---

The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should he released with necessary safeguards to allow for controlled use of the model, for example hy requiring that users adhere to usage guidelines restrictions access the model 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 take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are creators or original owners assets (e.g. code, data, models), used 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 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 license (e.g.. CC-BY 4.0) should be included for each asset. scraped data from particular source (e.g.. website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswi thcode 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 he 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: [Ye]]
Justification: The code model introduced in the paper are well documented, the documentation is provided alongside the assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate details of the dataset/code/mooel as part of their sub- missions 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 anonymized zip file.
14. 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, 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.
28

---

According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed 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?
Question:
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 expect authors adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
initial submissions, ble), such as institution conducting the review.
include any information that would break anonymity applica-
29


Reviews:
[{"review_id": "wbX4M1TxHu", "reviewer": "Reviewer_pTXc", "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.", "questions": "For the differences between SRM in the rehearsal graph and SCM in causality:\n- 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? \n- 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.\n- The operators in Figure 2 seem identical to the Intervention operator in causality.\n\n[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.\n\nThere are other minor typo errors:\n- It seems that in Eq.(1) or Eq.(3), it is better to add $t$ as a subscript for $V_j$ and $\\varepsilon_j$?\n- In line 181, \"ound\" might be \"round\".", "limitations": "Not applicable.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This paper is written well and clearly, with intuitive motivation and clarified novelty.\n\n- This paper includes a complete theoretical analysis and algorithmic design. Their proposed problem formalization is more general and practical than existing methods [37]. In particular, they first proposed a sequential method to maintain the dynamical influence, with guarantees of estimation error bound. They entailed Proposition 3.2 and Theorem 3.5 to help find the efficient alteration for $Z_t$ with the minimal cost. They finally propose the whole algorithm called AUF-MICNS, to avoid undesired outcomes in each decision round.\n\n- Experimental results show the effectiveness and efficiency of their proposed algorithm, where the evaluation metrics are success frequency, estimation error, average running time, etc.", "weaknesses": "I think my major concerns have been settled by the Supplementary Materials. So I have no other comments about the weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable feedback and appreciation of our work. We hope that our responses could mitigate your concerns.\n\n**Q1.** The difference between SRM and SCM.\n\n**A1.** Thank you for your insightful question. To some extent, the SRM and Rh(.) operations [1, 2] are indeed similar to their counterparts, SCM and do(.), in causality [3, 4]. However, there are some differences between the two graphical models. We will first outline these differences and then address the specific aspects you are interested in.\n\n\n1. The modeling granularity of the rehearsal graph is more flexible. Under the assumption of causal sufficiency [3], direct edges in a DAG (directed acyclic graph) represent causal linkages. For example, $A \\rightarrow C$ indicates that $A$ is the direct cause of $C$. In contrast, direct edges in a rehearsal graph do not necessarily represent causal linkages. For instance, $A \\rightarrow C$ only implies that changes in $A$ lead to changes in $C$, without stating that $A$ is the direct cause of $C$. In this sense, the rehearsal graph is similar to a MAG (maximal ancestral graph) [5], however:\n\n2. Bi-directional edges in a MAG do not have the same meaning as bi-directional edges in the SRM. Specifically, $A \\leftrightarrow B$ in a MAG indicates that there are common causes between $A$ and $B$. Consequently, $do(A)$ would remove all associations between $A$ and $B$. In contrast, $A \\leftrightarrow B$ in a rehearsal graph signifies that $A$ and $B$ mutually influence each other. Therefore, $Rh(A)$ only removes the influence of $B$ on $A$, resulting in $A \\rightarrow B$ in the modified graph.\n\n3. Possible dynamic influence relationships are allowed in SRM, as detailed in Appendix A.2.\n\nBased on the differences above, we would like to address your questions:\n- **Non-linear influences in rehearsal graph**. In this case, the influence $A \\rightarrow B$ in the SRM is defined as the changes in $B$ when a unit change occurs in $A$. This is similar to the causal effect; however, the SRM also allows for dynamic properties, while the SCM generally assumes stationarity. Different from classic causations which typically describe the nature process that is stationary, the influence relation is more in accord with the decision process which could be dynamic. To prevent the potential misleading, we adopt influence relation in the paper.\n\n- **Information of bi-directional edge**. As explained in point 2 above, a bi-directional edge in causality (MAG) indicates a non-ancestral relationship. In contrast, a bi-directional edge in the rehearsal graph models a mutually influenced relationship. This modeling approach differs from cyclic causality [6, 7, 8], which also allows for mutually influenced $A _{\\leftarrow}^{\\rightarrow} B$ in the causal graph.\n    1. In cyclic causality modeling, parameters related to $A _{\\leftarrow}^{\\rightarrow} B$ exist in both observational and interventional situations [6].\n    2. In SRM, parameters related to edge $A \\leftrightarrow B$ only appear when one variable is altered (no parameters are associated with bi-directional edges in observational situation). This modeling approach reduces the number of parameters in the observational case and is reasonable. Consider the following simple example as an illustration: when $x_1 \\leftrightarrow x_2$, $x_3 \\rightarrow x_1$, and $x_3 \\rightarrow x_2$, using $x_1 = ax_2 + bx_3$ and $x_2 = cx_1 + dx_3$ to model the relations is equivalent to $x_1 = \\alpha x_3$ and $x_2 = \\gamma x_3$ with $\\alpha = \\frac{ad+b}{1-ac}$ and $\\gamma = \\frac{bc+d}{1-ac}$. The latter model only uses 2 parameters, $\\alpha$ and $\\gamma$. Additionally, if $x_1$ is altered, the structure becomes $x_1 \\rightarrow x_2\\leftarrow x_3$. In this case, the parameter $\\beta_{x_1 x_2}$ associated with $x_1\\rightarrow x_2$ occurs. More details about the bi-directional edges are discussed in [2].\n- **The $Rh(\\cdot)$ operator in Figure 2 seems identical to intervention operator**. Conceptually, yes. However, as discussed in point 2 above, when operating on a node with bi-directional edges, these two operators will lead to different graph structures. This difference arises primarily from the distinct information contained in the bi-directional edges in rehearsal graph and MAG. To prevent the misunderstanding, we follow the existing operator $Rh(\\cdot)$.\n\n\nAt last, it is noteworthy that our approach can also work well when the structural information is expressed by an SCM (in linear Gaussain case), because Algorithm 2 and Proposition 3.2 also hold for SCM modeling. \n\nThanks again for your helpful feedback. We will add this discussion and comparison with new related works in the revised version.\n\n---\n\n**Q2.** Typo errors that subscript $t$ should be added. \n\n**A2.** Thanks for your advice. We will add the subscript $t$ for $V_j$ and $\\varepsilon_j$ in Eq. (1) and (3).\n\n---\n\n**Q3.** Typo errors that \"ound\" should be \"round\".\n\n**A3.** Thanks for your sharp observation. We will correct the spelling error.\n\n\n---\n\n**References:**\n\n[1] Rehearsal: Learning from prediction to decision, FCS 2022.\n\n[2] Rehearsal learning for avoiding undesired future, NeurIPS 2023.\n\n[3] Causation, Prediction, and Search, MIT Press, 2000.\n\n[4] Causality: Models, Reasoning and Inference, Cambridge University Press, 2009.\n\n[5] Ancestral graph Markov models, The Annals of Statistics, 2002.\n\n[6] Learning linear cyclic causal models with latent variables, JMLR 2012.\n\n[7] Causal relationship between obesity and vitamin D status: Bi-directional Mendelian randomization analysis of multiple cohorts, PLoS medicine 2013.\n\n[8] NODAGSFlow: Nonlinear cyclic causal structure learning, AISTATS 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nW2dzVN6gJ", "reviewer": "Reviewer_w1Mx", "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.", "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.\n\nI 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": "No limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The method of Qin et al. [37] suffers a high computational cost. In this paper, the authors convert the problem to a QCQP problem, which makes it computable in polynomial time. It is a valuable contribution.\n\n2. Theorem 3.3 presents an interesting and sensible theoretical guarantee. It is novel to see that some traditional online learning methods could be used in such decision tasks.", "weaknesses": "Some discussion about the offline RL are missing. See Questions for the details.\n\nGiven 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.\n\nThe 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.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the insightful feedback and the interest in our work! We hope our responses can address your concerns.\n\n**W1&Q1.** Discussion on the offline RL.\n\n**A1.** Thanks for your question. Generally speaking, online-offline hybrid RL methods can reduce the number of interactions by leveraging offline policy learning. However, these methods do not fit the AUF scenarios described in the paper for the following reasons:\n\n- In the offline training stage, hybrid RL methods use labeled offline datasets, i.e., offline datasets containing $(s, a, r)$ samples. However, in the AUF scenarios presented in the paper, only a few observational samples are available (in $(s, r)$ form), which do not contain information on any actions.\n- Considering \"no action\" as a special type of action is practical, but this approach would transform all offline data into the $(s, \\text{no-action}, r)$ form, making it difficult to learn effective offline policies.\n- To achieve an effective policy, hybrid RL methods require a large number of offline samples and online interactions compared to the rehearsal-based methods [1]. For example, millions of online and offline samples are typically needed to obtain an effective policy [2, 3]. In contrast, our approach works well with only 100 samples in the AUF setting. This is because the rehearsal-based method can leverage the fine-grained structural information contained in the involved variables, whereas RL methods cannot.\n\nWe will add this discussion to the revised paper. Thanks again!\n\n---\n\n**W2.** $\\tau$ in Theorem 3.5 and Algorithm 3.\n\n**A2.** We apologize for the confusion. In fact, the threshold $\\tau$ is used in Eq. (6) to construct the matrix $\\mathbf{P}=(\\chi^{-1}(\\tau)\\mathbf{C}\\mathbf{\\Sigma}\\mathbf{C}^\\top)^{\\frac{1}{2}}$, which appears in the constraint term in Eq. (6). Although $\\tau$ is not explicitly mentioned in Section 3.3, both Theorem 3.5 and Algorithm 3 are related to the optimization Eq. (6). Hence, Theorem 3.5 and Algorithm 3 are connected to the threshold $\\tau$ as well.\n\nWe will clarify the related expressions in the revised version. Thanks!\n\n---\n\n**W3.** Writing problems.\n\n**A3.** We truly appreciate your advice. We will review and refine the expressions in the paper. Thank you!\n\n---\n\n**Q2.** Discussion for the non-linear case.\n\n**A4.** Generally speaking, non-linearity is indeed a significant challenge. However, it can be addressed in some cases, and we discuss the non-linearity in the following two stages:\n\n- For estimating the parameters of the SRM. In this case, non-linearity leads to different loss and surrogate loss functions compared to Eq. (4) and Eq. (5). If the new loss function $\\ell_{\\text{new}}$ is also convex w.r.t. $\\beta$, then our proposed Algorithm 2 can still be used to estimate the parameters sequentially. Furthermore, Theorem 3.3 and Proposition 3.4 remain applicable.\n- For making decisions based on the estimation. When the relationships among variables are non-linear, Lemma 3.1 no longer holds. As an alternative, one can consider $\\mathbf{Y}_t = f(\\mathbf{x}_t, \\mathbf{z}_t^\\xi, \\mathbf{\\epsilon}_t)$, where $f$ is a non-linear function. To obtain a probability region as described in Proposition 3.2, the characteristic function [4] of the random vector may be useful. In this scenario, the constraint in Eq. (6) might no longer be linear or quadratic, which means the QCQP reduction may not apply. However, if the constraint is convex, optimization algorithms such as projection gradient descent [5] can be used to solve the new optimization problem.\n\nLastly, we want to emphasize that addressing non-stationarity and improving time complexity are challenging even in the linear case. We will include this discussion in the future work section of the paper. Thank you!\n\n---\n\n\n**References:**\n\n[1] Rehearsal learning for avoiding undesired future, NeurIPS 2023.\n\n[2] Hybrid RL: Using both offline and online data can make RL efficient, ICLR 2022.\n\n[3] Offline meta reinforcement learning with online self-supervision, ICML 2022.\n\n[4] Elementary probability theory, Springer 1977.\n\n[5] Convex optimization. Cambridge University Press 2004.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y883dBPwzX", "reviewer": "Reviewer_weAS", "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.", "questions": "(1) How do algorithms handle the exploration-exploitation tradeoff (if explorations are needed)?\n\n(2) Is it possible to establish a regret bound for the cost? If not, what are the challenges?", "limitations": "See weaknesses.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written, introduces a practical and interesting setting for AUF problems, and presents an algorithm with theoretical guarantees and numerical validations to address the task.", "weaknesses": "(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.\n\n(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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed feedback, and we hope our responses will address your concerns.\n\n**W1&Q2.** Theoretical guarantees (regret bound) for the cost.\n\n**A1.** Thanks for your insightful question. In fact, theoretical guarantees of the cost can be inferred from existing results (Lemma 3.1 and Theorem 3.3), and we discuss as follows:\n- First, by using the interior-point method, Eq. (6) can achieve the optimal solution $z^*_{\\hat{\\theta}_t}$ that minimizes the objective cost function in each decision round $t$ since it is a convex QCQP [1, 2]. This is discussed in lines 265-271.\n- Because the constraint in Eq. (6) is constructed by $\\hat{\\theta_t}$ rather than $\\theta_t$, let $C(\\cdot)$ denote the cost function. The cost regret is $C(z^*_{\\hat{\\theta_t}}) - C(z^*_{\\theta_t})$. Meanwhile, since $z^*(\\cdot)$ can also be viewed as a function, let $f(\\cdot)$ denote $C \\circ z^*(\\cdot)$. The regret for the cost is $f(\\hat{\\theta}_t) - f(\\theta_t)$ in round $t$. Consider the following properties:\n    1. $||\\hat{\\theta}_t - \\theta_t||^2$ enjoys a linear convergence rate as guaranteed in Theorem 3.3. \n    2. $f(\\cdot)$ is a polynomial function, because $C(\\cdot)$ is quadric (cost function) and $z^*(\\cdot)$ is polynomial (as $z^*(\\cdot)$ is polynomial w.r.t. $\\mathbf{A}, \\mathbf{B}, \\mathbf{C}$ in the constraint of Eq. (6), and $\\mathbf{A}, \\mathbf{B}, \\mathbf{C}$ are all polynomial w.r.t. $\\theta_t$/$\\hat{\\theta}_t$, by proof process of Lemma. 3.1 [3]). \n    3. Both $||\\hat{\\theta}_t||$ and $||\\theta_t||$ are bounded, by definition.\n- As implied by the properties above, $||f(\\hat{\\theta_t}) - f(\\theta_t)||^2$ also enjoys a linear convergence rate. Consider the following simple example as an illustration:\n $$\n    (x-y)^2\\leq Le^{-t} \\quad\\mathop{\\Longrightarrow}\\quad (x^2-y^2)^2 =(x+y)^2(x-y)^2\n    \\leq (|x|+|y|)^2(x-y)^2\n    \\leq 4U^2L e^{-t} = \\mathcal{O}(e^{-t}),\n$$\nwhere $U\\in \\mathbb{R}_*$ is the upper bound of $|x|$ and $|y|$.\n\nWe will refine this discussion in the revised paper to make the guarantees more clear. Thanks!\n\n---\n \n**W2.**  The minimal eigenvalue of the Hessian matrix in Theorem 3.3.\n\n**A2.** Thanks for your feedback. The Hessian matrix in Theorem 3.3 refers to $\\nabla^2 \\ell(\\cdot)$ instead of $\\nabla^2 \\hat{\\ell}(\\cdot)$, where functions $\\ell(\\cdot)$ and $\\hat{\\ell}(\\cdot)$ are defined in Eq. (4) and Eq. (5), respectively. Meanwhile, the $\\hat{g}_{j,t}$ in Algorithm 1 refers to the gradient of $\\hat{\\ell}(\\cdot)$, i.e., $\\nabla \\hat{\\ell}(\\cdot)$, instead of $\\nabla \\ell(\\cdot)$.\n\nAs a surrogate loss function of $\\ell(\\cdot)$, $\\hat{\\ell}(\\cdot)$ only uses the collected sample in each round to approximate $\\ell(\\cdot)$. Hence, it is possible that the minimal eigenvalue of $\\nabla^2 \\hat{\\ell}$ equals 0 (as in your provided example), but we want to emphasize that the minimal eigenvalue of $\\nabla^2 \\ell$, i.e., $\\mu_j$ in Theorem 3.3, is not 0 since $\\nabla^2 \\ell$ is proven to be positive-definite in Appendix D, lines 714-738. Making uninformative alterations, as in your provided example, can be viewed as an extreme sample from $n$ potential possible alterations ($n$ in Eq. (4)).\n \nWe apologize for the unclear presentation, and we will refine the related part. Thank you!\n\n---\n\n**Q1.** Exploration-exploitation tradeoff.\n\n**A3.** Thanks for your question. Our modeling approach is different from conventional RL methods [4]. For the AUF problem, there are few opportunities to take actions (and perform explorations); hence, exploiting all available information to make effective decisions is essential. By leveraging the structural information (SRM), the rehearsal-based method can make decisions effectively without exploring different decision actions, as illustrated in the experimental results. Additionally, as explained in A2 above, selecting alterations does not adversely affect parameter estimation, eliminating the need for an exploration-exploitation tradeoff.\n\nWe hope that these explanations better convey our points. Thanks again!\n\n---\n\n**References:**\n\n[1] On implementing a primal-dual interior-point method for conic quadratic optimization, Math. Program. 2003.\n\n[2] Interior-point polynomial algorithms in convex programming, SIAM 1994.\n\n[3] Rehearsal learning for avoiding undesired future, NeurIPS 2023.\n\n[4] Reinforcement learning: An introduction, MIT Press 2018", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)