Reward-oriented Causal Representation Learning
Authors: Zirui Yan
Emre Acartürk
Ali Tajer
Venue: NeurIPS 2025 poster ()
Keywords: causal representation learning
causal bandit
reward-oriented
Primary area: probabilistic_methods
TL;DR: Causal representation learning for downstream tasks (formalized as reward), with algorithms and regret bounds.

Abstract: Causal representation learning (CRL) is the process of disentangling the *latent* low-dimensional causally-related generating factors underlying high-dimensional observable data. Extensive recent studies have characterized CRL identifiability and *perfect* recovery of the latent variables and their attendant causal graph. This paper introduces the notion of *reward-oriented* CRL, the purpose of which is to move away from perfectly learning the latent representation and instead learning it to the extent needed for optimizing a desired downstream task (reward). In reward-oriented CRL, perfectly learning the latent representation can be excessive; instead, it must be learned at the *coarsest* level sufficient for optimizing the desired task. Reward-oriented CRL is formalized as the optimization of a desired function of the observable data over the space of all possible interventions and focuses on linear causal and transformation models.  To sequentially identify the optimal subset of interventions, an adaptive exploration algorithm is designed that learns the latent causal graph and the variables needed to identify the best intervention. It is shown that for an $n$-dimensional latent space and a $d$-dimensional observation space, over a horizon $T$ the algorithm's regret scales as $\tilde O(d^{\frac{1}{3}}n^{\frac{1}{3}}u^{\frac{2}{3}}T^{\frac{2}{3}} + u\sqrt{T})$, where $u$ measures total uncertainty in the graph estimates. Furthermore, an almost-matching lower bound is shown to scale as $\Omega(d^{\frac{1}{3}}n^{\frac{1}{3}}p^{\frac{2}{3}}T^{\frac{2}{3}} + p\sqrt{T})$, in which $u$ is replaced by $p$ that counts the number of causal paths in the graph.

Reward-oriented Causal Representation Learning
Zirui Yan"
Emre Acartürk' Rensselaer Polytechnic Institute acarte0rpi. edu
Rensselaer Polytechnic Institute yanzl1@rpi.. edu
Ali Tajer
Rensselaer Polytechnic Institute tajerßecse eejeerecse.rpi.eee. rpi.
Abstract
Causal representation learning (CRL) is the process of disentangling the latent low-dimensional causally-related generating factors underlying high-dimensional observable data. Extensive recent studies have characterized CRL identifiability and perfect recovery of the latent variables and their attendant causal graph. This paper introduces the notion of -oriedtoe CRL, the purpose of which is to move away from perfectly learning the latent representation and instead learning it to the extent needed for optimizing a desired downstream task (reward). In oriented CRL, perfectly learning the latent representation can be excessive; instead, it must be learned at the coarsest level sufficient for optimizing the desired task. neward-orienter CRL is formalized as the optimization of desired function of the observable data over the space of all possible interventions and focuses on linear causal and transformation models. To sequentially identify the optimal subset of interventions, an adaptive exploration algorithm is designed that learns the latent causal graph and the variables needed to identify the best intervention. It is shown that for an n--dimensional latent space and d-dimensional observation space, over horizon T the algorithm's regret scales O(d n u T + uvT),, where u measures total uncertainty in the graph estimates. Furthermore, an almost- matching lower bound shown to scale as ((d's p T + P)) in which u is replaced by p that counts the number of causal paths the graph.
Introduction
Consider a data-generating process which latent low-dimensional causally-related variables are mapped to observational high-dimensional data through unknown transformation. Causal repre- sentation learning (CRL) is the process of using observational data to learn the latent, unobserved generating factors, i.e., the latent variables and the latent causal graph that specifies their causal inter- actions. CRL is considered a significant step toward understanding the world by learning appropriate representations that support causal interventions, reasoning, and planning
CRL literature. There exists rich recent literature on CRL identifiability analysis - the objective of which is establishing conditions under which the latent space be recovered uniquely across various models for the latent causal model (c.g., linear, parametric, and non- non-parametric) and the unknown transformation (c.g., linear, parametric, and non-parametric). Some representative studies include 2 Aiming to establish possibilit/iipossiiiii results, the existing literature is primarily focused the asymptotic setting of access infinite number of observations, with limited studies on finite-sample guarantees [.. Specifically, we refer to 2 for the most closely related works in terms of setting and methodology.
Equual contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Learning unique, causal representation underlying the observed data is hypothesized to enable more improved and robust reasoning for downstream tasks [T. This is often encountered in technological, social, and biological domains where the observed data often lack straightforward interpretations and are generated by an unobserved data-generating mechanism with interpretable semantics.
Reward-oriented CRL. To understand the recovery limits in CRL, the existing literature has so far decoupled the CRL from the downstream objectives. This decoupling means that CRL may expend extra effort learning fine-grained details that do not contribute to the downstream objective, or conversely, lack sufficient accuracy to be useful. To address this gap, we introduce the notion of reward-oriented CRL, which directly integrates the downstream goal into the representation learning pipeline. In this paper, we consider rewards that are functions of the latent variables. Since the latent variables are not directly observable, efficient optimization of the reward may include, as a sub-task, recovering these latent representations. In this case, one would only need to learn the latent variables and graph to the coarsest level to optimize the downstream objectives. To formalize the objectives, we define a utility function that maps the latent causal system a downstream utility. This utility will be subsequently optimized over the space of possible interventions in the causal system. For example, consider a robotic arm with causally related joint variables. The arm's movements are monitored from camera images, and our downstream objective is to use these images to optimize the arm's s movements for a specific task. In such a task, achieving high placement accuracy does not require perfect recovery of all latent variables; instead, it suffices capture the critical joint relationships or to bound estimation errors below a level that leaves final task performance unaffected. Sending commands to the arm to adjust its actions is the intervention model on the underlying causal system.
Table I: Summary of results for reward-oriented CRL.
Intervention
Latent variables
Graph recovery
Regret bounds
Upper bound: Oldint r + ugVI)
soft
up to scaling & mixing
transitive closure
Lower bound:
PVT)
hard
up to scaling
perfect
Upper bound: O(dbn (idbniugr2: VLVT)
Connection to causal bandits. Optimizing utility in the latent space faces uncertainties in several ways, c.g., causal model, transformation, and probability models. Inevitably, an algorithm optimizing utility needs to explore the system to resolve these uncertainties before committing to decision. A data-adaptive exploration of interventions is intimately related to the literature on causal bandit (CB), albeit with two significant differences. First, in CB, the learner directly interacts with the causal system and observes the causal variables, a premise that does not hold in reward-oriented CRL. Second, in the CB literature, is often assumed that the causal graph's 's topology is known, which is not the case in reward-oriente CRL. Some representative studies on various causal models (e.g.. linear and non-linear) and intervention models (do, stochastic hard, and stochastic soft) include [64)
Due to these two significant differences with CB, designing reward-oriented algorithms will differ significantly from the CB algorithms by including a process that can perform CRL. This process has to perform an accurate-enougee CRL that facilitates identifying the best intervention. Hence, the CRL process we need to design differs from the existing ones that aim for perfect latent recovery.
We focus on reward-oriented CRL with (i) linear structural equation models over an n-dimensional latent causal system, (ii) linear transformations mapping to d-dimensional observations, and (iii) linear utility functions. Table summarizes the main guarantees on latent space recovery and regrer bounds until time T. where measures total uncertainty and p counts the number of causal paths. We defer the discussion of do intervention to Appendix [
Our key observations include the following.
Finite-sample identifiability. We provide finite-sample identifiability for linear SEMs, accommo- dating both stochastic soft and hard interventions. This is a critical step, since during exploration. we have access to only a finite number of samples.
Almost matching regret bounds. We establish upper and lower regret bounds for reward-oriented CRL. These bounds are specified in terms of the topology of the causal graph. Under soft interventions, these bounds match in their dependence on graph parameters and the time horizon T.
Refined bounds for causal bandits. The reward-oriented CRL framework subsumes CB by setting the latent to observation transformation to the identity function. We show that our algorithm also improves the oftte-of-the-ar regret bounds for the relevant CB settings.

---

Notations. For n E N. we define [n] _ {1.....77 n). Vectors are represented by lowercase bold letters, and element of vector v denoted by v(i]. Matrices are represented by uppercase bold letters, and we denote row and element (i,j) of matrix A by [A]; and by A f j. respectively. Moore-Penrose pseudoinverse of a matrix A is denoted by A For any matrix we denote the rank, column and null spaces of A by rank(A) A), col(A) and null( A), respectively. Il denotes the indicator function. Sets and events are denoted by calligraphic letters. The cardinality of the set A is denoted by |A], For vector x and positive semidefinite matrix A, we define ||x|| A = >vx Ax as the weighted &2 norm. The f--norms of vector x E I and matrix A are denoted by ||x||ş and ||A respectively. Finally, O is an order notation that ignores constant and poly-logarithmic factors.
2 Reward-oriented CRL Framework
Data-generating process. Consider a tata-generating process that transforms high-level, low- dimensional latent variables into low-level, high-dimensional observable data. Formally, consider a causal system represented by an unknown directed acyclic graph (DAG) G with nodes generating causally-related latent random variables Z _ [Z[1],
Z [n] These latent variables are mapped to a higher-dimensional observed data E Rd by an unknown linear transformation G E Rdxx according to X = G Z, where d 2 and G is full column rank. The set of parents and ancestors of node i [nx] are denoted by pii and an)). respectively. We denote the probability density function (pdf) of Z by p and denote the conditional pdf of Z[i] given its parent variables by (x(1t] = =([patt))) We call a permutation π = (TI....,, np) of [n] a valid causal order for all j,j E [nl, the membership i E pa(j) implies म. < Tj. We denote the maximum in-degree of G by dg and the length of its longest causal path by L. The latent causal variables are assumed to be related through a linear structural equation model (SEM) specified by Z B Z + E, where B E R=x" is the edge weight matrix and E E I" accounts for the exogenous noise, whose expected value is denoted by V & Ele]. The weight matrix B directly models the causal relations in the sense that the element B [[, is non-zero if and only if j E pa(i).
Interventions. We consider two types of intervention mechanisms: stochastic hard and soft, the distinction of which is how they impact the marginal distributions of the latent variables.
Soft intervention: As the least restrictive form of intervention, when applied to node i E In]. a soft intervention changes the conditional distribution (=(p]i] =i() to a distinct one. Equivalently, this alters the observational linear causal mechanism to an alternative one as follows:
observational:
Z = [B] Z + +
interventional: Z = BB'} 2 ++1 (1)
where [B']; denotes the vector of post-intervention edge weights, and [d]] Consequently, we define the interventional weight intervention noise with mean v [ d
e denotes the post-
matrix B as the composition of rows [B E [n]} and the mean vector as v²"
Hard intervention: As a special case of soft interventions, a hard intervention on node i removes its ancestral statistical dependence and changes (x( =(p) to a marginal distribution that is only a function of z(i). This mechanism is equivalent to setting B = O.
For simplicity of notations, throughout the analysis, assume only one intervention mechanism per node. However, this can be readily generalized to an arbitrary number as discussed in Appendix H We allow multiple nodes be intervened on simultancously and denote the space of possible interventions by A A 2|m]_ We denote the probability measure induced by the set of interventions a E A and the associated expectation by Pa and Eg, respectively.
Reward-oriented CRL. In reward-oriented CRL, the objective is to identify the set of interventions in A that maximizes an expected reward defined as a function of Z. In this paper, we focus on linear reward functions specified by U(Z)= & 0 Z EU, where E R is unknown reward parameter and EU represents utility noise term with mean 0. We denote the expected value of the utility U under intervention A by
Ha [Z) A learner's objective is to identify the optimal intervention a", denoted by
(2)
a² arg max Ula
aEA
All aspects of probability distributions, i.e., the topology of G. pre- and post-intervention matrices, and noise distributions, unknown. To identify a", the learner performs sequence of interventions
3

---

and receives feedback consisting of the observed data X and reward (2). The objective is to identify a' with the fewest number of interventions, which are selected adaptively based on the data and the collected rewards. The sequence of interventions over time is denoted by (ar E AA: : E N). Accordingly, we denote the set of the latent variables, data, and reward collected up to by
Z, _ [Z , Z,]: X, [X),...,XI]] To assess the efficiency of the learner in identifying a', we define the cumulative utility regret that it incurs relative to an oracle with access to the best intervention as
and U, &
[U(Z]).... U
(4)
T
T
RT
A
Σ( [Ua)] - (z,1)(Z))) = -aa Σ ua. 1=1
(5)
We remark that using such regret-based approach to identify a" can be naturally posed multi- armed bandit problem in which each of the 2n possible interventions can be represented by one arm. Applying vanilla bandit algorithm results in regret that scales exponentially in n, rendering regret that, even for a moderate-sized latent structure, can be highly inefficient. The objective in this paper is design algorithms that can break the exponential dependence on n by properly leveraging the intricate causal structures among the latent variables.
Identifiability metrics. Circumventing the exponential dependence of the regret on dimension and efficiently identifying a* hinge on properly recovering the latent variables Z and the underlying the core objective of CRL. Recent studies
causal graph G. both unobserved. These recoveries provide extensive identifiability guarantees for CRL - which specify conditions under which Z and can be uniquely recovered (up some uncertainty) from the observed data X. These guarantees are asymptotic, assuming access to an infinite number of samples of X. In the reward-oriented CRI, however, the decisions each time i must be based solely on & samples. To formalize the types of identifiability guarantees needed in our framework, we first speciffy the known mafinite-smppl identifiability guarantees that apply to the setting of this paper (linear SEMs and transformation), followed by their finite-sample counterparts. For this purpose, given X,, we define Gr. Zz and H; as estimates of 9, Zr, and G', respectively. We also denote the transitive closure of G by Gie- Theorem 1. Under linear SEM, linear transformation. and one intervention per node, CRL is endowed with the following infinite-sample identifiability guarantees.
(i) Hard intervention ( Theorem 21): is possible to perfectly recover G and recover Z up to scaling, i.e., 970 = G and Zix A X = CoZoe for some diagonal matrix Cn E RRxx (ii Soft intervention: It is possible to perfectly recover a transitive closure of 12) Theorem 1] and recover Z up to scaling and mixing with parents, i.e., Goe = Gre and Zoc H = Zo for some matrix Cs E Raxx such that for any given j. Cs = 0 for all & (j) U pa(j).
See Appendix E.I for details. Next, we specify sample counterparts of these identifiability statements in probably approximately correct (PAC) sense similar to (4.
Definition 1 ((c, 8)- recovery). For given t E N, the fnite-sample estimates Gr, Ż,, and H, are said to achieve (c, 8) recovery if the following statements hold with probability at least 1 1-8 5
(i) Hard intervention: G. = g and 2, H2X, -OH + Ex) Ze where Ch is a full-ank diagonal matrix, and we have | 2| < E.
(i) Soft intervention: G. = Grc and 2. H,X, (Cs + E.) Z, where Cs is a full rank matrix, for any given j. Cli. = 0 a for all i & {i} pa()) and ||x||22 I c.
Assumptions. Next, we outline the assumptions adopted for the reward-oriented CRL framework. First, we adopt the following CRI assumption (see, e.g., [2] Assumption 1(b)) and ( Assumption 1)), which ensures that the effects of an intervention can always be traced from the changes in the precision matrix (inverse covariance) of latent variables Z.
Assumption 1. An intervention on any non-root node changee row of the weight matrix, i.e., if (ii + 0 then [B], [B",,
This assumption automatically holds for hard and do interventions and is mild for soft interventions, requiring that the effect of an intervention is not limited to the exogenous noise distributions. Similar assumptions are common in the CRL literature and can effectively be interpreted as requiring that the statisties we use be non-degenerate. Next, we provide Selaerl assumptions that are standard in the causal bandit literature (21.

---

Assumption 2 (Weight matrices), Matrices B and B' and the utility parameter are unknown but have finite entries with known ranges. We denote the range of these entries by mB E SRt,, i.e. [B(i,j]| & mn, [B [i:5]] I mn, and [0[i]] S mB for all i, E [n].
Assumption 3 (Noise model). We assume that the statistical models for the noise v and v² are unknown and bounded. We define the m E Rt to specify the range of noise terms, i.e. |<x & m, for all i E [n] and t [T]. Finally, we assume the utility noise Eu is Saub-Gasssinn.
For simplicity in the presentation and without loss of generality, we set m my = 1. An immediate conclusion of Assumptions 2 and 3 that Z is bounded, i.e., 2| m for some E I....
weight matrices B,B
(a, s [i]
latent variable Z, transtormation G
DAG g
observation X,
DAG estimate G
CRL pesstiion muirioos
wright matrices estimates
A. A
latent estimates
H2 estimatee of Gt
CB: UBB-uoed solection
Bc41
Figure I: Schematic Pipeline of RO-CRL
3
Reward-oriented CRL Algorithm
Now we introduce the Neward-orientee Causal Representation Learning algorithm (RO-CRL) for hard and soft intervention. The pseudocode is provided Algorithm T Appendix [
3.1 Algorithmic Overview & Key Properties
Identifying the best intervention a" defined in (3) requires estimating the expected utility under 2 distinct statistical models associated with 2" possible intervention combinations E A. The key to breaking the exponential dependence of the number estimation routines we have to perform on is leveraging the intricate connection among all the 2" statistical models. Specifically, all the models inherit their randomness from two sources of noise models, // and v². The algebraic forms of the statistical models are shaped by the weight matrices B and B* and the utility parameters O. Hence, learning 2n distributions can be reduced to estimating two noise models and estimating the entries of B, B* 0. Estimating these parameters, however, depends on access the causal graph G (informative about the sparsity structures of B and B*) and the latent variables Z,, both of which are not directly observable.
To address this, RO-CRL properly explores various intervention combinations to form reliable enough estimates of G and Z. from observations X,, Achieving the right level of exploration is critical to avoid collecting excessive data X,, which will compromise the regret. Attaining the right exploration, therefore, depends on determining what the coarsest possible estimates of G and Z, that ensure reliable identification of the optimal intervention a*. Hence, RO-CRL balances a trade-off that involves adaptive exploration schedule that focuses on recovering 9 and Z, to the extent needed to find a". At each time 4, RO-CRL constructs estimates for the graph G. and inverse transform H, using differences between sample precision matrices with samples from the observational and interventional data. Since CRL only recovers variables up to scaling factors, we compute robust estimates of appropriately scaled B and B*. After sufficient exploration of interventions, they are subsequently selected according to the upper confidence bound (UCB) principle. The overall pipeline of this process is illustrated in Figure
matrix differences. The main statistic we use to estimate the latent variables and graph is the differences in precision matrices under various interventions. Denote the precision matrices of Z and X under distribution F. by O and O,, respectively. Accordingly, define R² and R, as the associated precision differences between observational (a 0) and single-node interventional (a = (i)) data, i.e., R² A O Of and R, ( Og. To specify the empirical counterparts of these precision differences, we denote the number of times that a E AA is selected until time t by
Precision
Na. - Eee(t] 1(a, a}.
5

---

Hence, the empirical sample mean and covariance of X for a E A are given by
Pa.t 1
Na.t E La X}X,, Ea,t _ 1
Na. E (a. = X Ma, Ma,t T
(8)
Accordingly, the empirical precision and precision differences are denoted by Qu,t - (Ea,)) and R - (f),² U4,, respectively. We use the following properties of Ri to estimate G and Z.
Lemma 1. The non-zero rows of latent precision difference R describe the latent graph:
[|[ 11|, #0 = j {i) U pa(i).
(9)
Furthermore, the observable precision difference R. -Gl) J//RRGG is subxpacee-oonstrained:: col(R.) - [ jE {i} Upa(i)}
(10)
3.2 Key Processes in RO-CRL
RO-CRL consists of two main stages. It begins with forced exploration phase, in which we apply node-level atomic interventions on all nodes fixed number of times. The purpose of forced exploration is to establish initial estimates for the relevant statistics. This is followed by an adaptive exploration stage, which we dynamically select sequence of interventions adaptively to the observations and utilities. This stage itself consists of several inference processes, whose collective objective is to specify a rule for translating observations into an intervention selection.
Stage - Forced exploration. To construct initial estimates of R,, the algorithm explores the observational model along with each of the single-node atomic intervention models for To times. To formalize this, the set of interventions in this forced exploration phase is denoted by Ao A {ύ. (1). (2)...... {n)]. The constant T, chosen such that the initial R, are sufficiently accurate to produce reliable enough graph estimate for the latent causal graph G.
Stage 2 Adaptive exploration. After forced exploration, at every 1 (N + +1To, we perform three inference and decision procedures to identify the next intervention a++1-
1. CRL: First, recover the latent variables and graph. This is initiated by first finding the estimate H4 for the inverse G. followed by using that to find estimates Gr.
2. UCB-based intervention selection: Subsequently, we introduce UCB-based decision rule that leverages the above estimates in conjunction with the reward U, to specify a,-1-
3. Under-sampling rule: Finally, we implement process that ensures that single-node interventions are explored sufficiently over time. When an intervention deemed under- sampled. will be prioritized for sampling over the intervention. This process ensures that the estimates H, and G. are updated incrementally, preventing total estimation error Ze from growing linearly with
3.3 Inference & Decision Rules
The quality the inference and decision rules in Stage 2 critical for identifying the sequence of interventions. In this subsection, we specify these rules.
1- CRLL rules. The CRL rules are implemented in two stages: baseline recovery and refined recovery. The baseline recovery process serves two key roles: (i) it estimates the causal graph G and latent variables Z, under soft interventions, and (ii) it acts as an intermediate step for estimating & and Z, under hard interventions. The refined recovery stage is applied only when hard interventions are present, with the specific goal of improving estimates produced by the baseline process. As expected, hard interventions yield stronger recovery guarantees, with their advantage stemming from this additional refinement step.
La - Baseline recovery steps. The baseline recovery of the latent space is based on the shared properties of soft and hard interventions, such Lemma and it has three inference routines.
ii) Inverse transform H,. We construct the baseline estimate H, E Ra row by row by assigning H.]: f- the principal eigenvector of R..,,
(11)
where principal eigenvector denotes the eigenvector associated with the largest absolute eigen- value of a symmetric matrix. The intuition here is that, due to Lemma with high probability, the following property holds with a low error level.
(H.]. G) R 0,
Vj & {i) U pa(i).
(12)

---

i Variables 2, The estimated latent variables are subsequently estimated via
2. - H,X, (H.G) Z.
(13)
and approximately equal the true latent variables Z, up to mixing with parent variables. (iii) Graph G. To form graph estimate, we first compute the estimated latent precision differences
R (H))* R4, R....
vi [m]
(14)
and then assign the non-zero rows of these matrices as edges according to:
i j
i j and [|,,,1 7.
(15)
Next, we find the transitive closure of G. as the estimated graph G. This procedure directly mirrors the graph property in Lemma [ and recovers the transitive closure of with high probability. We denote the parent set of node in G. by (a, In this rule, 7 > 0 is a threshold for determining if a row of the estimated latent precision differences is zero. To ensure that this threshold can differentiate between true edges and non-edges, we need to select it carefully. We show that choosing it in instance- dependent interval y E r0)) is necessary, where
min [
|| 0}
(16)
1.b - Refined recovery under hard interventions. When using hard interventions, the intervention target becomes independent of its non-descendants in the latent space. We impose this independence condition on the estimated latent variables by constructing minimum mean-squared-error (MMSE)
estimates of node's 's non-descendants in the estimated graph, which is equal to the transitive closure of the true graph with high probability. Specifically, we do the following.
(i) Refined inverse transform H,, Using the sample covariance matrices defined in 8 we first compute the estimated latent sample covariance matrices via
a, H, Va.t H Va Ao
(17)
We collect the MMSE estimates of node on pa,(1) environment {t} in matrix E, E Rxx as
[i, (a) & 1Z (0,li pa (i) (2% (1), (i))
(18)
Using these MMSE estimates, we update the estimate H, as
H + -1) HH,
(19)
(ii Variables refinement. We re-apply the relation Ż, = H,X,, We show that this procedure refines the estimates Z, to be approximately equal to the true variables Z up to scaling.
1111 Graph refinement. We refine the graph estimate &, by applying (15) using the updated H. Since the variables are now recovered up scaling by Lemmal [] this step returns the latent graph G exactly with high probability. Therefore, we do not take the transitive closure of G.
2 UCB-based selection rule. After estimating the latent variables and the graph, specify selection rule. Formalizing this rule involves characterizing confidence ellipsoids of the relevant parameters under different interventions. To this end, we first estimate the graph parameters and subsequently use the confidence ellipsoids of these estimates to construct the confidence ellipsoid of the interventions, enabling full description of the UCB-based selection of interventions.
2.a - Parameter estimation. We first estimate the SEM parameters B, B", and utility parameters 0 using the estimated variables Z, and the estimated graph Gr. To keep the notation compact, present the following algorithm and regret analysis as if the noise means after recovery are known, ie., ia for E A are known. This can be readily relaxed to accommodate unknown mean setting by using the same reparameterization technique as in (11, which involves adding a dummy node 1 to the graph estimates G.. along with the associated modifications to Z, and (t).
As we use finite samples X, to estimate Zr, there will inevitably be an estimation error. Therefore, at each time / E N, we design the weighted ridge regression estimators A, and A; at time for B and B", respectively. To estimate the observational weights [A]; we only use the samples which node i was not intervened. Conversely, to estimate the interventional weights [A*];, use the samples in
7

---

which node was intervened. We encode these selection rules via diagonal weight matrices W., and W which we will specify later. The i-th rows of the estimates A, and A; are specified follows.
Ad) A V.,
W., [ (2.pp,
D(i)), and - 1V (a,( W ([z)) [t]) (20)
where we have defined weighted and doubly weighted Gram matrices as
V (o)pa(() W (t) + In and V1,,e+1 Z
1,s,s Wi, Z, L,,, + In. (21)
Vi, _ IZlpa, W pa, + In and Vi, - Z.,..s Willlss Zi,,, + In (22)
where Zi - Z (t), :s] and I, is the identity matrix. An important consideration in the above estimates is the design of the weight matrices. At each time t, we construct diagonal matrices (Wi,. 1. W : E [n]} to softly filter out the outlier samples that are likely to have higher estimation
error. The diagonal elements for [1] are defined
min {1, [2. (i), 8) 1
8 [ E a.) and Wirls,s] A
(23)
G min {1. |[Z.|pa, s||
1ii E a.)
(24)
The designs of the diagonal weights are inversely proportional to Se. which is bound on the cumulative estimation error. This design uses smaller weights when Çr is higher. The weights are also inversely proportional to weighted &2 norm, often referred to as the weighted exploration bonus. A higher exploration bonus means lower confidence the sample and hence, lower weights.
Similarly, with Ze. - is], we define the estimate for A time E N follows.
Wo,ess s) - 1 min {1, 2 [:) o
0, $ 0 ' U,, Ve, e z Wo Ze L
(25)
Ce Vo,c, & Zo Wo.lis, : : s) 1,8 + In
(26)
2.b - Confidence ellipsoids and decision rule. After estimating the SEM and utility parameters, we use a UCB-based rule for sequential selection of interventions. The UCB under intervention a E A is defined as the maximum value of expected utility when the weights are in the confidence ellipsoids of a, denoted by Ca.t. In order to construct the confidence ellipsoid for a, we first form the following confidence ellipsoids for the estimated parameters, ie., A., A; and B₁:
C..e A
{ : ||5 V $ {Be((
(27)
C
{e : || - [A]] 1e: V.. I- < (,,,
(28)
and Co..
A {5: - 1 Bellvo. V S (c()))
(29)
where (8)) E R4, E E,i [n]} and (()( E IR,, E...EN) N) are sequences of confidence radii that control the size of confidence ellipsoids and 8, the tolerance of wrong estimates at time t. Accordingly, we define the relevant confidence ellipsoid for node under intervention a E A as
Ci,tt A i E a) C, Iii & a) Ci,t, and Ca.t A CU.a))) U Co.t Based on these, time t. our algorithm selects the intervention that maximizes the UCB. Let L, be the length of the longest causal path of G. Due the linear structure in SEMs, is defined
(30)
UCB A max (Ø Eli A Da) VaEA, and a++1 = arg max UCBa,t EC.)
(31)
acA
3 - Under-sampling rule. RO-CRL iteratively update various estimates. The performance of the UCB step contingent on the performance of the CRL step producing increasingly accurate estimates G. and H, To ensure such accuracy, we impose a rule requiring that single-node interventions be sufficiently explored over time. Such interventions are needed to construct the necessary statistics for the CRL step. To formalize this, we define the set of under-explored interventions as
AUE (a E Ao Na.1 ((()))
(32)
where the function f(().) is dec-ecccgg term that controls the adaptive exploration to collect observations X, when necessary. If AUE + 0, the algorithm is forced to random sample from ALE.
8

---

4 Regret Analysis for RO-CRL
In this section, we present the node-level instance-dependeni regret results for RO-CRL. We also present algorithm-indeppedent regret lower bounds to complement RO-CRL's achievable regret.
As an intermediate step toward regret analysis, we first provide PAC identifiability guarantees for recovering 9 and Z₁ These results depend on the least frequently selected single-node intervention up to time i, denoted by A mi Na.t Theorem 2 (Sample complexity). For any instant of RO-CRL that satisfies 8 2 N(e, where (e, C² max(6 .max] } (d + log(1/6))
(33)
under Assumption 1 the estimate H, constructed in (TT) for (99) and estimate G. constructed in (15
ensure (e, O)-A recovery of and G under soft (or hard) interventions specified in Definition 7
This implies that with probability at least 6, the error term E, specified in Definition 7 Qunder
both hard and soft interventions satisfies
|E 1 S C² (d+ (d++oog log(1/0)) /s2
(34)
The regret bounds have delicate differences under hard and soft interventions captured by the constants w E {ug, ). Let m E {S, H} indicate the intervention type, and Hm (i) & (i), Mn((), such that Hn (i) pi()) and Hs = an(i). Then u is defined as
if i is a root node otherwise
Σ Um + Vn. (35)
Um. [EE Umy + (i)
and
Um
By setting 6, = .2य² for confidence radii and controlling To to satisfy To 2 (emax STY,). ). we ensure that with probability at least - 46, the choice of ft defined in (32). Se for weights design and 3's for confidence radii will be equal to or in the order of
66
((.)) max ( (dbs 3 3u313, 13, N (C 66)
Si - - 11 (d log(1 log(1/)))//((G.))
(36)
[Ō(V]] pa (a)) Hard intervention (5,(()) (0(V) an (n)) Soft intervention
(x(5) = Ö(vm)
(37)
where under soft intervention u ug and under soft intervention u UH- Theorem 3 (Regret upper bound). Under Assumptions 7
with probability at least 1 46, the
average cumulative regret of RO-CRL is upper bounded by
R₁ s Ödd3n3u3T' + HVVT
(38)
When the noise means ia for a E A are unknown, the impact on the regret upper bound order is reflected in the parameter u, where the value will be set to is a root node instead of O.
Next, we establish a lower bound on the regret in the unknown mean setting. As no finite-sample lower bound for CRL is known in the literature, we provide the lower bound by fixing the estimation error as in Theorem 2 As the reward depends on how noise terms cumulatively contribute to the utility, the lower bound depends on the number of paths in the G. Denote mi as the number of causal paths from node i to node in Gie, and denote the number of paths as 2nd n + 1++ Ei= Σj=1 mi.. Theorem 4 (Lower bound under soft intervention). For any CRL-based algorithm that satisfies Theorem 2 there exist instances of a causal model on Gue and estimation error E, such that the expected cumulative regret of any algorithm is at least
Rr 2 2 n p + pVT).
(39)
Remark 1 (Tightness or the bounds). When comparing the upper bound in Theorem 3 and the lower bound in Theorem f we observe that both bounds show similar behavior with respect to parameters and the time horizon T. The only discrepancy comes from us and p. where us has an extra factor to count the dimension of graph connectivity in transitive closure.
Remark 2 (Causal bandits). Our reward-oriented CRL reduces the standard causal bandit setting if we set G = In and the utility function to U(Z) = Z [n]. By these choices, our regret bounds immediately provide regret bounds for causal bandits. Specifically, our upper and lower bounds simplify to Ö(un VT) and M(pTT), respectively, where p is defined on G instead of Gic- These bounds match at O(d) (T) for graph-independent regret bounds, eliminating the gap in previous results (24).

---

8000
RO-CRL
8000
RO-CRL
regret.
mnillmiiv regret
6000
6000
Curmalative
4000
4000
2000
2000
0
10000
30000
10000
20000
40000
T
Figure 2: Results of regret of RO RO-CRL Left: soft intervention. Right: hard intervention, Yellow shading denotes the exploration phase.
5 Experiments
In this section, we evaluate the empirical performance of RO-CRL. We report the regret of RO- CRL under both soft and hard interventions. Additional experiments, including CRL recovery. scaling behavior, comparison to baselines, and assumption violations, are deferred to Appendix CP
Latent graph. We generate random acyclic graph on n nodes by enforcing strictly lower- triangular weight matrix. To ensure that the UCB in RO-CRL is computable for any randomly generated graph, we force all weights and noises be positive (See Appendix [B). Specifically, observational weights are drawn from [0.25, 1] and interventional weights are set 0.1 times the corresponding observational weights for soft interventions and to for hard interventions. Noise terms are sampled i.i.d. from the uniform distribution U(0, 1]. We set 5 for these experiments and repeat the experiments times.
Figure 2 jillustrate the cumulative regret of RO-CRL under two types of interventions: soft inter- ventions (left) and hard interventions (right). In both cases, we observe an initial phase of forced exploration (highlighted in yellow), during which the algorithm collects sufficient interventional data to estimate the underlying causal structure and variables. After this phase, the regret curves begin to flatten, indicating that RO-CRL effectively identifies near-optimal interventions and achieves sublinear regret.
Conclusion
In this paper, have introduced the framework for formalizing and analyzing reward-oriented causal representation learning, the objective of which is to optimize a downstream task over the space of possible interventions in the causal system. The key difference between reward-oriented and conventional CRL is that CRL's objective of perfectly recovering the latent graph and variables can be excessive for optimizing downstream task. Specifically, for reward-oriented CRL, one needs to learn the latent graph and variables at the coarsest level that enable the identification of optimal interventions. To resolve uncertainties associated with the latent causal graph and the latent probability distributions, we have adopted a sequential framework to explore different interventions and identify the optimal one with few time instances possible. We have designed an adaptive exploration algorithm that learns only the coarsest representation necessary to optimize the downstream reward. We have provided smite-sample latent recovery guarantees for the causal graph and its variables, and regret bounds for different types of interventions. In the standard causal bandit setting, these bounds simplify and match, even improve upon previous results.
Acknowledgments and Disclosure of Funding
This work was supported in part by the Rensselaer-IBM Future of Computing Research Collaboration (FCRC).
"The codebase for the experiments be found at http://hhh...om//////aaaaa//0//0
10

---

References
[1] Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning, Proceedings of the IEEE, 109(5)6612-633 May 2021.
[2] Chandler Squires, Anna Seigal, Salil S. Bhate, and Caroline Uhler. Linear causal disentangle- ment via interventions. In Proc. International Conference Machine Learning, Honolulu, HI, July 2023.
[3] Burak Vancı, Emre Acartürk, Karthikeyan Shanmugam, Abhishek Kumar, and Ali Tajer. Score- based causal representation learning: Linear and general transformations. Journal of Machine Learning Research, 26(1 (6(112) 12):1-90, 2025.
[4] Emre Acartürk, Burak VaricI, Karthikeyan Shanmugam, and Ali Tajer. Sample complexity of interventional causal representation learning. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, December 2024.
[5] Tianyu Chen, Kevin Bello, Francesco Locatello, Bryon Aragam, and Pradeep Ravikumar. Identifying general mechanism shifts in linear causal representations. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, December 2024.
[6] Kartik Ahuja, Divyat Mahajan, Yixin Wang, and Yoshua Bengio. Interventional causal repre- sentation learning. In Proc. International Conference on Machine Learning, Honolulu, HI, July 2023.
[7] Jikai Jin and Vasilis Syrgkanis. Learning linear causal representations from general environ- ments: Identifiability and intrinsic ambiguity. Proc. Advances Neural Processing Systems, Vancouver, Canada, December 2024.
[8] Jiaqi Zhang, Chandler Squires, Kristjan Greenewald, Akash Srivastava, Karthikeyan Shan- mugam, and Caroline Uhler. Identifiability guarantees for causal disentanglement from soft interventions. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[9] Julius von Kügelgen, Michel Besserve, Wendong Liang, Luigi Gresele, Armin Kekić, Elias Bareinboim, David M Blei, and Bernhard Schölkopf. Nonparametric identifiability of causal rep- resentations from unknown interventions. In Proc. Advances in Neural Information Processing Systems, New Orlcans, LA, December 2023.
[10] Simon Buchholz, Goutham Rajendran, Elan Rosenfeld, Bryon Aragam, Bernhard Schölkopf, and Pradeep Ravikumar. Learning linear causal representations from interventions under general nonlinear mixing. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[11] Burak Varicı, Emre Acartürk, Karthikeyan Shanmugam, and Ali Tajer. General identifiability and achievability for causal representation learning. In Proc. International Conference on Artificial Intelligence and Statistics, Valencia, Spain, May 2024.
[12] Wendong Liang, Armin Kekić, Julius von Kügelgen, Simon Buchholz, Michel Besserve, Luigi Gresele, and Bernhard Schölkopf. Causal component analysis. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[13] Burak Vancı, Emre Acartürk, Karthikeyan Shanmugam, and Ali Tajer. Linear causal representa- tion learning from unknown multi-node interventions. In Proc. Advances Neural Information Processing Systems, Vancouver, Canada, December 2024.
[14] Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good inter- ventions via causal inference. In Proc. Advances Neural Information Processing Systems, Barcelona, Spain, December 2016.
[15] Elias Bareinboim, Andrew Forney, and Judea Pearl. Bandits with unobserved confounders: causal approach. In Proc. Advances in Neural Information Processing Systems, Montréal, Canada, December 2015.
11

---

[16] Sanghack Lee and Elias Bareinboim. Structural causal bandits: Where to intervene? In Proc. Advances Neural Information Processing Systems, Montréal, Canada, December 2018.
[17] Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit problems with causal background knowledge. In Proc. Conference Uncerluinty in Artificial Intelligence, virtual, August 2020.
[18] Vineet Nair, Vishakha Patil, and Gaurav Sinha. Budgeted and non-budgeted causal bandits. In Proc. International Conference on Artificial Intelligence and Statistics, virtual, April 2021.
[19] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Causal bandits with unknown graph structure. In Proc. Advances in Neural Information Processing Systems, virtual, December 2021.
[20] Scott Sussex, Anastasiia Makarova, and Andreas Krause. Model-based causal bayesian opti- mization. In Proc. International Conference on Learning Representations, Kigali, R wanda, May 2023.
[21] Burak VarICı, Karthikeyan Shanmugam, Prasanna Sattigeri, and Ali Tajer. Causal bandits for linear structural equation models. Journal of Machine Learning Research, 24(297):1-59, 2023.
[22] Shi Feng, Nuoya Xiong, and Wei Chen. Combinatorial causal bandits without graph skeleton. In Proc. Asian Conference on Machine Leurning, Hanoi, Vietnam, December 2023.
[23] Zirui Yan, Arpan Mukherjee, Burak Vanııı, and Ali Tajer. Improved bound for robust causal bandits with linear models. In Proc. IEEE International Symposium on Information Theory, Athens, Greece, July 2024.
[24] Zirui Yan, Dennis Wei, Dmitriy Katz-Rogozhnikov, Prasanna Sattigeri, and Ali Tajer. Causal bandits with general causal models and interventions. In Proc. International Conference on Artificial Intelligence and Statistics, Valencia, Spain, May 2024.
[25] Muhammad Qasim Elahi, Mahsa Ghasemi. and Murat Kocaoglu. Partial structure discovery is sufficient for no-regret learning in causal bandits. Proc. International Conference on Machine Learning Workshop on Foundations of Reinforcement Learning and Perspectives, Vienna, Austria, July 2024.
and
[26] Zirui Yan and Ali Tajer. Linear causal bandits: Unknown graph and soft interventions. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, December 2024.
[27] Roman Vershynin. High-dimennsiona probability: An introduction with applications in data science, volume 47. Cambridge University Press, Cambridge, UK, 2018.
[28] Chandler Davis and W. M. Kahan. The rotation of eigenvectors by perturbation. III. SIAM Journal on Numerical Analysis, 7(1):1-66, 1970.
[29] Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2022.
[30] Tor Lattimore and Csaba Szepesvári. Bandit Algorithmss. Cambridge University Press, Cam- bridge, UK, 2020.
[31] Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary environments. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, December 2019.
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:
Sections esstallish the results claimed in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long 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: The major limitations of the work the linear assumption on SEMs, transfor- mations and utility functions. We discuss these in detail in Appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification: We provide full set of assumptions at the end of Section 2 and referenced in the theorem statemnts. All proofs are included in the Appendix.
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 proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch 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 properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
See the details in the experiments section in the Appendix C
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of 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 a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to 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?
14

---

Answer: [Yes]
Justification:
We release the code with instructions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpss:/niis.cc.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 NeurlPS code and data submission guidelines (https
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 subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The algorithm details are described Section with pseudocode provided in Algorithm I All the parameter setting are discussed. The experimental details are provided in the experiments section (Section 5) and additional experiments (Appendix C).
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 be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
The theoretical results are based on high probability finite sample guarantee and average regret. We do not include the variance and error bars as metric in this paper; therefore, it is not defined and applicable.
Justification:
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror 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 not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiments only need CPUs.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn'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 http://wwrrr......opoo/tcttctcta
Answer: [Yes]
Justification: The research focus on theory only include the synthetic dataset and hence, do not have potential potential harmfulness.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is mostly theoretical and does not pose potential negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
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]
Justification:
This paper is mostly theoretical and does not pose such risks.
Guidelines:
The answer NA means that the paper poses no 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 usage guidelines 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.
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 are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Portions of the publicly available code of 3 available under Apache 2.0 license, is adopted in the code of our experiments.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information 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:
We released code for the experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 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 crowdsourcing nor research with human subjects.
Including this information 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 Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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
Does the paper describe the usage of LLMs if it 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.
Question:
Answer: [NA]
Justification:
The core method development this research does involve LLMs
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy bettts://neurre /0tps//eeccccooeeeeee/////////// for what should or should be described.
19

---

Reward-oriented Causal Representation Learning Supplementary Materials
Table of Contents
A Pseudocode
21
Computational complexity of RO-CRL.
21
Additional Experiments
21
D Additional Notations
24
D.I Precision Matrices
25
D22 Causal Bandit Notations
25
E Analysis of CRL Steps
27
E.1 Proof of palinite-sample Guarantees
27
Proof Finite-sample Guarantees
28
F
Proof Regret Upper Bound (Theorem)
30
F.1
Bounded System and Error Bound
................................
31
F2
Decomposition of Node-level Utility
34
F3
Proof of Concentration Inequality
35
F44
Cumulative Estimation Error
37
F55
Proof of General Regret Bounds
39
Proof Trade-off Upper Bounds [heorem
................................
40
F.7
Refined Upper Bound for Causal Bandit
................................
41
G
Proofs of Lower Bounds
41
G.1
Craph-dependent Lower Bound for Causal Bandil
41
2
Graph independent Lower Bound for Causal Bandit
44
G.3
Proof Reward-oriented CRL Lower Bound (Theorem
45
Multiple Interventions
46
H.1
Latent Data- genta-generating Process and Intervention
47
H2
Algorithm Modification
47
H.3 Changes in the Regret Bounds
47
Remark on do interventions
52
Broader impacts, Limitations and Further Discussions
52
20

---

A Pseudocode
Algorithm 1 Reward-oriented CRL (RO-CRL)
1: Forced exploration. Sample To times for each intervention Ao.
2: for (n + 1).o....d do
3: D> Latent recovery
4: Update the inverse transform estimate H2 via
5: Estimate 2, according to 2, =,,X,
6:
Update the graph estimate G. via (15) if hard interventions then Update the inverse transform estimate again using 19 Update Z, according to Z, = H,X,, Update the graph estimate again 9. via 15
7:
8:
9:
10:
11:
Under-sampling rule if A o then
12:
13:
Pull a, random sample from A.E
14:
else
Parameter estimation
16:
Set weight matrix W.... W and Wes for E [4] according to
23
25
Update A,, A and 0, according to 20 and (26)
18:
Set A; = 0 under hard intervention UCB selection
20:
Compute UCBa.: according to 31 for a E A
Pull a arg max UCBa,t
22:
Observe X₁ and (2,)
B
Computational complexity of RO-CRL
The computational cost of RO-CRL step can be broken down into two parts:
1. CRL: CRL routine depends on matrix inversions (O(d)), which can be expensive for large d. However, since the transformation is linear, we can detect the supporting subspace and project the samples effectively reducing the observation dimension n, and yielding overall per-step complexity of On*))
2. UCB-based selection: The computational bottleneck is the ineervention-seleetin step: the UCB intractable general causal graphs [26] Section 3.3]. To make the algorithm practical, (26) proposes techniques that efficiently compute an upper bound on the UCB, which we can incorporate into our approach. However, the upper bound is loose, and its robustness to imperfect latent recovery is unknown.
In the experiments, we use the following modification to ensure efficiency in the intervention selection step for RO-CRL.
Non-negative edge weights and noise (shifted system): We investigate the setting where all weights and noises are positive. A general system can be linearly transformed into such a non-negative system. key property of such systems that all variables are monotone their parents. To calculate the UCB, we can therefore maximize nodes sequentially in causal order and use the closed form in linear bandits. The resulting complexity is O Evejn) [pa, + +n²) for UCB selection in (1) where the number of latent dimensions.
C Additional Experiments
Latent Recovery Figure shows the variations of the graph recovery rate versus the sample size St. As expected, it is observed that the recovery improves with more samples 8t- Furthermore, the hard interventions, the stronger special case, consistently yield higher recovery rates than soft
21

---

1.00
1.00
Graph recovery rate
Graph recovery rate
0.75
0.75
0.50
0.50
0.25
Hard intervention
0.25
Hard intervention
Soft intervention
Soft intervention
0.00
0.00
20000
40000
20000
40000
%
Figure 3: Results of graph recovery on different value of for soft intervention (Gie) and hard intervention (9). Left: 10. Right: == 75.
interventions. Figures 4 and 5 show the norm of the error term E, and the average estimation error on latent variables Z for varying 5t. We can both terms decay, which conforms to the theoretical decay / 1/st Sy rate established in Theorem
4
Hard intervention
3
Hard intervention
3
Soft intervention
Soft intervention
Avg. of
Avg of
2
0
20000
40000
20000
40000
Figure 4: Results of the error term E, different value of Left: d 10. Right: d 75.
Hard intervention
Hard intervention
Avg. error Z
Soft intervention
Avg. error on Z
2.
Soft intervention
2.
0
0-0--
0-00--0
20000
40000
20000
40000
Figure 5: Results of average estimation error Z on different value of 8t. Left: = 10. Right:
d = 75.
Performance of CRL when varying n and d. In Table 2 we provide additional experiments evaluate the performance of CRL across different n, and intervention types, plotted against sample size st. These results show that the CRL performance of our RO-CRL algorithm is mostly consistent across variations system parameters: Variable recovery errors decay with increasing number of samples consistently with the theoretical rate of 1/st (Theorem 2) across all settings. Observation dimension does not affect results thanks to dimensionality reduction step. Finally, increasing n from 5 to 8 does not lead to significant drop in variable recovery performance. However, graph recovery performance significantly degrades for n under soft interventions, which can be explained by noting that the "true" graph under soft interventions is the transitive closure, which includes a high number of indirect edges. Such indirect effects are hard to track from the precision matrices, which makes the graph recovery for soft interventions more difficult.
22

---

Table 2: CRL performance versus n, d and intervention type.
(a) Latent recovery (MSE).
7
d
Int. type
St 50=1000
2000
4000
8000
16000
Soft
0.067
0.052
0.034
0.026
0.018
5
25
Soft
0.201
0.189
0.170
0.162
0.156
Soft
0.136
0.092
0.069
0.047
0.035
5
5
Hard
0.218
0.165
0.069
0.047
0.017
5
Hard
0.378
0.320
0.232
0.186
0.147
8
8
Hard
0,246
0.176
0.099
0.047
0.034
(b) Graph recovery rate.
n
d
Int. type
1,=1000
2000
4000
8000
16000
5
Soft
0.00
0.22
0.80
0.94
1.00
25
Soft
0.02
0.10
0.64
0.80
0.94
8
8
Soft
0.00
0.04
0.00
0.00
0.00
5
Hard
0.02
0.10
0.68
0.84
1.00
5
25
Hard
0.00
0,08
0.50
0.82
0.98
8
Hard
0.00
0.08
0.50
0.96
1.00
Varying observation dimension d: Thanks to dimensionality reduction techniques and the forced- exploration schedule, CRL's regret remains essentially unchanged as we increase the feature dimen- sion d from 100 while keeping the latent dimension with some previous findings in CRL under linear transformations 33 that the performance of CRL is that sensitive the feature dimension d, and this behavior does contradict our lower bound analysis, which is derived under the error bounds from CRL. Table 3 reports the corresponding runtime for different dat fixed time horizon T,, and the additional computational cost introduced by higher d remains well within practical limits.
5. This observation is consistent
Table 3: Average runtime (in minutes) with varying d when 5
d
10
25
50
75
100
soft
48.55
47.19
53,85
48.01
48.11
48.55
hard
63.12
65.83
67.66
67.24
67.54
68.32
Varying latent dimension n: (which also affects the u.) for fixed d 10. From Table 4 we observe that the cumulative regret grows by increasing We note the increase stems from two factors: (i) exploration cost for CRL varies with n, and (ii) the reward range becomes larger as n increases. These trends will be more clearly visualized in the figures to be included in the final version.
Table 4: Cumulative regret with different latent dimensions n when 10
3
5
soft
1524
4832
13298
37787
hard 1789
5382
14677
37830
Table Cumulative regret across different algorithms
Algo
RO-CRL
UCB
modified RO-CRL
hard
5382
15690
10132
soft
4832
16320
9726
23

---

Baselines. We compare RO-CRL with two baselines: vanilla UCB and modified version of RO-CRL, where CRL performed for a fixed fraction of the sample budget, after which the bandit proceeds without accounting for latent recovery error. Table reeporss the cumulative regret at the given final horizon 7 for different algorithms. As shown, both baselines perform significantly worse than RO-CRL. The performance gap between RO-CRI. and Modified RO-CRL will continue to increase with longer time horizons.
Assumption Violations.
Assumption] | We run experiments where [ssumption violated and provide the regret and variable recovery results in Tables [ First, we note that graph recovery consistently fails (the graph recovery rate is exactly 0) in this setting. However, Table 6 shows that latent variable recovery still works: Indeed, its analysis is independent of Assumption [] In T we evaluate cumulative regret versus time, and observe that the bandit algorithm does not achieve a sublinear regret after the forced exploration phase (t 2 18000 this case), meaning that the RO-CRL algorithm requires Assumption | to appropriately capture the true uncertainties and make good decisions.
Table 6: Cumulative regret under Assumption
violation (n d == 5)
3000
6000
9000
12000
15000
18000
21000
24000
Regret
0 2000 4000
4000
6000
6000
11000
16000
Table 7: Latent variable recovery MSE under Assumption
violation (n d 5)
St
1000
2000
4000
8000
16000
MSE 0.134
0.123
0.104
0.097
0.092
Boundedness violations We conduct experiments that deliberately violate two key assump- tions: bounded noise and known parameter bounds. The specific violations are as follows: Noise violation: We replace the bounded noise with unbounded Gaussian noise. Parameter violation:
Instead of properly rescaling the system, we multiply all parameters by factor of to simulate the violation. Note that such scaling can be offset by properly scaling the latent variables. Therefore, in these experiments, we explicitly set fixed scale of the latent variables.
As shown in Table g both violations result in linearly growing regret after the forced exploration phase (t 2 18000 in this case). This result aligns with theoretical expectations: violating the noise boundedness or known-pant parameter assumptions leads to confidence radii that no longer appropriately capture the true uncertainty, thereby causing increasingly poor decisions.
Table 8: Cumulative regret under bound violation (n = d d= 5)
6000
12000
15000
18000
19000
20000
21000
noise parameters
1909
4272
5382
5382
7176
8970
10764
421447
505197
516290
516290
685092
857133
1029174
D Additional Notations
In this section, we present the notations that will be useful in our analyses.
Given a symmetric matrix A E Rdddd we denote the vector of eigenvalues A ordered in descending order by X(A) Rd and the matrix of eigenvectors by Q(A) Rdddd such that A Q(A)- diag A(A)) Q(A)..
24

---

Table Table of Notations in Main Body
Notation
Description
Z
Latent variable
B. B
Obserrationa//meeeeetiinna weight matrices noises
plv"
mean of noises
X
Observable variable
U(Z)
TT Z EU
Observable reward Transforms
G
Z11, X[I]
i-th random variables data vector at time Interventions
Zr X₁
aEA
H²
Estimate of G at time t
Z H,X,
Estimate of sample Z, at time f Set of null and atomic intervention Estimates of A, A time Cumulative estimation error at time
Ao
A., Aï
St
D.1 Precision Matrices
In this paper, we will consider precision matrix differences as our learning signal for CRL, similarly to []. The precision matrix of a distribution is the inverse of its covariance matrix. In case of the latent variables, linear SEM can also be written explicitly as
denote the pre-inters pre-intervention precision matrix by O, Note that the implicit
Z -I-BB)
(40)
Let us denote the vector v as the variances of entries 6, and v as its interventional counterpart e*. Using this formulation, the precision matrix is given by
o² BI- diag(1/v) B)
Σ (I BJ) [-BB]
(41)
*E(M)
Let us construct two matrices K, K E IR NxN row by row
K] (v
1/2
Bl;
K - (v* -1/2
(v-1
B'] 1
(42)
such that in (41) is equal ([K&)) [K] Since this is only function of the generation
mechanism of node i, the precision matrix of the latent variables under action a E A, denoted by O given by
0
Σ ([K)
()) K] + [(K*) [K*)
(43)
iga
tEa
Therefore, K, K* fully parameterize the precision matrices of the latent variables under any action A. Finally, note that the precision matrices observed variables, denoted by O, for action E A, are given by
θ = O Thus, defining Q = K and Q* = K.G. both in NxD, the observed precision matrices are given by
(44)
O Σ ((Q)) [Q] + (EQ
(45)
iga
TEa
Similarly to the latent case, Q and Q" fully parameterize the observed precision matrices (Oa a A). In this paper, the CRL algorithms we design solely depend on estimates of Q and Q
D.2 Causal Bandit Notations
We define the row of weights under intervention as
Bak 1i ar} [B", + 1(i a.) [B].
(46)
25

---

First, we provide notations that are useful in our analyses. We denote the singular values of matrix A E IR MXN, where M Ny
(A) 02( 2 2ON(A)
(47)
In the proofs, we often work with zero-padded vectors and corresponding matrices. As a result, the matrices that contain these vectors have non-trivial null space leading to zero singular values. such cases, we use the effective smallest singular value that is non-zero. We denote the effective largest and smallest eigenvalues that correspond effective dimensions of a positive semidefinite matrix A with rank k by
muxx (A)
(A), and min (A)
(A()).
(48)
For square matrix U = AAT E R RNN, we denote the effective largest and smallest eigenvalues by
Amax (U)
Amax (AAT) = 0 maxx (A)
(49)
and Amin (U) Amin (AAT) = - min (A).
(50)
Then we construct data matrices that are closely related to Gram matrices. At time E N and for any node i [n], the data matrices U., E Raxt and UH, E Buxt consist of the weighted observational and interventional data, respectively. Specifically, we define
U (Zelpa,() WW,,, and U & (2elpa,(0) / Wie
(51)
where we denote A the square root of the matrix A.
We denote the relevant data matrices for node E [n] under intervention a E A by
Ut
f $ a U, + li E a) and Viai - + (52)
Combining 511 and (52). we have
Viaa Uza. UTa + In.
(53)
Similarly we define the data matrices that related V Vi,,,
Ü.. (20) Wie, and ÜJ (2elpa,(8) W
(54)
The relevant data matrices for node E [n] under intervention a E A are
Ú.a.t lii a) + 1fi E a)ū; and Vi = a, ÜT +la
(55)
(56)
Define NY, as the number of times that node E [n]] is intervened, and Ni, as its complement, i.e., Accordingly, for any E [n], & N and A, define
N Σ Eliiaa), and No, 1 N
(57)
Nant A e a) 1ii $ a)N
(58)
To proceed, we define the second-moment matrices and their effective largest and smallest eigenvalues
as
Ejatt
A
Eg (az( (1)]
(59)
Eminnt
min aEAA
Jmin (Er,a.).
(60)
Fimax,t
max :E|n],aEA
Tuax (Ei,,,)
(61)
where 6min > 0 guaranteed since there is no deterministic relation between nodes and their patients. These variables are inherent the system and remain unknown to the learner.
26

---

Lastly, we define A,,t and fa. as the weights that attains UCBa, i.e.,
(Aa,t, 0a.)=
arg max (A.0)ECm,_1
(0, Ex A Pacti)
(62)
Accordingly, we define the auxiliary variable 24 generated according to the following SEM
Z, A 2e + Et:
(63)
with the exact same realization of the noise & and the UCB is calculated as
((.) - UCBa,: 02 2x + EtA
(64)
E Analysis of CRL Steps
In this section, first prove the high probability error bounds for recovering the latent variables and graph using finite samples. For notational clarity, we drop oo from infinite-sample estimators and use these forms without subscript as infinite sample limits.
E.1 Proof of Infinite-sample Guarantees
In the infinite sample limit 3, - oo, covariance and precision matrix estimates converge to their true values. This enables us to derive identifiability guarantees without additional error terms. First, let us start by proving the main motivating property of precision differences.
Proof of Lemma Using the expansion 43
we note that the precision difference between null and single-node interventional distributions very structured.
R 0 - 0 (KK),) [K]
(65)
Using the definition of K, K in (2)) row i of either of these matrices have non-zero entries only in coordinates or pa(i). Therefore, only the principal submatrix coordinates (pa()), Ua)())
can be non-zero in R therefore, for any row j. the norm [ ll * 0 implies j E {i} U pa(i).
Using this fact, we can prove the second part of the lemma. Since R. = (Gt) R (G)), row sparsity of R immediately implies that
col( C col((Gt) R span (1) (a))
(66)
Rank-2 assumption. Next, let us investigate R and R, under Assumption 1 This assumption simply ensures that [K]; and [K*], have different directions for all i [n]] that is not the root node, which implies the following.
Lemma 2. Under Assumption | the precision matrix difference R. has rank I if and only if is root node, and has rank 2 otherwise. The rank of R, is equal to the rank of R.?.
Proof: Assumption 1 that is, [B] * [B*] used directly with the definitions of [K] (vli) 1 B], and K*), (i) - B*]. but we must change the noise variance, which yields rank-1 update to the matrix, with only the (i, -)tt element being non-zero. If is not a root node, then Assumption ] ensures that e; [B) and c; matrix.
a root node, both [B), [B'] =
[ have different directions, thus the overall difference of outer products yields rank-2
Proof of the soft intervention inverse transform estimation results are identical to 3 Lemma 4]. For graph estimation, follow closely proof of [ Lemma 5] follows.
Soft interventions.
In the infinite sample regime, using soft interventions, we recover the latent variables up to mixing with parent nodes, i.e.,
2= HX CsZ, where Cs HG with Cs(i,5] + 0 only j E {i} U pa()). The "estimated latent" precision matrix
(67)
difference is computed via
R = H
R. H
[cs] [Cs]
(68)
27

---

Using 3 Lemma 13], the up-to to-parents mixing in Cs results in up-to-descendants mixing in [ [i. 5l # 0 only if {i] de()). On the other hand, using Lemma only non-7ero rows of R are j E {i) U pa((). This implies that all rows and columns j $ { an will be zero in R. Therefore, the estimated graph & is worst supergraph of the transitive closure of the true graph G.
[Cs] that is, [C&]
Proof of the hard intervention post-processing steps in the infinite sample regime is identical to 3 Proof of Theorem 3].
Hard interventions.
E,2 Proof of Finite-sample Guarantees
In this section, we start by defining the error bounds for sample covariance and precision matrix estimation (27]
Lemma 3. With probability 1 - 8, the maximum error term in sample covariance matrices Σa, for a E Ao is bounded by
(d (d+ ( 1/2
max AD
Da. Eall S Css
(69)
St
Similarty, for bounded condition number for covariance matrices, the maximum error in the sample precision difference matrices R; for E [n]] is upper bounded by
(d+ (
(d+1og((10)
1/2
max
R R S CR.
(70)
The proof strategy for finite-sample guarantees follows closely to 4 We first show that infinite- sample guarantees can be recovered with low error if the estimation errors are low enough. Next, we use the error bounds of the specific precision difference estimator to derive overall error bounds for the overall CRL procedure.
Inverse transform estimation. In inverse transform estimation, the estimate H, is constructed row by row as the principal eigenvectors from finite-sample precision differences R We have the following result on the stability of this estimation procedure.
Lemma 4. Denote the principal eigenvector of R. by H; and that of Ri, as H Denote the minimum separation of the top two eigenvalues of R. by 1f", that is,
n =min A(R -((Ra)2 iE(m)
(71)
Using Davis-Kahan symmetric sin theorem when
RR RR,ell S 11" /2, we have
2
H H - H H
R; -R,all-
(72)
Following [4, Lemma 17], the inverse transform estimation is upper bounded by
2/n n
H. H|| <
max
R;
R
(73)
(E(2)
and the overall transformation error E, in Definition
is upper bounded by
2/n
E.ll <
max #E[n]
RR
R.
(74)
Graph estimation. latent precision difference matrices and thresholding them to recover edges. Let's first focus on the error bounds the computation side, which then yield errrr upper bounds in order achieve perfect graph recovery.
The graph estimation procedure consists of two steps: Computing the estimated
The equation for computing the estimated latent precision differences is
R = H R,
(75)
28

---

and similarly for sinite-sample counterparts. A perturbative error bound on the pseudoinverse term is given by, when H. H - H/ II), | H'll S | H|]
(76)
Therefore, a bound on the estimation crror in R. given by, when |
H &
[H']]
I R H IICH RR,: R H
H R.
(77)
The spectral norm bound is a natural upper bound on the & norm of any row of a matrix. other words, under the same circumstances, we have, for any [n).
[R ) < H [[[||] |||,, RR,,
R. H H R+)).
(78)
Since the minimum nonzero entry R y", it suffices for the error to below
max 4
Rg, R&ll || H
R. S 72/22
(79)
EE Pq]
to estimate all the edges in correctly, i.e., to ensure &. G. By shifting constants, this means
max R R. < "²"""
(80)
EE m
sufficient for (i) correct (soft) graph recovery, and (ii) for the error bound in 74 to hold.
Hard interventions. For the post-processing in hard interventions, we use the linear minimum mean square error estimator, which defined via a linear algebraic equation
E (1) = (f (O)) (f()),lp,, (i))
(81)
This part has three possible sources of error: Estimation of H,/2, finite sample estimation of covariance matrices, and incorrect graph estimation. Since with bounded error the graph will be correctly estimated, we focus on the other two. Specifically, ((), is actually defined via
22 ( = (.
(82)
which, whenever [E{(), E(gll || $ [1 ll. has an error upper bound
| - 2/,1 < 4 H HI - HH| + H [ip 21yll)
(83)
Given that (5 (pa),,, (i)) has bounded condition number, collecting constants, we get
E (i) 2 max
RR, - -R,l
(84)
sE(n]
and therefore, after update H, (I, H, the inverse transform estimate error becomes
E,
max iEIn
R., R.
(85)
If we use the error bound in Lemma with probability 1 - 5, we have
E, log(1/))
1/2
(86)
8t. Since the order of the error did not change, the required error level for graph recovery also remains in the same order.
In summary, ensuring that the precision difference estimation error is upper-bounded by
n²²" |
max R., R S
(87)
ensures that (i) the graph can be correctly identified, and (ii) the variables be recovered with error term in the same order as the precision difference errors, under both hard and soft interventions. This means that we can simply unify the constants by choosing the worst case, and use Lemma to prove Theorem which is restated here for the sake of completeness.
29

---

Theorem 5 (Sample complexity). For any instant of RO-CRL that satisfies st 2 (e,, where
N(e, 8) - C² max fE .max J loglog
(88)
under Assumption the estimate H, constructed in 111 for 19 and estimate Ge constructed in
(15)
ensure (e. P recovery of Zu and 9 under soft (or hard) interventions specified in Definition 1
This implies that with probability at least - 6, the error term E, specified in Definition 7 under both hard and soft interventions satisfies
EEl2 S C (oo+)g((/)))//z
(89)
Proof: Note that many intermediary results require the precision difference estimation errors to be upper-bounded. As such, provide error bounds where the error is required to be below a certain threshold. Then, the error bounds in Lemma B can be mapped to sample complexity statements to be used in our setting: With probability 6, the maximum error term in the sample covariance and precision matrices is bounded by if the instance satisfies
8t 2 Cee max 2
'mxx (d + log(1/6))
(90)
That is, if s, satisfies the above, for any (e, 6), the following error bounds hold with probability at least 1 - 6.
R R. e, ||
- S E
(91)
Then, given that Emax corresoonds to the maximum tolerable error level of analysis provided in this section, we get the error bounds and sample complexity statements for the CRL objectives provided in the theorem statement.
F Proof of Regret Upper Bound (Theorem 3
In this section, we prove the regret upper bound in Theorem 3 in three parts. For simplicity in notations, we provide the analysis for the setting in which the noise mean is known. The regret bounds for the more realistic setting in which the noise mean is unknown follow the same steps in straightforward way by padding dummy node to the graph and latent variables and noises, introducing one extra degree of freedom.
Part 1. we provide a decomposition of node-level utilities in Section F22 which provides the intuition behind our UCB construction (3T).
Part 2. Then we establish a more general bound than Theorem as Theorem 6 which holds under mild sader-sampling conditions. Its proof consists of four steps:
1. We show the system and its estimation error remain bounded in Section F.I and there is transformed linear SEM that 2n0 satisfies.
2. We show high probability ellipsoidal confidence sets for the parameter estimates A,, Aj and Og in Section F.3
3. We quantify how these uncertainties propagate along the causal paths in Section F4
4. Combining the above, we provide the high probability regret bounds in Section F.5
Part 3. Finally, leveraging Theorem 6 Part 2, we complete the proof of Theorem by choosing an appropriate fr(G.) to balance exploration and exploitation.
We will first prove all parts under known transformed mean setting, that is in for a E A, and then discuss how generalizes to unknown transformed mean setting. We emphasize that, although our proof follows the high-level structure of (23). it departs crucially in how we define the utility function and account for uncertainty in both 2apa i]] and Z[i), a direct use of their formulation leads to suboptimal bounds. Moreover, we derive instance destence-dependent regret upper bounds that generalize those in [23] Such refined bounds are essential in the transitive closure setting, where the maximum in-degree can be of the same order as
30

---

F1 Bounded System and Error Bound
F.1.1 Known Transformed Mean
Transformed SEM. As CRL, even in the infinite sample regime, only recovers the variables up to scaling, the estimates 70 do not obey the original SEM BZ E. Instead, we obtain the following system.
Lemma 5. As result of Theorem |
the estimated latent variables Zo are Markov with respect to the estimated graph Gxx. Specifically, there exist weight matrices A, A' E Ruxx such that
A --In-Ah - B)C² and A = A(I, B*)C"*
(92)
where a diagonal matrix chosen so that A and A' share the same support as B and B As result, ( and A [i are non-zero only if E (a) Finally, there exist exogenous-noise vectors E 2% (with independent entries) such that Zo follows linear SEM. For any time [N] and & a, the estimated variables follows the following linear SEM
Lxli, [A]; Zx 1] + & (5, f]
(93)
Similarly, i E a, alters the generating mechanism for node to
A t + 6 Lo, f] where we have at each time E N, the mean of the noises satisfies B[E = in under observation
2.0 (i,
(94)
and [0 [. 0f under intervention. And we use the term
vald = 1 E a} v1 + 1i ax) v/1l
(95)
Proof: Similar to
40 we know SEM follows
Z (In - (l-BB B)-
(96)
So under the infinite sample estimate and under t N with & a, we have the following relations
2 t] = H x:
(97)
CZ [:
(98)
C(I, B) -1
(99)
P (In A) Ae.
(100)
So that we have the relation
I A = AL, - B)C
(101)
Rearrange 1001 that we get
A I. A(I. - BjC-
(102)
And we know that = As. Similarly, the result holds for A * under E a,.
Similarly, the utility can be calculated
U(2) ŌT with 0 OC-!.
(103)
As A and A are problem dependent constant matrices with finite element, there exists m. R+ such that |[i mA and |A [i, S m and [0[i]| ma for i, E [n]] To simplify notation, we omit redefining other quantities (e.g. the intervention mean pa), which remain almost unchanged.
Cumulative estimation error. In Theorem 2 we characterized high- probabiityy bounds on Eg which captures the error in estimating Z, Recall that have scheduled 5, =²1 in Section and impose the following condition on forced exploration To and f())) for general regret upper bound.
68
To NV (Emaxx ÖnTT) and f((G.) ((emax de) We note that the setting adopt for Theorem later satisfies the above condition.
(104)
31

---

We know that at time t. Algorithm uses the estimates H. to estimate Z, only when there are no under-explored interventions. That is, we have for Ag the following condition holds
Na.: 2 ((.).) 2 (emax; 6t)
(105)
the following error bound Then according to Theorem we have with probability at least a
66
d log(1/6:)
E C
(106)
f((())
Define the error of estimating Z,, A, E Ruxtt by
A (H, H
(107)
For each s E [t], we have the following 2-norm bound for the error bound for the estimates for Zg at time as follows.
d log(1/6))
| s|1|2 - |2 2.11 mC
(108)
f(().)
where the first inequality holds due to the triangle inequality for norm, and the second inequality holds is due to (T06) and the boundedness of latent variables Z.
We define the estimation error of sample E [4] at time I N as
Z s| = 1: s) + Aeli, s]
(109)
Plugging (109) into the SEM in 93 and 944. We obtain at time
[t]
Z. s) A., [.0 + (I, Aa, )a.) + Eool::
(110)
Hence the error term e, E Ruxt in the finite sample SEM defined as
e| s] (I, Aa. (.
(111)
We can bound the above error for i E [n]] and s E [t] as
e s| s
In+1 Aa.li A s]]12
(112)
[T++1
Aa, I 1llll Ar(: 8]l22
(113)
d + log(1/5))
S m O'
(114)
fr(C,)
where we set C' C maxas.A max4e[n]
[|[ 1: which is an instant-dependent constant. We define the cumulative estimation error bound & at time 2 nTo as
d + (og(1/)))
G = t. C"
(115)
f((9.)
where C' is instance-dependent constant. This choice allows the following condition to hold.
z Σ e s]1
Vi e [m]
(116)
Remark 3. For the efficient RO-CRL, we need set the cumulative estimation error bound Ça as
d+ log(1/5.)
G
m C¹
(117)
fg().)
sE(e]
Or one can do more adaptive based on when you reset the whole estimates. The regret order of efficient RO-CRL will be the same RO-CRL but with larger constant multiplier.
32

---

Bounded variables. We have the following for the estimates for t E N
[ = [t
#||l < || Z [. f||2 _ || m
(118)
where the last inequality is due to the bounded variable | S m
Similarly, for all E [t] we have the following bound for Z, [: s] as
2 f s|] - [20l: + A.l: s|]l - | + ||A,[: s|]l S mm,
(119)
where we have defined
d log(1/6))
m ) -0(1
d fi(G.) )
m = | + C"
(120)
f((9))
Recall from 104 that
f((9)) 2 N (Emaxi =
(121)
Hence, we have
m = (())
(122)
F11.2 Generalization to Unknown Mean Setting
To handle an unknown post-transform noise mean, we augment the graph G with a dummy node, prepend I each variable and noise vector, and adjust the weight matrices accordingly. In such case, we define
ZP
(123)
Subsequently, the estimate time t is given by
1,
2 =
(124)
Z.
Analogous to Lemma 5 for all E N with a, 0. the padded variables satisfy
b.4 = AP. +
+ &
(125)
where we have defined A P E 1(++1)((++1)
0
and 211 (ooli 1
AP
(126)
A
Similarly, we can define the weights and noises under intervention as
A
and It =
(127)
A"
600 [: 1]
where the estimated mean values are
!
E| F. 4]
(128)
The weights for the utility parameter can be appended as
(129)
PC-1
Since the dummy node requires no estimation, the choice of & and the cumulative estimation error bounds remain valid. Consequently, identical order bounds apply both 2nd and 2,, as only an extra dimension of I has been added.
33

---

F.2
Decomposition of Node-level Utility
Similar to [21 Lemma IJ, we present following decomposition the expected utility value. Our design of the mean value estimator in the UCB definition in (3Tp is based on this lemma.
Corollary 1. When la is known, for intervention E A. the expected utility is related to the noise vector E via
Pa (0. 10.>
Σ A v/a 2=0
(130)
where A denotes the L-th power of matrix A.
Proof. We first show the results for the expected value of under intervention as follows. We know from the linear SEMs that
2,0 -In -
(131)
So. in linear SEMs, each latent random variable Z, can be specified a linear function of the exogenous noise variables e via recursive substitution of the structural equations. And the inverse has simple expansion since A, is strictly lower triangular. Specifically,
(In Aa)
In +
A
(132)
A
(133)
where 133 holds due to L the maximum path length and A becomes a zero matrix for 2 L 1.
Define the variable 2 2 H = A, 3 + & Hence, we obtain
2 = A 8.
(134)
t=
Since E and a are independent, the expectation each E, is for E [n]. and dummy noise. Then, we obtain the following results for the mean value
E|2 = Σ E
E
(135)
t=
[s
(136)
8=0 i=1
A V/a
(137)
Then, by the definition of expected mean of utility in we have
Pa [Z)]
(138)
= Ea(0 T Z + =Eul
(139)
10a 2 + svl
(140)
(2)
(141)
(0 Σ A V/a
(142)
t=
34

---

Under unknown transformed mean. Under unknown transformed mean, we are working with AP and A *p, we define the transformed weight matrix with padding as
A fi E ar) A + 1 & a + AP.
(143)
For the expected utility value under unknown transformed mean, have the following lemma. Lemma 6, Given intervention a E A. the expected utility value depends to the noise vector & via
L+1
Pa
Σ t=
A (.)0)
(144)
where A denotes the (-th power of matrix A.
Proof: The first few steps for the proof of Lemma still hold, with Ag and maximum length L + 1 instead of L due the dummy node, the changes in the proof start from [37 where we have
L++1 n
E|29|
=
Σ
A
pf
(145)
E=
1=1
L+1
A
[.0].
(146)
8=
Then, as the expected mean of utility defined in (2) we have
Pa
= [Z))(Z)
(147)
= Eal0 Z + sul
(148)
10a00 2P svl
(149)
= -0TEa((:
(150)
1++1
(0, Σ AP 01
(151)
t=0
F3 Proof of Concentration Inequality
In this section, provide the concentration inequality and then note how extend it to the unknown noise mean setting. We notice that certain parts of the proof can be replaced by a non-time-uniform argument (which does not improve the rate), focusing on the essential difference. We note we always work on the SEM associated with (93) and (94)
keep the same flow as previous results while
As the estimation quality is related to the degrees freedom, we begin by introducing the in-degree of our graph estimates. We denote d, as the number of parents of node in G. Then, by Theorem
2 together with our choice of the confidence levels {6,}. it holds with probability at least - 8,
ds,t pa(i) under hard intervention and d,,- = [in) under soft intervention with all i E [m] and
t N
Lemma (Confidence ellipsoids). With probability at least - 33., 3ör any node E [n]] and 2 1,
have
[[[A,] [A A..llll...VV...d--. S Br,(
(152)
[[[A]]: - [A [A'),ll IV.. S Bc,(
(153)
and |00 - C- C-'Ollva.Nooual-- -Vo.. S 3((b))
(154)
where m = 5(( + v (())() and
(r,((5)) 2 1 + Vdi,s + v 2 2og (n/6)) + du, log (1 + /
(155)
and B(())) + Vn + / 22o (1 (1/b)) + n log (1 + m2t/n(7
(156)
35

---

Proof: We observe that regressing [Z,] [er]: [ (1), restricted to time indices under the observational mechanism, yields an unbiased estimator of A. This connects the proof of our concentration lemma to prior results in robust causal bandits 23 However, a key distinction lies in the fact that both random variables on the node and its parent nodes pa,(i) have estimation errors. This introduces two sources of noise, which, if treated using previous techniques that assume noiseless anchors using regression [Z]; on [t)) would result in a multiplicative increase in the error. To avoid this, on the true variables. technic based on [29
the regression of [Zo]s [ex]: on pa,)p,
anchor instead of relying
We will provide the proof corresponding to the observational weights [A,]i. while the proof for the interventional weights [A;], and the utility parameters follows similarly.
We prove it by first establishing it for given time E Z. For any node E [n]. we decompose the error in estimation [Ar]s A.l AV..... for [1] follows.
A Aillv Ae.lv....V...dd--.
(157)
Vu. (2elpa.0) Wi,: ([Z)) - B) A,
(158)
Vee
12eopa, W. ((Z)); -(x)]: - i + [ex]i) - Ai
(159)
Ve.lVend Va
<
Ad]: A
+ (elpa Wisle
(160)
[...a. V...
I1: Stochastic and regularization crror
1z Fluctuation error
where A, refers to the auxiliary estimators which correspond to the ridge regression estimator when knowing the estimation error e, on Z,, i.e.,
[A]] [... pZ W., ([Ze]; [e:] 8)
(161)
Next, we bound the two error terms /1 and Iz.
Bounding Ji. The stochastic and regularization errors can be bounded by the following lemma. We notice we do not need the time uniform bounds, but non-time uniform bounds will not improve the regret order (See (30, Section 20] for a related example).
Lemma 8. For all node i [n]. for given E (T] with probability least
Sis we have
1 = [A.]. |A. A. Ailly A...v..VV...d S Vi, + 2
72 + di,t log 11
m2t
log
(162)
5
dr G2
Proof:
This lemma follows the result from 23 which based on 31 Theorem 1].
Based on Lemma g and our scheduling of 6, such that ΣtEn 8r = 8. we immediately have the following lemma
Lemma 9. For all node i E [ni), with probubility at least 1 - ô, for all E N, we have
4 Ac. A.
Vdd. AlI. S
+
2 log
12 + di,clog
1+
m²t
(163)
0,
dr
Bounding Iz. Now need to bound the fluctuation error 12, which can be decomposed as
1 [Vr..e]
1/212ellm W Wr.(e:]
(164)
Σ Wi,[s, (i) s) e s]
(165)
< Σ Werls, 8) [Vn
1 1/22,1pa, -1/22 (1), s) (r
(166)
36

---

Σ Wir(s, [Vr,,] 11/22, ppa, (t), s)
lerle, s]]
(167)
sE(t),ig,
Σ
Wa, e,
(x(pa .1/ Vandd-
(168)
sElj
Σ
W., e $)
Zolpa (1), s) V
(169)
sE
(170)
where 164 and (165) follow the definition of weighted norm and weight matrix, (166) and
167 hold due to the triangle inequality and weights are non-negative, (169) holds due to
J [ S ||: [ and 1770) is obtained using the definition of the weights and the property
& E
e [ 8] in (16).
Finally, substituting the results of Lemma 9 and 1700) with probability at least - 6, for all 2 0. we have
(
r2t
[|r]] Ail A. S1+ v di, +
v 2 2
+ di, log [+
(171)
dic?
Similarly, for the estimators for interventional weights, with probability at least - 8, for all 2 0. we have
( nd,
m²t 11
||A]] Ai..vv. $1+ /d, 22og
di log
(172)
di,
A similar proof can be get for the utility U where the in de-degree is and only concentration bound instead of n is needed, hence, with probability at least 8, for 2 O, we have
(5 + n log
m 1
||0c - 0 -V.oo..Ve...
I $1+
Vn+
2 log
(173)
n2
Combining the results in 171
172 and
173
we complete the proof.
Finally, in the unknown noise mean setting one simply replaces each d; by d; + (to account for the dummy node) and adjusts accordingly.
F.4 Cumulative Estimation Error
Lemma 7 in the previous section provides high-probability error bounds on our estimators. Due to the causal structure, these errors accumulate and propagate along the causal paths, leading to the estimation error in the utility. So we provide the following optimistic cumulative estimation error for utility U. To start with, we define the detailed cumulative uncertainty Ug,t E {u3,5, Ug,H).
is a root node mA E EjEra,()) (1) 4B + B,,t otherwise
and ug = mA Σ UgS5. + Bc.
43,4.1
(174)
Lemma 10. 18 = 9 or &. = for all E [N], and [A]; E Ci.e and [A*] E Ci for all E N and E [n] and 0, E for all 1 E N, then we have
1(A D]Ea. ((()) (Zoe(i < 2mh uaa
(175)
where un G... 9 and us i Gres and we define the term
4 MMnmmax
8
3T
B =
2 + E
(176)
Kmin
Kmin
37

---

4m
Kmin
T + am? ST
log
(177)
Kmin
m
where 7
m²m min
a
V
16
3
(max dj + 1)T6/2(T + +)) and
Litimax Emin
(12 + VF
E1
VF log
(178)
VIVE + +4+11)
am Miin
+ 4
log
(179)
7 1/5 44-11
1
8r
KmaxT am/ (i
(180)
S(n+1ITo
m
2m
+1.
(181)
S(n+1)T, T
3G
Proof: This proof is a cumulative estimation error at the node level of [23]. We first prove that when the conditions of the lemma hold, the latent variables i [n]] have cumulative estimation error as follows.
Lemma 11. I = or ف. for all E [N, and [A] E Ci. and [A*], E Ci2 for all e N and E [n] and 0g E Co all t N. then for i [n] we have
Σ 1 0.
2
E
2mn uB,
(182)
where u, = W.H if = and u, = uss G. = Sre that is defined in 35
Proef: We establish 182) via induction on the causal depth. We define the causal depth of node as the length of the longest directed causal path that ends at node i e [ri] in Go and denote it by L,,
Base step: L; = This is according the same proof in (23 with a change on m. and using the bounds for cumulative error that S.T, S C. S Çr for n'o S t T.
Induction Step. Assume that the property holds for causal depths up to L, k. We show that it will also be satisfied for L, = k + 1.
For this purpose, we start with the following expansion and apply the triangular inequality to find an upper bound for it.
1AA O.E
[
Z.(i, $]
(183)
( 0)E
[A....): -
(184)
T
= Σ
1(A UE 0)E |An..l (Z)lpa,))) (t),
t=1
1 (AA UE = 0) Eay (lAm, - (Am (p)
(185)
< mA
Σ
Σ I[AUE= = Fm
7D
2, 1| 2
(186)
jEpa.
where the transition to [85 holds due to the triangular inequality via adding and subtracting terms (A.,.) [2. (pa, (i), 4]: and 1866 holds since the triangle inequality of La2 norm and [(,,j S ma and similar proof as in the base step.
38

---

Next, we find an upper bound on the first summand in (86). We notice that the summation is taken over parents of node Thus, we aim find an upper bound for the error bound for each parent. Based on the induction assumption, for each node j E (1). we have
Σ1 -=1
b
t.. 1 2mBu..j.r
(187)
Subsequently, plugging 187 into 186).
we obtain
T Σ
114 0}
Σ
Ea. Zili Z.bi,
2
2mBusjj
(188)
(Epa (1)
(E)a
Combining the results in (166 and (188). we conclude
14A OJEa.
2 Ezli,t]
S Bug,
(189)
which proved the desired results in 182
Now we are ready to prove the final result for the utility function.
11 [AA = 0. Ú.(Z,) - (2r(tt)))
(190)
11 [A4 = 0, 2 - 0 -T 2r/::
(191)
Σ 1 [A (A = 03 OT, 2e(:,
T
{ UB = 0) (0. - 0) T 2,(3,t]]
(192)
S ( B)F.. [x [r. Bm
(193)
s 2mBug.T
(194)
Here we conclude the proof.
F.5 Proof of General Regret Bounds
Theorem 6 (General Regret upper bound). By setting confidence radius Bi,,(5t) and 3r(5.) according to Lemma 7 (&)) and To satisfy the condition in (104). If we define fr max f(().), then with probability al least 1 48, the average cunulative regret of RO-CRL is upper bounded by
Rr < Ö(nS + u((T u(VT++ +d+T)T*))
(195)
Proof: We start by defining the event in which, over T rounds, all confidence sets Ca,, contain the ground truth parameters f.. Specifically, Now define the eиror events E and ε for i E [r]] for each estimator
Vt [T]: Thorem 2hholds at time }
ÊCRL 4
(196)
E, A
Vt [T] [A], E C.a
(197)
Vt [T]: : [A*] E Ci.ee
(198)
39

---

Eg - vt E [T] : E Co.:
(199)
where the ()) and (6)) is chosen as in (155) and (156). Accordingly, define the event that at least one of the confidence ellipsoids of estimators does not contain the true parameters at at least one time index
n & (
n
n et n + P(ET9) + P(Ei)
ع E ECRL
(200)
By invoking the union bound on probability and Lemma 7 we have
P(ES) < IP(EERI.)
+
Σ (P(E))
(201)
8z
Σ 6
46.
(202)
n
n
1E2
2E
Next, we decompose the regret defined in under the events E.
T
B[RT| =
Ea.
(U(Z])
Ea. U(z)]
(203)
1=1
Σ
[A UE # #0} 2m + 1 0) (UCB.. -Ea, (U()))
(204)
S Snfr + Σ
11 1, 03E
UCB -Ba, [02l1UZ)0]]
(205)
T
nfr + Σ
1 1 = 0}
Ea, 10 [ūx) - Ea, (U(2)))
(206)
t=1
where we have used the set of incqualities
Ex- UV (Z.) I UCBa-(t) s UCB., (t) Ea, (Z()
(207)
Then using the lemma 10 and cumulative estimation S. defined in (115). we have
Rr S nfr + 2mBuggr
(208)
o (nfr u(VT + d
(209)
We note that the same results can be obtained for the unknown transformed mean setting.
E.6 Proof of Trade-off Upper Bounds (Theorem 3
Proof: Based on the Theorem 6. the remaining is to balancing the two terms
n2fr + ud'
(210)
while satisfying the condition
fe(ā.) 2 N (Emax: 8c) fi(G.) max max(d3 (d3n 3 3
(211)
Hence, by setting
2 13, N(emax 8:)3
(212)
where ue is defined as
0
if is root node otherwise
Wi.t EjEps,(6) Uj, + V (ia
and
U Uitt + Vn,
(213)
which establishes the desired result.
We note that the same proof steps work for the unknown transformed mean setting with the change in
40

---

F.7 Refined Upper Bound for Causal Bandit
Graph-dependent Bound Under the causal bandit setting, since ( Z[n], we eliminate all uncertainty in estimating the n-dimensional parameter t. In fact, we have Çe = for all t E [N] so no forced exploration needed. If we set G. = (or set weight matrices to I,), by applying Lemma] 1 in Section |.4 with the concentration inequality in Lemma 7 we immediately obtain our regret upper bound with high probability. From (209), we have with probability least 1 - 28, the regret bound of modified RO-CRL for CB is
RT S {O(UHAVT)
(214)
Graph-independent Bound To get graph-independent bound that corresponds the maximum in-degree dg and the maximum length of a causal path L. To match the corresponding lower bound that in the unknown transformed mean setting, we show the bound for "H,N in this region. In particular, we have
24-1
dgz + Vdold 1)
WHH dg
Edg 8=1
(215)
dg
As have the fact
v Vdg - 1)
d23
(216)
dg
So we obtain
WH,n = ((dg))
(217)
Hence, the regret bound for the modified RO-CRL for CB is
Rr S Ö(d/vT)
(218)
G Proofs of Lower Bounds
Equivalent definition of p. An alternative definition of p i 1 Ei= (p: 1) and p; is the number of causal path from noises to node i, which defined recursively as follows (on Gir).
On G:
if i is the root node Σ Ejean()) Pj +1 otherwise
P:
(219)
On Gtr:
1 p; Ejean() Pj +
if is the root node otherwise
(220)
G.1 Graph-dependent Lower Bound for Causal Bandit
Theorem 7. For any given graph G there exists causal bandit instance on such that the expected regret of any causal bandit algorithm is at least
R1 2 ((pn.T),
(221)
where Pn is defined in 211 on G.
Let II be the set of all policies on the set of stochastic bandit environments I, which contains all the possible bandit instances sharing the same DAG G and satisfying the conditions. The minimax regret is defined as
inf sup R n, IoTo xell I
(222)
41

---

where [Ry Tol denotes the expected regret of policy on the bandit instance To. We will consider set I, instead of I, that contains two bandit instances. By definition of minimax regret, lower bound for the regret of any policy on is also a lower bound for the minimax regret since
inf sup [Rr H. To] 2 inf sup RR n, ToT-
(223)
#ell IEEZ
senl IpEZ
Following this property, the central idea of the proof is as follows. Consider two linear SEM causal bandit instances that differ by a small fraction and are hard to distinguish. At the same time, we can construct them to have different optimal interventions, indicating that a selection policy cannot incur small regret for both at the same time under the same data realization. Note that the difference of the rewards, equivalently the regrets, observed by these two bandit instances under the same intervention can be computed by tracing the effect of the differing edge parameter over all the paths that end at the reward node.
We consider two linear SEM causal bandit instances 1, E Io that parameterized by - (B, B², and by / - (B, B', E). We note here that we assume the mean of the noise condi- tionally independent, that is, it can be dependent on the intervention. We note that the algorithm discussed previously can work under this setting without any modifications. For each node i [r]] in I, we have
Bern (1/2 1 6) (1rm(1/2)
i if E
(224)
where (g) denotes the Bernoulli random distribution with probability The noise is reversed in the second bandit instance I, which is
Bern(1 (1/2) ( +)
i
(225)
i
This is where the difference between the two bandit instances lies: if (i j) is edge in the graph, we have
B k [B] 1.
(226)
Except for this, all the rest are the same. Next, consider fixed bandit policy that generates the following filtration over time
F F a (aj. a,, Zz}.
(227)
The decision of π at time t is meea-reauurall.. Accordingly, define P. and P. as the probability measures induced by F, by rounds of interaction between т and the two bandit instances and I. When it clear from context, we use the shorthand terms and IP for Pr and Pr, respectively. We will show that ı cannot suffer small regret in both instances at the same time and under the same filtration FT-
By Lemma D since all the elements of observational and interventional weights are non-negative, the optimal intervention is the one that maximizes the expected value of each noise. The optimal action between two bandit instances only differs. This means optimal intervention for / is a 0 and that for I is in). Define E/ as the event in which the decision on node is supooptimal at least T times after T rounds on bandit instance I, i.c.,
T 2 2 for i E
E A
N
(228)
We note that the event Ej defined on the r-algebra defined by the filtration F,, that induces both IP and Pr., We compute the expected instantaneous regret when node is chosen sub-optimal in the first bandit instance, and the total regret is the summation over these nodes. Note that each path passes a node that node contributes to the expected regret. Furthermore, since every weight positive, in I, when a suboptimal action is chosen, the impact on average regret is determined by the number of paths that start from the node and end at the reward node n. Then, by the definition of εib, we have
T
R IP = Ep
140 - Pa.
(229)
42

---

Ep
1i a J +
(230)
iE/n]
P(E 6(mi,n + 1);
(231)
RE[n]
where (230) holds as we break down the regret and (331 holds due to the definition E in 228
Similarly, for 7, each node that is not intervened, it will occur at least ö(mi,n + 1) regret. Applying
the same steps as (229). 23Th. we obtain
RR
Ep
Mmal - Ha.
(232)
2 Eg
Σ
Σ
1li E a Jommn +1)
(233)
(T(T) iE(m)
T P(C))) 8(mi,n +1)
(234)
iE[n]
By combining (331
and 234
we have
T
R
+ R2
5
Pi,m (P(E) + P(E)))
(235)
2
iEinl
Next, we characterize lower bound PPE)) P(EtL) for i [n]. which involves the Kullback- Leibler (KL) divergence between IP and P. denoted by DEL (IP || PP.. For this purpose, leverage the following theorem.
Theorem 8 (Bretagnolle-Huit Huber inequality). Let P and be probability measures on the same measurable space ($2, F) and let A E F be an arbitrary event. Then,
P(A) + PP1)) 2
P))
(236)
2
By invoking Theorem g from 235
obtain
R2
IP| + R2
(man + 1)(p( + P(
(237)
2
T
(min + 1) exp( IP)),
(238)
T
Spn
P))
(239)
It remains to compute exp(-DRL. PP)) to conclude our proof, for which we leverage the following result.
Lemma 12. The KI. divergence between P and PP, the probability measures induced by Fs I and ī, is equal to
nT log (1 (1+22)) 25)(1 25)
DRL P)
(240)
2
Proof: Note that a Bayesian network factorizes as
P(Z
Z(n]) = I
(Z(( Z[pa())))
(241)
2=1
43

---

Additionally, the two bandit instances differ only in the mechanism of the first layer. Then, (PI PP) can be decomposed
(P P)
Σ DKL (P(Z Z(pa(i))) P( ([pa
(242)
By noting that the KL-divergence between two Bernoulli random variables with probabilities p and given by
DKL (Bern(r) Bern(g)) = r log ( + (1 r) log (122)
(243)
Since give (i)) the 7[1] under P Pand IP are both shifted Bernoulli random variables. From the above, we obtain for node E [n]
DEL (P(
(()) || [[ Z(pa(()))
Σ
DEL (Bern 2 + 6) || Ber(1/2))
(244)
Σ
DKL (Ber(((12))) || Ber(1/2 5))
(245)
AEfT
1 (i ar)
((=+0)
+22) (2+ log(1 + (
( 6) log(1 26)
(246)
T
1 ax) 1
Σ s=1
2 log (1+ 25) 26)
(247)
T
log
(248)
2
(1 + 20) 26)
where the last inequality holds since (1) +0) log( 1gg(1++0)) log(1+28)+ (4)()+2))+((-)))0
log(1- (20) < 2 log [T+2A](] 28)
for O < 8 < 1/2. And hence we have
DKL (P P)
T
log (a+
(1 26) 26)
(249)
2
we choose
VT to balance the terms in the lower bound, we obtain
1
max [R
IP). Rr
PI}
(RT
P + [R F))
(250)
238
T
5 Pr. exp(exp(- -D1I. || P))
(251)
248
Pnos(1 + +25) 226)
(252)
8
g Pn (1- T)
1
4 Tn/2
(253)
Tn/2
for T' 2 5, the term
(1
$
an increasing function of T' Hence, for T 2 have the
lower bound (1 $
Tn/2
0.22.5 By setting c 1 x 0.22.5 we have
max([Rr P). Rr P cp, VT.
(254)
G.2 Graph-independent Lower Bound for Causal Bandit
To get a graph-independent bound that corresponds to the maximum in-degree dg and the maximum length of causal path L. When L + 0 and d > 1, we have
g++ -
Pn
Σ
d2
(255)
dg -
t=
44

---

As we have the fact that
dg dl+1
dg - 1 - 2d
(256)
So we obtain
Pn O
(257)
Hence, the regret bound for the modified RO-CRL for CB is
[
PI, [T PJ 2 e dgvT
(258)
G.3 Proof of Reward-oriented CRL Lower Bound (Theorem
In Section G.1 we have shown a lower bound of Opnn vT) for the causal bandit. A similar result can be obtained for reward-oriented CRL as follows.
Corollary 2. When having the knowledge of & and Ho there exists causal model instance on Guo such that the expected regret of any algorithm is least
Rr 2 M(vTT),
(259)
where now p is defined on transitive closure Gic-
Proof: We set 0- 1, for both instances I and I. The proof then proceeds almost the same as for Theorem 7 with the only modification being the way interventions affect the utility. In this setting, each path terminating at node [n]] contributes
the overall utility. Hence, selecting the Σ JE(M) (m,. + 1). As counterpart of (237), we have
suboptimal intervention at node
T
R2 P +
R2
P
(ma, + L)(P(E)) P(
(260)
iE(n] jE(m]
>
(ma. + 1) 1))xp((-DDer) P)),
(261)
$Ein sE|n]
T
(P))
(262)
where the last formulation provides the p in the lower bound
Now we have shown the regret lower bound under the perfect scenario on the error E, = 0. Now we construct two more instances of causal models with E, occurring adversarially. We construct two instances of the causal model on Gie and demonstrate that under specific deviations, no algorithm can distinguish between them and the initial stage.
Let us examine the parameterization the two causal models, referred to as I' = (B, and 7' [B, B 8.. For the existing edges in graph Gecs (i,j) for < j and i, E [n], we define
[ [Bkk =
(263)
For the noises, for I' and 7' we define
lex 17 Eo ifi
ifi and [s: [e: Eo if c a
{
O
(264)
i
where Eo is constant that is defined later. And define the parameters 0 = 1, for both. Thus, the only difference between the two bandit instances lies in the mean of the noises. In the first causal model, the optimal action is when all the nodes intervened. In contrast, in the second causal graph model, the best action associated with all the nodes being not intervened.
We first consider any algorithm with forced exploration (or an under-sampling rule). Consider for time horizon T that the algorithm forced each intervention in Ag to perform Nr times, the Theorem provides the upper bound for the estimation enror
Ex = (v NT
(265)
45

---

We notice Eo controls the scaling of the system, and hence, controls the scaling of estimates and constants, By setting go such that |C ||E - O0 set E, adversarially as
d we have 6o O
d
We can
Ny
Nr
E, C
(266)
In such cases H, O, so that all estimates Z, O, no information is posted to the learner, and the learner cannot distinguish between these two instances. Consequently, there must exist bandit instance at which the algorithm plays the sub-optimal choice on each node i at least T/2 times. We note the sub-optimal intervention blocks the causal flow from an(i) de(i) {i} to the reward. Hence, we have the following reward decomposition
T
RT 1=
Σ
Σ
1(i ar) Σ
(m
Σ 1(k am) + +)) (267) AEde(()
(=(+1))N iE(m]
jEan(i)
where de(i) is the descendants of node and we note the term 1 & at) is used avoid counting any path more than once. By dropping the non-negative term associated with the 1 {kk & & a we can lower bound the regret by
T Σ
Rr 2
Σ (E()
[(iaa
Σ jEan(()
(mza + 1)60
(268)
(x+1)Nr
Similarly, we have
T Σ
RT M1
Eliia Σ
(myz + 1)80
(269)
jean(s)
By combining (268) and 269 we obtain
RR + [R I'] = pT
(270)
Hence, among these two causal graph instances, there will be at least one instance that incurs regret of
Rr 2 SppT
(271)
At the same time, the forced exploration period will incur a regret of order nNy. Combining the two we have
Rr 2 M(nNr + pT pT /d/Nr,
(272)
Lastly, we need a trade-off between the two. By setting Ny to be on the order
Nr d 2/3 2/3 2/3
(273)
This balances the two terms and provides the result.
RT 2 (d333)33T)
(274)
We note that the reward-oriented CRL method without forced exploration cannot leverage Theorem obtain meaningful regret bounds, all times we have H, and the regret scales linearly with T under the setting that ég = 1.
Finally, combining the results in (259) and (74). we know that there exist causal graph instance in I, I' and I' such that
Rr > Andtntp3 ppT).
(275)
H Multiple Interventions
In this section, state what changes are needed to adapt RO-CRL for multiple interventions per node. We focus on soft interventions, where hard interventions can be viewed as special case of this. To maintain consistency, redefine several key terms.
46

---

holds for H.1 Latent Data-generating Process and Intervention
Consider the case where there are possible distinct intervention mechanisms on each node i [n] We denote [B*] as the weight for intervention at node and define B as (B* {B*), i e [n]] the full set of such weights. We reserve B = B for observational weights, Similarly, we can define 5 for & & {O}U[s]. And we define the intervention as a vector a E [R(") in this case as afi] E [s] The intervention space has cardinality of ||| (s + 1)" instead of 2". Under intervention A, the follows the SEM
= B, 7 + ;
(276)
where we have
Ba]: = Bal
(277)
H.2 Algorithm Modification
Theorem 2 requires only one intervention per node, and its sample-complexity and error bounds remain unchanged. Hence, the CRL component of the algorithm requires no modification.
For UCB selection, *we let** [A]]: ** **denote the robust estimate for each intervention & E {0) as
[
A
V
[Zolpa.c W W.,,Z.], - - Ak {0) U [s]
(278)
where we have defined the weighted and doubly weighted Gram matrices as
V
Zulpa, W pa)) +I,
and VL. 12) 24 pa,()) + In.
(279)
Weight designs. The diagonal elements for weight matrices defined
1
W Wh, s) A 1 { = k) min (G (0))
(280)
Confidence ellipsoids. After performing estimation in each round, we construct the following confidence ellipsoids for k [ss]
c²t, {5 1|s [A il
W. S {B(((0))
(281)
H.3 Changes in the Regret Bounds
Theorem (Regret upper bound). Under Assumptions 7 average cumulative regret of RO-CRL is upper bounded by
with probability at least 45, the
Rr S d333d3n3 u33 + u(VST V3TT)
(282)
where we set = us for soft interventions and u uH for hard interventions..
The estimates 0, for and the confidence ellipsoids Cp., remain the same. We will skip some unimportant parts and focus on the changes under this setting. We refer the reader to [X for detailed steps. We notice the change mainly due to the changes in the following lemma and how we choose the confidence levels. We note that when m 1, the theorem reduces to the setting discussed in the main paper.
Now we discuss the changes needed for the proof steps discussed in Section
First, Lemma the discussion in Section F. still hold. Second, Lemma in Section H
all E [s] with mild change of
(o.) 1 ddi, + V log (kn/6.) + dr, log (1 + m2t//d
(283)
Now, we modify Lemma 10 to the following lemma.
47

---

Algorithm 2 Reward-oriented CRL (RO-CRL) for multiple interventions
1: Forced exploration. Sample To times for each intervention a E Ao.
2: for (n + 1)To,... do
D> Under-sampling rule 4: if' AA * then
3:
5: Pull a, random sample from A
6: else
7:
[> Latent recovery
8:
Update the inverse transform estimate H2 via 111
9:
Estimate Z, according Z, H,X,
10:
Update the graph estimate G. via (T5) if hard interventions then
11:
12:
Update the inverse transform estimate again using (99
13:
Update Z, according to 2, = H,X,
14:
Update the graph estimate again G, via 15 Parameter estimation
15:
Set weight matrix W according
280
Wa, according to 25
17:
Update A and A₂ according to (278 and 26 respectively
Set A 0 under hard intervention.
19:
t> UCB selection
Compute aCB according to (1 for a E A.
21:
Pull a++1 arg max UCBa.
Observe X, and (Z,)
Lemma 13. 1ʃ = G G. Gcc for all E [N, and [A]e E Ci,t and [A^] E Ci, for all E N
and E [n]] and 0g E for all t N, then we have
I1A OD Ü(()) U I 2mB UST Vs.
(284)
Proof: The changes to the proof are mainly in the Base step, where we aim to prove the following. For node E [m]] with causal depth L; show that
T
Eac
2,
S 2mmug,
(285)
where B' is defined as
4 MmKmax
3(s + 1)3T
B'
T
+ El
(286)
Emin
Kmin
4m
Kimin
+ (s 1)
log
+ tam²
Cr.
(287)
Kmin
s s+1
and E, is defined as
E = (s+ 1)
VinKmax Amin
T VFlog
1++1 + VF) +4+1
(288)
V s+1
am
+ 4
log
(289)
VAV
14 44-1
+ 87
Kmaxt + amm²
(290)
48

---

2m
+1
(291)
S(n+112 3((++))b
When the causal path of a node L3 = 1, according to SEM defined in 93 we have the following expansion:
T
Bas
[1]
Bm,
1 2e (p((p
[A 2.
(292)
Bag
sup by AeCiiaa
||b ballvi.n Viss
(293)
Zc(pa
(294)
V Ve -Vann
T
<
x
Nitt
(295)
where we define
Xmax
Viae,e
dct
(296)
Amin
Vi,ar.t)
Then, the weights we defined are bounded the range çam i we define the following constants. Note, we drop the index / for these constants, but they are variable of time.
1 for t E N. Leverage these bounds
Sen Kynin
A
Emin
and
Emax
(297)
Emin
G.m
Kimin
and
Emax
Kmax
(298)
1 n7c
m
VGe in
and
(299)
G.
In order proceed, we need upper and lower bounds for the maximum and minimum singular values of a These bounds depend on the number of non-zero rows of Ug matrices, which equals the values of the random variable Ni, Let us define the constant
7/ A max (am² Nom²Vnn,co a²,,mm"))
(300)
% A max (am² a² m²
(301)
%. A max (a,""V
Vn [T).
(302)
Then for every t e [T], and n E [t]. we define the error events corresponding to the maximum and minimum singular values of Ug, and U,, as
Eim,, A o{
No. and
{amin (Uee) S v /max {0, nsimin %
or Tmax (Ui,)) 2 / /nnxmax + t / J.
(303)
Ex,
A of No. = and {auin (U:.) S / /max (0, nimin 7n)
or Fmax (U..) 2 / nimmaxx + 77o) }
(304)
49

---

Similarly, we can define n, and Ei by replacing Nr. and Us. (or Us,e) by Ny, and U. (or ( respectively.
As result of 22 Lemma 8), if we define the union error event & as
E - (t. :t.n))tee [T]. [t], Eim, or Ein,
(305)
We have
3a
P(E,.) & 2NT(T + + 1)
(-
(306)
16
Bounding term E
1(E,u) Ei |
Same 23
the fact that S. increase with time t
and obtain
Σ m2t +1
2m
+
(307)
Sin+1)za T
36(n+1y26
t=1
Bounding E [188 Et= \..
We define the function h(x))
Thimax + 7n +I M(x) max {0, IK min 7 +1 I x> 0.
(308)
And we define the function when æ > as follows.
g(x, (t) A V [Fimax + orr V IKmin/ am? VI
(309)
IK im am V
We have the following theorem to show the monotonicity and relation h(x) and g(z).
Lemma 14. 123 Lemma 10] l(xx, (t) and g(x, (i) are both decreasing functions of x when x and h(x)) g(x), where is defined as a²
Now we are ready to bound the last term
T
E
Σ
AcE
< E
h(N...))
(310)
1=1
t=1
We define the set of time indices at which the chosen actions are under-explored as
H: (t [T] Ni S 4T}.
(311)
It can be readily verified that [Ha| < 8r. Furthermore, when Hi, we have
h(x)= < S(n+1)70 V Kmmxx + am? /F +1 ST..
(312)
Then we can bound summation when Hi occurs as follows.
T
S i(t H.)h(Ni... (t) S 87
Kmaxx ami am/2
(313)
Now we only need to bound the remaining part when & H4
E
I llte HH)M(NN
(314)
1=1
Note that when E HGS we have Ni and
h(NN,a..))) S g(Niaa
(315)
50

---

Now we discuss the major changes. We define the number of times that node is under mechanism k {0} U [s] at time t [N]
NEA
1(all =3
(316)
Using the above results and noting that H2 excludes those samples from initial rounds, we obtain
T
T
Σ 1ft E HV)h(Naa.))
&
att E (N
(317)
N,KTT
gn, Ct)
(318)
[E(+)
mm47+1
We bound the discrete sums through integrals and define
G+(y)= - <-( g(x)dr, y y 4T
(319)
x=
Since g(x) is a positive, decreasing function, for any & E N, 2 4T + we have
( S
g(z)dr (r()))
(320)
4=1++1
s=tr
Then, the summation in 318
is upper bounded by
Nake Σ
g(n) S Σ G.(N...).
(321)
RE(()
47
RE(4
Since g(x) is positive and decreasing, and G(y) is defined as an integral the function with positive first derivative and negative second derivative, it can be deduced that G is concave function. Thus, we have
Σ G.(NE,.T) s (8 + 1)G, (TT1) kE
(322)
Next, proceed to establish upper bound for the function G, which can be upper bounded as g(x)do
G
+ 4T)
(323)
8
8+1
+4r
m 2xmax
1
dr
x=
Kiin
Vitimin
/TKunin
1/1
jam²(1 + MKmax
Elimin m am2 Vxx dx
x=
Funin
- +1r
ST
IKuin /m amm dx
(324)
s=Ar
(V s++1 + Volog V (
< 2 Mikmax
T
Kmin
Vi T
s41 VI+1
T
3
2
log
Aimin
8 s
VV + + V4-1
2m log
Aamin
+ am?²
x+1
+
Cr.
(325)
Kunin
51

---

where (324 is due to the inequality v S VI+ and - and closed-form integral and discard positive terms in (32).. Combining the results in (307 (13), and (325), let E1 denote the accumulation of terms that exhibit at most logarithmic growth rates with respect to T and ÇT-
when
(V T
/msmux Volog
E (8 1)
V
+ VF
(326)
Kminn
amm's
V
T s+1
44+1
+ V
log
(327)
V
T s+1
+ V4
1
+ 87
Kmaxx + -am² V +
(328)
+ 771
2m
+
+1
(329)
S(n+1)20
3(in+)/To
Therefore, the final result for the bound is
T
4 MArmax
8
3(8 + 1)3T
E
Σ
Ait
T(s 1)+
F1
(330)
Kmin
Kinin
2
+ (s + 1) 4m
log
Kmin
++1* + am?
T
GT
(331)
fimin
And the rest of the proof remains almost the same, with only a difference confidence constants.
I Remark on do interventions
In this section, we discuss the results for do interventions, further restricted type of intervention. It a subelass of hard interventions in which intervention on node removes both ancestral connections and the randomness of 7[1] and sets the noise variable e [i] to fixed known value.
Remark 4 (do interventions). Under do interventions, there exists set of n + interventions such that getting one sample from each suffices to construct Hoc for which H G is a full-rank diagonal matrix. The resulting regret bounds depend on the causal model assumptions. For instance, in the standard setting where each latent variable Z E for E [k] with intervention space A= = [k]" and the conditional distributions pa (Z] [ppa(il) are arbitrary, all latent variables contribute to the utility node. In this case, the problem reduces to a multi-armed bandit, with a matching regret bounds scale as TT even without the latent recovery.
Broader impacts, Limitations and Further Discussions
This paper is purely theoretical, and the experiments only use synthetic data, so we are not aware of any negative societal impacts. Our principal limitation is the assumption of linearity. Specifically, we assume linear structural-equation models, linear transformation models, and linear utility functions. However, these assumptions are standard in both causal bandit and causal representation learning work under soft interventions, with the non-linear setting remaining largely unexplored. Extending reward-oriented CRL beyond linear models, therefore, remains an important avenue for future research.
We note that even in the simpler contexts (e.g., CRL or CB), the linear versus nonlinear models are investigated extensively. Here, we outline how each component can be individually generalized. To provide a concrete methodology for extensions, we first note that our current analysis consists of two parts: (i) analyzing finite-sample guarantees of a CRL algorithm, and (ii) analyzing how the CRL guarantees translate reward guarantees. We discuss how the same decomposition can address nonlinear models as well:
52

---

Latent SEM: It is possible to generalize the algorithms and performance guarantees to nonlinear SEMs. While the overall RO-CRL framework and pipeline remain intact, such a generalization has two distinct implications: one for the CRI. guarantees and another for the CB guarantees. On the CRL side, the subroutine can be replaced with methods designed for general SEMs that also provide finite-sample guarantees (e.g.. I. As result, the performance guarantees stated in Theorem 2 would need to be adjusted accordingly. On the bandit side, the UCB rule and reward estimators can similarly be replaced with their counterparts developed for nonlinear causal bandits (e.g., [20 24). Such generalization, however, is highly non-trivial and even in the simpler contexts (e.g., standalone CRL and CB), the linear and nonlinear settings are investigated separately, each with its exclusive technical challenges.
Transformation: There are existing results for CRL under nonlinear transformations [10 12]. However, finite-sample analysis of CRL under general transformations is still an open problem. Nevertheless, we note that any future finite- sample result can be integrated into our RO-CRL framework to extend it to nonlinear transformations: Given that the estimator provides graph and variables recovery error bound similar to Theorem 2, these estimates and error bounds can be used by the robust causal bandit algorithm. Similar to SEM generalization, long the setting does not violate the CB assumptions, the overall pipeline would work.
Our utility-function assumption is direct extension of the latent SEM one. Specif- ically, the framework can be modularly generalized to accommodate non-linear utilities when adopting the robust non-linear estimates in bandit settings. The key open question, therefore, is the same one that arises for latent-SEM causal-bandit methods: How robust are these algorithms to violations in the underlying variable?
Utility:
In all three cases, the structure of the analysis, error control in CRL, followed by robust bandit optimization, remains valid. The main requirement is that the substituted components provide compatible error guarantees.
Potential use cases for RO-CRL. Finally, we list some domains where latent interventions are plausible and RO-CRL could be applied.
Robotics: Consider a robot operating in an environment and observed through high- dimensional sensory data such as images. Interventional CRL enables recovery of in- terpretable latent factors (e.g., joint angles) that causally generate visual data. CRL is particularly suitable for robotics in vision-based contexts because high-dimensional obser- vations (images) obscure the causal variables and robots have known or assumed causal structure (c.g., a joint causes an end-effector position). In robotics, interventions on the latent variables can be achieved physically or via simulation. Physical interventions include, for instance, directly changing a joint angle or velocity (e.g., move joint 3 by +5") and moving the robot gripper to fixed position while leaving other joints free. In this context, an example downstream objective could be moving the robot arm to specific configuration using only the utility values and learned latent factors as control input.
Genomics: In gene regulatory networks, we observe high-dimensional expression data, typically measured from bulk or single-cell RNA sequencing. These arise from lower- dimensional latent variables representing unobserved biological drivers such as transcription factor activities, regulatory protein states, or signaling pathway activations. CRL a natural fit for gene regulatory analysis because gene expression is influenced by structured, latent causal process involving transcriptional and post-rransciiptional regulation. Standard repre- sentation learning techniques fail to recover biologically meaningful variables, often mixing causal and non-causal factors. Node-level interventions in the CRL framework correspond to perturbing individual latent regulatory variables. In gene networks, such interventions are biologically realizable via gene knockouts or CRISPR interference to silence specific genes or transcription factors and overexpression systems to activate regulators, to name few. this context, an example downstream objective could be to optimize a certain type of biological response over the set of some possible genetic modifications.
53


Reviews:
[{"review_id": "VTD7aWMyXw", "reviewer": "Reviewer_Z2af", "summary": "This paper introduces reward-oriented CRL, which shifts the focus from perfectly recovering latent causal representations to learning them only to the extent needed for optimizing a downstream reward function. The authors consider linear structural equation models (SEMs) with linear transformations mapping latent variables to observations, and linear utility functions. They develop the RO-CRL algorithm that adaptively explores interventions while maintaining confidence bounds, providing finite-sample identifiability guarantees and regret bounds of $\\tilde{O}(d^{1/3}n^{1/3}u^{2/3}T^{2/3} + u\\sqrt{T})$ for soft interventions, with nearly matching lower bounds.", "questions": "1. Could the precision matrix approach generalize using kernel methods or neural approximations for the nonlinear setting?\n\n3. How does $u$ scale with graph properties in typical instances? Can you provide examples where the gap between $u_S$ and $p$ is large vs. small? This would help understand when the bounds are truly tight.\n\n4. What happens when Assumption 1 is violated (i.e., interventions only affect noise)? Could the algorithm be modified to handle or detect such cases?\n\n5. What is the per-round computational complexity of RO-CRL? The eigendecomposition in equation (11) and matrix inversions throughout seem expensive for large $d$?\n\nNot a question but the work of Chen et al. NeurIPS'24. \"Identifying General Mechanism Shifts in Linear Causal Representations\" seems relevant as additional CRL literature. There, the authors indentify general interventions under a similar linear CRL setting.", "limitations": "I have only skimmed over the appendix so far. The authors could discuss further:\n- Computational scalability concerns for high-dimensional observations\n- Sensitivity to assumption violations (especially bounded noise and known parameter ranges)", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n**Quality:**\n- The paper provides rigorous theoretical analysis with finite-sample PAC identifiability guarantees (Theorem 2) that extend beyond typical asymptotic results in CRL\n- The regret bounds are nearly tight, with upper bound $\\tilde{O}(d^{1/3}n^{1/3}u^{2/3}T^{2/3} + u\\sqrt{T})$ and lower bound $\\Omega(d^{1/3}n^{1/3}p^{2/3}T^{2/3} + p\\sqrt{T})$ differing mainly in graph-dependent constants\n- The algorithm design cleverly balances CRL objectives with bandit optimization through weighted ridge regression and UCB-based selection\n- As a special case, the framework improves existing causal bandit bounds from $\\tilde{O}(d^{3/2}L\\sqrt{T})$ to $\\tilde{O}(d_G^L\\sqrt{T})$\n\n**Clarity:**\n- The paper is well-structured with clear motivation for task-oriented CRL\n- The algorithmic components (forced exploration, adaptive exploration with CRL rules, UCB selection, and under-sampling) are logically presented\n- Mathematical notation is consistent and appropriately defined\n\n**Significance:**\n- Addresses a fundamental gap between CRL's goal of perfect recovery and practical needs where coarse representations suffice\n- The framework naturally connects CRL and causal bandits, two previously disparate areas\n- The finite-sample analysis is particularly valuable for practical applications\n\n**Originality:**\n- The reward-oriented perspective on CRL is novel and well-motivated\n- The technical approach of using precision matrix differences for simultaneous graph learning and intervention optimization is creative\n\n## Weaknesses\n\n**Quality:**\n- The restriction to linear SEMs and linear transformations is certainly limiting\n- The assumptions (particularly Assumptions 1-3) are somewhat strong: bounded noise, known ranges for parameters, and intervention effects on weight matrices.\n- The dependence on the uncertainty parameter $u$ in the bounds is not well-characterized in terms of problem instances\n\n**Clarity:**\n- The relationship between $u_S$, $u_H$, and $p$ in the bounds could be explained more intuitively\n- The weight matrix design in equations (24)-(26) appears ad-hoc and could benefit from clearer justification\n- The transitive closure recovery under soft interventions vs. exact graph recovery under hard interventions needs better exposition\n\n**Significance:**\n- The improvement from $u$ to $p$ in bounds may not be substantial in many graphs where these quantities are similar\n\n**Originality:**\n- While the reward-oriented perspective is novel, the technical tools (precision matrices, ridge regression, UCB) are somewhat standard", "was_revised": true, "final_justification": "The authors addressed my questions. I think it is a good paper.", "rebuttal": "**Q1. Generalize precision matrix to nonlinear settings.** Yes, such generalizations are indeed possible. We kindly refer the reviewer to our reply to “Latent SEM” in **Question 1. Generalize to non-linear setting** in the response to reviewer dqb6 for a detailed discussion of this subject.\n\n**Q2. Scaling of $u\\_H, u\\_S, p$.** Thank you for raising this point. Under hard intervention, $u\\_H$ is upper bounded by $d_{G}^L$. Under soft intervention, the terms $u_S$​ and $p$ both grow at the same rate, which is exponentially with the number of nodes $n$ in most graphs. As a simple example, consider a chain graph, where each node $i$ is a child of node $i-1$. Hence, the ancestor set of node $i$ will be $\\\\{1,2,\\cdots, i-1\\\\}$. Since both $u$ and $p$ (with equivalent definition in (217)-(218)) involve summation over the ancestor set, they both scale as $2^n$. \n\nBeyond scaling similarly, we can also quantify the reward gap by comparing their growth rates. Since the difference in $u$ and $p$ lies in the uncertainty added at each layer ($\\sqrt{|An(u)|}$ vs. 1), the gap does not exceed their exponential growth. Based on this, we can show that the ratio of $u\\_S$ to $p$ converges to a graph-dependent constant $c$ for common graphs. For instance, we have $c \\leq 1.21$ for the hierarchical graph and $c \\approx 1.174$ for the chain graph. This indicates that the upper bound on regret is only a constant factor larger than the lower bound. \n\n**Q3. Violation of Assumption 1.** Thank you for the thoughtful question. It is shown in [3, Appendix B] that without this assumption, the causal graph is *not identifiable*. For instance, without this assumption, we cannot distinguish between 2-node graphs with and without an edge. Since performing any downstream task hinges on an identifiable underlying causal model, if this assumption is not satisfied, we can information-theoretically argue that no algorithm can have a provable guarantee. We will add a remark right after Assumption 1 to show its fundamental connection to identifiability guarantees in CRL.\n\n**Q4. Per-round computational complexity.** The computational cost can be broken down into two parts:\n1. **CRL:** Complexity of eigendecomposition and matrix inversion are both $O(d^3)$ and thus expensive for large $d$. However, since the transformation is linear, detecting the supporting subspace is simple: given that the observation model $X = g(Z)$ is noise-free, it suffices to collect $n$ samples to learn this subspace, which can be achieved during the initial forced exploration phase. Projecting all observations $X$ to this subspace (of dimension $n$) before doing further processing significantly improves scalability.\n2. **UCB-based selection:** The computational bottleneck is the intervention‑selection step. Solving the UCB rule is intractable on general causal graphs (see [25, §3.3]). In practice, we may adopt the following procedure.\n    - Non‑negative edge weights and noise (shifted system): We can add a shift to the system to make the system non-negative while not impacting the order of regret. Because all rewards are monotone in their parents’ variables, we can calculate the UCB by sequentially maximizing nodes in causal order and using the closed‑form in linear bandit. The resulting worst‑case complexity is $O(n\\*d\\_{\\hat G\\_t}^3)$, where $n$ is the number of latent dimensions and $\\hat d\\_{G\\_t}$ is the maximum in-degree in graph $\\hat G\\_t$\n    - UCB upper bounds: [25] proposes techniques that efficiently compute an upper bound on the UCB. These could be incorporated into our approach. But the upper bound is loose in practice, and their robustness to imperfect latent recovery is unknown.\n\n**On Chen et al. NeurIPS'24.** Thank you, we will include the reference in the final version of the paper. This paper’s setting and corresponding finite-sample results may provide another way to derive reward-oriented CRL results similar to our paper.\n\n**Quality 1. Restriction to linear SEMs.** We kindly refer the reviewer to our reply to **Question 1. Generalize to non-linear setting** in the response to reviewer dqb6.\n\n**Quality 2. Assumptions.** Our assumptions are standard, and some are necessary for identifiability guarantees of CRL and finite‑sample guarantees. More specifically:\n\n- *Assumption 1*. As noted earlier, without this assumption, CRL becomes unidentifiable. We will add a remark to clarify the necessity for this assumption.\n\n- *Assumption 2.* The boundedness of the weight matrices is not a critical issue. In the CRL setting, latent variables can be recovered only up to a scaling factor, and this level of recovery is sufficient for downstream tasks (even for reconstructing X). This is because the system X=G⋅Z is equivalent to X=(aG)⋅(Z/a) for any nonzero scalar a. Therefore, if we recover Z/a instead of the ground-truth Z, we can compensate for the scaling by estimating the transformation as a instead of G. In this sense, recovery of the latent variables is exact up to scaling, that is, any element of the set {Z/a:a∈R} is equally valid. Consequently, imposing boundedness on Z does not compromise the results. This boundedness can, in fact, be equivalently modeled by requiring the weight matrices that govern the dependencies among the coordinates of Z to be bounded.\n\n- *Assumption 3.* The primary goal of these assumptions is to assume a bounded system. Even in the simpler linear bandit setting, where the reward node is a child of all other nodes and there are no additional causal relations, analyses assume bounded feature vectors and weights [R1, R2]. Our causal setting naturally generalizes from that to SEMs, where we require the parents of each node to be bounded, which is the result of bounded weights and noise terms. These assumptions are standard in the causal bandit literature (e.g., [21]).\n\n[R1] Abbasi-Yadkori et al. Improved Algorithms for Linear Stochastic Bandits. NeurIPS 2021\n\n[R2] Flynn et al. Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures. NeurIPS 2023\n\n**Quality 3. Dependence of bounds on $u$ .** In equation (35), we specify the parameters $u\\_H$ and $u\\_S$ in terms of the graph topology. We acknowledge that using the notation $u\\_m$ to refer to $u\\_H$​ and $u\\_S$​ may create confusion, as it could be interpreted as a separate parameter. We will revise the notation to avoid this ambiguity.\n\nTo interpret (35), note that the parameter $u$ captures the cumulative uncertainty in the reward due to the estimation of latent SEM parameters. These uncertainties propagate along the causal paths from the root node(s) to the reward node. Accordingly, we define $u$ to reflect the accumulated uncertainties in estimating the weight matrices along these paths. This accumulation is expressed through the summation terms in (35). We will add a clarifying comment after the equation to make this interpretation explicit.\n\n**Clarity 1. The relationship between $u\\_S$, $u\\_H$, and $p$ in the bounds.** Please see the response to Q2.\n\n**Clarity 2. The weight matrix design in equations (24)-(26).** Thanks for asking us to clarify. We give lower weight to recovered latent variables that appear uncertain, based on the data collected so far. The weight matrix design is carefully crafted to keep our estimates tight and makes the confidence radius $\\beta\\_{i,t}$ in Eqs. (27)-(29) independent of the running estimation error, which feeds into the reward. It handles two kinds of uncertainty:\n1. Overall estimation error  (captured by $\\zeta\\_t$): When this aggregate error is large, we down‑weight all samples, requiring more evidence before drawing overly optimistic conclusions.\n2. Sample‑specific uncertainty: A weighted $\\ell\\_2$ norm acts as an exploration bonus, reducing the influence of individual samples that sit far from the population in linear regression and may be noisier than others because of imperfect recovery.\nBy integrating these two factors, the weighting mechanism focuses learning on the most reliable information rather than relying on ad‑hoc choices.\n\n**Clarity 3. The transitive closure recovery under soft interventions vs. exact graph recovery under hard interventions.** Thank you for the suggestion. We will add explanations for why there is fundamentally such a distinction in observation between hard and soft interventions. For that, we will cite the known impossibility results that establish that such recoveries are the best that can be guaranteed under the specified interventions.\n\n**Significance. The improvement from $u$ to $p$ in bounds may not be substantial.** We would like to clarify that $u$ and $p$ being close is a *desirable* property. These terms do *not* represent improvements. Rather, $p$ appears as a constant in the lower bound and $u$ as a constant in the upper bound. Therefore, having these two constants be as close as possible is desirable, as it establishes the tightness of the bound.\n\n**Originality. While the reward-oriented perspective is novel, the technical tools (precision matrices, ridge regression, UCB) are somewhat standard.** We note that some of the results/analysis in CRL do not have precedence in the CRL literature and can be considered contributions to that literature too (e.g., finite-sample guarantees under hard interventions). We do recognize that some of the techniques used in the causal bandit aspects are not entirely novel (although some aspects are novel, e.g., graph-dependent analysis versus worst-case analysis in the literature). \n\n**Limitation 1. Scalability.** Addressed in response to Q1.\n\n**Limitation 2. Sensitivity to assumption violations.** We provide additional experiments for violations of all assumptions. We kindly refer the reviewer to our “Assumption Violations” part in **Additional experiments** in the response to reviewer FrNT."}, {"review_id": "kiosAmNuAl", "reviewer": "Reviewer_dqb6", "summary": "This work considers the problem of causal representation learning from a reward-oriented perspective, where, contrary to prior works which optimize for perfect identifiability, they optimize for the coarsest level of identifiability for a specific downstream task. Focuses on the specific task of identifying an optimal set of interventions as specified by a linear utility function in terms of the latent variables. Considers linear SEMs with linear transformations to the latent space. Provides an algorithm, RO-CRL, for the reward-oriented CRL task under hard and soft interventions and specifies regret bounds for both settings.", "questions": "1. The SEM, transformation and utility function all being linear seems restrictive. Could these results be extended to any nonlinear setting?\n2. Is the dimension of the latent space assumed to be known a priori? If the causal variables are inherently latent, how could you know how many there are?\n3. Similarly, why can we assume that interventions on single latent variables aren’t actually affecting many latent variables?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This work addresses a key gap in CRL literature by developing methods that achieve identifiability only to the extent necessary for maximizing performance on downstream tasks. Current works focus primarily on perfect identifiability, requiring an excessive and arguably unrealistic number of interventions, thus making this work potentially more applicable.\n2. All proofs and theoretical findings seem correct.\n3. Paper was generally well written and enjoyable to read.\n\nWeaknesses:\n1. My primary concern is that the paper claims that prior works focused on perfect identifiability employ an ‘excessive’ number of interventions to achieve perfect identifiability; however [3] (as cited in the manuscript) indicates that a single atomic intervention on each node is sufficient for identifiability, where RO-CRL enforces more interventions than that in just stage 1of the algorithm. This seems misleading and questions whether this work is really capable or discovering meaningful causal representations more efficiently.\n2. Stage 1a and 1b of RO-CRL seems to indicate the ability to take both hard and soft interventions as desired; however, given the interventions are on unknown latent variables, it seems restrictive to think that you could know entirely whether an intervention is hard or soft.\n3. The work includes very limited synthetic experimental results and no real-world experimental results. It would be very interesting to see a real world example of how your approach could learn representations geared for a specific downstream task.", "was_revised": true, "final_justification": "The authors sufficiently addressed my concerns outlined in Weakness 1 and 2. While I believe this method to be very interesting and important for the field of CRL, which can sometimes feel impractical due to the infeasibility of many assumptions needed for perfect identifiability, I have questions regarding how this method will work in practice. For instance, I am not convinced that knowing latent dimensions and latent factors a priori is realistic or that methods could even have the ability to intervene on all latent variables. Real-world experiments would have been great, but I understand the difficulty given the lack of datasets. \n\nUltimately, I believe the work is interesting enough and has enough potential to be accepted, but I still remain underconfident in my evaluation.", "rebuttal": "**Q1. Generalize to non-linear settings.** Thank you for the question. While linear models represent an important class of causal models, transformations, and rewards, we do agree with the reviewer that generalization to nonlinear settings is also important. We note that even in the simpler contexts (e.g., CRL or CB), the linear versus nonlinear models are investigated extensively. Here, we outline how the linear SEM, linear transformation, and linear utility can be individually generalized. To provide a concrete methodology for extensions, we first note that our current analysis consists of two parts: (i) analyzing finite-sample guarantees of a CRL algorithm, and (ii) analyzing how the CRL guarantees translate to reward guarantees. We discuss how the same decomposition can address nonlinear models as well:\n- **Latent SEM:** It is possible to generalize the algorithms and performance guarantees to nonlinear SEMs. While the overall RO-CRL framework and pipeline remain intact, such a generalization has two distinct implications: one for the CRL guarantees and another for the CB guarantees. Setting aside the technical details, here is a high-level description of how this generalization works. On the CRL side, the CRL subroutine can be replaced with methods designed for general SEMs. For example, [11] provides an algorithm along with finite-sample guarantees applicable to general SEMs. As a result, the performance guarantees stated in Theorem 2 would need to be adjusted accordingly. On the bandit side, the UCB rule and reward estimators can similarly be replaced with their counterparts developed for nonlinear causal bandits (for instance, those based on Gaussian processes or neural networks [20, 23]). Such generalization, however, is highly non-trivial and even in the simpler contexts (e.g., standalone CRL and CB), the linear and nonlinear settings are investigated separately, each with its exclusive technical challenges.\n- **Transformation:** There are existing results for CRL under nonlinear transformations [9, 10, 13]. However, finite-sample analysis of CRL under general transformations is – to our knowledge – still an open problem. Nevertheless, we note that any future finite-sample result can be integrated into our RO-CRL framework to extend it to nonlinear transformations: Given that the estimator provides a graph and variables recovery error bound similar to Theorem 2, these estimates and error bounds can be used by the robust causal bandit algorithm. Similar to SEM generalization, as long as the setting does not violate the CB assumptions, the overall pipeline would work.\n- **Utility:** Our utility‑function assumption is a direct extension of the latent SEM assumption. Specifically, the framework can be modularly generalized to accommodate non‑linear utilities when adopting the robust non-linear estimates in bandit settings. The key open question, therefore, is the same one that arises for latent‑SEM causal‑bandit methods: How robust are these algorithms to violations in the underlying variable?\n\n**Q2. Dimension of the latent space.** The latent dimension is assumed to be known a priori, and there is a mechanical reason why: Our action space is *defined* by the latent space. That is, the number of controllable variables equals the number of latent dimensions. In fact, in CRL, the recovered variables are generally identified with their corresponding interventions. This enables the recovery of variables with known names/semantics but unknown values from high-dimensional observations. We note that for this reason, knowing the latent dimension – even if not strictly realistic – is a very common assumption in causal representation learning literature, including all references [2-13].\n\n**Q3. Single-node interventions aren’t actually affecting many latent variables?** Thank you for the thoughtful question. Indeed, transitioning to multinode intervention is a natural and realistic extension. We have adopted the single-node intervention model to facilitate clarity in exposition and describing the key ideas. Since this is the first paper addressing reward-oriented CRL, we deliberately chose single-node interventions to place the focus on the key ideas. At the expense of more crowded notations, all the steps can be readily extended to multi-node interventions, and all the logics of all the key processes remain the same up to some minor adjustments. We note that even in the CRL literature (without the downstream tasks), single-node interventions have been the primary focus primarily for the same reasons of facilitating clarity in analysis. Nonetheless, relaxing this assumption using existing techniques is a promising direction for future work.\n\n**W1. Number of interventions.** We would like to clarify what appears to be a misunderstanding. CRL guarantees depend on two issues: (1) how many intervention environments per node are necessary/sufficient? (2) What is the recovery guarantee for a given number of samples in each intervention environment? The full identifiability results generally dispense with the second dimension, assuming an *infinite* number of samples per intervention environment is available, and focus on characterizing how many intervention environments per node are required to ensure identifiability. As the reviewer correctly points out, the state-of-the-art results establish that one or two intervention environments per node is sufficient for perfect identifiability, assuming that under each environment we get an infinite number of samples.\n\nIn our framework, we also assume that we have exactly one intervention per node. Our key questions are\n1. What happens if we back off from having an infinite number of samples and assume access to only a finite number of samples?\n2. If we have a limited number of samples, how can we collect them sequentially and adaptively to the data so that we can form the best decision with the fewest samples?\n\nThe sequential design of data collection is naturally posed as a bandit framework. We hope this clarifies the reviewer’s primary concern about the scope of the paper.\n\n**W2. Hard and soft interventions.** Thank you for the question. To address this concern, we note three points:\n\n1. Hard interventions are special cases of soft interventions. When lacking information about what type of intervention has been used, we go with the default choice of assuming a soft intervention as it will accommodate both.\n2. Stage 1a is common to both soft and hard interventions. This stage will be carried out regardless of whether we know we have soft or hard intervention. If we know we have soft or we do not know the type of intervention, the CRL part of the algorithm terminates after completing Stage 1a. \n3. Stage 1b is exclusive to only hard intervention and will be carried out on top of Stage 1b only when we know that we have hard interventions. In such a case, carrying out Stage 1b, will refine the results and guarantees we get from performing only Stage 1a.\n\nWe note that such a conditional post-processing depending on *a priori* knowledge of whether hard interventions are used is not uncommon in CRL literature [3, 5].\n\n**W3. Limited evaluation and real-world examples.** We have performed additional experiments to evaluate the performance of RO-CRL across variations in the latent dimension, observed dimension, and assumption violations. The results are given in the additional experiments with Tables R1-7 in Response to reviewer FrNT. These results corroborate our existing evaluations in showing the efficacy of our proposed algorithm.\n\nRegarding real-world applications, unfortunately, currently there are no available datasets that are amenable to applying our algorithm. We hope that with the fast growth of the CRL literature, there will be such datasets for real-world experiments. We provide two potential use cases which we will include in the revised paper.\n- **Robotics:** Consider a robot operating in an environment that is observed through high-dimensional sensory data such as images. Interventional CRL offers a way to recover interpretable, disentangled latent factors (e.g., joint angles, end-effector positions) that causally generate visual data. CRL is particularly suitable for robotics in vision-based contexts because *high-dimensional observations* (images) obscure the causal variables and *robots* have known or assumed causal structure (e.g., a joint​ causes an end-effector position​). In this context, an example downstream objective could be moving the robot arm to a specific configuration using only the utility values and learned latent factors as control input. However, image generation is a highly nonlinear process, which does not fit our modeling assumptions.\n- **Genomics:** In gene regulatory networks, we observe high-dimensional expression data, typically measured from bulk or single-cell RNA sequencing. These observations are assumed to arise from a set of lower-dimensional latent variables, which represent unobserved biological drivers such as transcription factor activities, regulatory protein states, or signaling pathway activations. CRL is a natural fit for gene regulatory analysis because gene expression is influenced by a structured, latent causal process involving transcriptional and post-transcriptional regulation. Node-level interventions in the CRL framework correspond to perturbing individual latent regulatory variables. In gene networks, such interventions are biologically realizable via *gene knockouts* or **CRISPR interference* to silence specific genes or transcription factors and *overexpression systems* to activate regulators, to name a few. In this context, an example downstream objective could be to optimize a certain type of biological response over the set of some possible genetic modifications. However, we are not aware of current genomics datasets that support arbitrary multi-node interventions, which limits a direct evaluation at this time."}, {"review_id": "ciGknCZXmD", "reviewer": "Reviewer_FrNT", "summary": "This paper tackles the problem of learning causal representations (causal graphs and structural equations) in a setting where the goal is not to learn a representation that inverts the data generating process, but that can accurately model which interventions maximize a reward. The analysis is restricted to the setting where both the causal and reward models are linear. An algorithm for inference of the latent parameters in the limited time horizon is derived, as well as associated regret bounds. Some preliminary experimental results are obtained to validate the method.", "questions": "- In line 31, a large number of papers from the same authors are cited. Please be careful about self-citation and try including citations from a more diverse set of authors\n- As a suggestion for readability, I strongly suggest not using bold typeface to put emphasis, it is distracting for the reader. I suggest using italics if necessary", "limitations": "- Limitations should be discussed in the main text and not in the appendix", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- This paper formulates a novel and interesting problem of learning causal representations with the goal of maximizing a reward instead of inverting the data generating process. This could have important theoretical and practical applications\n- The theoretical analysis seems impressive and generalizes some existing results. It importantly operates in the finite sample setting\n\n## Weaknesses\n- I would like to see some experimental validation of the regret bounds. Figure 4 does suggest sublinear regret, but it would be great to have a more detailed analysis\n- It would also be interesting to have experimental comparison with other appropriate bandit algorithms\n- The paper is clear, but a bit heavy to read. I suggest trying to include a figure that explains the main algorithm. This could greatly help understanding\n- There is also little discussion of practical examples of applications of this framework. I suggest trying to include some to ground the discussion and highlight possible uses.", "was_revised": true, "final_justification": "I acknowledge the authors rebuttal and am looking forward to see the paper with the promised changes. I am happy to recommend this paper for acceptance.", "rebuttal": "**Q1. Citations.** We appreciate this feedback. In the revision, we will expand the discussions and to include more general discussion about causal representation learning and its latest developments.\n\n**Q2. Bold typeface.** Thank you for noting this. We will revise this accordingly.\n\n**W1. Experimental validation of the regret bounds.** Thank you for the suggestion. We incorporate new empirical results to validate the regret bounds. More specifically, we provide the following additional results:\n- Varying observation dimension $d$: Thanks to dimensionality reduction techniques and the forced-exploration schedule, CRL's regret remains essentially unchanged as we increase the feature dimension $d$ from 5 to 100 while keeping the latent dimension at $n=5$. This observation is consistent with some previous findings in CRL under linear transformations [5] that the performance of CRL is not that sensitive to the feature dimension $d$, and this behavior does not contradict our lower bound analysis, which is derived under the error bounds from CRL. Table R1 reports the corresponding runtime for different $d$at a fixed time horizon $T$, and the additional computational cost introduced by higher $d$ remains well within practical limits.\n\nTable R1: Average runtime (in minutes) with varying $d$ when $n=5$\n|$d$|5|10|25|50|75|100|\n|-|-|-|-|-|-|-|\n|soft|48.55|47.19|53.85|48.01|48.11|48.55|\n|hard|63.12|65.83|67.66|67.24|67.54|68.32|\n\n- Varying latent dimension $n$ (which also affects the $u$t) for fixed $d=10$. From table 2, we observe that the cumulative regret grows by increasing $n$. We note the increase stems from two factors: (i) exploration cost for CRL varies with $n$, and (ii) the reward range becomes larger as $n$ increases These trends will be more clearly visualized in the figures to be included in the final version.\n\nTable R2: Cumulative regret with different latent dimensions $n$ when $d=10$ \n|$n$|3|5|7|9|\n|-|-|-|-|-|\n|soft|1524|4832|13298|37787|\n|hard|1789|5382|14677|37830|\n\n**W2. Comparison with other bandit algorithms.** We have included additional results to compare against two baselines: vanilla UCB and a modified version of RO-CRL, where CRL is performed for a fixed fraction of the sample budget, after which the bandit proceeds without accounting for latent recovery error. Table R3 reports the cumulative regret at the given final horizon $T$ for different algorithms. As shown, both baselines perform significantly worse than RO-CRL. The performance gap between RO-CRL and Modified RO-CRL will continue to increase with longer time horizons.\n\n**Table R3:** Cumulative regret across different algorithms\n|Algorithm|RO-CRL|UCB|modified RO-CRL|\n|-|-|-|-|\n|hard|5382|15690|10132|\n|soft|4832|16320|9726|\n\n**W3. Include a figure that explains the main algorithm.** We will provide a schematic description of the pipeline of the processes to highlight the main steps of the framework and algorithm. This will, specifically, constitute the following key pieces:\n- CRL subroutine that is called after each exploratory sample\n- The key processes involved in UCB-based selection of interventions\n- Annotation on the link between estimates and original parameters\n- Idea behind the under-sampling rule\n\n**W4. Practical examples of applications.** We provide two potential use case examples for the RO-CRL framework and will include them in the revised paper.\n- **Robotics:** Consider a robot operating in an environment that is observed through high-dimensional sensory data such as images. Interventional CRL offers a way to recover interpretable, disentangled latent factors (e.g., joint angles, end-effector positions) that causally generate visual data. CRL is particularly suitable for robotics in vision-based contexts because *high-dimensional observations* (images) obscure the causal variables and *robots* have known or assumed causal structure (e.g., a joint​ causes an end-effector position​). In robotics, interventions on the latent variables can be achieved physically or via simulation. Physical interventions include, for instance, directly changing a joint angle or velocity (e.g., move joint 3 by +5°) and moving the robot gripper to a fixed position while leaving other joints free. In this context, an example downstream objective could be moving the robot arm to a specific configuration using only the utility values and learned latent factors as control input.\n- **Genomics:** In gene regulatory networks, we observe high-dimensional expression data, typically measured from bulk or single-cell RNA sequencing. These observations are assumed to arise from a set of lower-dimensional latent variables, which represent unobserved biological drivers such as transcription factor activities, regulatory protein states, or signaling pathway activations. CRL is a natural fit for gene regulatory analysis because gene expression is influenced by a structured, latent causal process involving transcriptional and post-transcriptional regulation. Standard representation learning techniques fail to recover biologically meaningful variables, often mixing causal and non-causal factors. Node-level interventions in the CRL framework correspond to perturbing individual latent regulatory variables. In gene networks, such interventions are biologically realizable via *gene knockouts* or *CRISPR interference* to silence specific genes or transcription factors and *overexpression systems* to activate regulators, to name a few. In this context, an example downstream objective could be to optimize a certain type of biological response over the set of some possible genetic modifications.\n\n**Limitations.** We will move the limitations paragraph to the conclusion.\n\n-----\n\n**Additional Experiments.** Finally, we include additional experiments.\n\n- **Performance of CRL when varying $n$ and $d$.** In Table R4, we provide additional experiments to evaluate the performance of CRL across different $n$, $d$ and intervention types, plotted against sample size $s\\_t$. These results show that CRL performance of our RO-CRL algorithm is mostly consistent across variations in system parameters: Variable recovery errors decay with increasing number of samples $s\\_t$ consistently with the theoretical rate of $1/s\\_t$ (Theorem 2) across all settings. Observation dimension $d$ does not affect results thanks to a dimensionality reduction step. Finally, increasing $n$ from 5 to 8 does not lead to a significant drop in variable recovery performance. However, graph recovery performance significantly degrades for $n=8$ under soft interventions, which can be explained by noting that the “true” graph under soft is the transitive closure which includes high numbers of indirect edges. Such indirect effects are hard to track from the precision matrices, which makes the graph recovery for soft interventions more difficult.\n\n**Table R4:** CRL performance versus $n$, $d$ and intervention type.\n\n(a) Latent recovery (MSE):\n\n|$n$|$d$|Int. type|$s\\_t =$ 1000|2000|4000|8000|16000|\n|-|-|-|-|-|-|-|-|\n|5|5|Soft|0.067|0.052|0.034|0.026|0.018|\n|5|25|Soft|0.201|0.189|0.170|0.162|0.156|\n|8|8|Soft|0.136|0.092|0.069|0.047|0.035|\n|5|5|Hard|0.218|0.165|0.069|0.047|0.017|\n|5|25|Hard|0.378|0.320|0.232|0.186|0.147|\n|8|8|Hard|0.246|0.176|0.099|0.047|0.034|\n\n(b) Graph recovery rate:\n\n|$n$|$d$|Int. type|$s\\_t =$ 1000|2000|4000|8000|16000|\n|-|-|-|-|-|-|-|-|\n|5|5|Soft|0.00|0.22|0.80|0.94|1.00|\n|5|25|Soft|0.02|0.10|0.64|0.80|0.94|\n|8|8|Soft|0.00|0.04|0.00|0.00|0.00|\n|5|5|Hard|0.02|0.10|0.68|0.84|1.00|\n|5|25|Hard|0.00|0.08|0.50|0.82|0.98|\n|8|8|Hard|0.00|0.08|0.50|0.96|1.00|\n\n- **Assumption Violations.**\n  - **Assumption 1:** We run experiments where Assumption 1 is violated and provide the regret and variable recovery results in Tables R5–6. First, we note that graph recovery consistently fails (the graph recovery rate is exactly 0) in this setting, which is consistent with our answer to Q3 of reviewer Z2af. However, Table R5 shows that latent variable recovery still works: Indeed, its analysis is independent of Assumption 1. In Table R6, we evaluate cumulative regret versus time, and observe that the bandit algorithm does not achieve a sublinear regret after the forced exploration phase ($t \\geq 18000$ in this case), meaning that RO-CRL algorithm requires Assumption 1 to appropriately capture the true uncertainties and make good decisions.\n\n**Table R5:** Cumulative regret under Assumption 1 violation ($n=d=5$)\n\n|$t$|3000|6000|9000|12000|15000|18000|21000|24000|\n|-|-|-|-|-|-|-|-|-|\n|Regret|0|2000|4000|4000|6000|6000|11000|16000|\n\n**Table R6:** Latent variable recovery MSE under Assumption 1 violation ($n=d=5$)\n\n|$s\\_t$|1000|2000|4000|8000|16000|\n|-|-|-|-|-|-|\n|MSE|0.134|0.123|0.104|0.097|0.092|\n\n- **Boundedness violations:** We conduct experiments that deliberately violate two key assumptions: bounded noise and known parameter bounds. The specific violations are as follows:\n    - Noise violation: We replace the bounded noise with unbounded Gaussian noise.\n    - Parameter violation: Instead of proper rescaling the system, we multiply all parameters by a factor of 10 to simulate the violation. Note that such a scaling can be offset by properly scaling the latent variables (see e.g. response to J78L, Q3). Therefore, in these experiments, we explicitly set a fixed scale of the latent variables.\n\n    As shown in Table R7, both violations result in linearly growing regret after the forced exploration phase ($t \\geq 18000$ in this case). This result aligns with theoretical expectations: violating the noise boundedness or known-parameter assumptions leads to confidence radii that no longer appropriately capture the true uncertainty, thereby causing increasingly poor decisions.\n\n**Table R7:** Cumulative regret under bound violation ($n=d=5$)\n|$t$|6000|12000|15000|18000|19000|20000|21000|\n|-|-|-|-|-|-|-|-|\n|noise|1909|4272|5382|5382|7176|8970|10764|\n|parameters|421447|505197|516290|516290|685092|857133|1029174|"}, {"review_id": "jeApo7LQ00", "reviewer": "Reviewer_J78L", "summary": "This paper introduces a novel framework called Reward-oriented Causal Representation Learning (RO-CRL), which rethinks the goal of causal representation learning (CRL). Rather than aiming for perfect identification of latent variables and their causal relations, the authors propose to learn the minimal representation sufficient to optimize a downstream reward function. The paper formalizes this notion in the context of linear structural equation models (SEMs) and linear transformations from latent to observed space, with linear utility functions. A key contribution is a regret-minimizing algorithm that adaptively explores interventions to identify the optimal intervention with respect to the unknown reward. The algorithm is analyzed under both soft and hard interventions, achieving nearly tight regret bounds. The paper also presents finite-sample identifiability results and shows that the proposed framework generalizes and improves upon causal bandit methods.", "questions": "Have the authors considered how the RO-CRL framework could be extended to non-linear SEMs or transformations? Even a qualitative discussion on potential challenges or future directions would strengthen the broader relevance of the work.\n\nThe paper would benefit from a more visible main-text discussion of empirical results, perhaps with illustrative toy examples that demonstrate key phenomena (e.g., how coarse representations suffice for specific rewards). Are the empirical claims consistent across different intervention types and graph structures?\n\nThe algorithm relies on known bounds for parameter magnitudes and noise levels. How sensitive is RO-CRL to violations or inaccuracies in these bounds?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper demonstrates high quality in its theoretical development, offering a detailed analysis of the RO-CRL algorithm. The manuscript is overall well-written. However, the structure of the paper is somewhat unusual and a bit confusing. For instance, the notation is explained at the end of the introduction.  Regarding significance, the shift from complete identifiability to task-oriented sufficiency is relevant, addressing common limitations of traditional CRL approaches when deployed in real-world decision-making systems. The originality of the work lies in formalizing the objective of utility-maximizing representation learning within a causal inference framework and in developing a regret-minimizing algorithm that explicitly avoids unnecessary modeling detail.\n\nHowever, there are some limitations. The main restriction is the reliance on linearity assumptions across the SEM, transformation, and utility function, which may reduce applicability to real-world domains. While these assumptions simplify the analysis, a discussion on potential extensions to more general settings would be relevant. The empirical evaluation is limited and relegated to the appendix, which makes it harder to assess the practical effectiveness of the method. Overall, there is a gap between theory and empirical interpretation.", "was_revised": true, "final_justification": "As posted on the rebuttal, the reviewers have provided an exhaustive reply, addressing some of the doubts I initially had.", "rebuttal": "**Q1. Extension to nonlinear setting.** Thank you for the chance to discuss the potential to extend to nonlinear settings. While linear models represent an important class of causal models, transformations, and rewards, we do agree with the reviewer that generalization to nonlinear settings is also important. Our framework sets the foundations for RO-CRL and we outline how it can accommodate nonlinear SEM, nonlinear transformation, and nonlinear rewards. To provide a concrete methodology for extensions, we first note that our current analysis consists of two parts: (i) analyzing finite-sample guarantees of a CRL algorithm, and (ii) analyzing how the CRL guarantees translate to reward guarantees. We discuss how the same decomposition can address nonlinear models as well:\n- **Latent SEM:** It is possible to generalize the algorithms and performance guarantees to nonlinear SEMs. While the overall RO-CRL framework and pipeline remain intact, such a generalization has two distinct implications: one for the CRL guarantees and another for the CB guarantees. Setting aside the technical details, here is a high-level description of how this generalization works. On the CRL side, the CRL subroutine can be replaced with methods designed for general SEMs. For example, [11] provides an algorithm along with finite-sample guarantees applicable to general SEMs. As a result, the performance guarantees stated in Theorem 2 would need to be adjusted accordingly. On the bandit side, the UCB rule and reward estimators can similarly be replaced with their counterparts developed for nonlinear causal bandits (for instance, those based on Gaussian processes or neural networks [20, 23]). Such generalization, however, is highly non-trivial and even in the simpler contexts (e.g., standalone CRL and CB), the linear and nonlinear settings are investigated separately, each with its exclusive technical challenges. \n- **Transformation:** There are existing results for CRL under nonlinear transformations [9, 10, 13]. However, finite-sample analysis of CRL under general transformations is – to our knowledge – still an open problem. Nevertheless, we note that any future finite-sample result can be integrated into our RO-CRL framework to extend it to nonlinear transformations: Given that the estimator provides a graph and variables recovery error bound similar to Theorem 2, these estimates and error bounds can be used by the robust causal bandit algorithm. Similar to SEM generalization, as long as the setting does not violate the CB assumptions, the overall pipeline would work.\n- **Utility:** Our utility‑function assumption is a direct extension of the latent SEM assumption. Specifically, the framework can be modularly generalized to accommodate non‑linear utilities when adopting the robust non-linear estimates in bandit settings. The key open question, therefore, is the same one that arises for latent‑SEM causal‑bandit methods: How robust are these algorithms to violations in the underlying variable?\n\n**Q2. Main-text empirical discussions.** Thank you for the suggestion. Given that the final version allows for one extra page in the main body, we will dedicate that extra page to move the key empirical observations to the main body, we will provide more discussions on them, and will also add new empirical results. More specifically, we have additional experimental settings to evaluate the performance of RO-CRL across variations in the latent dimension, observed dimension, and intervention types in random graphs (We kindly refer the reviewer to **Additional experiments** response to reviewer FrNT). Note that the tables in this response will be replaced by figures in the revised paper (the responses don’t allow images).\n\n““**Section 6. Experiments**\n\nIn this section, besides discussing and previous evaluations, we also provide new ones to assess the regret and latent recovery performance of RO-CRL across different intervention types and graph sizes. In all settings, we repeat the experiments 50 times.\n\nFirst, we demonstrate that RO-CRL shows sublinear regret, as established in Theorem 3. In Figure 4, we compare the regret of RO-CRL under soft (left) and hard interventions (right) on the same graph with $n=5$. We can see under both settings, after the forced exploration period (shaded as yellow), the algorithm converges and shows sublinear regret, validating results in Theorem 3. Thanks to the dimension-reduction step and the forced-exploration schedule, CRL's regret remains essentially unchanged as we increase the feature dimension $d$ from 5 to 100. Table R1 reports the corresponding runtime for each setting at a fixed time horizon $T$, and the additional computational cost introduced by higher $d$ remains well within practical limits. Finally, in Table R2, we show cumulative regret across different latent dimensions $n$. We note that all settings show sublinear regrets in the plot. Furthermore,  In Table R3, we compare the RO-CRL with other bandit algorithms.\n\nNext, we validate the latent recovery performance of RO-CRL. Figure 1 shows the graph recovery rate versus the sample size $s\\_t$ for $n=5$. As expected, it is observed that the recovery improves with more samples $s\\_t$. Furthermore, hard interventions (which are stronger than soft) consistently yield higher recovery rates than soft interventions. Figure 3 shows the average estimation error on latent variables Z for varying $s\\_t$. We can see both terms decay, which conforms to the theoretical decay $1/s\\_t$ rate established in Theorem 2. We next show in Table R4 that these observations are consistent across variations in $n$, $d$, intervention type.””\n\nWe do agree that illustrative examples would help readers to interpret the results more easily, and will include a toy example over the 2-node chain graph where the UCB criterion converges despite the variable recovery not being perfect. This will demonstrate that perfect recovery is not strictly required for good downstream task performance. We cannot include images in the response due to conference rules, however, the example consists of a full specification of the true and estimated latent variables (the means, edge weights, utility weights), and shows the calculations for UCB of the suboptimal arms dominated by the optimal arm’s true mean.\n\n**Q3. Known bounds for parameter magnitudes and noise levels.** Thank you for the thoughtful question. We first address it from a theoretical perspective, and then provide additional experiments to assess the sensitivity to the assumed bounds. The boundedness of the weight matrices is not a critical issue. In the CRL setting, latent variables can be recovered only up to a scaling factor, and this level of recovery does not compromise recovery of X (or any downstream task that uses X). In fact, recovery up to scaling recovers X as well as perfectly estimating Z. This is not limited to linear transformation, but to get the intuition across, we discuss the reason in the context of linear transformations in which X=G⋅Z. Such a transformation is equivalent to another system with the model X=(aG)⋅(Z/a) for any nonzero scalar a. Therefore, if we recover Z/a instead of the ground-truth Z, we can compensate for the scaling by estimating the transformation as a instead of G. In this sense, recovery of the latent variables is exact up to scaling, that is, any element of the set {Z/a:a∈R} is equally valid. Consequently, imposing boundedness on Z does not compromise the results. This boundedness can, in fact, be equivalently modeled by requiring the weight matrices that govern the dependencies among the coordinates of Z to be bounded.\n\nWe perform additional experiments and provide regret and variable recovery results under violations of Assumption 1 and boundedness assumptions in Tables R5–7 in the response to reviewer FrNT.\n- **Assumption 1 violations:** We observe that graph recovery consistently fails (the graph recovery rate is exactly 0), which is consistent with our answer to Q3. However, Table R5 shows that latent variable recovery still works, which is consistent with the fact that its analysis is independent of Assumption 1. In Table R6, we evaluate cumulative regret versus time, and observe that the bandit algorithm does not achieve a sublinear regret after the forced exploration phase ($t \\geq 18000$ in this case), meaning that RO-CRL algorithm requires Assumption 1 to ensure such sublinear regret results.\n- **Boundedness violations:** Both violations in noise and parameter bounds will lead to linear regret after the forced exploration phase. This aligns with theoretical expectations: violating either of them leads to confidence radii that no longer appropriately capture the true uncertainty, thereby causing increasingly poor decisions."}, {"review_id": "KrIyUhFBYU", "reviewer": "Reviewer_w3y6", "summary": "The paper proposes a new reward-oriented causal representation learning framework where the goal is to learn a latent representation well enough for some downstream task. The framework is formally described for soft and hard interventions, with corresponding identifiability guarantees under a linear SEM. \n\nThe RO-CRL algorithm is then presented as a method for recovering latent variables and discovering the optimal interventions. The algorithm first tests each atomic intervention a few times to get initial estimates of the inverse of $\\mathbf{G}$ and $\\mathcal{G}$. Using the estimates and reward, the next intervention is selected according to a UCB-based rule. The authors then provide regret upper bounds for their algorithm and a general lower bound on CRL algorithms, showing that their method is close to optimal.", "questions": "- Given the above, what would be an example of a real world scenario where we can intervene on each of the nodes in the causal graph but we still need to learn the latent variables occurs?\n  - In the robot example given in the introduction, it feels like if we are able to intervene on each of the joint angles, then we'd have access to their values.\n- How does the recovery of latent factors compare with the normal CRL setting?\n- How computationally expensive is the algorithm?\n\nIt is clear that considerable theoretical work was done. If the motivation and the setup were made clearer, I would be willing to increase my score.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "With the caveat that it is possible I misunderstood some parts of the submission as it was quite technical:\n\n**Strengths**\n- The paper is well-structured, though could benefit from additional diagrams to better explain the algorithm/idea.\n- The idea is novel and interesting, potentially sparking a new direction for future CRL research.\n- The paper contains significant theoretical contributions consisting of both novel identifiability results and new bounds.\n- Even without the representation learning part, the work contains state-of-the-art regret bounds for the causal bandit setting.\n\n**Weaknesses**\n- The motivation behind the idea could be clearer. While the notion of concentrating on the downstream task instead of perfect identifiability makes sense, it is unclear in what scenarios you'd be able to intervene on every single node in the causal SEM but not have access to the latent variables. In a sense, being able to intervene in this manner implies knowledge of at least what the latent variables are.\n- The algorithm could use further experimental evidence.\n- The restriction to linear SEM, transformation models and utility functions is somewhat restrictive.\n\nThere is a large number of typos/grammatical mistakes (e.g. just from the first two pages):\n- \"to the extended needed\" -> \"to the extent needed\"\n- \"Aiming at establish the possibility/impossibility results\" -> \"Aimed at establishing possibility/impossibility results\"\n- \"enable more improved\" -> \"enable improved\"", "was_revised": true, "final_justification": "The paper contains significant theoretical work. From the rebuttal, my main issue regarding the viability of the setting has been addressed and I appreciate the additional explanations. The fixing of typos and additional discussion of relevant points will strengthen the submission: I have thus raised my score from 3->5.", "rebuttal": "**Q1. Setting and motivation.** The observation that having access to single-node interventions on latent variables means at least knowing the variable labels is astute. In fact, in CRL, the recovered variables are precisely identified with their corresponding interventions. This enables the recovery of variables with known names/semantics but unknown *values* from high-dimensional observations, which leads to the second part of the question: When do latent variables exist but not directly observable?\n\nThese concerns broadly apply to interventional CRL; we will clarify them and include a summary in the revised manuscript.\n\nInterventional CRL has become one of the key branches of CRL. Its literature initially focused on the fundamental identifiability guarantees under stylized models (e.g., single-node interventions), and has since grown in various dimensions (e.g., unknown multi-node interventions). Whether the latent variables can be intervened (either individually or as a group) depends on the application domain. Below, we briefly review two such domains in which interventions on latent variables are plausible.\n- **Robotics:** Consider a robot operating in an environment and observed through high-dimensional sensory data such as images. Interventional CRL enables recovery of interpretable latent factors (e.g., joint angles) that causally generate visual data. CRL is particularly suitable for robotics in vision-based contexts because *high-dimensional observations* (images) obscure the causal variables and *robots* have known or assumed causal structure (e.g., a joint​ causes an end-effector position​). In robotics, interventions on the latent variables can be achieved physically or via simulation. Physical interventions include, for instance, directly changing a joint angle or velocity (e.g., move joint 3 by +5°) and moving the robot gripper to a fixed position while leaving other joints free.\n- **Genomics:** In gene regulatory networks, we observe high-dimensional expression data, typically measured from bulk or single-cell RNA sequencing. These arise from lower-dimensional latent variables representing unobserved biological drivers such as transcription factor activities, regulatory protein states, or signaling pathway activations. CRL is a natural fit for gene regulatory analysis because gene expression is influenced by a structured, latent causal process involving transcriptional and post-transcriptional regulation. Standard representation learning techniques fail to recover biologically meaningful variables, often mixing causal and non-causal factors. Node-level interventions in the CRL framework correspond to perturbing individual latent regulatory variables. In gene networks, such interventions are biologically realizable via *gene knockouts* or *CRISPR interference* to silence specific genes or transcription factors and *overexpression systems* to activate regulators, to name a few.\n\n**Q2. Comparison with normal CRL.** CRL identifiability guarantees are generally presented for the asymptotic regime of having an infinite amount of data. In our RO-CRL framework, we have to move away from this stylized assumption and work with a finite number of samples. As a special case of our setting, if we set our horizon $T \\to \\infty$, the latent recovery of our RO-CRL recovers the state-of-the-art known identifiability results under both soft and hard interventions (e.g., see [5, Algorithm 1]). With finite samples, however, RO-CRL prioritizes maximizing the cumulative utility. While shrinking the confidence radii requires progressively tightening the latent factor recovery error bounds, it also requires adaptive selection to track the uncertainty in estimates. Therefore, the overall latent error bounds are looser than having used all samples in a normal CRL algorithm. Conversely, if we were to separate CRL and bandit steps, i.e., first do CRL for a fixed portion of the samples then apply bandit, the cumulative regret can grow linearly in $T$ due to constant recovery errors after CRL pure exploration.\n\n**Q3. Computational complexity.** Computational cost per step can be broken down into two parts:\n1. **CRL:** CRL routine depends on matrix inversions ($O(d^3)$), which can be expensive for large $d$. However, since the transformation is linear, we can detect the supporting subspace and project the samples to it, effectively reducing the observation dimension $d$ to $n$, and yielding an overall per-step complexity of $O(n^4)$.\n2. **UCB-based selection:** The computational bottleneck is the intervention‑selection step: the UCB is intractable on general causal graphs [25, §3.3]. In practice, we may adopt the following procedure.\n    - Non‑negative edge weights and noise (shifted system): Because all rewards are monotone in their parents’ variables, to calculate the UCB, we can maximize nodes sequentially in causal order and use the closed‑form in linear bandit. The resulting worst‑case complexity is $O(n\\*d\\_{\\hat G\\_t}^3)$, where $n$ is the number of latent dimensions and $d\\_{\\hat G\\_t}$ is the maximum in-degree in $\\hat G\\_t$.\n    - UCB upper bounds: [25] proposes techniques that efficiently compute an upper bound on the UCB, which we could incorporate into our approach. But the upper bound is loose and their robustness to imperfect latent recovery is unknown.\n\n**W1. Intervention on the latent space.** We appreciate the reviewer’s careful attention to the viability of interventions. As discussed in response to Q1, viability of interventions highly depends on the application and there are important ones that naturally fit the scope of interventional CRL and are subjects of ongoing studies via CRL.\n\n**W2. Further experimental evidence.** We provide additional experiments to evaluate the performance of our algorithm across different $n$ and $d$. See Tables R1–4 in our response to reviewer FrNT. Overall, we observe that the regret (Theorem 3) and latent recovery (Theorem 2) results are both validated across variations in problem parameters. We also perform experiments to see the robustness of our algorithm to the assumptions we adopt (Assumptions 1–3). See Tables R5–7 in our response to reviewer FrNT. We observe that violation of any of these assumptions results in linear regret, which aligns with theoretical expectations.\n\n**W3. Linear SEM, transformation, and rewards.** While linear models represent an important class of causal models, transformations, and rewards, we do agree with the reviewer that generalization to nonlinear settings is also important. We note that even in the simpler contexts (e.g., CRL or CB), the linear versus nonlinear models are investigated extensively. Here, we outline how each component can be individually generalized. To provide a concrete methodology for extensions, we first note that our current analysis consists of two parts: (i) analyzing finite-sample guarantees of a CRL algorithm, and (ii) analyzing how the CRL guarantees translate to reward guarantees. We discuss how the same decomposition can address nonlinear models as well:\n- **Latent SEM:** It is possible to generalize the algorithms and performance guarantees to nonlinear SEMs. While the overall RO-CRL framework and pipeline remain intact, such a generalization has two distinct implications: one for the CRL guarantees and another for the CB guarantees. Setting aside the technical details, here is a high-level description of how this generalization works. On the CRL side, the CRL subroutine can be replaced with methods designed for general SEMs that also provide finite-sample guarantees (e.g., [11]). As a result, the performance guarantees stated in Theorem 2 would need to be adjusted accordingly. On the bandit side, the UCB rule and reward estimators can similarly be replaced with their counterparts developed for nonlinear causal bandits (e.g., [20, 23]). Such generalization, however, is highly non-trivial and even in the simpler contexts (e.g., standalone CRL and CB), the linear and nonlinear settings are investigated separately, each with its exclusive technical challenges.\n- **Transformation:** There are existing results for CRL under nonlinear transformations [9, 10, 13]. However, finite-sample analysis of CRL under general transformations is – to our knowledge – still an open problem. Nevertheless, we note that any future finite-sample result can be integrated into our RO-CRL framework to extend it to nonlinear transformations: Given that the estimator provides a graph and variables recovery error bound similar to Theorem 2, these estimates and error bounds can be used by the robust causal bandit algorithm. Similar to SEM generalization, as long as the setting does not violate the CB assumptions, the overall pipeline would work.\n- **Utility:** Our utility‑function assumption is a direct extension of the latent SEM one. Specifically, the framework can be modularly generalized to accommodate non‑linear utilities when adopting the robust non-linear estimates in bandit settings. The key open question, therefore, is the same one that arises for latent‑SEM causal‑bandit methods: How robust are these algorithms to violations in the underlying variable?\n\nIn all three cases, the structure of the analysis – error control in CRL followed by robust bandit optimization – remains valid. The main requirement is that the substituted components provide compatible error guarantees.\n\n**Typos.** We thank the reviewer, we will do a thorough proofread to clean the paper.\n\n**Algorithm/idea exposition.** If the paper is accepted, we will use the extra page in camera‑ready to add a high-level description of the data pipeline to make the setting clearer and highlight the algorithm’s main steps and central idea. The diagram will include the following parts:\n- CRL subroutine that is called after each exploratory sample\n- The key idea of UCB-selection\n- Annotation on the link between estimates and original parameters\n- Idea behind under-sampling rule"}]

Author rebuttal:

Meta-review: Causal representation learning is the problem of inverting a generative model to recover latent representations from data along with their causal relationships. In recent years, this problem has seen numerous positive results, mainly focused on identifiability and robustness. This paper addresses an interesting twist on this problem: Instead of providing guarantees on the latent representations themselves, the authors consider proving regret bounds for specific tasks. The results are similar in spirit to bandit-style problems.

The main results are presented in the linear setting, and it is not clear how to extend beyond this case. Other limitations include requiring knowledge of the latent dimension and factors, as well as being able to intervene on every factor. The assumptions also seem to be sufficient to identify everything (as in classical CRL) anyway, so there may not be any advantages to this approach.

Nonetheless, reviewers appreciated the new perspective on CRL (several of whom are themselves experts in CRL), and supported accepting the paper.
Decision: Accept (poster)