Non-Stationary Structural Causal Bandits
Authors: Yeahoon Kwon
Yesong Choe
Soungmin Park
Neil Dhir
Sanghack Lee
Venue: NeurIPS 2025 poster ()
Keywords: Non-stationarity
Sequential Decision Making
Primary area: probabilistic_methods
TL;DR: We propose a non-stationary structural causal bandit framework that models intervention propagation over time via temporal causal models, and introduce POMIS$^+$ to identify non-myopic strategies maximizing long-term rewards.

Abstract: We study the problem of sequential decision-making in environments governed by evolving causal mechanisms. Prior work on structural causal bandits--formulations that integrate causal graphs into multi-armed bandit problems to guide intervention selection--has shown that leveraging the causal structure can reduce unnecessary interventions by identifying possibly-optimal minimal intervention sets (POMISs). However, such formulations fall short in dynamic settings where reward distributions may vary over time, as their static, hence myopic, nature focuses on immediate rewards and overlooks the long-term effects of interventions. In this work, we propose a non-stationary structural causal bandit framework that leverages temporal structural causal models to capture evolving dynamics over time. We characterize how interventions propagate over time by developing graphical tools and assumptions, which form the basis for identifying non-myopic intervention strategies. Within this framework, we devise POMIS$^+$, which captures the existence of variables that contribute to maximizing both immediate and long-term rewards. Our framework provides a principled way to reason about temporally-aware interventions by explicitly modeling information propagation across time. Empirical results validate the effectiveness of our approach, demonstrating improved performance over myopic baselines.

Non-Stationary Structural Causal Bandits
Yeahoon Kwon'
Yesong Choe' Soungmin Park' Neil Dhir Sanghack Leel
Graduate School of Data Science, Scoul National University Focused Energy Inc.
{dataofyou, yesong, tjdals0653,, sanghack) @snhaack))sssu.....m ac.kr neil.dhir@fee www.r/ffccueeeeeerrgg....om
Abstract
We study the problem of sequential decision-making in environments governed by evolving causal mechanisms. Prior work on structural causal bandits-formmlltion that integrate causal graphs into multi-armed bandit problems to guide intervention selection- has shown that leveraging the causal structure can reduce unnecessary interventions by identifying cossibly-optimal minimal intervention sets (POMISs). However, such formulations fall short in dynamic settings where reward distribu- myyoicc-ntuure tions may vary over time, due to their static and thus myopic- nature focuses on immediate rewards and overlooks the long-term effects of interventions. In this work, we propose non-stationary structural causal bandit framework that leverages temporal structural causal models to capture evolving dynamics over time. We char- acterize how interventions propagate over time by developing graphical tools and assumptions, which form the basis for identifying non-myopic intervention strate- gies. Within this framework, devise POMIS which captures the existence of variables that contribute to maximizing both immediate and long-term rewards. Our framework provides principled way to reason about temporally-awee tions by explicitly modeling information propagation across time. Empirical results validate the effectiveness of our approach, demonstrating improved performance over myopic baselines.
interven-
Introduction
The Multi-Armed Bandit (MAB) problem classic decision-making scenario where an agent sequentially selects actions (arms), each with an unknown but fixed reward distribution, to maximize cumulative reward [Sutton and Barto 2018). A common assumption in MAB formulations that arms independent. meaning that the reward distribution of one arm does not depend another [Li and Robbins 1985 Auer et al., 2002a However, in many real-world settings, actions are not independent hidden factors may simultaneously influence both the choice of action and the observed reward, introducing unobserved confounders (UCs). Bareinboim et al.) 2015). Forney et al.) [017)] Lattimore et al. 20166] Zhang and Bareinboim (017 demonstrate that in the presence of UCs, standard bandit algorithms guarantees such as convergence to the optimal arm and sublinear regret-no longer hold as observed rewards may accurately reflect the true effect of actions. To address this, Lee and Bareinboim (2018) use structural causal models (SCMs) [Pearl 2009) and causal diagrams to identify which variables agent should intervene to learn an optimal policy.
In many real-world applications, the reward distribution associated with an action is not fixed but changes over time due to shifting contexts, user behavior environmental factors. Such settings motivate the study of non-stationary multi-armed bandit (NS-MAB) problems, which extend the classical formulation to handle temporal variation in reward dynamics. This dynamic formulation requires agents to continuously adapt to evolving environments by incorporating temporal information
"Coressponiigg authors
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

into their decision- decision-making process. In particular, it relaxes the assumption of fixed reward distributions that underpins the classical MAB setting. While prior approaches to NS-MAB address temporal shifts in reward through statistical modeling- such as bounded change models (Auer et al. [0022b or
recharging payoffs [Papadigenopoulos et al. [022] they typically model non-stationarity in purely statistical terms, overlooking the underlying causal mechanisms responsible for reward shifts. Yet, in many sequential decision-making problems, such shifts are driven by latent and evolving causal mechanisms. In such cases, ignoring the structural causes behind the reward changes can limit an agent's ss ability to make informed interventions. In contrast, we frame non-stationarity through the lens of SCMs, allowing to reason about how interventions propagate over time. The details are provided in Appendix
To our knowledge, the non-stationary MAB problem has not yet been studied through the causal lens. As such one could consider adapting existing causal methods for stationary settings. In particular, Lee and Bareinboim [2019) propose latent projection-based method to identify possibly-optinn arms under partial causal knowledge (as detailed in Appendix J.T). However, that approach does not explicitly account for temporal order, treating the non-stationary process as if it were stationary. As a result, it fails to reveal which arms influence which rewards over time. This matters because, in non-stationary environments, identifying truly optimal strategies-those informed by both causal structure and temporal dynamics is crucial. It enables more effective and timely interventions in real-world settings such healthcare, education, and resource allocation, where decisions must often be made under uncertainty and limited budgets. Intervening without regard to temporal structure may appear optimal in the short term but lead to sub-optimal cumulative outcomes, ultimately limiting long-term performance. By explicitly modeling temporal structure, our approach overcomes this by capturing how causal effects unfold over time. This enables non-myopic strategies that align with long-term reward maximization, which is essential for planning in dynamic environments.
In this work, we approach the NS-MAB problem through the causal lens by introducing a structural framework that captures temporal dynamics via a rolled-out causal grapt [ methods like POMIS fail to account for shifting causal structures over time and propose POMIS that identifies non non-myon myopic intervention strategies with theoretical guarantees ($5). We provide a graphical formulation of POMIS that characterizes how interventions propagate across time, which supports systematic identification of non- non-myopic optimal interventions ( ($6). Building on this, we develop an efficient algorithm for computing intervention sequences using these graphical structures ( We empirically evaluate POMIS+ + across three non-stationary tasks, demonstrating its superiority over the myopic baseline in regret and optimal arm selection by capturing long-term causal effects through lemporally-aware interventions ($8) Appendix A outlines the paper's structure.
($3). We show how prior
Contributions
structural causal bandit (NS-SCM- MAB)-that combines the nature of NS-MAB with the underlying SCMs. Our framework models temporal dynamies not only in the reward distributions but also the underlying causal structure, capturing how interventions propagate over time. This formulation enables temporally- making, where an intervention time may have effects on both immediate and future outcomes. Second, to support this, we devise POMIS which extends the original POMIS by incorporating variables from future time steps to better evaluate the long-term value of interventions. Third, we theoretically establish that a partial assignment to preceding variables can strictly improve the expected reward in the temporal manner. Finally, we design an algorithm that identifies such non- myopic intervention sequences and demonstrates its superiority over the myopic strategy through experiments across a range of non-stationary environments.
First, we propose
decision-
2 Preliminaries
We introduce notation from causal inference to understand multi-outcome causal MAB problems. Capital letters denote a single variable, and the domain of X is denoted (X)). Bold capital X =
(X1,-..; Xx,) represents a set of variables. Additionally, lowercase x E (X) represents a value
of variable X, and the set of values is described as bold lowercase x E (X) = 9 We
denote x [W as the values of x corresponding to the intersection W X.
'A rolled-out causal graph is a time-unfolded representation of an SCM that explicitly captures temporal dependencies across time steps. Similar constructions appear in causal modeling over time, see e.g., Koller and Friedman 2009 p. 203].
2

---

Stationary SCM-MAB
(b) Rolled-out stationary MAB
Figure I: (a) shows the causal diagram for stationary SCM-MAB. The graph notation for rolled-out version of the stationary MAB shown in (b) indexing each round by its corresponding time step.
framework. An SCM M is a tuple (U, V, F, P(U)), where V is set of endogenous variables and U is set of exogenous variables. Each fv E F is a function that determines each endogenous variable V. That is, V + fv (pay. uy) where Pay VV(V) (V) and Uv C U. P(U) is a joint distribution over the exogenous variables. The SCM induces a causal diagram G, which includes directed edges encoding functional relationships between endogenous variables, and bi-directed edges encoding UCs. We adopt family relationships Pa(-)g. Ch(())g. An(-),, and De(-)g to denote parents, children, ancestors and descendants of given variable where ancestors and descendants include its argument.
We adopt the structural causal model (SCM) Peeal 2009]
We consider a discrete-time setting where each time step & E {I....,T} (abbreviated t E [T)) corresponds to distinet point in time. We denote by V. S V set of variables each time step focusing on the specific variables indexed by the subscript t. Let U, S be the set of exogenous variables, including exogenous variable Uv, for every V2 Vi and unobserved confounders for every Vi, V/ E Vt if Uv: and Uy are correlated. V C V is the set of variables whose time index is strictly greater than I. Let X, S V. (Y,) denote the set of manipulative variables, where Y, the outcome variable. Then, let N C V X₁ denote the set of non non-manipulative variables. We use blackboard bold letter V = (V1,... Vr} } to represent the collection of all time-indexed variables throughout the sequence and use F (Fi...., Fr) denote the collection of all time-specific functions.
A vertex- tntee--induced subgraph is represented by GIV where V S V. Given causal diagram G, time-specific subgraph can be constructed as U 1----1 Vs). where denotes the starting time step and r represents the length of the time window. In particular, when t = 1. we refer to this graph as 'time slice', denoted by V.). The probability of Y y. when variables X are fixed to x, denoted Ply do(X = x)) using the do-operator- an intervened probability. The graphical representation of the intervention denoted Gx: a mutilated graph where the incoming edges onto X are removed.
3 Non-Stationary Multi-Armed Bandit as Structural Causal Model
We define the NS-SCM-MAB and identify the prob- lems that arise when an existing stationary SCM- MAB solution is applied to the NS-MAB prob- lem by reviewing the SCM-MAB [ee and Barein- be SCM, and Y E V be a reward variable, where 2(Y) C R. The arms of the bandits defined by the possible values x of the manipulative vari- able set X, where X C V \ (Y), and 9XX). Each arm is associated with reward distribution P(Y do(X x)). The expected reward of
fx. Ux
fz. U $ It.
fr. Uy. θ 24
boim 2018). Let M
fx, Ux,, @ 2t
f2. Uz, ① Dzv 2z
FY. UY + 2y
(a) g
(b) F
Figure SCM with non-stationary structure.
arm is denoted by E[Y do(X = x)], written as fx. The optimal value of x for the expected reward denoted by x", i.c., agent interacting with an SCM-MAB as [g, Y]. We now discuss time-expanded notation. When we expand it to the time horizon, for every /. E [7), the causal structure among time-indexed variables identical across all time steps (illustrated in Fig. [(b)). The arms of the bandits are defined by the possible values x; of the set X, C V, (Y,) and X2 E (X,). The reward distribution is
argmax (X) For clarity, we represent the information given an
3

---

defined P(Y.
do(X; = xt), 11111 (1=-1) where 11:-1 = do([X; = )=1)) denotes previous interventions and 11>1 the indicator function. We denote E|Y; do(X, xx), 1,>1 [1=-1] as Mx,,ha-11 abbreviated as Mx. The optimal value for X, is denoted x
Non-stationarity in structural causal models Before defining non non-stationarity, we clarity our understanding of stationarity. In the context of bandits, stationarity means that the reward distribution induced from pulling one arm (strategy) among all possible arms remains constant across all time steps E [T). Interpreted from the perspective of the SCM-MAB, this implies that the distribution over the outcome variable Y-under interventions on any variables in the set of action nodes X C V \ Y-remains unchanged, regardless of earlier interventions, as discussed in Appendix D Formally, we can express this as follows: for every pair of time steps t, t' E [T] with t o t', a reward distribution Pyye do(x;), 1r>1 (1-1)-1111)-- = Pive' do(x)), ), 1 -1-2-11 From this point of view, we introduce the NS-SCM-MAB where the reward distribution evolves over time.
Definition 3.1 (Non-stationary SCM-MAB), Given a causal diagram G, let M =
be an SCM and Y c V be set of reward variables Y = - (Y;), where T >> 1. An SCM-MAB (M, Y) is said to be non-stationary, for some 1, 1' E [T] with < L', if the reward distribution
P (Y: do xt). 1 11-1) + P (Yr do(X, = Lx>) 11-
The disparity between reward distributions is referred as a reward distribution shift.
The NS-SCM-MAN addresses the problem of arm selection in environments where the interventional distribution over reward variables may shift over time. This is illustrated in Fig. 2 As shown in the diagram, the value from the previous time step (t) can influence the subsequent time step (t'), as indicated by the red edges. This temporal influence causes the reward distribution to change over time, reflecting the non-stationary nature of the underlying SCM. To understand this setting from the agent's 's perspective, it is important to recognize that the topological ordering of variable generation is subordinated to the temporal ordering -variables associated with earlier time steps always instantiated before those at later time steps. Based on this temporal structure, we define the notion of temporal model within SCM. A temporal model is SCM that captures the time-specific causal mechanisms as perceived by the agent at a given time step.
Definition 3.2 (Temporal Model). Let M = (U, V. F.F, P(U)) be an SCM. For some t E [T] with T> 1, we define values V2 and uj, which correspond to the values of V; Pa(V,) \ V, and the set of correlated variables U, between V E V, and Vi. E Ve for every t + 1', respectively. A temporal model M, vi, un is defined (U,, V Fr, P(U, u²)) where each fv; E F, is function that determines V2 given predetermined values vł and u². That is, V + (pay, [V.] U uy, Uuū)
where Pay; S V [Vi) and Uv, U,.
Concisely, we denote Mr V,, u, by .M.. Since the agent can only manipulate variables within the current time step, the temporal model is regarded as an underlying mechanism from the agent's s perspective for each time step. The key point is that the mechanism may vary across time steps, which arises from information propagation, resulting in a reward distribution shift. A myopic agent, however, fails to adapt to this change and follows a strategy which chooses actions based on the current information only.
Non-stationarity caused by information propagation We introduce the concept of 'information propagation' which induces the reward distribution shift between the two subsequent temporal models, and examine how it arises from the perspective of temporal models. To illustrate this, we consider two temporal models M₁ = (U,, F,, P(U, u;)) and M = (U++1: V141,FF41 P(U,+1 ui+ To isolate the effect of structural changes, we fix the exogenous distributions by assuming P(U, ut) = P(U,+1 1 and P(uţ) = P(u ). The agent identifies that the data generation for M141 occurs only after the data generation governed by Mr. Therefore, the agent time can neither observe the values of variables at future time nor intervene in advance on future variables. Under the environment, fv. E Fi # fv-, E F1+1 where F,, Fr+1 E IF implies that the distribution induced from the SCM-MAB (Me, Yi may differ from the distribution from (Me+1, Y4+1). Such function inequality arises due to predetermined values v E (Vi++) where Vi+1 = Pay, Vi+1, which is determined at time step L. As a result, information propagation refers to the process by which the predetermined values, generated within a temporal model M,, influence the generation of value in another temporal model M,+1.
4

---

To understand the concept better, we examine a simple case of two subsequent temporal models depicted in Fig. [ the rest of the values are generated according to the topological (causal) order. At time step 1', the function generating X₂ is fx,, = Ux,, @ 2t. where 2, the value of Z generated at time step t. Thus, at time step r', the function fx, utilizes 2t, treating it as conditional parameter (i.e., constant at t') to generate the value of X In this setting, the reward distribution of the arms may change over time, introducing additional complexity and challenges.
At time step t, the value of X, is generated from the function fx, Ux, and
Graph representation of the NS-SCM-MAB The graph representation of the NS-SCM-MAB captures the dynamics of the underlying non-stationary structure and the dependencies between variables of different time slices. Each time slice corresponds to a set of variables V, E V and the relationships between these slices depicted by edges, which elaborate on in the sequel, representing the information propagation across time. To establish the conditional independence structure between the causal diagrams of the NS-SCM-MAB and its probability distribution, we assume the time-slice Markov property as temporal extension of the Markov property.
Assumption 3.1 (Time-slice Markov), Given a causal diagram G and a probability distribution P relative to G. for every time step / if (V. JL V Vet-1 Vi-1)g where V. V, then P is said to be time-slice Markov relative to G.
Assumption 3.1 illustrates that under non non-stationary dynamics, the SCM-MAB exhibits a first-order Markovian structure where each time slice depends only on the immediately preceding one.
In addition, the graphical structure and topology of each time slice are identical across all time steps; that is, V = [' for all * t' E (T]. This reflects the bandit nature of our setting, where each temporal model corresponds to repeated instance of the same underlying causal structure. Given any two time slices [[V e and G Vel, J. this property implies stationarity between the corresponding temporal model MABs (Mr, Y.) and (Me, Yv), provided that no information propagation occurs across time steps, as illustrated in Fig. I(b)
If there exists at least edge is represented as a transition edge (V,, Vv-). The edge indicates that information propagation from temporal model M, to another My, conforming to the two subsequent time slices V[V.] and G(V+' :r) occurs at every time step. Notably, Assumption 3.1 implies that transition edges may exist only between consecutive time slices (i.e., first-order), thereby prohibiting connections between non-adjacent time slices.
edge between [ 1 and G[Vel, where V2 E V, and V/ Ve, this
4 Motivating Example
The primary challenge we address is identifying action sequences that maximize the expected reward under the NS-SCM-MAB setting. We first contemplate the solution of the stationary SCM-MAB problem given a causal diagram & to understand the non-stationary causal bandit. In the stationary MAB setting, choosing set of arms can be interpreted as identifying set of nodes Z from V \ (Y) that maximize the expected reward for outcome variable Y, formally written as
zt
arg max
E[ do 2)].
(1)
(EV
Previously, Lee and Bareinboim 2018 proposed a do-calculus- approach to exclude inter- vention sets that may induce sub-optimal expected rewards, ultimately identifying possibly optimal minimal intervention sets (POMISs) [Le and Bareinboim 2018 Def. 2]. We demonstrate, however, that this approach may itself lead to sub-optimality in the NS NS-SCM-MAB setting.
In the non-stationary setting, unlike the stationary setting where the agent only computes a POMISs once, the agent explores the search space at every time step identify the POMISS for each time- indexed reward variable. For instance, in Fig. ([a) we may consider the process by which an agent selects an intervention set at each time step. We can identify the POMISs by utilizing the concepts of Minimal UC- Territory (MUCT) [Lee and Bareinboim) 2018 Def. 3] and Interventional Border (IB) [Lee and Bareinboim] 2018 Def. 4], which characterize the POMISS graphically.
At time step = 1, from the agent's perspective, the set of possible exploration sets is {0, (X1). (21), {X1, Z1) We use an algorithm enumerating all POMISs [ee and Bareinboim
5

---

(b)
(c)
X3
X2
Xs
12+}
2
Z
Zz
Zs
(22)
(Xa, Zz}
M
Y/2
1/2
Y/
(2a}
(0)
(d)
(c)
(f)
Figure (a) Non-stationary causal diagram with {1, 2,3.. (b-d) illustrate examples of MUCT/IB based on the agent's movement at each time step. (e) represents the agent's 's non-myopic intervention strategy at (red box). (f) depicts tree diagram of all possible scenarios when action selection starts with {Zi} (red text denotes POMIS*).
2018 Alg. 1] with respect to [ 1 Y1]. The algorithm generates ( v Yi) = and
IBC V , Y1) {41} from MUCT(G Y1 {X1, Zı, Y1) and MUCT(G V Vilx; Y1)
(Yi). These illustrated in Fig. 3(b) and Fig. 3(c) with the MUCT shaded in red and the IB shaded
in blue. Thus, we get POMISs with respect to C 1]. -i.-..e. POMIS; = {0, {Z) }}. As result,
following the same procedure each time step 1,2,3, 3, the agent obtains the following POMISs:
POMISs (0, [2 POMISs2 = {0, (Za)) POMISs; (0. {2a}
Up to these time steps, the agent has identified the intervention set within its observable range at each time step. We next examine whether the identified intervention sets remain valid
extended time horizon under the non-stationary setting. As illustrated with shaded blue in Fig. 3(d) MUCT(G U V 22]. Y2) induces IB U V2). Y2) (X1). Consequently. under the broader causal diagram g U V2). we deduce that POMIS, = ((X1). (Z2)). By applying the same procedure [ U V2 V3]. Ys]. obtain POMIS; ([X2), (2a)] Eventually, obtain
the following POMISs with broader horizon:
POMISs = {0, }), POMISS2 ((X1), ((Xi),(2)) (22)), POMISs; ((X2), (2a))
This differs from the previously computed myopic evaluations. These discrepancies highlight that variables such as {Xi) or {X2), excluded under myopic evaluations, may be optimal when viewed from a broader temporal perspective while seemingly valid options like @ become sub-optimal.
Therefore, the agent should have intervened on {X1} and {X2] in advance because those variables not manipulable for each current time step; {X1} } for / = 2 and {X2} for / = 3. However, the variables may not have been considered optimal for a reward variable at an advanced time step. This supported by the inequality below:
max PZz S (x2))
max P22
(2)
(2))
which is derived from Maz = E., Me, P(2 do(xg)) S Ex, May P(zyl do(z))) = Msg given [g] Y2]. This inequality shows that the expected reward for intervening on {X₂}
} is strictly
dominated by that of {Zz}. making (X²) suboptimal intervention for Yz. Nonetheless, this does not imply that {X2} should be excluded from the intervention set. Instead, it suggests that {X2}
and {22) must be jointly intervened upon (i.e., (X2, Z2) in Fig. 3(e)): while [22) is required to
optimize the immediate reward Y2, (X2) is necessary to influence the future reward Yg. Importantly,
intervening on (X2) does block the causal influence of {72) on Y,, thereby allowing both
short-term and long-term rewards to be considered simultancously. Similarly, for 1, the

---

intervention set is assembled as {X1, 21). Finally, we obtain the set of intervention sequences:
{(121). ( (2,)), (1Z)), (X2, Z2). 0). (0. [Z2). (9, [22) [X3, Za)). (0. (X2, 22); 0), ([X1, 21, (2z))] } the details of which are formalized in Def. 5.1. We can depict the tree
structure of these sequences as shown in Fig. 3()) where each branch illustrates a valid path if Z1
intervened at the first time. These combinations will be discussed in detail in $5
Building on the above example, we formally define the concept of POMIS for the NS-SCM-MAB and propose graphical method to capture its dynamic evolution while conserving optimality.
5 Conservation of Optimality
We examine theoretical guarantees for identifying optimal intervention sets under the NS-SCM- MAB problem. From $4 we know that myopic intervention (i.e.. pulling arms within the current manipulable variables) does not always guarantee optimality for broader horizon. Rather, the agent must consider the sequence in which variables should be intervened on for subsequent time steps-a non-myopic strategy. To formalize this notion, we define an intervention sequence as follows.
(XI...., Xx) be an intervention Definition 5.1 (Intervention Sequence). Given [[, Y], let S sequence where X, S V. (Y,) for t E [T].
Now, consider intervention sequence ((X,, 0,0, 0, (2,)) in Fig. In the first intervention set of the sequence, {X,, Z1 Eq. (3) shows that X1 E V1 may serve as a predetermined value for the temporal model M2, potentially contributing the maximization of the total reward. For model M, the maximized sum of expected rewards over two time steps t = 1,2 can be divided into two sums of maximized expected rewards, each corresponding the temporal model Mi and M2
E B Y2 do(X = x)] = E Mi MM do(Z - z)] + Malv (Y2 do = k)].
(3)
In this equation, we define X = {. 0). Z = {Z1} and K = 0. The value x1 is a predetermined value of M2 that is taken from the do-assignment at time 1. From this example, Thm. 5.1 shows that there exists an optimal temporal model under the specific pre-determined values.
Theorem 5.1. (Existence of Optimal Partial Assignment). Given information [g. YI, let X be POMIS with respect to v Yvl for the subsequent two time steps t, E [T'] with t < t.. Then, there exists an assignment w for a subset of variables W C Pa(Ve) = V such that
[Yr do(())]]
achieves the maximum expected reward for any vo with w = vt [W].
Remark 5.1. The subset W C Pa(V,, in Thm. 5.1 when combined with the intervention set Xe can be interpreted as POMIS with respect to I9T U Yr]. In other words, although W lies in time step and X in time step f', their union forms a possibly-optimal intervention set for Yv under the expanded temporal context, highlighting the intertemporal nature of optimal control.
Theorem 5.1 implies that once the optimal partial assignment w" is fixed, the remaining variables in Pa(V V e W have no influence on the expected reward of Y,. Therefore, the agent must select these variables with the original POMIS at t.
Definition 5.2 (POMIS with Future Support (POMIS+)). Given information [G, YJ. for subsequent time step t E [T]] with t < t', let X, be a POMIS with respect to [ Y.J. If there exists W. C V, \ (Yr} satisfying Thm. 5.1 such that Px, Ux, for every temporal model M, conforming to G[V.), then (X, UXW,, is called POMIS with future support for Yv, denoted POMIS
As the name suggests, P extends the original POMIS by incorporating one additional W, This set consists of variables that contribute to the maximization of the expected reward at subsequent time step. However, the selection of W, is constrained by the temporal structure of causal diagram G. Proposition 5.1. (Temporal Dependency). Given causal diagram G and a collection of time-specific variables V, POMIS S V, (Y:) for every t E [T] under Assumption 3.1
Proposition 5.1 implies that in causal diagram G, we can determine POMIS+ by only exploring the causal diagram window V U V
7

---

Algorithm Computing all intervention sequences
1: function (G, V, Y, T)
2: Input: G causal diagram; V collection of time indexed variables;
Y collection of time indexed rewards; T the time horizon of episode
return POMIS' SEQ (G, V. T)
4: function POMIS' SEQ(G, V, T. I 0). 12 0)
Yi + 0, Y 9 An(Y))
6: IF < {(MUCT(S
W Yx), IB ( w5
7: for (Xs. Ts) E do
8: 2 < IB Xs, It QI V, Ts, 2.I+) (by Alg.
< the earliest time index such that keys (I*)
10: if > then + $ o (POMIS' SEQ(G, V, Y, to 1,, 2))
11: else the product combination of all sets [ U q: 2 reaoys ( (hy Prop. 6.1
12:
return S
Graphical Characterization of POMIS
To graphically characterize POMIS borders over future rewards (IB*) and qualified interventional borders (QIB) which together enable the construction of POMIS based causal topological properties.
introduce two novel graphical inttrttttiiinn
Definition 6.1 (IB for the Subsequent Time Steps (IB+)), Given [G, Y]. for any W S An(Yr)g
(Yr), define ((W) IB(GUU Volw. Ye). Then, for each j E (l,..... ('), Z(W) V is called an Interventional Border at time slice j for Yr, denoted by IB j.
Intuitively, i is computed for the future reward Y8 but resides within V.. Therefore, we must identify qualified interventional border under [.) Yj]-thhtt that is, an IB that satisfies certain conditions to remain effective even when IB is fixed.
Definition (Qualified (QIB),, Let
V.J. Yr) X+ where 1, E (T) with <. X for every W _ V. (Yr). then X is a Qualified Interventional Border
If IB |xtuw Y₁ for reward variable Y,, denoted QIB,-
According the definition, the QIB is selected such that the variables in 1 though fixed to optimize Yr, do not block the causal influence on the current reward Y.. By taking the union of both IB f, and QIB,, we can identify POMIS,
Proposition 6.1. (Composition of POMIS+), Given [G, YI. IB 1, (G V.J. Ye) U (9VV., Yi) is POMIS,, for t, t' [T] and <t
As shown in Fig. an IB for Yv spans over two time steps (blue shaded), and [X,} QIB, w.r.t [[[V.], Y.] are {Zr} and {W., F. [W.} is chosen for QIB, then one candidate for POMIS,, {X,, W.) (light gray), whereas if the choice is [z,}
} an TB from Def. 6.1 The candidates for
W.
W
}. then POMIS* L,v L, is {Xe, Zz} (dark gray). However, by Def. 6.2 we choose [ for QIB, (purple shaded) not (We). which can explained using do-calculus: we can show that Mat Ma; I Ma; +; This incquality suggests that (X,, 2.} is determined Note that, under Assumption 3.1 it is sufficient consider only subsequent time step to obtain POMIS without examining other time steps. In other words, given [g] YJ. the union of IB 1
POMIST, rather than (X., W.).
Figure 4: POMIS for the sub- sequent time step.
Ve+1), Y++1) and QIB,(G Yt) constitutes POMIS, 7
7 Algorithmic Characterization
We propose a recursive algorithm (Alg. [T for constructing optimal intervention strategies under non- stationarity, which systematically explores the graph in a backward manner while avoiding exhaustive

---

40K
Cumulaative
Regret
10K
20K
0
0
0
1.0
1.0
1.0
Probability
0.5
0.5
0.5
POMIS
POMIS
0.0
0.0
50K
100K
50K
50K
Trials
Trials
Trials
(a) Task
(b) Task
(c) Task
Figure 5: Cumulative regret (top) and optimal arm selection probabilities (bottom) across tasks
(columns), with solid for Thompson Sampling and dashed for KL-UCB; shaded bands denote #1 SD.
enumeration of all variable subsets. Given a causal diagram G and a sequence of reward variables W, the algorithm first constructs subgraph G' consisting of ancestors of the target reward variable Y,- Then, all valid MUCT and IB pairs are identified in the graph g'(L ('in 6). The algorithm iteratively explores each MUCT/IB pair, updating two key maps: I and Q, corresponding IB (Def. 66.1 and QIB (Def. 6.2). respectively (Line 8), Both I+ and Q map each time ł to the selected intervention variables via the functions IB and QIB. These maps are propagated through the recursive structure of the algorithm, gradually expanding the intervention variables each time step. If the earliest time-step of variables currently stored IB+ has not yet reached start time (1 (4=1), the algorithm recursively calls itself to evaluate earlier time steps, taking the current I and Q as arguments (Line 10). Conversely, suppose IB reaches the start time, indicating complction of the backward enumeration. In this case, the algorithm generates all possible intervention combinations for each time step based on the final IB + and QIB maps, as stated in Prop. 6.1 It then enumerates all possible intervention sequences by taking the Cartesian product of these -eneste--specfic combinations, adding each sequence to the intervention sequence container S (Line 11). The construction of POMIS* sequences leverages graphical characteristics (i.e.. IB and QIB) to reduce redundant computations across time. The time complexity is exponential in both the horizon T and the number of variables [V], specifically (221Vi-T) The details of the time complexity are available in Appendix H We now show that the recursive enumeration performed by the algorithm exhaustive and correct with respect to the definition of POMIS+ sequences.
Theorem 7.1. (Soundness and Completeness). Given information [G, Y]. Alg. returns all interven- tion sequences composed solely of +OMIS sets.
8 Experiments
We evaluate how effectively the POMIS+ strategy captures long-term effects compared to the myopic POMIS baseline. We conduct experimenty] on three settings, each designed to highlight different aspects of temporal intervention planning. Detailed specifications for each task are provided in App. We report two catfiisssuuultiiiiev regret (CR) and optimal arm selection probability (OAP) under
two MAB solvers: Thompson Sampling (TS) Thompson
1933 and KL-UCB Cappéé et al. 2013].
Task 1 (Fig. 3(a): As shown in Fig. (la), CR of the TS for the POMIS strategy converges around step 20K (solid blue line). In contrast, the sequences constructed from the myopic POMIS strategy show no sign of convergence (solid red line). Similar patterns are observed for the OAP result. Quantitatively, by step 100K, the POMIS+ strategy achieves a CR of 1.9K +:2 (TS) and +-3 (KIL-UCB), with optimal-arm probabilities (OAP) of 1.7%% and 97.0+ respectively. Meanwhile, the POMIS baseline performs substantially worse, with CR values exceeding 34K and 37K, while OAP scores remain near zero. This result is attributed to the fact that myopic strategies fail to include intervention nodes such as X, for MUCT(G[V Y2) and X₂ for MUCT(G 3]. Yg). The inability to access such variables leads critical long-tern failures in non-stationary settings.
A Python implementation can be at: :tttps://githin http:///ghhhhbb.cemeooooooo/////

---

Task 2 (Fig. 4): As shown in the second column of Fig. 5 the POMIS* strategy consistently outper- forms the myopic POMIS baseline both cumulative regret and optimal arm selection probability. By step 100K, POMIS* achieves substantially lower regrets- 1.1 K 1 (TS) and 2.8K +444 (KI.- compared 11 11.8K 77 and 14.1K for the POMIS strategy. Furthermore, the OAP of POMIS reaches 96.5+2.66% (TS) and 90.0+-4.29 (KI.-UCB), while the POMIS baseline remains near zero, These results demonstrate that POMIS successfully captures the long-term effect X on Yv, which is overlooked by the myopic strategy.
Task (Fig. 6 The final experiment is based on the SCM, which inten- tionally violates the time-slice Markov assumption (Assumption 3.1 by introducing Long-range dependencies and latent interactions across time (Appendix F. As shown in Fig. cj)) POMIS outperforms the baseline, though the gap is smaller than previous tasks. By step 100K, the CR of POMIS+ is 3. (TS) and 8.6K+66 (KL-UCB), improving upon the POMIS baseline regret of &9 and +722 respectively. In terms of OAP, POMIS+ achieves 87 47.0%4.7% (TS) and 62.0 (KL-UCB), while POMIS reaches only 10.0+15.6% and 48.5 respectively. These results highlight that although the advantage of POMIS is par- tially reduced due to the absence of time-local independence, it still provides superior performance by leveraging earlier interventions that propagate across time via DUCs.
W
12/2
W3
Figure 6: g for Task 3.
9 Discussion
We assume access to the full causal structure during evaluation. In many real-world settings, however, the agent may have only limited partial access to future causal diagrams rather than complete knowledge of them. Extending our framework to handle partially observed or uncertain temporal structures while maintaining optimality-remiinn an important direction for future work.
While our proposed algorithm is theoretically sound and complete, its computational complexity constrained by the exponential growth of the search space. A promising direction is to exploit repeated or modular structures that frequently appear in non-stationary environments for instance, by developing segment- wise variants of our algorithm that reuse computed intervention sequences across recurring causal patterns. Such extensions could preserve theoretical soundness while substantially improving scalability and applicability larger, real-world domains.
For the experimental setting, each experimental trial corresponds to a complete causal rollout, where outcomes from all time steps aggregated into a single episode-level reward. This episodic formula- tion enables fair comparison across intervention sequences based on their overall causal influence over time. Although interventions are not executed sequentially across evolving environments, the causal dependencies among time-indexed variables are fully encoded in the temporal models, ensuring valid evaluation of the structural optimality of POMIS sequences. Further discussions provided in Appendix[KX K
10
Conclusion
In this work, we present novel framework; the NS-SCM-MAB, that integrates non-stationary multi- armed bandit problems with structural causal models. Our formulation captures both evolving reward distributions and shifting causal structures, enabling temporally aware decision-maken making that accounts for how interventions propagate over time. To formalize this, we introduce POMIS + temporally- extended notion of optimal intervention sets, and provide theoretical justification showing that conditioning preceding variables can achieve improved expected rewards in dynamic environments. Building on this, we develop an algorithm to identify non-myopic intervention strategies, and demonstrate its empirical advantages over myopic baselines across variety of non-stationary settings. We believe this work provides a foundation for causal reasoning in sequential pocision-making under temporal dynamics and opens up new avenues for research at the intersection of causal inference and non-stationary environments.
10

---

Acknowledgments and Disclosure of Funding
We thank anonymous reviewers for constructive comments improve the manuscript. This work was partly supported by the IITP (RS-2022-122205332558 RS-2025-02266552255) and NRF (RS-2023- 1021129//55% (5-2023-0022266322555)) grants funded by the Korean government. Yesong Choe was supported in part by Basic Science Research Program through the NRF funded by the Ministry of Education (RS-2025-254) (8000).
References
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-2566 2002a.
Peter Auer, Nicolo Basa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1))48-77, 2002b.
Elias Bareinboim, Andrew Forney, and Judea Pearl. Bandits with unobserved confounders: causal approach. Advances in Neural Information Processing Systems, 28:1342- 1350, 2015.
Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-lebbler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, pages 1516-1541, 2013.
Andrew Forney, Judea Pearl, and Elias Bareinboim. Counterfactual data-fusion for online reinforce- ment learners. In International Conference on Machine Learning, pages 1156-1164, PMLR. 2017.
John Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Staristical Society: Series B (Methodological), 41(2):148-18) 164, 1979.
Wen Huang and Xintao Wu. Robustly improving bandit algorithms with confounded and selection biased offline data: A causal approach. In Proceedings of the AAAI Conference on Artificial 2024.
Intelligence, volume 38, pages
Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques Adaptive Computation and Machine Learning. The MIT Press, 2009. ISBN 0262013193.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, (1):4-22, 1985.
Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good interventions via causal inference. In Advances in Neural Information Processing Systems, pages 1181-1189, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Sanghack Lee and Elias Bareinboim. Structural causal bandits: where to intervene? Advances in
Neural Information Processing Systems, 31, 2018.
Sanghack Lee and Elias Barcinboim. Structural causal bandits with non-manipulable variables. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4164-4172, 2019.
Behzad Nourani- Koliji, Steven Bilaj, Amir Rezaei Balef, and Setareh Maghsudi. Piecewise-stationary combinatorial semi-bandit with causally related rewards. In ECAI 2023, pages 1787-1794. IOS Press, 2023.
Orestis Papadigenopoulos, Constantine Caramanis, and Sanjay Shakkottai. Non-stationary bandits under recharging payoffs: Improved planning with sublinear regret. Advances in Neural Information Processing Systems, 0-20325-20333 2022.
Judea Pearl. Causality: models, reasoning and inference. Cambridge university press, 2009.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.

---

William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of samples. Biometrika, 25(3-4):285-299)) 1933.
Jin Tian and Judea Pearl. On the identification of causal effects. Technical Report R-290-L,
Department of Computer Science, University of California, Los Angeles, CA, 2003.
Thomas Sadanand Verma. Invariant Properties of Causal Models. Manuscript, 1992. University of California, Los Angeles.
Thomas Sadanand Verma and Judea Pearl. Equivalence and Synthesis of Causal Models. In Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, pages 220-227, Cambridge, MA,7 7 1990.
Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of applied probabiiity, 25(A):287-298, 1988.
Junzhe Zhang and Elias Bareinboim. Transfer learning multi-armed bandit: a causal approach. In Proceedings of the 16th Conference Autonomous Agents and MultiAgent Systems, pages 1778-1780, 2017.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We accurately state our abstract and introduction based on paper's main claims named POMIS+, which a temporally-aware extension of optimal intervention sets that accounts for both immediate and future rewards in non-stationary causal bandit settings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We list our assumptions early in the paper and refer to them throughout the paper these assumptions, naturally, have an impact on the work presented. We further discuss the assumptions at length on page four after they have been stated. Further we have derived the time-complexity of our main algorithm (see Alg. [ to ensure that the reader is fully informed of the computational overhead required to use our work. While we have sought to demonstrate a representative set of graphs to experiment with, we naturally cannot test them all but have provided adequate proofs which show that method is sound and complete for any SCM that conforms to the assumptions we make in this work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We introduce number of theorems with accompanying proofs. We make an assumption in this paper, all which are listed in the body: Assumption [.1] All our theorems, propositions and corollaries are found in the body of the paper, we also reproduce each statement in follodix by its corresponding proof. Supporting assumptions, lemmas and theorems are adequately referenced in all our contributions.
followed
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Ys]]
We provide the full set of parameters used to produce our experimental results, all the details can be found in Appendix In addition, we will make open-source the source-code post-review.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
14

---

(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We make the code openly available on GitHub, with clear instructions to reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
public/guides. htw.s//oooooniissoooooooooooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ lttips.ccc/ublli/guuiccoo CooesS/mmddmSSbmm ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specifyy all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
We provide all necessary details to reproduce our results in full. $8 and Appendix contain the necessary parameter settings used to reproduce the plots in As noted above, we will also release the code post-review. With that the reader is fully equipped test out our method and reproduce our results.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
15

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We display uncertainty quantification ("error bars") the plots which show the cumulative regret as well as the optimal arm-selection probabilities see Fig.E/ In the body of the text we only report the mean value reduce clutter but those results are also available.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time execution) needed reproduce the experiments?
Answer: [Yes]
Justification: This paper provides sufficient information about the computational resources required to reproduce the experiments, which is available in Appendix
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research conforms fully with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
16

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This is fundamental research, and the theorems and methods we present are only evaluated for their technical accuracy and compared to reference methods, to demonstrate the increased utility of our work. The work we present fundamental within the realm of causal inference and optimal decision-makinn (bandits). We cannot at this point in time construe any negative societal impacts that may stem from our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
This fundamental research and the work presented herein does not pose any such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
17

---

12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
The only relevant comparison to the work presented in this paper is that by Lee and Bareinboim [2018). All theorems and methods from that paper have been cited fully throughout the paper and appendix. This is only true for the theory, no additional assets (e.g., code, data, models) were used in this work.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should provided. For popular datasets, paperswi thcode. theode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Yes. We will provide code via GitHub. The repository will include README file with detailed instructions on how to use the code and reproduce the main results. All new assets introduced in the paper are documented and provided alongside the code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
18

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy lattps:/nnerrips http//errpp.ccccooofeeeeeeee//// for what should or should not be described.
19

---

A Organization
A schematic of our framework and its logical flow is illustrated in Fig. 7 The diagram visually maps how the paper develops, starting from the formulation of the non-stationary SCM-MAB problem in } and introducing the temporal model along with key graphical assumptions about the nature of non- stationarity. $5 establishes that in a temporal model, partial assignments of predetermined variables can affect optimal interventions at future time steps, motivating the definition of POMIS* myopic intervention. This Ieads into the graphical characterization in $ which defines key structures (IB f, QIB) that construct POMIS+ Finally, 7 presents algorithm that enumerates optimal intervention sequences based on these graphical clements. The structure clarifies the dependencies between the paper's components and highlights how our contributions build upon another.
non-
Sec.
Sec. 3.1
Non-stationary SCM-MAB
Graphical Representation Assumption 3.2, 3.3
Temporal Model Det. 3.2
Sec. 4
Sec. 6
Conservation of Optimality
Prop. 4.1 Temporal Dependency Def. 4.2 Definition of POMIS*
Enumerating All Intervention Sequences
Partial Assignment w Thm.
Sec. 5
Graphical Characterization
Prop. 5.1 Composition of POMIS*
Def. 5.1
QIB Def. 5.2
Figure 7: An overall schema of this paper.
B Preliminaries
Here present definitions of MIS, POMIS, MUCT, and IB.
Definition B.1. (Minimal Intervention Set (MIS) [eee and Bareinboim, 2018). A of variables X XCV \ { is said to be a minimal intervention sel relative to (9, YJ if there is no X' C X such that Px[x]] Fx for every SCM conforming to the G.
Definition B.2. (Possibly- Opttiall Minimal Intervention Set (POMIS) [Lee and Bareinboim 2018). Given information [G, Y], let X be a MIS. If there exists SCM conforming to & such that μx- > (zez)(X) where Z is the set MISs with respect to G and Y, then X a possibly- optimal minimal intervention set with respect to the information [g. Y].
Definition B.3. (C-component [Tian and Pearl 2003)) In a causal diagram G, two variables are said be in the same confounded component (for short, C-compooent CC(-)g) if and only if they connected by a bi-directed edge (i.e., path composed solely of V, ++ V₁).
In this paper, we denote CC(X)g = Uxex CC(X)g.
Definition B.4. tion (G. Y). let H be G cY))) set of variables T C V(H) containing Y where V(H) the set of variables in H, is called UC UC-territory on G with respect to Y if De = T and CC(T) T.
Coooserree-CCoffundders Territory Lee and Bareinboim, 2018 Given informa-
A UC-territory T is said to be minimal if no T' C T is UC-territory A minimal UC-Territrry (MUCT) for G and Y can constructed by extending a set of variables, starting from (Y), alterna- tively updating the set with the c-component and descendants of the set.
Definition B.5. (Interventional Border [Le and Bareinboim, 2018). ). Let T be minimal UC-territory on 9 with respect to Y. Then, X = pa T) iis called an interventional border for G with respect Y.
20

---

Algorithm 2 Minimal unobserved confounders' territory
1: function MUCT(G, Y)
2: = (Y)
3: Q ) T
4: while Q +
do 5: remove an element Q1 from Q
6: W = <C()))H T= TU W: Q = (QUde(W))z)
7: return
C
Nomenclature
NS
Non-stationary
SCM
Structural causal model
RL
Reinforcement learning
MAB
Multi-armed bandit
MIS
Minimal intervention
UC
Unobserved confounder
POMIS
Possibly-optimal minimal intervention set
MUCT
Minimal unobserved confounders' territory
IB
Interventional border
QIB
Qualified interventional border
DUC
Dynamically unobserved confounder
CR
Cumulative regret
OAP
Optimal arm-selection probability
KL-UCB
Kullback-Leiller upper confidence bound
D
Stationary SCM-MAB
The cumulative regret of the stationary setting given by:
T
Rr
Uixt EE [(xxx.).
where xi denotes the globally optimal arm, defined
arg max XXX
EI do =)]]
where fx, is the arm played at round L. The SCM-MAB setting assumes that the agent has full access the causal graph G of M, although its parametrization remains unknown-i.e.. the agent knows the structure G, but not the structural functions F or the distribution over exogenous variables P(U). Furthermore, the causal graph is assumed to be static, meaning that the underlying causal structure of the domain does not change over time. As a result, the agent interacts with the same causal model in each round.
In this setting, there is no confounding across time slices, and thus, no information propagates between rounds. Consequently, the reward distribution remains fixed across rounds.
practice, under the stationary setting, agent effectively observes, in each round, a causal diagram G composed of temporally disconnected slices, as illustrated in Fig. [(b) This stationary (and also non-stationary) formulation typically assumes that the number of arms constant throughout the interaction. The graphical structure and topology of each time slice identical across all rounds.
21

---

The SCM-MAB framework inherently introduces dependencies between arms, stemming from the underlying causal relationships among endogenous and exogenous variables. [eee and Bareinboim 2018 2019 identified two structural properties that can be derived from any SCM-MAB framework:
1. Arm equivalence: a characterization of arms that share identical reward distributions, deter- mined using constraints from do-calculus, and
2. Partial-orders among arms: under what topological conditions one arm can be optimal.
Leveraging these properties, one can identify minimal intervention sets (MIS) that constitute non- redundant collection of informative interventions. In addition, [ee and Bareinboim 2019] identified both MIS and POMIS for the stationary setting with non-manipulative variables. However, these characterizations rest on the assumption that the causal graph G remains static and stationary- meaning that no information is carried over from previous decisions. eextends beyond the stationary assumption to present the SCM-MAB framework in the non-stationary setting.
E
Comparison with Conventional Non-Stationary Bandit Algorithms
We contrast our approach to non-stationarity in the SCM-MAB with traditional non-stationary bandit settings. Our focus is on how causal modeling provides structured explanation for reward distribution shifts over time. as opposed to treating them as statistical artifacts. These build upon early foundational work on dynamic allocation and index policies [Whittle] 1988 Gittins 1979]
Conventional NS-bandit formulations Conventional non-stationary bandit algorithms aim to maintain low regrel with respect to comparator (or competitor) class-a predefined set of benchmark policies that may adapt over time to account for changing environments (e.g., policies that allow limited number of switches between arms, comparators that track the best-performing arm over recent time windows, or strategies that assume bounded changes in the underlying reward distribution). These algorithms are typically categorized into two regimes: adversarial and stochastic bandits, illustrated in Table
Table 1: Representative non-stationary bandit settings and algorithms (adapted from Lattimore and Szepesvári (0200).
Regime
Setting
Description
Representative Algorithms
Adversarial
L-switching
The identity of the optimal arm may change abruptly up times
Exp3.S, AdaHedge
Adversarial
Variation budget
Total variation reward sequences is bounded by V
Rexp3, Adapt-EvE
Stochastic
Piecewise-stationary
Rewards are stationary within inter- vals, with occasional change-poinss
Sliding- window UCB. Change- point Thompson Sampling
Stochastic
Drifting
Expected rewards evolve smoothly over time
Discounted UCB, Sliding-window UCB. SW-TS
Each setting assumes non-stationarity as statistical property: either abrupt shifts, or slowly drifting rewards. Some algorithms require knowledge of the number of switches L, while others are designed to be adaptive. the variation budget setting, the cumulative amount of change in reward distributions is bounded by budget V, offering finer-grane finer-grained control of non-stationariyy than simple change-point models.
Causal non-stationarity (our perspective) Our framework models non-stationarity as a conse- quence of causal information propagation across time. Specifically, transition edges in the causal graph G (e.g.. X,
2., induce changes in the downstream reward variables (e.g. Yr)), illustrated in Fig. This structure directly captures why the reward distribution changes.
For instance, whereas traditional settings might treat EE(Y, do(x)) as shifting arbitrarily with I, approach identifies structural causes: P(Y. do((x)) is influenced by information propagation
22

---

from previous variables (e.g. X,-1, 11-1). This allows us to model the mechanism behind reward distribution shifts.
Moreover, the presence of ares (or edges) between time slices in g determines where and how changes occur. This is elosely aligned with the "mean payoff drift" interpretation in traditional models [Lattimore and Szepesvári 2020 Chapter 31], but we interpret it in terms of explicit graphical information in G.
Summary Most traditional algorithms detect or adapt to change, but do not explain it. Our approach, by contrast, offers a mechanism- baaaaadds----eeddddd explanation of non- aon-ssttionartt--Oon grounded in causal understanding of the system under investigation, which is itself strong assumption- -via the SCM structure. This allows for:
Identification of reward-relevant intervention targets (POMIS+)
Intervention sequence planning backed by theoretical guarantees derived from the underlying causal structure
Ultimately, our method treats non-stationarity as structured phenomenon emergent from a dynamic causal model, rather than as an arbitrary change in observed statistics.
F Semi Time-Slice Markovian Non-Stationary SCM-MAB
W
W3
Figure 8: IB ranges over four time steps.
We begin by formalizing dynamic unobserved confounders (DUCs), which represent exogenous variables inducing dependencies across time.
Definition F.1. (Dynamic unobserved confounders (DUCs)). Given [g. Y]. let U, denote the set of exogenous variables that induce dependencies between variables in V, and Ve for some t < t'. If U, U/, then we refer to U, as dynamic unobserved confounder (DUC), indicating that Ug introduces confounding effects that persist across time.
When such DUCs are permitted the graphical structure, we say the temporal graph satisfies the cemi-time-slice Markov property.
Definition F2 (Semi-timme time-slice Markov). A temporal graph & satisfies the semi simi-time-slice Markov property if it allows the presence of dynamic unobserved confounders (DUCs) across time. That is. the graph permits bidirected edges between variables V, E V, and Ve Ve for t of t', representing confounding induced by exogenous variables U, E U that simultaneously affect both time slices.
Under the semi-time-slice Markov assumption induced by dynamic unobserved confounders (Def. F.I). we need to perform a time-expanded search for valid intervention targets across multiple time steps. Consider the example in Fig. 8 When we calculate IB for MUCT(G]U* V.l. Y4). the
result consists of four sets: IB = (X1). IB 4 = (W2). IB 4 = (Wa) and IB = (Wa) (blue
shaded). Given those IB* each time step, can determine each QIB, according to Def. 6.2 For ex- ample, when I = [X,} is given, the IB corresponding to the MUCT(G Vixx,,u,, Y1 (Y1) is Z1. hence QIB, = { (. Similarly, for for MUCT(G)V xl Ys), we can choose QIB = {Zy} (purple shaded). For now, by Prop 6.1 we obtain + 's by taking the union of each IB,t, and QIB, QIB,-POMISt, POMIS = (W2, 72). POMIS 3.4 = (W,, Za} and POMIS = (W4). These POMIS+ sets can then be used as components of an intervention sequence in the NS-SCM-MAB setting.
2 Y2), we can select QIB, = [12}. and
(X1, 2
23

---

G Proofs
Theorem 5.1. (Existence of Optimal Partial Assignment). Given information [[ YI, let X be POMIS with respect to [ Yv| for the subsequent two time steps t, [T'] with t < t'. Then, there exists an assignment w" for a subset of variables W S Pa(Ve) V such that
BMell (Y do(x;))
achieves the maximum expected reward for any vy with w = v [W].
Proof. Let 1, E [T] with < L' two time steps. Given the information [g, Y]. we an arbitrary target variable Yp E Y located in the time slice [[v.].
We consider any temporal model Me that conforms the time slice g e. Let X be POMIS for Yr with respect to the time slice G Ve.. The goal is to show that under any temporal model conforming to V[V.,, there exists a partial assignment w that preserves the optimality of
Xy-
By the definition of POMIS, there exists intervention assignment x². +Xxx.) such that:
E M [Yr do(x))] BM [[r do(z)] for all Z E Z (
where Z is the set all MISs for Yp in g[V
Now consider how expectations are evaluated in the temporal model Me: they are conditioned on predetermined variables V ((P((V))) Hence, there must exist at least one such vž under which the above inequality holds.
Fix any such vé- Since the domain ((P((Ve) is finite, and the conditional expectation E. [do()] is deterministic function of v and the do-intervention, there exists minimal subset W C Pa(Ve) such that w =v [W] satisfies:
do(z)], for all vyr such that v w". That is, fixing the partial assignment w suffices to preserve the optimality of the POMIS X,: regardless of how the remaining variables in Pa(Ve) )) W are instantiated.
MeM [Ye do(x)))] > E Ma Wir [Yrr
Since the choice of My was arbitrary (subject to conforming v[V,,), this concludes that such subset W and partial assignment w" must exist under any temporal model consistent with the time-slice causal structure.
Proposition 5.1. (Temporal Dependency). Given causal diagram G and a collection of time-specific variables V, POMIS 7,,1 S. V. (Yi) for every E [T] under Assumption 3.1
Proof. For the sake of contradiction, suppose that the proposition does not hold. Then, there exists some t E [7] such that:
POMIS ++ V. \ (8)
That is, there exists POMIS set X 11++1 such that:
EX X where X & V, (Y:}
By this existence, X must either lie in a future time slice (X e Ve with t t'), or X Y-- We now argue that such an X cannot be part of any valid POMIS set under Assumption 3.1 Recall that under the assumption, the only causal influences Y.+1 must flow through variables in V, (i.e., no time cycles and no backward edges from Ve with < t').
Furthermore, POMIS 1+1 is defined as the minimal set in V, such that the intervention at time t maximizes the expected reward at time & + 1. Including any X & V, \ (Y:) violates both this minimality and the validity of the do-intervention within time
This leads to a contradiction. Hence, for all E [T]] we must have:
POMIS C V2 (Y)
24

---

We now prove the composition property of POMIS t.e., which guarantees that interventions on IB i,er do not block the causal effect of QIB, on Y. Before proceeding, we formalize the fact that the set constructed by IB satisfies the partial assignment condition required by Thm. 5.1
Proposition G.1 (IB satisfies the condition of Thm. 5.1). Lett < tt' and let Xv be a POMIS for Yu g[ Then, the set [ (9 V.J, Yv) identifies a subset of Pa(Va (Ve) such that there exists a partial assignment w over this which satisfies the condition of Thm. 5.1
Proof. Let 1' and let Xe be a POMIS for Yp in g[Ve]..
From Thm. 5.1 this implies the existence a subset W C :.) and a partial assignment w such that for all v7. with V WW] w", the reward under do(x;) ) can be maximized.
Now consider the construction IB (GTU" Vil, puting the interventional border IB in the full unrolled graph G, and selecting from it only those variables that reside in V.
By definition, this set is formed by com-
Since the IB of Ye is known to be a POMIS, and since IB + is subset of this IB restricted to variables available at time t, the values assigned to IB + in any temporal model appear as part of some V₁ (Pa((V
Note that although Thm. 5.1 is stated in terms of a temporal model My, the structure of MM- including its structural functions and the set of predetermined variables Pa(Ve.) is dependent
the M. Since IB is computed from the global graph GIU Vil, it selects variables that reflect this SCM-induced structure, and thus corresponds to the W required in Thm. [5.1
f.
Therefore, IB " fulfills the role of W in Thm. 5.1 ensuring that fixing its values preserves the optimality of X consistent with w*.
Proposition 6.1. (Composition of POMIS*). Given [G, YI. IB IB (GUU V.J. Yr) U (GVV)) Yi) is a POMIS for t, E [T] and <t
Proof. X, QIB and W, IB i V.l. By Def. 6.2 X, is a Quali- fied Interventional Border (QIB) for Y, with respect G[V,], which implies that X₁ IS POMIS for Y, Thus, the first condition of Def. 5.2 is satisfied.
Next, established in Prop. G.1 the set W, constructed via IB satisfies the condition of Thm. 5.1 there exists partial assignment w; over W, such that the expected reward for Y, under do(x,)) maximized.
Moreover, due to the construction of QIB,, which requires that IB Vwl.ww Y)) = Xx for some V
Z C V, \ (Y,). it follows that interventions on W, do not interfere with the causal effect of X, on Y, within []..].
Therefore, the expected reward at time remains unchanged Px. Px.uw, Hence, by Def. 5.2 the combined set X, U W. is a POMIS
Theorem 7.1. (Soundness and Completeness). Given information [G, Y]. Alg. Teturns all interven- tion sequences composed solely of POMIS+ sets.
Proof. We prove the theorem by showing (i) soundness: every sequence returned by Alg, Dis is composed solely of +O and (ii) completeness: every valid sequence of +OMIS+ is returned.
(Soundness) Fix the final time step T. Let g' G[An(Yr)ol and suppose the algorithm selects valid MUCT/BB pair (X, T) under the g'. IB' (V, x+) updates the IB+ map by assigning each X X to its respective time step fx. For each E keys(T+) (T+), the function QIB(G, V. T, Q, I+) constructs a mutilated graph g V and from it computes all valid POMIS's (i.e., q₂) that do not intersect with T. In the base case (i.e., when the earliest 4g 0), the Cartesian product over all / gives sequences [I+ U qe q, E Q[4}. By Prop. 6.1 each [+] U q, valid POMIS+ set at time t. Thus, every sequence in S consists of only + sets.
25

---

(Completeness) The algorithm recursively traces backward from t = T to earlier time steps, guided by the smallest time index in the current IB map, denoted t., and recurses with horizon t. -. At each step, the algorithm considers all valid MUCT/IB pairs for Y,. The correctness of this step is guaranteed by the soundness and completeness of the algorithm POMISs from Lee and Bareinboim) (2018) Theorem 9]. Each recursive call updates the maps I+ and Q by accumulating IB and QIB sets across all considered time steps. Once the earliest time index in IB reaches 0, the recursion terminates. At this point, the algorithm forms the Cartesian product
([telyya((+kxkyaaa (2) {I [t]Uqe 9r E @[(]} enumerating every possible combination across time. Since every possible IB+ and QIB configuration is explored and retained, the final set & contains all valid sequences composed solely of POMIS sets.
H Algorithmic Characterization of POMIS+
Algorithm/ 3 Update It and Q from I
1: function IB* (V, (V)
2: for each X X do
3: Identify the time step & such that X V
4: if E I+ then
5: [+ x-
6: append X to I- [t]
7: return I+
8: function QIB(G, V. T, Q,I+)
9: for each t E keys I do
if't &f then
11:
G., 2(1 t 9 V V 7
for each X POMISs(G,, Y() do
13:
if T = 0 then append X to 2(1]
15:
return
In this appendix. we provide a detailed explanation of the algorithmic components used in the enumeration of POMIS+ intervention sequences, as introduced in 7 At first, define and clarify the role of the two internal maps, I+ and Q, which correspond to the Interventional border for the subsequent time steps (IB +) and qualified interventional borders (QIB), respectively.
Map of interventional border for the subsequent time steps (I*) Given a POMIS candidate X obtained from the MUCT-IB procedure, we identify the time step associated with each variable X X, and store the map I' [t]. The map I thus organizes variables in by their corre- sponding time step, preserving the temporal alignment of possible interventions. This time-indexed representation allows the algorithm recursively evaluate which time steps still require backward expansion, and is central to the structure of Alg. This structure ensures that only the earliest relevant time step is explored recursively, avoiding redundant expansion into irrelevant subgraphs.
Map of qualified interventional Border (Q) Once I is populated, the QIB map Q is computed by evaluating each subgraph V after mutilating with the intervention set I [t]. From this mutilated subgraph, we re-run the POMISs algorithm on the local reward variable Y, to identify any remaining minimal intervention sets. These are stored in Q[t] only if they do not overlap with the current MUCT set T, ensuring independence across temporal intervention levels. The QIB thus captures any residual variables time that are necessary to optimize the local reward, complementing the already selected IB
The recursive design of Alg. I ensuures that the enumeration of intervention sequences terminates when all relevant intervention variables are assigned by time = At that point, the algorithm takes the Cartesian product of all IB+ and QIB sets across time steps to generate complete intervention
26

---

sequences. This backward recursive approach avoids exhaustive enumeration by pruning irrelevant branches early and leveraging graph locality in the causal diagram.
W1
W2
W2
W
Z
Z.
7
Figure 9: Illustration of the intermediate stage of the algorithm after two recursive calls.
Example traces of recursive enumeration. Fig. illustrates an intermediate stage in the execution of our recursive POMIS* enumeration algorithm. The color-coded graph shows how MUCT, IB and QIB evolve across time steps as the algorithm proceeds backward.
At the final time step / (corresponding to Y4 in the figure), the algorithm computes the MUCT and IB from the subgraph g[V3 U V.), resulting in MUCT set {X,, Z4. Y1} (highlighted in red).
The corresponding IB consists of the set {X3,, Wa indicated in blue. Next, the QIB computed by evaluating the mutilated subgraph G[V ([Valx,,. WT WT yielding {Za} as an intervention set (highlighted in purple).
Since the current earliest time step in IB + is 1 = 3 > 1, the algorithm proceeds recursively with +- 2. In this second round, the algorithm again computes the MUCT/BB pair for Y2, resulting in MUCT (X2, Zz, Y2) (red), IB (X1, W2 (blue), and QIB {Zı} (purple), after mutilating
[[Vi with {X1, W2).
Wi
W2
Z
Figure 10: Illustration of the intermediate stage of the algorithm after three recursive calls.
Fig. also provides one of the recursive traces of our POMIS enumeration algorithm over steps, starting from the final reward Y, at time t = 4 and proceeding backward to Y1 at t 1. As before, red nodes indicate variables in the MUCT set, blue nodes indicate IB variables and purple nodes denote QIB elements at each stage.
At time = 4, the algorithm identifies the MUCT (Y4, Z4, X4) (highlighted in red), computed from the subgraph V V.). The IB+ map is then updated to include (X3, W4} (blue), and since {7z) influences to Y3 in G[V 3 N., the QIB is {Zz} at this step.
Proceeding to time t = 2, the algorithm observes that a single node Y3 can be a MUCT. The corresponding IB+ is updated to (Z2) (purple), with no further QIB identified. At time / = the MUCT set becomes (Yi, Zi, }1} (red). The IB+ is now (Z,) (blue), as Zi is needed to activate paths Y22 under the current mutilated graph. Again, no QIB is generated at this time. Finally, t = 0, the algorithm computes MUCT as (X1, Z1, Y1} (red), and identifies IB = (Wi} (bluc), completing the backward exploration.
This example highlights how our algorithm incrementally expands the maps I+ and @ over time by tracing from Yy back to earlier rewards. Each recursive call explores MUCT/IB combination while updating time-specific intervention targets, eventually enabling full enumeration when the earliest IB reaches time
Time Complexity Alg. i
The recursive construction of POMIS sequences explores possible intervention combinations over a time horizon T.. In the worst case, each time step requires enumer-
27

---

ating subsets of ancestors of Y; to compute MUCT/IB pairs, followed by QIB exploration-bowt involving searches over subsets of the variable set V (i.e., ))) Each of these steps incurs an exponential cost of up to 2|,,, resulting in 2 VI complexity per time step. After I' recursion, the total worst-case time complexity becomes O VI.7).
I Experiment Details
In this section, we provide detailed specifications of the SCMs used in our experiments to ensure reproducibility. For each experiment, the simulation was repeated 200 times using the corresponding SCM. All experiments were run dual-socket Intel Xeon Gold 5317 system with 24 physical cores (48 logical threads) at 3.0GHz.
Task 1. We implement an SCM composed of three time steps t = 1, 2, 3 with variable sets (X,, Zr, Yr and structural equations defined to model the propagation of intervention effects over time. The probability distributions over exogenous variables U are defined as: We use the following probabilities over exogenous variables:
P(Ux, 1) = 0.85,
P(Ux, =1 0.47,
P(Uz, 1) 0.14,
P(Uy, 1) 0.02,
P(Ux, = 1) = 0.80,
P(UX,Y. = = 0.55,
P(Uz. = 1) = 0.14,
P(Uy, = 1) = 0.01,
P(Ux, 1) = 0.01, P(UxSYS =) = 0.51,
P(Uz. =1 0.13,
P(Uy, =1) = 0.05.
The structural functions fv for each endogenous variable V are as follows (where ① denotes binary XOR and v is the valuation of its parents):
fx, Ux, @ Uxin
fx, X1 Ux, UU.Y
fx, X2 e Ux, Ux.y
fz. = X1 + Uz
fz. X2 + Uz.
fz. = Xs + Uz.
fr. Z1 Uy, Ux.X
fr. Ze @ Uy, @ Ux.t
fy. Z3 Uv, 0 Ux,Y
(a)==1
(b) 2
(0)=3
Figure 11: SCM definition for Task 1.
Task 2. We conducted the experiment with a two-step SCM defined over variables (W, X,, Z, Y2} for t = 1,2, as illustrated in Fig. 4 The structure explicitly models how intervention effects on X; propagate across time via X and influence downstream outcomes Y, and Y++1 through intermediary variables Z
The exogenous distribution P(U) is parameterized to highlight the long-term influence of early interventions. The assigned probabilities are as follows:
P(Ux; = 1) = 0.15,
P(Uz. = =) = 0.15,
P(Uv, =1) 0.02,
P(Ux, = 1) = 0.47
P(Uw. = 0.15,
P(Ux, = 1) = 0.02,
P(Uz. =) 0.12,
P(Ux,Y. 1) 0.55
P(Uy, =1) = 0.01,
P(Uw; =) 0.12
We define the structural equations Fig. (where denotes binary XOR). Notably, the structural
Swo Uwo
Sw Uw.
fx. Ux. @ Wo @ Uxay
fx. = Ux, @ Wi @ Uxiv @ Xo
fz. = No Uzo
fz, X1 @ Uz
fr. = Zo 4 Uv, @ Ux,Y
fv. = Zn @ Uv, @ Uxi
t=)
(b)
Figure 12: SCM definition for Task
functions for X2 and Yn include X, as parent, creating a direct dependency between early decisions and future rewards. This design allows us to test the effectiveness of DUC-based POMIS+ strategies in capturing delayed causal influences that are missed by myopic approaches.
28

---

Task 3. To clearly illustrate how information from early IB and QIB components can propagate across multiple time steps in the absence of the time-slice Markov assumption (Assumption [3.]]. we design an SCM inducing Fig. G This structure focuses on exposing the long-range effect of early interventions. The SCM contains three time steps 1,2, 3 over variables (W,, X,, Yz), with unobserved confounding between X₁ and y at each step. A bidirected edge between X2 and X3 further emphasizes the departure from the time-slice Markov assumption. This configuration enables us to test whether POMIS can successfully capture reward-relevanl information originating from earlier steps.
The structural functions fv for each endogenous variable V are defined as follows:
fw, = Uw. fx, Ux, @ Wi @ Ux,n
fw; Uw,
Jw; Uw, fx. = Ux, @ W3 @ Ux,X,
fx. Ux @ W2 @ Ux,xs
fv - Xo @ Un @ Uxin
@ Ux,Y @ X1 fvz x @ Uy, @ Uxav
@ Ux,ys @ X2
fys = X3 @ Uy, Uxxy
t
t
t=)=
Figure 13: SCM definition for Task
The probability distributions over exogenous variables are defined as:
P(Ux, = =1) = 0.82,
P(Uw, = 1) = 0.15,
P(Ux,n =1) 1) = 0.52,
P(Ux, 1) = 0.92,
P(Uv, =1) 0.02
P(Ux,Y2 = 1) = 0.44,
P(Ux,X= = -0.43,
P(Ur; 1) 0.01,
P(Uw, =1 =1) =0.2,
P(Ux= = 1) = 0.20,
P(Ux.Ya = =0.488
P(Urs 1) 0.05,
P(Uw, =1) -041.
J Limited Alternative Methods to Approach on NS-SCM-MAB
J.1 Projection-based approach on NS-SCM-MAB
W
W
W
X1
Z
7
7.5
7
Figure 14: MUCT and IB in the 9[v.Y]
Lee and Bareinboim [2099] builds on the framework of Lee and Bareinboim [0018 by relaxing the assumption that every variable in the system must be manipulable, while still operating under stationary setting. Their method uses latent projections (Verma and Pearl [1990] |erma (1922] to identify possibly-optimal intervention targets and infer dependency relations among them, even when only partial causal information is available.
In our setting, although the underlying process is non-stationary, the complete causal graph is revealed after all rounds. This allows the latent projection technique to be applied post hoc for identifying possibly-optimal arms. Nevertheless, such approach overlooks the temporal dynamics inherent to the con-stationary process, thereby failing to capture how specific interventions affect rewards across different time steps. In what follows, compare this projection- based approach with our method.
First all, we introduce projection- approach. stationary setting with non-manipulable variables, [ee and Bareinboim (2019) characterize possibly-optimal arms using the latent projection technique Verma and Pearl] 1990] Vermal [992]. They begin with causal diagram G = (V. and define set of non-manipulative variables N V [Y), where Y is the target variable. To construct
29

---

the latent projection onto the manipulative variables V \ N, they consider an augmented graph ς that explicitly represents unobserved confounders. They initialize a graph H. (V N, 0). then add edges as follows:
1. A directed edge between Vi and V, V; + V 9 or there exists a directed path from V; to Vj where all non-end vertices in the path between there are in N.
2. A bi-directed edge between Vi and Vj if V; ++ V3 E 9; or there exists directed paths from an unobserved confounder to V2 and VJ in 9 where all non-end vertices are in N.
Let Giv.) denote the causal diagram resulting from projecting 9 onto V They prove that PP Fu,Y (i.e., POMISs given (G, Y, N) POMISs given (H, Y)) via two propositions, which ensures that the optimality of an arm remains under (i) projection from G to H and (ii) the reverse projection. Proposition J.1 (Causal Identification without Non-manipulative Variables [Lee and Bareinboim 2019)). Given an SCM M = M = (V, UV,U, F, P(U)), there exists an SCM M = Mv (V.U, U.U.A F, F(U)) such that (y) = (v) for any X, Y C. V N and Y * A. Proposition J.2 (Causal Identification under the Projected Graph (Lee and Bareinboim 2019 Given a causal diagram G, let H -IViN]- For a SCM M = MM = (V N,U, P(U))
conforming to H. there exists SCM M M (V.U, U,F, P(U)) that conforms to G such that N and Y #
(y) = (2(y). for any Y
Theorem J.1 (POMIS Invariance under Projection). Given causal diagram 9 = (V. E), reward variable Y e: V. and a set of non- ma-miiaplllble variables N S [Y], let H. be the projection of g onto V N. Then,
G.Y = PU,Y
where G.Y denotes a set of POMISS given (g,
Based the projection- based approach introduced above. we derive Fig. via the latent projection. In Fig. 14, we obtain POMIS = XI, Zz, W2, Zz, Ws. Wa). This result coincides with the outcome of our proposed POMIS+ method (Fig. 8) in terms of maximizing the cumulative reward y Ex Y.. However, since the graph in Fig. 14 constructed by projecting all temporal models into a single static, stationary structure, it lacks temporal interpretability. We argue that such a projection is insufficient for modeling and analyzing non-stationary bandit problems. where the notion of time is inseparable from the causal dynamics.
Non-stationarity in bandits inherently involves modeling how reward distributions evolve over time, and our method is specifically designed to capture and exploit this temporal evolution. The significant advantage of our framework lies in its ability to identify time-specific intervention sets for each reward variable Y,. This makes POMIS + not only optimal in terms of cumulative reward but also more interpretable and practically applicable real-world scenarios where intervention constraints or objectives vary over time. Below, we present one example that highlights this property.
Illustrative case: Sequential treatment with risk constraint Suppose each time-indexed interven- tion variable Ze, Xt, W; represents a distinct medication administered at time t:
Zy: fast-acting drug that strongly affects immediate health (Y2) but may induce side effects.
Xy: slow-acting drug that influences future outcomes (c.g., Y1+1, Y(42).
Wr: supportive drug that amplifies or stabilizes drug effects in the future.
Now consider a scenario where we impose a safety constraint on early reward:
Let A = (421, X1). (Ze, W2), (Za, Wz), (Wa)) denote the intervention sequence obtained from the POMIS method (or projection-basee method) across all time steps, and let an E (A)) be joint intervention assignment to the first intervention set.
E do(au)) Se
to ensure that early treatments do not induce excessive physiological stress. A projection based method (Fig. 14h optimizes E[Y")] and may select (Z₁ = 1) it increases Y' overall- the fact that Z1 directly affects Y, and may violate the safety constraint.
In contrast, our method (Fig. g) distinguishes that:
30

---

Z1 is QIB1 influencing primarily Y1, while
X1 is I, that contributes Y4 through the path X X2 X3 Y4.
By leveraging this temporal decomposition, satisfying the constraint on Y1 and still improving long-term outcomes. Formally, we solve:
selectively intervene on X1 while avoiding Z1.
a"
arg max
E
Σ
Y, do(a)
(A)(A) S.1.3 (do
Summary This example highlights the limitations of projection in non-stationary bandits. While projection-based methods may yield high cumulative rewards, they are blind to when and how specific interventions act. Our POMIS framework enables temporally structured intervention planning, allowing for interpretable, constraint-aware, and scquentially optimal policies. In domains such as medicine or education whhee interventions at each stage must consider safety or ethical constraints such temporal disentanglement essential.
J.2 Forced stationary approach on NS-SCM-MAB
W:
W1
W2
Wi
W2
X
X1
1
1/2
1/2
(a)
(b) 9x,,85
(c) 9x,,
Figure 15: (a) Non-stationary causal diagram G and (b, c) mutilated graphs
In the main text, we analyzed the non-stationary SCM-MAB setting in which the reward distribution changes over time due to the causal influence of past interventions (see Def. 3.1). While our main algorithmic framework leverages time-specific causal structure, alternative approach: forced stationarity via direct intervention. The idea is to identify intervention sets that block the information propagation (see $3) across time slices-thus preventing reward distribution shifts. This allows the agent to reuse previously learned interventional effects, reducing the need to re-identify POMIS sets or re-calculate expected rewards every time step. Before formalizing this concept, we introduce the notion of transition edge blocking.
also possible to consider
Definition J.1 (Block). Let G be causal diagram and V. the set of endogenous variables time An intervention do = x,) is said to block transition edges if, in the mutilated graph 9x, all incoming edges from variables in previous time slices Ver to X, are removed. This operation prevents the information propagation from Vz to V, via X
When such a blocking intervention is applied, the reward variable becomes conditionally isolated from its historical influences. This motivates the following definition of forced stationarity, grounded the interventional reward distributions formalized Def. 3.1
Definition J.2 (Forced Stationarity). Given non-stationary SCM-MAB (M, Y), we say that an intervention set F C V, induces forced stationarity over reward variable Y, if for every t < t', and for every (F). (YG do(f), 1,51 41--1) = P(r do(f), 1est (41-1 U Une-1)).
In other words, the reward distribution remains invariant over time under repeated interventions F.
This formalization allows to distinguish between actual stationarity (inherent in the SCM) and stationarity that induced by intervention. The following lemma clarifies the relationship between blocking transition edges and enforcing reward stationarity.
31

---

Lemma J.1 (Blocking transition edges induces forced stationarity). Let G be causal diagram, and suppose an intervention on {Z,} blocks the transition edge Z - Zz. Then, we have:
PY ())) Des1 (11-2) = P(, do Z,), 1s1 11a-1).
Therefore, the intervention enforces reward stationarity across time.
Proof. By intervening on Ze, we remove the transition edge from Z to Ze (Def. J.I,, thereby preventing any causal effect from prior interventions from propagating Z, As a result, Y, under do(Z,) becomes conditionally independent of earlier actions, and its interventional distribution same as that of 1 under do 11)
The idea of forced stationarity provides a mechanism to simplify learning in non-stationary SCM- MABs: if one can construct a policy that always intervenes on such blocking variables (e.g.. Z,), the resulting reward distribution no longer shifts over time. This allows the agent to reuse previously learned information without recalculating POMISs at each step.
However, such interventions may reduce the optimality of the resulting policy, Although reward distributions may appear stationary under intervention F, the values themselves may not be maximized. Blocking information from previous time slices may prevent the agent from exploiting long-term causal pathways that yield higher rewards.
To illustrate this trade-off, consider the causal graphs in Fig. 15 In Fig. [5(b) we apply an intervention on X2, which removes the incoming edge from X1 to X2. thereby blocking temporal information transfer and enforcing stationarity. While this simplifies the learning problem, overlooks alternative intervention options. In Fig. [5(c) we do not intervene on X2, but instead W2- a variable that is path.
structurally valid and potentially in maximizing reward, even though it does not block the transition
This example reveals an important limitation of the forced stationarity paradigm: sets such as (X2) and (W2) both are interventional border (IB), yet only X₂ induces stationarity when intervened. If one naively prioritizes only those IB variables that block transition edges, the policy may become overly myopic and ignore possibly higher-rewarding retains the full temporal structure and dynamically adapts to changes in reward distribution without forcibly blocking information. This enables both fine- fine-grained interpretability and optimal intervention selection over time.
options. In contrast, our framework (i.c., P
While the limitations of forced stationarity are evident in scenarios where blocking discards useful long-term causal dependencies, we emphasize that this strategy is not inherently flawed. In fact, under certain structural conditions, forced stationarity may serve as a practical approach to simplifying learning in temporally complex environments. For example, if the reward variable Y, consistently depends on repeated set of parent variables over time-such through recurring transition edges- then blocking those transitions can yield invariant reward distributions without sacrificing performance.
In such cases, domain knowledge or structural priors can inform targeted interventions that induce stationarity while still capturing the most influential causal paths. This highlights a broader point: rather than rejecting forced stationarity entirely, it can be selectively applied when supported by sufficient knowledge about the system's 's temporal regularities.
K
More Discussions
K.1
Relaxing Natural Characteristics on Temporal Structure
Our main theoretical development naturally assumes both an identical graphical structure across time slices and the existence of transition edges between them. These assumptions are introduced to reflect natural characteristies of non-stationary environments and to facilitate tractable inference. Importantly, the assumption of identical structure is not essential to the correctness of our algorithm: even when the assumption is relaxed, our method remains sound and complete, provided that the full temporal causal graph is accessible.
32

---

In contrast, the existence of transition edges plays more critical role. Without such edges, causal information cannot propagate across time, and the algorithm may fail identify relevant variables at earlier steps, limiting its ability to construct non-myopic intervention strategies.
The property of identical time slices reflects the natural structure stationary bandit models (see, Fig. [ where variables and their dependencies are replicated across time for each time slice. While this natural assumption simplifies the search space by enabling repeated reasoning patterns, which is a characteristic of bandit settings, it is not required for the correctness of the graphical analysis or the definitions of IB+ and QIB.
The existence of transition edges between time slices enables information to propagate forward in time, allowing the algorithm to identify earlier variables that support future interventions. Without transition edges, information cannot propagate across time, preventing the algorithm from identifying long-range dependencies or constructing effective non- myopic strategies. More concretely, certain paths to earlier supporting variables (i.e., IB+) become unreachable, limiting the algorithm's 's ability to exploit temporal structure for long- term optimization.
This flexibility ensures that our framework is broadly applicable, even in domains where temporal structure varies over time. We emphasize that these assumptions serve as modeling conveniences that facilitate analysis and interpretation, rather than strict algorithmic requirements.
K.2 Non-Stationarity in Causal Bandits vs. Causality in Non-Stationary Bandits
It is useful to distinguish our formulation from alternative approaches that combine causality and non-stationarity opposite directions. Our work builds upon structural causal bandits (SCM-MABs) [Lee and Bareinboim] 2018 2019]. which assume fixed underlying causal graph and utilize it to guide interventions. We extend this line work by introducing non-stationarity at the level of the causal structure itself-modeling how causal dependencies and reward mechanisms evolve over time. In this sense, we develop a causal bandit framework that internalizes non-stationarity as a structural property.
By contrast, recent efforts that introduce causal reasoning into non-stationary bandit settings typically begin with traditional statistical formulations such as hiding-windowe or change-poing models and incorporate causal estimators to correct for confounding or adapt to changing environments (details are available in Appendix [E). For instance, Huang and Wu (2024) propose a method for handling confounded and selection breccioo--biaeed offline data by deriving robust causal bounds for each arm. Similarly, Nourani- Koliji et al. [2023] address piecewise-stationn stationaay bandits with causally related rewards by detecting changes in both reward distributions and causal structure using a Generalized Likelihood Latio(GLR)-baseee change-pon point detector. In these settings, causality is layered onto fundamentally statistical treatment of temporal change, often without structural assumptions about the underlying dynamics.
The distinction more than philosophical. Our model-based approach enables:
Reasoning about how non-stationarity arises (via temporal models and transition edges),
Derivation of non-myopic intervention strategies through temporally-aware graphical struc- tures (POMIS ) and
Theoretical guarantees grounded in structural assumptions.
In contrast, approaches based on statistical modeling typically emphasize adaptation c.g.. through sliding windows, discounting, change-point ditection-withowe modeling the underlying structural mechanisms that generate non-stationarity. These methods act as black-box in the sense that they detect shifts or trends in the data but do not explain them in terms of causal relationships system dynamics.
K.3 POMIS+ Sequences as Composition Possibly Optimal Intervention Sets within Temporal Models
intervention sequence and the causal responses of each time-indexed variable determine the expected cumulative reward in sequential decision problem. In our framework, this is formal-
33

---

ized by an SCM .M together with a sequence of possibly-optimal intervention sets namely, POMIS + identifiid across time.
While SCM-level definitions of POMIS (cf. Def. B.2) evaluate optimality based on the existence of at least one SCM where given intervention set performs optimally, temporal decision-making imposes stricter constraint: each reward Y, must be evaluated in the context of prior interventions. This context naturally gives rise a family of temporal models M, vÝ, where vž represents the predetermined values induced by earlier actions, Thus, the optimal intervention at each time step may be determined within this temporal model, reflecting only the information propagation available at time t.
In this subsection, show that the expected cumulative reward under full SCM can be equivalently decomposed into a sum of expected rewards under temporal models. Fach such term corresponds to POMIS set time selected with respect MM vt. The result is formalized in Prop. K.1 which clarifies how the temporal roll-out of POMIS+ constructs a compositionally valid and possibly-optimas global intervention plan.
an intervention
Proposition K.1 (Composition of Temporal Optima). Let M be an SCM conforming to G, and
let (Xi...., XT) be an optimal intervention sequence with realizations xi, Ki.....Xfp XT. Let vž denote the predetermined variables at time t given past interventions. Suppose each intervention set X is constructed as POMIS, Wt where W, S Pa(Vv) satisfies the condition in Thm. 5.1 Then:
T
BM
Ye do(x) x7)
MM vi [Y, | do(x))]
Proof. We begin by expanding the expected cumulative reward under the full SCM M:
T
T
E.M
Σ
Y do(x],
xi)
M [Y,
For each t [T], let vi denote the predetermined assignment to Pa(V,) induced by prior interven-
tions (x( , x²-1/ 1). Then the reward at time can equivalently computed in the conditioned temporal model M, vī as:
E.M YY do(x)............ .......,,,)] Milv? [Y, do(x)))
Applying this to each and summing, we obtain:
T
T
MMM
Σ
Ye
x5)
= Σ
Melvi [Ye do(x)))
1=1
as claimed.
This proposition formalizes how the cumulative reward in a full SCM can be decomposed into sequence of rewards, each governed by temporal model conditioned on prior interventions (i.c., predetermined values). supports the view that the POMIS sequence acts as a possibly-optimm plan across time, even though the optimality of individual interventions may depend on specific prior values.
While each temporal model M₁ V determines the optimal intervention at time under a fixed history of prior interventions, the globally optimal sequence across the entire SCM must be selected jointly, since each temporal model depends on the conditioning induced by earlier decisions.
Corollary K.1 (Local Optimality Does Not Imply Global Optimality). There exists SCM M and intervention sequences (X1,..., XT) such that for each t, X, is a possibly-optimal intervention set in the temporal model Mr | vi, but the joint sequence (X,,..,;Yp is not globally optimal for B.
T Ye
This corollary illustrates that local optimality under temporal models does not guarantee global optimality in the full SCM. Due to the interdependencies between time steps, early interventions may have long-term consequences that are not captured by myopic optimization. Therefore, joint planning across time is necessary to achieve globally optimal decisions.
34


Reviews:
[{"review_id": "3byQsJ1lmF", "reviewer": "Reviewer_EXe2", "summary": "This paper introduces a non-stationary structural causal bandit framework to address sequential decision-making in dynamic environments with evolving causal mechanisms. Unlike traditional static approaches, the proposed method uses temporal structural causal models to capture long-term effects of interventions. The authors develop graphical tools and assumptions to analyze intervention propagation over time and introduce POMIS+, an extension of minimal intervention sets that optimizes both immediate and long-term rewards. Empirical results show the framework outperforms myopic baselines.", "questions": "- If Assumption 3.1 is not satisfied, what would happen to the theory of optimal intervention set?\n\n- What does the non-stationarity originate from? It seems that the non-stationarity originates from the reward distribution shift, and this shift may come from the shifting causal structure. \n\n\n- It is not clear whether the proposed method allows the shifting causal structure in the model.\nThis paper makes Assumption 3.2, which constrains the causal structures of each time slice to be identical.\nHowever, in lines 62 and 73, it seems that POMIS+ allows the underlying causal structure to change.\nThen, which variables are allowed to induce the shifting causal structure? \n\n\n- Since $X$ is the arm of the bandit, why intervening $Z$ in Equation 1? It is not clear what $Z$ is. \n\n- In Section 3.1, it might be better to briefly introduce MUCT and IB before giving the motivating example.", "limitations": "This method makes the assumptions of the first-order Markovian structure, an identical time slice, and the existence of a transition edge.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n- This paper studies an important problem, which extends existing stationary MAB to the non-stationary one. It uses the lens of SCM to characterize the temporal causes of reward changes.\n\n- The authors develop the POMIS+ algorithm that considers the long-term outcome effect of the current intervention.\n\n- The authors theoretically analyze the optimal intervention sets.\n\n# Weaknesses\n\n- It is not quite clear how the authors tackle the non-stationarity problem intuitively. \n\n- In Figure 1, the definitions of $Z$ are lacking.\n\n- Some minor typos. For example, in lines 128 and 188, there is no Fig. 6(b) in the paper or the Appendix.", "was_revised": false, "final_justification": "", "rebuttal": "> It is not quite clear how the authors tackle the non-stationarity problem intuitively.\n\nThank you for raising this important point. We understand that the intuitive motivation for how our method tackles non-stationarity may not have been sufficiently clear from the current presentation.\n\nOur work addresses non-stationarity that arises from evolving causal mechanisms in terms of **structural changes** (i.e., causal dependencies that vary across time) and thus distributional changes (i.e., shifts in the reward distribution $P(Y_t \\mid \\operatorname{do}(\\mathbf{X}_t))$). Unlike standard SCM-MAB settings that assume stationarity and focus on short-term effects, our method is designed to capture **temporal dependencies** and **long-term consequences of interventions**.\n\nTo make this explicit, our contributions can be summarized as follows:\n\n- **Modeling**: We formulate a non-stationary structural causal model (NS-SCM) where each time variables $\\mathbf{V}_t$ has its own temporal model $\\mathcal{M}_t$ and causal graph $\\mathcal{G}\\bigl[\\mathbf{V}_t\\bigr]$, and causal influence propagates via defined **transition edges** between two time steps $t, t’ \\in \\bigl[T\\bigr]$.\n- **Methodology**: We introduce a strategy that identifies **non-myopic interventions** by tracking how causal influence flows across time using graphical reasoning.\n    - **POMIS**$^+$: We develop the concept of **POMIS**$^+$  to address a key limitation of the classical POMIS approach, which only identifies variables that are optimal for the *current* time step. In contrast, **POMIS**$^+$  **captures variables that are crucial for maximizing both immediate and future rewards** by explicitly modeling how interventions propagate over time through the causal graph. To this end, we define two components—**IB$^+$**, which tracks intervention-relevant variables across time, and **QIB**, which characterizes the time-local minimal sets conditioned on IB$^+$—and take the union of them to construct valid POMIS$^+$ sets. Also, we theorically proved $IB^+ \\cup QIB$ is a POMIS$^+$ (Proposition 5.1). This enables our method to identify long-term intervention strategies that classical POMIS cannot capture.\n    - **Algorithmic Contribution**: We design a recursive algorithm that enumerates **all valid intervention sequences** composed solely of POMIS$^+$  sets, guaranteeing **soundness and completeness** under a dynamic causal setting. The algorithm reduces computational cost by pruning unnecessary intervention sequences, thereby avoiding redundant searches and enabling tractable computation even in long-horizon decision settings.\n\nThis design enables our method to move beyond myopic, step-wise decision-making and to account for **how present actions affect future rewards** through the temporal causal structure.\n\nWe will revise the introduction and Section 3 to make these intuitions clearer, and add a motivating example that illustrates how non-stationarity impacts the intervention choice. Thank you again for your helpful feedback.\n\n> In Figure 1, the definitions of $Z$ are lacking.\n\n In lines 119–121, we define $\\mathbf{X} \\subseteq \\mathbf{V} \\setminus \\lbrace Y\\rbrace$ to be a **set of manipulative variables**, not a single variable. As clarified in `Section 2`, we use capital letters for individual variables and bold capital letters for sets of variables. For example, if the causal diagram includes variables $X$, $Y$, and $Z$, then possible choices for $\\mathbf{X}$ (i.e., subsets of $\\mathbf{V} \\setminus \\lbrace Y \\rbrace$) include $\\emptyset$, $\\lbrace X \\rbrace$, $\\lbrace Z \\rbrace$, and $\\lbrace X, Z \\rbrace$. Thus, $Z$ is one of the variables that can be included in the set $\\mathbf{X}$. To avoid confusion, we will revise the notation and denote the set as $\\mathbf{A}$ instead of $\\mathbf{X}$.\n\n> Some minor typos. For example, in lines 128 and 188, there is no Fig. 6(b) in the paper or the Appendix.\n\nWe apologize for the typo that may have caused confusion. The correct reference is to Fig. 7(b), which illustrates the case where the causal structure among time-indexed variables is identical across all time steps and contains no transition edges—i.e., the stationary SCM-MAB setting. We construct our non-stationary setting by building on this stationary foundation. We will correct this typo in the camera-ready version. Thank you for pointing out this typo.\n\n***Questions:***\n> If Assumption 3.1 is not satisfied, what would happen to the theory of optimal intervention set?\n\nThank you for this insightful question. As described in `Appendix G`, we generalize Assumption 3.1 by introducing a broader structural condition based on **semi time-slice Markov graphs**—which allow for temporal dependencies that are not strictly captured by direct transition edges between consecutive time slices. Specifically, we consider cases where variables across time are connected through **latent confounding**, such as Dynamic Unobserved Confounders (DUCs). This formulation allows for the possibility that variables from non-adjacent time steps may exhibit confounding effects, thereby relaxing the strict temporal adjacency required in Assumption 3.1.\n\nImportantly, our proposed framework and algorithm remain applicable under this generalization. The identification of optimal intervention sets, including POMIS$^+$, still relies on causal information encoded in the temporal graph—regardless of whether Assumption 3.1 is strictly satisfied. The key requirement is that the causal structure (including latent links) correctly reflects how information flows over time.\n\nWe introduced Assumption 3.1 primarily to present a **clean and interpretable normal-form model** for the main exposition. We appreciate your question, and in the revision we will clarify in the main text that our theoretical results extend beyond this assumption via the structural conditions formalized in `Appendix G`.\n\n> What does the non-stationarity originate from? ... this shift may come from the shifting causal structure.\n\nWe clarify that in our framework, **non-stationarity originates not merely from reward distribution shifts, but from structural changes in the underlying causal mechanisms over time**.\n\nSpecifically, as shown in **Figure 1(a)**, the temporal causal graph includes **transition edges**—depicted in red—that connect variables from one time step (e.g., $X_t$, $Z_t$) to variables in the subsequent step (e.g., $X_{t'}$, $Z_{t'}$). These edges indicate that the value of future variables is not only determined by contemporaneous parents (within time $t'$), but also by prior variables from time $t$.\n\nIn the corresponding SCM (Figure 1(b)), this is formalized by structural functions such as: $f_{z_{t'}} = U_{z_{t'}} \\oplus x_{t'} \\oplus x_t$\n which show that $Z_{t'}$ depends explicitly on past values $x_t$ and $x_{t'}$. These variables then influence rewards like $Y_{t'}$.\n\nThus, while the reward distribution may appear to shift over time (i.e., $P(Y_t \\mid \\operatorname{do}(X_t)) \\neq P(Y_{t'} \\mid \\operatorname{do}(X_{t'}))$), this shift is **not arbitrary**. It is explained by **causal information propagating across time**, encoded by transition edges in the graph and captured through structural equations. In this sense, our framework does not treat non-stationarity as a black-box drift, but rather provides a **mechanism-based explanation** grounded in the evolving structure of the causal model.\n\nThis distinction is crucial, as it enables principled reasoning about why rewards change—allowing for informed, temporally-aware interventions.\n\n> It is not clear whether the proposed method allows the shifting causal structure in the model. ... Then, which variables are allowed to induce the shifting causal structure?\n\nAs we noted previously, our framework models non-stationarity not through changes in the causal structure within each time slice, but through causal information propagation across time steps via transition edges.\n\nTo clarify your current question: the variables that induce shifting causal influence are those that serve as the **source nodes of transition edges**—namely, variables such as $X_t$ and $Z_t$ at time $t$, which have **outgoing edges pointing to variables at time** $t’$.\n\nAs illustrated in **Figure 1(a)**, these variables have outgoing edges to future variables like $X_{t’}$ or $Z_{t’}$, introducing **time-varying dependencies**. For instance, $Z_{t’}$ is determined by a realized value of $X_t$ and $X_{t’}$ is set by a value of  $Z_t$ as shown in the SCM (Figure 1(b)).\n\nThis means that although **each time slice shares the same internal structure** (as per Assumption 3.2), the **full temporal model exhibits structural evolution**, because the set of active parents for each variable grows across time via these inter-slice dependencies.\n\nSo in short: the structure of the entire system shifts over time, and the **variables that induce this shift are precisely those that participate in transition edges—like** $X_t$ **and** $Z_t$**—whose influence spans across time steps**. This mechanism is what enables our framework to capture non-stationarity in a structured and interpretable manner.\n\n> Since X is the arm of the bandit, why intervening Z in Equation 1? It is not clear what Z is. \n\nWe intended the set of possible arms of the bandit to be $\\mathbf{V} \\setminus \\lbrace Y \\rbrace$, which we denote as $\\mathbf{Z}$ in line 197 when formulating Equation (1). As stated above, we will revise the notation and consistently refer to the set of possible arms as $\\mathbf{A}$, instead of using any other symbol.\n\n> In Section 3.1, it might be better to briefly introduce MUCT and IB before giving the motivating example.\n\nWithout familiarity with MUCT and IB, our work may be difficult to fully assess, even though we introduce these definitions in `Appendix B`. We will include them in the camera-ready version. Thank you for this suggestion."}, {"review_id": "MKBCmUUIe7", "reviewer": "Reviewer_k47E", "summary": "The paper introduces NS-SCM-MAB, a non-stationary structural causal bandit framework that models evolving causal mechanisms and captures how interventions affect both immediate and future rewards. It extends prior work by incorporating temporal dynamics into causal graphs and proposes a method for identifying the set of interventions that includes the best possible sequence of actions. The authors develop an algorithm to find such interventions and show, both theoretically and empirically, that it outperforms myopic strategies in dynamic environments.", "questions": "- Definition 3.1 may require clarification: shouldn't it depend on whether $Y_t = Y_{t'}$ (i.e., whether the reward corresponds to the same node across time)? Even in stationary environments, if $Y_t \\neq Y_{t'}$, the stated equality may not hold.  \n\n- Can authors explain the necessity of Assumption 3.3?", "limitations": "Refer to strengths and weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper addresses an important and realistic setting, as causal mechanisms in the real world are often non-stationary. This aspect has not been explored in prior work.  \n- The theoretical foundation is solid; the authors show that their algorithm is both sound and complete.  \n\n**Weaknesses:**\n\n- The novelty of the contribution is unclear. The proposed approach appears to be a natural extension of the framework by Lee and Bareinboim [2018] to non-stationary environments.  \n- There is no regret lower bound or discussion of optimal regret after identifying the set of POMIS$^+$. It is unclear whether a more efficient strategy than standard UCB could be applied over the POMIS$^+$ sets.  \n- Figure 6(b), which is referenced in lines 128 and 188, is missing from the paper.", "was_revised": true, "final_justification": "Thank you to the authors for their detailed responses, which have addressed part of my concerns.\n\nI am now convinced of the novelty of the paper. However, I remain unconvinced regarding the second issue. Similar to the work of Lee & Bareinboim (2018), this paper focuses on identifying possibly optimal intervention sets, that is, determining sets of nodes that can be removed from the action space a priori, without any sampling or interaction with the environment. In my view, this approach is somewhat incomplete, as it does not address whether such pre-processing is the only viable use of the causal structure. An important unaddressed question is whether incorporating causal information and extra observations during the learning process, over these possibly optimal sets, could lead to improved regret bounds.\n\nThat said, given that this is the first work to study non-stationary networks in causal bandits, I see this as a promising direction for future work. I will therefore increase my score to 4.", "rebuttal": "> The novelty of the contribution is unclear. The proposed approach appears to be a natural extension of the framework by Lee and Bareinboim [2018] to non-stationary environments. \n\nThank you for the thoughtful comment. We would like to take this opportunity to clarify how our work differs from prior approaches. While our work is indeed inspired by the structural causal bandit framework of [1], our contribution departs significantly from theirs, both conceptually and technically.\n\nThe key distinction lies in our treatment of **non-myopic intervention sequences** under temporal causal dynamics. The original POMIS framework identifies a set of possibly-optimal interventions under a stationary causal model. In contrast, our framework—NS-SCM-MAB—explicitly models evolving causal mechanisms over time and aims to identify a set of all possibly-optimal ***sequences* of interventions** spanning multiple time steps.\n\nThe limitation of existing method is clearly illustrated in our motivating example (see `Section 3.1`). As shown in **Fig. 4(a)**, **the existing method fails to select the crucial variable** $X_1$, resulting in a policy that does **not converge at all**, even with increased trials. This example highlights that **ignoring long-term causal dependencies can lead to intervention failures with severe performance consequences**.\n\nThe underlying challenge in the NS-SCM-MAB setting is not merely harder—it demands finer-grained and graph-theoretically precise control over how interventions influence future outcomes. To conserve optimality for each reward $Y_t$ , we introduce the notion of POMIS$^+$, which accounts for both immediate and temporally propagating effects. We further develop **two novel graphical tools**—**IB$^+$ and QIB**—and prove that their union satisfies the POMIS$^+$ condition (Proposition 5.1).\n\nAn additional difficulty lies in the need to **identify all such valid intervention sequences**, not just identifying POMIS$^+$ for a single $Y_t$. This motivates our second contribution: a recursive algorithm that, grounded in Proposition 5.1, is theoretically **sound and complete** in enumerating every valid sequence composed of POMIS$^+$ sets. This level of combinatorial and structural rigor goes well beyond what existing methods achieve.\n\nTo the best of our knowledge, **no existing method**—including those developed for dynamic or non-stationary bandits—offers a principled way to **characterize or compute structurally optimal intervention sequences** in the presence of evolving causal dependencies. Addressing this challenge requires a **fundamentally new framework**, including new theoretical results (e.g., Theorem 4.1), new graphical tools, and a new recursive algorithm (see `Section 5`)—all of which go significantly beyond the scope of prior work.\n\nTherefore, while our work builds on earlier causal bandit literature, we now recognize the importance of **more explicitly articulating** how our formulation generalizes prior frameworks—particularly in terms of modeling assumptions, graphical structure, and the nature of intervention sequences. We thank you for prompting this clarification, and we will ensure that these distinctions and contributions are more clearly emphasized in the revised version of the paper.\n\n[1] Lee, S., & Bareinboim, E. (2018). Structural causal bandits: Where to intervene?. *Advances in neural information processing systems*, *31*.\n\n> There is no regret lower bound or discussion of optimal regret after identifying the set of POMIS$^+$. It is unclear whether a more efficient strategy than standard UCB could be applied over the POMIS$^+$ sets.\n\nThank you for raising this point. We respectfully clarify that the focus of our work lies not in designing a new bandit algorithm, but in integrating causal structure into non-stationary bandit problems to reduce the set of intervention candidates through structural causal reasoning. Specifically, our framework leverages SCM and the causal diagram to identify POMIS$^+$ sequences, which represent minimal sets of possibly-optimal interventions over time. By doing so, we aim to **narrow the action sequence space** in a principled way based on causal structure (i.e., off-line pre-processing), rather than improving regret through algorithmic innovation.\n\nOnce the POMIS$^+$ sets are identified, any standard bandit algorithm—such as KL-UCB or Thompson Sampling—can be applied to explore over these reduced sets. **The regret analysis of such algorithms would then follow from existing regret bounds**, conditioned on the restricted arm space defined by POMIS$^+$. We believe this modularity is a strength of our framework: it complements existing bandit strategies by providing a **causally informed reduction of the decision space**, rather than replacing the exploration mechanism itself. Although the asymptotic regret class remains unchanged, reducing the number of arms through POMIS$^+$ can lead to smaller regret in practice, as regret bounds typically scale with the number of arms.\n\nWe appreciate the opportunity to clarify this distinction and will revise the manuscript to make this point more explicit.\n\n> Figure 6(b), which is referenced in lines 128 and 188, is missing from the paper.\n\nThank you for pointing this out. The figure reference should have been to Fig. 7(b), which depicts a scenario in which the causal graph over time remains identical across time steps, without any transition edges—i.e., the stationary SCM-MAB case. This serves as the foundation upon which we define our non-stationary setting. We appreciate your attention to detail and will ensure that all such referencing issues are corrected in the final version.\n\n***Questions:***\n    \n> Definition 3.1 (Non-stationary SCM-MAB) may require clarification: shouldn't it depend on whether $Y_{t}=Y_{t′}$ (i.e., whether the reward corresponds to the same node across time)? Even in stationary environments, if $Y_{t}\\neq Y_{t′}$, the stated equality may not hold.\n\nWe thank the reviewer for the comment. We would like to clarify that Definition 3.1 does not rely on whether $Y_t = Y_{t'}$ in a literal variable sense. In our framework, $Y_t$ and $Y_{t'}$ are **time-indexed reward variables** that represent the same underlying outcome measured at different time steps (e.g., blood sugar level at $t=1$ vs. $t=5$). This is conceptually distinct from comparing entirely different variables (e.g., blood sugar vs. LDL cholesterol), which would require a different notation or modeling framework altogether—such as defining a multi-dimensional outcome vector or using separate variables like $Y_t$ and $W_{t'}$.\n\nOur setting assumes a consistent reward semantics across time, and non-stationarity is defined in terms of shifts in the **distribution** of this time-indexed reward under identical interventions. Thus, Definition 3.1 remains valid even when $Y_t \\neq Y_{t'}$ as variable names—because what matters is whether their conditional distributions under the same intervention remain invariant (e.g., $P(LDL_1 \\mid \\operatorname{do(statin_1)}) = P(LDL_5 \\mid \\operatorname{do(statin_5)})$. \n\nScenarios involving fundamentally different outcomes across time are outside the scope of our current formulation.\n    \n> Can authors explain the necessity of Assumption 3.3?\n    \nThank you for this thoughtful question. We introduced Assumption 3.3 to define **a normal-form NS-SCM-MAB setting**, where non-stationarity arises due to continuous information propagation across time. This assumption ensures that the temporal causal model is connected from $t = 1$ to $t = T$, enabling a clean theoretical characterization of how information and intervention effects evolve over time.\n    \nThis structural connectivity serves as a necessary formal prerequisite for the theoretical and conceptual formulation of temporal POMIS$^+$ sets, which are designed to capture how early interventions influence future rewards across time. Without this assumption, the temporal graph may decompose into disconnected components, making it unclear whether a coherent intervention sequence can or should be optimized over the entire horizon.\n    \nHowever, we emphasize that our method remains valid even when Assumption 3.3 does not hold. In such cases, the environment effectively reduces to a set of **disconnected subgraphs**, each of which can be handled independently using our proposed approach. This corresponds to **solving separate causal bandit problems** **over each segment of the time horizon** where information is locally propagated.\n    \nTherefore, Assumption 3.3 rather serves to define the expressive setting in which our theory and algorithm can be jointly applied over the entire time horizon. We will revise the text to make this intention clearer and to highlight the flexibility of our method beyond this assumption. We hope this response addresses your concern. Should you have any further questions or require additional clarification, we would be glad to elaborate."}, {"review_id": "OHnvpKlSWt", "reviewer": "Reviewer_Jv4n", "summary": "The paper studies a setting of the multi-armed bandit (MAB) problem with causal structure, where the environment is non-stationary, unlike in previous work. The author formally introduces the non-stationary SCM-MAB framework using a graphical representation. The main contribution of the paper is to reduce the size of the action space by removing the actions that could never be optimal. To achieve this, the authors extend the classic result of Lee and Bareinboim (2018) to their setting.", "questions": "1- Could you elaborate on the points noted in the section above? Specifically, what are the new technical contributions and challenges that your work addresses?\n\n2- The computational complexity of Algorithm 1 is exponential in the number of nodes. For large-scale graphs, this makes the algorithm impractical. How flexible are your results for extension to parametric SCMs (e.g., linear models)?", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper addresses an interesting problem in the causal bandit literature and provides solid theoretical analysis. However, I am concerned about the novelty and contribution of the work. The main contribution appears to be identifying the best possible action by extending results from Lee and Bareinboim (2018). It does not seem that this extension is particularly challenging.\nFurthermore, the paper provides neither a worst-case nor an instance-optimal regret guarantee with respect to the SCM. Of course, if we treat POMIS⁺ as independent arms, we could bound the regret using the classic bounds of KL-UCB or Thompson sampling, but there is no discussion of the optimality of this approach.", "was_revised": true, "final_justification": "Overall, I agree that the problem and its motivation are important. The extension from non-stationary bandits to causal bandits is also novel. However, I'm still not convinced that the only practical use of the causal graph is to prune a subset of actions offline, after which a standard bandit algorithm is applied. That’s why I still lean toward rejection, although I have increased my score from 2 to 3.", "rebuttal": "> I am concerned about the novelty and contribution of the work. The main contribution appears to be identifying the best possible action by extending results from Lee and Bareinboim (2018). It does not seem that this extension is particularly challenging.\n\n> Could you elaborate on the points noted in the section above? Specifically, what are the new technical contributions and challenges that your work addresses? \n\nThank you for the thoughtful comment. We would like to take this opportunity to clarify how our work differs from prior approaches. Although inspired by the structural causal bandit framework of [1], our approach constitutes distinct challenges going beyond a mere extension.\n\n- Original POMIS  [1]: Identifies **a possibly-optimal set of variables** to intervene on at a single time step, assuming a stationary causal model where the causal structure and reward distribution remain fixed over time.\n- Our NS-SCM-MAB framework: Identifies a possibly-optimal **sequence of intervention sets** across multiple time steps, under a non-stationary causal model where the causal structure and reward mechanisms evolve over time.\n\nTo aid clarity, we begin by explicitly highlighting the limitations of the previous framework [1] before introducing our own. These limitations are clearly illustrated in the motivating example provided in `Section 3.1`. As shown in **Figure 4(a)**, the existing method **fails to select the essential variable** $X_1$, leading to a policy that **fails to converge**, even as the number of trials increases. This demonstrates that neglecting long-term causal dependencies can cause interventions to fail and result in **substantial performance degradation**.\n\nThe core challenge in the NS-SCM-MAB setting is not simply increased difficulty—it requires more granular, graph-theoretically grounded control over how interventions impact future outcomes. To preserve optimality across time-indexed rewards $Y_t$, we introduce the concept of POMIS$^+$, which explicitly incorporates both immediate and temporally propagated effects. To support this, we develop **two new graphical tools**, **IB$^+$ and QIB**, and prove that their union is sufficient to satisfy the POMIS$^+$ condition (Proposition 5.1).\n\nA further challenge lies in the need to **enumerate all valid intervention sequences**, not just identify a POMIS$^+$ set for a single $Y_t$. This motivates our second major contribution: a recursive algorithm, grounded in Proposition 5.1, that is **provably sound and complete** in generating all admissible sequences composed of POMIS$^+$ sets. The level of structural and combinatorial rigor required here goes significantly beyond what prior approaches have attempted.\n\nTo our knowledge, **no existing method**—including those developed for dynamic or non-stationary bandit problems—provides a principled framework for **characterizing or computing optimal intervention sequences** under evolving causal structures. Addressing this challenge necessitates a **fundamentally new approach**, encompassing novel theoretical results (e.g., Theorem 4.1), new graphical tools, and a recursive construction method (`Section 5`)—all of which represent substantial departures from previous work.\n\nWhile our approach is inspired by prior research on causal bandits, we now recognize the importance of **more clearly articulating** how our formulation advances those ideas—particularly with regard to modeling assumptions, temporal graph structure, and the scope of intervention planning. We appreciate your suggestion, and we will ensure that these distinctions and contributions are more prominently highlighted in the revised manuscript.\n\n[1] Lee, S., & Bareinboim, E. (2018). Structural causal bandits: Where to intervene?. Advances in neural information processing systems, 31.\n\n> Furthermore, the paper provides neither a worst-case nor an instance-optimal regret guarantee with respect to the SCM. \n\n> Of course, if we treat POMIS$^+$ as independent arms, we could bound the regret using the classic bounds of KL-UCB or Thompson sampling, but there is no discussion of the optimality of this approach.\n \nIf one aims to minimize regret while accounting for dependencies among arms, it would require modeling the underlying SCM in its canonical form—i.e., representing the exogenous variables and their structural mappings [2]. However, this is not our primarily concern.\nOur goal is not to exploit inter-arm statistical dependencies for regret minimization, but rather to leverage structural properties of the causal diagram to reduce the intervention space. By identifying POMIS$^+$ sets via IB$^+$ and QIB from the observed causal graph $\\mathcal{G}$, we propose a principled, SCM and causal graph based method for pruning the action sequence space prior to any bandit algorithm.\n\nThe regret behavior of downstream algorithms can then be analyzed using existing regret bounds, applied to the reduced action space defined by POMIS$^+$. This **modular design** is a key advantage of our framework: rather than modifying the exploration procedure itself, it offers a **causally grounded narrowing of the intervention space** that can be used in conjunction with any standard bandit algorithm. While this does not alter the asymptotic regret class, the practical regret may be significantly lower—since regret bounds often scale with the size of the action set, and POMIS$^+$ helps restrict it meaningfully.\nWe will revise the manuscript to clarify this distinction and avoid confusion about the intended scope of our contribution.\n\n[2] Zhang, J., Tian, J., & Bareinboim, E. (2022). Partial counterfactual identification from observational and experimental data. In *International Conference on Machine Learning* (pp. 26548-26558). PMLR.\n\n> The computational complexity of Algorithm 1 is exponential in the number of nodes. For large-scale graphs, this makes the algorithm impractical. How flexible are your results for extension to parametric SCMs (e.g., linear models)? \n\nWe appreciate the concern regarding scalability, and we would like to take this opportunity to clarify the scope and practicality of our approach.\n\nOur method is designed as an **offline phase** for structural causal reasoning, performed prior to any bandit algorithm or online reward learning. The primary goal of Algorithm 1 is to identify possibly optimal intervention sequences using **purely graphical criteria**, without requiring any knowledge of the underlying functional mechanisms or noise distributions of the SCM.\n\nThis is made possible because our algorithm builds on graphical tools such as **do-calculus**, IB$^+$, and QIB, which operate entirely at the level of the causal graph $\\mathcal{G}$—a structural abstraction of the SCM. In other words, intervention sets are selected based on **causal dependencies encoded in** $\\mathcal{G}$, not by computing interventional distributions such as $\\mathbb{E}\\bigl[Y \\mid \\operatorname{do}(\\mathbf{x})\\bigr]$.\n\nTherefore, even when the SCM is assumed to be linear, **the underlying causal graph typically remains unchanged**. As a result, the complexity of enumerating intervention sequences remains exponential, regardless of whether the SCM is linear or nonlinear. That is, the computational challenge arises from the size of the search space induced by the causal structure—not from the complexity of evaluating parametric models.\n\nImportantly, the graph-based reasoning we adopt is highly **practical and general**—especially in domains where full parameterization of the SCM is unavailable or hard to estimate. For example, while it may be difficult to precisely learn structural equations, the causal graph is often more readily obtainable (e.g., via data-driven causal discovery) or can be hypothesized based on domain knowledge. In such settings, our method offers a robust and assumption-light solution that avoids reliance on strong parametric forms.\n\nIn practice, there are also opportunities to reduce the computational burden by leveraging **repeated graph structures**. For example, in many real-world environments, the underlying causal diagram exhibits **periodically repeating non-stationary patterns** over a fixed time window $\\tau$. This reflects settings where structural shifts occur cyclically—such as seasonal changes in recommendation systems or periodic maintenance cycles in industrial processes.\n\nIn such cases, once an optimal intervention sequence is computed for the first $\\tau$ time steps, the same sequence (or its variants) can be reused in subsequent cycles. This makes the **effective time complexity depend only on** $\\tau$, rather than the total episode length $T$. Although the complexity remains exponential in $\\tau$, the reduction in effective horizon can significantly improve scalability in practice.\n\nWe will incorporate this clarification into the revision to reflect how structure-level regularities—common in real-world applications—can help mitigate worst-case complexity while retaining theoretical guarantees."}, {"review_id": "DiDcFKKEtP", "reviewer": "Reviewer_KTWZ", "summary": "This paper introduces a non-stationary causal bandit framework that models evolving causal mechanisms over time. The authors propose POMIS+, a method to identify interventions that optimize both immediate and long-term rewards by analyzing temporal propagation effects. . Experiments show improved performance over myopic baselines in dynamic environments.", "questions": "I have some questions for authors:\n\nAssumption 3.1 implies that transition edges may exist only between consecutive time slices (i.e., first-order). I am not exactly sure why this assumption is needed in the first place—why POMIS+ can still be used when this assumption does not hold, just by increasing the length of the causal diagram window. If otherwise, can you explain what is the actual reason behind this assumption other than reducing computational issues?\n\nAlso, regarding Assumption 3.3, why must information propagation occur at every time step? What if this does not hold for consecutive time steps where information propagation does not occur? Will the proposed method fail to handle this case, or will it still work?\n\nHow scalable is the proposed algorithm? For bigger causal graphs with multiple sources of information propagation across time steps, will it be able to effectively identify the POMIS+?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Summary of Contributions: The paper has three main contributions:\n(1) a novel framework integrating structural causal models with non-stationary bandits for principled modeling of evolving causal mechanisms; (2) the POMIS+ method, which captures the existence of variables that contribute to maximizing both immediate and long-term rewards; and (3) comprehensive experimental validation demonstrating POMIS+'s superior performance in capturing long-term effects compared to myopic POMIS baselines across three distinct test settings.\n\nCritique:\nThe main limitations of the proposed work are the assumptions. The identical time-slice structure assumption (Assumption 3.2) may restrict real-world applicability. Furthermore, Assumption 3.1's constraint that transition edges exist only between consecutive time slices could be overly restrictive in practice. The paper would benefit from a more thorough justification of these assumptions, particularly regarding why Assumption 3.1 is necessary.\n\nOverall Assessment:\nDespite these limitations, the paper is technically solid and makes several meaningful contributions. I therefore recommend acceptance.", "was_revised": true, "final_justification": "I thank the reviewer for the detailed response to my questions. Including some discussion from the response will improve the manuscript. I will keep score for the paper.", "rebuttal": "> Assumption 3.2 may restrict real-world applicability.\n\nThank you very much for bringing this to our attention. We agree that Assumption 3.2 may indeed limit applicability in certain real-world scenarios. For example, in domains such as healthcare or industrial control systems, the underlying causal graph  $\\mathcal{G}\\bigl[\\mathbf{V}_t\\bigr]$ may evolve over time due to policy changes or system reconfigurations—such as changes in causal relationships between variables.\n\nIn fact, our method remains valid even when Assumption 3.2 is relaxed, allowing for such structural changes. This is because identifying POMIS$^+$ at each time step $t$ only requires access to the ancestral graph of $Y_t$ — i.e., $\\mathcal{G}\\bigl[An(Y_t)\\bigr]$. Therefore, our proposed Algorithm 1 (\"Computing all intervention sequences\") remains sound and complete even when this assumption is relaxed.\n\nThe reason we initially adopted this assumption was that it aligns with a natural form of traditional non-stationary bandit in our setting—where causal dependencies may change over time *through the presence of transition edges*, which encode the propagation of information across time. This modeling choice aligns with prior work, such as Aglietti et al. [1], which makes a same Assumption 1.1 in the context of dynamic causal optimization in the time series manner.\n\nWe discuss this assumption further in `Appendix L`. Due to space limitations, we were unable to include this discussion in the main body, but we will be sure to incorporate it in the camera-ready version to improve clarity.\n\n[1] Aglietti, V., Dhir, N., González, J., & Damoulas, T. (2021). Dynamic causal Bayesian optimization. *Advances in Neural Information Processing Systems*, *34*, 10549-10560.\n\n> Assumption 3.1's constraint that transition edges exist only between consecutive time slices could be overly restrictive in practice.\n\n> The paper would benefit from a more thorough justification of these assumptions, particularly regarding why Assumption 3.1 is necessary. \n\nThank you for raising this important point. You are right that Assumption 3.1 “Time-slice Markov'”—that transition edges exist only between consecutive time slices—could be restrictive in real-world scenarios and our proposed method can still be used if the assumption does not hold.\n\nIn traditional structural causal models (SCMs), temporal behavior is captured via topological ordering (i.e., causal order) over nodes in the graph, which we might interpret as a notion of time. This is a traditional Markovian property. However, in our setting—non-stationary structural causal bandits—the agent operates in a repeated decision-making scenario where each time step corresponds to a separate episode. Therefore, a purely topological interpretation of time is insufficient. We require a more explicit representation of temporal transitions to account for how causal influence propagates across real time steps.\n\nThis is why we formally introduce the notion of “**time-slice Markov”** as Assumption 3.1—where transitions are constrained to flow between adjacent slices (i.e. first-order Markov). It serves as a practical way to simplify temporal modeling while preserving clarity of the time series. We also define its counterpart, “**semi time-slice Markov”**, in `Appendix G` ”Semi Time-Slice Markovian Non-Stationary SCM-MAB”, inspired by the classical notion of semi-Markovian graphs (i.e., DAGs with latent confounding represented by bidirected edges). Initially, we restricted “semi time-slice Markov” to cases involving latent confounding between two time steps—i.e., Dynamic Unobserved Confounders (DUC).\n\nHowever, your insightful question made us realize that **any violation of the first-order transition assumption—including observed, long-range dependencies across time—should also be captured under the broader semi-Markov category**. We appreciate this clarification and will revise the appendix to include these cases, while ensuring that the main text clearly states that our proposed methods remain valid under the relaxed Assumption 3.1 (Semi Time-slice Markov). This clarification helps reduce potential confusion about the role of Assumption 3.1 and makes the paper more precise and complete—thank you again for your valuable feedback.\n\n***Questions:***\n> Assumption 3.1 implies that transition edges may exist only between consecutive time slices (i.e., first-order).  I am not exactly sure why this assumption is needed in the first place—why POMIS$^+$ can still be used when this assumption does not hold, just by increasing the length of the causal diagram window. If otherwise, can you explain what is the actual reason behind this assumption other than reducing computational issues?\n\nThank you for your thoughtful follow-up question. As we discussed in our response to your earlier comment on Assumption 3.1, the constraint that transition edges exist only between adjacent time slices (i.e., first-order) is not required for the correctness of our method. POMIS$^+$ can still be applied when this assumption does not hold, including in cases involving longer-range or non-local temporal dependencies such as n-th order cases.\n\nThe reason we introduce Assumption 3.1 is not to enforce a limitation, but to provide an interpretable *temporal* abstraction. In our non-stationary bandit setting, episodes unfold in real time, and thus we explicitly model temporal transitions across slices. By assuming a first-order structure, we simplify both exposition and implementation without losing generality. As clarified above, our method remains valid under a broader “semi time-slice Markov” condition, which we will expand on in `Appendix G` to include cases beyond the first-order. We appreciate your comment, as it helped us better articulate the generality of our assumptions.\n\n> Regarding Assumption 3.3, why must information propagation occur at every time step?What if this does not hold for consecutive time steps where information propagation does not occur? Will the proposed method fail to handle this case, or will it still work?\n\nThank you very much for your accurate reading of our paper and for raising this insightful question.\n\nTo directly address your concern: **our proposed method still works even if Assumption 3.3 does not hold**. However, when information propagation does not occur across certain time steps (i.e., the transition edges are missing between some time-slices $\\mathbf{V}_{t}$ and $\\mathbf{V}_s$ where $t \\neq s$), the temporal structure becomes disconnected, and we consider the environment as the separated non-stationary SCM-MABs. If the information propagation does not occur across all time steps , we may have stationary graphs which illustrated in Lee and Barenboim [2]. In such cases, we apply our method **separately** to each connected segment of the causal graph.\n\nFor instance, consider a scenario where $t = \\lbrace 1,2,3,4 \\rbrace$ and the structure is such that $\\mathbf{V}_{1} \\rightarrow \\mathbf{V}_2$, there are **no** transition edges between $\\mathbf{V}_2$ and $\\mathbf{V}_3$, and then $\\mathbf{V}_3 \\rightarrow \\mathbf{V}_4$. In this case, our algorithm can still be used by running it independently on each segment: $\\mathcal{G} \\bigl[ \\mathbf{V}_1 \\cup \\mathbf{V}_2 \\bigr]$ and $\\mathcal{G}\\bigl[ \\mathbf{V}_3 \\cup \\mathbf{V}_4 \\bigr]$. Conceptually, this corresponds to handling **two independent non-stationary decision-making problems**.\n\nWhile a user of the algorithm could reasonably manage such cases in practice, we introduced Assumption 3.3 to define a *normal-form* NS-SCM-MAB setting. We acknowledge that this may have caused confusion, and we appreciate your feedback—it will help us clarify the scope and flexibility of our method in the final version. We will make sure to incorporate this clarification into the main text to prevent the confusion occurred from Assumption 3.3.\n\n[2] Lee, S., & Bareinboim, E. (2018). Structural causal bandits: Where to intervene?. *Advances in neural information processing systems*, *31*.\n\n> How scalable is the proposed algorithm? For bigger causal graphs with multiple sources of information propagation across time steps, will it be able to effectively identify the POMIS$^+$?\n\nThank you for the excellent question. We agree that the scalability of our algorithm is inherently tied to the complexity of the causal graph, particularly when there are multiple sources of information propagation across time steps. Since our method is based on **graphical criteria alone**, the size of the graph—and in particular, the number of nodes and transition edges—can impact the computational cost of identifying POMIS$^+$ sets.\n\nHowever, we emphasize that our algorithm is designed to operate as an **offline preprocessing step**, performed prior to any online decision-making or reward learning. This separation allows the intervention search to be done once, and reused thereafter.\n\nMoreover, in many real-world applications, the temporal causal graph exhibits **repeated or modular structure**—for instance, environments where the graph evolves periodically over a fixed time window $\\tau$ (e.g., weekly behavior cycles or seasonal effects). In such cases, we only need to compute optimal intervention sets within this repeating window. Once identified, the same POMIS$^+$ sequence (or a variant) can be **reused across cycles**, substantially reducing the effective computation cost in practice. We will revise the paper to make this practical consideration clearer and to highlight how recurring structural patterns can mitigate computational challenges in real settings."}, {"review_id": "dZZlCQ0EZW", "reviewer": "Reviewer_4V3R", "summary": "This paper studies sequential decision making where rewards may be correlated through unobserved counfounders and across time. The relationship between variables are described through a temporal causal graph. The authors propose the POMIS+ approach, which allows to determine variables that contribute to maximizing immediate and future rewards, and test its performance in a numerical experiment.", "questions": "- What practical situations could be effectively modelled by your framework? \n\n- Adversarial bandit theory is able to deal with arbitrarily complex reward structures. Although your non-stationary causal framework is certainly able to capture complex reward dynamics, it seems hard to obtain meaningful convergence results, as opposed to adversarial bandit theory for which several sharp theoretical results have been derived. What are the advantages of your method as compared to the adversarial bandit literature?", "limitations": "I think this article could be of interest, however it is hardly legible in its current format because it is too complex and compact. I think that a conference like Neurips is not a good match for such a study: a specialized journal, where the authors would have more space to elaborate on their framework and its advantages would be better. I therefore lean towards rejecting it.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "STRENGTHS:\n\n- The framework is interesting is new.\n- The authors did a great job putting the evolving causal environment in perspective with the existing literature in the supplementary material.\n\nWEAKNESSES:\n\n- The pratical interest of the framework is not sufficiently highlighted. \n\n- I think the framework developed in this paper is too complicated and general for a conference paper. This comes with two inconvenients. \n\nFirst, there are a lot of heavy notations which hamper the legibility of the paper: section 2 introduces too many concepts and notations without enough explanation in my opinion (manipulative vs non manipulative, which adds to endogenous vs exogenous variables...), and too many definitions (among which IB and QIB, which are quite intricate) are introduced after that. In my opinion, the 9 pages format is not suited for introducing such a complex machinery. \n\nSecond, the framework is too general for sharp theoretical insights to be derived, although assumption 3.1 and 3.2 significantly narrow it (which begs the question: why being so general before introducing such assumptions?). From my understanding, the results established in this paper are rather weak: they are limited to the existence of an optimal partial assignement (theorem 4.1), the fact that POMIS+ is Markovian (proposition 4.1)---which seems a natural consequence of assumption 3.1 indeed---, characterization of POMIS+ via QIB (proposition 5.1) which I don't find really insightful.\n\nI must admit that in spite of having carefully readed the paper, I haven't understood well its main points (in spite of being rather knowledgeable in bandit theory and acquainted with causality). I think this is because it is too complicated and compact: a specialized journal should be a better match for this work.", "was_revised": true, "final_justification": "I am largely convinced by the additional clarifications they provided regarding the motivation and relevance of the proposed framework. In particular, I agree that applications involving sensitive policy-making require an understanding of complex causal structures, rather than simply adapting to observed payoff variations.\n\nWhile I still find the proposed framework somewhat overly complex, and the results not particularly sharp, I recognize the potential value in laying the foundations for a new line of theoretical research. I appreciate the authors' effort to position their work as a step toward broader developments within the community.\n\nIn light of the authors’ commitment to better motivate their framework and improve the presentation—especially when introducing new concepts—I have decided to increase my score from 3 to 4.", "rebuttal": "> The pratical interest of the framework is not sufficiently highlighted.\n\nThank you for this valuable observation. We acknowledge that the practical value of our framework may not have been emphasized sufficiently in the initial submission and appreciate the opportunity to clarify.\n\nOur work is directly motivated by real-world decision-making scenarios where both **reward dynamics and underlying causal relationships evolve over time**—for example, in healthcare, where a sequence of treatments affects future patient outcomes through time-varying physiological mechanisms, or in education, where pedagogical interventions affect learning trajectories in temporally dependent ways.\n\nClassical bandit algorithms (stationary or non-stationary) often treat temporal variation as a statistical artifact, whereas structural causal bandits focus on the reward shift that occurs due to an evolving causal structure. This leads to **non-myopic strategies** that are critical in domains where interventions have delayed or cumulative effects.\n\nWe will revise the manuscript to include concrete real-world motivating examples (e.g., time-evolving treatment planning in healthcare) and better highlight how our algorithm can guide decision-making in these settings.\n\n> there are a lot of heavy notations which hamper the legibility of the paper: ...\n\n`Section 2` **introduces several foundational concepts and notations** that may initially appear dense or abrupt. Our intention was to formally define the setting with precision, especially given the layered nature of the non-stationary SCM-MAB framework. In particular, we will add brief examples when defining manipulable and exogenous variables. We believe that improving the exposition in `Section 2` will enhance the overall accessibility and clarity of the paper.\n\n> The framework is too general for sharp theoretical insights to be derived, although assumption 3.1 and 3.2 significantly narrow it.\n\n> the results established in this paper are rather weak : they are limited to the existence ..\n\nThank you for your concerns. We respectfully disagree with the characterization that our results are limited to the three components you listed. In fact, the **main contribution of our work lies not just in each result (e.g., Propositions, Theorems, and Definitions) taken individually, but also in how these components are carefully integrated to enable the systematic construction and enumeration of all valid intervention sequences over time.** No existing solution or algorithm can construct these intervention sequences.\n\nTheorem 4.1 (Existence), Proposition 4.1 (Temporal dependency of POMIS$^+$), and Proposition 5.1 (graphical characterization via QIB and IB$^+$) are **not standalone contributions**, but rather serve as the **theoretical backbone for Algorithm 1**, which is our central result. This algorithm is not a heuristic or sampling procedure—it is a **sound and complete method** that exhaustively enumerates **all possibly-optimal sequences** of interventions across multiple time steps, based purely on structural properties of the causal graph.\n\nTo demonstrate the limitations of applying existing stationary algorithms [1] without our algorithm enumerating sequences, we present a concrete failure case in our motivating example (`Section 3.1`). As shown in **Figure 4(a)**, applying a method designed under stationary assumptions leads to the exclusion of a crucial variable, $X_1$, from the intervention set. As a result, the learned policy **fails to converge entirely**, even as the number of trials increases. This outcome clearly illustrates that **ignoring temporally extended causal dependencies can result in significant performance degradation**.\n\nAchieving this required more than technical derivations: we had to redefine the intervention problem under non-stationary causal dynamics (Definition 3.1), develop novel graphical tools (Definition 5.1 and 5.2, based on Theorem 4.1), and formalize their compositional structure across time (Algorithm 1 and Theorem 6.1). These results are deeply interdependent and were **designed as a unified framework** to support principled, structure-aware sequential decision-making in evolving environments.\n\nTo the best of our knowledge, **no prior work** has offered a formal mechanism to construct all such valid intervention sequences in non-stationary causal settings. We will revise the manuscript to better emphasize how the results you mentioned contribute jointly to this broader and more impactful goal. Thank you again for prompting this clarification.\n\n[1] Lee, S., & Bareinboim, E. (2018). Structural causal bandits: Where to intervene?. Advances in neural information processing systems, 31.\n\n> too many definitions (among which IB and QIB, which are quite intricate) are introduced after that. In my opinion, the 9 pages format is not suited for introducing such a complex machinery.\n\n> A specialized journal should be a better match for this work.\n\nWhile we appreciate the suggestion, we believe our work is well aligned with the NeurIPS community. The problem of planning optimal intervention sequences under evolving causal structures sits at the intersection of causal inference, sequential decision-making, and graphical modeling—core topics of interest at NeurIPS.\n\nRecent NeurIPS papers, such as [2–4], reflect the community's engagement with structurally rich, causally informed decision frameworks. We also made an effort to ensure accessibility: rather than presenting definitions upfront, we begin with a motivating example in Section 3.1 that naturally introduces the core challenges and guides the reader toward the formal concepts (e.g., POMIS$^+$, QIB). We ensure that the final version will be made contributions even clearer.\n\n[2] Kumor, D., Zhang, J., & Bareinboim, E. (2021). Sequential causal imitation learning with unobserved confounders. *Advances in Neural Information Processing Systems*, *34*, 14669-14680.\n\n[3] Elahi, M. Q., Ghasemi, M., & Kocaoglu, M. (2024). Partial structure discovery is sufficient for no-regret learning in causal bandits. *Advances in Neural Information Processing Systems*, *37*, 109066-109100.\n\n[4] Zhang, J., & Bareinboim, E. (2022). Online reinforcement learning for mixed policy scopes. *Advances in Neural Information Processing Systems*, *35*, 3191-3202.\n\n***- Questions:***\n    \n> What practical situations could be effectively modelled by your framework?\n    \nOur framework is designed for sequential decision-making problems where both the reward distribution and the underlying causal structure change over time, and where **long-term causal reasoning** is essential.\n    \nOne example is longitudinal healthcare, where early treatments can influence future health outcomes via time-delayed pathways. For instance, prescribing a medication today (e.g., $X_1$) may affect not only immediate outcomes ($Y_1$) but also downstream outcomes ($Y_2$, $Y_3$, ...) through intermediate variables—captured by temporal causal dependencies in our model. Our framework enables the identification of **non-myopic intervention sequences** that account for such evolving structures.\n    \nSimilarly, in education or public policy, early-stage interventions (e.g., tutoring, incentives) can have delayed and structurally mediated impacts. In these settings, modeling time-varying causal dependencies is critical to designing effective long-term strategies under limited budgets.\n\nWe will clarify and emphasize these practical implications in the revision.\n    \n> Adversarial bandit theory is able to deal with arbitrarily complex reward structures. ... What are the advantages of your method as compared to the adversarial bandit literature?\n    \nThank you for this question. We agree that adversarial bandit theory provides strong regret guarantees under general and worst-case reward sequences. However, our work is driven by a fundamentally different goal: rather than merely adapting to changing reward dynamics, we aim to understand and utilize the **causal mechanisms** that generate them. While adversarial models treat non-stationarity as arbitrary or even adversarial, our framework explains it as the result of structured causal processes unfolding over time. This distinction allows our method to reason about how and why rewards change and to plan interventions accordingly. We mentioned this in `Appendix F`.\n    \nIn particular, our framework enables **non-myopic planning** by identifying early interventions that have delayed effects via temporal causal paths. It also supports **mechanism-based explanations** of reward shifts (e.g., through transition edges in the causal graph), rather than relying solely on statistical drift. This structure is especially relevant in domains where intervention planning and interpretability are critical, such as healthcare, education, and policy-making—areas where blindly adapting to reward trends without causal understanding may be insufficient or even harmful.\n    \nAlthough adversarial bandits offer sharper theoretical guarantees in worst-case settings, they typically do not incorporate causal knowledge and cannot inform **targeted interventions** grounded in the system’s structure. In contrast, our approach builds on the assumption that such structure (e.g., causal graphs) is either known or hypothesized, and leverages it to constrain the space of intervention sequences. Once this causal abstraction is in place—e.g., via the POMIS$^+$ sets—**any bandit algorithm**, including those developed for adversarial settings, can be used on top. In this sense, our contribution serves as a **causal decision-theoretic layer** that enhances interpretability and long-term planning, rather than replacing regret-minimizing solvers.\n    \nWe will revise the manuscript to better highlight this distinction and the complementary nature of our framework with respect to existing bandit approaches."}]

Author rebuttal:

Meta-review: The authors propose an extension of the POMIS framework to time-series data. They do this in the context of non-stationary causal bandit algorithms. The scores are mixed and the paper as it stands currently is borderline. 

Applying POMIS on the time-unfolded graph does make sense. The technical contribution in this sense may be limited. The insight that comes with it is valuable: Intervene a priori and clamp down that intervention to identify the optimal arm later. 

Some concerns of critical reviewers I do not agree with: Assumptions 3.1 and 3.2 seem sensible to me. I am pretty sure 3.1, especially, can be relaxed without many issues. I also am not concerned about practical utility as this is a fundamental contribution. The lack of regret bound is a valid concern. The causal structure certainly could have been used in other ways instead of only pruning the action space, but this is not grounds for rejection.
Decision: Accept (poster)