Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning
Authors: Mirco Mutti
Riccardo De Santi
Marcello Restelli
Alexander Marx
Giorgia Ramponi
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement learning
Posterior sampling
Causality
Primary area: reinforcement learning

Abstract: Posterior sampling allows exploitation of prior knowledge on the environment's transition dynamics to improve the sample efficiency of reinforcement learning. The prior is typically specified as a class of parametric distributions, the design of which can be cumbersome in practice, often resulting in the choice of uninformative priors. In this work, we propose a novel posterior sampling approach in which the prior is given as a (partial) causal graph over the environment's variables. The latter is often more natural to design, such as listing known causal dependencies between biometric features in a medical treatment study. Specifically, we propose a hierarchical Bayesian procedure, called C-PSRL, simultaneously learning the full causal graph at the higher level and the parameters of the resulting factored dynamics at the lower level. We provide an analysis of the Bayesian regret of C-PSRL that explicitly connects the regret rate with the degree of prior knowledge. Our numerical evaluation conducted in illustrative domains confirms that C-PSRL strongly improves the efficiency of posterior sampling with an uninformative prior while performing close to posterior sampling with the full causal graph.

Published as a conference paper at ICLR 2024
EXPLOITING CAUSAL GRAPH PRIORS WITH POSTE- RIOR SAMPLING FOR REINFORCEMENT LEARNING
Mirco Mutti', ; Riiccaroo De Santi Marcello Restelli,, Alexander Marx? Giorgia Ramponi TTechnion, 2ETH Zurich, "ETH Al Center, 'Politecnico di Milano mirco. m@technion ac. il, rdesanti (0nthi ch, marcello resteeli@eol alexander www.aai..teeeeee...eee. ch, giorgia. ramponi aai ethz.ch chh
ABSTRACT
Posterior sampling allows exploitation of prior knowledge on the environment's transition dynamics to improve the sample efficiency of reinforcement learning. The prior is typically specified as a class of parametric distributions, the design of which can be cumbersome in practice, often resulting in the choice of uninforma- tive priors. In this work, we propose novel posterior sampling approach in which the prior is given as (partial) causal graph over the environment's variables. The latter is often more natural to design, such as listing known causal dependencies between biometric features in medical treatment study, Specifically, we propose a hierarchical Bayesian procedure, called C-PSRL, simultaneously learning the full causal graph at the higher level and the parameters of the resulting factored dynamics at the lower level. We provide an analysis of the Bayesian regret of C- PSRL that explicitly connects the regret rate with the degree of prior knowledge. Our numerical evaluation conducted illustrative domains confirms that C-PSRI. strongly improves the efficiency of posterior sampling with an uninformative prior while performing close to posterior sampling with the full causal graph.
INTRODUCTION
Posterior sampling (Thompson] 1933), a.k.a. Thompson sampling, is a powerful alternative to clas- sic optimistic methods for Reinforcement Learning (RL, [Sutton Barto 2018) as guarantees outstanding sample efficiency (Osband et al. 2013) through an explicit model of the epistemic un- certainty that allows exploiting prior knowledge over the environment dynamics. Specifically, Pos- terior Sampling for Reinforcement Learning (PSRI., Strens 2000, Osband et al. (013) implements a Bayesian procedure in which, at every episode k, (1) a model of the environment's dynamics sampled from parametric prior distribution Px. (2) an optimal policy Tu is computed (e.g., through value iteration (Bellman (957)) according to the sampled model, (3) a posterior update is performed on the prior parameters to incorporate in Pk+1 the evidence collected by running π& in the true en- vironment. Under the assumption that the true environment's 's dynamics are sampled with positive probability from the prior Po. the latter procedure is provably efficient it showcases Bayesian regret that scales with O(VK) being K the total number of episodes (Osband & Van Roy 2017).
Although posterior sampling has been also praised for its empirical prowess (Chapelle Li 2011
specifying the prior through class of parametric distributions, crucial requirement of PSRL, can be cumbersome in practice. Let us take a Dynamic Treatment Regime (DTR, Murphy 2003) as an illustrative application. Here, aim to overcome patient's disease by choosing, each stage, treatment based on the patient's evolving conditions and previously administered treatments. The goal is identify the best treatment for the specific patient quickly. Medicine provides plenty of prior knowledge to help solve the DTR problem. However, it is not easy to translate this knowledge into a parametric prior distribution that is general enough include the model of any patient while being sufficiently narrow to foster efficiency. Instead, it is remarkably easy to list some known causal relationships between patient's is state variables, such as heart rate and blood pressure, or diabetes and glucose level. Those causal edges might come from experts' knowledge (e.g., physicians) previ- ous clinical studies. A prior in the form of a causal graph is more natural to specify for practitioners,
Work done while the author was at Politecnico di Milano. Joint authos-uu

---

Published as a conference paper at ICLR 2024
who might be unaware of the intricacies of Bayesian statistics. Posterior sampling does not currently support the specification of the prior through a causal graph, which limits its applicability.
This paper proposes novel posterior sampling methodology that can exploit prior specified through a partial causal graph over the environment's 's variables. Notably, a complete causal graph allows for factorization of the environment's dynamics, which be then expressed tored Markov Decision Process (FMDP, Boutilier et al.] 2000). PSRL can be applied to FMDPs, as demonstrated by previous work (Osband & Van Roy 2014), where the authors assume know the complete causal graph. However, this assumption is often unreasonable in practical applications
Fac-
Instead, assume have partial knowledge of the causal graph, which leads considering set of plausible FMDPs. Taking inspiration from (Hong et al. 20200] 2022b a Kveton et al. (021). we design a hierarchical Bayesian procedure, called Causal PSRL (C-PSRL), extending PSRL to the setting where the true model lies within a set of FMDPs (induced by the causal graph prior). At each episode, C-PSRL first samples a factorization consistent with the causal graph prior. Then, it samples the model of the FMDP from a lower-level prior that is conditioned on the sampled factorization. After that, the algorithm proceeds similarly to PSRL on the sampled FMDP.
Having introduced C-PSRL, we study the Bayesian regret it induces on the footsteps of previous analyses for PSRL. in FMDPs (Osband & Van Roy] 2014) and hierarchical posterior sampling (Hong) et al.) (022b). Our analysis shows that C-PSRL takes the best of both worlds by avoiding direct dependence on the number of states in the regret (as in FMDPs) and without requiring a full causal graph prior (as in hierarchical posterior sampling). Moreover, pendency of the Bayesian regret on the number of causal edges known a priori and encoded in the (partial) causal graph prior. Finally, we empirically validate C-PSRL against two relevant baselines: PSRL with an uninformative prior, i.e., that does not model potential factorizations in the dynamics, and PSRL equipped with the full knowledge of the causal graph (an oracle prior). We carry out the comparison in simple yet illustrative domains, which show that exploiting a causal graph prior improves efficiency over uninformative priors while being only slightly inferior to the oracle prior.
analytically capture the de-
In summary, the main contributions of this paper include the following:
A novel problem formulation that links PSRL with a prior expressed as a partial causal graph to the problem of learning an FMDP with unknown factorization (Section 2):
A methodology (C-PSRL) that extends PSRL to exploit partial causal graph prior (Section 3
The analysis of the Bayesian regret of C-PSRL, which is Ö( K/29 where K is the total number of episodes and 17 is the degree of prior knowledge (Section
An ancillary result on causal discovery that shows how a (sparse) super-graph of the true causal graph can be extracted from a run of C-PSRL as a byproduct (Section 55);
An experimental evaluation of the performance of C-PSRL against PSRL with uninformative or oracle priors in illustrative domains (Section 6)
Finally, the aim of this work is to enable the use of posterior sampling for RL. in relevant applications through a causal perspective on prior specification. We believe this contribution can help to close the gap between PSRL research and actual adoption of PSRL methods in real-world problems.
PROBLEM FORMULATION
In this section, we first provide preliminary background on graphical causal models (Section 2.1 and Markov decision processes (Section 2.2]. Then, we explain how a causal graph on the variables of a Markov decision process induces a factorization of its dynamics (Section 2.3 Finally, we formalize the reinforcement learning problem in the presence of causal graph prior (Section 2.4
Notation. With few exceptions, we will denote set or space as A, their elements as a E A. constants or random variables with A, and functions as f. We denote ((A) the probability simplex over A, and [A] the set of integers f1..... A.). For a d-dimensional vector z, we define the scope operator xZ] X kez Iy for any set I C [d]. When I = {i) is singleton, we use zz(i] as shortcut for x r[[[]]] A recap of the notation, which is admittedly involved, can be found in Appendix A
1 'DTR is an example, where several causal relations affecting patient's conditions remain mystery. We report regret rates with the common "Big-O" notation, in which Ô hides logarithmic factors. Note that the rate here simplified highlight the most relevant factors. A complete rate can be found in Theorem 4.1
2

---

Published as a conference paper at ICLR 2024
2.1 CAUSAL GRAPHS
Let X' = و and y - {Y; be sets of random variables taking values 2 Mi E [M]
respectively, and let p: X' + (J)) strictly positive probability density. Further, let g = (N,Y,
be bipartite Directed Acyclic Graph (DAG), or bigraph, having left variables X, right variables
D. and a set of edges C X' x y. We denote as 2; the parents of the variable Y E V. such as 2j = fi E [dx] (X,, X2) E 2} and
Ujejar1 UiEz, {(X,, Y,)). We say that g is Z-sparse maxje[dy] |2yl S 2 & dx, and we call Z the degree of sparseness of g.
The tuple (p, 9) called graphical causal model Pearl 2009) if fulfills the Markov factorization property with respect to G, that is p(Xx3) p(x')p((((e) p(X) | P)(v[o|<=(z)) and all interventional distributions are well defined Note that the causal model that we consider in this paper does not admit confounding. Further, we can exclude "vertical" edges in Y x y and directed edges y x X. Finally, we call causal graph the component G of a graphical causal model.
2.2 MARKOV DECISION PROCESSES
A finite episodic Markov Decision Process (MDP,Putermaall Puterman 2014) defined throug the tuple M == (S, A. J., H). where S is a state space of size S, A is an action space of size A, S x A A(S) is a Markovian transition model such that p( p(511,, a) denotes the conditional probability of the next state s' given the state and action a, S x A + A[0,, 11) is reward function such that the reward collected performing action in state s is distributed as r(s, a) with mean R(s, a) = E|r(s, a)), μ ((S) is the initial state distribution, H < oo is the episode horizon.
An agent interacts with the MDP as follows. First, the initial state is drawn 81 ~ μ. For each step h < H. the agent selects action a₁ A. Then, they collect reward rh ~ r(sh, an) while the state transitions to S1+11 ~ p(-|sh, an). The episode ends when S is reached.
The strategy from which the agent selects action each step is defined through non-stationary, stochastic policy π = {TT, (Ne E II, where each TT, : S - A (AA) is a function such that n (a|s) denotes the conditional probability of selecting action in state at step h, and IT is the policy space. A policy æ E IT can be evaluated through its value function V : : + [0, H]. which the expected sum of rewards collected under æ starting from state at step h. i.c.
(s) = E Σ
R(sH, aw) R(sk,aw)
sh -
Vs h E [M].
We further define the value function of π in the MDP M under μ as VM((T) = Eenu (s).
2.3 CAUSAL STRUCTURE INDUCES FACTORIZATION
In the previous section, we formulated the MDP in a tabular representation, where each state (action) is identified by unique symbol s E S (a E A). However, in relevant real-world applications, the states and actions may be represented through finite number of features, say ds and d features respectively. The DTR problem is an example, where state features can be, e.g.. blood pressure and glucose level, action features can be indicators whether a particular medication is administered.
Let those state and action features be modeled by random variables in the interaction between an agent and the MDP, graph of its variables, such that the value of a variable only depends on the values of its causal parents. Looking back DTR, we might know that the value of the blood pressure step h only depends on its value at step h and whether a particular medication has been administered.
consider additional structure in the process by considering the causal
Formally, we can show that combining an MDP M (S, A. P. T, n, H! with causal graph over its variables, which we denote as GM = (x) gives a factored MDP (Boutilier et al. 2000)
F (18))H (D), Py, Po μ. H, Z,N),
Both assumptions come naturally with factored MDPs (see Section 2.3 Informally, an intervention on
node Y; E y (or in X') assigns y(7] to constant e, i.c., ( c) T. All mechanisms Pt. where i is not intervened on, remain invariant. For more details the causal notation refer (Pearl 2009 Chapter 1).
3

---

Published as a conference paper at ICLR 2024
Z
0
20, {0,2) dy 20, {1
dx
2
2 set of consistent factorizations
causal graph prior Go true graph 9r.
3
Figure I: (Left) Illustrative causal graph prior Go with dx = 4, = 2 features, degree of sparse- ness Z The hidden true graph Gr. includes all the edges in Gu plus the red-dashed edge (3, 1). (Right) Visualization of Z, the set of factorizations consistent with Go. which is the support of the hyper-prior Po- The factorization 2, of the true FMDP F. is highlighted in red.
Xax is factored state-action space with dx = ds + da discrete variables, y/ - S = = x... Vay is a factored state space with dy = dy variables, and 2j are the causal parents of each state variable, which are obtained from the edges 2 of GM- Then, is a factored transition model specified as p(yl2)) II Py (wbil x(2;]), Vy E V X, and is factored reward function r(x) r=(r)(]))))) with mean R(x) j== R(a[z,)), Vo X. Finally, μ E A()) and H the initial state distribution and episode horizon specified in M. Z is the degree of sparseness of GM. N is a constant such that all the variables are supported in [NV]
where X' 8 A= x
r(æ[2z]),
The interaction between an agent and the FMDP can be described exactly as we did in Section 2.2 for a tabular MDP, and the policies with their corresponding value functions are analogously de- fined. With the latter formalization of the FMDP induced by a causal graph, we now have all the components to introduce our learning problem in the next section.
2.4 REINFOR LEARNING WITH PARTIAL CAUSAL GRAPH PRIORS
In the previous section, we show how the prior knowledge of a causal graph over the MDP variables can be exploited to obtain an FMDP representation of the problem, which is well-known to allow for more efficient reinforcement learning thanks to the factorization of the transition model and reward function (Osband & Van Roy| 2014 Xu & Tewari [020 Tian et al. 2020 Chen al. 2020 Talebi ett al. 2021 Rosenberg & Mansour 2021). However, in several applications is unreasonable to as-
sume prior knowledge of the full causal graph, and causal identification is costly in general (Gillispie)
& Perlman 2001: Shah & Peters) 2020). Nonetheless, some prior knowledge of the causal graph, i.c., a portion of the edges, may be easily available. For instance, DTR problem some edges of the causal graph on patient's 's variables are commonly known, whereas several others are elusive.
In this paper, we study the reinforcement learning problem when partial causal graph prior Go S 9M on the MDP M is available I We formulate the learning problem in Bayesian sense, in which the instance F. is sampled from prior distribution Pg. consistent with the causal graph prior Go In [ true instance F.. Analogously to previous works on Bayesian RL formulations, e.g., (Osband et al.) 2013). we evaluate the performance of a learning algorithm in terms of its induced Bayesian regret. Definition 1 (Bayesian Regret). Let 2 a learning algorithm and let Pg. a prior distribution on FMDPs consistent with the partial causal graph prior Go. The K -episodes Bayesian regret of a is
we illustrate both the causal graph prior Go and the (hidden) true graph GF. of the
K VV.(T)) - v.(TT)) -V.
BR(K) = ForPGo
(T) is the value of the policy n in F. under p. n. arg max+en V.(x) is the optimal policy in F., and Ty is the policy played by algorithm at step l E [K].
where VT(T))
The Bayesian regret allows to evaluate a learning algorithm on average over multiple instances. This is particularly suitable in some domains, such as DTR, in which is crucial to achieve good performance of the treatment policy on different patients. In the next section, we introduce an algorithm that achieves a Bayesian regret rate that is sublinear in the number of episodes K.
*For two bigraphs G. = (X,)),.) and G.
(X, 2.)). we let G. C G. if 2, C 2..
We will specify in the next Section how the prior Ps, can he constructed.
4

---

Published as a conference paper at ICLR 2024
3 CAUSAL PSRL
To face the learning problem described in the previous section, we cannot naively apply the PSRL algorithm for FMDPs (Osband & Van Roy 2014). since we cannot access the factorization z. of the true instance F.. but only causal graph prior Gn = (X, z0) such that 2p C Z.. Moreover, 24 is always latent in the interaction process, in which we can only observe sate-action-rewar realiza- tions from F., The latter can be consistent with several factorizations of the transition dynamics of F., which means we can neither extract 2, directly from data. This is the common setting of hier- archical Bayesian methods (Hong et al.] 2020, 2022a by sampled from a latent hypothesis space on top of the hicrarchy, which then conditions the sampling of the observed state down the hierarchy. In our setting, we can see the latent hypothesis space as the space of all the possible factorizations that are consistent with Go. whereas the observed states are the model parameters of the FMDP, from which we observe realizations. The algorithm that propose, Causal PSRL (C-PSRL), builds on this intuition to implement a principled hierarchical posterior sampling procedure to minimize the Bayesian regret exploiting the causal graph prior.
Kveton et al. (02T). where a latent state is
Algorithm Causal PSRL (C-PSRL)
1: input: causal graph prior Go S GF. degree of sparseness Z
2: Compute the set of consistent factorizations
Z = 21 x
Zdy
(2y)se(dr)
|æy| < Z and 20,5 S 2j Vj [dyl]
3: Build the hyper-prior Po and the prior Po((|z) for each x E 2
4: for episode k: 0, 1,..., K do
5: Sample
P& and p- Pe((1z) to build the FMDP Fu
6: Compute the policy T& +- arg max VF, (TT) collect an episode with Ty. in F,
7: Compute the posteriors Pa+1 and Pk+1 (-12) with the collected data
8: end for
First, C-PSRL computes the set Z. illustrated in Figure | (right), of the factorizations consistent with Go. i.e., which are both Z-sparse and include all of the edges in zo (line 2). Then, it specifies a parametric distribution Po. called hyper-prion over the latent hypothesis space Z, and, for each z E Z. further parametric distribution Po(-12), which is a prior on the model parameters, i.e., transition probabilities, conditioned on the latent state 2 (line 3). The former represents the agent's belief over the factorization of the true instance F., the latter on the factored transition model p. /
Having translated the causal graph prior Go into proper parametric prior distributions, C-PSRL ex- ecutes a hierarchical posterior sampling procedure (lines 4-8). For each episode k. the algorithm sample a factorization = from the current hyper-prior Px. and a transition model p from the prior Pa(-1z) such that p is factored according to (line 5). With these two, it builds the FMDP Fx (line 5), for which it computes the optimal policy Th solving the corresponding planning problem, which is deployed on the true instance F, for one episode (line 6). Finally, the evidence collected in F, serves to compute the closed-form posterior updates of the prior and prper-prior (line 7).
As shall see, Algorithm [ has compelling statistical properties, a regret sublinear in K (Section 4 with a notion of causal discovery (Section 3. and promising empirical performance (Section ().
Recipe. Three key ingredients concur to make the algorithm successful. First, C-PSRL links RL. of an FMDP F. with unknown factorization to a hierarchical Bayesian learning, in which the factorization acts observed state down the hierarchy. Secondly, C-PSRL exploits the causal graph prior Go to reduce the size of the latent hypothesis space Z, which is super-exponential in dx, dy in general (Robinson) 1973). Finally, C-PSRL harnesses the specific causal structure of the problem to get factorization (line 5) through independent sampling of the parents 2, E Z, for each Y,, which significantly reduces the number of hyper-prior parameters. Crucially, this can be done as we do not admit "vertical" edges in ) and edges from ) to X, such that parents' assignment cannot lead to a cycle.
latent state on top of the hierarchy, and the transition probabilities
the
Degree of sparseness. C-PSRI takes as input (line 1) the degree of sparseness Z of the true FMDP F., which might be unknown in practice. In that case, Z can be seen as an syper-parameter of the algorithm, which can be either implied through domain expertise or tuned independently.
A description of parametric distributions Po and Po(+22) and their posterior updates is in Appendix B
5

---

Published as a conference paper at ICLR 2024
Planning in FMDPs. C-PSRL requires exact planning in FMDP (line 6), which is intractable in general (Mundhenk et al. 2000; Lusena et al. (200T). While we do not address computational issues in this paper, note that efficient approximation schemes have been developed (Guestrin et al. 2003). Moreover, under linear realizabiliity assumptions for the transition model or value functions, exact planning methods exist (Yang & Wang 2019 [in al. 2020b Deng et al. 2022).
REGRET ANALYSIS OF C-PSRL
In this section, we study the Bayesian regret induced by C-PSRL with Z-sparse causal graph prior Go = (A',), ,,,))))))))))) 20). First, we define the degree of prior knowledge 1, S. minje[dy] |2,,5, which is a lower bound on the number of causal parents revealed by the prior Go for each state variable Y,. We then provide an upper bound on the Bayesian regret of C-PSRL, which we discuss in Section 4.1
Theorem 4.1. Let Go be causal graph prior with degree of sparseness Z and degree of prior knowledge 1, The K Keepisoees Bayesian regret incurred by C-PSRL is
BR(K)= = ( = ((1 dy + VH24X-1) VK).
While we defer the proof of the result to Appendix we report a sketch of its main steps below.
Step 1.
The first step of our proof bridges the previous analyses of a hierarchical version of PSRL, which reported in (Hong et al., (022b), with the one of PSRL for factored MDPs (Osband & Van Roy 2014). In short, we can decompose the Bayesian regret (see Definition]] [
K
BR(K)= = E
2.)] + Σ
EA Zx) V.([T)]
E
k
where Ex1-] is the conditional expectation given the evidence collected until episode k, and (T )) = (y--)((1==) [T)( ] is the value function of π on average over the posterior P=(=))). In- formally, the first term captures the regret due to the concentration of the posterior Pa(-]z.) around the true transition model p. having fixed the true factorization 2., Instead, the second term cap- tures the regret due to the concentration of the hyper-posterior Ps around the true factorization 2.. Through a non-trt non-trivial adaptation of the analysis in (Hong al. (022b) to the FMDP setting, we can bound each term separately to obtain (2 N + Z))).
The upper bound of the previous step is close to the final result up to factor / Z related the size of the latent hypothesis space. Since C-PSRL performs local sampling from the product space 2 = 2 x... x 2dy- by combining independent samples 2j E 2j for each variable Y, as we briefly explained in Section we can refine the dependence in | maxxe[dv] |2,1 |Z].
Step 2.
Step 3. Finally, to obtain the final rate reported in Theorem 4.1 we have to capture the dependency in the degree of prior knowledge v in the Bayesian regret by upper bounding maxye[dy] |2
max jE(dy]
|
Z-n
dx 11 (xx77
2dx-n
i
4.1 DISCUSSION OF THE BAYESIAN REGRET
The regret bound in Theorem 4. contains two terms, which informally capture the regret to learn the transition model having the true factorization (left), and to learn the true factorization (right).
The first term is typical in previous analyses of vanilla posterior sampling. Especially, the best known rate for the MDP setting is (SH)) (Osband & Van Roy 2017). In a FMDP setting with known factorization, the direct dependencies with the size S, A of the state and action spaces can be refined obtain ((Ha)" N//2 /K) (Osband & Van Roy 2014). Our rate includes additional factors of H and N, but a better dependency on the number of state Teatures dy.
The second term of the regret rate is instead unique hierarchical Bayesian settings, which include an additional source of randomization the sampling of the latent state from the hyper-prior. In Theorem 4.1 are able to express this term in the degree of prior knowledge 7, resulting in a rate

---

Published as a conference paper at ICLR 2024
Ö( O(VK/2"). The latter naturally demonstrates that richer causal graph prior Go will benefit the efficiency of PSRL, bringing the regret rate closer to the one for an FMDP with known factorization.
We believe that the rate in Theorem is shedding light how prior causal knowledge, here expressed through a partial causal graph, impacts on the efficiency of posterior sampling for RL.
5 C-PSRL EMBEDS A NOTION OF CAUSAL DISCOVERY
In this section, we provide an ancillary result that links Bayesian regret minimization with C-PSRL to notion of causal discovery, which call weak causal discovery. Especially, show that can extract a Z-sparse super-graph of the causal graph Gy. of the true instance F. as a byproduct.
K-1 of optimal policies for the FMDPss { K-1 drawn from the posteriors. Every FMDP FR is linked to corresponding graph (or factorization) 9r. = (X, ) =k), where 2 ~ Ps is sampled from the hyper-posterior. Note that the algorithm does not enforce any causal meaning the edges ny of GF., Nonetheless, we aim show that we can extract a Z-sparse super-ge super-graph of Gy. from the sequence {F*] with high probability.
A run of C-PSRL produces a sequence {
First, we need to assume that any misspecification in GF. negatively affects the value function of m&- Thus, we extend the traditional notion of causal minimality (Spirtes et al. (2000) to value functions.
Definition 2 (elua Minimality). An FMDP F fulfills e-value minimality, if for any FMDP F encoding a proper subgraph of Gy, i.e,, 95, C Cgr, holds that V2 > Vi, + e, where Vy, Vi, are the value functions of the optimal policies in F, F' respectively.
Then, as a corollary of Theorem 4.1 we can prove the following result.
Corollary 5.1 (Weak Causal Discovery). Let F. be an FMDP in which the transition model fulfills the causal minimality assumption with respect to Gy., and let F. fulfil c-value minimality. Then, GF. S. 9Fx holds with high probability, where GFx is a Z-sparse graph randomly selected within the sequence {G K-1 produced by C-PSRL over K- = Ö(H 2222xx2// episodes.
The latter result shows that C-PSRI. discovers the causal relationships between the FMDP variables, but cannot casily prune the non-causal edges, making 9Fx super-graph of GF.. In Appendix D we report detailed derivation the previous result. Interestingly, Corollary [..] suggests a direct link between regret minimization in FMDP with unknown factorization and (weak) notion of causal discovery, which might be further explored in future works.
6 EXPERIMENTS
In this section, we provide experiments to both support the design of C-PSRL (Section B and val- idate its regret rate (Section ( We consider two simple yet illustrative domains. The first, which we call Random FMDP, benchmarks the performance of C-PSRL on randomly generated FMDP instances, a setting akin to the Bayesian learning problem (see Section 2.4 that we considered in previous sections. The latter is traditional Taxi environment (Dietterich] 2000), which is naturally factored and hints at a potential application. In those domains, we compare C-PSRL against two natural baselines: PSRL for tabular MDPs (Strens,20000 and Factored PSRL (F-PSRL), which ex- tends PSRL to factored MDP settings (Osband & Van Roy 2014). Note that F-PSRL is equivalent to an instance of C-PSRL that receives the true causal graph prior as input, i.e., has an oracle prior.
FMDP (relevant parameters are reported in the caption of Figure [ is sampled uniformly from the prior specified through random causal graph, which is Z-sparse with at least two edges for every state variable (1) = 2). Then, the regret minimized by running PSRL., F-PSRL, and C-PSRL (17 2) for 500 episodes. Figure 2a shows that C-PSRL achieves regret that is significantly smaller than PSRL, thus outperforming the bascline with an uninformative prior, while being surprisingly close to F-PSRL, having the oracle prior. Indeed, C-PSRL resulted efficient in estimating the transition model of the sampled FMDP, as we can see from Figure which reports the l, distance between the true model p. and the Ps sampled by the algorithm at episode k.
Random FMDPs.
Taxi. For the Taxi domain, we use the common Gym implementation (Brockman et al. 2016). In this environment, taxi driver needs pick up a passenger at a specific location, and then it has to
7

---

Published as a conference paper at ICLR 2024
30
rogrer .10
modal error
regro -1.08
regret 110*
20
10
250
250
300
200
episodes
episodes
opisodes
opisodes
(a) Random FMDP
(b) Random FMDP
(c) Taxi 3 x 3
(d) Taxi 5 x
PSRL
F-PSRL
C-PSRL (n)
Figure 2: (a.b) Regret and model error as a function of the episodes in the Random FMDP domain with dx = 9, dy = 6, = 5,
2, H = 100. (c,d) Regret as a function of the episodes in Taxi with dx 5, dy = 4, = 5, N = [5, 2, 1,6, = 15. The plots report the mean and 95% c.i. over 20 runs.
3 xx3 3 with dx- = 5, dy = = 2, = 5, N = [3, 3, 2, 1, 6), H = 10, Taxi
bring the passenger to their destination. The environment represented as a grid, with some special cells identifying the passenger location and destination. As reported in [Simão & Spaan (2019), this domain inherently factored since the state space is represented by four independent features: The position of the taxi (row and column), the passenger's 's location and whether they are the taxi, and the destination. We perform the experiment on two grids with varying size (3 x 3 and 5 x 5 respectively), for which report the relevant parameters in Figure 2 Here we compare the proposed algorithm C-PSRL (1) = 2) with PSRL, while F-PSRL is omitted as the knowledge of the oracle prior is not available. Both algorithms converge to good policy eventually in the smaller grid (see the regret in Figure 2 Instead, when the size of the grid increases, PSRL is still suffering linear regret after 400 episodes, whereas C-PSRL succeeds in finding good policy efficiently (see Figure[d) Notably, this domain resembles the problem of learning optimal routing in taxi service, and our results show that exploiting common knowledge (such as that the location of the taxi and passenger's destination) in the form of causal graph prior can be a game changer.
RELATED WORK
We revise here the most relevant related work in posterior sampling, factored MDPs, and causal RL.
Posterior sampling. Thompson sampling [Thompson) 1933 is well-known Bayesian algorithm
that has been extensively analyzed in both multi-armed bandit problems (Kaufmann et al. 2012
Agrawal & Goyal 2012) and RL (Osband et al. 2013). Osband & Van Roy (2017) provides regret rate O(H / SAK) for vanilla Thompson sampling in RL, which is called the PSRL algorithm.
Recently, other works adapted Thompson sampling to hierarchical Bayesian problems (Hong et al.) 2020 2022a bl Kveton et al. 2021). Mixture Thompson sampling (Hong al., (022b), which is similar to PSRL but samples the unknown MDP from a mixture prior, is arguably the closest to our setting. In this paper, we take inspiration from their algorithm to design C-PSRL and derive its analysis, even though, instead of their tabular setting, we tackle fundamentally different problem on factored MDPs resulting from a casual graph prior, which induces unique challenges.
Factored MDPs Previous works considered RL in FMDPs (Boutilier et al. 2000) with either
known OOband & Van Roy| [2014] Xu & Tewari 2020 Talebi al., [202]] Tian al., 2020 Chen
et al. 2020) or unknown (Strehl et 2007: Vigorito & Barto 2009 Diuk et al. [2009] Chakraborty & Stone 201T Hallak et al.] 2015 2015]GGGo Guo Brunskill [017 Rosenberg & Mansour] (021) factoriza- tion. The PSRL algorithm has been adapted to both finite-horizon (Osband & Van Roy] 2014) and infinite-horizon (Xu & Tewari 2020) FMDPs. The former assumes knowledge of the factorization,
close to our setting with an oracle prior, and provides Bayesian regret of order Ó(H 2/2 /K) Previous works also studied RI. FMDPs in a frequentist sense, either with known (Chen et al.) 2020) or unknown (Rosenberg & Mansour 2021) factorization. Rosenberg & Mansour (2021) em- ploy an optimistic method that is orthogonal to ours, whereas they leave as an open problem captur- ing the effect of prior knowledge, for which provide answers in Bayesian setting.
Causal RL. Various works addressed RL with a causal perspective (see Kaddour et al. 2022
Chapter 7). Causal principles are typically exploited to obtain compact representations of states and transitions (Tomar et al. 2021 Gasse et al. (02T), or to pursue generalization across tasks and
environments (Zhang et al. 2020 Huang al. 2022 Feng al. 2022 Mutti et al. 2023). Closer to
8

---

Published as a conference paper at ICLR 2024
setting, [u et al. (2022) aim to exploit prior causal knowledge to learn in both MDPs and FMDPs. Our work differs from theirs in two key aspects: We show how to exploit a partial causal graph prior instead of assuming knowledge of the full causal graph, and we consider Bayesian formulation of the problem while they tackle a frequentist setting through optimism principles. [Zhang (2020b)
show interesting application of causal RL for designing treatments in DTR problem.
Causal bandits. Another research line connecting causal models and sequential decision makinng
is the one on causal bandity (Lattimore et al.. 2016 Sen et al.) 2017 Lee & |Bareinboim 2018
2019 Lu et al. 2020 102 Nair et al. [021] X Kiong & Chen 2022 Feng & Chen 2023), in which the actions the bandit problem correspond to interventions on varialess of causal graph. There, the causal model specifies a particular structure on the actions, modelling their dependence with
the rewarding variable, instead of the transition dynamies as our work. Moreover, they typically assume the causal model to be known, with the exception of (Lu et al.) [001)), and they study the simple regret in a frequentist sense rather than the Bayesian regret given a partial causal prior.
8 CONCLUSION
In this paper, we presented how to exploit prior knowledge expressed through a partial causal graph to improve the statistical efficiency of reinforcement learning. Before reporting some concluding remarks, it is worth commenting on where such causal graph prior might be originated from.
Exploiting experts' knowledge. One natural application of our methodology is to exploit domain- specific knowledge coming from experts. In several domains, e.g., medical or scientific applications, expert practitioners have some knowledge over the causal relationships between the domain's 's vari- ables. However, they might not have full picture of the causal structure, especially when they face complex systems such as the human body or biological processes. Our methodology allows those practitioners to easily encode their partial knowledge into a graph prior, instead of having to deal with technically involved Bayesian statistics to specify parametric prior distributions, and then let C-PSRL figure out a competent decision policy with the given information.
Exploiting causal discovery. Identifying the causal graph over domain's 's variables, which is usu- ally referred as causal discovery, is main focus of causality (Pearl 2009 Chapter 3). The literature provides plenty of methods to perform causal discovery from data (Peters et al. 2017 Chapter 4), including learning causal variables and their relationships in MDP settings (Zhang et al. 2020 Mutti]
et al. 2023). However, learning the full causal graph, even when it is represented with bigraph as
MDP settings (Mutti et al.) 2023). can be statistically costly or even prohibitive (Gillispie & Perl-
man 2001 Wadhwa & Dong, 202T). Moreover, not all the causal edges are guaranteed to transfer across environments (Mutti et al. 2023), which would force to perform causal discovery anew for any slight variation of the domain (e.g., changing the patient in DTR setting). Our methodology al- lows to focus on learning the universal causal relationships (Mutti et al. 2023). which transfer across environments, e.g., different patients, and then specify the prior through partial causal graph.
The latter paragraphs describe two scenarios in which our work enhance the applicability of PSRL, bridging the gap between how the prior might be specified in practical applications and what previ- ous methods currently require, i.e., a parametric prior distribution. To summarize our contributions, we first provided a Bayesian formulation of reinforcement learning with prior knowledge expressed through a partial causal graph. Then, we presented an algorithm, C-PSRL, tailored for the latter problem, and we analyzed its regret to obtain a rate that is sublinear in the number of episodes and shows a direct dependence with the degree of causal knowledge. Finally, we derived an ancillary result to show that C-PSRL embeds a notion of causal discovery, and we provided an empirical validation of the algorithm against relevant baselines. C-PSRI. resulted nearly competitive with F- PSRI., which enjoys richer prior, while clearly outperforming PSRL. with an uninformative prior.
Future works may derive tighter analysis of the Bayesian regret of C-PSRL, as well as stronger causal discovery result that allows to recover a minimal causal graph instead of a super-graph. An- other important aspect is to address computational issues inherent to planning in FMDPs to scale the implementation of C-PSRL to complex domains. Finally, interesting future directions include extending our framework to model-free PSRL (Dann et al.) 2021 Tiapkin et al. 2023), in which the prior may specify causal knowledge of the reward or the value function directly, and to study how prior misspecification (Simchowitz al. 202T) affects the regret rate.
9

---

Published as a conference paper at ICLR 2024
REFERENCES
Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, 2012.
Karl Johan Aström. Optimal control of Markov processes with incomplete state information. Jour- nal of Mathematical Analysis and Applications, 10(L):174-205, 1965.
Richard Bellman. Dynamic programming. Princeton University Press, 1957.
Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programming with factored representations. Artificial Intelligence, 121(1-2):49-11 107, 2000.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.01544 2016.
Doran Chakraborty and Peter Stone. Structure learning in ergodic factored mdps without knowledge of the transition function's 's in-degree. In International Conference on Machine Learning. 2011.
Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. In Advances in Neural Information Processing Systems, 2011.
Xiaoyu Chen, Jiachen Hu, Lihong Li, and Liwei Wang, Efficient reinforcement learning in factored mdps with application to constrained rl. In International Conference on Learning Representa- tions, 2020.
Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. In Advances in Neural Informa- fion Processing Systems, 2021.
Zihao Deng, Siddartha Devic, and Brendan Juba. Polynomial time reinforcement learning in fac- tored state mdps with linear value functions. In International Conference on Artificial Intelligence and Statistics, 2022.
Thomas G. Dietterich. Hierarchical reinforcement learning with the maxq value function decompo- sition. Journal of Artificial Intelligence Research, 13:227-303, 2000.
Carlos Diuk, Lihong Li, and Bethany R Leffler. The adaptive k-meteorologists problem and its application to structure learning and feature selection in reinforcement learning. In International Conference on Machine Learning. 2009.
Fan Feng, Biwei Huang, Kun Zhang, and Sara Magliacane. Factored adaptation for non-stationary reinforcement learning. Advances in Neural Information Processing Systems, 2022.
Shi Feng and Wei Chen. Combinatorial causal bandits. In AAAI Conference on Artificial Intelli- gence, 2023,
Maxime Gasse, Damien Grasset, Guillaume Gaudron, and Pierre-Yves Oudeyer. Causal reinforce- ment learning using observational and interventional data. arXiv preprint arXiv:2106.144. 14421, 2021.
Steven B Gillispie and Michael D Perlman. Enumerating Markov equivalence classes of acyelic digraph models. In Uncertainty in Artificial Intelligence, 2001.
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algo- rithms for factored mdps. Journal of Artificial Intelligence Research, 19:399 468, 2003.
Zhaohan Daniel Guo and Emma Brunskill. Sample efficient feature selection for factored mdps.
arXiv preprint arXiv: arXiv: 1703.03454, 2017.
Assaf Hallak, François Schnitzler, Timothy Mann, and Shie Mannor. Off-policy model-based learn- ing under unknown factored dynamics. In International Conference on Machine Learning, 2015.
Joey Hong, Branislav Kveton, Manzil Zaheer, Yinlam Chow, Amr Ahmed, and Craig Boutilier. Latent bandits revisited. In Advances in Neural Information Processing Systems, 2020.
10

---

Published as a conference paper at ICLR 2024
Joey Hong, Branislav Kveton, Manzil Zaheer, and Mohammad Ghavamzadeh. Hierarchical Bayesian bandits. In International Conference on Artificial Intelligence and Statistics, 2022a.
Joey Hong, Branislav Kveton, Manzil Zaheer, Mohammad Ghavamzadeh, and Craig Boutilier. Thompson sampling with mixture prior. In International Conference on Artificial Intelligence and Statistics, 2022b.
Biwei Huang, Fan Feng, Chaochao Lu, Sara Magliacane, and Kun Zhang. Adarl: What, where, and how to adapt in transfer reinforcement learning. In International Conference on Learning Representations, 2022.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably effi cient? In Advances Neural Information Processing Systems, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference Machine Learning, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, 2020b.
Jean Kaddour, Aengus Lynch, Qi Liu, Matt J Kusner, and Ricardo Silva. Causal machine learning: A survey and open problems. arXiv preprint 1rXiv:2206.15477 2022.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory, 2012.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. In Advances Neural Information Processing Systems, 2016
Branislav Kveton, Chih wei Hsu, Craig Boutilier, Csaba Szepesvari, Manzil Zaheer, Martin Mlade- nov, and Michael Konobeev. Meta- veta-Thompson sampling. In International Conference Machine Learning. 2021.
Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good interventions via causal inference. In Advances in Neural Information Processing Systems, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithmss. Cambridge University Press, 2020.
Sanghack Lee and Elias Bareinboim. Structural causal bandits: Where to intervene? In Advances
in Neural Information Processing Systems, 2018.
Sanghack Lee and Elias Bareinboim. Structural causal bandits with non-manipulable variables. In AAAI Conference on Artificial Intelligence, 2019.
Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit problems with causal background knowledge. In Uncertainty in Artificial Intelligence, 2020.
Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Causal bandits with unknown graph structure. In Advances in Neural Information Processing Systems, 2021.
Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Efficient reinforcement learning with prior causal knowledge. In Conference on Causal Learning and Reasoning, 2022.
Christopher Lusena, Judy Goldsmith, and Martin Mundhenk. Nonapproximability results for par- tially observable Markov decision processes. Journal of Artificial Intelligence Research, 14:83- 103. 2001.
Olivier Marchal and Julyan Arbel. On the uub-Gaussianity of the Beta and Dirichlet distributions. Electronic Communications in Probability, 22:1-14, 2017.
Alexander Marx, Arthur Gretton, and Joris M Mooij. A weaker faithfulness assumption based on triple interactions. Uncertainty in Artificial Intelligence, 2021.
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, and Eric Allender. Complexity of finite- horizon Markov decision process problems. Journal of the ACM (JACM), 17-4).681-720, 2000.
11

---

Published as a conference paper at ICLR 2024
Susan A Murphy. Optimal dynamic treatment regimes. Journal of the Royal Statistical Society:
Series (Statistical Methodology), 65(2):331-355, 2003.
Mirco Mutti, Riccardo De Santi, Emanuele Rossi, Juan Felipe Calderon, Michael Bronstein, and
Marcello Restelli. Provably efficient causal model based reinforcement learning for systematic generalization. In AAAI Conference Artificial Intelligence, 2023.
Vineet Nair, Vishakha Patil, and Gaurav Sinha. Budgeted and non-budgeted causal bandits. In International Conference Artificial Intelligence and Staristics, 2021.
Osband and Benjamin Van Roy. Near-optimal reinforcement learning factored mdps. In Advances in Neural Information Processing Systems, 2014.
Ian Osband and Benjamin Van Roy. Why posterior sampling better than optimism for reinforce- ment learning? In International Conference Machine Leurning, 2017.
lan Osband, Daniel Russo, and Benjamin Van Roy. (More) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, 2013.
Judea Pearl. Causality. Cambridge University Press, 2009.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: Foundations and learning algorithms. The MIT Press, 2017.
Martin L Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Robert W Robinson, Counting labeled acyclic digraphs. New Directions the Theory of Graphs, pp. 239-273, 1973.
Aviv Rosenberg and Yishay Mansour. Oracle-efficient regret minimization in factored mdps with unknown structure. In Advances in Neural Information Processing Systems, 2021.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-1243 2014.
Rajat Sen, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Identifying best interventions through online importance sampling. In International Conference Machine Learning, 2017.
Rajen D. Shah and Jonas Peters. The hardness of conditional independence testing and the gener- alised covariance measure. Annals of Statistics, 4813):514--1538, 2020.
Thiago D) Simão and Matthijs TJ Spaan. Safe policy improvement with baseline bootstrapping in factored environments. AAAI Conference on Artificial Intelligence, 2019.
Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu, Thodoris Lykouris, Miro Dudik, and Robert E Schapire. Bayesian decision-make making under misspecified priors with appli- cations to meta-learning In Advances in Neural Information Processing Systems, 2021.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. The MIT Press, 2000.
Alexander L Strehl, Carlos Diuk, and Michael L Littman. Efficient structure learning factored- state mdps. In AAAI Conference on Artificial Intelligence, 2007.
Malcolm Strens. A Bayesian framework for reinforcement learning. In International Conference on Machine Learning. 2000.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Mohammad Sadegh Talebi, Anders Jonsson, and Odalric Maillard. Improved exploration in factored average-reward mdps. In International Conference Artificial Intelligence and Statistics, 2021.
12

---

Published as a conference paper at ICLR 2024
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.
Yi Tian, Jian Qian, and Suvrit Sra. Towards minimax optimal reinforcement learning in factored Markov decision processes. In Advances in Neural Information Processing Systems, 2020.
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Nau- mov, Pierre Perrault, Michal Valko, and Pierre Menard. Model-free posterior sampling via learn- ing rate randomization. In Advances Neural Information Processing Systems, 2023.
Manan Tomar, Amy Zhang, Roberto Calandra, Matthew E Taylor, and Joelle Pineau. Model-invariant state abstractions for model-based reinforcement learning. arXiv preprint arXiv:2102.09850, 2021.
Christopher M Vigorito and Andrew G Barto. Incremental structure learning in factored mdps with continuous states and actions. University of Massachusetts Amherst- Depperrt-eerrtmmnttt of Computer Science, Technical Report, 2009.
Samir Wadhwa and Roy Dong- On the sample complexity of causal discovery and the value of domain expertise. arXiv preprint (rXiv:2/02.03274: 2021.
Nuoya Xiong and Wei Chen. Combinatorial pure exploration of causal bandits. In International Conference Learning Representations, 2022.
Ziping Xu and Ambuj Tewari. Reinforcement learning in factored mdps: Oracle-efficient algo- rithms and tighter regret bounds for the non-episodic setting. In Advances in Neural Information Processing Systems, 2020.
Lin Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, 2019.
Amy Zhang, Clare Lyle, Shagun Sodhani, Angelos Filos, Marta Kwiatkowska, Joelle Pineau, Yarin Gal, and Doina Precup. Invariant causal prediction for block mdps. In International Conference Machine Learning, 2020.
Jiji Zhang, A comparison of three Occam's razors for Markovian causal models. The British Journal for the Philosophy of Science, 2020a.
Jiji Zhang and Peter Spirtes. Detection of unfaithfulness and robust causal inference. Minds and Machines, 18(2):239-271, 2008
Junzhe Zhang. Designing optimal dynamic treatment regimes: A causal reinforcement learning approach. In International Conference Machine Learning, 2020b.
13

---

Published as a conference paper at ICLR 2024
APPENDIX
List of symbols
15
Parametric priors and posterior updates
17
Note computational complexity
18
Weak causal discovery
19
Regret analysis
Analysis for a general latent hypothesis space
21
Refinement Product latent hypothesis spaces
25
E.3
Refnnmmen 2: Degree of prior knowledge
27
High probability confidence widths
28
E.5
Auxiliary lemmas
29
Additional experiment with varying prior knowledge
32
Note on confounding
33
14

---

Published as a conference paper at ICLR 2024
A
LIST OF SYMBOLS
Basic mathematical objects
A
A Set or space
A
A Constant or random variable
A Element of a
((A)
A
Probability simplex over .A
I: A
B
A Function from A to B
[A]
A
Set of integers [A] = .,.
A
Scope operator [ = X ier for any set I S [d], E Rd
Causal graph
g
A
Directed acyclic bigraph 9 = (X. V).
X
A
Set of dx random variables {X, ddx taking values E [N]
y
Set of dy random variables { taking values Mj E [N]
A Directed edges X''' x
23
Parents of Y such that 2j {i (X,, (x E
Z
A Degree of sparseness such that 1zyl Z. [dy]
N
A Size of the support of random variables
MDP
M
A
Markov decision process M = (S, A, H,,,
S
A
State space
A
A
Action space
Transition model p: P A(S)
Reward function r : S x - A(O, 1J)
Initial state distribution μ A(S)
H
Episode horizon H < 0c
S
Size of the state space S = [S]
A
A Size of the action space A = A
A State E S
A Action a E A
R(s,a)
Mean reward B[r(s,a)
Factored MDP
F
A Factored Markov Decision Process F { (D/, 24 2j. Tj Ja M, 11, N,
dx
A Number of state-action variables
dy
A
Number of state variables
X
A
Factored state-action space X = X1 x... . Xax
y
A Factored state space y = }) x x... x Vdr
A Directed edges C X' x y, i.e., a factorization
A Parents of Y; such that zj (i (X,, Y,) = Factored transition model pvyl (z) = 1 P
Zj
A Factored reward function r(x) = Σ (x[=,]
A Initial state distribution μl E A())
H
A Episode horizon H < oc
Z
A Degree of sparseness such that |z,| < Z, V. E [dy]
N
A Size of the support of state and action variables
Learning problem
K
Number of episodes
k
A Episode index
Step index
15

---

Published as a conference paper at ICLR 2024
Z
-
Space of the consistent factorizations 2 C X x
Zj
Space of the consistent parents of Y, such that 2 = 21 ..yyy
Po
Hyper-prior the factorizations consistent with Go (supported in 2)
Phe
Posterior of the syper-prior Po at episode & E [K]
Po(122
Prior the FMDPs with factorization
Pa()12)
Posterior of the prior Po(-Iz) episode lo E [K]
Poo
Prior the FMDPs consistent with 9o such that
Ps. (F) = P
BR(K)
K -episodees Bayesian regret
Regret analysis
Ω
A Set of all the possible assignments of X (Xihellx)) S
8 iiEldxi
A Index on the support of random variables, n E [N]
H
A History of observations ((#,,,, Fr.l))ee(H until episode k
Z
A Random variable of the global factorization at episode k
A
Random variable of the local factorization at episode l for factor
Z
Random variable of the true factorization
Zzo
Random variable of the true factorization for j-th factor
E+
Conditional expectation given history Hk. E&l1 El. Hg]
Conditional probability given history He. [ TP[ HP]
16

---

Published as a conference paper at ICLR 2024
B PARAMETRIC PRIORS AND POSTERIOR UPDATES
In the following, we detail how the hyper-priors and priors of C-PSRL (Algorithm) T can be spec- ified through parametric distributions, and how the corresponding parameters are updated with the evidence provided by the collected data.
The hyper-prior Po = f= is defined through dy distributions over the set of local factor- izations 2....., 2dy resepetively, where each 2j contains the parents assignments for the variable Y, consistent with the graph prior Go. Let assume any arbitrary ordering of the local factorizations 2, Zy. such that each 2; is indexed by i E [|2 Then, we can specify the hyper-prior categorical distribution
Po)(2;:) -at(i;
W.
Σe wi
where the sum is over t E [|2,]], and the vector of parameters w is initialized as w = (1...., 1).
Then, for each local factorization 2; 2, of the variable Y,, specify the prior Po.5(112) over the model parameters of the corresponding transition factor py. The transition factor pj is (Ni2z,, (111s,,11 N) stochastic matrix. The prior is specified through a Dirichlet distribution for each row of Pj. i.c.,
Po. z;; a:) Dir(O), .Ni....,,0:n ON: AN)) (
Il 0an-1
where a is vector of parameters initialized as
(I,..., and B(a)
II F(ax///T an) is normalizing factor.
Having specified the hyper-prior and prior, now show how to update them with the new evidence. Let be .,...., ON ~ Px.s(-la(z,)) a)), and assume to collect the transition (x|zg),vıll = i) from the true FMDP F.. Then, the posterior is
PR- (01., . ON) P(uli) = 0 ....... (0),,.( aN: Og 0
n=1
which is still a Dirichlet distribution with parameters Dir(O),.... ONi ai:a...... ar + 1, ..... aN).
Then, we can propagate the posterior up the hierarchy to update the byper-prion as
(2+ x Plyli = (z))( x (ho(3i
P = = 01 (1l....,0N)).. PN) ON = (x))d..,)))(())........ .N) (1)
x Pho()i)) /
B(a) II 80n d(O)....,0N)
a (h.s(z;w) B(a 04 +,..., an)
B(ax)
x Pho((; Oi +1
Σ, 04 +1
where ( obtained by plugging the parametric prior in TT. we derive B by computing the integral
over the simplex of (0)..... 0x), and ④ follows from I l( 1) (a.) = (a; + II r(ax)
and I'(a, + Eizi a.) r'Σe ac) E, 1). The resulting posterior is still categorical
distribution with the parameters Wi f- W/ Σ. artl
artl
17

---

Published as a conference paper at ICLR 2024
C NOTE ON COMPUTATIONAL COMPLEXITY
As we mentioned Section 3 (paragraph on "Planning FMDPs"), the C-PSRL algorithm is not fully tractable as it requires solve exact planning in FMDP (line 6). As pointed out in the paper, the computational issue may be overcome through clever approximation schemes (Guestrin al., 2003) or exploiting the structure of the specific FMDP instance. E.g. under linear realiz- ability of the transition model or the value function, which means the transition and value function can be expressed as linear combinations of vector of features, tractable exact planning methods have been developed (Yang & Wang. 2019 Jin et al. 2020b; Deng et al. 2022). Furthermore, this computational issue is not specific the C-PSRI. algorithm but affects PSRL in FMDPs in general.
Nonetheless, C-PSRL actually induces an additional computational cost over the standard F-PSRL. algorithm. This is the burn-in cost of computing the set of consistent factorizations in line 2 of Algorithm T Notably, our method allows to build the set of consistent parents for each variable Y; independently (see Section "Recipe"), "), which means the process can be parallelized on dy workers. For each worker, we need to build set of Z-7 (dx--) elements, which we can do recursively by calling the base function at most O(24x -) times. The latter result gracefully characterize how the degree of prior knowledge y/ impacts the statistical (see Theorem and computational complexity in similar way.
While we underline again that this is not the computational bottleneck of C-PSRL, understanding how to avoid the computational burn-in (e.g., not pre-computing the whole set of factorizations but building it incrementally) is a nice direction for future works.
18

---

Published as a conference paper at ICLR 2024
D WEAK CAUSAL DISCOVERY
In the following, we show that we can extract, under a relatively mild causal minimality assumption, Z-sparse super-DAG of the true causal graph Gr. as byproduct of of Algorithm [ We call this result weak causal discovery, to make a clear distinction between discovering a sparse super-DAG of a causal graph and true causal discovery, in which the minimal graph is discovered.
As required for any causal discovery algorithm, we need to state an assumption that connects the causal graph 9r. with the distribution p. (i.e., the transition model) from which our observations are sampled in an i..dd manner (Spirtes et al. 2000). Typically, in causal discovery, it is assumed that p. fulfills the faithfulness assumption with regard GF. i.c. every independence in p. implies a d-separation (see Definition which can be violated by path cancellations or xor-type dependencies, and weaker assumptions have been proposed (Spirtes et al.) 2000 Pearl [209:] |Max et al. (02I). In this work, we build upon a strictly weaker assumption than faithfulness: causal minimality (Spirtes et al., 2000 ?
[ beeoow) in Gy_. Faithfulness, however, is a rather strong assumption
Definition 3 (Causal Minimality). A distribution P satisfies causal minimality with respect to DAG g if P fulfills the Markov factorization property with respect to G, but not with respect to any proper subgraph of G.
Intuition. More intuitively, a distribution is minimal with respect to G if and only if there is no node that is conditionally independent of any of its parents, given the remaining parents (Peters) iet al. 2017). There are two important points in this statement: i) none of the parents of a node is redundant, and ii) the dependence to a parent may only be detected given the remaining parents. Aspect ii) is a strictly weaker statement than required by faithfulness, which can be illustrated with a simple example. Consider the causal structure X + Y + Z, where all random variables are binary. If we generate X and Z via an unbiased coin and assign Y as Y ;= X xor Z, Y will be marginally independent of X, as well as marginally independent of Z. However, Y is not independent of X (resp. 2) when we condition on its second parent Z (resp. X). Such example violates faithfulness, i.c., there is a causal edge that is not matched by a dependence, but it does not violate causal minimality. For a more detailed discussion on such triples, refer to (Marx et al. 2021).
In our context, Algorithm has a positive probability of sampling all parents jointly (or a superset of them), and does not rely on checking pairs individually. Therefore, we can build upon the weaker assumption, causal minimality. Beyond identifiability in the limit, we are interested in the finite sample behaviour of approach. Therefore, we propose slightly stronger assumption for the value function, which is inspired by causal minimality.
Definition 2 (e- Value Minimality). An FMDP F fulfills e-value minimality, if for any FMDP F encoding a proper subgraph of GT, i.e., G C GF. it holds that V > V + E. where Vi, Vi, are the value functions of the optimal policies in F, F' respectively.
Intuitively, e-value minimality ensures that if we were to miss true parent, the resulting optimal value function would be at most e-optimal compared to the optimal value function evaluated on a graph that contains all true parents. Based on this rather lightweight assumption, we can extract from Algorithm T a graph G5x that is guaranteed to be either the true DAG Gy_, or a Z-sparse super-DAG of Gy. with high probability.
Corollary 5.1 (Weak Causal Discovery). Let F, be an FMDP in which the transition model fulfills the causal minimality assumption with respect to GF,, and let F, fulfill e-value minimality. Then, Gy. S &Grx holds with high probability, where GFx is a Z-sparse graph randomly selected within the sequence (Gr,) K-1 produced by C-PSRL. over K = Ö(H 2dx episodes.
Proof. From Theorem
we have that the K K-episodes Bayesian regret of Algorithm T is
E
Σ v.(m.)-V..l V.()..) S CiV 2d VK,
"The detinition refers SGS- minimmaill proposed by Spirtes et al. 2000 There exists an alternative defini- tion called P- minimality, proposed by | (2009). In our setting, both assumptions are equivalent, since they only differ on graphs that violate triangle faithfulness (Zhang) 2020a Zhang & Spirtes] (008). Since nodes within X' or within y are allowed to he adjacent, such triangle structures cannot occur within our assumptions.
19

---

Published as a conference paper at ICLR 2024
with high probability for some constant C1 that does not depend K. Through standard regret- to-pac argument (Jin et al. 2018). follows
E [V. (x.)) (.(TR) S C2v 2dx
(5)
vK
with high probability for some constant C2 that does not depend on K. and for policy Tk that is randomly selected within the sequence of policies {TR k=o By noting that тк can be c-optimal the true FMDP F. only Gy. S 95x through the c- value minimality assumption (Definition 2) we let E (T.. - V.(Tx)] c in (5), which gives K C2ll de 24x /e² and concludes the proof.
K-1 produced by Algorithm
d-Separation. For the reader's convenience, here report brief definition of d-separation. More details can be found in (Peters et al. (017).
Definition (d-Separation). path (X....,)) between two vertices X, Y in DAG is d- connecting given set Z, if
1. every collide the path is an ancestor of Z, and
2. every non-collider on the path is not in Z.
If there is no path d-connecting X and Y given Z, then X and are d-separated given Z. Sets X and Y are d-separated given Z. if for every pair X, Y, with X X and Y Y, X and Y are d-separated given Z.
"A collider C path (..., Q,C, W.... -) is node with arrowhead pointing towards i.c. C
20

---

Published as a conference paper at ICLR 2024
E REGRET ANALYSIS
In this section, we provide the full derivation of the following result. Theorem 4.1. Let Gg be causal graph prior with degree of sparseness Z and degree of prior knowledge 1, The K Keepisodes Bayesian regret incurred by C-PSRL is
BR(K) - (( (1222212212 + VH2dx-1)
K
On a high level, the proof is made up of two parts. The first part (presented in Section consists of decomposing the Bayesian regret into two components and then upper bounding the two expressions separately. This leads the intermediate regret bound for general latent hypothesis space, i.e., where the hypothesis space is not necessarily a product space, reported in Section E.I The second part of the proof refines the analysis by considering product latent hypothesis space (Section E.2) and the degree of prior knowledge (Section
E.3 ultimately reaching the theorem statement.
We define the set ! 2 [dxx [AV] of all the possible assignments of X {X, For the sake concision, we will denote pı [y]i] x xx[=]] as pe (x(=;)) where will not lead to ambiguity. Moreover, we denote [+1-] probability given the history of observations H4: = (( rn,s) (MM))))) collected until episode k. Auxiliary results and lemmas mentioned alongside the analysis are reported in the Sections E.4
E[- He] and Px1--]
Pf- Hul the conditional expectation and
and E.5
E. ANALYSIS FOR A GENERAL LATENT HYPOTHESIS SPACE
We first report decomposition of the Bayesian regret and then proceeds bound each component separately, which are then combined in single regret rate.
Bayesian regret decomposition. For episode k, we define VT 2) Ex>PP((l)) [+)(T]] as the expected value of policy according to the posterior conditioned on the latent factorization 2 ~ Ps and history Hg. As shown in (Russo & Van Roy 2014] Proposition 1) for the bandit setting and in (Hong et al. 2022b Section 5.1, Equation 6) for the reinforcement learning setting, we can decompose the Bayesian regret as
K BR(n) = Σ
K
E - VI Z,)] k
+ I
Σ E
Va(Tk; V. (TR)] K
-V)
(6)
by adding and subtracting VA(TT,, Z.) and noticing that π. Z, are identically distributed to T Za given Hy. Notice that Z, and Z. indicate random variables, while we will indicate with the low- ercase counterpart specific values of these random variables. The first term represents the regret incurred due to the concentration of the posteriors of the reward and transition models given the true factorization, while the second term captures the cost to identify the true latent factorization. We will bound each term of 66) separately.
Upper bounding the first term of (
For episode k; we define the event
E Y [dy]
n 12y] E Ω: (x(=,)) FA (=( s ca((lz)1)
and ||pF (x[2,])
- Da (a( s )
where the quantities are defined as follows. Fs denotes the FMDP sampled at episode hav-
ing mean reward R7 (Ir[z;)) and transition model pr, (z(z²]) for all æ|ž;] E Ω. The expression
(x((((z)) = Expp(( (x(())) denotes the posterior mean of Rs. (x(2,)). while (x({)), = m(=;))))e(N ne(N] with P& (yly)
x[2,]) = (F-P(()a)) [pr(y]i] n x[2;])] denotes the posterior mean transition probability vector of size for the j-th factor given a factorization With e (x(²²)) and Φ<x[2,]) we denote probabbiby confidence widths for the j-th factor of the mean reward and transition model respectively. A detailed derivation of such confidence widths
can be found in Section H.4 Informally, the event Fş expresses how close the mean rewards and
21

---

Published as a conference paper at ICLR 2024
transition models sampled at the episode i are to their posterior means. We refer with Eg to the complementary event of Eg.
Now, by reminding that и., Z. identically distributed to Ta. Z given Hy. rewrite each element of the sum within the first term (6) as
E
VAL (Tx) (T 2x)
E
E
(Tx) V=((Ta]
E
R (k,,, FA An, Zx)) + HIpFF (Sk, Ak, (K An, Zx)ll1
(3)
H
E
- FFx + (Xa, - -xxx
H
(Ra,(x - FF.. + (Xw.l - (x
$ E
(R
FA (2)1) IIP 1
E H
where we have used the definition of V (T Zx) in step ① Lemma E.3 in step step (3). and the defimition Eg in step 4).
2 Lemma E.4 in
By defining By (. (Z,)) := ck (Xx, (2)) du (Xe. (2,1) the sum of both confidence widths, we can bound the second term of (7) by using Lemma E.5 while we bound the first term of the same
equation by showing that Eş conditioned on He is unlikely. We rewrite the first term of (6) as
H
B k
(R
(X (2)
+ E
(Xr, (X,,
(X.. (2
(8)
where we have distributed the indicator function. For the first term within the sums of (8. we have
E RRr, (Xx,
Fi (Xx, (2)))
(9)
PPP ((Rr, (x( rr)rr
(10)
(XnA
PR (z)) (x(( 2 (x(
(11)
a[Z/JER
cx(2 cx(x(21))
exp
3/411a8(0222
(12)
=12,)E0
1og(2kdy
exp
(13)
=1Z,]en
Σ exp
( log N2))
(14)
2K
22

---

Published as a conference paper at ICLR 2024
In step 11) have used Lemmal E.2 and E.1 and in step (2) we have plugged-in the definition of
o (z(2,] from (plugged-in in o² of RA
where ag Rt (zx (z(zz]) represents the parameters of the posterior
over the mean reward for the j-th factor at episode & given factorization Z5. For the second term within the sums of (8), we have
B
115,, (Xa, (Z,)) Pa (X.M
N
max PF (Xn, NE
IA
p PPx(IP5 (X (2z), m) PA - dp
)x(x{(z5))
< 2Pp
VN
2x(T12,112
Σ mE
Σ
2exp
N
(15)
Kdy
The steps analogous the ones for upper bounding the first term of 88 Specifically, in step 1 we use a trivial upper bound on the /--norm and in step (2) we divide the confidence width by the
square root of the vector length /N according to lemma (Lattimore & Szepesvári 2020 Theorem
5.4.c). The parameters a (a| [Z)])) introduced in step (3) represent the parameters of the posterior
over the transition model for the j-th factor at episode given factorization Z).
By plugging 14 and
15 into (8) and then 8 into
bound the first term of (6)
K
E
(T....
Va(TT, 2,1]
< SHH2
H
E [Be( [2)1]]
(16)
where we recall that Bx (X = ca
Φ (Xx,a
Upper bounding the second term of (6). Since there is no fundamental distinction between latent states in the tabular and factored MDP settings, our analysis this section is aligned with (Hong et al. 2022b Appendix B.3, step 2) and aims at effectively translating it into the factored MDPs
notation.
In order to bound the second term of (6). we first need to define confidence sets over latent factoriza- tions. For each episode k, we define a set of factorizations C so that Z. E C2 with high probability. only exploit proxy statistic for how well the
Since the latent factorization is unobserved, model parameter posterior of each latent factorization predicts the rewards. We start defining a counting function (²)2)) = Ei=l 1[Z 2} as the number of times the factorization has been sampled until episode k. Next, we define the following statistic associated with a factorization and episode k.
k-1 Gx(2)= = 1(2 = 2) Vi(Tn,)) HV2 h=1j=1
dy ΣΣ ((X,,
dy Σ h=0
-
R [sl
1=1
The latter represents the total under-estimation of observed returns, as it expresses the difference between the lower confidence bound on the returns and the observed ones, assuming that is the true latent factorization. Now we can define Cs {2 E Gx(2) S (=N+(z) log K} as the set latent factorizations with at most / (HN+(==)oo log K excess. In the following, we show that Z, E C₁ holds with high probability for any episode.
Fix Z, = 2. Let Tx,2 = {I < k Z, = 2} the set of episodes where 2 has been sampled until episode kt We will first upper bound (z) by martingale with respect the history, then bound
23

---

Published as a conference paper at ICLR 2024
the martingale using Azuma- Hoeffdinnss inequality. We define the event
Ek { |Rn (X (2,1) - Fx. A [2j S (2a,((N. and || (X (3))
Ph. (X (2)Dı) S (X
in which the sampled reward and transition probabilities for factor j in step h of episode k are close to their posterior means. Let ع = U A=1 - - Ex.n.J be the event that this holds for every factor, step, and episode. By union bound we have that
())(E))))) & P&( (XA,, (A( (2)1) 2 V 2X
+PaaT (X (Zz))
PPAXKAAZZ)II 2 V2 X (x))(
())
22x (XaA
20 (xa
$ exp
+ exp
o²
No²
S (Kdy (Kdy)
where we have used Lemmas E.2 and
E. in step I
and &k,h.j is the complementary event of En.
Hence, for & = k=
U hhj.. we have
K
H
K ΣEΣΣ
H
P(E)- = ΣΣΣΣ Σ
PR((E)))))
Σ
N -
k-1h-12E2 f=1 =|Z,]En
For episode 1 E Tk... let A V.((..) E R.Alj. Since B 0. (Ai)tET, is martingale difference sequence with respect to the histories (HI) Following exactly the same steps as in (Hong et al. 2022b Proof of Lemma 7), we derive upper bound the probability of Z. not being in the factorizations set Ck. namely:
PZZ. Ct) S 2|ZZHK-
(17)
We can now decompose the second term of (6) according to whether the sampled latent factorization is in C& or not. Formally, we have
K
VA(TE, Zx) - Vi((T)) -v)))((TT)) 112x ( E cc.)
E
VR(TK Zx) - V+(TW)]
< E
H P(Z. $ Ck)
(18)
From the previous steps, using 17 we have that the second term of 118 is upper bounded by 2 Z H2, while in the following we derive an upper bound for the first term of (18) as (Hong al.
2022b Appendix B.3, step 4). We have
E
VA(TE, Zx) - Vo(Ta)) 112a E Cc}
K
HV2E
3x (x.,1117))))
h 1=1
H dy
Rembl) ) 112 C+}
+ E
V VA(TA, Zx)
2
Bel (X. (z,1)
k=
h=1 1=1
h= j=1
(
KK H dy
< 2V
Be (x(xanl2)))
+E
Σ Gx+1(z++1Z11
LEEZ
24

---

where Published as a conference paper at ICLR 2024
(3) S
dy ΣΣΣ
K
HV2E
Be (x
+ VIžKK log K 1
where in step
1 we use the definition of GK+1 (z) and in step 2 we upper bound the same quantity.
Bayesian regret for general latent hypothesis space. terms of (6). we get
Combining the upper bounds of the two
dy E (Z,x),l1//11 HV2E
BR(K) S NH H
Bu (xx
k
+ Z K log K + 12 + 2
(1)
KH 2N Ao,o
N + 3H dy N Nax + 3H N Ndx KH [o log (1
v k log K + H
where in step T we have used Lemma E.5 and we denote
A min min [1o6 (z|z))l,, min (ااري
jayay ||00 (=12)
Due to the Z-sparseness assumption, rewrite the Bayesian regret
BR(K) < 2H dyH + dy NY
N N²KH log
(1+
KHl
2N Ao,
+ V K H
- HHdd + Hidy N VK
VBIKH + +2
Notably, this rate is sublinear in the number of episodes K and latent factorization |Z], exponential in the degree of sparseness Z.
E.2 REFINEMENT 1: PRODUCT LATENT HYPOTHESIS SPACES
As we briefly explained in Section 3 C-PSRL samples the factorization from the product space Z = Zi X Zay by combining independent samples 2j E Zj for each variable Yj. This allows us refine the dependence in |2| C == maxje[dy] |2,| S |Z]. We replicate the same steps of the previous section in order to derive the Bayesian regret for the setting with product latent hypothesis space. For the sake of clarity, report here the main steps highlighting the difference with the previous section.
For an episode ls E [K], we define C -²= ( : S V (N)((,,) log K
k-1
11 Σ
((())=110 - 1=1
(Fi(XL((z))) Ra,bil)
h=1
(X P. (Xen V23.. (x))==)))(=)))
= 1Z) 2,). While (z(zz) captures the under-estimation the observed returns the level of single factor, (25))) counts the number of times that the local factorization zy has been sampled for node j until episode k. Next, we define Th (1 Z 23} } as the set of episodes where 2j has been sampled for node j.
and - =
First, we can derive an upper bound of (E) depending on by noticing that the inner-most sum depends only on the local factorization hence we can swap the preceding sums over 2 and dy
25

---

Published as a conference paper at ICLR 2024
shown in step ①I) of the following:
P(E) ΣΣΣΣ
Σ PA(EMA)))
K
dy
E NKdy)dxx=
k=1 j alz,JEn
(1) K
dy
ΣΣΣΣ E
j= 2yE2, ala,EER (Kdy-Ndx--
S HCK-1
Now, we wish upper bound P(Zz. & C For episode / Th.,, let A/ =E (X,,,
E R.,(j). Since FA[4]] = we have that (AI) a martingale difference sequence with respect to the histories (Hi)ETTi,n
By following the same steps as in Hong et al. 2022b), we get
H
G(())1(E}= = Σ H (
IET
h=1
+ (X,,ll)))))) - (X (x.N(())))
Σ
A
IET2.ay
and by fixing [T = (2²)) u < t, and using Azuma-Hoeffding's inequality, we derive
P& (E) HHulog SP
Σ
A z v Hu log K
S K-2
IET2..g
Therefore, by using union bounds, we can write
dy Σ
PZZ. & C+) -
P(Z & C
j=1
dy
Σ
P (+(()) 2 HHulog
1=1 Z,EZ,
dy S(( +
Σ
(G(()))18)) VHulog
F= E2 u=1
dy HCK-1
(19)
We decompose the second term of (6) according whether the sampled latent factorization in Ck or not, as in the previous section. Formally, we have
K
K
VA(TE, 2x) V.((T)) Vv.(x) 117x E cw)
(A 7x) [T()T)]
H P(Z. $ Ct)
From (19), we know that the second term is upper bounded by dy Cy Meanwhile, we can bound the first term as follows
K
E
VA Zx) VT(TT)) )11.))))226
112x e Ck)
A=l
26

---

Published as a conference paper at ICLR 2024
K
H
dy
S E
Fo(XaM125D) - (XAM)))))))
k=1
h= j=1
(( (X 1 E [
K
H
dy
K
H dy
HV2E
(xx,
+
Σ
(Fa(XRn
hm1
jml
+ +XI
(..XAlZZz.)D.. - (28u(XaM12)))11 c
1
K
< HV2E
+B Σ (zj)(zz) + drCH
2,E2)
(2)
K
dy
x HV2E
Be(Xan
+ Σ
Σ
V
dyCH CH
dy
J=
2,22
K
dy
S HV2E
Bx
+ CKH K + Cy
h=1=11
where in step
I
we use the definition of GK++ (2) and in step 2 we upper bound the same quantity.
Bayesian regret for a product latent hypothesis space. we can write
Exploiting the Z-sparseness assumption,
(R(K)= ò
= (H²d Hådy VCKH dH²
(20)
Notably, this rate is sublinear in the number of episodes K and the number of latent local factoriza- tions C, exponential in the degree of sparseness Z.
E.3 REFINEMENT 2: DEGREE OF PRIOR KNOWLEDGE
Finally, we aim to capture the dependency in the degree prior knowledge 7j in the Bayesian regret. To do that, we have express C max]e(dy] [z]| in terms of 17. We can write
2
2
dx
T
=
2=0
==0
where we count the empty factorization when i = O. Given a graph hyper-prior that fixes 1) < Z edges for each node ], we can count the number of admissible local factorizations
7 -j dx
1=0
where we count the factorization with only the edges fixed a priori when i = 0. We can build an upper bound on C as follows.
2-1 T=
Σ 1=1
dx 1)
i
(dx + +1 22 -22
< 2dxx 2dx-7-1 exp
4(1 7, dx)
b(dx 72,1) (dx -1)=-223 4(1 Z dx)
-dx exp
27

---

Published as a conference paper at ICLR 2024
Since it is hard interpret the rate of the latter upper bound, derive looser version that is easier to interpret. We have
2
C
Σ
dx
11
dx 2x-
dx
2
Σ
==
< 22x - 2dx - +1
2dx-
From the latter notice that each unit of the degree of prior knowledge make the hypothesis space shrink with an exponential rate, and thus the corresponding regret terms as well. In particular,
by plugging-in the upper bound C < 2dx-n 2xx in the Bayesian regret in 20 obtain the final upper bound, which
BR(K) = ò (12dr + dy N i + 22xx KK + dy 2 -11)
(21)
E.4 HIGH PROBABILITY CONFIDENCE WIDTHS
Here define high- probbbbbbbbyyty confidence widths the reward function and transition model along the lines of Hong et al. (2022b). but with the difference that the confidence widths are defined for all factors and their possible assignments rather than for state-action pairs in the tabular setting. We denote as C& (x]{,)) and Φ& (x(2;]) the confidence widths for the j-th factor of the reward function and the transition model respectively. In the following, indicate with R and pæ the mean reward and transition model of the FMDP F respectively.
Reward function. First, we write the posterior mean reward for the j-th factor, given a factor- ization z as (x(2))) (x-_a((s))((<((((]))) We wish have high probability bound of the type
I&& ([)((r()))) - Fa (x(=;)) 2 (x(+)))) S K
for all j [dy] and possible assignments æ|2;] Ω. By the union bound, we have
Px [
Fa(x[(z)) 2 (x((22)))
dy Px
{
[R((((z)) (x(x))))) cacol(e))
j=1 mlaslER
Ps (1R+(oks)) -x cu (x(())))
Applying a union bound again to the latter expression, we can derive the following one-sided bound:
Px R>(([2)]) Fn 2 (x(2(3))) < 2Kdy
According Lemma E.1 Rı = R - (x(z)) a oussuaaausna random variable
with 2 1/ (4 (I (zj) | + 1)). Therefore, through the Cramèr-Chernoff method exploited in
Lemma E.2 we have that the high probability bound above holds if
c* (x(2,))) 20
1
exp
2K Ndx
28

---

Published as a conference paper at ICLR 2024
which holds if and only if
cx(2(23)) 2 V 20 dy
log(2K 2K 2y Ndx)
(plugged-in o² of R&)
-V 2 2 (3l ((22))]] +1)
Hence, we pick (x(2)())) = V (11n(ta|=:)1++1) where is a lower bound on the value of dx, which holds due to the Z-sparseness assumption.
ly Nz)
Transition model. The derivation is analogous to the one for the reward function, hence here we report only the differences. First, we write the posterior mean transition probability for the j-th factor, given a factorization as (y]j] = n æ{2,]) EF-PL( [pr(y[]] n ==2z])], which is the probability, according the posterior at time kt over the element
[N]] of the domain of the
j-th component of Y. Since we want to bound the deviations over all components of a factor, we define the vector form of the previous expression as (t<()(2)) = (fx (y[s)
=(<;)))ne(M) By
following the same steps as for the confidence width of the reward function, we get
Ou (=[2)]) = V (1laf (2 (a(2,)]la +1)
(22)
where the VN term is due to Lattimore & Szepesvári 2020 Theorem 5.4.c), since the 1 norm sums over No -ubbaauassii random variables and therefore the induced random variable is (No*)- subgaussian.
E.5 AUXILIARY LEMMAS
Lemma E.1 (Theorem and of Marchal & Arbel (017))) Let Beta(a, B3 for a O. Then X- - [[[X] is -ubgaauussa with o² 1/(4(a + 1)). Similarly, let X ~ Dir(a) for a R. Then - [X[] o² -ssugaaussaan with 0² = 1/ (4 (I|a 1)).
Lemma E.2 (Theorem 5.3 of Lattimore & Szepesvári 2020 X is ob-suaauuss,an then for any 8
c²
P(X 2 e) S exp
2o
Lemma E.3 (Value Difference Lemma, Lemma and policy n,
Hong al. (0022)), ). For any MDPs M',
H
(Mr(m)-VMll)
E
Σ
RM (Sh, An) RM (Sh, A&) H 1p (Sa, An) PM (Sa, Ab)ll
Proof. This upper bound can be obtained by trivially upper bounding with the reward at each step. and therefore with h the value function within the statement in (Jin al. 2020a| Lemma C.I).
Lemma E.4 (Deviations of Factored Reward and Transitions Osband & Van Roy (0144). Given
two reward functions and R with scopes {2, 1=1
f we can upper bound the deviations by
dy
R(xx) - R(x)) < Σ (x(x))) - R2 (x(2,))
and, given two transition models p and with scopes E by
upper bound the deviations
dy
[p(x) - p(x) s
Σ
(x[2,))
29

---

Published as a conference paper at ICLR 2024
Lemma E.5. For episode ic and latent facton 2, let Bx(2zz)) [=(]=))](()])))])(] for
any j [dy] and z[zØ] & Ω2 Let Ao.: min { (minj,rfz] (x|z)1] m.n I| (a|z))ili)
indicates the minimum level of concentration between the reward function transition model priors for any factor and latent factorization Then, we have
K H dy (e(AAAle))) &
KH 2N Ao,
ΣΣ
Hdy Ndx +dy NH HdyNH V Ndx KH dy Náx Náx) log 1+
Proof. We define (x(2))) = Σ Σ 1[X1,12z)] = æ[zz]} as the number of times the as- signment x x|2y] was sampled up to episode for factor j. We can decompose the sum
K
H dy
Be(X
H1 dy ΣΣΣ k=1-=1j-1
K
K H dy ΣΣΣ k=1h-1jm
I[N (X
where we upper bound by 1 the regret in a step due to one factor. Therefore, the first term is upper bounded by d since there are most Náx assignments for each j E [dy] and the same one can appear in the sum at most H times, thus removing the dependency on K. Due to the assumption of 7-sparseness, we will later use the bound Hdy N2, As for the second term, we define Ne, (x(=,)) = [x(x(2))) + Ex=1 x[x) = x[2}]} as the number of times æ[z]] was sampled up to step h of episode k, for factor We split Bx into cj and øs. For Cj we have:
K
H dy (NNa(x > (X
ΣΣ>
K
H (NN((MM > HI 1=
2 (11 R (X,, [=)1) +1)
dy
log(2K (222KKy N2)
ΣΣΣ> Σ
H[Na(rl>))) > H 21 (zy D11 + (N +2
k= 1= #Ezyle
K 1
(ggd2Ky
ΣΣΣ
21 (X (2,1)] + (xleg)
k= 1= m(2,|e
dy v 1og(2Kdy
(w(s,)
Σ
Nx+1(+|2)])
Σ
a (XR,A [211i] + w
dy
KH/Ndx
1
KH lo N
2Ag +
u=1
KH
< <dr Ndx NdxKH KH log (2Kdy log
|+
2Ndx No.:
where in the first step we have plugged-in eg picked in Section 4, in the second step have ex- ploited the posterior update rule, in step three we have used that if N*(x(<z)) > H we have that H. 2.N (a: 22,]). and in the remaining passages we have used known bounds as in (Hong et al. 20226 Lemma 6). Analogously, for Φe we can derive the following.
Nk. (x(=,)) < [x
(Xa. > H)
KH 2Ndx No.z
< dy NH Ndx KH log (4Kdy
[1
30

---

Published as a conference paper at ICLR 2024
Notice that again, due to the Z-sparseness, replace in the steps above Náx with N Com- bining the terms, we have:
H dy
K ( & Hdy No +2dy NH, Ndx log (4K N log 1+ 2N Ao,
R= /=1j=1
31

---

Published as a conference paper at ICLR 2024
F ADDITIONAL EXPERIMENT WITH VARYING PRIOR KNOWLEDGE
In Section we reported results for C-PSRL with a fixed degree of prior knowledge = is interesting to see how changing the degree of prior knowledge affects the regret of C-PSRL. To this end, in Figure 3 we report an additional experiment in the same setting of Figures 2a 2b where we compare C-PSRL with
f1,2, 3, 4) against F-PSRL, which corresponds C-PSRL with 7j = 5, meaning the full graph is provided as an mput to the algorithm. Note that we omit PSRL from the plot here to get clearer view of the regret curves.
Perhaps surprisingly, varying the prior causal knowledge does not affect the regret of C-PSRL. in a significant way. This may look discordant with the result in Theorem [4.] However, we note that this domain is extremely small, so that the regret rate is actually dominated by the first term. Investigating the fine-grained impact of yj in the regret C-PSRL in larger domains (especially when dx > Z) would be nice corroboration of our theoretical analysis, which we leave future work.
rogret -102
2
episodes
F-PSRL
C-PSRL = 4)
C-PSRL bn
C-PSRL (n =
C-PSRL (n
Figure 3: Regret and model error function of the episodes in the Random FMDP domain with
dx = 9, dy = 6, = 5, N = 2, H = 100. The plots report the mean and 95% c.i. over 20 runs.
32

---

Published as a conference paper at ICLR 2024
G NOTE ON CONFOUNDING
In this paper, we assume there is no confounding acting on the variables of a causal graph g = 22) While this assumption brings the proposed problem formulation closer the literature on FMDPs (Osband & Van Roy) 2014 Xu & Tewari 2020 TTian et al. 2020 Chen et al. 2020) Talebi al. 2021: Rosenberg & Mansour 2021), we believe that extending our analysis to include confounding would further narrow the gap between our formulation and real-world applications, which may admit confounding. Here, report few notes on how confounding affects our results and the additional challenges it brings, while we leave future work formal study on confounding and how deal with
Let us waive the no confounding assumption and admit the presence of set of unobserved random de taking values cj [N]. In general, we can identify three types of confound- ing according to how the unobserved variables C interact with the observed variables X,
variables C = {C₂ ز=
(1) Confounding on X' i.e. there are causal edges of the form X, < Cj Xx for some j E [dc] and i, k E [dx]. This can be equivalently modeled through bi-directed edges in X' x X:
(2) Confounding between X' and V, i..., there are causal edges of the form X; t Cj + Y, for some i [dx]. j E [dc), and & [dy]- This can be equivalently modeled through bi-directed edges in X' x 3/;
(3) Confounding on y. i.c., there are causal edges of the form Y, f C2 - Yx for some j E [de] and k [dy]. This can be equivalently modeled through bi-directed edges in y )
The type (1) can be casily incorporated in our analysis, as the confounding does not affect transitions in any meaningful way. Specifically, our regret result (Theorem 4.1) would stand without changes, whereas the causal discovery result (Corollary [.I] would be slightly weakened. In particular, we could still identify the edges in x y since we observe all parents of each node in V, however, the edges in X' x X cannot be discovered by our procedure.
The type (2) is arguably the most challenging: The confounding directly impact the transition prob- abilities P(X.)) )) pO (D)((,C))p((" ())(C, where the conditioning C. is unobserved. Our feeling that this case brings the model close to Partially Observable MDP (POMDP, Aström 1965) formulation. Unfortunately, learning in POMDPs is known to be intractable general (e.g.. Krish- namurthy et al.) 2016), which means further structural assumptions shall be considered to deal with this type of confounding.
The type (3) also be problematic. With this type of confounding, do not observe all of the causal parents of the variables V, which may complicate modeling the transition probabilities in some (rare) cases.
33


Reviews:
[{"review_id": "HK7ZJazAND", "reviewer": "Reviewer_m9sB", "summary": "Posterior sampling guarantees sample efficiency by exploiting prior knowledge of the environment's dynamics. In practice, the class of parametric distributions can be cumbersome and uninformative. This paper proposes a hierarchical Bayesian procedure, C-PSRL, that uses the (partial) causal graph over the environment's variables as the prior. Its Bayesian regret is associated with the degree of prior knowledge. Empirical experiments show that C-PSRL improves the efficiency of posterior sampling with an uninformative prior.", "questions": "1. Line 92: I'm a little confused about why the DAG is divided into X and Y parts. If X is the state-action space and Y is the state space, where is the reward in the DAG? In common DAGs, each node represents a random variable, but here, each node seems more like a realization of the tuple (s, a) or just state 's', which makes me doubt the interpretability of the DAG.\n2. Figure 1 (right): The set Z includes 9 different DAGs. However, shouldn't the set of factorizations consistent with G_0 contain 2x2x3=12 possible FMDPs? Or did I miss some selection criteria for the set Z?\n3. Algorithm 1: From line 5 to line 6, could you provide more details on how to obtain F_* from F_k?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea of replacing an uninformative prior with a causal graph is attractive. Additionally, the byproduct of weak causal discovery reveals the possibility of how to utilize reinforcement learning in the causal discovery field.", "weaknesses": "My biggest concern is why not learn directly from the parents of the reward, given that we want to utilize causal prior knowledge? If I understand correctly, this paper focuses more on the parents of actions and states. As we all know, the value of a variable depends only on the values of its causal parents (line 122). If our goal is to learn the policy that maximizes the reward, shouldn't we primarily focus on the parents of the reward for greater efficiency and simplicity?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "D4DOvc3ge6", "reviewer": "Reviewer_fSwc", "summary": "The paper proposes a novel approach to posterior sampling for reinforcement learning (PSRL), namely C-PSRL, that exploits the partial causal graph (which is given as prior knowledge) as a prior. C-PSRL iteratively samples the causal graph which induces FMDP and updates the posterior. As a result, C-PSRL improves the Bayesian regret to $\\tilde{\\mathcal{O}}(\\sqrt{K/2^\\eta})$ where $\\eta$ represents a degree of prior knowledge. An interesting property of C-PSRL is a weak causal discovery, i.e., it discovers the sparse super-graph of the ground-truth causal graph as a byproduct. Experimental results demonstrate the effectiveness of the proposed algorithm.", "questions": "- How can the byproduct (i.e., super-graph of the ground-truth causal graph) be utilized? Also, if one is interested in recovering the ground-truth causal graph, do you think there is any way to further prune the super-graph to obtain the true graph?\n- It would be interesting to see the performance of C-PSRL given the low prior knowledge (e.g., $\\eta = 0, 1$). The experiment only shows the case of $\\eta=2$.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The manuscript is well-written. As one who is not an expert in PSRL literature, it was not too difficult to follow the paper.\n- The problem setting where only the partial causal graph is given is interesting. Also, the motivation is clear; in many practical scenarios complete true causal graph is often not accessible but only partial causal relationships are known.\n- The paper suggests a neat solution that extends PSRL and provides the Bayesian regret analysis, though I did not check the proofs. Empirical validation demonstrates its effectiveness compared to naive PSRL.", "weaknesses": "- It is unclear what is the implications of the weak causal discovery result. It states that the $Z$-sparse super-graph of the ground-truth causal graph can be recovered, but it does not speak for itself, and difficult to understand what is the takeaway message. For example, is it fundamentally impossible for the C-PSRL to recover the ground-truth causal graph? If this is the case, then is it still possible for the C-PSRL to obtain (converge to) optimal policy? Is the degree of the difference between the true causal graph and super-graph associated with the convergence rate or optimality?\n- The assumption that the (correct) partial causal graph is given as a priori is understandable. However, it is also important to discuss what would happen if this assumption does not hold. For example, how would C-PSRL behave if the initial partial causal graph is wrong (i.e., when some of its edges are non-causal)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tDYh3f7YVM", "reviewer": "Reviewer_mWkL", "summary": "This work proposes an extension of Osband & Van Roy (2014, NeurIPS) where only partial knowledge of the causal graph is needed as opposed to full knowledge. More specifically, the aim is to still provide competitive rates in terms of Bayesian regret with such partial knowledge. The authors also find that their method also performs a weak notion of causal discovery as a byproduct.", "questions": "- Could you compare with the regret bounds of Lattimore et al (2016) that also use knowledge of the causal structure to improve regret in the context of bandits instead of RL ? Are there connections?  See also the extension with unknown graph in Lu et al (2021)\n\n\n\n- Lattimore, F., Lattimore, T. & Reid, M. D. Causal bandits: learning good interventions via causal inference. In Adv. Neural Information Processing Systems Vol. 29 (2016) \n- Lu, Y., Meisami, A. and Tewari, A., 2021. Causal bandits with unknown graph structure. Advances in Neural Information Processing Systems, 34, pp.24817-24828.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- An extension of an interesting frameowork \n- clear statement about what are the new contributions", "weaknesses": "Some issues in clarity of presentation and about what are the interventions here ? The paper is not written in causality notation \n- Not clear how much computational complexity is added wrt to PSRL; eg what is the complexity of step 2 in Algo 1 ? \n- defintions in Sec 2.1 are currently wrong or incomplete: the Markov factorization is not what makes an CBN, since it applies to standard BNs. See definitions of CBN in eg [Pearl, 2009, Definition 1.3.1] , it's about *all* interventional distributions having the Markov fact. and other constraints. \n- I'm not understanding in Alg 1 about step 7, are these posteriors in closed form ? If not, what approximations are used and how do they affect the regret ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gVQ8H9Jak0", "reviewer": "Reviewer_i58j", "summary": "This work proposes a posterior sampling algorithm to address the reinforcement learning problem given a partial causal graph. The method utilizes the knowledge of a partial causal graph to construct a set of plausible factored MDPs (FMDPs). Then, it is framed as a hierarchical Bayesian model, with a prior over the factorization (equivalently, the complete causal graph) at a higher level and priors over the transitions and rewards at a lower level (given the factorization). The proposed posterior sampling C-PSRL algorithm proceeds by first sampling a factorization from the posterior, then sampling the MDP's parameters from the posterior given the factorization, and computing the optimal policy given the sampled FMDP. The paper proves that the Bayesian regret of the proposed C-PSRL algorithm is sublinear in the number of episodes and shows that C-PSRL can identify a super-graph of the true causal graph.", "questions": "Please address the above weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The motivation behind tackling the RL problem using a partial causal graph is compelling and essential for improving the practicality of posterior sampling algorithms in the RL context. The proposed algorithm is intuitive and incorporates Bayesian regret analysis. \n\nAlthough the theoretical analysis is based on the PSRL approach in FMDPs in Osband & Van Roy (2014) and the hierarchical posterior sampling method in Hong et al (2022b), the paper analyzes the connection between the degree of prior knowledge in the partial causal graph and the Bayesian regret, which is interesting. The paper also provides a result on the weak causal discovery.", "weaknesses": "1. The experiment section is quite brief. There may be some missing details.\n\n   a. In particular, the construction of priors is not discussed in detail. Although the priors are discussed in lines 173-178, it is not very clear to me about the distribution of the latent hypothesis space. For example, how do we select the support of this distribution (given the sparseness Z) and assign the prior probability of each factorization? What are the priors of the transition probabilities and rewards? How are the posterior distributions updated (do we need conjugate priors)?\n\n   b. Is the assumption in Lemma D.1 satisfied by the baseline with uninformative priors in the experiments?\n\n   c. Additionally, it might be beneficial to include an experiment involving F-PSRL with the causal graph set to the partial causal graph.\n\n2. Could the author provide justification for the assumption made in Definition 2 that any misspecification in $\\mathcal{G}_{\\mathcal{F}_k}$ negatively affects the value function of $\\pi_k$? \n\nA minor issue: in line 180, line 9 does not exist in Algorithm 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)