# Bounded (O(1)) Regret Recommendation Learning via Synthetic Controls Oracle
††thanks: Identify applicable funding agency here. If none, delete this.

Enoch Hyunwook Kang  University of Washington
P. R. Kumar  Texas A&M University

###### Abstract

In online exploration systems where users with fixed preferences repeatedly
arrive, it has recently been shown that $O(1)$, i.e., bounded regret, can be
achieved when the system is modeled as a linear contextual bandit. This result
may be of interest for recommender systems, where the popularity of their
items is often short-lived, as the exploration itself may be completed quickly
before potential long-run non-stationarities come into play. However, in
practice, exact knowledge of the linear model is difficult to justify.
Furthermore, potential existence of unobservable covariates, uneven user
arrival rates, interpretation of the necessary rank condition, and users
opting out of private data tracking all need to be addressed for practical
recommender system applications. In this work, we conduct a theoretical study
to address all these issues while still achieving bounded regret. Aside from
proof techniques, the key differentiating assumption we make here is the
presence of effective Synthetic Control Methods (SCM), which are shown to be a
practical relaxation of the exact linear model knowledge assumption. We verify
our theoretical bounded regret result using a minimal simulation experiment.

###### Index Terms:

Recommender systems, Synthetic Controls, Bounded regret

##  I Introduction

In many modern personalization systems (e.g., video/music recommendation
systems), users with highly heterogeneous preferences arrive sequentially and
repeatedly to choose an item. In this context, online learning models have
been increasingly used for their ability to address potential presentation
bias [1] which may occur through repeated data collection - learning feedback
loop when using typical matrix methods [2, 3].

Among online learning models, contextual bandit models [4, 5, 6, 7, 8, 9, 10]
are often used when it is reasonable to make two assumptions on the reward
model. The first assumption is that a user’s observable covariates (e.g.,
demographics, age, sex, etc.), user’s arm (=item) choice, and unknown model
parameters jointly determine the stochastic reward model. (When these unknown
parameters are not shared among arms, we call this model a “disjoint”
contextual bandit model.) The vector of observed covariates is called the
context. The second assumption is that the distribution of the stochastic
reward from an arm with a given context does not change over time. (Each
user’s context itself may change over time in the long run.) The objective of
the contextual bandit model is often to minimize the order of cumulative
regret (=total loss of welfare) as a function of time $T$ [11, 12, 13, 14], as
many recommender systems prioritize user welfare.

In the special case when users arrive repeatedly and each user’s context can
be considered fixed over the short run (e.g., a music listener’s genre
preference does not change after a few songs), the best known regret bound is
constant, i.e., O(1) [15], for the class of models called linear contextual
bandit models [11, 13, 12]. In typical linear contextual bandit model
settings, it is assumed that there is a known function $\phi_{m}$ that maps a
context into a vector representation that is linearly related to the mean of
the reward from arm $m$. It has been shown in [15, 16] that when user arrivals
are modeled as random sampling from a fixed distribution, boundedness of
regret can be attained if and only if the representation vectors jointly
satisfy a full rank condition (details in Section II-A).

The boundedness of regret for linear contextual bandit models is an attractive
result for many recommender system applications. Popularities of video topics
on video platforms are only ephemeral; topics may lose their timeliness before
they get old. However, this violates the second assumption of contextual
bandits. Addressing such potential non-stationarities, either by explicitly
modeling non-stationarities or by addressing worst-case scenarios, has been an
active area of study in the bandit literature [17, 18, 19, 20, 21, 22, 23, 24,
25]. The bounded regret approach attempts to address non-stationarities by
completing exploration quickly enough before long-run non-stationarities kick
in.

Despite the attractiveness of the $O(1)$ regret result in contextual bandits,
it is not clear how the conditions described above can be justified for
practical recommender systems. Specifically, there are five issues that need
to be addressed:

  1. Issue (1):

Due to the potential existence of unobservable covariates [26], known context
information (along with arm choice) may not fully determine the stochastic
reward. This violates the contextual bandit model assumption.

  2. Issue (2):

The existence of a linear representation, a well-justified assumption [16],
does not justify the assumption that the linear representation function is
exactly known. This violates the linear contextual bandit model assumption.

  3. Issue (3):

User arrivals may be far from i.i.d. sampling; they may even be of different
orders, such as $\ln T$ and $T$.

  4. Issue (4):

Disjoint linear contextual bandit models (where unknown parameters are not
common to arms) are widely used [11, 12] for recommender systems. However, the
condition required for the disjoint case to achieve bounded regret [27, 16] is
not an easily operationalizable condition (details in Section II-A)

  5. Issue (5):

A user’s context and the rewards she observes may remain private information
if she opts out of tracking.

In this paper, we focus on the theoretical study of addressing these issues
either by relaxing or by justifying the assumptions to show that we can
consider using bounded O(1) regret methods for recommender systems
applications.

  1. -

For issues (1) and (2), we assume the existence of Synthetic Control method
(SCM) [28, 29, 30, 31, 32, 33, 34] we can use, which is “arguably the most
important innovation in the policy evaluation literature in the last 15 years”
[35]. We observe that what is achieved in Synthetic Control methods is exactly
equivalent to a relaxation of the assumption that the linear representation
function is precisely known111Most Synthetic Control methods address linear
factor model settings, which are non-stationary generalizations of disjoint
linear contextual bandit model settings [12]. While our setting considers
sequential arrivals, the stationarity of the setting allows the application of
synthetic control methods.; this resolves issue (2). As Synthetic Control
methods can address unobserved covariates in the long run [28], issue (1) is
also resolved.

  2. -

For issue (3), our condition only requires some of the users to have similar
order of arrival rates.

  3. -

For issue (4), we provide an operationalizable condition that requires the
user set size to be larger than $|M|\ln|M|$ (this value may be larger under
non-uniform preferences among users over arms).

  4. -

For issue (5), we show users’ strong incentive to opt in and comply with the
recommendations.

The rest of the paper is organized as follows. We provide the relevant
background on bounded regret results and SCM in Section II. Then we present
our main model, the main algorithm we call Counterfactual-UCB (CFUCB), and its
bounded regret analysis in Sections III, IV, and V. Finally, we further
validate the proposed theory via a minimalistic simulation experiment in
Section VII. After reaching the conclusion, Section IX briefly discusses
related previous works.

##  II Preliminaries

###  II-A Bounded regret results for (disjoint) linear contextual bandit
models

In this section, we review the problem settings and conditions for which
bounded regret can be attained for non-disjoint [15] and disjoint [27] linear
contextual bandit models. In Section III, we discuss how they can be relaxed
or justified for practical recommender systems.

Let $A$ be the set of users and $M$ the set of arms. Each user $j\in A$ is
associated with a context vector $\mathbf{x}_{j}\in\mathbb{R}^{k}$, where $k$
is the number of observable covariates for each user.

Rewards model In the setting of [15], every time user $j$ arrives and pulls
arm $m$ the user receives a reward
$\phi_{m}(\mathbf{x}_{j})^{\prime}\beta+\epsilon$, where
$\\{\phi_{m}:\mathbb{R}^{k}\mapsto\mathbb{R}^{d}\\}_{m\in M}$ are linear
representation functions that are assumed to be precisely known, $\beta$ is a
common parameter vector of dimension $d$ that is shared across the arms, and
$\epsilon$ is a i.i.d. zero-mean random noise that follows a sub-Gaussian
distribution with variance proxy $\sigma^{2}$. In the setting of disjoint
linear contextual bandits [27], the reward equation is
$\phi_{m}(\mathbf{x}_{j})^{\prime}\beta_{m}+\epsilon$ where $\beta_{m}$ is an
arm-specific parameter vector for arm $m$.

User arrivals In the settings of [15, 27], user arrivals are modeled as a
result of repeated i.i.d. random sampling according to a fixed distribution
over $A$. Note that this user arrival model is equivalent to independent
repeated user arrivals with exponential inter-arrival times [36].

Condition for bounded regret It is shown in [15, 16] that bounded regret can
be achieved in this setting if and only if $\left\\{\phi_{m_{j*}}(x_{j})\mid
j\in A\right\\}$ spans $\mathbb{R}^{d}$, where $m_{j*}$ is the optimal arm for
user $j$, i.e., $m_{j*}=\operatorname{argmax}_{m\in
M}\phi_{m}(\mathbf{x}_{j})^{\prime}\theta$. In the disjoint case, bounded
regret can be achieved if and only if
$\left\\{\phi_{m_{j*}}(\mathbf{x}_{j})\mid j\in A_{m}\right\\}$ spans
$\mathbb{R}^{d}$ for each $m\in M$, where $A_{m}$ is the set of users whose
optimal arm is $m$, i.e., $A_{m}=\\{j\in A:m_{j*}=m\\}$ [27, 16]. Since $k$
generic randomly generated vectors in $\mathbb{R}^{d}$ with $d\geq k$ are
almost surely linearly independent, this condition can simply be rewritten as
$|A_{m}|\geq d$ for $m\in M$.

###  II-B Synthetic Control Methods (SCM)

Synthetic Control Methods (SCM) have been one of the most actively studied
areas of econometrics [35, 32]. They can be described as an observational
method of finding a linear combination to synthetically construct a user $j\in
A$ from other users in $E\subset A\setminus\\{j\\}$ using their contexts and
previous data. While the coefficients of the linear combination were
constrained to be non-negative and sum to one in the vanilla SCM [28, 29],
recent advances in SCM effectively relax these constraints [30, 31, 32, 33,
34]. Throughout, we will consider this more relaxed version of SCMs.

######  Definition 1 (Synthetic Control Method (SCM)).

Suppose that we are given context vectors $\\{\mathbf{x}_{i}\\}_{i\in A}$ and
previous reward histories $\\{\mathbf{h}_{i}\\}_{i\in A}$. Denote the one and
only arm as arm $1$. A Synthetic Control Method (SCM) is a method that, for
given large enough $E\subseteq A$ and user $j\notin E$, takes
$\\{\mathbf{x}_{i}\\}_{i\in E\cup\\{j\\}}$ and $\\{\mathbf{h}_{i}\\}_{i\in
E\cup\\{j\\}}$ as inputs and outputs $\\{a_{ji}\\}_{i\in E}$ that satisfies
$\mu_{j1}=\sum_{i\in E}a_{ji}\mu_{i1}$, where $\mu_{j1}$ describes user $j$’s
mean reward from arm $1$.

######  Lemma 1 (Abadie et al., 2010 [28]).

Given long enough $\\{\mathbf{h}_{i}\\}_{i\in E\cup\\{j\\}}$, SCM can infer
the linear combination coefficients $\\{a_{ji}\\}_{i\in E}$ described in
Definition 1 as precise as we want, even in the presence of the unobservable
covariates222SCM typically considers the reward model
$Y_{j}(k)=\phi(\mathbf{x}_{j})^{\prime}\beta(t)+\psi(\mathbf{y}_{j})^{\prime}\lambda(t)+\epsilon(k)=\mu_{j}+\epsilon(k)$,
which is called the linear factor model. Abadie et al. 2010 [28] shows Lemma 1
for the linear factor model..

##  III The main model

In this section, we introduce the main model considered in this paper. We
denote the set of users by $A$ and the set of arms by $M$. We further denote
by $A_{+}$ the subset of users who opt in for the revelation of their private
data. That is, the recommender knows $\mathbf{x}_{j}\in\mathbb{R}^{k}$ of user
$j\in A_{+}$ and the rewards user $j\in A_{+}$ receives.

###  III-A Rewards model and objective

Let $Y_{j,m}(k)$ denote the reward obtained from user $j$’s $k$th pull of arm
$m$. We first consider the reward model
$Y_{j,m}(k)=\phi_{m}(\mathbf{x}_{j})^{\prime}\beta_{m}+\psi_{m}(\mathbf{y}_{j})^{\prime}\lambda_{m}+\epsilon(k)=\mu_{j,m}+\epsilon(k)$,
the multi-arm extension of the static version of the model2 usually considered
by SCM methods.

For each user $j\in A$, define $m_{j}^{*}\in M$ as an optimal arm that
satisfies $\mu_{j,m^{*}_{j}}\geq\mu_{j,m}\;\;\forall m\in M$, and
$\Delta_{j,m}:=\mu_{j,m^{*}_{j}}-\mu_{j,m}$ as the instantaneous pseudo-regret
of using arm $m$. Denote the arm pulled by user $j$ at its $n$-th arrival by
$m_{j}(n)$. Let $N_{j}(t)$ be the random variable indicating the total number
of arrivals of user $j$ until time $t$. Then the finite time pseudo-regret of
user $j$ until time $T$ is
$Regret_{j}(T):=\sum_{n=1}^{N_{j}(T)}\Delta_{j,m_{j}(n)}=\sum_{n=1}^{N_{j}(T)}(\mu_{j,m^{*}_{j}}-\mu_{j,m_{j}(n)})$,
which we will simply abbreviate as “regret.” The system’s total regret is
$\sum_{j\in A}Regret_{j}(T)$.

Let $\mathbf{h}_{j,m}$ denote the previous history of rewards for user $j\in
A_{+}$ from the arm $m\in M$. Definition 1 and Lemma 1 in Section II-B allows
us to make the following assumption:

######  Assumption 1 (Synthetic Control Oracle (SCO)).

Fix an arm $m\in M$. For any $E\subseteq A_{+}$ and $j\in E^{c}\cap A_{+}$
that satisfies $rank(\\{\phi_{m}(\mathbf{x}_{i})\\})_{i\in E}\geq
dim(\phi_{m}(\mathbf{x}_{j}))$, there is a Synthetic Control Oracle (SCO) that
takes $(\\{\mathbf{x_{i}}\\}_{i\in E\cup\\{j\\}},\\{\mathbf{h}_{i,m}\\}_{i\in
E\cup\\{j\\}})$ as its input and outputs $\\{a_{ji}^{(m)}\\}_{i\in E}$ that
satisfies $\mu_{jm}=\sum_{i\in E}a_{ji}^{(m)}\mu_{im}$, regardless of the
unobservable covariates $\\{\mathbf{y}_{i}\\}_{i\in E\cup\\{j\\}}$.

The following lemma shows that the SCO assumption is a relaxation of the
requirement for knowledge of a precise linear model knowledge in typical
linear contextual bandit models:

######  Lemma 2.

Assumption 1 is a relaxation of the assumptions that (i) there are no
unobserved covariates, and (ii) that the linear model is known to the
recommender.

###### Proof of Lemma 2.

From Lemma 1, it is immediate that Assumption 1 is a relaxation of the $(i)$
part assumption that there are no unobserved covariates. For the $(ii)$ part,
for any $E\subseteq A$ with $rank(\\{\phi_{m}(\mathbf{x}_{j})\\})_{j\in E}\geq
dim(\phi_{m}(\mathbf{x}_{j}))$ and $j\notin E$, we can find
$\\{a_{ji}^{(m)}\\}_{i\in E}$ such that $\phi_{m}(\mathbf{x}_{j})=\sum_{i\in
E}a_{ji}^{(m)}\phi_{m}(\mathbf{x}_{i})$. This implies that
$\mu_{j,m}=\phi_{m}(\mathbf{x}_{j})^{\prime}\beta_{m}=\sum_{i\in
E}a_{ji}^{(m)}\phi_{m}(\mathbf{x}_{i})^{\prime}\beta_{m}=\sum_{i\in
E}a_{ji}^{(m)}\mu_{i,m}$. ∎

In many practical recommender systems, it is not necessary to consider a
separate user context representation function $\phi_{m}$ for each arm $m\in
M$. For example, in movie recommendation problem, user context representation
may represent a user’s affinity for different genres, how much the user values
plot complexity, and the user’s preference for movies with a specific mood
(e.g., light-hearted, serious, or thought-provoking), all of which are
characteristics not specific to a particular movie. This leads us to consider
a simplified model
$Y_{i,m}(k)=\phi(\mathbf{x}_{j})^{\prime}\beta_{m}+\psi(\mathbf{y}_{j})^{\prime}\lambda_{m}+\epsilon(k)=\mu_{j,m}+\epsilon(k)$.
Below is the resulting simplified form of Assumption 1.

######  Assumption 1 (Synthetic Control Oracle (SCO) in simplified reward
model).

For any $E\subseteq A_{+}$ and $j\in E^{c}\cap A_{+}$ that satisfies
$rank(\\{\phi(\mathbf{x}_{i})\\})_{i\in E}\geq dim(\phi(\mathbf{x}_{j}))$,
there is a Synthetic Control Oracle (SCO) that takes
$(\\{\mathbf{x_{i}}\\}_{i\in E\cup\\{j\\}},\\{\mathbf{h}_{i,m}\\}_{i\in
E\cup\\{j\\}})$ as its input and outputs $\\{a_{ji}\\}_{i\in E}$ that
satisfies $\mu_{jm}=\sum_{i\in E}a_{ji}\mu_{im}$ for any $m$, regardless of
the unobservable covariates $\\{\mathbf{y}_{i}\\}_{i\in E\cup\\{j\\}}$.

The simplified SCO is useful in practice as it can generalize experiences
among arms. In Spotify, for example, there are more than 60,000 songs (=arms)
newly registered each day [37]; given this simplified disjoint version
Assumption 1, the SCO in Spotify’s case can take previous user experiences
from existing songs as its input and output the linear combination
coefficients that can be used for the future exploration of newly registered
songs.

###  III-B User arrivals

We generalize the arrival model in Section II-A to allow for users with
arrival rates of different orders. Let $S_{j}(n)$ be the random variable
indicating user $j$’s $n$th arrival time, and
$F^{(n)}_{j}(t):=P(\\{S_{j}(n)\leq t\\})$. For $i,j\in A$, define
$q_{ij,m}(x):=-\frac{B}{A}\mathcal{W}_{-1}\left(-\frac{A}{B}(\frac{x}{d})^{-\frac{C}{B}}\right)$,
where $\mathcal{W}_{-1}$ is the lower branch Lambert W-function [38], where
$A=1$, $B=\sum_{n\neq m}\frac{16}{{\Delta_{i,n}}^{2}}$ and
$C=\frac{16c^{2}_{m,t}}{{\Delta_{j,m}}^{2}}$. (Remark: $q_{ij,m}(x)$ increases
faster than $\ln x$ but slower than $x$ \- see Appendix XI).

######  Assumption 2.

Consider users $E_{j,m}:=\\{i\in
A\setminus\\{j\\}:\lim\sup_{n\to\infty}\frac{\int_{0}^{+\infty}P(N_{i}(t)<q_{ij,m}(N_{j}(t))dF_{j}^{(n)}(t)}{\frac{1}{n^{2}}}<+\infty\\}.$
We assume that $|E_{j,m}\cap A_{+}\cap A_{m}|\geq d$ for all $j\in A_{+}$ and
$m\in M$.

Intuitively, $E_{j,m}$ refers to users in $A$ whose orders of arrival rates
are not far behind the arrival rate of $j$. Assumption 2 says that, for each
opted in user, there are enough other opted in users whose tastes are
different from hers but have similar (or faster) arrival rate orders. It
generalizes the user arrival model of [15] discussed in Section II-A, i.e.,
i.i.d. random sampling according to a fixed distribution over $A$, where
arrival rate orders are the same for all users in $A$:

######  Lemma 3 (Exponential inter-arrival times (equivalent to i.i.d. sampled
arrivals)).

Suppose that each user $i\in A$ repeatedly arrives independently with $i.i.d.$
exponentially distributed inter-arrival times with parameter $\lambda_{i}$.
Then $E_{j,m}=A$, and Assumption 2 becomes $|A_{+}\cap A_{m}|\geq d$ for $m\in
M$, a reminiscent of condition $|A_{m}|\geq d$ for $m\in M$ in Section II-A.

Lemma 4 shows that Assumption 2 also holds also for Sub-Gaussian arrivals
(proof in Appendix X).

######  Lemma 4 (Subgaussian inter-arrival times).

Suppose that each user $i\in A$ repeatedly arrives independently with $i.i.d.$
1-sub-Gaussian inter-arrival times with mean $\theta_{i}$. Then $E_{j,m}=A$,
and Assumption 2 becomes $|A_{+}\cap A_{m}|\geq d$ for $m\in M$.

###  III-C Operationalizable condition for bounded regret

Note that the condition described in Assumption 2 of Section III-B
($|E_{j,m}\cap A_{+}\cap A_{m}|\geq d$) serves as a counterpart to the
condition $|A_{m}|\geq d$ for $m\in M$ in Section II-A; if we further assume
that all user arrival rates are of the same order (which results in
$E_{j,m}=A$ (e.g., Lemma 3 and 4)), that condition becomes $|A_{+}\cap
A_{m}|\geq d$. However, this condition cannot be verified, as $A_{m}$ is
unknown: if $A_{m}$ were known, exploration would be unnecessary.

Theorem 5 provides a path to an operationalizable condition: Assumption 2 is
highly likely to be satisfied if we are given a sufficiently large number of
users in $A_{+}$ compared to the number of arms. Its proof is deferred to
Appendix X.

######  Theorem 5.

Suppose that the optimal arms associated with users $\\{m^{*}_{j}:j\in A\\}$
are independently and uniformly distributed over $A$ and user arrival rates
are of the same order. If
$|A_{+}|\geq|M|d+\max\\{|M|d,4\left(|M|\ln|M|+|M|\ln\frac{1}{\epsilon}+d\right)\\}$
holds, then $P(\\{|A_{m}\cap A_{+}|\geq d\;\forall m\in M\\})\geq 1-\epsilon$.

##  IV CFUCB algorithm

We now introduce our main algorithm we call the Counterfactual-UCB (CFUCB)
recommendation algorithm. In a typical UCB-based algorithm (e.g., [39] for the
multi-armed bandit problem), each user forms a confidence interval solely
based on her own experience, which one may call the self-experience based
confidence interval. For all users who opted in, the recommender not only
knows the user’s self-experience based confidence interval, but it can also
construct a confidence interval based solely on other users’ experiences. We
call this the counterfactual confidence interval.

Self-experience based Confidence interval. Denote by
$\overline{Y}_{j,m}(t)=\frac{\sum_{k=1}^{N_{j,m}(t)}Y_{j,m}(k)}{N_{j,m}(t)}$
the empirical mean reward of user $j$ on arm $m$, and define the width
${w}^{se}_{j,m}(t):=\sqrt{\frac{\ln N_{j}(t)}{N_{j,m}(t)}}$. Defining
$\overline{Y}_{j,m}(t)+{w}^{se}_{j,m}(t)$ as $ucb^{se}_{j,m}(t)$ and
$\overline{Y}_{j,m}(t)-{w}^{se}0_{j,m}(t)$ as $lcb^{se}_{j,m}(t)$, the self-
experienced confidence interval is
$CI^{se}_{j,m}(t):=[lcb^{se}_{j,m}(t),ucb^{se}_{j,m}(t)]$.

Counterfactual Confidence interval. Define ${A_{m}}(d,t):=\\{j\in
A_{+}:|\\{i\in A_{+}:N_{i,m}(t)>N_{j,m}(t)\\}|<d\\}$. This set includes the
top $d$ users in $A_{+}$ for arm $m$ with all ties at the bottom being
included. Since Assumption 2 implies that $|A_{+}|\geq d+1$,
$|{A_{m}}(d+1,t)|\geq d+1$. Let $E_{j,m}(t)$ be any arbitrarily chosen
$d$-size subset of ${A_{m}}(d+1,t)\setminus j$. From SCO (Assumption 1), we
are given $\\{a_{ji}\\}_{i\in E_{j,m}}$ such that $\mu_{j,m}=\sum_{i\in
E_{j,m}(t)}a_{ji}\mu_{i,m}$. Define $\widehat{Y}_{j,m}(t):=\sum_{i\in
E_{j,m}(t)}a_{ji}\overline{Y}_{i,m}(t)$ and call it the counterfactual mean
reward of user $j$ for arm $m$. The width $w^{cf}_{j,m}(t)$ of the
corresponding counterfactual confidence interval is chosen as
$w^{cf}_{j,m}(t):=\sqrt{\frac{2\ln d+4\ln
N_{j}(t)}{N_{j,m}^{\min}(t)/c_{m,t}^{2}}}$, where $c_{m,t}:=\sum_{i\in
E_{j,m}(t)}|a_{ji}|$, and $N_{j,m}^{\min}(t):=\min_{i\in
E_{j,m}(t)}N_{i,m}(t)$. The counterfactual confidence interval is defined as
$CI^{cf}_{j,m}(t):=[lcb_{j,m}^{cf}(t),ucb^{cf}_{j,m}(t)]$, where
$ucb^{cf}_{j,m}(t):=\widehat{Y}_{j,m}(t)+w^{cf}_{j,m}(t)$ and
$lcb^{cf}_{j,m}(t):=\widehat{Y}_{j,m}(t)-w^{cf}_{j,m}(t)$.

For future references, let’s restate the upper confidence bounds we defined
above:

$\displaystyle
ucb^{se}_{j,m}(t):=\overline{Y}_{j,m}(t)+w^{se}_{j,m}(t),\;ucb^{cf}_{j,m}(t):=\widehat{Y}_{j,m}(t)+w^{cf}_{j,m}(t).$
(1)

The Counterfactual UCB (CFUCB) algorithm. Let $s_{k}$ be the time of the $k$th
arrival from $A$, $a_{k}$ be the user that arrives at $s_{k}$, $m_{k}$ be the
arm pulled at $s_{k}$, and $r_{k}$ be the corresponding reward. Note that
$m_{k}$ and $r_{k}$ are known to the recommender if and only if user $a_{k}$
has opted in, i.e., $a_{k}\in A_{+}$.

1 for  _$k=1,2,\ldots$_ do

2 Observe $s_{k}$ and $a_{k}$

3 if  _$a_{k}\in A_{+}$ (i.e., $a_{k}$ is a user who opted in)_ then

4 for  _$m=1,2,\ldots,|M|$_ do

5 Compute $ucb^{se}_{(a_{k},m)}(s_{k})$ (Self-experienced upper confidence
bound) according to Eq (1)

6 Compute $ucb^{cf}_{(a_{k},m)}(s_{k})$ (counterfactual upper confidence
bound) according to Eq (1)

7
$\widetilde{ucb}_{(a_{k},m)}(s_{k})=\min(ucb^{se}_{(a_{k},m)}(s_{k}),ucb^{cf}_{(a_{k},m)}(s_{k}))$

8

9 Set $m_{k}=\arg\min_{m\in M}\\{\widetilde{ucb}_{(a_{k},m)}(s_{k})\\}$

10 Recommend user $a_{k}$ pull the arm $m_{k}$ and obtain $r_{k}$

11 Store $Y_{(a_{k},m_{k})}(N_{a_{k},m_{k}}(s_{k}))=r_{k}$ for later use in
lines 4 and 5

12

13

Algorithm 1 CFUCB Algorithm

##  V Analysis of CFUCB

We first start by describing how the confidence intervals are chosen.
Following the spirit of [39], they bound the violation probability by the
inverse square of the total number of pulls at time $t$. The proofs are
deferred to Section X.

######  Lemma 6 ([39]).

For $\epsilon\geq\sqrt{\frac{4\ln N_{j}(t)}{N_{j,m}(t)}}$,
$P(|\overline{Y}_{j,m}(t)-\mu_{j,m}|>\epsilon)\leq N_{j}(t)^{-2}$.

######  Lemma 7.

Let $c_{m,t}:=\sum_{i\in E_{j,m}(t)}|a_{i}^{(j)}|$. Then, for
$\epsilon\geq\sqrt{\frac{2\ln d+4\ln
N_{j}(t)}{N_{j,m}^{\min}(t)/c_{m,t}^{2}}}$,
$P(|\widehat{Y}_{j,m}(t)-\mu_{j,m}|>\epsilon)\leq N_{j}(t)^{-2}$.

Lemmas 8 and 9 are the key results in this paper, in that they provide
intuition of why bounded regret is achieved.

######  Lemma 8.

If $CI^{se}_{i,n}(t)$ and ${CI}^{cf}_{i,n}(t)$ both include the true mean
$\mu_{i,n}$ for all $i\in A$ and $n\in M$, user $j$ pulls arm $m$ only if
$\min\left(2\sqrt{\frac{4\ln N_{j}(t)}{N_{j,m}(t)}},2\sqrt{\frac{2\ln d+4\ln
N_{j}(t)}{N_{j,m}^{\min}(t)/c_{m,t}^{2}}}\right)\geq\Delta_{j,m}$, i.e.,
$N_{j,m}(t)\leq\frac{16\ln N_{j}(t)}{{\Delta_{j,m}}^{2}}$ and
$N^{min}_{j,m}(t)\leq\frac{8c^{2}_{m,t}(\ln d+2\ln
N_{j}(t))}{{\Delta_{j,m}}^{2}}$.

######  Lemma 9.

If $CI^{se}_{i,n}(t)$ and ${CI}^{cf}_{i,n}(t)$ both include the true mean
$\mu_{i,n}$ for all $i\in A$ and $n\in M$, then a user $j$ who arrives at time
$t$ pulls a non-optimal arm $m$, i.e., one with $\Delta_{j,m}>0$, only if

$\min_{E_{j,m}\cap A_{+}\cap A_{m}}\\{N_{i}(t)-(\sum_{n\neq
m}\frac{16}{{\Delta_{i,n}}^{2}})\ln N_{i}(t)\\}\leq\frac{8c^{2}_{m,t}(\ln
d+2\ln N_{j}(t))}{{\Delta_{j,m}}^{2}}.$ (2)

See Section X for their proofs. Lemma 9 says that the inequality (2) is a
necessary condition for a user $j$ to pull a non-optimal arm $m$. Since LHS of
growing like $N_{i}(t)$ increases far faster than the RHS of (2) growing only
like $\ln N_{j}(t)$, the inequality will soon cease to hold for all non-
optimal arms unless there exists a user $i$ in $E_{j,m}\cap A_{+}\cap A_{m}$
with $N_{i}(t)$ that increases far slower than $N_{j}(t)$. Since there is no
such $i\in E_{j,m}\cap A_{+}\cap A_{m}$ (Assumption 2), only the optimal arm
will be pulled afterwards except when the true mean $\mu_{i,n}$ is not
included $CI^{se}_{i,n}(t)\cap{CI}^{cf}_{i,n}(t)$. A concentration inequality
however assures the inclusion of the means in the confidence intervals with
high probability.

The following Proposition 1 formalizes the intuition provided above, showing
that Assumptions 1 and 2 are indeed enough to achieve bounded expected regret.
For the proof, refer to the Appendix X.

######  Proposition 1.

Under Assumptions 1 and 2, $E[Regret_{j}(T)]\leq\sum_{m\in
M}\Delta_{j,m}\left(\frac{\pi^{2}|A||M|}{6}+\frac{k\pi^{2}|A|}{6}\right)$ for
$j\in A_{+}$. Since this bound does not increase with $T$, the system expected
regret $\sum_{j\in A}E[Regret_{j}(T)]$ is bounded.

##  VI Incentive to opt in and comply

Suppose that a user $i\in A$ only cares about the asymptotic order of the
regret, and not its precise value. That is, user $i$ is indifferent between an
$f(T)$ regret and an $g(T)$ regret if and only if $f(T)=\Theta(g(T))$. We say
that such a user $i$ has asymptotic preference (defined formally in Appendix
XII). Would there be any incentive for the user $i$ to opt out or not follow
the recommendation at any time? This is a dynamic game, and the question
relates to whether opting in and following the recommendation constitutes a
Subgame Perfect Nash Equilibrium (SPNE) [40]. If all the users of $A$ have
asymptotically indifferent preferences, it is trivial that no user can
strictly improve herself by opting out or not complying to recommendation
since she already has $O(1)$ regret and there is no smaller order of regret
that can be contemplated. Hence we have the following result:

######  Theorem 10.

Under Assumption 2, for users with asymptotically indifferent preferences, the
strategy where every user opts in and complies is a Subgame Perfect Nash
Equilibrium (SPNE).

The formal formulation of this game and result are provided in the Appendix
XII.

######  Remark.

While Theorem 10 posits our result as SPNE, our result is actually much more
robust than SPNE. This is because we allow coalitional deviation as long as
Assumption 2 holds, i.e., $|E_{j,m}\cap A_{+}\cap A_{m}|\geq d$ for all $j\in
A_{+}$ and $m\in M$.

##  VII Simple simulation analysis

Figure 1: The regret of the opted in users compared to that opted out users
(200 users, 20 arms, feature vector dimension 5)

As we are suggesting a new practical setting that relaxes the ’knowledge of
$\phi$’ assumption (Assumption 1), our empirical simulation analysis can
simply be devoted to verifying the theoretical results thus far. Specifically,
we aim for the empirical demonstration of the opted-in users’ $O(1)$ expected
regret and the opted-out users’ $O(\ln T)$ regret. Our SCM oracle computes the
coefficients using the user feature vectors. Our algorithm only knows about
the coefficients.

In this experiment, we have 200 users repeatedly arriving to explore 20 arms.
Each user independently arrives according to its own renewal process with
positively truncated $i.i.d.$ Gaussian inter-arrival times. Both user and arm
feature vectors (unknown) are randomly and uniformly generated as vectors on
the surface of the $0$-centered unit sphere in $\mathbb{R}^{5}$. Rewards are
generated according to the simplified disjoint model (Section III-A), i.e.,
the reward resulting from an arm pull is the inner product of the user’s and
the pulled arm’s feature vectors plus i.i.d. $N(0,0.1)$ noise.

Figure 1 averages the results of ten experiments, with arrivals and feature
vectors newly generated for each experiment. As can be seen, the regret graph
for the opted-in users almost levels off by the time each user pulls each arm
five times on average. In contrast, the average regret of the opted-out users
grows logarithmically with $T$.

##  VIII Conclusions

In this paper, we present a theoretical study addressing the challenges in
applying recent bounded regret results [15, 27, 16] to practical recommender
systems. These challenges encompass unobservable covariates, unknown linear
representation functions, user arrival rates, and incentives to opt in. We
present an algorithm that relies on a more practical assumption than the
knowledge of linear representation functions, while still enabling bounded
regret. This algorithm also allows other practical relaxations, including
allowing very different orders of arrival rates among users.

##  IX Related works

The issue of not knowing $\phi$ in linear contextual bandits has been studied
in the representation learning literature. Recent studies [41, 42] examined
the linear contextual bandit representation selection problem, i.e., learning
to choose a good representation $\phi$ from a finite set of known
representations $\Phi$. However, it remains challenging for practical
recommender systems applications to assume the knowledge of $\Phi$. In [43],
they study $\phi$ learning problem beyond representation selection; however,
their setting and results are not directly related to online learning
settings.

At the intersection of Synthetic Control Methods (SCM) and bandit methods,
recent studies [44, 45, 46] have attempted to develop online learning versions
of SCM. Compared to these works, our focus is not on developing a good SCM
method itself, but on assuming existence of a good SCM method. To the best of
our knowledge, this work is the first to observe that what is achieved by SCM
is a relaxation of what is assumed in the linear contextual bandit models.

On the subject of incentive issues, there are many works on incentive
constraints in coordinating exploration. [47] studies Bayesian perspectives of
incentivizing myopic users with a private context to explore, with the goal of
achieving $O\left(\log^{3}(T)\right)$ regret. [48] considers incentive-
compatible exploration coordination in a setting opposite to ours: the context
is private, but the mean reward associated with each arm is known. In this
work, we illustrate that opting in (revelation of private information) is
Subgame Perfect Nash Equilibrium (SPNE) and achieve $O(1)$ regret.

## References

  * [1] Harald Steck et al.  “Deep learning for recommender systems: A Netflix case study”  In _AI Magazine_ 42.3, 2021, pp. 7–18
  * [2] Daniel Fleder and Kartik Hosanagar  “Blockbuster culture’s next rise or fall: The impact of recommender systems on sales diversity”  In _Management science_ 55.5 INFORMS, 2009, pp. 697–712
  * [3] Dokyun Lee and Kartik Hosanagar  “How do recommender systems affect sales diversity? A cross-category investigation via randomized field experiment”  In _Information Systems Research_ 30.1 INFORMS, 2019, pp. 239–259
  * [4] Walid Bendada, Guillaume Salha and Théo Bontempelli  “Causal personalization in music streaming apps with contextual bandits”  In _ACM RecSys conference_ , 2020, pp. 420–425
  * [5] Liang Tang, Yexi Jiang, Lei Li and Tao Li  “Ensemble contextual bandits for personalized recommendation”  In _ACM RecSys conference_ , 2014, pp. 73–80
  * [6] Liang Tang et al.  “Personalized recommendation via parameter-free contextual bandits”  In _ACM SIGIR conference_ , 2015, pp. 323–332
  * [7] Li Zhou and Emma Brunskill  “Latent contextual bandits and their application to personalized recommendations for new users”  In _arXiv preprint arXiv:1604.06743_ , 2016
  * [8] Weihao Kong, Emma Brunskill and Gregory Valiant  “Sublinear optimal policy value estimation in contextual bandits”  In _AISTATS_ , 2020, pp. 4377–4387  PMLR
  * [9] Alberto Bietti, Alekh Agarwal and John Langford  “A contextual bandit bake-off”  In _The Journal of Machine Learning Research_ 22.1 JMLRORG, 2021, pp. 5928–5976
  * [10] Dylan Foster and Alexander Rakhlin  “Beyond ucb: Optimal and efficient contextual bandits with regression oracles”  In _ICML_ , 2020, pp. 3199–3210  PMLR
  * [11] Lihong Li, Wei Chu, John Langford and Robert E Schapire  “A contextual-bandit approach to personalized news article recommendation”  In _ACM WWW conference_ , 2010, pp. 661–670
  * [12] Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey and Guido Imbens  “Estimation considerations in contextual bandits”  In _arXiv preprint arXiv:1711.07077_ , 2017
  * [13] Wei Chu, Lihong Li, Lev Reyzin and Robert Schapire  “Contextual bandits with linear payoff functions”  In _AISTATS_ , 2011, pp. 208–214  JMLR WorkshopConference Proceedings
  * [14] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi and Yunzong Xu  “Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective”  In _arXiv preprint arXiv:2010.03104_ , 2020
  * [15] Botao Hao, Tor Lattimore and Csaba Szepesvari  “Adaptive exploration in linear contextual bandit”  In _AISTATS_ , 2020, pp. 3536–3545  PMLR
  * [16] Matteo Papini et al.  “Leveraging good representations in linear contextual bandits”  In _ICML_ , 2021, pp. 8371–8380  PMLR
  * [17] Omar Besbes, Yonatan Gur and Assaf Zeevi  “Stochastic multi-armed-bandit problem with non-stationary rewards”  In _Advances in neural information processing systems_ 27, 2014
  * [18] Yoan Russac, Claire Vernade and Olivier Cappé  “Weighted linear bandits for non-stationary environments”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [19] Yoan Russac, Olivier Cappé and Aurélien Garivier  “Algorithms for non-stationary generalized linear bandits”  In _arXiv preprint arXiv:2003.10113_ , 2020
  * [20] Peng Zhao, Lijun Zhang, Yuan Jiang and Zhi-Hua Zhou  “A simple approach for non-stationary linear bandits”  In _AISTATS_ , 2020, pp. 746–755  PMLR
  * [21] Haipeng Luo, Chen-Yu Wei, Alekh Agarwal and John Langford  “Efficient contextual bandits in non-stationary worlds”  In _Conference On Learning Theory_ , 2018, pp. 1739–1776  PMLR
  * [22] Yifang Chen, Chung-Wei Lee, Haipeng Luo and Chen-Yu Wei  “A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free”  In _Conference on Learning Theory_ , 2019, pp. 696–726  PMLR
  * [23] Su Jia, Qian Xie, Nathan Kallus and Peter I Frazier  “Smooth Non-Stationary Bandits”  In _arXiv preprint arXiv:2301.12366_ , 2023
  * [24] Chao Qin and Daniel Russo  “Adaptivity and confounding in multi-armed bandit experiments”  In _arXiv preprint arXiv:2202.09036_ , 2022
  * [25] Tanner Fiez et al.  “Adaptive experimental design and counterfactual inference”  In _arXiv preprint arXiv:2210.14369_ , 2022
  * [26] Paul R Rosenbaum and Donald B Rubin  “Assessing sensitivity to an unobserved binary covariate in an observational study with binary outcome”  In _Journal of the RSS: Series B_ 45.2 Wiley Online Library, 1983, pp. 212–218
  * [27] Weiqiang Wu, Jing Yang and Cong Shen  “Stochastic linear contextual bandits with diverse contexts”  In _AISTATS_ , 2020, pp. 2392–2401  PMLR
  * [28] Alberto Abadie, Alexis Diamond and Jens Hainmueller  “Synthetic control methods for comparative case studies: Estimating the effect of California’s tobacco control program”  In _Journal of the American statistical Association_ 105.490 Taylor & Francis, 2010, pp. 493–505
  * [29] Alberto Abadie and Guido W Imbens  “Bias-corrected matching estimators for average treatment effects”  In _Journal of Business & Economic Statistics_ 29.1 Taylor & Francis, 2011, pp. 1–11
  * [30] Nikolay Doudchenko and Guido W Imbens  “Balancing, regression, difference-in-differences and synthetic control methods: A synthesis”, 2016
  * [31] Muhammad Amjad, Devavrat Shah and Dennis Shen  “Robust synthetic control”  In _The Journal of Machine Learning Research_ 19.1 JMLR. org, 2018, pp. 802–852
  * [32] Alberto Abadie  “Using synthetic controls: Feasibility, data requirements, and methodological aspects”  In _Journal of Economic Literature_ 59.2 American Economic Association 2014 Broadway, Suite 305, Nashville, TN 37203-2425, 2021, pp. 391–425
  * [33] Eli Ben-Michael, Avi Feller and Jesse Rothstein  “The augmented synthetic control method”  In _Journal of the American Statistical Association_ 116.536 Taylor & Francis, 2021, pp. 1789–1803
  * [34] Bruno Ferman  “On the properties of the synthetic control estimator with many periods and many controls”  In _Journal of the American Statistical Association_ 116.536 Taylor & Francis, 2021, pp. 1764–1772
  * [35] Susan Athey and Guido W Imbens  “The state of applied econometrics: Causality and policy evaluation”  In _Journal of Economic perspectives_ 31.2 American Economic Association 2014 Broadway, Suite 305, Nashville, TN 37203-2418, 2017, pp. 3–32
  * [36] Geoffrey Grimmett and David Stirzaker  “Probability and random processes”  Oxford university press, 2020
  * [37] Tim Ingham  “Over 60,000 tracks are now uploaded to Spotify every day. that’s nearly one per second.”  In _Music Business Worldwide_ , 2021  URL: https://www.musicbusinessworldwide.com/over-60000-tracks-are-now-uploaded-to-spotify-daily-thats-nearly-one-per-second/
  * [38] Robert M Corless et al.  “On the Lambert W function”  In _Advances in Computational mathematics_ 5 Springer, 1996, pp. 329–359
  * [39] Peter Auer  “Using confidence bounds for exploitation-exploration trade-offs”  In _Journal of Machine Learning Research_ 3.Nov, 2002, pp. 397–422
  * [40] Drew Fudenberg and Jean Tirole  “Game theory”  MIT press, 1991
  * [41] Andrea Tirinzoni et al.  “Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees”  In _arXiv preprint arXiv:2210.13083_ , 2022
  * [42] Andrea Tirinzoni, Matteo Pirotta and Alessandro Lazaric  “On the Complexity of Representation Learning in Contextual Linear Bandits”  In _AISTATS_ , 2023, pp. 7871–7896  PMLR
  * [43] Simon S Du et al.  “Few-shot learning via learning the representation, provably”  In _arXiv preprint arXiv:2002.09434_ , 2020
  * [44] Vivek Farias, Ciamac Moallemi, Tianyi Peng and Andrew Zheng  “Synthetically controlled bandits”  In _arXiv preprint arXiv:2202.07079_ , 2022
  * [45] Anish Agarwal, Devavrat Shah and Dennis Shen  “Synthetic interventions”  In _arXiv preprint arXiv:2006.07691_ , 2020
  * [46] Jiafeng Chen  “Synthetic control as online linear regression”  In _Econometrica_ 91.2 Wiley Online Library, 2023, pp. 465–491
  * [47] Bangrui Chen, Peter Frazier and David Kempe  “Incentivizing exploration by heterogeneous users”  In _Conference On Learning Theory_ , 2018, pp. 798–818  PMLR
  * [48] Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins and Zhiwei Steven Wu  “Bayesian exploration with heterogeneous agents”  In _The World Wide Web Conference_ , 2019, pp. 751–761
  * [49] Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer  “Finite-time analysis of the multiarmed bandit problem”  In _Machine learning_ 47.2 Springer, 2002, pp. 235–256
  * [50] Robert M Corless et al.  “On the LambertW function”  In _Advances in Computational mathematics_ 5.1 Springer, 1996, pp. 329–359

##  X Proofs

###### Proof of Lemma 4.

Let $P(N_{i}(t)<q_{ij,m}(N_{j}(t)))=h_{j,m}(t)$. Then

$\displaystyle\int h_{j,m}F_{S_{j}(n)}$ (5)
$\displaystyle=\int_{[0,n(\theta^{j}-\epsilon))}h_{j,m}F_{S_{j}(n)}+\int_{[n(\theta^{j}-\epsilon),\infty)}h_{j,m}F_{S_{j}(n)}$
$\displaystyle\leq h_{j,m}(0^{+})\times
e^{-2n\epsilon^{2}}+h_{j,m}(n(\theta^{j}-\epsilon))\times 1$
$\displaystyle=2|A|e^{-2n\epsilon^{2}}+h_{m}^{(j)}(n(\theta^{j}-\epsilon))$
$\displaystyle=2|A|(\exp({-2n\epsilon^{2}})+\exp(-2\frac{(n(\theta^{j}-\epsilon)-\lceil
q_{ij,m}(\frac{n(\theta^{j}-\epsilon)}{\theta^{j}-\epsilon^{j}})\rceil\theta_{\max})^{2}}{\lceil
q_{ij,m}(\frac{n(\theta^{j}-\epsilon)}{\theta^{j}-\epsilon^{j}})\rceil})$
$\displaystyle+\exp(-2\frac{{\epsilon^{j}}^{2}}{\theta^{j}-\epsilon^{j}}n(\theta^{j}-\epsilon)))$
$\displaystyle=2|A|\left(2\exp({-2n\epsilon^{2}})+\exp(-2\frac{(n(\theta^{j}-\epsilon)-\lceil
q_{ij,m}(n)\rceil\theta_{\max})^{2}}{\lceil q_{ij,m}(n)\rceil})\right)$
$\displaystyle(\mbox{for simplicity, we fix }\epsilon^{j}=\epsilon)$
$\displaystyle=O(\frac{1}{n^{2}}).$

Above,
(5) holds because $P(S_{n}^{(j)}\leq n(\theta^{j}-\epsilon))\leq
e^{-2n\epsilon^{2}}\mbox{ and since }g_{m}^{(j)}\mbox{ is a decreasing
function}$,
(5) holds because of Lemma 11 below,
(5) holds because

$\displaystyle\left(n(\theta^{j}-\epsilon))-\lceil
q_{ij,m}(n)\rceil\theta_{\max}\right)^{2}\geq\lceil
q_{ij,m}(n)\rceil^{2}\mbox{ for all }n\geq N\mbox{ for some }N$ (6)
$\displaystyle(\Rightarrow)(n(\theta^{j}-\epsilon))-\lceil
q_{ij,m}(n)\rceil\theta_{\max})^{2}\geq\ln(n)\lceil q_{ij,m}(n)\rceil\mbox{
for all }n\geq N$ (7)
$\displaystyle(\Rightarrow)\exp(-2\frac{(n(\theta^{j}-\epsilon)-\lceil
q_{ij,m}(n)\rceil\theta_{\max})^{2}}{\lceil
q_{ij,m}(n)\rceil})=O(\frac{1}{n^{2}}),$

∎

######  Lemma 11.

$h_{j,m}(t):=P(N^{(i)}(t)<q_{ij,m}(N^{(j)}(t)))\leq|A|\left(\exp(-2\frac{(t-\lceil
q_{ij,m}(\frac{t}{\theta^{j}-\epsilon^{j}})\rceil\theta_{\max})^{2}}{\lceil
q_{ij,m}(\frac{t}{\theta^{j}-\epsilon^{j}})\rceil})+\exp({-2\frac{{\epsilon^{j}}^{2}}{\theta^{j}-\epsilon^{j}}t})\right)$.

###### Proof of Lemma 11.

$\displaystyle h_{j,m}(t):=P(N^{(i)}(t)<q_{ij,m}(N^{(j)}(t)))$ $\displaystyle\
\ \ \ \ \ =\int P(N^{(i)}(t)<q_{ij,m}(n))\;dF_{N^{(j)}(t)}(n)$ $\displaystyle\
\ \ \ \ \ \leq\int P(N^{(i)}(t)<q_{ij,m}(n))\;dF_{N^{(j)}(t)}(n)$
$\displaystyle\ \ \ \ \ \ =\int P(S^{(i)}_{\lceil
q_{ij,m}(n)\rceil)}>t)\;dF_{N^{(j)}(t)}(n)$ $\displaystyle\ \ \ \ \ \
=(\int_{[0,\frac{t}{\theta^{j}-\epsilon^{j}}]}P(S^{(i)}_{\lceil
q_{ij,m}(n)\rceil)}>t)\;dF_{N^{(j)}(t)}(n)$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \
\;+\int_{(\frac{t}{\theta^{j}-\epsilon^{j}},\infty)}P(S^{(i)}_{\lceil
q_{ij,m}(n)\rceil)}>t)\;dF_{N^{(j)}(t)}(n))$ $\displaystyle\ \ \ \ \ \
\stackrel{{\scriptstyle(c)}}{{\leq}}\left(P(S^{(i)}_{\lceil
q_{ij,m}(\frac{t}{\theta^{j}-\epsilon^{j}})\rceil)}>t)\times
1+1\times\exp({-2\frac{{\epsilon^{j}}^{2}}{\theta^{j}-\epsilon^{j}}t})\right)$
(8) $\displaystyle\ \ \ \ \ \ =\left(\exp(-2\frac{(t-\lceil
q_{ij,m}(\frac{t}{\theta^{j}-\epsilon^{j}})\rceil\theta_{i})^{2}}{\lceil
q_{ij,m}(\frac{t}{\theta^{j}-\epsilon^{j}})\rceil})+\exp({-2\frac{{\epsilon^{j}}^{2}}{\theta^{j}-\epsilon^{j}}t})\right)$
$\displaystyle\ \ \ \ \ \ \leq|A|\left(\exp(-2\frac{(t-\lceil
q_{ij,m}(\frac{t}{\theta^{j}-\epsilon^{j}})\rceil\theta_{\max})^{2}}{\lceil
q_{ij,m}(\frac{t}{\theta^{j}-\epsilon^{j}})\rceil})+\exp({-2\frac{{\epsilon^{j}}^{2}}{\theta^{j}-\epsilon^{j}}t})\right).$
(9)

Above,

  * •

$\theta_{\max}:=\max_{i\in A}\theta_{i}.$

  * •

The inequality (c) of (8) holds because we apply left tail Hoeffding
inequality, i.e.,

$\displaystyle P\left(S_{n}^{(j)}\leq
n(\theta^{j}-\epsilon^{j})\right)=P\left(N^{(j)}(n(\theta^{j}-\epsilon^{j}))\geq
n\right)\leq e^{-2n\epsilon^{j2}}$ $\displaystyle\Leftrightarrow
P\left(N^{(j)}(t)\geq\frac{t}{\theta^{j}-\epsilon^{j}}\right)\leq
e^{-2\frac{\epsilon^{j2}}{\theta^{j}-\epsilon^{j}}t}$

and $\lceil q_{ij,m}(n)\rceil$ is an increasing function of $n$.

∎

###### Proof of Theorem 5.

For simplicity, we denote $|A_{+}|=a$ and $|M|=b$. Let $I_{m}$ be the
indicator random variable for the event $\\{|A_{m}|<d+1\\}$, and
$I:=\sum_{m\in M}I_{m}$. What we want is to upper bound $P(I>0)$ by
$\epsilon$. Note that

$\displaystyle P(I>0)=P(I\geq 1)$ $\displaystyle\leq E[I]\ \ \ \mbox{ (because
of Markov's inequality) }$ $\displaystyle=bE[I_{1}]$
$\displaystyle=bP(I_{1}=1)$
$\displaystyle=b\sum_{k=0}^{d}\binom{a}{k}\left(1-\frac{1}{b}\right)^{a-k}\left(\frac{1}{b}\right)^{k}$
$\displaystyle\leq
b\sum_{k=0}^{d}\binom{a}{k}\left(1-\frac{1}{b}\right)^{a-d}\left(\frac{1}{b}\right)^{k}$
$\displaystyle\leq
b\sum_{k=0}^{d}\frac{a^{k}}{k!}{\exp}(-\frac{a-d}{b})\left(\frac{1}{b}\right)^{k}\mbox{
(because }\binom{a}{k}\leq\frac{a^{k}}{k!}\mbox{, and }1+x\leq e^{x})$
$\displaystyle={\exp}\left(\frac{d}{b}\right)\sum_{k=0}^{d}\frac{1}{k!}\left(\frac{a}{b}\right)^{k}{\exp}\left(-\frac{a}{b}\right)$
$\displaystyle=b{\exp}\left(\frac{d}{b}\right)P\left(Z\leq d\right)\mbox{,
where }Z\sim Poi(\frac{a}{b})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}b{\exp}\left(\frac{d}{b}\right)\exp\left(-\frac{1}{2}\frac{b}{a}\frac{\left(a-bd\right)^{2}}{b^{2}}\right)$
(10)
$\displaystyle=b{\exp}\left(\frac{1}{b}\left(d-\frac{\left(a-bd\right)^{2}}{2a}\right)\right)$
$\displaystyle={\exp}\left(\ln
b-\frac{1}{b}\left(\frac{\left(a-bd\right)^{2}}{2a}-d\right)\right).$ (11)

Above, the inequality $(a)$ of (10) holds because $Z\sim Poisson(\lambda)$,
$\operatorname{Pr}[Z\leq\lambda-x]\leq e^{-\frac{x^{2}}{2\lambda}}$ for $0\leq
x\leq\lambda$, where in our case $\frac{a}{b}\geq d$ as assumed,
$\lambda=\frac{a}{b}$, $\lambda-x=d$ and $x=\frac{a}{b}-d=\frac{a-bd}{b}$).

Let us further assume that $a\geq(1+\eta)bd$. Now

$\displaystyle a\geq(1+\eta)bd$ $\displaystyle(\Leftrightarrow)\ \ \
(1+\eta)(a-bd)\geq(1+\eta)a-a=\eta a$ $\displaystyle(\Leftrightarrow)\ \ \
a\leq(a-bd)\frac{(1+\eta)}{\eta}.$ (12)

Then,

$\displaystyle P(I>0)\leq\epsilon$ $\displaystyle(\Leftarrow)\ \ \
{\exp}\left(\ln
b-\frac{1}{b}\left(\frac{\left(a-bd\right)^{2}}{2a}-d\right)\right)\leq\epsilon\
\ \mbox{ (because of (\ref{eq:6}))}$ $\displaystyle(\Leftrightarrow)\ \ \
\exp\left(-\frac{(\frac{\left(a-bd\right)^{2}}{2a}-d)-b\ln
b}{b}\right)\leq\epsilon$ $\displaystyle(\Leftrightarrow)\ \ \
\frac{\left(a-bd\right)^{2}}{2a}\geq b\ln b+b\ln\frac{1}{\epsilon}+d$
$\displaystyle(\Leftarrow)\ \ \ a-bd\geq\frac{2(1+\eta)}{\eta}\left(b\ln
b+b\ln\frac{1}{\epsilon}+d\right)\ \ \mbox{ (because of (\ref{eq:7}))}$ (13)

∎

###### Proof of Lemma 6..

This follows from the 1-sub-Gaussian tail bound
$P(|\overline{Y}_{j,m}(t)-\mu_{j,m}|>\epsilon)\leq
2exp({-N_{i,m}(t)\epsilon^{2}/2})$. Since we want to upper bound
$P(|\overline{Y}_{j,m}(t)-\mu_{j,m}|>\epsilon)\leq$ by $N_{j}(t)^{-2}$, the
value of $\epsilon$ that renders 2$exp({-N_{i,m}(t)\epsilon^{2}}/2)\leq
N_{j}(t)^{-2}$ will suffice. This yields $\epsilon\geq\sqrt{\frac{4\ln
N_{j}(t)}{N_{j,m}(t)}}$. ∎

###### Proof of Lemma 7..

$\displaystyle P(|\widehat{Y}_{j,m}(t)-\mu_{j,m}|>\epsilon)$ $\displaystyle\ \
\ \ \ \ =1-P(|\widehat{Y}_{j,m}(t)-\mu_{j,m}|\leq\epsilon)$ $\displaystyle\ \
\ \ \ \ \leq
1-\Pi_{i\in{E_{j,m}(t)}}P(|a_{ji}||{Y}_{i,m}(t)-\mu_{i,m}|\leq|a_{i}^{(j)}|\frac{\epsilon}{c_{m,t}})$
$\displaystyle\ \ \ \ \ \ =1-\Pi_{i\in
E_{j,m}(t)}(1-P(|{Y}_{i,m}(t)-\mu_{i,m}|>\frac{\epsilon}{c_{m,t}}))$
$\displaystyle\ \ \ \ \ \ \leq 1-\Pi_{i\in
E_{j,m}(t)}((1-\exp(\frac{-N_{i,m}(t)\epsilon^{2}}{2c_{m,t}^{2}})))$
$\displaystyle\ \ \ \ \ \ \leq 1-\Pi_{i\in
E_{j,m}(t)}(1-\exp(\frac{-N_{j,m}^{\min}(t)\epsilon^{2}}{2c_{m,t}^{2}})\;\;(\because
N_{j,m}^{\min}(t):=\min_{i\in E_{j,m}(t)}N_{i,m}(t))$ $\displaystyle\ \ \ \ \
\ =1-(1-\exp(\frac{-N_{j,m}^{\min}(t)\epsilon^{2}}{2c_{m,t}^{2}}))^{d}$
$\displaystyle\ \ \ \ \ \ \leq
d\exp(\frac{-N_{j,m}^{\min}(t)\epsilon^{2}}{2c_{m,t}^{2}}).$

Therefore,
$\epsilon\geq\sqrt{\frac{2\ln(d/\delta)}{N_{j,m}^{\min}(t)/c_{m,t}^{2}}}$
implies $P(|\widehat{Y}_{j,m}(t)-\mu_{j,m}|>\epsilon)\leq\delta$.

Since we want CI with $\delta=1/N_{j}(t)^{-2}$ following the spirit of [49],
CI with width $\sqrt{\frac{2\ln d+4\ln
N_{j}(t)}{N_{j,m}^{\min}(t)/c_{m,t}^{2}}}$ works.

∎

###### Proof of Lemma 8.

Denote the optimal arm for user $j$ as arm $m^{*}_{j}$. According to Algorithm
1, $\\{$user $j$ pulls arm
$m\\}\subseteq\\{\widetilde{\text{ucb}}_{j,m}(t)\geq\widetilde{\text{ucb}}_{j,m^{*}_{j}}(t)\\}$.
Note that
$\widetilde{\text{lcb}}_{j,m}(t)\leq\mu_{j,m}\leq\widetilde{\text{ucb}}_{j,m}(t)$
and
$\widetilde{\text{lcb}}_{j,m^{*}_{j}}(t)\leq\mu_{j,m^{*}_{j}}\leq\widetilde{\text{ucb}}_{j,m^{*}_{j}}(t)$
holds according to the assumption that under the assumption that all true
means are within CIs. Therefore, $\\{$user $j$ pulls arm
$m\\}\subseteq\\{\widetilde{\text{lcb}}_{j,m}(t)\leq\mu_{j,m},\mu_{j,m}\leq\mu_{j,m^{*}},\mu_{j,m^{*}}\leq\widetilde{\text{ucb}}_{j,m^{*}_{j}}(t),\widetilde{\text{ucb}}_{j,m^{*}_{j}}(t)\leq\widetilde{\text{ucb}}_{j,m}(t)\\}$
$=$
$\\{\widetilde{\text{lcb}}_{j,m}(t)\leq\mu_{j,m}\leq\mu_{j,m^{*}_{j}}\leq\widetilde{\text{ucb}}_{j,m}(t)\\}=\\{\mu_{j,m},\mu_{j,m^{*}_{j}}\in
CI^{se}_{j,m}(t)\cap{CI}^{cf}_{j,m}(t)\\}$. Note that
$\\{\mu_{j,m},\mu_{j,m^{*}_{j}}\in
CI^{se}_{j,m}(t)\cap{CI}^{cf}_{j,m}(t)\\}\subseteq\\{\min(2w^{se}_{j,m}(t),2w^{cf}_{j,m}(t))\geq\Delta_{j,m}\\}$.
Therefore, under the assumption that all true means are within CIs, user $j$
pulls arm $m$ only if
$\min(2w^{se}_{j,m}(t),2w^{cf}_{j,m}(t))\geq\Delta_{j,m}$ holds. Combining
this with Lemma 6 and 7 yields the result. ∎

###### Proof of Lemma 9..

Fix user $j$ and arm $m$. Note that for any arm $i\in A$,
$N_{i,m}(t)=N_{i}(t)-\sum_{n\in M\setminus m}N_{i,n}(t)$. Let $t^{n}$ be the
last time prior to $t$ at which a non-optimal arm $n$ is played by user $i$.
Then $N_{i,n}(t)=N_{i,n}(t^{n})\leq\frac{16\ln
N_{i}(t^{n})}{{\Delta_{i,n}}^{2}}\leq\frac{16\ln
N_{i}(t)}{{\Delta_{i,n}}^{2}}$ holds by Lemma 8. Therefore, for user $i\in
A_{m}$, for arm $m$, $N_{i,m}(t)\geq N_{i}(t)-(\sum_{n\neq
m}\frac{16}{{\Delta_{i,n}}^{2}})\ln N_{i}(t)$. By the Assumption (2),
$|E_{j,m}\cap A_{+}\cap A_{m}|\geq d$ holds, and therefore
$N_{j,m}^{\min}(t)\geq N_{i,m}(t)$ holds for some $i\in A_{j,m}$. Therefore,
$N_{j,m}^{\min}(t)\geq N_{i,m}(t)\geq N_{i}(t)-(\sum_{n\neq
m}\frac{16}{{\Delta_{i,n}}^{2}})\ln N_{i}(t)$ for some $i\in E_{j,m}\cap
A_{+}\cap A_{m}$. That is, $N_{j,m}^{\min}(t)\geq\min_{E_{j,m}\cap A_{+}\cap
A_{m}}\\{N_{i}(t)-(\sum_{n\neq m}\frac{16}{{\Delta_{i,n}}^{2}})\ln
N_{i}(t)\\}$. Substituting this into
$N^{(\min)}_{j,m}(t)\leq\frac{8c^{2}_{m,t}(\ln
d+2N_{j}(t))}{{\Delta_{j,m}}^{2}}$ from Lemma 8, it can be seen that arm $m$
is pulled by user $j$ only when $\min_{E_{j,m}\cap A_{+}\cap
A_{m}}\\{N_{i}(t)-(\sum_{n\neq m}\frac{16}{{\Delta_{i,n}}^{2}})\ln
N_{i}(t)\\}\leq\frac{8c^{2}_{m,t}(\ln d+2N_{j}(t))}{{\Delta_{j,m}}^{2}}$. ∎

###### Proof of Proposition 1..

Let $G_{j,m}:=\\{$User $j$ arrives at time $t$ and pulls a non-optimal arm
$m\\}$ and $V_{t}:=\\{\mu_{i,n}\in CI^{se}_{i,n}(t)\cap CI^{cf}_{i,n}(t)\
\forall i\in A_{m},n\in M\\}$ as $V(t)$. Let $P(G_{j,m}(t)|V(t))=g_{j,m}(t)$.
Then,

$\displaystyle E[Regret_{j}(T)]=\sum_{m\in M\setminus
m^{*}_{j}}\Delta_{j,m}E[\text{\\# of user $j$'s non-optimal arm $m$ pulls
before $T$}]$ $\displaystyle\ \ \ \ \ \ \ =\sum_{m\in M\setminus
m^{*}_{j}}\Delta_{j,m}\sum_{n=1}^{\infty}E[1_{G_{j,m}(S_{n,j})}1_{S_{n,j}\leq
T}]$ $\displaystyle\ \ \ \ \ \ \ =\sum_{m\in M\setminus
m^{*}_{j}}\Delta_{j,m}\sum_{n=1}^{\infty}E[E[1_{G_{j,m}(S_{n,j})}1_{S_{n,j}\leq
T}|S_{n,j}]]$ $\displaystyle\ \ \ \ \ \ \ =\sum_{m\in M\setminus
m^{*}_{j}}\Delta_{j,m}(\sum_{n=1}^{\infty}E[E[1_{G_{j,m}(S_{n,j})}1_{S_{n,j}\leq
T}|V(S_{n,j})^{c},S_{n,j}]P(V(S_{n,j})^{c}|S_{n,j})+$ $\displaystyle\ \ \ \ \
\ \ \ \ \ \ \ E[1_{G_{j,m}(S_{n,j})}1_{S_{n,j}\leq
T}|V(S_{n,j}),S_{n,j}]P(V(S_{n,j})|S_{n,j})])$ $\displaystyle\ \ \ \ \ \ \
\leq\sum_{m\in M\setminus
m^{*}_{j}}\Delta_{j,m}\left(\sum_{n=1}^{\infty}E[P(V(S_{n,j})^{c}|S_{n,j})]+\sum_{n=1}^{\infty}E[E[1_{G_{j,m}(S_{n,j})}1_{S_{n,j}\leq
T}|V(S_{n,j}),S_{n,j}]]\right)$ $\displaystyle\ \ \ \ \ \ \ \leq\sum_{m\in
M\setminus
m^{*}_{j}}\Delta_{j,m}\left(\frac{\pi^{2}|A||M|}{6}+\sum_{n=1}^{\infty}E[E[1_{G_{j,m}(S_{n,j})}|V(S_{n,j}),S_{n,j}]\right)$
$\displaystyle\ \ \ \ \ \ \ \sum_{m\in M\setminus
m^{*}_{j}}\Delta_{j,m}\left(\frac{\pi^{2}|A||M|}{6}+\sum_{n=1}^{\infty}E[P({G_{j,m}(S_{n,j})}|V(S_{n,j}),S_{n,j}]\right)$
$\displaystyle\ \ \ \ \ \ \ \ =\sum_{m\in M\setminus
m^{*}_{j}}\Delta_{j,m}\left(\frac{\pi^{2}|A||M|}{6}+\sum_{n=1}^{\infty}\int_{0}^{+\infty}g_{j,m}(t)dF^{(n)}_{j}(t)\right)$
$\displaystyle\ \ \ \ \ \ \ \ \stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{m\in
M\setminus
m^{*}_{j}}\Delta_{j,m}\left(\frac{\pi^{2}|A||M|}{6}+\sum_{n=1}^{\infty}\int_{0}^{+\infty}\sum_{i\in
E_{j,m}\cap A_{+}\cap A_{m}}P(N_{i}(t)\leq
q_{ij,m}(N_{i}(t)))\;\;dF^{(n)}_{j}(t)\right)$ (14) $\displaystyle\ \ \ \ \ \
\ \ \ =\sum_{m\in M\setminus
m^{*}_{j}}\Delta_{j,m}\left(\frac{\pi^{2}|A||M|}{6}+\sum_{i\in E_{j,m}\cap
A_{+}\cap A_{m}}\sum_{n=1}^{\infty}\int_{0}^{+\infty}P(N_{i}(t)\leq
q_{ij,m}(N_{i}(t)))\;\;dF^{(n)}_{j}(t)\right)$ $\displaystyle\ \ \ \ \ \ \ \ \
\leq\sum_{m\in M\setminus
m^{*}_{j}}\Delta_{j,m}\left(\frac{\pi^{2}|A||M|}{6}+\sum_{i\in E_{j,m}\cap
A_{+}\cap
A_{m}}\sum_{n=1}^{\infty}k\frac{1}{n^{2}}\right)\;\;(\because\text{Assumption
\ref{ass: Arrivalcondition}})$ $\displaystyle\ \ \ \ \ \ \ \ \ \leq\sum_{m\in
M\setminus
m^{*}_{j}}\Delta_{j,m}\left(\frac{\pi^{2}|A||M|}{6}+\frac{k\pi^{2}|A|}{6}\right)=\sum_{m\in
M}\Delta_{j,m}\left(\frac{\pi^{2}|A||M|}{6}+\frac{k\pi^{2}|A|}{6}\right).$

Above, inequality (a) of equation (14) is from

$\displaystyle g_{j,m}(t)\leq P(\\{\min_{E_{j,m}\cap A_{+}\cap
A_{m}}\\{N_{i}(t)-(\sum_{n\neq m}\frac{16}{{\Delta_{i,n}}^{2}})\ln
N_{i}(t)\\}\leq\frac{8c^{2}_{m,t}(\ln d+2\ln
N_{j}(t))}{{\Delta_{j,m}}^{2}}\\})\;\;(\because\text{Lemma
\ref{lemma:WrongArmCond}})$ $\displaystyle\ \ \ \ \ \ \ \ \leq\sum_{i\in
E_{j,m}\cap A_{+}\cap A_{m}}P(\\{N_{i}(t)-(\sum_{n\neq
m}\frac{16}{{\Delta_{i,n}}^{2}})\ln N_{i}(t)\leq\frac{8c^{2}_{m,t}(\ln d+2\ln
N_{j}(t))}{{\Delta_{j,m}}^{2}}\\})$ $\displaystyle\ \ \ \ \ \ \ \
\leq\sum_{i\in E_{j,m}\cap A_{+}\cap A_{m}}P(N_{i}(t)\leq
q_{ij,m}(N_{i}(t)))\;\;(\because\text{Lemma \ref{Lambert}})$

∎

##  XI Function $q_{ij,m}$ in Section III-B: details

######  Lemma 12.

For $A,B,C>0$, $Ay-B\ln y<C\ln(\frac{x}{d})$ is satisfied only if
$y<-\frac{B}{A}\mathcal{W}_{-1}\left(-\frac{A}{B}(\frac{x}{d})^{-\frac{C}{B}}\right)$,
where $\mathcal{W}_{-1}$ denotes the lower branch of the Lambert $W$-function
[50].

###### Proof of Lemma 12.

For $A,B,C>0$, $\frac{A}{C}y-\frac{B}{C}\ln y<\ln(\frac{x}{d})\iff
y^{-\frac{B}{C}}e^{\frac{A}{C}y}<(\frac{x}{d})\iff
ye^{-\frac{A}{B}y}>(\frac{x}{d})^{-\frac{C}{B}}\iff-\frac{A}{B}ye^{-\frac{A}{B}y}<-\frac{A}{B}(\frac{x}{d})^{-\frac{C}{B}}\iff-\frac{B}{A}\mathcal{W}_{0}\left(-\frac{A}{B}(\frac{x}{d})^{-\frac{C}{B}}\right)<y<-\frac{B}{A}\mathcal{W}_{-1}\left(-\frac{A}{B}(\frac{x}{d})^{-\frac{C}{B}}\right)$
where $\mathcal{W}_{0}$ denotes the principal branch of the Lambert
$W$-function. Therefore, $Ay-B\ln y<C\ln(\frac{x}{d})$ holds only if
$y<-\frac{B}{A}\mathcal{W}_{-1}\left(-\frac{A}{B}(\frac{x}{d})^{-\frac{C}{B}}\right)$.
∎

In the present case, $y=N_{i}(t)$, $x=N_{j}(t)$, $A=1$, $B=\sum_{n\neq
m}\frac{16}{{\Delta_{i,n}}^{2}}$ and
$C=\frac{16c^{2}_{m,t}}{{\Delta_{j,m}}^{2}}$. Define $q_{ij,m}$ as
$q_{ij,m}(x)=-\frac{B}{A}\mathcal{W}_{-1}\left(-\frac{A}{B}(\frac{x}{d})^{-\frac{C}{B}}\right)$
where we use the above parameter values. One can easily check that
$\frac{B}{A}\mathcal{W}_{-1}\left(-\frac{A}{B}x^{-\frac{C}{B}}\right)$ is a
function growing faster than $\ln x$ and slower than $x$.

##  XII Incentive considerations

###  XII-A Sequential game description

The CFUCB Algorithm 1 can be posited as a game
$G=(A,M,\\{\\{S_{i}(n)\\}_{n\in\mathbb{N}}\\}_{i\in
A},\\{\mathbf{x}_{i}\\}_{i\in A},\\{\beta_{m}\\}_{m\in M},\Gamma)$. It is
defined as an $|A|$-player infinite horizon sequential game, where

  * -

$A$ denotes the index set of users and $M$ denote the index set of arms.

  * -

$\\{\\{S_{i}(n)\\}_{n\in\mathbb{N}}\\}_{i\in A}$ denotes the arrival time
processes of users in $A$

  * -

$\Gamma$ denotes the counterfactual UCB sharing mechanism (we describe below).

$G$ is a sequential game [40] where an arrival of any user in $A$ is one stage
of the game. At the beginning of the game, which we call epoch $0$, each user
$i$ is asked to report its feature vector $\mathbf{x}_{i}$. (Of course, it can
refuse to report it by opting out at time $0$). At each epoch $k$,

  1. 1)

A user we denote by $a_{k}\in A$ arrives. The recommender observes $a_{k}$.

  2. 2)

If and only if $a_{k}\in A_{+}$, the recommender calculates the counterfactual
UCBs $\\{{ucb}^{cf}_{a_{k},m}(s_{k})\\}_{m\in M}$ according to Equation (1)
and lets user $a_{k}$ know the counterfactual UCBs.

  3. Remark.

$\Gamma$ of game $G$, the counterfactual-UCB sharing mechanism, is formally
defined as a function that maps the previous history of reports the
recommender has at $k$,
$\\{a_{l},(\widehat{m}_{l},\widehat{r}_{l})\\}_{l=1}^{k-1}$, into
$\\{{ucb}^{cf}_{a_{k},m}(s_{k})\\}_{m\in M}$.

  4. 3)

After receiving $\\{{ucb}^{cf}_{a_{k},m}(s_{k})\\}_{m\in M}$ from the
recommender, the user calculates $\widetilde{ucb}_{a_{k},m}(s_{k})$ for all
$m\in M$ according to
$\widetilde{ucb}_{a_{k},m}(s_{k})=\min(ucb^{se}_{a_{k},m}(s_{k}),{ucb}^{cf}_{a_{k},m}(s_{k})$.
(Note that user $a_{k}$ can calculate $\\{ucb^{se}_{a_{k},m}(s_{k})\\}_{m\in
M}$ by only using it’s own pulling history, which is private information.)

  5. 4)

User $a_{k}$ then pulls arm $m_{k}:=\arg\min_{m\in
M}\\{\widetilde{ucb}_{a_{k},m}(s_{k})\\}$ and observes a reward that we denote
by $r_{k}$.

  6. 5)

According to its reporting strategy, user generates its report
$(\widehat{m}_{k},\widehat{r}_{k})$ from the truth $({m}_{k},{r}_{k})$ and
sends it to the recommender.

  7. 6)

The recommender receives $(\widehat{m}_{k},\widehat{r}_{k})$ and stores it.

###  XII-B Incentive analysis

We denote by $\sigma_{i}$ the strategy of user $i$ of never opting out and
complying to recommendation at any of its arrivals. We define
$\sigma=\times_{i\in A}\sigma_{i}$ as the strategy profile corresponding to
each user $i\in A$ following $\sigma_{i}$.

The strategy profile where every $i\in A$ chooses $\sigma_{i}$ is defined as
$\sigma$. When no user ever violates the two assumptions, the outcome of
$\sigma$ and Algorithm 1 are the same. Corollary 1, which is an immediate
result of Proposition 1, formally states this observation.

######  Corollary 1.

Under Assumption 1 and 2, under the strategy profile $\sigma$, every user’s
expected regret is bounded.

Now we formally define the notion of “asymptotically indifferent users”. Given
the game $G$ and some strategy profile $\sigma$, after playing the game up to
time $T$, denote the regret of user $i$ up to time $T$ by
$Regret^{(i)}_{\sigma}(T)$. Suppose that for each $i\in A$, we are able to
achieve $E[Regret^{(i)}_{\sigma}(T)]=O(f_{\sigma}^{(i)}(T)]$ for some function
$f_{\sigma}^{(i)}$. Denoting the set of all possible strategy profiles
$\Sigma$, we say that an user $i$ has an asymptotically indifferent preference
if its preference can be described by a complete and transitive preference
relation $\succeq_{i}$ on $\Sigma$ such that
$\sigma\succeq_{i}{\sigma^{\prime}}$ if and only if
$f^{(i)}_{\sigma}(T)=O(f^{(i)}_{\sigma^{\prime}}(T))$. We say that $\sigma$ is
strictly preferred to $\sigma^{\prime}$ by user $i$ if
$\sigma\succeq_{i}{\sigma^{\prime}}$ but not
${\sigma^{\prime}}\succeq_{i}\sigma$.

######  Corollary 2.

Suppose that all the users in $A$ have asymptotically indifferent preferences.
Then $\sigma$ constitutes a Subgame Perfect Nash Equilibrium for the game
$G=(A,M,\\{\\{S_{i}(n)\\}_{n\in\mathbb{N}}\\}_{i\in
A},\\{\mathbf{x}_{i}\\}_{i\in A},\\{\beta_{m}\\}_{m\in M},\Gamma)$.

###### Proof of Corollary 2.

This result is immediate from Corollary 1, in that (i) no other strategy
profile can be strictly preferred to $\sigma$ by any user with aymptotically
indifferent preference; (ii) $\sigma$ already achieves bounded regret, i.e.,
$O(1)$, for all the users, and (iii) thus cannot be improved in terms of
asymptotically indifferent preference. ∎