# Learning User Preferences in Non-Stationary Environments

Wasim Huleihel Soumyabrata Pal Ofer Shayevitz W. Huleihel is with the
Department of Electrical Engineering-Systems at Tel-Aviv university, Tel-Aviv
6997801, Israel (e-mail: wasimh@tauex.tau.ac.il).S. Pal is with the Computer
Science Department at the University of Massachusetts Amherst, Amherst, MA
01003, USA (email: spal@cs.umass.edu).O. Shayevitz is with the Department of
Electrical Engineering-Systems at Tel-Aviv university, Tel-Aviv 6997801,
Israel (email: ofersha@eng.tau.ac.il).

###### Abstract

Recommendation systems often use online collaborative filtering (CF)
algorithms to identify items a given user likes over time, based on ratings
that this user and a large number of other users have provided in the past.
This problem has been studied extensively when users’ preferences do not
change over time (static case); an assumption that is often violated in
practical settings. In this paper, we introduce a novel model for online non-
stationary recommendation systems which allows for temporal uncertainties in
the users’ preferences. For this model, we propose a user-based CF algorithm,
and provide a theoretical analysis of its achievable reward. Compared to
related non-stationary multi-armed bandit literature, the main fundamental
difficulty in our model lies in the fact that variations in the preferences of
a certain user may affect the recommendations for other users severely. We
also test our algorithm over real-world datasets, showing its effectiveness in
real-world applications. One of the main surprising observations in our
experiments is the fact our algorithm outperforms other static algorithms even
when preferences do not change over time. This hints toward the general
conclusion that in practice, dynamic algorithms, such as the one we propose,
might be beneficial even in stationary environments.

##  1 Introduction

Recommendation systems provide users with appropriate items based on their
revealed preferences such as ratings. Due to their wide applicability,
recommendation systems have received significant attention in machine learning
and data mining societies [53, 45, 47, 6, 36, 48, 31]. In practice,
recommendation systems often employ _collaborative filtering_ (CF) [22], for
recommending (potentially) liked items to a given user by considering items
that other “similar” users liked. There are two main categories of CF
algorithms: _user-based_ , e.g., [46, 30, 12, 7, 29], and _item-based_ , e.g.,
[25, 50, 38, 14], and many references therein. User-based algorithms exploit
similarity in the user space by recommending a particular user $u$ those items
which were liked by other similar users. Item-based algorithms, in contrast,
exploit similarity in the item space by recommending items similar to those
which were liked in the past by a particular user.

Prevalent recommendation systems typically operate in an online fashion where
items are recommended to users over time, and the obtained ratings are used
for future recommendations. Typically, the goal in such a problem is to
maximize the number of likes revealed at any time. This problem has been
studied extensively, e.g., [12, 14, 29, 13], always under the assumption that
user’s preferences do not vary over time. In practice, however, temporal
changes in the structure of the user’s preferences are an intrinsic
characteristic of the problem, since users change their taste occasionally
[27, 39, 42, 26, 33, 52, 5, 40, 43, 23]. Ignoring these changes results in
recommendation algorithms which are doomed to failure in practice. This sets
the goal of this paper: _we aim to model and understand the effect of non-
stationary environment on online recommendation systems_.

To that end, we introduce a novel latent probabilistic model for online non-
stationary recommendation systems, and analyze the reward of an online user-
based algorithm. Our model and certain elements of the algorithm are inspired
by related static models and algorithms studied in [12, 14, 29]. In a
nutshell, each user in our model has a latent probability preference vector
which describes the extent to which he/she likes or dislikes each item.
Similar users have similar preference vectors (this will be defined rigorously
in the following section). At a given time step $t=1,2,\ldots$, the algorithm
recommends a single item to each user, typically different for each user, and
with probability specified by the corresponding preference vector, the user
likes or dislikes the recommended item. Following [12, 14, 29] we impose the
constraint that an item that has been rated by a user, cannot be recommended
to the same user again. This is due to the fact that in many applications,
such as, recommendation of movies or books, a rating often corresponds to
consuming an item, and there is little point in, e.g., recommending a product
that has been previously purchased in the past for a second time, at least not
immediately. While in certain applications, this constraint might be
unnecessary/irrelevant, it _forces_ our algorithm to exploit the user-item
structure for collaboration. In any case, repeating the same recommendations
only makes the problem easier algorithmically, and the results of this paper
can be generalized to account for this case as well. Finally, to model the
non-stationarity in the users’ preferences, we allow users to change their
user-type over time.

Main Contributions. Despite the success of CF, there has been no theoretical
development to justify its effectiveness in non-stationary environment. The
main contributions of this paper are two-fold. First, we introduce a novel
model for general online non-stationary recommendation systems where we
generalize the stationary model introduced in [12] by allowing arbitrary
shifts in user preferences over time. Our second main contribution is a
theoretical analysis of a user-based CF algorithm that maximize the number of
recommendations that users like. As time evolves, our CF algorithm randomly
explores batches of items, one batch at a time, in order to learn users’
preferences of new items in each batch. By splitting the space into optimal
number of batches, our algorithms can start exploiting without having learned
the preferences of the users regarding at all items. Furthermore, in each
batch, our algorithm tests for variations, and once a change in the preference
of a certain user is detected, that user is removed from the exploitation
steps. Our results allow us to quantify the “price of non-stationarity”, which
mathematically captures the added complexity embedded in changing users’
preferences versus stationary ones. The proposed algorithm achieve near-
optimal performance relative to an oracle that recommends all likable items
first. Our findings, such as the scaling of the cold-start time on the various
parameters, and the effect of non-stationary environment on recommendation,
can inform the design of recommendation algorithms, and refine our
understanding of the associated benefits and costs while designing a practical
recommendation system.

Related Work. While to the best of our knowledge, this is the first work that
_analytically_ studies temporal changes in the users’ preferences, theoretical
results have been established for the stationary setting where there are no
changes in the user preferences over time. We next briefly survey these prior
works. One of the first initial asymptotic theoretical results concerning
user-based CF were established in [11]. Most related to our approach are the
setups and algorithms studied in [12, 14, 29, 13]. In particular, [12]
analyzed a user-based algorithm for online two-class CF problem in a similar
setting to ours, while a corresponding item-based algorithm was analyzed in
[14]. A probabilistic model in an online setup was studied in [19], and [4]
study a probabilistic model in an offline setup, and derived asymptotic
optimal performance guarantees for two-class CF problem. Theoretical
guarantees for a one-class models were derived in [29]. Another related work
is [21], who considered online recommendation systems in the context of linear
multi-armed bandit (MAB) problem [15].

Our setup relates to some variants of the MAB problem. An inherent conceptual
difference between our setup and standard MAB formulation [55] is that in our
case an item can be recommended to a user just once, while in MAB an item (or
arm) is allowed to be recommended ceaselessly. In fact, the solution principle
for MAB is to explore for the best item, and once found, keep exploiting
(i.e., recommending) it [2, 15]. This observation applies also to clustered
bandits [16], or, bandits with dependent arms [44]. Specifically, in these
formulations the arms are grouped into clusters, and within each cluster arms
are correlated. It is assumed, however, that the assignment of arms to
clusters is known, while in our setup this information is not available.
Another related formulation of MAB is “sleeping bandits” [35], where the
availability of arms vary over time in an adversarial manner, while in our
setup, the sequence of items that are available is not adversarial. Finally, a
more recent related version is the problem of MAB with non-stationary rewards,
e.g., [28, 24, 56, 10, 8, 34, 41, 17, 18, 3, 32, 51, 37, 9, 1, 57]. This
formulation allows for a broad range of temporal uncertainties in the rewards.
While the motivation of this setup is similar to ours, due to the same reasons
as above, the results and methods in these papers are quite different from
ours. In particular, the main fundamental difficulty in our model compared to
MAB literature lies in the fact that variations in the preferences of a
certain user may affect the recommendations for other users severely.

##  2 Model and Learning Problem

In this section we introduce the model and the learning problem considered in
this paper. We start with the static setting where users’ preferences do not
change over time, and then generalize to the dynamic setting.

Static Model. Consider a system with ${\mathsf{N}}$ users and ${\mathsf{M}}$
items. A user may “like” ($+1$) or “dislike” ($-1$) an item. At each time
step, each user is recommended an item that he has not consumed yet. Each user
$u\in[{\mathsf{N}}]\triangleq\\{1,2,\ldots,{\mathsf{N}}\\}$ is associated with
a _latent_ (unknown) preference vector
$\mathbf{p}_{u}\in\left[0,1\right]^{{\mathsf{M}}}$, whose entries $p_{ui}$ are
the probabilities of user $u$ liking item $i\in[{\mathsf{M}}]$, independently
across items. We assume that an item $i$ is either _likable_ for user $u$,
i.e., $p_{ui}>1/2$, or _unlikable_ , i.e., $p_{ui}<1/2$. The reward earned by
the recommendation system up to any time step is the total number of liked
items that have been recommended so far across all users (a precise definition
will be given in the sequel). Accordingly, to maximize this reward, clearly
likable items for the user should be recommended before unlikable ones. For a
particular item $i$, recommended to a user $u$, the observed rating is a
random variable $\mathbf{R}_{ui}$, such that $\mathbf{R}_{ui}=1$ with
probability $p_{ui}$, and $\mathbf{R}_{ui}=-1$ with probability $1-p_{ui}$.
The ratings are assumed random in order to model the fact that users are not
fully consistent in their ratings. A CF algorithm operates as follows: at each
time step $t=0,1,\ldots$, the algorithm recommends a single item
$i=\pi_{u,t}\in[{\mathsf{M}}]$ to each user $u\in[{\mathsf{N}}]$, and obtains
a realization of the binary random variable $\mathbf{R}_{ui}$ in response.
Thus, if $\mathbf{R}_{ui}=1$, user $u$ likes item $i$, and
$\mathbf{R}_{ui}=-1$ means that user $u$ does not like item $i$. Either way,
as we explain and motivate in the Introduction, once rated by user $u$, item
$i$ _will not_ be recommended to that user again.

To learn the preference of some user for an item, we need this user to rate
that item. However, since we cannot recommend that item to the same user
again, the only way to estimate the preferences of a user is through
_collaboration_ (e.g., by making inferences from ratings made by other users).
In order to make collaborative recommendations based on users’ preferences we
must assume some structure/relation between users and/or items. To that end,
we study a latent model, in which users are clustered. Specifically, following
[4, 19, 12, 14, 29, 13] (and many references therein), we assume that each
user belongs to one of ${\mathsf{K}}<{\mathsf{N}}$ _user-types_ , where users
of the same type have “similar” item preference vectors. The number of types
${\mathsf{K}}$ represents the heterogeneity in the population. This assumption
is common and implicitly invoked by contemporary user-based CF algorithms
[49], which perform well in practice. Several empirical justifications for the
clustering behavior in the user-item space can be found in, e.g., [54, 12,
29].

There are many ways to define similarity between users. For example, in [20,
4, 19, 13] two users are considered of the same type if they have the same
exact ratings, and these rating vectors are generated at random. While this
model is perhaps unrealistic and does not capture challenges in real-world
datasets, it allows for a neat theoretical analysis. A slightly more general
and flexible model was proposed in [12]. Here, two users $u$ and $v$ belong to
the same type if their corresponding preference vectors ${\mathbf{p}}_{u}$ and
${\mathbf{p}}_{v}$ are the same, nonetheless, their actual ratings might be
different. In [29] this assumption was significantly relaxed by assuming
instead that the preference vectors belonging to the same type are more
similar (in terms of the magnitude of their inner product) than those
belonging to other types. Roughly speaking, in this paper we follow this
latter assumption, but we relax it even further. The precise statement of our
assumptions will be given in the following section. This concludes the
presentation of the static model. We next incorporate the non-stationary
aspect.

User Variations. As explained in the introduction, our paper initializes the
theoretical investigation of the situation where the preferences of users do
not remain static but vary over time. To model this, we allow users to change
their user-type over time. To wit, denote the type of user
$u\in[{\mathsf{N}}]$ at time $t\in[{\mathsf{T}}]$ by ${\cal
T}_{u}(t)\in[{\mathsf{K}}]$. In the sequel, ${\cal T}_{u}(1)$, for any
$u\in[{\mathsf{N}}]$, designates the initial clustering of users into types.
We assume that each user can change his type an _arbitrary_ number of times,
but bound the total number of such variations. Specifically, we define two
notions for variations:

$\displaystyle\mathsf{V_{1}}$
$\displaystyle\triangleq\max_{u\in[{\mathsf{N}}]}\sum_{t\in[{\mathsf{T}}-1]}\mathds{1}[{\cal
T}_{u}(t)\neq{\cal T}_{u}(t+1)],$ (1)

and

$\displaystyle\mathsf{V_{2}}$
$\displaystyle\triangleq{\mathsf{N}}^{-1}\sum_{t\in[{\mathsf{T}}-1]}\sum_{u\in[{\mathsf{N}}]}\mathds{1}[{\cal
T}_{u}(t)\neq{\cal T}_{u}(t+1)],$ (2)

where $\mathds{1}[\cdot]$ is the indicator function. These definitions capture
the constraint imposed on the non-stationary environment faced by the CF
algorithm. In words, $\mathsf{V}_{1}$ is the maximum number of variations over
${\mathsf{T}}$ steps, while $\mathsf{N}\mathsf{V}_{2}$ is the total number of
variations. In general, $\mathsf{V_{1}}$ and $\mathsf{V_{2}}$ are designed to
depend on the time horizon ${\mathsf{T}}$. It turns out that in order to
obtain the tightest bound on the reward, both definitions are needed. It is
clear that $\mathsf{V_{1}}\leq\mathsf{N}\cdot\mathsf{V}_{2}$.

In this paper, we consider the already non-trivial case where the values of
(or, at least, upper bounds on) $\mathsf{V}_{1}$ and $\mathsf{V}_{2}$ are
_given_ to the learner/algorithm in advance. This is inline with the various
settings of classical results in the non-stationary MAB literature, e.g., [10,
8, 41]. Nonetheless, in a similar fashion to recent advances in the MAB
literature [34, 3, 18], it is an important, challenging, and of practical
importance to propose and analyze algorithms which are oblivious to the number
of variations (see Appendix 5).

Learning Problem and Reward. Generally speaking, a reasonable objective for a
CF algorithm is to maximize the expected reward up to time ${\mathsf{T}}$,
i.e.,

$\displaystyle\overline{\mathsf{reward}}({\mathsf{T}})\triangleq\mathbb{E}\sum_{t\in[{\mathsf{T}}]}\frac{1}{{\mathsf{N}}}\sum_{u\in[{\mathsf{N}}]}\mathbf{R}_{u\pi_{u,t}},$

where we note that the recommended item $\pi_{u,t}$ is a random variable
because it is chosen by the CF algorithm as a function of previous responses
to recommendations made at previous times. In this paper, however, we focus on
recommending _likable_ items. Following [12, 14, 29, 13], we consider the
accumulated reward defined as the expected total number of liked items that
are recommended by an algorithm up to time ${\mathsf{T}}$, i.e.,

$\displaystyle\mathsf{reward}({\mathsf{T}})\triangleq\mathbb{E}\sum_{t\in[{\mathsf{T}}]}\frac{1}{{\mathsf{N}}}\sum_{u\in[{\mathsf{N}}]}\mathds{1}\left[p_{u\pi_{u,t}}>1/2\right].$
(3)

Note that the main difference between these two objectives is that the former
prioritize items according to their probability of being liked, while the
latter asks to recommend likable items for a user in an arbitrary order. This
is sufficient for many real recommendation systems such as for movies and
music (see, [12, Sec. 2] for a detailed discussion). We would like to
emphasize that depending on the intended application, other metrics can be
considered. For example, one may be interested in the number of actual
“clicks” rather then the number of “likable” recommendations. Indeed, in some
applications, the former is the measurable quantity. Nonetheless, we believe
that our algorithms and techniques can handle such a criterion as well.

##  3 Algorithms and Theoretical Guarantees

In this section, we present our algorithm Collaborative which recommends items
to users over time, followed by a formal theoretical statement for its
performance. We start with a non-formal description of our algorithm. The
pseudocodes are given in Algorithms 1–3. The algorithm takes as input the
parameters $(\alpha,\lambda,\mathsf{T_{static}},\Delta_{{\mathsf{T}}})$, which
we shall discuss below.

We now describe the proposed algorithm. Below, we use “$t$” to denote the time
index at any step of the algorithm. Also, in the sequel, we use ${\cal P}$ to
denote an estimated partitioning of the users into clusters, i.e., ${\cal P}$
is a collection of clusters, where each cluster refers to a set of users who
have same estimated user type.

#### Batches.

In Algorithm 1, the time horizon ${\mathsf{T}}$ is partitioned into
$\left\lceil{\mathsf{T}}/\Delta_{\mathsf{T}}\right\rceil$ batches of size
$\Delta_{\mathsf{T}}$ each, and denoted by $\\{{\cal B}_{b}\\}_{b\geq 1}$. We
use $\tau$ to denote the time index at which each batch starts, namely, for
the $b^{\mathsf{th}}$ batch $\tau=(b-1)\Delta_{\mathsf{T}}$, for
$b\in[1,\left\lceil 1/\Delta_{\mathsf{T}}\right\rceil]$. At the beginning of
each batch, we _restart_ Algorithm Recommend, and run it for the entire batch.
Also, at the beginning of each batch, we estimate an initial partition ${\cal
P}_{0}$ for the set of all users $[\mathsf{N}]$ using Algorithm 3, which we
describe bellow. At each subsequent time index $t$, the Algorithm Recommend
either runs a _test for variations_ with probability (w.p.)
$\mathsf{p}_{{\mathsf{T}}}\propto\sqrt{\mathsf{V}_{1}/{\mathsf{T}}}$, or,
explores-exploits w.p. $1-\mathsf{p}_{{\mathsf{T}}}$.

#### User partitioning in the batch.

The goal of Algorithm 3 is to create a partition of the users into types. To
that end, routine $\textsc{Test}(\mathsf{T_{static}},\lambda,{\cal
S}_{t-1},{\cal P}_{0})$ recommends $\mathsf{T_{static}}\in\mathbb{N}$ random
items ${\cal T}_{\mathsf{test}}$ ($\left|{\cal
T}_{\mathsf{test}}\right|=\mathsf{T_{static}}$) to all users in ${\cal
S}_{t-1}\subseteq[{\mathsf{N}}]$, initialized in each batch to be the set of
all users $[{\mathsf{N}}]$. Then, using the obtained responses
$\left\\{\mathbf{R}_{ui}\right\\}_{u\in[{\cal S}],i\in{\cal
T}_{\mathsf{test}}}$, in the second and third steps of this algorithm a
partition of the users is created. Specifically, for any pair of distinct
users $u,v\in{\cal S}_{t-1}$, we let $\mathsf{X}_{u,v}$ be the number of items
for which $u$ and $v$ had the same responses. Let
$\mathsf{E}_{u,v}=\mathds{1}\left[\mathsf{X}_{u,v}\geq\lambda\cdot\mathsf{T_{static}}\right]$,
for some $\lambda>0$. Accordingly, users $u$ and $v$ are inferred to have the
same type if $\mathsf{E}_{u,v}=1$. Subsequently, if there exists a valid
partitioning ${\cal P}$ over the set of users in ${\cal S}_{t-1}$, which is
consistent with the variables $\mathsf{E}_{u,v}$, then we declare that ${\cal
P}$ is our estimated user-partition, otherwise, we place all users in the same
group. This is true precisely when the graph with edge set $\mathsf{E}_{u,v}$
is a disjoint union of cliques. Note that this partitioning procedure is
equivalent to the cosine similarity test, declaring that two users $u$ and $v$
as being neighbors if their cosine similarity is at least as large as some
threshold. The values of $\mathsf{T_{static}}$ and $\lambda\in(0,1)$ are
specified in Theorem 1.

#### Variations detection in the batch.

Given the partitions ${\cal P}_{0}$ and ${\cal P}$, in step 14 of Algorithm 1
we compare those partitions in order to detect any variations using routine
Variation. We show that if the user variations is not “too large” in the
corresponding batch, then it is possible to draw a one-to-one correspondence
between the clusters in ${\cal P}$ and ${\cal P}_{0}$, and therefore, it is
possible to identify the users who have changed their clusters, i.e., they are
in a different cluster in ${\cal P}$ than the one in ${\cal P}_{0}$. All such
users are declared as “bad” users and are included in the set ${\cal V}_{t}$.
We update ${\cal S}_{t}\leftarrow{\cal S}_{t-1}\setminus{\cal V}_{t}$. The
users in ${\cal V}_{t}$ will be excluded from future exploitation rounds.

Procedure 1 Collaborative Algorithm for recommending items.

0: Parameters $(\alpha,\lambda,\mathsf{T_{static}},\Delta_{\mathsf{T}})$.

1: Set index batch $b=1$.

2: while $b\leq\left\lceil{\mathsf{T}}/\Delta_{\mathsf{T}}\right\rceil$ do

3: Set $\tau\leftarrow(b-1)\Delta_{\mathsf{T}}$.

4: Call
Recommend$(\tau,\alpha,\lambda,\mathsf{T_{static}},\Delta_{\mathsf{T}})$.

5: Set $b\leftarrow b+1$ and return to the beginning of Step 2.

Procedure 2
Recommend$(\tau,\alpha,\lambda,\mathsf{T_{static}},\Delta_{\mathsf{T}})$

1: Select a random ordering $\sigma$ of the items $[{\mathsf{M}}]$.

2: Define $\mathsf{p_{R}}={\mathsf{N}}^{-\alpha}$ and
$\mathsf{p_{T}}=\sqrt{\mathsf{V_{1}}/({\mathsf{T}}\cdot\mathsf{T_{static})}}$.

3: Let $t$ to be the time index at any step of the algorithm.

4: ${\cal
P}_{0}\leftarrow$Test($\mathsf{T_{static}}$,$\lambda$,$[{\mathsf{N}}]$).

5: Initialize ${\cal S}_{\tau+\mathsf{T_{static}}}\leftarrow[{\mathsf{N}}]$.

6: while
$\tau+\mathsf{T_{static}}<t\leq\min({\mathsf{T}},\tau+\Delta_{\mathsf{T}})$ do

7: Draw $\Theta\sim\mathsf{Bern}(\mathsf{p_{T}})$.

8: if $\Theta=0$ then

9: ${\cal S}_{t}\leftarrow{\cal S}_{t-1}$.

10: $\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ With probability
$\mathsf{p_{R}}$: $\pi_{u,t}\leftarrow$ random item for all
$u\in[{\mathsf{N}}]$ that has not rated.

11: $\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ With probability
$1-\mathsf{p_{R}}$: $\pi_{u,t}\leftarrow$ item $i$ that user $u\in{\cal
S}_{t}$ has not rated and that maximizes score $\hat{p}_{ui}^{(t)}$ in (4).

12: else

13: ${\cal P}\leftarrow$Test($\mathsf{T_{static}}$,$\lambda$,${\cal
S}_{t-1}$).

14: ${\cal V}_{t}\leftarrow$Variation$({\cal P},{\cal P}_{0})$.

15: ${\cal S}_{t}\leftarrow{\cal S}_{t-1}\setminus{\cal V}_{t}$.

Procedure 3 Test($\mathsf{T_{static}}$,$\lambda$,${\cal S}_{t-1}$) Algorithm
for partitioning users.

1: Recommend $\mathsf{T_{static}}$ random items ${\cal T}_{\mathsf{test}}$ to
all users in ${\cal S}_{t-1}$.

2: For any $u\neq v\in{\cal S}_{t-1}$, let $\mathsf{X}_{u,v}$ be the number of
items in ${\cal T}_{\mathsf{test}}$ for which $u$ and $v$ had the same
responses, and let
$\mathsf{E}_{u,v}=\mathds{1}\left[\mathsf{X}_{u,v}\geq\lambda\cdot\mathsf{T_{static}}\right]$.

3: Let ${\cal P}$ be the valid partitioning over users consistent with the
variables $\mathsf{E}_{u,v}$. If such a partitioning does not exist, let
${\cal P}\equiv{\cal S}_{t-1}$.

4: Return ${\cal P}$.

Procedure 4 Variation$({\cal P},{\cal P}_{0})$ Algorithm for testing
variations.

1: For each cluster ${\cal C}$ in ${\cal P}$, find a cluster ${\cal
C}^{\prime}$ in ${\cal P}_{0}$ that shares at least half the users in ${\cal
C}$ i.e., $\left|{\cal C}\cap{\cal C}^{\prime}\right|\geq\frac{|{\cal
C}|}{2}$.

2: Establish a one-to-one mapping from clusters in ${\cal P}$ to clusters in
${\cal P}_{0}$ in this manner. If such a one-to-one mapping is not possible,
return $\emptyset$.

3: Identify the set of users ${\cal V}$ who belong to different clusters in
${\cal P}$ and ${\cal P}_{0}$.

4: Return ${\cal V}$.

#### Exploration-Exploitation.

Since we restart the main algorithm in each batch, we focus on a particular
batch $b$ in the explanation below. For ease of notation, we omit the batch
index from all definitions. As mentioned above, w.p. $1-\mathsf{p_{T}}$ our
algorithm performs an exploration-exploitation routine. In such a case, with
probability $\mathsf{p_{R}}={\mathsf{N}}^{-\alpha}$ the algorithm randomly
explores the space of items, and with complementary probability,
$1-\mathsf{p_{R}}$, the algorithm exploits by recommending those items that
maximize a certain score. With some abuse of notation let
$\mathbf{R}_{ui}^{(t)}\in\left\\{-1,0,1\right\\}$ be the observed rating of
user $u$ to item $i$ up to time $t$ in the $b^{\mathsf{th}}$ batch, where
“$0$” means that no rating has been given yet (in the $b^{\mathsf{th}}$
batch). When exploiting, the algorithm evaluates empirical probabilities
$\hat{p}_{ui}^{(t)}$, at time $t$, for user $u\in{\cal S}_{t}$, and item $i$.
These empirical probabilities are defined as follows,

$\displaystyle\hat{p}_{ui}^{(t)}\triangleq\begin{cases}\frac{\sum_{v\in\mathsf{neigh}(u,t)}\mathds{1}\left[\mathbf{R}_{vi}^{(t)}=1\right]}{\mathsf{C}_{ut}},\
&\text{if }\mathsf{C}_{ut}>0\\\ 1/2,\ &\text{otherwise},\end{cases}$ (4)

where
$\mathsf{C}_{ut}\triangleq\sum_{v\in\mathsf{neigh}(u,t)}\mathds{1}[\mathbf{R}_{vi}^{(t)}\neq
0]$, and the “neighborhood” of user $u\in{\cal S}_{t}$ at time $t$ in the
$b^{\mathsf{th}}$ batch is $\mathsf{neigh}(u,t)\triangleq{\cal
P}_{0}(u)\cap{\cal S}_{t}$, where ${\cal P}_{0}(u)$ is the set of users in the
same cluster as user $u$ in the initial partition ${\cal P}_{0}$ created in
the beginning of the batch. Note that the exploitation step at any time index
$t$ is done only for those users which are present in ${\cal S}_{t}$. Finally,
we emphasize here that the empirical probabilities $\hat{p}_{ui}^{(t)}$ as
well as the neighborhoods $\mathsf{neigh}(u,t)$, are all refreshed at the
beginning of each batch; ratings from previous batches are ignored in the
evaluation of these quantities.

######  Remark 1.

In practice, we can continue recommending items to any user $u$ in
$\mathcal{V}_{t}$ (bad users) based on the items liked by other users who
belong to $\mathcal{P}_{0}(u)$.

Theoretical performance guarantee. In the following, we state our main
theoretical result, which is a lower bound on the reward in (3) achieved by
Algorithm Collaborative. To that end, we introduce three natural and prima
facie necessary assumptions, which will be used in order to establish our
result.

  * A1

No $\Delta$-ambiguous items. For every user $u\in[{\mathsf{N}}]$ and item
$i\in[{\mathsf{M}}]$, there exists a constant $\Delta\in(0,1/2]$ such that
$\left|p_{ui}-1/2\right|\geq\Delta$.

  * A2

Minimum portion of likeable items. There exists a constant $\mu\in[0,1]$, such
that for every user $u\in[{\mathsf{N}}]$, it holds
$\sum_{i=1}^{{\mathsf{M}}}\mathds{1}\left[p_{ui}>1/2\right]\geq\mu{\mathsf{M}}$.

  * A3

(In)coherence. There exist constants $\gamma_{2}\geq\gamma_{1}\in[0,1)$ such
that if two users $u$ and $v$ are of _different_ types, then $\langle
2{\mathbf{p}}_{u}-\mathbf{1},2{\mathbf{p}}_{v}-\mathbf{1}\rangle\leq
4\gamma_{1}\Delta^{2}{\mathsf{M}}$, and if they are of the _same_ type, then
$\langle 2{\mathbf{p}}_{u}-\mathbf{1},2{\mathbf{p}}_{v}-\mathbf{1}\rangle\geq
4\gamma_{2}\Delta^{2}{\mathsf{M}}$. Here $\mathbf{1}$ is the all ones vector.

In a nutshell, Assumption A1 is necessary to assure that one can infer whether
an item is either likable or unlikable with a finite number of samples. The
parameter $\Delta$ quantifies the inconsistency (or, noise), where $\Delta=0$
($\Delta=1/2$) is the completely noisy (noiseless) case. The second condition
states that each user likes at least a fraction $\mu$ of the total items. This
assumption is made to avoid degenerate situations were a user $u$ does not
like any item. Note that one can always ignore those users whose activity is
insignificant since their contribution to the reward will be insignificant as
well. Evidently, from a practical point of view, any real-world recommendation
engine must prioritize users whose activity is significant. Notice that
relevant literature, such as [12, 29], makes the same assumptions as well.

The more interesting assumption is A3. The incoherence part of assumption A3
requires that the preference vectors for any two users $u$ and $v$ belonging
to different user-types are not too similar, so that the cosine similarity
test can separate users of different types over time. The parameter
$\gamma_{1}$ controls this incoherence; the smaller $\gamma_{1}$ is, the less
similar are users of different types. This incoherence assumption appears in
[12] as well. The coherence part of assumption A3 asks that any two users of
the same user-type share a large fraction of the items that they find likable,
and this fraction is controlled by the parameter $\gamma_{2}$. This coherence
assumption should be contrasted with [12] where it was assumed that the
preference vectors ${\mathbf{p}}_{u}$ and ${\mathbf{p}}_{v}$ of two users $u$
and $v$ from the same user-type to be exactly the same, which is evidently a
stronger assumption, and accordingly, our coherence assumption relaxes that
significantly.

_We would like to clarify that the above assumptions are only required for the
analysis; Our proposed algorithm can be implemented regardless of these
assumptions_. As is shown in Section 4, in real-world applications, our
algorithm works well even if these assumptions do not hold. We next provide
two examples where the typical values of the various parameters in assumptions
A1–A3 are derived.

######  Example 1.

Consider the noiseless case where $\Delta=1/2$. In this case, the users’
ratings are deterministic given their user-types. Accordingly we generate
${\mathsf{K}}$ $\mathsf{d}$-dimensional binary vectors
$\\{\mathbf{b}_{i}\\}_{i=1}^{{\mathsf{K}}}$ by randomly drawing $\mathsf{d}$
statistically independent $\mathsf{Bernoulli}(1/2)$ random variables, for each
user-type. Here $\mathsf{d}\leq{\mathsf{M}}$ is some parameter. Then, the
preference vector of any user in the $\ell$ user-type (i.e., ${\cal
T}_{\ell}$) will be the concatenation of $\mathbf{b}_{\ell}$ with
${\mathsf{M}}-\mathsf{d}$ statistically independent $\mathsf{Bernoulli}(1/2)$
random variables. To wit, the preference vector of user $u\in{\cal T}_{\ell}$
is ${\mathbf{p}}_{u}=[\mathbf{b}_{\ell};\mathbf{e}_{u}]$, where
$\mathbf{e}_{u}$ is a binary vector whose ${\mathsf{M}}-\mathsf{d}$ elements
are statistically independent $\mathsf{Bernoulli}(1/2)$ random variables. Now,
for any two users $u$ and $v$ from different user-types, it should be clear
that the inner product $\frac{1}{{\mathsf{M}}}\langle
2{\mathbf{p}}_{u}-\mathbf{1},2{\mathbf{p}}_{v}-\mathbf{1}\rangle$ is merely a
sum of ${\mathsf{M}}$ Rademacher random variables normalized by
${\mathsf{M}}$. Accordingly, a standard concentration inequality on sum of
Rademacher random variables tell us that the value of this inner product is in
the interval
$[-\Theta(\sqrt{\frac{\log{\mathsf{M}}}{{\mathsf{M}}}}),\Theta(\sqrt{\frac{\log{\mathsf{M}}}{{\mathsf{M}}}})]$,
with probability at least $1-\mathsf{poly}({\mathsf{M}}^{-1})$. Therefore, for
the incoherence condition to hold with high probability we need
$\gamma_{1}>\Theta(\sqrt{\frac{\log{\mathsf{M}}}{{\mathsf{M}}}})$. On the
other hand, if $u$ and $v$ are from the same user-type, the inner product of
the first $\mathsf{d}$ items is maximal (i.e., unity) by construction.
Therefore, using the same arguments it can be shown that the value of the
above inner product is at least
$\frac{\mathsf{d}}{{\mathsf{M}}}-\Theta(\sqrt{\frac{({\mathsf{M}}-\mathsf{d})\log({\mathsf{M}}-\mathsf{d})}{{\mathsf{M}}^{2}}})\geq\frac{\mathsf{d}}{{\mathsf{M}}}-\Theta(\sqrt{\frac{\log{\mathsf{M}}}{{\mathsf{M}}}})$,
with high probability. This implies that the coherence condition holds if
$\gamma_{2}\leq\frac{\mathsf{d}}{{\mathsf{M}}}-\Theta(\sqrt{\frac{({\mathsf{M}}-\mathsf{d})\log{\mathsf{M}}}{{\mathsf{M}}^{2}}})$.
When $\mathsf{d}={\mathsf{M}}$, which means that users of the same user-type
have exactly the same preference vectors and therefore $\gamma_{2}$ can get as
large as $1$. Otherwise, there is a certain payment depending on how similar
the preference vectors are, controlled by $\mathsf{d}$. Finally, the typical
value of $\mu$ is clearly around $1/2$ with high probability.

######  Example 2.

We generalize the previous example. Consider the case where each entry of the
$\mathsf{d}$-dimensional vectors
$\\{\mathbf{b}_{\ell}\\}_{\ell=1}^{{\mathsf{K}}}$ is $\frac{1}{2}+\Delta$ with
probability $\mu$ and $\frac{1}{2}-\Delta$ with probability $1-\mu$, for a
fixed $\Delta$. Then, as in the previous example, the preference vector of
user $u\in{\cal T}_{\ell}$ is
${\mathbf{p}}_{u}=[\mathbf{b}_{\ell};\mathbf{e}_{u}]$, where $\mathbf{e}_{u}$
is now a random vector whose ${\mathsf{M}}-\mathsf{d}$ elements are
statistically independent, and each element is either $\frac{1}{2}+\Delta$
with probability $\mu$ and $\frac{1}{2}-\Delta$ with probability $1-\mu$.
Then, using the same arguments as in the previous example, it can be shown
that if users $u$ and $v$ are of different user types, then the incoherence
condition holds with high probability when
$\gamma_{1}>(1-2\mu)^{2}+\Theta(\sqrt{\frac{\log{\mathsf{M}}}{{\mathsf{M}}}})$.
On the other hand, if users $u$ and $v$ are of the same user type, then the
coherence condition holds with high probability when
$\gamma_{2}\leq\frac{\mathsf{d}}{{\mathsf{M}}}-(1-2\mu)^{2}-\Theta(\sqrt{\frac{({\mathsf{M}}-\mathsf{d})\log({\mathsf{M}}-\mathsf{d})}{{\mathsf{M}}^{2}}})$.

Let $a\vee b\triangleq\max(a,b)$ and $a\wedge b\triangleq\min(a,b)$, for
$a,b\in\mathbb{R}$. We are now in position to state our main result.

######  Theorem 1.

Let $\delta\in(0,1)$ and $\nu\in(0,1)$ be some pre-specified tolerances. Take
as input to Collaborative $\alpha\in(0,4/7]$, any
$\lambda\in(\lambda_{-},\lambda_{+})$, and
$\Delta_{\mathsf{T}}={\mathsf{T}}\wedge\sqrt{\frac{2\nu{\mathsf{T}}}{\mathsf{3V_{2}}}\kappa}$,
where $\lambda_{\pm}\triangleq
2\gamma_{1}\Delta^{2}+\frac{1}{2}\pm\Delta^{2}(\gamma_{2}-\gamma_{1})$ and
$\kappa\triangleq\mathsf{T_{static}}(1-\delta-\mu)$. Define
$\mathsf{T_{static}}\triangleq\frac{2\log(3{\mathsf{N}}^{2}/\delta)}{\Delta^{4}(\gamma_{2}-\gamma_{1})^{2}}$
and
$\mathsf{T}_{\mathsf{learn}}\triangleq\left[1\vee\frac{3\mathsf{V_{2}}}{2\nu(1-\delta-\mu)}\right]\mathsf{T}_{\mathsf{static}}.$
Consider the latent source model and assumptions A1–A3. If at every time-
point, the portion of users belonging to any user-type is at least $\nu$,
then, for any
${\mathsf{T}}_{\mathsf{learn}}\leq{\mathsf{T}}\leq\mu\cdot{\mathsf{M}}$, the
expected proportion of liked items recommended by Collaborative up until time
${\mathsf{T}}$ satisfies

$\displaystyle\mathsf{reward}({\mathsf{T}})$
$\displaystyle\geq(1-\delta)\cdot{\mathsf{T}}-\kappa\vee\sqrt{\frac{3\mathsf{V_{2}{\mathsf{T}}}\kappa}{2\nu}}-2\mathsf{V_{1}}\mathsf{T_{static}}-2\sqrt{\mathsf{V}_{1}{\mathsf{T}}\mathsf{T_{static}}}-\frac{3\mathsf{V_{2}}{\mathsf{T}}}{2\nu}\wedge\sqrt{\frac{3\mathsf{V}_{2}{\mathsf{T}}\kappa}{2\nu}}.$
(5)

For ${\mathsf{T}}<{\mathsf{T}}_{\mathsf{learn}}$, the reward satisfies
$\mathsf{reward}({\mathsf{T}})\geq\mu\cdot{\mathsf{T}}$.

The proof of Theorem 1 can be found in Appendix A, and we now discuss its
implications. For ${\mathsf{T}}<{\mathsf{T}}_{\mathsf{learn}}$, the algorithm
may give poor recommendations. This is reasonable since in the first
${\mathsf{T}}_{\mathsf{learn}}$ rounds mostly random items are recommended,
independently of the users responses, and thus the reward is at least
$\mu\cdot{\mathsf{T}}$. This is the initial phase for which our CF algorithm
gives poor recommendations. Then, for
${\mathsf{T}}_{\mathsf{learn}}<{\mathsf{T}}<\mu\cdot{\mathsf{M}}$, the
algorithm becomes efficient. Specifically, when
$\mathsf{V_{1}}=\mathsf{V_{2}}=0$, we get that
$\mathsf{reward}({\mathsf{T}})/{\mathsf{T}}\geq(1-\mathsf{T_{learn}}/{\mathsf{T}})\cdot(1-\delta-\eta)$.
Therefore, the proposed algorithm becomes near-optimal, as the achieved reward
is $(1-\varepsilon^{\prime})$–close to an oracle that recommends only likeable
items and thus achieves a reward of ${\mathsf{T}}$. Note that contrary to
multi-armed bandit literature, linear reward is common in collaborative
filtering frameworks (see, for example, [12, 29, 13]). For
${\mathsf{T}}>\mu\cdot{\mathsf{M}}$, on the other hand, one cannot guarantee
that likable items remain, and the learning time (cold-start time) is
${\mathsf{T}}_{\mathsf{learn}}={\mathsf{T}}_{\mathsf{static}}$.

Clearly, when $\mathsf{V_{1}},\mathsf{V_{2}}>0$ the reward decreases.
Specifically, if both of these parameters scale as $O({\mathsf{T}}^{c})$, for
some constant $c\in[0,1]$, then the payoff for non-stationarity compared to
the static case is of order $O(\sqrt{{\mathsf{T}}^{1+c}})$, a sub-linear cost
in ${\mathsf{T}}$. In particular, ignoring the exact dependency of the reward
on the various parameters, the scaling of (5) with ${\mathsf{T}}$ is
$\mathsf{reward}({\mathsf{T}})/{\mathsf{T}}\geq
1-\delta-O(\sqrt{{\mathsf{T}}^{c-1}})$. This result provides a spectrum of
orders of the payoff ranging between order $O(\sqrt{{\mathsf{T}}})$ (constant
number of variations), and of order $O({\mathsf{T}})$ (number of variations is
$O({\mathsf{T}})$). The sub-linearity growth implies that our user-based CF
algorithm has long run average performance that converges to the performance
that would have been achieved in the static environment, where users’
preferences do not vary. Finally, in terms of the learning time, it can be
checked that
${\mathsf{T}}_{\mathsf{learn}}=\Theta({\mathsf{T}}^{c}\log({\mathsf{N}}^{2}/\delta))$,
and thus the condition ${\mathsf{T}}>{\mathsf{T}}_{\mathsf{learn}}$ boils down
to ${\mathsf{T}}>\Theta([\log({\mathsf{N}}^{2}/\delta)]^{\frac{1}{1-c}})$.
Therefore, when there are variations, the cold-start time grows, and the
scaling of the variations with ${\mathsf{T}}$ dictates the poly-log order of
this learning phase.

Next, we study the dependency of the learning time in Theorem 1 on
$\gamma_{1}$ and $\gamma_{2}$, for Example 1 above. It can be seen that the
learning time depend on these parameters via the term
$(\gamma_{2}-\gamma_{1})^{-2}$. Accordingly, when $\mathsf{d}={\mathsf{M}}$ in
Example 1 we get that $(\gamma_{2}-\gamma_{1})^{-2}$ is of order constant by
taking $\gamma_{1}=\Theta(\sqrt{\frac{\log{\mathsf{M}}}{{\mathsf{M}}}})$ and
$\gamma_{2}=1$. In fact, it is evident that this is true when
$\mathsf{d}=\Theta({\mathsf{M}})$ as well, and thus if any two users from the
same user-type share a constant fraction of the total number of items that
they find likeable, then this has a multiplicative constant effect on the
learning time. If however, $\mathsf{d}=o({\mathsf{M}})$, say,
$\mathsf{d}=O({\mathsf{M}}^{q})$, for $q\in(0,1/2)$, then we can set
$\gamma_{2}=\Theta({\mathsf{M}}^{-c})$, and accordingly,
${\mathsf{T}}_{\mathsf{static}}$ will scale as
${\mathsf{M}}^{2q}\cdot\log({\mathsf{N}}^{2}/\delta)$, for $\alpha\to 0$.
Accordingly, we see that when negligible amount of common items are likeable
by users of the same type, then the learning time is significantly larger, as
expected.

Below we mention briefly some of the technical challenges encountered in the
proof of Theorem 1. First, we establish a connection between the static reward
and the reward of a dynamic oracle in the non-stationary setting. This
connection is general and can be used in other possible static recommendation
system models that incorporate non-stationary environment. One of the main
difficulties in the proof of Theorem 1 is the analysis of how would a
variation in the preference of some user affects other users in its estimated
neighborhood. Unless this user is detected by Algorithm 3, the algorithm does
not know the change of this user, and it will keep using this user’s feedback
to make recommendations for other users. This is one source of added regret
incurred by the unsuccessful and incorrect detections of the change-points.
Other sources of regret are the cost associated with the detection/testing
delay, and a regret incurred by variations happening when testing. These costs
are captured by the third and fourth terms at the R.H.S. of (5).

##  4 Experiments

We simulate an online recommender system using real-world data in order to
understand whether our algorithm performs well, even when the data is not
generated by the probabilistic model introduced in Section 2. To that end, we
follow a similar vein as in [12, 29], and look at movie ratings from the
popular Movielens25m dataset,111https://grouplens.org/datasets/movielens/25m/
which provides 5-star rating and free-text tagging activity from Movielens, a
movie recommendation service. We parsed the first $7$ million ratings for our
experiment, and consider only those users who have rated at least $225$
movies, ending up with a total number of ${\mathsf{N}}=247$ users.

To avoid any kind of biases, we also restrict ourselves to movies which are
more or less equally liked and disliked by the users. To that end, we choose
those movies whose average ratings is between $2.5$ and $3.5$, and we found
out that ${\mathsf{M}}=10149$ such movies exist. Finally, we looked at two
genres: Action and Romance. For each user $u\in[{\mathsf{N}}]$, we recover
piece-wise stationary preferences by the following steps:

  1. 1.

We sort the movies rated by user $u$ in ascending order according to the time-
stamp.

  2. 2.

We partition the movies rated by user $u$ into $15$ bins so that each bin
contains equal number of movies. We will consider each bin to be a window of
time.

  3. 3.

For each bin, we find the number $\mathsf{a}_{u}\in\mathbb{N}$ of Action
movies rated by user $u$, as well as $\mathsf{r}_{u}\in\mathbb{N}$ the number
of Romance movies rated by the same user.

Accordingly, note that in each bin, the probability of user $u$: liking a
movie tagged Action but not Romance is
$\mathsf{a}_{u}/(\mathsf{a}_{u}+\mathsf{r}_{u})$; liking a movie tagged
Romance but not Action is $\mathsf{r}_{u}/(\mathsf{a}_{u}+\mathsf{r}_{u})$;
liking a movie tagged both Action and Romance is 1, and finally, a movie which
does not have any of these tags is 0. We want to point out that we consider
the number of Action and Romance movies that were rated by the user, rather
than just liked, since any user is biased towards rating the movies he will
like (see, [29]), and therefore the number of movies rated by the user is a
better indicator of his preference towards the genre. Fig. 1 shows the
probability of $5$ randomly chosen users liking Action movies across $10$
different bins. It is clear that the preferences exhibit a piece-wise
stationary behaviour, and that the variations are significant.

We now assume for simplicity that the number of rounds in each bin is $100$
(this value is unknown to the algorithm), and we took the total number of
rounds to be ${\mathsf{T}}=600$. In lieu of creating the initial disjoint
clusters at the beginning of each batch (i.e., $\mathcal{P}_{0}$), we
recommend $\mathsf{T}_{\mathsf{static}}$ randomly chosen items to all users.
For each user $u\in[{\mathsf{N}}]$, we take the neighbors of $u$ to be the top
$10$ users whose feedback vector has the highest cosine similarity with that
of user $u$, over the $\mathsf{T}_{\mathsf{static}}$ recommended items.
Further, since ${\mathsf{T}}=600$ is quite small, we do not test for bad users
in each batch (namely, we skip lines $13-15$ in Algorithm 2). The reasons for
this modification are as follows. First, in the theoretical analysis, we have
assumed that ratings of a single bad user can potentially result in faulty
recommendations for all other users in their user group. However, in practice,
that might not be the case as future recommendations are determined by
multiple other users who can negate the effect of that bad user. Secondly, as
the dataset for our experiment is not very large ($10$ neighbors for each
user), detecting bad users based on ratings of neighbors can be unreliable.
Finally, for small $\mathsf{T}$, $\mathsf{T}_{\mathsf{static}}$ is
comparatively large and therefore testing for bad users can potentially bias
the accumulated reward towards larger batch-sizes. Nevertheless, as we will
show, our experiment clearly demonstrates the dependence on
$\Delta_{{\mathsf{T}}}$ and $\mathsf{T}_{\mathsf{static}}$ in the non-
stationary setting. We run Algorithm 1 with $\mathsf{T}_{\mathsf{static}}=10$
and $p_{\mathsf{R}}=0.1$, for several different values of the batch-size
$\Delta_{\mathsf{T}}$, each for $5$ different iterations. The performance of
the algorithms is measured in terms of the average cumulative reward up to
time ${\mathsf{T}}$, namely,

$\mathsf{acc}\text{-}\mathsf{reward}({\mathsf{T}})\triangleq\sum_{t\in[{\mathsf{T}}]}\frac{1}{{\mathsf{N}}}\sum_{u\in[{\mathsf{N}}]}\mathbf{R}_{u\pi_{u,t}},$

where $\pi_{u,t}$ is the item recommended by the algorithm to user $u$ at time
$t$. The average cumulative reward up to time ${\mathsf{T}}$ is given in Table
1. From this table, it is clear that the highest average cumulative reward is
obtained when the batch-size is $\Delta_{\mathsf{T}}=100$, and decreases
gradually as the batch-size increases. Finally, not that since we are not
detecting bad users in our experiments, the knowledge of $\mathsf{V}_{1}$ is
not required ($\mathsf{V}_{1}$ is only used to set $p_{\mathsf{T}}$). Notice
that $\mathsf{V}_{2}$ is used to set the batch-size $\Delta_{\mathsf{T}}$
correctly. Since an incorrect value of $\mathsf{V}_{2}$ results in a sub-
optimal value for $\Delta_{\mathsf{T}}$, computing the average cumulative
reward by iterating through different values of $\Delta_{\mathsf{T}}$ also
gives an idea about the sensitivity of our algorithms with respect to this
mis-specification. As can be seen from our results, the highest value of
$\mathsf{acc}\text{-}\mathsf{reward}({\mathsf{T}})$ was achieved when
$\Delta_{\mathsf{T}}=100$, while the
$\mathsf{acc}\text{-}\mathsf{reward}({\mathsf{T}})$ degrades gracefully with
the mis-specification of $\Delta_{\mathsf{T}}$ (or, $\mathsf{V}_{2}$).

$\Delta_{\mathsf{T}}$ | $\mathsf{acc}\text{-}\mathsf{reward}({\mathsf{T}})$
---|---
50 | 316.707
100 | 325.716
150 | 306.538
200 | 278.219
300 | 278.642
350 | 224.893
400 | 239.410
450 | 204.127
500 | 162.96
550 | 169.97
600 | 137.40
Table 1: Accumulated reward as a function of the batch-size:
$\Delta_{\mathsf{T}}=600$ corresponds to the static case, and
$\Delta_{\mathsf{T}}=100$ corresponds to the optimal value.

Next, we illustrate the benefit of our algorithm compared to the static
algorithm even in a stationary environment. To that end, we run Algorithm 1
with $\Delta_{\mathsf{T}}\in\\{100,600\\}$,
${\mathsf{T}}_{\mathsf{static}}\in\\{10,30,60,80,100\\}$, and assume a single
bin of size ${\mathsf{T}}=600$. Our results are presented in Fig. 2, and
perhaps surprisingly, Algorithm 1 with $\Delta_{\mathsf{T}}=100$ achieves a
better accumulated reward compared to $\Delta_{\mathsf{T}}=600$ (static
algorithm), for small values of ${\mathsf{T}}_{\mathsf{static}}$. The main
reason for this phenomenon is because for Algorithm 1 with
$\Delta_{\mathsf{T}}=600$, the neighbors of any user might not be well chosen
due to small values of $\mathsf{T}_{\mathsf{static}}$ because of which the
user will receive poor recommendations throughout the entire time frame. On
the other hand, running Algorithm 1 with $\Delta_{\mathsf{T}}=100$ restarts
Algorithm 2 at periodic intervals. As a result, the users have a good set of
neighbors in some batches and a bad set in others, but the cumulative reward
concentrate because the neighbors are independent across the batches. However,
the performance of the algorithm with $\Delta_{\mathsf{T}}=600$ improves as
${\mathsf{T}}_{\mathsf{static}}$ gets larger since the quality of the
estimated neighborhood improves. This experiment hits that it is better to
restart the recommendation algorithm periodically, i.e., follow Algorithm 1
(with $\Delta_{{\mathsf{T}}}<{\mathsf{T}}$) even in stationary environments.
We would like to emphasize that an insufficient number of samples for the
initial clustering, results in a worse accumulated reward for
$\Delta_{\mathsf{T}}=600$. In practice, however, the number of samples used
for the initial clustering might be difficult to determine a-priori. In that
situation, we suggest to restart the algorithm periodically with a small value
of $\mathsf{T}_{\mathsf{static}}$. Indeed, since the batches are independent,
the accumulated reward concentrates due to the law of large numbers.

Figure 1: The probability $\mathsf{a}_{u}/(\mathsf{a}_{u}+\mathsf{r}_{u})$ of
user $u$ liking a movie with Action tag but not Romance tag, for five
different users, across $10$ different bins/windows. Figure 2: Comparison of
Average Cumulative Reward $\mathsf{acc-reward(T)}$ for batchsize
$(\Delta_{{\mathsf{T}}})\in\\{100,600\\}$ and
${\mathsf{T}}_{\mathsf{static}}\in\\{10,30,60,80,100\\}$.

Next, we further compare the performance of our algorithm to the static case
[12], and to the Popularity Amongst Friends (PAF) algorithm [4]. We consider
the same setting as in [12]. In particular, we again quantize movie ratings
$\geq 4$ as $+1$ (likable), movie ratings $<3$ as $-1$ (unlikable), and
missing ratings as $0$. We consider the top ${\mathsf{N}}=250$ and
${\mathsf{M}}=500$ users and movies, respectively. This results in $\approx
80\%$ nonzero entries among the total number of entries in the rating matrix.
There are of course missing entries in the resulted rating matrix.
Accordingly, in our simulation if at a certain time, item $i$ was recommended
to user $u$, who has not rated that item, we receive $0$ reward. Despite that
we will still treat item $i$ as being consumed by user $u$, and accordingly,
item $i$ cannot be recommended to user $u$ again. Since we allow algorithms to
recommend an item to a given user only once, after
${\mathsf{T}}={\mathsf{M}}=500$ time steps, all items have been recommend to
all users. As before, the performance of the algorithms is measured in terms
of the average cumulative reward up to time ${\mathsf{T}}$.

Figure 3: The accumulated reward over time achieved by Algorithm Collaborative
and existing recommendation algorithm Popularity Amongst Friends [4], for
several values of the variation budget $\mathsf{V}\in\\{0,5,10\\}$, using
Movielens10m dataset.

In the simulation, we run Algorithm Collaborative with three different values
for the variation budget
$\mathsf{V}=\mathsf{V_{1}}=\mathsf{V_{2}}\in\\{0,5,10\\}$, and recall that
$\mathsf{V}=0$ corresponds to the static case [12]. The results are given in
Fig. 3. It is evident that Algorithm Collaborative significantly outperforms
PAF algorithm, a fact which was already observed in [12]. More importantly we
see that assuming that $\mathsf{V}=5$, and accordingly recommending in
batches, gives the best results among the other values of $\mathsf{V}$, and in
particular the static case. Except for coping with variations in the
preferences of users, this can be attributed also to _model mismatch_. To wit,
the static algorithm Recommend was designed for a certain probabilistic model
which may not capture certain phenomena in real-world datasets. Accordingly,
it might be the case that the algorithm will “stuck” on a certain wrong rating
trajectory which will hinder the rate at which likeable movies are
recommended. Working in batches, and by which letting the algorithm to
“restart” occasionally, may compensate for this mismatch. Finally, note that
the reason for the $\cap$-shape of the obtained curves is the fact that after
recommending most of the likable items (around $t\approx 310$), mostly
unlikable movies are left to recommend, until we exhaust all possible movies.

##  5 Conclusion and Outlook

In this paper, we introduced a novel model for online non-stationary
recommendation systems, where users may change their preferences over time
adversarially. For this model, we analyzed the performance of a CF
recommendation algorithm, and derived a lower bound on its achievable reward.

We hope our work has opened more doors than it closes. Apart from tightening
the obtained lower bound on the reward, there are several exciting directions
for future work. First, it is of significant importance to tackle the case
where the number of variations is unknown. Devising universal algorithms which
are oblivious to the knowledge of the non-stationarity, and proving
theoretical guarantees is quite challenging (see, for example, the recent
papers [34, 3, 18] where the problem of non-stationary MAB with unknown number
of variations was considered). Secondly, it is very interesting and
technically challenging to derive information-theoretic upper bounds on the
performance (reward) of any CF algorithm for the general model introduced in
this paper. The results of this paper can be rather directly generalized to
one-class recommendation systems where users only rate what they like and
never reveal what they dislike. It would be interesting to introduce and
analyze models which combines both content/graph information on top of the
collaborative filtering information. Also, while in this paper our ultimate
goal was to design recommender system which maximize the number of likes, in
some applications one might want to take into account other aspects, such as
fairness, novelty and multi-stakeholder recommender systems. Formally
analyzing such aspects has not been done, and is of practical and theoretical
importance. Finally, as was mentioned in the Appendix 4 there are several
inherent challenges with standard CF datasets used for simulating (non-
stationary) online recommender systems. Implementing a real interactive online
recommendation system and testing our algorithms over it is an important step
towards a complete understanding of CF based recommender systems.

## References

  * [1] R. Allesiardo, R. Féraud, and O. Maillard.  The non-stationary stochastic multi-armed bandit problem.  Int J Data Sci Anal, 3:267–283, 2017.
  * [2] P. Auer, N. Cesa-Bianchi, and P. Fischer.  Finite-time analysis of the multiarmed bandit problem.  Machine Learning, 47:235–256, 05 2002.
  * [3] P. Auer, P. Gajane, and R. Ortner.  Adaptively tracking the best bandit arm with an unknown number of distribution changes.  In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99, pages 138–158. PMLR, 25–28 Jun 2019.
  * [4] K. Barman and O. Dabeer.  Analysis of a collaborative filter based on popularity amongst neighbors.  IEEE Transactions on Information Theory, 58(12):7110–7134, Dec 2012\.
  * [5] P. Basile, A. Caputo, M. Degemmis, P. Lops, and G. Semeraro.  Modeling short-term preferences in time-aware recommender systems.  In UMAP Workshops, 2015.
  * [6] R. Bell, Y. Koren, and C. Volinsky.  Modeling relationships at multiple scales to improve accuracy of large recommender systems.  In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’07, pages 95–104, New York, NY, USA, 2007. ACM.
  * [7] A. Bellogin and J. Parapar.  Using graph partitioning techniques for neighbour selection in user-based collaborative filtering.  In Proceedings of the Sixth ACM Conference on Recommender Systems, RecSys ’12, pages 213–216. ACM, 2012.
  * [8] O. Besbes, Y. Gur, and A. Zeevi.  Stochastic multi-armed-bandit problem with non-stationary rewards.  In Advances in Neural Information Processing Systems 27, pages 199–207, 2014.
  * [9] O. Besbes, Y. Gur, and A. Zeevi.  Non-stationary stochastic optimization.  Operations Research, 63(5):1227–1244, 2015.
  * [10] Besbes Omer and Gur Yonatan and Zeevi Assaf.  Stochastic multi-armed-bandit problem with non-stationary reward.  In Proceedings of the 20th International Conference on Neural Information Processing Systems, pages 199–207, 2014.
  * [11] G. Biau, B. Cadre, and L. Rouvière.  Statistical analysis of k -nearest neighbor collaborative recommendation.  Ann. Statist., 38(3):1568–1592, 06 2010.
  * [12] G. Bresler, G. H. Chen, and D. Shah.  A latent source model for online collaborative filtering.  In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS’14, pages 3347–3355, 2014.
  * [13] G. Bresler and M. Karzand.  Regret bounds and regimes of optimality for user-user and item-item collaborative filtering.  arXiv:1711.02198, 2019.
  * [14] G. Bresler, D. Shah, and L. F. Voloch.  Collaborative filtering with low regret.  In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, SIGMETRICS ’16, pages 207–220, New York, NY, USA, 2016. ACM.
  * [15] S. Bubeck and N. Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  Foundations and Trends in Machine Learning, 5(1):1–122, 2012.
  * [16] L. Bui, R. Johari, and S. Mannor.  Clustered bandits.  CoRR, 2012.
  * [17] Y. Cao, W. Zheng, B. Kveton, and Y. Xie.  Nearly optimal adaptive procedure for piecewise-stationary bandit: a change-point detection approach.  In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
  * [18] Y. Chen, C.-W. Lee, H. Luo, and C.-Y. Wei.  A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free.  In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99, pages 696–726. PMLR, 25–28 Jun 2019.
  * [19] O. Dabeer.  Adaptive collaborating filtering: The low noise regime.  In 2013 IEEE International Symposium on Information Theory, pages 1197–1201, July 2013.
  * [20] A. S. Das, M. Datar, A. Garg, and S. Rajaram.  Google news personalization: Scalable online collaborative filtering.  In Proceedings of the 16th International Conference on World Wide Web, WWW ’07, pages 271–280, New York, NY, USA, 2007. ACM.
  * [21] Y. Deshpande and A. Montanari.  Linear bandits in high dimension and recommendation systems.  In Allerton Conference on Communication, Control, and Computation, pages 1750–1754, October 2012.
  * [22] M. D. Ekstrand, J. T. Riedl, and J. A. Konstan.  Collaborative filtering recommender systems.  Found. Trends Hum.-Comput. Interact., 4(2):81–173, Feb. 2011.
  * [23] F. Eskandanian and B. Mobasher.  Detecting changes in user preferences using hidden markov models for sequential recommendation tasks.  CoRR, abs/1810.00272, 2018.
  * [24] A. Garivier and E. Moulines.  On upper-confidence bound policies for non-stationary bandit problems.  06 2008.
  * [25] D. L. Gregory, A. J. Jennifer, and A. B. Eric.  Collaborative recommendations using item-to-item similarity mappings.  U.S. Patent 6266649B1, 1998.
  * [26] N. Hariri, B. Mobasher, and R. Burke.  Context adaptation in interactive recommender systems.  In RecSys 2014 - Proceedings of the 8th ACM Conference on Recommender Systems, pages 41–48, 10 2014.
  * [27] N. Hariri, B. Mobasher, and R. Burke.  Adapting to user preference changes in interactive recommendation.  In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), pages 4268–4274, 2015.
  * [28] C. Hartland, N. Baskiotis, S. Gelly, M. Sebag, and O. Teytaud.  Change point detection and meta-bandits for online learning in dynamic environments.  04 2011.
  * [29] R. Heckel and K. Ramchandran.  The sample complexity of online one-class collaborative filtering.  In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, pages 1452–1460. JMLR.org, 2017.
  * [30] J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl.  An algorithmic framework for performing collaborative filtering.  In Proceedings of the 22Nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’99, pages 230–237, New York, NY, USA, 1999. ACM.
  * [31] M. Jahrer, A. Töscher, and R. Legenstein.  Combining predictions for accurate recommender systems.  In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, pages 693–702, New York, NY, USA, 2010. ACM.
  * [32] K.-S. Jun, R. Willett, S. Wright, and R. Nowak.  Bilinear bandits with low-rank structure.  In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3163–3172. PMLR, 09–15 Jun 2019.
  * [33] B. Karahodza, H. Supic, and D. Donko.  An approach to design of time-aware recommender system based on changes in group user’s preferences.  In 2014 X International Symposium on Telecommunications (BIHTEL), pages 1–4, Oct 2014.
  * [34] Z. S. Karnin and O. Anava.  Multi-armed bandits: Competing with optimal sequences.  In Advances in Neural Information Processing Systems 29, pages 199–207. 2016.
  * [35] R. Kleinberg, A. Niculescu-Mizil, and Y. Sharma.  Regret bounds for sleeping experts and bandits.  volume 80, pages 425–436, 01 2008.
  * [36] Y. Koren.  Factorization meets the neighborhood: A multifaceted collaborative filtering model.  In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, pages 426–434, New York, NY, USA, 2008. ACM.
  * [37] B. Kveton, C. Szepesvari, A. Rao, Z. Wen, Y. Abbasi-Yadkori, and S. Muthukrishnan.  Stochastic low-rank bandits, 2017.
  * [38] G. Linden, B. Smith, and J. York.  Amazon.com recommendations: item-to-item collaborative filtering.  IEEE Internet Computing, 7(1):76–80, Jan 2003.
  * [39] J. Liu, E. Pedersen, and P. Dolan.  Personalized news recommendation based on click behavior.  In 2010 International Conference on Intelligent User Interfaces, 2010.
  * [40] X. Liu.  Modeling users’ dynamic preference for personalized recommendation.  In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI’15, pages 1785–1791, 2015.
  * [41] H. Luo, A. Agarwal, and J. Langford.  Efficient contextual bandits in non-stationary worlds.  In COLT, 2017.
  * [42] J. L. Moore, S. Chen, T. Joachims, and D. Turnbull.  Taste over time: the temporal dynamics of user preferences.  In ISMIR, 2013.
  * [43] S. Mukherjee, H. Lamba, and G. Weikum.  Item recommendation with evolving user preferences and experience.  CoRR, abs/1705.02519, 2017.
  * [44] S. Pandey, D. Chakrabarti, and D. Agarwal.  Multi-armed bandit problems with dependent arms.  pages 721–728, 01 2007.
  * [45] J. D. M. Rennie and N. Srebro.  Fast maximum margin matrix factorization for collaborative prediction.  In Proceedings of the 22Nd International Conference on Machine Learning, ICML ’05, pages 713–719, New York, NY, USA, 2005. ACM.
  * [46] P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl.  Grouplens: An open architecture for collaborative filtering of netnews.  In Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work, CSCW ’94, pages 175–186, New York, NY, USA, 1994. ACM.
  * [47] R. Salakhutdinov and A. Mnih.  Probabilistic matrix factorization.  In Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS’07, pages 1257–1264, USA, 2007.
  * [48] R. Salakhutdinov and A. Mnih.  Bayesian probabilistic matrix factorization using markov chain monte carlo.  In Proceedings of the 25th International Conference on Machine Learning, ICML ’08, pages 880–887, New York, NY, USA, 2008. ACM.
  * [49] B. Sarwar, G. Karypis, J. Konstan, and J. Riedl.  Analysis of recommendation algorithms for e-commerce.  In Proceedings of the 2Nd ACM Conference on Electronic Commerce, EC ’00, pages 158–167, New York, NY, USA, 2000. ACM.
  * [50] B. Sarwar, G. Karypis, J. Konstan, and J. Riedl.  Item-based collaborative filtering recommendation algorithms.  In Proceedings of the 10th International Conference on World Wide Web, WWW ’01, pages 285–295, New York, NY, USA, 2001. ACM.
  * [51] R. Sen, K. Shanmugam, M. Kocaoglu, A. Dimakis, and S. Shakkottai.  Contextual Bandits with Latent Confounders: An NMF Approach.  In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 518–527. PMLR, 20–22 Apr 2017.
  * [52] F. Shi, C. Ghedira, and J. Marini.  Context adaptation for smart recommender systems.  IT Professional, 17(6):18–26, Nov 2015.
  * [53] L. Si and R. Jin.  Flexible mixture model for collaborative filtering.  In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML’03, pages 704–711. AAAI Press, 2003.
  * [54] I. Sutskever, J. B. Tenenbaum, and R. R. Salakhutdinov.  Modelling relational data using bayesian clustered tensor factorization.  In Advances in Neural Information Processing Systems 22, pages 1821–1828. 2009.
  * [55] W. R. Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  Biometrika, 25(3/4):285–294, 1933.
  * [56] J. Y. Yu and S. Mannor.  Piecewise-stationary bandit problems with side observations.  In Proceedings of the 26th Annual International Conference on Machine Learning, ICML’09, page 1177–1184, 2009.
  * [57] P. Zhao, L. Zhang, Y. Jiang, and Z.-H. Zhou.  A simple approach for non-stationary linear bandits.  In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 746–755. PMLR, 26–28 Aug 2020.

##  Appendix A Proof of Theorem 1

To prove Theorem 1, we establish first a few accompanying results. We start
with the following lemma which bounds the probability that user of different
(same) type have the same response. For this lemma, we assume that users
_cannot_ change their type over time, and denote the type of user
$u\in[{\mathsf{N}}]$ by ${\cal T}_{u}$.

######  Lemma 1 (Same Response Lemma).

Consider the latent source model and the incoherence Assumption A3. Let $\ell$
be an item chosen uniformly at random from $[{\mathsf{M}}]$. Then, the
probability that two users $u$ and $v$ rate $\ell$ in the same way is:

$\displaystyle\mathbb{P}\left[\mathbf{R}_{u\ell}=\mathbf{R}_{v\ell}|{\cal
T}_{u}\neq{\cal T}_{v}\right]\leq 2\gamma_{1}\Delta^{2}+\frac{1}{2},$ (6)

for users of different types, and,

$\displaystyle\mathbb{P}\left[\mathbf{R}_{u\ell}=\mathbf{R}_{v\ell}|{\cal
T}_{u}={\cal T}_{v}\right]\geq 2\gamma_{2}\Delta^{2}+\frac{1}{2},$ (7)

for users of the same type.

###### Proof.

Notice that for two users $u$ and $v$ belonging to different user groups, the
probability in question is

$\displaystyle\mathbb{P}\left[\mathbf{R}_{u\ell}=\mathbf{R}_{v\ell}|{\cal
T}_{u}\neq{\cal T}_{v}\right]$
$\displaystyle=\frac{1}{{\mathsf{M}}}\sum_{i=1}^{{\mathsf{M}}}\left[p_{u,i}p_{v,i}+(1-p_{u,i})(1-p_{v,i})\right]$
$\displaystyle\quad=\frac{1}{{\mathsf{M}}}\sum_{i=1}^{{\mathsf{M}}}\left[\frac{(2p_{u,i}-1)(2p_{v,i}-1)}{2}+\frac{1}{2}\right]$
$\displaystyle\quad=\frac{1}{{\mathsf{M}}}\langle
2{\mathbf{p}}_{u}-\mathbf{1},2{\mathbf{p}}_{v}-\mathbf{1}\rangle+\frac{1}{2}$
$\displaystyle\quad\leq 2\gamma_{1}\Delta^{2}+\frac{1}{2},$

where the inequality follows from the incoherence Assumption A3. Similarly,
for two users of the same type,

$\displaystyle\mathbb{P}\left[\mathbf{R}_{u\ell}=\mathbf{R}_{v\ell}|{\cal
T}_{u}={\cal T}_{v}\right]$ $\displaystyle=\frac{1}{{\mathsf{M}}}\langle
2{\mathbf{p}}_{u}-\mathbf{1},2{\mathbf{p}}_{v}-\mathbf{1}\rangle+\frac{1}{2}$
$\displaystyle\geq 2\gamma_{2}\Delta^{2}+\frac{1}{2},$

where, again, the inequality follows from the coherence Assumption A3. ∎

The following lemma gives a condition on the number of random recommendations
needed for the cosine-similarity test to output the correct clustering with
high probability, assuming that no variations happened during the test. We
establish a few notations. Let ${\cal
T}_{\mathsf{test}}\subseteq[{\mathsf{M}}]$ be a set of $\mathsf{L}$ items
chosen uniformly at random from ${\mathsf{M}}$. Let
$\mathsf{Y}_{u,v}\in\\{0,1\\}$ be a binary variable indicating whether $(u,v)$
are in the same cluster or not, for $u,v\in[{\mathsf{N}}]$. Using the
responses $\\{\mathbf{R}_{u,i}\\}_{u\in[{\mathsf{N}}],i\in{\cal
T}_{\mathsf{test}}}$, we would like to infer the values of $\mathsf{Y}_{u,v}$
for all $u,v\in[{\mathsf{N}}]$. For any pair of distinct users
$u,v\in[{\mathsf{N}}]$, let $\mathsf{X}_{u,v}$ be the random variable
corresponding to the number of items for which $u$ and $v$ had the same
responses. Finally, we let

$\displaystyle\hat{\mathsf{Y}}_{u,v}=\begin{cases}1,\
&\mathrm{if}\;\mathsf{X}_{u,v}\geq\lambda\cdot\mathsf{L}\\\ 0,\
&\mathrm{otherwise},\end{cases}$ (8)

for some $\lambda\geq 0$. We have the following result.

######  Lemma 2.

Consider the latent source model and the incoherence Assumption A3. Let
$\delta\in(0,1)$. For any
$\mathsf{L}\geq\frac{2\log(3{\mathsf{N}}^{2}/\delta)}{\Delta^{4}(\gamma_{2}-\gamma_{1})^{2}}\triangleq\mathsf{T_{static}}$,
and any $\lambda\in[\lambda_{-},\lambda_{+}]$ with
$\lambda_{-}=2\gamma_{1}\Delta^{2}+\frac{1}{2}+\sqrt{\frac{2}{\mathsf{L}}\log(3{\mathsf{N}}^{2}/\delta)}$
and
$\lambda_{+}=2\gamma_{2}\Delta^{2}+\frac{1}{2}-\sqrt{\frac{2}{\mathsf{L}}\log(3{\mathsf{N}}^{2}/\delta)}$,
the test in (8) discriminates between $\mathsf{Y}_{u,v}=0$ and
$\mathsf{Y}_{u,v}=1$, for any pair of users $u,v\in[{\mathsf{N}}]$, with
probability at least $1-\delta/3$.

###### Proof.

First, it is clear that Lemma 1 implies that

$\displaystyle\mathbb{E}\left[\mathsf{X}_{u,v}|\mathsf{Y}_{u,v}=0\right]\leq\mathsf{L}\Big{(}2\gamma_{1}\Delta^{2}+\frac{1}{2}\Big{)},$
$\displaystyle\mathbb{E}\left[\mathsf{X}_{u,v}|\mathsf{Y}_{u,v}=1\right]\geq\mathsf{L}\Big{(}2\gamma_{2}\Delta^{2}+\frac{1}{2}\Big{)}.$

Then, we note that $\mathsf{X}_{u,v}$ is a sum of $\mathsf{L}$ random
variables in $[-1,1]$, drawn without replacement from $[{\mathsf{M}}]$.
Accordingly, Hoeffding’s inequality gives,

$\displaystyle\mathbb{P}\left[\left.\mathsf{X}_{u,v}\geq\lambda_{-}\cdot\mathsf{L}\right|\mathsf{Y}_{u,v}=0\right]$
$\displaystyle\leq\exp\left[-\frac{\left(\lambda_{-}\cdot\mathsf{L}-\mathbb{E}\left[\mathsf{X}_{u,v}|\mathsf{Y}_{u,v}=0\right]\right)^{2}}{2\mathsf{L}}\right]$
(9)
$\displaystyle\leq\exp\left[-\frac{\left(\lambda_{-}-2\gamma_{1}\Delta^{2}-\frac{1}{2}\right)^{2}}{2}\mathsf{L}\right],$
(10)

and

$\displaystyle\mathbb{P}\left[\left.\mathsf{X}_{u,v}\leq\lambda_{+}\cdot\mathsf{L}\right|\mathsf{Y}_{u,v}=1\right]$
$\displaystyle\leq\exp\left[-\frac{\left(2\gamma_{2}\Delta^{2}+\frac{1}{2}-\lambda_{+}\right)^{2}}{2}\mathsf{L}\right].$
(11)

Therefore, taking
$\lambda_{-}=2\gamma_{1}\Delta^{2}+\frac{1}{2}+\sqrt{\frac{2}{\mathsf{L}}\log(3{\mathsf{N}}^{2}/\delta)}$
and
$\lambda_{+}=2\gamma_{2}\Delta^{2}+\frac{1}{2}-\sqrt{\frac{2}{\mathsf{L}}\log(3{\mathsf{N}}^{2}/\delta)}$,
we obtain that

$\displaystyle\mathbb{P}\left[\left.\mathsf{X}_{u,v}\geq\lambda_{-}\cdot\mathsf{L}\right|\mathsf{Y}_{u,v}=0\right]$
$\displaystyle\leq\frac{\delta}{3{\mathsf{N}}^{2}},$ (12)

and

$\displaystyle\mathbb{P}\left[\left.\mathsf{X}_{u,v}\leq\lambda_{+}\cdot\mathsf{L}\right|\mathsf{Y}_{u,v}=1\right]$
$\displaystyle\leq\frac{\delta}{3{\mathsf{N}}^{2}}.$ (13)

Picking any $\lambda\in[\lambda_{-},\lambda_{+}]$, we can see that the bounds
in (12)–(13), with $\lambda_{-}$ and $\lambda_{+}$ replaced by $\lambda$. This
is equivalent to
$\mathbb{P}\left[\left.\hat{\mathsf{Y}}_{u,v}\neq\mathsf{Y}_{u,v}\right|\mathsf{Y}_{u,v}=\ell\right]\leq\delta/(3{\mathsf{N}}^{2})$,
for $\ell=0,1$. Such $\lambda$ exists if $\lambda_{+}\geq\lambda_{-}$, which
holds whenever,

$\displaystyle\mathsf{L}\geq\frac{2\log(3{\mathsf{N}}^{2}/\delta)}{\Delta^{4}(\gamma_{2}-\gamma_{1})^{2}}=\mathsf{T_{static}}.$
(14)

Finally, taking a union bound over all pairs of users (we trivially have at
most $\mathsf{N}^{2}$ such pairs) we conclude that we can correctly infer the
values of $\mathsf{Y}_{u,v}$ for all $u,v\in[{\mathsf{N}}]$ (and therefore
cluster all such pairs of users correctly), with probability at least
$1-\delta/3$, as claimed. ∎

We would like to mention here that the test described above can only
distinguish between whether $\mathsf{Y}_{u,v}=1$ or $\mathsf{Y}_{u,v}=0$,
_assuming_ that users did not change their type during the test. If, however,
a test is conducted when there are switches, we can still infer the clustering
of those users who have not changed during the test correctly.

We are now in a position to prove Theorem 1. With some abuse of notation, let
us denote by $\mathsf{reward}({\cal B}_{\ell})$ the expected reward
accumulated in batch ${\cal B}_{\ell}$, i.e.,

$\displaystyle\mathsf{reward}({\cal B}_{\ell})$
$\displaystyle\triangleq\mathbb{E}\left[\sum_{t\in{\cal
B}_{\ell}}\frac{1}{{\mathsf{N}}}\sum_{u=1}^{{\mathsf{N}}}\mathds{1}[\mathbf{R}_{u\pi_{u,t}}=1]\right]$
$\displaystyle=|{\cal B}_{\ell}|-\mathbb{E}\left[\sum_{t\in{\cal
B}_{\ell}}\frac{1}{{\mathsf{N}}}\sum_{u=1}^{{\mathsf{N}}}\mathds{1}[\mathbf{R}_{u\pi_{u,t}}=0]\right]$
$\displaystyle\triangleq|{\cal B}_{\ell}|-\mathsf{regret}({\cal B}_{\ell}),$
(15)

where $\mathsf{regret}({\cal B}_{\ell})$ is the regret accumulated during
batch ${\cal B}_{\ell}$. As can be seen from Algorithm Collaborative, we
decompose the recommendation horizon ${\mathsf{T}}$ to a sequence of batches
of size $\Delta_{\mathsf{T}}$ each. To obtain Theorem 1, we will relate the
total reward/regret with the local reward/regret of the static algorithm
Recommend. Specifically, let ${\cal B}_{\ell}$, for
$\ell=1,2,\ldots,\left\lceil{\mathsf{T}}/\Delta_{\mathsf{T}}\right\rceil$,
denote the $\ell$’th batch of size $\Delta_{\mathsf{T}}$, and let $t_{{\cal
B}_{\ell}}$ be the ending time of batch ${\cal B}_{\ell}$. We will keep track
of a set of users $\mathcal{V}_{t}\subseteq[{\mathsf{N}}]$ which will include
all those users for whom we have been able to identify that they have have
changed their user groups at some point of time during the batch
$\mathcal{B}_{\ell}$. We initialize
$\mathcal{V}_{t_{\mathcal{B}_{\ell-1}}+1}=\phi$ at the beginning of the batch
to be the empty set. We define

$\displaystyle\mathsf{V}_{\mathcal{B}_{\ell},1}\triangleq\sum_{t\in{\cal
B}_{\ell}\setminus t_{{\cal B}_{\ell}}}\mathds{1}\left[{\cal
T}_{u}(t)\neq{\cal T}_{u}(t+1),\;\text{for some}\;u\in[{\mathsf{N}}]\right],$
(16)

as the number of variations that have occurred during the batch
$\mathcal{B}_{\ell}$. Furthermore, we let

$\displaystyle\mathsf{V}_{\mathcal{B}_{\ell},2}\triangleq\frac{1}{{\mathsf{N}}}\sum_{u\in[N]}\sum_{t\in{\cal
B}_{\ell}\setminus t_{{\cal B}_{\ell}}}\mathds{1}\left[{\cal
T}_{u}(t)\neq{\cal T}_{u}(t+1)\right],$ (17)

as the total number of variations that have occurred during the batch
$\mathcal{B}_{\ell}$. For $\tau\in\mathcal{B}_{\ell}$, we define
$\mathsf{Z}_{\tau}$ to be an indicator random variable which is unity if some
user switches its type in a window of $2\cdot\mathsf{T_{static}}$ around round
$\tau$ within the batch $\mathcal{B}_{\ell}$. For $\tau\in\mathcal{B}_{\ell}$,
let us denote $\mathsf{W}_{\tau}:=\\{\max\\{\tau-\mathsf{T_{static}},t_{{\cal
B}_{\ell-1}+1}\\},\dots,\min\\{\tau+\mathsf{T_{static}},t_{{\cal
B}_{\ell}}\\}\\}$ as the window of size $2\cdot\mathsf{T_{static}}$ around
$\tau$. Then, note that $\mathsf{Z}_{\tau}$ can be written as

$\displaystyle\mathsf{Z}_{\tau}=\mathds{1}\left[\sum_{u\in[{\mathsf{N}}]}\sum_{t\in\mathsf{W}_{\tau}}\mathds{1}\left[{\cal
T}_{u}(t)\neq{\cal T}_{u}(t+1)\right]>0\right].$ (18)

As can be seen from Algorithm Recommend, at every round in each batch, we
start a test with probability $1/\sqrt{\Delta_{{\mathsf{T}}}}$, which involves
recommending randomly sampled items to every user for $\mathsf{T_{static}}$
rounds. After each such test, we can use Lemma 2 to partition the set of
users. In addition, in the fourth step of Algorithm Recommend we conduct a
_reference test_ at the beginning of the batch. In the sequel, we denote this
test by $\mathsf{Test}_{0}$, and further denote the $(j+1)^{\mathsf{th}}$ test
by $\mathsf{Test}_{j}$. The partition induced by the $(j+1)^{\mathsf{th}}$
test is denoted by $\mathcal{P}_{\mathsf{Test}_{j}}$. By comparing the
partitions $\mathcal{P}_{\mathsf{Test}_{j}}$ and
$\mathcal{P}_{\mathsf{Test}_{0}}$, we will be able to partially identify users
who have changed their user groups in the batch. This is done in Algorithm
Test. We will call those users who have changed their user groups in a
particular batch as bad users and those users who have not changed their user
groups throughout the batch as good users. Moreover, a user is also good until
he changes his user group and will be denoted as bad from the round he changes
his group. In order to bound the regret over each batch we will consider the
following three cases:

  * •

Case 1: Consider the situation where at least $2/3$ of the users of any
particular user group have changed their user group. We denote this event by
$\mathcal{E}_{1}$. In such a case, we will upper bound the regret in the batch
$\mathcal{B}_{\ell}$ by $\mathsf{\Delta}_{T}$. Notice that, since
$\mathsf{V}_{\mathcal{B}_{\ell},2}\geq\frac{2\nu}{3}$, therefore conditioned
on ${\cal E}_{1}$, we have
$\mathsf{regret}(\mathcal{B}_{\ell})\leq\frac{3\Delta_{\mathsf{T}}\mathsf{V}_{\mathcal{B}_{\ell},2}}{2\nu}$.

  * •

Case 2: In this case, we will assume that for every user group, at most $1/3$
of the users change their user groups in the batch. For any test
$\mathcal{P}_{\mathsf{Test}_{j}}$, notice that we can actually end up with
more than $\mathsf{K}$ clusters (say we have $\mathsf{K}^{\prime}$ clusters)
because of variations. In that case, we will identify all the users in the
smallest $\mathsf{K}^{\prime}-\mathsf{K}$ clusters as users who have changed
their user group. Note that, it is possible that we make a mistake in this
process because one of the clusters in the smallest
$\mathsf{K}^{\prime}-\mathsf{K}$ clusters might correspond to good users who
have not changed their user group. This, however, must mean that a larger
cluster among the largest $\mathsf{K}$ clusters must correspond to users who
have changed. This in turn implies that at least $\frac{2\nu\mathsf{N}}{3}$
users have changed since the size of the smaller cluster corresponding to
users who do not change their group throughout the batch $\mathcal{B}_{\ell}$
is at least $\frac{2\nu{\mathsf{N}}}{3}$. We will denote this event by
$\mathcal{E}_{2}$. As in the previous case, we trivially upper bound the
regret in the batch $\mathcal{B}_{\ell}$ by $\Delta_{\mathsf{T}}$, and
similarly to Case 1, we have
$\mathsf{regret}(\mathcal{B}_{\ell})\leq\frac{3\Delta_{\mathsf{T}}\mathsf{V}_{\mathcal{B}_{\ell},2}}{2\nu}$,
conditioned on ${\cal E}_{2}$.

  * •

Case 3: In this case, as in the previous case, we assume that for every user
group, at most $1/3$ of the users change their user groups in the batch.
Contrary to the previous case, we will also assume that in every test with
more than $\mathsf{K}$ clusters (say, $\mathsf{K}^{\prime}$ clusters), the
users in the smallest $\mathsf{K}^{\prime}-\mathsf{K}$ users correspond to
users who have changed their user group. For a future test $j$ started at
round $\tau_{\mathsf{test},j}$ such that
$\mathsf{Z}_{\tau_{\mathsf{test},j},u}=0$, we will compare the partitions
$\mathcal{P}_{\mathsf{Test}_{0}}$ and $\mathcal{P}_{\mathsf{Test}_{j}}$ by
establishing a bijective mapping between the clusters of the two partitions.
For every cluster $\mathcal{C}$ in $\mathcal{P}_{\mathsf{Test}_{0}}$, we can
find a cluster $\mathcal{C}^{\prime}$ in $\mathcal{P}_{\mathsf{Test}_{j}}$
such that at least two-thirds of the elements in
$\mathcal{C},\mathcal{C^{\prime}}$ are common. Subsequently, for all those
users in $\mathcal{C}$ which are not present in $\mathcal{C}^{\prime}$, we
correctly identify them as users who have changed their user groups. For a
pair of distinct users $(u,v)\subset[{\mathsf{N}}]\times[{\mathsf{N}}]$
belonging to the same user group at the beginning of the batch
$\mathcal{B}_{\ell}$, we call them interesting if one of them have changed
their user group. Note that, for any pair of interesting users $(u,v)$ where
one of them have changed their user group at any round after the reference
test is conducted and remains in different user group before the
$(j+1)^{\mathsf{th}}$ test is started will belong to different clusters in
$\mathcal{P}_{\mathsf{Test}_{j}}$. Note that it is possible that
$\mathsf{Z}_{t_{\mathcal{B}_{\ell-1}}+1,u}=1$, i.e., some user $u$ might
change their user group during the first $\mathsf{T_{static}}$ rounds when the
reference test is being conducted. Since we can label the top $\mathsf{K}$
clusters (by the corresponding user-group) returned by the reference test as
we know that two-thirds users of every user group did not change. We denote by
$\mathcal{P}_{\mathsf{Test}_{0}}(u)$ the cluster (label) $u$ belongs to in the
partition returned by the reference test $\mathsf{Test}_{0}$. Let us define an
indicator random variable $\mathsf{L}_{u}$ which is unity if user $u$ has
changed his user group in the first $\mathsf{T_{static}}$ rounds. Consider
such a user $u$ for which $\mathsf{L}_{u}=1$. In that case, three things are
possible at the end of the reference test:

    1. 1.

$u$ might belong to the smallest $\mathsf{K}^{\prime}-\mathsf{K}$ clusters in
the reference test in which case $u$ is identified as a user who has changed
his user group and he is not involved in the main algorithm started after the
reference test, i.e., $u$ is added to the set
$\mathcal{V}_{\mathsf{T_{static}}}$. We define an indicator random variable
$\mathsf{X}_{u,1}$ which is unity if user $u$ has changed his user group
during the first $\mathsf{T_{static}}$ rounds in the batch, and is returned in
the smallest $\mathsf{K}^{\prime}-\mathsf{K}$ clusters at the end of the
reference test.

    2. 2.

$u$ belongs to the cluster corresponding to his new user group in which case
we will not be able to infer that $u$ has changed his user group. In this
case, we will consider $u$ to be a good user unless he changes his user group
later. We will consider his user group at the end of the reference test
($\mathcal{P}_{\mathsf{Test}_{0}}(u)$ which is same as
$\mathcal{T}_{u}(t_{\mathcal{B}_{\ell-1}}+1+\mathsf{T_{static}})$) to be his
actual user group. We will call this a special case and we define an indicator
random variable
$\mathsf{X}_{u,2}\triangleq\mathds{1}[\mathcal{P}_{\mathsf{test}_{0}}(u)=\mathcal{T}_{u}(t_{\mathcal{B}_{\ell-1}}+1+\mathsf{T_{static}})]$
which is unity if user $u$ changes his user group during the first
$\mathsf{T_{static}}$ rounds in the batch, and belongs to his final user group
(the user group he belongs to at the end of the reference test).

    3. 3.

$u$ remains in his original user group (or an intermediate user group if he
changes his user group multiple times during the reference test). We define an
indicator random variable $\mathsf{X}_{u,3}$ which is unity if the user
changes his user group in the first $\mathsf{T_{static}}$ rounds and does not
belong to his final user group (the user group he belongs to at the end of the
reference test) at the end of the reference test, i.e.,
$\mathsf{X}_{u,3}\triangleq\mathds{1}[\mathcal{P}_{\mathsf{test}_{0}}(u)\neq\mathcal{T}_{u}(t_{\mathcal{B}_{\ell-1}}+1+\mathsf{T_{static}})]$.
For a round $\tau>\mathsf{T_{static}}$ in ${\cal B}_{\ell}$, we will define an
indicator random variable
$\mathsf{J}_{u,\tau}=\mathds{1}[\mathcal{T}_{u}(\tau)\neq\mathcal{P}_{\mathsf{Test}_{0}}(u)]$,
which is unity if user $u$ is in a different group at round $\tau$ than the
user group of $u$ that was returned by the reference test.

We are now in a position to bound the regret over each batch. To that end, we
will decompose the regret into a few terms and analyze the contribution of
each term separately. First, as we described above conditioned on Cases 1 and
2, namely, ${\cal A}\triangleq{\cal E}_{1}\cup{\cal E}_{2}$ we have

$\displaystyle\mathsf{regret}({\cal B}_{\ell}|{\cal A})$
$\displaystyle\triangleq\frac{1}{{\mathsf{N}}}\sum_{t\in\mathcal{B}_{\ell}\setminus{\cal
T}_{\mathsf{test,\ell}}}\sum_{u\in[{\mathsf{N}}]}\mathbb{E}\left[\mathds{1}\left[\mathbf{R}_{u,\pi_{u,t}}=0\mid\mathcal{A}\right]\right]$
(19)
$\displaystyle\leq\frac{3\Delta_{{\mathsf{T}}}\mathsf{V}_{\mathcal{B}_{\ell},2}}{2\nu}.$
(20)

Next, we analyze Case 3, where we condition on ${\cal A}^{c}$, namely,

$\displaystyle\mathsf{regret}({\cal B}_{\ell}|{\cal
A}^{c})\triangleq\frac{1}{{\mathsf{N}}}\sum_{t\in\mathcal{B}_{\ell}\setminus{\cal
T}_{\mathsf{test,\ell}}}\sum_{u\in[{\mathsf{N}}]}\mathbb{E}\left[\mathds{1}\left[\mathbf{R}_{u,\pi_{u,t}}=0\mid\mathcal{A}^{c}\right]\right].$
(21)

We do that by considering each of the sub-cases listed above.

###  A.1 Variations When Testing

We bound the regret for those rounds in the batch for which
$\mathsf{Z}_{\tau}=1$. Specifically, for a round $\tau\in\mathcal{B}_{\ell}$,
we denote the event $\mathcal{E}_{\tau,1}$ when $\mathsf{Z}_{\tau}=1$, which
by definition imply that there is a variation in a window of size
$2\cdot\mathsf{T_{static}}$ around round $\tau$ for some user. In particular,
using the definitions in (16) and (18), we note that

$\displaystyle\sum_{\tau\in\mathcal{B}_{\ell}\setminus{\cal
T}_{\mathsf{test,\ell}}}\mathsf{Z}_{\tau}$
$\displaystyle\leq\sum_{\tau\in\mathcal{B}_{\ell}}\sum_{t\in\mathsf{W}_{\tau}}\mathds{1}\left[{\cal
T}_{u}(t)\neq{\cal T}_{u}(t+1),\;\text{for some }u\in[{\mathsf{N}}]\right]$
(22) $\displaystyle\leq
2\cdot\mathsf{V}_{\mathcal{B}_{\ell},1}\cdot\mathsf{T_{static}}.$ (23)

Therefore, we can bound the regret in those rounds and users where
$\mathsf{Z}_{\tau}=1$ by

$\displaystyle\mathsf{A}_{2}$
$\displaystyle\triangleq\frac{1}{{\mathsf{N}}}\mathbb{E}\left[\sum_{t\in\mathcal{B}_{\ell}\setminus{\cal
T}_{\mathsf{test,\ell}}}\sum_{u\in[{\mathsf{N}}]:\mathsf{Z}_{t}=1}\mathds{1}\left[\mathbf{R}_{u,\pi_{u,t}}=0\mid\mathcal{A}^{c}\right]\right]$
(24)
$\displaystyle\leq\mathbb{E}\left[\sum_{\tau\in\mathcal{B}_{\ell}}\mathds{1}\left[\mathsf{Z}_{t}=1\right]\right]$
(25) $\displaystyle\leq
2\cdot\mathsf{V}_{\mathcal{B}_{\ell},1}\cdot\mathsf{T_{static}}.$ (26)

###  A.2 Regret Due To Testing

We bound the regret for those rounds where we test in Algorithm Recommend.
Specifically, for a round $\tau\in\mathcal{B}_{\ell}$, we define the indicator
random variable $\mathsf{Y}_{\tau}$ which is unity when a test is being
conducted at the round $\tau$. We have

$\displaystyle\mathsf{A}_{3}$
$\displaystyle\triangleq\frac{1}{{\mathsf{N}}}\mathbb{E}\left[\sum_{t\in\mathcal{B}_{\ell}\setminus{\cal
T}_{\mathsf{test,\ell}}:\mathsf{Y}_{\tau}=1}\sum_{u\in[{\mathsf{N}}]}\mathds{1}\left[\mathbf{R}_{u,\pi_{u,t}}=0\mid\mathcal{A}^{c}\right]\right]$
(27)
$\displaystyle\leq\mathbb{E}\left[\sum_{t\in\mathcal{B}_{\ell}}\mathds{1}\left[\mathsf{Y}_{\tau}=1\right]\right]$
(28) $\displaystyle\leq\Delta_{\mathsf{T}}\cdot p\cdot\mathsf{T_{static}},$
(29)

where we have used the fact that
$\mathbb{P}[\mathsf{Y}_{\tau}=1]=\mathbb{P}[\tau\in\mathrm{Test}]=p$, $|{\cal
B}_{\ell}|=\Delta_{{\mathsf{T}}}$, and each test takes $\mathsf{T_{static}}$
rounds.

###  A.3 Undetected Bad Users

For a user $u\in[{\mathsf{N}}]$, we define an indicator random variable
$\mathsf{B}_{u,t}$ which is unity if the user is not included in the set of
bad users $\mathcal{V}_{t}$ at round $t\in\mathcal{B}_{\ell}$. Furthermore,
for a round $t$ after the reference test, namely, $t\in{\cal
B}_{\ell}\setminus{\cal T}_{\mathsf{test},\ell}$, where ${\cal
T}_{\mathsf{test},\ell}\triangleq[t_{\mathcal{B}_{\ell-1}}+1,\ldots,t_{\mathcal{B}_{\ell-1}}+\mathsf{T_{static}}]$,
define an indicator random variable $\mathsf{H}_{t}$ which is unity if there
is a bad user which is undetected (or, untested) involved in the algorithm. As
we explain Below this random variable can be decomposed into the union of
three sub-cases which we discussed above. For any round $t\in{\cal
B}_{\ell}\setminus{\cal T}_{\mathsf{test},\ell}$, we have:

  * •

A user $u$ who satisfies
$\mathsf{L}_{u}=1,\mathsf{B}_{u,t}=1,\mathsf{X}_{u,3}=1,\mathsf{J}_{u,t}=1$
and $\mathsf{Z}_{t}=0$, is one who has changed his user group in the first
$\mathsf{T_{static}}$ rounds in the batch, was not in his final user group at
the end of the reference test, and his user group at round $t$ is different
from his user group that was returned by the reference test, i.e.,

$\displaystyle\mathcal{T}_{u}(t_{\mathcal{B}_{\ell-1}}+1+\mathsf{T_{static}})\neq\mathcal{P}_{\mathsf{Test}_{0}}(u)\quad\text{and}\quad\mathcal{T}_{u}(t)\neq\mathcal{P}_{\mathsf{Test}_{0}}(u).$

  * •

A user $u$ who satisfies
$\mathsf{L}_{u}=1,\mathsf{B}_{u,t}=1,\mathsf{X}_{u,2}=1,\mathsf{J}_{u,t}=1$
and $\mathsf{Z}_{t}=0$, is one who has changed his user group in the first
$\mathsf{T_{static}}$ rounds in the batch, and his user group at the end of
the reference test is also same as the one provided by the estimate of the
reference test, but his user group at round $t$ is different from his user
group at the end of the reference test, i.e.,

$\displaystyle\mathcal{T}_{u}(t_{\mathcal{B}_{\ell-1}}+1+\mathsf{T_{static}})=\mathcal{P}_{\mathsf{Test}_{0}}(u)\quad\text{and}\quad\mathcal{T}_{u}(t)\neq\mathcal{P}_{\mathsf{Test}_{0}}(u).$

  * •

A user $u$ who satisfies
$\mathsf{L}_{u}=0,\mathsf{B}_{u,t}=1,\mathsf{J}_{u,t}=1$ and
$\mathsf{Z}_{t}=0$ is one who has not changed his user group in the first
$\mathsf{T_{static}}$ rounds in the batch, but his user group at round $t$ is
different from his user group at the beginning of the batch, i.e.,

$\displaystyle\mathcal{T}_{u}(t_{\mathcal{B}_{\ell-1}}+1+\mathsf{T_{static}})=\mathcal{T}_{u}(t),\quad\text{for}\;t\in{\cal
T}_{\mathsf{test},\ell},$
$\displaystyle\mathcal{T}_{u}(t)\neq\mathcal{P}_{\mathsf{Test}_{0}}(u).$

Given the above three sub-cases, it is clear that $\mathsf{H}_{t}$ for
$t\in{\cal B}_{\ell}\setminus{\cal T}_{\mathsf{test},\ell}$, can be written as

$\displaystyle\mathsf{H}_{t}$
$\displaystyle=\mathds{1}\left[\sum_{u\in[{\mathsf{N}}]}\mathds{1}\left[\mathsf{L}_{u}=1,\mathsf{B}_{u,t}=1,\mathsf{X}_{u,3}=1,\mathsf{J}_{u,t}=1,\mathsf{Z}_{t}=0\right]\right.$
$\displaystyle\quad\quad\quad+\sum_{u\in[{\mathsf{N}}]}\mathds{1}\left[\mathsf{L}_{u}=0,\mathsf{B}_{u,t}=1,\mathsf{J}_{u,t}=1,\mathsf{Z}_{t}=0\right]$
$\displaystyle\left.\quad\quad\quad+\sum_{u\in[{\mathsf{N}}]}\mathds{1}\left[\mathsf{L}_{u}=1,\mathsf{B}_{u,t}=1,\mathsf{X}_{u,2}=1,\mathsf{J}_{u,t}=1,\mathsf{Z}_{t}=0\right]>0\right].$
(30)

Basically, $\mathsf{H}_{t}$ indicates whether at time $t\in{\cal
B}_{\ell}\setminus{\cal T}_{\mathsf{test},\ell}$ a bad user is present or not.
Accordingly, we bound the regret in this case as follows

$\displaystyle\mathsf{A}_{4}$
$\displaystyle\triangleq\frac{1}{{\mathsf{N}}}\mathbb{E}\left[\sum_{t\in{\cal
B}_{\ell}\setminus{\cal
T}_{\mathsf{test},\ell}:\mathsf{H}_{t}=1}\sum_{u\in[{\mathsf{N}}]}\mathds{1}\left[\mathbf{R}_{u,\pi_{u,t}}=0\mid\mathcal{A}^{c}\right]\right]$
(31) $\displaystyle\leq\mathbb{E}\sum_{t\in{\cal B}_{\ell}\setminus{\cal
T}_{\mathsf{test},\ell}}\mathds{1}\left[\mathsf{H}_{t}=1\right]$ (32)
$\displaystyle=\mathbb{E}\sum_{t\in{\cal B}_{\ell}:\exists
u\in[{\mathsf{N}}],\mathsf{J}_{u,t}=1}\mathsf{G}_{t},$ (33)

where in (33) we sum over all those rounds where some user changed its type,
and $\mathsf{G}_{t}$ counts the number of rounds it takes to detect the bad
users. This random variable is clearly stochastically dominated by by a
Geometric random variable with mean $1/p$. Indeed, a test can start at every
round with probability $p$, and a test that starts at a round
$\mathsf{Z}_{t}=0$ will certainly reveal that the user is in a different user
group than the one returned in the reference test
$\mathcal{P}_{\mathsf{test}_{0}}$. Accordingly, we will add that user to the
set $\mathcal{V}_{t_{{\cal B}_{\ell-1}}+1+\mathsf{T_{static}}+t}$. Therefore,
we obtain that,

$\displaystyle\mathsf{A}_{4}$ $\displaystyle\leq\mathbb{E}\sum_{t\in{\cal
B}_{\ell}:\exists
u\in[{\mathsf{N}}],\mathsf{J}_{u,t}=1}\mathsf{G}_{t}\leq\mathbb{E}\sum_{t\in{\cal
B}_{\ell}:\exists
u\in[{\mathsf{N}}],\mathsf{J}_{u,t}=1}\frac{1}{p}\leq\frac{\mathsf{V}_{{\cal
B}_{\ell},1}}{p}.$ (34)

###  A.4 The “Static” Regret

It remains to bound the regret for those round where we do not test and all
bad users are detected, i.e.,

$\displaystyle\mathsf{A}_{5}\triangleq\frac{1}{{\mathsf{N}}}\mathbb{E}\left[\sum_{t\in{\cal
B}_{\ell}\setminus{\cal
T}_{\mathsf{test},\ell}:\mathsf{H}_{t}=0,\mathsf{Y}_{t}=0}\sum_{u\in[{\mathsf{N}}]\setminus\mathcal{V}_{t}}\mathds{1}\left[\mathbf{R}_{u,\pi_{u,t}}=0\mid\mathcal{A}^{c}\right]\right].$
(35)

We shall refer to this regret as the static regret. This static case was
studied in [12], where algorithm Recommend was analyzed thoroughly. As
discussed before, in [12] it was assumed that users of the same user-type have
the same exact preference vectors, while in this paper we assume the weaker
coherence Assumption A3. Nonetheless, except for a few technical differences
(which we highlight in the proof of the following result), our analysis relies
on the proof of Theorem 1 in [12].

######  Lemma 3 (No Variations).

Let $\delta\in(0,1)$, and consider the latent source model and assumptions
A1–A3. Also, assume that
${\mathsf{N}}=\Omega\left(\frac{{\mathsf{M}}}{\nu}\log\frac{1}{\delta}+\left(\frac{3}{\delta}\right)^{1/\alpha}\right)$.
Then, for any
$\mathsf{T_{static}}\leq\Delta_{{\mathsf{T}}}\leq\mu\cdot{\mathsf{M}}$, we
have

$\displaystyle\mathsf{A}_{5}$
$\displaystyle\leq(\Delta_{{\mathsf{T}}}-\mathsf{T_{static}})\cdot\delta.$
(36)

###  A.5 Collecting Terms

We finally collect all the above bounds to obtain the result stated in Theorem
1. Specifically, using (20), (26), (29), (34), and Theorem 1, we obtain

$\displaystyle\mathsf{regret}({\cal B}_{\ell})$
$\displaystyle\leq\mathsf{T_{static}}\cdot(1-\mu)+(\Delta_{{\mathsf{T}}}-\mathsf{T_{static}})\cdot\delta+2\cdot\mathsf{V}_{\mathcal{B}_{\ell},1}\cdot\mathsf{T_{static}}+p\cdot\Delta_{{\mathsf{T}}}\cdot\mathsf{T_{static}}$
$\displaystyle\quad+\frac{\mathsf{V}_{\mathcal{B}_{\ell},1}}{p}+\frac{3\Delta_{{\mathsf{T}}}\mathsf{V}_{\mathcal{B}_{\ell},2}}{2\nu}$
(37)
$\displaystyle\leq\delta\cdot\Delta_{{\mathsf{T}}}+\mathsf{T_{static}}\cdot(1-\delta-\mu)+2\cdot\mathsf{V}_{\mathcal{B}_{\ell},1}\cdot\mathsf{T_{static}}+p\cdot\Delta_{{\mathsf{T}}}\cdot\mathsf{T_{static}}$
$\displaystyle\quad+\frac{\mathsf{V}_{\mathcal{B}_{\ell},1}}{p}+\frac{3\Delta_{{\mathsf{T}}}\mathsf{V}_{\mathcal{B}_{\ell},2}}{2\nu},$
(38)

where the first term at the r.h.s. of (37) is the regret due to the first
$\mathsf{T_{static}}$ rounds where we recommend random items. Since (38) is
true for every batch ${\cal B}_{\ell}$, we can sum-up over $\ell$, and obtain
that

$\displaystyle\mathsf{regret}({\mathsf{T}})$
$\displaystyle\leq\sum_{\ell=1}^{\left\lceil{\mathsf{T}}/\Delta_{\mathsf{T}}\right\rceil}\mathsf{regret}({\cal
B}_{\ell})$ (39)
$\displaystyle\leq\delta\cdot{\mathsf{T}}+\frac{{\mathsf{T}}}{\Delta_{{\mathsf{T}}}}\mathsf{T_{static}}\cdot(1-\delta-\mu)+2\cdot\mathsf{V_{1}}\cdot\mathsf{T_{static}}+p\cdot{\mathsf{T}}\cdot\mathsf{T_{static}}+\frac{\mathsf{V}_{1}}{p}+\frac{3\Delta_{{\mathsf{T}}}\mathsf{V_{2}}}{2\nu}.$
(40)

Minimizing the r.h.s. of the above inequality w.r.t. $p$, we obtain that its
optimal value is
$p^{\star}=\sqrt{\mathsf{V}_{1}/(\mathsf{T}\cdot\mathsf{T_{static}})}$.
Therefore,

$\displaystyle\mathsf{regret}({\mathsf{T}})$
$\displaystyle\leq\delta\cdot{\mathsf{T}}+\frac{{\mathsf{T}}}{\Delta_{{\mathsf{T}}}}\mathsf{T_{static}}\cdot(1-\delta-\mu)+2\cdot\mathsf{V_{1}}\cdot\mathsf{T_{static}}+2\sqrt{\mathsf{V}_{1}\cdot{\mathsf{T}}\cdot\mathsf{T_{static}}}+\frac{3\Delta_{{\mathsf{T}}}\mathsf{V}_{2}}{2\nu}.$
(41)

It is left to do is to minimize the r.h.s. of the above inequality over
$\Delta_{\mathsf{T}}$. The optimal value is given in a form of a solution for
a cubic equation. Alternatively, it turns out that the following choice which
minimizes the first three terms at the r.h.s. of (41) is

$\displaystyle\Delta_{\mathsf{T}}^{*}=\min\left({\mathsf{T}},\sqrt{\frac{2\nu{\mathsf{T}}}{3\mathsf{V_{2}}}\kappa}\right),$
(42)

where $\kappa\triangleq\mathsf{T_{static}}(1-\delta-\mu)$. Substituting this
value back in (41) gives

$\displaystyle\mathsf{regret}({\mathsf{T}})$
$\displaystyle\leq\delta\cdot{\mathsf{T}}+\max\left(\kappa,\sqrt{\frac{3\mathsf{V_{2}{\mathsf{T}}}\kappa}{2\nu}}\right)+2\cdot\mathsf{V_{1}}\cdot\mathsf{T_{static}}+2\sqrt{\mathsf{V}_{1}\cdot{\mathsf{T}}\cdot\mathsf{T_{static}}}$
$\displaystyle\quad\quad+\min\left(\frac{3\mathsf{V_{2}}{\mathsf{T}}}{2\nu},\sqrt{\frac{3\mathsf{V}_{2}{\mathsf{T}}\kappa}{2\nu}}\right),$
(43)

and so
$\mathsf{reward}({\mathsf{T}})={\mathsf{T}}-\mathsf{regret}({\mathsf{T}})$ is
lower bounded by the same expression as in Theorem 1. Note that the condition
$\Delta_{\mathsf{T}}>\mathsf{T_{static}}$ in Lemma 3 boils down to
${\mathsf{T}}>\mathsf{T}_{\mathsf{static}}\cdot\max\left\\{1,\frac{\mathsf{3V_{2}}}{2\nu(1-\delta-\mu)}\right\\}=\mathsf{T}_{\mathsf{learn}}$.
Finally, for ${\mathsf{T}}\leq\mathsf{T}_{\mathsf{learn}}$, we get that
$\mathsf{reward}({\mathsf{T}})\geq\mu\cdot{\mathsf{T}}$, as claimed.

###  A.6 Proof of Lemma 3

To prove the result in Lemma 3, it is suffice to lower bound the probability
$\mathbb{P}\left[\mathbf{R}_{u\pi_{u,t}}=1,\mathsf{Y}_{t}=0,\mathsf{H}_{t}=0\right]$.
To that end, for any $u\in[{\mathsf{N}}]$ and $t\in[{\mathsf{T}}]$, define

$\displaystyle{\cal
G}_{u,t}\triangleq\left\\{|\partial_{t}(u)|\geq\frac{2\nu{\mathsf{N}}}{3}\right\\},$
(44)

where $\partial_{t}(u)$ is the set of neighbors at time $t$ user $u$ have from
the same user-types, respectively. For $t$ large enough the probability of
${\cal G}_{u,t}$ is lower bounded strictly by zero. To show that recall that
$|{\cal T}_{u}(t)|$ is the number of users in user’s $u$ type at round $t$. As
we argued above at each round we know that $|{\cal
T}_{u}(t)|>\frac{2\nu{\mathsf{N}}}{3}$. Also, recall that in the beginning of
the batch we devote the first $\mathsf{T_{static}}$ recommendations for
creating an initial partition ${\cal P}_{0}$ of the users into types (see, the
the fourth step in Algorithm 2). We showed in Lemma 2 that the resulted
partition is correct with probability at least $1-\delta/3$, and therefore,
$|\partial_{t}(u)|\frac{2\nu{\mathsf{N}}}{3}$ with the same probability, i.e.,
$\mathbb{P}[{\cal G}_{u,t}]\geq 1-\delta/3$, for $t\in{\cal
B}_{\ell}\setminus{\cal T}_{\mathsf{test},\ell}$.

Next, using the same steps as in the proof of Lemma 2 in [12], we show that
the good neighborhoods have, through random exploration, accurately estimated
the probability of liking each item. Thus, we correctly classify each item as
likable or not with high probability. In particular, we show Below that

$\displaystyle\mathbb{P}\left[\left.\mathbf{R}_{u,\pi_{u,t}}=1,\mathsf{Y}_{t}=0,\mathsf{H}_{t}=0\right|{\cal
G}_{u,t}\right]$ $\displaystyle\geq
1-2{\mathsf{M}}\exp\left(-2\frac{\Delta^{2}\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)-\frac{1}{{\mathsf{N}}^{\alpha}}.$
(45)

Before proving the above inequality let us first show how we can use it lower
bound the regret. Indeed, combining the above inequality with the fact that
$\mathbb{P}[{\cal G}_{u,t}]\geq 1-\delta/3$, we get

$\displaystyle\mathbb{P}\left[\mathbf{R}_{u,\pi_{u,t}}=1,\mathsf{Y}_{t}=0,\mathsf{H}_{t}=0\right]$
$\displaystyle\geq 1-2{\mathsf{M}}\exp\left(-2\frac{\Delta^{2}\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)-\frac{1}{{\mathsf{N}}^{\alpha}}-\frac{\delta}{3}.$
(46)

It can be seen that if the number of users ${\mathsf{N}}$ satisfy
${\mathsf{N}}=\Omega\left(\frac{{\mathsf{M}}}{\nu}\log\frac{1}{\delta}+\left(\frac{3}{\delta}\right)^{1/\alpha}\right)$,
and of course $t\geq\mathsf{T_{static}}$, then the r.h.s. of (46) is at least
$1-\delta$, namely,
$\mathbb{P}\left[\mathbf{R}_{u,\pi_{u,t}}=1,\mathsf{Y}_{t}=0,\mathsf{H}_{t}=0\right]\geq
1-\delta$. Therefore, we obtain,

$\displaystyle\mathsf{A}_{5}$ $\displaystyle\leq\sum_{t\in{\cal
B}_{\ell}\setminus{\cal
T}_{\mathsf{test},\ell}}\frac{1}{{\mathsf{N}}}\sum_{u=1}^{{\mathsf{N}}}\mathbb{P}\left[\mathbf{R}_{u,\pi_{u,t}}=0,\mathsf{Y}_{t}=0,\mathsf{H}_{t}=0|{\cal
A}^{c}\right]$
$\displaystyle\leq(\Delta_{{\mathsf{T}}}-\mathsf{T_{static}})\cdot\delta,$
(47)

where in the second inequality we have used Assumption A2. Next, we prove
(45). First, we lower bound the number of times an arbitrary item has been
rated by the good neighbors of some user $u$, conditioned on the event ${\cal
G}_{u,t}$. To that end, note that the number of good neighbors user $u$ has
and who have rated item $i$ is stochastically dominated by
$\mathsf{Binomial}\left(\frac{2\nu{\mathsf{N}}}{3},\frac{t}{{\mathsf{M}}{\mathsf{N}}^{\alpha}}\right)$.
Let ${\cal D}$ be the event “item $i$ has less than $\frac{\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}$ ratings from good neighbors of $u$”.
Then, Chernoff’s bound then gives

$\displaystyle\mathbb{P}\left({\cal D}\right)$
$\displaystyle\leq\mathbb{P}\left(\mathsf{Binomial}\left(\frac{2\nu{\mathsf{N}}}{3},\frac{t}{{\mathsf{M}}{\mathsf{N}}^{\alpha}}\right)\leq\frac{\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)$ (48)
$\displaystyle\leq\exp\left(-\frac{\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right).$ (49)

Next, conditioned on ${\cal G}_{u,t}$ and ${\cal D}$ we prove that with high
probability when exploiting the algorithm predicts correctly every item as
likable or unlikable for user $u$. Recall our definition for the posterior
$\hat{p}_{u\ell}$ in (4). Suppose item $i$ is likeable by user $u$, and let
$\mathsf{G}\triangleq\frac{\nu t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}$.
Then, conditioned on $\mathsf{G}$, $\hat{p}_{u\ell}$ stochastically dominates
$\tilde{p}_{ui}\triangleq\mathsf{Binomial}(\mathsf{G},p_{ui})/\mathsf{G}$.
Then,

$\displaystyle\mathbb{P}\left(\left.\tilde{p}_{ui}\leq\frac{1}{2}\right|\mathsf{G}\right)$
$\displaystyle=\mathbb{P}\left(\left.\mathsf{Binomial}(\mathsf{G},p_{ui})\leq\frac{\mathsf{G}}{2}\right|\mathsf{G}\right)$
(50) $\displaystyle\leq\exp\left(-2\mathsf{G}\Delta^{2}\right)$ (51)
$\displaystyle\leq\exp\left(-2\frac{\Delta^{2}\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right),$ (52)

where the first inequality follows from Hoeffding’s inequality, and the second
inequality is because $p_{ui}\geq 1/2+\Delta$. Using monotonicity, we also
have

$\displaystyle\mathbb{P}\left(\left.\tilde{p}_{ui}\leq\frac{1}{2}\right|\mathsf{G}\geq\frac{\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)$
$\displaystyle\leq\exp\left(-2\frac{\Delta^{2}\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right).$ (53)

Using the same steps we can show that if item $i$ is unlikeable by user $u$
then with the same probability $\tilde{p}_{ui}\geq\frac{1}{2}$. Taking a union
bound over all items we get that with probability at least
$1-{\mathsf{M}}\exp\left(-2\frac{\Delta^{2}\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)$ our algorithm correctly
classifies every item as likable or unlikable for user $u$. We are now in a
position to prove (45). Specifically, for user $u$ at time $t$, conditioned on
${\cal G}_{u,t}$ we have shown in (49) that with probability at least
$1-{\mathsf{M}}\exp\left(-\frac{\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)$ _every_ item has more than
$\frac{\nu t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}$ ratings from good
neighbors of $u$. Now, using the fact that with probability at least
$1-{\mathsf{M}}\exp\left(-2\frac{\Delta^{2}\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)$ we classify correctly all
items, coupled with the fact that we exploit with probability
$1-{\mathsf{N}}^{-\alpha}$, we get

$\displaystyle\mathbb{P}\left[\left.\mathbf{R}_{u,\pi_{u,t}}=1,\mathsf{Y}_{t}=0,\mathsf{H}_{t}=0\right|{\cal
G}_{u,t}\right]$ $\displaystyle\geq 1-{\mathsf{M}}\exp\left(-\frac{\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)-{\mathsf{M}}\exp\left(-2\frac{\Delta^{2}\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)$
$\displaystyle\quad\quad-\frac{1}{{\mathsf{N}}^{\alpha}}$ (54)
$\displaystyle\geq 1-2{\mathsf{M}}\exp\left(-2\frac{\Delta^{2}\nu
t{\mathsf{N}}^{1-\alpha}}{3{\mathsf{M}}}\right)-\frac{1}{{\mathsf{N}}^{\alpha}},$
(55)

as claimed.