Further Responses
We thank the reviewer for following up with some nice questions. Below, we provide detailed answer to them:
**Experiments.**
To answer the reviewer's question, we compare with a strong baseline, an Alternating Minimization (AM) based algorithm introduced in [1] and modify the AM algorithm by adding the blocking constraint. Note that even without the blocking constraint, AM algorithm outperforms several baselines as reported in [1]. The AM algorithm is very general since it handles a low rank reward matrix (a special case of which is the cluster setting).
In the same MovieLens setting described in the global response (with $M=200$ users, $N=200$ items and $T=60$ rounds), the modified AM algorithm, ran with the same parameters as reported in [1], obtains a Cumulative Regret of 6901.93. On the other hand, as shown in the plot,
our algorithm obtains a Cumulative regret of 6543.91 while the greedy algorithm with 30 and 10 exploration rounds obtains a cumulative regret of 7302.19 and 7794.96 respectively. Thus our algorithm, outperforms the AM algorithm with the blocking constraint. However, we point out again that the AM algorithm does not have any theoretical guarantees at all (not even without the blocking constraint) while our algorithm has strong theoretical guarantees.
[1] Alternating Linear Bandits for Online Matrix-Factorization Recommendation (2018)
**Gap assumption. Authors discussed two cases with two different solutions. How can your algorithm differentiate these two cases if there is no gap assumption?**
To get the intuition for how the algorithm can differentiate between the two cases, we first consider the phased elimination algorithm for standard Multi-armed Bandits (MAB) (see Exercise [6.8] in [2]). This algorithm doesn't require the knowledge of any gap parameters, but still achieves the optimal instance dependent regret. It does this by getting more accurate estimates of the arm rewards over phases and eliminating arms based on a pre-specified threshold that decreases exponentially with each phase. If there is huge gap in the rewards between the best arm and the rest, then the sub-optimal arms will be identified and eliminated in earlier phases. On the other hand, if the gap is small, then the sub-optimal arms will be eliminated in later phases. In both these cases, it can be shown that the algorithm achieves the optimal regret while being oblivious to the gap.
Our algorithm is designed along similar lines- it runs in phases and in every phase, we estimate the user clusters and simultaneously eliminate arms within each cluster. In the beginning of the algorithm, these clusters are coarse. As the algorithm proceeds, we refine our clusters and eliminate arms based on a pre-specified threshold. If the gap between clusters is large, our algorithm can separate these clusters in earlier phases. On the other hand, if the gap between clusters is small, our algorithm can separate them in later phases where we have more data. In both these cases, we can show that our regret is minimax optimal, without actually knowing the distance between clusters.
To be more precise, we have a graph based approach for clustering users. The graph based approach takes a pre-specificied parameter $\Delta_{\ell}$ (in phase $\ell$) that decreases exponentially with the phase index. Here the graph corresponds to a user-similarity graph constructed based on the estimates from our low rank matrix completion module. and subsequently, the clustering proceeds by simply considering each connected component of the user similarity graph as a cluster.
If the clustering succeeds that is, the sets of users belonging to separate true clusters are identified, then we are good. But note that even if the clustering does not succeed, we show that it is because the entry-wise gap between the cluster centers must be small - i.e. the gap must be $O(\Delta_{\ell})$. Because of this, we can treat the users jointly as a single cluster of users. Hence, we will suffer bounded regret in the exploration component in the next phase. Note that we have not used any explicit knowledge of gap anywhere. Since $\Delta_{\ell}$ decreases exponentially, the regret decreases exponentially with the phase index $\ell$ (even if we are not able to distinguish between the true clusters of users).
[2] https://tor-lattimore.com/downloads/book/book.pdf
**Theoretical analysis. For theorem 1, How does $C$ affect your regret bound?**
Of course, the setting of C=1 is trivial as the reviewer mentions.
We have assumed $C$ to be a constant (i.e. it does not scale with M,N,T) - see Assumption 2. Our regret guarantee scales polynomially in $C$ (more precisely, the dependence is $O(C^3)$) - but for simplicity of results/exposition, we have hidden the dependence of $C$ within the $\widetilde{O}(\cdot)$ notation. However, if the reviewer suggests, we can make the dependence of $C$ explicit in our result.