Paper deep dive

Information-Directed Sampling for Causal Bandits

Muhammad Qasim Elahi, Murat Kocaoglu, Mahsa Ghasemi

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 112

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%

Last extracted: 7/20/2026, 3:09:22 AM

Summary

This paper introduces a Bayesian framework for contextual causal bandits with non-manipulable variables. It proposes causal variants of Thompson Sampling and Information-Directed Sampling (IDS) that exploit shared causal mechanisms to update reward estimates across interventions. Theoretical contributions include entropy-dependent sublinear Bayesian regret bounds for Thompson Sampling and IDS, along with high-probability confidence bounds for Monte Carlo approximations. Experiments demonstrate superior performance over baselines by effectively sharing information across interventions.

Entities (12)

Johns Hopkins University · organization · 99%Mahsa Ghasemi · person · 99%Muhammad Qasim Elahi · person · 99%Murat Kocaoglu · person · 99%Purdue University · organization · 99%Information-Directed Sampling · algorithm · 98%Thompson Sampling · algorithm · 98%Causal Bandits · problem-domain · 95%Structural Causal Model · framework · 93%Non-manipulable Variables · concept · 92%Bayesian Regret · metric · 90%Monte Carlo approximation · method · 88%

Relation Signals (14)

Murat Kocaoglu → affiliatedwith → Johns Hopkins University

confidence 99% · Murat Kocaoglu2 ... School of Computer Science Johns Hopkins University2

Muhammad Qasim Elahi → affiliatedwith → Purdue University

confidence 99% · School of Electrical and Computer Engineering Purdue University1

Murat Kocaoglu → affiliatedwith → Johns Hopkins University

confidence 99% · School of Computer Science Johns Hopkins University2

Mahsa Ghasemi → affiliatedwith → Purdue University

confidence 99% · School of Electrical and Computer Engineering Purdue University1

Muhammad Qasim Elahi → affiliatedwith → Purdue University

confidence 99% · Muhammad Qasim Elahi1 ... School of Electrical and Computer Engineering Purdue University1

Causal Bandits → handles → Non-manipulable Variables

confidence 95% · We study contextual causal bandits with non-manipulable variables

Thompson Sampling → providesregretboundfor → Causal Bandits

confidence 95% · For Thompson Sampling, we establish an entropy-dependent sublinear Bayesian regret bound.

Information-Directed Sampling → providesregretboundfor → Causal Bandits

confidence 95% · For IDS, we derive an entropy-dependent regret bound... recovers the standard sublinear IDS rate.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Causal bandits exploit structural relationships among variables to share information across interventions and accelerate the identification of high-reward decisions. In many applications, however, some variables cannot be directly manipulated, even though they influence the reward and provide useful information about the underlying causal system. We study contextual causal bandits with non-manipulable variables, where context variables are observed before action selection and additional variables are observed after each intervention. Assuming a known causal graph without latent confounding, we adopt a Bayesian formulation in which the conditional probability tables of the observational distribution constitute the unknown parameter. This representation allows observations collected under one intervention to update reward estimates for other interventions through their shared causal mechanisms. We develop causal variants of Thompson Sampling and Information-Directed Sampling (IDS) for this setting. For Thompson Sampling, we establish an entropy-dependent sublinear Bayesian regret bound. For IDS, we derive an entropy-dependent regret bound that explicitly quantifies the additional error introduced by Monte Carlo approximation of the expected regret and information gain; when these quantities are available exactly, the bound recovers the standard sublinear IDS rate. We further provide high-probability confidence bounds for the Monte Carlo estimates used by the algorithm. Experiments on several synthetic causal bandit tasks show that the proposed methods outperform causal and non-causal baselines by more effectively exploiting information shared across interventions.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

110,585 characters extracted from source content.

Expand or collapse full text

Information-Directed Sampling for Causal Bandits Muhammad Qasim Elahi1 Murat Kocaoglu2 Mahsa Ghasemi1 School of Electrical and Computer Engineering Purdue University1 School of Computer Science Johns Hopkins University2 elahi0@purdue.edu, mkocaoglu@jhu.edu, mahsa@purdue.edu Abstract Causal bandits exploit structural relationships among variables to share information across interventions and accelerate the identification of high-reward decisions. In many applications, however, some variables cannot be directly manipulated, even though they influence the reward and provide useful information about the underlying causal system. We study contextual causal bandits with non-manipulable variables, where context variables are observed before action selection and additional variables are observed after each intervention. Assuming a known causal graph without latent confounding, we adopt a Bayesian formulation in which the conditional probability tables of the observational distribution constitute the unknown parameter. This representation allows observations collected under one intervention to update reward estimates for other interventions through their shared causal mechanisms. We develop causal variants of Thompson Sampling and Information-Directed Sampling (IDS) for this setting. For Thompson Sampling, we establish an entropy-dependent sublinear Bayesian regret bound. For IDS, we derive an entropy-dependent regret bound that explicitly quantifies the additional error introduced by Monte Carlo approximation of the expected regret and information gain; when these quantities are available exactly, the bound recovers the standard sublinear IDS rate. We further provide high-probability confidence bounds for the Monte Carlo estimates used by the algorithm. Experiments on several synthetic causal bandit tasks show that the proposed methods outperform causal and non-causal baselines by more effectively exploiting information shared across interventions. 1 Introduction In the classical multi-armed bandit problem, a decision-maker repeatedly selects an action from a finite set and observes the resulting reward. Because the reward distributions are initially unknown, the learner must balance exploration, which gathers information about uncertain actions, and exploitation, which favors actions believed to yield high rewards Lattimore and Szepesvári (2020); Slivkins and others (2019); Vermorel and Mohri (2005). Without additional structure, observing the reward of one action typically provides no direct information about the rewards of the other actions. Consequently, effective algorithms must explore the available actions sufficiently often Garivier and Cappé (2011); Jamieson and Nowak (2014); Jamieson et al. (2014). In many decision-making problems, however, actions are related through a common underlying mechanism. An observation collected after one action may therefore provide information about several other actions. Structured bandit methods exploit such relationships to improve statistical efficiency and reduce unnecessary exploration Schulz et al. (2020); Jun and Zhang (2020); Tirinzoni et al. (2020); Van Parys and Golrezaei (2024); Wan et al. (2023); Mersereau et al. (2009). The central challenge is to characterize and exploit the relevant information-sharing structure while continuing to balance exploration and exploitation. Causal bandits provide a principled framework for structured decision-making when the environment is governed by an underlying structural causal model Lattimore et al. (2016); Sen et al. (2017); Lee and Bareinboim (2018); Wei et al. (2024); Qasim Elahi et al. (2024). In this setting, each action corresponds to an intervention on the causal system, and the resulting observations are generated according to a shared causal model Pearl (2009). Unlike an unstructured bandit model, the reward distributions associated with different interventions are coupled through common causal mechanisms. Consequently, observations obtained under one intervention can potentially improve the learner’s estimates of the rewards associated with other interventions Lattimore et al. (2016); Sen et al. (2017); Yabe et al. (2018); Lee and Bareinboim (2018). Many existing causal bandit formulations permit interventions on a large collection of observed variables. In practice, however, some variables cannot be directly manipulated. Examples include genetic characteristics in healthcare, demographic attributes in public-policy applications, and macroeconomic conditions in economic decision-making. Although such variables are non-manipulable, they may strongly influence the reward and the effects of feasible interventions. Their presence therefore changes the set of candidate interventions and creates an additional challenge for efficiently sharing information across actions. Lee and Bareinboim Lee and Bareinboim (2019) study causal bandits with non-manipulable variables in graphs that may contain latent confounding. They characterize the interventions that can be optimal under the manipulability constraints and use a generalized z2z^2-identification procedure to derive multiple estimators of interventional reward distributions. These estimators are combined through a bootstrap-based minimum-variance weighted average and incorporated into variants of Thompson Sampling and KL-UCB. Their results demonstrate the empirical value of exploiting causal information, but do not provide regret guarantees for the resulting algorithms. We study contextual causal bandits with non-manipulable variables under the assumption that the causal graph is known and contains no latent confounders. At each round, context variables are observed before the learner selects an intervention. The learner subsequently observes the reward and the remaining observed variables in the causal graph. For example, in a healthcare application, patient characteristics and medical history may be available before treatment selection, whereas physiological measurements that cannot be directly manipulated may be observed after treatment. The learner’s objective is to select a feasible intervention that maximizes the context-dependent expected reward. Following the Bayesian information-theoretic framework of Russo and Van Roy (2016, 2014), we represent uncertainty about the causal system using a random parameter θ. Because the graph contains no latent confounders, the relevant interventional distributions are identifiable from the observational distribution through the truncated factorization formula. We therefore let θ collect the conditional probability tables associated with the causal graph. Observations from each round update the posterior distribution over these shared parameters, allowing samples collected under one intervention to improve the estimated rewards and information gains of other interventions. Based on this formulation, we develop causal variants of Thompson Sampling and Information-Directed Sampling. Thompson Sampling selects an intervention according to its posterior probability of being optimal under the observed context. IDS instead selects a distribution over interventions by balancing their expected instantaneous regret against the information they provide about the context-dependent optimal decision. Since the posterior expectations required by IDS are generally unavailable in closed form, we estimate them using Monte Carlo samples and explicitly account for the resulting approximation error. Our main contributions are summarized as follows: • We formulate contextual causal bandits with non-manipulable variables in a Bayesian framework in which the conditional probability tables of the observational distribution are treated as the unknown parameter. This formulation enables observations collected under one intervention to update estimates associated with other interventions through their shared causal mechanisms. • We propose causal Thompson Sampling and Information-Directed Sampling algorithms for this setting. We establish an entropy-dependent sublinear Bayesian regret bound for Thompson Sampling. For IDS, we derive a regret bound that separates the standard information-theoretic term from the additional error caused by Monte Carlo approximation; the oracle version, in which the information ratio is computed exactly, achieves the standard sublinear IDS guarantee. • We derive high-probability concentration bounds for the Monte Carlo estimates of the expected instantaneous regret and contextual information gain. These results provide computable confidence sets and quantify the effect of posterior-sampling error on the IDS regret guarantee. • We evaluate the proposed methods on multiple synthetic causal bandit tasks, including structured examples and randomly generated causal graphs. The results show that the proposed algorithms outperform causal and non-causal baselines by more effectively exploiting information shared across interventions. 2 Preliminaries We adopt the Structural Causal Model (SCM) framework Pearl (2009). An SCM, denoted by ℳM, is defined as a 4-tuple ⟨,,,P()⟩ ,V,F,P(U) , where U denotes a set of exogenous (unobserved) variables determined by factors external to the model, and V denotes a set of endogenous (observed) variables determined by variables in ∪U through the structural functions F. In our setting, the endogenous variables V take values in finite domains and consist of the reward variable Y, actionable (manipulable) variables, non-actionable (non-manipulable) variables, and context variables. For further simplicity, we assume they are binary throughout the paper. For any subset of nodes ⊆X , let Ω() (X) denote the Cartesian product of the state spaces of all variables in X. However, our proposed methods and results also hold when the observed nodes are discrete and may take more than two possible values. The structural functions F specify how each ViV_i is assigned a value, denoted as vi=fi(i,i)v_i=f_i(PA^i,U^i), based on the values of its parent variables i⊆PA^i and exogenous variables i⊆U^i . Finally, P()P(U) is the probability distribution over the exogenous variables U. Each SCM is associated with a causal graph =⟨,⟩G= ,E , where the edge set E consists of two types: directed edges, such as Vi→VjV_i→ V_j, which indicate direct functional dependence (i.e., ViV_i is used in defining fjf_j in F), and bidirected edges, such as Vi↔VjV_i V_j, which represent the presence of an unobserved (latent) confounder affecting both ViV_i and VjV_j. We use notations pa, ch, an, and de to refer to the parents, children, ancestors, and descendants of a variable, respectively. Capitalized forms, such as Pa, Ch, An, and De, include the variable itself (e.g., An(W)=an(W)∪WAn(W)=an(W)∪W). For a set of variables, the relations are defined as the union of their individual outputs, e.g., An()=⋃W∈An(W)An(W)= _W An(W). Note that pa(Vi)=ipa(V_i)=PA^i. A subgraph of G, denoted ¯G_ X, is obtained by removing edges pointing to the variables in X. The connected component (c-component) of the DAG G, containing vertex ViV_i, is denoted by (Vi) C_G(V_i), which is the maximal set of all vertices in G that have a path to ViV_i, consisting only of bi-directed edges Tian and Pearl (2002). In the K-armed bandit problem, K arms with distinct reward distributions are available, and the goal is to minimize cumulative regret over T rounds. Regret is defined as the difference between the maximum expected cumulative reward achievable by always selecting the optimal arm and the expected cumulative reward obtained by a given algorithm. In the SCM-MAB setting, each arm corresponds to an intervention on a subset of variables. Given a causal graph G with reward Y, the arms are defined as do(=)∣⊆∖Ydo(X=x) Y, where the distribution of the reward variable under the intervention do(=)do(X=x), denoted by P(Y)P(Y_x), coincides with the interventional distribution P(Y)P_x(Y). The expected reward associated with an intervention is μ=[Y∣do()] _x=E[Y (x)]. When additional context variables C are observed prior to the intervention, the objective becomes to optimize the expected reward conditioned on the context, namely μ(=)=[Y∣do(),=] _x(C=c)=E[Y (x),C=c]. Moreover, we assume that C is closed under ancestry, i.e., An()=An(C)=C, so that context variables have only other context variables as ancestors and are therefore unaffected by interventions, thereby preserving their interpretation as pre-intervention information and avoiding time-ordering issues. 3 Possibly Optimal Arms for Causal Bandits In this section, we revisit the results of Lee and Bareinboim (2019), which characterize possibly optimal arms in causal bandits when certain nodes in the causal graph are non-manipulable. Let ⊆∖YN \Y\ denote the set of non-manipulable variables, noting that the reward variable Y is also inherently non-manipulable. Definition 1. (Unobserved Confounder (UC)-Territory Lee and Bareinboim (2018)) Consider a causal graph (,)G(V,E) with reward node Y, and let ℋH be the subgraph [(Y)]G[ An(Y)]. A set of variables ⊆V(ℋ)T V(H) containing Y is called a UC-territory on G with respect to Y if ℋ()= De_H(T)=T and ℋ()= C_H(T)=T. A UC-territory is minimal if none of its proper subsets containing Y is a UC-territory. A minimal UC-territory, denoted by (,Y) MUCT(G,Y), can be constructed by starting from the set Y\Y\ and alternately extending the current set by its c-component and its descendants until the set no longer changes. Definition 2. (Interventional Border Lee and Bareinboim (2018)) Let T be a minimal UC-territory on G with respect to Y. Then, =()∖X= Pa(T) is called the interventional border of G with respect to Y, denoted by (,Y) IB(G,Y). Lemma 1. Lee and Bareinboim (2018) For a graph G with reward node Y, (¯,Y) IB(G_ W,Y) is a possibly optimal minimal intervention set (POMIS) for any ⊆∖YW \Y\. XXYYZZ(a) 1G_1 XXYY(b) ℋ1H_1 XXWWYYZ1Z_1Z2Z_2(c) 2G_2 XXWWYY(d) ℋ2H_2 Figure 1: Original causal graphs 1G_1 and 2G_2, along with their projections ℋ1H_1 and ℋ2H_2. For a causal graph G in which all nodes except the reward node Y are manipulable, we use the notation ℙ,YP_G,Y to denote the collection of all POMISs. In the more general setting where the variables in N cannot be intervened upon, we use ℙ,YP^N_G,Y to denote the corresponding collection of possibly optimal minimal intervention sets. Following Lee and Bareinboim (2019), these intervention sets can be obtained through a projection step. We initialize a graph ℋ=⟨∖,∅⟩H= , and add a directed edge Vi→VjV_i→ V_j if Vi→VjV_i→ V_j is present in G, or if there exists a directed path from ViV_i to VjV_j whose non-endpoint vertices all belong to N. We add a bidirected edge Vi↔VjV_i V_j if this edge is present in G, or if the projection of paths passing through variables in N induces latent confounding between ViV_i and VjV_j. The results of Lee and Bareinboim (2019) show that the POMISs of the original causal bandit problem under the manipulability constraints can be obtained by enumerating the POMISs of the projected graph ℋH using Lemma 1. Thus, ℙ,Y=ℙℋ,YP^N_G,Y=P_H,Y. Consider the causal graph 1G_1 with reward node Y and non-manipulable set =ZN=\Z\, and let ℋ1H_1 be the graph resulting from the projection step, as shown in Figure 1. The possibly optimal intervention sets for the original causal graph can be obtained from ℋ1H_1 using Lemma 1. In particular, ℙℋ1,Y=∅,X=ℙ1,YP_H_1,Y=\ ,\X\\=P^N_G_1,Y. Therefore, the candidate optimal arms are do()do(), do(X=0)do(X=0), and do(X=1)do(X=1). Similarly, for the causal graph 2G_2 with reward node Y and non-manipulable set =Z1,Z2N=\Z_1,Z_2\, the projected graph ℋ2H_2 is shown in Figure 1. In this case, ℙℋ2,Y=∅,W=ℙ2,YP_H_2,Y=\ ,\W\\=P^N_G_2,Y, and the candidate optimal arms are do()do(), do(W=0)do(W=0), and do(W=1)do(W=1). More generally, we use A to denote the set of all interventions generated by all POMISs, that is, :=⋃∈ℙ,Ydo(=):∈Ω()A:= _S ^N_G,Y\do(S=s):s∈ (S)\, where do(∅)do( ) denotes the observational action. We use the causal graph 1G_1 to illustrate how samples obtained from different arms can be used to improve reward estimates across interventions. As an illustrative example, let Z represent the age of a patient, let X denote a medication or treatment, and let Y represent the health outcome. The patient’s age Z has a causal effect on the outcome Y but cannot be directly manipulated. The candidate optimal arms are do()do(), do(X=0)do(X=0), and do(X=1)do(X=1). Their expected rewards are given by P(Y=1∣do())=∑x,zP(Y=1∣x,z)P(x∣z)P(z)P(Y=1 do())= _x,zP(Y=1 x,z)P(x z)P(z), P(Y=1∣do(X=0))=∑zP(Y=1∣X=0,z)P(z)P(Y=1 do(X=0))= _zP(Y=1 X=0,z)P(z), and P(Y=1∣do(X=1))=∑zP(Y=1∣X=1,z)P(z)P(Y=1 do(X=1))= _zP(Y=1 X=1,z)P(z). We assume that the causal graph is known, but the observational distribution is unknown. Since all non-intervened variables in the causal graph are observed after each interaction, samples collected under the different interventions can be combined to estimate the conditional distributions of variables given their parents. Because these conditional distributions are shared across the reward expressions of different interventions, observations obtained under one arm can improve the estimated rewards of the other arms. In the next section, we formalize this information sharing through a Bayesian posterior over the parameters of the observational distribution. 4 Bayesian Formulation for Causal Bandits We consider a general probabilistic (Bayesian) formulation in which uncertain quantities are modeled as random variables. At each time t, the agent selects an action At∈A_t and observes a reward. For each action a∈a and time t, let Ya,t∈Y_a,t denote the potential reward that would be observed at time t if action a were selected. There exists an unknown real-valued parameter vector θ such that, conditioned on θ, the rewards are independent across time and satisfy [YAt,t∣]=μ(At)E[Y_A_t,t θ]= _ θ(A_t). The parameter θ is random under a prior distribution, capturing uncertainty about the underlying reward-generating mechanism. Uncertainty in θ induces uncertainty about the optimal action A⋆∈arg⁡maxa∈⁡μ(a)A ∈ _a _ θ(a), where ties are broken using a fixed deterministic rule. The mean cumulative regret of a policy is defined as [RegT]=[∑t=1T(YA⋆,t−YAt,t)]E[Reg_T]=E\! [ _t=1^T (Y_A ,t-Y_A_t,t ) ], where the expectation is taken over the randomness in the actions AtA_t, the rewards, and the prior distribution over θ. This performance metric is commonly referred to as Bayesian regret or Bayesian risk. Action AtA_t is chosen based on the history ℱt=(1,A1,A1,1,YA1,1,…,t−1,At−1,At−1,t−1,YAt−1,t−1)F_t= (C_1,A_1,V_A_1,1,Y_A_1,1,…,C_t-1,A_t-1,V_A_t-1,t-1,Y_A_t-1,t-1 ) available before observing the context at time t. Formally, a randomized policy π=(πt)t∈ℕπ= ( _t )_t is a sequence of deterministic functions, where πt(ℱt,t) _t (F_t,C_t ) specifies a probability distribution over the action set A. Let ()D(A) denote the set of probability distributions over A. After observing tC_t, the action AtA_t is selected by sampling from πt(ℱt,t) _t (F_t,C_t ). With some abuse of notation, we typically denote this distribution by πt _t, where πt(a∣t)=ℙ(At=a∣ℱt,t=t) _t(a _t)=P (A_t=a _t,C_t=c_t ) denotes the probability assigned to action a under the realized context tc_t. As shorthand notation, we use Pt(⋅)P_t(·) for P(⋅∣ℱt)P(· _t) and t(⋅)E_t(·) for (⋅∣ℱt)E(· _t), respectively. After observing t=tC_t=c_t, we define the context-conditioned posterior by Ptt(⋅):=P(⋅∣ℱt,t=t)P_t^c_t(·):=P(· _t,C_t=c_t) and the corresponding conditional expectation by t(⋅)E_t^c_t(·). In the contextual setting, at each time t, a context t∈C_t is observed prior to selecting an action. The expected reward depends on both the action and the context and satisfies [YAt,t∣t=,]=μ(At,)E[Y_A_t,t _t=c, θ]= _ θ(A_t,c). Accordingly, we define the oracle mapping Π⋆:→ :C by Π⋆():=arg⁡maxa∈⁡μ(a,) (c):= _a _ θ(a,c), where ties are broken using a fixed deterministic rule. The mean cumulative Bayesian regret relative to this oracle mapping, conditional on the realized contexts tt=1T\C_t\_t=1^T, is given by [∑t=1T(YΠ⋆(t),t−YAt,t)|tt=1T].E [ _t=1^T (Y_ (C_t),t-Y_A_t,t )\, |\,\C_t\_t=1^T ]. (1) One remaining task is to specify the parameter θ in the causal bandit setting. We assume that the causal graph contains no unobserved confounders. Under this assumption, any interventional distribution, including the conditional interventional distributions arising in the contextual setting, is identifiable from the observational distribution and the graph structure through the truncated factorization formula Pearl (2009). For instance, P(∖∣do())=∏Vi∈∖P(vi∣i)P(v_V do(x))= _V_i P(v_i _i), where the parent values are evaluated consistently with the intervention =X=x. Thus, the observational distribution naturally determines the parameter θ. Under the Markov assumption, the joint distribution factorizes as P()=∏Vi∈P(vi∣i)P(v)= _V_i P(v_i _i). Rather than computing the posterior over the entire joint observational distribution, we compute the posterior over its local conditional probability distributions using the history of observations ℱtF_t. For each variable Vi∈V_i with rir_i possible values xi1,…,xirix_i^1,…,x_i^r_i, the local likelihood consists of a collection of multinomial distributions, one for each configuration of iPa_i. Specifically, P(Vi=xik∣i=ij,ij)=θijkP (V_i=x_i^k _i=pa_i^j, θ_ij )= _ijk, where θijk>0 _ijk>0 and ∑k=1riθijk=1 _k=1^r_i _ijk=1. Here, i1,…,iqipa_i^1,…,pa_i^q_i denote the qiq_i possible configurations of the parent set iPa_i, where qi=∏Xℓ∈irℓq_i= _X_ _ir_ , and ij=(θij1,…,θijri) θ_ij=( _ij1,…, _ijr_i) denotes the parameter vector associated with the j-th parent configuration. We define i=(i1,…,iqi) θ_i=( θ_i1,…, θ_iq_i), and the overall parameter vector is therefore =(1,…,n) θ=( θ_1,…, θ_n). Similar to Heckerman et al. (2006), to ensure efficient computation, we assume parameter independence across the vectors ij θ_ij. Consequently, conditioned on the history of observations ℱtF_t, each vector ij θ_ij can be updated independently. Assuming that each vector ij θ_ij follows a conjugate Dirichlet prior, namely Dir⁡(ij∣αij1,…,αijri)Dir\! ( θ_ij _ij1,…, _ijr_i ), the posterior distribution over the parameter space is given by Pt()=P(∣ℱt)=∏i=1n∏j=1qiPt(ij).P_t( θ)=P ( θ _t )= _i=1^n _j=1^q_iP_t( θ_ij). (2) Pt(ij)=Dir⁡(ij∣αij1+Nij1(ℱt),…,αijri+Nijri(ℱt)).P_t( θ_ij)=Dir ( θ_ij _ij1+N_ij1(F_t),…, _ijr_i+N_ijr_i(F_t) ). (3) Here, Nijk(ℱt)N_ijk(F_t) denotes the number of times the realization Vi=xikV_i=x_i^k has been observed in the history ℱtF_t when i=ijPa_i=pa_i^j and the corresponding action does not intervene on ViV_i. After observing the current context t=tC_t=c_t, the posterior used for action selection is Ptt()=P(∣ℱt,t=t)P_t^c_t( θ)=P( θ _t,C_t=c_t), which is obtained by conditioning Pt()P_t( θ) on the observed context. Equation (2) can be used to compute the posterior over the parameter space and to draw posterior samples. Maintaining an accurate posterior is crucial for effective exploration and exploitation in the bandit problem. Input : Causal graph G and the action set A induced by all POMISs of the projected graph. for t=1t=1 to T do Compute the posterior Pt()P_t( θ) using (2); Observe the realized context t=tC_t=c_t; Compute the context-conditioned posterior Ptt()P_t^c_t( θ); Sample t∼Ptt() θ_t P_t^c_t( θ); Select action at←arg⁡maxa∈⁡[Ya,t∣t,t]a_t← _a E[Y_a,t θ_t,c_t]; Play action ata_t, observe the reward and all non-intervened variables, and update the history ℱt+1F_t+1; Algorithm 1 Thompson Sampling for causal bandits with non-manipulable variables 5 Thompson Sampling Algorithm for Causal bandits A bandit algorithm can select actions according to the posterior probability that an intervention is optimal, a strategy known as posterior sampling or Thompson sampling Thompson (1933). We propose a Thompson sampling algorithm for causal bandits with non-manipulable variables. Algorithm 1 maintains, at each round t, a posterior distribution over the parameter space, denoted by Pt()P_t( θ), capturing uncertainty given the history of observations up to round t. After observing the realized context t=tC_t=c_t, the action at round t is selected as at∈arg⁡maxa∈⁡[Ya,t∣t,t],a_t∈ _a E[Y_a,t θ_t,c_t], where t θ_t is an independent sample drawn from the context-conditioned posterior distribution Pt(∣t=t)P_t( θ _t=c_t). The posterior is updated in a Bayesian manner after each interaction, consistent with the classical Thompson sampling framework. To analyze regret in the contextual setting, we introduce a nonnegative coefficient Γt _t such that the expected instantaneous regret satisfies t[YΠ⋆(t),t−YAt,t∣t]≤ΓtIt(Π⋆(t);(At,YAt,t)∣t).E_t\! [Y_ (C_t),t-Y_A_t,t _t ]≤ _t I_t\! ( (C_t);(A_t,Y_A_t,t) _t ). The quantity Γt2 _t^2 is referred to as the information ratio and characterizes the trade-off between incurring low regret and acquiring information about the optimal action under the realized context. The term It(Π⋆(t);(At,YAt,t)∣t):=DKL(Pt(Π⋆(t),At,YAt,t∣t)∥Pt(Π⋆(t)∣t)Pt(At,YAt,t∣t))I_t\! ( (C_t);(A_t,Y_A_t,t) _t ):=D_KL\! (P_t\! ( (C_t),A_t,Y_A_t,t _t )\; \|\;P_t\! ( (C_t) _t )P_t\! (A_t,Y_A_t,t _t ) ) denotes the filtered mutual information between the optimal action under the realized context and the action-reward observation at round t. This quantity measures how much the observation collected at round t reduces uncertainty about the optimal action under the realized context. Since Π⋆(t) (C_t) is a deterministic function of the full oracle mapping Π⋆ , the cumulative information gain is bounded by the entropy H(Π⋆)H( ). Theorem 1 provides a bound on the mean cumulative regret. Theorem 1. The mean cumulative Bayesian regret of Algorithm 1 is bounded for any T∈ℕT as follows, where Γ≥Γt ≥ _t for all t∈1,…,Tt∈\1,…,T\: [∑t=1T(YΠ⋆(t),t−YAt,t)]≤ΓH(Π⋆)T.E\! [ _t=1^T (Y_ (C_t),t-Y_A_t,t ) ]≤ H( )\,T. The entropy H(Π⋆)H( ) quantifies the decision-maker’s initial uncertainty regarding the optimal-action mapping. The mean cumulative regret incurred by Algorithm 1 depends on the time horizon T, the entropy H(Π⋆)H( ), and the worst-case upper bound on the information-ratio coefficient Γt _t. Following Russo and Van Roy (2016), we establish a simple worst-case upper bound given by Γt2≤||2 _t^2≤ |A|2, or equivalently Γt≤||2 _t≤ |A|2. We adopt this worst-case bound because the causal structure may provide no useful information sharing across interventions in the worst case. Therefore, the constant Γ in Theorem 1 can be replaced with ||2 |A|2, leading to the regret bound stated in Corollary 1. Moreover, since Π⋆ maps the context space C to the action space A, the number of possible mappings is |||||A|^|C| when C is finite, which implies that the entropy satisfies H(Π⋆)≤log⁡(||||)=||log⁡||H( )≤ (|A|^|C| )=|C| |A|. Corollary 1. Suppose that the context space C is finite. The mean cumulative Bayesian regret for Algorithm 1 is bounded for any T∈ℕT as follows: [∑t=1T(YΠ⋆(t),t−YAt,t)]≤T||||log⁡||2.E\! [ _t=1^T (Y_ (C_t),t-Y_A_t,t ) ]≤ T|A||C| \!|A|2. 6 Information-Directed Sampling Algorithm for Causal bandits Information-Directed Sampling (IDS) is a general framework for constructing decision-making algorithms. Rather than specifying a concrete sequence of computational steps, IDS defines an optimization criterion that guides the selection of actions. The framework balances two competing objectives: minimizing the expected instantaneous regret and acquiring informative observations about the identity of the optimal action. In the contextual setting, after observing the realized context t=tC_t=c_t at time t, IDS selects an action distribution that minimizes the ratio of the squared expected regret Δt(π∣t)2 _t(π _t)^2 to the information gain gt(π∣t)g_t(π _t) about the optimal action under that context, namely Π⋆(t) (c_t), over all sampling distributions π∈()π (A). The resulting IDS policy πtIDS(t) _t^IDS(c_t) is formally defined as: πtIDS(t)∈argminπ∈()Ψt(π∣t):=Δt(π∣t)2gt(π∣t). _t^IDS(c_t)∈ _π (A) \ _t(π _t):= _t(π _t)^2g_t(π _t) \. The expected instantaneous regret of a policy π is defined as Δt(π∣t)=∑a∈π(a)Δt(a∣t) _t(π _t)= _a π(a) _t(a _t), where Δt(a∣t):=t[YΠ⋆(t),t−Ya,t∣t=t] _t(a _t):=E_t\! [Y_ (c_t),t-Y_a,t _t=c_t ] denotes the expected instantaneous regret incurred by selecting action a at time step t under context tc_t. Thus, the regret of a randomized policy is the probability-weighted average of the regrets of its constituent actions. Similarly, the information gain of a policy is defined as gt(π∣t)=∑a∈π(a)gt(a∣t)g_t(π _t)= _a π(a)g_t(a _t), where gt(a∣t):=It(Π⋆(t);Ya,t∣t=t)=Ht(Π⋆(t)∣t=t)−Ht(Π⋆(t)∣t=t,Ya,t)g_t(a _t):=I_t\! ( (c_t);Y_a,t _t=c_t )=H_t\! ( (c_t) _t=c_t )-H_t\! ( (c_t) _t=c_t,Y_a,t ) denotes the information gained by selecting action a. In other words, gt(a∣t)g_t(a _t) measures the expected reduction in posterior uncertainty about the optimal action under context tc_t after observing the corresponding reward Ya,tY_a,t. The quantity Ψt(π∣t) _t(π _t), referred to as the information ratio, quantifies the expected regret incurred per unit of information acquired and therefore captures the trade-off between exploiting actions with low immediate regret and exploring actions that provide information about the optimal action. At each time step, IDS greedily selects a policy that minimizes this criterion. We adopt the conventions 0/0:=00/0:=0 and x/0:=+∞x/0:=+∞ for every x>0x>0. Input: Causal graph G, confidence level δ′δ , posterior sample size N, and action set A induced by all POMISs of the projected graph for t=1t=1 to T do Compute the posterior Pt()P_t( θ) using (2); Observe the realized context t=tC_t=c_t; Compute the context-conditioned posterior Ptt()=P(∣ℱt,t=t)P_t^c_t( θ)=P( θ _t,C_t=c_t); Draw N independent samples from Ptt()P_t^c_t( θ); For every a∈a , select any value Δ~t(a∣t) _t(a _t) from the confidence interval in Lemma 3, using δ=δ′2T||δ= δ 2T|A|; For every a∈a , select any value g~t(a∣t) g_t(a _t) from the confidence interval [g¯t(a∣t),g¯t(a∣t)] [ g_t(a _t), g_t(a _t) ] in Lemma 4, using δ=δ′2T||δ= δ 2T|A|; Set Δ→t(t):=[Δ~t(a∣t)]a∈ _t(c_t):=[ _t(a _t)]_a ; Set g→t(t):=[g~t(a∣t)]a∈ g_t(c_t):=[ g_t(a _t)]_a ; at←IDSAction(,Δ→t(t),g→t(t))a_t \! (A, _t(c_t), g_t(c_t) ); Play action ata_t, observe the reward and all non-intervened variables, and update the history ℱt+1F_t+1; Algorithm 2 Information-Directed Sampling for Causal Bandits with Non-Manipulable Variables We use an example to illustrate why the quantity gt(a∣t)g_t(a _t) is useful for characterizing how informative a particular action is. Since we treat the observational distribution as defining the parameter space, one might argue that the empty intervention do()do() is the most informative about the parameter θ, as it provides direct samples from the natural data-generating process. However, our objective is not merely to learn the full observational distribution, but rather to reduce uncertainty about the optimal action under the realized context t=tC_t=c_t. Consider a simple causal graph in which X→YX→ Y. The quantities relevant for identifying the optimal action are the context-dependent conditional probabilities P(Y=1∣X=0,t)P(Y=1 X=0,c_t) and P(Y=1∣X=1,t)P(Y=1 X=1,c_t). If P(X=0∣t)P(X=0 _t) is small relative to P(X=1∣t)P(X=1 _t), then samples drawn from the observational distribution will rarely provide information about the behavior of Y when X=0X=0 under that context. In such a case, performing the intervention do(X=0)do(X=0) may be substantially more informative than do()do() for determining the optimal action Π⋆(t) (c_t). This distinction is precisely captured by gt(a∣t)g_t(a _t), which measures the expected reduction in posterior uncertainty about Π⋆(t) (c_t) resulting from selecting action a. We now proceed to formally derive the expressions needed to compute Δt(a∣t) _t(a _t) and gt(a∣t)g_t(a _t). Lemma 2. The information gain associated with an action a∈a at time step t, conditional on the realized context t=tC_t=c_t, is given by gt(a∣t)=DKL(Ptt(Π⋆(t),Ya)∥Ptt(Π⋆(t))Ptt(Ya)).g_t(a _t)=D_KL\! (P_t^c_t\! ( (c_t),Y_a )\, \|\,P_t^c_t\! ( (c_t) )P_t^c_t\! (Y_a ) ). (4) The corresponding posterior distributions satisfy Ptt(Π⋆(t)=a⋆)=∼Ptt()[a⋆=arg⁡maxa′∈⁡μ(a′,t)],P_t^c_t\! ( (c_t)=a )=E_ θ P_t^c_t( θ) [ 1\! \a = _a _ θ(a ,c_t) \ ], (5) Ptt(Ya=y)=∼Ptt()[P(Ya=y∣,t)],P_t^c_t\! (Y_a=y )=E_ θ P_t^c_t( θ) [P\! (Y_a=y θ,c_t ) ], (6) and Ptt(Π⋆(t)=a⋆,Ya=y) P_t^c_t\! ( (c_t)=a ,Y_a=y ) =∼Ptt()[a⋆=arg⁡maxa′∈⁡μ(a′,t)P(Ya=y∣,t)], =E_ θ P_t^c_t( θ) [ 1\! \a = _a _ θ(a ,c_t) \P\! (Y_a=y θ,c_t ) ], (7) for every a⋆∈a and y∈0,1y∈\0,1\. Moreover, the expected instantaneous regret associated with action a at time step t under context tc_t is Δt(a∣t) _t(a _t) =∼Ptt()[∑a⋆∈a⋆=argmaxa′∈μ(a′,t) =E_ θ P_t^c_t( θ) [ _a 1\! \a = _a _ θ(a ,c_t) \ ×P(Ya⋆=1∣,t)−P(Ya=1∣,t)]. 99.58464pt× P\! (Y_a =1 θ,c_t )-P\! (Y_a=1 θ,c_t ) ]. (8) When the parameter space is finite and discrete, the quantities gt(a∣t)g_t(a _t) and Δt(a∣t) _t(a _t) can be evaluated exactly by summing over all possible values of θ. In our contextual causal bandit setting, however, θ parameterizes the observational distribution and belongs to a continuous probability simplex. Consequently, the posterior expectations defining gt(a∣t)g_t(a _t) and Δt(a∣t) _t(a _t) are generally analytically intractable. We therefore approximate these quantities using Monte Carlo samples drawn from the context-conditioned posterior distribution Ptt()P_t^c_t( θ). The following results control the approximation error introduced by this sampling procedure. Lemma 3 (Concentration of the Expected Regret). Fix a time step t, a realized context t=tC_t=c_t, an action a∈a , and δ∈(0,1)δ∈(0,1). Let Δ^t(a∣t) _t(a _t) be the Monte Carlo estimator of Δt(a∣t) _t(a _t) computed using N independent samples from Ptt()P_t^c_t( θ). Then, with probability at least 1−δ1-δ, |Δ^t(a∣t)−Δt(a∣t)|≤2Nlog⁡(2δ). | _t(a _t)- _t(a _t) |≤ 2N \! ( 2δ ). To control the Monte Carlo approximation error in the information gain, we derive simultaneous concentration bounds for the posterior probabilities Ptt(Π⋆(t)=a⋆)P_t^c_t( (c_t)=a ), Ptt(Ya=y)P_t^c_t(Y_a=y), and Ptt(Π⋆(t)=a⋆,Ya=y)P_t^c_t( (c_t)=a ,Y_a=y). These bounds yield computable lower and upper confidence bounds for gt(a∣t)g_t(a _t) that hold uniformly over all actions. Lemma 4 (Concentration of the Information Gain). Fix a time step t, a realized context t=tC_t=c_t, and δ∈(0,1)δ∈(0,1). For each a∈a , let g¯t(a∣t) g_t(a _t) and g¯t(a∣t) g_t(a _t) denote the lower and upper confidence bounds defined in (35) and (33), respectively, and constructed using N independent samples from the context-conditioned posterior distribution Ptt()P_t^c_t( θ). Then, with probability at least 1−δ1-δ over the Monte Carlo samples, g¯t(a∣t)≤gt(a∣t)≤g¯t(a∣t),∀a∈. g_t(a _t)≤ g_t(a _t)≤ g_t(a _t), ∀ a . The proof of Lemma 4, together with the explicit construction of the confidence bounds, is provided in Appendix A.6. Theorem 2. Fix δ′∈(0,1)δ ∈(0,1) and a horizon T∈ℕT . With probability at least 1−δ′1-δ over the Monte Carlo samples used by Algorithm 2, the Bayesian regret satisfies [∑t=1T(YΠ⋆(t),t−YAt,t)]≤H(Π⋆)(T||2+2∑t=1Tγt). \! [ _t=1^T (Y_ (C_t),t-Y_A_t,t ) ]≤ H( ) ( T|A|2+2 _t=1^T _t ). (9) Here, for each time step t, γt:=supπ∈S||,t 1(t),t 2(t)∈tΔ(t),t 1(t),t 2(t)∈tg(t)|(π⊤t 1(t))2π⊤t 1(t)−(π⊤t 2(t))2π⊤t 2(t)|, _t:= _ subarraycπ∈ S_|A|,\\ _t^\,1(c_t), _t^\,2(c_t) _t(c_t),\\ g_t^\,1(c_t), g_t^\,2(c_t) ^g_t(c_t) subarray | (π _t^\,1(c_t) )^2π g_t^\,1(c_t)- (π _t^\,2(c_t) )^2π g_t^\,2(c_t) |, (10) where S||:=π∈ℝ+||:∑a∈π(a)=1.S_|A|:= \π ^|A|_+: _a π(a)=1 \. The vectors t 1(t) _t^\,1(c_t) and t 2(t) _t^\,2(c_t) range over the componentwise confidence set (tΔ(t))(C _t(c_t)) obtained from Lemma 3, while t 1(t) g_t^\,1(c_t) and t 2(t) g_t^\,2(c_t) range over the componentwise confidence set (tg(t))(C^g_t(c_t)) obtained from Lemma 4, all evaluated at the realized context t=tC_t=c_t. Both confidence sets are constructed using δ=δ′2T||δ= δ 2T|A|. The expectation in (9) is taken over the prior, contexts, rewards, and action-selection randomness, conditional on the Monte Carlo confidence event. We analyze the regret of the proposed IDS algorithm for causal bandits with non-manipulable variables (Algorithm 2). Theorem 2 provides a Bayesian regret bound in which the additional term involving γt _t quantifies the effect of computing the information ratio using Monte Carlo estimates. The widths of the confidence intervals in Lemma 3 and Lemma 4 scale as O(log⁡(c/δ)/N)O\! ( (c/δ)/N ) for an appropriate constant c. Therefore, increasing the posterior sample size N shrinks the confidence sets and can only decrease, or leave unchanged, γt _t. Similarly, decreasing δ produces a higher-confidence guarantee but wider confidence intervals, which can increase γt _t, whereas increasing δ produces narrower intervals and can decrease γt _t. In Theorem 2, the choice δ=δ′/(2T||)δ=δ /(2T|A|) balances the simultaneous confidence requirement across all rounds and actions with the resulting estimation error. Provided that the relevant information-gain denominators remain bounded away from zero, the confidence sets contract as N increases, and consequently γt _t approaches zero. Thus, γt _t measures the worst-case inflation of the information ratio caused by finite Monte Carlo estimation. In the idealized oracle setting, the information ratio is computed exactly, the confidence sets collapse to the true values, and γt=0 _t=0 for every t. Corollary 2 (IDS with Oracle Access). Suppose the information ratio can be computed exactly at every round, equivalently, the Monte Carlo estimation error vanishes so that γt=0 _t=0 for all t. Then, for any T∈ℕT , the mean cumulative regret of Algorithm 2 satisfies [∑t=1T(YΠ⋆(t),t−YAt,t)]≤||2TH(Π⋆).E\! [ _t=1^T (Y_ (C_t),t-Y_A_t,t ) ]≤ |A|2\,T\,H( ). This result follows directly from the standard IDS analysis when the information ratio is computed exactly. To illustrate how causal structure can affect the prior distribution over optimal interventions and thereby tighten the regret bound, consider the causal graph in Figure 2(a), consisting of the binary nodes X, Y, and Z, with edges X→YX→ Y, Z→XZ→ X, and Z→YZ→ Y, where Y is the reward node and Z is non-manipulable. There is no context variable in this example. Because Z cannot be manipulated, the feasible intervention set is =do(),do(X=1),do(X=0)A=\do(),do(X=1),do(X=0)\. Unlike an unstructured bandit model in which the arms are assigned unrelated reward parameters, the expected rewards of these interventions are jointly determined by the same causal mechanisms and shared conditional probability tables. Thus, the causal model induces a joint prior over the intervention rewards and, consequently, a prior distribution over the optimal intervention Π⋆ . Assuming no prior observations, we place independent Beta⁡(1,1)Beta(1,1) priors on the Bernoulli parameters in each row of the conditional probability tables and estimate P(Π⋆=a)P( =a) using N=50,000N=50,000 Monte Carlo samples. We obtain P(Π⋆=do())≈0.08P( =do())≈ 0.08, P(Π⋆=do(X=1))≈0.46P( =do(X=1))≈ 0.46, and P(Π⋆=do(X=0))≈0.46P( =do(X=0))≈ 0.46. By Hoeffding’s inequality and a union bound over the three interventions, these estimates have a simultaneous error bound of approximately ±0.0093± 0.0093 at overall confidence level 0.9990.999. The resulting entropy is H(Π⋆)=−∑a∈P(Π⋆=a)log⁡P(Π⋆=a)≈0.9165H( )=- _a P( =a) P( =a)≈ 0.9165, which is strictly smaller than the worst-case value log⁡||=log⁡3≈1.0986 |A|= 3≈ 1.0986. Consequently, the oracle IDS regret bound becomes [RegT]≤3H(Π⋆)T/2≈1.1725TE[Reg_T]≤ 3H( )T/2≈ 1.1725 T, whereas the worst-case uniform-prior benchmark is 3log⁡(3)T/2≈1.2837T 3 (3)T/2≈ 1.2837 T. Thus, in this example, the causal model reduces the leading regret coefficient by approximately 8.7%8.7\% relative to the worst-case entropy bound. Moreover, because the interventions share the same causal mechanisms, observations collected under one intervention can update beliefs about the rewards and information gains of other interventions, although this additional cross-intervention information sharing is not explicitly captured by the worst-case factor ||/2|A|/2. 7 Experiments We empirically compare the performance of our proposed algorithms with existing baselines on three tasks of increasing complexity. The corresponding causal graphs are shown in Figure 2, where red nodes denote non-manipulable variables, C denotes a context variable, and Y denotes the reward variable. For Task 1 (Figure 2(a)), the set of POMISs after the projection step is ∅,X\ ,\X\\, resulting in the possibly optimal arms do()do(), do(X=0)do(X=0), and do(X=1)do(X=1). For Task 2 (Figure 2(b)), the set of POMISs is X1,X2\\X_1\,\X_2\\, yielding the possibly optimal arms do(X1=0)do(X_1=0), do(X1=1)do(X_1=1), do(X2=0)do(X_2=0), and do(X2=1)do(X_2=1). For Task 3 (Figure 2(c)), the set of POMISs is ∅,X1,X2,X1,X2\ ,\X_1\,\X_2\,\X_1,X_2\\, resulting in a total of nine possibly optimal arms. We evaluate three baseline methods, including two non-causal algorithms: vanilla UCB and Bernoulli Thompson Sampling (TS), both applied to the set of possibly optimal interventions identified from the POMISs. The third baseline is the algorithm proposed in Lee and Bareinboim (2019), which uses z2z^2ID to construct multiple estimators of each arm’s reward distribution and combines them using minimum-variance convex weights obtained through quadratic programming. For all three tasks, the CPTs are randomly sampled to construct Bayesian networks consistent with the corresponding causal graphs. For each baseline and each proposed algorithm, we run 500 independent trials and plot the average cumulative regret, together with bands corresponding to two standard deviations, in Figure 3. For tasks containing a context variable, a new context value is sampled independently at each round, and all algorithms select actions conditioned on the observed context. For IDS, the number of posterior samples used to estimate the expected regret and information gain is set to N=1000N=1000. The results show that both proposed algorithms outperform the baselines by more effectively exploiting the causal structure and the information shared across interventions. In particular, IDS outperforms Thompson Sampling by explicitly balancing expected instantaneous regret against information gain, thereby favoring informative interventions that reduce posterior uncertainty about the context-dependent optimal action. XXYYZZ (a) Task 11 X2X_2YYX1X_1CCZZ (b) Task 22 X1X_1YYX2X_2X3X_3Z1Z_1Z2Z_2C (c) Task 33 Figure 2: Causal graphs used in the experiments (a) Task 11 (b) Task 22 (c) Task 33 Figure 3: Regret versus time for the three tasks with the corresponding causal graphs shown in Figure 2 (a) N=10,ρ=0.1N_G=10,ρ=0.1 (b) N=15,ρ=0.1N_G=15,ρ=0.1 (c) N=15,ρ=0.2N_G=15,ρ=0.2 Figure 4: Regret versus time for Erdős–Rényi random chordal graphs with varying graph density We further compare our proposed algorithms with the baseline methods on Erdős–Rényi random chordal graphs with varying numbers of nodes N_G and graph densities ρ. After sampling each causal graph, 15%15\% of its nodes are randomly designated as non-manipulable, and a subset of the remaining nodes is designated as context variables. The results are shown in Figure 4, and the graph-generation procedure is described in Section A.10 of the supplementary material. As in the three structured tasks, the proposed algorithms achieve lower cumulative regret than the baselines on the randomly generated graphs. Finally, we consider an additional synthetic causal graph motivated by a real-world healthcare scenario in Section A.9 of the supplementary material, further illustrating the applicability of the proposed framework. 8 Conclusion We study contextual causal bandits with non-manipulable variables and introduce Bayesian Thompson Sampling (TS) and Information-Directed Sampling (IDS) algorithms for this setting. By maintaining a posterior distribution over the conditional probability tables of the causal model, the proposed methods exploit information shared across interventions to improve learning efficiency. We establish an entropy-dependent sublinear Bayesian regret bound for Thompson Sampling. For IDS, we derive a regret guarantee that explicitly captures the additional error introduced by Monte Carlo approximation, while the oracle version recovers the standard sublinear IDS bound. Empirical results on structured and randomly generated causal graphs show that the proposed algorithms outperform existing causal and non-causal baselines. Overall, our framework provides a principled approach for sequential decision-making in causal systems containing variables that influence the reward but cannot be directly manipulated. 9 Acknowledgements This research has been supported in part by NSF CAREER 2617987, IIS 2617859, Adobe Research and Intuit. References A. Garivier and O. Cappé (2011) The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, p. 359–376. Cited by: §1. D. Heckerman, C. Meek, and G. Cooper (2006) A bayesian approach to causal discovery. Innovations in Machine Learning: Theory and Applications, p. 1–28. Cited by: §4. K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck (2014) Lil’UCB: an optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, p. 423–439. Cited by: §1. K. Jamieson and R. Nowak (2014) Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 2014 48th annual conference on information sciences and systems (CISS), p. 1–6. Cited by: §1. K. Jun and C. Zhang (2020) Crush optimism with pessimism: structured bandits beyond asymptotic optimality. Advances in Neural Information Processing Systems 33, p. 6366–6376. Cited by: §1. D. Koller and N. Friedman (2009) Probabilistic graphical models: principles and techniques. MIT press. Cited by: §A.10. F. Lattimore, T. Lattimore, and M. D. Reid (2016) Causal bandits: learning good interventions via causal inference. In Advances in Neural Information Processing Systems, p. 1181–1189. Cited by: §1. T. Lattimore and C. Szepesvári (2020) Bandit algorithms. Cambridge University Press. Cited by: §1. S. Lee and E. Bareinboim (2018) Structural causal bandits: where to intervene?. In Advances in Neural Information Processing Systems 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), p. 2573–2583. Cited by: §1, Definition 1, Definition 2, Lemma 1. S. Lee and E. Bareinboim (2019) Structural causal bandits with non-manipulable variables. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, p. 4164–4172. Cited by: §1, §3, §3, §7. A. J. Mersereau, P. Rusmevichientong, and J. N. Tsitsiklis (2009) A structured multiarmed bandit problem and the greedy policy. IEEE Transactions on Automatic Control 54 (12), p. 2787–2802. Cited by: §1. J. Pearl (2009) Causality. Cambridge University Press. Cited by: §1, §2, §4. M. Qasim Elahi, M. Ghasemi, and M. Kocaoglu (2024) Partial structure discovery is sufficient for no-regret learning in causal bandits. arXiv e-prints, p. arXiv–2411. Cited by: §1. D. Russo and B. Van Roy (2014) Learning to optimize via information-directed sampling. Advances in neural information processing systems 27. Cited by: §A.1, §1. D. Russo and B. Van Roy (2016) An information-theoretic analysis of thompson sampling. Journal of Machine Learning Research 17 (68), p. 1–30. Cited by: §1, §5. E. Schulz, N. T. Franklin, and S. J. Gershman (2020) Finding structure in multi-armed bandits. Cognitive psychology 119, p. 101261. Cited by: §1. R. Sen, K. Shanmugam, A. G. Dimakis, and S. Shakkottai (2017) Identifying best interventions through online importance sampling. arXiv preprint arXiv:1701.02789. Cited by: §1. A. Slivkins et al. (2019) Introduction to multi-armed bandits. Foundations and Trends® in Machine Learning 12 (1-2), p. 1–286. Cited by: §1. C. Squires, S. Magliacane, K. Greenewald, D. Katz, M. Kocaoglu, and K. Shanmugam (2020) Active structure learning of causal dags via directed clique trees. Advances in Neural Information Processing Systems 33, p. 21500–21511. Cited by: §A.10. W. R. Thompson (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 (3/4), p. 285–294. Cited by: §5. J. Tian and J. Pearl (2002) A general identification condition for causal effects. In Aaai/iaai, p. 567–573. Cited by: §2. A. Tirinzoni, A. Lazaric, and M. Restelli (2020) A novel confidence-based algorithm for structured bandits. In International Conference on Artificial Intelligence and Statistics, p. 3175–3185. Cited by: §1. B. Van Parys and N. Golrezaei (2024) Optimal learning for structured bandits. Management Science 70 (6), p. 3951–3998. Cited by: §1. J. Vermorel and M. Mohri (2005) Multi-armed bandit algorithms and empirical evaluation. In European conference on machine learning, p. 437–448. Cited by: §1. R. Wan, L. Ge, and R. Song (2023) Towards scalable and robust structured bandits: a meta-learning framework. In International Conference on Artificial Intelligence and Statistics, p. 1144–1173. Cited by: §1. L. Wei, M. Q. Elahi, M. Ghasemi, and M. Kocaoglu (2024) Approximate allocation matching for structural causal bandits with unobserved confounders. Advances in Neural Information Processing Systems 36. Cited by: §1. A. Yabe, D. Hatano, H. Sumita, S. Ito, N. Kakimura, T. Fukunaga, and K. Kawarabayashi (2018) Causal bandits with propagating inference. arXiv preprint arXiv:1806.02252. Cited by: §1. Appendix A Supplementary Material In the following subsections, we provide comprehensive and formal mathematical proofs for the the theorems presented in the main paper. A.1 Optimizing the Contextual Information Ratio If g→t(t)=0→ g_t(c_t)= 0, then none of the available actions provides information about the optimal action under context tc_t. In this case, we select an action that minimizes the expected instantaneous regret. Otherwise, at time t we select an action by solving minπ∈S||⁡(π⊤Δ→t(t))2π⊤g→t(t), _π∈ S_|A| (π _t(c_t) )^2π g_t(c_t), (11) where S||=π∈ℝ+||:∑kπk=1S_|A|=\π _+^|A|: _k _k=1\ is the probability simplex. We use the conventions 0/0:=00/0:=0 and x/0:=+∞x/0:=+∞ for x>0x>0. Russo and Van Roy Russo and Van Roy [2014] show that this optimization problem is convex and admits an optimal solution with at most two nonzero components. Therefore, although IDS is a randomized policy, it suffices to randomize over at most two actions at each round. Function IDSAction(,Δ→t(t),g→t(t)A, _t(c_t), g_t(c_t)): if g→t(t)=0→ g_t(c_t)= 0 then return an action a∗∈arg⁡mina∈⁡Δt(a∣t)a^*∈ _a _t(a _t). For each pair a,a′∈a,a such that a≠a′a≠ a compute qa,a′←arg⁡minq∈[0,1]⁡(qΔt(a∣t)+(1−q)Δt(a′∣t))2qgt(a∣t)+(1−q)gt(a′∣t).q_a,a ← _q∈[0,1] (q\, _t(a _t)+(1-q)\, _t(a _t) )^2q\,g_t(a _t)+(1-q)\,g_t(a _t). Select (a∗,a∗)←arg⁡mina≠a′⁡(qa,a′Δt(a∣t)+(1−qa,a′)Δt(a′∣t))2qa,a′gt(a∣t)+(1−qa,a′)gt(a′∣t).(a^*,a^**)← _a≠ a (q_a,a \, _t(a _t)+(1-q_a,a )\, _t(a _t) )^2q_a,a \,g_t(a _t)+(1-q_a,a )\,g_t(a _t). return a∗a^* with probability qa∗,a∗q_a^*,a^** and a∗a^** with probability 1−qa∗,a∗1-q_a^*,a^**. End Function Algorithm 3 Function to optimize the contextual information ratio A.2 Proof of Theorem 1 [RegT]=[∑t=1T(YΠ⋆(t),t−YAt,t)]=[∑t=1Tt[YΠ⋆(t),t−YAt,t∣t]].E[Reg_T]=E\! [ _t=1^T (Y_ (C_t),t-Y_A_t,t ) ]=E\! [ _t=1^TE_t\! [Y_ (C_t),t-Y_A_t,t _t ] ]. (12) We introduce a nonnegative constant Γt _t such that the per-round regret satisfies t[YΠ⋆(t),t−YAt,t∣t]≤ΓtIt(Π⋆(t);(At,YAt,t)∣t).E_t\! [Y_ (C_t),t-Y_A_t,t _t ]≤ _t I_t\! ( (C_t);(A_t,Y_A_t,t) _t ). (13) Then, [RegT] [Reg_T] ≤[∑t=1TΓtIt(Π⋆(t);(At,YAt,t)∣t)] \! [ _t=1^T _t I_t\! ( (C_t);(A_t,Y_A_t,t) _t ) ] ≤Γ[∑t=1TIt(Π⋆(t);(At,YAt,t)∣t)] ≤ \,E\! [ _t=1^T I_t\! ( (C_t);(A_t,Y_A_t,t) _t ) ] ≤ΓT[∑t=1TIt(Π⋆(t);(At,YAt,t)∣t)]. ≤ T\,E\! [ _t=1^TI_t\! ( (C_t);(A_t,Y_A_t,t) _t ) ]. The second inequality follows from the assumption that Γ≥Γt ≥ _t for all t∈ℕt , and the third inequality follows from the Cauchy–Schwarz and Jensen inequalities. Since Π⋆(t) (C_t) is a deterministic function of the full optimal-action mapping Π⋆ , the data-processing inequality gives It(Π⋆(t);(At,YAt,t)∣t)≤It(Π⋆;(At,YAt,t)∣t).I_t\! ( (C_t);(A_t,Y_A_t,t) _t )≤ I_t\! ( ;(A_t,Y_A_t,t) _t ). (14) Let tO_t denote the complete observation collected at time t, including tC_t, AtA_t, YAt,tY_A_t,t, and all observed non-intervened variables, so that ℱt+1=σ(ℱt,t)F_t+1=σ(F_t,O_t). By the chain rule for mutual information, It(Π⋆;(At,YAt,t)∣t)≤It(Π⋆;t).I_t\! ( ;(A_t,Y_A_t,t) _t )≤ I_t\! ( ;O_t ). (15) By the definition of conditional mutual information, It(Π⋆;t)=H(Π⋆∣ℱt)−[H(Π⋆∣ℱt+1)∣ℱt].I_t\! ( ;O_t )=H\! ( _t )-E\! [H\! ( _t+1 ) _t ]. Summing over t yields a telescoping series: [∑t=1TIt(Π⋆(t);(At,YAt,t)∣t)]≤H(Π⋆)−[H(Π⋆∣ℱT+1)]≤H(Π⋆).E\! [ _t=1^TI_t\! ( (C_t);(A_t,Y_A_t,t) _t ) ]≤ H( )-E\! [H\! ( _T+1 ) ]≤ H( ). (16) Substituting this bound gives [RegT]≤ΓH(Π⋆)T.E[Reg_T]≤ H( )\,T. (17) This completes the proof of Theorem 1. A.3 Proof of Corollary 1 We fix a realization of ℱtF_t and condition on the realized context t=C_t=c. Write pa:=Pt(Π⋆()=a∣t=)p_a:=P_t( (c)=a _t=c). By the TS posterior-matching property, Pt(At=a∣t=)=paP_t(A_t=a _t=c)=p_a. Moreover, conditional on ℱtF_t and t=C_t=c, the action AtA_t and the optimal action Π⋆() (c) are independent because AtA_t is generated using an independent posterior sample. Also let K=||K=|A| be the total number of actions. Define the posterior mean reward of action a at context c: μ¯a:=Et[Ya,t∣t=]. μ_a:=E_t[Y_a,t _t=c]. Also define the posterior mean reward under the optimal action for that context: μ¯⋆:=Et[YΠ⋆(),t∣t=]=∑a∈paEt[Ya,t∣Π⋆()=a,t=]. μ :=E_t[Y_ (c),t _t=c]= _a p_a\,E_t[Y_a,t (c)=a,C_t=c]. Then the conditional instantaneous regret is Δt() _t(c) :=Et[YΠ⋆(),t−YAt,t∣t=] :=E_t\! [Y_ (c),t-Y_A_t,t _t=c ] =μ¯⋆−∑a∈Pt(At=a∣t=)μ¯a = μ - _a P_t(A_t=a _t=c)\, μ_a =∑a∈pa(Et[Ya,t∣Π⋆()=a,t=]−μ¯a). = _a p_a (E_t[Y_a,t (c)=a,C_t=c]- μ_a ). (18) Applying the Cauchy–Schwarz inequality gives Δt()2 _t(c)^2 ≤K∑a∈pa2(Et[Ya,t∣Π⋆()=a,t=]−μ¯a)2. ≤ K _a p_a^2 (E_t[Y_a,t (c)=a,C_t=c]- μ_a )^2. (19) Because rewards are Bernoulli, for each a the two distributions Pt(Ya,t∈⋅∣Π⋆()=a,t=)andPt(Ya,t∈⋅∣t=)P_t(Y_a,t∈· (c)=a,C_t=c) P_t(Y_a,t∈· _t=c) are distributions on 0,1\0,1\, and their total variation distance equals the absolute difference of their means: TV(Pt(Ya,t∣Π⋆()=a,t=),Pt(Ya,t∣t=))=|Et[Ya,t∣Π⋆()=a,t=]−μ¯a|.TV\! (P_t(Y_a,t (c)=a,C_t=c),\,P_t(Y_a,t _t=c) )= |E_t[Y_a,t (c)=a,C_t=c]- μ_a |. Applying Pinsker’s inequality for each a gives (Et[Ya,t∣Π⋆()=a,t=]−μ¯a)2 (E_t[Y_a,t (c)=a,C_t=c]- μ_a )^2 ≤12KL(Pt(Ya,t∣Π⋆()=a,t=)∥Pt(Ya,t∣t=)). ≤ 12KL\! (P_t(Y_a,t (c)=a,C_t=c)\ \|\ P_t(Y_a,t _t=c) ). (20) Plugging (20) into (19) yields Δt()2 _t(c)^2 ≤K2∑a∈pa2KL(Pt(Ya,t∣Π⋆()=a,t=)∥Pt(Ya,t∣t=)). ≤ K2 _a p_a^2\,KL\! (P_t(Y_a,t (c)=a,C_t=c)\ \|\ P_t(Y_a,t _t=c) ). (21) We now relate the right-hand side to the information obtained under Thompson Sampling. Since AtA_t and Π⋆() (c) are conditionally independent given ℱtF_t and t=C_t=c, we have It(Π⋆();(At,YAt,t)∣t=) I_t\! ( (c);(A_t,Y_A_t,t) _t=c ) =∑a∈paIt(Π⋆();Ya,t∣t=) = _a p_a\,I_t\! ( (c);Y_a,t _t=c ) =∑a∈∑a′∈papa′KL(Pt(Ya,t∣Π⋆()=a′,t=)∥Pt(Ya,t∣t=)) = _a _a p_ap_a \,KL\! (P_t(Y_a,t (c)=a ,C_t=c)\ \|\ P_t(Y_a,t _t=c) ) ≥∑a∈pa2KL(Pt(Ya,t∣Π⋆()=a,t=)∥Pt(Ya,t∣t=)). ≥ _a p_a^2\,KL\! (P_t(Y_a,t (c)=a,C_t=c)\ \|\ P_t(Y_a,t _t=c) ). (22) Combining (21) and (22) gives Δt()2≤K2It(Π⋆();(At,YAt,t)∣t=). _t(c)^2≤ K2I_t\! ( (c);(A_t,Y_A_t,t) _t=c ). Therefore, for every realized context c, Γt2≤K2, _t^2≤ K2, or equivalently, Γt≤K2=||2. _t≤ K2= |A|2. Thus, Γ=||2 = |A|2 is a valid upper bound on the information-ratio coefficient Γt _t for every time step t. Therefore, by Theorem 1, [RegT]≤ΓH(Π⋆)T=||2H(Π⋆)T.E[Reg_T]≤ H( )\,T= |A|2\,H( )\,T. (23) Moreover, since Π⋆ maps the context space C to the action space A, the total number of possible mappings is at most |||||A|^|C| when C is finite. This implies that the entropy is bounded as H(Π⋆)≤log⁡(||||)=||log⁡(||)H( )≤ \! (|A|^|C| )=|C| \! (|A| ). Consequently, [RegT]≤T||||log⁡||2.E[Reg_T]≤ T|A||C| |A|2. This completes the proof of Corollary 1. A.4 Proof of Lemma 2 We fix time step t and the realized context t=tC_t=c_t. We begin with the definition of the information gain: gt(a|t)=DKL(Pt(Π∗(t),Ya,t∣t)∥Pt(Π∗(t)∣t)Pt(Ya,t∣t)).g_t(a|c_t)=D_KL\! (P_t( ^*(c_t),Y_a,t _t)\, \|\,P_t( ^*(c_t) _t)P_t(Y_a,t _t) ). We compute each term separately. Posterior of Π∗(t) ^*(c_t). By definition, Pt(Π∗(t)=a∗∣t)=P(Π∗(t)=a∗∣ℱt,t=t).P_t( ^*(c_t)=a^* _t)=P( ^*(c_t)=a^* _t,C_t=c_t). Using the law of total expectation over θ, Pt(Π∗(t)=a∗∣t)=∼Pt(∣t)[P(Π∗(t)=a∗∣,t)].P_t( ^*(c_t)=a^* _t)=E_ θ P_t( θ _t) [P( ^*(c_t)=a^* θ,c_t) ]. Given θ and context tc_t, the optimal action is deterministic, hence P(Π∗(t)=a∗∣,t)=a∗=arg⁡maxa∈⁡[Ya,t∣,t].P( ^*(c_t)=a^* θ,c_t)= 1 \a^*= _a E[Y_a,t θ,c_t] \. Substituting, Pt(Π∗(t)=a∗∣t)=∼Pt(∣t)[a∗=arg⁡maxa∈⁡[Ya,t∣,t]].P_t( ^*(c_t)=a^* _t)=E_ θ P_t( θ _t) [ 1 \a^*= _a E[Y_a,t θ,c_t] \ ]. Posterior of YaY_a. By definition, Pt(Ya,t=y∣t)=P(Ya,t=y∣ℱt,t=t).P_t(Y_a,t=y _t)=P(Y_a,t=y _t,C_t=c_t). Conditioning on θ gives Pt(Ya,t=y∣t)=∼Pt(∣t)[P(Ya,t=y∣,t)].P_t(Y_a,t=y _t)=E_ θ P_t( θ _t) [P(Y_a,t=y θ,c_t) ]. Joint posterior. Using the law of total expectation, Pt(Π∗(t)=a∗,Ya,t=y∣t) P_t( ^*(c_t)=a^*,Y_a,t=y _t) =∼Pt(∣t)[P(Π∗(t)=a∗,Ya,t=y∣,t)]. =E_ θ P_t( θ _t) [P( ^*(c_t)=a^*,Y_a,t=y θ,c_t) ]. Since Π∗(t) ^*(c_t) is deterministic given θ and tc_t, we have Pt(Π∗(t)=a∗,Ya,t=y∣t) P_t( ^*(c_t)=a^*,Y_a,t=y _t) =∼Pt(∣t)[P(Π∗(t)=a∗∣,t) =E_ θ P_t( θ _t) [P( ^*(c_t)=a^* θ,c_t) ×P(Ya,t=y∣,t)]. × P(Y_a,t=y θ,c_t) ]. Substituting the indicator representation, Pt(Π∗(t)=a∗,Ya,t=y∣t)=∼Pt(∣t)[a∗=argmaxa∈[Ya,t∣,t] P_t( ^*(c_t)=a^*,Y_a,t=y _t)=E_ θ P_t( θ _t) [ 1\a^*= _a E[Y_a,t θ,c_t]\ ×P(Ya,t=y∣,t)]. × P(Y_a,t=y θ,c_t) ]. This establishes the expressions used in the KL divergence. Expected instantaneous regret. By definition, Δt(a|t)=[YΠ∗(t),t−Ya,t∣t=t,ℱt]. _t(a|c_t)=E\! [Y_ ^*(c_t),t-Y_a,t _t=c_t,F_t ]. Using the law of total expectation over θ, Δt(a|t)=∼Pt(∣t)[[YΠ∗(t),t−Ya,t∣,t]]. _t(a|c_t)=E_ θ P_t( θ _t) [E\! [Y_ ^*(c_t),t-Y_a,t θ,c_t ] ]. Expanding the first term gives [YΠ∗(t),t∣,t] [Y_ ^*(c_t),t θ,c_t] =∑a∗∈a∗=arg⁡maxa∈⁡[Ya,t∣,t] = _a^* 1 \a^*= _a E[Y_a,t θ,c_t] \ ×P(Ya∗,t=1∣,t). × P(Y_a^*,t=1 θ,c_t). Also, since the rewards are Bernoulli, [Ya,t∣,t]=P(Ya,t=1∣,t).E[Y_a,t θ,c_t]=P(Y_a,t=1 θ,c_t). Substituting both expressions, Δt(a|t)=∼Pt(∣t)[∑a∗∈a∗=argmaxa∈[Ya,t∣,t] _t(a|c_t)=E_ θ P_t( θ _t) [ _a^* 1 \a^*= _a E[Y_a,t θ,c_t] \ ×P(Ya∗,t=1∣,t)−P(Ya,t=1∣,t)]. × P(Y_a^*,t=1 θ,c_t)-P(Y_a,t=1 θ,c_t) ]. This completes the proof of Lemma 2. A.5 Proof of Lemma 3 Fix time step t and the realized context t=tC_t=c_t. From Lemma 2, define f():=∑a∗∈a∗=arg⁡maxa∈⁡[Ya,t∣,t]P(Ya∗,t=1∣,t)−P(Ya,t=1∣,t).f( θ):= _a^* 1\! \a^*= _a E[Y_a,t θ,c_t] \P(Y_a^*,t=1 θ,c_t)-P(Y_a,t=1 θ,c_t). Then Δt(a∣t)=∼Pt(∣t)[f()]. _t(a _t)=E_ θ P_t( θ _t)\! [f( θ) ]. Let 1,…,N θ_1,…, θ_N be i.i.d. samples from Pt(∣t)P_t( θ _t), and define the Monte Carlo estimator Δ^t(a∣t)=1N∑i=1Nf(i). _t(a _t)= 1N _i=1^Nf( θ_i). We now bound the range of f()f( θ). For any fixed θ, exactly one term in the indicator sum equals 11 because ties are broken deterministically. Hence, ∑a∗∈⋯P(Ya∗,t=1∣,t)=P(YΠ∗(t),t=1∣,t). _a^* 1\·s\\,P(Y_a^*,t=1 θ,c_t)=P\! (Y_ ^*(c_t),t=1 θ,c_t ). Because Π∗(t) ^*(c_t) maximizes the expected reward under θ and tc_t, P(YΠ∗(t),t=1∣,t)≥P(Ya,t=1∣,t).P\! (Y_ ^*(c_t),t=1 θ,c_t )≥ P(Y_a,t=1 θ,c_t). Since both probabilities belong to [0,1][0,1], it follows that 0≤f()≤1.0≤ f( θ)≤ 1. Define Xi:=f(i)X_i:=f( θ_i). Then X1,…,XNX_1,…,X_N are independent and satisfy 0≤Xi≤10≤ X_i≤ 1 almost surely, and [Xi]=Δt(a∣t),1N∑i=1NXi=Δ^t(a∣t).E[X_i]= _t(a _t), 1N _i=1^NX_i= _t(a _t). Applying Hoeffding’s inequality to the sample mean of bounded variables yields, for any ϵ>0ε>0, ℙ(|Δ^t(a∣t)−Δt(a∣t)|≥ϵ)≤2exp(−2Nϵ2).P\! ( | _t(a _t)- _t(a _t) |≥ε )≤ 2 \! (-2Nε^2 ). Setting the right-hand side equal to δ, i.e., δ=2exp⁡(−2Nϵ2),δ=2 \! (-2Nε^2 ), gives ϵ=12Nlog⁡(2δ).ε= 12N \! ( 2δ ). Therefore, with probability at least 1−δ1-δ, |Δ^t(a∣t)−Δt(a∣t)|≤12Nlog⁡(2δ)≤2Nlog⁡(2δ). | _t(a _t)- _t(a _t) |≤ 12N \! ( 2δ )≤ 2N \! ( 2δ ). Hence, ℙ(|Δ^t(a∣t)−Δt(a∣t)|≤2Nlog⁡(2δ))≥1−δ.P\! ( | _t(a _t)- _t(a _t) |≤ 2N \! ( 2δ ) )≥ 1-δ. This completes the proof of Lemma 3. A.6 Concentration of the Information Gain Proof of Lemma 4. Fix a time step t and condition on the realized context t=tC_t=c_t. Throughout this section, ties in the definition of the optimal action are resolved using a fixed deterministic tie-breaking rule. We use Pt(∣t)P_t( θ _t) as shorthand for P(∣ℱt,t=t)P( θ _t,C_t=c_t). For each action a∈a , define pta(a∗,y) p_t^a(a^*,y) :=Pt(Π∗(t)=a∗,Ya,t=y∣t), :=P_t\! ( ^*(c_t)=a^*,Y_a,t=y _t ), pt⋆(a∗) p_t (a^*) :=Pt(Π∗(t)=a∗∣t), :=P_t\! ( ^*(c_t)=a^* _t ), pta(y) p_t^a(y) :=Pt(Ya,t=y∣t), :=P_t\! (Y_a,t=y _t ), for a∗∈a^* and y∈0,1y∈\0,1\. By Lemma 2, the joint posterior probability satisfies pta(a∗,y)=∼Pt(∣t)[a∗=arg⁡maxa′∈⁡[Ya′,t∣,t]P(Ya,t=y∣,t)].p_t^a(a^*,y)=E_ θ P_t( θ _t) [ 1\! \a^*= _a E [Y_a ,t θ,c_t ] \P\! (Y_a,t=y θ,c_t ) ]. (24) Let (1),…,(N) θ^(1),…, θ^(N) be N independent samples from Pt(∣t)P_t( θ _t), and define ai∗:=arg⁡maxa′∈⁡[Ya′,t∣(i),t].a_i^*:= _a E [Y_a ,t θ^(i),c_t ]. The corresponding Monte Carlo estimators are p^ta(a∗,y) p_t^a(a^*,y) :=1N∑i=1Nai∗=a∗P(Ya,t=y∣(i),t), := 1N _i=1^N 1\a_i^*=a^*\P\! (Y_a,t=y θ^(i),c_t ), (25) p^t⋆(a∗) p_t (a^*) :=1N∑i=1Nai∗=a∗, := 1N _i=1^N 1\a_i^*=a^*\, (26) p^ta(y) p_t^a(y) :=1N∑i=1NP(Ya,t=y∣(i),t). := 1N _i=1^NP\! (Y_a,t=y θ^(i),c_t ). (27) Define the confidence radii ϵ1(N,δ) _1(N,δ) :=12Nlog⁡(12||2δ), = 12N \! ( 12|A|^2δ ), (28) ϵ2(N,δ) _2(N,δ) :=12Nlog⁡(6||δ), = 12N \! ( 6|A|δ ), ϵ3(N,δ) _3(N,δ) :=12Nlog⁡(12||δ). = 12N \! ( 12|A|δ ). Concentration of the posterior probabilities. The summands in (25) lie in [0,1][0,1]. Therefore, for any ε>0 >0, Hoeffding’s inequality gives ℙ(|p^ta(a∗,y)−pta(a∗,y)|≥ε)≤2exp⁡(−2Nε2).P\! ( | p_t^a(a^*,y)-p_t^a(a^*,y) |≥ )≤ 2 (-2N ^2). Applying a union bound over all a,a∗∈a,a^* and y∈0,1y∈\0,1\ gives, with probability at least 1−δ/31-δ/3, |p^ta(a∗,y)−pta(a∗,y)|≤ϵ1(N,δ),∀a,a∗∈,y∈0,1. | p_t^a(a^*,y)-p_t^a(a^*,y) |≤ _1(N,δ), ∀ a,a^* , y∈\0,1\. (29) Similarly, applying Hoeffding’s inequality and a union bound over a∗∈a^* gives, with probability at least 1−δ/31-δ/3, |p^t⋆(a∗)−pt⋆(a∗)|≤ϵ2(N,δ),∀a∗∈. | p_t (a^*)-p_t (a^*) |≤ _2(N,δ), ∀ a^* . (30) Finally, applying Hoeffding’s inequality and a union bound over a∈a and y∈0,1y∈\0,1\ gives, with probability at least 1−δ/31-δ/3, |p^ta(y)−pta(y)|≤ϵ3(N,δ),∀a∈,y∈0,1. | p_t^a(y)-p_t^a(y) |≤ _3(N,δ), ∀ a , y∈\0,1\. (31) Combining (29), (30), and (31) with a union bound shows that all three concentration events hold simultaneously with probability at least 1−δ1-δ. For notational convenience, define L1,ta(a∗,y) L_1,t^a(a^*,y) :=max⁡0,p^ta(a∗,y)−ϵ1, := \! \0, p_t^a(a^*,y)- _1 \, U1,ta(a∗,y) U_1,t^a(a^*,y) :=min⁡1,p^ta(a∗,y)+ϵ1, := \! \1, p_t^a(a^*,y)+ _1 \, L2,t(a∗) L_2,t(a^*) :=max⁡0,p^t⋆(a∗)−ϵ2, := \! \0, p_t (a^*)- _2 \, U2,t(a∗) U_2,t(a^*) :=min⁡1,p^t⋆(a∗)+ϵ2, := \! \1, p_t (a^*)+ _2 \, L3,ta(y) L_3,t^a(y) :=max⁡0,p^ta(y)−ϵ3, := \! \0, p_t^a(y)- _3 \, U3,ta(y) U_3,t^a(y) :=min⁡1,p^ta(y)+ϵ3, := \! \1, p_t^a(y)+ _3 \, where ϵi=ϵi(N,δ) _i= _i(N,δ) for i∈1,2,3i∈\1,2,3\. Upper confidence bound. The contextual information gain can be written as gt(a∣t)=DKL(pta∥pt⋆pta),g_t(a _t)=D_KL (p_t^a\, \|\,p_t p_t^a ), (32) where (pt⋆pta)(a∗,y)=pt⋆(a∗)pta(y). (p_t p_t^a )(a^*,y)=p_t (a^*)p_t^a(y). Using DKL(P∥Q)≤χ2(P∥Q)=∑xP(x)2Q(x)−1,D_KL(P\|Q)≤χ^2(P\|Q)= _x P(x)^2Q(x)-1, together with the concentration bounds above, define g¯t(a∣t):=min⁡log⁡2,max⁡0,∑a∗∈y∈0,1(U1,ta(a∗,y))2L2,t(a∗)L3,ta(y)−1. g_t(a _t):= \! \ 2,\, \! \0,\, _ subarrayca^* \\ y∈\0,1\ subarray (U_1,t^a(a^*,y) )^2L_2,t(a^*)L_3,t^a(y)-1 \ \. (33) Whenever L2,t(a∗)L3,ta(y)=0L_2,t(a^*)L_3,t^a(y)=0, the corresponding ratio in (33) is interpreted as +∞+∞. The additional bound by log⁡2 2 follows from gt(a∣t)=It(Π∗(t);Ya,t∣t)≤Ht(Ya,t∣t)≤log⁡2.g_t(a _t)=I_t\! ( ^*(c_t);Y_a,t _t )≤ H_t(Y_a,t _t)≤ 2. Consequently, on the joint concentration event, gt(a∣t)≤g¯t(a∣t),∀a∈.g_t(a _t)≤ g_t(a _t), ∀ a . (34) Lower confidence bound. Because the KL divergence is jointly convex in its two arguments, a lower confidence bound is obtained from the following convex program: g¯t(a∣t):=minimizeP,Q g_t(a _t)= P,Qminimize DKL(P∥Q) D_KL(P\|Q) (35) subject to L1,ta(a∗,y)≤P(a∗,y)≤U1,ta(a∗,y), L_1,t^a(a^*,y)≤ P(a^*,y)≤ U_1,t^a(a^*,y), ∀a∗∈,y∈0,1, 133.72786pt∀ a^* , y∈\0,1\, L2,t(a∗)L3,ta(y)≤Q(a∗,y)≤U2,t(a∗)U3,ta(y), L_2,t(a^*)L_3,t^a(y)≤ Q(a^*,y)≤ U_2,t(a^*)U_3,t^a(y), ∀a∗∈,y∈0,1, 133.72786pt∀ a^* , y∈\0,1\, ∑a∗∈y∈0,1P(a∗,y)=1, _ subarrayca^* \\ y∈\0,1\ subarrayP(a^*,y)=1, ∑a∗∈y∈0,1Q(a∗,y)=1, _ subarrayca^* \\ y∈\0,1\ subarrayQ(a^*,y)=1, P(a∗,y)≥0,Q(a∗,y)≥0, P(a^*,y)≥ 0, Q(a^*,y)≥ 0, ∀a∗∈,y∈0,1. 133.72786pt∀ a^* , y∈\0,1\. The KL divergence in (35) is understood in the extended-value sense, with 0log⁡(0/q)=00 (0/q)=0 and plog⁡(p/0)=+∞p (p/0)=+∞ for p>0p>0. On the joint concentration event, the true distributions P(a∗,y)=pta(a∗,y)P(a^*,y)=p_t^a(a^*,y) and Q(a∗,y)=pt⋆(a∗)pta(y)Q(a^*,y)=p_t (a^*)p_t^a(y) are feasible for (35). Therefore, the optimal value of the program satisfies g¯t(a∣t)≤gt(a∣t),∀a∈. g_t(a _t)≤ g_t(a _t), ∀ a . (36) Combining (34) and (36), we conclude that, with probability at least 1−δ1-δ, g¯t(a∣t)≤gt(a∣t)≤g¯t(a∣t),∀a∈. g_t(a _t)≤ g_t(a _t)≤ g_t(a _t), ∀ a . The numerical solution of (35) is described in Section A.7. ∎ A.7 KL Divergence Minimization under Box Constraints We fix time step t, context t=tC_t=c_t, and an action a∈a . We consider the problem of minimizing the Kullback–Leibler (KL) divergence between two discrete distributions under the box and normalization constraints induced by the high-probability confidence intervals. Recall that the contextual information gain is defined as gt(a∣t)=DKL(Pt(Π∗(t),Ya,t∣t)∥Pt(Π∗(t)∣t)Pt(Ya,t∣t)).g_t(a _t)=D_KL\! (P_t( ^*(c_t),Y_a,t _t)\; \|\;P_t( ^*(c_t) _t)P_t(Y_a,t _t) ). To obtain a lower bound on gt(a∣t)g_t(a _t), we solve the following constrained optimization problem over probability distributions P and Q: minimize DKL(P∥Q) D_KL(P\,\|\,Q) subject to L1,ta(a∗,y)≤P(a∗,y)≤U1,ta(a∗,y), L_1,t^a(a^*,y)≤ P(a^*,y)≤ U_1,t^a(a^*,y), ∀a∗∈,y∈0,1, 50.00008pt∀ a^* ,\,y∈\0,1\, L2,t(a∗)L3,ta(y)≤Q(a∗,y)≤U2,t(a∗)U3,ta(y), L_2,t(a^*)L_3,t^a(y)≤ Q(a^*,y)≤ U_2,t(a^*)U_3,t^a(y), ∀a∗∈,y∈0,1, 50.00008pt∀ a^* ,\,y∈\0,1\, ∑a∗∈,y∈0,1P(a∗,y)=1,∑a∗∈,y∈0,1Q(a∗,y)=1, _a^* ,\;y∈\0,1\P(a^*,y)=1, _a^* ,\;y∈\0,1\Q(a^*,y)=1, P(a∗,y)≥0,Q(a∗,y)≥0,∀a∗∈,y∈0,1. P(a^*,y)≥ 0, Q(a^*,y)≥ 0, ∀ a^* ,\,y∈\0,1\. Here, the confidence radii are ϵ1(N,δ)=12Nlog⁡(12||2δ), _1(N,δ)= 12N \! ( 12|A|^2δ ), ϵ2(N,δ)=12Nlog⁡(6||δ), _2(N,δ)= 12N \! ( 6|A|δ ), ϵ3(N,δ)=12Nlog⁡(12||δ). _3(N,δ)= 12N \! ( 12|A|δ ). The KL divergence is jointly convex in P and Q, and all the constraints above are linear. Therefore, the optimization problem is a convex program, and every locally optimal solution is globally optimal. We solve this program using a standard convex optimization solver that supports the relative-entropy function. In particular, the objective is represented as DKL(P∥Q)=∑a∗∈,y∈0,1rel_entr⁡(P(a∗,y),Q(a∗,y)),D_KL(P\|Q)= _a^* ,\;y∈\0,1\rel\_entr\! (P(a^*,y),Q(a^*,y) ), where rel_entr⁡(p,q)=plog⁡(pq)rel\_entr(p,q)=p \! ( pq ) is interpreted in the extended-value sense. The box, nonnegativity, and normalization constraints are supplied directly to the solver. If a feasible initialization is required, one can project the midpoint of each box onto the corresponding bounded probability simplex. For bounds Li≤xi≤UiL_i≤ x_i≤ U_i, the Euclidean projection of a vector z onto the bounded simplex has the form xi=min⁡Ui,max⁡Li,zi−λ,x_i= \! \U_i, \! \L_i,z_i-λ \ \, where λ is chosen so that ∑ixi=1 _ix_i=1. The value of λ can be found efficiently by bisection. Unlike independently clamping and then renormalizing the coordinates, this projection satisfies the box and normalization constraints simultaneously. The convex program is solved separately for every a∈a , and its optimal value is used as g¯t(a∣t) g_t(a _t). A.8 Proof of Theorem 2 (Contextual Case) Fix a horizon T∈ℕT and a realized context sequence 1:T=(1,…,T)=(1,…,T).C_1:T=(C_1,…,C_T)=(c_1,…,c_T). For notational convenience, write 1:T[⋅]:=[⋅|1:T=1:T].E_c_1:T[·]:=E\! [\,·\, |C_1:T=c_1:T ]. For every π∈S||π∈ S_|A|, define Δt(π∣t) _t(π _t) :=∑a∈π(a)Δt(a∣t), := _a π(a) _t(a _t), (37) gt(π∣t) g_t(π _t) :=∑a∈π(a)gt(a∣t), := _a π(a)g_t(a _t), (38) where Δt(a∣t) _t(a _t) :=t[YΠ⋆(t),t−Ya,t|t=t], :=E_t\! [Y_ (c_t),t-Y_a,t |C_t=c_t ], (39) gt(a∣t) g_t(a _t) :=It(Π⋆(t);Ya,t|t=t). :=I_t\! ( (c_t);Y_a,t |C_t=c_t ). (40) The corresponding information ratio is Ψt(π∣t):=Δt(π∣t)2gt(π∣t). _t(π _t):= _t(π _t)^2g_t(π _t). (41) Let πt∘(t)∈arg⁡minπ∈S||⁡Ψt(π∣t) _t (c_t)∈ _π∈ S_|A| _t(π _t) (42) denote the oracle IDS distribution, and let π^t(t) π_t(c_t) denote the distribution selected by Algorithm 2 using the confidence sets. Step 1: Regret decomposition. By the tower property, 1:T[∑t=1T(YΠ⋆(t),t−YAt,t)] _c_1:T\! [ _t=1^T (Y_ (C_t),t-Y_A_t,t ) ] =1:T[∑t=1TΔt(π^t∣t)]. =E_c_1:T\! [ _t=1^T _t( π_t _t) ]. (43) Using Δt(π^t∣t)=Ψt(π^t∣t)gt(π^t∣t), _t( π_t _t)= _t( π_t _t) g_t( π_t _t), followed by Cauchy–Schwarz and Jensen’s inequality, gives 1:T[∑t=1T(YΠ⋆(t),t−YAt,t)] _c_1:T\! [ _t=1^T (Y_ (C_t),t-Y_A_t,t ) ] ≤1:T[∑t=1TΨt(π^t∣t)]1:T[∑t=1Tgt(π^t∣t)]. ≤ E_c_1:T\! [ _t=1^T _t( π_t _t) ] E_c_1:T\! [ _t=1^Tg_t( π_t _t) ]. (44) Step 2: Bounding the cumulative information gain. Let Zt:=Π⋆(t).Z_t:= (c_t). Since ZtZ_t is a deterministic function of the random policy Π⋆ , the data-processing inequality gives It(Zt;Ya,t|t=t)≤It(Π⋆;Ya,t|t=t).I_t\! (Z_t;Y_a,t |C_t=c_t )≤ I_t\! ( ;Y_a,t |C_t=c_t ). (45) Consequently, gt(π^t∣t) g_t( π_t _t) =∑a∈π^t(a∣t)It(Zt;Ya,t|t=t) = _a π_t(a _t)I_t\! (Z_t;Y_a,t |C_t=c_t ) ≤It(Π⋆;YAt,t|At,t=t). ≤ I_t\! ( ;Y_A_t,t |A_t,C_t=c_t ). (46) Conditional on the history ℱtF_t and the observed context, the randomization used to generate AtA_t is independent of Π⋆ . Therefore, I(Π⋆;At|ℱt,1:T=1:T)=0.I\! ( ;A_t |F_t,C_1:T=c_1:T )=0. It follows from the chain rule for mutual information that 1:T[∑t=1Tgt(π^t∣t)] _c_1:T\! [ _t=1^Tg_t( π_t _t) ] ≤∑t=1TI(Π⋆;At,YAt,t|ℱt,1:T=1:T) ≤ _t=1^TI\! ( ;A_t,Y_A_t,t |F_t,C_1:T=c_1:T ) =I(Π⋆;ℱT+1|1:T=1:T) =I\! ( ;F_T+1 |C_1:T=c_1:T ) ≤H(Π⋆|1:T=1:T)≤H(Π⋆). ≤ H\! ( |C_1:T=c_1:T )≤ H( ). (47) Substituting (47) into (44) yields 1:T[∑t=1T(YΠ⋆(t),t−YAt,t)] _c_1:T\! [ _t=1^T (Y_ (C_t),t-Y_A_t,t ) ] ≤H(Π⋆)1:T[∑t=1TΨt(π^t∣t)]. ≤ H( )\,E_c_1:T\! [ _t=1^T _t( π_t _t) ]. (48) Step 3: Oracle information-ratio bound. Fix t and let pt(a∣t):=Pt(Π⋆(t)=a|t=t).p_t(a _t):=P_t\! ( (c_t)=a |C_t=c_t ). (49) Consider the Thompson-sampling distribution πtTS(a∣t)=pt(a∣t). _t^TS(a _t)=p_t(a _t). Because πt∘ _t minimizes the true information ratio, Ψt(πt∘∣t)≤Ψt(πtTS∣t). _t( _t _t)≤ _t( _t^TS _t). (50) For a,b∈a,b , let μt,a _t,a :=t[Ya,t|t=t], :=E_t\! [Y_a,t |C_t=c_t ], (51) μt,a∣b _t,a b :=t[Ya,t|Π⋆(t)=b,t=t]. :=E_t\! [Y_a,t | (c_t)=b,C_t=c_t ]. (52) Posterior matching gives Δt(πtTS∣t)=∑a∈pt(a∣t)(μt,a∣a−μt,a). _t( _t^TS _t)= _a p_t(a _t) ( _t,a a- _t,a ). (53) Hence, Δt(πtTS∣t)2 _t( _t^TS _t)^2 ≤||∑a∈pt(a∣t)2(μt,a∣a−μt,a)2. ≤|A| _a p_t(a _t)^2 ( _t,a a- _t,a )^2. (54) Since the rewards are Bernoulli, Pinsker’s inequality implies (μt,a∣a−μt,a)2 ( _t,a a- _t,a )^2 ≤12DKL(Pt(Ya,t∣Π⋆(t)=a,t)∥Pt(Ya,t∣t)). ≤ 12D_KL\! (P_t(Y_a,t (c_t)=a,c_t) \|P_t(Y_a,t _t) ). (55) Therefore, Δt(πtTS∣t)2 _t( _t^TS _t)^2 ≤||2∑a∈pt(a∣t)2DKL(Pt(Ya,t∣Π⋆(t)=a,t)∥Pt(Ya,t∣t)). ≤ |A|2 _a p_t(a _t)^2D_KL\! (P_t(Y_a,t (c_t)=a,c_t) \|P_t(Y_a,t _t) ). (56) On the other hand, gt(πtTS∣t) g_t( _t^TS _t) =∑a∈pt(a∣t)It(Π⋆(t);Ya,t|t=t) = _a p_t(a _t)I_t\! ( (c_t);Y_a,t |C_t=c_t ) =∑a∈∑b∈pt(a∣t)pt(b∣t) = _a _b p_t(a _t)p_t(b _t) ×DKL(Pt(Ya,t∣Π⋆(t)=b,t)∥Pt(Ya,t∣t)). × D_KL\! (P_t(Y_a,t (c_t)=b,c_t) \|P_t(Y_a,t _t) ). (57) Every term in (57) is nonnegative. Keeping only the diagonal terms b=ab=a gives gt(πtTS∣t) g_t( _t^TS _t) ≥∑a∈pt(a∣t)2DKL(Pt(Ya,t∣Π⋆(t)=a,t)∥Pt(Ya,t∣t)). ≥ _a p_t(a _t)^2D_KL\! (P_t(Y_a,t (c_t)=a,c_t) \|P_t(Y_a,t _t) ). (58) Combining (56) and (58) yields Δt(πtTS∣t)2≤||2gt(πtTS∣t). _t( _t^TS _t)^2≤ |A|2g_t( _t^TS _t). Thus, Ψt(πt∘∣t)≤Ψt(πtTS∣t)≤||2. _t( _t _t)≤ _t( _t^TS _t)≤ |A|2. (59) Step 4: Confidence sets and Algorithm 2. For vectors ∈ℝ|| ^|A| and ∈ℝ+|| g ^|A|_+, define Ft(π;,):=(π⊤)2π⊤.F_t(π; , g):= (π )^2π g. (60) At time t, Algorithm 2 selects vectors ~t(t)∈tΔ(t)and~t(t)∈tg(t) _t(c_t) _t(c_t) g_t(c_t) ^g_t(c_t) by selecting one value from each corresponding confidence interval. Define the information ratio computed from these selected values as Ψ^t(π∣t):=Ft(π;~t(t),~t(t)). _t(π _t):=F_t\! (π; _t(c_t), g_t(c_t) ). (61) Algorithm 2 then selects π^t(t)∈arg⁡minπ∈S||⁡Ψ^t(π∣t). π_t(c_t)∈ _π∈ S_|A| _t(π _t). (62) Let ℰE be the event on which, simultaneously for every t≤Tt≤ T and every a∈a , Δt(a∣t)∈t,aΔ(t)andgt(a∣t)∈t,ag(t). _t(a _t) _t,a(c_t) g_t(a _t) ^g_t,a(c_t). Using δ=δ′2T||δ= δ 2T|A| in Lemmas 3 and 4, and applying a union bound over the time steps, actions, and the two concentration results, gives ℙ(ℰ)≥1−δ′.P(E)≥ 1-δ . (63) For each time step t, define γt:=supπ∈S||,t 1(t),t 2(t)∈tΔ(t),t 1(t),t 2(t)∈tg(t)|(π⊤t 1(t))2π⊤t 1(t)−(π⊤t 2(t))2π⊤t 2(t)|. _t:= _ subarraycπ∈ S_|A|,\\ _t^\,1(c_t), _t^\,2(c_t) _t(c_t),\\ g_t^\,1(c_t), g_t^\,2(c_t) ^g_t(c_t) subarray | (π _t^\,1(c_t) )^2π g_t^\,1(c_t)- (π _t^\,2(c_t) )^2π g_t^\,2(c_t) |. (64) The ratios in (64) are interpreted using the conventions 0/0:=00/0:=0 and x/0:=+∞x/0:=+∞ for every x>0x>0. On ℰE, the true vectors t(t) _t(c_t) and t(t) g_t(c_t) belong to their respective confidence sets. By construction, the vectors ~t(t) _t(c_t) and ~t(t) g_t(c_t) selected by Algorithm 2 also belong to these confidence sets. Consequently, in (64), we may choose t 1(t)=t(t),t 1(t)=t(t), _t^\,1(c_t)= _t(c_t), g_t^\,1(c_t)= g_t(c_t), and t 2(t)=~t(t),t 2(t)=~t(t). _t^\,2(c_t)= _t(c_t), g_t^\,2(c_t)= g_t(c_t). Therefore, |Ψt(π∣t)−Ψ^t(π∣t)|≤γtfor every π∈S||. | _t(π _t)- _t(π _t) |≤ _t every π∈ S_|A|. (65) Using (62), (65), and the optimality of πt∘ _t , we obtain Ψt(π^t∣t) _t( π_t _t) ≤Ψ^t(π^t∣t)+γt ≤ _t( π_t _t)+ _t ≤Ψ^t(πt∘∣t)+γt ≤ _t( _t _t)+ _t ≤Ψt(πt∘∣t)+2γt ≤ _t( _t _t)+2 _t ≤||2+2γt. ≤ |A|2+2 _t. (66) Step 5: Final bound. On the event ℰE, substituting (66) into (48) gives [∑t=1T(YΠ⋆(t),t−YAt,t)|tt=1T] \! [ . _t=1^T (Y_ (C_t),t-Y_A_t,t )\, |\,\C_t\_t=1^T ] ≤H(Π⋆)(T||2+2∑t=1Tγt). ≤ H( ) ( T|A|2+2 _t=1^T _t ). (67) Since ℙ(ℰ)≥1−δ′P(E)≥ 1-δ , the claimed bound holds with probability at least 1−δ′1-δ . This completes the proof. A.9 Application to a Causal Graph Motivated by a Real-World Scenario HealthHealthRecoveryRecoveryTreatmentTreatmentDietDietLifestyleLifestyle (a) Causal graph. (b) Cumulative regret. Figure 5: Experimental results for a causal graph motivated by a real-world healthcare scenario. To demonstrate the applicability of our proposed algorithms to practical settings, we consider a causal graph motivated by a real-world healthcare scenario. The graph is illustrated in Figure 5(a). The red nodes, LifestyleLifestyle and HealthHealth, represent non-manipulable variables, while RecoveryRecovery is the outcome variable of interest. The manipulable variables DietDiet and TreatmentTreatment constitute the candidate intervention arms. We assume that all variables take values in finite discrete domains. We then apply our proposed algorithm, together with the considered baseline methods, to the resulting causal bandit problem. The cumulative regret of the different methods is shown in Figure 5(b). A.10 Sampling Erdős–Rényi Random Chordal Graphs To generate connected moral directed acyclic graphs (DAGs), we use a modified Erdős–Rényi sampling procedure. A moral DAG is a DAG whose completed partially directed acyclic graph (CPDAG) consists of a single chain component. Restricting attention to moral DAGs simplifies the orientation procedure while providing a useful setting that can later be extended to more general DAG structures. We begin by sampling a uniformly random ordering of the vertices, denoted by σ. For the n-th vertex in this ordering, we sample its in-degree according to Xn=max⁡1,Bin⁡(n−1,ρ),X_n= \1,\,Bin(n-1,ρ) \, where Bin⁡(n−1,ρ)Bin(n-1,ρ) denotes a binomial random variable with parameters n−1n-1 and ρ. We then select XnX_n parents uniformly at random from the vertices that precede the n-th vertex in the ordering σ. The use of at least one parent for every vertex after the first ensures that the resulting graph is connected. To ensure chordality, we apply the elimination procedure described by Koller and Friedman [2009], using the reverse of σ as the elimination ordering. This construction follows the methodology adopted in prior work [Squires et al., 2020]. After generating the DAG structure, we independently sample conditional probability tables (CPTs) for all variables in a manner consistent with the parent sets of the sampled graph.

Instant research discovery