Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints
Authors: Soumyabrata Pal
Arun Suggala
Karthikeyan Shanmugam
Prateek Jain
Venue: NeurIPS 2023 poster (2023)
Keywords: Blocked Bandits
Collaborative Filtering
Clustering
TL;DR: This paper theoretically studies multi-user bandit optimization where each arm can be pulled only a small number of times by each user.

Abstract: We consider the problem of \emph{blocked} collaborative bandits where there are multiple users, each with an associated multi-armed bandit problem. These users are grouped into \emph{latent} clusters such that the mean reward vectors of users within the same cluster are identical. Our goal is to design algorithms that maximize the cumulative reward accrued by all the users over time, under the \emph{constraint} that no arm of a user is pulled more than $\mathsf{B}$ times. 
This problem has been originally considered by \cite{Bresler:2014}, and designing regret-optimal algorithms for it has since remained an open problem.
In this work, we propose an algorithm called B-LATTICE (Blocked Latent bAndiTs via maTrIx ComplEtion) that collaborates across users, while simultaneously satisfying the budget constraints, to maximize their cumulative rewards. Theoretically, under certain reasonable assumptions on the latent structure, with 
$\mathsf{M}$ users, $\mathsf{N}$ arms, $\mathsf{T}$ rounds per user, and $\mathsf{C}=O(1)$ latent clusters, B-LATTICE achieves a per-user regret of  $\widetilde{O}(\sqrt{\mathsf{T}(1 + \mathsf{N}\mathsf{M}^{-1})})$ under a budget constraint of $\mathsf{B}=\Theta(\log 
\mathsf{T})$. These are the first sub-linear regret bounds for this problem, and match the minimax regret bounds when $\mathsf{B}=\mathsf{T}$. Empirically, we demonstrate that our algorithm has superior performance over baselines even when $\mathsf{B}=1$. B-LATTICE is a phased algorithm where in each phase it clusters users into groups and collaborates across users within a group to quickly learn their reward models.

Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints
Soumyabrata Pal
Arun Sai Suggala Google Research Bangalore, India arunss@google.c com com
Karthikeyan Shanmugam Google Research Bangalore, India
Google Research Bangalore, India
soumyabratapal 130gmail com
karthikeyanva@googee.com
Prateek Jain Google Research Bangalore, India praj prajain@google. com
Abstract
We consider the problem of blocked collaborative bandits where there multiple users, each with an associated multi-armed bandit problem. These users are grouped into latent clusters such that the mean reward vectors of users within the cluster are identical. Our goal is to design algorithms that maximize the cumulative reward accrued by all the users over time, under the constraint that no arm of a user is pulled more than B times. This problem has been originally considered 4., and designing regret-optimal algorithms for has since remained an open problem. In this work, we propose an algorithm called B-LATTICE (Blocked Latent bAndiT's via maTrix ComplEtion) that collaborates across users, while simultaneously satisfying the budget constraints, to maximize their cumulative rewards. Theoretically, under certain reasonable assumptions on the latent structure, with M users, N arms, rounds user, and C O(1) latent clusters, B-LATTICE achieves a per-user regret of O(VT(1 NM-1) under a budget constraint of B (log T). These are the first sub-linear regret bounds for this problem, and match the minimax regret bounds when T. Empirically, we demonstrate that our algorithm has superior performance over baselines even when LATTIIC runs in phases where each phase it clusters users into groups and collaborates across users within group to quickly learn their reward models.
1.
1 Introduction
Modern recommendation systems cater millions of users and items [ on daily basis, typically in online fashion. A critical feature of such systems is to quickly learn tastes of individual users from sequential actions and feedback, and suggest personalized products for each user. Furthermore, in practice, item that has already been consumed by user is recommended very few times to the same user (or not recommended all). This because, in applications such as movie/book recommendations, typical user will find little interest in consuming the same item multiple times.
This problem that we rename as Blocked Collaborative Bandits was abstracted out by 4 with modeling assumption that users have a latent clustering structure. That is, each user can belong to an unknown cluster and the expected reward for an item/movie is same for all users in a cluster. Formally, consider M users, N items and T rounds with M. N > T (M, N z 10 in recommendation systems such as YubTube) and in each round, every user is recommended some item (potentially different for each user). On consuming the item, noisy reward is assigned. As mentioned above,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Paper
Setting
Metric
Guarantees (Worst-Case Case)
B I. user clusters
pscudo regrel (maximize
Bresler et al,, 2014 4
O(T)
likeable items)
1,
Bresler et al., 2018
user, item clusters; noiseless rewards
regret
Ō(1)
B = 1.
O(T + NM HMM-1jp 1)13))
Ariu et al., 2020
user, item clusters
regret
sub-optimal in N. T
B user clusters
ØlyT(1 + NM-1j
Pul et al., 2023 25
regret
minimax optimal in N. M. T
B B= Gilog T),
This Work
user clusters
regret
T + NM-
Table I: Comparison of various approaches for blocked collaborative bandits. All the regret bounds stated here are worst-case bounds and assume C = ( Moreover, the regret averaged across users. The worst-case pseudo-regret in ( is linear when the items have rewards close to 0.5, In (2). the authors' proposed a greedy algorithm whose worst-case has T//3 dependence.
it is assumed that the users can be clustered in C clusters, where < M, N, and users in the same cluster have identical reward distributions over items. Furthermore, any item can be recommended to particular user at most B times, after which the item is blocked for the user.
4 considered this problem for B = 1 in the setting where a user in cluster c on being recommended item j provides like (+1) with probability Pej and dislike (-1) with probability 1 - Pej. The authors studied a notion of pseudo-regret corresponding to minimizing the number of un-likeable items for user, i.e., items for which the probability of user giving a like (+1) is less than 1/2. To this end, the authors proposed the that performs random exploration in each round with certain probability. During exploitation provides recommendations based on a neighborhood of similar users. However, maximizing the number of likeable items is limiting as it does not prioritize items with large rewards and completely disregards the item ordering. Despite these theoretical limitations, variants of the collaborative algorithm designed in 4 have found applications in predicting Bitcoin price, (2] information retrieval [12] among others.
algorithm, an c-greedy style algorithm
Recent works have studied this problem under more practical notion of regret which involves maximizing the cumulative rewards accrued over time 2 5). However, these works assume a cluster structure among both users and items. This assumption entails that there are many copies of the highest rewarding item for any user; this voids the blocking constraint and makes the problem significantly easier. Moreover, the algorithms designed in [2] greedy (they perform exploration first to cluster users, items, and then perform exploitation) and achieve significantly sub-optimal regret. These bounds, translated to the original blocked bandit problem where there no item clusters. have sub-optimal dependence on the number of items N. The algorithms designed in (5) assumed a noiseless binary feedback model which allowed for constant regret. However, these algorithms are not casily extendable to the more general noisy reward setting we consider in this work.
Another line of work has studied this problem when B = T (i.e., no budget constraints on arms) 24
21] While some of these works have designed regret optimal algorithms (25), the B T budget constraint is too lenient in many modern recommendation systems. To summarize, existing works have either attempted to solve the much harder setting of B 1 by imposing additional restrictions on the problem or the simpler = T setting which is not very relevant in practice.
This Work. In this work, we make progress on this problem by considering the intermediate setting of B=c (log T). We do not impose any cluster structure among items (as in 4), and consider a general notion of regret which involves maximizing the cumulative rewards under the budget constraints. We propose B-LATTICE(AIg. []. a phased algorithm which carefully balances exploration and exploitation. Our algorithm also performs on-the-fly clustering of users and collaborates across users within a cluster to quickly learn their preferences, while simultaneously satisfying the budget constraints. The key contribution of our work is that under certain standard incoherence assumptions (also used recently in 25 and a budget constraint of B = O(log T), we show that B-LATTICE achieves per-user regret of ( NM- Empirically, our algorithm can even handle budget constraint of B = 1 and perform better than baselines (Alg. (6. However, bounding its regret
(.)),(()) hides logarithmic factors in M, N. T

---

in this setting is much more challenging which we aim to address in future work. That being said, under an additional cluster structure on the items, we show that our theoretical guarantees hold even for B = 1 (Appendix
We also provide a non-trivial regret lower bound of (( VMMM-VVTM-/22 1/3). Our proof involves a novel reduction to multi-hypootesis testing and relies on Fano's 's inequality for approximate recovery [28] (see Appendix E). Our techniques could be of independent interest even outside the context of very small or very large. However, we conjecture that our upper bounds are actually tight since they recover the same rates as the B = T setting [55;; tightening the lower bound is left as a future work. Finally, we verify theoretical results by simulations synthetic data (sce Appendix C). Here, we compare a more practical version of B- LLATTICEAAloorimm 6 with Collaborati ve veevvee-eereeee Greedy 4.. We demonstrate that B B-LATTICE not only has good regret but also other practically desirable properties such as a small cold-start period, and repeated high quality recommendations.
this work. Our lower bound tight in two regimes when the number of rounds
Techniques. Our algorithm is built on recent works that have studied this problem without the budget constraint [7 25 17 developed a regret optimal algorithm called LATTICE that runs in phases. At any phase, the algorithm maintains grouping of users which it refines over time (these groups are nothing but our current estimate of user clusters). Within each group, the algorithm relies on collaboration to quickly estimate the reward matrix. To be precise, the algorithm performs random exploration followed by low-rank matrix completion [8] to get a good estimate of the user-item reward matrix. Next, the algorithm uses the estimated reward matrix to eliminate sub-optimal arms for each user. Finally, it refines the user clusters by placing users with similar reward structure in the same group.
Extending the above algorithmic recipe to our setting poses a couple of challenges. First, observe that the oracle optimal strategy in the budget constrained setting is to recommend each of the top T/B items B times; we refer to these top times as golden items the sequel. To compete against such policy, our algorithm needs to quickly identify the golden items for each user. The LATTICE algorithm described above doesn't perform this, as it aims to only identify the top item for every user. So, one of the key novelties in our algorithm is to design test to quickly identify the golden items and recommend them to the users. The second challenge arises from the usage of low-rank matrix completion oracles in LATTICE. To be precise, LATTICE requires more accurate estimates of the user-item reward matrix the later phases of the algorithm. To this end, it repeatedly recommends an item to user to reduce the noise in its estimates. However, this is infeasible in our setting due to the budget constraints. So, the second novelty in our algorithm is to avoid repeated recommendations and design alternate exploration strategy that adheres to the budget constraints.
Other Related Work:
Item-Item Collaborative Filtering (CF). A complementary theoretical line of work proposes to exploit clustering structure across the items instead of users 7
23 27 22 Under a similar blocking
constraint, the authors have provided a sub-linear regret guarantee based on a certain measure of complexity called the doubling dimension. Since then, there have been several works in the literature that have attempted to exploit a cluster structure on both users and items 6
Variants of User- User CF. [15) has looked into the problem of non-stationary user-user collaborative filtering where the preferences of users change over time. [13] studies a variant where the user only provides positive ratings i.e when the user has liked item. p and
3 studies probabilistic models
for user user CF in an online and offline model respectively.
Cluster Structure across users. In several problems related to multi-armed bandits, cluster structure across users have been explored. In particular, in [ 20 cluster-structure across users while each item has a d-dimensional context chosen uniformly at random at each round. The preferences each user a linear function the context vector and the cluster id. Under these settings, the authors prove strong regret bound. However, note that in our setting, the item contexts are hidden; hence, these techniques are not applicable to our setting.
10 21 (6),, the authors have imposed
2 Problem Setting and Background
Notation. We write [m] to denote the set 21,2,..., m.) For a vector E Rm v, denotes the 7th element; for any set 2 C [mt] let vu denote the vector restricted to the indices in U. Similarly,
3

---

for A E R A; denotes the -tt element and the 8th row of A respectively. For any set u S [m]. [n], Au.y denotes A restricted to the rows in Z and columns in V. Let | lo denote absolute value of the largest entry in matrix A. NO, o²) denotes the Gaussian distribution with O mean and variance o². We write EX to denote the expectation of random variable X. ||U||2 2, corresponds to the maximum euclidean norm of a row of the matrix U. More precisely, for matrix U E Mxr, the norm || [a ||U||l2- Thus, if | 2, is small as in Lemma 1, then all rows of U have small &g norm.
Problem Setting, Consider an online recommendation system with M users, N items and rounds. Let P E RMXN be the reward matrix which is unknown, Here, we assume the set of M users can be partitioned into disjoint but unknown clusters (()), C(2) ,..,, CCC)) such that any two users u, [M] belonging to the same cluster have identical reward vectors i.e. P. Pv. In each round E [T]. every user is recommended an item (can be different for each user) by the system. In turn,
the system receives feedback in the form of reward from each user. Let, R (t)
upp(t)) be the observed
reward for recommending item Pu (t) E [N] to user at round such that:
P (t) + +E( (!)
R (P.
(I)
(e)
where (1) (t) denotes the unbiased additive noise. We assume that elements of (E (Bu..(t)
[ue[M]
ue [M] are
TE[T.
i..d. zero mean sub- -ooo-gaussian random variables with variance proxy o² i.e. for all u, L [M] x (T),
we have (E(!)
(t) = 0 and for all s E R, we have E Exxp(sE( (t) I exp(o?s2/20 222). As in practical recommendation systems, impose be recommended more than B times to a user, for some small B = Olog T). For simplicity of presentation, assume T is multiple of B. However, we would like to note that results hold for
additional constraint that the same item cannot
general T. Without loss of generality, we assume N 2 T/B, since otherwise the budget constraints cannot be satisfied.
Our goal is to design a method that maximizes cumulative reward. Let n. : [N] - [N] denote the function that sorts the rewards of user E [M] in descending order, i.e., for any < j. P (i) Z P Pus.()) The oracle optimal strategy for this problem is to recommend ==... T/B. the top T/B items with the highest reward, B times each. This leads us to the following notion of regret
BP [F M
P (a)
Reg(T (T) A
Σ
Σ
BE(T/B],.E[M]
[E
where the expectation over the randomness in the policy and the rewards, and (t(() is any policy that satisfies the budget constraints.
Importance of collaboration. Suppose we treat each user independently and try to minimize their regret. In this case, when B is as small as O(log T), we will incur regret that is almost linear in T. This is because we will not have enough data for any item to know if it has a high or a low reward. This shows the importance of collaboration across users to achieve optimal regret. The latent cluster structure in our problem allows for collaboration and sharing information about items across users.
For ease of exposition of our ideas, we introduce a couple of definitions.
Definition 1. A subset of users S C [M] is called "nice" if S = Cl) for some A S [C]. In other words, can be represented as the union of some subset of clusters.
Definition 2. For any user E [M], we call the set of items {Tx(())]T T/B (i.e., the set of best T/B items) to be the golden items for user u.
This corresponds to the following analogue of multi-agent multi-armed bandits (MAB)- we have M users each involved in separate MAB problem with the set of N arms (corresponding the N items) and rounds. The mean reward of each arm different for each user captured by the M x reward matrix P. In each round t, every agent u E [M] simultancously pulls an unblocked arm pa (t) of their choice based on the feedback history of all users (including u) from previous rounds. Subsequently the noisy feedback for all M users and their corresponding arm pulls at round t is revealed to everyone.

---

2.1 Low-Rank Matrix Completion
Additional Notation. For an estimate P of reward matrix P. we will use n.. [N] - [N] to denote
the items ordered according to their estimated reward for the user u i... P (i) 2 P P. when
i < j. For any user [M] and any subset of items A C [N], we will use nu A [|A] + [N] to
denote the permutation Ty restricted to items in A S [N] i.e. for any user u E [M] and any i. E [[A]]
satisfying j. we will have P Pux,, (A)14 2 P G)14 Here, (i( A corresponds to the 7th item
among items in sorted in descending order of expected reward for user u.
An important workhorse of our algorithm is low-rank matrix completion, which is a well studied
problem in the literature [6 18
8 17]. Given a small set of entries that are randomly sampled from matrix, these algorithms infer the missing values of the matrix. More precisely, consider a
low-rank matrix Q E IRM Let f S [M] x [N] be a random set of indices obtained by picking each index in [M] x [N] independently with probability p > 0. Let (Ziz) (A.))
the corresponding noisy entries (sub-gand gaub-gaussian random variables with variance proxy o² > 0) that we observe which satisfy i = Qu v(..j) St In this work rely on nuclear norm minimization to estimate Q (see Algorithm 4). Recent works have provided tight sementtwwise recovery guarantees for this algorithm 8 17. We state these guarantees in the following Lemma.
Lemma 1 (Lemma 2 in 17). Consider matrix Q E RR with rank and SVD decomposition VEVT satisfying || | I SVur/M, //rlMM,IVVll... S / Jur/N and condition number O()) Let d = max(M, N), d2 min(M, N), noise variance o² > O, and let sampling probability p be such (for some constant e > 0). Suppose we sample a subset of indices 0 M x [N] such that each tuple of indices (i.j) E [M] x [N] is included in Qt independently with probability p. Let {Z,z) (e))en be the noisy observations corresponding all indices in S. Then Algorithm 4 when run with inputs (M, N, ,,,22r,,00 Fr,2, Ω2 (Ziz) (1))()))))))) returns an estimate Q of Q which satisfies the following error bounds with probability at least 1 - O + 12
that p = 52 _ max 1,, a²2H))
o LoV/'² Vogglogdd d1
IQQ 100 =
Vpd2
Lemma] 1 provides guarantees on the estimate Q of Q given the set of noisy observations corre- sponding to the entries in Ω. Equation 3 says that the quality of the estimate becomes better with the increase in sampling probability p that determines the number of entries in Ω. Note the detailed Algorithm ESTIMATE (Alg. 4 designed in [1 S is provided in Appendix
Remark (Warm-up (Greedy Algorithm)). Using Lemma [ is easy to design a greedy algorithm (Alg. 3 in Appendix B for B = 1; for a fixed number of rounds m, we recommend random unblocked items to every user. Since the reward matrix P a low-rank matrix, we use Algorithm f to estimate the entire muirix. Subsequently, we recommend the best estimated unblocked items for each user for the remaining rounds. We can prove that the regret suffered by such an algorithm is The dependence on number of rounds T is sub-optinal, but Alg. 5 does
O (NNMM) not require the knowledge of any gaps corresponding to the reward matrix P. See Appendix B for detailed proof. We would like to note that the result can be generalized easily to B = Olog
3 Main Results
Let X E CxN be the sub-mutee mobrimatii of the expected reward matrix P comprising C distinct rows of P corresponding to each of the C true clusters. Also, let 7 := max;,jelr) |CO) denote the ratio of the maximum and minimum cluster size. To obtain regret bounds, we make the following assumptions on the matrix X:
Assumption (Assumptions on X). Let X = U be the SVD of X. Also, let X satisfy the following: 1) Condition number: X. is full-rank and has non zero singular values X > .... >>>> Ac
with condition number XI/Xc O(1), 2) p-incoherence: ||V||2, S VuC/N, 3) Subset Strong
Convexity: For some a satisfying a log M = 2211,, 7 = for all subset of indices S S [M] C, the minimum non zero singular value of Vs must be least /a|S|/M
5

---

Remark 2 (Discussion on Assumption D. We need Assumption only to bound the incoherence factors and condition numbers of sub-matrices whose rows correspond to a nice subset of users and the columns comprise of at least T1/3 golden items for each user in that nice subset. This implies that information is well spread-out across the entries instead of being concentrated in a few. Thus, we invoke Lemma for those sub-matrices and ufilize existing guarantees for low rank matrix completion. Our theorem statement can hold under significantly weaker assumptions but for clarity, we used the theoretically clean and simple to state Assumption 7 Note that the assumption is not required to run our algorithm or any offline matrix completion oracle- the only purpose of the assumption is to invoke existing theoretical guarantees of offline low rank matrix completion algorithms with & error guarantees.
Assumption 2. We will assume that p, T, [,,|||llss C positive constants and do not scale with the number of users M, items N or the number of rounds T.
Assumption 2 is only for simplicity of exposition/analye we can easily generalize our guarantees any of the parameters in Assumption 2 scale with In that case, the regret has additional polynomial factors of p, T. |P| | lao C- moreover these quantities (or a loose upper bound) are assumed to be known to the algorithm. Now, we present our main theorem:
and is standard in the literature. As in 25
Theorem 1. Consider the blocked collaborative bandits problem with M users, N items, C clusters,
T rounds with blocking constraint B = Olog T) such such that at every round t E [T], we observe reward R(O) as defined in eq. I with noise variance proxy o² > O. Let P E RRM be the expected reward matrix and X RCM be the sub-matrix of P with distinct rows. Suppose Assumption 0 is satisfied by X and Assumption 2 is true. Then Alg. B B-LATTICE initialized with phase index É 1 L. M = [M]], = [[N]], C. T, tu = 1, texploit = 0, P = 0 and c(log M) for some constant c > guarantees the regret Reg(T) defined under the blocking constraint (eg.
2 to be:
Reg (T) = =6( TTmx (1, )
(4)
Note that the regret guarantee in Theorem I is small long N =0 M (but M. N can be extremely large). The dependence of the regret number of rounds scales as VT. This result also matches the vT dependence the number of rounds without the blocking constraint [17] 23). Furthermore, Theorem [ also highlights the importance of collaboration across users compared with standard multi-armed bandits, the effective number of arms is now the number of items per user.
Remark 3. Note that in our model, we have assumed that users in the same latent cluster have identical true rewards across all items. Although we have made this assumption for simplicity as in other works in the literature [25] 2 3 5J. the assumption of each user having exactly I of C different mean vectors can be relaxed significantly. In fact, in [25), a similar cluster relaxation was done the following way for known value of v > 0 there are C clusters such that 1) users in the same cluster have same best item and mean reward vectors that differ entry-wise by at most v 2) any users in different clusters have mean reward vectors that differ entry- wise by at least 20v. Our analysis can be extended to the relaxed cluster setting with an addition cost in regret terms of v.
We now move on to rigorous lower bound in this setting.
Theorem 2. Consider the blocked collaborative bandits problem with M users, N items, C 1 cluster, reward matrix P E [0, M|M T rounds with blocking constraint B such that at every round
t te [T,, we observe reward R (t) as defined eq. (11 with noise random variables (E(() Twe [M]
(t) (1) [
generated i..dd according to a zero mean Gaussian with variance 1. In that case, any algorithm must suffer regret of at least
(T) = (2( max (V
NB T (olog(//T) M
BVM
Note that the main difficulty in proving tight lower bounds in the blocked collaborative bandits setting is that, due to the blocking constraint of B. a single item having different rewards can only cause a
'It suffices for us if B = clog T for any constant e > c' where e' is a constant independent of all other model parameters. This is because, we simply want B to be at least the number of phases. Since our phase lengths increase exponentially, the number of phases is Ollog T).

---

difference in regret of at most B in two separate instances constructed in standard measure change arguments [9.. However, we prove two regret lower bounds on this problem, out of which the latter is the technically more interesting one.
The first term in the lower bound in Thm. fooloow from simple reduction from standard multi- armed bandits. Intuitively, if we have T/B known identical copies of each item, then the blocking constraint void but with C = 1, this is (almost) equivalent to a standard multi-armed bandit problem with MT rounds, NBT distinct arms (up to normalization with M). The lower bound follows from invoking standard results in MAB literature. For B T, we recover the matching regret lower bound in [25] without the blocking constraint. Furthermore, for B = (log T), the first term is tight up to log factors when number of rounds small for example when T O (Appendix E
The second term in the lower bound is quite non-trivial. Note that the second term is tight up to log factors when the number of rounds T (NN) is very large (close the number of items) and B = O(log T) is small. We obtain this bound via reduction of the regret problem to a multiple hypothesis testing problem with exponentially many instances and applying Fano's inequality [28) (commonly used in proving statistical lower bounds in parameter estimation) for approximate recovery. Our approach might be of independent interest in other online problems as well. (Appendix L
Remark 4. We leave the problem of extending our guarantees for B = future work. However we make progress by assuming a cluster structure over items as well. More precisely, suppose both items and users can be grouped into a constant number of disjoint clusters such that (user,item) pairs in same cluster have same expected reward. Then, we can sidestep the statistical dependency issues in analysis Alg. for B 1 and provide similar guarantees as in Thm. 7 (see Appendix F
4 B-LATTICE Algorithm
B-LATTICE is a recursive algorithm and runs in Olog T) phases of exponentially increasing length. B B-LATTCE assume the knowledge of the following quantities- users M, items N, clusters C. rounds T, blocking constraint B, maximum true reward ||x incoherence factor μl, cluster size ratio noise variance o² > 0 and other maintains a partitioning of users into crude clusters, and a set of active items for each such crude cluster. Let ( be the partitioning of users in the 8th phase, and Ar(5) be the list containing the set
in Assumption [
At any phase, the algorithm
of active items for each group of users in M( In the first phase, we place all users into a single group and keep all items active for every user; that is, M [[M]].
[[N]]. There are three
key components in each phase: (a) exploration, (b) exploitation, and (c) user clustering. In what
follows, explain these components in detail. For simplicity of exposition, suppose Assumption
is true namely the parameters μ1, a, 7, [PPl C are constants.
Exploration (Alg. D. The goal of the Explore sub-routine is to gather enough data to obtain a better estimate of the reward matrix. To be precise, let ( be the users in the 7th group at phase f, and (C,),) be the set of active items for this group. Let P Mite .yte. be the sub-matrix of P corresponding to rows (fF)) and columns (f(+)) (recall, this sub- sub-matrix has rank most C). Our goal get an estimate P (M(e.)) (ycc. of this matrix that entry-wise O(2 -f) close to the true matrix. To do this, for each user in (f.)), we randomly recommend items from (/(5.) with probability 22 log di (Line 6). Here, d1 = max(I|M((.)) 1,1(0)))))) d2 min (IM().9) (W(4))) We dg
p O then rely on low-rank matrix completion algorithm (Algorithm 4 to estimate the low rank sub-matrix. we show that our estimate is entry-wise ( accurate. This also shows that our algorithm gets more accurate estimate of P P.
By relying on Lemma []
go to the later phases.
User Clustering (lines 7-8 of Alg. D.. After the exploration phase, we refine the user partition to make it more fine-grained An important property we always want to ensure in our algorithm is that M(4.)) the th group/crude cluster in phase f, is a nice subset for all (f. i) (see Definition for a definition of nice subset). To this end, we build user-similarity graph whose nodes
users in ((.+), and draw an edge between two users if they have similar rewards for all the arms in (tt..)) (Line 8 in Alg. is, we group all the users in a connected component into single cluster. our analysis, we show that each connected component of the graph is nice subset.
Next, we partition (E, based on the connected components of the graph. That
7

---

Algorithm 1 B-LATTICE (Blocked Latent bAndiTs via maTrix ComplEtion
Require:
Phase index (, List of disjoint nice subsets of users M list of corresponding subsets of active items No clusters C, rounds T, round index to. exploit rounds fexploit estimate P of P, entry-wise eπrоr guarantee of P restricted to users in .M and all items in N count matrices K, L. NMXX // 1) K, are global variables 2) _M is a list of disjoint subset of users, each of which are proved to be nice w.h.p.
1: for 1th nice subset of users M E M with active items A/(c.)) (1th set in list AT(9)
2: Sett to. Set = = = e//88Cife >
and A = |ll otherwise. Set De+1 = E
// Beginning of a phase
Run exploit component for users M with active items N14. dated active set of items, round index and exploit rounds N( tt fexplit Exploit(MM(4..) ,Nrit.t), ( teppiit P Mit..._yt..) wat.), At).
Obtain up-
//Becommend common set of identified golden items (VT6,))) 1, 5: if [A 2 T1/3 and p < 1 then
4: Set = =
d2 min(I (. (V and cl
for some appro-
27,
priate fixed constant c >>> 0.
6: Run explore component for users in (E.) with active items N/C..) Update estimate and round index ,,((t,)) P. + Exp)orre(MM))) (, (tt,,,,, p) such that Metee - Micio (xte,))) S Def1 w.h.p.
//Random Exploration and estimation of relevant reward sub-matrix 7: For every user u E (M compute T.! = [i e (VC,) P (T= P 24 }.
8:
Construct graph g(C.)) whose nodes are users in ( and an edge exists between two users u, v
((.3) if P p < 2Ax+1 for all items æ E (A(C..))
// Construct graph encoding user similarity Intitialize lists M = | and N,(++)> =I]
9:
10:
For each connected component M(fisa)) (U,M(i)))) = M compute A((())) Mit...)) T.. Append Append ((E..)) into MM and (((..)) into A A?(++1)
//Construct finer clusters and identify joint good items
Invoke B-LATTICE(É + L, (((()))) (N((++)) C, T,o [ t, tewbit P, E141, K, L).
11:
// Recurse for new list of user groups and corresponding surviving items
12:
else
13:
For each user MC00, recommend unblocked items in (666)) until end of rounds.
end
15:
end for
Exploitation (Alg, 3). The main goal in the Exploit sub-routine of our algorithm is to identify common golden items for a group of users jointly. Consider group of users M with active items N at the beginning of exploit sub-routine invoked in the 4th phase of Algorithm I We perform the following test Line of the Exploit sub-routine: for every user u. E M, we check
P (I)A PwR., (IAD 2 c'2-è for some constant > 0 that if the estimated highest rewarding and lowest rewarding items of the user u have significant gap. For all the users that satisfy the above property, we take a union of the items close to the estimated highest rewarding item for each of them (Line 3). We can show that these identified items are actually golden items for all users in the nice subset M. Hence, we immediately recommend these identified golden items to every user in the nice subset B times. In case golden item is blocked for user, we recommend an unblocked active item (Line 5). Subsequently we remove the golden items from the active set of items (Line 8) and prune it. We go on repeating the process with the pruned of items until we can find no user that satisfy the above gap property between highest and lowest estimated rewarding items in the active set.
To summarize, in each phase of Algorithm [. we perform the exploration, exploitation and user clustering steps described above. As the algorithm proceeds, get more fine grained clustering of users, and more accurate estimates the rewards of active items. Using this information, the algorithm tries identify golden items and recommends the identified golden items users.
Implementation Details: The actual implementation of the algorithm described above a bit more involved due to the fact that every user has to be recommended item at every time step (see

---

Algorithm 2 Explore (Explore Component of a phase)
Require:
Phase index t, nice subset users M, active items N, round index to. sam- //Takes particular set of users (nice w.h.p.), their
pling probability p. corresponding set of active items and returns an estimate of corresponding reward sub-matrix. Unblocked items
data recommendations are kept track (almost) randomly recommended obtain in global variables K,L. Data from previous phases are not used to maintain independence.
1: For each (i E M x W. independently set d,j = 1 with probability and 6g 0 with probability 1
2: Denote Q2 = {(t,] J) M x .V ري
and m maxieM |i E N (i.j) Q be the maximum number of index tuples in partieular row. Initialize observations corresponding indices in Q to be A &.
Set m, =j E A (u, j) E Q]
// Create Bernoulli Mask Q with the idea of recommending all items in ?
3: for each user u E M do
4: for rounds ( Find item in [i E EN (u.j) E Q, duy 1]. Set رus
2,..., me, do
// Find item in for the user that has not been recommended yet in this
function instantiation
6: Ku= + Luz B (= unblocked), set (t(t) and recommend to Observe R R and (1)
update A = AU [R (p) Kus + Kus +1. Recommend unblocked item in $2
7: If + Lus = B (= is blocked), recommend any unblocked item (t() in N s.t. (t))) & Q. Set A = Au (R (R (p)(tt) where t' < / is the last round when Pu (t') was recommended to user u but the observation R has not been used in an invocation of the function Estimate. Update Kuz Kus 1 and Lus f- Luss 1. / //Found item blocked but some observation can be re-used end for
Update (t) (t)
9: for rounds t= to + mh, + I...., to do
10:
Recommend any unblocked item (1) in V s.t. (u, P=(()) & Q. Update Ltp)(!) <- Lupu(t) 1.
// No available items in Ω to recommend. Recommend some other item end for
12:
end for
13: Compute the estimate P (a C, and return P, m.
// Low Rank Matrix Completion of Reward Sub-matrix PMW using observations in Ω
problem setting in Section 2p. To see this, consider the following scenario. Suppose, we identified item j golden item for users in the nice subset M (crude cluster) in the Exploit sub-routine invoked in some phase of Alg. [ Moreover, suppose there are two users 41, U2 in the cluster for whom the item has been recommended n1, n1, times respectively, for some ni 122. So, for the final n2 Ti iterations during which the algorithm recommends item j to u, it has to recommend some other item u2- In our algorithm, we randomly recommend item from the remaining active rounds. We store the rewards from these recommendations and use them the exploration component of future phases. A similar phenomenon also occurs in the Explore sub-routine where we sometimes need to recommend items outside the sub-sampled set of entries in f2 (Line 7 and 10 Alg. 2 To this end, we introduce matrices K, L E MRM which perform the necessary book-keeping for us.
of items for during those 72
K tracks number of times item has been recommended to user and the corresponding observation has been already used in computing an estimate of some reward sub-matrix (Line 2 of Alg. 2 Since these estimates are used cluster users and eliminate items (Lines 7-10 in Alg. D. these observations are not reused in subsequent phases to avoid statistical dependencies. L tracks the number of times an item has been recommended computing an estimate of reward sub-matrix so far. These observations can still be used once in Line of Alg. Observe that K.j + Lij the total times user has been recommended item j. In practice, eliminating observations is unnecessary and we can reuse observations whenever required. Hence Alg. can work even when B 1 (see Alg. o a simplified and practical version).
user and the corresponding observation has not been used in
Handling very few active items (Line 5 in Alg. D.. Recall, in the exploration step of phase é, we randomly recommend active items with probability p O log p > 1, then we simply recommend all the remaining unblocked items for each until the end. In our analysis, can
d2

---

Algorithm 3 Exploit (Exploit Component of a phase)
Require: Phase index f, nice subset of users M, active items N, round index to, exploit rounds exploits estimate
P of P and enor guarantee A such that PM.N- PM.r| S 88CA, with high probability. / //Takes particular set of users (nice w.h.p.), their corresponding set of active items and an estimate of corresponding reward sub-matrix as input. Identifies common golden items for all aforementioned users in this module and recommenda them jointly until exhausted recommendations are kept track of in global variables K, and active items are pruned.
1: while there exists E .M such that P ( - Caanw-PPaae PURIQNNII 2 64CA.) do
2: Compute R2 {j .N Puj (1X 2 J for every user M.. Compute 8 Uus.MR... // Find common set of golden items for all users in M
3: for rounds f = to + f, + 2,....,6e
S|B
4: for each user u E M do
5:
Denote by the [(L - lo/B]] item in S. I' + Lur < B (r is unblocked), then recommend to and update L... Lie 1. K.. L.x B blocked), recommend any unblocked item y (i.e Kuy + Luy B) for the user u and update Luy + Luy + 1.
// Recommend all identified golden items
6:
end for end for
7:
8:
Update A' W /// Remove golden items and prune active items W
9:
Update ta + to + |S| B feeploit <- texploit |S
10:
end while
11: Return N, to faxploit.
show that this happens only if the size of surviving items is small, and when the number of remaining rounds is very small. Hence the regret is small if we follow this approach (Lemma (5) Similarly, when remaining rounds become smaller than T// we follow the same approach.
Running Time: Computationally speaking, the main bottleneck of our algorithm is the matrix completion function Estimate invoked in Line 13 of the Explore Component (Algorithm 2). All the remaining steps have lower order run-times. Note that the Estimate function is invoked at most Oo T) times since there are can be at most C disjoint nice subsets of users at a time and the number of phases is log T. Moreover, note that the Estimate function (Algorithm 4) solves a convex objective in Line 3 - this has a time complexity OM + NPM) which is slightly limiting because of the quadratic dependence. However, number of highly efficient techniques have been proposed for optimizing the aforementioned objective even when M, N are in the order of millions (see [14).
Proof Sketch of Theorem I We condition on the high probability event that the low rank matrix completion estimation step is always successful (Lemma [7]. Note that for fixed user, the items chosen for recommendation in the exploit component of any phase are golden items and costs zero regret if they are unblocked and recommended. Even if it blocked, we show a swapping ignore the explore component the g phase, we can bound the sub-optimality gap of the surviving active items by some pre-determined We prove that this holds even with the (chosen) permutation of the recommended items (Lemma (8). We choose ee be exponentially decreasing in and the number of rounds in the explore component of phase E is roughly 1/e.. Putting these together, we obtain the regret guarantee in Theorem
to similar effect. That is, with appropriate permutation of the recommended items, argument the regret incurred from golden-items altogether. Moreover,
Conclusion and Future Work
We study the problem of Collaborative Bandits in the setting where each item can be recommended to user a small number of times. Under some standard assumptions and a blocking constraint of Ollg T). we show phased algorithm B-LATTICE with regret guarantees that match the tight results with no blocking constraint [25]. To the best of our knowledge, this is the first regret guarantee for such a general problem with no assumption of item clusters. We also provide novel regret lower bounds that match the upper bound in several regimes. Relaxing the assumptions, extending guarantees to blocking constraint of B and tightening the gap between the regret upper and lower bounds very interesting directions for future work.
10

---

Acknowledgements
We would like thank Sandeep Juneja for helpful discussions on understanding the information theoretic limits of the problem.
References
[1] Charu C Aggarwal et al. Recommender systems, volume 1. Springer. 2016.
[2] Kaito Ariu, Narae Ryu, Se- Young Yun, and Alexandre Proutière. Regret in online recom- mendation systems. Advances in Neural Information Processing Systems, 33:21 141-2110,,,, 2020.
[3] Kishor Barman and Onkar Dabeer. Analysis of collaborative filter based on popularity amongst neighbors. IEEE Transactions on Information Theory, 58(12):7110-7134 2012.
[4] Guy Bresler, George H. Chen, and Devavrat Shah. A latent source model for online collaborative filtering. Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS' 14, pages 3347-3355 2014.
[5] Guy Bresler and Mina Karzand. Regret bounds and regimes of optimality for user-user and item-item collaborative filtering. In 2018 Information Theory and Applications Workshop (ITA), pages 1-37. IEEE, 2018
[6] Guy Bresler and Mina Karzand. Regret bounds and regimes of optimality for user-user and item-item collaborative filtering. IEEE Transactions on Information Theory, 6776::41974422. 2021.
[7] Guy Bresler, Devavrat Shah, and Luis Filipe Voloch. Collaborative filtering with low regret. In Proceedings of the 2016 ACM SIGMETRICS International Conference Measurement and Modeling of Computer Science, SIGMETRICS '16 pages 207-220, New York, NY, USA, 2016. ACM.
[8] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. arXiv preprint arXiv: 190Xiv 07698, 2019.
[9] Onkar Dabeer. Adaptive collaborating filtering: The low noise regime. In 2013 IEEE Interna- tional Symposium on Information Theory, pages 1197-1201. IEEE, 2013.
[10] Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglou, Giovanni Zappella, and Evans Etrue. On context-dependent clustering of bandits. In International Conference on Machine Learning, pages 1253-1262. PMLR, 2017.
[11] Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits. In International Conference Machine Learning, pages 757-765. PMLR, 2014.
[12] Dorota Glowacka et al. Bandit algorithms in information retrieval. Foundations and Trends in Information Retrieval, 13(4):299 2019.
[13] Reinhard Heckel and Kannan Ramchandran. The sample complexity of online one-class collaborative filtering. In International Conference Machine Learning, pages 1452-1460. PMLR, 2017.
[14] Cho-Jui Hsich and Peder Olsen. Nuclear norm minimization via active subspace selection. In International Conference Machine Learning, pages 575-583. PMLR, 2014.
[15) Wasim Huleihel, Soumyabrata Pal, and Ofer Shayevitz. Learning user preferences in non- stationary environments. In International Conference on Artificial Intelligence and Statistics, pages 1432-1440. PMLR, 2021.
[16] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 665-674, 2013.
11

---

[17] Prateck Jain and Soumyabrata Pal. Online low rank matrix completion. arXiv preprint arXiv:2209.03997, 2022.
[18] Vladimir Koltchinskii, Karim Lounici, and Alexandre B Tsybakov. Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. 2011.
[19] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[20] Shuai Li, Wei Chen, and Kwong-Sak Leung. Improved algorithm online clustering of bandits. arXiv preprint arXiv:
2019.
[21] Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 539-548, 2016.
[22] Greg Linden, Brent Smith, and Jeremy York. Amazon. com recommendations: Item-to-item collaborative filtering. IEEE Internet computing, 7(1):76-80, 2003.
[23] Gregory Linden, Jennifer A Jacobi, and Eric A Benson. Collaborative recommendations using item-to-item similarity mappings, July 24 2001. US Patent 6,266,649.
[24] Odalric-Ambrym Maillard and Shie Mannor. Latent bandits. In International Conference Machine Learning, pages 136-144. PMLR, 2014.
[25] Soumyabrata Pal, Arun Sai Suggala, Karthikeyan Shanmugam, and Prateek Jain. Optimal algorithms for latent bandits with cluster structure. arXiv preprint arXiv:2301.0704/4 2023.
[26] Yunzhe Qi, Tianxin Wei, Jingrui He, et al. Neural collaborative filtering bandits via meta learning, arXiv preprint arXiv:2201.13399 2022.
[27] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Item-based collaborative filtering recommendation algorithms. Proceedings of the 10th international conference on World Wide Web, pages 285 225-295,22 2001.
[28] Jonathan Scarlett and Volkan Cevher. An introductory guide fano's inequality with applica- tions in statistical estimation. arXiv preprint uxXiv:191.0000 2019.
[29] Devavrat Shah and Kang Zhang. Bayesian regression and bitcoin. In 2014 52nd annual Allerton conference on communication, control, and computing (Allerton), pages 409-414 IEEE, 2014.
12

---

Limitations: The main contributions of our works are theoretical. From a theoretical point of view, the limitations of our paper are discussed in (nnd In particular, we believe that tightening the gap between the upper and lower bounds in regret will require novel and non-trivial algorithmic ideas we leave this as an important direction of future work.
Broader Impact: impact.
Due to the theoretical nature of the work, we do not foresee any adverse societal
A Low rank matrix completion
Below, we describe the Estimate sub-routine to estimate a M x N low rank matrix Q of rank r given a partially observed set of noisy entries (Zij (i.)een corresponding to a subset & S [M] [N]. Here EZy Qi for all (i.j) Ω and furthermore, (Zzz (Kj)en independent sub- sub-gaussian random variables with variance proxy most o²
Algorithm 4 Estimate (Low-rank matrix completion
Require: Matrix dimensions (M. N), noise varianee o², rank r, subset of indices that are observed Ω C
[M] x [N] and noisy observations (Ziz (+.)))
1: Partition the rectangular matrix into square matrices. Without loss of generality, assume I N. each
E [N], randomly set Ç to be a value in the set [[N/M] uniformly at random. Partition indices in [N]
into [N) [N](* ..... [N](k) where & = [N/M] and [N]( = [i E [N] | Ç: = =q} for each q [K]. Set
2 2 (MM) (N)()) for all q [k].
(If M 2 N. partition the indices in [M].]
2: for q [k] do
3: Solve the following convex program with A Cia max M, N). for some constant C2 0
(9)
min (()))MMX(N(()))
Σ
2
where |iQ(0)], ||. denotes nuclear norm of matrix Q (0) and Tu(f) index of j set (N]())
4: end for
5: Return Q E R MxN such that Q (M) Q (4) for all E [+]
B Explore-Then-Cone
(ETC)
We first present greedy algorithm in the blocked setting with B (no repetition) that uses the Explore-Then "ThenCCommi (ETC) framework. Such an algorithm has two disjoint phases exploration and exploitation. We will first jointly explore the set of items (without repeating same item for any user) for all users for a certain number rounds and compute an estimate P of the reward matrix P. Subsequently, in the exploitation phase, for each user, recommend the best estimated distinct items (that have not been recommended in the exploration phase to that user) inferred from the estimated reward matrix P. Note that we explore too less, then our estimate will be poor and hence we will suffer large regret once we commit in the exploitation phase. On the other hand, if we explore too much, then the exploration cost will be high. Our goal is to balance both the exploration length and the exploitation cost under the blocked setting. Thus, we obtain the following result:
Theorem 3. Consider the GBB setting with M users, C= = O(1) clusters, N items, T recommendation rounds and blocking constraint B = 1. Set d2 = mMi N). Let R up.(t) be the reward in each round, defined as in ①T. Suppose d2 2(p log(rdz) Let P MRM be the expected reward matrix that satisfies the conditions stated in Lemma and let o² be the noise variance in rewards. Then, Algorithm 3 applied the online rank-r matrix completion problem under the blocked setting guarantees the regret defined as in eq. 2 be:
Reg (T) (1TT113 |
1/3 max (1,
1/3 M
N
2 max (1,
N (M + +|111
T-2)
(6)
In order to understand the result, note that the second term in the regret bound stems from the fact that in our algorithmic framework, the low rank matrix completion module needs certain number of
13

---

Algorithm 5 ETC
Algorithm with Blocking constraint B = 1)
Require: users M, items N, rounds T, noise o², rank of P.
1: Set p p- O= (
Tor
2/3
Set d2 min N) and À = do for
constant C.
2: For each tuple of indices (i,j) E [M] x []. independently set d,j = with probability p and
p. 3: Denote f (1.5) E [M] x [N] 6; = } and m [M [] E [N] (i, E 2 to be the
8;j = with probability
maximum number of index tuples in particular row. For all (i,j) E Ω2 set Maski = 0.
4: for rounds f 1, 2. .................. 771 do
5: For each user u 24 recommend an item Pt(t) in {j E [N] (u,j) E 22 Maskuf = 0} and set Maskup. and has not been recommended yet user u. Observe R
1. If not possible then recommend any item (t()) in [N] s.t. (u, Pa Pt)) & 22
"Pp(())
6: end for
7: Compute the estimate (stimate(MM, [N], o², r, 2 [R (x))
E
R as
output of P
8: for each remaining rounds do
9: Set J'. argmaxjE(M) ())(() for each user u, s.t. Fu(K) has not been recommended before
10: For each user u E [M]. recommend the item (i%. to user u.
end for
observed indices and therefore a certain number of exploration rounds (note that 2 Cp²d5' d2 for some constant C O in Lemma D Similarly, the third term stems from the failure of the estimation module; again, the term T can be replaced by T-c for any constant > 0. The first term in the regret bound captures the dependence on the number of rounds T - the scaling of T2/3 is sub-optimal and our subsequent goal is to improve this dependence to the rate of VT.
Proof of Theorem 3 Suppose we explore for period of rounds such that the exploration period
succeeds with a probability of - v. Conditioned on the event that the exploration period succeeds,
obtain estimate P of the reward matrix P satisfying [P Pllco S Recall π. [N] - [N] to be the permutation on [N] such that for any i,j E [ i < j. we have P Pu..,()) 2 P Pu (f) Similarly, denote म. : [N] + [N] such that for for any i, E [N]; <.j. we have (i) P Pu (z)- Now consider any index i E [T] for which we will analyze P Put,,()) P (.)((() which is the error
we choose the ,th item according to the estimated matrix P (instead of P). There are several cases that we need to consider. First, suppose (i) TT.(f) where j S i. In that case, have P (a) P (1) 2 0. Now, consider the other case where j > implying that the element in the jth position in the permutation nu has shifted to the left in म., In order for this to happen, there must exist an element in < i S i2 for which (i2) n., (i1) implying that an element in in the permutation has shifted to the right in H.. Therefore,
P Po...(1) Punm(i) P Poñ.(() - P Pu + Puu.. (1) - -Pai P.n
+ P (n (12)
P (12) + Pun P (u 2 -2p
Pl S p. P. (1) P (unu(tz)= 2 0 (since i S i2). P (t)) where we used the fact that P
P "T. (8) = P (t) P (i) 2 0 (since i1 S. i). Therefore, at each step of the exploitation stage, for each user u, we recommend one of the top T items (as inferred from P) with the highest reward that have not been recommended until that round to the user in each such step, we will suffer a regret of at most 2p if we compare with the item the same index in T.. before, conditioned on the event that the exploration fails (and in the exploration stage as well), the regret at each step be
14

---

bounded from above by c/ In that case, we have
Regn (T)
Σ
P ux (0)
Σ
P (1)
S max
Σ
P (x)
Σ P PuT,(()
M
[M[M]
[M] [E[T]
AE(T]
LE[T]
LE[T]
- 25 P X + 2(T - 5) Pr Pr(ppllrration succeeds) + 2(T - 1) Pr(Exploration fails)
25
P
+ + P|
We use Lemma
set S = O(ND v NNloog (Np such that p 0 v42
1 log d2
and
p
==1- 1= ). We have
Reg(T) s <N VNplog M5-1
|P|| + TO or
1 log d2
+ T(8 + )) ||
Vdg p
For simplicity, we ignore the logarithmic and lower order terms and attempt to minimize No P|l00
2/3
log d2
(Simplifted Expression) by choosing p (N||Pl>>>) 2/3
Tar
v log dh
dd
Vdz
5 pf Cp²d2 log d2, then notice that Np 2 and therefore Np + Np log M6-1
O log MÒ-1) Subsequently, we have
N (o d2 1/3
(T) = = (P)b
log VT 1PlloT
d2
There exists an edge case when the value of that minimizes the simplified expression satisfies S Cj²d,'' log" d2. Then we can substitute p = Cy²dd log d2. In that case, the second term in the simplified expression will still be bounded as before. On the other hand the first term in the simplified expression will now be bounded by O Nu² log d2 (MNT))[[ Hence, our regret will be bounded by
d2
(10"1""Nooo ( d2
1/3
Reg( = O (TT233(0277111 (l(x) 1/3
log VMT log (MNT) P| + || T-2)
d2
d2
= Ō (
P 3 max
1, M
N 1/3
+ 1= 1 max (1,
N
|P|| T
M
C Experiments
We conduct detailed synthetic experiments in order to validate the theoretical guarantees/properties of our algorithm. For this purpose we use simplified version of B-LATTICE described in Alg. (all experiments have been performed on Google Colab instance with 12GB RAM):
In PB-LATTICE(AIg op. do not the exploit component for simplicity. Intuitively, if the user is recommended a golden item during the explore component, it a good event in any case. Furthermore, in Step 14, we use k-means to cluster the users. Since we obtain significantly large embedding vector for each user in Step 13, k-means is quite practical.
We run DA-TAETIN several synthetic datasets. There are two main baselines for us to consider 1) Greedy Algorithm namely Alg. 2 In the setting where the user u, on being recommended item j provides a like (+1) with probablity P and dislike (-1) with probability 1 Puj. we also compare with Collaborative Greedy in 4.. However, recall that 4., even in the restricted setting, only provides theoretical guarantees the number of likeable items (items with probability of liking > 0.5) recommended during the course of rounds.
We generate three synthetic datasets to validate our algorithms. For each of them, we take M = 150 users, N 150 items and T 60 rounds (hence the total items recommended will be 9000). The reward matrix P UVT (U E M and V E NRNC)) is generated as in (25) in the ,th row of U, the (i%C)th entry set to be 1 while the other entries are 0; the entries of are sampled in the following way for the three datasets.
15

---

200
B-LATTICE
LATTICE Greedy
Reward
-50
Greedy (m=30)
Groedy
Roundwise Reward
Greedy (m=30)
Rounds
Rounds
(a) V has entries distributed according 00((0,25) We (b) V has entries generated according (0 25). We observe R (+)
((P (u) 0.25)
observe R (apu(1) (8) -NP (())
(1)
Cumulative Reward
200
Gready
Greedy (m=10)
Roundwise Rewarr
4.5
Gready (m-30)
Greedy (mm10)
4.0
3.0
50
2.5
30
20
30
50
10
Rounds
Rounds
(c) has entries distrihuted according to (0), (d) entries distributed according to ((0, 5). We observe (t)
= N (O); 0.25)
observe (t)
NN up.ctt), 0.25)
(1)
(P)(
100
I-LATTICE
Cumulative Reward
Gready
Roundwise Reward
Gready (m-30)
0.5
Collaborative Greedy
0.6
Collaberative Greedy
20
64
02
Rounds
Rounds
(e) V has entries distributed in J0.05, 0.95] with equal (f) V has entries distributed in [0.05, 0.95] with equal probability. We observe (1( (t)(tt) 2Ber (upp(())))) probability. We observe R up.. (t) 2Ber (P))..t))
Figure 1: Cumulative Regret of the greedy algorithm (Alg. 5) and the Blocked LATTICE algorithm (simplified version in Alg. 6. the setting where our observations are in ( [+1,-] -1] i.e. the user likes (+1) an item with probability p and dislikes with probability algorithm provided
p. we also compare with the named Collaborative-Grres Greedy. all our settings, we have M 150 users, N 150 items, C = 4 clusters and T 60 rounds. The ground truth reward matrix P = UVT is generated in the following way: each row of is a standard basis vector while each entry V is sampled independently from (0,, 25) in (a) each entry of V is sampled independently from 2( 5) in (b) and each entry of U sampled independently from (0, 1) in (c). In (a) and (b), gaussian noise with variance 0.25 is added the expected observation and in (c), observe +1 (probability expected reward) or -1. Notice that PB- PB-LATTICE has 1) a small cold-start period 2) always makes good recommendations 3) better empirical rewards than other baselines.
16

---

Algorithm 6 PB-LATTICE (Practical Blocked Latent bAndiTs via maTrix ComplEtion with blocking constraint B 1)
Require: Phase index L. phase length my, List of disjoint nice subsets of users ( list of corre-
sponding subsets of active items A clusters C, rounds T, noise o² > 0, round index tu, gap factor V/.
1: Set À = 100 Vinov//eeMMMM (m²/M).
2: for rounds + 1,40 + 2,,..., min(lo m, T) do
3: for 7th nice subset of users M(L,) (M()) with active items A((e.) (ith set in list A(O) do
4: Initialize (2(
5: for user in (t.i) do
6: Choose a random item j E A(((.)) for recommendation to user u. If j is not blocked, recommend j to user u and observe Zuj to be the feedback from user for item j. If j is blocked, then recommend any j' E A/te.i) that is unblocked for user u E M().)) Observe Zujr to be the feedback from user for item j'.
7:
Update Q2(1) 22(1) U {(u,))}
8: end for
9: end for
10: end for
11: for 7th nice subset of users M(L.)) M( with active items A(te,) (ith set in list do
12: Initialize M(++1)= and (((++)
13: Compute T MRM by solving the convex program
1
Σ
Zig - Tiy)² + Me..
min TERNXM (KJ)R
2
14:
Solve k-means for users in M(Ee) using the vector embedding formed by the rows in TmMcn Choose best & S by using ELBOW method. Denote the cluster of users by (M(()s)))
15:
for each cluster users M(fij) do Compute set of active arms (f(A. {s E ((G.) Tus 2
16:
(T) Ve for some M((.h.)). Here 7y is the permutation of the surviving items in (/(6.) in descending order of estimated reward for user Append Mll.i.i to ( and (f(..i to A(4+1). end for
17:
18:
19:
Compute m M4+1 as function of f. Set t min(to + m, T).
Ift < T, invoke Algorithm PB-LATTICE(phase é 1, phase length m4+1, list users M(++1)
20:
list of items AV(+1), clusters C, rounds T, noise o², round index to + m, gap factor ve+1)..
21: end for
1. (DI:) Each entry of V is sampled from gaussian distribution N/0, 25) with mean zero and variance 25. User on being recommended item j provides random feedback distributed according to (PP ujj. 0.25).
2. (D2:) Each entry of V is sampled from a uniform distribution 4(0, 5) with range [o, 5).
User on being recommended item provides random feedback distributed according to ([P us. 0.25).
3. (D3:) Each entry of V is sampled from uniform distribution [0.05, 0.95] with equal probability. User on being recommended item y provides a like (+1) with probability P.j and dislike (-1) with probability 1 1- Puj-
For the PB-LATTICEalgorite parameters as m = 10 + 2 and 1y = [P| / (8 2²). Since PB LB-LATTICEIS recursive algorithm, we initialize PB-LATTICEwith phase index I, phase length 12, list users [[M]] list of items [[N], clusters C, rounds T, noise o², round index 1, gap factor ||P|| /16. For the greedy algorithm (Alg. 5 we experiment with two exploration periods (m 10 and m = 30). Finally, for the Collaborative-Greedy algorithm in [4, we choose 0 = 0.5 and 0.5.
(Alg- 6) we choose the hyper-parameterr on the phase lengths and gap
17

---

Results and Insights: The cumulative reward until round t (defined as M M ΣØ= Σm P Papp())
and the round wise reward at round (defined as M ca=1 P Pesp.(t)) is plotted for all the three datasets DI, D2, D3. in Figures la lb rewards, PB- PB-LATTICEhaS several practically relevant properties which are demonstrated through our experiments:
Ic
ld le and If Apart from obtaining good empirical
1. Note from Figures Ib and Id that the greedy algorithm has a large cold-start period for good exploitation properties. If the exploration is too small, then the estimation becomes poor. On the other hand, PB-LATTICHE CEimproes in phases therefore, it has a small cold-start period i.e. it starts recommending relevant items very quickly and also has good estimation guarantees
2. Collaborative-greedy in proposes exploration rounds throughout the entire course of T rounds. This is often impractical as users will demand good recommendations throughout. This demonstrated in Fig. [f where the red curve tround-wise reward of Collaborative- Greedy) has several dips but the round-wise regret of EE-LATTICEsttue high.
D Detailed Proof of Theorem 1
Next, we characterize some properties namely the condition number and incoherence of sub- matrices of P restricted to a nice subset of users. The following Lemmas 2 and can be found in [25]
Lemma 2. Suppose Assumption iss true. Consider sub-matrix P o having non-zero singular
values X1 > we have
> Ne: (for C' C). Then, if the rows of Psub correspond to a nice subset of users,
N, X
V.
Ac
Lemma 3. Suppose Assumption 7 is true. Consider a sub-matrix P sub E B
XA' (with SVD decomposition P subb UEV) of P whose rows correspond to a nice subset of users. Then,
S V Cr and
U
S
N'
aM'
2,00
2,00
Lemmas
2 and B Jlloo us to apply low rank matrix completion (Lemma] to relevant sub-matrices of the reward matrix P.
D.1 Main Analysis
Blocked LATTICE run in phases consisting of exploit component and explore component indexed by = ........ Note that the exploit component of phase is followed by the explore component. However, for the first phase, the exploit component has a length of zero rounds. Importantly note that any phase (say E) for distinct nice subsets of users (EE)), (E.f) will be run asynchronously as reward observations corresponding one subset is not used to determine the policy for any other subset of users. At the beginning of the explore component of each phase l, we have the following set of desirable properties:
(A) We will run the explore component of phase asynchronously and separately for list of disjoint nice subsets of users ( = (..,,,,((,,,,,.)) and respective sets of arms
Ar(0) {AV(L.))... ... ,N((..e)) where a₂ I C such that UsE(a)) C [M), (E60 n M( = @ for any i.j E [ag] (i.c. the groups of users are nice subsets of [M] with no overlap) and ATCa) C [N] (i.e. the active set of items (L((.)) for users in ((,)) are a subset [N] but the active sets can overlap). The sets {(M(é,)) (oM((t.),,A((E..)) _A((..)) ]ie(as] remain unchanged during the explore component of phase t. As mentioned before, the round at which the explore component of the phase starts is different for each subset of nice users (t.1).
(B) At any round items chosen for recommendation (see Step 5 in Alg. 3 in exploit components so far (from round = 1) for users in (f..). In other words, the items in (ftt))
[T] in particular phase f, let us denote by Mit.. to be the set of
Mie..) have already been
recommended to all users in ((.)) up to 2th phase. In that case, we also maintain that
(E,)) Milaa S ( (t) T/B
18

---

the best T/B items (golden items) not chosen for recommendation so far in the exploit phases for users in M are contained in the set of surviving items i.e. if 2 [N] it must happen that
O Mans)
then
T/B- T/B-/oc 2) MeGi)) for all E [od]
Arces 2
U (Tt(tt MEMUN)
(8)
Note that eq. 8 iiplies that for every user _M there sufficient golden items in A to be recommended for the remaining rounds. To see this, note that there are T/ T/B B golden items at the beginning and no golden items which are unblocked are climinated. Hence the number of remaining rounds at any point must be smaller than the number of possible allowed recommendations of golden items belonging to the surviving set of items.
(C) Furthermore, for all i [ar], the set A/t,ii must also satisfy the following:
P Pu (1)AAG - min Puj S ce for all u E M
JENUL.
where eg is a fixed exponentially decreasing sequence in (in particular, choose e1 ovp for l > for some constant C" > 0).
[P|| and = C²2 min (IP))
log N
Next, at the beginning of the exploit component of phase & + 1, we will have the following set of desirable properties:
(a) At every round in the exploit component of phase + 1, we maintain a list of disjoint nice
subsets of users M(++1) (M((+1.1) ..... M(.,,,(((a)))) (where Us M((+1,))) C
[M] and corresponding sets of items A( = (A((E-1,411) ". 10641,8. 1)} where ag+1 S C Cand [
C [N]. Note that in the exploit component, we also use the round index in the superscript for item subsets as they can change during the exploit component (unlike the explore component).
(b) We ensure that for any user M(++1.0), the of items chosen for recommendation in the exploit component of phase E + belongs to the set of best T items i.c. { (f))?
Since LATTICE is random, will say that our algorithm is (ce, good if at the beginning of the explore component of the 5th phase the algorithm can maintain list of users and items satisfying properties A-C. Let us also define the event E(() be true if properties (A-C) are satisfied at the beginning of the explore component of phase é by the phased climination algorithm. We can show that if our algorithm is (ee, e) good then the low rank matrix completion step (denoted by the event e in the explore component of phase É is successful (i.c. the event e/ is true) with high probability.
Conditioned on the aforementioned two events e/",, with probability 1, during all rounds t of the exploit component in phase + 1, properties a - b are satisfied and the event E Eff++) is going to be true. We are going prove inductively that our algorithm is (ee, -)-good for all phases indexed by f for our choice of { with high probability.
Base Case: For L 1 (the first phase), the number of rounds in the exploit component is zero and we start with the explore component. We initialize (1.11) = (N). = [M] and therefore, we have
max Puj min Puj (E
|Pl| for all u E [M]. <
JEN(..)
Clearly, [M] is nice subset of users and finally for every user u E [M]. the best T/B items (golden items) {TH, (t) belong to the entire set of items. Thus for & 1, conditions A-C satisfied at the beginning of the explore component and therefore the event ((1) is true. Hence, our initialization makes the algorithm (I]P]] -)oooo..
Inductive Argument: Suppose, at the beginning of the phase E, we condition on the events g that Algorithm is (godd))good for all < f. This means that conditions (A-C) are satisfied at the beginning of the explore component of all phases up to and including that of & for each
19

---

reward sub- matrix (indexed by E (az)) corresponding to the users in M and items in A Next, our goal is run low rank matrix completion in order to estimate each of the sub-matrices corresponding to {M((e,) , (
Exploration Strategy: Consider a particular nice subset users (M and corresponding active items A (s.t. | T1/3) the beginning of the explore component of phase for M For each user u E M we are going to sample each item j E AA((.))) with probability p (to be determined based on the desired error guarantee). Suppose the set of indices sampled in the explore component of phase l is denoted by Ω C MM(()) x A Now, for each user E MMt.i) we recommend all the unblocked items in the set Aa {j (V(.) (u.j) | ((9) and obtain the corresponding noisy reward (note that for blocked items in the aforementioned set, we have already obtained the corresponding noisy rewards).
For simplicity, we intend to complete the explore component at the same round for all users in M( If, for two for user u but recommendation of all items in A is incomplete for user v, then for the remaining rounds we recommend to user arbitrary unblocked items from A Note that this is always possible since the set M/(+.) has sufficiently many unblocked items allowing recommendations in the remaining rounds at beginning of explore component of phase f. We start with the following lemma to characterize the round complexity of estimating the sub-matrix P P .Vve. up to entry-wist wiiee error A with high probability using the noisy observations corresponding to the subset of indices (
u, V MM it happens that recommendation of all items in A is complete
Lemma 4. Consider a particular subset of nice users M(E.)) and corresponding active items Ar(e.S) (such that min (M/ (M/(TC), (WTG.)) z T1/3) the beginning of the explore component of phase f. Suppose d1 = max([ (.(.)))))) and d2 = min(I (N(.)) Let us fix Det1 (2 μr log di d2) and condition on the event c() Suppose Assumptions and are satisfied. In that case, in explore component of phase E, by choosing 2 p c( some constant > 0) and using
2 e2pelog logd (for
A
m = =0
pp log (M
VN)
max (I,
Nr M
log T)))
A E+1
rounds under the blocked constraint, we can compute an estimate P(0) E R MMN such that with probability - O(T 3), , we have
P MUGLANEE P P
S A
(10)
where o² is the noise variance, z is the incoherence of reward matrix P and jı is the incoherence factor of reward sub-matrix P Mit.
Proof of Lemma 4 We are going to Lemma in order compute an estimate ((() Arcea of
the sub-matrix P M.te-i),yree. satisfying p00
MIGO - PP -MMaa.,yy..
A2+1- Since ((e.))
nice subset of users, the cardinality of [M(.)) must be larger than M/(rC), Recall that is
the ratio of the maximum cluster size and the minimum cluster size; M/ /C being the average cluster size implies that the minimum cluster size is bounded from above by M/(rC). From Lemmal [ we
know that by using my = =(p [ATe..0 + ( plog([MM(E.) 8-1) rounds (see Lemma
restricted to users in (f,0) such that with probability at least 1 (6 di 12) (see Remark 5
-0(0) ( log d1
( Mud P PM vvl.
v vp2
where di = max (L. (((.)))), d2 min() and jú is the incoherence factor of the matrix P PMecoAyea In order for the right hand side to be less than Aet1, we can set
20

---

p' log for some appropriate constant e O. Since the event & is true. we must have 2/11
p=
that [ 2 M/(rC); hence d2 2 min (M Therefore, we must have that
my 0 0² p log( M VN) max (1, NT) 1
M log T))
where substitute 8-1 1/poly(T) and furthermore, the condition of the Lemma statement implies that dz 12 (T 9). Hence, complete the proof of the lemma.
Remark (Remark in (8). The error probability can be reduced from O + di to 0 d2 for any constant > 0 with only constant factor changes in the round complexity and the estimation guarantees
P Pl so. We will use 12 rest of the paper.
Note that although μ. the incoherence factor of the sub-matrix P M _p0.0) is unknown, from Lemma 3 we know that jı is bounded from above by O(μ) (recall that C, O(1))
Exploration Strategy continued: In particular, we choose Ar+1 = =e/176C at the beginning of the explore component of phase for the set of users M(F with active items A One edge case scenario when for a particular set of nice users M at the beginning of the explore component of phase f, we have [A((..)] T1/3, this case, this of nice users M do not progress to the next phase and in the explore component, we simply recommend arbitrary items in A/CC)) to users in (M...) for the remaining rounds. Another interesting edge case scenario is when d2 = min( min([M(t.) ((t..) |W((,)), .) is so small that the requisite error guarantee A4+1 (eq. 10 cannot be achieved even by setting p 1 i.e. we recommend all the items in the active set. Recall that by our induction assumption, AA(E,)) is sufficiently large that possible recommend
unblocked items for the number of remaining rounds (say T- with ty being the round at which the explore component of phase & starts). In that case, the set of users (E..)) do not progress to the subsequent phase; we simply recommend arbitrary unblocked items in the set set (f,,)) to the users in ((()) for the remaining rounds. both the above edge case scenarios, the explore component of phase for users in (.. would last for the remaining rounds from where it starts. We now show the following lemma:
Lemma 5. Consider a particular subset of nice users M(E.) and corresponding surviving items AC(E,S the beginning of the explore component of phuse f. Suppose d₁ max ([M (,W and d2 min(IM((..) [A((..)) Now Det1 c/ c//166C is such that there does not exist any p E J0, for which RHS in eq. 3can be D estimation of matrix P restricted to the rows in ((( and columns in (E.,) In that case, must have for all users E ((ES)
(P (PuRA - -Pay) = 5 (0 log di max (VT,TV Mr
(T (T) max
yEN().)
where Le is the round at which the explore component of phase & starts.
Proof. Note that by our induction hypothesis, must have B [V( 2 T T- tz because the set of surviving items must contain sufficient unblocked items (for recommendation in the remaining rounds) for every user u E ( Hence, by setting p = eq. with a certain number of rounds, we can obtain estimate Q of P satisfying
| M ware PMo 11.0 = 0 o -0(0v/ 1rS log di
Vdz
Hence, this implies that our choice of A&+1 satisfies A = 0 / logd
implying that
Vdz
of oC OCv/e 4d log di Vdg
Now, there are two possibilities: 1) either d2 = [M(e.0] implying that M/ S
21

---

[M < |
In that case, we have that E, =0( Peclov/ologg vMr
Now, because of our
induction assumption, we will have
(P (Pus NV..) Puy) S ==== =0 [o 15 Vp BEA
logd
VMr
Therefore, for any user u E MM(ei,, we recommend arbitrary unblocked items Attaa) for the remaining rounds then we can bound the following quantity
(T (-t+) te) max (Pusu(I)INVe.. - Paay) 0 TTLL V w log d1 yEA(..))
VMr
2) The second possibility is the following: d2 = ( 2 B B - -tt). In that case, from our induction assumption, we have that (B = O(log T))
$ Et =6 - 110 log d1
(Pun.(1) (V..) Puy) BEA(L.))
max
VT - t
and therefore
P PuTT( - Puy) S 12) =ō(=c
CC v 113 log di
(T te))
(T 4) max SEN())
41
o(ocy 1 Tlggg
Consider ( (( to be the family of nice subsets of which do not fall into the edge case scenarios i.e. 1) there exists 0 < S for which the theoretical bound in RHS in eq. [ can be
smaller than A4t1 2) we have (N(6.3) 2 T1/3, More precisely M corresponds to the set
{MicO M( with active items A/(21 Aet1 = 2 (
1D3 log max
min([ (A((0)))
and [ 2 T1/3]
Suppose M/(rC) = 2(T2/3). As mentioned before, the event E)² is true if the algorithm has successfully computed an estimate ((() MxN such that for all (ee M
P ( Mas9 PMMCA)
S Aeti for all M(E.)) e MM
(11)
implying that for each of the distinet nice subsets M(C..) E M after the explore component of phase f, the algorithm finds good entry-wise estimate of the sub-matrix P MMea (ice.)) In the
following part of the analysis, we will repeatedly condition on the events c (conditions A-C are satisfied at the beginning of the explore component phase E) and the event E (eq. i0 true for all nice subsets M(f.i) E M in the explore component of phase E). Note that the event el is true due to the induction hypothesis and conditioned on the event e(0) the event e(t) true with probability least 1 O(T ((T (after taking union bound over C clusters).
Fix any ((E.)) C (( and condition on the events &g algorithm has computed the estimate p(t) the user by
e(t) c(t)
For each user u E ((E.), once the
M0.9 in eq. 11 let us denote set of good items for
T. e N(eD
P.,y 2 G.. -ore) 1OB- m((.)) 11LTTE
224+1}
(12)
R = Ej ((EN) PNNy > ( - 2A
(13)
22

---

where is the round index at the end of the explore component of phase l and 10(40 Masas) is the number of rounds in exploit components of phases that the user u E M has encountered so far. Note from our algorithm, that users in the same nice subset M have encountered exactly the same number of rounds in exploit components of phases until the end of phase f. Recall that users in M have been recommended the same set of items until blocked (unless blocked already for some user in which case the item in question has already been recommended B times) in the exploit components of phases until the end of phase E (this set of items chosen for recommendation in the exploit components up show the following statement to be true (in the following lemma, we remove the superscript t in ( Mit.)) for
to end of phase l is denoted by O (f.d) M If we condition on the event &3
c()) then
simplicity the round index corresponds to the end of phase for users in M((..)):
Lemma 6. Condition on the events - ES being true. Consider a nice subset of users Mlt.)) M((t) and their corresponding set of active items A(t..) for which guarantees in eq. 11 holds. Ler 00 Mi be the set of items that have been chosen for recommendation to users in M in exploit
components of the first l phases. Denote 2 = [N]
(() Mu..y In that case, for every user u E M(E.).
10 | Mcc..) must belong to the set Tu
the items Tu [5) 2 for all E [TB-1_
Proof. Let us fix user u E M with active set of arms A Let us also fix an item a = (T(())
2 for t [TB - 10 100---oo0ic..... Mic.. order according to their estimated reward in P(() Mie.0 .N(e.)) Now there are two possibilities regarding the position of the arm in the permutation -- 1) (t) Z = (t)) | Z for some t S which implies that in the permutation मे Z, the position of the arm a is ti- In that case, the arm
-TB-1-o
|] Recall that मे Z is the permutation of the items sorted in descending
a survives in the set ( by definition (see eq. 12) 2) Now, suppose that (t. | 2 = (t1) z for some t I which implies that in the permutation ग Z, the arm a has been shifted to the right (from æ 2). In that case, there must exist another item b = T. (12) Z for l2 > I such that Tu((2) 2 = Tu (43) 2 for 13 S l. Now, we will have
P (e)
P:0
(0)
P
Pus
P
+ u2 P( < 2
where we used the following facts a) conditioned on the event Eg we have P(2 P Pus S Ae41 1 for all E M , E A((..)) b) Pub P S O by definition. Hence, this implies that a E T
Corollary 1. Condition the events 2,0,eh ,e being true. Consider nice subset of users (LE M((() and their corresponding set of active items (1,3 for which guarantees in eq. 11 holds. Suppose te is the final round of the explore component of phase E for users in Ml..), In that case, for user the set Tt contains sufficient items that are unblocked and can be recommended for the remaining tg rounds.
Proof. From Lemma 11 we showed that T:( comprises the set of items (s))) 2 for all 8 E
[TB 1 - (
M where Z = [N] 1 M Now, suppose the thth item in the set H. = (t'(')) |
2) 3}v=1 T-) M((.)) has been recommended to user u by < times in previous phases. In that case, the number of allowed recommendations of items in T:( is at least TB- B
((0) Mes
EkEn. by
which is more than the remaining rounds that is at most TB- B (0()) Exen. by (B 100 Minn M
rounds have already been used up when the golden items were identified and recommended).
Consider nice subset of users (LLi) e M and its corresponding active set of items A for which eq. holds true. At the end of the explore component of phase E, based on the estimate ((0) MMt.)..e. we construct a graph g(E,)) whose nodes are given by the users in MCL,. Now, we
23

---

draw an edge between two users u, U E M if P P02 S 20e+1 for all considered items
I EN(E).
Lemma 7. Condition on the events & Eg being true. Consider a nice subset of users M
M'(e) and their corresponding set of active items N for which guarantees eq. I1 holds. Consider the graph gl formed by the users in M such that an edge exists between two users
u E _M if P - < 2 for all considered items a E &Ntt..), Nodes in gita)
corresponding users in the same cluster form clique. Also, users in each connected component of the graph g(t.)) form a nice subset of users.
Proof. For any two users u, V E (M belonging to the same cluster, consider an arm x E (V(L)) We must have
P - P(O)
P(O
P uz + P war
P oz
+ P oz
P
24
Now, consider two u, ( that belongs different clusters P, Q respectively. Note that since the event g is true, (M(..) is a union of clusters comprising P, Q. Furthermore, we have already established that nodes in g(t.)) (users in (((())) restricted to the same cluster form a clique. There every connected component of the graph ((t.1) can be represented as a union of a subset of clusters.
Lemma 8. Condition on the events Eg e being true. Consider a nice subset of users M(L.) M)(e) and their corresponding set of active items N( for which guarantees in eq. 11 holds. In that case, for any subset y C (N(t))) and any for every user u E _M((.), we must have
P P - -Pu., 6 S S Put. - (sily S P (1) - P (e) 64
Proof. Since, we condition on the event ELe, we must have computed an estimate p(0), an estimate of P restricted to users in ( and items in (C6,)) such that
(
P A - P Mo < Aet1-
We can decompose the term being studied the following manner:
P(0 (())
(s)
= = 1...(1) (1) y (D) +
(8)
(()
(())
P(0) (I) us ( + P (2)
(2)
()) Nm, Nm, (s))
Let us bound the quantity ((0)
(.) ux. (e)yy In order to analyze this quantity, we will consider
P(0
a few cases, In the first case, suppose that T.(s)) y (ti) y for t 2 8. In that case, we will have that [(()
(x)pp/ un, (x)ly 2 0. In the second case, suppose T.. (s)))) (.(2t) for
-p(()
t2 < s and Tu (ts)) ) (T(s)
) for ty < s. In that case, we have
((0)
(())
(s)))
(
-P(
(M) + (F)( Pu) + (u)u(s) P(() NT,, (s)))'
P
(
=P (a)l
(.)) + (Tults))D Pana + P (u)()))))
((0
(.))))) 2 -2
where we used the fact P (t))( - P um Pu 2 0. In the final case, we assume that ग., (s) y
(t2))) y for > to and (t,) y = (s) y for f3 > s. This means that both the items
(a( D1 T. (ta) have been shifted the left in the permutation 7, |. Hence,
p ((()
(o))))
(m)))
P (s) y P (s), - - (s)ly
(+)l)
WT., (s)p) P(()
(e))) 2 -2 + +P (s) (s)ly -24 + PuT,, - P PPxr,)))p
24

---

Hence there must exist an element (ta) y such that 2a < s and (t(ss) 1 = (Taa)) y for
ts > In that case, we must have
P Puxi(ts)ly (u))
(ts)l
P (ta))
Puss((ts) (())
p(0) (t,(()))
pp(0)
+
und (ta)
utu(t (tT((())))
2 --24441 + PPO) uF.(()))))
P
-2 -P00
p(0
-2
(ta)l
(
aFu(t;)
Therefore, in this case, we get that P(
(e) - -D00
uTu()) 2 -4 Again, we will have that
P (1)D
P0)
( -p(()
(
(1)(1
+ P0 (TTDD - (*)
(1)) + P() (.)())
P(0
aF,(1)1 2
224+1
By combining the above arguments, we have that
P(O) u (T)
k(0)
P a.)
( - 6
(
By a similar set of arguments involving triangle inequalities, we will also have
P0 (
-P
P())
(1) - -P(2 (.)())) + 6
(x)
This completes the proof of the lemma.
We now show the following lemma characterizing the union of good items for connected component of the graph ((..), Recall that ( Mic.0 counts the number of rounds excluding the ones used
up in exploit component so far up to the eth phase.
Lemma 9. Condition the events E ( elf)
being true. Consider nice subset of users M
M)(() and their corresponding set of active items MVt..) for which guarantees in eq. 11 holds. Consider a subset of users G E ((t.s) forming a connected component. Fix Fix set y Uueg Tg
J for some I such that for every user u E 9, we have Tu(s') | ((tei) Ta(s) y for s'
(t)) Micn and some common index 8. In that case, we must have
TB
max P U. P.r) EEG 2,yEy
max (P (Pua..(1I) P un (an.()))iaa))) 24CA++1 WEG
max
I
Proof. Let us fix a user G. We have max P uzz P vy P ( min P vy. Now, there two possibilities for any y E y: first, suppose that E (.(0), In that case, we have
P (1)
Puy = P PP - P (s) + Poo.(s))) (.)(()))))))) + (
P Puy
Recall that the set () was constructed as
T(0 EEEA P >
2A where s' = TB-1 - Mina
(14)
Since !.
bound P
P 2 Also, from the construction of T.
UF. (5')
(r) [ is present in the set (0) Also, since T. is just subset of (f(+.)), the positions of the items (7.(r) [ do not change the permutation corresponding to the items in
T.(") sorted by estimated reward for v in decreasing order i.c. (r) (V(e..)) 7,(r) T.(") for any r E [s]. Hence P (a) uR. (+))T!!) 0. Hence, by combining the above, have
P Poi
P by < P P.n, - Por. (R) 24
Next, consider the when y (!(0) Hence, there must exist user u such that y T T.( and u is connected to u via a path of length same cluster form clique proved in Lemma 7. In that case, have the following decomposition:
2C - (since there are clusters and users in the
P (R) - Poy = (.).(1) P PPEL(1))
+ P (UID P ( + P (s)) - (s)
+ P (a))) ( + WR (
P uy P wuy
P Poy
25

---

Now, let us consider the terms pairwise. Due to our construction of the graph ((,,) for two users u, v connected via path of length L, we must have
PM
P
2L Note that
PO
P
P
(2)
+
P
P2
PMP
S 4LA,-1
(1)
where we used that PO)
-P
(
(1) S Next, we have P PVP. (1)1 (i)()))D S Pu Pui
un. (1)
P uF (+)) 4L Furthermore, again have (r(r) | =Fu(r) Tul for any r E [s]
and therefore P ( - P (o)()") = O. Finally, P u Puy + PaP ag Pay S 4LA++1 (since P
(T)( P 21)+)) Hence by combining, we have that
P (I)
P my <
P P (a)l 12LA
Hence, we complete the proof of the lemma (by substituting L
Lemma 10. Condition the events ( el being true. Consider nice subset of users (
E3
M and their corresponding set of active items M(,,5) for which guarantees in eq. 11 holds.
Consider two users u, V E .Mit.t) having edge i.e.
P P(0) uz
S 20 for all a E Nee,) In
that case, for any subset y C (((t,,)) and any s [[]]]] for every user M(e..), we must have
P (1).
P (o)( 12 S P Pa (u). S P Po.,(D)) P (o),()) 122
Proof. We can decompose the term being studied in the following manner:
P(O)
((()
(1)
= (
P(O
((0)
P(0) ( + POO on.(s)ly ()))"
p(()
Let us bound the quantity (f) - (0)
(
00D In order to analyze this quantity, we will consider few cases. In the first case, suppose that (s(s) y (t1) y for t1 2 In that case, will have that ((())
p(())
(+)l) 2 0. In the second case, suppose (u(s) y = (t y for
oZ (s) y
< and Tu (t3) 1 (s) ) for ta < s. In that case, we have
P0
-P (
0 (
= 00 (x)))) - (
(
(.) (F) + P(O)
P(O
())( - P (T) 2 -4Ar+1
(+)l
(s) 2 0. In the final case, we assume that (s) | N. (tz) y for > t2 and म. (t3) y= = (s) for to > s. This means that both the items (s) D. D, (t3) y have been shifted to the left in the permutation म. y. Hence,
where we used the fact (())
(.)( (0)
(.)( = 5
(t)) ((0)
P(O
P(0)
(T)
(F)(y)
(())
P
PuRo()))y' + P Pu..(O)) -P Pui
vi)l))l
P (+)))
((0)
(R 2 -4Ae+1 + + - P (u)l())ly
- + (ta))) - (s)p()))
Hence there must exist an element 7. (ta) y such that t4 < s and 7,(tt) 1 = Ta(tt) y for ts > In that case, we must have
P Pun.(Cs)D) P (e)) P
(t
P (t))l
P - (t)l( - p(()
p(()
P (2)
e..(())) P (ta)()t))
-4A + p (
-A441 p()))
(n)( p(()
2 -AA++1-
(..)))
(ūn(())
26

---

Therefore, in this case, we get that P(O)
-p(1)
vT.(s) 2 -8A441. Hence we get
e8.(s)
P
(.)
os.
(1)
P
((0)
(())
P
844+1
(.)
(
(
Also, we will have that
P0
(D)) = 50
(1)
VR
(1)
( + (()
(()
+ (U)
(1, 2 -44+11
By combining the above arguments, we have that
p(0) (L)
(
(
P on, 40
(
-
12A
(e)
By similar set of arguments involving triangle inequalities, we will also have
P
UTJD - P (.) S
P
p(0
on) v..()) + 12A
This completes the proof of the lemma.
Now, for any fixed subset y S (/(..) , let us define the set R y for user below:
R! y {j e
P uy P
( 2
Hence, R. y corresponds to the set of items for user that is close to the item with the highest estimated reward for user u restricted to the set y at the end of the explore component of phase
e(t) Lemma 11. Condition the events Eg .e3 being true. Consider nice subset of users M(e.)) M)(e) and their corresponding set of active items N(t.i) for which guarantees in eq. holds. Fix any subset y C (((,,)), In that case, for every user u E (Mtt), the item with the highest reward T (1) 1
in the set y must belong to the R!! y. Moreover, max " uu Puoll 40
Proof. Let us user E (E,))) with active of arms A(,,)) Now, we will have
P(0) P (a)
P(0)
uT (1)) (1))
P (1) + P (1)D)) P (1)(1)) P (1) - (()) (T) & 2
which implies that (1(1) 1 R(
|.. Here we used the fact that (())
P (.)
- Pujy S Aeti
P uuyy (())
(1)) A4t1 and P (I))) P
(u) I 0. Next, notice that for any s, s' R! y
P Pus'
P(0) us
+ P()) (())
((0)
p(() uss
(()
S 44
use
08
ut ut.
us
Lemma 12. Condition the events Eg Eg being true. Consider nice subset of users M(E.))
( (
M)(E) and their corresponding set of active items A(L for which guarantees in eq. 17 holds. Fix any subset y S ( Consider two users u, v E MDL having an edge in the graph ((..).
Conditioned on the events 2 we must have
max ZER! D.PER!
IP - Pwwl < 16A and
max ZER D..ER!
P - P S 164
Proof. From the construction of g(t.)), we know that users u. v. E M(E)) have an edge
(8)
((0)
24 (and therefore Pur P S P P + P uz
p
P(O)
S 44a+1) for all x E N(t.s) For simplicity of notation, let us denote R., to
27

---

be the set RVz y. Suppose P (1))) = and P (1) = b. Consider any pair of items I E Ru: y/ E R2 respectively. Therefore, for x E R2 this must mean that Paz 2 a 4 (note that (1) J E R.). For y E Re must similarly have Pey 2 b 4 Since u, connected by an edge, we must have Puz 2 a 84++1 and Pay 2 8A4+1. Now, we have P vz: implying that b
P (1))
e+:: hence
Pux - Puy. S P (1) (1)RR
Pay S a - (b- 81++1) & 16A
similar analysis for shows that Pay -Pn S 1 This completes the proof of the lemma.
Lemma 13. Condition the events g( el0) being true. Consider nice subset of users M
M and their corresponding set of active items NPte. for which guarantees in eq. 11 holds. Fix any subset y C C Consider two users u, v E M having a path of length the graph
glt..) Conditioned on the events ()) Ee
we must have
max RER MyER, and
PuR - P uyy S 8(L + 1)4e+1
max ZER S D'EER!
IPEz Poyl S 8(L++ 1)4
Proof. Recall from the construction of g(t.) that conditioned on Eg users u, v E M(si) have an edge if 1 p S 24 (and therefore |Paz - P S 4A for all E M(t..) Again,
for simplicity of notation, let denote Ryy be the set R( y.. Suppose P (1) P (1))) = b. Consider any pair of items E Ru, E Rr respectively. Therefore, for E R this must mean that P uz 2 4A541. For y E Ry, we must similarly have Pay 2 4 Since u, U are connected by an path of length L (say 01,02,.... A(L-1)), we must have Paiæ 2 a 8A,+1, Pay Payz 2 a 12A and finally Poz 2 444(L + 1)A+++ By a similar analysis 4(L + 1)
and
P ayy 2 b 4(L + 1) Now, we have P (1)D P Paz implying that b
hence
P Pwr
Pay ay < P (1)RR.) - Pay S a a- (b- 4(L + 1)4x+1) S 8(L 1)4
Again, similar analysis for shows that P. Puy - Pux S 8(L 1)A4+1. This completes the proof of the lemma.
Corollary 2. Condition the events el0) e0 being true. Consider nice subset of users M(ED) M and their corresponding set of active items N(E,,) for which guarantees in eq. 11 holds. Fix any subset & C ((,),, Consider two users u, v E (L..) having a path in the graph G
T.) Conditioned
on the events EL (()) we must have
max D
Paz - P Puyl S 16CA and
max zER! ! P.DER!OD
P - P S 16CA
!"
Proof. The proof follows from the fact that any two users u, V E ( connected via a path must have shortest path of length at most 2C conditioned on the events Eg e This is because, from Lemma [3] we know that users the same cluster form a clique and since there are at most clusters, the shortest path must be of length at most 1
Hence, for particular set of users M(E,) MM consider the jth connected component of G((.)) comprising of users (((ii.) If we consider the union of items S My | for any subset y [ then from Corollary we must have that for any user E M(tii.))
max 2
P NSP Puyl S 16CA
(15)
This follows from the fact that every element E S must exist in R(() | for some E ((t.))); moreover, v connected and therefore the shortest path joining them must be of length at most 2C - 1. Finally we use Corollary 2 to conclude equation 15
28

---

Lemma 14. Condition the events 8 e being true. Consider nice subset of users M E
M)(e) and their corresponding set of active items N( for which guarantees in eq. 11 holds. Consider the jth connected component of the graph g comprising of users M Let N ((.))
Met.n) T denote the union of good items for users in M(t...) In that case,
1. For every user u E MM the items Tu(s) INNOOQu for [TB 00
Miea must
belong to the set N(G6) Le. the golden items that have not been chosen for recommendation to users in M((dd) in exploit components of previous phases must belong to the surviving set of items NiEAs),
2. For any subset y CN(ee))) and any 8 S 13%, we must have the following for any A >
I (1)D - P (.)( 2 A for some u E M
then P (I)D())D - P (mm()s)
2 P (o))(1)) - P (.) 4 e+1 2 A (2C 1)4De+1 for all v E M
Proof. The proof of the first part follows directly from Lemma 11 where we showed that for particular user u E MM(,), the items P ar. (H))N))
for s E TB - -l Min. must belong to
the set Tal) (and the fact that A((e..)) 2 T
We move on to the proof of the second part of the lemma. Recall that any two users u, v E M((aa have edge in the graph (((.)) if
(()) uu
P 224++ for all E A((()) In that case, we have
Poi. P
P P Poin(D)) - (o).())
P (1)
P (F) 4A A 4
We are going to prove the Lemma statement by induction on length of the shortest path joining the users u, The base case (when the path length is 1 i.c. u, joined by edge) is proved above. Suppose the statement is true when length of the shortest path is L- - 1. In that case, we have the following set of incqualities (suppose is the neighbor of and the length of the shortest path joining u. w is L 1)
P DR. (1)D - P P.R 2 (1)D) P PA (
(1) P (w)y 4LA,+1 2 A 4LA
The lemma statement follows from the fact that the length of the shortest path between users v in the same connected component at most 2C This completes the proof of the lemma.
Partition of ( in phase L + 1 into nice subsets of users and their corresponding active subsets of items: Consider a nice set of users Mff.i) at the end of the explore component of phase f i.e. the start of the subsequent phase l + for the users in (E,,) At this point, conditioned on e(
events Ele) Eg our goal is to further partition the users in (f.a) into more nuanced nice subsets.
Suppose the number of rounds at least 1/3 /B = 1/33 implying that the active set of items A((e,)) is of size at least ((13/3 (induction assumption property B). Suppose, we index the connected components of the graph ((t,.) formed by the users in ( E AM((), Now, for each index j. the set of users corresponding to the 5th connected component of the graph (g(E.)) forms the jth nice subset of users (Lemma 7 stemming from users in ( E EM())) let us denote this set of users by (1+11.2) for some index > For this set of users ((++1,2) at the start of the exploit component of phase E + 1 (round (), we define the active set of items (((11.)) to be UNEM(eILLe) T.( Hence _A( _ forms the family of nice sets of users (that progress to the (e 1)th phase) and their corresponding active set of items at the beginning (exploit component) of phase é + 1 for users stemming from Mr Next, we discuss our recommendation strategy for ((+11,)) (a nice subset of users) in the exploit component of phase + 1.
{(M 1,=),
29

---

Strategy in exploit component of phase + 1: Note that in the exploit component of phase E + 1 for users in ((&AJ) = ((+1,2) (new notation indicating that M((x)) = M is a nice subset of users at phase L ++ 1) for some indices i, and 2, we follow a recursive approach to identify and recommend items (m=(())]r for all users u E M( At the beginning of the exploit component of phase e + 1 (say round t), we will also initialize O(t+1.)) to be the set of items o M(c.a) (i.e. the golden items that have been chosen for recommendation in the exploit components of previous phases (1 E) to users (f and recommended sufficiently enough number of times to be blocked). At start of the exploit component of phase e ++1 (round f), recall that the active set of items is given by A((++1,,,)) = UueM(eL.s) Ti( We reiterate here that corresponds the index of the starting round in the exploit component phase + 1 for users in the nice subset M(++1,2))
Let us denote TB -
O | and y -N(e-114,)) First of all, note that from Lemma 14
M for r E [s] must belong to the set y i.e. the best s items among those that are not in the set Ol++1.) we look two possibilities:
for all users u E M 11+1,, the items (r) [N] olet1))
must survive in Y' (Lemma 14). Now,
M(++1.))
1. (Possibility A): For all users u E M((+1,,),, we have that P (1))))))) (a)) I 64CA In that case, we stop the exploit component of phase É + 1 and move on to the explore component of phase e + 1 for users in MM++1,=) and active items V. Conditioned on events e(()) el)) in Lemma 15 we show that the above condition implies for every user u E -M(++1,2), must have
max S 88CAA+1. z.EEY
Furthermore, for Z = NN] (E+1)) M it must happen that y 2 { (s)
|
T/B- (o(t11) M((+1.=) for every user E M((+1.2) In other words, for each user (++1,es) the set y must contain all the top golden items ( ( (TT(T))TTTT that were not recommended in the exploit components far.
3),=1
2. (Possibility B): For some user E _M(+1. we have that P Pu
(s)ly 2 64CAz+1. In that case, from Lemma 14 we know that for every user v E MM(+1,=) we must have P ( P
(s) 2 36CA In that case, if we consider the set of items
S = Uu R((0) | },, then from Lemma 13 (or see eq. 15
must have that for
every user u E M(e+1..)
max P ux P Puyl 2,EES
S 16CAet1
(16)
For every user u E (F+1,,; recall that in Lemma 11 we showed that (1) | 1 R!
y' and Lemma 14 we showed that TT(1) 1 TI( | [N \ otttee) Hence,
(1) y = n. (1) [N
Ma-1.. belongs to the set S for every user u E (E+1.=))
Hence we must have that the items S is subset of (TT(r) [N] \ olf+1.)) } )) we index the items in S. For each of the subsequent (S] rounds (indexed by E [BS)), for every user u E ((+11,2) we go to the [b/BB] item S and recommend to user unblocked. On the other hand, if the [b/ BB item in S is blocked (or becomes blocked) for the user
Suppose
(2+1,2) then we simply recommend any unblocked item in ((+1....) This is always possible because we will prove via induction (see Lemma 15 and in particular eq. 23 that every round in the exploit component of phase L 1, the number of unblocked
items for any user u ((++1,2) in the set A 1,t,2) (where is the previous decision
round for M((+1a) on whether possibility A or B is true) is always larger than the number
30

---

of remaining rounds. We make the following updates:
((4111+111) Mitti,)) US
(17)
Mu+im
M((+11115) t ( \
(e+1,+)))) M((11.)
(18)
1 1 and y (((+12)))
(19)
ie update the set O by taking union with the set of [S] identified items in (Tu (4)]4==1 for users u E M((+1.s), After these S| rounds, for the set of users M(++1,s), the set of active items. A/(++1...)) pruned by removing the items in S and the time index is increased from i to f + [8].
At this point, we repeat the same process again for users in M(++1,=) with the pruned set of active items .V(++1,,,.) i.e. we check for possibility A or possibility B. If we encounter possibility B, then we again find the set of items S Uug.Meets, R (0) 1 and recommended it to all users in M in |S] steps as outlined above. We do this step recursively until we encounter Step for the users in M and at that point we exit the exploit component of phase f and enter the explore component of phase & + 1.
As before, at the beginning of the explore component of phase + 1 for the nice subset of users (6+11,2) let us denote the set of active items by A/f++1,2) and the set of items considered for recommendation in the exploit phases including the (L + 1)th one by (M(--1.s) (i.e. we remove the t in the superscript for simplicity). Therefore, the end of the explore component of phase é 1 for the nice subset of users (f++I.=), the set of active items A((++1,)) satisfy the following:
Lemma 15. Consider a nice subset of users M((+1,=) and their corresponding set of active items A(t+1..2) the end of the exploit stage of phase e+ 1.e. for all users E M(t+1.z) we have
P WF (L)AATC11)))) - -PuR.iiiea-- (s))Wtii)))))
I 64CAs+1 for s = TB - M
Suppose ((++1,2)
comprised of the users in connected component of the graph g(t.5) which in turn is formed by the users in M for which guarantees in eq. 11 holds true i.e. we condition on the events c(f) , being true. In that case, must have that
1. for all users u E M(++1.2)
MAx (C
P
P Payl S 88CA++1
i.e. the best and worst items in the set 1(+1,, for any user E M(+1.,) has close rewards.
2. Denote Z = [N] \ Mu-Laa) to be set of items not chosen for recommendation to users in ((++1,2) the exploit component of phases until (and including) phase e (+ Then it must happen that
(441)) Mit+1,s) S (T)
(20)
TB -o---)
\(et11))
2
U NEMM+11.)
(mx(()
2)p=1 miittt)))
(21)
Proof. Suppose at the end the explore component of phase e, M(E+1,2) C M(E.) We will prove more general statement. Consider the rounds (,, l2.... at which we check for possibility A or possibility B (this includes the starting and ending rounds of the exploit component of phase 11) At oltt) ) (((e)
any such round t,, for all users 1,)1,,2 must have that (TB ((++1.8)))) and
max =.y)A(++1,,.)))
P Puz
P
Puyl=
5
max 1EM((+1))
(i (P (IF ( (M))((CH))))))) +4CA441
(22)
((t+lder))) 2
U (Tm(1') 2) where 2= [N] ( ((+1..))
(23)
1EM(++1)))
olttbiee) M((-1a) C (T) TB-1
(24)
31

---

for = =T= T We will prove the statement above via induction on the recursions performed in the exploit component of the phase e + 1. For the base case, we consider the round 4 which corresponds to the beginning of the exploit component phase + 1. At this round, recall that 0 Mes. for every user (((+1..)
M
A((+1d))))) uweMict...)) Tu. Of course, with TT
we must have (r) J Fr=1 T (Lemma 11p and since A((+11,) is union of the sets T, (r) [V(e.)) (r( M(+11.2) for all E [s]. Hence by invoking Lemma (in the statement of Lemma we have J Φ i.c. y = A((+11.)) and (s) | | = (s(s) ((+11=)) (f.)). ), we obtain the statement of the Lemma for round tj.
for T
Mita)
Suppose the induction statement is true for round la and the second possibility i.e. possibility B became true. In that case, do not exit the recursion and goal is to show that the lemma statement is true at the next decision round ta+1. The induction hypothesis implies that for every
user u E M(++1a), we have that Tu (TB 1-1--00
-0 Mic. ) survives in the set of items (ff+1.
and furthermore, we have (TB - 10
|
| Tu(s) | for s = TB
Mec.a
(e+1,))) (note that s is common for all users in M(++1=)) The induction hypothesis also implies M that
2 U
{tu(t) 3)²-1 where Z = [N] \ M(++i.) and = T -1O16tLtt))
M(++1.5)
MEMiCHa))
(25)
((41.6))) S (T) M(+1.1)
TB-
(26)
Again, at the decision round las since the possibility B was true, for one of the users u E ((+1,2)
we must have for s T o 1000 1.fo4t)
M((-1.))
P (1)
un. (O)A 64CAe+1
implying that for every user v E (((11,2) have
P PoR. (D)W - (() 2 56CAA41
The above equation further implies that (Lemma 8). for every user v E M(++1,s), we will have
Pur. (1))W - -P (i 2 50CA
Hence, as mentioned before, if we consider the set of items S = UnE R | then from Lemma 13 (or see eq. 15). we must have that for every user E M(e_1,)), T TT(1) (((+I.da::)) E S and
max WES
P
umu (1) -P Puyll S &16AA+1-
(27)
Hence, if we remove the set S to update (((++)ta ie. ((e+)ifa4s1n) + A((++iaane) \ S, for every user ((+11,2), we must have
(TB - 1010 Mrc. ) (
(T -lo(ett0)) 1) (
TT (TB Miterne
This is because for each user u, only elements which have larger rewards than (TB MicH1.a) ) | (((++1.a))))) are removed which makes the aforementioned item survive in
M(ll1.)) ((++1.te- and also moves its position up (recall that ((411f411) + (ff11e)) U in the
list of surviving items sorted in decreasing order by expected reward. Hence, can apply Lemma
32

---

g
to conclude the first part of the induction proof. In order to show the final statement, with
olette) TB
Ma-tin we can simply substitute that
(P (PoR.(1)A (o.. 64CAc+1 vEM((++..)
max
when possibility A became true decision round f, and we exit the exploir component to enter the explore component of phase e for users in (
Moreover, we will also have that
S _ (Tu(r) [ pi where s = TB -1
Mct+1.s)
(28)
(et221f)) Mict1.)) and s = (
S S (T)( 23/==1 where == [N]
Mit+1.a)
(29)
SC (Tu(1))
TB)
TB-
(30)
N((thee-11))) 2
U (Tu(tt)
3/==1 TB-1-s
(31)
NEMilLa
where 2 [N]
(ethaa))) Meila L.) and 8 =
/ Miell.x)
(32)
This first implication is due to induction hypothesis (see eq 25) which implies that the best
items in the smaller set A((+), is same the best 8 TB
O
(f+112) items in the
Metil.)
larger set [N] \
((t1) Mi++1ay Hence, it is evident that the set S must also be a subset of the best TB- items (golden items) for user namely {Tu(4) Since the above facts are true for all users E (M(+1,,) we can also conclude that the new pruned set of items A1((+1,t++ at the next decision round fa+1 is a superset of the best TB ((t1iaa)))) items for every user u. This Mit+1.s)
completes the second part of the induction proof.
dl) c with choice of Det1 /88C, conditions A-C Lemma 16. Conditioned the events Eg will be satisfied at the beginning of the explore component of phase for the different nice subsets e(++1) (M()+1,)) and their corresponding set of active arms (N(e-1,2)) implying that the event El will be true.
Proof.
1. Proof of condition A: Due our induction hypothesis, condition A is true for the explore component of phase f. Hence, the explore component of phase E is implemented separately and asynchronously for each disjoint nice subset of users ((E.i) E A C ((()) (recall that M corresponds to the nice subsets of users which do not fall into the edge case scenarios). Let us fix one such nice subset of users ((f.) M After the successful low rank matrix completion step (event e(f) is true), we find the connected components of graph ((f.i) which in turn correspond to nice subsets of users as well (see Lemma 7 Since the above facts are true for all nice subsets of users in M)(() the nice subsets of users that progress to the (E + 1)th phase are disjoint. Since these set of users are not modified during
the exploit component of phase l + 1, condition A is true at the beginning of the explore component of phase ++1 1.
2. Proof of conditions B and C: Again, let fix subset of nice users ((+1,,s that has progressed to phase E + 1 and was in turn part of the nice subset of users M ( in phase f. In other words, the set of users M (1+1,,2) corresponds to a connected component of the
graph (f..)) From Lemma 15 we can conclude that conditions B and C are true at the beginning of the explore component of phase f. + for users in M((+1,,) with choice of A++1 64+1/ f411/88C /8SC where 6 was pre-determined. Therefore, the conditions B and C hold for all nice subsets of users {M((+1.2) that have progressed to phase ++
Hence, conditioned on the events El (()) with choice of A C+1//88C the algorithm will be
(Ee+1,& E + -)-good and the event Eg
((+1) will be true.
33

---

D.2 Analyzing the regret guarantee
Lemma 17. Consider a fixed decreasing sequence {<e)e21 where 61 | and et C²2-'min min |IP|l0o
oyP logN) for E > 1 for some constant C' O. Let us denote the event
= dl Ne E to imply that our algorithm (ce, -o--goooo at all phases indexed by l and the explore components of all phases are successful with the length of the explore component of phase f being
0 log(M VN) my m²= 00
max (1.M) log T))
NT
The above statement implies that for any nice subset of users M that has progressed to the hth phase with active items NCC,5) at the beginning of the explore components, with my rounds, we can compute an estimate P MMe.9,,re of P Mii., satisfying
M - P PICEo S A
In that case, the event & is true with probability at least 1 CT-
Proof. Notice that
Pr(8)) =1 - 11 el0e
U
2 (Pr(e + Pr(et E(()
Pr n nE ne + Pr(ef
|
elfe
n (E nE(
e't
ECt
2 (Pr(E + Pr(E E(Ti))
Pr
(f)
cfe-!) el-1))) + Pr(Ef E(7)) 21 1
where we used the following facts 1) Pr(e 0 and Pr(effte E (e-"),gf-))) 1) 0 for all E (Lemma 16 2) Pr(c) E CT implied from Lemma with additional union bounds over the number of phases (at most the number of rounds T) and the number of disjoint nice subsets of users that have progressed in each phase (at most the number of clusters C). An important fact to keep in mind is that the above analysis is possible since the observations used compute estimates are never repeated in Alg. 2 and we are able to avoid complex dependencies.
Now, we are ready to prove our main regret bound. Suppose we condition on the event & as defined the event ε, let denote by Pa be some sequence of items
in Lemma 17 Conditioned recommended to the user E [M] by our algorithm. The probability of this sequence of items being recommended is Pr(Nue[Mip E)
D.2.1 Swapping argument
Let us fix a particular user E [M] and sequence of recommended items Pa such that Pa(() [N] the item recommended to user u at round l.. For sake analysis, we will construct permutation 0,, [T] {pa(( ((.)()) of the items (Pa(())x((T) with sequential modifications (0,, is initialized with Pa). For any phase indexed by f, consider the exploit and explore components for a nice subset of users ((e.), The sequence of items recommended user during the explore component remain unchanged i.e. for any phase f, (t) (t( for all rounds t E [t] such that t corresponds to the explore component of phase E for the user u.
Now, for the exploit component in phase recall that O Mer \ (o(r)) Mir.s) is the set of items chosen for recommendation particularly in the exploit component of phase E (we remove the super-script t since we refer to the end the exploit components in phase and phase & 1 respectively). Suppose
Mi.. \ (((-1) was chosen at round in the explore component of phase E, the 5th item in the set (e))
34

---

to be recommended to all users in (M but was found to be blocked for user E M before it could be recommended B times. Let us also denote A be set of active items for users in ((C.)) at round i (i.e. la was the previous decision round where it was decided whether possibility or possibility B was true). Since the 6th item in the set O(1) Min0 \ ( was blocked for user u, instead we recommend any unblocked item for user u from the current set of active items A This is always possible; we showed in Lemma 15 (see eq. contain sufficient unblocked items for possible recommendations for remaining rounds for any user in the corresponding nice subset of users during the exploit component. Now there are two possibilities:
23 that the active set of items always
1. (bth item in the set (
Mit.s) was recommended in round t' in the explore component of previous phase ) We consider the active set of items A(EE (such that u E MM .k) in phase f') where L' < f is the phase index (and t' is the round index) when the 6th item in O(f)
MiL..) AOMA,,
MMCE.)) \ O (say a) was recommended to the user u during the explore component. Let us denote the item that we have recommended as replacement to user u at round i by a'. Note that since a' E AN(66.)) it must happen that a' E &N(EE,M
(h) since (((.ta.)) S N' M))
In that case, we have
(t) = a' and Pu(t') We swap the above items so that in the modified sequence, we have
(t) = a and (t') = a'
The goal of the swapping operation at round t in the exploit component is to modify the sequence of items such that 1) the item a chosen for recommendation at round is assigned to round t in the exploit component 2) the item a actually recommended in round t' < t and phase l' f is replaced by another item a' (actually recommended at round t >> t' in phase f >> E') such that both a, a' belongs to the same set of active items A/te' A) (u E MM h) for some h). We will also say that the item a chosen for recommendation is replaced by swapping operation of length 1. This is because the chosen element for recommendation a was recommended in the explore component of a previous phase. A more precise definition of the length of a swapping operation is provided below.
Mitio 2. (bth item in the ser Oli) (o(tt)) was recommended in the exploit component of previous phase): This is the more difficult case. As before, let us denote the 8th item in the set 0
Mitas) by a. Of course, the item a could not have been chosen for recom- mendation in the exploit component of previous phase (i.e. cannot belong in the set Me \ Mi for any E' < E with u E MM(' .) in phase f'.) In that case, the item a was recommended in the exploit component of phase E as part of a swapping operation. With this intuition in mind, let us define length of a swapping operation precisely:
\ Muee.,,
Definition 3 (Length of swapping operation). For a user u, suppose ai E Eolt) Mies \ (ott-1) Mila
is item chosen for recommendation in the exploit component of phase E but found to be blocked. In that case, we will say that d1 is replaced by a swapping operation of length L+1 I
if there exists L+ 1 items a1, 02..... OL, aL+1, L + 1 phases p1 > P2 > and respective rounds t1, t2..... .,. tL. fL+1 such that 1) a1 is chosen for recommendation in exploit component of phase pı at round ti 2) for each 2 S i L. 0;-1 has been recommended in the exploit component of phase pi at round 1, when the intended item chosen for recommendation was a; 3) ay has been recommended in the explore component of phase PL+1 at round 1L+1 3) aL+1 is the item recommended to user u in place of an in phase pl at round t1.
PL >> PL+1
As before, aL+1 belongs to current set of active items Alt,tt..)) at round tj for users in ((,.) (recall that la is the decision round just prior to L1). In the above definition, note that L must be finite since there are finite number of components and the first phase only has an explore component (recall that exploit component in the first phase has zero rounds).
For user u E (f.i), suppose an E o(0)
Muss \ (f--)) is an item chosen for recommen- dation in the exploit component of phase but found to be blocked. Moreover suppose a1 must be replaced by a swapping operation of length L (see Definition for notations). In that case, we make the following modifications to the permutation 0,:
(t,) a, for all 1 S i L+
35

---

hee[T] Lemma 18. Condition on the event E. Consider the modified sequence of distinct items (Qu(t) [tu(t))eT) for a certain fixed user u. For any phase i to which the user u has progressed as part of the nice subset Mita), consider the exploit component starting from round index texplcit,start.f to lexploit,ends In that case, the set of elements (0,(1) t E //explait,start.tt lexplait.end,e]] is equivalent to the set of elements (()) (O(6e
MM Mit.9 repeated B times i.e. the golden items chosen for recommendation in the exploit component of phase to users in M(t.i) Similarly, consider the explore component starting from round index start, 1o end, In that case, for any 1 E (explore.start, En Lexpploreeend ond.tly ,) it must happen that (t(t)= E NN(... i.e. the set of active items for M during the explore component of phase f.
Proof. We start with the following claim.
Claim 1. For a user u E &M suppose an E Og \ S
Mas.) is an item chosen for recommen- dation in the exploit component of phase at round t but found to be blocked for user u. Moreover suppose an has been replaced by a swapping operation of length L+ 1 (see refinitionnsfr notations). In that case, we already have (I.(1.) = 0; for all S S We only need to modify the sequence by making the following two chunges: 1) 0,(4) d1 2) (1((++)) UL+11 Note that in the true sequence, aL+1 has been recommended in the round 1 replacing the intended item a1
Proof. We will prove the claim via induction. Notation-wisee suppose for any E' I é, the user u belongs to the set MM(e' and the set of active items at round & for users in M is denote by / (for simplicity, we remove the superscripts). The base case for the item ai is recommended in the explore component of phase p2 at round l2. We find an unblocked item 02 in the set set N S A(...) (note that items are never added to the active set across phases and only pruned), recommend at round t according to our algorithm. For analysis, we modify
is true by construction here
(ta) = 01 and (. = 02
Now, suppose our claim true for some L = I. Now, for L = 1 + 1, note that (1 was recommended in the exploit component of phase P2 at round i2;; this implies that @1 must have been used to replace another item 02 via swapping operation of length 1. By our induction hypothesis, we must have 0, (t,) = for all 2 I i < L (as a matter of fact, we will have 6,, (+++1) = a,). Therefore, only the pair of modifications (41) = aj and (x((+++)) = a++I suffice to bring the desired changes in O..
We can also conclude from Claim T that 1) any round in the exploit component of some phase for user u, if the chosen item to be recommended is found to be blocked, then that chosen item is brought the 8th position in the sequence 0. 2) Once the chosen item is brought to its correct position in 0.. it will not be modified/moved in any future round. 3) All chosen items for recommendation to user corresponding to exploit components are moved to their correct position (i.e. the intended round for their recommendation) in the sequence 0g. Next we make the following claim:
Claim 2. Consider the setting in Claim 7 It must happen that all the items a1, 02 .g...., aL+1 must belong to the set ((PL+1.)) the set of active items in the phase PL-1 for users in the nice subset (() to which u belongs and ag was recommended in its explore component.
Proof. Again, note that items are never added the active set across phases and only pruned. If an item ai is replaced by aL+I via swapping operation of length L + 1, it implies that aj was used to replace item 02 (via a swapping operation of length L), a2 was used to replace ag (via swapping operation of length L - 1) and so on. The final golden item for user u in this sequence a was recommended in phase PL+1 the explore component and belonged to the set of active items
() Hence, this implies that all the subsequent surviving items a1 022 a3......... aL-1, 0L+1 must have belonged to the set of active items ((PL)..)) as well.
From Claim 2 we can conclude that for any round / in the explore component of some phase e for user u, if Pu (7) is replaced in the sequence 0,, at round I, then p.. (4), (t) belong to the same set of active items (e,0) With both these arguments, complete the proof of the lemma.
D
36

---

D.2.2 Final Regret analysis
Let us condition on the event &. Consider any user u E [M] recall that (Pu(t) is the random variable denoting the sequence of T items recommended to the user u, Pu(() is a realization of (E))) conditioned on the event Furthermore, 9g is the modified sequence a permutation of the T items {Pu(t)} recommended for user For simplicity of notation, we will assume that M(C))) for every phase É. Hence the active set of items during the explore component of phase L for the nice subset of users (M...) is denoted by ArCC.) Also, in line with previous usage of notations, let us denote (
O((-1) M MMt,a) to be the set of items chosen for recommendation particularly in the exploit component of phase f. Moreover, O denotes the entire set of items chosen for recommendation in all the exploit components to user u. other words, & is the final phase to
which user u has progressed then O2 ((fa)) M( We denote the regret for the user u by
Reg.. (T) 3 -= E
[
Σ
P (a)m(() -Pupatt))
[E[T]
where the expectation is over the randomness in the algorithm and the noise in the observations.
Note that with this notation, we have Reg(T) (T) | = M EVEiM Reg.. E. We now have the
following set of inequalities for regret of user W:
Reg,. (T) & E
Σ
P (t)a(t) P Pupa.ce)
1 E = IE
Σ TET
P (1)
P Pupices) |8)
BE[T]
Σ Pr(pu(t) = Pa((t) [8)
Σ
P (s) - P (t)
(w())
[E|T]
Σ (r(p.(t)=pa(()) = (8)
Σ (E[T]
P umT(()) - P u0)
(=(t)
Let us denote the of rounds in the exploit component of gth phase by exploit(e, (M. and the
explore component of gth phase by explore(E, M(t..)) Therefore we can further decompose the regret for user w as follows:
Regu (T)
Σ Pr(pa(t) =P((t) (8)
Σ
Σ
(Pus.(() P Pwo.(())
((())
EE(e..) 1Eexploit((.MMMM....
Σ
Σ
(Pusr(()) P Puo.co))
RE[T..] (Eex)lore(..M(0.0)
Next, our arguments are conditioned on the event & and any sequence Pa (t) having a non-zero probability of appearing conditioned on event E. Recall in Lemma 15 we proved by induction that O. S {Tt(())TTT Moreover, in Lemma 18 we proved that items chosen for recommendation in the exploit components for user are in their correct positions (i.e. the round when they were intended to be recommended but might have been found to blocked) in the sequence 0g. Consider permutation of the best T items for user on [T] + ((T( such that
ou (4) = (t) for all t E ( ((.6))
= (()) On.
where in round in any exploit component, the permutation maps the item chosen for recom- mendation (which we know to be among the best T items) for user that round. For any round belonging to the explore component, the permutation arbitrarily maps the remaining items among the best T items (namely the set { (t'))em \ O.). Notice that EieTT Therefore, we can further decompose the regret as
P Puna(t) = >iETT P Puou(t)- (t).
Reg.. (T) 1
Σ
(r(p.(() pm(()) (E
Σ RETe.. (EEeploit((.MM(...)
Σ
(P Puor,()) - P PuO_(t))
Pa(()
+ Σ
Σ
(P (Pouu()) - P Pw)_(t))
tE[T.) MEexplore(E.MM(.)
Σ (r(p.(() pn(()) (8)
Σ
Σ
(P (Puos(0) - -P Puε.(0))
Pa())
RE|T. (Eexplore((,,MM
37

---

For the explore component in the phase indexed by L, we have proved in Lemma 14 that the active set of items ( is superset of { hee Ou. Therefore, we can bound (using Lemma 4 and condition C stated at beginning of sec. D.I for any + tu (L,, denotes index of the final phase that user u was part of)
Σ
(P (Puon(()) -Pui (i) S m ce - 0 0
Tr log(M max (1,
Nr M
log T)) ce.
(Eexplore(,.MMC..) where zi is the incoherence factor of the sub-matrix P. PMICO, .N Next, using the facts that De+1 6g+1 /88C,88 2eg = 68+1, C, T (1), we get that (after hiding log factors for simplicity)
(Puna(t) P uā. (1) 0 pr
max (1. )) =
Ō( (0 2r max (1, M)
N
Σ
EE
EE
(Eexplore(E.M
In the above statement, from Lemmas 2 and we also used the fact that jı O(μ) and the condition number of the sub-matrix P (MC..)) ( O(1). Finally, for the explore component of the final we will also have (in the final phase, one of the edge case scenarios might
phase Lu, from Lemma 11 appear)
Σ
( Puou(() - P (1) = - (au max (VT.
) M
+
0
00ppp F
max
1, M
(Eexplore(E.MMte.
Hence, we can put together everything to conclude that
Σ
Σ
Puon(()) - Paii Po).(t))
RE
(.C.xplor((..MMc...
Σ
021
max
(1,
N
Ō
T2 (112112 max (VT.
Ee
M
M
δ p2p
max (I. N + Ō (on max (VT.
T M
m&
Ber20
0²
o
N M) + 0 0 max (VT.
T2
T2.
T T + J.
max
1
M
=1 o²pe max (1,M) we can bound
where J is the number of phases with Eg 2 tb By choosing $-
Σ
Σ
(Pro_(t)- P Po...o) = (Joopa
T max (1. N
RE|C.] (EE)))
where we used the fact that N > T and therefore the last term in the previous equation is a lower order term compared the first two ones. Next, recall that we choose 6g C²2-t min (IPPlloo T (so that the condition
log 0 in Lemma is automatically satisfied for all E) for some constant C" > 0, the maximum number phases for which 6e > ob can be bounded from above by [PP]
= o (1gg log + min
ov/ ))) Therefore, we can hide J inside Ō and obtain Tog
Σ RETéVl tEexplore(E.MMGG..))
Σ
(P (Pudy(1) - P Pu)_(()) ((11//2 V Tmmx (1, N ))
Therefore, must have that
Reg., (T) 000 Tmax (1, N )) Reg (T) 1==00 000001 T max (1, N
))
Finally, we use the fact that
< Reg( T) E Pr(EP (Reg(T) E*). From Lemma 17 we know that Pr(E3) < - Reg( T) | - < T| therefore,
Reg
Reg(T) (T) Reg(T) E Pr(E")(Reg())) (*) δ (11212 max (1, MM
N
+ +T
which completes the proof of our main result.
38

---

at round I. E Proof of Lower Bound (Theorem 2
Consider problem setting with M users, N items and T rounds, blocking constraint B, noise variance proxy o² = 1 and all expected rewards in [0, 1]. Here we consider C = 1 i.c. all users belong the same cluster. Let us denote particular policy chosen by the recommendation system as π that belongs to the class of polices II. Moreover, let us also denote by & the set of possible environments corresponding the expected reward matrices that has all rows be same (satisfies cluster structure for C = 1). In that case, the minimax regret is given by
inf sup (eg(T:: xell
E.1 Lower Bound via reduction
We can ease the problem by assuming that at each round = ..,,..., T, the users come a sequential fashion - the 1th user is recommended an item based on all previous history of observations including the feedback obtained from recommending items from users 1.2.....5 Furthermore, also assume that the N items can be partitioned into NB/ TT known groups where each group has identical items- hence we have a simple multi-armed bandit problem (MAB) with NB/T TB arms and MT rounds with single user. A lower bound on this simplified MAB problem will imply lower bound on our setting i.e by appropriately normalizing, we have
inf sup Reg( T) 2 #Ell FEE
inf sup RegMAB (MT; = S2 M well wer
NB T
MT) = Ω
NB M
M
where we simply used the standard regret lower bound in multi-armed bandits with K arms and T rounds which is ((VKT)
[1
E.2 Lower Bound via application of Fano's inequality
As before, we can ease the original problem by assuming that each round t 1, 2,..... come in sequential fashion the 1th user is recommended an item based on all previous history of observations including the feedback obtained from recommending items from users .. 11 at round t. Clearly, a lower bound on the simplified problem will imply a lower bound on our setting i.e by appropriately normalizing, we have
. T, the users
1
inf sup Reg(T;: 2 inf sup RegMAB (MT;E). #ell PEE
rell WEE
Furthermore, ignoring the normalizing factor by M, for C= 1, the simplified problem is equivalent a standard Multi-armed bandit (MAB) problem with a single agent with MT rounds and an additional hard constraint that each item can be pulled most MB times. We will construct (TB-1) environments in the following way: let T {S S [N] [S] TB TB-1} be the set of all subsets of [N] of size TB-1 Now for each subset S E T, we construct an environment by assuming that the agent on pulling any arm the S observes a random reward distributed according to ((A, 1) and on pulling any arm outside the set S observes random reward distributed according to (O 1). This corresponds
the the reward matrix (in our original problem) having an entry in the TB columns indexed in S and 0 in the remaining columns. Let Ess Es denote the expectation, probability measure and the environment if S E T is the set of chosen columns for constructing the environment.
Next we assume that the S is chosen uniformly random from T. Hence we must have RegMaB Es)
inf sup RegMAR (MT;)) ) 2 inf E hlll FEE
#ell
Fix any policy E II. Condition the set S being selected from T. Let R(S) be the number of times arms indexed the set are pulled the MT rounds. In that case we must have
RegMAB ET; Z Ps(R(S) < 3MT MTA
4
Now, consider the estimation problem of which set S was selected from T. Let X be an estimator that takes as input the observations in the MT rounds and returns set S in the following way: it
39

---

finds S as the set of T arms that have been pulled the most number of times jointly and returns S if R(S) 2 3MT/ 4 and the null set otherwise. We consider the estimator X to make an error if it returns set & such that Sns & T/4B. the estimator X makes an error, note that R(S) 3MT/4 /4 implics that R( S) 2 MT/2 (since each arm can be pulled at most M times) hence, it implies that R(S) - MT/ 22. Therefore, if we denote Error as the enror event, then must have MTA
3MT MTA
RegMAB (T: 2 (R)()(S) &
2 Psrrr)))))
4
MTA
MTA 4
inf sup RegMAB ( (MT:E) 2 P(Error) Tell vEE
ESTTPS (Error)
4
Therefore, goal is bound the quantity T At this point have reduced our problem to a multiple hypothesis testing problem. Therefore, in order to lower bound the probability of the event Error,
Fano's 's inequality for approximate recovery:
Lemma (Fano's inequality with approximate recovery (28)). For any random variables V, V on alphabets V, V, consider an error when d(V, V) 2 L foror some R. In that case, if we denote the error event by Error, we must have
0 and distance function d
P(Error) 21 I(V;V)+ + log2
log Gmax
VL
where Gmax max Even ldd(,, 6) 1] and I(V;V) is the mutual information between the random variables V and V.
In the special case when the random variable V is uniform, then we can upper bound the mutual information by I(V; V) I max,,sey v v S max,,sev KL(PPllPPr) where the second inequality follows from Data-procssiing inequality (Py = P(- v) corresponds to the probability of the observations given V = v).
Next, we apply it to our setting to prove an estimation error lower bound for our designed estimator X. In our setting, Grnxx corresponds to the maximum possible number of sets in T that have intersection of size more than /4B with some fixed set S E TT Clearly we have
N-T S T T- T/4B (t)
N
T T/4)
2Ne
T-
T-T/4B
T/4B
Gmax
Σ
S
T
4e
T
t=T/4B+1
Furthermore, in setting, also have that
(L(Ps|(Ps.) S,S'ET
max
Σ EsR((i)) max(KL(A((O)). 1)IN(A,)) 1)), KL(N(A, 1))) S 2MBTA RESUS'
this follows from the fact that the distributions Ps. Ps- are most separated in KL-DDiergencce S S' 0 and by using the fact that each arm be pulled at most MB times. Therefore, must have (provided N = cT for some large enough constant > 0, and T is large enough) for some constant d'
T(S: 9) log
2MBTA² 2 + log 2
P(Error) 2
2
log GRAN
log
(N/T)T T/46
7/48
(
4e
2 1 2MB2TA² 2 + log
2MBA
2 0.9
C'T (N/T)
c' log /N (T)
[oT( have that for some constant " 2
Therefore, substituting
A
BVM
inf sup RegMAR (MT:)) 2 d'TB-1 V (MlogNN/T) "lll,ee wEE
and therefore
inf sup Reg Reg(T;)) inf sup RegMAB (MT:E) = 22( ( (Vlogg(//T)
1
rell veE
M well DEE
BVM
40

---

Algorithm 7 BBUIC (Blocked Latent Bandits with User and Item Clusters)
Require: Phase index L, List of disjoint nice subsets of users M list of corresponding subsets of active items A clusters C, rounds T, noise o² O, round index to. exploit rounds exploit estimate of P, incoherence μa, entry-wise error guarantee eg of restricted to all users in M(() and all items in A count matrix K NYMNN
1: for 7th nice subset of users M E M!! with active items A (ith set in list A(()) do
2: Set = lg- Set EC+1 = ee/2,, A = Es/8SC and A =f+1/88C.
3: Run exploit component for users in M((..) with active items N,te,., Obtain
updated active set of items, round index and exploit rounds A/(c. lexpliit Exploit Itemmmmmmm...ee..... ltte_lltetteeeeeeeeeeeee (lante_Cuser((M AA(()))) texploit P PM Mye,,, Ae). (, (A((C))), d2 = min min([MM (, and c( ooddn"oog for A2-1d2
4: Set di = max(I.M(6.))
some appropriate fixed constant e 0.
5:
if [ 2 T1/3 and < then
6: Run explore component for users in M(63) with active items A Obtain updated estimate and round index P,t t Explore ltem___te____ ltaealltte_eeteeeeeeeeeee Cluster(MM(..))) N160, t,p) such that
P MM. P (Miro
I Aet1 w.h.p.
For every user u E MM(e), compute T:( Li E A((.)) Pu Pnj S 2 Construct graph ((ei)) whose nodes are users in M(ed) and an edge exists between two users u, E M(C.) if (2 -P(0 < 2 for all arms x E ((C,,))
7:
8:
Intitialize lists M (((+1)== = [ and A((++) --
9:
10:
For each connected component M((i.) (U,M(ean) Mll.il), compute Ait.i.))
Tv.
For each connected component ((Gdd) construct graph (((,5.)) whose nodes are items
11:
in (((,.)) and an edge exists between two items u, u E A((.) ((0) (() I 16CAe+1
for all users E MM(i.,) Update N( to be the set of items NeL.)) = fxr (Ve,,) is connected with some node i))()..))).
Invoke B-LATTICE({ 1, ,N(e+1) C. fesploit: P. P, K, g((eh))
13: else
14: For each user u E M(L.), recommend unblocked items in A/C, until end rounds.
15: end if
16:
end for
F Blocked Bandits having User and Item Clusters with blocking constraint B B=
Recall that this setting, the N items can be grouped into C' disjoint clusters (11), D(2) .... DC') that are unknown. The expected reward for user u (belonging to cluster E [C] on being recom- mended item j (belonging to cluster b E (C') is Pij Qa where Q E RxC'' is the small core reward matrix (unknown). this setting, we provide our theoretical guarantees with B i.e. any item can be recommended to user only once under the blocking constraint.
Recall that the main reason our thcoretical analysis required B O(log T) for Thm. I setting is that if the observations that were used to compute estimates of some reward sub-matrix in a certain phase with certain guarantees that hold with some probability, then conditioning on such estimates with the said guarantees make the aforementioned observations dependent in analysis of future phases. In the BBIC setting, we show that in each phase, the possibility of the nice subsets of users and their corresponding active items is actually bounded and small. On the other hand, the possibilities were exponentially large in the number of items in the GBB setting. Therefore, we can use a for all argument here implying that for set of already used observations, we can show that for all possible nice subsets of users and their active items, they can be used again to compute acceptable estimates. Such an analysis allows to provide theoretical guarantees with B = 1 for the BBIC setting.
41

---

Algorithm 8 Stw.aott_tttetCClseeeeeepappppp Component of a phase)
Require:
Phase index E, nice subset users M, active items N,, round index to. estimate P of P and eπror guarantee A such that [P M..N' M.N 88CA, with high probability, similarity
graph Giem over the set of items N.
while there exists MM()))) such that P (.).(1) P u (T-foak))) Z 64CAe} do
2: Compute R. = E P (1)A 2 for every user E M. Compute
S UuE
3: Update 8 -- {u E gitem is connected with some node in S}.
4:
for rounds t = tu + +1, 1, + 2......tu to |S do
5:
for each user E M do
6:
Denote by x the (t to) item in S. If Kw == (z is unblocked), then recommend u and update K <- If Kur = 1 (x is blocked), recommend any unblocked item y in (i.e Kuy = 0) for the user u and update Kuy <-
7:
end for
8:
end for
9:
Update N 8. Update to to + +8)
10: end while
Return No
Algorithm 9 htarre__tttetccuuseeeepppppoo Component of phase)
Require: Phase index É, nice subset of users M, active items round index ty, sampling probability p.
1: For each tuple of indices (i.j) M W, independently set d.j with probability p and
6ij = 0 with probability
2: Denote Ω (( . x V 6. 1} and maxim 1í E W (i,5) 2 to be the maximum number of index tuples in a particular row. Initialize observations corresponding to indices in 52 be A
3: for rounds f = 4 + 1, 1, +,
do
4: for each
.M do
5: Find an item z in {j E N (u.j) E Ω2 buj = 13. If Kus == (z is unblocked), set
(t) and recommend
user u. Observe R (p)(() and update A (R (t)
upu (P)
Kas 1. 1. Kf = is blocked), recommend any unblocked item (t) in N s.t. (u, (t)) & Ω Update (t) + 1. Set A = AU (R (1)) was recommended to user u.
6:
(p where t' < t is the round when Pu (t')
7: end for
8: end for
9: Compute estimate p Estiimate(M,NN,,,..C C, A) and return P,40 + m.
Therefore in Algorithm 7 for the BBIC setting, we only have single counter matrix K E {0, 1] M which is binary. The matrix is initialized to be a zero matrix. Whenever an item j recommended to user i, we set K.; 1. If, in a future phase, we need to recommend item j to user again, due to the blocking constraint, we simply reuse the observation (see Step 6 in Alg.
F.1 Algorithm and Discussion
We start with definition for nice subsets of items analogous to the nice subset of users (see Definition D
Definition 4. A subset of items S C [N] will be called "nice" if USEA D(1) for some A C [C']. In other words, S can be represented as the union of some subset of clusters of items.
As in the analysis of GBB setting, will have the desirable properties A-C that should be satisfied with high probability at the beginning of the explore component of phase f. Recall that we defined the event e(() to be true if properties (A-C) are satisfied at the beginning of the explore component
42

---

of phase by the phased elimination algorithm. Here, we stipulate further property D that the corresponding surviving set of items for each nice subset of users M E MM()) is also a nice subset of items.
Furthermore, we defined the event E when eq. 10 is true for all nice subsets M E = in the explore component of phase f. Algorithm 7 is similar recursive algorithm as A Aggorithm| | and the
only modification the addition of Step 11. As Alg. we instantiate Alg. 7 with phase index
list of nice subsets of users having single element comprising all users i.c. M [M]] and corresponding list of active items A(I) [[N]] clusters C, rounds T, blocking constraint B, noise o², round index 1, exploit rounds O, estimate P to be OMxN, incoherence μ and 61 O || a /
log M
Here, we will have a single count matrix K which is binary and is initialized to be an all zero matrix. e())
properties A-D will be satisfied at We are going to show recursively that conditioned on e Eg
the beginning of phase f + 1.
Base Case: For l = 1 (the first phase), the number of rounds in the exploit component is zero and we start with the explore component. We initialize M(..) = [N], [M] and therefore, we have
max Puj min Puj jENU..)
Pl for all u E [M].
jEN(..)
Clearly, [M] is a nice subset of users, [N] is nice subset of items and finally for every user a [M], the best T/B items (golden items) {ITa (t)) belong to the entire set of items. Thus for & = 1, conditions A-D are satisfied the beginning of the explore component and therefore the event &
is true. Furthermore, from Lemma 4 eq. 10 is true for the first phase with probability 1 o 12)
implying that the event c(1) is true with high probability.
Inductive Argument: Suppose, at the beginning of the phase E, we condition on the events El c(i) Ni= eli) that Algorithm is (cood)-good for all I L. This means that conditions (A-D) are satisfied at the beginning of the explore component of all phases up to and including that of l for each reward sub-matrix (indexed by i (az)) corresponding to the users in (ff. and items in AM(e.)), Furthermore, we also condition on the event eq. (((3)) M( and their corresponding set of items Afte.)) implying that the event g is true. Recall that for user the set ( was constructed as
10 is true for all nice subsets of users
T:0 E Poj PoR,( 2 where s' TB-1 10)
(33)
Mic.
which implies that every item in T is close to one of the golden items in Att,,) At the end of Step 10 in Alg. 7 we can still show that Lemma 9 holds for each set of users (f,ii.)) as they form a connected component. Notice that in Step 11 Lemma 9 for each set of users M(E..,, we construct graph item whose nodes correspond to the items in (L.))) and edge exists between - (()) two items u, E ((C.)) if
am < 16CA4+1 for all users x E (M(...)) Analogous to the proof of Lemma] 7 we can conclude here as well that items in the same item cluster form a clique.
( au
Therefore, any connected component in the graph G!(e?)) must correspond since condition D true and AC(E.)) is already a nice subset of items. Hence the of modified items ((((,i))) constructed at the end of Step 11 in Alg. is nice subset of items. Furthermore, we can also prove the corresponding version of Lemma
nice subset of items
Lemma 19. Condition on the events E, ; e(() being true. Consider a nice subset of users ((6ad)
and their corresponding set of active items ((t.i.)) for which guarantees in eq. 11 holds. Fix any set
y A((..)))) I for some I such that for every user u E 9, we have Tu(ss) (V = (s(s) 1
for 5' TB (0)) Mu.o and some common index In that case, must have
max
max
P uz -Pry
S max wEg
(PuR. -P Pao.(())N()))) +24CC+ +2)(C+C)AA4
vEg
2
Proof. Note that with the analysis of Lemma 9 the conclusion true for the constructed (ff.))
at the end of Step 10 in Alg. However, in the modified set of items A((,.)),, we are only adding
43

---

items in NV that either belong to the same cluster (in which case there is no added gap) or if we are adding items belonging different cluster, then the added gap on the RHS can be at most C' -+ The above statement follows from similar argument as in Lemma 13 where we showed that gap in expected reward between two users in (((A.) (or rather two users connected by a path in ((C,)) for the same item is at most O(C4441).
Hence, we have shown that each subset of users MM(E.))) is a nice subset of users and furthermore. the corresponding subset of items constructed at the end of Step 11 is nice subset of items. Next, we move on to the exploir component of phase & where we use similar trick (See Step 3 in Alg. 8) to ensure that at the end, we are left with nice subset of items. As before, we can show that the constructed set of items itself nice subset of items. We can again prove the following modified version of Corollary 2
Corollary 3. Condition on the events Eg el being true. Consider a nice subset of users M(E. E M and their corresponding set of active items NOt.) for which guarantees in eq. holds. Fix any subset C CN Consider users u, v E MMC.)) having path in the graph 9 Conditioned on the events Eg E we must have
max
[P
P Payl= S 16(C + C') and max
[P 2.yES
Poyl S 16(C C')
2.yES
where S fz ((.2.) is connected with R !R!...
Proof. The proof again follows from the fact that adding items belonging to a different cluster but connected via path to the original items in R (8) the RHS.
U RV can only add term of at most 16C' De+1 in
Therefore, at the beginning of the explore component of phase E + for particular nice subset of users (M++1,,) the corresponding set of items A((+1,a) must be nice subset of items as well. Most importantly, what this implies that for the low rank matrix completion step in the explore component of phase + 1, as well. This because, in eq. 10 in Lemma 4 we can take a union bound over all possible nice subsets of usery and all possible nice subsets of items. Since the number of clusters C, C' O(1), the total possibilities (1) as well (although exponential in the number of clusters). Hence, the complex dependencies of the previously made observations used to compute prior estimates resulted by the conditioning on surviving items and users is no longer problem we have simply made a for all argument. The rest of the analysis follows in the GBB setting and we arrive at similar result as in Theorem 1 but with B = when the set of items can be clustered into = O(1) disjoint clusters.
re-use observations from previous phases and provide theoretical guarantees
44


Reviews:
[{"review_id": "etJAYUcB6A", "reviewer": "Reviewer_tR2a", "summary": "This paper studies blocked collaborative bandits. Multiple users, clustered in a fixed number of clusters according to the rewards obtained from them are provided recommendations in each discrete time instance till T timesteps. The paper proposes algorithms that minimize the cumulative regret with the constraint that no user is recommended the same arm (item ) more than B times. The authors propose an algorithm called B-LATTICE  that collaborates across users while satisfying budget constraints, and minimising regret. The authors show theoretical guarantees of the proposed algorithm and also validate their results empirically with synthetic data. ", "questions": "see weaknesses. ", "limitations": "none", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper introduces an important setting with practical application. The main strength of the paper is its sublinear regret guarantee. The authors give the first sublinear regret algorithm in the proposed setting. Furthermore, the analysis and proposed algorithms are involved and nontrivial; the authors do an excellent job of providing an intuitive understanding of their proposed algorithms.  ", "weaknesses": "The paper does a poor job of explaining the setting and its connection to Bandits. Following are my questions and (some) suggestions to the authors. \n\n1. A crisp summary of how the problem is MAB problem is missing from the introduction/setting section. For instance, the following points are not clear in the first reading of the first 2 sections; what constitutes an arm (items?), who pulls arms (a recommendation engine or users), it is not clear that rewards are not only arm-specific but also user dependent (which in my opinion most important difference from classic MAB setting).\n\n2. Can authors shed some light on what is known apriori to the algorithm/recommendation engine? For instance, the authors use the fact that the number of true clusters  $C$ is known in Algorithm B-LATTICE, however, I don't understand why T is needed as an input. In particular. can the regret guarantee of the proposed algorithm be converted into an anytime guarantee (for any value of large enough T)? In contrast, in the Greedy algorithm (Remark 1) authors explicitly use T. \n\n3. I don't see why the authors normalize the cumulative regret by $M$ (Equation 2). Is it crucial to consider per-user regret guarantee? Howe do the results fare without this normalization?\n\n \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for making some excellent points. Below, we discuss them in details:\n\n***A crisp summary of how the problem is MAB problem is missing from the introduction/setting section. For instance, the following points are not clear in the first reading of the first 2 sections; what constitutes an arm (items?), who pulls arms (a recommendation engine or users), it is not clear that rewards are not only arm-specific but also user dependent***\n\nWe apologize for the ambiguity. We will clarify this point in the final manuscript with more available space.\n\nTo answer the reviewer's question, as discussed in Section 2, our setting has $M$ users, $N$ items and $T$ rounds. The expected (user, item) affinity is both item-specific and user-dependent - captured by the $M\\times N$ reward matrix $\\mathbf{P}$. In each round, for each user $u$, the recommendation engine recommends an unblocked item $\\rho_u(t)$ (possibly different for each user) based on the feedback history until the previous round.  Subsequently the recommendation engine observes noisy feedback  for the recommendations of each of the $M$ users at round $t$.   \n\nThis corresponds to the following analogue of multi-armed bandits (MAB) - we have $M$ users each involved in a separate MAB problem with the same set of $N$ arms (corresponding to the $N$ items) and T rounds. The mean reward of each arm is different for each user captured by the $M\\times N$ reward matrix $\\mathbf{P}$. In each round $t$, every agent $u$ simultaneously pulls an unblocked arm $\\rho_u(t)$ of their choice based on the feedback history  of all users (including $u$) from previous rounds. Subsequently the noisy feedback for all users and their corresponding arm pulls at round $t$ is revealed to everyone. \n\n***Can authors shed some light on what is known apriori to the algorithm/recommendation engine? For instance, the authors use the fact that the number of true clusters $C$ is known in Algorithm B-LATTICE, however, I don't understand why T is needed as an input. In particular. can the regret guarantee of the proposed algorithm be converted into an anytime guarantee (for any value of large enough T)? In contrast, in the Greedy algorithm (Remark 1) authors explicitly use T.***\n\nGreat question! Algorithm 1/Recommendation engine has apriori access to $M,N,C,T,B,\\sigma^2$ corresponding to users, items, clusters, rounds, budget and noise variance. Note that the number of rounds $T$ is only needed in Step 5 of Algorithm 1 for a technical/theoretical reason - here we say that if the number of surviving items is smaller than $T^{1/3}$ for a  particular nice subset of users, then we directly go to Step 13 in Algorithm 1 and recommend unblocked items in the surviving set arbitrarily to the corresponding users in the nice subset until the end of rounds. Note that we can get around this issue by using doubling trick commonly used in bandit literature for anytime algorithms (Besson and Kaufmann 2018) - however we have resisted its use for simplicity. Moreover, in practice, we do not need this step at all - see Algorithm 6 (a simplified version of B-LATTICE) in Appendix C for instance that we have implemented for our experiments. \n\nThe reviewer is correct to point out that in the greedy algorithm, the value of $T$ is required crucially in contrast.\n\n***I don't see why the authors normalize the cumulative regret by $M$ (Equation 2). Is it crucial to consider per-user regret guarantee? Howe do the results fare without this normalization?***\n\nThe normalization factor of $M$ does not hold much significance as the reviewer points out. As a starting point, our goal was to study the average regret over users and hence the normalization over $M$. However, regret is an additive quantity and therefore removing the normalization factor will simply lead to a re-scaled regret of $\\widetilde{O}(\\sqrt{(M+N)T})$.  "}, {"review_id": "Otgd93oIB6", "reviewer": "Reviewer_tct3", "summary": "This paper studies the blocked collaborative bandits where each user represent a single bandit problem. The latent groups are assummed to exist among users in which all the users in a group share the same expected reward. But the constrant is placed on the number of serving time for each user to solve the challenge of lacking user-item interactions. Then, the authors introduce a complicated algorithms including the exploitation, exploration and clustering components. The theoretical analysis is provided and achieved a tigher regret bound for this setting.", "questions": "In this problem setting, it seems to not have the assumption regarding the reward gap between two clusters. The reward gap assumption is commen in the problem of online clustering of bandits. How does it influence the analysis?", "limitations": "More empirical evaluations are needed.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper provide two regret bound. The first one recover the results and follows the regret analysis is online clustering of bandits. The second authors provide a lower bound, which consider the case when T is large.", "weaknesses": "The introduced algorithm is very complicated and I am worried about the efficiency of this algorithm. Authors didn't report the time cost of this algorithm and conduct ablation study for the exploration component. Because this paper tries to solve a very practical problem, the online recommendation, it only has very limited empirical evaluations, which run on the systhetic datasets. The main manuscript doesn't inlcude the empirical evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for asking some great questions. Below, we discuss them in details:\n\n***time cost of this algorithm***\n\nComputationally, the main bottleneck of our algorithm is the matrix completion function *Estimate* invoked in Line 13 of the Explore Component (Algorithm 2). All the remaining steps have lower order run-times. Note that the  *Estimate* function is invoked at most $O(C\\log T)$ times since there are can be at most $C$ disjoint nice subsets of users at a time and the number of phases is $\\log T$. Moreover, note that the  *Estimate* function (Algorithm 4) solves a convex objective in Line 3 - this has a time-complexity of order $O(M^2N+N^2M)$. Moreover, a number of highly efficient techniques have been proposed for optimizing this objective even when M, N are in the order of millions (for example, see https://www.cs.utexas.edu/~cjhsieh/nuclear_icml_cameraready.pdf).\n\n***No assumption regarding the reward gap between two clusters***\n\nYes, indeed, we do not have any such assumption and we consider it as a strength of our work.\n- especially since previous works such as [11,20] have used this assumption crucially for a greedy solution where the users are clustered first and then collaboration is exploited. In our setting, intuitively speaking, consider two clusters whose reward gap is unknown - there are two possible cases 1) the reward gap is small -  in this case, good items for users of one cluster will also be good items for users of another cluster. We can gather more data corresponding to a common set of good items for users of both clusters jointly and estimate/complete the corresponding reward sub-matrix by exploiting the fact that the sub-matrix has rank at most $2$. 2) However, if the reward gap is large, then it will be revealed at some stage after the matrix completion step - now, we design a graph based similarity approach to cluster the users correctly. \n\nTo summarize, the clustering is not done at the beginning (unlike previous works) but is done gradually as more information is obtained - thus clustering, exploration and exploitation are implemented jointly in our algorithm.\n\n***conduct ablation study for the exploration component.***\n\nWe are sorry but this statement is unclear to us. If the exploration component in the algorithm is removed, then the exploit component will not work - therefore the algorithm itself will not work anymore. Are we missing something? Can the reviewer please clarify what they mean by this statement? \n\n***limited empirical evaluations, which run on the systhetic datasets***\n\nPlease see the global post and the attached pdf. We have provided detailed experiments/plots on the well known MovieLens dataset to further validate the efficacy of our algorithm. \n\n[1] https://tor-lattimore.com/downloads/book/book.pdf\n\nNote that our main contributions are theoretical in nature and experiments are mostly for validation of theoretical guarantees. "}, {"review_id": "uFyytxviS2", "reviewer": "Reviewer_2VtF", "summary": "The paper considers the problem of blocked collaborative bandits with multiple users that each belong to a cluster with associated bandit instance. The goal is to minimize the regret of each user while satisfying the constraint that each arm can be played at most B times for each user. The paper proposes an algorithm with sublinear regret upper bound.", "questions": "- It seems that the regret lower bound in Theorem 2 is linear in T while the upper bound is sublinear?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a novel algorithm that uses matrix completion and clustering techniques.\n- Although not very surprising, a regret bound of O(sqrt{TN/M}) is proved when B=O(log T).\n- The paper also proves a lower bound on the regret. ", "weaknesses": "- The regret upper bound holds only for B=O(log T). As the papers main contribution is providing regret bounds with the existence of the budget constraint B, I believe the authors should provide the dependency of the regret bound on B.\n- Assumption 1 is strong. It requires the information to not be concentrated in some clusters which in my opinion is an interesting case to deal with. Moreover, the choice of assumptions and constants is unnatural; for example why is |S|=T^{1/3} in Assumption 1.3?\n- The regret lower bound does not match the achieved upper bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for making some excellent points. Below, we discuss them in details:\n\n***As the papers main contribution is providing regret bounds with the existence of the budget constraint B, I believe the authors should provide the dependency of the regret bound on B.***\n\nThe regret scales as $\\sqrt{B}$  - Since $B=O(\\log T)$, this term is hidden inside the $\\widetilde{O}()$ notation in the regret for simplicity - our goal was to emphasize the dependence on $M,N,T$ which are the large quantities. However, as the reviewer suggests, we will add this in the final version.   \n\n***Assumption 1 is strong. It requires the information to not be concentrated in some clusters which in my opinion is an interesting case to deal with. Moreover, the choice of assumptions and constants is unnatural; for example why is |S|=T^{1/3} in Assumption 1.3?***\n\nWe completely agree with the reviewer that the information being concentrated in some clusters is an interesting case - indeed, relaxing Assumption 1 is an important research direction.\nImportantly, note that unlike previous works (for instance [11,20]), we do not assume anything about separation between cluster centers. In fact, note that in Assumption 1, we can scale down the singular values of $X$ by as much as we want to reduce the separation between cluster centers. However, such an operation does not change the regret guarantee.\n\nAlso note that, we do need to start somewhere and we made a similar assumption as in Pal et. al. (2023) - [24] in the paper. Since $T$ is much smaller than $M,N$, the assumption is satisfied by a wide variety of matrices [24]. \n\nWe also agree that the constant $1/3$  in the expression pointed out by the reviewer might look unnatural - however, it has been made only for simplicity of exposition. To generalize, any constant $\\beta<1/2$ would have been sufficient for us. This constant comes up in Step 5 of Algorithm 1 -  all we want to say is that if the number of surviving items is smaller than $T^{\\beta}$  for a particular nice subset of users, then we have to recommend arbitrarily from the surviving items to the corresponding users. This leads to a order-wise smaller regret of $o(T^{1/2})$ since we show that the number of remaining rounds must always be smaller than the number of surviving items.  \n\nWe will clarify this point in the final manuscript with more available space.\n\n***The regret lower bound does not match the achieved upper bound.***\n\nYes, surprisingly, this seems to be a technically difficult problem and bridging the gap is left as future work. The difficulty, in particular, has been explained in L238-241. However, saying that, we do believe that our upper bound is tight and the lower bound can be improved.\nAs mentioned in L250-255, our lower bound in Theorem 2 itself is very non-trivial and requires novel ideas involving reduction to multiple hypothesis testing problem and exploiting Fano's inequality. Note that our current lower bound matches the upper bound when $T$ is very small or very large (L243-L255). \n\n\n\n***It seems that the regret lower bound in Theorem 2 is linear in T while the upper bound is sub-linear?***\n\nExcellent question! The second term in the lower bound the reviewer refers is of the form $\\widetilde{\\Omega}(T/\\sqrt{M})$ assuming $B=O(\\log T)$. Notice carefully that the denominator has a $\\sqrt{M}$ factor but the numerator does not have a fractional power of $N$. On the other hand, the regret upper bound is of the form $\\widetilde{O}(\\sqrt{NT/M})$ . Since $N \\gg T$, the lower bound is not a contradiction and can in fact be much smaller than the upper bound. The second term matches the upper bound only when $T\\approx N$  i.e. $T$ is very large as mentioned in L251. We hope this clarifies the question."}, {"review_id": "QGAwZ2vcne", "reviewer": "Reviewer_7P26", "summary": "In this paper, the authors tackle a collaborative-filtering type multi-armed bandit problem. There are many users, each facing a multi-armed bandit problem. However, there are only $C$ base multi-armed bandit instances, where each user comes from one of these instances. The authors provide a novel algorithm which only pulls each arm at most $B$ times per user, and provide information theoretic lower bounds for this new setting. The authors also provide an improved, practical version of this method.", "questions": "See weaknesses. My primary question is regarding the assumption of knowing $C$, and that each user has exactly 1 of $C$ different mean vectors.", "limitations": "Discussed, modulo $C$ above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed algorithm is reasonably easy to follow, and makes intuitive sense. The authors explain the process clearly.\n2. The authors provide a new lower bound, using a different Fano's inequality based method. The approach and proof of the upper bound make sense, but I have not checked the details thoroughly.\n3. It would be good to emphasize that $N,M\\gg T$ is actually a very relevant setting; $T$ is number of interactions per user, each user will only interact with the system a moderate number of times, but the overall number of users can be very large.", "weaknesses": "1. The assumptions regarding $C$ are very strong. a) that all users come from exactly 1 of $C$ instances (no within group variability), b) that $C$ is exactly known, and c) that $\\tau$ is constant (it is unclear how the bound depends on $\\tau$). Additional text regarding why these assumptions are reasonable, the brittleness of the algorithm to these differences, or on how these assumptions can be loosened, would strengthen the paper.\n2. Empirical improvement: it does not appear that the algorithm has much better performance than the greedy baselines, unless I am misreading Figure 1? It could improve the paper to add simulations for larger $T$ to show how the asymptotic behavior compares (over Greedy). Additionally, comparing against [24] in the case where $B=T$ would be interesting. Finally, to highlight the improvement of collaboration, it could help to include a baseline of running e.g. UCB independently for each user, showing that this would yields dramatically worse performance.\n3. Clarity: the work is overall quite clear and well-written, but there are some points (discussed below) that could help improve presentation.\n\nMinor:\n1. Lower bound as stated is not technically correct. Classical bandit lower bounds hold when the noise is truly Gaussian (or Bernoulli), and cannot be invoked for general sub-Gaussian random variables, as the variance proxy is an upper bound (e.g. a Gaussian with variance .01 is 1-sub-Gaussian).\n2. Eqs after Line 1252 and 1259 have typing errors; maybe missing a $\\geq$?\n\nTypos:\nLine 28: unknown cluster and *the* expected reward\n53: suboptimal dependence on *the* number\n207: \"columns comprise of at\"\n249: \"small for e.g.\"\nFig 1 caption: period missing before last sentence, space after PB-Lattice.\nRedundancy in setting $\\Delta_{\\ell+1}$ in line 2 of Alg 1\nLine 274,278: clarify that goal is to get an entrywise $O(2^{-\\ell})$ estimate.\nB-Lattice doesn't take in B as input, and this parameter doesn't show up anywhere in Alg 1. Alg 2 also doesn't take $B$ as input.\nUsing $\\mathbf{C}$ as a counts matrix and $C$ as the number of clusters is confusing notation.\n\n\nAlgorithmic clarification:\n1. It appears as though $\\mathcal{M}^{(\\ell)}$ is an *estimation* of disjoint nice subsets of users, whereas in Algorithm 1's input it is stated that they are truly nice subsets of users.\n2. Line 287: each connected component is a nice subset *with high probability*? Several results need to be clarified that they're conditional on the good event in Lemma 1 (that estimation worked).\n3. The algorithms defined do not appear to be \"stand-alone\", i.e. they have side effects involving the matrices C and D (which appear to be global variables)? A clearer description of what each algorithms requires as input, and what variables it modifies, would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Knowledge of C***\n\nPlease note that C is a small positive constant integer that does not scale with M,N,T (users,items,rounds). In fact, it suffices if we know a loose upper bound for C. Also, if C is unknown, then at the  beginning, we can use a small number of rounds to estimate C. For instance, in our model, we can use a constant number of rounds to gather data for all users corresponding to the same set of items and then fit k-means combined with the ELBOW method to estimate the value of C.\n\n***each user has exactly 1 of C different mean vectors.***\n\nExcellent question! Although we have made this assumption for simplicity as in other papers in the literature [2,3,5,24], the assumption of each user having exactly 1 of C different mean vectors can be relaxed significantly. In fact, in [24], a similar cluster relaxation was done in the following way - there are C clusters such that 1) users in the same cluster have mean vectors  that differ entry-wise by at most $\\nu$  2) for any 2 users in different clusters have mean vectors that differ entry-wise by at least $20\\nu$.  Our work can be easily extended to this relaxed definition of clusters too! We will add a detailed remark regarding this in the main paper.\n\n***$\\tau$ is a constant***\n\nAgain, this is for simplicity of exposition. To obtain the explicit dependence on $\\tau$, we need to use Theorem 2 in Chen et. al. 2019 for matrix completion. We did the corresponding calculation and found the regret in Theorem 1 eq. (4) to be scaling as $O(\\tau^3)$. \n\n***Empirical improvement:***\n\nWe thank the reviewer for very helpful and excellent questions/suggestions! We have discussed them in detail below:\n\n1) *not having better performance than greedy baselines* - We would like to note that greedy algorithm, when run with the ``right'' exploration parameter, achieves the optimal $\\sqrt{T}$ regret in MABs. For instance, see Eq (6.7) of [1] where the authors derive $\\sqrt{T}$ regret of greedy with best exploration parameter. Also, see Figure 7.1 [1] where UCB barely outperforms greedy. The caveat though is that this right exploration parameter is dependent on the sub-optimality gaps which are unknown in advance; consequently, it is not implementable in practice. We believe a similar phenomenon happens in our setting (i.e., greedy with best exploration parameter is a very strong baseline with good regret guarantees). In our experiments, we compare B-LATTICE with this strong baseline and show that our algorithm outperforms (albeit slightly) the baseline. We believe this is a strong empirical evidence supporting the efficacy of our algorithm. \n\nThat being said, as the reviewer suggests, we will add simulations with larger T in the revised manuscript.\n\n[1] https://tor-lattimore.com/downloads/book/book.pdf\n\n2) \\textit{ comparing against [24] in the case where $B=T$} Note that the definition of regret in the two settings is very different. For our setting, for each user, the best thing to do in hindsight is to recommend the top $T/B$ items $B$ times. On the other hand, for $B=T$, the best thing to do is to recommend the top item $T$ item. Because of this, the two algorithms are incomparable. \n\n3) \\textit{Baseline of UCB } Note that our simulations are done in the setting when $B=1$. This means that each item can be recommended only once to every user. In this setting, UCB boils down to just randomly recommending items - it becomes completely trivial. Hence there is very little point in comparing with individual UCB - it is as good as randomly recommending items.\n\n***Lower bound as stated is not technically correct. Classical bandit lower bounds hold when the noise is truly Gaussian (or Bernoulli***\n\nThanks for pointing it out. Our lower bounds are also proved specifically for when the noise is zero mean gaussian with unit variance. We will take care of this minor issue.\n\nWe will address all the remaining minor issues/typos/clarification requests as pointed out by the reviewer in the subsequent version.\n\n***Algorithmic Clarifications***\n\n1) ***It appears as though $\\mathcal{M}^{(\\ell)}$ is an estimation of disjoint nice subsets of users, whereas in Algorithm 1's input it is stated that they are truly nice subsets of users.***\n\nThe reviewer is correct. We do show that with high probability that $\\mathcal{M}^{(\\ell)}$ is a nice subset of users in every phase $\\ell$ (Lemma 7 and Lines 890-904 in Appendix). As a matter of fact, B-LATTICE can run even if the sets of users in  $\\mathcal{M}^{(\\ell)}$ are not nice - but they do need to be disjoint. We will clarify these further.\n\n2) ***Line 287: each connected component is a nice subset with high probability? Several results need to be clarified that they're conditional on the good event in Lemma 1 (that estimation worked).***\n\nYes, each connected component is a nice subset with high probability. Thanks for pointing this out. We will clarify this clearly.\n\n3) ***The algorithms defined do not appear to be \"stand-alone\", i.e. they have side effects involving the matrices C and D (which appear to be global variables)? A clearer description of what each algorithms requires as input, and what variables it modifies, would be helpful.***\n\nYes, indeed the matrices C and D are global variables. As the reviewer suggests, we will definitely improve clarity of the algorithm further with more available space in the next version. "}, {"review_id": "z9PcojkFg1", "reviewer": "Reviewer_HmVS", "summary": "This paper considers the online recommendation for a hard-clustered user. \n\nProblem setup summary:\nThis problem involves $M$ users and $N$ items. the reward matrix $P \\in R^{M \\times N}$ is unknown. There are $T$ rounds in total, and each user receives a recommendation $\\rho_u(t)$ at each round. Each user belongs to one of (unknown) clusters indexed by $\\{1,2,\\dots,C\\}$. Each user can consume at most $B = O(\\log T)$ same item. \n\nThe oracle-optimal strategy is to recommend top-($T/B$) items for $B$ (max possible) times, and the regret is the loss of recommending items except for these top arms. \n\nThis is multitask learning in the sense that the results are better than solving $N$-armed bandit for each of $M$ users (in that case, regret would be linear to $M$).\n\nSection 2.1 introduces a bound on the accuracy of low-rank matrix completion (Lemma 1, [16]). Based on that it describes the performance of explore-then-commit with $B=1$. Section 3 introduced the B-Lattice algorithm, its regret bound (Thm 1), and regret lower bound (Thm 2)\n\nThe paper proposes B-LATTICE algorithm for online recommendation. The algorithms is phased and at each phase $l$ it obtains accuracy of $2^{-l}$. This paper is well-written. Although the algorithm described here is not truly practical in the sense it can be applied to real recommendation (see weaknesses). The contributions of the paper are enough good. My main concerns are about the solidness of the results.\n\n#####\nI think the paper is above the acceptance threshold even though the exposition can have some space for improvement, so I keep current rating (WA).", "questions": "* Is Lemma 1 derived from Lemma 2 of [16] (or from Lemma 5 of [16])?\n\n* Question on the applicability of Lemma1: Lemma 1 requires the sampling of $\\Omega$ to be iid. I assume B-Lattice adopts the same bound, but can it be usable for such a complex sampling scheme? \n\n* Questions on the bounds:\n  * Can the authors clarify the incoherency condition (L176: $||\\bar{U}||_{2,\\infty}$ - this norm undefined?), and subset strong smoothness? \n  * What is the dependence of Thm1 in $C$ (# of clusters)?\n  * What $B = \\Theta(\\log T)$ exactly states? In particular, can i be $C \\log T$ where $C>0$ is independent of $T,N,M$, and # of clusters? \n\n* (minor) Are the technology used in this paper (bound on low-rank matrix completion and graphs) entirely new in this paper? How the basic technology can be compared with related work (e.g., Table 1)?\n\n* (minor) Is there any way to simplify the algorithm? For example, can explore (Alg 2) be randomly recommending an available item, and exploit be randomly recommending an item weighted on the likelihood to be good?", "limitations": "Not applied.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* A new scheme on the factorized recommendation with bandit settings (Tbl 1) \n* parametric rate of regret\n* Non-trivial (non-tight) regret lower bound using Fano's inequality.\n* Simulation results in appendix", "weaknesses": "* Somewhat artificial budget constraint (top T/B items, where B is consistent over all items)\n* Many parts of the algorithms are in the appendix (mainly, Alg 4,5)\n* Alg depends on B, C that are hard-to-know before (in particular B).\n* Alg is very involved.\n* (minor) exposition on the order of elements can be improved. \n  * For example, Lemma 1 informally describes incoherency before the main results, the main results part (Thm 1) do not include B-LATTICE detail even though it is bound on this algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for making some excellent points. Below, we discuss them in details:\n\n***1) Somewhat artificial budget constraints 2) Many parts of the algorithms are in the appendix (mainly, Alg 4,5) 3) Alg depends on B, C that are hard-to-know before (in particular B).****\n\n1) We apologize but the first point is a bit unclear to us - we motivated the necessity of budget B from a marginal utility point of view in the Introduction. Will it be possible for the reviewer to clarify a bit more?\n\nPerhaps the reviewer is saying that B being fixed across all items is artificial - note that even if this is true, the regret problem in a fixed B setting across all items was unsolved theoretically. However, we agree that (user,item)-dependent B is an important direction of future work.  \n\n2) Due to space restrictions, it was necessary for us to keep several components in the Appendix. In the final version, with more available space, we will move back Algorithms 4,5 to the main paper.\n\n3) Note that $B,C$ are positive integers and assumed to be very small. So,\n even if they are unknown, we can easily estimate them very well from a small amount of exploratory data. We can definitely add a remark clarifying this in the paper.\n\n***Is Lemma 1 derived from Lemma 2 of [16] (or from Lemma 5 of [16])?***\n\nLemma 1 in our paper is derived from Lemma 2 of [16] (by setting $s=1$). Note that Lemma 5 of [16] is actually sub-optimal since its error guarantee has an additional undesirable factor of aspect ratio  - this is removed in Lemma 2 of [16].\n\n***Question on the applicability of Lemma1: Lemma 1 requires the sampling of $\\Omega$\n to be i.i.d. I assume B-Lattice adopts the same bound, but can it be usable for such a complex sampling scheme?***\n \n The reviewer is right to point out that Lemma 1 requires the sampling of $\\Omega$ to be i.i.d. We do ensure this in our algorithm. For a specific sub-matrix given as input in Algorithm 2, we do sample $\\Omega$ independently for matrix completion in Line 1 of Algorithm 2 - of course the sub-matrix that we choose to complete is determined based on the feedback history. More precisely, suppose Algorithm 2 is invoked with the set of users $\\mathcal{M}$ , set of items $\\mathcal{N}$ and sampling probability $p$. Then $\\Omega$ is chosen such that every entry $(i,j)\\in \\mathcal{M}\\times \\mathcal{N}$ is present in $\\Omega$ with probability $p$. Therefore, we can use the guarantees of Lemma 1 for the estimate of the sub-matrix $\\mathbf{P}_{\\mathcal{M},\\mathcal{N}}$ (reward matrix $\\mathbf{P}$ restricted to users in $\\mathcal{M}$ and items in $\\mathcal{N}$) . \n \n ***1) Incoherence condition: $\\left|\\left|\\mathbf{U}\\right|\\right|_{2,\\infty}$ 2) subset strong smoothness (SSS)***\n \n$||\\mathbf{U}||_{2,\\infty}$ corresponds to the maximum euclidean norm of a row of the matrix $\\mathbf{U}$.\n \nMore precisely, for a matrix $\\mathbf{U}\\in \\mathbb{R}^{M\\times r}$, the norm $||\\mathbf{U}||_{2,\\infty}$ \n\nis equal to $\\max_{i \\in [M]} ||\\mathbf{U}_i||_2$. \n\nThus, if $||\\mathbf{U}||_{2,\\infty}$  is small as in Lemma 1, then all rows of $\\mathbf{U}$ have a small $\\ell_2$ norm.\n\n\n The SSS assumption states that all sub-matrices of a tall matrix restricted to at least a certain number of rows must have the minimum eigenvalue to be bounded from below. \n \nWe will clarify these further in the next version of the manuscript.\n \n ***What is the dependence of Thm1 in C?***\n \n The regret guarantee in Theorem 1 eq. (4) scales as $O(C^3)$ . However, since $C$ is assumed to be a small constant, we have suppressed this dependence within the Big-O notation. Our main goal was to highlight the dependencies on $M,N,T$ in the regret guarantee.\n \n ***What $B=\\Theta(\\log T)$ exactly states? Can it be $\\dots$***\n\nYes, the reviewer is correct. It suffices for us if $B=c\\log T$ for any constant $c>c'$ where $c'$ is a constant independent of all other model parameters. This is because, we simply want $B$ to be at least the number of phases. Since our phase lengths increase exponentially, the number of phases is $O(\\log T)$. We will add this clarification to the paper. \n\n***Minor Points*** \n\n1) Yes, to the best of our knowledge, our matrix-completion based approach is completely novel. Previous works have often used a cluster first and then exploit approach which is greedy and often sub-optimal.\n\n2) Yes, both suggestions of the reviewer - randomly recommending items in explore and recommending items weighted by some score in exploit are good suggestions for simplification and can be implemented in practice. \nWe agree that in practice, our algorithm can be simplified significantly. We have in fact provided such a simplified version PB-LATTICE in Algorithm 6 (Section C in Appendix) that we have implemented in our simulations. We have also provided a greedy Explore Then Commit (ETC) Algorithm that is much simpler to state and analyze (Appendix B) but obtains sub-optimal guarantees (Remark 1)"}]

Author rebuttal:
**Experiments on Movielens-10M dataset**

Reviewer tct3 requested for additional experiments on real-world datasets - in response, we show a set of experiments on the popular MovieLens dataset. Relevant figures can be found in the attached pdf.

We take the Movielens 10M dataset (https://grouplens.org/datasets/movielens/10m/), take 200 users who have rated most movies, 200 movies that have been rated the most and consider the $200\times 200$ reward matrix associated with those users and movies. The number of missing entries in that matrix is $<20$% and we use standard imputation techniques to fill those missing values. We consider this reward matrix to be the ground truth and remains unknown to the algorithm. Subsequently, we experiment with our set-up  - $M=200$ users, $N=200$ items, number of rounds $T=60$ and budget $B=1$. In every round, one chosen unblocked item is consumed by the each user who then provides a noisy feedback - the expectation of this feedback is the corresponding entry of the ground truth reward matrix and the additive noise is zero-mean gaussian with variance $0.5$. The goal is to sequentially recommend items to every user based on prior history and minimize the regret across all users (see equation 2 in the paper). We compare our algorithm B-LATTICE (a simplified version in Algorithm 6) with ETC algorithm (Algorithm 5) and tuned exploration parameter. All relevant plots have been provided in the attached pdf.

Note that the greedy/ETC algorithm, when run with the ``right'' exploration parameter, achieves the optimal regret in MABs. For instance, see Eq (6.7) of [1] where the authors derive optimal regret of greedy with best exploration parameter. Also, see Figure 7.1 [1] where UCB barely outperforms greedy. The caveat though is that this right exploration parameter is dependent on the sub-optimality gaps which are unknown in advance; consequently, it is not implementable in practice.  In our experiments, we compare B-LATTICE with this strong baseline  and show that our algorithm outperforms the baseline.  Furthermore, we also show that our algorithm has a small cold-start period (time before it starts meaningful recommendations)  and also has high round-wise reward in every round - in other words, it makes good recommendations in every round. On the other hand, the greedy/ETC algorithm (with $30$ exploration rounds) has a significantly large cold-start period (30 rounds). 

[1] https://tor-lattimore.com/downloads/book/book.pdf

Meta-review: Based on the discussion in the review period, the reviewers see this paper as having the following main strengths:
- The paper proposes a novel algorithm that uses matrix completion and clustering techniques.
- Solid regret upper and lower bounds
- different from many previous works, this work makes no gap assumption between the clusters
- Reasonable experiments for a theory paper

The main weaknesses recognized were:
- The Algorithm is very involved (although the presentation was reasonable) and needs to have knowledge of usually-unknown parameters
- The dependence on the number of clusters in the regret bound is high ($O(C^3)$)
- Many clarity improvements necessary, based on the author-reviewer discussions

Overall, the reviewers think that the strengths outweigh the concerns for this paper.
Decision: Accept (poster)