Rehearsal Learning for Avoiding Undesired Future
Authors: Tian Qin
Tian-Zuo Wang
Zhi-Hua Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: decision-making
structural rehearsal model
Bayesian inference
probabilistic graphical model
TL;DR: We present a rehearsal learning framework based on structural rehearsal models and Bayesian inference for recommending appropriate decisions to avoid undesired future outcomes.

Abstract: Machine learning (ML) models have been widely used to make predictions. Instead of a predictive statement about future outcomes, in many situations we want to pursue a decision: what can we do to avoid the undesired future if an ML model predicts so? In this paper, we present a rehearsal learning framework, in which decisions that can persuasively avoid the happening of undesired outcomes can be found and recommended. Based on the influence relation, we characterize the generative process of variables with structural rehearsal models, consisting of a probabilistic graphical model called rehearsal graphs and structural equations, and find actionable decisions that can alter the outcome by reasoning under a Bayesian framework. Moreover, we present a probably approximately correct bound to quantify the associated risk of a decision. Experiments validate the effectiveness of the proposed rehearsal learning framework and the informativeness of the bound.

Rehearsal Learning for Avoiding Undesired Future
Tian Qin, Tian-Zuo Wang, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology Nanjing University, Nanjing. 210023, China {qint, wangtz, zhouzh](1lel (arrhh@@@ammm ajj.eddi.
Abstract
Machine learning (ML) models have been widely used make predictions. Instead of predictive statement about future outcomes, in many situations we want to pursue decision: what we do to avoid the undesired future if ML model predicts so? In this paper, we present a rehearsal learning framework, in which decisions that can persuasively avoid the happening of undesired outcomes can be found and recommended. Based on the influence relation, we characterize the generative process variables with structural rehearsal models, consisting of a probabilistic graphical model called rehearsal graphs and structural equations, and find actionable decisions that can alter the outcome by reasoning under Bayesian framework. Moreover, we present a probably approximately correct bound to quantify the associated risk of decision. Experiments validate the effectiveness of the proposed rehearsal learning framework and the informativeness of the bound.
Introduction
Machine learning (ML) has achieved great success in various applications, including computer vision [1] natural language processing 22, recommender systems 3 4, etc. In addition to perception tasks such as classifying an image, ML. models have been widely used to make predictions, or forecasting, about future quantities of interest (5] 6). In many scenarios, however, what we ultimately pursue is typically not attaining merely predictive statement on what is likely to happen. Instead, as potential next direction 77, we may seek a way, possibly through decision-making, to avoid the happening of the upcoming undesired future, if the ML model predicts so.
Suppose we variables X to predict future outcome Y with an ML model h. Given instance x, h outputs a warning signal ğ = h(x) which is outside our desired range. The problem is: what do make the future Y fall into the desired range? We assume that there an intermediate stage where one can make actionable decisions to influence Y; egg. after a sales prediction made at the beginning of month, there is intermediate time window before the month-end for the sales manager to take action. We consider decisions in the form of altering variables with fixed values, egg. setting the discount 10%. We henceforth call such decisions alterations. Let Z denote the variables in the intermediate stage. The avoiding undesired future (AUF) problem is then how to alter variables in Z that the future Y could be shifted to fall into the desired range.
Common decision makinn methods under the umbrella of reinforcement learning (RL) g can be applied to the AUF problem but may not be the most appropriate. The reasons include that (a) RL mainly focuses on sequential decision-making tasks while AUF desires a direct decision to change the upcoming future outcome, for which considering decision sequences could be unnecessary unrealistic; (b) the success of RL in playing games ( and autonomous control 10] rely on sufficient interactions between the agent and the environment, but interactions in real AUF problems can be extremely sparse, e.g., the sales manager in the above example can only interact with the environment and make decisions once month; (c) the Markov decision process (MDP) formalism in RL abstracts decision-making into states, actions, and rewards, which may overlook useful fine- graing structural
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

information in AUF, e.g., the connections between variables that can be altered may help identify useful actions without any exploration. Explicitl incorporating such connections in modeling the AUF problem would be preferable since otherwise approximating them with MDPs may require unnecessarily large state or action spaces.
Therefore, we need a specific method for solving AUF that takes account of the structural information and avoids the use of the large number of interactions. An immediate thought would be seeking cause- effusc relations between variables [12]. which have been leveraged for some decision-related problems (see Section for a discussion of related work). But as indicated by Zhou 77 causal relations can help but should not be taken as a prerequisite for decision-making for reasons that (a) humans can make good decisions without a thorough or faithful causal understanding of the surrounding environment, sometimes correct decisions can even be made based on an incorrect causal understand- ing; (b) guiding decisions with causal relations is not always sensible as causation reveals truths that always hold, whereas decision-making is coping with real environments which are often open and dynamic: (c) causal modeling could be helpless for decision makion if the identified causal factors unactionable; needless say, it is very difficult to discover true cause-effect relations from data 13. Recognizing that correlation is helpful for prediction but insufficient for recisiinnmakinng and that causation is needed for scientific discovery but too luxury be relied on for decision-main making, Zhou 7 claimed that what is required for decision-making is kind of intermediate relation that is stronger than correlation but less demanding than causation; this relation was later called influence relation 11. Moreover, Zhou 77 attributed a decision to a series of hypothesized "rehearsal" of possible actions, which is intuitive way of leveraging even discovering the influence among variables involved in a decision task. Fig. depicts an intuitive demonstration of the relationship among correlation, influence, and causation.
Prediction
Correlation
Decision
Influence
Actionable
Discovery
Causation
Figure 1: Relationship between corre- lation, influence, and causation [
|
Based on the concept of rehearsal, we present the structural rehearsal model (SRM) to model the AUF problem. The SRM consists of new probabilistic graphical model called rehearsal graphs and a collection of generative structural equations. In contrast to traditional structural causal models (SCM) [12], the SRM allows dynamic modeling and accommodates the influence relation among variables, effectively capturing the interactions between interrelated but not necessarily causally linked variables. Given the true SRM, the effect of alterations can be calculated estimated by conducting rehearsals. Consequently, the AUF problem can be addressed by searching for optimal alterations that yield the desired outcomes, though the search process could be complex and difficult.
Note that structural models such as SRMs are generally not available in advance, and learning them from limited observational data is difficult well. In solving the AUF problem, one needs to tackle challenges posed by limited data, the uncertainty of structural models, and the possibly huge search space for finding optimal alteration. Morcover, system outputting decisions should provide some kind of guarantee on the probability of successfully avoiding undesired future, especially in high-stake applications such economic and safety tasks. The AUF problem can also come in an online fashion and induce an ppploration-xxploiaatiioo trade-off: a decision-make can choose alterations that will reveal more structural information benefit future pnecision-mainng or alterations that will maximize the success probability in the current decision round.
To address the aforementioned challenges and tackle the AUF problem, we introduce a rehearsal learning framework that integrates structural rehearsal models and Bayesian inference. This frame- work effectively captures the inherent uncertainty in decision- making processes aimed at averting undesired outcomes by unifying structural modeling, alteration finding, and success probability bounding. Our contributions are as follows:
1. Structural Rehearsal Model:
We propose SRM, a novel modeling approach distinet from SCM, designed to model the influence relation, which is more essential than causal relations for decision- making problems.
2. Constrained Optimization for AUF: We formulate a constrained optimization problem to solve the AUF problem, striking balance between averting undesired future scenarios and accurately learning rehearsal models.
2

---

3. Rehearsal Learning Framework: We develop a rehearsal learning framework tailored for solving AUF, showing that building decisions based on the influence relation is practical and feasible. We propose specific learning methods for the basic linear case and show that optimal solutions are not attainable in polynomial time in the framework if joint alterations are allowed, assuming P o NP. This insight underscores the significance of developing approximate solutions over exact ones. 4. Risk Quantification: We introduce probably approximately correct bound to quantify the associated risk inherent in a given decision. Our experiments provide empirical evidence of the informativeness of this bound.
2 Structural Rehearsal Models
are used to describe causal relations among variables, based on which actions that affect the outcome could be found. However, in some real-world problems, especially those involving decisions, causal relations are not adequate. For example, let P and Q denote the prices of product in two stores, respectively. If the first store decreases P to aftract customers, the second store will decrease Q accordingly because the second store will lose consumers otherwise. From a causal view, it seems that causes Q. But obviously, also causes P by symmetry. So we have a bi-directional "causal" relation, which is invalid in causal modeling. Mistakes will occur if one applies SCMs this example as only one-way causal relation is allowed in SCMs. The issue of such interrelated but not necessarily causally linked variables, as well as several other issues such as the dynamic and time-dependent nature of decision decision-making, which will be discussed later, are taken into account in the following new structural model called the structural rehearsal model (SRM).
Conventionally, SCMs 12
An SRM consists of set of rehearsal graphs and corresponding structural equations. rehearsal graph qualitatively describes the relations between variables, and the structural equations characterize the generating process of variables in detail. In contrast to static causal modeling, SRM allows dynamic modeling by defining both the graphs and equations over a time index t, which accounts for possible evolutions of the environment. We represent an SRM with {(G,, 0.) h. where G2 denotes the rehearsal graph at time / and Og parameterizes corresponding structural equations.
Rehearsal graphs allow both directional and bi-directional edges. The directional edges depict the generation ordering of variables and the bi-directional ones indicate interrelated variables that are mutually influenced. Fig. depicts an example. The definition of rehearsal graphs is given below: Definition 1 (Mixed graph). Let G = (V, E) be graph, where V denotes the vertices and E the edges. G is mixed graph if for any distinct vertices u, V, there is at most one edge connecting them, and the edge is either directional (u + v or + v) or bi-directional (u ++ v).
Definition (Bi-directional clique). A bi-directional clique C = (V*, ,E) of mixed graph G (V, E) is a complete subgraph induced by V C V such that any edge E E is bi-directional. C is maximal if adding any other vertex does not induce a bi-directional clique.
Definition 3 (Rehearsal graph). Let G (V, E) be mixed graph. Let {Ci) denote all maximal bi-directional cliques of G, where C, = (Vg, EG). G a rehearsal graph if and only if:
1. V n V = @ for any i * j.
2. Vi E [4], u E V.. if there is any edge pointing from u to V then Vo E V u.u u
3. The directional edges permit topological ordering for (C:)
Each vertex in a rehearsal graph corresponds to a variable. And the variables are generated following the ordering depicted by the directional edges. The variables in common maximal bi-directional clique, where only bi-directional edges exist, are mutually influenced instead of having a fixed generating order. Given rehearsal graph G, structural equations accompanying the rehearsal graph are defined over cliques {(VÇ, E Let PAÇ G {u Ee E Vf, - in G} denote parents of the i-th maximal bi-directional clique. Suppose that the unobserved noise variables are Gaussian, then the structural equation describing the generation process of V is parameterized by [B, E, } C 0:
V = (PA B.) + +
(1)
where /i is multi-valued function parameterized by B; and e; NO, Σ,) denotes the noise.
We denote the operation that alters variable X with fixed value x by Rh(X = x)), meaning that we perform rehearsal of setting X to through realistic hypothetical means. When Rh(X = x) is
3

---

A
A
A
F
F
P
P
B
G
E
G G<>E E
B
G
E
>
>C
B
C C
(Go, 0o)
01),0))
(Gr, Qr)
(a) G
(b) G
(c) GREE
(d) [Gr 0.)),
Figure 2: (a) displays an example rehearsal graph. (b) and (c) displays its alteration graphs with rehearsal operations on {F) and (B. E, F) respectively. We use plate notation to simplify the edges: If an endpoint of an edge falls exactly on the boundary of a rectangle, then there are edges for every vertex in that rectangle. (d) shows full SRM {(G, 0.) :. where t is the time index and the rehearsal graph G2 and parameters 0, can evolve over time. Recall the example of two stores and let the variables follow the depicted SRM. Suppose that t 1, the second store takes new marketing strategy that no longer follows the price of the first store, then P will not directly affect Q: The generation process evolves to P Q in G1 instead of P Q in Gg. Then for the first store, previously correct decision at f = O, which aims to affect C by altering P, is ineffective at = 1.
applied, we remove the incoming arrows of X in the original rehearsal graph G to get an alteration rehearsal graph xX=x, and the accompanying structural equations are modified according to the newly introduced parental relations in GX=x, where a new set of parameters in 0 could be introduced for the unseen parental relations to offer more flexible modeling abilities. The distribution PP | Rh(X x)) of all variables after applying Rh(X x) can be derived from Eq. (.. Example illustrations are in Figs. [b The "invalid" bi-directional "causal" relations are valid rehearsal graphs: P ++ Q becomes P Q when applying RP(P) and becomes P + Q when applying (h), capturing the interrelated influence between the two variables.
An important feature of SRM that distinguishes it from SCM is the capability of modeling dynamic and time-dependent real-world decision-making environments, where variable relations may evolve and correct decisions can vary dramatically at different times even for the same problem [14]. It is worth noting that these dynamic environments should not be confused with the conventional notion of dynamic systems, where the relationships among variables simply repeat over time. As causal modeling seeks to identify enduring cause-and-effect relationships, SCMs can be helpful in tasks such as "Al for science" [1] 16 17 where the objective is to uncover persistent scientific truths. However, SCMs can be restrictive describing the dynamic nature of decision problems. In contrast, the dynamic and time-dependent feature of environments is captured by SRM using evolving rehearsal graphs and corresponding parameters: At time i, the generating process characterized by (G,, O() can differ from previous ones. Fig. 2d illlstrrras an example where correct decisions vary across time and an SRM {(G,, ), is used to model the dynamic decision environment.
Although Or can be learned from data with general supervised learning methods given a fixed graphical structure, generally rehearsal graphs could not be uniquely identified from data. We present basic properties of rehearsal graphs and a preliminary graph class learning procedure in Appendix A
3 The AUF Problem
We treat AUF as multi-round online decision-making problem, where in the t-th decision round, an agent makes decisions to affect the outcome if it receives an undesired prediction, serving as a warning signal, from an ML model. In real problems, variables involved in each decision round generally do not appear simultaneously; e.g., a single decision round spans a full month, then a decision-maker may encounter new variables every day. Ignoring the variable generation order can be problematic, but modeling the decision process with refined time granularity is too demanding.
Therefore, we make midway proposal. We identify two important time points in AUF, the time the ML prediction is made and the time just before the generation of the concerned outcome, so the variables appearing in the f-th decision round fall into three consecutive time segments separated by the two time points: X,, variables appeared before the prediction is made; Z, variables appeared after the prediction and before the generation of the outcome; and Y,, the outcome variable. After the prediction, if the agent decides to do something to change the future outcome, the only variables can alter are those in Z,, since X, has already happened and cannot be altered. For example, suppose that in the 1-th month, a sales manager predicts the month sales Y, on the first day of that month and designs promotions in that month accordingly. Then X, can be marketing variables that appeared
4

---

before the first day and Z, can be variables in the remaining days of that month, such as the price next week, which can be altered to affect month sales.
More specifically, the decision process in the 1-th round is: An agent first observes Xz, with which an ML model gives pre- diction Y, for the outcome: if Y, & S, where S denotes the set of desired values, the agent should perform alterations on Z to prevent Y, E S: after the alteration, the agent can observe full Z and the outcome Y, We assume that the generation mech- anism of the encountered variables can be described by an SRM {(G,, 0z) where (G,, 0z) characterizes the generation pro- cess in the 1-th round. Fig. 3 depicts an example. For simplicity, the environment is stable, i.e., G2 = G,
X
Z
Y
21
Z0
+11
X2
Zz 24
>Bg
time
observe X. and make prediction
conducct alterations observe Z,
observe Y,
Rehearsal graph G, in the (-th round. The timeline shows the order in which the three sets of vari- ables are generated and events that happened to agent at different times in one round.
Figure 3:
assume that
0, = 0 for all t. Note that the agent does not have access to the true SRM. instead, it can access historical data D = ((x", z², y²) }') from which some information about the SRM can be learned.
In real scenarios, some variables cannot be manually altered or cannot be set to certain values. We denote the set of feasible alteration values for an actionable variable Z; E by (Z,)) which we assume to be a closed interval. An alteration is denoted by & {(Ze.. 2a, Ja)))= where Zo, E Z is the variable to be altered, 2a, E AZZ.,) is the alteration value, and ls is the alteration size. Applying & is treated as performing a rehearsal Rh({,) A Rh( Za. Za; )
1/m 1) on G.
The overall AUF problem is then given D and X,, t 1,..., T, that arrives sequentially, find alterations & in each round to successfully avoid the undesired future as many times as possible. The problem can be formulated as
T EI(Y, [XY xx, x., Rh(()))
max Eor
EETT
(2)
where e is the noise in Eq. ① and I[-) is the indicator function.
If the underlying SRM is known, one can obtain P(Y, xx, Rh(E:)). and the only issue is searching for a & that maximizes P(Y, E S x,, Rh(E))). The main obstacle to solving AUF, however, is the uncertainty of the SRM. The uncertainty leads to exploration-exploitttoo trade-off: In each round, the agent chooses alterations that help reveal true SRMs (exploration), a more accurate environment model may be obtained and benefit decisions in future rounds, but it may fail in the current round. On the other hand, if the agent chooses a short-sighted decision that successfully avoids the upcoming undesired future (exploitation), it may learn little about SRMs, making future optimizations difficult. In addition, the effect of alterations can propagate to downstream variables through the directional edges in rehearsal graph, thus the value of unactionable variables may be affected by altering the pallorationexxploitaaio
actionable ones. A feasible approach should take account of the uncertainty, trade-off, and propagation of effects in the online decision process and yield reasonable decisions.
Some extra knowledge can be utilized. First, the partition of the three sets of variables reflects the order in which the variables are generated. Any edge crossing the three sets should point from the previous one to the latter one, which reduces the uncertainty on G. Further, since an agent observes X, before making a decision, the generating mechanism inside X, does not affect the distribution of outcomes, as shown in Prop. 4 so we can safely pretend that G does not have edges inside X,.
Proposition 4. For any (G1. 02) and (G2, 02) on X, U Z, U Y, if they differ only in descrübing the generation of Xx, then for any X. = Xt and alterations on Ze, we have
P P(y: x,, Rh(E): G1 0,) = P (y: x4. Rh((); G22 02).
In the following, restrict attention to a basic instance of the AUF problem: The structural equations fis are linear and the desired set S is a convex polytope, i.e.,
V = 3 PA + +G,, S = {y E ER/Y| My S d), where | denotes the cardinality of set, d e R', P.MM E | and B, E R IPASIIIIVI
5

---

Rehearsal Learning
In this section, we present a rehearsal learning framework address the AUF problem in Eq. (2 and present specific methods for the linear case in Eq. (3) in which we use sampling and rehearsal of actions as basic building block to find and evaluate decisions.
To account for the uncertainty introduced by limited data, we resort to Bayesian inference. The state of knowledge of the SRM is described by the posterior distribution:
P(G, D.) F(G) D.) G, Dr),
where Dr is the evidence collected until the beginning of round I, consisting of the initial observational trade-off between choosing
data D and {(x,, f., Z, v=) To handle the axploraton-eeplloiatii alterations that help recovers the true SRM and alterations that can avoid undesired future in the
current round, we leave the choice the agent by introducing hyper-parameter that balances these two kinds of alterations. In the t-th round, we propose to solve
max E.
I(G, θ Ze Y, Dr. Xt, Rh(E))
(5)
s.t. Eg (T, E G,O,x, | (
(6)
The constraint in Eq. (6) reflects the required performance: Performing the alteration should make the belief that the desired future can be successfully achieved greater than т given knowledge of the SRM so far. The objective function in Eq. (5) denotes the mutual information between the SRM and the observations revealed after the alteration. Overall, the solution the optimization problem should avoid undesired future and meanwhile be most informative about the true SRM.
The proposed optimization problem introduces computational challenges, e.g., one has a super-expomential number of rehearsal graphs to compute the mutual information or the success probability. We divide rehearsal learning into three approximately tractable components: Bayesian update of SRMs, candidate alteration selection, and mutual information maximization. To better guide decision-making, bound to quantify the risk associated with the selected alteration.
also present sampling-basee probably approximately correct (PAC)
4.1 Bayesian Update of SRMs
Recall that the posterior of SRMs is divided into the posterior of graphs P(G' | D.) and that of structural equation parameters P(O G, D:) in Eq. 4 For the former term, we adopt a bootstrapping- based approximation [18), which learns multiple rehearsal graphs bootstrapped data build set of graphs G and weigh each graph E 9 equaall. The approximated posterior of graphs is
P(G Dz)
Σ G
9
Consequently, for the second term P(O G, Dr), we only need estimate parameters corresponding to graphs that appear in G, which greatly reduces computation. The parameter posterior factorizes as
P(O G. G.
II
P(Bv-, Eve (")D)).
G'EA(G).
where A(G)) is set of graphs that includes G and related alteration graphs and V denotes maximal bi-directional clique. P( Eve G', ,)) the posterior a set of regression parameters and noise variance given data of V and its parents in G'. So various Bayesian learning methods [19] are applicable for its estimation. We adopt Bayesian ridge regression (00 to learn the parameters. In addition, graph learning is time-consuming, we use an incremental implementation: We build an initial graph posterior from purely observational data for / = 0 using Eq. 77). then update the posterior with
P[G D.) x P(G) D.-I) 1 Σ P(z., ye Xt, Ec, C
where 0: is sampled from P(O G, D,-1) and the averaged summation term is an empirical estimate of likelihood. With the above approximations and learning, we effectively obtain an approximate posterior and efficient sampler over SRMs, which forms the basis of the following two steps.

---

4.2 Candidate Alteration Selection
In the second part, we find candidate alterations that satisfy the performance constraint in Eq. 6 The constraint cannot be accurately computed as it takes an expectation over discrete G and continuous O. To reduce the computational burden, we estimate the constraint with posterior samples. Note that the value of variables V is uniquely determined by G, 0, and the noise e in Eq. ( We can evaluate all alterations by generating Y, from a common set of SRMs and noise samples. Suppose we have an i.i.d. sample 5 ((G,, 0, {;) H= the empirical estimate of Eq. (6) is
Pe. (S) - Hi Vi.e. E)//nn
where yig, is the concerned outcome generated following the SRM specified by (Gi, 0i, ex) and Rh(Ei). A general method for candidate alteration selection has three stages:
1. Sample two sets of i.i.d. parameters, the training set Str {(G,, 0i, ei) and the validation 1 -i=++1 1- from PP(G, 0 Dz) and P( 0).
set Seat {(G,, 0,, }
2. Build candidate alteration set C by conducting rehearsals on Str and finding alterations & that achieve required performance т, i.e., Vε, E C, Pc, (Srr) 2 т.
3. Validate alterations in C' by rehearsals on Seat and remove those with Pr. (Sval) < T from C.
The validation procedure is to alleviate overfitting as in standard machine learning pipelines. If stage 2 or 3 outputs an empty set, the system should refuse to make any recommendations. The agent can lower and restart if a smaller is still adequate for the task hand.
For given alteration, validation relatively easy to perform. The only issue to address is to find a set of alterations that pass the test on Str. An immediate approach would be enumerating possible alterations and making rehearsals on training samples to check the constraint. But the enumeration can be computationally prohibitive as the alteration space be combinatorial and continuous. A compromise between the optimality of recommended alterations and the computational fcasibility is to work some finite subset of alterations using some discretization tricks or heuristics. Fortunately, due to the linear structure of the SRMs considered here, Prop. [] shows that the outcome variables are linear in the alteration values, implying the existence of more efficient and effective solutions.
Proposition 5. Let & = {(Za, 2 )i= be a valid alteration where Za, E Ze and Za, E A. Given (G, 0, E) and Xx, the outcome variables are linear the alteration values. We have
Y, Ax, Bz CCe
(8)
where zf = (Zay..... ;aa T. A, B, and C are constant matrices of appropriate shapes and are uniquely determined by G. O and altered variables Z (Zu, 1/
Size-1 Alteration. We consider cases where agent can alter only one variable in each round, i.e., k 1. Suppose the altered variable in round is Zí Provided with a fixed SRM, along with fixed noise, Eq. (8) reduces to a line in YR| with di- rection B g|X|, Due to the convexity of the desired region S, if altering Z; can make Y E S. then the set of feasible al- teration values can be represented by an interval [u, 2] (the endpoints can be infin- ity). Finding candidate alterations on the training data is then equivalent to finding
Algorithm 1 Finding candidate alterations of size 1
Input: S., [(G ,, H Sen. {(G,, 0,, e,)};
1: C' +- 0
P Store candidate alterations
2: for 7, E Z do
3: int1 +- FIND 7,.T)
b Training
4: int2 + FIND Zs,
5: C+ CU ((Z,, intl O intt)]]
D Validation
6:
function FIND(S, Z.T)
& Find alteration values for Z Store valid intervals
7:
int
for (G, e, E S do
9:
[u, v] <- solution of M(Ax + BZ + Cε) <d A. B. C are determined by G. 0. int <- int [u, vj n A(Z))
10:
11:
elements that intersect at least n T inter- vals obtained from samples in S.,, which is easy to compute. Alg. | includes the ba- sic training and validation stages of finding candidate alterations. The overall time complexity is O(Z, log n). A more detailed algorithm and running time analysis given in Appendix B
12: return {z nr < #intervals int containing =}
Output: The found alterations
Size-k Alteration. By relating to the NP-hard maximum feasible subsystem problem 21 we prove Thm. 6 showing that finding single & that satisfies the constraint, which is much simpler
7

---

than finding all valid alterations, is difficult if P = NP. This result suggests that we should focus on approximate solutions rather than exact ones. We also give mixed integer linear programming approach in Appendix B
Theorem 6. Unless P = NP. finding a k-dimensional z E A(Z)) that satisfies Ei=1 [IM
B,25 + C,e,) < d) 2 n-t (if there is a valid solution) is not solvable with any algorithm of running time polynomial in k and n.
4.3 Mutual Information Maximization
The remaining task is to optimize the mutual information over the found candidate alteration set C. We factorize the objective function with two information entropy terms over Z, and Y;
I O Ze, Y, Dr, (x) H(e, Y, | x,, H(Z,, Y, O, Et)
(9)
Xr, &t). Due to the Eq. (9) can be estimated with samples from P(G, 0 D2) and Pl O,O,x,,
sampling involved in the estimation procedure, Eq. ( is expensive to evaluate. The continuous input space makes difficult find an optimal alteration value for a fixed alteration target Z Thus, we find z with Bayesian optimization [22], which seeks to optimize a black-box function g(z) with a small number of evaluations by iteratively querying function values at some data points. We run the optimization procedure for every alteration target in C and find the corresponding best alteration values. Finally, the alteration that gives maximum mutual information is selected as the recommended output. Details about the estimation procedure and Bayesian optimization are given in Appendix C
Given decision, it important to know how likely the decision can successfully avoid the undesired future. Though the candidate selection procedure already rules out potentially terrible alterations using Sty and Swat, a more refined measure preferable. Based on the scenario approach in robust control literature 23 24 we derive PtC-style bound on the posterior success probability in Thm. 7 The bound is easy compute as it only requires posterior samples. The practical implication of the bound is that it quantifies the uncertainty, or risk, associated with the alteration. thus can help make better decisions. Notably, the bound holds for any SRM with arbitrary additive noise, which could be helpful for future extensions with non-Gaussian noise and nonlinear SRMs.
Theorem 7. Given an observed evidence Xt, an alteration &, and desired set S = (y E RIY| My S d). let Seval = {(G;, (,, [i be n i.i.d. samples from P(G, 0 e Dz). Let {y') be generated from Rh(g) and Secot following the structural equations in Eq. Q Define n. _ ii y' HS.. Let p 1 no/n, _ F- (1 6/(2n); + n, if < otherwise 2 0, Do, n. + 1) if no > 0 otherwise 2 1, where (-;a, ((:a,3) 3) is the
and p 111FF116//00
inverse cumulative distribution function of the beta distribution with parameters a and B. For any d E (0, 1), with probubility at least 1 - 5, we have
max { p v1n(2/8)/2n) &P(Y.ESD, X1, RM(EE) S min {D.0+ vmn22/8/22n
4.4 Discussion
The proposed rehearsal learning framework is general and flexible, with any of the three steps ad- justable without interfering with the others. For scenarios more complicated than linear ones, one can replace methods in each step accordingly: The Bayesian update of SRMs can use any advanced Bayesian (structure) learning methods 25 26 27 28 as long as they allow sampling from the poste- rior. The mutual information maximization step can leverage any black-box optimization methods 12 [29]. For the most important and difficult candidate alteration finding step, which is difficult even for the linear case when allowing joint alterations, efficient heuristics lincarization tricks can be used. Given the great uncertainty of real- woaldworld problems, exactly solving the AUF problem is extremely difficult if not impossible, while with the rehearsal learning framework, provide practical and systematic approximate solution that tackles the problem with certain guarantees, which exhibits that developing more efficient approximate solutions is promising future direction.
For the SRM, there are some practical considerations. After a rehearsal operation, the change of the parental relations results in new sets of parameters. In the absence of further constraints, as is the case in this work, these new parameters may bear no direct resemblance to the previous ones. However, it is conceivable to impose specific assumptions on these parameters to achieve more
8

---

efficient modeling, For instance, one may assume the new parameters are connected with the original ones through operations like marginalizatton. In practical implementations, is also reasonable to limit the size of a clique and maintain the number of parameter sets to an acceptable level. Moreover, it is unlikely that we would need to or be able to alter every possible subset of clique, so one can reduce unnecessary computational burden by ignoring the parameters that would not be used.
5
Related Work
There have been some efforts to combine structural models with decision-making, with most of them focusing on causal structures [30]. Some work explores the causal bandit problem, where the causal structure underlying rewards and actions is considered [31
36). In different vein, Aglietti et al. [37 investigated a Bayesian optimization problem with a known causal DAG, and
32
33
34
35
Aglietti et al. [38 extended this work to dynamic setting. However, these studies typically assume that the true causal graph is known, a condition that is challenging to meet in woaldworld applications,
although causal discovery methods could help to some extent [39] 40 41 42
43
44
To remove
focused on the Markov equivalence class of the true causal graphs. However, even when causal relations are known, applying causal bandits or causal Bayesian optimization to AUF is not suitable because they often seek single universally optimal action. In contrast, optimal decisions in AUF can vary depending on the context X. Some research approaches decision problems from the perspective of causal structures and causal effect estimation. For example, Wang et al. [47] developed a method for estimating set of possible causal effects to aid decision-making. Additionally, there has been active research in estimating causal structures or effects in interactive environments [48 49 50
the assumption, de Kroon et al. 45 leveraged separating sets, while Lu et al.
46
52).
The aforementioned efforts yielded effective methods for certain decision-related problems, but all of them rely on causal modeling, which could be too luxurious and restrictive for decision problems [7]. On the other hand, correlation, which is the basis of most ML models, is insufficient for decision- making. Therefore,
turn the influence relation, which lies between correlation and causation and forms a basis of decisions [7] Building on the influence relation, we propose SRM, which is capable of modeling interrelated but not necessarily causally linked variables and dynamically evolving decision systems. Moreover, the proposed rehearsal learning framework demonstrates the feasibility of building macision upon influence and rehearsal.
Experiments
We evaluate the proposed approach two datasets. We mainly interested in if the proposed ap- proach can successfully avoid the undesired future with high probability, the exploration-exploitan trade-off, and the informativeness of the PAC-style guarantces. For each dataset, we alter one variable in each round and repeat experiments with 100 rounds 20 times. The graph prior is initialized with samples from the learnable graph equivalence class instead of learning from data well-established rehearsal graph learning methods are still in the process of development. The success probability is estimated with 1,000 samples from the true SRM. We compute the PAC bound with 1,000 samples from the posterior with 8 = 0.05. The observational dataset size is set to 10. We also compare with several reinforcement learning methods DDPG 53 PPO 54 SAC 55 and CATS [56].
Ride-Hailing Data. We abstract SRM from ride-hailing scenario. where a ride-hailing app needs to make decisions to promote user rating (RAT). We consider relevant variables including the weather condition, the number of users, traffic congestion (TRA), etc. The app alter two variables, the discount level (DIS) and the recommendation level (REC) of a specific route. There exist interrelated variables in the scenario: If REC of specific route is high, then TRA on that route will be high since more users will choose that route; and if there is a high TRA on that route, the REC should be low. The size of X,, Ze and Y, are 2, 4, and 1 respectively. The true structural equations are set according to domain knowledge. The feasible alteration values are [-2, 2] for DIS and REC. The range of RAT [0, 1], so we the desired region to S [0.8, 1] to avoid RAT below 0.8.
Bermuda Data.
We take an example from ecology, where environment variables in Bermuda are recorded (57) and the variable generation order is available (58). The size of X,, Z,, Y, are 3, 7, and 1 respectively. The true structural equations are obtained by performing linear regression on

---

Numbber
Probubility
Estimated information
PAC bounds 1=07
5m0.3
005-
Ride halling
61
[-0.7
2.0.5
06-
044
02-
Lowerbound bound
Upper
Tro: prolubiity
000
Bemmuda
0.-
02-
01-
D44-
0.
10C
Number of counds
Figure 4: Results on the Ride-hailing and the Bermuda data. The bands depict standard deviations.
normalized data. We assume that 5 variables are actionable 37 with a feasible alteration region [-1,1]. Y, represents the net coral ecosystem calcification (NEC). We want maintain high NEC.
So we set the desired region to S = |0.5, 2] which is above the 75th percentile of the dataset.
Table shows the average probabilities of suc- cessfully avoiding the undesired future of several RL methods and the proposed rehearsal learning method with t = 0.7. Our method achieves the goal of AUF with probability around 0.7, while the others fail to do so with merely 100 interac-
Dataset
DDPG PPO SAC CATS T 0.7
Ridc-hailing 0.173 0.154 0.177 0.104
0.714 Bermuda 0.230 0.190 0.205 0.215 0.679
Table 1: Avg. success probability.
tions with the environment, which further underscores the importance of considering structural information in the interaction-limited AUF problem. On the other hand, if we increase T, RI. methods can achieve satisfying performance, e.g., DDPG achieves 0.688 average success probability when = 10, 000 on the Bermuda data. For the ride-hailing data, 95.8% alterations recommended by the proposed method are to alter REC, which affects RAT through the interactions between REC and TRA and the direct link between TRA and REC: REC < TRA- - RAT. Note that REC cannot be identified as valid cause so causal modeling is not suitable for this problem.
Fig. shows the full results. Given T, the found alteration can satisfy the probability requirement in most cases. Exceptions are settings where т = 0.9. Alterations with such a high success probability rarely exist, so the method can fail. In our implementation. when the recommendation is not attainable, the constraint is dropped and the method will only optimize the mutual information. Therefore the corresponding number of success rounds, as well as the success probability. is low, but the mutual information is high. The third column shows trade-off between avoiding the undesired future and learning the SRM: smaller т is likely to give higher mutual information. An interesting phenomenon that the true success probability often fluctuates around т instead of achieving higher values. An explanation is that if an alteration has a high success probability, then the effect of the alteration is less uncertain, so less new information can be revealed and the method will instead choose others with lower success probabilities. Finally, the last column shows that the true probabilities are bounded by the PAC-style bound with a relatively small gap, so it can be informative for guiding real decisions.
7 Conclusion
Realizing that correlation is inadequate and that causation is not always suitable, we advocate relying on the influence relation for decision-making In this paper, we propose the first rehearsal learning framework that tackles the AUF (Avoiding Undesired Future) problem with influence modeling. The key to the proposed framework is SRM, which considers the interrelations of variables and the dynamic time-dependent nature of decision environments. By unifying rehearsals on SRMs and Bayesian inference, the framework recommends decisions that can persuasively avoid the undesired future. We also provide a PAC-style bound to quantify the associated risk of recommended decisions and further show the hardness of basic linear instance of the framework, revealing that future work should focus on developing approximate solutions rather than exact ones.
10

---

Acknowledgments
This research was supported by National Key R&D Program of China (2022200114800) and NSFC (61921006). The authors thank the reviewers for their valuable comments.
References
[1] Athanasios Voulodimos, Nikolaos Doulamis, Anastasios D. Doulamis, and Eftychios Protopa- padakis. Deep learning for computer vision: A brief review. Computational Intelligence and Neuroscience, pages 1-13, 2018.
[2] Hang Li. Deep learning for natural language processing: Advantages and challenges. National Science Review, 5(1):24-26, 09 2017.
[3] Zeynep Batmaz, Ali Yürekli, Alper Bilge, and Cihan Kaleli. A review on deep learning for recommender systems: Challenges and remedies. Artificial Intelligence Review, 52(1):1-37, 2019.
[4] Xiong-Hui Chen, Bowei He, Yang Yu, Qingyang Li, Zhiwei Tony Qin, Wenjie Shang. Jieping Ye, and Chen Ma. Sim2rec: A simulator- based rpcision-makingg approach to optimize real- world long-term user engagement in sequential recommender systems. In Proceedings of the Thirty-Nimth IEEE International Conference on Duta Engineering, pages 3389-3402, 2023.
[5] Konstantina Kourou, Themis P Exarchos, Konstantinos Exarchos, Michalis V Karamouzis, and Dimitrios I Fotiadis. Machine learning applications in cancer prognosis and prediction. Computational and Structural Biotechnology Journal, 13:8-17, 2015.
[6] Harsha Chamara Hewage and H. Niles Perera. Comparing statistical and machine learning methods for sales forecasting during the post-promotional period. In IEEE International Conference on Industrial Engineering and Engineering Management, pages 462-466, 2021.
[7] Zhi-Hua Zhou. Rehearsal: Learning from prediction decision. Frontiers of Computer Science, 16(4):1-3,2) 2022.
[8] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[9] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing Atari with deep reinforcement learning. CoRR, abs/ abs/1312.5602. 2013.
[10] Bahare Kiumarsi, Kyriakos G. Vamvoudakis, Hamidreza Modares, and Frank L. Lewis. Optimal and autonomous control using reinforcement learning: A survey. IEEE Transactions on Neural Networks and Learning Systems, 296))220422062 2018.
[11] Zhi-Hua Zhou. Rehearsal: Learning from prediction to decision. Keynote at the CCF Conference on AI, Urumqi, China, 2023.
[12] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, 2nd edition, 2009.
[13] David M. Chickering. Learning Bayesian networks is NP-complete. Learning from Data. Lecture Notes in Statistics, 112:121-130 1995.
[14] Xiong-Hui Chen, Junyin Ye, Hang Zhao, Yi-Chen Li, Haoran Shi, Yu-Yan Xu, Zhihao Ye, Si-Hang Yang, Anqi Huang, Kai Xu, Zongzhang Zhang, and Yang Yu. Imitator learning: Achieve out-of-the-box imitation ability in variable environments. CoRR, abs/2310.05712,, 2023.
[15] Michael E. Sobel. Causal Inference in the Social and Behavioral Sciences, pages 1-38. Springer, 1995.
[16] Kenneth J. Rothman and Sander Greenland. Causation and causal inference in epidemiology. American Journal of Public Health, 144-1)55144-1150, 2005.

---

[17] Adam Massmann, Pierre Gentine, and Jakob Runge. Causal inference for process understanding earth sciences. CoRR, abs/2105.00912, 2021.
[18] Nir Friedman, Moisés Goldszmidt, and Abraham J. Wyner. Data analysis with Bayesian networks: A bootstrap approach. CoRR, abs/1301 16695, 2013.
[19]
Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
[20] Michael E. Tipping. Sparse bayesian learning and the relevance vector machine. Journal of Machine Learning Research, 1:211 12211-246 1-44,, 2001.
[21] Edoardo Amaldi and Viggo Kann. The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science, 147(1):181-28)) 1995.
[22] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104 (1):148-175, 2016.
[23] Giuseppe C. Calafiore and Marco C. Campi. The scenario approach to robust control design. IEEE Transactions on Automatic Control, 51(5):742-7533 2006.
[24] Thom Badings, Alessandro Abate, Nils Jansen, David Parker, Hasan A. Poonawala, and Mariëlle Stoelinga. Sampling-basee based robust control of autonomous systems with non- Gaussian noise. Thirty-Sivir Sixth AAAI Conference on Artificial Intelligence, pages 9669 9678,, 2022.
[25] Christopher KI Williams and Carl Edward Rasmussen. Gaussian Processes for Machine Learning. MIT press Cambridge, 2006.
[26] Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. Advances in Neural Information Processing Systems, pages 2370-2378. 2016.
[27] Raj Agrawal, Chandler Squires, Karren D. Yang, Karthikeyan Shanmugam, and Caroline Uhler. ABCD-strategy: Budgeted experimental design for targeted causal structure discovery. In Proceedings of the Swenny-Second International Conference on Artificial Intelligence and Statistics, pages 3400-3409, 2019.
[28] Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf, and Andreas Krause. DiBS: Differentiable Bayesian structure learning. In Advances in Neural Information Processing Systems, pages 24111-24123, 2021.
[29] Sourabh Katoch, Sumit Singh Chauhan, and Vijay Kumar. review on genetic algorithm: Past, present, and future. Multimedia Tools and Applications, 80(5):801188126 2021.
[30] Zhe Zhu, Xiong-Hui Chen, Hong-Long Tian, Kun Zhang, and Yang Yu. Offline reinforcement learning with causal structured world models. CORR, abs/2206.01474, 2022.
[31] Finnian Lattimore, Tor Lattimore, and Mark D. Reid. Causal bandits: Learning good inter- ventions via causal inference. In Advances in Neural Information Processing Systems, pages 1181-1189, 2016.
[32] Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, and Ken-ichi Kawarabayashi. Causal bandits with propagating inference. In Proceedings of the Thirty-Fifth International Conference on Machine Learning, pages 5508-5516, 2018
[33] Sanghack Lee and Elias Bareinboim. Structural causal bandits: Where to intervene? In Advances in Neural Information Processing Systems, pages 2573-2583, 2018.
[34] Sanghack Lee and Elias Bareinboim. Structural causal bandits with non-manipulable variables. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, pages 4164 4172,
2019.
[35] Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit problems with causal background knowledge, Proceedings of the Thirty-Sixth Conference on Uncertainty in Artificial Intelligence, pages 141-150 2020.
12

---

[36] Neil Dhir. Chronological causal bandits. CoRR, abs/2112.01819, 2021.
[37] Virginia Aglietti, Xiaoyu Lu, Andrei Paleyes, and Javier González. Causal Bayesian optimiza- tion. Proceedings of the Twenty-Thine Third International Conference on Artificial Intelligence and Statistics, pages 3155-3164, 2020.
[38] Virginia Aglietti, Neil Dhir, Javier González, and Theodoros Damoulas. Dynamic causal Bayesian optimization. In Advances in Neural Information Processing Systems, pages 10549- 10560, 2021.
[39] Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search. MIT press, 2nd edition, 2000.
[40] David M. Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507-554, 2002.
[41] Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non- Gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7: 2003-2030) 2006.
[42] Patrik O. Hoyer, Dominik Janzing, Joris M. Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In Advances Neural Information Processing Systems, pages 689-696, 696, 2008
[43] Kun Zhang and Aapo Hyvärinen. On the identifiability of the post-nonlinear causal model. In Proceedings of the Swenty-Fifih Conference on Uncertainty in Artificial Intelligence, pages 647-655, 2009.
[44] Tian Qin, Tuo Wang, and Zhi-Hua Zhou. Learning causal structure on mixed data with tree-structured functional models. In Proceedings of the Twenty-Third SIAM International Conference Data Mining, pages 613 621, 2023.
[45] Arnoud A. W. M. de Kroon, Danielle Belgrave, and Joris M. Mooij. Causal discovery for causal bandits utilizing separating sets. CoRR, abs/2009.079) 2020.
[46] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Causal bandits with unknown graph structure. In Advances Neural Information Processing Systems, pages 24817-24828, 2021.
[47] Tian-Zuo Wang, Tian Qin, and Zhi-Hua Zhou. Estimating possible causal effects with latent variables via adjustment. In Proceedings of the Fortieth International Conference on Machine Learning, pages 36308-36333 2023.
[48] Tian-Zuo Wang. Xi-Zhu Wu, Sheng- Huang, and Zhi-Hua Zhou. Cfst-efeet identifying causal effects when only response variable is observable. In Proceedings of the Thirty-Seventh International Conference on Machine Learning, pages 10060-10069, 2020.
[49] Tian-Zuo Wang and Zhi-Hua Zhou Actively identifying causal effects with latent variables given only response variable observable. In Advances Neural Information Processing Systems, pages 15007-15018, 2021.
[50] Tian Qin, Tian-Zuo Wang, and Zhi-Hua Zhou. Budgeted heterogencous treatment effect estimation. In Proceedings of the Thirty-Eight International Conference on Machine Learning, pages 8693-8702, 2021.
[51] Tian-Zuo Wang. Tian Qin, and Zhi-Hua Zhou. Sound and complete causal identification with latent variables given local background knowledge. In Advances in Neural Information Processing Systems, pages 00325-10335 2022.
[52] Tian-Zuo Wang, Tian Qin, and Zhi-Hua Zhou. Sound and complete causal identification with latent variables given local background knowledge. Artificial Intelligence, 322: 103964, 2023.
[53] 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 Fourth International Conference on Learning Representations, 2016.
13

---

[54] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, htss/1707.06347 2017.
[55] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critie: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the Thirty-Fifth International Conference on Machine Learning, pages 1856-1865, 2018.
[56] Maryam Majzoubi, Chicheng Zhang, Rajan Chari, Akshay Krishnamurthy, John Langford, and Aleksandrs Slivkins. Efficient contextual bandits with continuous actions. In Advances in Neural Information Processing Systems, pages 349-360, 2020.
[57] Travis A. Courtney, Mario Lebrato, Nicholas R. Bates, Andrew Collins, Samantha J. de Putron, Rebecca Garley, Rod Johnson, Juan-Carlos Molinero, Timothy Noyes, Christopher L. Sabine, and Andreas J. Andersson. Environmental controls on modern scleractinian coral and reef-scale calcification. Science Advances, ((1))ee1701356 2017.
[58] Andreas Andersson and Nicholas Bates. In situ measurements used for coral and reef-scale calcification structural equation modeling including environmental and chemical measure- ments, and coral calcification rates in Bermuda from 2010 to 2012 (BEACON project), 2018.
[59] Kumar Sricharan, Dennis L. Wei, and Alfred O. Hero III. Ensemble estimators for multivariate entropy estimation. IEEE Transactions on Information Theory, 59(7):4374-438 2013.
[60] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the Twenty-Seventh International Conference on Machine Learning, pages 1015-1022, 2010.
[61] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[62] Licio Romao, Kostas Margellos, and Antonis Papachristodoulou. Tight generalization guaran- tees for the sampling and discarding approach to scenario optimization. In Proceedings the Fifty-ninth IEEE Conference on Decision and Control, pages 2228-2228222222222222222222----- 2223,223, 2020.
14

---

A Rehearsal Graphs: Characterization and Learning
In this section, we present full motivations, basic properties, and preliminary learning strategies for rehearsal graphs.
The ability to describe and identify causal relations is at the heart of both human and artificial intelligence. The work of Pearl [2] on causality lays the foundation for accurately describing causal relations and making sound inference. Despite its elegance and expressiveness in abstracting causal- ity from human cognition, one may encounter difficulties when applying Pearl's causal framework to real-world observations. We identify three kinds of misspecifications that could make causal modeling fail: a) model misspecification b) data-collection misspecification c) adversary misspecification.
Model misspecification means that the variables used in the causal modeling process are inaccurate so there are indeterminant causal relations among the variables. For example, demand (D) and price (P) are two variables that are causally related. But there is not a determinant causal direction between D and P since intervening on causes to change but meanwhile intervening on P causes D to change. A workaround is modeling with finer granularity by adding a time index to D and P. Then we have D, causes P-+1 and Pt causes D1+1-
Data-collection misspecification means that the data collected are not perfectly aligned with the specified variable. For example, we may have variables D1, D2, P1, P2 in the causal model that denote two measures D and P at different time. But the data collected may not rigorously follow the order since there can be time delays and mismatches of the modeling time intervals and real ones. This misspecification results in a misalignment between the model and data, hence no sound causal conclusions can be drawn from the data.
Adversary misspecification refers to ignoring the existence of adversaries in causal modeling. For example, let P and Q denote the prices of product in two stores. If P is decreased then Q will also be decreased, otherwise, the second store will lose some consumers. From a causal view, it seems that P causes Q. But obviously, Q also causes P by symmetry. So we have bi-directional causal relation, which is cannot be described in causal modeling. The reason for this phenomenon that each store is adversary that reacts interventions from other agents.
The preceding three misspecifications are not necessarily disjoint in real problems and are hard to identify in advance. The consequence is that one cannot identify perfect causal knowledge even if with an infinite amount of data since the modeling and the data do not exhibit consistent determinant causal relations. In order to model both the non-determinant and determinant causal relations in data, we introduce a new probabilistic graphical model: rehearsal graphs.
A.1 Rehearsal Graphs Probabilistic Graphical Model
Definition 8 (Mixed graph). Let G = (V, E) be graph, where V denotes the vertices and E the edges. G is mixed graph if for any distinct vertices u, V, there is at most edge connecting them, and the edge can be either directional or bi-directional, i.e., u + + or u + v. Definition 9 (Bi-directional clique). A bi-directional clique C' (Ve, ES) of mixed graph G (V, E) is a complete induced subgraph such that any edge e E E bi-directional. A single vertex also constituents valid bi-directional clique. C is maximal if adding any other vertex does not induce bi-directional clique.
Definition 10 (Rehearsal graph). Let G = (V, V) be a mixed graph. Let {Ci) denote all maximal bi-directional cliques of G, where C, (V;, E.). G is rehearsal graph if and only if:
Vg n Vÿ- = 9 for any i *
2. Vi E [1] u V VG, if there is any edge pointing from VS, then Vo E Vf, + 8. 3. The directional edges permit topological ordering for {C+))_
Definition 11 (Factorization). Let G = (V, E) be a rehearsal graph and C₁ (V:, E E [k] be maximal bi-directional cliques of G. We say that a joint probability P over factorizes according to G if P can be expressed as product
P(V)
II P(V. PA.), (=1
(10)
where PA, {u] Bu E V in
15

---

A.2 c-Separation
As probabilistic graphical model, like Bayesian networks or Markov networks, rehearsal graphs also have graphical characterization of independence relations. Mimicking the d-separation for Bayesian networks, we present c-separation for rehearsal graphs. Here the "c" means "cliques".
Definition 12 (e-separation), A path p in rehearsal graph G is said to be c-separated (or blocked) by a set of vertices if and only if
1. p contains a chain ma + 12 + my j such that the bi-directionally connected vertices {m: C Z, or
my + j or a fork 4- mi + m2
2. p contains an inverted fork (or collider) i - m1 ++ m2 ++ ... ++ my + j such that no vertices in fm are in Z and such that no descendants of mm))/ in Z.
set Z is said to e-separate from Y if and only if Z blocks every path from a vertex in X to a vertex in Z. We write X GLg Z when Z c-separates X from Y in G.
Lemma 13. Let G = (V, B) be rehearsal graph, y V be two distinct vertices, and Z a set of vertices. Let C(v) denote the vertices of the maximal bi-directional clique to which v belongs. If LL Z, then (xx) lL C(y) Z.
Proof. We prove this by contradiction. Assume that C(x) LL. C(y) does not hold given HG Z. meaning that there exists path unblocked by Z between some C(x) and some V E Cly)- Then there is an unblocked path x ++ p ++ y between x and y, which is contradiction since Z is supposed to block every path between and y-
Lemma 14. Let = E) be a rehearsal graph, Ca, C2 C V be set of vertices of two distinct maximal bi-directional cliques, and a set of vertices. If C. ll a Cb Z, then for all probability functions P that factorizes according to G, Ca 11 Cb Z.
Proof. We construct a DAG G EV from G with one-to-one mapping f: every maximal cliques C, of G is represented with a vertex 0; E G. 0g = .,.....,0 vf (:ll, and the edge directions 6ag (here omit the edge directions) in G, where {as); is index set, there is counterpart g in the original G that reads wi 22
between O,s are kept. For any path p Dan Vaz
vai [Cal Vaz uaz
|Cogl
[C,,
+ Vag
vi va
+ Vai
where v is the j-th vertex in C... For any 2 h(Z) = f8 V ( C Z}. From the definition of c-separation for rehearsal graphs and d-separation for Bayesian networks, we see that if q is c-separated by in G, then is d-separated by M(Z) in G. Therefore, if Ca G C. Z, then every path hetween v. and ti is d-separated by h(2). Due to the Markov property of Bayesian networks, for all P that factorizes according to G (which also factorizes according to G by definition), we have U. .l P h(Z), i.e. C. 1p Cb (h()). Since (h(2) C Z, we have C. 11p C, 2.
C V. we map it to a set of vertices G with
Theorem 15. Let G = (V, E) be a rehearsal graph. For all probability functions P that factorizes according to G and any three disjoint subsets of vertices X, X,Y.Z V. if X ll. Y Z, then X K.p Y Z.
Proof.
X le Y
Ll. y 2
(11)
Vz X, Le C(y) 22
(12)
Vr X.y 1Lp C(y) Iz
(13)
Vr X, Y,v 11 1lyl
(14)
X X Y Z.
(15)
16

---

F
A
A
G
E
B
G
B
E
C
D
C
D
C
D
(a) rehearsal graph G.
(b) Ci-
(c) G2-
A
A
G
B
G
B
E
C
D
C
D
C
D
(d) Gzz-
(e) Ga
(1) G
B
G
D
gg) Go
Figure 5: An example rehearsal graph and its Bayesian network counterparts that encode the same conditional independence relations. We use plate notation to simplify the edges. For example, in (a), vertex A having an edge pointing the rectangle containing three vertices, implies that A-E, A-F, and A-G..
Theorem 16. Let (V, V,B. E) be a rehearsal graph. Let (V, be any DAG that have identical skeleton with G (see Fig. for an example). If all directional edges in G appear in G', then for any disjoint set of vertices X. and Z, we have X 11 Y 7 if and only if X L. Y Z, where G means c-separation for rehearsal graphs and e d-separation for DAGs.
Proof. We first prove X Le Y Z + X Y 1
Every path p in G has unique counterpart in G' that shares the same vertex sequence. p and p/ only differ in some edges: a bi-directional edge u + in is a directed one u - e or u + v in G'. Obviously, the mapping between and p' is one-to-one. We only need show that for any path p/ in G². its counterpart in is c-separated by a set Z, then p' d-separated in G.
We prove it by contradiction. Assume that p' is not d-separated by Z, then according to the definition of d-separation, we have that (a) for every chain - m + j and every fork < m + j in p'. & Z, and that (b) for every inverted fork i chain i + mi ++ m2 ++ + my + j and every fork 4- mi + m2 + ++ my + j in p. we have {m=)_1 Z Z since otherwise either
f j in p'. ([m} U des(m)) n Z * 0. For every
mi + p and () () Z + 9 since otherwise there exists inverted fork *, E [7] such that (fm,) U (ms((,)) n = 0. which violates requirement (b). Combining the above results, have that p
mi p' and my E Z,
my E Z, which violate requirement (a). For every inverted fork i - mi < m2 ..... ... + my + in p. (fm,),_. U (de((fm))) (/m))))))))
m. <
c-separated by Z, which is a contradiction. Therefore, is d-separated by Z, which concludes that X ll Y Z + Gr Y Z.
We next prove X HL Y Z X 1L. Y Z.
17

---

Again we prove by contradiction. Assume that there exists path from I E X in that is not c-separated by Z. Let p be x - mi <> mf ++ + mi m2 + m2 + ... < ++ m y (we omit the direction of directional edges). We
in
m²
m + m construct a path q from x to y by picking one vertex from each bi- di-dreccionnlly connected subpath m. + m² + ...... ++ m in order such that q contains only directional edges, so q is also a path in G". For each dirirecctinlll connected subpath m. ++ m ++ ... + m. in p. if it is part of a m
chain + m. m ++ the definition of c-separation, {m \ Z + 0, we randomly select a vertex U; E {m;])= \ to join q. If the bi-directionally connected subpath a part of an inverted fork * - m + m + ++ mi < *, then by the definition of c-separation, either some mi E Z or some descendant of {m )/ is in Z. In the former case, we select V; -m² to join q. and in the latter, we randomly select any v, E (m]) By construction, q = x - 01 -... ft- is a path from X to Y in G' and not d-separated, which is a contradiction. Therefore, any path p from X to Y in G is c-separated by Z, which concludes X He Y Z = I Y Z.
fork t- m! ++ m + + m
then by
Theorem 17. Let G (V, E) be a rehearsal graph. For any three disjoint subsets of vertices X. Y, Z C V, if 1Pp Y for all probability functions P that factorizes according to G, then X LG Z.
Proof. Let G² (V, VV,EE E') be any DAG that has identical skeleton with G and has all directional edges in G. Let Vi {v; //= denote the set of vertices in maximal bi-directional clique in G and PA, the parent of V,, Then V, is also a clique in G'. Without loss of generality, assume the topological ordering among V; 01 < 1/2 < ................................ < ut- By the chain rule, we have P(V: -Tk P(nk Pk-1: 2k- where the LHS is the conditional probability defined in the factorization of G and the RHS is the factorization defined by G'. So if P is probability function that factorizes according to G. then p also factorizes according to G", and vice versa. Let P(-) denote the probability family
that factorizes according to., :. We have P(G)) = P(G').
P(G)=P(G))
YP P X
z
VPEP(G'), X 1 Y
(16)
completeness di separatiion
X X Y
(17)
Thm. 16
X X Y Z.
(18)
A.3 Structure Learning
If we drop the bi-directional edges rehearsal graph, it becomes valid Bayesian network, which means that Bayesian networks are special cases of rehearsal graphs. So learning rehearsal graphs can only be harder than learning Bayesian networks. In this subsection, we present a preliminary learning method. More efficient learning methods are left for further research.
Thm. 16 shows that a rehearsal graph has several Bayesian network counterparts that have the same skeleton and encode the same conditional independence relations. So by learning Bayesian network or a Markov equivalence class of Bayesian networks from data, we can determine the skeleton of the rehearsal graph. Then we can get a rehearsal graph or a set of rehearsal graphs that cannot be distinguished from observational data by adding bi-directional edges the edges whose directions are not determined. Assuming that the observational distribution factorizes according to rehearsal graph and that all conditional independence relations of the distribution are encoded by the rehearsal graph, Algorithm lists all valid rehearsal graphs. The first three steps of Algorithm aare are simply the IC algorithm for Bayesian network learning [12.. Then we list all Bayesian networks and map them back to rehearsal graphs by replacing directional edges with bi-directional ones.
18

---

Algorithm 2 Learning rehearsal graphs from observational data
Input:
Observational distribution P(V).
1: For each pair of variables and b in V, search for set Sab such that a II. b Sab holds.
Construct an undirected graph G such that vertices and are connected with an edge if and only no set Sab can be found.
2: For each pair of nonadjacent variables a and b with common neighbor c, check if E Sab. It is, then continue. If is not, then add arrowheads pointing at c, i.e., a + c b.
3: In the partially directed graph that results, orient as many of the undirected edges possible subject to two conditions:
ii Any alternative orientation would yield new u-structure;
Any alternative orientation would yield directed cycle.
4: List all Markov equivalent directed graphs from the partially directed graph. Denote the set of Markov equivalent graphs with 91-
5: For each listed graph in 91. build set of mixed graphs 9 by enumerating all possible combinations cliques and replace the directional edges therein with bi-directional edges.
6: Check if the graphs in each Go are valid rehearsal graphs. If they are not, remove them from corresponding G%.
Output: Markov equivalent rehearsal graphs Gi U (Ugeg, 92).
B Candidate Alteration Selection
B.1
Size-1 Alteration
Algorithm in the main text shows the main steps of finding candidate alterations, where details on finding alteration values that satisfy the performance requirement are omitted. Here we give more details in Algorithm The main idea is to sort the found intervals in increasing order, then keep those that appear more than n I times. Sorting the array Line 17 on average costs On log n) time if using quicksort. Other operations cost (n) time. Thus, the overall average running time of Algorithm 3 ([zz)) n log n).
B.2 Size-k Alteration
We propose to build finite candidate set by solving a mixed-integed linear programming problem:
Σ e
max eE(0,1)" 2
s.t. M(A,++B,5 + C,e.) - S (1-e;)as i E [n'].
where e; is binary decision variable that equals 1 if the i-th incquality is satisfied and 0 otherwise, and a is a constant vector that upper bounds the left-hand side. If the found solution satisfies -T, corresponding z will be joined in the candidate set. The above programming is run for every combination of at most i alteration targets multiple times to obtain multiple alterations. The hard constraints satisfied by previous programs for common Z are randomly dropped in following iterations to encourage diverse solutions, thus the n' I n constraints instead n.
E, e;
C Mutual Information Maximization
Here detail the estimation of the mutual information objective in Eq. 5 We have
(G, θ Zi, Y, D2, x,, & = H(Z,, Y, De, &t) - H(Z, Y, G, D.,
In order estimate the mutual information,
only need estimate H(Z,, Y, Dr, x4, E and
HZ, Y, G, D,, estimation method ENTROPYESTIMATE that estimates information entropy with samples is used as black-box method since various methods are available, e.g., Sricharan et al. [59].
xx, &. We give a detailed estimation procedure in Algorithm 4 The entropy
Let g - (G, θ Z, Y, D,, X & denote the target optimization function to be used Bayesian optimization (22]. A Gaussian process is used to attain the posterior of g. Denote the posterior
19

---

Algorithm Find candidate single alterations
Input: S {(G,, 0₁ { Seat {(G,. 0,,
C
Store candidate alterations
2: for Zi E Z do
3: int1 <- FIND Str: 7i.7)
Training
4: int2 <- FIND vat: T)
5: C+ CU [1Z,, intl n int2)]
Validation
6: function FIND(S, T.
> Find alteration values Store valid intervals
7: int
8: for e, E do
9: [u, + solution of M(Ax + Bz + Cε) <d D A, B, C are determined by G, 0, Z int int {u, u) [(2)]
11: return FLLTERINTERVALSSint,, [TT]
12: function FILTERINTERVALS(Z, k)
Find elements that appear more than & times in I
arr +
14:
for [u, E I do
arr +- arr {(u, 0)} 16: arr f- arr 1[}
0 or I indicates the value is taken from the left the right
endpoints of an interval
17: arr + sorted(arr)
Sorted in increasing order with the first element as the key
ent
19: for < < arr do
if [ then cnt - cnt +1
If the value is left endpoint
21:
22:
else
23:
cnt < cnt arr[i][1] < cnt
24:
Record the number of intervals that intersect at arr [
25:
rtn f- (
26:
left <- NULL, right + NULL
27:
for 0 < |arr| do
Scan the array and record valid intervals
28:
right t arr [0 if [arr[i][]] then
29:
30:
left is NULL then left arr[i][()
31:
32:
else
33:
if left is not NULL then rtn - rtn U right)) left NULL
34:
35:
36:
return rtn
Output:
The found alterations C
20

---

mean and variance at an unseen 21+1 by My (Z(+1) and (z)-1) respectively. Given queried points {z! :...,, ) we upper confidence bound [60] as querying criterion select the next point:
Mg (g(2(+) + 7. 7g.0gg2"" (2(
arg max z/+ EC((E)
where y is constant and C(Z is the feasible region of Z defined by C. We run this optimization process for every alteration target in C find the corresponding best alteration values. Finally, the alteration, including both target variables and values, that has maximum mutual information is selected as the recommended output.
Algorithm 4 Mutual information estimation
Input: The posterior estimate p(G, Dz). the candidate graph the observed x, the alteration E. the number of samples for estimating an entropy term n, the number of samples for structural parameters n'.
1: srms f-D 0)
2: for G G do
3: for i [[n. Di do
4:
Sample O from p(0 G. D2) srms srms U ( 0:) 6: samples -
5:
7: for (G E srms do
8: Sample z and y from p(z,y y G. x,
9: samples + samples U {z,
10: H1 ENTRROPYESTIAATT
H2 +
12: for G G do
entropies 00 0
14: for i [n'] do
Sample 0 from p(0 G, D.)
16:
samples < 0
17:
for E [n] do
18:
Sample and from p(z, G, x,) samples + samples y))
20:
entropies + entropies U (ENTROPYESTTNAATE(SSMMpl.. cond_ento cond_entropy- average of entropies
21:
il fl2 + cond_entropy p(G D.)
23: + H1 H₂
Output: The mutual information estimate î
D Proofs
In this section, we provide proof for claims in the main text.
Proposition 4. For any (G1, 01) and (G2, 02) X, U Z₁ U Y,,, if they differ only in describing the generation of Xx, then any Xt = X, and alterations on Zy we have
IP Py: xx, : IP (ye xt, Rh(g)) G2, 0z)
Proof. We have
P(y x, Rh(E);
Σ P(z x, Rb())))) G., 0,)P(y 2, Rh(E); 0.), i= 1,2.
Since (G1, 0,) and (G2, 02) only differ parameters controlling P(x), we have
P(z x, Rh(E); 01) P(z x, Rh(():) G2 02),
21

---

and
P(y 2, x, RM()); 01) = P(y 2, x, Rh(E); G2, 02).
Combining the above equations gives
Py x, Rh(E): Gi, = Py x, ; 02).
Proposition 5. Let & {(Zu; =am))== be valid alteration where Zea Zy and Ra; E A(z,,). Given (G, 0 E) and X1, the outcome variables are linear in the alteration values. We have
Y, = Ax; B + Ce,
(8)
where v = (Zay).... Zay,. ) A, B, and are constant matrices of appropriate shapes and are uniquely determined by G, and altered variables z (Ze, Ji=1
Proof. The proposition is immediate by noting that if the parent set of variables can be described
by
PA A'x + B'z B'z +CE,
then
V -e
8 B'r + C'
can be described in similar linear form.
Theorem 6. Unless P = NP, finding a k-dimensional of E A(Z)) that satisfies Ex=1 I(M(A,
B + C,e,) S d) 2 n (if there a valid solution) is not solvable with any algorithm of running time polynomial in k and n.
Proof. We prove this by contradiction. Assume that the problem is solvable with subroutine f that runs in polynomial time. Then, given any infeasible linear system E [Ax & b}, we can find a feasible subsystem containing many inequalities possible by finding maximized that gives valid solution for the problem of finding a T that satisfies at least n T inequalities. And the process of finding maximized 7 can be finished by running binary search on and calling which will be called at most O(log n) times. Thus the overall running time will still be polynomial. However, finding a maximum feasible subsystem is known to be NP-hard (2T), which cannot be solved within polynomial time if P # NP. Therefore we have contradiction and conclude that the problem does not admit& a polynomial time algorithm.
Theorem 7. Given an observed evidence X an alteration &. and desired set S = (y E RIYI| My S d}, let Seval = {GG, E,) be n i.i.d. samples from PGG, 0, Dz). Let Vr be generated from Rh(E) and Seval following the structural equations in Eq. ① Define n. - {i no/n, g
y' & S. Let p
(1 - 6/(2n); no + 1, -nn) no) if < n otherwise & O, and p 2 1- 1 (- no, n - + 1) if n., > 0 otherwise p 1, where (:;a,; a., 3) is the inverse cumulative distribution function of the beta distribution with parameters a and B. For any 5 E (0, 1), with probability at least 1 - 5, we have
max p. v [m(2/6)/2m) < P (IIYYESD...... Rh(E)) < min (p.0 + 1m(2/8)/22
Proof. The proof is mainly based on the scenario approach 23 and adapted from Badings et al. (24]
The desired region for Y is given by S {y E RIY| by
My d). We define scaled version of S
R(A) = fx E R My & Xd + (1 - 3)
(19)
where h IR is a Chebyshev center of S [61). We have R(1) = S and R(1)) R(A2) for any
0 S λ1 < Ag. Using Prop. 5. we express each y' with
y' = A B + +CE,
(20)
22

---

We use the scenario approach to estimate the probability of the happening of undesired Y with the following convex scenario optimization problem with discarded samples:
min A
À
(21)
s.t. y' E R(2) Vi (1...., Q.Q
which has scalar decision variable A. We denote the optimal solution of the above optimization program with lio Q a subset of samples whose constraints have been discarded according to
the following rule [24] Lem. 1]: The sample removal set Q S [l....,n} is obtained by iteratively removing the active constraints from (2T). Thus, given N samples and any two removal sets with cardinalities |Qzl < 1Q2). it holds that Q1 C Q2. Moreover, any discarded sample i E Q violates
the solution X to Eq. 21 i.e. y" & R3 (aa)) with probability one. When discarding |Q| = no samples, it holds that (()))) C S. When discarding [Q] = n, - samples (no > 0), 1() C S.
We further assume that given sample (G,, 0,, Ea) from P(G, 0, D:), the probability that the generated y' is on the boundary of any polytope R(A) for any À 2 0 is zero.
Based on the results of Romao et al. 62 Thm. 5] and Badings et al. 124 Thm. 1J, we have
P { y & R() {c = Fle; |Ql + 1, - IQ)..
(22)
where F(;;0,,3) is the cumulative distribution function of the beta distribution with parameters and B. [Q] < n. Equivalently, we have
PP P(P y & B(Mia)) > cf = F(e: 1Q1 + 1, 1Q).
(23)
Solving 1 - F(e: [2| + 1 IQ1)
2n we have
5
5
c= F- 2n
:Q1 + 1,,,,n110 IQ))
(24)
For notational convenience, let Fi(-) F(+; + 1.)- We have
P { p y & R(Xie)))
6
>F (1
2n ]
(25)
2n
Using Boole's inequality, we know that
8
R (()))
8
8
P Ply& E R(A)) F
Σ P
(1
2n
2n
]
2
(26)
Therefore, we have
P py & ((A)) FF
-)
2 1 2
(27)
2n
After observing y's at hand, we replace Q by na- Since R(X 5
C and
1-0 P & R()))) S
FT (1 2n implies P (y & R(Mi.) < F=11(1 ) we have
P P(y - 8. ) 2n) 2 P
8 ]
6
P(y $ R(xi)) S F1
2n
2 1
(28)
2'
which further gives
p B p(y+
8
(1
- 2 1 -
(29)
2n
2'
When n. = n, P Pyy& E > 0 trivially holds. Thus, p S P (Y, S Dr, x1, Rh({)) holds with
probability at least 1 5 For the other half of the lower bound, we apply Hoeffding's 's inequality on bi-
2.
nary variables D, A T(y S). Note that DL_ D. = n. and E(D,) = P (Y, E S D,, x,, Rh())) we have
P the n PYY ES| D., RM(E)) >
n ln
2
8
(30)
2
2
23

---

that is.
In(2/5)
P P EI X,, Rb(EE) p
(31)
2n
Combining
and (1). we have with probability at least
2
In (2/0))
max D: p
<P Dr, Xi, Rh(E)).
(32)
2n
For the upper bound, adopt similar approach. From Eq. 22 by noting that P (vy $ R(Xia))
P (y R(((a))) 1, we get
p Pfp(y R(Aia))) 2 1 e- e) (e).
(33)
Substituting (e) with In we have
P pfp(y ((Xie)))))) 21 12)
(34)
2n
2n
Again via Boole's inequality,
P
P (y E R(A))) 51 F.
2
(35)
2n
2
When n, > 0, since R(}; -1) J and ni P E R(A;)) 1 F.
implies P(y E
n
2n
R(M -1)) < F-1 no-1 ( (2n) we have
P Py E 51 F
2 P P ((X 51- no-1
8
>
1
6
2n
2n
2
(36)
When n, = 0, Ply E) S trivially holds. Thus,
PYY S Dr, x,, Rh(E))
(37)
holds with probability least Eq. 30
8 Applying Hoeffding's s inequality from the other direction of
we get
In (2(2/)
PX.EESS D,, RM(()) S D
(38)
2n
Combining the above results gives the upper bound that holds with probability at least
8.
2"
ln(2/6)
PP P(Y E Dr, Rh(E)) & min p.p +
(39)
2n
Combining the lower bound (32) and the upper bound 39 gives the overall bound.
E Data Details
E.1 Ride-Hailing Data
We give details about the Ride-Hailing data in this section. The variables included in the generation process are
weather: weather condition;
#user: number of users in the neighborhood;
24

---

recommend: recommendation level of the iide-hailing app for specific route;
congestion: traffic congestion on the route;
time: time spent for the ride;
discount: discount provided by the app;
rating: user rating for the ride.
The rehearsal graph for the variables is given in Fig. The presumed actionable variables that be altered by the app are "recommend" and 'discount'.
recommend
weather
congestion
rating
#user
time
discount
X
Y
Figure 6: The rehearsal graph for ride-hailing data.
E.2
Bermuda Data
We give details about the Bermuda data this section. The Bermuda data involves set of environ- The variables included in the generation process are
mental variables [57 58 37
Chla: sea surface chlorophyll a;
Sal: sea surface salinity;
TA: seawater total alkalinity;
DIC: seawater dissolved inorganic carbon;
CO2: seawater Pco.;
Temp: bottom temperature;
NEC: net ecosystem calcification;
Light: bottom light levels;
Nut: PC1 of N H4, NiO, + NiO3, SiOA;
25

---

pHsw: seawater pH
Qa seawater saturation with respect to aragonite.
The rehearsal graph for the variables is given in Fig. The presumed actionable variables that be
altered are: DIC, TA, ΩA. Chla, and Nut.
Light
DIC
Chla
Nut
Temp
NEC
TA
pHsw
Sal
QA
CO2
X
Z
Y
Figure 7: The rehearsal graph for Bermuda data.
26


Reviews:
[{"review_id": "XDYWIuv1AW", "reviewer": "Reviewer_LZtj", "summary": "The paper argues that in decision-making, correlation is usually not enough but causation can be excessive. It introduces the idea of “rehearsation” which is a compromise between the two. Specifically, the paper proposes a novel rehearsal learning framework which models the interactions between interrelated (but not necessarily casually linked) variables in a dynamical system called structural rehearsal models (SRM). This frameowrk is applied to the problem of Avoiding Undesirable Future. A Bayesian inference framework is adopted to learn the graph posterior of the SRM. Mutual information maximisation is used as a criterion to select the alterations (similar notion to intervention in the causal setting) from a candidate set. Finally, a PAC bound is derived to quantify the decision risk in this framework.", "questions": "* How does the algorithm scale with the number of variables in the graph?\n* Can the rehearsation formulation be used for other decision making problems than AUF?", "limitations": "Please see weaknesses section", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* The paper introduces the new paradigm of “rehearsation” to decision making problems. To the best of my knowledge, this is a novel contribution. \n* The PAC bound on the posterior is useful analysis and also practical in terms of quantifying uncertainty.\n* Considering the linear case is a useful first step in building this framework.", "weaknesses": "* The main issue for me is the lack of comparison to similar methods in the causal inference literature, e.g. Causal Bandits/BO. The rehearsation framework is presented as a more sound framework for tacking AUF, but causal method can still be used as a practical for this problem even if they are philosophically not the principled methods to use. I would have liked to see a comparison against at least one prominent method in this area such as Causal BO.\n\n* Similarly to my point above, I would have liked to see a bit more discussion on the strengths and limitations of this work compared to other methods that the authors mention such as Reinforcement learning and Causal Bandits. This could be on a practical level rather than a theoretical one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments! Below we address your questions in a point-by-point fashion.\n\n> W1. Regarding comparison to methods in causal inference literature, e.g. Causal Bandits/BO.\n\nThanks for your suggestion! We need to clarify that causal bandits (CB) and causal Bayesian optimization (CBO) methods are not applicable to AUF for two reasons.\n\nFirstly, CBO and some CB methods assume known causal graphs [1,2,3]. However, the causal graph is not provided as input in AUF, and a causal graph that faithfully describes the relations among the variables may not exist at all (e.g., the interrelated relations captured by rehearsal graphs). As causal graphs are not available in AUF, such methods are not applicable. Secondly, the optimal decisions in AUF depend on the observed evidence $X$. However, current CB methods do not consider the existence of $X$ and only seek an optimal arm that maximizes the expected reward. Such approaches are unlikely to yield good results, as there is no universally optimal decision (arm) for all possible circumstances represented by $X$.\n\nTo verify the above points, we conducted new experiments with a recent CB method that can handle unknown causal graphs [4]. As we had anticipated, the average success probabilities were respectively 0.073 and 0.066 for two datasets, which are far from satisfying, indicating that CB is not suitable for AUF.\n\nAdditionally, we want to emphasize that the main purpose of the experiments was not to show superior performance but rather to demonstrate the feasibility of solving decision-making problems with rehearsal modeling. The proposed framework yielding favorable results indicates that this work could lay a foundation for promising future investigations into this topic.\n\n> W2. Regarding the strengths and limitations.\n\nThe strengths of our work stem from the innovative use of rehearsal relations, which effectively help reduce the required number of interactions, as demonstrated in the experiments. As mentioned in Sec. 1, the success of reinforcement learning (RL) relies on a large number of interactions with the environment, which is feasible for game playing but can be unsuitable for problems like AUF, where interactions are sparse. In such cases, leveraging structural knowledge to enhance decision-making is a natural consideration. This aspect shares some similarities with causal bandits, where structural causal knowledge is used. However, causal knowledge can be too excessive and is difficult to obtain. Thus, we propose using the rehearsal relation, offering a more flexible approach yet still providing decision-making benefits. Another advantage of our proposed method is its ability to make decisions in the face of uncertainty, as it does not presume knowledge of the true underlying graph.\n\nAs for limitations, a notable one of the current work, which could be addressed in future studies, is that sequential decision-making has not been considered, while RL methods excel in handling such scenarios. We think this limitation does not interfere with the main purpose of this work, which is to demonstrate the feasibility of rehearsal learning. We believe that this is a promising aspect that can be addressed in future research.\n\n> Q1. How does the algorithm scale with the number of variables in the graph?\n\nThis is indeed an important question in practice. Since the exact characterization of the framework is intricate, we next provide a simplified analysis. \n\nLet $d$ denote the number of variables. We divide the running time into two parts. The first part is learning $\\mathcal{G}$. For a practical graph learning procedure, it usually has a running time of $O(\\text{poly}(d))$. Building $\\mathcal{G}$ therefore consumes $O(|\\mathcal{G}|\\text{poly}(d))$ time. The second part is the update and decision finding in each round. Consider a simplified setting with only directional edges. The number of parameters is $O(d^2)$ as there are at most $O(d^2)$ edges. Let $O(B)$ denote the running time of a Bayesian updating method for one equation, like Bayesian linear regression. The time complexity of decision finding is $O(d n \\log n)$ (see Sec. 4.2). The time complexity of the second part is then roughly $O(B d^2 + n' |\\mathcal{G}| + d n \\log n)$, where $n'$ is the number of samples for updating the graph posterior. The overall complexity for $T$ rounds is thus $O(|\\mathcal{G}|\\text{poly}(d)+T(B d^2 + n' |\\mathcal{G}| + d n \\log n))$, which scales polynomially with $d$. When considering bi-directional edges, it is reasonable to restrict the size of cliques to a constant to reduce modeling complexities. In this case, the number of parameters can be bounded by $O(poly(d))$, and the overall running time could still scale polynomially with $d$.\n\n\n> Q2. Can the rehearsation formulation be used for other decision-making problems than AUF?\n\nYes, the formulation can adapt to various decision-making problems. The discussion primarily focuses on AUF because the scarcity of interactions in AUF necessitates the use of structural knowledge, and the rehearsation formulation is a good choice. But the rehearsation formulation, especially the SRM, is quite general. We can describe the variables in other decision problems with SRMs as well and modify the objective functions. For example, if the goal is to maximize the outcome instead of AUF, the expected outcome could be placed into the constraint Eq. (6), and the following optimization steps still apply.\n\nThank you again for providing valuable feedback! We hope that the explanations address your concern appropriately. Some of the above discussion will also be incorporated into the revised version of the paper.\n\n[1] Aglietti et al. Causal Bayesian optimization. AISTATS, 2020.\n\n[2] Sussex et al. Model-based Causal Bayesian Optimization. ICLR, 2023.\n\n[3] Lee and Bareinboim. Structural Causal Bandits: Where to Intervene? NeurIPS, 2018.\n\n[4] Malek et al. Additive Causal Bandits with Unknown Graph. ICML. 2023.\n"}, {"review_id": "dMD7ex9ath", "reviewer": "Reviewer_9i1V", "summary": "This paper presents a new graphical architecture, called SRM, whose goal is to be in-between correlational studies and causality models that are SMC. The idea is that identifying variables influenced by decision on other variables is easier than causality learning, and sufficient for decision making. The decision model is supposed to make decision in different time steps, in order to avoid ending up in undesirable states. \n\nTo do so, a new family of graphs is introduced, for which are provided learning and inference algorithms, at least in the case where structural equations are linear with Gaussian noise and where inferences are of the AUF (Avoiding Undesirable Future) kind, which consists in maximizing the probability of the outcome being in desirable states over time-steps.", "questions": "As this is not my main area of expertise (to say the least), I have only a few questions besides those raised by the mentioned weaknesses:\n\n* At present, it is unclear to me whether the data sets are synthetically generated or not? If so, is there not a bonus to the presented method to use data generated from SRM? \n\n* Is there no way to prevent the observation made in the experiments, i.e., to have a drastic loss of performance (in terms of success probabilities) if the constraint on the sucess probability cannot be satisfied? Cannot we rather have a bi-objective function scaled into one? It seems very extreme to have only a 0.1 probability of success when pre-specifying a wished probability of 0.9. \n\n* From a decision-theoretic perspective, maximizing the probability of being in a state for one output variable can be seen as a very peculiar decision problem, and in practice one often wish to maximize some expected utility whose value may depend on many factors/variables. In particular, previously mentioned models such as MDP or reinforcement learning methods allow to specify such targets. Is the current framework restricted to probabilities of belonging to a state?", "limitations": "Limitations are reaonsably discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The article provides a generic abstract framework to make decision-making in a dynamic environment, while providing means to make inferences and find adequate decision \n\n* First experiments are provided that demonstrate the performances of the algorithm, that seems to work as expected except for high required success rates, in which cases it breaks down (due to the drop of the success constraint)", "weaknesses": "* Comparison with other decision dynamic probabilistic models: the approach mainly deals with the problem of making decisions in a dynamical setting witht he wish to attain given performances. Other frameworks that come to mind when reading the paper are Markov Decision Processes (where the goal would be to maximize the average hitting time of some states) and also Dynamic influence diagrams (or even Dynamic Bayesian Networks with the possibility of interventions as decisions). As those are dynamic tools allowing to solve decision problems, it is unclear why they cannot apply to the current problems and frameworks?\n\n* Effects of hyper-parameters: the complete learning + inference scheme requires a lot of parameters to fix/tune, and it is unclear how much efforts must go into determining those for the algorithms to work. For instance, how does the sampling of graphs as well as the number of graphs in $\\mathcal{G}$ affect the efficiency of the algorithms? If $\\mathcal{G}$ is small, the posterior could have only a few positive values, and it is not clear wether this is a problem at all? The same can be said for other steps, as those all require some approximations. Not much is given in this respect in the experiments, including in the supplementary materials.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments! Below we address your questions in a point-by-point fashion.\n\n> W1. It is unclear why other tools cannot apply to the current problems and frameworks.\n\nThank you for raising this point! Indeed, other decision tools such as MDP can be applied to the AUF problem. We have conducted experiments with the MDP-based reinforcement learning (RL) method DDPG and contextual bandit method CATS in the original version and added two RL methods in the response to W1 raised by Reviewer LgnQ. However, as suggested by the experiments, in problems like AUF where the number of interactions is extremely sparse and limited, traditional modeling tools that do not leverage structural information may suffer from data scarcity, and resorting to causal knowledge could sometimes be inappropriate and excessive. Therefore, the use of rehearsal relations is a more suitable choice. Moreover, we want to emphasize that one of the key contributions of this work is providing evidence that showcases the feasibility of building decision-making models based on rehearsal relations. We believe that this finding can serve as a starting point for promising future investigations into the proposed rehearsal learning framework.\n\n> W2. Regarding the effects of hyper-parameters.\n\nThe main hyper-parameters in the proposed framework are the size of $\\mathcal{G}$ and the number of samples in each approximation step. Unfortunately, the effect of these parameters is obviously problem-dependent and may not have a universally applicable answer. \n\nTo empirically explore the impact of these hyper-parameters, we conducted new experiments using the two settings in Sec. 5. The method exhibited similar performances with the number of samples ranging from 100 to 10,000. But since samples used in approximation are mainly drawn from the posterior distribution, whose computational costs are minor compared to the costs of taking real actions, it is reasonable to set a large sample size. And when doubling the number of graphs (originally set to the size of a learnable equivalence class), we observed that the posterior probability quickly concentrated on a small set of graphs, which had a limited effect on the subsequent rounds. The final average success probabilities for $\\tau=0.7$ were 0.707 and 0.682 for the two datasets, respectively, almost matching the previous performance. On the other hand, halving the size resulted in degraded performance (0.577 and 0.474). The rationale behind the results is probably that graphs in a small set $\\mathcal{G}$ are likely to be all far from the true graph, leading to poor approximation. In contrast, for a large $\\mathcal{G}$, the weights of unreliable graphs diminish after only a few rounds and have little impact on the future learning process. These findings suggest that setting a large $\\mathcal{G}$ could be a good choice if there are sufficient computational resources.\n\n>  Q1. Whether the data sets are synthetically generated or not? If so, is there not a bonus to the presented method to use data generated from SRM?\n\nYes, the datasets were synthetically generated since otherwise we would not be able to evaluate the performance of all methods due to the lack of true environments. The data were generated from SRMs because SRM is an appropriate way of describing the data-generating process in many problems. However, it is worth noting that the data can also be equivalently generated using an MDP formulation with sufficiently many (or continuous) states and actions. From this perspective, we think that the data-generating mechanisms should not be taken as a bonus for the proposed method. Instead, it is an inherent advantage of the proposed method to be able to find and utilize the structural information from data.\n\n> Q2. Is there no way to prevent the drastic loss of performance if the constraint on the success probability cannot be satisfied? Cannot we rather have a bi-objective function scaled into one?\n\nThe drastic loss of performance is certainly preventable, and the bi-objective you mentioned is surely a feasible solution. As explained in the last paragraph in Sec. 5, the reason for the drastic loss is that in our implementation, once the method finds the constraint cannot be satisfied, it drops the constraint and just find an action that could maximize the mutual information. We also mentioned an alternative implementation for this situation in Lines 262-263, where we recommend lowering the parameter $\\tau$ and restarting for the current round. To resolve your concern, we conducted experiments with the alternative implementation for $\\tau=0.9$. We decreased $\\tau$ by 0.05 when the constraints were not satisfiable. The average success probabilities were then 0.714 and 0.727, which do not exhibit a drastic loss of performance.\n\n> Q3. Is the current framework restricted to probabilities of belonging to a state?\n\nNo, the framework can be easily extended to handle other objectives. The SRM modeling and optimizing for an objective are two relatively independent components. For example, we can replace the constraints on the probability of belonging to a state in Eq. (6) with constraints on other user-defined expected utilities. The following Bayesian updates and decision-finding can readily adapt to this scenario with some modifications. The reason we currently use the probabilities of belonging to a state instead of other expected utilities is that, in this initial work, we consider the \"undesired future\" as a discrete binary variable. More general extensions, including using other reward functions and different action costs, are reserved for future studies and exploration of the rehearsal learning framework.\n\nThank you again for your insightful feedback! We hope that the explanations address your concern appropriately. We will also incorporate the above discussions into the revised version of the paper."}, {"review_id": "XhZuuEjBz8", "reviewer": "Reviewer_LgnQ", "summary": "The authors present a formulation called the rehearsal learning framework to study problems where reasoning about undesirable future outcomes can be leveraged to avoid those undesirable futures---a kind of forward-looking counterfactual reasoning.  The authors additionally show how decisions can be made within this framework using Bayesian methods, and prove some PAC bounds.", "questions": "* On line 30ish, the authors compare and contrast their formalism of AUF with the usual sequential decision paradigm of RL.  I'm not sure I fully buy this distinction, and I'm pretty sure MDPs can capture exactly as much structure as the authors suggest their formalism is capable of capturing (After all, RL has been applied to and solved many difficult games that have long term structure to be modeled, it's just usually the case that any decisions that might lead to negative rewards far in the future are absorbed into some value function after having seen that detrimental effect happen enough times in, e.g., simulation, and not via some explicit counterfactual/graphical reasoning process).  Could the authors clarify these sentences, or perhaps change the emphasis to be more one of sample efficiency, because I'm not sure I fully buy the strength of the current language?\n\n* The formalism of \"rehearsation\" proposed by the authors starts looking very similar to the process of, e.g., performing rollouts within a simulator to see if some trajectory stays within some feasibility region, or satisfies some kind of safety constraint (especially common in the robotics literature).  Could the authors comment on how they see their work interacting with this line of work?\n\n* Could the authors provide some analysis of how the method's performance fares as the assumptions around low sample efficiency are relaxed?  Table 1 clearly indicates the superiority of the method, but surely DDPG starts winning after the number of interactions with the environment is increased.  Or do I misunderstand the relevant limits?  (Regardless, it's always a great idea to better articulate where the method starts to fail!)\n\n* The authors are selling their method as one that requires fewer interactions with an environment, but also demonstrate pretty strong sensitivity of their method to the hyperparameter $\\tau$ (which is obviously problem dependent).  Could the authors comment here?", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:  This work represents a fairly novel formulation of a decision problem, building upon prior work in probabilistic graphical models and causal modeling.\n\nQuality/clarity:  This work is fairly clear, though it is also fairly dense. \n\nSignificance: This particular formulation seems important, and is underexplored relative to the more traditional scenarios.  I suspect this method will be an influential launch-point for future work on rehearsal learning.", "weaknesses": "* The authors could probably spend more time comparing their method to other classical decision problem baselines (e.g., SAC / PPO, etc.).  There's also something of a cottage industry of sample-efficient methods in the RL literature that are probably relevant here, and it's unclear how much this method is buying you relative to these.  In short, it makes it difficult to situate how good this method really is, without a comparison to a more familiar method or problem.  That said, the experiments provided by the authors in their chosen domains are certainly compelling, and do seem to provide strong evidence of the efficacy of the method.  I just worry the authors have drawn a small box around the problem they care about which exactly coincides with where their method wins, and not terribly well overlapping with the space of problems people actually care to solve.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments! Below we address your concerns and questions in a point-by-point fashion.\n> W1. Regarding comparison with other baselines and sample-efficient methods (e.g. SAC / PPO).\n\nThanks for the suggestion! We conducted new experiments with SAC and PPO. The average success probabilities are:\n\n|  | SAC | PPO | Ours|\n| --- | --- | --- | --- |\n|Ride-hailing  | .177 | .154 | .714 |\n|Bermuda  | .205 | .190 | .679 |\n\nWe see that limited sample sizes pose challenges for baselines to achieve desired performance. However, we want to clarify that the main aim of the experiments was not to demonstrate that our method outperforms baselines. Instead, we want to show that it is possible and sensible to build decision-making on rehearsal relations (instead of correlation and causation), at least for some problems. It is more like a by-product that the proposed formulation has benefits for some problems with scarce data. And we hope this work could inspire future investigations into rehearsal-based decision-making.\n> Q1. Regarding the distinction between rehearsal formalism and RL, and the structures that MDP can capture.\n\nWe acknowledge that MDP-based RL methods can be applied to problems like AUF (Lines 30-31). The MDP formalism surely can capture enough information with sufficient modeling granularity. However, MDP may not be the most appropriate language for certain structural information. Let's consider an example with two actionable variables $A$ and $B$, and an outcome $C$ with the structure $A\\leftarrow B \\leftrightarrow C$. An MDP model needs to specify the transition probabilities between all possible 3-dimensional states and consider all actions $(A,B)=(a,b)$. On the other hand, by utilizing rehearsal graphs, we know that actioning on $A$ does not have any effect on $C$, and thus we can safely consider actions on $B$ only. Both formalisms are capable of capturing all information involved in the decision process, but in some scenarios, the proposed formalism can reveal more direct and helpful information. Furthermore, as you pointed out, the ability to capture structural information is closely related to sample efficiency. If there are sufficiently many samples, the two formalisms should contain a similar amount of information. But if the sample is limited, which is the main setting considered in this work, using the proposed formalism could be more beneficial. \n> Q2. Regarding the connection between rehearsation and rollouts.\n\nThe rehearsal operation and rollouts share some similarities: both involve evaluating the effects of actions by activating the actions in some environments. Their difference lies in the underlying rationale. Rollouts are more akin to an empirical test of a policy, though conducted in simulators rather than real environments. While the rehearsal operation is rooted in the rehearsation relation, which is believed to be useful for decision-making and lies between correlation and causation. By performing rehearsal on a fully specified SRM, we can gain a precise understanding of how the effect of actions is propagated through the rehearsal links and what happens if we manually cut off the links. This level of understanding can be highly informative in guiding decision-making for some critical applications. In contrast, rollouts can be less strict: the simulator can even be some neural networks or other black-box simulators, whose inner mechanisms may not be transparent but are enough for evaluating a policy in some problems. Hence, the precise rehearsal operation and the flexible rollouts may complement each other and offer unique advantages in different problems.\n> Q3. Regarding how the performance fares as the assumptions around low sample efficiency are relaxed.\n\nWe conducted new experiments with increased $T$. The average success probabilities of DDPG and our method on the Bermuda dataset are presented below:\n\n| T | 100 | 500 | 1000 | 4000 | 7000 | 10000 | 15000 | 20000 |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| DDPG | .230 | .243 | .255 | .516 | .642 | .688 | .707 | .708 |\n| Ours | .679 | .687 | .693 | .709 | .703  | .707  | .708 | .709\n\nThe performance of DDPG increases as $T$ gets larger, and catches up with the proposed method around $T=15000$. The proposed method also benefits from increased samples and maintains success probabilities greater than 0.7 after $T=4000$. The stability of the proposed method with increased samples is easy to understand: the learned SRMs become more accurate with more data, which in turn helps find good decisions.\n\n> Q4. Regarding the sensitivity to $\\tau$.\n\n$\\tau$ represents the user's desired level of certainty in avoiding undesired future. A smaller $\\tau$ indicates that the user is willing to accept a lower success probability. As long as the success probability is close to $\\tau$, we should consider the user's requirement as satisfied, and the problem as successfully addressed. From this perspective, the proposed method succeeded with $\\tau=0.3, 0.5, 0.7$, and does not show a strong sensitivity. As for cases with $\\tau=0.9$, as explained in our response to Q2 raised by Reviewer 9i1V, the drop in performance was due to the specific implementation. With an alternative implementation, the method achieved improved success probabilities of 0.714 and 0.727 on two datasets.\n\nAs you pointed out, if the goal is to maximize the success probability instead of matching a fixed preference, the optimal choice of $\\tau$ will heavily depend on the specific problem. The user can start from a large $\\tau$ and see if the constraints are satisfiable. If unsatisfiable, the decision-maker can lower $\\tau$ and restart the process. This flexibility allows the user to fine-tune the decision-making process and adapt it to specific problems.\n\nThank you again for your valuable feedback! We hope that the explanations address your concern appropriately. We will incorporate the above discussions into the revised paper."}, {"review_id": "lAfJPtlA9E", "reviewer": "Reviewer_8gB7", "summary": "This work presented a rehearsal learning framework to avoid undesired future. The framework was characterized by a \nprobabilistic graphical model called rehearsal graphs and structual equaitons, and the actionable decisions that enable the \noutcome to be altered are found under a bayesian famework, and the correct bound to quantify the associated risk was \noffered.", "questions": "1. I think a basic computational costs should be evaluated for the proposed algorithm.\nThe experiments should add more comparison between the proposed method and existing methods.\n\n2. Could authors please include temporal causal models as baselines?  I would also suggest that authors should compare the proposed method with causal bandit methods. \n", "limitations": "see the weakness and question sections. \n\n", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The problem that the paper is trying to solve is important, how to exploit the data generating mechanism to improve decision-making efficiency is of great importance but not yet fully addressed. \n\n2. The paper is generally well written and clearly motivated. \n\n", "weaknesses": "I think the biggest problem of this paper is the difference between the Strcutural Rehearsal Model (SRM) and Structural Causal Model (SCM). Authors claimed that SCM cannot address the dynamic problem with time involved which is not true.\nThere are a large number of existing work which investigate the causal structure learning / inference problem for dynamic systems and they can be leveraged for temporal decision making. The most widely used model is called Granger Causality Model and its variants. I don't see essential difference between SRM and SCM, if the only difference is the so called dynamic issue claimed in the paper. \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments! Below we address your questions in a point-by-point fashion.\n\n> W1. Regarding the difference between the Strcutural Rehearsal Model (SRM) and Structural Causal Model (SCM), and the dynamic issue in decision problems.\n\nThanks for raising the question! We are sorry for the possible misunderstanding raised by the word \"dynamic\". We want to clarify the distinction between the \"dynamic\" setting considered in the causal discovery and causal inference literature and the \"dynamic\" setting we refer to in this work. In the causal discovery and inference literature, the \"dynamic\" setting typically involves dynamic systems that expand over time. Related methods commonly assume that the causal structures among variables at consecutive time fragments remain unchanged and simply repeat over time, so that valid causal discovery and inference on time-series data are possible. However, in our work, when we mention the \"dynamic\" and time-dependent nature of decision-making, we mean that the relations among the same group of variables can evolve (or change) at different time segments. For example, offering a discount may attract more customers initially, but as time evolves and an economic recession occurs, the relations can change: offering the same discount may be useless. This evolving aspect is not considered in previous work on causality.  We will modify the description in the revised version of the paper to make it more comprehensive.\n\nFurthermore, in addition to the \"evolving\" nature of SRM, the fundamental difference between SRM and SCM is the distinct relations they described, namely rehearsation and causation, which we gave a detailed motivation and explanation in Section 2 and Appendix B. Compared to SCM, SRM additionally considers variables that are interrelated, altering each of them would render other variables to change, which can be inappropriate or inconvenient to model with causal relations. Moreover, we want to emphasize that this work is the first exploration into rehearsation and rehearsal learning. This study has already successfully demonstrated the possibility of building decision-making frameworks based on rehearsation, and revealed the potential advantage over other methods for problems with extremely sparse interactions. We believe that this work could open up exciting avenues for meaningful future investigations into rehearsal modeling-based decision-making.\n\n> Q1. Regarding computational costs and comparison with more baselines.\n\nThe average running time of the proposed method on two datasets for $T=100$ rounds is 228.4 and 332.6 seconds, respectively. As the running time can vary a lot with different learning components used in the framework, the actual running time may not be very informative. Hence, we give a simplified analysis of the running time complexity in the response to Q1 raised by Reviewer LZtj. The overall time complexity is about $O(|\\mathcal{G}|\\text{poly}(d)+T(B d^2 + n' |\\mathcal{G}| + d n \\log n))$, where $d$ denotes the number of variables and $n$ and $n'$ are respectively the sampling sizes in the candidate action finding step and the Bayesian update step. The time complexity reveals that the proposed method scales polynomially with the number of variables.\n\nAs for comparisons with more baselines, we conducted new experiments with the two settings in Section 5 using classic reinforcement learning methods SAC and PPO. The average success probabilities are presented in the following table:\n\n|  | SAC | PPO | DDPG | CATS | Ours|\n| --- | --- | --- | --- | --- | --- |\n|Ride-hailing  | .177 | .154 | .173 | .104 | .714 |\n|Bermuda  | .205 | .190 | .230 | .215 | .679 |\n\nAs observed, baselines do not achieve desirable performance, which is probably due to the scarcity of interactions in the AUF problem. However, we want to emphasize that the main purpose of the experiments was not to demonstrate that our method outperforms other baselines. Instead, as the first exploration, we want to show with the experiments that it is possible and sensible to build decision-making on rehearsal relations (instead of correlation and causation), at least for some problems. We hope this work could inspire future investigations into rehearsal-based decision-making. \n\n> Q2. Regarding including temporal causal models and causal bandits as baselines.\n\nThank you for the suggestion! Solving AUF with causal methods requires the method to be capable of optimizing the probability of belonging to a desired region with unknown causal structures. Unfortunately, we explored various temporal causal methods, but none of them can be applied. Regarding causal bandits, most studies assume a known causal graph [1,2,3], which is not available in our setting. We came across a very recent work [4] that does not require knowledge of the causal graph, and we conducted new experiments using this method. The average success probabilities obtained were far from satisfactory, achieving 0.073 and 0.066 on the two datasets, respectively. We believe that the poor performance is mainly attributed to the fact that causal bandits aim to find a universally good action (arm) with an optimal expected reward, while in the AUF problem, the optimal action depends on the observed $X$, and there is no single action that performs well across all circumstances.\n\nThank you again for your valuable feedback! We hope that the explanations address your concerns appropriately. We will also incorporate some of the above discussions into the revised version of the paper.\n\n[1] Lattimore et al. Causal Bandits: Learning Good Interventions via Causal Inference. NeurIPS, 2016.\n\n[2] Lee and Bareinboim. Structural Causal Bandits: Where to Intervene? NeurIPS, 2018.\n\n[3] Lee and Bareinboim. Structural Causal Bandits with Non-manipulable Variables. AAAI, 2019.\n\n[4] Malek et al. Additive Causal Bandits with Unknown Graph. ICML. 2023."}, {"review_id": "pev18q0vDB", "reviewer": "Reviewer_Pcym", "summary": "The paper proposes the framework of Structural Rehearsal Models (SRMs) which is similar to Structural Causal Models but not based on causal relations but instead on rehearsation [1]. In this kind of relation, edges can be bi-directional and indicate that some values influence each other. SRMs are then used to tackle the problem of Avoiding Undesired Future (AUF), where the agent wants to manipulate some intermediate variables Z in order to keep the value of final variable Y within the desired range; the problem is formulated using SRMs. Then, the algorithm is proposed for the case with linear dependencies and one-node interventions. Experiments in toy environments are conducted, showing that the proposed algorithm outperforms off-the-shelf RL algorithms.\n\n[1] https://link.springer.com/article/10.1007/s11704-022-2900-0\n", "questions": "[Q1] What happens if you have some clique, e.g. with 3 elements, and then one of the elements is used in the intervention? What will be the function to produce values for the remaining 2 elements, and how does it relate to an un-intervened function? Is it derived from the base one, or are there completely new parameters to learn here? In the latter case, there would be 2^c possible parameter sets for each clique of size c, right?\n\n[Q2] Section 4.2 - can you please explain how you derive the initial set of graphs G?\n\n[Q3] You mention in the paper that your framework enables non-stationary graphs etc. But this is never actually used, and experiments are for the simpler case. Moreover, it seems that this time-dependence could be introduced also for normal SCMs and it is actually orthogonal to the question if you use SCMs or SRMs. Can you maybe elaborate more on that aspect and argue if it is the case that this non-stationarity is more natural in the case of SRMs?\n", "limitations": "I suggest to the authors to include a subsection or a paragraph dedicated to listing the limitations, e.g.: focusing on linear case, toy environments, etc. ", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "[S1] The ideas presented in the paper are novel and seem to be well motivated by the need of having a less strict variant of “causal”-based models, where we still can leverage the structure without requiring strict causality.\n\n[S2] The paper is nicely written and well structured, mostly easy to follow.\n", "weaknesses": "[W1] I think having a concrete case where you show that your algorithm works well and causality-based methods either cannot be used or work worse is crucial. I am not 100% convinced by the experiments in the paper. Can causality-based methods be used there (if needed, by lumping together the variables from one clique)? If so, some causality-based methods should be included in the comparison. If not, please provide a compelling explanation why this is not feasible.\n\n[W2] I was not able to understand how the computation graph is changed when the intervention changes size of some clique; I present more details in [Q1]. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments! Below we address your questions in a point-by-point fashion.\n\n> W1. Regarding the experiments and if causality-based methods can be used (if needed, by lumping together the variables from one clique).\n\nThanks for the insightful questions! We want to emphasize that the primary goal of the experiments was not to demonstrate that our method outperforms specific baselines. Instead, as the first attempt to explore rehearsal learning, we aimed to illustrate through the experiments that building decision-making models based on rehearsal relations (rather than relying on correlation or causation) is feasible and sensible, at least for certain problems. The experiments clearly achieved this objective.\n\nRegarding the applicability of causality-based methods by lumping together the variables from one clique, we are afraid that it is not a suitable approach. While lumping together variables might seem like an intuitive way to incorporate causality, it results in coarse modeling granularity, making it challenging to find appropriate decisions. For example, if we lump three interrelated variables $V_1,V_2,V_3$ together as a single node $W$ in a causal graph, then the atomic intervention would be a joint intervention on $W=(V_1,V_2,V_3)$ simultaneously. The joint intervention on the three variables can be infeasible or unnecessarily costly for some decision tasks. Furthermore, in this lumping approach, we cannot model size-1 interventions in the \"causal\" graph by selectively intervening on only one variable, let's say $V_1$, while keeping the other two, $V_2$ and $V_3$, untouched. The reason is that intervening on $V_1$ would result in changes in $V_2$ and $V_3$, given their interrelated nature. In less formal terms, that means performing $do(W=w)$, which actually intervenes on an individual component, could lead to $W\\ne w$, which does not make sense in causality. Consequently, this approach is not well-suited for capturing the intricate relationships among interrelated variables. On the other hand, using SRM to model these variables are more appropriate, enabling us to account for fine-grained interventions and accurately capture their effects on the system.\n\n> W2 and Q1. Regarding the change of the graph when the intervention changes the size of some clique.\n\nConsider an example with a clique of size three. When intervening on one variable, the generating mechanism for the other two variables uses another set of parameters, which is generally different from those in generating the un-intervened function and is not derived from the base one if no further assumptions are made. Hence, in the most general case, there could be $2^c$ possible parameter sets for each clique of size $c$, as you correctly pointed out. In practical implementations, it is reasonable to limit the size of a clique and maintain the number of parameter sets to an acceptable level. Moreover, it is unlikely that we would need to or be able to intervene on every possible subset of a clique. We can save the parameters corresponding to those generating mechanisms that would not be used, thus reducing unnecessary computational burden. Also, we can impose certain assumptions on the relations among the parameters. For instance, it is possible to marginalize the parameters of the base case and use them as priors for the other sets of parameters, leading to more efficient modeling.\n\n> Q2. Regarding the generation of the initial set of graphs.\n\nThe generation of the initial set of graphs $\\mathcal{G}$ is given in Section 4.1, where we adopt a bootstrapped-based method. Specifically, we obtain a candidate graph $G$ by sampling from the observed data with replacement and applying a graph learning method on the re-sampled data, such as the preliminary learning method introduced in Appendix B. $\\mathcal{G}$ is constructed by repeating this procedure $|\\mathcal{G}|$ times. Each graph $G \\in \\mathcal{G}$ is given equal weight to serve as the prior distribution of the graphs. Subsequently, as we receive examples in each round, we update the posterior distribution of these graphs accordingly. We can then sample graphs from this posterior distribution in the following steps.\n\n> Q3. Regarding the time-dependence of SRM.\n\nThis paper primarily focuses on demonstrating the feasibility of using rehearsal to enhance decision-making in a basic setting. Non-stationary environment modeling is a more general and practical consideration but is also a much more complicated topic that requires further research and investigation. Intuitively, it is possible to model environments at time $t$ with a different causal graph and describe them with multiple SCMs. But the temporal nature is not inherent in SCMs. And current temporal causal modeling generally assumes that the causal structure in a dynamic system simply repeats over time, which is different from the situation we considered where the relations among variables can evolve over time. As for SRMs, since it is designed for modeling decision-making tasks, where time is an indispensable component, it is natural for them to have intrinsic time dependence. \n\nMoreover, an interesting observation that may warrant further exploration in future studies is that the interrelated variables in SRMs can provide hints for the possible evolution of variable relations. In an evolving dynamic environment, the change from $A\\rightarrow B$ to $A\\leftarrow B$ may undergo an intermediate stage where the relation is $A\\leftrightarrow B$, which is not considered in causal modeling. From this perspective, SRMs seem to be a more natural choice for describing such evolutions and incorporating structural knowledge into decision-making tasks.\n\nThank you again for your insightful feedback! We hope that the explanations address your concerns appropriately. We will also incorporate the above discussions into the revised version of the paper."}]

Author rebuttal:

Meta-review: This paper proposes a new rehearsal learning framework to avoid the undesired future (AUF) in decision making that studies the relationship of variables between definitions of correlation and causality. It presents Structural Rehearsal Model (SRM) that can handle dynamic graphs in contrast to traditional Structural Causal Model (SCM) with static graphical models. This work provides theoretical analysis of the new framework and conducts preliminary experiments on synthetic data to showcases the feasibility of building decision-making models based on rehearsal relations.

All reviewers appreciates the novelty of this new problem setting and multiple reviewers increase their ratings after rebuttal. All reviewers agree on the acceptance of this work. Reviewer LgnQ has a remaining concern that the proposed framework is designed for the particular problem domain (AUF) that might be too small and impact its broader impact, but he/she does not consider it to be a criterion against the acceptance of this submission.
Decision: Accept (poster)