*$\dagger$*$\dagger$affiliationtext: Department of Industrial Engineering and Decision Analytics*$\dagger$*$\dagger$affiliationtext: The Hong Kong University of Science and Technology

#  Provably Efficient Learning in Partially Observable Contextual Bandit

Xueping Gong  Jiheng Zhang

###### Abstract

In this paper, we investigate transfer learning in partially observable
contextual bandits, where agents have limited knowledge from other agents and
partial information about hidden confounders. We first convert the problem to
identifying or partially identifying causal effects between actions and
rewards through optimization problems. To solve these optimization problems,
we discretize the original functional constraints of unknown distributions
into linear constraints, and sample compatible causal models via sequentially
solving linear programmings to obtain causal bounds with the consideration of
estimation error. Our sampling algorithms provide desirable convergence
results for suitable sampling distributions. We then show how causal bounds
can be applied to improving classical bandit algorithms and affect the regrets
with respect to the size of action sets and function spaces. Notably, in the
task with function approximation which allows us to handle general context
distributions, our method improves the order dependence on function space size
compared with previous literatures. We formally prove that our causally
enhanced algorithms outperform classical bandit algorithms and achieve orders
of magnitude faster convergence rates. Finally, we perform simulations that
demonstrate the efficiency of our strategy compared to the current state-of-
the-art methods. This research has the potential to enhance the performance of
contextual bandit agents in real-world applications where data is scarce and
costly to obtain.

##  1 Introduction

Bandit learning problems involve an agent making a series of decisions with
the aim of maximizing rewards or minimizing regrets, as described in [16].
Classical bandit algorithms typically do not consider any prior knowledge,
which may result in substantial time and computational costs to learn a near-
optimal policy. To address this issue, transfer learning (TL) techniques have
been proposed to expedite the learning process of a target task by leveraging
knowledge obtained from a related source task. These techniques often rely on
exploiting domain expertise and transferring knowledge that remains invariant
across the source and target domains, as discussed in [43].

Transfer learning (TL) methods commonly assume that both the expert and
learner agents have access to the same information, as noted in [3, 24].
However, this assumption does not always hold true in practical scenarios. For
instance, human drivers rely on past experiences to form a mental model of the
world, which guides their actions along with other sensory inputs such as
visual information. Such experiential information cannot be captured by
sensors like cameras and lidar present in autonomous vehicles. Furthermore,
autonomous vehicles themselves have their own observed contexts that are not
available to human drivers. This leads to a transfer learning problem in
partially observable contextual bandit problems (TLPOCB).

Drawing from the motivating example mentioned previously, we examine transfer
learning problems in partially observable contextual bandits. In this setting,
the expert has access to either complete or partial contextual information,
which it passes on to the agent. However, the agent can only gather partial
contextual information due to restricted transfer resulting from factors such
as privileged information, privacy concerns, or physical limitations. Another
scenario involves enhancing the performance of a partial model by discovering
a new factor that can impact the performance of the current model, though the
causal relationship of this factor is currently unknown. In such cases, we can
estimate the frequency of the new factor and use our method to improve model
performance. Typically, the frequency of the new factor is independent of pre-
existing models.

Using expert data without comprehending the expert context can result in
biased learned policies that require a considerable amount of new data samples
to improve. Causal inference has been widely employed in addressing unobserved
contextual information in bandit and transfer learning problems, as discussed
in [2, 41, 15, 3, 25, 11], where qualitative knowledge on causal relationships
is frequently available in complex reinforcement learning (RL) settings. In
[31], a framework is established for inferring the effect of actions (target)
from a combination of a causal model (to be defined) and diverse sources of
data (source). Building upon this framework, we outline three transfer
learning tasks in partially observable contextual bandits. Identifying causal
effects in offline learning often necessitates instrumental variables (IVs) or
proxies, which may not be practical, as noted in [14, 39, 11]. Therefore, we
develop new causal bounds for general context and reward distributions,
whether discrete or continuous, to assist learner agents in achieving faster
learning rates with limited source requirements. These causal bounds enable
the reduction of exploration variance in our bandit algorithms, thus
accelerating learning rates.

Our contributions can be summarized as follows. Firstly, we introduce new
tight causal bounds for partially observable transfer learning algorithms. To
approximate these bounds, we develop sampling algorithms that sequentially
solve refined linear programming problems to obtain valid samples. We
demonstrate that under mild assumptions on sampling distribution, the ordered
statistics generated by our algorithms can converge to the bounds obtained by
discretization optimization problems in probability. Moreover, with the help
of optimization procedure, the convergence results can be enhanced to almost
surely convergence. Additionally, our algorithms incorporate estimation error,
which is often neglected in previous literature [41, 19, 25]. In the Task 2
where the causal effect can be fully identified, we compute the sample size
required to achieve $\epsilon$-identification [22]. Secondly, we provide
theoretical evidence that our algorithms consistently outperform classical
algorithms, as shown in Table 1. Our theoretical results illustrate how our
bounds impact the gap-dependent regrets and minimax regrets in terms of bandit
quantities, such as the cardinality of action sets. Moreover, our transfer
learning algorithms only require several causal bounds rather than the whole
dataset, which may show advantages when transferring the whole dataset is
costly. Thirdly, we consider transfer learning with function approximation in
Task 3 and develop a context-dependent method to handle the bounds and improve
the learning rate. Our regret demonstrates an improvement in dependence on
policy space $\Pi$ from $\sqrt{|\Pi|}$ to $\sqrt{\log|\Pi|}$, compared with
[41]. Finally, we conduct various numerical experiments to demonstrate the
effectiveness of our methods.

transfer learning tasks | gap-dependent upper bound | minimax upper bound
---|---|---
multi-armed bandit | $\sum_{a\in\mathcal{A},\Delta_{a}>0}\frac{\log T}{\Delta_{a}}$ | $\sqrt{|\mathcal{A}|T\log T}$
$\sum_{a\in\widetilde{\mathcal{A}^{*}},\Delta_{a}>0}\frac{\log T}{\Delta_{a}}$ | $\sqrt{|\widetilde{\mathcal{A}^{*}}|T\log T}$
contextual bandits with finite contexts | $\sum_{w\in\mathcal{W}}\sum_{a\in\mathcal{A},\Delta_{w,a}>0}\frac{\log T}{\Delta_{w,a}}$ | $\sqrt{|\mathcal{W}||\mathcal{A}|T\log T}$
$\sum_{w\in\mathcal{W}}\sum_{a\in\widetilde{\mathcal{A}^{*}}(w),\Delta_{w,a}>0}\frac{\log T}{\Delta_{w,a}}$ | $\sum_{w\in\mathcal{W}}\sqrt{|\widetilde{\mathcal{A}^{*}}(w)|\mathbb{P}(W=w)T\log T}$
contextual bandits with function approximation | not applicable | $\sqrt{|\mathcal{A}|T\log(\delta^{-1}|\mathcal{F}|\log T)}$
$\sqrt{\mathbb{E}_{W}[|\mathcal{A}^{*}(W)|]T\log(\delta^{-1}|\mathcal{F}^{*}|\log
T)}$
Table 1: Comparison with classical bandit algorithms (row 2,4,6) and ours (row 3,5,7). Here, we hide the absolute constants.  transfer learning tasks | minimax lower bound | note
---|---|---
multi-armed bandit | $\Omega\left(\sqrt{|\mathcal{A}|T}\right)$ | $\widetilde{\mathcal{A}^{*}}:=\\{a\in\mathcal{A}|h(a)\geq\mu^{*}\\}\subset\mathcal{A}$
$\Omega\left(\sqrt{|\widetilde{\mathcal{A}^{*}}|T}\right)$
contextual bandits with finite contexts | $\Omega\left(\sqrt{|\mathcal{W}||\mathcal{A}|T}\right)$ |  $\sum_{w\in\mathcal{W}}\sqrt{|\widetilde{\mathcal{A}^{*}}(w)|\mathbb{P}(W=w)}$ $\leq\sqrt{\sum_{w\in\mathcal{W}}|\mathcal{A}^{*}(w)|}$
$\Omega\left(\sum_{w\in\mathcal{W}}\sqrt{|\widetilde{\mathcal{A}^{*}}(w)|\mathbb{P}(W=w)T}\right)$
contextual bandits with function approximation | $\Omega\left(\sqrt{|\mathcal{A}|T\log(|\mathcal{F}|)}\right)$ |  $\mathcal{F}^{*}\subset\mathcal{F}$ and $\mathcal{A}^{*}(w)\subset\mathcal{A}$ for each $w\in\mathcal{W}$
$\Omega\left(\sqrt{\mathbb{E}_{W}[|\mathcal{A}^{*}(W)|]T\log(|\mathcal{F}^{*}|)}\right)$
Table 2: Continued table of Table 1.

###  1.1 Related Work

Our work is related to prior research on causal bounds. In [30], a general
calculus known as do-calculus is developed for identifying causal effects
using probabilistic tools. For non-identifiable causal problems, Tian and
Pearl [36] derives a model-free causal bound. Zhang and Bareinboim [40]
formulates a linear programming approach to obtain a causal bound in a
discrete setting, while Shridharan and Iyengar [33] makes this approach
scalable. Li and Pearl [18, 20] extend these methods to non-binary outcomes,
and Zhang and Bareinboim [41] employs instrumental variables to extend them to
continuous outcomes. However, these LP-based methods may not be tight and rely
on structural assumptions on hidden confounders. Li and Pearl [19] is the
first to consider partially observable back-door and front-door criteria and
employs a non-linear optimization problem to compute causal bounds.
Nonetheless, solving a non-linear optimization problem is computationally
intensive and may get trapped in local optima. Duarte et al. [6] summarize
these optimization-based methods and provides an automated approach to causal
inference in discrete settings. Zhang et al. [42] employ a Markov Chain Monte
Carlo (MCMC) method to approximate causal bounds using observational and
experimental data. However, this method is not directly applicable in our
setting because the agent in our scenario has access to partial knowledge
about latent confounders, whereas Zhang et al. [42] make structural
assumptions on latent confounders. As a result, Zhang et al. [42] only need
sample a random vector from Dirichlet distributions while we need to sample
constrained table from distributions supported on more complex simplex.

Our work is also closely linked to transfer learning. Zhang and Bareinboim
[40], Lazaric et al. [17] investigate transfer learning in multi-armed bandit
problems. Cai et al. [3] examine transfer learning in contextual bandits with
covariate shift, where two tasks share the same reward function (causal
effects) across two bandits. Liu et al. [24] apply transfer learning
techniques in recommendation systems. Liu et al. [25] extend the ideas in [40,
41] to reinforcement learning settings. A similar work is [35], which uses a
partially missing offline dataset to enhance the performance of online
learning in linear bandits. Though several papers [28, 29] investigate
partially observable contextual bandits, we found few papers focusing on
transfer learning in partially observable contextual bandits.

Partially Observable Markov decision process (POMDP), including general
partially observable dynamical systems [37], also shares the similarity with
our setting. Researchers have developed various methods to address causal
inference in POMDPs. For example, Guo et al. [12] use instrumental variables
to identify causal effects, while Shi et al. [32], Lu et al. [26] extend this
approach to general proxy variables in offline policy evaluation. In online
reinforcement learning, Jin et al. [13], Wang et al. [38] use the backdoor
criterion to explicitly adjust for confounding bias when confounders are fully
observable. They also incorporate uncertainty from partially observable
confounders into the Bellman equation and demonstrate provably optimal
learning with linear function approximation in both fully and partially
observable tasks. However, due to the complexity of reinforcement learning,
transfer learning in POMDPs with the general function approximation still
remains unknown. In our task 3, we address the problem of partially observable
contextual bandit with the general function approximation under realizability
assumption, which shows the potential to generalize to POMDPs and other
related settings.

##  2 Preliminaries

_Causal models._ In this section, we introduce the basic notations and
definitions used throughout the paper. We use capital letters to denote
variables ($X$) and small letters for their values ($x$). Let $\mathcal{X}$
stand for the domain of $X$, and $|\mathcal{X}|$ for its cardinality if $X$ is
finite and discrete. We use $F(x)$ to represent the cumulative distribution
function for random variable $X$.

We will use structural causal models (SCMs) [31] as the basic semantical
framework of our analysis. A SCM $\mathcal{M}$ consists of a set of observed
(endogenous) variables and unobserved (exogenous) variables. The values of
each endogenous variable are determined by a structural function taking as
argument a combination of the other endogenous and exogenous variables. A
causal diagram associated with the SCM $\mathcal{M}$ is a directed acyclic
graph where nodes correspond to variables and edges represent causal relations
(see the causal graph of TLPOCB in Figure 1).

_Multi-armed bandit._ We now define the MAB setting using causal language. An
agent for a stochastic MAB is given a SCM $\mathcal{M}$ with a decision node
$A$ representing the arm selection and an outcome variable $Y$ representing
the reward. For arm $a\in\mathcal{A}$, its expected reward $\mu_{a}$ is thus
the effect of the action $do(a)$, i.e., $\mu_{a}=\mathbb{E}[Y|do(a)]$. Let
$\mu^{*}=\max_{a\in\mathcal{A}}\mu_{a}$ and $a^{*}$ denote the optimal
expected reward and the optimal arm, respectively. At each round
$t=1,2,\cdots,T$, the agent performs an action $do(A_{t}=a_{t})$ and observes
a reward $Y_{t}$. The objective of the agent is to minimize the cumulative
regret, namely,

$Reg(T)=T\mu^{*}-\sum_{t=1}^{T}\mathbb{E}[Y_{t}].$ (1)

_Contextual bandit._ We then describe the contextual bandit in causal setting.
An agent for a contextual bandit is given a SCM $\mathcal{M}$ with an observed
context variable $W$ besides the arm selection node $A$ and a reward variable
$Y$. At each round $t=1,2,\cdots,T$, the agent can observe a context $w_{t}$
and performs an action $do(A_{t}=a_{t})$ based on contexts and historical
information. For each arm $a\in\mathcal{A}$, its expected reward given the
context $w$ is defined as $\mu_{a,w}=\mathbb{E}[Y|do(a),w]$. Let $\mu^{*}_{w}$
denote the optimal expected reward with respect to the context $w$. The
objective of the agent is to minimize the cumulative regret, namely,

$Reg(T)=\sum_{t=1}^{T}\mathbb{E}[\mu^{*}_{w_{t}}-\mu_{a,w_{t}}|w_{t}].$ (2)

Here, the expectation is taken w.r.t the randomness of algorithms.

However, the regret in such setting typically scales with $|\mathcal{W}|$ as
it can be regarded as generic reinforcement learning problems. A practical way
to avoid dependent on $|\mathcal{W}|$ is to use function approximation
methods. We assume that the agent has access to a class of reward functions
$\mathcal{F}\subset\mathcal{W}\times\mathcal{A}\to[0,1]$ (e.g., linear
function classes) that characterizes the mean of the reward distribution for a
given context-action pair.

######  Assumption 2.1 (Realizability)

There exists a function $f^{*}\in\mathcal{F}$ such that $f(w,a)=E[Y|w,do(a)]$.

This realizability assumption is standard in contextual bandit literature [34,
8, 10]. Let $\pi_{f}(w)=\mathop{\arg\max}_{a\in\mathcal{A}}f(w,a)$ denote the
policy induced by the regression function $f\in\mathcal{F}$. The set of all
induced policies is denoted as $\Pi=\\{\pi_{f}|f\in\mathcal{F}\\}$, which
forms the policy space. The objective of the agent is to achieve low regret
with respect to the optimal policy $\pi_{f^{*}}$, and the cumulative regret
over time horizon $T$ is defined as follows:

$Reg(T)=\sum_{t=1}^{T}\mathbb{E}[f^{*}(w_{t},\pi_{f^{*}}(w_{t}))-f^{*}(w_{t},\pi_{f}(w_{t}))|w_{t}].$
(3)

$A$$Y$$W$$U$ Figure 1: A causal model with unobserved context $U$ and observed
context $W$, where the causal relationship between $W$ and $U$ can be
arbitrary.

The presence of unobserved confounder $U$ can make the transfer learning tasks
challenging. Next, we give an example to show that direct approaches can lead
to a policy function that is far from the true optimal policy.

Example. Consider a 2-arm contextual bandit problem, where the action $A$,
context $U,W$ are binary. At the beginning of each round, two binary
contextual variables $U,W$ are sampled from two independent Bernoulli
distribution, $\mathbb{P}(U=1)=0.9,\mathbb{P}(W=1)=0.5.$ The context variables
$U,W$ affect the reward $Y$ received during each round according to Table 3.

The expert agent can observe the contextual variable $U,W$ and executes a
context-aware optimal policy
$\pi^{*}_{expert}:\mathcal{W}\times\mathcal{U}\to\mathcal{A}$. As a result,
the expert generates multiple data points to obtain an observational
distribution $\mathbb{P}(A,W)$ as shown in Table 4. Now we compute the causal
effect

$\mathbb{E}[Y|do(A=0),W]=10\times 0.1+0.9\times 0.9=1.81,\forall
W\in\\{0,1\\}$

and

$\mathbb{E}[Y|do(A=1),W]=0\times 0.1+1\times 0.9=0.9,\forall W\in\\{0,1\\}.$

Therefore, the optimal policy for the agent is $\pi_{agent}^{*}(W)=0$ with
probability $1$. However, the policy differs a lot from $\pi^{*}_{expert}$ as
$\pi^{*}_{expert}$ mainly select the arm $1$.

Upon closer examination of the example, it becomes clear that the asymmetrical
probability mass function of the hidden context variable $U$ leads to a
significant difference between the optimal expert and agent policies.
Specifically, for the context $U=1$ that occurs frequently, the rewards of the
two arms are relatively similar, while for the rarely occurring context $U=0$,
the rewards differ significantly between the two arms. If the agent has
knowledge of the distribution of $U$, it can infer that the observed rewards
may be heavily influenced by the skewness from $F(u)$ and adjust its decision-
making accordingly to make the correct choices.

$(U,W)$ | $(0,0)$ | $(0,1)$ | $(1,0)$ | $(1,1)$
---|---|---|---|---
$\mathbb{E}[Y|do(A=0)]$ | $0$ | $0$ | $1$ | $1$
$\mathbb{E}[Y|do(A=1)]$ | $10$ | $10$ | $0.9$ | $0.9$
Table 3: Reward table $(A,W)$ | $(0,0)$ | $(0,1)$ | $(1,0)$ | $(1,1)$
---|---|---|---|---
$\mathbb{P}(A,W)$ | $0.05$ | $0.05$ | $0.45$ | $0.45$
Table 4: observation probability for agents

##  3 Transfer Learning via Causal Inference

In this section, we connect causal analysis with transfer learning [40, 25, 3]
in RL by discussing a transfer scenario between two different agents. We apply
do-calculus to systematically estimate the expected reward of each arm for the
target agent.

###  3.1 Task 1: transfer from contextual bandit to MAB

We first consider an off-policy learning problem between an contextual bandit
expert and a MAB agent. Contextual bandits [1, 23, 4] is a variation of MAB
where the expert can observe extra contextual information $W$ associated with
the reward signal $Y$. The expert follows certain policy and summarizes its
experiences as the joint distribution $\hat{F}(a,y,w)$. However, there exists
a latent confounder $U$ that affects the causal effects between actions and
rewards, making the observed contextual bandit model incomplete. The agent,
who is observing the expert interacting with the environment, wants to be more
efficient and reuse the observed $\hat{F}(a,y,w)$ with the help of extra prior
knowledge about $U$, i.e., $\hat{F}(u)$, to find the optimal policy faster.

Causal bounds. This transfer scenario is depicted in Figure 1, where the
actions $A$, outcomes $Y$, context $W$ and $U$, and causal structures used by
the expert and the agent are identical. In the first task, the MAB agent is
unable to observe contexts, but we will also examine the case where the agent
can partially observe contexts in the task 2 and 3. The missing contexts may
be due to privacy protection or legal restrictions. As the new agent cannot
observe $W$ or $U$, its objective is to minimize regret as defined in equation
(1).

One can find the optimal action $do(A=a^{*})$ by evaluating
$\mathbb{E}[Y|do(a)]$. Therefore, the off-policy learning problem is
equivalent to identifying the causal effect $\mathbb{E}[Y|do(a)]$ given the
observational distribution ${F}(a,y,w)$ and prior knowledge $F(u)$. Although
$U$ is unobserved during online learning, its distribution can be usually
known regardless of the model itself (e.g., $U$ stands for gender, gene type,
blood type, or age). Alternatively, if costs permit, one can estimate ${F}(u)$
by re-testing within a small sampled sub-population. However, even though
$W\cup U$ is assumed to be sufficient, the causal effects of the action $A$ on
the reward $Y$ is non-identifiable from incomplete experiences ${F}(a,y,w)$
and ${F}(u)$, because the back-door path $A\leftarrow U\rightarrow Y$ is still
unblocked. This means that the causal effects of $A$ on $Y$ cannot be
estimated without bias, regardless of sample size.

However, we can tight obtain bounds on the causal effects via an optimization
problem when given a prior distribution $F(u)$ and $F(a,y,w)$. The
optimization problem is as follows:

$\begin{array}[]{rcl}&&\sup/\inf\mathbb{E}_{\mathcal{M}}[{Y|do(a)}]\\\
&s.t.&F_{\mathcal{M}}(a,y,w)=F(a,y,w),\\\ &&F_{\mathcal{M}}(u)=F(u).\\\
\end{array}$ (4)

Here, the sup/inf is taken over all causal models $\mathcal{M}$, and
$F_{\mathcal{M}}$ represents the distributions in the causal model
$\mathcal{M}$. Denote the solutions to (4) as $h(a)$ and $l(a)$, respectively.
Since the optimization is performed over all compatible causal models, the
resulting bounds are guaranteed to be tight. It is worth noting that the
sufficient and necessary condition for causal identification is that $h(a)$ is
equal to $l(a)$. We provide a formal statement of this result in the appendix.
This idea is similar to that proposed in other works, such as [30, 42, 36].

In Theorem 3.1, we provide a specific version of the optimization problem (4)
to obtain bounds on the causal effects of actions on rewards. We consider the
estimation error $\epsilon$ and distinguish between known and unknown
variables by using $\hat{F}$ to represent the observed distributions and $F$
to represent the unknown variables.

###### Theorem 3.1

Given a causal diagram $\mathcal{G}$ and a distribution compatible with
$\mathcal{G}$, let $\\{W,U\\}$ be a set of variables satisfying the back-door
criterion in $\mathcal{G}$ relative to an ordered pair $(A,Y)$, where
$\\{W,U\\}$ is partially observable, i.e., only probabilities $\hat{F}(a,y,w)$
and $\hat{F}(u)$ with the maximum estimation error $\epsilon$, the causal
effects of $A$ on $Y$ are then bounded as follows:

$l(a_{0})\leq\mathbb{E}[Y|do(a_{0})]\leq h(a_{0}),$

where $l(a_{0})$ and $h(a_{0})$ are solutions to the following functional
optimization problem for any given $a_{0}$

$\displaystyle
l(a_{0})=\inf\int_{w\in\mathcal{W},u\in\mathcal{U}}\int_{y\in\mathcal{Y}}ydF(y|a_{0},w,u)dF(w,u)$
$\displaystyle
h(a_{0})=\sup\int_{w\in\mathcal{W},u\in\mathcal{U}}\int_{y\in\mathcal{Y}}ydF(y|a_{0},w,u)dF(w,u)$
$\displaystyle s.t.$
$\displaystyle\int_{u\in\mathcal{U}}dF(a,y,w,u)=F(a,y,w),\forall(a,y,w)\in\mathcal{A}\times\mathcal{W}\times\mathcal{U}$
$\displaystyle\int_{a\in\mathcal{A},y\in\mathcal{Y},w\in\mathcal{W}}dF(a,y,w,u)=F(u),\forall
u\in\mathcal{U}$
$\displaystyle\int_{y\in\mathcal{Y}}dF(a,y,w,u)=F(a,w,u),\forall(a,w,u)\in\mathcal{A}\times\mathcal{W}\times\mathcal{U}$
$\displaystyle\int_{a\in\mathcal{A}}dF(a,w,u)du=F(w,u),\forall(w,u)\in\mathcal{W}\times\mathcal{U}$
$\displaystyle
F(y|a,w,u)F(a,w,u)=F(a,y,w,u),\forall(a,y,w,u)\in\mathcal{A}\times\mathcal{Y}\times\mathcal{W}\times\mathcal{U}$
$\displaystyle|F(a,y,w)-\hat{F}(a,y,w)|\leq\epsilon,\forall(a,y,w)\in\mathcal{A}\times\mathcal{Y}\times\mathcal{W}$
$\displaystyle|F(u)-\hat{F}(u)|\leq\epsilon,\forall u\in\mathcal{U}.$

Here the inf/sup is taken with respect to all unknown cumulative distribution
functions $F(a,y,w,u)$, $F(a,w,u)$, $F(y|a,w,u)$, $F(w,u)$, $F(a,y,w)$ and
$F(u)$.

The functional optimization problem presented in Theorem 3.1 provides tight
lower and upper bounds on the average causal effect $l(a_{0})$ and $h(a_{0})$,
respectively, for any given $a_{0}\in\mathcal{A}$. Our results generalize
those of [19] to random variables with estimation error, while [19] only
considers the case of discrete random variables without estimation error.
Moreover, this optimization problem can be applied to both parametric and non-
parametric cases.

It is essential to consider constraints for all $a\in\mathcal{A}$, rather than
just the given $a_{0}$ of interest, as only considering constraints for
$a_{0}$ would result in non-tight bounds. As an example, the optimal solutions
generated by the non-linear optimization problem in [19] may not belong to any
valid causal models, leading to non-tight bounds. Therefore, one need to
consider all values of the given random variable $X$ to obtain tight bounds,
even if only causal bounds under a specific intervention $do(X=x)$ are
required.

The original optimization problem is challenging to solve due to its
inefficiency and intractability. Firstly, the functional constraints for
unknown distributions make the optimization problem intractable. Secondly,
solving a non-linear optimization problem can often get trapped in local
optima. In some cases, narrow causal bounds that do not include the true
causal effects may lead to critical false decisions. To overcome these
challenges, it is necessary to approximate the problem to make it easier to
solve and to obtain global solutions with high probability.

The optimization problem can be naturally simplified by probability mass
functions for discrete random variables with bounded support. To extend this
approach to general random variables, we only consider random variables with
bounded support and discretize $\mathcal{A}$, $\mathcal{W}$, $\mathcal{U}$,
and $\mathcal{Y}$ into $n_{\mathcal{A}}$, $n_{\mathcal{W}}$,
$n_{\mathcal{U}}$, and $n_{\mathcal{Y}}$ disjoint blocks, respectively. For
random variables that take in finite values, they have natural discretization.
We first define

$x_{ijkl}=\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}dF(a,y,w,u)$

and then integrate both sides of the first equality over $\mathcal{A}_{i}$,
$\mathcal{Y}_{j}$, and $\mathcal{W}_{k}$ to obtain

$\sum_{l}x_{ijkl}=\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k}}dF(a,y,w).$

This allows us to reformulate the first equality in terms of integration
instead of the original pointwise equality.

As the discretization becomes finer, i.e., $diam(\mathcal{A}_{i})$,
$diam(\mathcal{Y}_{j})$, $diam(\mathcal{W}_{k})$, and $diam(\mathcal{U}_{l})$
approach zero for all $(i,j,k,l)$, the approximation error converges to zero
for good distributions. For discrete and finite random variables, the number
of constraints is finite so the approximation error can be exactly zero for
natural discretization. The other equalities hold naturally if the first
constraint is satisfied. For the constraints

$\int_{a\in\mathcal{A},y\in\mathcal{Y},w\in\mathcal{W}}dF(a,y,w,u)=F(u)$

for all $u\in\mathcal{U}$, we integrate these constraints using the same
approach as

$\sum_{ijk}x_{ijkl}=\int_{u\in\mathcal{U}_{l}}dF(u),\forall l.$

Compared with the original functional constraints in distributions, the linear
constraints for $x_{ijkl}$ are much easier to handle.

After discretization, the objective of the original optimization problem is

$\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a)}]=\sum_{j,k,l}\frac{y_{j}x_{ijkl}\sum_{i^{\prime},j^{\prime}}x_{i^{\prime}j^{\prime}kl}}{\sum_{j^{\prime}}x_{ij^{\prime}kl}},$
(5)

where $y_{j}$ is chosen to be
$\frac{\int_{y\in\mathcal{Y}_{j}}ydy}{\int_{y\in\mathcal{Y}_{j}}dy}$, as this
option can reduce the approximation error (see the appendix for more details).
If $\mathcal{Y}_{j}$ is an interval, then the above choice of $y_{j}$ is just
the midpoint of $\mathcal{Y}_{j}$,

The first transfer learning task requires obtaining causal bounds from the
number of $n_{\mathcal{A}}$ optimization problems. Since every optimization
problem shares the same feasible region, it is efficient to solve all
optimization problems in a unified way. To obtain the global solutions, we use
Monto-Carlo method to approximate the above discrete optimization problem.

Monte-Carlo algorithm. Monte Carlo (MC) algorithms are a key approach for
sampling causal models subject to constraints. However, efficiently sampling
probability tables with row and column constraints can be challenging. After
discretization, the problem of sampling $x_{ijkl}$ is equivalent to sampling
from a simplex $\mathcal{D}$ defined by the linear constraints

$\displaystyle\sum_{l}x_{ijkl}=\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k}}dF(a,y,w),\forall(i,j,k)\in[n_{\mathcal{A}}]\times[n_{\mathcal{Y}}]\times[n_{\mathcal{W}}]$
(6) $\displaystyle\sum_{ijk}x_{ijkl}=\int_{u\in\mathcal{U}_{l}}dF(u),\forall
l\in[n_{\mathcal{U}}].$

Let

${\theta}_{ijk}=\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k}}d{F}(a,y,w).$
(7)

Similarly, we can define $\theta_{l}$ and $\hat{\theta}_{l}$, so we rewrite
the linear equations as

$\displaystyle\sum_{l}x_{ijkl}={\theta}_{ijk},\forall
i\in[n_{\mathcal{A}}],j\in[n_{\mathcal{Y}}],k\in[n_{\mathcal{W}}]$ (8)
$\displaystyle\sum_{ijk}x_{ijkl}={\theta}_{l},\forall l\in[n_{\mathcal{U}}].$

The overall equalities provide
$n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}+n_{\mathcal{U}}-1$ linearly
independent constraints, as both types of equalities imply
$\sum_{ijkl}x_{ijkl}=1$. Since there are
$n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}n_{\mathcal{U}}$ unknown
variables, we need to determine the value of
$n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}n_{\mathcal{U}}-n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}-n_{\mathcal{U}}+1$
unknowns.

Directly sampling $x_{ijkl}$ from distributions supported on $[0,1]$ and
rejecting invalid samples that do not satisfy the inequality constraints can
be sample-inefficient. To address this issue, we can incorporate inequalities
to shrink the support of each unknown variable. For instance, Li and Pearl
[19] proposed using the bounds

$x_{ijkl}\leq\min\\{\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k}}dF(a,y,w),\int_{u\in\mathcal{U}_{l}}dF(u)\\}$

and

$x_{ijkl}\geq\max\\{0,\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k}}dF(a,y,w)+\int_{u\in\mathcal{U}_{l}}dF(u)-1\\}$

in their optimization problem. However, the support of each unknown $x_{ijkl}$
in [19]:
$[\max\\{0,\theta_{ijk}+\theta_{l}-1\\},\min\\{\theta_{ijk},\theta_{l}\\}]$,
is not as tight as those found by solving the linear programming problem (9):

$\displaystyle\min/\max x_{ijkl}$ (9) $\displaystyle s.t.$ linear constraints
(8) are satisfied $\displaystyle 0\leq
x_{i^{\prime}j^{\prime}k^{\prime}l^{\prime}}\leq
1,\forall(i^{\prime},j^{\prime},k^{\prime},l^{\prime}).$

Clearly, the solutions generated by [19] may not satisfy all the constraints
in (6), which further contributes to the lack of tightness in their approach.
We provide evidence for this claim by reporting the proportion of valid
samples obtained with different sample spaces in Table 5 for the example
discussed in Section 4.

sample space for $x_{ijkl}$ | valid sample proportion
---|---
$[0,1]$ | $\approx 0$
$[\max\\{0,\theta_{ijk}+\theta_{l}-1\\},\min\\{\theta_{ijk},\theta_{l}\\}]$ | $<10^{-4}$
support found by LP(9) | $0.3\%$
Algorithm 1 | $100\%$
Table 5: Valid sample proportion with different sample spaces for the given
example in Section 4.

We also report the simulation results in Section 4 for causal bounds, which
evidently support our arguments.

While the individual bounds for $x_{ijkl}$ obtained by (9) are tight, the
sample efficiency is still unsatisfactory. To improve sample efficiency, we
introduce the sampling algorithm based on sequential LP. Suppose that we find
a linearly independent variable index set
$S:=\\{n_{1},n_{2},\cdots,n_{|S|}\\}$ with cardinality
$n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}n_{\mathcal{U}}-n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}-n_{\mathcal{U}}+1$
of (8). For the first variable $x_{n_{1}}$, we solve (9) to find its support
$[l_{n_{1}},h_{n_{1}}]$, and we sample a $\hat{x}_{n_{1}}$ from a user-given
distribution truncated to $[l_{n_{1}},h_{n_{1}}]$. Then, for the $n_{i}$ step,
the previous values of $x_{n_{1}},\cdots,x_{n_{i-1}}$ have been determined by
sampling. We add the constraints for $x_{n_{j}}$, $j=1,2,\cdots,i-1$, where it
is equal to its corresponding value. Together with new constraints in (9), we
can find a support $[l_{n_{i}},h_{n_{i}}]$ and sample a valid value for
$x_{n_{i}}$ by solving

$\displaystyle\min/\max x_{n_{i}}$ (10) $\displaystyle s.t.$ linear
constraints (8) are satisfied $\displaystyle 0\leq
x_{i^{\prime}j^{\prime}k^{\prime}l^{\prime}}\leq
1,\forall(i^{\prime},j^{\prime},k^{\prime},l^{\prime})$ $\displaystyle
x_{n_{j}}=\hat{x}_{n_{j}},j=1,2,\cdots,i-1,$

where $\hat{x}_{n_{j}}$ is a sampled value for $x_{n_{j}}$. After $|S|$ steps,
the remaining $x_{ijkl}$ with its index $(i,j,k,l)\notin S$ can be solved by
linear equations (8). These sequential LP steps ensure that we always find
valid samples in the simplex defined by (9).

Sequentially solving LPs and sampling components of $\mathbf{x}$ induce a
distribution supported on the simplex defined by $\eqref{eq: linear
programming to find support}$. Although this is the most computationally
extensive step, it can significantly improve the sample efficiency. In
comparison, the sample efficiency of directly sampling $x_{ijkl}$ from
distributions supported on $[0,1]$ or using the bounds proposed in [19] is
much lower, as shown in Table 5. We will discuss our sampling method on
general simplex in appendix.

The remaining concern is the estimation error in RHS of (6). Denote

$\hat{\theta}_{ijk}=\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k}}d\hat{F}(a,y,w).$

Since $\theta_{ijk}\in[0,1]$, the variance of one sample is at most
$\frac{1}{4}$. If ${\theta}_{ijk}$ has $n$ i.i.d. samples, then its largest
variance of $\hat{\theta}_{ijk}$ is $\frac{1}{4n}$. We can simply set
$\epsilon=\frac{1}{2\sqrt{n}}$ if $n$ is given. We can sample $\theta_{l}$ and
$\theta_{ijk}$ from distributions with known parameters $\hat{\theta}_{l}$ and
$\hat{\theta}_{ijk}$:

$\displaystyle\hat{\theta}_{ijk}=\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k}}d\hat{F}(a,y,w),\forall
i\in[n_{\mathcal{A}}],j\in[n_{\mathcal{Y}}],k\in[n_{\mathcal{W}}]$ (11)
$\displaystyle\hat{\theta}_{l}=\int_{u\in\mathcal{U}_{l}}d\hat{F}(u),\forall
l\in[n_{\mathcal{U}}].$

For example, if one want to reflect the concentration property, then one can
choose the truncate Gaussian distribution
$\mathcal{N}(\hat{\theta}_{x},\frac{1}{4n_{x}})$ for $x=ijk$ or $x=l$. If one
expects the worst cases, then one can choose the uniform distribution for
$\theta_{x}$ with discrepancy parameter $\epsilon$.

Algorithm 1 MC for causal bound

1:cumulative distribution functions $\hat{F}(a,y,w)$ and $\hat{F}(u)$,
discrepancy parameter $\epsilon$, sampling distribution ${F}_{s}$, batch size
$B$

2:Discrete the variable domain
$\mathcal{A},\mathcal{Y},\mathcal{W},\mathcal{U}$

3:Select a linearly independent variable index set $S$ with size
$n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}n_{\mathcal{U}}-n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}-n_{\mathcal{U}}+1$
for linear equations (8)

4:Compute each $\hat{\theta}_{ijk}$ and $\hat{\theta}_{l}$ according to (11)

5:Set a counter $cnt$ to $0$

6:while $cnt<B$ do

7: Sample ${\theta}_{x}$ from the uniform distribution supported on
$[\max\\{\hat{\theta}_{x}-\epsilon,0\\},\max\\{\hat{\theta}_{x}+\epsilon,1\\}]$
for all $x=ijk$ or $x=l$

8: Sequentially solve LP (10) to find support $[l_{ijkl},h_{ijkl}]$ for each
$x_{ijkl}$ with $(i,j,k,l)\in S$ and sample a value from $F_{s}$ truncated to
$[l_{ijkl},h_{ijkl}]$

9: Solving remaining $x_{ijkl}$ by linear equations (8) for all
$(i,j,k,l)\notin S$

10: Compute the causal effect $b_{cnt}(a)$ by (5) for each $a$

11: $cnt=cnt+1$

12:For each $a$, sort $B$ valid causal bound and get
$b_{(1)}(a),b_{(2)}(a),\cdots,b_{(B)}(a)$

13:$l(a)=b_{(1)}(a)$ and $h(a)=b_{(B)}(a)$ for $a\in\mathcal{A}$

The optimization problem (4) after discretization is

$\displaystyle\max/\min\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a)}]$ (12)
$\displaystyle s.t.$ $\displaystyle\sum_{l}x_{ijkl}={\theta}_{ijk},\forall
i\in[n_{\mathcal{A}}],j\in[n_{\mathcal{Y}}],k\in[n_{\mathcal{W}}]$
$\displaystyle\sum_{ijk}x_{ijkl}={\theta}_{l},\forall l\in[n_{\mathcal{U}}].$

If all referred random variables are discrete, the optimization (12) can be
exactly the same as (4) for natural discretization. For general random
variables, it is still an open problem that whether the solution to (12) will
converge to the solution to (4) as the discretization becomes finer. However,
we have the following probability convergence results for variables
$\mathbf{x}:=(x_{ijkl})$. Denote the solutions to (12) as $\hat{l}(a)$ and
$\hat{h}(a)$. For simplicity, we denote the induced sampling measure for
$\mathbf{x}$ as $\mathbb{P}_{s}$. The existence and uniqueness can be easily
proved by Kolmogorov’s extension theorem.

###### Proposition 3.1

Assume that the sampling measure $\mathbb{P}_{s}$ satisfies
$\forall\mathbf{x}\in\mathcal{D}$, and $\forall\delta>0$,

$\mathbb{P}_{s}(\mathcal{B}(\mathbf{x},\delta)\cap\mathcal{D})>0,$

where $\mathcal{B}(\mathbf{x},\delta)$ is a ball centered at $\mathbf{x}$ with
radius $\delta$. If the discrepancy parameter is set to $0$, then $b_{(1)}(a)$
converges to $\hat{l}(a)$ in probability and $b_{(B)}(a)$ converges to
$\hat{h}(a)$ in probability for $B\to\infty$.

The condition
$\mathbb{P}_{s}(\mathcal{B}(\mathbf{x},\delta)\cap\mathcal{D})>0$ means that
the sampling distribution can cover all feasible models. This condition can be
satisfied by various continuous distributions such as the uniform
distribution, truncated Gaussian distribution, and others.

Similar to [42], we can establish a concentration result for our sampling
algorithm using Chernoff’s bound. However, this result is not as useful as
Proposition 3.1. Firstly, the concentration property relies on the
distribution of causal bounds, which is often complex and difficult to know in
practice. Secondly, people are usually more interested in convergence results
than concentration results in approximation problems. For example, if one has
several $l(a)$ samples, it is more reasonable to use the minimum value among
them rather than the average results.

Regarding other statistical properties, Mosteller [27] shows that if the
distribution on causal bounds $F_{b}(x)$ is continuous and has a density
$p_{b}(x)$, then the $q$-th quantile $b_{[Bq]}$ asymptotically follows the
normal distribution
$\mathcal{N}(F_{b}^{-1}(q),\frac{q(1-q)}{B[p_{b}(F_{b}^{-1}(q))]^{2}})$.

To accelerate the convergence speed of Algorithm 1, we can incorporate an
optimization procedure OPT(min/max, object, feasible domain $\mathcal{D}$,
initial guess $\mathbf{x}_{0}$). The optimization procedure OPT takes as input
the objective function to minimize/maximize, the feasible domain
$\mathcal{D}$, and an initial guess $\mathbf{x}_{0}$. The procedure OPT seeks
to find local optima $\mathbf{x}_{loc}\in\mathcal{D}$ that optimizes the
objective function locally. Specifically, in each iteration of Algorithm 1, we
use the sampled value $\mathbf{x}$ as the initial guess $\mathbf{x}_{0}$ and
feed it to OPT. The output of OPT is then used as the updated estimate of
causal bounds. The modified algorithm with OPT can be found in the appendix.
By leveraging the optimization procedure, we can further enhance the result in
Proposition 3.1 under mild assumptions on OPT.

###### Proposition 3.2

Assume that the sampling measure $\mathbb{P}_{s}$ satisfies
$\forall\mathbf{x}\in\mathcal{D}$, and $\forall\delta>0$,

$\mathbb{P}_{s}(\mathcal{B}(\mathbf{x},\delta)\cap\mathcal{D})>0,$

where $\mathcal{B}(\mathbf{x},\delta)$ is a ball centered at $\mathbf{x}$ with
radius $\delta$. Given a deterministic procedure OPT which satisfies for any
local optima $\mathbf{x}_{loc}$, there exists $\delta>0$ such that for any
initial guess
$\mathbf{x}_{0}\in\mathcal{B}(\mathbf{x}_{loc},\delta)\cap\mathcal{D}$, OPT
can output $\mathbf{x}_{loc}$ as a result. If the discrepancy parameter is set
to $0$, then $b_{(1)}(a)$ and $b_{(B)}(a)$ converge almost surely to
$\hat{l}(a)$ and $\hat{h}(a)$ for $B\to\infty$, respectively.

This result suggests that the modified algorithm with OPT can converge to the
optimal solution with higher rate, and the convergence speed can be
accelerated compared to the original algorithm. Intuitively, the optimization
procedure OPT makes the probability $F_{b}$ concentrate at local optima rather
than spread over the whole feasible domain. Additionally, optimization
procedures can usually work effectively at local regions and guarantee local
optimality for sufficiently close initial guesses. Therefore, the assumption
on OPT is not so strict.

MAB. We now consider the first transfer learning task for
$|\mathcal{A}|<\infty$. The algorithm proceeds as follows: first, we remove
any arm $a$ for which $h(a)<\max_{i\in\mathcal{A}}l(i)$. Next, we truncate the
upper confidence bound $U_{a}(t)$ for the remaining actions using their
respective causal bounds. Specifically, we define the truncated upper
confidence bound as $\hat{U}_{a}(t)=\min\\{U_{a}(t),h(a)\\}$. The algorithm
then chooses the action with the highest truncated UCB and update the average
reward of the chosen action.

Algorithm 2 Transfer learning in multi-armed bandit

1:time horizon $T$, causal bound $l(a)$ and $h(a)$

2:Remove the arm $a$ for $h(a)<\max_{i\in\mathcal{A}}l(i)$ and denote the
remaining arm set as $\mathcal{A}^{*}$

3:Initialize reward vector $\hat{\mu}_{a}(1)$ and the number of pull
$n_{a}(1)$ to zero, for all $a\in\mathcal{A}^{*}$

4:for round $t=1,2,\cdots,T$ do

5: Compute the upper confidence bound
$U_{a}(t)=\min\\{1,\hat{\mu}_{a}(t)+\sqrt{\frac{2\log T}{n_{a}(t)}}\\}$

6: Truncate $U_{a}(t)$ to $\hat{U}_{a}(t)=\min\\{U_{a}(t),h(a)\\}$ for all
$a\in\mathcal{A}^{*}$

7: Choose the action
$a_{t}=\mathop{\arg\max}_{a\in\mathcal{A}^{*}}\hat{U}_{a}(t)$

8: Observe a reward $y_{t}$

9: Update the empirical mean
$\hat{\mu}_{a_{t}}(t+1)=\frac{\hat{\mu}_{a_{t}}n_{a_{t}}(t)+y_{t}}{n_{a_{t}}(t)+1}$
and the number of pulling $n_{a_{t}}(t+1)=n_{a_{t}}(t)+1$

10: For $a\neq a_{t}$, update $\hat{\mu}_{a}(t+1)=\hat{\mu}_{a}(t)$ and
$n_{a}(t+1)=n_{a}(t)$

###### Theorem 3.2

Consider a $|\mathcal{A}|$-MAB problem with rewards bounded in $[0,1]$. For
each arm $a\in\mathcal{A}$, its expected reward $\mu_{a}$ is bounded by
$[l(a),h(a)]$. Then in the Algorithm 2, the number of draws
$\mathbb{E}[N_{a}(T)]$ for any sub-optimal arm is upper bounded as:

$\mathbb{E}[N_{a}(T)]\leq\left\\{\begin{aligned}
&0,h(a)<\max_{i\in\mathcal{A}}l(i)\\\
&\frac{\pi^{2}}{6},\max_{i\in\mathcal{A}}l(i)\leq h(a)<\mu^{*}\\\ &\frac{\log
T}{\Delta_{a}^{2}},h(a)\geq\mu^{*}.\end{aligned}\right.$

As a simple corollary, the minimax upper bound is
$\mathcal{O}(\sqrt{|\widetilde{\mathcal{A}^{*}}|T\log T})$, which also matches
the lower bound $\Omega(\sqrt{|\widetilde{\mathcal{A}^{*}}|T})$ in transfer
learning setting (see more details in appendix).

###  3.2 Task 2: transfer from contextual bandit to partially observable
contextual bandit

In the second task, we consider the transfer learning problem from contextual
bandit to partially observable contextual bandit. The expert has access to the
complete contexts $W$ and $U$, while the agent can only observe partial
context $W$. The objective is to derive the causal effect
$\mathbb{E}[Y|do(a),w]$ using the knowledge $F(a,y,w,u)$.

###### Proposition 3.3

In the task 2, the causal effect is fully identified and given by

$\mathbb{E}[Y|do(a),w]=\int_{u\in\mathcal{U}}\mathbb{E}[Y|a,w,u]dF(u).$

Since $W$ and $U$ block the back-door path from $A$ to $Y$, we can use the
rules of do-calculus and condition on the value of $U$ to fully identify the
causal effect $\mathbb{E}[Y|do(a),w]$. This proposition justifies the use of
standard off-policy learning techniques that assume source and target agents
are identical.

Given that the expert provides $F(a,y,w,u)$, it is possible to compute
$F(y|a,w,u)$ and $F(u)$ from observation data. However, in practical
scenarios, estimating $F(y|a,w,u)$ and $F(u)$ can result in uncertainties.
Recent research in causal inference, such as [22, 21], has investigated the
impact of estimation error from finite samples. In particular, Li et al. [22]
introduced the concept of $\epsilon$-identification, which extends the
original identification concept and accounts for the influence of estimation
error from finite samples. To address this, we establish an
$\epsilon$-identification result using finite samples.

###### Proposition 3.4

Suppose $A$, $Y$, $W$, and $U$ are all discrete random variables with bounded
support. Assume that the samples are independently and identically
distributed. For given $a,w$ and each tuple $(y,u)$, the fraction of samples
containing $(y,u)$ is at least $\kappa$, where $\kappa$ is an absolute
positive constant. Then, for a sample size of
$n\geq\frac{2|\mathcal{U}|^{2}|\mathcal{Y}|^{2}}{\kappa\delta^{2}}\ln\left(\frac{2|\mathcal{U}|\sum_{y\in\mathcal{Y}}y}{\epsilon}\right)$,
one can achieve $\epsilon$-identification for $\mathbb{E}[Y|do(a),w]$, meaning
that $|\mathbb{E}[Y|do(a),w]-\hat{\mathbb{E}}[Y|do(a),w]|\leq\epsilon$ with
probability at least $1-\delta$. Here, $\hat{\mathbb{E}}[Y|do(a),w]$ is the
sample estimate of the causal effect.

###  3.3 Task 3: transfer from partially observable contextual bandit to
partially observable contextual bandit

We will now consider a more challenging scenario in which knowledge is
transferred between two partially observable contextual bandit agents. In this
task, the expert only provides partial model knowledge $\hat{F}(a,y,w)$ to the
agent, while the agent can have prior information $\hat{F}(u)$. In this
setting, the causal effect $\mathbb{E}[y|do(a),w]$ is partially identified.

Similarly, we need to solve the following optimization problem:

$\begin{array}[]{rcl}&&\sup/\inf\mathbb{E}_{\mathcal{M}}[{Y|do(a),w}]\\\
&s.t.&F_{\mathcal{M}}(a,y,w)=F(a,y,w),\\\ &&F_{\mathcal{M}}(u)=F(u),\\\
\end{array}$ (13)

and discrete it as Section 3.1 does. The object is

$\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a),w}]=\sum_{j,k,l}\frac{y_{j}\theta_{l}x_{ijkl}}{\sum_{j^{\prime}}x_{ij^{\prime}kl}}.$
(14)

Algorithm 3 provides causal bounds for several discrete points, which can be
generalized to the entire space $\mathcal{Y}\times\mathcal{W}$ through
interpolation.

Algorithm 3 MC for causal bound with $w$

1:cumulative distribution functions $\hat{F}(a,y,w)$ and $\hat{F}(u)$,
discrepancy parameter $\epsilon$, sampling distribution ${F}_{s}$, batch size
$B$

2:Discrete the variable domain
$\mathcal{A},\mathcal{Y},\mathcal{W},\mathcal{U}$

3:Select a linearly independent variable index set $S$ with size
$n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}n_{\mathcal{U}}-n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}-n_{\mathcal{U}}$
for linear equations (8)

4:Compute each $\hat{\theta}_{ijk}$ and $\hat{\theta}_{l}$ according to (11)

5:Set a counter $cnt$ to $0$

6:while $cnt<B$ do

7: Sample ${\theta}_{x}$ from the uniform distribution supported on
$[\max\\{\hat{\theta}_{x}-\epsilon,0\\},\max\\{\hat{\theta}_{x}+\epsilon,1\\}]$
for all $x=ijk$ or $x=l$

8: Sequentially solve LP (10) to find support $[l_{ijkl},h_{ijkl}]$ for each
$x_{ijkl}$ with $(i,j,k,l)\in S$ and sample a value from $F_{s}$ supported on
$[l_{ijkl},h_{ijkl}]$

9: Solving remaining $x_{ijkl}$ by linear equations (8) for all
$(i,j,k,l)\notin S$

10: Compute the causal effect $b_{cnt}(w,a)$ by (14) for each $a$ and $w$

11: $cnt=cnt+1$

12:For each $w,a$, sort $B$ valid causal bound and get
$b_{(1)}(w,a),b_{(2)}(w,a),\cdots,b_{(B)}(w,a)$

13:$l(w,a)=b_{(1)}(w,a)$ and $h(w,a)=b_{(B)}(w,a)$ for
$(w,a)\in\mathcal{W}\times\mathcal{A}$

Contextual bandit. We will begin by discussing discrete contexts and then move
on to more general function approximation problems. The objective is to
minimize the regret as shown in (2). Suppose that the true causal effect
$\mathbb{E}[Y|do(a),w]$ falls within the interval $[l(w,a),h(w,a)]$. We define
the set $\mathcal{A}^{*}(x)$ as follows:

$\mathcal{A}^{*}(x)=\mathcal{A}-\\{a\in\mathcal{A}|h(x,a)\leq\max_{i\in\mathcal{A}}l(x,i)\\}.$

This set eliminates suboptimal context-action pairs $(w,a)$ through causal
bounds. Recall that the context-dependent optimal expected reward is denoted
$\mu_{w}^{*}=\max_{a\in\mathcal{A}}\mathbb{E}[Y|do(a),w]$.

Algorithm 4 Transfer learning in contextual bandit

1:time horizon $T$, causal bound $l(w,a)$ and $h(w,a)$

2:Denote $\hat{\mu}_{w,a}(t)$ as the empirical mean of the arm $a$ when
context $w$ occurs

3:Denote $n_{w,a}(t)$ as the number of pulling the arm $a$ when context $w$
occurs

4:Initialize $\mu_{w,a}(1)$ and $n_{w,a}(1)$ to zero with size
$|\mathcal{A}||\mathcal{W}|$

5:for round $t=1,2,\cdots,T$ do

6: Observe the context $w_{t}$

7: Compute the upper confidence bound
$U_{w_{t},a}(t)=\min\\{1,\hat{\mu}_{w_{t},a}(t)+\sqrt{\frac{\log
t}{n_{w_{t},a}(t)}}\\}$

8: Compute the best arm candidate set $\mathcal{A}^{*}(w_{t})$

9: Truncate $U_{w_{t},a}(t)$ to
$\hat{U}_{w_{t},a}(t)=\min\\{U_{w_{t},a}(t),h(w_{t},a)\\}$ for
$a\in\mathcal{A}^{*}(w_{t})$

10: Choose the action
$a_{t}=\mathop{\arg\max}_{a\in\mathcal{A}^{*}(w_{t})}\hat{U}_{w_{t},a}(t)$

11: Observe a reward $y_{t}$

12: Update the empirical mean $\hat{\mu}_{w_{t},a}(t)$ and the number of
pulling $n_{w_{t},a}(t)$

###### Theorem 3.3

Consider a contextual bandit problem with $|\mathcal{A}|<\infty$ and
$|\mathcal{W}|<\infty$. For each arm $a\in\mathcal{A}$ and expected
conditional reward $\mu_{w,a}$ bounded by $[l(w,a),h(w,a)]$. For any given
context $w\in\mathcal{W}$, suppose $w$ occurs for $T_{w}$ times. Then in the
Algorithm 2, the conditional number of draws $\mathbb{E}[N_{a}(T_{w})]$ for
any sub-optimal arm is upper bounded as:

$\mathbb{E}[N_{a}(T_{w})]\leq\left\\{\begin{aligned}
&0,h(w,a)<\max_{i\in\mathcal{A}}l(w,i)\\\
&\frac{|\mathcal{A}|\pi^{2}}{6},\max_{i\in\mathcal{A}}l(w,i)\leq
h(w,a)<\mu^{*}_{w}\\\ &\frac{8\log
T_{w}}{\Delta_{w,a}^{2}}+|\mathcal{A}|,h(w,a)\geq\mu^{*}_{w}\end{aligned}\right.$

In this scenario, the classical agent minimizes regrets for $|\mathcal{W}|$
independent bandit instances. The above theorem (Theorem 3.3) shows how causal
bounds improve the performance of classical bandit algorithms by controlling
the number of times each arm is pulled. Note that Theorem 3.2 is a special
case when $|W|=1$.

Compared with [5], authors provide gap-dependent regret bounds for tabular
reinforcement learning which removes state-action pairs that are not reached
by an optimal policy, i.e.,

$\mathcal{O}(\sum_{w\in\mathcal{W}}\sum_{a\in\widetilde{\mathcal{A}^{*}}(w)}\frac{\log
T}{\Delta_{w,a}}).$

This result shows similarity in our transfer learning setting as we can model
each context as a state and apply the generic RL methods. However, our method
still outperforms generic RL algorithms as the contexts can not be affected by
the actions. Hence, the goal of RL algorithms for optimal state-action
(context-action) pair is not realizable, so the define the regret (2) with
respect to a context-dependent optimal action.

###### Theorem 3.4

Consider a contextual bandit problem with $|\mathcal{A}|<\infty$ and
$|\mathcal{W}|<\infty$. Denote

$\widetilde{\mathcal{A}^{*}}(x)=\mathcal{A}-\\{a\in\mathcal{A}|h(x,a)<\mu_{w}^{*}\\}.$

Then the regret of Algorithm 4 satisfies

$\limsup_{T\to\infty}\frac{\mathbb{E}[Reg(T)]}{\sqrt{T\log
T}}\leq\sum_{w\in\mathcal{W}}\sqrt{8(|\widetilde{\mathcal{A}^{*}}(w)|-1)\mathbb{P}(W=w)}.$

The result does not scale with $\sqrt{|\mathcal{A}^{*}(w)|}$ but with
$\sqrt{|\widetilde{\mathcal{A}^{*}}(w)|}$. Although our Algorithm 4 does not
explicitly remove suboptimal arms in
$\widetilde{\mathcal{A}^{*}}(w)-\mathcal{A}^{*}(w)$, the property of UCB can
still control the number of such suboptimal arms due to truncation by causal
upper bounds.

Using Cauchy-Schwarz inequality, we have

$\sum_{w\in\mathcal{W}}\sqrt{8(|\widetilde{\mathcal{A}^{*}}(w)|-1)\mathbb{P}(W=w)}\leq\sqrt{8\sum_{w\in\mathcal{W}}(|\widetilde{\mathcal{A}^{*}}(w)|-1)}.$

This inequality shows clearly that any elimination of suboptimal arms will
improve transfer learning algorithms. It also implies that our regret result
outperform that of [5] in terms of minimax versions, as the minimax regret in
[5] scales with the right hand side.

Denote the contextual bandit instances with prior knowledge $l(w,a)$ and
$h(w,a)$ as

$\mathfrak{M}=\\{\text{contextual bandit instances with
}l(w,a)\leq\mu_{w,a}\leq h(w,a),\forall a\in\mathcal{A},\forall
w\in\mathcal{W}\\}.$

###### Theorem 3.5

Suppose $|\mathcal{A}|<\infty$ and $|\mathcal{W}|<\infty$. Then for any
algorithm $\mathsf{A}$, there exists an absolute constant $c>0$ such that

$\sup_{\mathfrak{M}}\limsup_{T\to\infty}\frac{Reg(T)}{\sqrt{T}}\geq\frac{1}{27}\sum_{w\in\mathcal{W}}\sqrt{(|\widetilde{\mathcal{A}^{*}}(w)|-1)\mathbb{P}(W=w)}.$

The lower bound result indicates that our Algorithm 3 is near-optimal up to
logarithmic terms in $T$.

Function approximation. Next, we consider continuous and general context
distributions. Since contexts are infinite, it is impossible to learn an
optimal policy, except when the reward has specific function structures, such
as linear. Therefore, we consider the following function approximation setting
under the realizability assumption. Once again, we assume that the true causal
effect falls within $[l(w,a),h(w,a)]$.

We eliminates the functions that cannot be the true reward function using
causal bound:

$\mathcal{F}^{*}=\\{f\in\mathcal{F}|l(w,a)\leq f(w,a)\leq h(w,a)\\}$

and modify the best arm candidate set as following

$\mathcal{A}^{*}(x)=\\{a\in\mathcal{A}|a=\mathop{\arg\max}_{i\in\mathcal{A}}f(x,i)\text{
for some $f$ in $\mathcal{F}^{*}$}\\}.$

Our algorithm (Algorithm 5) is based on the inverse gap weighting technique
(IGW) [9, 1, 10, 34]. In previous literature concerning IGW, this strategy is
employed using a fixed action set size $|\mathcal{A}|$, and the learning rate
$\gamma$ is typically chosen to follow fixed non-adaptive schedule [9, 34].
However, our algorithm differs from these existing approaches in three
aspects. Firstly, we only apply the IGW scheme to functions and actions that
are not eliminated by causal bounds. Secondly, we select the learning rate
$\gamma_{t}$ to be context-dependent, capturing the influence of causal bounds
on the arm set. This adaptive approach enhances the efficiency of our
algorithm in the online learning process, resulting in improved performance in
the transfer learning task. Thirdly, in comparison with [10], our regret order
in $T$ is $\mathcal{O}(\sqrt{T\log(\delta^{-1}\log T)})$ instead of
$\mathcal{O}(\sqrt{T\log(\delta^{-1}T^{2})}\log T)$. By eliminating suboptimal
functions using certain causal bounds rather than relying on data-driven upper
confidence bounds on the policy space, we are able to save additional $\log T$
terms.

Algorithm 5 Transfer learning in function approximation

1:time horizon $T$, confidence parameter $\delta$, tuning parameters $\eta$,
causal bound $l(w,a)$ and $h(w,a)$

2:Eliminate function space $\mathcal{F}$ and obtain $\mathcal{F}^{*}$ via
causal bound

3:Set epoch schedule $\\{\tau_{m}=2^{m},\forall m\in\mathbb{N}\\}$

4:for epoch $m=1,2,\cdots,\lceil\log_{2}T\rceil$ do

5: Compute the function
$\hat{f}_{m}=\mathop{\arg\min}_{f\in\mathcal{F}^{*}}\sum_{t=1}^{\tau_{m-1}}(f(w_{t},a_{t})-y_{t})^{2}$
via the Least Square Oracle

6: for round $t=\tau_{m-1}+1,\cdots,\tau_{m}$ do

7: Observe the context $w_{t}$

8: Compute the best action candidate set $\mathcal{A}^{*}(w_{t})$

9: Compute
$\gamma_{t}=\sqrt{\frac{\eta|\mathcal{A}^{*}(w_{t})|\tau_{m-1}}{\log(2\delta^{-1}|\mathcal{F}^{*}|\log
T)}}$ (for the first epoch, $\gamma_{1}=1$)

10: Compute $\hat{f}_{m}(w_{t},a)$ for each action
$a\in\mathcal{A}^{*}(w_{t})$ and the following probabilities
$p_{t}(a)=\left\\{\begin{array}[]{lcl}\frac{1}{|\mathcal{A}^{*}(w_{t})|+\gamma_{t}(\hat{f}_{m}(w_{t},\hat{a}_{t})-\hat{f}_{m}(w_{t},a))},\text{
for all }a\in\mathcal{A}^{*}(w_{t})-\\{\hat{a}_{t}\\}\\\ 0,\text{ for all
}a\in\mathcal{A}-\mathcal{A}^{*}(w_{t}),\\\
1-\sum_{a\neq\hat{a}_{t}}p_{t}(a),\text{ for }a=\hat{a}_{t},\\\
\end{array}\right.$ where
$\hat{a}_{t}=\max_{a\in\mathcal{A}}\hat{f}_{m}(w_{t},a)$.

11: Sample $a_{t}\sim p_{t}(\cdot)$ and take the action $a_{t}$

12: Observe a reward $y_{t}$

In Algorithm 5, one needs to compute $\mathcal{F}^{*}$ and
$\mathcal{A}^{*}(w)$. A naive way costs $\mathcal{O}(|\mathcal{F}|)$ time
complexity, which becomes inefficient for large $|\mathcal{F}|$ and infeasible
for infinite $|\mathcal{F}|$. Actually, we can implicitly compute
$\mathcal{F}^{*}$ by clipping, i.e., using

$\min\\{\max\\{\hat{f}_{m}(w,a),l(w,a)\\},h(w,a)\\}$

as the estimator at the epoch $m$. As $\hat{f}_{m}$ gets closer to the true
reward function $f^{*}$, which is within the causal bounds, the causal bounds
gradually lose their constraint effect. For computing $\mathcal{A}^{*}(w)$, we
refer readers to the section 4 of [10], where a systematic method for
computing $\mathcal{A}^{*}(w)$ within a given accuracy is provided.

Another option to implement Algorithm 5 is to compute
$\mathbb{E}_{W}[|\mathcal{A}^{*}(W)|]$ using expert knowledge $F(a,y,w)$. We
can set
$\gamma_{t}=\sqrt{\frac{\eta\mathbb{E}_{W}[|\mathcal{A}^{*}(W)|]\tau_{m-1}}{\log(2\delta^{-1}|\mathcal{F}^{*}|\log
T)}}$, so that $\gamma_{t}$ remains constant within an epoch. Our proof still
holds for this option, and the regret order is the same as in Theorem 3.6.
Intuitively, $|\mathcal{A}(w_{t})|$ is a sample from an induced distribution
with a mean of $\mathbb{E}_{W}[|\mathcal{A}^{*}(W)|]$, so on average, the
regrets of both options are of the same order.

###### Theorem 3.6

Consider a contextual bandit problem with $|\mathcal{A}|<\infty$ and
$|\mathcal{F}|<\infty$. Suppose that the realizability 2.1 holds. Then with
probability at least $1-\delta$, the expected regret $\mathbb{E}[Reg(T)]$ of
Algorithm 5 is upper bounded by

$\mathcal{O}\left(\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]T\log(\delta^{-1}|\mathcal{F}^{*}|\log
T)}\right).$

As pointed out by [10], the gap-dependent regret of general contextual bandits
is not possible, so we only consider minimax regrets. Previous works such as
[41] and [25] have also explored transfer learning in general contextual
bandits, but the method in [41] relies on instrumental variables, and their
regrets scale with $\sqrt{|\Pi|}$ instead of the more desirable
$\sqrt{\log|\Pi|}$. However, finding instrumental variables is still an open
problem in academia. Additionally, the authors of [41] treat each basis policy
as an independent arm in bandit problems, which is often invalid as similar
policies can provide information to each other. For example, exploring the
optimal policy can also provide information about the second optimal policy,
since these two policies typically yield similar actions and only differ in a
small amount of contexts. This insight helps explain why their regret depends
on $\sqrt{|\Pi|}$ (as $|\Pi|=|\mathcal{F}|$) rather than more desirable
$\sqrt{\log|\Pi|}$.

We also prove that our upper bound in Theorem 3.6 matches the lower bound in
transfer learning. Denote the contextual bandit instances with prior knowledge
$l(w,a)$ and $h(w,a)$ as

$\mathfrak{M}=\\{\text{contextual bandit instances with }l(w,a)\leq
f^{*}(w,a)\leq h(w,a),\forall(a,w)\in\mathcal{A}\times\mathcal{W}\\}.$

###### Theorem 3.7

Consider a contextual bandit problem with $|\mathcal{A}|<\infty$ and
$|\mathcal{F}|<\infty$. Assume that the agent has access to the function space
$\mathcal{F}$ and the realizability assumption holds. Then for any algorithm
$\mathsf{A}$, we have

$\sup_{\mathfrak{M}}\limsup_{T\to\infty}\frac{Reg(T)}{\sqrt{T}}\geq\sqrt{\mathbb{E}_{W}[|{\mathcal{A}^{*}}(W)|]\log|\mathcal{F}^{*}|}.$

Infinite function classes. It is worth noting that Algorithm 5 and Theorem 3.6
can be easily extended to handle infinite $\mathcal{F}$ using standard
learning-theoretic tools such as metric entropy. Suppose $\mathcal{F}$ is
equipped with a maximum norm $\|\cdot\|$. We can consider an
$\epsilon$-covering $\mathcal{F}^{*}_{\epsilon}$ of $\mathcal{F}^{*}$ under
maximum norm. Since $|\mathcal{F}^{*}_{\epsilon}|$ is finite, we can directly
replace $\mathcal{F}^{*}$ with $\mathcal{F}^{*}_{\epsilon}$ and do not change
any algorithmic procedure. Thanks to the property of $\epsilon$-covering,
there exists a function $f_{\epsilon}^{*}\in\mathcal{F}^{*}_{\epsilon}$ such
that $\|f_{\epsilon}^{*}-f^{*}\|\leq\epsilon.$ Hence, the regret can be
bounded by

$Reg(T)\leq
8\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]T\log(2\delta^{-1}|\mathcal{F}^{*}_{\epsilon}|\log
T)}+\epsilon T.$

By replacing the dependence on $\log|\mathcal{F}^{*}|$ in the algorithm’s
parameters with $\log|\mathcal{F}^{*}_{\epsilon}|$ and setting
$\epsilon=\frac{1}{T}$, we obtain a similar result as Theorem 3.6 up to an
additive constant of $1$.

######  Definition 3.1 ([7])

Let $(\mathcal{F},\|\cdot\|)$ be a normed space. The set
$\\{f_{1},\cdots,f_{N}\\}$ is an $\epsilon$-covering of $\mathcal{F}$ if
$\forall f\in\mathcal{F}$, there exists $i\in[N]$ such that
$\|f-f_{i}\|\leq\epsilon$. The covering number
$N(\mathcal{F},\|\cdot\|,\epsilon)$ is defined as the minimum cardinality $N$
of the covering set over all $\epsilon$-coverings of $\mathcal{F}$.

It clear that $Reg(T)$ scales with $\sqrt{\log
N(\mathcal{F}^{*},\|\cdot\|,\epsilon)}$. Note that
$N(\mathcal{F}^{*},\|\cdot\|,\epsilon)\leq N(\mathcal{F},\|\cdot\|,\epsilon)$
as $\mathcal{F}^{*}\subset\mathcal{F}$. The covering number shows clearly how
extra causal bounds help improve the algorithm performance by shrinking the
search space. Let $m=\inf_{w,a}l(w,a)$ and $M=\sup_{w,a}h(w,a)$. These bounds
chip away the surface of the unit sphere and scoop out the concentric sphere
of radius $m$. Therefore, the transfer learning algorithm only needs to search
within a spherical shell with a thickness of at most $M-m$.

##  4 Numerical Experiments

In this section, we conduct experiments to validate our findings.

Causal bounds. To evaluate the effectiveness of our proposed Algorithm 1, we
compare it with the method proposed by Li and Pearl [19] when all variables
are binary. Specifically, we randomly generate distributions
$\mathbb{P}(a,y,w)$, as shown in Table 6, and set $\mathbb{P}(U=1)=0.1$.

$(A,Y,W)$ | $(0,0,0)$ | $(0,0,1)$ | $(0,1,0)$ | $(0,1,1)$ | $(1,0,0)$ | $(1,0,1)$ | $(1,1,0)$ | $(1,1,1)$
---|---|---|---|---|---|---|---|---
$\mathbb{P}(a,y,w)$ | 0.2328 | 0.1784 | 0.1351 | 0.1467 | 0.0304 | 0.1183 | 0.0149 | 0.1433

We implement Algorithm 1 with a batch size of $20000$, and set $\epsilon=0$ as
Li and Pearl [19] assumes the given distributions are accurate. The results
are presented in Table 6. Our method can tighten the bounds obtained by Li and
Pearl [19], as evidenced by the narrower ranges of the estimated causal
effects. Moreover, we observe that solving non-linear optimization is quite
unstable and often leads to local optima. To obtain global solutions, we
repeat solving non-linear optimization with randomly initialized starting
points.

causal effect | non-linear optimization [19] | our Algorithm 1
---|---|---
$\mathbb{E}[Y|do(A=0)]$ | $[0.283,0.505]$ | $[0.371,0.466]$
$\mathbb{E}[Y|do(A=1)]$ | $[0.240,0.807]$ | $[0.300,0.705]$
Table 6: Comparison with causal bounds in partially observable problems.

Transfer learning in MAB. We compare our proposed transfer learning algorithm
(Algorithm 2) with standard multi-armed bandit (MAB) algorithms that do not
have access to causal bounds. We also include the counterparts that
incorporate a naive transfer procedure (without distinguishing the do-
distribution), which we refer to as UCB-.

We present simulation results for $5$-armed Bernoulli bandits with probability
$0.1,0.2,0.3,0.6,0.8$. Simulations are partitioned into rounds of $T=10^{5}$
trials averaged over $50$ repetitions. For each task, we collect $1000$
samples generated by a source agent and compute the empirical joint
distribution. The estimated causal bounds without the knowledge of $F(u)$
(CUCB in Figure 2 [40]) are $h(a)=0.9,0.35,0.92,0.96,0.92$, and
$l(a)=0,0.08,0.1,0.3,0.4$. The estimated causal bounds with the knowledge of
$F(u)$ are $h(a)=0.2,0.25,0.77,0.7,0.9$, and $l(a)=0.01,0.08,0.19,0.38,0.71$.

The regret curves are presented in Figure 2. We observe that the regret of
UCB- sharply grows linearly and becomes sublinear after a certain turning
point. This negative transfer result indicates that the agent spends many
trials to overcome the influence of wrong knowledge. In contrast, our proposed
algorithm achieves orders of magnitude faster convergence rates, as the causal
bounds effectively eliminate suboptimal arms. These results corroborate with
our findings and demonstrate that prior experiences can be transferred to
improve the performance of the target agent, even when identifiability does
not hold.

Moreover, we find that a tighter causal bound can further improve the
performance of classical algorithms. Even when the number of observations is
not statistically significant, our approach can still rival standard methods,
i.e., no negative transfer occurs. Overall, our experiments provide strong
evidence that our proposed transfer learning algorithm can significantly
improve the performance of contextual bandit agents.

$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{5}$$0$$100$$200$$300$$400$time
$t$regretUCB-UCBCUCBours Figure 2: Comparison with classical and causally
enhanced algorithms. The top and bottom dashed curves represent the curves
obtained by adding and subtracting one standard deviation to the regret curve
of the corresponding color, respectively.

Transfer learning in contextual bandits. We randomly generate a function space
$\mathcal{F}=\\{(w-w_{0})^{\top}(a-a_{0})\\}$ with a size of $50$ by sampling
parameters $w_{0},a_{0}$ in $\mathbb{R}^{d}$ from $\mathcal{N}(0,0.1)$, where
$d=10$. We then randomly choose a function as the true reward function $f^{*}$
from the first 5 functions, and generate the reward as

$Y=f^{*}(W,A)+\mathcal{N}(0,0.1),$

where the context $W$ is drawn i.d.d. from standard normal distributions and
$A$ is the selected action. The whole action set $\mathcal{A}$ is randomly
initialized from $[-1,1]^{d}$ with a size of $10$. We repeat each instance
$50$ times to obtain a smooth regret curve.

We compare the performance of our algorithm with FALCON [34], a well-known
version of IGW. From the numerical results, we observe that our algorithm
outperforms FALCON significantly, even without eliminating infeasible
functions. The average size of $\mathcal{A}(w)$ is $3.254$ in our randomly
selected instances, indicating that eliminating action size can significantly
improve performance. Additionally, our algorithm is particularly effective for
homogeneous functions, as these functions usually attain the maximum at the
same points. In this case, adaptively eliminating suboptimal actions is a very
effective way to reduce regrets.

$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$\cdot 10^{5}$$0$$0.5$$1$$1.5$$\cdot
10^{4}$time $t$regretFALCON [34]ours Figure 3: Comparison with classical and
causally enhanced algorithms in function approximation settings. The top and
bottom dashed curves represent the curves obtained by adding and subtracting
one standard deviation to the regret curve of the corresponding color,
respectively.

## References

  * Agarwal et al. [2012] A. Agarwal, M. Dudík, S. Kale, J. Langford, and R. Schapire.  Contextual bandit learning with predictable rewards.  In _Artificial Intelligence and Statistics_ , pages 19–26. PMLR, 2012\.
  * Bareinboim et al. [2015] E. Bareinboim, A. Forney, and J. Pearl.  Bandits with unobserved confounders: A causal approach.  _Advances in Neural Information Processing Systems_ , 28, 2015.
  * Cai et al. [2022] C. Cai, T. T. Cai, and H. Li.  Transfer learning for contextual multi-armed bandits.  _arXiv preprint arXiv:2211.12612_ , 2022.
  * Chu et al. [2011] W. Chu, L. Li, L. Reyzin, and R. Schapire.  Contextual bandits with linear payoff functions.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 208–214. JMLR Workshop and Conference Proceedings, 2011.
  * Dann et al. [2021] C. Dann, T. V. Marinov, M. Mohri, and J. Zimmert.  Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning.  _Advances in Neural Information Processing Systems_ , 34:1–12, 2021.
  * Duarte et al. [2023] G. Duarte, N. Finkelstein, D. Knox, J. Mummolo, and I. Shpitser.  An automated approach to causal inference in discrete settings.  _Journal of the American Statistical Association_ , (just-accepted):1–25, 2023.
  * Fan [1953] K. Fan.  Minimax theorems.  _Proceedings of the National Academy of Sciences of the United States of America_ , 39(1):42, 1953.
  * Foster and Rakhlin [2020] D. Foster and A. Rakhlin.  Beyond ucb: Optimal and efficient contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pages 3199–3210. PMLR, 2020.
  * Foster et al. [2018] D. Foster, A. Agarwal, M. Dudík, H. Luo, and R. Schapire.  Practical contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pages 1539–1548. PMLR, 2018.
  * Foster et al. [2020] D. J. Foster, A. Rakhlin, D. Simchi-Levi, and Y. Xu.  Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective.  _arXiv preprint arXiv:2010.03104_ , 2020.
  * Gong and Zhang [2022] X. Gong and J. Zhang.  Dual instrumental method for confounded kernelized bandits.  _arXiv preprint arXiv:2209.03224_ , 2022.
  * Guo et al. [2022] H. Guo, Q. Cai, Y. Zhang, Z. Yang, and Z. Wang.  Provably efficient offline reinforcement learning for partially observable Markov decision processes.  In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 8016–8038. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/guo22a.html.
  * Jin et al. [2019] C. Jin, Z. Yang, Z. Wang, and M. I. Jordan.  Provably efficient reinforcement learning with linear function approximation, 2019.
  * Kallus [2018] N. Kallus.  Instrument-armed bandits.  In _Algorithmic Learning Theory_ , pages 529–546. PMLR, 2018.
  * Lattimore et al. [2016] F. Lattimore, T. Lattimore, and M. D. Reid.  Causal bandits: Learning good interventions via causal inference.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Lattimore and Szepesvári [2020] T. Lattimore and C. Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Lazaric et al. [2013] A. Lazaric, E. Brunskill, et al.  Sequential transfer in multi-armed bandit with finite set of models.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Li and Pearl [2022a] A. Li and J. Pearl.  Probabilities of causation with nonbinary treatment and effect.  _arXiv preprint arXiv:2208.09568_ , 2022a.
  * Li and Pearl [2022b] A. Li and J. Pearl.  Bounds on causal effects and application to high dimensional data.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 5773–5780, 2022b.
  * Li and Pearl [2022c] A. Li and J. Pearl.  Unit selection with nonbinary treatment and effect.  _arXiv preprint arXiv:2208.09569_ , 2022c.
  * Li et al. [2022] A. Li, S. Jiang, Y. Sun, and J. Pearl.  Learning probabilities of causation from finite population data.  _arXiv preprint arXiv:2210.08453_ , 2022.
  * Li et al. [2023] A. Li, S. Mueller, and J. Pearl.  Epsilon-identifiability of causal quantities.  _arXiv preprint arXiv:2301.12022_ , 2023.
  * Li et al. [2010] L. Li, W. Chu, J. Langford, and R. E. Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pages 661–670, 2010.
  * Liu et al. [2018] B. Liu, Y. Wei, Y. Zhang, Z. Yan, and Q. Yang.  Transferable contextual bandit for cross-domain recommendation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Liu et al. [2021] C. Liu, Y. Zhang, Y. Shen, and M. M. Zavlanos.  Learning without knowing: Unobserved context in continuous transfer reinforcement learning.  In _Learning for Dynamics and Control_ , pages 791–802. PMLR, 2021\.
  * Lu et al. [2023] M. Lu, Y. Min, Z. Wang, and Z. Yang.  Pessimism in the face of confounders: Provably efficient offline reinforcement learning in partially observable markov decision processes, 2023\.
  * Mosteller [2006] F. Mosteller.  _On some useful “inefficient” statistics_.  Springer, 2006.
  * [28] H. Park and M. K. S. Faradonbeh.  A regret bound for greedy partially observed stochastic contextual bandits.  In _Decision Awareness in Reinforcement Learning Workshop at ICML 2022_.
  * Park and Faradonbeh [2021] H. Park and M. K. S. Faradonbeh.  Analysis of thompson sampling for partially observable contextual multi-armed bandits.  _IEEE Control Systems Letters_ , 6:2150–2155, 2021.
  * Pearl [2009] J. Pearl.  Causal inference in statistics: An overview.  _Statistics surveys_ , 3:96–146, 2009.
  * Powell [2018] S. Powell.  The book of why.  _Journal of MultiDisciplinary Evaluation_ , 14(31):47–54, 2018.
  * Shi et al. [2022] C. Shi, M. Uehara, J. Huang, and N. Jiang.  A minimax learning approach to off-policy evaluation in confounded partially observable markov decision processes.  In _International Conference on Machine Learning_ , pages 20057–20094. PMLR, 2022.
  * Shridharan and Iyengar [2022] M. Shridharan and G. Iyengar.  Scalable computation of causal bounds.  In _International Conference on Machine Learning_ , pages 20125–20140. PMLR, 2022.
  * Simchi-Levi and Xu [2021] D. Simchi-Levi and Y. Xu.  Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.  _Mathematics of Operations Research_ , 2021.
  * Tennenholtz et al. [2021] G. Tennenholtz, U. Shalit, S. Mannor, and Y. Efroni.  Bandits with partially observable confounded data.  In _Uncertainty in Artificial Intelligence_ , pages 430–439. PMLR, 2021.
  * Tian and Pearl [2002] J. Tian and J. Pearl.  A general identification condition for causal effects.  In _Aaai/iaai_ , pages 567–573, 2002.
  * Uehara et al. [2022] M. Uehara, A. Sekhari, J. D. Lee, N. Kallus, and W. Sun.  Provably efficient reinforcement learning in partially observable dynamical systems.  _ArXiv_ , abs/2206.12020, 2022.  URL https://api.semanticscholar.org/CorpusID:250048691.
  * Wang et al. [2021] L. Wang, Z. Yang, and Z. Wang.  Provably efficient causal reinforcement learning with confounded observational data.  _Advances in Neural Information Processing Systems_ , 34:21164–21175, 2021.
  * Xu et al. [2021] L. Xu, H. Kanagawa, and A. Gretton.  Deep proxy causal learning and its application to confounded bandit policy evaluation.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Zhang and Bareinboim [2017] J. Zhang and E. Bareinboim.  Transfer learning in multi-armed bandit: a causal approach.  In _Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems_ , pages 1778–1780, 2017.
  * Zhang and Bareinboim [2021] J. Zhang and E. Bareinboim.  Bounding causal effects on continuous outcome.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 12207–12215, 2021.
  * Zhang et al. [2022] J. Zhang, J. Tian, and E. Bareinboim.  Partial counterfactual identification from observational and experimental data.  In _International Conference on Machine Learning_ , pages 26548–26558. PMLR, 2022.
  * Zhuang et al. [2021] F. Zhuang, Z. Qi, K. Duan, D. Xi, Y. Zhu, H. Zhu, H. Xiong, and Q. He.  A comprehensive survey on transfer learning.  _Proceedings of the IEEE_ , 109(1):43–76, 2021\.  doi: 10.1109/JPROC.2020.3004555.

##  Appendix A Deferred Proofs

###  A.1 Proof of mentioned facts

###### Fact A.1.1

Given a series of known observational distributions $F^{1},\cdots,F^{n}$,
consider an optimization problem for causal effects:

$\displaystyle\inf/\sup CE(\mathcal{M})$ $\displaystyle
F^{i}_{\mathcal{M}}=F^{i},i=1,\cdots,n,$

where $CE(\mathcal{M})$ is the desired casual effect and $F_{\mathcal{M}}^{i}$
is a distribution in the model $\mathcal{M}$. Here, the inf/sup is taken with
respect to all compatible causal models $\mathcal{M}$. Then, a sufficient and
necessary condition to identify $CE(\mathcal{M})$ is $LB=UB$, where $LB$ and
$UB$ are the lower and upper bound solutions to the optimization problem.

Proof.  If $LB=HB$, then for any compatible model $\mathcal{M}_{1}$ and
$\mathcal{M}_{2}$, we have

$LB=CE(\mathcal{M}_{1})=CE(\mathcal{M}_{2})=UB.$

According the definition of causal identification, the required causal effect
$CE(\mathcal{M})$ can be fully identified.

On the contrary, suppose $CE(\mathcal{M})$ is causal identifiable. Then for
any compatible model pair $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, we have
$CE(\mathcal{M}_{1})=CE(\mathcal{M}_{2})$. Traveling over all compatible
models immediately yields

$LB=CE(\mathcal{M}_{1})=CE(\mathcal{M}_{2})=UB.$

$\square$

###### Fact A.1.2

During discretization, equality constraints in Theorem 3.1 are automatically
satisfied in the sense of integration.

Proof.  The first constraint has been checked.

For the second equality, we integrate over $\mathcal{U}_{l}$ and have

$\displaystyle\int_{u\in\mathcal{U}_{l}}dF(u)du$ $\displaystyle=$
$\displaystyle\int_{a\in\mathcal{A},y\in\mathcal{Y},w\in\mathcal{W},u\in\mathcal{U}_{l}}dF(a,y,w,u)du$
$\displaystyle=$
$\displaystyle\sum_{ijk}\int_{a\in\mathcal{A}_{i},\in\mathcal{Y}_{j},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}dF(a,y,w,u)du$
$\displaystyle=$ $\displaystyle\sum_{ijk}x_{ijkl}.$

Hence, the second equality constraint holds in the sense of integration.

For the third and the fourth equality constrains, we can do integration over
corresponding blocks and check the equality in the same way.

The conditional distribution in the fifth equality can be approximated by
$x_{ijkl}$. See details in the proof of approximating objective (5).

$\square$

###### Fact A.1.3

The object in Theorem 3.1 after discretization is approximately equal to (5).

Proof.  We use the average values to approximate distributions at certain
points. First, we only need to consider the value

$\int_{y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}y\frac{dF(a,y,w,u)dF(w,u)}{dF(a,w,u)},$

as summing over $j,k,l$ can yield the object.

Suppose the given $a\in\mathcal{A}_{i}$ and let $vol(\cdot)$ denote the volume
of the given block. For the values of distributions in
$\mathcal{A}_{i}\times\mathcal{Y}_{j}\times\mathcal{W}_{k}\times\mathcal{U}_{l}$,
we have

$\displaystyle dF(a,y,w,u)\approx$
$\displaystyle\frac{dadydwdu}{vol(\mathcal{A}_{i})vol(\mathcal{Y}_{j})vol(\mathcal{W}_{k})vol(\mathcal{U}_{l})}\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}dF(a,y,w,u)$
$\displaystyle=$
$\displaystyle\frac{x_{ijkl}dadydwdu}{vol(\mathcal{A}_{i})vol(\mathcal{Y}_{j})vol(\mathcal{W}_{k})vol(\mathcal{U}_{l})},$
$\displaystyle dF(a,w,u)\approx$
$\displaystyle\frac{dadwdu}{vol(\mathcal{A}_{i})vol(\mathcal{W}_{k})vol(\mathcal{U}_{l})}\int_{a\in\mathcal{A}_{i},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}dF(a,w,u)$
$\displaystyle=$
$\displaystyle\frac{dadwdu}{vol(\mathcal{A}_{i})vol(\mathcal{W}_{k})vol(\mathcal{U}_{l})}\int_{a\in\mathcal{A}_{i},y\in\mathcal{Y},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}dF(a,y,w,u)$
$\displaystyle=$
$\displaystyle\frac{\sum_{j^{\prime}}x_{ij^{\prime}kl}dadwdu}{vol(\mathcal{A}_{i})vol(\mathcal{W}_{k})vol(\mathcal{U}_{l})},$
$\displaystyle dF(w,u)\approx$
$\displaystyle\frac{dwdu}{vol(\mathcal{W}_{k})vol(\mathcal{U}_{l})}\int_{w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}dF(w,u)$
$\displaystyle=$
$\displaystyle\frac{dwdu}{vol(\mathcal{W}_{k})vol(\mathcal{U}_{l})}\int_{a\in\mathcal{A},y\in\mathcal{Y},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}dF(a,y,w,u)$
$\displaystyle=$
$\displaystyle\frac{\sum_{i^{\prime},j^{\prime}}x_{i^{\prime}j^{\prime}kl}dwdu}{vol(\mathcal{W}_{k})vol(\mathcal{U}_{l})}.$

Plugging all above equalities yields

$\displaystyle\int_{y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}y\frac{dF(a,y,w,u)dF(w,u)}{dF(a,w,u)}$
$\displaystyle\approx$
$\displaystyle\frac{x_{ijkl}\sum_{i^{\prime},j^{\prime}}x_{i^{\prime}j^{\prime}kl}}{\sum_{j^{\prime}}x_{ij^{\prime}kl}}\int_{y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}$
$\displaystyle=$
$\displaystyle\frac{x_{ijkl}\sum_{i^{\prime},j^{\prime}}x_{i^{\prime}j^{\prime}kl}}{\sum_{j^{\prime}}x_{ij^{\prime}kl}}\int_{y\in\mathcal{Y}_{j},w\in\mathcal{W}_{k},u\in\mathcal{U}_{l}}ydydydu/vol(\mathcal{Y}_{j})vol(\mathcal{W}_{k})vol(\mathcal{U}_{l})$
$\displaystyle\approx$
$\displaystyle\frac{y_{j}x_{ijkl}\sum_{i^{\prime},j^{\prime}}x_{i^{\prime}j^{\prime}kl}}{\sum_{j^{\prime}}x_{ij^{\prime}kl}}.$

If $y_{j}$ is chosen to be
$\frac{\int_{y\in\mathcal{Y}_{j}}ydy}{\int_{y\in\mathcal{Y}_{j}}dy},$ then the
last symbol of approximation can be replaced with the symbol of equal. If
$\mathcal{Y}_{j}$ is an interval, $y_{j}$ can be chosen as the midpoint of
$\mathcal{Y}_{j}$. $\square$

The step of approximating $dF$ is crucial in reducing the approximation error.
For absolutely continuous cumulative distribution functions, the approximation
error will converge to zero as the diameter of each block approaches zero.
Furthermore, if all random variables are discrete, the approximation error can
be exactly zero when using the natural discretization. In this case, the
original objective can be expressed as

$\sum_{y\in\mathcal{Y},w\in\mathcal{W},u\in\mathcal{U}}y\frac{\mathbb{P}(A=a,Y=y,W=w,U=u)\mathbb{P}(W=w,U=u)}{\mathbb{P}(A=a,W=w,U=u)}.$

Our discretization method can be regarded as approximating probability mass
functions.

###### Fact A.1.4

If the estimator $\hat{\theta}_{x}$ for $\theta_{x}\in[0,1]$ has $n_{x}$
i.i.d. samples, then the variance of $\hat{\theta}_{x}$ is at most
$\frac{1}{4n_{x}}$.

Proof.  Since $\theta_{x}^{2}\leq\theta_{x}$, then

$Var(\theta_{x})=\mathbb{E}[\theta_{x}^{2}]-(\mathbb{E}[\theta_{x}])^{2}\leq\mathbb{E}[\theta_{x}]-(\mathbb{E}[\theta_{x}])^{2}\leq\frac{1}{4}.$

Hence, we have

$Var(\hat{\theta}_{x})=\frac{1}{n_{x}}Var({\theta}_{x})\leq\frac{1}{4n_{x}}.$

$\square$

###  A.2 Proof of Theorem 3.1

Proof.  Since $W$ and $U$ satisfies the back-door criterion, we can condition
on $W,U$ to identify the causal effect $\mathbb{E}[Y|do(a_{0})]$ We have

$\displaystyle\mathbb{E}[Y|do(a_{0})]$
$\displaystyle=\int_{w\in\mathcal{W},u\in\mathcal{U}}\mathbb{E}[Y|do(a_{0}),w,u]dF(w,u)$
$\displaystyle=$
$\displaystyle\int_{w\in\mathcal{W},u\in\mathcal{U}}\mathbb{E}[Y|a_{0},w,u]dF(w,u)$
$\displaystyle=$
$\displaystyle\int_{w\in\mathcal{W},u\in\mathcal{U}}\int_{y\in\mathcal{Y}}ydF(y|a_{0},w,u)dF(w,u).$

The equalities come from the normalization properties of distribution
functions. The inequalities come from the estimation error. $\square$

###  A.3 Proof of convergence results of Algorithm 1

We first prove the following lemma to show that our sampling algorithm can
cover all values in the feasible region $\mathcal{D}$. We denote the truncated
distribution to $[l,h]$ from the user-given distribution $F_{s}$ when $x_{i}$
is given in sequential LPs as $F_{s}(x|x_{i},[l,h]).$

###### Lemma A.1

The Algorithm 7 induces a distribution on the given simplex $\mathcal{D}$.

Proof.  We need to prove the sample generated by Algorithm 7 can exactly cover
the region of $\mathcal{D}$. On the one hand, for any output $\mathbf{x}$, the
feasibility of each component of $\mathbf{x}$ indicates that $\mathbf{x}$ must
lie in $\mathcal{D}$. On the another hand, for any
$\hat{\mathbf{x}}\in\mathcal{D}$, we show that this point can be generated by
solving sequential LPs. Since $\hat{\mathbf{x}}\in\mathcal{D}$,
$\hat{\mathbf{x}}$ is a feasible solution to the first LP

$\displaystyle\min/\max x_{1}$ $\displaystyle s.t.$ $\displaystyle
A\mathbf{x}\leq\mathbf{b},\mathbf{x}\geq\mathbf{0}.$

One can check the feasibility of $\hat{\mathbf{x}}$ in the following LPs

$\displaystyle\min/\max x_{i}$ $\displaystyle s.t.$ $\displaystyle
A\mathbf{x}\leq\mathbf{b},\mathbf{x}\geq\mathbf{0}$ $\displaystyle
x_{1}=\hat{x}_{1},\cdots,x_{j}=\hat{x}_{j},j=1,2,\cdots,i-1,$

because $\hat{\mathbf{x}}\in\mathcal{D}$ and the previous $i$ components are
exactly equal to those of $\hat{\mathbf{x}}$.

Suppose that the number of components of $\hat{\mathbf{x}}$ is $d$. Then the
induced distribution is

$F(\hat{\mathbf{x}})=F_{s}(x_{1}|[l_{1},h_{1}])\prod_{i=2}^{d}F_{s}(x_{i}|[l_{i},h_{i}],x_{j},j=1,2,\cdots,i-1).$

$\square$

We now give the proof for Proposition 3.1.

Proof.  The discretization optimization problem (12) has one-to-one
correspondence between $\mathbf{x}$ and each causal model where all random
variables are discrete. From Lemma A.1, we know the one-to-one correspondence
between each model and $\mathbf{x}$. Therefore, $[\hat{l}(a),\hat{h}(a)]$ is
the support of the induced distribution on casual bounds.

As shown in (5), the object can be regarded as a function of $\mathbf{x}$. We
define $\phi=\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a)}]$ which is a continuous
mapping from $\mathcal{D}$ to $[0,1]$. The continuity of $\phi$ is clear for
$\sum{j^{\prime}}x_{ij^{\prime}kl}>0$. When
$\sum_{j^{\prime}}x_{ij^{\prime}kl}=0$, the non-negativity of $x_{ijkl}$
implies $\sum_{i^{\prime},j^{\prime}}x_{i^{\prime}j^{\prime}kl}=0$. In this
case, we can set the value of
$\frac{y_{j}x_{ijkl}\sum_{i^{\prime},j^{\prime}}x_{i^{\prime}j^{\prime}kl}}{\sum_{j^{\prime}}x_{ij^{\prime}kl}}$
to be 0 to maintain continuity.

Given that $\mathcal{D}$ is a compact set, there exists $\mathbf{x}_{l}$ such
that $\phi(\mathbf{x}_{l})=\hat{l}(a)$. The continuity indicates that
$\forall\epsilon>0$, there exists $\delta>0$ such that
$\phi(\mathbf{x})<\hat{l}(a)+\epsilon$ for all
$\mathbf{x}\in\mathcal{B}(x_{h},\delta)$, then

$\mathbb{P}(b(a)<\hat{l}(a)+\epsilon)=\mathbb{P}_{s}\left(\bigcup_{b<\hat{l}(a)+\epsilon}\\{\mathbf{x}\in\mathcal{D}|\phi(\mathbf{x})=b\\}\right)\geq\mathbb{P}_{s}(\mathcal{B}(\mathbf{x}_{h},\delta))>0.$

This implies that

$\mathbb{P}(b_{(1)}(a)<\hat{l}(a)+\epsilon)=1-(1-\mathbb{P}(b(a)<\hat{l}(a)+\epsilon))^{B}\to
1$

as $B\to\infty$. Since $b_{(1)}(a)$ is a feasible solution to the discrete
optimization problem, we have

$\mathbb{P}(\hat{l}(a)\leq
b_{(1)}(a)<\hat{l}(a)+\epsilon)=1-(1-\mathbb{P}(b(a)<\hat{l}(a)+\epsilon))^{B}\to
1$

which implies $b_{(1)}(a)\to\hat{l}(a)$ in probability.

Similarly, we can prove that $\mathbb{P}(b_{(B)}(a)>\hat{h}(a)-\epsilon)<1$
and thus $b_{(B)}(a)\to\hat{h}(a)$ in probability.

$\square$

Algorithm 6 MC for causal bound with an extra optimization procedure

1:cumulative distribution functions $\hat{F}(a,y,w)$ and $\hat{F}(u)$,
discrepancy parameter $\epsilon$, sampling distribution ${F}_{s}$, batch size
$B$, optimization procedure OPT

2:Discrete the variable domain
$\mathcal{A},\mathcal{Y},\mathcal{W},\mathcal{U}$

3:Select a linearly independent variable index set $S$ with size
$n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}n_{\mathcal{U}}-n_{\mathcal{A}}n_{\mathcal{Y}}n_{\mathcal{W}}-n_{\mathcal{U}}+1$
for linear equations (8)

4:Compute each $\hat{\theta}_{ijk}$ and $\hat{\theta}_{l}$ according to (11)

5:Set a counter $cnt$ to $0$

6:while $cnt<B$ do

7: Sample ${\theta}_{x}$ from the uniform distribution supported on
$[\max\\{\hat{\theta}_{x}-\epsilon,0\\},\max\\{\hat{\theta}_{x}+\epsilon,1\\}]$
for all $x=ijk$ or $x=l$

8: Sequentially solve LP (10) to find support $[l_{ijkl},h_{ijkl}]$ for each
$x_{ijkl}$ with $(i,j,k,l)\in S$ and sample a value from $F_{s}$ supported on
$[l_{ijkl},h_{ijkl}]$

9: Solving remaining $x_{ijkl}$ by linear equations (8) for all
$(i,j,k,l)\notin S$

10: Use the obtained feasible sample $\mathbf{x}$ as the initial guess into
OPT(min/max,(5),$\mathcal{D}$,$\mathbf{x}$)

11: Compute the causal effect $b_{cnt}(a)$ by the outputs of OPT for each $a$

12: $cnt=cnt+1$

13:For each $a$, sort $B$ valid causal bound and get
$b_{(1)}(a),b_{(2)}(a),\cdots,b_{(B)}(a)$

14:$l(a)=b_{(1)}(a)$ and $h(a)=b_{(B)}(a)$ for $a\in\mathcal{A}$

Proof.  The one-to-one correspondence between $\mathbf{x}$ and each causal
model has been proved in Lemma A.1. Therefore, $[\hat{l}(a),\hat{h}(a)]$ is
the support of the induced distribution on casual bounds. As shown in the
proof of Proposition 3.1, the defined
$\phi=\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a)}]$ is a continuous mapping from
$\mathcal{D}$ to $[0,1]$.

Given that $\mathcal{D}$ is a compact set, there exists $\mathbf{x}_{l}$ such
that $\phi(\mathbf{x}_{l})=\hat{l}(a)$. The property of OPT implies that there
exists $\delta>0$ such that

$\textbf{OPT}(min/max,\eqref{eq: object-average causal
effect},\mathcal{D},\mathbf{x})=\mathbf{x}_{l},\forall\mathbf{x}\in\mathcal{B}(\mathbf{x}_{l},\delta)\cap\mathcal{D}.$

Hence, we have

$\mathbb{P}(b(a)=\hat{l}(a))\geq\mathbb{P}_{s}(\mathcal{B}(\mathbf{x}_{l},\delta)\cap\mathcal{D})>0.$

Due to Borel-Cantelli lemma we can prove that $b_{(1)}(a)\to\hat{l}(a)$ almost
surely, because each $b_{i}(a)$ is independently sampled by Algorithm 6.
Similarly, we can prove that $b_{(B)}(a)\to\hat{h}(a)$ almost surely.

$\square$

###  A.4 Proof of regrets in Section 3.1

We first prove Theorem 3.2.

Proof.  Case 1: $h(a)<\max_{i\in\mathcal{A}}l(i)$

From the algorithmic construction, we know that such arm $a$ is removed and
thus

$\mathbb{E}[N_{a}(T)]=0.$

Case 2: $\max_{i\in\mathcal{A}}l(i)\leq h(a)<\mu^{*}$.

Let $a^{*}=\mathop{\arg\max}_{a\in\mathcal{A}}\mathbb{E}[Y|do(a)]$ be the
optimal action with respect to $w$. Define the following event

$\mathcal{E}(t)=\left\\{\hat{\mu}_{a}\in[{\mu}_{a}-\frac{\log
t}{n_{a}(t)},{\mu}_{a}+\frac{\log t}{n_{a}(t)}],\forall
a\in\mathcal{A}\right\\}$

Then the Chernoff’s bound yields

$\mathbb{P}(\overline{\mathcal{E}(t)})\leq\sum_{a\in\mathcal{A}}\exp(-2n_{a}(t)\times\frac{\log
t}{n_{a}(t)})\leq\frac{|\mathcal{A}|}{t^{2}}$

For any given $w$, the event $\\{A_{t}=a\\}$ implies
$\hat{U}_{a}(t)>\hat{U}_{a^{*}}(t)$. However,

$\mu^{*}>h(a)\geq\hat{U}_{a}(t)$

and

$\hat{U}_{a^{*}}(t)\geq\mu^{*}$

if $\mathcal{E}(t)$ holds. This leads to contradiction. Therefore,

$\displaystyle\mathbb{E}[N_{a}(T)]$
$\displaystyle=\sum_{t=1}^{T}\mathbb{P}(A_{t}=a)$
$\displaystyle=\sum_{t=1}^{T}\mathbb{P}(A_{t}=a|\mathcal{E}(t))\mathbb{P}(\mathcal{E}(t))+\mathbb{P}(A_{t}=a|\overline{\mathcal{E}(t)})\mathbb{P}(\overline{\mathcal{E}(t)})$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{P}(\overline{\mathcal{E}(t)})$
$\displaystyle\leq\sum_{t=1}^{T}\frac{|\mathcal{A}|}{t^{2}}$
$\displaystyle\leq\frac{|\mathcal{A}|\pi^{2}}{6}.$

Case 3: $h(a)\geq\mu^{*}$

We reuse the notation $\mathcal{E}(t)$ in the case 2. Condition on the event
$\bigcap_{t=1}^{T}\mathcal{E}(t)$, if $n_{a}(t)\geq\frac{8\log
T}{\Delta_{a}^{2}}$, then

$\hat{U}_{a}(t)\leq U_{a}(t)=\mu_{a}+\sqrt{\frac{2\log
t}{n_{a}(t)}}\leq\mu_{a}+\frac{1}{2}\Delta_{a}=\mu^{*}\leq\hat{U}_{a^{*}}(t),$

so Algorithm 4 will not choose the action $a$ at the round $t$. Therefore,

$\mathbb{E}[N_{a}(T)]\leq\mathbb{E}\left[N_{a}(T)\bigg{|}\bigcap_{t=1}^{T}\mathcal{E}(t)\right]+T\mathbb{P}\left(\overline{\bigcap_{t=1}^{T}\mathcal{E}(t)}\right)\leq\frac{8\log
T}{\Delta_{a}^{2}}+T\mathbb{P}\left(\overline{\bigcup_{t=1}^{T}\mathcal{E}(t)}\right).$

We conclude the proof by showing

$T\mathbb{P}\left(\overline{\bigcup_{t=1}\mathcal{E}(t)}\right)\leq
T\sum_{t=1}^{T}\frac{|\mathcal{A}|}{t^{2}}<T\times\frac{|\mathcal{A}|}{T}=|\mathcal{A}|.$

$\square$

Actually, the proof is just a simple modification of that in Theorem 3.3,
because MAB can be regarded as a special case of contextual bandits.

###### Theorem A.1

Consider a MAB bandit problem with $|\mathcal{A}|<\infty$. Denote

$\widetilde{\mathcal{A}^{*}}=\mathcal{A}-\\{a\in\mathcal{A}|h(a)<\mu^{*}\\}.$

Then the regret of Algorithm 2 is upper bounded by

$\mathbb{E}[Reg(T)]\leq\sqrt{8(|\widetilde{\mathcal{A}^{*}}(w)|-1)T\log T}.$

Proof.  Theorem 3.2 shows that

$\displaystyle\mathbb{E}[Reg(T)]$
$\displaystyle=\sum_{a\in\mathcal{A}}\Delta_{a}\mathbb{E}[N_{a}(T)]$
$\displaystyle\leq\sum_{a\in\widetilde{\mathcal{A}^{*}}}\frac{8\log
T}{\Delta_{a}}\mathbf{I}\left\\{\Delta_{a}\geq\Delta\right\\}+T\Delta+\mathcal{O}(|\mathcal{A}|)$
$\displaystyle\leq\frac{8(|\widetilde{\mathcal{A}^{*}}|-1)\log
T}{\Delta}+T\Delta+\mathcal{O}(|\mathcal{A}|).$

Specifying $\Delta=\sqrt{\frac{8(|\widetilde{\mathcal{A}^{*}}|-1)\log T}{T}}$
concludes the proof. $\square$

Denote the contextual bandit instances with prior knowledge $l(a)$ and $h(a)$
as

$\mathfrak{M}=\\{\text{MAB bandit instances with }l(a)\leq\mu_{a}\leq
h(a),\forall a\in\mathcal{A}\\}.$

###### Theorem A.2

Suppose $|\mathcal{A}|<\infty$. Then for any algorithm $\mathsf{A}$, there
exists an absolute constant $c>0$ such that

$\min_{\mathsf{A}}\sup_{\mathfrak{M}}Reg(T)\geq\frac{1}{27}\sqrt{(|\widetilde{\mathcal{A}^{*}}|-1)T}.$

Proof.  This is a direct corollary of MAB regret lower bound, because any arm
in $\widetilde{\mathcal{A}^{*}}$ cannot be the optimal one. $\square$

###  A.5 Proof of Proposition 3.3

Proof.  From the rule of do-calculus, we have

$\displaystyle\mathbb{E}[Y|do(a),w]=$
$\displaystyle\int_{u\in\mathcal{U}}\mathbb{E}[Y|do(a),w,u]dF(u)$
$\displaystyle=$
$\displaystyle\int_{u\in\mathcal{U}}\mathbb{E}[Y|a,w,u]dF(u).$

The last equality is due to the rule of do-calculus as $W$ and $U$ is
sufficient to block all back-door paths from $A$ to $Y$. $\square$

###  A.6 Proof of Proposition 3.4

Proof.  In the discrete setting, the causal effect can be written as

$\mathbb{E}[Y|do(a),w]=\sum_{u\in\mathcal{U},y\in\mathcal{Y}}y\mathbb{P}(y|a,w,u)\mathbb{P}(u).$

The sample size of $\hat{\mathbb{P}}(u)$ and $\hat{\mathbb{P}}(y|a,w,u)$ is at
least $\kappa n$. Due to i.d.d. assumption of each tuple $(y,u)$ and
Hoeffding’s inequality, then with probability at least
$1-\delta/(2|\mathcal{U}||\mathcal{Y}|)$, we have

$|\hat{\mathbb{P}}(u)-\mathbb{P}(u)|\leq\exp(-\kappa
n\delta^{2}/(2|\mathcal{U}|^{2}|\mathcal{Y}|^{2})),|\hat{\mathbb{P}}(y|a,w,u)-\mathbb{P}(y|a,w,u)|\leq\exp(-\kappa
n\delta^{2}/(2|\mathcal{U}|^{2}|\mathcal{Y}|^{2})).$

Therefore, since

$\hat{\mathbb{E}}[Y|do(a),w]=\sum_{u\in\mathcal{U},y\in\mathcal{Y}}y\hat{\mathbb{P}}(y|a,w,u)\hat{\mathbb{P}}(u),$

with probability at least $1-\delta$, we have

$\displaystyle|\hat{\mathbb{E}}[Y|do(a),w]-{\mathbb{E}}[Y|do(a),w]|$
$\displaystyle=$
$\displaystyle\left|\sum_{u\in\mathcal{U},y\in\mathcal{Y}}y(\hat{\mathbb{P}}(y|a,w,u)\hat{\mathbb{P}}(u)-{\mathbb{P}}(y|a,w,u){\mathbb{P}}(u))\right|$
$\displaystyle\leq$
$\displaystyle\sum_{u\in\mathcal{U},y\in\mathcal{Y}}y|\hat{\mathbb{P}}(y|a,w,u)\hat{\mathbb{P}}(u)-{\mathbb{P}}(y|a,w,u){\mathbb{P}}(u)|$
$\displaystyle\leq$
$\displaystyle\sum_{u\in\mathcal{U},y\in\mathcal{Y}}y\left(|\hat{\mathbb{P}}(y|a,w,u)-{\mathbb{P}}(y|a,w,u)|\mathbb{P}(u)+\hat{\mathbb{P}}(y|a,w,u)|\hat{\mathbb{P}}(u)-{\mathbb{P}}(u)|\right)$
$\displaystyle\leq$ $\displaystyle
2|\mathcal{U}|(\sum_{y\in\mathcal{Y}}y)\exp(-\kappa
n\delta^{2}/(2|\mathcal{U}|^{2}|\mathcal{Y}|^{2})).$

Let the RKS be equal to $\epsilon$. Then we have

$n\geq\frac{2|\mathcal{U}|^{2}|\mathcal{Y}|^{2}}{\kappa\delta^{2}}\ln\left(\frac{2|\mathcal{U}|\sum_{y\in\mathcal{Y}}y}{\epsilon}\right).$

$\square$

###  A.7 Omitted theorems in Task 3

###### Theorem A.3

Given a causal diagram $\mathcal{G}$ and a distribution compatible with
$\mathcal{G}$, let $\\{W,U\\}$ be a set of variables satisfying the back-door
criterion in $\mathcal{G}$ relative to an ordered pair $(A,Y)$, where
$\\{W,U\\}$ is partially observable, i.e., only probabilities $\hat{F}(a,y,w)$
and $\hat{F}(u)$ with the maximum estimation error $\epsilon$, the causal
effects of $A=a_{0}$ on $Y$ when $W=w_{0}$ occurs are then bounded as follows:

$l(w_{0},a_{0})\leq\mathbb{E}[Y|do(a_{0}),w_{0}]\leq h(w_{0},a_{0}),$

where $l(w_{0},a_{0})$ and $h(w_{0},a_{0})$ are solutions to the following
functional optimization problem for any given $a_{0}$ and $w_{0}$

$\displaystyle
l(w_{0},a_{0})=\inf\int_{w\in\mathcal{W},u\in\mathcal{U}}\int_{y\in\mathcal{Y}}ydF(y|a_{0},w_{0},u)dF(u)$
$\displaystyle
h(w_{0},a_{0})=\sup\int_{w\in\mathcal{W},u\in\mathcal{U}}\int_{y\in\mathcal{Y}}ydF(y|a_{0},w_{0},u)dF(u)$
$\displaystyle s.t.$ $\displaystyle
F(y|a,w,u)F(a,w,u)=F(a,y,w,u),\forall(a,y,w,u)\in\mathcal{A}\times\mathcal{Y}\times\mathcal{W}\times\mathcal{U}$
$\displaystyle\int_{y\in\mathcal{Y}}dF(a,y,w,u)=F(a,w,u),\forall(a,w,u)\in\mathcal{A}\times\mathcal{W}\times\mathcal{U}$
$\displaystyle\int_{a\in\mathcal{A},y\in\mathcal{Y},w\in\mathcal{W}}dF(a,y,w,u)=F(u),\forall
u\in\mathcal{U}$
$\displaystyle\int_{u\in\mathcal{U}}dF(a,y,w,u)=F(a,y,w),\forall(a,y,w)\in\mathcal{A}\times\mathcal{W}\times\mathcal{U}$
$\displaystyle|F(a,y,w)-\hat{F}(a,y,w)|\leq\epsilon,\forall(a,y,w)\in\mathcal{A}\times\mathcal{Y}\times\mathcal{W}$
$\displaystyle|F(u)-\hat{F}(u)|\leq\epsilon,\forall u\in\mathcal{U}.$

Here the inf/sup is taken with respect to all unknown cumulative distribution
functions $F(a,y,w,u)$, $F(a,y,w)$, $F(a,w,u)$, $F(u)$.

Proof.  The object is shown in the proof of Proposition 3.3. The equalities
come from the normalization properties, and inequalities follow from
estimation error. $\square$

Denote the followng optimization problem

$\displaystyle\max/\min\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a),w}]$ (15)
$\displaystyle\sum_{l}x_{ijkl}={\theta}_{ijk},\forall
i\in[n_{\mathcal{A}}],j\in[n_{\mathcal{Y}}],k\in[n_{\mathcal{W}}]$
$\displaystyle\sum_{ijk}x_{ijkl}={\theta}_{l},\forall l\in[n_{\mathcal{U}}].$

where the objective $\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a),w}]$ after
discretization is defined as

$\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a),w}]=\sum_{jkl}\frac{y_{j}\theta_{l}x_{ijkl}}{\sum_{j^{\prime}}x_{ij^{\prime}kl}}.$
(16)

Denote the solutions to (15) as $\hat{l}(w,a)$ and $\hat{h}(w,a)$. Note that
the optimization problem (13) shares the same feasible region with that of
(4).

###### Proposition A.1

Assume that the sampling measure $\mathbb{P}_{s}$ satisfies
$\forall\mathbf{x}\in\mathcal{D}$, and $\forall\delta>0$,

$\mathbb{P}_{s}(\mathcal{B}(\mathbf{x},\delta)\cap\mathcal{D})>0,$

where $\mathcal{B}(\mathbf{x},\delta)$ is a ball centered at $\mathbf{x}$ with
radius $\delta$. If the discrepancy parameter is set to $0$, then
$b_{(1)}(w,a)$ converges to $\hat{l}(w,a)$ in probability and $b_{(B)}(w,a)$
converges to $\hat{h}(w,a)$ in probability for any given $(w,a)$ and
$B\to\infty$.

Proof.  As shown in (14), the object can also be regarded as a function of
$\mathbf{x}$. We define $\phi=\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a),w}]$
which is a continuous mapping from $\mathcal{D}$ to $[0,1]$. The continuity of
$\phi$ holds similarly.

Given that $\mathcal{D}$ is a compact set, there exists $\mathbf{x}_{l}$ such
that $\phi(\mathbf{x}_{l})=\hat{l}(w,a)$. The continuity indicates that
$\forall\epsilon>0$, there exists $\delta>0$ such that
$\phi(\mathbf{x})<\hat{l}(w,a)+\epsilon$ for all
$\mathbf{x}\in\mathcal{B}(x_{h},\delta)$, then

$\mathbb{P}(b(w,a)<\hat{l}(w,a)+\epsilon)=\mathbb{P}_{s}\left(\bigcup_{b<\hat{l}(w,a)+\epsilon}\\{\mathbf{x}\in\mathcal{D}|\phi(\mathbf{x})=b\\}\right)\geq\mathbb{P}_{s}(\mathcal{B}(\mathbf{x}_{h},\delta))>0.$

This implies that

$\mathbb{P}(b_{(1)}(w,a)<\hat{l}(w,a)+\epsilon)=1-(1-\mathbb{P}(b(w,a)<\hat{l}(w,a)+\epsilon))^{B}\to
1$

as $B\to\infty$. Since $b_{(1)}(a)$ is a feasible solution to the discrete
optimization problem, we have

$\mathbb{P}(\hat{l}(w,a)\leq
b_{(1)}(w,a)<\hat{l}(w,a)+\epsilon)=1-(1-\mathbb{P}(b(w,a)<\hat{l}(w,a)+\epsilon))^{B}\to
1$

which implies $b_{(1)}(w,a)\to\hat{l}(w,a)$ in probability.

Similarly, we can prove that
$\mathbb{P}(b_{(B)}(w,a)>\hat{h}(w,a)-\epsilon)<1$ and thus
$b_{(B)}(w,a)\to\hat{h}(w,a)$ in probability.

$\square$

We can also incorporate the optimization procedure OPT. Replacing the
objective (5) in Algorithm 6 with (14), we can also prove the similar almost
surely convergence result.

###### Proposition A.2

Assume that the sampling measure $\mathbb{P}_{s}$ satisfies
$\forall\mathbf{x}\in\mathcal{D}$, and $\forall\delta>0$,

$\mathbb{P}_{s}(\mathcal{B}(\mathbf{x},\delta)\cap\mathcal{D})>0,$

where $\mathcal{B}(\mathbf{x},\delta)$ is a ball centered at $\mathbf{x}$ with
radius $\delta$. Given a deterministic procedure OPT which satisfies for any
local optima $\mathbf{x}_{loc}$, there exists $\delta>0$ such that for any
initial guess
$\mathbf{x}_{0}\in\mathcal{B}(\mathbf{x}_{loc},\delta)\cap\mathcal{D}$, OPT
can output $\mathbf{x}_{loc}$ as a result. If the discrepancy parameter is set
to $0$, then $b_{(1)}(w,a)$ and $b_{(B)}(w,a)$ converge almost surely to
$\hat{l}(w,a)$ and $\hat{h}(w,a)$ for $B\to\infty$, respectively.

Proof.  The one-to-one correspondence between $\mathbf{x}$ and each causal
model has been proved in Lemma A.1. Therefore, $[\hat{l}(w,a),\hat{h}(w,a)]$
is the support of the induced distribution on casual bounds. As shown in the
proof of Proposition 3.1, the defined
$\phi=\hat{\mathbb{E}}_{\mathcal{M}}[{Y|do(a),w}]$ is a continuous mapping
from $\mathcal{D}$ to $[0,1]$.

Given that $\mathcal{D}$ is a compact set, there exists $\mathbf{x}_{l}$ such
that $\phi(\mathbf{x}_{l})=\hat{l}(w,a)$. The property of OPT implies that
there exists $\delta>0$ such that

$\textbf{OPT}(min/max,\eqref{eq: object-average causal
effect},\mathcal{D},\mathbf{x})=\mathbf{x}_{l},\forall\mathbf{x}\in\mathcal{B}(\mathbf{x}_{l},\delta)\cap\mathcal{D}.$

Hence, we have

$\mathbb{P}(b(w,a)=\hat{l}(w,a))\geq\mathbb{P}_{s}(\mathcal{B}(\mathbf{x}_{l},\delta)\cap\mathcal{D})>0.$

Due to Borel-Cantelli lemma we can prove that $b_{(1)}(w,a)\to\hat{l}(w,a)$
almost surely, because each $b_{i}(w,a)$ is independently sampled by Algorithm
6. Similarly, we can prove that $b_{(B)}(w,a)\to\hat{h}(w,a)$ almost surely.

$\square$

###  A.8 Proof of Theorem 3.3

Proof.  We consider any given $w$ in the following proof.

Case 1: $h(w,a)<\max_{i\in\mathcal{A}}l(w,i)$

From the algorithmic construction, we know that such arm $a$ is removed and
thus

$\mathbb{E}[N_{a}(T_{w})]=0.$

Case 2: $\max_{i\in\mathcal{A}}l(w,i)\leq h(w,a)<\mu^{*}_{w}$.

Let $a_{w}^{*}=\mathop{\arg\max}_{a\in\mathcal{A}}\mathbb{E}[Y|do(a),w]$ be
the optimal action with respect to $w$. Define the following event

$\mathcal{E}_{w}(t)=\left\\{\hat{\mu}_{w,a}\in[{\mu}_{w,a}-\frac{\log
t}{n_{w,a}(t)},{\mu}_{w,a}+\frac{\log t}{n_{w,a}(t)}],\forall
a\in\mathcal{A}\right\\}$

Then the Chernoff’s bound yields

$\mathbb{P}(\overline{\mathcal{E}_{w}(t)})\leq\sum_{a\in\mathcal{A}}\exp(-2n_{w,a}(t)\times\frac{\log
t}{n_{w,a}(t)})\leq\frac{|\mathcal{A}|}{t^{2}}$

For any given $w$, the event $\\{A_{t}=a\\}$ implies
$\hat{U}_{w,a}(t)>\hat{U}_{w,a_{w}^{*}}(t)$. However,

$\mu_{w}^{*}>h(w,a)\geq\hat{U}_{w,a}(t)$

and

$\hat{U}_{w,a_{w}^{*}}(t)\geq\mu^{*}_{w}$

if $\mathcal{E}_{w}(t)$ holds. This leads to contradiction. Therefore,

$\displaystyle\mathbb{E}[N_{a}(T_{w})]$
$\displaystyle=\sum_{t=1}^{T_{w}}\mathbb{P}(A_{t}=a|w_{t}=w)$
$\displaystyle=\sum_{t=1}^{T_{w}}\mathbb{P}(A_{t}=a|w_{t}=w,\mathcal{E}_{w}(t))\mathbb{P}(\mathcal{E}_{w}(t))+\mathbb{P}(A_{t}=a|w_{t}=w,\overline{\mathcal{E}_{w}(t)})\mathbb{P}(\overline{\mathcal{E}_{w}(t)})$
$\displaystyle\leq\sum_{t=1}^{T_{w}}\mathbb{P}(\overline{\mathcal{E}_{w}(t)})$
$\displaystyle\leq\sum_{t=1}^{T_{w}}\frac{|\mathcal{A}|}{t^{2}}$
$\displaystyle\leq\frac{|\mathcal{A}|\pi^{2}}{6}.$

Case 3: $h(w,a)\geq\mu^{*}_{w}$

We reuse the notation $\mathcal{E}_{w}(t)$ in the case 2. Condition on the
event $\bigcap_{t=1}^{T_{w}}\mathcal{E}_{w}(t)$, if $n_{w,a}(t)\geq\frac{8\log
T_{w}}{\Delta_{w,a}^{2}}$, then

$\hat{U}_{w,a}(t)\leq U_{w,a}(t)=\mu_{w,a}+\sqrt{\frac{2\log
t}{n_{w,a}(t)}}\leq\mu_{w,a}+\frac{1}{2}\Delta_{w,a}=\mu_{w}^{*}\leq\hat{U}_{w,a_{w}^{*}}(t),$

so Algorithm 4 will not choose the action $a$ at the round $t$. Therefore,

$\mathbb{E}[N_{a}(T_{w})]\leq\mathbb{E}\left[N_{a}(T_{w}),\bigcap_{t=1}^{T_{w}}\mathcal{E}_{w}(t)\right]+T_{w}\mathbb{P}\left(\overline{\bigcap_{t=1}^{T_{w}}\mathcal{E}_{w}(t)}\right)\leq\frac{8\log
T_{w}}{\Delta_{w,a}^{2}}+T_{w}\mathbb{P}\left(\overline{\bigcup_{t=1}^{T_{w}}\mathcal{E}_{w}(t)}\right).$

We conclude the proof by showing

$T_{w}\mathbb{P}\left(\overline{\bigcup_{t=1}^{T_{w}}\mathcal{E}_{w}(t)}\right)\leq
T_{w}\sum_{t=1}^{T_{w}}\frac{|\mathcal{A}|}{t^{2}}<T_{w}\times\frac{|\mathcal{A}|}{T_{w}}=|\mathcal{A}|.$

$\square$

###  A.9 Proof of Theorem 3.4

Proof.  Let $\Delta_{w}$ be the constant with respect to $w$ that we will
specify later. From the proof of Theorem 3.3, we know that the expected regret
can be upper bounded as

$\displaystyle\mathbb{E}[Reg(T)]$
$\displaystyle=\sum_{w\in\mathcal{W}}\sum_{a\in\mathcal{A}}\Delta_{w,a}\mathbb{E}[N_{a}(T_{w})]$
$\displaystyle\leq\sum_{w\in\mathcal{W}}\left(\sum_{a\in\widetilde{\mathcal{A}^{*}}(w)}\frac{8\log
T_{w}}{\Delta_{w,a}}\mathbf{I}\left\\{\Delta_{w,a}\geq\Delta_{w}\right\\}+T\Delta_{w}\right)+\mathcal{O}(|\mathcal{A}|)$
$\displaystyle\leq\sum_{w\in\mathcal{W}}\left(\frac{8(|\widetilde{\mathcal{A}^{*}}(w)|-1)\log
T}{\Delta_{w}}+T_{w}\Delta_{w}\right)+\mathcal{O}(|\mathcal{A}|).$

We select $\Delta_{w}=\sqrt{\frac{8\widetilde{|\mathcal{A}^{*}}(w)|\log
T}{T_{w}}}$ so

$\mathbb{E}[Reg(T)]\leq\sum_{w\in\mathcal{W}}\sqrt{8(|\widetilde{\mathcal{A}^{*}}(w)|-1)T_{w}\log
T}.$

By strong law of large numbers, we have

$\displaystyle\limsup_{T\to\infty}\frac{\mathbb{E}[Reg(T)]}{\sqrt{T\log
T}}\leq$
$\displaystyle\sum_{w\in\mathcal{W}}\sqrt{8(|\widetilde{\mathcal{A}^{*}}(w)|-1)\limsup_{T\to\infty}\frac{T_{w}}{T}}$
$\displaystyle=$
$\displaystyle\sum_{w\in\mathcal{W}}\sqrt{8(|\widetilde{\mathcal{A}^{*}}(w)|-1)\mathbb{P}(W=w)}.$

$\square$

###

Proof.  Consider $|\mathcal{W}|$ MAB instances. For any given context $w$, the
set that the optimal arm will be in is $\mathcal{A}^{*}(w)$. For any algorithm
$\mathsf{A}$, let $\mathsf{A}_{w}$ be the induced algorithm of $\mathsf{A}$
when $w$ occurs. From the minimax theorem for MAB instances [16], we know that
there exists a MAB instance for each $w$ such that the regret of
$\mathsf{A}_{w}$ is at least
$\frac{1}{27}\sqrt{(|\widetilde{\mathcal{A}^{*}}(w)|-1)T_{w}},$ where $T_{w}$
is the number of occurrence of $w$. Hence,

$\displaystyle Reg(T)$
$\displaystyle\geq\sum_{w\in\mathcal{W}}\frac{1}{27}\sqrt{(|\widetilde{\mathcal{A}^{*}}(w)|-1)T_{w}}.$

and thus

$\displaystyle\limsup_{T\to\infty}\frac{Reg(T)}{\sqrt{T}}$
$\displaystyle\geq\frac{1}{27}\sum_{w\in\mathcal{W}}\sqrt{(|\widetilde{\mathcal{A}^{*}}(w)|-1)\cdot\limsup_{T\to\infty}\frac{T_{w}}{T}}$
$\displaystyle=\frac{1}{27}\sum_{w\in\mathcal{W}}\sqrt{(|\widetilde{\mathcal{A}^{*}}(w)|-1)\mathbb{P}(W=w)}.$

$\square$

###  A.10 Proof of Theorem 3.6

The framework presented in [34, 10] provides a method to analyze contextual
bandit algorithms in the universal policy space $\Psi$. In this paper, we
mainly focus on a subspace of $\Psi$ shaped by causal bounds. We demonstrate
that the action distribution $p_{m}$ selected in Algorithm 5 possesses
desirable properties that contribute to achieving low regrets.

For each epoch $m$ and any round $t$ in epoch $m$, for any possible
realization of $\gamma_{t}$, $\hat{f}_{m}$, we define the universal policy
space of $\Psi$:

$\Psi=\prod_{w\in\mathcal{W}}\mathcal{A}^{*}(w).$

With abuse of notations, we define

$\mathcal{R}(\pi)=\mathbb{E}_{W}[f^{*}(W,\pi(W))]\text{ and
}Reg(\pi)=\mathcal{R}(\pi_{f^{*}})-\mathcal{R}(\pi).$

The above quantities do not depend on specific values of $W$. The following
empirical version of above quantities are defined as

$\widehat{\mathcal{R}}_{t}(\pi)=\hat{f}_{m(t)}(w,\pi(w))\text{ and
}\widehat{Reg}_{t}(\pi)=\mathbb{E}_{W}[\widehat{\mathcal{R}}_{t}(\pi_{\hat{f}_{m(t)}})-\widehat{\mathcal{R}}_{t}(\pi)],$

where $m(t)$ is the epoch of the round $t$.

Let $Q_{m}(\cdot)$ be the equivalent policy distribution for
$p_{m}(\cdot|\cdot)$, i.e.,

$Q_{m}(\pi)=\prod_{w\in\mathcal{W}}p_{m}(\pi(w)|w),\forall\pi\in\Psi.$

The existence and uniqueness of such measure $Q_{m}(\cdot)$ is a corollary of
Kolmogorov’s extension theorem. Note that both $\Psi$ and $Q_{m}(\cdot)$ are
$\mathcal{H}_{\tau_{m-1}}$-measurable, where $\mathcal{H}_{t}$ is the
filtration up to the time $t$. We refer to Section 3.2 of [34] for more
detailed intuition for $Q_{m}(\cdot)$ and proof of existence. By Lemma 4 of
[34], we know that for all epoch $m$ and all rounds $t$ in epoch $m$, we can
rewrite the expected regret in terms of our notations as

$\mathbb{E}[Reg(T)]=\sum_{\pi\in\Psi}Q_{m}(\pi)Reg(\pi).$

For simplicity, we define an epoch-dependent quantities

$\rho_{1}=1,\rho_{m}=\sqrt{\frac{\eta\tau_{m-1}}{\log(2\delta^{-1}|\mathcal{F}^{*}|\log
T)}},m\geq 2,$

so $\gamma_{t}=\sqrt{|\mathcal{A}^{*}(w_{t})|}\rho_{m(t)}$ for $m(t)\geq 2$.

###### Lemma A.2

(Implicit Optimization Problem). For all epoch $m$ and all rounds $t$ in epoch
$m$, $Q_{m}$ is a feasible solution to the following implicit optimization
problem:

$\displaystyle\sum_{\pi\in\Psi}Q_{m}(\pi)\widehat{Reg}_{t}(\pi)\leq\mathbb{E}_{W}[\sqrt{|\mathcal{A}^{*}(W)|}]/\rho_{m}$
(17)
$\displaystyle\mathbb{E}_{W}\left[\frac{1}{p_{m}(\pi(W)|W)}\right]\leq\mathbb{E}_{W}[\mathcal{A}^{*}(W)]+\mathbb{E}_{W}[\sqrt{|\mathcal{A}^{*}(W)|}]\rho_{m}\widehat{Reg}_{t}(\pi),\forall\pi\in\Psi.$
(18)

Proof.  Let $m$ and $t$ in epoch $m$ be fixed. Denote
$\mathcal{P}(\mathcal{W})$ as the context distribution. We have

$\displaystyle\sum_{\pi\in\Psi}Q_{m}(\pi)\widehat{Reg}_{t}(\pi)$
$\displaystyle=$
$\displaystyle\sum_{\pi\in\Psi}Q_{m}(\pi)\mathbb{E}_{w_{t}}\left[(\hat{f}_{m}(w_{t},\pi_{\hat{f}_{m}}(w_{t}))-\hat{f}_{m}(w_{t},\pi(w_{t})))\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{w_{t}\sim\mathcal{P}(\mathcal{W})}\left[\sum_{a\in\mathcal{A}^{*}(w_{t})}\sum_{\pi\in\Psi}\mathbf{I}\left\\{\pi(w_{t})=a\right\\}Q_{m}(\pi)(\hat{f}_{m}(w_{t},\pi_{\hat{f}_{m}}(w_{t}))-\hat{f}_{m}(w_{t},a))\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{w_{t}\sim\mathcal{P}(\mathcal{W})}\left[\sum_{a\in\mathcal{A}^{*}(w_{t})}p_{m}(a|w_{t})(\hat{f}_{m}(w_{t},\pi_{\hat{f}_{m}}(w_{t}))-\hat{f}_{m}(w_{t},a))\right].$

The first and second equalities are the definitions of
$\widehat{Reg}_{t}(\pi)$ and $Q_{m}(\pi)$, respectively.

Now for the context $w_{t}$, we have

$\displaystyle\sum_{a\in\mathcal{A}^{*}(w_{t})}p_{m}(a|w)(\hat{f}_{m}(w_{t},\pi_{\hat{f}_{m}}(w_{t}))-\hat{f}_{m}(w_{t},a))$
$\displaystyle=\sum_{a\in\mathcal{A}^{*}(w_{t})-\\{\pi_{\hat{f}_{m}}(w_{t})\\}}\frac{\hat{f}_{m}(w_{t},\pi_{\hat{f}_{m}}(w_{t}))-\hat{f}_{m}(w_{t},a)}{|\mathcal{A}^{*}(w_{t})|+\gamma_{t}(\hat{f}_{m}(w_{t},\pi_{\hat{f}_{m}}(w_{t}))-\hat{f}_{m}(w_{t},a))}$
$\displaystyle\leq[|\mathcal{A}^{*}(w_{t})|-1]/\gamma_{t}$
$\displaystyle\leq\sqrt{|\mathcal{A}^{*}(w_{t})|}/\rho_{m}.$

We plug in the above term and apply the i.d.d. assumption on $w_{t}$ to
conclude the proof of the first inequality.

For the second inequality, we first observe that for any policy $\pi\in\Psi$,
given any context $w\in\mathcal{W}$,

$\frac{1}{p_{m}(\pi(w)|w)}=|\mathcal{A}^{*}(w)|+\gamma_{t}(\hat{f}_{m}(w,\pi_{\hat{f}_{m}}(w))-\hat{f}_{m}(w,a)),$

if $a\neq\pi_{\hat{f}_{m}}(w)$, and

$\frac{1}{p_{m}(\pi(w)|w)}\leq\frac{1}{1/|\mathcal{A}^{*}(w)|}=|\mathcal{A}^{*}(w)|+\gamma_{t}(\hat{f}_{m}(w,\pi_{\hat{f}_{m}}(w))-\hat{f}_{m}(w,a)),$

if $a=\pi_{\hat{f}_{m}}(w)$. The result follows immediately by taking
expectation over $w$. $\square$

Compared with IOP in [34], the key different part is that
$\mathbb{E}_{W}[|\mathcal{A}^{*}(W)|]$ is replaced by the cardinality
$|\mathcal{A}|$ of the whole action set. Another different part is the
universal policy space $\Psi$. We define $\Psi$ as
$\prod_{w\in\mathcal{W}}\mathcal{A}^{*}(w)$ rather than
$\prod_{w\in\mathcal{W}}\mathcal{A}$. These two points highlight the
adaptivity to contexts and show how causal bound affects the action selection.

Define the following high-probability event

$\Gamma=\left\\{\forall m\geq
2,\frac{1}{\tau_{m-1}}\sum_{t=1}^{\tau_{m-1}}\mathbb{E}_{w_{t},a_{t}}[(\hat{f}_{m(t)}(w_{t},a_{t})-f^{*}(w_{t},a_{t}))^{2}|\mathcal{H}_{t-1}]\leq\frac{1}{\rho_{m}^{2}}\right\\}.$

The high-probability event and its variants have been proved in literatures
[9, 34, 10]. Our result is slightly different from them as the whole function
space is eliminated to $\mathcal{F}^{*}$. Since these results share the same
form, it is straightforward to show $\Gamma$ holds with probability at least
$1-\delta/2$. This is the result of the union bound and the property of the
Least Square Oracle that is independent of algorithm design.

Our setting do not change the proof procedure of the following lemma [34],
because this lemma does not explicitly involve the number of action set. This
lemma bounds the prediction error between the true reward and the estimated
reward.

###### Lemma A.3

Assume $\Gamma$ holds. For all epochs $m>1$, all rounds $t$ in epoch $m$, and
all policies $\pi\in\Psi$, then

$\left|\widehat{\mathcal{R}}_{t}(\pi)-\mathcal{R}_{t}(\pi)\right|\leq\frac{1}{2\rho_{m}}\sqrt{\max_{1\leq
m^{\prime}\leq
m-1}\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{m^{\prime}}(\pi(W)|W)}\Bigg{]}}.$

The third step is to show that the one-step regret $Reg_{t}(\pi)$ is close to
the one-step estimated regret $\widehat{Reg}_{t}(\pi)$. The following lemma
states the result.

###### Lemma A.4

Assume $\Gamma$ holds. Let $c_{0}=5.15$. For all epochs $m$ and all rounds $t$
in epoch $m$, and all policies $\pi\in\Psi$,

$\displaystyle Reg(\pi)\leq
2\widehat{Reg}_{t}(\pi)+c_{0}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}/\rho_{m},$
(19) $\displaystyle\widehat{Reg}_{t}(\pi)\leq
2Reg(\pi)+c_{0}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}/\rho_{m},.$ (20)

Proof.  We prove this lemma via induction on $m$. It is easy to check

$Reg(\pi)\leq 1,\widehat{Reg}_{t}(\pi)\leq 1,$

as $\gamma_{1}=1$ and $c_{0}\mathbb{E}_{W}\big{[}\mathcal{A}^{*}(W)\big{]}\geq
1$. Hence, the base case holds.

For the inductive step, fix some epoch $m>1$ and assume that for all epochs
$m^{\prime}<m$, all rounds $t^{\prime}$ in epoch $m^{\prime}$, and all
$\pi\in\Psi$, the inequalities (19) and (20) hold. We first show that for all
rounds $t$ in epoch $m$ and all $\pi\in\Psi$,

$Reg(\pi)\leq
2\widehat{Reg}_{t}(\pi)+c_{0}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}/\rho_{m}.$

We have

$\displaystyle Reg(\pi)-\widehat{Reg}_{t}(\pi)$ $\displaystyle=$
$\displaystyle[\mathcal{R}(\pi_{f^{*}})-\mathcal{R}(\pi)]-[\widehat{\mathcal{R}}_{t}(\pi_{\hat{f}_{m}})-\widehat{\mathcal{R}}_{t}(\pi)]$
$\displaystyle\leq$
$\displaystyle[\mathcal{R}(\pi_{f^{*}})-\mathcal{R}(\pi)]-[\widehat{\mathcal{R}}_{t}(\pi_{f^{*}})-\widehat{\mathcal{R}}_{t}(\pi)]$
$\displaystyle\leq$
$\displaystyle|\mathcal{R}(\pi_{f^{*}})-\widehat{\mathcal{R}}_{t}(\pi_{f^{*}})|+|\mathcal{R}(\pi)-\widehat{\mathcal{R}}_{t}(\pi)|$
$\displaystyle\leq$ $\displaystyle\frac{1}{\rho_{m}}\sqrt{\max_{1\leq
m^{\prime}\leq
m-1}\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{m^{\prime}}(\pi_{f^{*}}(W)|W)}\Bigg{]}}+\frac{1}{\rho_{m}}\sqrt{\max_{1\leq
m^{\prime}\leq
m-1}\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{m^{\prime}}(\pi(W)|W)}\Bigg{]}}$
$\displaystyle\leq$ $\displaystyle\frac{\max\limits_{1\leq m^{\prime}\leq
m-1}\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{m^{\prime}}(\pi_{f^{*}}(W)|W)}\Bigg{]}}{5\rho_{m}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}}+\frac{\max\limits_{1\leq
m^{\prime}\leq
m-1}\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{m^{\prime}}(\pi(W)|W)}\Bigg{]}}{5\rho_{m}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}}+\frac{5\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}}{8\rho_{m}}.$

The last inequality is by the AM-GM inequality. There exists an epoch $i$ such
that

$\max_{1\leq m^{\prime}\leq
m-1}\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{m^{\prime}}(\pi(W)|W)}\Bigg{]}=\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{i}(\pi(W)|W)}\Bigg{]}.$

From Lemma A.2 we know that

$\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{i}(\pi(W)|W)}\Bigg{]}\leq\mathbb{E}_{W}[\mathcal{A}^{*}(W)]+\mathbb{E}_{W}[\sqrt{|\mathcal{A}^{*}(W)|}]\rho_{i}\widehat{Reg}_{t}(\pi),$

holds for all $\pi\in\Psi$, for all epoch $1\leq i\leq m-1$ and for all rounds
$t$ in corresponding epochs.

Hence, for epoch $i$ and all rounds $t$ in this epoch, we have

$\displaystyle\frac{\max\limits_{1\leq m^{\prime}\leq
m-1}\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{m^{\prime}}(\pi(W)|W)}\Bigg{]}}{5\rho_{m}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}}$
$\displaystyle=$
$\displaystyle\frac{\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{i}(\pi_{f^{*}}(W)|W)}\Bigg{]}}{5\rho_{m}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}},\text{
(\lx@cref{creftype~refnum}{lem: IOP}:\eqref{eq: one-step regret bound 2})}$
$\displaystyle\leq$
$\displaystyle\frac{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]+\mathbb{E}_{W}[\sqrt{|\mathcal{A}^{*}(W)|}]\rho_{i}\widehat{Reg}_{t}(\pi)}{5\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}\rho_{m}},\text{
(inductive assumption) }$ $\displaystyle\leq$
$\displaystyle\frac{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]+\mathbb{E}_{W}[\sqrt{|\mathcal{A}^{*}(W)|}]\rho_{i}[2Reg(\pi)+c_{0}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}/\rho_{i}]}{5\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}\rho_{m}},\text{
(Jensen's inequality) }$ $\displaystyle\leq$
$\displaystyle\frac{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]+\sqrt{\mathbb{E}_{W}[|\mathcal{A}^{*}(W)|]}\rho_{i}[2Reg(\pi)+c_{0}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}/\rho_{i}]}{5\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}\rho_{m}},\text{
($\rho_{i}\leq\rho_{m}$ for $i\leq m$) }$ $\displaystyle\leq$
$\displaystyle\frac{2}{5}Reg(\pi)+\frac{1+c_{0}}{5\rho_{m}}\sqrt{\mathbb{E}_{W}[|\mathcal{A}^{*}(W)|]}.$

We can bound $\frac{\max_{1\leq m^{\prime}\leq
m-1}\mathbb{E}_{W}\Bigg{[}\frac{1}{p_{m^{\prime}}(\pi(W)|W)}\Bigg{]}}{5\rho_{m}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}}$
in the same way.

Combing all above inequalities yields

$\displaystyle Reg(\pi)-\widehat{Reg}_{t}(\pi)\leq$
$\displaystyle\frac{2(1+c_{0})\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}}{5\rho_{m}}+\frac{4}{5}\widehat{Reg}_{t}(\pi)+\frac{5\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}}{8\rho_{m}}$
$\displaystyle\leq$
$\displaystyle\widehat{Reg}_{t}(\pi)+(\frac{2(1+c_{0})}{5}+\frac{5}{8})\frac{\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}}{\rho_{m}}$
$\displaystyle\leq$
$\displaystyle\widehat{Reg}_{t}(\pi)+c_{0}\frac{\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}}{\rho_{m}}.$

Similarly, we have

$\displaystyle\widehat{Reg}_{t}(\pi)-Reg(\pi)$ $\displaystyle=$
$\displaystyle[\widehat{\mathcal{R}}_{t}(\pi_{\hat{f}_{m}})-\widehat{\mathcal{R}}_{t}(\pi)]-[\mathcal{R}(\pi_{f^{*}})-\mathcal{R}(\pi)]$
$\displaystyle\leq$
$\displaystyle[\widehat{\mathcal{R}}_{t}(\pi_{\hat{f}_{m}})-\widehat{\mathcal{R}}_{t}(\pi)]-[\mathcal{R}(\pi_{\hat{f}_{m}})-\mathcal{R}(\pi)]$
$\displaystyle\leq$
$\displaystyle|\mathcal{R}(\pi_{\hat{f}_{m}})-\widehat{\mathcal{R}}_{t}(\pi_{\hat{f}_{m}})|+|\mathcal{R}(\pi)-\widehat{\mathcal{R}}_{t}(\pi)|.$

We can bound the above terms in the same steps.

$\square$

Proof.  Our regret analysis builds on the framework in [34].

Step 1: proving an implicit optimization problem for $Q_{m}$ in Lemma A.2.

Step 2: bounding the prediction error between $\widehat{\mathcal{R}}_{t}(\pi)$
and $\mathcal{R}_{t}(\pi)$ in Lemma A.3. Then we can show that the one-step
regrets $\widehat{Reg}_{t}(\pi)$ and ${Reg}(\pi)$ are close to each other.

Step 3: bounding the cumulative regret $Reg(T)$.

By Lemma 4 of [34],

$\mathbb{E}[Reg(T)]=\sum_{t=1}^{T}\sum_{\pi\in\Psi}Q_{m(t)}(\pi)Reg(\pi).$

From Lemma A.4, we know

$Reg(\pi)\leq
2\widehat{Reg}_{t}(\pi)+c_{0}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}/\rho_{m}$

so

$\displaystyle\mathbb{E}[Reg(T)]=$
$\displaystyle\sum_{t=1}^{T}\sum_{\pi\in\Psi}Q_{m(t)}(\pi)Reg(\pi)$
$\displaystyle\leq$ $\displaystyle
2\sum_{t=1}^{T}\sum_{\pi\in\Psi}Q_{m(t)}(\pi)\widehat{Reg}_{t}(\pi)+\sum_{t=1}^{T}c_{0}\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}/\rho_{m(t)}$
$\displaystyle\leq$
$\displaystyle(2+c_{0})\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}\sum_{t=1}^{T}\frac{1}{\rho_{m(t)}}$
$\displaystyle\leq$
$\displaystyle(2+c_{0})\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}\sum_{m=1}^{\left\lceil\log
T\right\rceil}\sqrt{\log(2\delta^{-1}|\mathcal{F}^{*}|\log T)\tau_{m-1}/\eta}$
$\displaystyle\leq$
$\displaystyle(2+c_{0})\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]}\sum_{m=1}^{\left\lceil\log
T\right\rceil}\sqrt{\log(2\delta^{-1}|\mathcal{F}^{*}|\log T)\tau_{m-1}/\eta}$
$\displaystyle\leq$
$\displaystyle(2+c_{0})\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]\log(2\delta^{-1}|\mathcal{F}^{*}|\log
T)\sum_{m=1}^{\left\lceil\log T\right\rceil}\tau_{m-1}/\eta}$
$\displaystyle\leq$
$\displaystyle(2+c_{0})\sqrt{\mathbb{E}_{W}[\mathcal{A}^{*}(W)]\log(2\delta^{-1}|\mathcal{F}^{*}|\log
T)T/\eta}.$

$\square$

###  A.11 Proof of Theorem 3.5

Proof.  We first consider $|\mathcal{W}|<\infty$. Since the agent have
knowledge about causal bound, any function in $\mathcal{F}-\mathcal{F}^{*}$
can not be the true reward function. For any given context $w$, the set that
the optimal arm will be in is $\mathcal{A}^{*}(w)$. For any algorithm
$\mathsf{A}$, let $\mathsf{A}_{w}$ be the induced algorithm of $\mathsf{A}$
when $w$ occurs. Namely, the agent has access to a function space
$\mathcal{F}_{w}=\\{f(w,\cdot)|\forall f\in\mathcal{F}^{*}\\}$ and an action
set $\mathcal{A}^{*}(w)$.

From the minimax theorem 5.1 in [1], we know that there exists a contextual
bandit instance such that the regret of $\mathsf{A}_{w}$ is at least
$\sqrt{{\mathcal{A}^{*}}(w)T_{w}\log|\mathcal{F}_{w}|}=\sqrt{{\mathcal{A}^{*}}(w)T_{w}\log|\mathcal{F}^{*}|},$
where $T_{w}$ is the number of occurrence of $w$. Hence,

$\displaystyle Reg(T)$
$\displaystyle\geq\sum_{w\in\mathcal{W}}\sqrt{|{\mathcal{A}^{*}}(w)|T_{w}\log|\mathcal{F}^{*}|}$
$\displaystyle\geq\sqrt{\sum_{w\in\mathcal{W}}|{\mathcal{A}^{*}}(w)|T_{w}\log|\mathcal{F}^{*}|}.$

and thus

$\displaystyle\limsup_{T\to\infty}\frac{Reg(T)}{\sqrt{T}}$
$\displaystyle\geq\sqrt{\sum_{w\in\mathcal{W}}|{\mathcal{A}^{*}}(w)|\log|\mathcal{F}^{*}|\cdot\limsup_{T\to\infty}\frac{T_{w}}{T}}$
$\displaystyle=\sqrt{\sum_{w\in\mathcal{W}}|{\mathcal{A}^{*}}(w)|\log|\mathcal{F}^{*}|\mathbb{P}(W=w)}$
$\displaystyle=\sqrt{\mathbb{E}_{W}[|{\mathcal{A}^{*}}(W)|]\log|\mathcal{F}^{*}|}.$

Now assume $|\mathcal{W}|=\infty$. Thanks to Glivenko-Cantelli theorem, the
empirical distribution converges uniformly to the true reward distribution. We
conclude the proof by applying the dominated convergence theorem and the
Fubini’s theorem, because ${\mathcal{A}^{*}}(w)$ is uniformly bounded by
$|\mathcal{A}|$.

$\square$

##  Appendix B Related Materials

######  Definition B.1 (Back-Door Criterion)

Given an ordered pair of variables $(X,Y)$ in a directed acyclic graph
$\mathcal{G}$, a set of variables $\mathbf{Z}$ satisfies the back-door
criterion relative to $(X,Y)$, if no node in $\mathbf{Z}$ is a descendant of
$X$, and $\mathbf{Z}$ blocks every path between $X$ and $Y$ that contains an
arrow into $X$.

######  Definition B.2 (d-separation)

In a causal diagram $\mathcal{G}$, a path $\mathcal{P}$ is blocked by a set of
nodes $\mathbf{Z}$ if and only if

  1. 1.

$\mathcal{P}$ contains a chain of nodes $A\leftarrow B\leftarrow C$ or a fork
$A\rightarrow B\leftarrow C$ such that the middle node $B$ is in $\mathbf{Z}$
(i.e., $B$ is conditioned on), or

  2. 2.

$\mathcal{P}$ contains a collider $A\leftarrow B\rightarrow C$ such that the
collision node $B$ is not in $\mathbf{Z}$, and no descendant of $B$ is in
$\mathbf{Z}$.

If $\mathbf{Z}$ blocks every path between two nodes $X$ and $Y$ , then $X$ and
$Y$ are d-separated conditional on $\mathbf{Z}$, and thus are independent
conditional on $\mathbf{Z}$.

If $X$ is a variable in a causal model, its corresponding intervention
variable $I_{X}$ is an exogenous variable with one arrow pointing into $X$.
The range of $I_{X}$ is the same as the range of $X$, with one additional
value we can call “off”. When $I_{X}$ is off, the value of $X$ is determined
by its other parents in the causal model. When $I_{X}$ takes any other value,
$X$ takes the same value as $I_{X}$, regardless of the value of $X$’s other
parents. If $X$ is a set of variables, then $I_{X}$ will be the set of
corresponding intervention variables. We introduce the following do-calculus
rules proposed in [30].

Rule 1 (Insertion/deletion of observations)

$\mathbb{P}(\mathbf{Y}|do(\mathbf{X}),\mathbf{Z},\mathbf{W})=\mathbb{P}(\mathbf{Y}|do(\mathbf{X}),\mathbf{W})$

if $\mathbf{Y}$ and $I_{\mathbf{Z}}$ are d-separated by
$\mathbf{X}\cup\mathbf{W}$ in $\mathcal{G}^{*}$, the graph obtained from
$\mathcal{G}$ by removing all arrows pointing into variables in $\mathbf{X}$.

Rule 2 (Action/observation exchange)

$\mathbb{P}(\mathbf{Y}|do(\mathbf{X}),do(\mathbf{Z}),\mathbf{W})=\mathbb{P}(\mathbf{Y}|do(\mathbf{X}),\mathbf{Z},\mathbf{W})$

if $\mathbf{Y}$ and $I_{\mathbf{Z}}$ are d-separated by
$\mathbf{X}\cup\mathbf{Z}\cup\mathbf{W}$ in $\mathcal{G}^{\dagger}$, the graph
obtained from $\mathcal{G}$ by removing all arrows pointing into variables in
$\mathbf{X}$ and all arrows pointing out of variables in $\mathbf{z}$.

Rule 3 (Insertion/deletion of actions)

$\mathbb{P}(\mathbf{Y}|do(\mathbf{X}),do(\mathbf{Z}),\mathbf{W})=\mathbb{P}(\mathbf{Y}|do(\mathbf{X}),\mathbf{W})$

if $\mathbf{Y}$ and $I_{\mathbf{Z}}$ are d-separated by
$\mathbf{X}\cup\mathbf{W}$ in $\mathcal{G}^{*}$, the graph obtained from
$\mathcal{G}$ by removing all arrows pointing into variables in $\mathbf{X}$.

##  Appendix C Additional algorithms and experiments

We generalize the sampling method for general simplex $\mathcal{D}$

$A\mathbf{x}\leq\mathbf{b},\mathbf{x}\geq\mathbf{0}.$

in Algorithm 7. Without loss of generality, we always assume $\mathcal{D}$ is
not empty.

Algorithm 7 A sampling algorithm for the given simplex

1:a simplex $\mathcal{D}$, a sampling distribution $F_{s}$ supported on
$[0,1]$

2:Denote the number of components of $\mathbf{x}$ as $d$

3:Solving the following LP  $\displaystyle\min/\max x_{1}$ $\displaystyle
A\mathbf{x}\leq\mathbf{b},\mathbf{x}\geq\mathbf{0}.$ to find the bound
$[l_{1},h_{1}]$ for $x_{1}$

4:Sample a value $\hat{x}_{1}$ from the truncated $F_{s}$ supported on
$[l_{1},h_{1}]$

5:for $i=2,\cdots,d$ do

6: Solving the follow LP  $\displaystyle\min/\max x_{i}$ $\displaystyle
A\mathbf{x}\leq\mathbf{b},\mathbf{x}\geq\mathbf{0}$ $\displaystyle
x_{j}=\hat{x}_{j},j=1,\cdots,i-1.$ to find the bound $[l_{i},h_{i}]$ for
$x_{1}$