# Towards Domain Adaptive Neural Contextual Bandits

Ziyan Wang
Georgia Institute of Technology
<EMAIL_ADDRESS>&Hao Wang
Rutgers University
<EMAIL_ADDRESS>

###### Abstract

Contextual bandit algorithms are essential for solving real-world decision
making problems. In practice, collecting a contextual bandit’s feedback from
different domains may involve different costs. For example, measuring drug
reaction from mice (as a source domain) and humans (as a target domain).
Unfortunately, adapting a contextual bandit algorithm from a source domain to
a target domain with distribution shift still remains a major challenge and
largely unexplored. In this paper, we introduce the first general domain
adaptation method for contextual bandits. Our approach learns a bandit model
for the target domain by collecting feedback from the source domain. Our
theoretical analysis shows that our algorithm maintains a sub-linear regret
bound even adapting across domains. Empirical results show that our approach
outperforms the state-of-the-art contextual bandit algorithms on real-world
datasets.

##  1 Introduction

Contextual bandit (CB) algorithms have shown great promise for naturally
handling exploration/exploitation trade-off problems with optimal statistical
properties. Notably, LinUCB [1] and its various adaptations [2, 3, 4, 5, 6, 7,
8, 9], have been shown to be able learn the optimal strategy when all data
come from the same domain. However, these methods fall short when applied to
data from a new domain. For example, a drug reaction prediction model trained
by collecting feedback from mice (the source domain) may not work for humans
(the target domain).

So, how does one effectively explore a high-cost target domain by only
collecting feedback from a low-cost source domain, e.g., exploring drug
reaction in humans by collecting feedback from mice or exploring real-world
environments by collecting feedback from simulated environments? The challenge
of effective cross-domain exploration is multifaceted: (1) The need for
_effective exploration_ in both the source and target domains depends on _the
quality of representations_ learned in the source domain, which in turn
requires _effective exploration_ ; this leads to a chicken-and-egg dilemma.
(2) Aligning source-domain representations with target-domain representations
is nontrivial in bandit settings, where ground-truth may still be unknown if
the action is incorrect. (3) Balancing these aspects – effective exploration
and accurate alignment in bandit settings – is also nontrivial.

To address these challenges, as the first step, we allow our method to
simultaneously perform _effective exploration_ and _representation alignment_
, leveraging unlabeled data from both the source and target domains.
Interestingly, our theoretical analysis reveals that naively doing so leads to
sub-optimal accuracy/regret (verified by our empirical results) and naturally
leads to additional terms in the target-domain regret bound. We then follow
the regret bound derived from our analysis to develop an algorithm that
adaptively collect feedback from the source domain while aligning
representations from the source and target domains. Our contributions are
outlined as follows:

  * •

We identify the problem of contextual bandits across domains and propose
domain-adaptive contextual bandits (DABand) as a the first general method to
explore a high-cost target domain while only collecting feedback from a low-
cost source domain.

  * •

Our theoretical analysis shows that our method can achieve a sub-linear regret
bound in the target domain.

  * •

Our empirical results on real-world datasets show our DABand significantly
improve performance over the state-of-the-art contextual bandit methods when
adapting across domains.

##  2 Related Work

Contextual Bandits. In the realm of adaptive decision-making, contextual
bandit algorithms, epitomized by LinUCB [1], have carved a niche in
efficiently balancing the exploitation-exploration paradigm across a spectrum
of use cases, notably in complex adaptive systems such as recommender systems
[1, 10]. These algorithmic frameworks, along with their myriad adaptations [2,
3, 4, 7, 5, 6, 9, 8, 11], have decisively outperformed conventional bandit
models that operate devoid of contextual awareness [12]. This superiority is
underpinned by theoretical models, paralleling the insights in [12], where
LinUCB variants are validated to conform to optimal regret boundaries in
targeted scenarios [13]. However, a discernible gap in these methodologies is
their reduced efficacy in a new domain, particularly when getting feedback
involves high cost. Our proposed DABand bridges this gap by adeptly aligning
both source-domain and target-domain representations in the latent space,
thereby reducing performance drop when transfer across different domains.

Domain Adaptation. The landscape of domain adaptation has been extensively
explored, as evidenced by a breadth of research [14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25]. The primary objective of these studies has been the
alignment of source and target domain distributions to facilitate the
effective generalization of models trained on labeled source data to unlabeled
target data. This alignment is conventionally attained either through the
direct matching of distributional statistics [15, 26, 27, 20, 24] or via the
integration of an adversarial loss [28, 29, 30, 19, 31, 21, 22, 23]. The
latter, known as adversarial domain adaptation, has surged in prominence,
bolstered by its theoretical foundation [32, 33, 19, 34], the adaptability of
end-to-end training in neural network architectures, and its empirical
efficacy. However, these methods only work in offline settings, and assumes
complete observability of labels in the source domain. Therefore they are not
applicable to our online bandit settings.

Domain Adaptation Related to Bandits. There is also work related to both
domain adaptation and bandits. Specifically, Guo et al. [35] propose a domain
adaptation method using a bandit algorithm to select which domain to use
during training.

We note that their goal and setting is different from our DABand’s. (1) [35]
focuses on improving accuracy in a typical, offline domain adaptation setting.
In contrast, our DABand focuses on minimizing regret in an online bandit
setting. (2) [35] assumes complete access to ground-truth labels in the source
domain, while in our bandit setting, ground-truth may still be unknown if the
action is incorrect. Therefore their work is not applicable to our setting.

##  3 Theory

In this section, we formalize the problem of contextual bandits across domains
and derive the corresponding regret bound. We then develop our DABand inspired
by this bound in Sec. 4. All proofs of lemmas, theorems can be found in the
Appendix.

Notation. We use $[k]$ to denote the set $\\{1,2,\cdots,k\\}$, for
$k\in\mathbb{N}^{+}$. The Euclidean norm of a vector ${\bf
x}\in\mathbb{R}^{d}$ is denoted as $\|{\bf x}\|_{2}=\sqrt{{\bf x}^{T}{\bf
x}}$. We denote the operator norm and Frobenius norm of a matrix ${\bf
W}\in\mathbb{R}^{m\times n}$ as $\|W\|$ and $\|W\|_{F}$, respectively. Given a
semi-definite matrix $A\in\mathbb{R}^{d\times d}$ and a vector ${\bf
x}\in\mathbb{R}^{d}$, we denote the Mahalanobis norm as $\|{\bf
x}\|_{A}=\sqrt{{\bf x}^{T}A{\bf x}}$. For a function $\mathit{f}(T)$ of a
parameter $T$, we denote as $\mathcal{O}(\mathit{f}(T))$ the terms growing in
the order of $\mathit{f}(T)$, ignoring constant factors. We assume all the
action spaces are identical and with cardinality of $K$, i.e.,
$|\mathcal{A}_{1}|=|\mathcal{A}_{2}|=\cdots=|\mathcal{A}_{N}|=K$. We use
$\langle\cdot,\cdot\rangle$ to denote the inner product of two vectors. We
denote as $a_{{\mathcal{D}},i}$ the action $i$ in domain ${\mathcal{D}}$, and
omit the subscript ${\mathcal{D}}$ when the context is clear, e.g.,
$x_{i,a_{i}^{*}}^{\mathcal{D}}\equiv
x_{i,a_{{\mathcal{D}},i}^{*}}^{\mathcal{D}}$.

###  3.1 Preliminaries

Typical Contextual Bandit Setting. Suppose we have $N$ samples from an unknown
domain $\mathcal{D}$, which is represented as $\\{{\bf
x}_{i,a}^{\mathcal{D}},a_{i}^{*}\\}_{i\in[N],a\in[K]}$. Here, ${\bf
x}_{i,a}\in\mathcal{D}$ denotes the context for action $a\in\mathcal{A}_{i}$,
and $a_{i}^{*}\in\mathcal{A}_{i}$ is the ground-truth action that will receive
the optimal reward. We denote as $r_{i,a}$ the received reward in round $i$
after performing action $a$ and $\widehat{a}_{i}\in\mathcal{A}_{i}$ the chose
action by a bandit algorithm in round $i$. The goal in typical contextual
bandits is to learn a policy of choosing actions $\widehat{a}_{i}$ in each
round to minimize the regret after $N$ rounds:

$\displaystyle
R=\sum\nolimits_{i=1}^{N}r_{i,a_{i}^{*}}-\sum\nolimits_{i=1}^{N}r_{i,\widehat{a}_{i}}.$
(1)

LinUCB. LinUCB [1] is a classic method for the typical contextual bandit
setting. It assumes that the reward is linear to its input context, i.e.,
${\bf x}_{i,a}$. During each round $i$, the agent selects an arm according to
historical contexts and their corresponding rewards, $r_{i,a}$:

$\displaystyle\widehat{a}_{i}=\mathop{\rm
argmax}_{a\in\mathcal{A}_{i}}\left\\{{\bf
x}_{i,a}^{T}\theta_{i}+\alpha\left\|{\bf
x}_{i,a}\right\|_{A_{i-1}^{-1}}\right\\},$

where $A_{i-1}=\gamma{\bf I}_{d}+\sum\nolimits_{j=1}^{i-1}{\bf
x}_{j,\widehat{a}_{j}}{\bf x}_{j,\widehat{a}_{j}}^{T}$ with $\gamma>0$ and
${\bf x}_{j,\widehat{a}_{j}}^{T}$ as the historical selected action’s context.
${\bf x}_{i,a}$ is the context for the candidate action $a$ in round $i$.
$\alpha>0$ is a hyperparameter that adjusts the exploration rate.

LinUCB with Representation Learning. In this paper, we use Neural LinUCB [11,
10] as a backbone model to handle high-dimensional context with representation
learning. We assume that there exist a ground-truth encoder $\phi^{*}$ to
encode the raw context ${\bf x}_{i,a}$ into a latent-space representation
(encoding) $\phi^{*}({\bf x}_{i,a})$. Subsequently, the reward for the context
${\bf x}_{i,a}$ is then $r({\bf x}_{i,a})=\langle\theta^{*},\phi^{*}({\bf
x}_{i,a})\rangle$ plus some stochastic noise $\epsilon$. Furthermore, we use
the same setting as in [11] where the ground-truth rewards are restricted to
the range of $[0,1]$. Additionally, we further bound predicted rewards by
normalizing $\|\widehat{\theta}\|=1$ and $\|\widehat{\phi}({\bf
x}_{i,a})\|=1$.

In the single-domain typical setting, the goal is to learn an encoder
$\widehat{\phi}$ and the contextual bandit parameter $\widehat{\theta}$, such
that our estimated reward $\widehat{{r}}({\bf
x}_{i,a})=\langle\widehat{\theta},\widehat{\phi}({\bf x}_{i,a})\rangle$ can be
close to the ground-truth reward $r({\bf x}_{i,a})$. One can then use this to
form derive policies to minimize the regret in Eqn. 1.

For simplicity, in Definition 3.1 below, we further denote as
$f_{\mathcal{D}}$ the (ground-truth) labeling function for domain
$\mathcal{D}$ and as $h\in\mathcal{H}$ a hypothesis such that $f$ is
parameterized by $\phi_{\mathcal{D}}^{*},\theta_{\mathcal{D}}^{*}$, and $h$ is
parameterized by $\widehat{\phi},\widehat{\theta}$.

###  3.2 Our Cross-Domain Contextual Bandit Setting

Typical contextual bandits operate in a single domain ${\mathcal{D}}$. In
contrast, our cross-domain bandit setting involves a source domain
$\mathcal{S}$ and a target domain $\mathcal{T}$. In this setting, one can only
collect feedback (reward) from the source domain, but not from the target
domain. Specifically: (1) We assume a low-cost _source domain_ (experiments on
mice), where for each round $i$, one has access to the contexts $\\{{\bf
x}_{i,a}^{\mathcal{S}}\\}_{a\in[K]}$ for each candidate actions, chooses one
action $\widehat{a}_{i}$, and receives reward
$r^{{\mathcal{S}}}_{i,\widehat{a}_{i}}$. (2) Additionally, we assume a high-
cost _target domain_ where collecting feedback (reward) is expensive
(experiments on humans); therefore, one only has access to the contexts
$\\{{\bf x}_{i,a}^{\mathcal{T}}\\}_{a\in[K]}$ for each candidate actions for
each round, but cannot collect feedback (reward)
$r^{{\mathcal{T}}}_{i,\widehat{a}_{i}}$ for any action in the target domain.
The goal in our cross-domain contextual bandits is to learn a policy of
choosing actions $\widehat{a}_{i}$ in the target domain to minimize the
target-domain zero-shot regret for $N$ (hypothetical) future rounds:

$\displaystyle
R_{{\mathcal{T}}}=\sum\nolimits_{i=1}^{N}r^{{\mathcal{T}}}_{i,a_{i}^{*}}-\sum\nolimits_{i=1}^{N}r^{{\mathcal{T}}}_{i,\widehat{a}_{i}}.$
(2)

Difference between Eqn. 1 and Eqn. 2. In the typical setting, Eqn. 1 uses
different updated policies for each round; this is also true for the source
domain. In contrast, the target regret in Eqn. 2 use the same fixed policy
obtained from the source domain for all $N$ (hypothetical) rounds because one
cannot collect feedback from the target domain. See the difference between
Definition 3.4 and Definition 3.5 below for a more formal comparison.

###  3.3 Formal Definitions of Error

######  Definition 3.1 (Labeling Function and Hypothesis).

We define the labeling function $f_{\mathcal{D}}$ and the hypothesis $h$ for
domain ${\mathcal{D}}$ as follows:

$\displaystyle f_{\mathcal{D}}({\bf x}_{i,a}^{\mathcal{D}})$
$\displaystyle={r}({\bf
x}_{i,a}^{\mathcal{D}})=\langle\theta_{\mathcal{D}}^{*},\phi_{\mathcal{D}}^{*}({\bf
x}_{i,a}^{\mathcal{D}})\rangle+\epsilon_{i}$ $\displaystyle h({\bf
x}_{i,a}^{\mathcal{D}})$ $\displaystyle=\widehat{{r}}({\bf
x}_{i,a}^{\mathcal{D}})=\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a}^{\mathcal{D}})\rangle+\epsilon_{i}$

where $\theta_{\mathcal{D}}^{*}$ is the optimal predictor for domain
${\mathcal{D}}$, $\widehat{\theta}$ denotes the estimated predictor, and
$\epsilon_{i}$ is the random noise.

Next, we analyze how well our hypothesis $h$ estimates the labeling function
$f$ (i.e., ground-truth hypothesis). Definition 3.2 below quantifies the
closeness between two hypotheses by calculating the absolute difference in
their estimated rewards.

######  Definition 3.2 (Estimated Error between Two Hypotheses).

Assuming all contexts ${\bf x}_{i,\widehat{a}_{i}}^{\mathcal{D}}$ are from
domain $\mathcal{D}$, the error between two hypotheses
$h_{1},h_{2}\in\mathcal{H}$ on domain ${\mathcal{D}}$ given selected actions
$\\{\widehat{a}_{i}\\}_{i\in[N]}\in[K]$ is

$\displaystyle\epsilon_{\mathcal{D}}(h_{1},h_{2})$
$\displaystyle=\sum\nolimits_{i=1}^{N}\Bigg{(}\big{|}h_{1}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{D}})-h_{2}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{D}})\big{|}\Bigg{)}=\sum\nolimits_{i=1}^{N}\Bigg{(}\Big{|}\langle\widehat{\theta}_{1},\widehat{\phi}_{1}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{D}})\rangle-\langle\widehat{\theta}_{2},\widehat{\phi}_{2}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{D}})\rangle\Big{|}\Bigg{)}.$ (3)

Note that the domain ${\mathcal{D}}$ above can be the source domain
${\mathcal{S}}$ or the target domain ${\mathcal{T}}$. We then define the error
of our estimated hypothesis in these domains.

######  Definition 3.3 (Source- and Target-Domain Error).

With $N$ samples from the source domain $\mathcal{S}$, and $f_{S}$ denoting
the labeling function for ${\mathcal{S}}$, the source-domain error is then

$\displaystyle\epsilon_{\mathcal{S}}(f_{\mathcal{S}},h)$
$\displaystyle=\sum\nolimits_{i=1}^{N}\Bigg{(}\big{|}f_{S}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})-h({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\big{|}\Bigg{)}=\sum\nolimits_{i=1}^{N}\Bigg{(}\Big{|}\langle\theta_{\mathcal{S}}^{*},\phi_{\mathcal{S}}^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\Bigg{)},$

where ${\bf x}_{i,\cdot}^{\mathcal{S}}$ comes from $\mathcal{S}$. Furthermore,
$\widehat{a}_{i}=\mbox{arg}\max_{a}h({\bf x}_{i,a}^{\mathcal{S}})$ and
$a_{i}^{*}=\mbox{arg}\max_{a}f_{S}({\bf x}_{i,a}^{\mathcal{S}})$. For
simplicity, we shorten the notation
$\epsilon_{\mathcal{S}}(f_{\mathcal{S}},h)$ to $\epsilon_{\mathcal{S}}(h)$ and
similarly use $\epsilon_{\mathcal{T}}(h)$ for domain $\mathcal{T}$. Assuming
${\bf x}_{i,\cdot}^{\mathcal{T}}$ comes from $\mathcal{\mathcal{T}}$, the
estimated error for the target domain is then:

$\displaystyle\epsilon_{\mathcal{T}}(f_{\mathcal{T}},h)$
$\displaystyle=\sum\nolimits_{i=1}^{N}\Bigg{(}\big{|}f_{\mathcal{T}}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})-h({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\big{|}\Bigg{)}=\sum\nolimits_{i=1}^{N}\Bigg{(}\Big{|}\langle\theta_{\mathcal{T}}^{*},\phi_{\mathcal{T}}^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\Bigg{)}.$

###  3.4 Source Regret and Target Regret

Below define the regret for the source and target domains.

######  Definition 3.4 (Source Regret).

Assuming ${\bf x}_{i,\cdot}^{\mathcal{S}}$ comes from domain $\mathcal{S}$,
the source regret (i.e., the regret in the source domain) is

$\displaystyle\mathit{R}_{\mathcal{S}}$
$\displaystyle=\sum\nolimits_{i=1}^{N}\Bigg{(}f_{\mathcal{S}}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})-f_{\mathcal{S}}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\Bigg{)}=\sum\nolimits_{i=1}^{N}\Bigg{(}\langle\theta_{S}^{*},\phi_{\mathcal{S}}^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle-\langle\theta_{\mathcal{S}}^{*},\phi_{S}^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Bigg{)}.$ (4)

The goal in our cross-domain contextual bandits is to learn a policy of
choosing actions $\widehat{a}_{i}$ in the high-cost target domain (e.g., human
experiments) by collecting feedback only in the source domain (e.g., mouse
experiments). Formally, we would like to minimize the target regret as defined
below.

######  Definition 3.5 (Target Regret and Problem Formulation).

Denoting the estimated hypothesis as
$\widehat{h}=\left\\{\widehat{\phi},\widehat{\theta}\right\\}$, the target
regret we aim to minimize is defined as

$\displaystyle\mathit{R}_{\mathcal{T}}$
$\displaystyle=\sum\nolimits_{i=1}^{N}\Bigg{(}f_{\mathcal{T}}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})-f_{\mathcal{T}}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\Bigg{)}$ $\displaystyle\mbox{s.t.
}\widehat{a}_{i}$ $\displaystyle=\mathop{\rm argmax}_{a}\widehat{h}({\bf
x}_{i,a}^{\mathcal{T}})+\alpha\|\widehat{\phi}({\bf
x}_{i,a}^{\mathcal{T}})\|_{[A^{\mathcal{S}}]^{-1}},\quad\widehat{h}=\mathop{\rm
argmin}_{h}\epsilon_{\mathcal{S}}(h),$

where $A^{\mathcal{S}}=\gamma{\bf
I}+\sum\nolimits_{i=1}^{N}[\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})][\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})]^{T}$ denotes the context matrix
accumulated by the selected context features in the source domain.

###  3.5 Cross-Domain Error Bound for Regression

Prior to introducing our final regret bound, it is necessary to define an
additional component. A fundamental challenge in general domain adaptation
problems is to manage the divergence between source and target domains.
Unfortunately, previous domain adaptation theory only covers _classification_
tasks [36, 19]. In contrast, the problem of contextual bandits is essentially
a reward _regression_ problem. To address this challenge, we introduce the
following new definition to bound the error between the source and target
domains.

######  Definition 3.6 ($\mathcal{H}\Delta\mathcal{H}$ Hypothesis Space for
Regression).

For a hypothesis space $\mathcal{H}$, the symmetric difference hypothesis
space $\mathcal{H}\Delta\mathcal{H}$ is the set of hypotheses s.t.

$\displaystyle g\in\mathcal{H}\Delta\mathcal{H}\quad\iff\quad g(x)=|h({\bf
x})-h^{\prime}({\bf x})|.$

We then can further define the Divergence for $\mathcal{H}\Delta\mathcal{H}$
Hypothesis Space:

$\displaystyle\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})$
$\displaystyle=2\enspace\sup_{h,h^{\prime}\in\mathcal{H}}|\mathbb{E}_{x\sim\mathcal{S}}[|h(x)-h^{\prime}(x)|]-\mathbb{E}_{x\sim\mathcal{T}}[|h(x)-h^{\prime}(x)|]|$

######  Definition 3.7 (Optimal Hypothesis).

The optimal hypothesis, denoted as $h^{*}$, can balance the estimated error
for both source and target domain. Formally,

$\displaystyle h^{*}$
$\displaystyle=\mbox{arg}\min_{h\in\mathcal{H}}\enspace\epsilon_{\mathcal{S}}(h)+\epsilon_{\mathcal{T}}(h),$

and we define the minimum estimated error for the optimal hypothesis $h^{*}$
as

$\displaystyle\psi$
$\displaystyle=\epsilon_{\mathcal{S}}(h^{*})+\epsilon_{\mathcal{T}}(h^{*}).$

Algorithm 1 DABand Training Algorithm

1: Input: regularization parameter $\gamma>0$, number of total steps $N$,
episode length $H$, exploration parameters $\alpha$.

2: Output: parameters of the model:
$\widehat{\phi}_{N},\widehat{\theta}_{N},A_{N},b_{N}$.

3: Initialization: $A_{0}=\gamma{\bf I},b_{0}={\bf 0}$, and for
$\widehat{\theta}_{0}$ and $\widehat{\phi}_{0}$ are initialized following
[11].

4: for $i=1,...,N$ do

5: Obtain $\left\\{{\bf x}_{i,a}^{\mathcal{S}}\right\\}_{a\in[K]}$ and
$\left\\{{\bf x}_{i,a}^{\mathcal{T}}\right\\}_{a\in[K]}$ from the source and
the target domain, respectively.

6: Choose an action $\widehat{a}_{i}=\mathop{\rm
argmax}_{a\in[K]}\left[\widehat{\phi}_{i-1}({\bf
x}_{i,a}^{\mathcal{S}})\right]\widehat{\theta}_{i-1}+\alpha\|\left[\widehat{\phi}_{i-1}({\bf
x}_{i,a}^{\mathcal{S}})\right]\|_{A_{i-1}}$.

7: Get the reward $r_{i}=\mathbf{r}({\bf x}_{i,\widehat{a}_{i}})$ based on the
selected action $\widehat{a}_{i}$.

8: Update bandit parameters:

9: $\begin{cases}A_{i}=A_{i-1}+\left[\widehat{\phi}_{i-1}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\right]\left[\widehat{\phi}_{i-1}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\right]^{T},\\\
b_{i}=b_{i-1}+r_{i}\left[\widehat{\phi}_{i-1}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\right],\\\
\widehat{\theta}_{i}=A_{i}^{-1}b_{i}\end{cases}$

10: if $mod(i,H)=0$ then

11: for $j=1,...,H$ do

12: Calculate $\mathcal{L}^{DABand}$ in Eqn. 10.

13: Update encoder $\widehat{\phi}_{i}$ and discriminator $g$ by back-
propagation to solve the minimax optimization in Eqn. 9.

14: end for

15: else

16: $\widehat{\phi}_{i}=\widehat{\phi}_{i-1}$

17: end if

18: end for

19: Output: $\widehat{\phi}_{N},\widehat{\theta}_{N},A_{N},b_{N}$.

###  3.6 Final Regret Bound

With all the definitions of source/target regret in Definition 3.4 and
Definition 3.5, we can then bound the target regret using Theorem 3.1 below.

######  Theorem 3.1 (Target Regret Bound).

Denoting the contexts from the source domain ${\mathcal{S}}$ as $\\{{\bf
x}_{t,a}^{\mathcal{S}}\\}_{i\in[N],a\in[K]}$, the associated ground-truth
action as $\\{a_{i}^{*}\\}_{i=1}^{N}$, and the contexts from the target domain
${\mathcal{T}}$ as $\\{{\bf x}_{t,a}^{\mathcal{T}}\\}_{i\in[N],a\in[K]}$, the
upper bound for our target regret $R_{{\mathcal{T}}}$ is

$\displaystyle\mathit{R}_{\mathcal{T}}$
$\displaystyle\triangleq\sum_{i=1}^{N}\Bigg{(}\Big{|}\langle\theta_{\mathcal{T}}^{*},\phi_{\mathcal{T}}^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\theta_{\mathcal{T}}^{*},\phi_{\mathcal{T}}^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\Bigg{)}$
$\displaystyle\leq{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\underbrace{\mathit{R}_{\mathcal{S}}}_{Source~{}Regret}}+{\color[rgb]{1,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0.5}\pgfsys@color@cmyk@stroke{0}{1}{0.50}{0}\pgfsys@color@cmyk@fill{0}{1}{0.50}{0}\underbrace{\epsilon_{\mathcal{S}}(h)}_{Regression~{}Error}}+{\color[rgb]{0,0.5,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,1}\pgfsys@color@cmyk@stroke{1}{0.50}{0}{0}\pgfsys@color@cmyk@fill{1}{0.50}{0}{0}\underbrace{N\cdot\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})}_{Data~{}Divergence}}+{\color[rgb]{1,0.58,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.58,0}\pgfsys@color@cmyk@stroke{0}{0.42}{1}{0}\pgfsys@color@cmyk@fill{0}{0.42}{1}{0}\underbrace{\sum_{i=1}^{N}\Bigg{(}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\Bigg{)}}_{Predicted~{}Reward}}+{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color@cmyk@fill{0.85}{0}{0.33}{0}\underbrace{\psi+C}_{Constant}},$
(5)

where $\mathit{R}_{\mathcal{S}}$, $\epsilon_{\mathcal{S}}(h)$, and
$\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}$ are defined in previous sections.
$\psi$ and $C$ are constants which are independent of the problems.

Here we provide several observations (for more analysis, please refer to the
Appendix):

  * (1)

Since $R_{\mathcal{S}}$ is sub-linear w.r.t. the number of samples in the
source domain, so is $R_{\mathcal{T}}$.

  * (2)

Theorem 3.1 bounds the target regret using the source regret, enabling the
exploration of the target domain by only collecting feedback (reward) from the
source domain.

  * (3)

Typical generalization bounds in DA naively minimize the source regret
$R_{{\mathcal{S}}}$ while aligning source and target data in the latent space
(i.e., minimizing $\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}$). This is not
sufficient, as we need two additional terms, i.e., the regression error
$\epsilon_{\mathcal{S}}(h)$ and the predicted reward
$\sum\nolimits_{i=1}^{N}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}$, as regularization terms.

  * (4)

Minimizing the regression error $\epsilon_{\mathcal{S}}(h)$ encourages
accurate prediction of source rewards.

  * (5)

Minimizing the predicted reward
$\sum\nolimits_{i=1}^{N}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}$ regularizes the model to
avoid overestimating rewards.

Note that Theorem 3.1 is nontrivial. While it does resemble the generalization
bound in domain adaptation, there are key differences. As mentioned in
Observation (3) above, our target regret bound includes two additional crucial
terms not found in domain adaptation. Specifically:

  * •

Regression Error in the Source Domain.
$\sum\nolimits_{i=1}^{N}\Bigg{(}\Big{|}\langle\theta_{\mathcal{S}}^{*},\phi_{\mathcal{S}}^{*}(x_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle-\langle\widehat{\theta},\widehat{\phi}(x_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\Bigg{)}$
(i.e., $\epsilon_{\mathcal{S}}(h)$ in Theorem 3.1), which defines the
difference between the true reward from selecting action $\widehat{a}_{i}$ and
the estimated reward for this action.

  * •

Predicted Reward.
$\sum\nolimits_{i=1}^{N}\Bigg{(}\Big{|}\langle\widehat{\theta},\widehat{\phi}(x_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\Bigg{)}$,
which serves as a regularization term to regularize the model to avoid
overestimating rewards.

The results of the ablation study in Table 4 in Sec. 5 highlight the
significance of these two terms. Details for more analysis are in Appendix
F.3.1.

##  4 Method

With Theorem 3.1, we can then design our DABand algorithm to obtain optimal
target regret. We discuss how to translate each term in Eqn. 5 to a
differential loss term in Sec. 4.1 and then put them together in Sec. 4.2.

###  4.1 From Theory to Practice: Translating the Bound in Eqn. 5 to
Differentiable Loss Terms

Source Regret. Inspired by Neural-LinUCB [11], we use LinUCB [1] to update
$\widehat{\theta}$ and the following empirical loss function when updating the
encoder parameters $\widehat{\phi}$ by back-propagation in round $i$:

$\displaystyle\mathcal{L}_{i}^{\mathit{R}_{\mathcal{S}}}=\sum\nolimits_{a=1}^{K}\left(\widehat{\theta}^{T}\widehat{\phi}({\bf
x}_{i,a})-{r}({\bf x}_{i,a})\right)^{2},$ (6)

where $\theta$ is the contextual bandit parameter, and $\widehat{\phi}$ is the
encoder shared by the source and target domains, i.e., we set
$\widehat{\phi}_{{\mathcal{S}}}=\widehat{\phi}_{{\mathcal{T}}}$ during
training.

Insights. From Eqn. 6, a fundamental difference between classification
problems and bandit problems becomes apparent. In classification tasks, both
the ground-truth label and the estimated label are accessible. However, in
bandit problems, we only know the estimated label and reward. If the estimated
rewards align with our estimated label’s correctness, it suggests knowledge of
the ground-truth label for that feature. If not, we can only deduce that the
estimated label is inaccurate, without identifying the correct label among the
other candidates. This uncertainty significantly amplifies the complexity of
contextual bandit problems.

Regression Error. We use $L_{1}$ loss to optimize the regression error,
defined as the difference between the true reward from selecting action
$\widehat{a}_{i}$ and the estimated reward for this action (see Definition 3.3
for a detailed explanation of this regression error). Minimizing the
_regression error_ term directly _encourages accurate prediction of source
rewards_ using $L_{1}$ loss. Specifically, we use

$\displaystyle\mathcal{L}_{i}^{\epsilon_{\mathcal{S}}(h)}=\left|\langle\theta_{\mathcal{S}}^{*},\phi_{\mathcal{S}}^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\right|,$ (7)

where $\langle\theta_{\mathcal{S}}^{*},\phi_{\mathcal{S}}^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle$ is the reward received by the
agent in the source domain. Minimizing the regression error term above
directly encourages accurate prediction of source rewards.

Data Divergence. The data divergence term in Eqn. 5 leads to following loss
term:

$\displaystyle\mathcal{L}^{div}=\max_{g}N\cdot(\mathbb{E}^{\mathcal{S}}[\mathcal{L}_{D}(g(\widehat{\phi}({\bf
x})),0)]+\mathbb{E}^{\mathcal{T}}[\mathcal{L}_{D}(g(\widehat{\phi}({\bf
x})),1)]),$

where $\mathbb{E}^{\mathcal{S}}$ and $\mathbb{E}^{\mathcal{T}}$ denote
expectations over the data distributions of $({\bf x},a)$ in the source and
target domains, respectively. $g$ is a discriminator that classifies whether
${\bf x}$ is from the source domain or the target domain. $\mathcal{L}_{D}$ is
the binary classification accuracy, where labels $0$ and $1$ indicate the
source and target domains, respectively. In practice, we use the cross-entropy
loss as a differentiable surrogate loss. As in [28], solving the minimax
optimization
$\min\nolimits_{\widehat{\phi}}\max\nolimits_{g}{\mathcal{L}}^{div}$ is
equivalent to aligning source- and target-domain data distributions in the
latent (encoding) space induced by the encoder $\widehat{\phi}$.

Table 1: Accuracy on the target domain for the DIGIT dataset. Note that in
this zero-shot target regret setting, the accuracy
$ACC=1-\tfrac{1}{N}R_{{\mathcal{T}}}$, where $R_{{\mathcal{T}}}$ is the target
regret.

Metrics |  Acc Per Class $\uparrow$ |  Acc $\uparrow$
---|---|---
Test Accuracy | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Average
LinUCB [1] |  0.3667$\pm$0.03 |  0.4045$\pm$0.02 |  0.5102$\pm$0.03 |  0.3811$\pm$0.01 |  0.3157$\pm$0.04 |  0.3445$\pm$0.01 |  0.4229$\pm$0.03 |  0.4595$\pm$0.03 |  0.3489$\pm$0.02 |  0.2449$\pm$0.01 |  0.3808$\pm$0.02
LinUCB-P [1] |  0.3645$\pm$0.02 |  0.6398$\pm$0.04 |  0.3151$\pm$0.02 |  0.2709$\pm$0.03 |  0.2258$\pm$0.01 |  0.1995$\pm$0.02 |  0.1752$\pm$0.01 |  0.3786$\pm$0.04 |  0.1273$\pm$0.02 |  0.2992$\pm$0.03 |  0.3060$\pm$0.02
NLinUCB [11] |  0.3781$\pm$0.04 |  0.3228$\pm$0.03 |  0.3569$\pm$0.03 |  0.3381$\pm$0.04 |  0.3663$\pm$0.04 |  0.4312$\pm$0.05 |  0.4766$\pm$0.05 |  0.4004$\pm$0.05 |  0.4034$\pm$0.02 |  0.3613$\pm$0.03 |  0.3816$\pm$0.04
NLinUCB-P [11] |  0.8588$\pm$0.03 |  0.2224$\pm$0.02 |  0.3880$\pm$0.03 |  0.3029$\pm$0.02 |  0.2978$\pm$0.03 |  0.0000$\pm$0.01 |  0.1869$\pm$0.02 |  0.2243$\pm$0.01 |  0.2148$\pm$0.01 |  0.0000$\pm$0.00 |  0.2706$\pm$0.02
DABand (Ours) |  0.6879$\pm$0.10 |  0.6654$\pm$0.03 |  0.6056$\pm$0.01 |  0.5694$\pm$0.05 |  0.5978$\pm$0.05 |  0.5428$\pm$0.03 |  0.6086$\pm$0.02 |  0.5700$\pm$0.01 |  0.6261$\pm$0.04 |  0.5016$\pm$0.02 |  0.5984$\pm$0.02
Ours vs. NLinUCB | +0.3098 | +0.3426 | +0.2487 | +0.2313 | +0.2315 | +0.1116 | +0.1320 | +0.1696 | +0.2227 | +0.1403 | +0.2168

Table 2: Accuracy on the target domain for the VisDA17 dataset. Note that in
this zero-shot target regret setting, the accuracy
$ACC=1-\tfrac{1}{N}R_{{\mathcal{T}}}$, where $R_{{\mathcal{T}}}$ is the target
regret.

Metrics |  Acc Per Class $\uparrow$ |  Acc $\uparrow$
---|---|---
Test Accuracy | aeroplane | bicycle | bus | car | horse | knife | motorcycle | person | plant | skateboard | train | truck | Average
LinUCB [1] | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A
LinUCB-P [1] |  0.0510$\pm$0.02 |  0.0190$\pm$0.00 |  0.1360$\pm$0.05 |  0.0440$\pm$0.02 |  0.0390$\pm$0.01 |  0.5580$\pm$0.06 |  0.0410$\pm$0.02 |  0.2050$\pm$0.05 |  0.0850$\pm$0.04 |  0.0920$\pm$0.13 |  0.0580$\pm$0.02 |  0.0460$\pm$0.12 |  0.1145$\pm$0.06
NLinUCB [11] |  0.2870$\pm$0.03 |  0.0220$\pm$0.02 |  0.0000$\pm$0.00 |  0.1250$\pm$0.02 |  0.0000$\pm$0.00 |  0.0130$\pm$0.02 |  0.0470$\pm$0.02 |  0.0000$\pm$0.00 |  0.0460$\pm$0.02 |  0.0050$\pm$0.00 |  0.6550$\pm$0.04 |  0.0000$\pm$0.00 |  0.1001$\pm$0.02
NLinUCB-P [11] |  0.0060$\pm$0.01 |  0.0020$\pm$0.01 |  0.9222$\pm$0.02 |  0.0010$\pm$0.00 |  0.0080$\pm$0.01 |  0.0990$\pm$0.03 |  0.0030$\pm$0.00 |  0.0020$\pm$0.00 |  0.0180$\pm$0.02 |  0.0420$\pm$0.01 |  0.0000$\pm$0.00 |  0.0150$\pm$0.01 |  0.0932$\pm$0.01
DABand (Ours) |  0.5500$\pm$0.02 |  0.3560$\pm$0.04 |  0.4500$\pm$0.02 |  0.3850$\pm$0.01 |  0.5590$\pm$0.04 |  0.2650$\pm$0.03 |  0.6480$\pm$0.03 |  0.2410$\pm$0.03 |  0.4880$\pm$0.04 |  0.4060$\pm$0.02 |  0.7680$\pm$0.05 |  0.1970$\pm$0.02 |  0.4428$\pm$0.03
Ours vs. NLinUCB | +0.2630 | +0.3340 | +0.4500 | +0.2600 | +0.5590 | +0.2520 | +0.6010 | +0.2410 | +0.4420 | +0.4010 | +0.1130 | +0.1970 | +0.3427

Table 3: Accuracy on the target domain for the S2RDA49 dataset. Note that in
this zero-shot target regret setting, the accuracy
$ACC=1-\tfrac{1}{N}R_{{\mathcal{T}}}$, where $R_{{\mathcal{T}}}$ is the target
regret.

Metrics |  Acc Per Class $\uparrow$ |  Acc $\uparrow$
---|---|---
Test Accuracy | aeroplane | bicycle | bus | car | knife | motorcycle | plant | skateboard | train | truck | Average
LinUCB [1] | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A | N/A
LinUCB-P [1] |  0.1430$\pm$0.02 |  0.2600$\pm$0.03 |  0.0810$\pm$0.01 |  0.0240$\pm$0.01 |  0.1070$\pm$0.02 |  0.0570$\pm$0.01 |  0.1060$\pm$0.01 |  0.0390$\pm$0.01 |  0.0960$\pm$0.02 |  0.1260$\pm$0.03 |  0.1039$\pm$0.02
NLinUCB [11] |  0.0350$\pm$0.00 |  0.1210$\pm$0.02 |  0.0510$\pm$0.01 |  0.0870$\pm$0.02 |  0.0270$\pm$0.00 |  0.0240$\pm$0.01 |  0.2720$\pm$0.04 |  0.0090$\pm$0.00 |  0.1730$\pm$0.02 |  0.0309$\pm$0.01 |  0.1108$\pm$0.02
NLinUCB-P [11] |  0.0000$\pm$0.00 |  0.0000$\pm$0.00 |  0.0000$\pm$0.00 |  0.2990$\pm$0.03 |  0.7000$\pm$0.02 |  0.0000$\pm$0.00 |  0.0000$\pm$0.00 |  0.0000$\pm$0.00 |  0.0000$\pm$0.00 |  0.1160$\pm$0.01 |  0.1115$\pm$0.01
DABand (Ours) |  0.5470$\pm$0.03 |  0.6410$\pm$0.03 |  0.5840$\pm$0.03 |  0.2140$\pm$0.01 |  0.0460$\pm$0.01 |  0.7570$\pm$0.04 |  0.5680$\pm$0.04 |  0.1340$\pm$0.02 |  0.1110$\pm$0.02 |  0.3120$\pm$0.02 |  0.3914$\pm$0.03
Ours vs. NLinUCB | +0.5120 | +0.5200 | +0.5330 | +0.1270 | +0.0190 | +0.7330 | +0.2960 | +0.1250 | -0.0620 | +0.2811 | +0.2806

Predicted Reward. The predicted reward term in Eqn. 5, i.e.,
$\sum\nolimits_{i=1}^{N}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}$, can be translated to the
loss term $\sum\nolimits_{i=1}^{N}\mathcal{L}_{i}^{reg}$, where for each round
$i$ we have

$\displaystyle\mathcal{L}_{i}^{reg}=\left|\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}\rangle\right|.$ (8)

Minimizing the predicted reward $\mathcal{L}_{i}^{reg}$ regularizes the model
to avoid overestimating rewards.

Constant Term. In Eqn. 5, $\psi+C$ is the constant term, where $\psi$ is
defined in Definition 3.7, and $C$ is a positive constant (see the Appendix
for more details).

###  4.2 Putting Everything Together: DABand Training Algorithm

Putting all non-constant loss terms above together, we have the final minimax
optimization problem

$\displaystyle\min\nolimits_{\widehat{\phi}}\max\nolimits_{g}\mathcal{L}^{DABand},$
(9)

where the value function (objective function):

$\displaystyle{\mathcal{L}}^{DABand}=\sum\nolimits_{i=1}^{N}(\mathcal{L}_{i}^{\mathit{R}_{\mathcal{S}}}+\mathcal{L}_{i}^{\epsilon_{\mathcal{S}}(h)}+\mathcal{L}_{i}^{reg})+\lambda\cdot\mathcal{L}_{i}^{div}.$
(10)

Note that we need to alternate between updating $\widehat{\theta}$ using
LinUCB [1] and updating the encoder $\widehat{\phi}$ with the discriminator
$g$ in Eqn. 9.

Formally, our algorithm operates as follows: In each iteration, we access the
context in the original feature space (i.e., $\mathbb{R}^{d}$) for each action
from both source and target domains, denoted as
$\left\\{x_{i,a}^{\mathcal{S}}\right\\}_{a\in[K]}$ and
$\left\\{x_{i,a}^{\mathcal{T}}\right\\}_{a\in[K]}$ respectively. Subsequently,
we compute the latent representation using the encoder $\phi(\cdot)$ and
select the action $\widehat{a}_{i}$ for iteration $i$ based on the LinUCB
selection rule. The bandit parameters (i.e., $\theta,A,b$) are updated in each
iteration. The weights in $\phi$ are updated every episode of length $H$
(i.e., a batch with $H$ past iterations) using our objective function in Eqn.
9, following the same rule as in Neural-LinUCB [11]. Alg. 1 summarizes our
algorithm.

##  5 Experiments

In this section, we compare DABand with existing methods on real-world
datasets.

Datasets. To demonstrate the effectiveness of our DABand, We evaluate our
methods in terms of prediction accuracy and zero-shot target regret on three
datasets, i.e., DIGIT [37], VisDA17 [38], and S2RDA49 [39]. See details for
each dataset in Appendix B.

Baselines. We compare our DABand with both classic and state-of-the-art
contextual bandit algorithms, including LinUCB [1], LinUCB with principle
component analysis (PCA) pre-processing (i.e., LinUCB-P), Neural-LinUCB [11]
(NLinUCB), and Neural-LinUCB variant that incorporates PCA (i.e., NLinUCB-P).
Details for each baselines and discussion are in Appendix C. Note that domain
adaptation baselines are not applicable to our setting because it only works
in offline settings and assumes complete observability of labels in the source
domain (see Appendix C for details).

Zero-Shot Target Regret (Accuracy). We evaluate different methods on the zero-
shot target regret setting in Definition 3.5, where all methods can only
collect feedback from the source domain, but not the target domain. In this
setting, accuracy is equal to $1$ minus the average target regret, i.e.,
$ACC=1-\tfrac{1}{N}R_{{\mathcal{T}}}$, where $R_{{\mathcal{T}}}$ is defined in
Eqn. 2 and Definition 3.5. Therefore higher accuracy indicates lower target
regret and better performance.

We report the per-class accuracy and average accuracy of different methods in
Table 1, Table 2 and Table 3 for DIGIT, VisDA17 and S2RDA49, respectively. Our
DABand demonstrates favorable performance against NLinUCB, a leading
contextual bandit algorithm with representation learning. Despite NLinUCB’s
superior representation learning capabilities through neural networks (NN)
over LinUCB – yielding impressive performance in single-domain applications –
its efficacy in cross-domain tasks is heavily contingent on the disparity
between the source and target domains. Typically, the strengths of NN, which
include enhanced representation learning (feature extraction), may
inadvertently amplify this domain divergence, potentially leading to
overfitting on the source domain. Conversely, our DABand algorithm not only
improves accuracy but also adeptly addresses the challenges posed by domain
divergence. Note that LinUCB encounters an out-of-memory issue due to the
high-dimensionality of the data in VisDA17 and S2RDA49, marked as “N/A” in
Table 2 and Table 3, respectively.

Figure 1: The cumulative regrets of different methods for 1,920 rounds on
DIGIT (left), VisDA17 (middle), and S2RDA49 (right). Results are averaged over
5 runs. LinUCB is not reported for VisDA17 and S2RDA49 due to out-of-memory
issues.

Continued Training in Target Domains and Cumulative Regret. Besides zero-shot
target regret, we also evaluate how different methods perform when one
continues their training in the high-cost target domain and starts to collect
feedback (reward) after the model is trained in the source domain. A good
cross-domain bandit model can provide a head-start in this setting, therefore
enjoying significantly lower cumulative regret in the target domain and saving
substantial cost in collecting feedback in the high-cost target domain.

Fig. 1 shows the cumulative regrets of different methods on DIGIT, VisDA17 and
S2RDA49, respectively. We show results averaged over five runs with different
random seeds. Our DABand consistently surpasses all baselines for all rounds
in terms of both cumulative regrets and their increase rates, demonstrating
DABand’s potential to significantly reduce the cost in high-cost target
domains.

Table 4: Results of the ablation study in terms of accuracy (higher is
better). Note that the accuracy $ACC=1-\tfrac{1}{N}R_{{\mathcal{T}}}$, where
$R_{{\mathcal{T}}}$ is the target regret. “R” and “P” is short for “Regression
Error” and “Predicted Reward”, respectively.

Datasets | w/o R $\&$ P | w/o R | w/o P | DABand (Full)
---|---|---|---|---
DIGIT | 0.5676 | 0.5716 | 0.5768 | 0.5984
VisDA17 | 0.4088 | 0.4238 | 0.4304 | 0.4642
S2RDA49 | 0.3691 | 0.3704 | 0.3719 | 0.3914

Ablation Study. To verify the effectiveness of each term in our DABand’s
regret bound (Theorem 3.1, we report the accuracy of our proposed DABand after
removing the Regression Error term and/or the Predicted Reward term (during
training) in Table 4 for DIGIT, VisDA17 and S2RDA49. Results on all datasets
show that removing either term will lead to performance drop. For example, in
VisDA17, our full DABand achieves accuracy of $0.4642$; the accuracy drops to
$0.4238$ after removing the Regression Error (R) term, and further drops to
$0.4088$ after removing the Predicted Reward (P) term. These results verify
the effectiveness of these two terms in our DABand.

##  6 Conclusion

In this paper, we introduce a novel domain adaptive neural contextual bandit
algorithm, DABand, which adeptly combines effective exploration with
representation alignment, utilizing unlabeled data from both source and target
domains. Our theoretical analysis demonstrates that DABand can attain a sub-
linear regret bound within the target domain. This marks the first regret
analysis for domain adaptation in contextual bandit problems incorporating
deep representation, shallow exploration, and adversarial alignment. We show
that all these elements are instrumental in the domain adaptive bandit setting
on real-world datasets. Moving forward, interesting future research could be
to uncover more innovative techniques for aligning the source and target
domains (mentioned in Appendix E), particularly within the constraints of: (1)
bandit settings, as opposed to classification settings, and (2) the high-
dimensional and dense nature of the target domain, contrasted with the sparse
and simplistic nature of the source domain.

## References

  * Li et al. [2010] Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _WWW_ , pages 661–670, 2010.
  * Yue and Guestrin [2011] Yisong Yue and Carlos Guestrin.  Linear submodular bandits and their application to diversified retrieval.  In _NIPS_ , pages 2483–2491, 2011.
  * Agarwal et al. [2014] Alekh Agarwal, Daniel J. Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E. Schapire.  Taming the monster: A fast and simple algorithm for contextual bandits.  In _ICML_ , pages 1638–1646, 2014.
  * Li et al. [2016] Shuai Li, Alexandros Karatzoglou, and Claudio Gentile.  Collaborative filtering bandits.  In _SIGIR_ , pages 539–548, 2016.
  * Kveton et al. [2017] Branislav Kveton, Csaba Szepesvári, Anup Rao, Zheng Wen, Yasin Abbasi-Yadkori, and S. Muthukrishnan.  Stochastic low-rank bandits.  _CoRR_ , abs/1712.04644, 2017.
  * Foster et al. [2018] Dylan J. Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert E. Schapire.  Practical contextual bandits with regression oracles.  In _ICML_ , pages 1534–1543, 2018.
  * Korda et al. [2016] Nathan Korda, Balazs Szorenyi, and Shuai Li.  Distributed clustering of linear bandits in peer to peer networks.  In _ICML_ , pages 1301–1309, 2016.
  * Mahadik et al. [2020] Kanak Mahadik, Qingyun Wu, Shuai Li, and Amit Sabne.  Fast distributed bandits for online recommendation systems.  In _SC_ , pages 1–13, 2020.
  * Zhou et al. [2019] Dongruo Zhou, Lihong Li, and Quanquan Gu.  Neural contextual bandits with upper confidence bound-based exploration.  _arXiv preprint arXiv:1911.04462_ , 2019.
  * Wang et al. [2022] Hao Wang, Yifei Ma, Hao Ding, and Yuyang Wang.  Context uncertainty in contextual bandits with applications to recommender systems.  In _AAAI_ , 2022.
  * Xu et al. [2020] Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu.  Neural contextual bandits with deep representation and shallow exploration.  _arXiv preprint arXiv:2012.01780_ , 2020.
  * Auer [2002] Peter Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _JMLR_ , 3:397–422, 2002.
  * Chu et al. [2011] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandits with linear payoff functions.  In _AISTATS_ , pages 208–214, 2011.
  * Pan and Yang [2009] Sinno Jialin Pan and Qiang Yang.  A survey on transfer learning.  _TKDE_ , 22(10):1345–1359, 2009.
  * Pan et al. [2010] Sinno Jialin Pan, Ivor W Tsang, James T Kwok, and Qiang Yang.  Domain adaptation via transfer component analysis.  _TNN_ , 22(2):199–210, 2010.
  * Long et al. [2018] Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I. Jordan.  Conditional adversarial domain adaptation.  In _NIPS_ , pages 1647–1657, 2018.
  * Saito et al. [2018] Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada.  Maximum classifier discrepancy for unsupervised domain adaptation.  In _CVPR_ , pages 3723–3732, 2018.
  * Sankaranarayanan et al. [2018] Swami Sankaranarayanan, Yogesh Balaji, Carlos D. Castillo, and Rama Chellappa.  Generate to adapt: Aligning domains using generative adversarial networks.  In _CVPR_ , pages 8503–8512, 2018.
  * Zhang et al. [2019] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael I Jordan.  Bridging theory and algorithm for domain adaptation.  _arXiv preprint arXiv:1904.05801_ , 2019.
  * Peng et al. [2019] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang.  Moment matching for multi-source domain adaptation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1406–1415, 2019.
  * Chen et al. [2019] Ziliang Chen, Jingyu Zhuang, Xiaodan Liang, and Liang Lin.  Blending-target domain adaptation by adversarial meta-adaptation networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2248–2257, 2019.
  * Dai et al. [2019] Shuyang Dai, Kihyuk Sohn, Yi-Hsuan Tsai, Lawrence Carin, and Manmohan Chandraker.  Adaptation across extreme variations using unlabeled domain bridges.  _arXiv preprint arXiv:1906.02238_ , 2019.
  * Wang et al. [2020] Hao Wang, Hao He, and Dina Katabi.  Continuously indexed domain adaptation.  _arXiv preprint arXiv:2007.01807_ , 2020.
  * Nguyen-Meidine et al. [2021] Le Thanh Nguyen-Meidine, Atif Belal, Madhu Kiran, Jose Dolz, Louis-Antoine Blais-Morin, and Eric Granger.  Unsupervised multi-target domain adaptation through knowledge distillation.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 1339–1347, 2021.
  * Xu et al. [2023] Zihao Xu, Guangyuan Hao, Hao He, and Hao Wang.  Domain indexing variational bayes: Interpretable domain index for domain adaptation.  In _ICLR_ , 2023.
  * Tzeng et al. [2014] Eric Tzeng, Judy Hoffman, Ning Zhang, Kate Saenko, and Trevor Darrell.  Deep domain confusion: Maximizing for domain invariance.  _arXiv preprint arXiv:1412.3474_ , 2014.
  * Sun and Saenko [2016] Baochen Sun and Kate Saenko.  Deep CORAL: correlation alignment for deep domain adaptation.  In _ICCV workshop on Transferring and Adapting Source Knowledge in Computer Vision (TASK-CV)_ , pages 443–450, 2016.
  * Ganin et al. [2016a] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Franccois Laviolette, Mario Marchand, and Victor Lempitsky.  Domain-adversarial training of neural networks.  _JMLR_ , 17(1):2096–2030, 2016a.
  * Zhao et al. [2017] Mingmin Zhao, Shichao Yue, Dina Katabi, Tommi S. Jaakkola, and Matt T. Bianchi.  Learning sleep stages from radio signals: A conditional adversarial architecture.  In _ICML_ , pages 4100–4109, 2017.
  * Tzeng et al. [2017] Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell.  Adversarial discriminative domain adaptation.  In _CVPR_ , pages 7167–7176, 2017.
  * Kuroki et al. [2019] Seiichi Kuroki, Nontawat Charoenphakdee, Han Bao, Junya Honda, Issei Sato, and Masashi Sugiyama.  Unsupervised domain adaptation based on source-guided discrepancy.  In _AAAI_ , pages 4122–4129, 2019.
  * Goodfellow et al. [2014] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In _NIPS_ , pages 2672–2680, 2014.
  * Zhao et al. [2018] Han Zhao, Shanghang Zhang, Guanhang Wu, José M. F. Moura, João Paulo Costeira, and Geoffrey J. Gordon.  Adversarial multiple source domain adaptation.  In _NIPS_ , pages 8568–8579, 2018.
  * Zhao et al. [2019] Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J. Gordon.  On learning invariant representations for domain adaptation.  In _ICML_ , pages 7523–7532, 2019.
  * Guo et al. [2020] Han Guo, Ramakanth Pasunuru, and Mohit Bansal.  Multi-source domain adaptation for text classification via distancenet-bandits.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2020.
  * Ben-David et al. [2010] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  _Machine learning_ , 79:151–175, 2010.
  * Ganin et al. [2016b] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Franccois Laviolette, Mario March, and Victor Lempitsky.  Domain-adversarial training of neural networks.  _Journal of machine learning research_ , 17(59):1–35, 2016b.
  * Peng et al. [2017] Xingchao Peng, Ben Usman, Neela Kaushik, Judy Hoffman, Dequan Wang, and Kate Saenko.  Visda: The visual domain adaptation challenge.  _arXiv preprint arXiv:1710.06924_ , 2017.
  * Tang and Jia [2023] Hui Tang and Kui Jia.  A new benchmark: On the utility of synthetic data with blender for bare supervised learning and downstream domain adaptation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15954–15964, 2023.
  * Lin et al. [2014] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_ , pages 740–755. Springer, 2014.
  * Real et al. [2017] Esteban Real, Jonathon Shlens, Stefano Mazzocchi, Xin Pan, and Vincent Vanhoucke.  Youtube-boundingboxes: A large high-precision human-annotated data set for object detection in video.  In _proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5296–5305, 2017.
  * Chang et al. [2015] Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al.  Shapenet: An information-rich 3d model repository.  _arXiv preprint arXiv:1512.03012_ , 2015.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * Barbu et al. [2019] Andrei Barbu, David Mayo, Julian Alverio, William Luo, Christopher Wang, Dan Gutfreund, Josh Tenenbaum, and Boris Katz.  Objectnet: A large-scale bias-controlled dataset for pushing the limits of object recognition models.  _Advances in neural information processing systems_ , 32, 2019.
  * Prabhu et al. [2021] Viraj Prabhu, Shivam Khare, Deeksha Kartik, and Judy Hoffman.  Sentry: Selective entropy optimization via committee consistency for unsupervised domain adaptation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 8558–8567, 2021.

##  Appendix A Proofs

###  A.1 Proofs for Lemmas

######  Lemma A.1.

For any hypotheses $h,h^{\prime}\in\mathcal{H}$ and $a\in\mathcal{A}$ is
selected by either $h$ or $h^{\prime}$,

$\displaystyle|\epsilon_{\mathcal{S}}(h,h^{\prime})-\epsilon_{\mathcal{T}}(h,h^{\prime})|\leq\dfrac{N}{2}\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T}).$

###### Proof.

By definition of $\mathcal{H}\Delta\mathcal{H}$, we have

$\displaystyle\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})$
$\displaystyle=2\enspace\sup_{h,h^{\prime}\in\mathcal{H}}|\mathbb{E}_{{\bf
x}\sim\mathcal{S}}[|h({\bf x})-h^{\prime}({\bf x})|]-\mathbb{E}_{{\bf
x}\sim\mathcal{T}}[|h({\bf x})-h^{\prime}({\bf x})|]|$
$\displaystyle=\dfrac{2}{N}\enspace\sup_{h,h^{\prime}\in\mathcal{H}}\Big{|}N\cdot\mathbb{E}_{{\bf
x}\sim\mathcal{S}}[|h({\bf x})-h^{\prime}({\bf x})|]-N\cdot\mathbb{E}_{{\bf
x}\sim\mathcal{T}}[|h({\bf x})-h^{\prime}({\bf x})|]\Big{|}$
$\displaystyle=\dfrac{2}{N}\enspace\sup_{h,h^{\prime}\in\mathcal{H}}\Big{|}\epsilon_{\mathcal{S}}(h,h^{\prime})-\epsilon_{\mathcal{T}}(h,h^{\prime})\Big{|}$
$\displaystyle\geq\dfrac{2}{N}\enspace\Big{|}\epsilon_{\mathcal{S}}(h,h^{\prime})-\epsilon_{\mathcal{T}}(h,h^{\prime})\Big{|}.$

∎

######  Lemma A.2.

Given three hypotheses $h_{1},h_{2},h_{3}\in\mathcal{H}$, we have the
following triangle inequality:

$\displaystyle\epsilon_{\mathcal{D}}(h_{1},h_{2})\leq\epsilon_{\mathcal{D}}(h_{1},h_{3})+\epsilon_{\mathcal{D}}(h_{2},h_{3}).$
(11)

###### Proof.

The hypothesis difference

$\displaystyle\epsilon_{\mathcal{D}}(h_{1},h_{2})$
$\displaystyle=\sum\nolimits_{i=1}^{N}\bigg{|}h_{1}(x^{\mathcal{D}})-h_{2}(x^{\mathcal{D}})\bigg{|}$
$\displaystyle=\sum\nolimits_{i=1}^{N}\bigg{|}h_{1}(x^{\mathcal{D}})-h_{2}(x^{\mathcal{D}})+h_{3}(x^{\mathcal{D}})-h_{3}(x^{\mathcal{D}})\bigg{|}$
$\displaystyle\leq\sum\nolimits_{i=1}^{N}\bigg{|}h_{1}(x^{\mathcal{D}})-h_{3}(x^{\mathcal{D}})\bigg{|}+\sum\nolimits_{i=1}^{N}\bigg{|}h_{3}(x^{\mathcal{D}})-h_{2}(x^{\mathcal{D}})\bigg{|}$
$\displaystyle=\epsilon_{S}(h_{1},h_{3})+\epsilon_{S}(h_{2},h_{3}).$

∎

######  Lemma A.3.

Let $\mathcal{H}$ be a hypothesis space. Then for every $h\in\mathcal{H}$:

$\displaystyle\epsilon_{\mathcal{T}}(h)\leq\epsilon_{\mathcal{S}}(h)+\dfrac{N}{2}\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})+\psi,$
(12)

where $\psi$ is defined in Definition 3.7.

###### Proof.

By definition in Definition 3.3 in main paper, we start from
$\epsilon_{\mathcal{T}}(h)=\epsilon_{\mathcal{T}}(h,f_{\mathcal{T}})$, then we
have

$\displaystyle\epsilon_{\mathcal{T}}(h)$
$\displaystyle=\epsilon_{\mathcal{T}}(f_{\mathcal{T}},h)$
$\displaystyle\leq\epsilon_{\mathcal{T}}(f_{\mathcal{T}},h^{*})+\epsilon_{\mathcal{T}}(h,h^{*})$
$\displaystyle\leq\epsilon_{\mathcal{T}}(h^{*})+\epsilon_{\mathcal{S}}(h,h^{*})+|\epsilon_{\mathcal{T}}(h,h^{*})-\epsilon_{\mathcal{S}}(h,h^{*})|$
$\displaystyle\leq\epsilon_{\mathcal{T}}(h^{*})+\epsilon_{\mathcal{S}}(h,h^{*})+\dfrac{N}{2}\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})$
$\displaystyle\leq\epsilon_{\mathcal{T}}(h^{*})+\epsilon_{\mathcal{S}}(h)+\epsilon_{\mathcal{S}}(h^{*})+\dfrac{N}{2}\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})$
$\displaystyle=\epsilon_{\mathcal{S}}(h)+\psi+\dfrac{N}{2}\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T}).$

∎

###  A.2 Proof for the Target Regret Bound

######  Theorem A.1 (Target Regret Bound).

Denoting the contexts from the source domain ${\mathcal{S}}$ as $\\{{\bf
x}_{t,a}^{\mathcal{S}}\\}_{i\in[N],a\in[K]}$, the associated ground-truth
action as $\\{a_{i}^{*}\\}_{i=1}^{N}$, and the contexts from the target domain
${\mathcal{T}}$ as $\\{{\bf x}_{t,a}^{\mathcal{T}}\\}_{i\in[N],a\in[K]}$, the
upper bound for our target regret $R_{{\mathcal{T}}}$ is

$\displaystyle\mathit{R}_{\mathcal{T}}$
$\displaystyle\triangleq\sum\nolimits_{i=1}^{N}\Bigg{(}\Big{|}\langle\theta_{\mathcal{T}}^{*},\phi_{\mathcal{T}}^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\theta_{\mathcal{T}}^{*},\phi_{\mathcal{T}}^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\Bigg{)}$
$\displaystyle\leq{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\underbrace{\mathit{R}_{\mathcal{S}}}_{Source~{}Regret}}+{\color[rgb]{1,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0.5}\pgfsys@color@cmyk@stroke{0}{1}{0.50}{0}\pgfsys@color@cmyk@fill{0}{1}{0.50}{0}\underbrace{\epsilon_{\mathcal{S}}(h)}_{Regression~{}Error}}+{\color[rgb]{0,0.5,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,1}\pgfsys@color@cmyk@stroke{1}{0.50}{0}{0}\pgfsys@color@cmyk@fill{1}{0.50}{0}{0}\underbrace{N\cdot\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})}_{Data~{}Divergence}}+{\color[rgb]{1,0.58,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.58,0}\pgfsys@color@cmyk@stroke{0}{0.42}{1}{0}\pgfsys@color@cmyk@fill{0}{0.42}{1}{0}\underbrace{\sum\nolimits_{i=1}^{N}\Bigg{(}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\Bigg{)}}_{Predicted~{}Reward}}+{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color@cmyk@fill{0.85}{0}{0.33}{0}\underbrace{\psi+C}_{Constant}},$

where $\mathit{R}_{\mathcal{S}}$, $\epsilon_{\mathcal{S}}(h)$, and
$\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}$ are defined in Sec. 3. $\psi$ and
$C$ are constants.

###### Proof.

[Please check the full proof in the next page.]

By the definition of the Target Regret Bound, we have

$\displaystyle\mathit{R}_{\mathcal{T}}$
$\displaystyle=\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\theta^{*},\phi^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}$
$\displaystyle=\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\theta^{*},\phi^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle+\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}$
$\displaystyle\leq\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}+\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}$
$\displaystyle\leq\epsilon_{\mathcal{T}}(h)+\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle+\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}$
$\displaystyle\leq\epsilon_{\mathcal{T}}(h)+{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color@cmyk@fill{0.85}{0}{0.33}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}}+{\color[rgb]{0.5,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,1,0}\pgfsys@color@cmyk@stroke{0.50}{0}{1}{0}\pgfsys@color@cmyk@fill{0.50}{0}{1}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}}$
$\displaystyle=\epsilon_{\mathcal{T}}(h)+{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color@cmyk@fill{0.85}{0}{0.33}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}}+{\color[rgb]{0.5,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,1,0}\pgfsys@color@cmyk@stroke{0.50}{0}{1}{0}\pgfsys@color@cmyk@fill{0.50}{0}{1}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}}$
$\displaystyle\quad+{\color[rgb]{1,0.52,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.52,1}\pgfsys@color@cmyk@stroke{0}{0.48}{0}{0}\pgfsys@color@cmyk@fill{0}{0.48}{0}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}}-{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}}$
$\displaystyle\leq\epsilon_{\mathcal{T}}(h)+{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color@cmyk@fill{0.85}{0}{0.33}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}}+{\color[rgb]{1,0.52,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.52,1}\pgfsys@color@cmyk@stroke{0}{0.48}{0}{0}\pgfsys@color@cmyk@fill{0}{0.48}{0}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}}$
$\displaystyle\quad+\Bigg{|}{\color[rgb]{0.5,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,1,0}\pgfsys@color@cmyk@stroke{0.50}{0}{1}{0}\pgfsys@color@cmyk@fill{0.50}{0}{1}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}}-{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}}\Bigg{|}$
$\displaystyle\leq{\color[rgb]{1,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0.5}\pgfsys@color@cmyk@stroke{0}{1}{0.50}{0}\pgfsys@color@cmyk@fill{0}{1}{0.50}{0}\epsilon_{\mathcal{T}}(h)}+\dfrac{N}{2}\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})+{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color@cmyk@fill{0.85}{0}{0.33}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{T}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{T}})\rangle\Big{|}\bigg{]}\Bigg{)}}$
$\displaystyle\quad+{\color[rgb]{1,0.52,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.52,1}\pgfsys@color@cmyk@stroke{0}{0.48}{0}{0}\pgfsys@color@cmyk@fill{0}{0.48}{0}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle+\langle\theta^{*},\phi^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle-\langle\theta^{*},\phi^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}}$
$\displaystyle\leq{\color[rgb]{1,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0.5}\pgfsys@color@cmyk@stroke{0}{1}{0.50}{0}\pgfsys@color@cmyk@fill{0}{1}{0.50}{0}\epsilon_{\mathcal{S}}(h)+\psi+\dfrac{N}{2}\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})}+\dfrac{N}{2}\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})+{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>(13)
$\displaystyle\quad+{\color[rgb]{1,0.52,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.52,1}\pgfsys@color@cmyk@stroke{0}{0.48}{0}{0}\pgfsys@color@cmyk@fill{0}{0.48}{0}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle-\langle\theta^{*},\phi^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}}+{\color[rgb]{1,0.52,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.52,1}\pgfsys@color@cmyk@stroke{0}{0.48}{0}{0}\pgfsys@color@cmyk@fill{0}{0.48}{0}{0}\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle-\langle\theta^{*},\phi^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}}$
$\displaystyle\leq\epsilon_{\mathcal{S}}(h)+\psi+N\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})+C_{1}+\mathit{R}_{S}+\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}+\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}$
$\displaystyle\leq\epsilon_{\mathcal{S}}(h)+\psi+N\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})+C_{1}+\mathit{R}_{S}+\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}+C_{2}$ (14)
$\displaystyle\leq\epsilon_{\mathcal{S}}(h)+\psi+N\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})+\mathit{R}_{S}+\sum^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\bigg{]}\Bigg{)}+C$ (15)
$\displaystyle={\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\underbrace{\mathit{R}_{\mathcal{S}}}_{Source~{}Regret}}+{\color[rgb]{1,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0.5}\pgfsys@color@cmyk@stroke{0}{1}{0.50}{0}\pgfsys@color@cmyk@fill{0}{1}{0.50}{0}\underbrace{\epsilon_{\mathcal{S}}(h)}_{Regression~{}Error}}+{\color[rgb]{0,0.5,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,1}\pgfsys@color@cmyk@stroke{1}{0.50}{0}{0}\pgfsys@color@cmyk@fill{1}{0.50}{0}{0}\underbrace{N\cdot\widehat{d}_{\mathcal{H}\Delta\mathcal{H}}(\mathcal{S},\mathcal{T})}_{Data~{}Divergence}}+{\color[rgb]{1,0.58,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.58,0}\pgfsys@color@cmyk@stroke{0}{0.42}{1}{0}\pgfsys@color@cmyk@fill{0}{0.42}{1}{0}\underbrace{\sum_{i=1}^{N}\Bigg{(}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\Bigg{)}}_{Predicted~{}Reward}}+{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color@cmyk@fill{0.85}{0}{0.33}{0}\underbrace{\psi+C}_{Constant}},$

where $C=C_{1}+C_{2}$. Furthermore, the inequality (13) is due to the fact
that the range of reward lies in $(0,1)$, which implies
$\sum\nolimits^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}})\rangle-\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}})\rangle\Big{|}\bigg{]}\Bigg{)}\leq\sum\nolimits^{N}_{i=1}\Bigg{(}\bigg{[}1\bigg{]}\Bigg{)}:=C_{1}$,
and the inequality (14) is due to
$\sum\nolimits^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,\widehat{a}_{i}})\rangle\Big{|}\bigg{]}\Bigg{)}\leq\sum\nolimits^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\theta^{*},\phi^{*}({\bf
x}_{i,a_{i}^{*}})\rangle\Big{|}\bigg{]}\Bigg{)}:=C_{2}$. Furthermore, the
inequality (15) is due to
$\sum\nolimits^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,a_{i}^{*}})\rangle\Big{|}\bigg{]}\Bigg{)}\leq\sum\nolimits^{N}_{i=1}\Bigg{(}\bigg{[}\Big{|}\langle\widehat{\theta},\widehat{\phi}({\bf
x}_{i,\widehat{a}_{i}})\rangle\Big{|}\bigg{]}\Bigg{)}$. ∎

##  Appendix B Datasets

To evaluate the effectiveness of our DABand, for each dataset, we treat the
“easy” domain as the low-cost source domain and the more challenging one as
the high-cost target domain. This allows us to demonstrate the efficacy of our
method by adapting from a simpler to a more complex domain within a contextual
bandit setting.

_DIGIT._ Our DIGIT dataset consists of MNIST and MNIST-M. MNIST is a gray-
scale hand-written digit dataset, while MNIST-M [37] features color digits. In
this paper, MNIST serves as our source domain, and MNIST-M as our target
domain, offering a more challenging adaptation path. The MNIST digits are
gray-scale and uniform in size, aspect ratio, and intensity range, in stark
contrast to the colorful and varied digits of MNIST-M. Therefore, adapting
from MNIST to MNIST-M presents a greater challenge than adapting from MNIST-M
to MNIST, where the target domain is less complex.

_VisDA17._ The VisDA-2017 image classification challenge [38] addresses a
domain adaptation problem across 12 classes, involving three distinct
datasets. The training set consists of 3D rendering images, whereas the
validation and test sets feature real images from the COCO [40] and YouTube
Bounding Boxes [41] datasets, respectively. Ground truth labels were provided
only for the training and validation sets. Scores for the test set were
calculated by a server operated by the competition organizers. For our
purposes, we use the training set as the source domain and the validation set
as the target domain.

_S2RDA49._ The S2RDA49 (Synthetic-to-Real) is a new benchmark dataset [39]
constructed in 2023. This dataset contains $49$ classes. The source domain
(i.e., the synthetic domain) is synthesized by rendering 3D models from
ShapeNet [42]. The used 3D models are in the same label space as the
target/real domain, and each class has 12K rendered RGB images. The target
domain (i.e., the real domain) of S2RDA49 contains $60535$ images from $49$
classes, collected from the ImageNet validation set [43], ObjectNet [44],
VisDA2017 validation set [38], and the web. In this paper, we select the only
$10$ class that matches the VisDA17 dataset.

##  Appendix C Baselines

We compare our DABand with both classic and state-of-the-art contextual bandit
algorithms. We start with LinUCB [1], a typical baseline for linear contextual
bandit problems. To enable comprehensive comparisons, we extend our evaluation
to include LinUCB augmented with pre-processed features using principle
component analysis (PCA), referred to as LinUCB-P. In LinUCB-P, we first apply
PCA to fit on training data (without labels/feedback) in both source and
target domain. Then, with transformed, lower-dimensional context data, LinUCB
is performed to see whether this pre-alignment procedure can transfer the
knowledge to the target domain. Another pivotal baseline in our study is
Neural-LinUCB [11] (NLinUCB), which utilizes several layers of fully connected
neural networks to dynamically process the original features at the beginning
of every iteration. Similar to LinUCB-P, we introduce a NLinUCB variant that
incorporates PCA, i.e., NLinUCB-P. Note that domain adaptation baselines are
not applicable to our setting. Specifically, domain adaptation methods only
work in offline settings, and assume complete observability of labels in the
source domain. In contrast, contextual bandit is an online setting where the
oracle is revealed only when correctly predicted. Therefore domain adaptation
methods are not applicable to our online bandit settings.

##  Appendix D Implementation Details

In this section, we provide detailed insights into the implementation of our
approach, applied to two distinct datasets: DIGIT and VisDA17. We use Pytorch
to implement our method, and all experiments are run on servers with NVIDA
A5000 GPUs.

DIGIT. Within the DIGIT dataset framework, we use the MNIST dataset as the
source domain and MNIST-M as the target domain. To ensure compatibility
between the datasets, we standardize the channel size of images in the source
domain ($c_{\mathcal{S}}=1$) to align with that in the target domain
($c_{\mathcal{T}}=3$). Each image undergoes normalization and is resized to
$28\times 28$ pixels with 3 channels to accommodate the format requirements of
both domains. Then, an encoder is utilized to diminish the data’s
dimensionality to a more manageable latent space. Following this reduction,
the data is processed through two fully connected neural network layers,
ending in the final latent space necessary for loss computation as delineated
in main paper. For the optimal hyperparameters, we set the learning rate to
$1\times e^{-5}$, with $\lambda$ is chosen from $\\{1.0,5.0,10.0,15.0,20.0\\}$
and kept the same for all experiments. Additionally, we set the exploration
rate $\alpha$ to $0.05$.

VisDA17. We use the VisDA17 dataset’s training set as the source domain, with
the validation set functioning as the target domain. We adhere to
preprocessing steps established by [45] to ensure uniformity across domains:
Each image is normalized and resized to $224\times 224$ pixels with 3
channels, matching the requisite specifications for both source and target
domains. For hyperparameters, the learning rate of $1\times e^{-5}$ is
applied, with $\lambda$ is chosen from $\\{1.0,5.0,10.0,15.0,20.0\\}$ and then
kept the same for all experiments. We set the exploration rate $\alpha$ to
$0.05$.

S2RDA49. We selects $10$ classes from the original $49$ classes since it
matches the target domain samples in VisDA17 [38]. We adhere to preprocessing
steps established by [45] to ensure uniformity across domains: Each image is
normalized and resized to $224\times 224$ pixels with 3 channels. For
hyperparameters, the learning rate of $1\times e^{-3}$ is applied, with
$\lambda$ chosen from $\\{1.0,5.0,10.0,15.0,20.0\\}$ and then kept the same
for all experiments. We set the exploration rate $\alpha$ to $0.01$.

##  Appendix E Limitation

This work contains several limitations. Specifically, we highlight below:

Intuitive Perspective. The bandit algorithm indeed enjoys interpretability and
the accuracy of its closed-form updates, but this is true only because it
typically employs a linear model.

Unfortunately, linear models do not work very well for real-world data, which
is often high-dimensional. For example, the empirical results for LinUCB and
LinUCB-P in Table 1 and Table 2 show that such linear contextual bandit
algorithms significantly underperform state-of-the-art neural bandit
algorithms, which use back-propagation (similar results are shown in [9, 11]).
In summary deep learning models with back-propagation is necessary due to the
following reasons:

  * •

High-Dimensional Data. To enhance performance in real-world high-dimensional
data (e.g., images), the integration of deep learning (and back-propagation)
is necessary, though this may sacrifice a portion of the algorithm’s
explanatory power.

  * •

Covariate Shift and Aligning Source and Target Domains in the Latent Space. In
our settings where there is covariance shift between the source and target
domains, a deep (nonlinear) encoder is required to transform the original
context into a latent space where source-domain encodings and target-domain
encoders can align. This also necessitates deep learning models with back-
propagation.

Indeed, there is a trade-off between interpretability and performance. This
would certainly be an interesting future direction, but it is out of the scope
of this paper.

Theoretical Perspective. Our Theorem 3.1 is sharp, as all the inequalities are
based on lemmas in the paper and the Cauchy inequality. Identifying the
criteria under which the target regret bound reaches equality as well as how
one can achieve it in practice would be interesting future work.

Empirical Perspective. The performance of DABand largely relies on the
alignment quality between the source and target domains. Therefore, for two
domains that cannot be aligned (for example, most domain adaptation tasks are
predefined, and the data for both domains is pre-processed and cleaned, not
original real-world data), it is challenging to evaluate how DABand can still
transfer knowledge across different domains. Furthermore, it is still unknown
whether, if we increase the domain shift in a dataset from another domain, our
DABand can still perform well. These issues are beyond the scope of this
paper, but they represent interesting areas for future work.

##  Appendix F Discussions

###  F.1 Difference between Bandit and Classification Settings

In the classification setting, given a sample ${\bf x}$, a model predicts its
label $\widehat{y}$. Since its ground-truth label is known, one can directly
apply the cross-entropy loss to perform back-propagation and update our model.
In contrast, in bandit settings, for each sample ${\bf x}$, our model predicts
an action $\widehat{a}$ by optimizing the estimated rewards. One then submits
this predicted action to the environment and receives feedback that only
indicates whether the predicted action $\widehat{a}$ is the optimal action
$a^{*}$ or not. If not, we are informed that our prediction is incorrect, yet
we do not receive information on what the correct (optimal) action should be.
Moreover, during training, we only train on 300 episodes for DIGIT and VisDA17
and 100 episodes for S2RDA49. Each episode contains 64 samples. This implies
that compared with those DA methods which train on multiple epochs, in our
settings, all of the models only see a sample once. Such complexity makes the
bandit setting much more challenging.

###  F.2 Importance of Bandits and DABand

Bandit algorithms are designed to navigate environments where feedback is
sparse, costly, and indirect. By efficiently learning from limited feedback –
identifying not just when a prediction is wrong but adapting without explicit
guidance on the right choice – bandit algorithms offer a strategic advantage
in dynamically evolving settings. Our DABand exemplifies this by leveraging a
low-cost source domain to improve performance in a high-cost target domain,
thereby reducing cumulative regret (improving accuracy) while minimizing
operational costs. DABand not only reduces the expense associated with
acquiring and labeling vast datasets but also capitalizes on the intrinsic
adaptability of bandit algorithms to learn and optimize in complex, uncertain
environments.

###  F.3 Discussion on Zero-shot Target Regret Bound

####  F.3.1 Significance of Theorem 3.1

Note that Theorem 3.1 is nontrivial. While it does resemble the generalization
bound in domain adaptation, there are key differences. As mentioned in
Observation (3) in Sec. 3.6, our target regret bound includes two additional
crucial terms not found in domain adaptation. Specifically:

  * •

Regression Error in the Source Domain.
$\sum\nolimits_{i=1}^{N}\Bigg{(}\Big{|}\langle\theta_{\mathcal{S}}^{*},\phi_{\mathcal{S}}^{*}(x_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle-\langle\widehat{\theta},\widehat{\phi}(x_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\Bigg{)}$,
which defines the difference between the true reward from selecting action
$\widehat{a}_{i}$ and the estimated reward for this action.

  * •

Predicted Reward.
$\sum\nolimits_{i=1}^{N}\Bigg{(}\Big{|}\langle\widehat{\theta},\widehat{\phi}(x_{i,\widehat{a}_{i}}^{\mathcal{S}})\rangle\Big{|}\Bigg{)}$,
which serves as a regularization term to regularize the model to avoid
overestimating rewards.

The results of the ablation study in Table 4 in Sec. 5 highlight the
significance of these two terms. Moreover, we would also like to highlight the
key novelty/challenges in deriving Theorem 3.1:

  * •

Generalization of $\mathcal{H}\Delta\mathcal{H}$ Distance to Regression. In
the original multi-domain generalization bound [1], the
$\mathcal{H}\Delta\mathcal{H}$ divergence between source and target domains is
derived for classification models. However, contextual bandit is essentially a
reward regression problem, and therefore necessitates generalizing the
$\mathcal{H}\Delta\mathcal{H}$ distance from the classification case to the
regression case. This presents a significant technical challenge, and leads to
a series of modification in the proof.

  * •

Decomposing the Target Regret into the Source Regret with Other Terms. The
subsequent challenge involves decomposing the regret bound for the target
domain (i.e., the target regret) into a source regret term and other terms to
upper-bound the target regret. This is necessary because we do not have access
to feedback/reward from the target domain (we only have access to
feedback/reward in the source domain). This process requires a nuanced
understanding of the interplay between source and target domain dynamics
within our model’s framework.

####  F.3.2 Testing Phase rather than Traditional Bandit Learning Settings

Our regret bound in Theorem 3.1 is a zero-shot regret bound for the target
domain (with empirical results in the Zero-Shot Target Regret paragraph of
Sec. 5), which corresponds to a testing phase.

However, we would like to clarify that extending this bound to handle
continued training in the target domain (corresponding to the Continued
Training in Target Domains and Cumulative Regret paragraph of Sec. 5) is
straightforward. At a high level, we can have

$\displaystyle R_{\mathcal{T}}^{total}=R_{\mathcal{T}}^{zero-
shot}+R_{\mathcal{T}}^{continued},$

with the first term handled by our DABand’s Theorem 3.1 and the second term
handled by typical single-domain contextual bandit.

####  F.3.3 Scale of Source Regret and Predicted Rewards

Similar to Neural-LinUCB, in our DABand, the true reward is restricted to the
range of $[0,1]$ (as we mentioned in Sec. 3.1); therefore it will not make the
source regret unbounded.

Furthermore, our DABand algorithm tries to minimize the source regret while
aligning the source and target domains. The minimization of the source regret
is theoretically guaranteed, as discussed in recent work such as Neural-LinUCB
[11].

##  Appendix G Potential Impact of DABand

Our DABand has many potential real-world applications, especially when
obtaining responses is costly. For instance, in testing new drugs, we can
construct responses from mice for new drug A, and then use DABand to obtain
the zero-shot hypothetical regret bound for responses in humans. In another
scenario, we can collect data (responses) on humans for another published,
similar drug B, and then transfer knowledge by aligning the divergence between
drug A and drug B. If both regrets reveal acceptable performance, we might not
need excessive costs for back-and-forth testing, which significantly speeds up
the process and reduces costs.

## NeurIPS Paper Checklist

  1. 1.

Claims

  2. Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

  3. Answer: [Yes]

  4. Justification: It can be found in the Sec. 1.

  5. Guidelines:

     * •

The answer NA means that the abstract and introduction do not include the
claims made in the paper.

     * •

The abstract and/or introduction should clearly state the claims made,
including the contributions made in the paper and important assumptions and
limitations. A No or NA answer to this question will not be perceived well by
the reviewers.

     * •

The claims made should match theoretical and experimental results, and reflect
how much the results can be expected to generalize to other settings.

     * •

It is fine to include aspirational goals as motivation as long as it is clear
that these goals are not attained by the paper.

  6. 2.

Limitations

  7. Question: Does the paper discuss the limitations of the work performed by the authors?

  8. Answer: [Yes]

  9. Justification: In Appendix E.

  10. Guidelines:

     * •

The answer NA means that the paper has no limitation while the answer No means
that the paper has limitations, but those are not discussed in the paper.

     * •

The authors are encouraged to create a separate "Limitations" section in their
paper.

     * •

The paper should point out any strong assumptions and how robust the results
are to violations of these assumptions (e.g., independence assumptions,
noiseless settings, model well-specification, asymptotic approximations only
holding locally). The authors should reflect on how these assumptions might be
violated in practice and what the implications would be.

     * •

The authors should reflect on the scope of the claims made, e.g., if the
approach was only tested on a few datasets or with a few runs. In general,
empirical results often depend on implicit assumptions, which should be
articulated.

     * •

The authors should reflect on the factors that influence the performance of
the approach. For example, a facial recognition algorithm may perform poorly
when image resolution is low or images are taken in low lighting. Or a speech-
to-text system might not be used reliably to provide closed captions for
online lectures because it fails to handle technical jargon.

     * •

The authors should discuss the computational efficiency of the proposed
algorithms and how they scale with dataset size.

     * •

If applicable, the authors should discuss possible limitations of their
approach to address problems of privacy and fairness.

     * •

While the authors might fear that complete honesty about limitations might be
used by reviewers as grounds for rejection, a worse outcome might be that
reviewers discover limitations that aren’t acknowledged in the paper. The
authors should use their best judgment and recognize that individual actions
in favor of transparency play an important role in developing norms that
preserve the integrity of the community. Reviewers will be specifically
instructed to not penalize honesty concerning limitations.

  11. 3.

Theory Assumptions and Proofs

  12. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

  13. Answer: [Yes]

  14. Justification: All the theoretical results and assumptions can be found in Sec. 3 and Appendix A, and all the proofs are in Appendix A.

  15. Guidelines:

     * •

The answer NA means that the paper does not include theoretical results.

     * •

All the theorems, formulas, and proofs in the paper should be numbered and
cross-referenced.

     * •

All assumptions should be clearly stated or referenced in the statement of any
theorems.

     * •

The proofs can either appear in the main paper or the supplemental material,
but if they appear in the supplemental material, the authors are encouraged to
provide a short proof sketch to provide intuition.

     * •

Inversely, any informal proof provided in the core of the paper should be
complemented by formal proofs provided in appendix or supplemental material.

     * •

Theorems and Lemmas that the proof relies upon should be properly referenced.

  16. 4.

Experimental Result Reproducibility

  17. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

  18. Answer: [Yes] .

  19. Justification: It is simple to replicate.

  20. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

If the paper includes experiments, a No answer to this question will not be
perceived well by the reviewers: Making the paper reproducible is important,
regardless of whether the code and data are provided or not.

     * •

If the contribution is a dataset and/or model, the authors should describe the
steps taken to make their results reproducible or verifiable.

     * •

Depending on the contribution, reproducibility can be accomplished in various
ways. For example, if the contribution is a novel architecture, describing the
architecture fully might suffice, or if the contribution is a specific model
and empirical evaluation, it may be necessary to either make it possible for
others to replicate the model with the same dataset, or provide access to the
model. In general. releasing code and data is often one good way to accomplish
this, but reproducibility can also be provided via detailed instructions for
how to replicate the results, access to a hosted model (e.g., in the case of a
large language model), releasing of a model checkpoint, or other means that
are appropriate to the research performed.

     * •

While NeurIPS does not require releasing code, the conference does require all
submissions to provide some reasonable avenue for reproducibility, which may
depend on the nature of the contribution. For example

       1. (a)

If the contribution is primarily a new algorithm, the paper should make it
clear how to reproduce that algorithm.

       2. (b)

If the contribution is primarily a new model architecture, the paper should
describe the architecture clearly and fully.

       3. (c)

If the contribution is a new model (e.g., a large language model), then there
should either be a way to access this model for reproducing the results or a
way to reproduce the model (e.g., with an open-source dataset or instructions
for how to construct the dataset).

       4. (d)

We recognize that reproducibility may be tricky in some cases, in which case
authors are welcome to describe the particular way they provide for
reproducibility. In the case of closed-source models, it may be that access to
the model is limited in some way (e.g., to registered users), but it should be
possible for other researchers to have some path to reproducing or verifying
the results.

  21. 5.

Open access to data and code

  22. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

  23. Answer: [No] .

  24. Justification: Data are all available online, and We will release the code once this paper is accepted.

  25. Guidelines:

     * •

The answer NA means that paper does not include experiments requiring code.

     * •

Please see the NeurIPS code and data submission guidelines
(https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.

     * •

While we encourage the release of code and data, we understand that this might
not be possible, so “No” is an acceptable answer. Papers cannot be rejected
simply for not including code, unless this is central to the contribution
(e.g., for a new open-source benchmark).

     * •

The instructions should contain the exact command and environment needed to
run to reproduce the results. See the NeurIPS code and data submission
guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more
details.

     * •

The authors should provide instructions on data access and preparation,
including how to access the raw data, preprocessed data, intermediate data,
and generated data, etc.

     * •

The authors should provide scripts to reproduce all experimental results for
the new proposed method and baselines. If only a subset of experiments are
reproducible, they should state which ones are omitted from the script and
why.

     * •

At submission time, to preserve anonymity, the authors should release
anonymized versions (if applicable).

     * •

Providing as much information as possible in supplemental material (appended
to the paper) is recommended, but including URLs to data and code is
permitted.

  26. 6.

Experimental Setting/Details

  27. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?

  28. Answer: [Yes]

  29. Justification: All the things are in Appendix B, Appendix C and Appendix D.

  30. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The experimental setting should be presented in the core of the paper to a
level of detail that is necessary to appreciate the results and make sense of
them.

     * •

The full details can be provided either with the code, in appendix, or as
supplemental material.

  31. 7.

Experiment Statistical Significance

  32. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

  33. Answer: [Yes]

  34. Justification: In Table 1, Table 2 and Table 3 for DIGIT, VisDA17 and S2RDA49, respectively.

  35. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The authors should answer "Yes" if the results are accompanied by error bars,
confidence intervals, or statistical significance tests, at least for the
experiments that support the main claims of the paper.

     * •

The factors of variability that the error bars are capturing should be clearly
stated (for example, train/test split, initialization, random drawing of some
parameter, or overall run with given experimental conditions).

     * •

The method for calculating the error bars should be explained (closed form
formula, call to a library function, bootstrap, etc.)

     * •

The assumptions made should be given (e.g., Normally distributed errors).

     * •

It should be clear whether the error bar is the standard deviation or the
standard error of the mean.

     * •

It is OK to report 1-sigma error bars, but one should state it. The authors
should preferably report a 2-sigma error bar than state that they have a 96%
CI, if the hypothesis of Normality of errors is not verified.

     * •

For asymmetric distributions, the authors should be careful not to show in
tables or figures symmetric error bars that would yield results that are out
of range (e.g. negative error rates).

     * •

If error bars are reported in tables or plots, The authors should explain in
the text how they were calculated and reference the corresponding figures or
tables in the text.

  36. 8.

Experiments Compute Resources

  37. Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

  38. Answer: [No] .

  39. Justification: All of our experiments don’t require high performance computing resource, and a single GPU with 16 GB memory is enough. Therefore we do not include in our paper.

  40. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The paper should indicate the type of compute workers CPU or GPU, internal
cluster, or cloud provider, including relevant memory and storage.

     * •

The paper should provide the amount of compute required for each of the
individual experimental runs as well as estimate the total compute.

     * •

The paper should disclose whether the full research project required more
compute than the experiments reported in the paper (e.g., preliminary or
failed experiments that didn’t make it into the paper).

  41. 9.

Code Of Ethics

  42. Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

  43. Answer: [Yes]

  44. Justification: We satisfy all the requirements.

  45. Guidelines:

     * •

The answer NA means that the authors have not reviewed the NeurIPS Code of
Ethics.

     * •

If the authors answer No, they should explain the special circumstances that
require a deviation from the Code of Ethics.

     * •

The authors should make sure to preserve anonymity (e.g., if there is a
special consideration due to laws or regulations in their jurisdiction).

  46. 10.

Broader Impacts

  47. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

  48. Answer: [Yes]

  49. Justification: In Appendix G.

  50. Guidelines:

     * •

The answer NA means that there is no societal impact of the work performed.

     * •

If the authors answer NA or No, they should explain why their work has no
societal impact or why the paper does not address societal impact.

     * •

Examples of negative societal impacts include potential malicious or
unintended uses (e.g., disinformation, generating fake profiles,
surveillance), fairness considerations (e.g., deployment of technologies that
could make decisions that unfairly impact specific groups), privacy
considerations, and security considerations.

     * •

The conference expects that many papers will be foundational research and not
tied to particular applications, let alone deployments. However, if there is a
direct path to any negative applications, the authors should point it out. For
example, it is legitimate to point out that an improvement in the quality of
generative models could be used to generate deepfakes for disinformation. On
the other hand, it is not needed to point out that a generic algorithm for
optimizing neural networks could enable people to train models that generate
Deepfakes faster.

     * •

The authors should consider possible harms that could arise when the
technology is being used as intended and functioning correctly, harms that
could arise when the technology is being used as intended but gives incorrect
results, and harms following from (intentional or unintentional) misuse of the
technology.

     * •

If there are negative societal impacts, the authors could also discuss
possible mitigation strategies (e.g., gated release of models, providing
defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms
to monitor how a system learns from feedback over time, improving the
efficiency and accessibility of ML).

  51. 11.

Safeguards

  52. Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?

  53. Answer: [N/A]

  54. Justification: This question is not applicable to our paper.

  55. Guidelines:

     * •

The answer NA means that the paper poses no such risks.

     * •

Released models that have a high risk for misuse or dual-use should be
released with necessary safeguards to allow for controlled use of the model,
for example by requiring that users adhere to usage guidelines or restrictions
to access the model or implementing safety filters.

     * •

Datasets that have been scraped from the Internet could pose safety risks. The
authors should describe how they avoided releasing unsafe images.

     * •

We recognize that providing effective safeguards is challenging, and many
papers do not require this, but we encourage authors to take this into account
and make a best faith effort.

  56. 12.

Licenses for existing assets

  57. Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

  58. Answer: [Yes]

  59. Justification: We follow the rule to mention and cite others’ assets used in this paper.

  60. Guidelines:

     * •

The answer NA means that the paper does not use existing assets.

     * •

The authors should cite the original paper that produced the code package or
dataset.

     * •

The authors should state which version of the asset is used and, if possible,
include a URL.

     * •

The name of the license (e.g., CC-BY 4.0) should be included for each asset.

     * •

For scraped data from a particular source (e.g., website), the copyright and
terms of service of that source should be provided.

     * •

If assets are released, the license, copyright information, and terms of use
in the package should be provided. For popular datasets,
paperswithcode.com/datasets has curated licenses for some datasets. Their
licensing guide can help determine the license of a dataset.

     * •

For existing datasets that are re-packaged, both the original license and the
license of the derived asset (if it has changed) should be provided.

     * •

If this information is not available online, the authors are encouraged to
reach out to the asset’s creators.

  61. 13.

New Assets

  62. Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

  63. Answer: [N/A]

  64. Justification: This question is not applicable to our paper.

  65. Guidelines:

     * •

The answer NA means that the paper does not release new assets.

     * •

Researchers should communicate the details of the dataset/code/model as part
of their submissions via structured templates. This includes details about
training, license, limitations, etc.

     * •

The paper should discuss whether and how consent was obtained from people
whose asset is used.

     * •

At submission time, remember to anonymize your assets (if applicable). You can
either create an anonymized URL or include an anonymized zip file.

  66. 14.

Crowdsourcing and Research with Human Subjects

  67. Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

  68. Answer: [N/A]

  69. Justification: This question is not applicable to our paper.

  70. Guidelines:

     * •

The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.

     * •

Including this information in the supplemental material is fine, but if the
main contribution of the paper involves human subjects, then as much detail as
possible should be included in the main paper.

     * •

According to the NeurIPS Code of Ethics, workers involved in data collection,
curation, or other labor should be paid at least the minimum wage in the
country of the data collector.

  71. 15.

Institutional Review Board (IRB) Approvals or Equivalent for Research with
Human Subjects

  72. Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

  73. Answer: [N/A]

  74. Justification: This question is not applicable to our paper.

  75. Guidelines:

     * •

The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.

     * •

Depending on the country in which research is conducted, IRB approval (or
equivalent) may be required for any human subjects research. If you obtained
IRB approval, you should clearly state this in the paper.

     * •

We recognize that the procedures for this may vary significantly between
institutions and locations, and we expect authors to adhere to the NeurIPS
Code of Ethics and the guidelines for their institution.

     * •

For initial submissions, do not include any information that would break
anonymity (if applicable), such as the institution conducting the review.