Information-Directed Sampling for Causal Bandits

# Information-Directed Sampling for Causal Bandits
Source: [https://arxiv.org/html/2607.15577](https://arxiv.org/html/2607.15577)
Murat Kocaoglu2Mahsa Ghasemi1 School of Electrical and Computer EngineeringPurdue University1 School of Computer ScienceJohns 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\.

## 1Introduction

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 rewardsLattimore and Szepesvári \([2020](https://arxiv.org/html/2607.15577#bib.bib55)\); Slivkins and others \([2019](https://arxiv.org/html/2607.15577#bib.bib56)\); Vermorel and Mohri \([2005](https://arxiv.org/html/2607.15577#bib.bib57)\)\. 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 oftenGarivier and Cappé \([2011](https://arxiv.org/html/2607.15577#bib.bib44)\); Jamieson and Nowak \([2014](https://arxiv.org/html/2607.15577#bib.bib58)\); Jamiesonet al\.\([2014](https://arxiv.org/html/2607.15577#bib.bib39)\)\.

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 explorationSchulzet al\.\([2020](https://arxiv.org/html/2607.15577#bib.bib38)\); Jun and Zhang \([2020](https://arxiv.org/html/2607.15577#bib.bib37)\); Tirinzoniet al\.\([2020](https://arxiv.org/html/2607.15577#bib.bib36)\); Van Parys and Golrezaei \([2024](https://arxiv.org/html/2607.15577#bib.bib60)\); Wanet al\.\([2023](https://arxiv.org/html/2607.15577#bib.bib61)\); Mersereauet al\.\([2009](https://arxiv.org/html/2607.15577#bib.bib62)\)\. 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 modelLattimoreet al\.\([2016](https://arxiv.org/html/2607.15577#bib.bib25)\); Senet al\.\([2017](https://arxiv.org/html/2607.15577#bib.bib46)\); Lee and Bareinboim \([2018](https://arxiv.org/html/2607.15577#bib.bib26)\); Weiet al\.\([2024](https://arxiv.org/html/2607.15577#bib.bib50)\); Qasim Elahiet al\.\([2024](https://arxiv.org/html/2607.15577#bib.bib43)\)\. In this setting, each action corresponds to an intervention on the causal system, and the resulting observations are generated according to a shared causal modelPearl \([2009](https://arxiv.org/html/2607.15577#bib.bib33)\)\. 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 interventionsLattimoreet al\.\([2016](https://arxiv.org/html/2607.15577#bib.bib25)\); Senet al\.\([2017](https://arxiv.org/html/2607.15577#bib.bib46)\); Yabeet al\.\([2018](https://arxiv.org/html/2607.15577#bib.bib49)\); Lee and Bareinboim \([2018](https://arxiv.org/html/2607.15577#bib.bib26)\)\.

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 BareinboimLee and Bareinboim \([2019](https://arxiv.org/html/2607.15577#bib.bib52)\)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 generalizedz2z^\{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 ofRusso and Van Roy \([2016](https://arxiv.org/html/2607.15577#bib.bib54),[2014](https://arxiv.org/html/2607.15577#bib.bib59)\), we represent uncertainty about the causal system using a random parameter𝜽\\boldsymbol\{\\theta\}\. 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𝜽\\boldsymbol\{\\theta\}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\.

## 2Preliminaries

We adopt the Structural Causal Model \(SCM\) frameworkPearl \([2009](https://arxiv.org/html/2607.15577#bib.bib33)\)\. An SCM, denoted byℳ\\mathcal\{M\}, is defined as a 4\-tuple⟨𝐔,𝐕,𝐅,P​\(𝐔\)⟩\\langle\\mathbf\{U\},\\mathbf\{V\},\\mathbf\{F\},P\(\\mathbf\{U\}\)\\rangle, where𝐔\\mathbf\{U\}denotes a set of exogenous \(unobserved\) variables determined by factors external to the model, and𝐕\\mathbf\{V\}denotes a set of endogenous \(observed\) variables determined by variables in𝐔∪𝐕\\mathbf\{U\}\\cup\\mathbf\{V\}through the structural functions𝐅\\mathbf\{F\}\. In our setting, the endogenous variables𝐕\\mathbf\{V\}take values in finite domains and consist of the reward variableYY, 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𝐗⊆𝐕\\mathbf\{X\}\\subseteq\\mathbf\{V\}, letΩ​\(𝐗\)\\Omega\(\\mathbf\{X\}\)denote the Cartesian product of the state spaces of all variables in𝐗\\mathbf\{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𝐅\\mathbf\{F\}specify how eachViV\_\{i\}is assigned a value, denoted asvi=fi​\(𝐏𝐀i,𝐔i\)v\_\{i\}=f\_\{i\}\(\\mathbf\{PA\}^\{i\},\\mathbf\{U\}^\{i\}\), based on the values of its parent variables𝐏𝐀i⊆𝐕\\mathbf\{PA\}^\{i\}\\subseteq\\mathbf\{V\}and exogenous variables𝐔i⊆𝐔\\mathbf\{U\}^\{i\}\\subseteq\\mathbf\{U\}\. Finally,P​\(𝐔\)P\(\\mathbf\{U\}\)is the probability distribution over the exogenous variables𝐔\\mathbf\{U\}\.

Each SCM is associated with a causal graph𝒢=⟨𝐕,𝐄⟩\\mathcal\{G\}=\\langle\\mathbf\{V\},\\mathbf\{E\}\\rangle, where the edge set𝐄\\mathbf\{E\}consists of two types: directed edges, such asVi→VjV\_\{i\}\\rightarrow V\_\{j\}, which indicate direct functional dependence \(i\.e\.,ViV\_\{i\}is used in definingfjf\_\{j\}in𝐅\\mathbf\{F\}\), and bidirected edges, such asVi↔VjV\_\{i\}\\leftrightarrow V\_\{j\}, which represent the presence of an unobserved \(latent\) confounder affecting bothViV\_\{i\}andVjV\_\{j\}\. We use notationspa,ch,an, anddeto refer to the parents, children, ancestors, and descendants of a variable, respectively\. Capitalized forms, such asPa,Ch,An, andDe, include the variable itself \(e\.g\.,An​\(W\)=an​\(W\)∪W\\textit\{An\}\(W\)=\\textit\{an\}\(W\)\\cup\{W\}\)\. For a set of variables, the relations are defined as the union of their individual outputs, e\.g\.,An​\(𝐖\)=⋃W∈𝐖An​\(W\)\\textit\{An\}\(\\mathbf\{W\}\)=\\bigcup\_\{W\\in\\mathbf\{W\}\}\\textit\{An\}\(W\)\. Note thatpa​\(Vi\)=𝐏𝐀i\\textit\{pa\}\(V\_\{i\}\)=\\mathbf\{PA\}^\{i\}\. A subgraph of𝒢\\mathcal\{G\}, denoted𝒢𝐗¯\\mathcal\{G\}\_\{\\overline\{\\mathbf\{X\}\}\}, is obtained by removing edges pointing to the variables in𝐗\\mathbf\{X\}\. The connected component \(c\-component\) of the DAG𝒢\\mathcal\{G\}, containing vertexViV\_\{i\}, is denoted by𝖢𝖢𝒢​\(Vi\)\\mathsf\{CC\}\_\{\\mathcal\{G\}\}\(V\_\{i\}\), which is the maximal set of all vertices in𝒢\\mathcal\{G\}that have a path toViV\_\{i\}, consisting only of bi\-directed edgesTian and Pearl \([2002](https://arxiv.org/html/2607.15577#bib.bib4)\)\.

In theKK\-armed bandit problem,KKarms with distinct reward distributions are available, and the goal is to minimize cumulative regret overTTrounds\. 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𝒢\\mathcal\{G\}with rewardYY, the arms are defined asdo​\(𝐗=𝐱\)∣𝐗⊆𝐕∖Y\{\\mathrm\{do\}\(\\mathbf\{X\}=\\mathbf\{x\}\)\\mid\\mathbf\{X\}\\subseteq\\mathbf\{V\}\\setminus\{Y\}\}, where the distribution of the reward variable under the interventiondo​\(𝐗=𝐱\)\\mathrm\{do\}\(\\mathbf\{X\}=\\mathbf\{x\}\), denoted byP​\(Y𝐱\)P\(Y\_\{\\mathbf\{x\}\}\), coincides with the interventional distributionP𝐱​\(Y\)P\_\{\\mathbf\{x\}\}\(Y\)\. The expected reward associated with an intervention isμ𝐱=𝔼​\[Y∣do​\(𝐱\)\]\\mu\_\{\\mathbf\{x\}\}=\\mathbb\{E\}\[Y\\mid\\mathrm\{do\}\(\\mathbf\{x\}\)\]\. When additional context variables𝐂\\mathbf\{C\}are observed prior to the intervention, the objective becomes to optimize the expected reward conditioned on the context, namelyμ𝐱​\(𝐂=𝐜\)=𝔼​\[Y∣do​\(𝐱\),𝐂=𝐜\]\\mu\_\{\\mathbf\{x\}\}\(\\mathbf\{C\}=\\mathbf\{c\}\)=\\mathbb\{E\}\[Y\\mid\\mathrm\{do\}\(\\mathbf\{x\}\),\\mathbf\{C\}=\\mathbf\{c\}\]\. Moreover, we assume that𝐂\\mathbf\{C\}is closed under ancestry, i\.e\.,A​n​\(𝐂\)=𝐂An\(\\mathbf\{C\}\)=\\mathbf\{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\.

## 3Possibly Optimal Arms for Causal Bandits

In this section, we revisit the results ofLee and Bareinboim \([2019](https://arxiv.org/html/2607.15577#bib.bib52)\), which characterize possibly optimal arms in causal bandits when certain nodes in the causal graph are non\-manipulable\. Let𝐍⊆𝐕∖\{Y\}\\mathbf\{N\}\\subseteq\\mathbf\{V\}\\setminus\\\{Y\\\}denote the set of non\-manipulable variables, noting that the reward variableYYis also inherently non\-manipulable\.

###### Definition 1\.

\(Unobserved Confounder \(UC\)\-TerritoryLee and Bareinboim \([2018](https://arxiv.org/html/2607.15577#bib.bib26)\)\) Consider a causal graph𝒢​\(𝐕,𝐄\)\\mathcal\{G\}\(\\mathbf\{V\},\\mathbf\{E\}\)with reward nodeYY, and letℋ\\mathcal\{H\}be the subgraph𝒢​\[𝖠𝗇​\(Y\)\]\\mathcal\{G\}\[\\mathsf\{An\}\(Y\)\]\. A set of variables𝐓⊆V​\(ℋ\)\\mathbf\{T\}\\subseteq V\(\\mathcal\{H\}\)containingYYis called aUC\-territoryon𝒢\\mathcal\{G\}with respect toYYif𝖣𝖾ℋ​\(𝐓\)=𝐓\\mathsf\{De\}\_\{\\mathcal\{H\}\}\(\\mathbf\{T\}\)=\\mathbf\{T\}and𝖢𝖢ℋ​\(𝐓\)=𝐓\\mathsf\{CC\}\_\{\\mathcal\{H\}\}\(\\mathbf\{T\}\)=\\mathbf\{T\}\.

A UC\-territory is minimal if none of its proper subsets containingYYis a UC\-territory\. A minimal UC\-territory, denoted by𝖬𝖴𝖢𝖳​\(𝒢,Y\)\\mathsf\{MUCT\}\(\\mathcal\{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 BorderLee and Bareinboim \([2018](https://arxiv.org/html/2607.15577#bib.bib26)\)\)Let𝐓\\mathbf\{T\}be a minimal UC\-territory on𝒢\\mathcal\{G\}with respect toYY\. Then,𝐗=𝖯𝖺​\(𝐓\)∖𝐓\\mathbf\{X\}=\\mathsf\{Pa\}\(\\mathbf\{T\}\)\\setminus\\mathbf\{T\}is called the interventional border of𝒢\\mathcal\{G\}with respect toYY, denoted by𝖨𝖡​\(𝒢,Y\)\\mathsf\{IB\}\(\\mathcal\{G\},Y\)\.

###### Lemma 1\.

Lee and Bareinboim\([2018](https://arxiv.org/html/2607.15577#bib.bib26)\)For a graph𝒢\\mathcal\{G\}with reward nodeYY,𝖨𝖡​\(𝒢𝐖¯,Y\)\\mathsf\{IB\}\(\\mathcal\{G\}\_\{\\overline\{\\mathbf\{W\}\}\},Y\)is a possibly optimal minimal intervention set \(POMIS\) for any𝐖⊆𝐕∖\{Y\}\\mathbf\{W\}\\subseteq\\mathbf\{V\}\\setminus\\\{Y\\\}\.

XXYYZZ\(a\)𝒢1\\mathcal\{G\}\_\{1\}

XXYY\(b\)ℋ1\\mathcal\{H\}\_\{1\}

XXWWYYZ1Z\_\{1\}Z2Z\_\{2\}\(c\)𝒢2\\mathcal\{G\}\_\{2\}

XXWWYY\(d\)ℋ2\\mathcal\{H\}\_\{2\}

Figure 1:Original causal graphs𝒢1\\mathcal\{G\}\_\{1\}and𝒢2\\mathcal\{G\}\_\{2\}, along with their projectionsℋ1\\mathcal\{H\}\_\{1\}andℋ2\\mathcal\{H\}\_\{2\}\.For a causal graph𝒢\\mathcal\{G\}in which all nodes except the reward nodeYYare manipulable, we use the notationℙ𝒢,Y\\mathbb\{P\}\_\{\\mathcal\{G\},Y\}to denote the collection of all POMISs\. In the more general setting where the variables in𝐍\\mathbf\{N\}cannot be intervened upon, we useℙ𝒢,Y𝐍\\mathbb\{P\}^\{\\mathbf\{N\}\}\_\{\\mathcal\{G\},Y\}to denote the corresponding collection of possibly optimal minimal intervention sets\. FollowingLee and Bareinboim \([2019](https://arxiv.org/html/2607.15577#bib.bib52)\), these intervention sets can be obtained through a projection step\. We initialize a graphℋ=⟨𝐕∖𝐍,∅⟩\\mathcal\{H\}=\\langle\\mathbf\{V\}\\setminus\\mathbf\{N\},\\emptyset\\rangleand add a directed edgeVi→VjV\_\{i\}\\to V\_\{j\}ifVi→VjV\_\{i\}\\to V\_\{j\}is present in𝒢\\mathcal\{G\}, or if there exists a directed path fromViV\_\{i\}toVjV\_\{j\}whose non\-endpoint vertices all belong to𝐍\\mathbf\{N\}\. We add a bidirected edgeVi↔VjV\_\{i\}\\leftrightarrow V\_\{j\}if this edge is present in𝒢\\mathcal\{G\}, or if the projection of paths passing through variables in𝐍\\mathbf\{N\}induces latent confounding betweenViV\_\{i\}andVjV\_\{j\}\. The results ofLee and Bareinboim \([2019](https://arxiv.org/html/2607.15577#bib.bib52)\)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ℋ\\mathcal\{H\}using Lemma[1](https://arxiv.org/html/2607.15577#Thmlemma1)\. Thus,ℙ𝒢,Y𝐍=ℙℋ,Y\\mathbb\{P\}^\{\\mathbf\{N\}\}\_\{\\mathcal\{G\},Y\}=\\mathbb\{P\}\_\{\\mathcal\{H\},Y\}\.

Consider the causal graph𝒢1\\mathcal\{G\}\_\{1\}with reward nodeYYand non\-manipulable set𝐍=\{Z\}\\mathbf\{N\}=\\\{Z\\\}, and letℋ1\\mathcal\{H\}\_\{1\}be the graph resulting from the projection step, as shown in Figure[1](https://arxiv.org/html/2607.15577#S3.F1)\. The possibly optimal intervention sets for the original causal graph can be obtained fromℋ1\\mathcal\{H\}\_\{1\}using Lemma[1](https://arxiv.org/html/2607.15577#Thmlemma1)\. In particular,ℙℋ1,Y=\{∅,\{X\}\}=ℙ𝒢1,Y𝐍\\mathbb\{P\}\_\{\\mathcal\{H\}\_\{1\},Y\}=\\\{\\emptyset,\\\{X\\\}\\\}=\\mathbb\{P\}^\{\\mathbf\{N\}\}\_\{\\mathcal\{G\}\_\{1\},Y\}\. Therefore, the candidate optimal arms ared​o​\(\)do\(\),d​o​\(X=0\)do\(X=0\), andd​o​\(X=1\)do\(X=1\)\. Similarly, for the causal graph𝒢2\\mathcal\{G\}\_\{2\}with reward nodeYYand non\-manipulable set𝐍=\{Z1,Z2\}\\mathbf\{N\}=\\\{Z\_\{1\},Z\_\{2\}\\\}, the projected graphℋ2\\mathcal\{H\}\_\{2\}is shown in Figure[1](https://arxiv.org/html/2607.15577#S3.F1)\. In this case,ℙℋ2,Y=\{∅,\{W\}\}=ℙ𝒢2,Y𝐍\\mathbb\{P\}\_\{\\mathcal\{H\}\_\{2\},Y\}=\\\{\\emptyset,\\\{W\\\}\\\}=\\mathbb\{P\}^\{\\mathbf\{N\}\}\_\{\\mathcal\{G\}\_\{2\},Y\}, and the candidate optimal arms ared​o​\(\)do\(\),d​o​\(W=0\)do\(W=0\), andd​o​\(W=1\)do\(W=1\)\. More generally, we use𝒜\\mathcal\{A\}to denote the set of all interventions generated by all POMISs, that is,𝒜:=⋃𝐒∈ℙ𝒢,Y𝐍\{d​o​\(𝐒=𝐬\):𝐬∈Ω​\(𝐒\)\}\\mathcal\{A\}:=\\bigcup\_\{\\mathbf\{S\}\\in\\mathbb\{P\}^\{\\mathbf\{N\}\}\_\{\\mathcal\{G\},Y\}\}\\\{do\(\\mathbf\{S\}=\\mathbf\{s\}\):\\mathbf\{s\}\\in\\Omega\(\\mathbf\{S\}\)\\\}, whered​o​\(∅\)do\(\\emptyset\)denotes the observational action\.

We use the causal graph𝒢1\\mathcal\{G\}\_\{1\}to illustrate how samples obtained from different arms can be used to improve reward estimates across interventions\. As an illustrative example, letZZrepresent the age of a patient, letXXdenote a medication or treatment, and letYYrepresent the health outcome\. The patient’s ageZZhas a causal effect on the outcomeYYbut cannot be directly manipulated\. The candidate optimal arms ared​o​\(\)do\(\),d​o​\(X=0\)do\(X=0\), andd​o​\(X=1\)do\(X=1\)\. Their expected rewards are given byP​\(Y=1∣d​o​\(\)\)=∑x,zP​\(Y=1∣x,z\)​P​\(x∣z\)​P​\(z\)P\(Y=1\\mid do\(\)\)=\\sum\_\{x,z\}P\(Y=1\\mid x,z\)P\(x\\mid z\)P\(z\),P\(Y=1∣do\(X=0\)\)=∑zP\(Y=1∣X=0,z\)P\(z\)P\(Y=1\\mid do\(X=0\)\)=\\sum\_\{z\}P\(Y=1\\mid X=0,z\)P\(z\), andP\(Y=1∣do\(X=1\)\)=∑zP\(Y=1∣X=1,z\)P\(z\)P\(Y=1\\mid do\(X=1\)\)=\\sum\_\{z\}P\(Y=1\\mid 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\.

## 4Bayesian Formulation for Causal Bandits

We consider a general probabilistic \(Bayesian\) formulation in which uncertain quantities are modeled as random variables\. At each timett, the agent selects an actionAt∈𝒜A\_\{t\}\\in\\mathcal\{A\}and observes a reward\. For each actiona∈𝒜a\\in\\mathcal\{A\}and timett, letYa,t∈𝒴Y\_\{a,t\}\\in\\mathcal\{Y\}denote the potential reward that would be observed at timettif actionaawere selected\. There exists an unknown real\-valued parameter vector𝜽\\boldsymbol\{\\theta\}such that, conditioned on𝜽\\boldsymbol\{\\theta\}, the rewards are independent across time and satisfy𝔼​\[YAt,t∣𝜽\]=μ𝜽​\(At\)\\mathbb\{E\}\[Y\_\{A\_\{t\},t\}\\mid\\boldsymbol\{\\theta\}\]=\\mu\_\{\\boldsymbol\{\\theta\}\}\(A\_\{t\}\)\. The parameter𝜽\\boldsymbol\{\\theta\}is random under a prior distribution, capturing uncertainty about the underlying reward\-generating mechanism\. Uncertainty in𝜽\\boldsymbol\{\\theta\}induces uncertainty about the optimal actionA⋆∈arg⁡maxa∈𝒜⁡μ𝜽​\(a\)A^\{\\star\}\\in\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mu\_\{\\boldsymbol\{\\theta\}\}\(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\)\]\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]=\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{A^\{\\star\},t\}\-Y\_\{A\_\{t\},t\}\\right\)\\right\], where the expectation is taken over the randomness in the actionsAtA\_\{t\}, the rewards, and the prior distribution over𝜽\\boldsymbol\{\\theta\}\. This performance metric is commonly referred to as Bayesian regret or Bayesian risk\.

ActionAtA\_\{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\)\\mathcal\{F\}\_\{t\}=\\left\(\\mathbf\{C\}\_\{1\},A\_\{1\},\\mathbf\{V\}\_\{A\_\{1\},1\},Y\_\{A\_\{1\},1\},\\ldots,\\mathbf\{C\}\_\{t\-1\},A\_\{t\-1\},\\mathbf\{V\}\_\{A\_\{t\-1\},t\-1\},Y\_\{A\_\{t\-1\},t\-1\}\\right\)available before observing the context at timett\. Formally, a randomized policyπ=\(πt\)t∈ℕ\\pi=\\left\(\\pi\_\{t\}\\right\)\_\{t\\in\\mathbb\{N\}\}is a sequence of deterministic functions, whereπt​\(ℱt,𝐂t\)\\pi\_\{t\}\\left\(\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{t\}\\right\)specifies a probability distribution over the action set𝒜\\mathcal\{A\}\. Let𝒟​\(𝒜\)\\mathcal\{D\}\(\\mathcal\{A\}\)denote the set of probability distributions over𝒜\\mathcal\{A\}\. After observing𝐂t\\mathbf\{C\}\_\{t\}, the actionAtA\_\{t\}is selected by sampling fromπt​\(ℱt,𝐂t\)\\pi\_\{t\}\\left\(\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{t\}\\right\)\. With some abuse of notation, we typically denote this distribution byπt\\pi\_\{t\}, whereπt​\(a∣𝐜t\)=ℙ​\(At=a∣ℱt,𝐂t=𝐜t\)\\pi\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=\\mathbb\{P\}\\left\(A\_\{t\}=a\\mid\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)denotes the probability assigned to actionaaunder the realized context𝐜t\\mathbf\{c\}\_\{t\}\. As shorthand notation, we usePt​\(⋅\)P\_\{t\}\(\\cdot\)forP\(⋅∣ℱt\)P\(\\cdot\\mid\\mathcal\{F\}\_\{t\}\)and𝔼t​\(⋅\)\\mathbb\{E\}\_\{t\}\(\\cdot\)for𝔼\(⋅∣ℱt\)\\mathbb\{E\}\(\\cdot\\mid\\mathcal\{F\}\_\{t\}\), respectively\. After observing𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}, we define the context\-conditioned posterior byPt𝐜t\(⋅\):=P\(⋅∣ℱt,𝐂t=𝐜t\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\cdot\):=P\(\\cdot\\mid\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\)and the corresponding conditional expectation by𝔼t𝐜t​\(⋅\)\\mathbb\{E\}\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\cdot\)\.

In the contextual setting, at each timett, a context𝐂t∈𝒞\\mathbf\{C\}\_\{t\}\\in\\mathcal\{C\}is observed prior to selecting an action\. The expected reward depends on both the action and the context and satisfies𝔼​\[YAt,t∣𝐂t=𝐜,𝜽\]=μ𝜽​\(At,𝐜\)\\mathbb\{E\}\[Y\_\{A\_\{t\},t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\},\\boldsymbol\{\\theta\}\]=\\mu\_\{\\boldsymbol\{\\theta\}\}\(A\_\{t\},\\mathbf\{c\}\)\. Accordingly, we define the oracle mappingΠ⋆:𝒞→𝒜\\Pi^\{\\star\}:\\mathcal\{C\}\\to\\mathcal\{A\}byΠ⋆​\(𝐜\):=arg⁡maxa∈𝒜⁡μ𝜽​\(a,𝐜\)\\Pi^\{\\star\}\(\\mathbf\{c\}\):=\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mu\_\{\\boldsymbol\{\\theta\}\}\(a,\\mathbf\{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\{𝐂t\}t=1T\\\{\\mathbf\{C\}\_\{t\}\\\}\_\{t=1\}^\{T\}, is given by

𝔼\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\|\{𝐂t\}t=1T\]\.\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\,\\middle\|\\,\\\{\\mathbf\{C\}\_\{t\}\\\}\_\{t=1\}^\{T\}\\right\]\.\(1\)One remaining task is to specify the parameter𝜽\\boldsymbol\{\\theta\}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 formulaPearl \([2009](https://arxiv.org/html/2607.15577#bib.bib33)\)\. For instance,P​\(𝐯𝐕∖𝐗∣d​o​\(𝐱\)\)=∏Vi∈𝐕∖𝐗P​\(vi∣𝐩𝐚i\)P\(\\mathbf\{v\}\_\{\\mathbf\{V\}\\setminus\\mathbf\{X\}\}\\mid do\(\\mathbf\{x\}\)\)=\\prod\_\{V\_\{i\}\\in\\mathbf\{V\}\\setminus\\mathbf\{X\}\}P\(v\_\{i\}\\mid\\mathbf\{pa\}\_\{i\}\), where the parent values are evaluated consistently with the intervention𝐗=𝐱\\mathbf\{X\}=\\mathbf\{x\}\. Thus, the observational distribution naturally determines the parameter𝜽\\boldsymbol\{\\theta\}\.

Under the Markov assumption, the joint distribution factorizes asP​\(𝐯\)=∏Vi∈𝐕P​\(vi∣𝐩𝐚i\)P\(\\mathbf\{v\}\)=\\prod\_\{V\_\{i\}\\in\\mathbf\{V\}\}P\(v\_\{i\}\\mid\\mathbf\{pa\}\_\{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ℱt\\mathcal\{F\}\_\{t\}\. For each variableVi∈𝐕V\_\{i\}\\in\\mathbf\{V\}withrir\_\{i\}possible valuesxi1,…,xirix\_\{i\}^\{1\},\\ldots,x\_\{i\}^\{r\_\{i\}\}, the local likelihood consists of a collection of multinomial distributions, one for each configuration of𝐏𝐚i\\mathbf\{Pa\}\_\{i\}\. Specifically,P\(Vi=xik∣𝐏𝐚i=𝐩𝐚ij,𝜽i​j\)=θi​j​kP\\left\(V\_\{i\}=x\_\{i\}^\{k\}\\mid\\mathbf\{Pa\}\_\{i\}=\\mathbf\{pa\}\_\{i\}^\{j\},\\boldsymbol\{\\theta\}\_\{ij\}\\right\)=\\theta\_\{ijk\}, whereθi​j​k\>0\\theta\_\{ijk\}\>0and∑k=1riθi​j​k=1\\sum\_\{k=1\}^\{r\_\{i\}\}\\theta\_\{ijk\}=1\. Here,𝐩𝐚i1,…,𝐩𝐚iqi\\mathbf\{pa\}\_\{i\}^\{1\},\\ldots,\\mathbf\{pa\}\_\{i\}^\{q\_\{i\}\}denote theqiq\_\{i\}possible configurations of the parent set𝐏𝐚i\\mathbf\{Pa\}\_\{i\}, whereqi=∏Xℓ∈𝐏𝐚irℓq\_\{i\}=\\prod\_\{X\_\{\\ell\}\\in\\mathbf\{Pa\}\_\{i\}\}r\_\{\\ell\}, and𝜽i​j=\(θi​j​1,…,θi​j​ri\)\\boldsymbol\{\\theta\}\_\{ij\}=\(\\theta\_\{ij1\},\\ldots,\\theta\_\{ijr\_\{i\}\}\)denotes the parameter vector associated with thejj\-th parent configuration\. We define𝜽i=\(𝜽i​1,…,𝜽i​qi\)\\boldsymbol\{\\theta\}\_\{i\}=\(\\boldsymbol\{\\theta\}\_\{i1\},\\ldots,\\boldsymbol\{\\theta\}\_\{iq\_\{i\}\}\), and the overall parameter vector is therefore𝜽=\(𝜽1,…,𝜽n\)\\boldsymbol\{\\theta\}=\(\\boldsymbol\{\\theta\}\_\{1\},\\ldots,\\boldsymbol\{\\theta\}\_\{n\}\)\.

Similar toHeckermanet al\.\([2006](https://arxiv.org/html/2607.15577#bib.bib53)\), to ensure efficient computation, we assume parameter independence across the vectors𝜽i​j\\boldsymbol\{\\theta\}\_\{ij\}\. Consequently, conditioned on the history of observationsℱt\\mathcal\{F\}\_\{t\}, each vector𝜽i​j\\boldsymbol\{\\theta\}\_\{ij\}can be updated independently\. Assuming that each vector𝜽i​j\\boldsymbol\{\\theta\}\_\{ij\}follows a conjugate Dirichlet prior, namelyDir⁡\(𝜽i​j∣αi​j​1,…,αi​j​ri\)\\operatorname\{Dir\}\\\!\\left\(\\boldsymbol\{\\theta\}\_\{ij\}\\mid\\alpha\_\{ij1\},\\ldots,\\alpha\_\{ijr\_\{i\}\}\\right\), the posterior distribution over the parameter space is given by

Pt​\(𝜽\)=P​\(𝜽∣ℱt\)=∏i=1n∏j=1qiPt​\(𝜽i​j\)\.P\_\{t\}\(\\boldsymbol\{\\theta\}\)=P\\left\(\\boldsymbol\{\\theta\}\\mid\\mathcal\{F\}\_\{t\}\\right\)=\\prod\_\{i=1\}^\{n\}\\prod\_\{j=1\}^\{q\_\{i\}\}P\_\{t\}\(\\boldsymbol\{\\theta\}\_\{ij\}\)\.\(2\)Pt​\(𝜽i​j\)=Dir⁡\(𝜽i​j∣αi​j​1\+Ni​j​1​\(ℱt\),…,αi​j​ri\+Ni​j​ri​\(ℱt\)\)\.P\_\{t\}\(\\boldsymbol\{\\theta\}\_\{ij\}\)=\\operatorname\{Dir\}\\left\(\\boldsymbol\{\\theta\}\_\{ij\}\\mid\\alpha\_\{ij1\}\+N\_\{ij1\}\(\\mathcal\{F\}\_\{t\}\),\\ldots,\\alpha\_\{ijr\_\{i\}\}\+N\_\{ijr\_\{i\}\}\(\\mathcal\{F\}\_\{t\}\)\\right\)\.\(3\)Here,Ni​j​k​\(ℱt\)N\_\{ijk\}\(\\mathcal\{F\}\_\{t\}\)denotes the number of times the realizationVi=xikV\_\{i\}=x\_\{i\}^\{k\}has been observed in the historyℱt\\mathcal\{F\}\_\{t\}when𝐏𝐚i=𝐩𝐚ij\\mathbf\{Pa\}\_\{i\}=\\mathbf\{pa\}\_\{i\}^\{j\}and the corresponding action does not intervene onViV\_\{i\}\. After observing the current context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}, the posterior used for action selection isPt𝐜t​\(𝜽\)=P​\(𝜽∣ℱt,𝐂t=𝐜t\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\)=P\(\\boldsymbol\{\\theta\}\\mid\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\), which is obtained by conditioningPt​\(𝜽\)P\_\{t\}\(\\boldsymbol\{\\theta\}\)on the observed context\. Equation \([2](https://arxiv.org/html/2607.15577#S4.E2)\) 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

𝒢\\mathcal\{G\}and the action set

𝒜\\mathcal\{A\}induced by all POMISs of the projected graph\.

for*t=1t=1toTT*do

Compute the posterior

Pt​\(𝜽\)P\_\{t\}\(\\boldsymbol\{\\theta\}\)using \([2](https://arxiv.org/html/2607.15577#S4.E2)\);

Observe the realized context

𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\};

Compute the context\-conditioned posterior

Pt𝐜t​\(𝜽\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\);

Sample

𝜽t∼Pt𝐜t​\(𝜽\)\\boldsymbol\{\\theta\}\_\{t\}\\sim P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\);

Select action

at←arg⁡maxa∈𝒜⁡𝔼​\[Ya,t∣𝜽t,𝐜t\]a\_\{t\}\\leftarrow\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\[Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\}\_\{t\},\\mathbf\{c\}\_\{t\}\];

Play action

ata\_\{t\}, observe the reward and all non\-intervened variables, and update the history

ℱt\+1\\mathcal\{F\}\_\{t\+1\};

Algorithm 1Thompson Sampling for causal bandits with non\-manipulable variables
## 5Thompson 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 samplingThompson \([1933](https://arxiv.org/html/2607.15577#bib.bib48)\)\. We propose a Thompson sampling algorithm for causal bandits with non\-manipulable variables\. Algorithm[1](https://arxiv.org/html/2607.15577#alg1)maintains, at each roundtt, a posterior distribution over the parameter space, denoted byPt​\(𝜽\)P\_\{t\}\(\\boldsymbol\{\\theta\}\), capturing uncertainty given the history of observations up to roundtt\. After observing the realized context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}, the action at roundttis selected asat∈arg⁡maxa∈𝒜⁡𝔼​\[Ya,t∣𝜽t,𝐜t\],a\_\{t\}\\in\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\[Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\}\_\{t\},\\mathbf\{c\}\_\{t\}\],where𝜽t\\boldsymbol\{\\theta\}\_\{t\}is an independent sample drawn from the context\-conditioned posterior distributionPt​\(𝜽∣𝐂t=𝐜t\)P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{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\\Gamma\_\{t\}such that the expected instantaneous regret satisfies

𝔼t​\[YΠ⋆​\(𝐂t\),t−YAt,t∣𝐂t\]≤Γt​It​\(Π⋆​\(𝐂t\);\(At,YAt,t\)∣𝐂t\)\.\\mathbb\{E\}\_\{t\}\\\!\\left\[Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\mid\\mathbf\{C\}\_\{t\}\\right\]\\leq\\Gamma\_\{t\}\\sqrt\{I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)\}\.The quantityΓt2\\Gamma\_\{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 termIt\(Π⋆\(𝐂t\);\(At,YAt,t\)∣𝐂t\):=DKL\(Pt\(Π⋆\(𝐂t\),At,YAt,t∣𝐂t\)∥Pt\(Π⋆\(𝐂t\)∣𝐂t\)Pt\(At,YAt,t∣𝐂t\)\)I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\):=D\_\{\\mathrm\{KL\}\}\\\!\\left\(P\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),A\_\{t\},Y\_\{A\_\{t\},t\}\\mid\\mathbf\{C\}\_\{t\}\\right\)\\;\\middle\\\|\\;P\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)P\_\{t\}\\\!\\left\(A\_\{t\},Y\_\{A\_\{t\},t\}\\mid\\mathbf\{C\}\_\{t\}\\right\)\\right\)denotes the filtered mutual information between the optimal action under the realized context and the action\-reward observation at roundtt\. This quantity measures how much the observation collected at roundttreduces uncertainty about the optimal action under the realized context\. SinceΠ⋆​\(𝐂t\)\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\)is a deterministic function of the full oracle mappingΠ⋆\\Pi^\{\\star\}, the cumulative information gain is bounded by the entropyH​\(Π⋆\)H\(\\Pi^\{\\star\}\)\. Theorem[1](https://arxiv.org/html/2607.15577#S5.Ex2)provides a bound on the mean cumulative regret\.

###### Theorem 1\.

The mean cumulative Bayesian regret of Algorithm[1](https://arxiv.org/html/2607.15577#alg1)is bounded for anyT∈ℕT\\in\\mathbb\{N\}as follows, whereΓ≥Γt\\Gamma\\geq\\Gamma\_\{t\}for allt∈\{1,…,T\}t\\in\\\{1,\\ldots,T\\\}:

𝔼​\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\]≤Γ​H​\(Π⋆\)​T\.\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\right\]\\leq\\Gamma\\sqrt\{H\(\\Pi^\{\\star\}\)\\,T\}\.

The entropyH​\(Π⋆\)H\(\\Pi^\{\\star\}\)quantifies the decision\-maker’s initial uncertainty regarding the optimal\-action mapping\. The mean cumulative regret incurred by Algorithm[1](https://arxiv.org/html/2607.15577#alg1)depends on the time horizonTT, the entropyH​\(Π⋆\)H\(\\Pi^\{\\star\}\), and the worst\-case upper bound on the information\-ratio coefficientΓt\\Gamma\_\{t\}\. FollowingRusso and Van Roy \([2016](https://arxiv.org/html/2607.15577#bib.bib54)\), we establish a simple worst\-case upper bound given byΓt2≤\|𝒜\|2\\Gamma\_\{t\}^\{2\}\\leq\\frac\{\|\\mathcal\{A\}\|\}\{2\}, or equivalentlyΓt≤\|𝒜\|2\\Gamma\_\{t\}\\leq\\sqrt\{\\frac\{\|\\mathcal\{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Γ\\Gammain Theorem[1](https://arxiv.org/html/2607.15577#S5.Ex2)can be replaced with\|𝒜\|2\\sqrt\{\\frac\{\|\\mathcal\{A\}\|\}\{2\}\}, leading to the regret bound stated in Corollary[1](https://arxiv.org/html/2607.15577#S5.Ex3)\. Moreover, sinceΠ⋆\\Pi^\{\\star\}maps the context space𝒞\\mathcal\{C\}to the action space𝒜\\mathcal\{A\}, the number of possible mappings is\|𝒜\|\|𝒞\|\|\\mathcal\{A\}\|^\{\|\\mathcal\{C\}\|\}when𝒞\\mathcal\{C\}is finite, which implies that the entropy satisfiesH​\(Π⋆\)≤log⁡\(\|𝒜\|\|𝒞\|\)=\|𝒞\|​log⁡\|𝒜\|H\(\\Pi^\{\\star\}\)\\leq\\log\\left\(\|\\mathcal\{A\}\|^\{\|\\mathcal\{C\}\|\}\\right\)=\|\\mathcal\{C\}\|\\log\|\\mathcal\{A\}\|\.

###### Corollary 1\.

Suppose that the context space𝒞\\mathcal\{C\}is finite\. The mean cumulative Bayesian regret for Algorithm[1](https://arxiv.org/html/2607.15577#alg1)is bounded for anyT∈ℕT\\in\\mathbb\{N\}as follows:

𝔼​\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\]≤T​\|𝒜\|​\|𝒞\|​log⁡\|𝒜\|2\.\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\right\]\\leq\\sqrt\{\\frac\{T\|\\mathcal\{A\}\|\|\\mathcal\{C\}\|\\log\\\!\|\\mathcal\{A\}\|\}\{2\}\}\.

## 6Information\-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=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}at timett, IDS selects an action distribution that minimizes the ratio of the squared expected regretΔt​\(π∣𝐜t\)2\\Delta\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)^\{2\}to the information gaingt​\(π∣𝐜t\)g\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)about the optimal action under that context, namelyΠ⋆​\(𝐜t\)\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\), over all sampling distributionsπ∈𝒟​\(𝒜\)\\pi\\in\\mathcal\{D\}\(\\mathcal\{A\}\)\. The resulting IDS policyπtIDS​\(𝐜t\)\\pi\_\{t\}^\{\\mathrm\{IDS\}\}\(\\mathbf\{c\}\_\{t\}\)is formally defined as:

πtIDS\(𝐜t\)∈argminπ∈𝒟​\(𝒜\)\{Ψt\(π∣𝐜t\):=Δt​\(π∣𝐜t\)2gt​\(π∣𝐜t\)\}\.\\pi\_\{t\}^\{\\mathrm\{IDS\}\}\(\\mathbf\{c\}\_\{t\}\)\\in\\arg\\min\_\{\\pi\\in\\mathcal\{D\}\(\\mathcal\{A\}\)\}\\left\\\{\\Psi\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\):=\\frac\{\\Delta\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)^\{2\}\}\{g\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)\}\\right\\\}\.The expected instantaneous regret of a policyπ\\piis defined asΔt​\(π∣𝐜t\)=∑a∈𝒜π​\(a\)​Δt​\(a∣𝐜t\)\\Delta\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)=\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\(a\)\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\), whereΔt​\(a∣𝐜t\):=𝔼t​\[YΠ⋆​\(𝐜t\),t−Ya,t∣𝐂t=𝐜t\]\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\):=\\mathbb\{E\}\_\{t\}\\\!\\left\[Y\_\{\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\),t\}\-Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\]denotes the expected instantaneous regret incurred by selecting actionaaat time stepttunder context𝐜t\\mathbf\{c\}\_\{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 asgt​\(π∣𝐜t\)=∑a∈𝒜π​\(a\)​gt​\(a∣𝐜t\)g\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)=\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\(a\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\), wheregt​\(a∣𝐜t\):=It​\(Π⋆​\(𝐜t\);Ya,t∣𝐂t=𝐜t\)=Ht​\(Π⋆​\(𝐜t\)∣𝐂t=𝐜t\)−Ht​\(Π⋆​\(𝐜t\)∣𝐂t=𝐜t,Ya,t\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\):=I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\);Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)=H\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)\-H\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\},Y\_\{a,t\}\\right\)denotes the information gained by selecting actionaa\. In other words,gt​\(a∣𝐜t\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)measures the expected reduction in posterior uncertainty about the optimal action under context𝐜t\\mathbf\{c\}\_\{t\}after observing the corresponding rewardYa,tY\_\{a,t\}\. The quantityΨt​\(π∣𝐜t\)\\Psi\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\), referred to as theinformation 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 conventions0/0:=00/0:=0andx/0:=\+∞x/0:=\+\\inftyfor everyx\>0x\>0\.

Input:Causal graph

𝒢\\mathcal\{G\}, confidence level

δ′\\delta^\{\\prime\}, posterior sample size

NN, and action set

𝒜\\mathcal\{A\}induced by all POMISs of the projected graph

for*t=1t=1toTT*do

Compute the posterior

Pt​\(𝜽\)P\_\{t\}\(\\boldsymbol\{\\theta\}\)using \([2](https://arxiv.org/html/2607.15577#S4.E2)\);

Observe the realized context

𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\};

Compute the context\-conditioned posterior

Pt𝐜t​\(𝜽\)=P​\(𝜽∣ℱt,𝐂t=𝐜t\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\)=P\(\\boldsymbol\{\\theta\}\\mid\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\);

Draw

NNindependent samples from

Pt𝐜t​\(𝜽\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\);

For every

a∈𝒜a\\in\\mathcal\{A\}, select any value

Δ~t​\(a∣𝐜t\)\\widetilde\{\\Delta\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)from the confidence interval in Lemma[3](https://arxiv.org/html/2607.15577#Thmlemma3), using

δ=δ′2​T​\|𝒜\|\\delta=\\frac\{\\delta^\{\\prime\}\}\{2T\|\\mathcal\{A\}\|\};

For every

a∈𝒜a\\in\\mathcal\{A\}, select any value

g~t​\(a∣𝐜t\)\\widetilde\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)from the confidence interval

\[g¯t​\(a∣𝐜t\),g¯t​\(a∣𝐜t\)\]\\left\[\\underline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\),\\overline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\right\]in Lemma[4](https://arxiv.org/html/2607.15577#Thmlemma4), using

δ=δ′2​T​\|𝒜\|\\delta=\\frac\{\\delta^\{\\prime\}\}\{2T\|\\mathcal\{A\}\|\};

Set

Δ→t​\(𝐜t\):=\[Δ~t​\(a∣𝐜t\)\]a∈𝒜\\vec\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\):=\[\\widetilde\{\\Delta\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\]\_\{a\\in\\mathcal\{A\}\};

Set

g→t​\(𝐜t\):=\[g~t​\(a∣𝐜t\)\]a∈𝒜\\vec\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\):=\[\\widetilde\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\]\_\{a\\in\\mathcal\{A\}\};

at←IDSAction​\(𝒜,Δ→t​\(𝐜t\),g→t​\(𝐜t\)\)a\_\{t\}\\leftarrow\\text\{IDSAction\}\\\!\\left\(\\mathcal\{A\},\\vec\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\),\\vec\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\\right\);

Play action

ata\_\{t\}, observe the reward and all non\-intervened variables, and update the history

ℱt\+1\\mathcal\{F\}\_\{t\+1\};

Algorithm 2Information\-Directed Sampling for Causal Bandits with Non\-Manipulable VariablesWe use an example to illustrate why the quantitygt​\(a∣𝐜t\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{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 interventiond​o​\(\)do\(\)is the most informative about the parameter𝜽\\boldsymbol\{\\theta\}, 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=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\. Consider a simple causal graph in whichX→YX\\rightarrow Y\. The quantities relevant for identifying the optimal action are the context\-dependent conditional probabilitiesP\(Y=1∣X=0,𝐜t\)P\(Y=1\\mid X=0,\\mathbf\{c\}\_\{t\}\)andP\(Y=1∣X=1,𝐜t\)P\(Y=1\\mid X=1,\\mathbf\{c\}\_\{t\}\)\. IfP​\(X=0∣𝐜t\)P\(X=0\\mid\\mathbf\{c\}\_\{t\}\)is small relative toP​\(X=1∣𝐜t\)P\(X=1\\mid\\mathbf\{c\}\_\{t\}\), then samples drawn from the observational distribution will rarely provide information about the behavior ofYYwhenX=0X=0under that context\. In such a case, performing the interventiond​o​\(X=0\)do\(X=0\)may be substantially more informative thand​o​\(\)do\(\)for determining the optimal actionΠ⋆​\(𝐜t\)\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)\. This distinction is precisely captured bygt​\(a∣𝐜t\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\), which measures the expected reduction in posterior uncertainty aboutΠ⋆​\(𝐜t\)\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)resulting from selecting actionaa\. We now proceed to formally derive the expressions needed to computeΔt​\(a∣𝐜t\)\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)andgt​\(a∣𝐜t\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\.

###### Lemma 2\.

The information gain associated with an actiona∈𝒜a\\in\\mathcal\{A\}at time steptt, conditional on the realized context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}, is given by

gt\(a∣𝐜t\)=DKL\(Pt𝐜t\(Π⋆\(𝐜t\),Ya\)∥Pt𝐜t\(Π⋆\(𝐜t\)\)Pt𝐜t\(Ya\)\)\.g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=D\_\{\\mathrm\{KL\}\}\\\!\\left\(P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\),Y\_\{a\}\\right\)\\,\\middle\\\|\\,P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)\\right\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\\\!\\left\(Y\_\{a\}\\right\)\\right\)\.\(4\)The corresponding posterior distributions satisfy

Pt𝐜t​\(Π⋆​\(𝐜t\)=a⋆\)=𝔼𝜽∼Pt𝐜t​\(𝜽\)​\[𝟙​\{a⋆=arg⁡maxa′∈𝒜⁡μ𝜽​\(a′,𝐜t\)\}\],P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\\star\}\\right\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\)\}\\left\[\\mathbbm\{1\}\\\!\\left\\\{a^\{\\star\}=\\arg\\max\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\mu\_\{\\boldsymbol\{\\theta\}\}\(a^\{\\prime\},\\mathbf\{c\}\_\{t\}\)\\right\\\}\\right\],\(5\)Pt𝐜t​\(Ya=y\)=𝔼𝜽∼Pt𝐜t​\(𝜽\)​\[P​\(Ya=y∣𝜽,𝐜t\)\],P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\\\!\\left\(Y\_\{a\}=y\\right\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\)\}\\left\[P\\\!\\left\(Y\_\{a\}=y\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\\right\)\\right\],\(6\)and

Pt𝐜t​\(Π⋆​\(𝐜t\)=a⋆,Ya=y\)\\displaystyle P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\\star\},Y\_\{a\}=y\\right\)=𝔼𝜽∼Pt𝐜t​\(𝜽\)​\[𝟙​\{a⋆=arg⁡maxa′∈𝒜⁡μ𝜽​\(a′,𝐜t\)\}​P​\(Ya=y∣𝜽,𝐜t\)\],\\displaystyle\\qquad=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\)\}\\left\[\\mathbbm\{1\}\\\!\\left\\\{a^\{\\star\}=\\arg\\max\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\mu\_\{\\boldsymbol\{\\theta\}\}\(a^\{\\prime\},\\mathbf\{c\}\_\{t\}\)\\right\\\}P\\\!\\left\(Y\_\{a\}=y\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\\right\)\\right\],\(7\)for everya⋆∈𝒜a^\{\\star\}\\in\\mathcal\{A\}andy∈\{0,1\}y\\in\\\{0,1\\\}\.

Moreover, the expected instantaneous regret associated with actionaaat time stepttunder context𝐜t\\mathbf\{c\}\_\{t\}is

Δt​\(a∣𝐜t\)\\displaystyle\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=𝔼𝜽∼Pt𝐜t​\(𝜽\)\[∑a⋆∈𝒜𝟙\{a⋆=argmaxa′∈𝒜μ𝜽\(a′,𝐜t\)\}\\displaystyle=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\)\}\\Bigg\[\\sum\_\{a^\{\\star\}\\in\\mathcal\{A\}\}\\mathbbm\{1\}\\\!\\left\\\{a^\{\\star\}=\\arg\\max\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\mu\_\{\\boldsymbol\{\\theta\}\}\(a^\{\\prime\},\\mathbf\{c\}\_\{t\}\)\\right\\\}×P\(Ya⋆=1∣𝜽,𝐜t\)−P\(Ya=1∣𝜽,𝐜t\)\]\.\\displaystyle\\hskip 99\.58464pt\\times P\\\!\\left\(Y\_\{a^\{\\star\}\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\\right\)\-P\\\!\\left\(Y\_\{a\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\\right\)\\Bigg\]\.\(8\)

When the parameter space is finite and discrete, the quantitiesgt​\(a∣𝐜t\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)andΔt​\(a∣𝐜t\)\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)can be evaluated exactly by summing over all possible values of𝜽\\boldsymbol\{\\theta\}\. In our contextual causal bandit setting, however,𝜽\\boldsymbol\{\\theta\}parameterizes the observational distribution and belongs to a continuous probability simplex\. Consequently, the posterior expectations defininggt​\(a∣𝐜t\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)andΔt​\(a∣𝐜t\)\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)are generally analytically intractable\. We therefore approximate these quantities using Monte Carlo samples drawn from the context\-conditioned posterior distributionPt𝐜t​\(𝜽\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\)\. The following results control the approximation error introduced by this sampling procedure\.

###### Lemma 3\(Concentration of the Expected Regret\)\.

Fix a time steptt, a realized context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}, an actiona∈𝒜a\\in\\mathcal\{A\}, andδ∈\(0,1\)\\delta\\in\(0,1\)\. LetΔ^t​\(a∣𝐜t\)\\widehat\{\\Delta\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)be the Monte Carlo estimator ofΔt​\(a∣𝐜t\)\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)computed usingNNindependent samples fromPt𝐜t​\(𝛉\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\)\. Then, with probability at least1−δ1\-\\delta,

\|Δ^t\(a∣𝐜t\)−Δt\(a∣𝐜t\)\|≤2N​log⁡\(2δ\)\.\\left\|\\widehat\{\\Delta\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\-\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\right\|\\leq\\sqrt\{\\frac\{2\}\{N\}\\log\\\!\\left\(\\frac\{2\}\{\\delta\}\\right\)\}\.

To control the Monte Carlo approximation error in the information gain, we derive simultaneous concentration bounds for the posterior probabilitiesPt𝐜t​\(Π⋆​\(𝐜t\)=a⋆\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\\star\}\),Pt𝐜t​\(Ya=y\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(Y\_\{a\}=y\), andPt𝐜t​\(Π⋆​\(𝐜t\)=a⋆,Ya=y\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\\star\},Y\_\{a\}=y\)\. These bounds yield computable lower and upper confidence bounds forgt​\(a∣𝐜t\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)that hold uniformly over all actions\.

###### Lemma 4\(Concentration of the Information Gain\)\.

Fix a time steptt, a realized context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}, andδ∈\(0,1\)\\delta\\in\(0,1\)\. For eacha∈𝒜a\\in\\mathcal\{A\}, letg¯t​\(a∣𝐜t\)\\underline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)andg¯t​\(a∣𝐜t\)\\overline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)denote the lower and upper confidence bounds defined in \([35](https://arxiv.org/html/2607.15577#A1.E35)\) and \([33](https://arxiv.org/html/2607.15577#A1.E33)\), respectively, and constructed usingNNindependent samples from the context\-conditioned posterior distributionPt𝐜t​\(𝛉\)P\_\{t\}^\{\\mathbf\{c\}\_\{t\}\}\(\\boldsymbol\{\\theta\}\)\. Then, with probability at least1−δ1\-\\deltaover the Monte Carlo samples,

g¯t​\(a∣𝐜t\)≤gt​\(a∣𝐜t\)≤g¯t​\(a∣𝐜t\),∀a∈𝒜\.\\underline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\leq g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\leq\\overline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\),\\qquad\\forall a\\in\\mathcal\{A\}\.

The proof of Lemma[4](https://arxiv.org/html/2607.15577#Thmlemma4), together with the explicit construction of the confidence bounds, is provided in Appendix[A\.6](https://arxiv.org/html/2607.15577#A1.SS6)\.

###### Theorem 2\.

Fixδ′∈\(0,1\)\\delta^\{\\prime\}\\in\(0,1\)and a horizonT∈ℕT\\in\\mathbb\{N\}\. With probability at least1−δ′1\-\\delta^\{\\prime\}over the Monte Carlo samples used by Algorithm[2](https://arxiv.org/html/2607.15577#alg2), the Bayesian regret satisfies

𝔼​\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\]≤H​\(Π⋆\)​\(T​\|𝒜\|2\+2​∑t=1Tγt\)\.\\displaystyle\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\right\]\\leq\\sqrt\{H\(\\Pi^\{\\star\}\)\\left\(\\frac\{T\|\\mathcal\{A\}\|\}\{2\}\+2\\sum\_\{t=1\}^\{T\}\\gamma\_\{t\}\\right\)\}\.\(9\)Here, for each time steptt,

γt:=supπ∈S\|𝒜\|,𝚫t1​\(𝐜t\),𝚫t2​\(𝐜t\)∈𝒞tΔ​\(𝐜t\),𝒈t1​\(𝐜t\),𝒈t2​\(𝐜t\)∈𝒞tg​\(𝐜t\)\|\(π⊤​𝚫t1​\(𝐜t\)\)2π⊤​𝒈t1​\(𝐜t\)−\(π⊤​𝚫t2​\(𝐜t\)\)2π⊤​𝒈t2​\(𝐜t\)\|,\\gamma\_\{t\}:=\\sup\_\{\\begin\{subarray\}\{c\}\\pi\\in S\_\{\|\\mathcal\{A\}\|\},\\\\ \\boldsymbol\{\\Delta\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\),\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)\\in\\mathcal\{C\}^\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\),\\\\ \\boldsymbol\{g\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\),\\boldsymbol\{g\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)\\in\\mathcal\{C\}^\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\\end\{subarray\}\}\\left\|\\frac\{\\left\(\\pi^\{\\top\}\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\)\\right\)^\{2\}\}\{\\pi^\{\\top\}\\boldsymbol\{g\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\)\}\-\\frac\{\\left\(\\pi^\{\\top\}\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)\\right\)^\{2\}\}\{\\pi^\{\\top\}\\boldsymbol\{g\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)\}\\right\|,\(10\)where

S\|𝒜\|:=\{π∈ℝ\+\|𝒜\|:∑a∈𝒜π​\(a\)=1\}\.S\_\{\|\\mathcal\{A\}\|\}:=\\left\\\{\\pi\\in\\mathbb\{R\}^\{\|\\mathcal\{A\}\|\}\_\{\+\}:\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\(a\)=1\\right\\\}\.The vectors𝚫t1​\(𝐜t\)\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\)and𝚫t2​\(𝐜t\)\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)range over the componentwise confidence set\(𝒞tΔ​\(𝐜t\)\)\(\\mathcal\{C\}^\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\)obtained from Lemma[3](https://arxiv.org/html/2607.15577#Thmlemma3), while𝐠t1​\(𝐜t\)\\boldsymbol\{g\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\)and𝐠t2​\(𝐜t\)\\boldsymbol\{g\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)range over the componentwise confidence set\(𝒞tg​\(𝐜t\)\)\(\\mathcal\{C\}^\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\)obtained from Lemma[4](https://arxiv.org/html/2607.15577#Thmlemma4), all evaluated at the realized context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\. Both confidence sets are constructed usingδ=δ′2​T​\|𝒜\|\\delta=\\frac\{\\delta^\{\\prime\}\}\{2T\|\\mathcal\{A\}\|\}\. The expectation in \([9](https://arxiv.org/html/2607.15577#S6.E9)\) 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](https://arxiv.org/html/2607.15577#alg2)\)\. Theorem[2](https://arxiv.org/html/2607.15577#Thmtheorem2)provides a Bayesian regret bound in which the additional term involvingγt\\gamma\_\{t\}quantifies the effect of computing the information ratio using Monte Carlo estimates\. The widths of the confidence intervals in Lemma[3](https://arxiv.org/html/2607.15577#Thmlemma3)and Lemma[4](https://arxiv.org/html/2607.15577#Thmlemma4)scale asO​\(log⁡\(c/δ\)/N\)O\\\!\\left\(\\sqrt\{\\log\(c/\\delta\)/N\}\\right\)for an appropriate constantcc\. Therefore, increasing the posterior sample sizeNNshrinks the confidence sets and can only decrease, or leave unchanged,γt\\gamma\_\{t\}\. Similarly, decreasingδ\\deltaproduces a higher\-confidence guarantee but wider confidence intervals, which can increaseγt\\gamma\_\{t\}, whereas increasingδ\\deltaproduces narrower intervals and can decreaseγt\\gamma\_\{t\}\. In Theorem[2](https://arxiv.org/html/2607.15577#Thmtheorem2), the choiceδ=δ′/\(2​T​\|𝒜\|\)\\delta=\\delta^\{\\prime\}/\(2T\|\\mathcal\{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 asNNincreases, and consequentlyγt\\gamma\_\{t\}approaches zero\. Thus,γt\\gamma\_\{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\\gamma\_\{t\}=0for everytt\.

###### 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\\gamma\_\{t\}=0for alltt\. Then, for anyT∈ℕT\\in\\mathbb\{N\}, the mean cumulative regret of Algorithm[2](https://arxiv.org/html/2607.15577#alg2)satisfies

𝔼​\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\]≤\|𝒜\|2​T​H​\(Π⋆\)\.\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\right\]\\leq\\sqrt\{\\frac\{\|\\mathcal\{A\}\|\}\{2\}\\,T\\,H\(\\Pi^\{\\star\}\)\}\.

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](https://arxiv.org/html/2607.15577#S7.F2)\(a\), consisting of the binary nodesXX,YY, andZZ, with edgesX→YX\\to Y,Z→XZ\\to X, andZ→YZ\\to Y, whereYYis the reward node andZZis non\-manipulable\. There is no context variable in this example\. BecauseZZcannot be manipulated, the feasible intervention set is𝒜=\{d​o​\(\),d​o​\(X=1\),d​o​\(X=0\)\}\\mathcal\{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Π⋆\\Pi^\{\\star\}\. Assuming no prior observations, we place independentBeta⁡\(1,1\)\\operatorname\{Beta\}\(1,1\)priors on the Bernoulli parameters in each row of the conditional probability tables and estimateP​\(Π⋆=a\)P\(\\Pi^\{\\star\}=a\)usingN=50,000N=50\{,\}000Monte Carlo samples\. We obtainP​\(Π⋆=d​o​\(\)\)≈0\.08P\(\\Pi^\{\\star\}=do\(\)\)\\approx 0\.08,P​\(Π⋆=d​o​\(X=1\)\)≈0\.46P\(\\Pi^\{\\star\}=do\(X=1\)\)\\approx 0\.46, andP​\(Π⋆=d​o​\(X=0\)\)≈0\.46P\(\\Pi^\{\\star\}=do\(X=0\)\)\\approx 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\\pm 0\.0093at overall confidence level0\.9990\.999\. The resulting entropy isH​\(Π⋆\)=−∑a∈𝒜P​\(Π⋆=a\)​log⁡P​\(Π⋆=a\)≈0\.9165H\(\\Pi^\{\\star\}\)=\-\\sum\_\{a\\in\\mathcal\{A\}\}P\(\\Pi^\{\\star\}=a\)\\log P\(\\Pi^\{\\star\}=a\)\\approx 0\.9165, which is strictly smaller than the worst\-case valuelog⁡\|𝒜\|=log⁡3≈1\.0986\\log\|\\mathcal\{A\}\|=\\log 3\\approx 1\.0986\. Consequently, the oracle IDS regret bound becomes𝔼​\[RegT\]≤3​H​\(Π⋆\)​T/2≈1\.1725​T\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leq\\sqrt\{3H\(\\Pi^\{\\star\}\)T/2\}\\approx 1\.1725\\sqrt\{T\}, whereas the worst\-case uniform\-prior benchmark is3​log⁡\(3\)​T/2≈1\.2837​T\\sqrt\{3\\log\(3\)T/2\}\\approx 1\.2837\\sqrt\{T\}\. Thus, in this example, the causal model reduces the leading regret coefficient by approximately8\.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\|\\mathcal\{A\}\|/2\.

## 7Experiments

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](https://arxiv.org/html/2607.15577#S7.F2), where red nodes denote non\-manipulable variables,CCdenotes a context variable, andYYdenotes the reward variable\. ForTask 1\(Figure[2](https://arxiv.org/html/2607.15577#S7.F2)\(a\)\), the set of POMISs after the projection step is\{∅,\{X\}\}\\\{\\emptyset,\\\{X\\\}\\\}, resulting in the possibly optimal armsd​o​\(\)do\(\),d​o​\(X=0\)do\(X=0\), andd​o​\(X=1\)do\(X=1\)\. ForTask 2\(Figure[2](https://arxiv.org/html/2607.15577#S7.F2)\(b\)\), the set of POMISs is\{\{X1\},\{X2\}\}\\\{\\\{X\_\{1\}\\\},\\\{X\_\{2\}\\\}\\\}, yielding the possibly optimal armsd​o​\(X1=0\)do\(X\_\{1\}=0\),d​o​\(X1=1\)do\(X\_\{1\}=1\),d​o​\(X2=0\)do\(X\_\{2\}=0\), andd​o​\(X2=1\)do\(X\_\{2\}=1\)\. ForTask 3\(Figure[2](https://arxiv.org/html/2607.15577#S7.F2)\(c\)\), the set of POMISs is\{∅,\{X1\},\{X2\},\{X1,X2\}\}\\\{\\emptyset,\\\{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 inLee and Bareinboim \([2019](https://arxiv.org/html/2607.15577#bib.bib52)\), which usesz2z^\{2\}ID 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](https://arxiv.org/html/2607.15577#S7.F3)\. 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 toN=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\)Task11X2X\_\{2\}YYX1X\_\{1\}CCZZ\(b\)Task22X1X\_\{1\}YYX2X\_\{2\}X3X\_\{3\}Z1Z\_\{1\}Z2Z\_\{2\}CC\(c\)Task33
Figure 2:Causal graphs used in the experiments![Refer to caption](https://arxiv.org/html/2607.15577v1/pts1.png)\(a\)Task11
![Refer to caption](https://arxiv.org/html/2607.15577v1/pts2.png)\(b\)Task22
![Refer to caption](https://arxiv.org/html/2607.15577v1/pts3.png)\(c\)Task33

Figure 3:Regret versus time for the three tasks with the corresponding causal graphs shown in Figure[2](https://arxiv.org/html/2607.15577#S7.F2)![Refer to caption](https://arxiv.org/html/2607.15577v1/pts11.png)\(a\)N𝒢=10,ρ=0\.1N\_\{\\mathcal\{G\}\}=10,\\rho=0\.1
![Refer to caption](https://arxiv.org/html/2607.15577v1/pts22.png)\(b\)N𝒢=15,ρ=0\.1N\_\{\\mathcal\{G\}\}=15,\\rho=0\.1
![Refer to caption](https://arxiv.org/html/2607.15577v1/pts33.png)\(c\)N𝒢=15,ρ=0\.2N\_\{\\mathcal\{G\}\}=15,\\rho=0\.2

Figure 4:Regret versus time for Erdős–Rényi random chordal graphs with varying graph densityWe further compare our proposed algorithms with the baseline methods on Erdős–Rényi random chordal graphs with varying numbers of nodesN𝒢N\_\{\\mathcal\{G\}\}and graph densitiesρ\\rho\. 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](https://arxiv.org/html/2607.15577#S7.F4), and the graph\-generation procedure is described in Section[A\.10](https://arxiv.org/html/2607.15577#A1.SS10)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](https://arxiv.org/html/2607.15577#A1.SS9)of the supplementary material, further illustrating the applicability of the proposed framework\.

## 8Conclusion

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\.

## 9Acknowledgements

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\.InProceedings of the 24th annual conference on learning theory,pp\. 359–376\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p1.1)\.
- D\. Heckerman, C\. Meek, and G\. Cooper \(2006\)A bayesian approach to causal discovery\.Innovations in Machine Learning: Theory and Applications,pp\. 1–28\.Cited by:[§4](https://arxiv.org/html/2607.15577#S4.p5.5)\.
- K\. Jamieson, M\. Malloy, R\. Nowak, and S\. Bubeck \(2014\)Lil’UCB: an optimal exploration algorithm for multi\-armed bandits\.InConference on Learning Theory,pp\. 423–439\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p1.1)\.
- K\. Jamieson and R\. Nowak \(2014\)Best\-arm identification algorithms for multi\-armed bandits in the fixed confidence setting\.In2014 48th annual conference on information sciences and systems \(CISS\),pp\. 1–6\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p1.1)\.
- K\. Jun and C\. Zhang \(2020\)Crush optimism with pessimism: structured bandits beyond asymptotic optimality\.Advances in Neural Information Processing Systems33,pp\. 6366–6376\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p2.1)\.
- D\. Koller and N\. Friedman \(2009\)Probabilistic graphical models: principles and techniques\.MIT press\.Cited by:[§A\.10](https://arxiv.org/html/2607.15577#A1.SS10.p3.1)\.
- F\. Lattimore, T\. Lattimore, and M\. D\. Reid \(2016\)Causal bandits: learning good interventions via causal inference\.InAdvances in Neural Information Processing Systems,pp\. 1181–1189\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p3.1)\.
- T\. Lattimore and C\. Szepesvári \(2020\)Bandit algorithms\.Cambridge University Press\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p1.1)\.
- S\. Lee and E\. Bareinboim \(2018\)Structural causal bandits: where to intervene?\.InAdvances in Neural Information Processing Systems 31,S\. Bengio, H\. Wallach, H\. Larochelle, K\. Grauman, N\. Cesa\-Bianchi, and R\. Garnett \(Eds\.\),pp\. 2573–2583\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p3.1),[Definition 1](https://arxiv.org/html/2607.15577#Thmdefinition1.p1.10.10),[Definition 2](https://arxiv.org/html/2607.15577#Thmdefinition2.p1.7.7),[Lemma 1](https://arxiv.org/html/2607.15577#Thmlemma1.p1.4)\.
- S\. Lee and E\. Bareinboim \(2019\)Structural causal bandits with non\-manipulable variables\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.33,pp\. 4164–4172\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p5.1),[§3](https://arxiv.org/html/2607.15577#S3.p1.2),[§3](https://arxiv.org/html/2607.15577#S3.p3.19),[§7](https://arxiv.org/html/2607.15577#S7.p2.2)\.
- A\. J\. Mersereau, P\. Rusmevichientong, and J\. N\. Tsitsiklis \(2009\)A structured multiarmed bandit problem and the greedy policy\.IEEE Transactions on Automatic Control54\(12\),pp\. 2787–2802\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p2.1)\.
- J\. Pearl \(2009\)Causality\.Cambridge University Press\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p3.1),[§2](https://arxiv.org/html/2607.15577#S2.p1.18),[§4](https://arxiv.org/html/2607.15577#S4.p3.10)\.
- M\. Qasim Elahi, M\. Ghasemi, and M\. Kocaoglu \(2024\)Partial structure discovery is sufficient for no\-regret learning in causal bandits\.arXiv e\-prints,pp\. arXiv–2411\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p3.1)\.
- D\. Russo and B\. Van Roy \(2014\)Learning to optimize via information\-directed sampling\.Advances in neural information processing systems27\.Cited by:[§A\.1](https://arxiv.org/html/2607.15577#A1.SS1.p2.1),[§1](https://arxiv.org/html/2607.15577#S1.p7.2)\.
- D\. Russo and B\. Van Roy \(2016\)An information\-theoretic analysis of thompson sampling\.Journal of Machine Learning Research17\(68\),pp\. 1–30\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p7.2),[§5](https://arxiv.org/html/2607.15577#S5.p2.14)\.
- E\. Schulz, N\. T\. Franklin, and S\. J\. Gershman \(2020\)Finding structure in multi\-armed bandits\.Cognitive psychology119,pp\. 101261\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p2.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](https://arxiv.org/html/2607.15577#S1.p3.1)\.
- A\. Slivkinset al\.\(2019\)Introduction to multi\-armed bandits\.Foundations and Trends® in Machine Learning12\(1\-2\),pp\. 1–286\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p1.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 Systems33,pp\. 21500–21511\.Cited by:[§A\.10](https://arxiv.org/html/2607.15577#A1.SS10.p3.1)\.
- W\. R\. Thompson \(1933\)On the likelihood that one unknown probability exceeds another in view of the evidence of two samples\.Biometrika25\(3/4\),pp\. 285–294\.Cited by:[§5](https://arxiv.org/html/2607.15577#S5.p1.9)\.
- J\. Tian and J\. Pearl \(2002\)A general identification condition for causal effects\.InAaai/iaai,pp\. 567–573\.Cited by:[§2](https://arxiv.org/html/2607.15577#S2.p2.28)\.
- A\. Tirinzoni, A\. Lazaric, and M\. Restelli \(2020\)A novel confidence\-based algorithm for structured bandits\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 3175–3185\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p2.1)\.
- B\. Van Parys and N\. Golrezaei \(2024\)Optimal learning for structured bandits\.Management Science70\(6\),pp\. 3951–3998\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p2.1)\.
- J\. Vermorel and M\. Mohri \(2005\)Multi\-armed bandit algorithms and empirical evaluation\.InEuropean conference on machine learning,pp\. 437–448\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p1.1)\.
- R\. Wan, L\. Ge, and R\. Song \(2023\)Towards scalable and robust structured bandits: a meta\-learning framework\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 1144–1173\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p2.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 Systems36\.Cited by:[§1](https://arxiv.org/html/2607.15577#S1.p3.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](https://arxiv.org/html/2607.15577#S1.p3.1)\.

## Appendix ASupplementary Material

In the following subsections, we provide comprehensive and formal mathematical proofs for the the theorems presented in the main paper\.

### A\.1Optimizing the Contextual Information Ratio

Ifg→t​\(𝐜t\)=0→\\vec\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)=\\vec\{0\}, then none of the available actions provides information about the optimal action under context𝐜t\\mathbf\{c\}\_\{t\}\. In this case, we select an action that minimizes the expected instantaneous regret\. Otherwise, at timettwe select an action by solving

minπ∈S\|𝒜\|⁡\(π⊤​Δ→t​\(𝐜t\)\)2π⊤​g→t​\(𝐜t\),\\min\_\{\\pi\\in S\_\{\|\\mathcal\{A\}\|\}\}\\frac\{\\left\(\\pi^\{\\top\}\\vec\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\\right\)^\{2\}\}\{\\pi^\{\\top\}\\vec\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\},\(11\)whereS\|𝒜\|=\{π∈ℝ\+\|𝒜\|:∑kπk=1\}S\_\{\|\\mathcal\{A\}\|\}=\\\{\\pi\\in\\mathbb\{R\}\_\{\+\}^\{\|\\mathcal\{A\}\|\}:\\sum\_\{k\}\\pi\_\{k\}=1\\\}is the probability simplex\. We use the conventions0/0:=00/0:=0andx/0:=\+∞x/0:=\+\\inftyforx\>0x\>0\.

Russo and Van RoyRusso and Van Roy \[[2014](https://arxiv.org/html/2607.15577#bib.bib59)\]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\)\\mathcal\{A\},\\vec\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\),\\vec\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)*\)*:

if*g→t​\(𝐜t\)=0→\\vec\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)=\\vec\{0\}*then

returnan action

a∗∈arg⁡mina∈𝒜⁡Δt​\(a∣𝐜t\)a^\{\*\}\\in\\arg\\min\_\{a\\in\\mathcal\{A\}\}\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\.

For each pair

a,a′∈𝒜a,a^\{\\prime\}\\in\\mathcal\{A\}such that

a≠a′a\\neq a^\{\\prime\}compute

qa,a′←arg⁡minq∈\[0,1\]⁡\(q​Δt​\(a∣𝐜t\)\+\(1−q\)​Δt​\(a′∣𝐜t\)\)2q​gt​\(a∣𝐜t\)\+\(1−q\)​gt​\(a′∣𝐜t\)\.q\_\{a,a^\{\\prime\}\}\\leftarrow\\arg\\min\_\{q\\in\[0,1\]\}\\frac\{\\left\(q\\,\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\+\(1\-q\)\\,\\Delta\_\{t\}\(a^\{\\prime\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\)^\{2\}\}\{q\\,g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\+\(1\-q\)\\,g\_\{t\}\(a^\{\\prime\}\\mid\\mathbf\{c\}\_\{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^\{\*\*\}\)\\leftarrow\\arg\\min\_\{a\\neq a^\{\\prime\}\}\\frac\{\\left\(q\_\{a,a^\{\\prime\}\}\\,\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\+\(1\-q\_\{a,a^\{\\prime\}\}\)\\,\\Delta\_\{t\}\(a^\{\\prime\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\)^\{2\}\}\{q\_\{a,a^\{\\prime\}\}\\,g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\+\(1\-q\_\{a,a^\{\\prime\}\}\)\\,g\_\{t\}\(a^\{\\prime\}\\mid\\mathbf\{c\}\_\{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 3Function to optimize the contextual information ratio
### A\.2Proof of Theorem[1](https://arxiv.org/html/2607.15577#S5.Ex2)

𝔼​\[RegT\]=𝔼​\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\]=𝔼​\[∑t=1T𝔼t​\[YΠ⋆​\(𝐂t\),t−YAt,t∣𝐂t\]\]\.\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]=\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\right\]=\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{t\}\\\!\\left\[Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\mid\\mathbf\{C\}\_\{t\}\\right\]\\right\]\.\(12\)
We introduce a nonnegative constantΓt\\Gamma\_\{t\}such that the per\-round regret satisfies

𝔼t​\[YΠ⋆​\(𝐂t\),t−YAt,t∣𝐂t\]≤Γt​It​\(Π⋆​\(𝐂t\);\(At,YAt,t\)∣𝐂t\)\.\\mathbb\{E\}\_\{t\}\\\!\\left\[Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\mid\\mathbf\{C\}\_\{t\}\\right\]\\leq\\Gamma\_\{t\}\\sqrt\{I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)\}\.\(13\)
Then,

𝔼​\[RegT\]\\displaystyle\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]≤𝔼​\[∑t=1TΓt​It​\(Π⋆​\(𝐂t\);\(At,YAt,t\)∣𝐂t\)\]\\displaystyle\\leq\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\Gamma\_\{t\}\\sqrt\{I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)\}\\right\]≤Γ​𝔼​\[∑t=1TIt​\(Π⋆​\(𝐂t\);\(At,YAt,t\)∣𝐂t\)\]\\displaystyle\\leq\\Gamma\\,\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\sqrt\{I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)\}\\right\]≤Γ​T​𝔼​\[∑t=1TIt​\(Π⋆​\(𝐂t\);\(At,YAt,t\)∣𝐂t\)\]\.\\displaystyle\\leq\\Gamma\\sqrt\{T\\,\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)\\right\]\}\.
The second inequality follows from the assumption thatΓ≥Γt\\Gamma\\geq\\Gamma\_\{t\}for allt∈ℕt\\in\\mathbb\{N\}, and the third inequality follows from the Cauchy–Schwarz and Jensen inequalities\.

SinceΠ⋆​\(𝐂t\)\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\)is a deterministic function of the full optimal\-action mappingΠ⋆\\Pi^\{\\star\}, the data\-processing inequality gives

It​\(Π⋆​\(𝐂t\);\(At,YAt,t\)∣𝐂t\)≤It​\(Π⋆;\(At,YAt,t\)∣𝐂t\)\.I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)\\leq I\_\{t\}\\\!\\left\(\\Pi^\{\\star\};\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)\.\(14\)
Let𝒪t\\mathcal\{O\}\_\{t\}denote the complete observation collected at timett, including𝐂t\\mathbf\{C\}\_\{t\},AtA\_\{t\},YAt,tY\_\{A\_\{t\},t\}, and all observed non\-intervened variables, so thatℱt\+1=σ​\(ℱt,𝒪t\)\\mathcal\{F\}\_\{t\+1\}=\\sigma\(\\mathcal\{F\}\_\{t\},\\mathcal\{O\}\_\{t\}\)\. By the chain rule for mutual information,

It​\(Π⋆;\(At,YAt,t\)∣𝐂t\)≤It​\(Π⋆;𝒪t\)\.I\_\{t\}\\\!\\left\(\\Pi^\{\\star\};\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)\\leq I\_\{t\}\\\!\\left\(\\Pi^\{\\star\};\\mathcal\{O\}\_\{t\}\\right\)\.\(15\)
By the definition of conditional mutual information,

It​\(Π⋆;𝒪t\)=H​\(Π⋆∣ℱt\)−𝔼​\[H​\(Π⋆∣ℱt\+1\)∣ℱt\]\.I\_\{t\}\\\!\\left\(\\Pi^\{\\star\};\\mathcal\{O\}\_\{t\}\\right\)=H\\\!\\left\(\\Pi^\{\\star\}\\mid\\mathcal\{F\}\_\{t\}\\right\)\-\\mathbb\{E\}\\\!\\left\[H\\\!\\left\(\\Pi^\{\\star\}\\mid\\mathcal\{F\}\_\{t\+1\}\\right\)\\mid\\mathcal\{F\}\_\{t\}\\right\]\.
Summing overttyields a telescoping series:

𝔼​\[∑t=1TIt​\(Π⋆​\(𝐂t\);\(At,YAt,t\)∣𝐂t\)\]≤H​\(Π⋆\)−𝔼​\[H​\(Π⋆∣ℱT\+1\)\]≤H​\(Π⋆\)\.\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}\\right\)\\right\]\\leq H\(\\Pi^\{\\star\}\)\-\\mathbb\{E\}\\\!\\left\[H\\\!\\left\(\\Pi^\{\\star\}\\mid\\mathcal\{F\}\_\{T\+1\}\\right\)\\right\]\\leq H\(\\Pi^\{\\star\}\)\.\(16\)
Substituting this bound gives

𝔼​\[RegT\]≤Γ​H​\(Π⋆\)​T\.\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leq\\Gamma\\sqrt\{H\(\\Pi^\{\\star\}\)\\,T\}\.\(17\)
This completes the proof of Theorem[1](https://arxiv.org/html/2607.15577#S5.Ex2)\.

### A\.3Proof of Corollary[1](https://arxiv.org/html/2607.15577#S5.Ex3)

We fix a realization ofℱt\\mathcal\{F\}\_\{t\}and condition on the realized context𝐂t=𝐜\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\. Writepa:=Pt​\(Π⋆​\(𝐜\)=a∣𝐂t=𝐜\)p\_\{a\}:=P\_\{t\}\(\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\. By the TS posterior\-matching property,Pt​\(At=a∣𝐂t=𝐜\)=paP\_\{t\}\(A\_\{t\}=a\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)=p\_\{a\}\. Moreover, conditional onℱt\\mathcal\{F\}\_\{t\}and𝐂t=𝐜\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}, the actionAtA\_\{t\}and the optimal actionΠ⋆​\(𝐜\)\\Pi^\{\\star\}\(\\mathbf\{c\}\)are independent becauseAtA\_\{t\}is generated using an independent posterior sample\. Also letK=\|𝒜\|K=\|\\mathcal\{A\}\|be the total number of actions\.

Define the posterior mean reward of actionaaat context𝐜\\mathbf\{c\}:

μ¯a:=Et​\[Ya,t∣𝐂t=𝐜\]\.\\bar\{\\mu\}\_\{a\}:=E\_\{t\}\[Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\]\.Also define the posterior mean reward under the optimal action for that context:

μ¯⋆:=Et​\[YΠ⋆​\(𝐜\),t∣𝐂t=𝐜\]=∑a∈𝒜pa​Et​\[Ya,t∣Π⋆​\(𝐜\)=a,𝐂t=𝐜\]\.\\bar\{\\mu\}^\{\\star\}:=E\_\{t\}\[Y\_\{\\Pi^\{\\star\}\(\\mathbf\{c\}\),t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\]=\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{a\}\\,E\_\{t\}\[Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\]\.
Then the conditional instantaneous regret is

Δt​\(𝐜\)\\displaystyle\\Delta\_\{t\}\(\\mathbf\{c\}\):=Et​\[YΠ⋆​\(𝐜\),t−YAt,t∣𝐂t=𝐜\]\\displaystyle:=E\_\{t\}\\\!\\left\[Y\_\{\\Pi^\{\\star\}\(\\mathbf\{c\}\),t\}\-Y\_\{A\_\{t\},t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\\right\]=μ¯⋆−∑a∈𝒜Pt​\(At=a∣𝐂t=𝐜\)​μ¯a\\displaystyle=\\bar\{\\mu\}^\{\\star\}\-\\sum\_\{a\\in\\mathcal\{A\}\}P\_\{t\}\(A\_\{t\}=a\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\,\\bar\{\\mu\}\_\{a\}=∑a∈𝒜pa​\(Et​\[Ya,t∣Π⋆​\(𝐜\)=a,𝐂t=𝐜\]−μ¯a\)\.\\displaystyle=\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{a\}\\left\(E\_\{t\}\[Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\]\-\\bar\{\\mu\}\_\{a\}\\right\)\.\(18\)
Applying the Cauchy–Schwarz inequality gives

Δt​\(𝐜\)2\\displaystyle\\Delta\_\{t\}\(\\mathbf\{c\}\)^\{2\}≤K​∑a∈𝒜pa2​\(Et​\[Ya,t∣Π⋆​\(𝐜\)=a,𝐂t=𝐜\]−μ¯a\)2\.\\displaystyle\\leq K\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{a\}^\{2\}\\left\(E\_\{t\}\[Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\]\-\\bar\{\\mu\}\_\{a\}\\right\)^\{2\}\.\(19\)
Because rewards are Bernoulli, for eachaathe two distributions

Pt\(Ya,t∈⋅∣Π⋆\(𝐜\)=a,𝐂t=𝐜\)andPt\(Ya,t∈⋅∣𝐂t=𝐜\)P\_\{t\}\(Y\_\{a,t\}\\in\\cdot\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\quad\\text\{and\}\\quad P\_\{t\}\(Y\_\{a,t\}\\in\\cdot\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{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\\\!\\left\(P\_\{t\}\(Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\),\\,P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\right\)=\\left\|E\_\{t\}\[Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\]\-\\bar\{\\mu\}\_\{a\}\\right\|\.
Applying Pinsker’s inequality for eachaagives

\(Et​\[Ya,t∣Π⋆​\(𝐜\)=a,𝐂t=𝐜\]−μ¯a\)2\\displaystyle\\left\(E\_\{t\}\[Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\]\-\\bar\{\\mu\}\_\{a\}\\right\)^\{2\}≤12KL\(Pt\(Ya,t∣Π⋆\(𝐜\)=a,𝐂t=𝐜\)∥Pt\(Ya,t∣𝐂t=𝐜\)\)\.\\displaystyle\\leq\\frac\{1\}\{2\}KL\\\!\\left\(P\_\{t\}\(Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\ \\\|\\ P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\right\)\.\(20\)
Plugging \([20](https://arxiv.org/html/2607.15577#A1.E20)\) into \([19](https://arxiv.org/html/2607.15577#A1.E19)\) yields

Δt​\(𝐜\)2\\displaystyle\\Delta\_\{t\}\(\\mathbf\{c\}\)^\{2\}≤K2∑a∈𝒜pa2KL\(Pt\(Ya,t∣Π⋆\(𝐜\)=a,𝐂t=𝐜\)∥Pt\(Ya,t∣𝐂t=𝐜\)\)\.\\displaystyle\\leq\\frac\{K\}\{2\}\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{a\}^\{2\}\\,KL\\\!\\left\(P\_\{t\}\(Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\ \\\|\\ P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\right\)\.\(21\)
We now relate the right\-hand side to the information obtained under Thompson Sampling\. SinceAtA\_\{t\}andΠ⋆​\(𝐜\)\\Pi^\{\\star\}\(\\mathbf\{c\}\)are conditionally independent givenℱt\\mathcal\{F\}\_\{t\}and𝐂t=𝐜\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}, we have

It​\(Π⋆​\(𝐜\);\(At,YAt,t\)∣𝐂t=𝐜\)\\displaystyle I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\\right\)=∑a∈𝒜pa​It​\(Π⋆​\(𝐜\);Ya,t∣𝐂t=𝐜\)\\displaystyle=\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{a\}\\,I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\);Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\\right\)=∑a∈𝒜∑a′∈𝒜papa′KL\(Pt\(Ya,t∣Π⋆\(𝐜\)=a′,𝐂t=𝐜\)∥Pt\(Ya,t∣𝐂t=𝐜\)\)\\displaystyle=\\sum\_\{a\\in\\mathcal\{A\}\}\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}p\_\{a\}p\_\{a^\{\\prime\}\}\\,KL\\\!\\left\(P\_\{t\}\(Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a^\{\\prime\},\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\ \\\|\\ P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\right\)≥∑a∈𝒜pa2KL\(Pt\(Ya,t∣Π⋆\(𝐜\)=a,𝐂t=𝐜\)∥Pt\(Ya,t∣𝐂t=𝐜\)\)\.\\displaystyle\\geq\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{a\}^\{2\}\\,KL\\\!\\left\(P\_\{t\}\(Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\)=a,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\ \\\|\\ P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\)\\right\)\.\(22\)
Combining \([21](https://arxiv.org/html/2607.15577#A1.E21)\) and \([22](https://arxiv.org/html/2607.15577#A1.E22)\) gives

Δt​\(𝐜\)2≤K2​It​\(Π⋆​\(𝐜\);\(At,YAt,t\)∣𝐂t=𝐜\)\.\\Delta\_\{t\}\(\\mathbf\{c\}\)^\{2\}\\leq\\frac\{K\}\{2\}I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\);\(A\_\{t\},Y\_\{A\_\{t\},t\}\)\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\\right\)\.
Therefore, for every realized context𝐜\\mathbf\{c\},

Γt2≤K2,\\Gamma\_\{t\}^\{2\}\\leq\\frac\{K\}\{2\},or equivalently,

Γt≤K2=\|𝒜\|2\.\\Gamma\_\{t\}\\leq\\sqrt\{\\frac\{K\}\{2\}\}=\\sqrt\{\\frac\{\|\\mathcal\{A\}\|\}\{2\}\}\.
Thus,Γ=\|𝒜\|2\\Gamma=\\sqrt\{\\frac\{\|\\mathcal\{A\}\|\}\{2\}\}is a valid upper bound on the information\-ratio coefficientΓt\\Gamma\_\{t\}for every time steptt\. Therefore, by Theorem[1](https://arxiv.org/html/2607.15577#S5.Ex2),

𝔼​\[RegT\]≤Γ​H​\(Π⋆\)​T=\|𝒜\|2​H​\(Π⋆\)​T\.\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leq\\Gamma\\sqrt\{H\(\\Pi^\{\\star\}\)\\,T\}=\\sqrt\{\\frac\{\|\\mathcal\{A\}\|\}\{2\}\\,H\(\\Pi^\{\\star\}\)\\,T\}\.\(23\)
Moreover, sinceΠ⋆\\Pi^\{\\star\}maps the context space𝒞\\mathcal\{C\}to the action space𝒜\\mathcal\{A\}, the total number of possible mappings is at most\|𝒜\|\|𝒞\|\|\\mathcal\{A\}\|^\{\|\\mathcal\{C\}\|\}when𝒞\\mathcal\{C\}is finite\. This implies that the entropy is bounded asH​\(Π⋆\)≤log⁡\(\|𝒜\|\|𝒞\|\)=\|𝒞\|​log⁡\(\|𝒜\|\)H\(\\Pi^\{\\star\}\)\\leq\\log\\\!\\left\(\|\\mathcal\{A\}\|^\{\|\\mathcal\{C\}\|\}\\right\)=\|\\mathcal\{C\}\|\\log\\\!\\left\(\|\\mathcal\{A\}\|\\right\)\. Consequently,

𝔼​\[RegT\]≤T​\|𝒜\|​\|𝒞\|​log⁡\|𝒜\|2\.\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leq\\sqrt\{\\frac\{T\|\\mathcal\{A\}\|\|\\mathcal\{C\}\|\\log\|\\mathcal\{A\}\|\}\{2\}\}\.This completes the proof of Corollary[1](https://arxiv.org/html/2607.15577#S5.Ex3)\.

### A\.4Proof of Lemma[2](https://arxiv.org/html/2607.15577#Thmlemma2)

We fix time stepttand the realized context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\. We begin with the definition of the information gain:

gt\(a\|𝐜t\)=DK​L\(Pt\(Π∗\(𝐜t\),Ya,t∣𝐜t\)∥Pt\(Π∗\(𝐜t\)∣𝐜t\)Pt\(Ya,t∣𝐜t\)\)\.g\_\{t\}\(a\|\\mathbf\{c\}\_\{t\}\)=D\_\{KL\}\\\!\\left\(P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\),Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\)\\,\\middle\\\|\\,P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)\\mid\\mathbf\{c\}\_\{t\}\)P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\)\.
We compute each term separately\.

#### Posterior ofΠ∗​\(𝐜t\)\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)\.

By definition,

Pt​\(Π∗​\(𝐜t\)=a∗∣𝐜t\)=P​\(Π∗​\(𝐜t\)=a∗∣ℱt,𝐂t=𝐜t\)\.P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\}\\mid\\mathbf\{c\}\_\{t\}\)=P\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\}\\mid\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\)\.
Using the law of total expectation over𝜽\\boldsymbol\{\\theta\},

Pt​\(Π∗​\(𝐜t\)=a∗∣𝐜t\)=𝔼𝜽∼Pt​\(𝜽∣𝐜t\)​\[P​\(Π∗​\(𝐜t\)=a∗∣𝜽,𝐜t\)\]\.P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\}\\mid\\mathbf\{c\}\_\{t\}\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\left\[P\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\\right\]\.
Given𝜽\\boldsymbol\{\\theta\}and context𝐜t\\mathbf\{c\}\_\{t\}, the optimal action is deterministic, hence

P​\(Π∗​\(𝐜t\)=a∗∣𝜽,𝐜t\)=𝟙​\{a∗=arg⁡maxa∈𝒜⁡𝔼​\[Ya,t∣𝜽,𝐜t\]\}\.P\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)=\\mathbbm\{1\}\\left\\\{a^\{\*\}=\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\[Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\]\\right\\\}\.
Substituting,

Pt​\(Π∗​\(𝐜t\)=a∗∣𝐜t\)=𝔼𝜽∼Pt​\(𝜽∣𝐜t\)​\[𝟙​\{a∗=arg⁡maxa∈𝒜⁡𝔼​\[Ya,t∣𝜽,𝐜t\]\}\]\.P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\}\\mid\\mathbf\{c\}\_\{t\}\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\left\[\\mathbbm\{1\}\\left\\\{a^\{\*\}=\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\[Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\]\\right\\\}\\right\]\.

#### Posterior ofYaY\_\{a\}\.

By definition,

Pt​\(Ya,t=y∣𝐜t\)=P​\(Ya,t=y∣ℱt,𝐂t=𝐜t\)\.P\_\{t\}\(Y\_\{a,t\}=y\\mid\\mathbf\{c\}\_\{t\}\)=P\(Y\_\{a,t\}=y\\mid\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\)\.
Conditioning on𝜽\\boldsymbol\{\\theta\}gives

Pt​\(Ya,t=y∣𝐜t\)=𝔼𝜽∼Pt​\(𝜽∣𝐜t\)​\[P​\(Ya,t=y∣𝜽,𝐜t\)\]\.P\_\{t\}\(Y\_\{a,t\}=y\\mid\\mathbf\{c\}\_\{t\}\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\left\[P\(Y\_\{a,t\}=y\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\\right\]\.

#### Joint posterior\.

Using the law of total expectation,

Pt​\(Π∗​\(𝐜t\)=a∗,Ya,t=y∣𝐜t\)\\displaystyle P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\},Y\_\{a,t\}=y\\mid\\mathbf\{c\}\_\{t\}\)=𝔼𝜽∼Pt​\(𝜽∣𝐜t\)​\[P​\(Π∗​\(𝐜t\)=a∗,Ya,t=y∣𝜽,𝐜t\)\]\.\\displaystyle=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\Big\[P\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\},Y\_\{a,t\}=y\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\\Big\]\.
SinceΠ∗​\(𝐜t\)\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)is deterministic given𝜽\\boldsymbol\{\\theta\}and𝐜t\\mathbf\{c\}\_\{t\}, we have

Pt​\(Π∗​\(𝐜t\)=a∗,Ya,t=y∣𝐜t\)\\displaystyle P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\},Y\_\{a,t\}=y\\mid\\mathbf\{c\}\_\{t\}\)=𝔼𝜽∼Pt​\(𝜽∣𝐜t\)\[P\(Π∗\(𝐜t\)=a∗∣𝜽,𝐜t\)\\displaystyle=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\Big\[P\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)×P\(Ya,t=y∣𝜽,𝐜t\)\]\.\\displaystyle\\qquad\\qquad\\times P\(Y\_\{a,t\}=y\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\\Big\]\.
Substituting the indicator representation,

Pt\(Π∗\(𝐜t\)=a∗,Ya,t=y∣𝐜t\)=𝔼𝜽∼Pt​\(𝜽∣𝐜t\)\[𝟙\{a∗=argmaxa∈𝒜𝔼\[Ya,t∣𝜽,𝐜t\]\}\\displaystyle P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\},Y\_\{a,t\}=y\\mid\\mathbf\{c\}\_\{t\}\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\Big\[\\mathbbm\{1\}\\\{a^\{\*\}=\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\[Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\]\\\}×P\(Ya,t=y∣𝜽,𝐜t\)\]\.\\displaystyle\\times P\(Y\_\{a,t\}=y\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\\Big\]\.
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\]\.\\Delta\_\{t\}\(a\|\\mathbf\{c\}\_\{t\}\)=\\mathbb\{E\}\\\!\\left\[Y\_\{\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\),t\}\-Y\_\{a,t\}\\mid\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\},\\mathcal\{F\}\_\{t\}\\right\]\.
Using the law of total expectation over𝜽\\boldsymbol\{\\theta\},

Δt​\(a\|𝐜t\)=𝔼𝜽∼Pt​\(𝜽∣𝐜t\)​\[𝔼​\[YΠ∗​\(𝐜t\),t−Ya,t∣𝜽,𝐜t\]\]\.\\Delta\_\{t\}\(a\|\\mathbf\{c\}\_\{t\}\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\left\[\\mathbb\{E\}\\\!\\left\[Y\_\{\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\),t\}\-Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\\right\]\\right\]\.
Expanding the first term gives

𝔼​\[YΠ∗​\(𝐜t\),t∣𝜽,𝐜t\]\\displaystyle\\mathbb\{E\}\[Y\_\{\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\),t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\]=∑a∗∈𝒜𝟙​\{a∗=arg⁡maxa∈𝒜⁡𝔼​\[Ya,t∣𝜽,𝐜t\]\}\\displaystyle=\\sum\_\{a^\{\*\}\\in\\mathcal\{A\}\}\\mathbbm\{1\}\\left\\\{a^\{\*\}=\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\[Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\]\\right\\\}×P​\(Ya∗,t=1∣𝜽,𝐜t\)\.\\displaystyle\\qquad\\qquad\\times P\(Y\_\{a^\{\*\},t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\.
Also, since the rewards are Bernoulli,

𝔼​\[Ya,t∣𝜽,𝐜t\]=P​\(Ya,t=1∣𝜽,𝐜t\)\.\\mathbb\{E\}\[Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\]=P\(Y\_\{a,t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\.
Substituting both expressions,

Δt\(a\|𝐜t\)=𝔼𝜽∼Pt​\(𝜽∣𝐜t\)\[∑a∗∈𝒜𝟙\{a∗=argmaxa∈𝒜𝔼\[Ya,t∣𝜽,𝐜t\]\}\\displaystyle\\Delta\_\{t\}\(a\|\\mathbf\{c\}\_\{t\}\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\Bigg\[\\sum\_\{a^\{\*\}\\in\\mathcal\{A\}\}\\mathbbm\{1\}\\left\\\{a^\{\*\}=\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\[Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\]\\right\\\}×P\(Ya∗,t=1∣𝜽,𝐜t\)−P\(Ya,t=1∣𝜽,𝐜t\)\]\.\\displaystyle\\times P\(Y\_\{a^\{\*\},t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\-P\(Y\_\{a,t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\\Bigg\]\.
This completes the proof of Lemma[2](https://arxiv.org/html/2607.15577#Thmlemma2)\.

### A\.5Proof of Lemma[3](https://arxiv.org/html/2607.15577#Thmlemma3)

Fix time stepttand the realized context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\. From Lemma[2](https://arxiv.org/html/2607.15577#Thmlemma2), define

f​\(𝜽\):=∑a∗∈𝒜𝟙​\{a∗=arg⁡maxa∈𝒜⁡𝔼​\[Ya,t∣𝜽,𝐜t\]\}​P​\(Ya∗,t=1∣𝜽,𝐜t\)−P​\(Ya,t=1∣𝜽,𝐜t\)\.f\(\\boldsymbol\{\\theta\}\):=\\sum\_\{a^\{\*\}\\in\\mathcal\{A\}\}\\mathbbm\{1\}\\\!\\left\\\{a^\{\*\}=\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\mathbb\{E\}\[Y\_\{a,t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\]\\right\\\}P\(Y\_\{a^\{\*\},t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\-P\(Y\_\{a,t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\.Then

Δt​\(a∣𝐜t\)=𝔼𝜽∼Pt​\(𝜽∣𝐜t\)​\[f​\(𝜽\)\]\.\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\\!\\left\[f\(\\boldsymbol\{\\theta\}\)\\right\]\.
Let𝜽1,…,𝜽N\\boldsymbol\{\\theta\}\_\{1\},\\ldots,\\boldsymbol\{\\theta\}\_\{N\}be i\.i\.d\. samples fromPt​\(𝜽∣𝐜t\)P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\), and define the Monte Carlo estimator

Δ^t​\(a∣𝐜t\)=1N​∑i=1Nf​\(𝜽i\)\.\\widehat\{\\Delta\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}f\(\\boldsymbol\{\\theta\}\_\{i\}\)\.
We now bound the range off​\(𝜽\)f\(\\boldsymbol\{\\theta\}\)\. For any fixed𝜽\\boldsymbol\{\\theta\}, exactly one term in the indicator sum equals11because ties are broken deterministically\. Hence,

∑a∗∈𝒜𝟙​\{⋯\}​P​\(Ya∗,t=1∣𝜽,𝐜t\)=P​\(YΠ∗​\(𝐜t\),t=1∣𝜽,𝐜t\)\.\\sum\_\{a^\{\*\}\\in\\mathcal\{A\}\}\\mathbbm\{1\}\\\{\\cdots\\\}\\,P\(Y\_\{a^\{\*\},t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)=P\\\!\\left\(Y\_\{\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\),t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\\right\)\.BecauseΠ∗​\(𝐜t\)\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)maximizes the expected reward under𝜽\\boldsymbol\{\\theta\}and𝐜t\\mathbf\{c\}\_\{t\},

P​\(YΠ∗​\(𝐜t\),t=1∣𝜽,𝐜t\)≥P​\(Ya,t=1∣𝜽,𝐜t\)\.P\\\!\\left\(Y\_\{\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\),t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\\right\)\\geq P\(Y\_\{a,t\}=1\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\)\.Since both probabilities belong to\[0,1\]\[0,1\], it follows that

0≤f​\(𝜽\)≤1\.0\\leq f\(\\boldsymbol\{\\theta\}\)\\leq 1\.
DefineXi:=f​\(𝜽i\)X\_\{i\}:=f\(\\boldsymbol\{\\theta\}\_\{i\}\)\. ThenX1,…,XNX\_\{1\},\\ldots,X\_\{N\}are independent and satisfy0≤Xi≤10\\leq X\_\{i\}\\leq 1almost surely, and

𝔼​\[Xi\]=Δt​\(a∣𝐜t\),1N​∑i=1NXi=Δ^t​\(a∣𝐜t\)\.\\mathbb\{E\}\[X\_\{i\}\]=\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\),\\qquad\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}X\_\{i\}=\\widehat\{\\Delta\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\.Applying Hoeffding’s inequality to the sample mean of bounded variables yields, for anyϵ\>0\\epsilon\>0,

ℙ\(\|Δ^t\(a∣𝐜t\)−Δt\(a∣𝐜t\)\|≥ϵ\)≤2exp\(−2Nϵ2\)\.\\mathbb\{P\}\\\!\\left\(\\left\|\\widehat\{\\Delta\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\-\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\right\|\\geq\\epsilon\\right\)\\leq 2\\exp\\\!\\left\(\-2N\\epsilon^\{2\}\\right\)\.
Setting the right\-hand side equal toδ\\delta, i\.e\.,

δ=2​exp⁡\(−2​N​ϵ2\),\\delta=2\\exp\\\!\\left\(\-2N\\epsilon^\{2\}\\right\),gives

ϵ=12​N​log⁡\(2δ\)\.\\epsilon=\\sqrt\{\\frac\{1\}\{2N\}\\log\\\!\\left\(\\frac\{2\}\{\\delta\}\\right\)\}\.Therefore, with probability at least1−δ1\-\\delta,

\|Δ^t\(a∣𝐜t\)−Δt\(a∣𝐜t\)\|≤12​N​log⁡\(2δ\)≤2N​log⁡\(2δ\)\.\\left\|\\widehat\{\\Delta\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\-\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\right\|\\leq\\sqrt\{\\frac\{1\}\{2N\}\\log\\\!\\left\(\\frac\{2\}\{\\delta\}\\right\)\}\\leq\\sqrt\{\\frac\{2\}\{N\}\\log\\\!\\left\(\\frac\{2\}\{\\delta\}\\right\)\}\.Hence,

ℙ\(\|Δ^t\(a∣𝐜t\)−Δt\(a∣𝐜t\)\|≤2N​log⁡\(2δ\)\)≥1−δ\.\\mathbb\{P\}\\\!\\left\(\\left\|\\widehat\{\\Delta\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\-\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\right\|\\leq\\sqrt\{\\frac\{2\}\{N\}\\log\\\!\\left\(\\frac\{2\}\{\\delta\}\\right\)\}\\right\)\\geq 1\-\\delta\.This completes the proof of Lemma[3](https://arxiv.org/html/2607.15577#Thmlemma3)\.

### A\.6Concentration of the Information Gain

###### Proof of Lemma[4](https://arxiv.org/html/2607.15577#Thmlemma4)\.

Fix a time stepttand condition on the realized context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\. Throughout this section, ties in the definition of the optimal action are resolved using a fixed deterministic tie\-breaking rule\. We usePt​\(𝜽∣𝐜t\)P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)as shorthand forP​\(𝜽∣ℱt,𝐂t=𝐜t\)P\(\\boldsymbol\{\\theta\}\\mid\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\)\.

For each actiona∈𝒜a\\in\\mathcal\{A\}, define

pta​\(a∗,y\)\\displaystyle p\_\{t\}^\{a\}\(a^\{\*\},y\):=Pt​\(Π∗​\(𝐜t\)=a∗,Ya,t=y∣𝐜t\),\\displaystyle:=P\_\{t\}\\\!\\left\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\},Y\_\{a,t\}=y\\mid\\mathbf\{c\}\_\{t\}\\right\),pt⋆​\(a∗\)\\displaystyle p\_\{t\}^\{\\star\}\(a^\{\*\}\):=Pt​\(Π∗​\(𝐜t\)=a∗∣𝐜t\),\\displaystyle:=P\_\{t\}\\\!\\left\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)=a^\{\*\}\\mid\\mathbf\{c\}\_\{t\}\\right\),pta​\(y\)\\displaystyle p\_\{t\}^\{a\}\(y\):=Pt​\(Ya,t=y∣𝐜t\),\\displaystyle:=P\_\{t\}\\\!\\left\(Y\_\{a,t\}=y\\mid\\mathbf\{c\}\_\{t\}\\right\),fora∗∈𝒜a^\{\*\}\\in\\mathcal\{A\}andy∈\{0,1\}y\\in\\\{0,1\\\}\. By Lemma[2](https://arxiv.org/html/2607.15577#Thmlemma2), 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\)=\\mathbb\{E\}\_\{\\boldsymbol\{\\theta\}\\sim P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\left\[\\mathbbm\{1\}\\\!\\left\\\{a^\{\*\}=\\arg\\max\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\mathbb\{E\}\\left\[Y\_\{a^\{\\prime\},t\}\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\\right\]\\right\\\}P\\\!\\left\(Y\_\{a,t\}=y\\mid\\boldsymbol\{\\theta\},\\mathbf\{c\}\_\{t\}\\right\)\\right\]\.\(24\)
Let𝜽\(1\),…,𝜽\(N\)\\boldsymbol\{\\theta\}^\{\(1\)\},\\ldots,\\boldsymbol\{\\theta\}^\{\(N\)\}beNNindependent samples fromPt​\(𝜽∣𝐜t\)P\_\{t\}\(\\boldsymbol\{\\theta\}\\mid\\mathbf\{c\}\_\{t\}\), and define

ai∗:=arg⁡maxa′∈𝒜⁡𝔼​\[Ya′,t∣𝜽\(i\),𝐜t\]\.a\_\{i\}^\{\*\}:=\\arg\\max\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\mathbb\{E\}\\left\[Y\_\{a^\{\\prime\},t\}\\mid\\boldsymbol\{\\theta\}^\{\(i\)\},\\mathbf\{c\}\_\{t\}\\right\]\.The corresponding Monte Carlo estimators are

p^ta​\(a∗,y\)\\displaystyle\\widehat\{p\}\_\{t\}^\{a\}\(a^\{\*\},y\):=1N​∑i=1N𝟙​\{ai∗=a∗\}​P​\(Ya,t=y∣𝜽\(i\),𝐜t\),\\displaystyle:=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\mathbbm\{1\}\\\{a\_\{i\}^\{\*\}=a^\{\*\}\\\}P\\\!\\left\(Y\_\{a,t\}=y\\mid\\boldsymbol\{\\theta\}^\{\(i\)\},\\mathbf\{c\}\_\{t\}\\right\),\(25\)p^t⋆​\(a∗\)\\displaystyle\\widehat\{p\}\_\{t\}^\{\\star\}\(a^\{\*\}\):=1N​∑i=1N𝟙​\{ai∗=a∗\},\\displaystyle:=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\mathbbm\{1\}\\\{a\_\{i\}^\{\*\}=a^\{\*\}\\\},\(26\)p^ta​\(y\)\\displaystyle\\widehat\{p\}\_\{t\}^\{a\}\(y\):=1N​∑i=1NP​\(Ya,t=y∣𝜽\(i\),𝐜t\)\.\\displaystyle:=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}P\\\!\\left\(Y\_\{a,t\}=y\\mid\\boldsymbol\{\\theta\}^\{\(i\)\},\\mathbf\{c\}\_\{t\}\\right\)\.\(27\)
Define the confidence radii

ϵ1​\(N,δ\)\\displaystyle\\epsilon\_\{1\}\(N,\\delta\):=12​N​log⁡\(12​\|𝒜\|2δ\),\\displaystyle=\\sqrt\{\\frac\{1\}\{2N\}\\log\\\!\\left\(\\frac\{12\|\\mathcal\{A\}\|^\{2\}\}\{\\delta\}\\right\)\},\(28\)ϵ2​\(N,δ\)\\displaystyle\\epsilon\_\{2\}\(N,\\delta\):=12​N​log⁡\(6​\|𝒜\|δ\),\\displaystyle=\\sqrt\{\\frac\{1\}\{2N\}\\log\\\!\\left\(\\frac\{6\|\\mathcal\{A\}\|\}\{\\delta\}\\right\)\},ϵ3​\(N,δ\)\\displaystyle\\epsilon\_\{3\}\(N,\\delta\):=12​N​log⁡\(12​\|𝒜\|δ\)\.\\displaystyle=\\sqrt\{\\frac\{1\}\{2N\}\\log\\\!\\left\(\\frac\{12\|\\mathcal\{A\}\|\}\{\\delta\}\\right\)\}\.

#### Concentration of the posterior probabilities\.

The summands in \([25](https://arxiv.org/html/2607.15577#A1.E25)\) lie in\[0,1\]\[0,1\]\. Therefore, for anyε\>0\\varepsilon\>0, Hoeffding’s inequality gives

ℙ​\(\|p^ta​\(a∗,y\)−pta​\(a∗,y\)\|≥ε\)≤2​exp⁡\(−2​N​ε2\)\.\\mathbb\{P\}\\\!\\left\(\\left\|\\widehat\{p\}\_\{t\}^\{a\}\(a^\{\*\},y\)\-p\_\{t\}^\{a\}\(a^\{\*\},y\)\\right\|\\geq\\varepsilon\\right\)\\leq 2\\exp\(\-2N\\varepsilon^\{2\}\)\.Applying a union bound over alla,a∗∈𝒜a,a^\{\*\}\\in\\mathcal\{A\}andy∈\{0,1\}y\\in\\\{0,1\\\}gives, with probability at least1−δ/31\-\\delta/3,

\|p^ta​\(a∗,y\)−pta​\(a∗,y\)\|≤ϵ1​\(N,δ\),∀a,a∗∈𝒜,y∈\{0,1\}\.\\left\|\\widehat\{p\}\_\{t\}^\{a\}\(a^\{\*\},y\)\-p\_\{t\}^\{a\}\(a^\{\*\},y\)\\right\|\\leq\\epsilon\_\{1\}\(N,\\delta\),\\qquad\\forall a,a^\{\*\}\\in\\mathcal\{A\},\\quad y\\in\\\{0,1\\\}\.\(29\)
Similarly, applying Hoeffding’s inequality and a union bound overa∗∈𝒜a^\{\*\}\\in\\mathcal\{A\}gives, with probability at least1−δ/31\-\\delta/3,

\|p^t⋆​\(a∗\)−pt⋆​\(a∗\)\|≤ϵ2​\(N,δ\),∀a∗∈𝒜\.\\left\|\\widehat\{p\}\_\{t\}^\{\\star\}\(a^\{\*\}\)\-p\_\{t\}^\{\\star\}\(a^\{\*\}\)\\right\|\\leq\\epsilon\_\{2\}\(N,\\delta\),\\qquad\\forall a^\{\*\}\\in\\mathcal\{A\}\.\(30\)
Finally, applying Hoeffding’s inequality and a union bound overa∈𝒜a\\in\\mathcal\{A\}andy∈\{0,1\}y\\in\\\{0,1\\\}gives, with probability at least1−δ/31\-\\delta/3,

\|p^ta​\(y\)−pta​\(y\)\|≤ϵ3​\(N,δ\),∀a∈𝒜,y∈\{0,1\}\.\\left\|\\widehat\{p\}\_\{t\}^\{a\}\(y\)\-p\_\{t\}^\{a\}\(y\)\\right\|\\leq\\epsilon\_\{3\}\(N,\\delta\),\\qquad\\forall a\\in\\mathcal\{A\},\\quad y\\in\\\{0,1\\\}\.\(31\)
Combining \([29](https://arxiv.org/html/2607.15577#A1.E29)\), \([30](https://arxiv.org/html/2607.15577#A1.E30)\), and \([31](https://arxiv.org/html/2607.15577#A1.E31)\) with a union bound shows that all three concentration events hold simultaneously with probability at least1−δ1\-\\delta\.

For notational convenience, define

L1,ta​\(a∗,y\)\\displaystyle L\_\{1,t\}^\{a\}\(a^\{\*\},y\):=max⁡\{0,p^ta​\(a∗,y\)−ϵ1\},\\displaystyle:=\\max\\\!\\left\\\{0,\\widehat\{p\}\_\{t\}^\{a\}\(a^\{\*\},y\)\-\\epsilon\_\{1\}\\right\\\},U1,ta​\(a∗,y\)\\displaystyle U\_\{1,t\}^\{a\}\(a^\{\*\},y\):=min⁡\{1,p^ta​\(a∗,y\)\+ϵ1\},\\displaystyle:=\\min\\\!\\left\\\{1,\\widehat\{p\}\_\{t\}^\{a\}\(a^\{\*\},y\)\+\\epsilon\_\{1\}\\right\\\},L2,t​\(a∗\)\\displaystyle L\_\{2,t\}\(a^\{\*\}\):=max⁡\{0,p^t⋆​\(a∗\)−ϵ2\},\\displaystyle:=\\max\\\!\\left\\\{0,\\widehat\{p\}\_\{t\}^\{\\star\}\(a^\{\*\}\)\-\\epsilon\_\{2\}\\right\\\},U2,t​\(a∗\)\\displaystyle U\_\{2,t\}\(a^\{\*\}\):=min⁡\{1,p^t⋆​\(a∗\)\+ϵ2\},\\displaystyle:=\\min\\\!\\left\\\{1,\\widehat\{p\}\_\{t\}^\{\\star\}\(a^\{\*\}\)\+\\epsilon\_\{2\}\\right\\\},L3,ta​\(y\)\\displaystyle L\_\{3,t\}^\{a\}\(y\):=max⁡\{0,p^ta​\(y\)−ϵ3\},\\displaystyle:=\\max\\\!\\left\\\{0,\\widehat\{p\}\_\{t\}^\{a\}\(y\)\-\\epsilon\_\{3\}\\right\\\},U3,ta​\(y\)\\displaystyle U\_\{3,t\}^\{a\}\(y\):=min⁡\{1,p^ta​\(y\)\+ϵ3\},\\displaystyle:=\\min\\\!\\left\\\{1,\\widehat\{p\}\_\{t\}^\{a\}\(y\)\+\\epsilon\_\{3\}\\right\\\},whereϵi=ϵi​\(N,δ\)\\epsilon\_\{i\}=\\epsilon\_\{i\}\(N,\\delta\)fori∈\{1,2,3\}i\\in\\\{1,2,3\\\}\.

#### Upper confidence bound\.

The contextual information gain can be written as

gt\(a∣𝐜t\)=DKL\(pta∥pt⋆pta\),g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=D\_\{\\mathrm\{KL\}\}\\left\(p\_\{t\}^\{a\}\\,\\middle\\\|\\,p\_\{t\}^\{\\star\}p\_\{t\}^\{a\}\\right\),\(32\)where

\(pt⋆​pta\)​\(a∗,y\)=pt⋆​\(a∗\)​pta​\(y\)\.\\bigl\(p\_\{t\}^\{\\star\}p\_\{t\}^\{a\}\\bigr\)\(a^\{\*\},y\)=p\_\{t\}^\{\\star\}\(a^\{\*\}\)p\_\{t\}^\{a\}\(y\)\.Using

DKL​\(P∥Q\)≤χ2​\(P∥Q\)=∑xP​\(x\)2Q​\(x\)−1,D\_\{\\mathrm\{KL\}\}\(P\\\|Q\)\\leq\\chi^\{2\}\(P\\\|Q\)=\\sum\_\{x\}\\frac\{P\(x\)^\{2\}\}\{Q\(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\}\}\.\\overline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\):=\\min\\\!\\left\\\{\\log 2,\\,\\max\\\!\\left\\\{0,\\,\\sum\_\{\\begin\{subarray\}\{c\}a^\{\*\}\\in\\mathcal\{A\}\\\\ y\\in\\\{0,1\\\}\\end\{subarray\}\}\\frac\{\\bigl\(U\_\{1,t\}^\{a\}\(a^\{\*\},y\)\\bigr\)^\{2\}\}\{L\_\{2,t\}\(a^\{\*\}\)L\_\{3,t\}^\{a\}\(y\)\}\-1\\right\\\}\\right\\\}\.\(33\)WheneverL2,t​\(a∗\)​L3,ta​\(y\)=0L\_\{2,t\}\(a^\{\*\}\)L\_\{3,t\}^\{a\}\(y\)=0, the corresponding ratio in \([33](https://arxiv.org/html/2607.15577#A1.E33)\) is interpreted as\+∞\+\\infty\. The additional bound bylog⁡2\\log 2follows from

gt​\(a∣𝐜t\)=It​\(Π∗​\(𝐜t\);Ya,t∣𝐜t\)≤Ht​\(Ya,t∣𝐜t\)≤log⁡2\.g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=I\_\{t\}\\\!\\left\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\);Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\\right\)\\leq H\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\)\\leq\\log 2\.Consequently, on the joint concentration event,

gt​\(a∣𝐜t\)≤g¯t​\(a∣𝐜t\),∀a∈𝒜\.g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\leq\\overline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\),\\qquad\\forall a\\in\\mathcal\{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\\displaystyle\\underline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=\\underset\{P,Q\}\{\\operatorname\{minimize\}\}DKL​\(P∥Q\)\\displaystyle D\_\{\\mathrm\{KL\}\}\(P\\\|Q\)\(35\)subject toL1,ta​\(a∗,y\)≤P​\(a∗,y\)≤U1,ta​\(a∗,y\),\\displaystyle L\_\{1,t\}^\{a\}\(a^\{\*\},y\)\\leq P\(a^\{\*\},y\)\\leq U\_\{1,t\}^\{a\}\(a^\{\*\},y\),∀a∗∈𝒜,y∈\{0,1\},\\displaystyle\\hskip 133\.72786pt\\forall a^\{\*\}\\in\\mathcal\{A\},\\quad y\\in\\\{0,1\\\},L2,t​\(a∗\)​L3,ta​\(y\)≤Q​\(a∗,y\)≤U2,t​\(a∗\)​U3,ta​\(y\),\\displaystyle L\_\{2,t\}\(a^\{\*\}\)L\_\{3,t\}^\{a\}\(y\)\\leq Q\(a^\{\*\},y\)\\leq U\_\{2,t\}\(a^\{\*\}\)U\_\{3,t\}^\{a\}\(y\),∀a∗∈𝒜,y∈\{0,1\},\\displaystyle\\hskip 133\.72786pt\\forall a^\{\*\}\\in\\mathcal\{A\},\\quad y\\in\\\{0,1\\\},∑a∗∈𝒜y∈\{0,1\}P​\(a∗,y\)=1,\\displaystyle\\sum\_\{\\begin\{subarray\}\{c\}a^\{\*\}\\in\\mathcal\{A\}\\\\ y\\in\\\{0,1\\\}\\end\{subarray\}\}P\(a^\{\*\},y\)=1,∑a∗∈𝒜y∈\{0,1\}Q​\(a∗,y\)=1,\\displaystyle\\sum\_\{\\begin\{subarray\}\{c\}a^\{\*\}\\in\\mathcal\{A\}\\\\ y\\in\\\{0,1\\\}\\end\{subarray\}\}Q\(a^\{\*\},y\)=1,P​\(a∗,y\)≥0,Q​\(a∗,y\)≥0,\\displaystyle P\(a^\{\*\},y\)\\geq 0,\\qquad Q\(a^\{\*\},y\)\\geq 0,∀a∗∈𝒜,y∈\{0,1\}\.\\displaystyle\\hskip 133\.72786pt\\forall a^\{\*\}\\in\\mathcal\{A\},\\quad y\\in\\\{0,1\\\}\.
The KL divergence in \([35](https://arxiv.org/html/2607.15577#A1.E35)\) is understood in the extended\-value sense, with0​log⁡\(0/q\)=00\\log\(0/q\)=0andp​log⁡\(p/0\)=\+∞p\\log\(p/0\)=\+\\inftyforp\>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\}^\{\\star\}\(a^\{\*\}\)p\_\{t\}^\{a\}\(y\)are feasible for \([35](https://arxiv.org/html/2607.15577#A1.E35)\)\. Therefore, the optimal value of the program satisfies

g¯t​\(a∣𝐜t\)≤gt​\(a∣𝐜t\),∀a∈𝒜\.\\underline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\leq g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\),\\qquad\\forall a\\in\\mathcal\{A\}\.\(36\)
Combining \([34](https://arxiv.org/html/2607.15577#A1.E34)\) and \([36](https://arxiv.org/html/2607.15577#A1.E36)\), we conclude that, with probability at least1−δ1\-\\delta,

g¯t​\(a∣𝐜t\)≤gt​\(a∣𝐜t\)≤g¯t​\(a∣𝐜t\),∀a∈𝒜\.\\underline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\leq g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\leq\\overline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\),\\qquad\\forall a\\in\\mathcal\{A\}\.The numerical solution of \([35](https://arxiv.org/html/2607.15577#A1.E35)\) is described in Section[A\.7](https://arxiv.org/html/2607.15577#A1.SS7)\. ∎

### A\.7KL Divergence Minimization under Box Constraints

We fix time steptt, context𝐂t=𝐜t\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}, and an actiona∈𝒜a\\in\\mathcal\{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\)=DK​L\(Pt\(Π∗\(𝐜t\),Ya,t∣𝐜t\)∥Pt\(Π∗\(𝐜t\)∣𝐜t\)Pt\(Ya,t∣𝐜t\)\)\.g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=D\_\{KL\}\\\!\\left\(P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\),Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\)\\;\\middle\\\|\\;P\_\{t\}\(\\Pi^\{\*\}\(\\mathbf\{c\}\_\{t\}\)\\mid\\mathbf\{c\}\_\{t\}\)P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\)\.
To obtain a lower bound ongt​\(a∣𝐜t\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\), we solve the following constrained optimization problem over probability distributionsPPandQQ:

minimizeDK​L​\(P∥Q\)\\displaystyle D\_\{KL\}\(P\\,\\\|\\,Q\)subject toL1,ta​\(a∗,y\)≤P​\(a∗,y\)≤U1,ta​\(a∗,y\),\\displaystyle L\_\{1,t\}^\{a\}\(a^\{\*\},y\)\\leq P\(a^\{\*\},y\)\\leq U\_\{1,t\}^\{a\}\(a^\{\*\},y\),∀a∗∈𝒜,y∈\{0,1\},\\displaystyle\\hskip 50\.00008pt\\forall a^\{\*\}\\in\\mathcal\{A\},\\,y\\in\\\{0,1\\\},L2,t​\(a∗\)​L3,ta​\(y\)≤Q​\(a∗,y\)≤U2,t​\(a∗\)​U3,ta​\(y\),\\displaystyle L\_\{2,t\}\(a^\{\*\}\)L\_\{3,t\}^\{a\}\(y\)\\leq Q\(a^\{\*\},y\)\\leq U\_\{2,t\}\(a^\{\*\}\)U\_\{3,t\}^\{a\}\(y\),∀a∗∈𝒜,y∈\{0,1\},\\displaystyle\\hskip 50\.00008pt\\forall a^\{\*\}\\in\\mathcal\{A\},\\,y\\in\\\{0,1\\\},∑a∗∈𝒜,y∈\{0,1\}P​\(a∗,y\)=1,∑a∗∈𝒜,y∈\{0,1\}Q​\(a∗,y\)=1,\\displaystyle\\sum\_\{a^\{\*\}\\in\\mathcal\{A\},\\;y\\in\\\{0,1\\\}\}P\(a^\{\*\},y\)=1,\\quad\\sum\_\{a^\{\*\}\\in\\mathcal\{A\},\\;y\\in\\\{0,1\\\}\}Q\(a^\{\*\},y\)=1,P​\(a∗,y\)≥0,Q​\(a∗,y\)≥0,∀a∗∈𝒜,y∈\{0,1\}\.\\displaystyle P\(a^\{\*\},y\)\\geq 0,\\quad Q\(a^\{\*\},y\)\\geq 0,\\quad\\forall a^\{\*\}\\in\\mathcal\{A\},\\,y\\in\\\{0,1\\\}\.
Here, the confidence radii are

ϵ1​\(N,δ\)=12​N​log⁡\(12​\|𝒜\|2δ\),\\epsilon\_\{1\}\(N,\\delta\)=\\sqrt\{\\frac\{1\}\{2N\}\\log\\\!\\left\(\\frac\{12\|\\mathcal\{A\}\|^\{2\}\}\{\\delta\}\\right\)\},ϵ2​\(N,δ\)=12​N​log⁡\(6​\|𝒜\|δ\),\\epsilon\_\{2\}\(N,\\delta\)=\\sqrt\{\\frac\{1\}\{2N\}\\log\\\!\\left\(\\frac\{6\|\\mathcal\{A\}\|\}\{\\delta\}\\right\)\},ϵ3​\(N,δ\)=12​N​log⁡\(12​\|𝒜\|δ\)\.\\epsilon\_\{3\}\(N,\\delta\)=\\sqrt\{\\frac\{1\}\{2N\}\\log\\\!\\left\(\\frac\{12\|\\mathcal\{A\}\|\}\{\\delta\}\\right\)\}\.
The KL divergence is jointly convex inPPandQQ, 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

DK​L​\(P∥Q\)=∑a∗∈𝒜,y∈\{0,1\}rel​\_​entr⁡\(P​\(a∗,y\),Q​\(a∗,y\)\),D\_\{KL\}\(P\\\|Q\)=\\sum\_\{a^\{\*\}\\in\\mathcal\{A\},\\;y\\in\\\{0,1\\\}\}\\operatorname\{rel\\\_entr\}\\\!\\left\(P\(a^\{\*\},y\),Q\(a^\{\*\},y\)\\right\),where

rel​\_​entr⁡\(p,q\)=p​log⁡\(pq\)\\operatorname\{rel\\\_entr\}\(p,q\)=p\\log\\\!\\left\(\\frac\{p\}\{q\}\\right\)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 boundsLi≤xi≤UiL\_\{i\}\\leq x\_\{i\}\\leq U\_\{i\}, the Euclidean projection of a vectorzzonto the bounded simplex has the form

xi=min⁡\{Ui,max⁡\{Li,zi−λ\}\},x\_\{i\}=\\min\\\!\\left\\\{U\_\{i\},\\max\\\!\\left\\\{L\_\{i\},z\_\{i\}\-\\lambda\\right\\\}\\right\\\},whereλ\\lambdais chosen so that∑ixi=1\\sum\_\{i\}x\_\{i\}=1\. The value ofλ\\lambdacan 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 everya∈𝒜a\\in\\mathcal\{A\}, and its optimal value is used asg¯t​\(a∣𝐜t\)\\underline\{g\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\.

### A\.8Proof of Theorem[2](https://arxiv.org/html/2607.15577#Thmtheorem2)\(Contextual Case\)

Fix a horizonT∈ℕT\\in\\mathbb\{N\}and a realized context sequence

𝐂1:T=\(𝐂1,…,𝐂T\)=\(𝐜1,…,𝐜T\)\.\\mathbf\{C\}\_\{1:T\}=\(\\mathbf\{C\}\_\{1\},\\ldots,\\mathbf\{C\}\_\{T\}\)=\(\\mathbf\{c\}\_\{1\},\\ldots,\\mathbf\{c\}\_\{T\}\)\.For notational convenience, write

𝔼𝐜1:T\[⋅\]:=𝔼\[⋅\|𝐂1:T=𝐜1:T\]\.\\mathbb\{E\}\_\{\\mathbf\{c\}\_\{1:T\}\}\[\\cdot\]:=\\mathbb\{E\}\\\!\\left\[\\,\\cdot\\,\\middle\|\\mathbf\{C\}\_\{1:T\}=\\mathbf\{c\}\_\{1:T\}\\right\]\.
For everyπ∈S\|𝒜\|\\pi\\in S\_\{\|\\mathcal\{A\}\|\}, define

Δt​\(π∣𝐜t\)\\displaystyle\\Delta\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\):=∑a∈𝒜π​\(a\)​Δt​\(a∣𝐜t\),\\displaystyle:=\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\(a\)\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\),\(37\)gt​\(π∣𝐜t\)\\displaystyle g\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\):=∑a∈𝒜π​\(a\)​gt​\(a∣𝐜t\),\\displaystyle:=\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\(a\)g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\),\(38\)where

Δt​\(a∣𝐜t\)\\displaystyle\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\):=𝔼t\[YΠ⋆​\(𝐜t\),t−Ya,t\|𝐂t=𝐜t\],\\displaystyle:=\\mathbb\{E\}\_\{t\}\\\!\\left\[Y\_\{\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\),t\}\-Y\_\{a,t\}\\middle\|\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\],\(39\)gt​\(a∣𝐜t\)\\displaystyle g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\):=It\(Π⋆\(𝐜t\);Ya,t\|𝐂t=𝐜t\)\.\\displaystyle:=I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\);Y\_\{a,t\}\\middle\|\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)\.\(40\)The corresponding information ratio is

Ψt\(π∣𝐜t\):=Δt​\(π∣𝐜t\)2gt​\(π∣𝐜t\)\.\\Psi\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\):=\\frac\{\\Delta\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)^\{2\}\}\{g\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)\}\.\(41\)
Let

πt∘​\(𝐜t\)∈arg⁡minπ∈S\|𝒜\|⁡Ψt​\(π∣𝐜t\)\\pi\_\{t\}^\{\\circ\}\(\\mathbf\{c\}\_\{t\}\)\\in\\arg\\min\_\{\\pi\\in S\_\{\|\\mathcal\{A\}\|\}\}\\Psi\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)\(42\)denote the oracle IDS distribution, and letπ^t​\(𝐜t\)\\widehat\{\\pi\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)denote the distribution selected by Algorithm[2](https://arxiv.org/html/2607.15577#alg2)using the confidence sets\.

#### Step 1: Regret decomposition\.

By the tower property,

𝔼𝐜1:T​\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\]\\displaystyle\\mathbb\{E\}\_\{\\mathbf\{c\}\_\{1:T\}\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\right\]=𝔼𝐜1:T​\[∑t=1TΔt​\(π^t∣𝐜t\)\]\.\\displaystyle\\qquad=\\mathbb\{E\}\_\{\\mathbf\{c\}\_\{1:T\}\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\Delta\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\]\.\(43\)Using

Δt​\(π^t∣𝐜t\)=Ψt​\(π^t∣𝐜t\)​gt​\(π^t∣𝐜t\),\\Delta\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)=\\sqrt\{\\Psi\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)\}\\sqrt\{g\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)\},followed by Cauchy–Schwarz and Jensen’s inequality, gives

𝔼𝐜1:T​\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\]\\displaystyle\\mathbb\{E\}\_\{\\mathbf\{c\}\_\{1:T\}\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\right\]≤𝔼𝐜1:T​\[∑t=1TΨt​\(π^t∣𝐜t\)\]​𝔼𝐜1:T​\[∑t=1Tgt​\(π^t∣𝐜t\)\]\.\\displaystyle\\qquad\\leq\\sqrt\{\\mathbb\{E\}\_\{\\mathbf\{c\}\_\{1:T\}\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\Psi\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\]\}\\sqrt\{\\mathbb\{E\}\_\{\\mathbf\{c\}\_\{1:T\}\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\]\}\.\(44\)

#### Step 2: Bounding the cumulative information gain\.

Let

Zt:=Π⋆​\(𝐜t\)\.Z\_\{t\}:=\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)\.SinceZtZ\_\{t\}is a deterministic function of the random policyΠ⋆\\Pi^\{\\star\}, the data\-processing inequality gives

It\(Zt;Ya,t\|𝐂t=𝐜t\)≤It\(Π⋆;Ya,t\|𝐂t=𝐜t\)\.I\_\{t\}\\\!\\left\(Z\_\{t\};Y\_\{a,t\}\\middle\|\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)\\leq I\_\{t\}\\\!\\left\(\\Pi^\{\\star\};Y\_\{a,t\}\\middle\|\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)\.\(45\)Consequently,

gt​\(π^t∣𝐜t\)\\displaystyle g\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)=∑a∈𝒜π^t\(a∣𝐜t\)It\(Zt;Ya,t\|𝐂t=𝐜t\)\\displaystyle=\\sum\_\{a\\in\\mathcal\{A\}\}\\widehat\{\\pi\}\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)I\_\{t\}\\\!\\left\(Z\_\{t\};Y\_\{a,t\}\\middle\|\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)≤It\(Π⋆;YAt,t\|At,𝐂t=𝐜t\)\.\\displaystyle\\leq I\_\{t\}\\\!\\left\(\\Pi^\{\\star\};Y\_\{A\_\{t\},t\}\\middle\|A\_\{t\},\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)\.\(46\)
Conditional on the historyℱt\\mathcal\{F\}\_\{t\}and the observed context, the randomization used to generateAtA\_\{t\}is independent ofΠ⋆\\Pi^\{\\star\}\. Therefore,

I\(Π⋆;At\|ℱt,𝐂1:T=𝐜1:T\)=0\.I\\\!\\left\(\\Pi^\{\\star\};A\_\{t\}\\middle\|\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{1:T\}=\\mathbf\{c\}\_\{1:T\}\\right\)=0\.It follows from the chain rule for mutual information that

𝔼𝐜1:T​\[∑t=1Tgt​\(π^t∣𝐜t\)\]\\displaystyle\\mathbb\{E\}\_\{\\mathbf\{c\}\_\{1:T\}\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\]≤∑t=1TI\(Π⋆;At,YAt,t\|ℱt,𝐂1:T=𝐜1:T\)\\displaystyle\\qquad\\leq\\sum\_\{t=1\}^\{T\}I\\\!\\left\(\\Pi^\{\\star\};A\_\{t\},Y\_\{A\_\{t\},t\}\\middle\|\\mathcal\{F\}\_\{t\},\\mathbf\{C\}\_\{1:T\}=\\mathbf\{c\}\_\{1:T\}\\right\)=I\(Π⋆;ℱT\+1\|𝐂1:T=𝐜1:T\)\\displaystyle\\qquad=I\\\!\\left\(\\Pi^\{\\star\};\\mathcal\{F\}\_\{T\+1\}\\middle\|\\mathbf\{C\}\_\{1:T\}=\\mathbf\{c\}\_\{1:T\}\\right\)≤H\(Π⋆\|𝐂1:T=𝐜1:T\)≤H\(Π⋆\)\.\\displaystyle\\qquad\\leq H\\\!\\left\(\\Pi^\{\\star\}\\middle\|\\mathbf\{C\}\_\{1:T\}=\\mathbf\{c\}\_\{1:T\}\\right\)\\leq H\(\\Pi^\{\\star\}\)\.\(47\)Substituting \([47](https://arxiv.org/html/2607.15577#A1.E47)\) into \([44](https://arxiv.org/html/2607.15577#A1.E44)\) yields

𝔼𝐜1:T​\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\]\\displaystyle\\mathbb\{E\}\_\{\\mathbf\{c\}\_\{1:T\}\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\right\]≤H​\(Π⋆\)​𝔼𝐜1:T​\[∑t=1TΨt​\(π^t∣𝐜t\)\]\.\\displaystyle\\qquad\\leq\\sqrt\{H\(\\Pi^\{\\star\}\)\\,\\mathbb\{E\}\_\{\\mathbf\{c\}\_\{1:T\}\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\Psi\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\]\}\.\(48\)

#### Step 3: Oracle information\-ratio bound\.

Fixttand let

pt\(a∣𝐜t\):=Pt\(Π⋆\(𝐜t\)=a\|𝐂t=𝐜t\)\.p\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\):=P\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=a\\middle\|\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)\.\(49\)Consider the Thompson\-sampling distribution

πtTS​\(a∣𝐜t\)=pt​\(a∣𝐜t\)\.\\pi\_\{t\}^\{\\mathrm\{TS\}\}\(a\\mid\\mathbf\{c\}\_\{t\}\)=p\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\.Becauseπt∘\\pi\_\{t\}^\{\\circ\}minimizes the true information ratio,

Ψt​\(πt∘∣𝐜t\)≤Ψt​\(πtTS∣𝐜t\)\.\\Psi\_\{t\}\(\\pi\_\{t\}^\{\\circ\}\\mid\\mathbf\{c\}\_\{t\}\)\\leq\\Psi\_\{t\}\(\\pi\_\{t\}^\{\\mathrm\{TS\}\}\\mid\\mathbf\{c\}\_\{t\}\)\.\(50\)
Fora,b∈𝒜a,b\\in\\mathcal\{A\}, let

μt,a\\displaystyle\\mu\_\{t,a\}:=𝔼t\[Ya,t\|𝐂t=𝐜t\],\\displaystyle:=\\mathbb\{E\}\_\{t\}\\\!\\left\[Y\_\{a,t\}\\middle\|\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\],\(51\)μt,a∣b\\displaystyle\\mu\_\{t,a\\mid b\}:=𝔼t\[Ya,t\|Π⋆\(𝐜t\)=b,𝐂t=𝐜t\]\.\\displaystyle:=\\mathbb\{E\}\_\{t\}\\\!\\left\[Y\_\{a,t\}\\middle\|\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=b,\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\]\.\(52\)Posterior matching gives

Δt​\(πtTS∣𝐜t\)=∑a∈𝒜pt​\(a∣𝐜t\)​\(μt,a∣a−μt,a\)\.\\Delta\_\{t\}\(\\pi\_\{t\}^\{\\mathrm\{TS\}\}\\mid\\mathbf\{c\}\_\{t\}\)=\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\left\(\\mu\_\{t,a\\mid a\}\-\\mu\_\{t,a\}\\right\)\.\(53\)Hence,

Δt​\(πtTS∣𝐜t\)2\\displaystyle\\Delta\_\{t\}\(\\pi\_\{t\}^\{\\mathrm\{TS\}\}\\mid\\mathbf\{c\}\_\{t\}\)^\{2\}≤\|𝒜\|​∑a∈𝒜pt​\(a∣𝐜t\)2​\(μt,a∣a−μt,a\)2\.\\displaystyle\\leq\|\\mathcal\{A\}\|\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)^\{2\}\\left\(\\mu\_\{t,a\\mid a\}\-\\mu\_\{t,a\}\\right\)^\{2\}\.\(54\)
Since the rewards are Bernoulli, Pinsker’s inequality implies

\(μt,a∣a−μt,a\)2\\displaystyle\\left\(\\mu\_\{t,a\\mid a\}\-\\mu\_\{t,a\}\\right\)^\{2\}≤12DKL\(Pt\(Ya,t∣Π⋆\(𝐜t\)=a,𝐜t\)∥Pt\(Ya,t∣𝐜t\)\)\.\\displaystyle\\leq\\frac\{1\}\{2\}D\_\{\\mathrm\{KL\}\}\\\!\\left\(P\_\{t\}\(Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=a,\\mathbf\{c\}\_\{t\}\)\\middle\\\|P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\)\.\(55\)Therefore,

Δt​\(πtTS∣𝐜t\)2\\displaystyle\\Delta\_\{t\}\(\\pi\_\{t\}^\{\\mathrm\{TS\}\}\\mid\\mathbf\{c\}\_\{t\}\)^\{2\}≤\|𝒜\|2∑a∈𝒜pt\(a∣𝐜t\)2DKL\(Pt\(Ya,t∣Π⋆\(𝐜t\)=a,𝐜t\)∥Pt\(Ya,t∣𝐜t\)\)\.\\displaystyle\\leq\\frac\{\|\\mathcal\{A\}\|\}\{2\}\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)^\{2\}D\_\{\\mathrm\{KL\}\}\\\!\\left\(P\_\{t\}\(Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=a,\\mathbf\{c\}\_\{t\}\)\\middle\\\|P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\)\.\(56\)
On the other hand,

gt​\(πtTS∣𝐜t\)\\displaystyle g\_\{t\}\(\\pi\_\{t\}^\{\\mathrm\{TS\}\}\\mid\\mathbf\{c\}\_\{t\}\)=∑a∈𝒜pt\(a∣𝐜t\)It\(Π⋆\(𝐜t\);Ya,t\|𝐂t=𝐜t\)\\displaystyle=\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)I\_\{t\}\\\!\\left\(\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\);Y\_\{a,t\}\\middle\|\\mathbf\{C\}\_\{t\}=\\mathbf\{c\}\_\{t\}\\right\)=∑a∈𝒜∑b∈𝒜pt​\(a∣𝐜t\)​pt​\(b∣𝐜t\)\\displaystyle=\\sum\_\{a\\in\\mathcal\{A\}\}\\sum\_\{b\\in\\mathcal\{A\}\}p\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)p\_\{t\}\(b\\mid\\mathbf\{c\}\_\{t\}\)×DKL\(Pt\(Ya,t∣Π⋆\(𝐜t\)=b,𝐜t\)∥Pt\(Ya,t∣𝐜t\)\)\.\\displaystyle\\qquad\\qquad\\times D\_\{\\mathrm\{KL\}\}\\\!\\left\(P\_\{t\}\(Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=b,\\mathbf\{c\}\_\{t\}\)\\middle\\\|P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\)\.\(57\)Every term in \([57](https://arxiv.org/html/2607.15577#A1.E57)\) is nonnegative\. Keeping only the diagonal termsb=ab=agives

gt​\(πtTS∣𝐜t\)\\displaystyle g\_\{t\}\(\\pi\_\{t\}^\{\\mathrm\{TS\}\}\\mid\\mathbf\{c\}\_\{t\}\)≥∑a∈𝒜pt\(a∣𝐜t\)2DKL\(Pt\(Ya,t∣Π⋆\(𝐜t\)=a,𝐜t\)∥Pt\(Ya,t∣𝐜t\)\)\.\\displaystyle\\geq\\sum\_\{a\\in\\mathcal\{A\}\}p\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)^\{2\}D\_\{\\mathrm\{KL\}\}\\\!\\left\(P\_\{t\}\(Y\_\{a,t\}\\mid\\Pi^\{\\star\}\(\\mathbf\{c\}\_\{t\}\)=a,\\mathbf\{c\}\_\{t\}\)\\middle\\\|P\_\{t\}\(Y\_\{a,t\}\\mid\\mathbf\{c\}\_\{t\}\)\\right\)\.\(58\)Combining \([56](https://arxiv.org/html/2607.15577#A1.E56)\) and \([58](https://arxiv.org/html/2607.15577#A1.E58)\) yields

Δt​\(πtTS∣𝐜t\)2≤\|𝒜\|2​gt​\(πtTS∣𝐜t\)\.\\Delta\_\{t\}\(\\pi\_\{t\}^\{\\mathrm\{TS\}\}\\mid\\mathbf\{c\}\_\{t\}\)^\{2\}\\leq\\frac\{\|\\mathcal\{A\}\|\}\{2\}g\_\{t\}\(\\pi\_\{t\}^\{\\mathrm\{TS\}\}\\mid\\mathbf\{c\}\_\{t\}\)\.Thus,

Ψt​\(πt∘∣𝐜t\)≤Ψt​\(πtTS∣𝐜t\)≤\|𝒜\|2\.\\Psi\_\{t\}\(\\pi\_\{t\}^\{\\circ\}\\mid\\mathbf\{c\}\_\{t\}\)\\leq\\Psi\_\{t\}\(\\pi\_\{t\}^\{\\mathrm\{TS\}\}\\mid\\mathbf\{c\}\_\{t\}\)\\leq\\frac\{\|\\mathcal\{A\}\|\}\{2\}\.\(59\)

#### Step 4: Confidence sets and Algorithm[2](https://arxiv.org/html/2607.15577#alg2)\.

For vectors𝚫∈ℝ\|𝒜\|\\boldsymbol\{\\Delta\}\\in\\mathbb\{R\}^\{\|\\mathcal\{A\}\|\}and𝒈∈ℝ\+\|𝒜\|\\boldsymbol\{g\}\\in\\mathbb\{R\}^\{\|\\mathcal\{A\}\|\}\_\{\+\}, define

Ft​\(π;𝚫,𝒈\):=\(π⊤​𝚫\)2π⊤​𝒈\.F\_\{t\}\(\\pi;\\boldsymbol\{\\Delta\},\\boldsymbol\{g\}\):=\\frac\{\(\\pi^\{\\top\}\\boldsymbol\{\\Delta\}\)^\{2\}\}\{\\pi^\{\\top\}\\boldsymbol\{g\}\}\.\(60\)
At timett, Algorithm[2](https://arxiv.org/html/2607.15577#alg2)selects vectors

𝚫~t​\(𝐜t\)∈𝒞tΔ​\(𝐜t\)and𝒈~t​\(𝐜t\)∈𝒞tg​\(𝐜t\)\\widetilde\{\\boldsymbol\{\\Delta\}\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\\in\\mathcal\{C\}^\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\\qquad\\text\{and\}\\qquad\\widetilde\{\\boldsymbol\{g\}\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\\in\\mathcal\{C\}^\{g\}\_\{t\}\(\\mathbf\{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\)\)\.\\widehat\{\\Psi\}\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\):=F\_\{t\}\\\!\\left\(\\pi;\\widetilde\{\\boldsymbol\{\\Delta\}\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\),\\widetilde\{\\boldsymbol\{g\}\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\\right\)\.\(61\)Algorithm[2](https://arxiv.org/html/2607.15577#alg2)then selects

π^t​\(𝐜t\)∈arg⁡minπ∈S\|𝒜\|⁡Ψ^t​\(π∣𝐜t\)\.\\widehat\{\\pi\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\\in\\arg\\min\_\{\\pi\\in S\_\{\|\\mathcal\{A\}\|\}\}\\widehat\{\\Psi\}\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)\.\(62\)
Letℰ\\mathcal\{E\}be the event on which, simultaneously for everyt≤Tt\\leq Tand everya∈𝒜a\\in\\mathcal\{A\},

Δt​\(a∣𝐜t\)∈𝒞t,aΔ​\(𝐜t\)andgt​\(a∣𝐜t\)∈𝒞t,ag​\(𝐜t\)\.\\Delta\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\in\\mathcal\{C\}^\{\\Delta\}\_\{t,a\}\(\\mathbf\{c\}\_\{t\}\)\\quad\\text\{and\}\\quad g\_\{t\}\(a\\mid\\mathbf\{c\}\_\{t\}\)\\in\\mathcal\{C\}^\{g\}\_\{t,a\}\(\\mathbf\{c\}\_\{t\}\)\.Using

δ=δ′2​T​\|𝒜\|\\delta=\\frac\{\\delta^\{\\prime\}\}\{2T\|\\mathcal\{A\}\|\}in Lemmas[3](https://arxiv.org/html/2607.15577#Thmlemma3)and[4](https://arxiv.org/html/2607.15577#Thmlemma4), and applying a union bound over the time steps, actions, and the two concentration results, gives

ℙ​\(ℰ\)≥1−δ′\.\\mathbb\{P\}\(\\mathcal\{E\}\)\\geq 1\-\\delta^\{\\prime\}\.\(63\)For each time steptt, define

γt:=supπ∈S\|𝒜\|,𝚫t1​\(𝐜t\),𝚫t2​\(𝐜t\)∈𝒞tΔ​\(𝐜t\),𝒈t1​\(𝐜t\),𝒈t2​\(𝐜t\)∈𝒞tg​\(𝐜t\)\|\(π⊤​𝚫t1​\(𝐜t\)\)2π⊤​𝒈t1​\(𝐜t\)−\(π⊤​𝚫t2​\(𝐜t\)\)2π⊤​𝒈t2​\(𝐜t\)\|\.\\gamma\_\{t\}:=\\sup\_\{\\begin\{subarray\}\{c\}\\pi\\in S\_\{\|\\mathcal\{A\}\|\},\\\\ \\boldsymbol\{\\Delta\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\),\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)\\in\\mathcal\{C\}^\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\),\\\\ \\boldsymbol\{g\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\),\\boldsymbol\{g\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)\\in\\mathcal\{C\}^\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\\end\{subarray\}\}\\left\|\\frac\{\\left\(\\pi^\{\\top\}\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\)\\right\)^\{2\}\}\{\\pi^\{\\top\}\\boldsymbol\{g\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\)\}\-\\frac\{\\left\(\\pi^\{\\top\}\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)\\right\)^\{2\}\}\{\\pi^\{\\top\}\\boldsymbol\{g\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)\}\\right\|\.\(64\)The ratios in \([64](https://arxiv.org/html/2607.15577#A1.E64)\) are interpreted using the conventions0/0:=00/0:=0andx/0:=\+∞x/0:=\+\\inftyfor everyx\>0x\>0\.

Onℰ\\mathcal\{E\}, the true vectors𝚫t​\(𝐜t\)\\boldsymbol\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)and𝒈t​\(𝐜t\)\\boldsymbol\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)belong to their respective confidence sets\. By construction, the vectors𝚫~t​\(𝐜t\)\\widetilde\{\\boldsymbol\{\\Delta\}\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)and𝒈~t​\(𝐜t\)\\widetilde\{\\boldsymbol\{g\}\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)selected by Algorithm[2](https://arxiv.org/html/2607.15577#alg2)also belong to these confidence sets\. Consequently, in \([64](https://arxiv.org/html/2607.15577#A1.E64)\), we may choose

𝚫t1​\(𝐜t\)=𝚫t​\(𝐜t\),𝒈t1​\(𝐜t\)=𝒈t​\(𝐜t\),\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\)=\\boldsymbol\{\\Delta\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\),\\qquad\\boldsymbol\{g\}\_\{t\}^\{\\,1\}\(\\mathbf\{c\}\_\{t\}\)=\\boldsymbol\{g\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\),and

𝚫t2​\(𝐜t\)=𝚫~t​\(𝐜t\),𝒈t2​\(𝐜t\)=𝒈~t​\(𝐜t\)\.\\boldsymbol\{\\Delta\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)=\\widetilde\{\\boldsymbol\{\\Delta\}\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\),\\qquad\\boldsymbol\{g\}\_\{t\}^\{\\,2\}\(\\mathbf\{c\}\_\{t\}\)=\\widetilde\{\\boldsymbol\{g\}\}\_\{t\}\(\\mathbf\{c\}\_\{t\}\)\.Therefore,

\|Ψt\(π∣𝐜t\)−Ψ^t\(π∣𝐜t\)\|≤γtfor everyπ∈S\|𝒜\|\.\\left\|\\Psi\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)\-\\widehat\{\\Psi\}\_\{t\}\(\\pi\\mid\\mathbf\{c\}\_\{t\}\)\\right\|\\leq\\gamma\_\{t\}\\qquad\\text\{for every \}\\pi\\in S\_\{\|\\mathcal\{A\}\|\}\.\(65\)
Using \([62](https://arxiv.org/html/2607.15577#A1.E62)\), \([65](https://arxiv.org/html/2607.15577#A1.E65)\), and the optimality ofπt∘\\pi\_\{t\}^\{\\circ\}, we obtain

Ψt​\(π^t∣𝐜t\)\\displaystyle\\Psi\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)≤Ψ^t​\(π^t∣𝐜t\)\+γt\\displaystyle\\leq\\widehat\{\\Psi\}\_\{t\}\(\\widehat\{\\pi\}\_\{t\}\\mid\\mathbf\{c\}\_\{t\}\)\+\\gamma\_\{t\}≤Ψ^t​\(πt∘∣𝐜t\)\+γt\\displaystyle\\leq\\widehat\{\\Psi\}\_\{t\}\(\\pi\_\{t\}^\{\\circ\}\\mid\\mathbf\{c\}\_\{t\}\)\+\\gamma\_\{t\}≤Ψt​\(πt∘∣𝐜t\)\+2​γt\\displaystyle\\leq\\Psi\_\{t\}\(\\pi\_\{t\}^\{\\circ\}\\mid\\mathbf\{c\}\_\{t\}\)\+2\\gamma\_\{t\}≤\|𝒜\|2\+2​γt\.\\displaystyle\\leq\\frac\{\|\\mathcal\{A\}\|\}\{2\}\+2\\gamma\_\{t\}\.\(66\)

#### Step 5: Final bound\.

On the eventℰ\\mathcal\{E\}, substituting \([66](https://arxiv.org/html/2607.15577#A1.E66)\) into \([48](https://arxiv.org/html/2607.15577#A1.E48)\) gives

𝔼​\[∑t=1T\(YΠ⋆​\(𝐂t\),t−YAt,t\)\|\{𝐂t\}t=1T\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\left\.\\sum\_\{t=1\}^\{T\}\\left\(Y\_\{\\Pi^\{\\star\}\(\\mathbf\{C\}\_\{t\}\),t\}\-Y\_\{A\_\{t\},t\}\\right\)\\,\\right\|\\,\\\{\\mathbf\{C\}\_\{t\}\\\}\_\{t=1\}^\{T\}\\right\]≤H​\(Π⋆\)​\(T​\|𝒜\|2\+2​∑t=1Tγt\)\.\\displaystyle\\qquad\\leq\\sqrt\{H\(\\Pi^\{\\star\}\)\\left\(\\frac\{T\|\\mathcal\{A\}\|\}\{2\}\+2\\sum\_\{t=1\}^\{T\}\\gamma\_\{t\}\\right\)\}\.\(67\)Sinceℙ​\(ℰ\)≥1−δ′\\mathbb\{P\}\(\\mathcal\{E\}\)\\geq 1\-\\delta^\{\\prime\}, the claimed bound holds with probability at least1−δ′1\-\\delta^\{\\prime\}\. This completes the proof\.

### A\.9Application to a Causal Graph Motivated by a Real\-World Scenario

Health\\mathrm\{Health\}Recovery\\mathrm\{Recovery\}Treatment\\mathrm\{Treatment\}Diet\\mathrm\{Diet\}Lifestyle\\mathrm\{Lifestyle\}\(a\)Causal graph\.![Refer to caption](https://arxiv.org/html/2607.15577v1/real_exp.png)\(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\)](https://arxiv.org/html/2607.15577#A1.F5.sf1)\. The red nodes,Lifestyle\\mathrm\{Lifestyle\}andHealth\\mathrm\{Health\}, represent non\-manipulable variables, whileRecovery\\mathrm\{Recovery\}is the outcome variable of interest\. The manipulable variablesDiet\\mathrm\{Diet\}andTreatment\\mathrm\{Treatment\}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\)](https://arxiv.org/html/2607.15577#A1.F5.sf2)\.

### A\.10Sampling 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σ\\sigma\. For thenn\-th vertex in this ordering, we sample its in\-degree according to

Xn=max⁡\{1,Bin⁡\(n−1,ρ\)\},X\_\{n\}=\\max\\left\\\{1,\\,\\operatorname\{Bin\}\(n\-1,\\rho\)\\right\\\},whereBin⁡\(n−1,ρ\)\\operatorname\{Bin\}\(n\-1,\\rho\)denotes a binomial random variable with parametersn−1n\-1andρ\\rho\. We then selectXnX\_\{n\}parents uniformly at random from the vertices that precede thenn\-th vertex in the orderingσ\\sigma\. 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 byKoller and Friedman \[[2009](https://arxiv.org/html/2607.15577#bib.bib40)\], using the reverse ofσ\\sigmaas the elimination ordering\. This construction follows the methodology adopted in prior work\[Squireset al\.,[2020](https://arxiv.org/html/2607.15577#bib.bib41)\]\. 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\.