Summary
The authors studied the high-dimensional linear contextual bandit problem where the number of features 𝑝 is greater than the budget 𝑇, or it may even be infinite.
Problem setting: They assumed each arm has an individual hidden parameter, and the contexts are drawn from nature for each round.
They argue that only by using the notion of effective dimension, in some cases when data distributions have a small effective rank, explore-then-commit algorithm can address this problem.
Strengths
They adopted the new techniques from [Bartlett et al., 2020] to design an explore-then-commit algorithm with this 'tough' environment - where the dimension $p$ is large compared to the number of samples. Seems like this observation is original.
Plus, they proved that their regret bound is tight by proving several lower bounds. If their arguments are all correct, these results can be significant.
Weaknesses
I am unsure whether this paper is clear enough.
1) It's not straightforward whether they assumed 'benign covariance matrix' in proposition 1 or their assumption 1 implies benign covariance matrix.
2) I cannot understand how one can take an inverse matrix in line 117 when $p>n$.
3) Eventually, seems like they made only two major assumptions - Assumption 1 with sub-gaussianity, and Assumption 2 which is about the error rate of the OLS. Especially, for AEtC, they only used Assumption 1. I am strongly doubtful that they achieve a meaningful regret bound without any additional assumption on high-dimensional space - As in the first paragraph of Chapter 7, 'High-dimensional statistics' by Martin Wainwright, if the model lacks any additional structure, then there is no hope of getting a consistent estimator in the high-dimensional environment.
Questions
0) In line 117, you mentioned that $\hat{\theta}$ can be achieved by simple OLS (ordinary least square) operation. However, you mentioned that $p>n$. How can you define $(XX^\top)^{-1}$ in this case? The authors also mentioned that their analysis can be executable even when $p=\infty$ (the first sentence of the abstract.) Please help me to understand this.
1) The authors use the word 'optimal balance' when they describe AEtC. Here's the sentence:
> Moreover, we introduce an adaptive explore-then-commit (AEtC) algorithm that adaptively finds the optimal balance.
I want to ask what the word 'optimal' means. I cannot see any lower-bound proof of the exploration in this paper. Did you prove that none of the EtC algorithms can beat the AEtC algorithm? If not, I believe that one should be careful of using the word 'optimal.'
2) According to my understanding, AEtC is an algorithm that relieves the assumption on the knowledge of $\Sigma^{(i)}$ (and naturally Assumption 2) from EtC, not the algorithm that improves the order of regret, am I right?
3) I want to know whether you 'assumed' the covariance matrix to be benign, or Assumption 1 (or 2) implies the covariance matrix to be benign.
4) In your proposition 1, I want to check that your $\lambda_k^{(i)}$ is exactly $k^{-1 + 1/T^a}$ or $k^b$, not the orderwise notation, am I right?
5) Maybe a silly question, but suppose that we regard your problem as a K-armed bandit problem, without considering the context. Then, isn't this mean that we already have a regret bound of $O(\sqrt{KT})$? Even for EtC, we have $O(T^{2/3})$ regret bound for K-armed bandit with EtC. What is the main factor that separates your problem from the naive K-armed bandit problem?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
There's no negative societal impact of their work.
I also think they didn't state their limitations or future works properly.