Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes efficient algorithms for matrix GLM bandit with regret and runtime guarantees additive in the matrix dimensions a significant improvement from previous work on low-rank bandits with linear and non-linear rewards (generalized linear model). Both the algorithms are verified on a suite of numerical experiments. 
strengths_and_weaknesses: -- Strengths:
1. The extension to GLM reward using a quadratic optimization problem is non-trivial. This forms the key novel step in the first algorithm, while the second step relies on a standard GLM-UCB algorithm. The novelty for the reduction to low-dimensional space lies in construction of an oracle inequality. Although, this reduces the regret incurred by the bandit algorithm making its implementation computationally expensive.

2. In order to improve the computational complexity of the proposed algorithm, the authors suggest another algorithm by excluding inclusions into a properly determined subspace thereby allowing to invoke any low-dimensional GLM bandit algorithm. Surprisingly, this inclusion doesn't lead to large estimation error as compared to the previous algorithm. 

-- 
Weakness: 

1. Writing can be significantly improved. While the paper is technical, the description of the results and the intuition behind them can be elucidated using a clear language. 
questions: --
Did the authors consider other methods to detect low-rank especially those based on random projections, thresholding and PCA, at least int the numerical section?
limitations: --
Writing can be significantly improved.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper considers generalized low-rank matrix bandit problems. The expected rewards are modeled as $\mu(\langle \Theta^*, X_t\rangle)$ and $\Theta^* \in \mathbb{R}^{d_1 \times d_2}$ is an unknown low-rank matrix with rank $r$. 
For this problem, the authors firstly proposed the subspace extraction-based algorithm G-ESTT. 
G-ESTT's subspace extraction guarantee is based on Stein's method.
In stage 2 of the G-ESTT, based on the extracted subspace, LowGLM-UCB is run. 
The overall regret guarantee is improved from the previous algorithm. 
They further proposed G-ESTS, which is an even faster (in time complexity) algorithm than G-ESTT.
G-ESTS achieves the same order of the bound of G-ESTT, and improved bound when the action set is finite. 
Finally, numerical experiments on the synthetic data have shown the efficacy of the proposed algorithm in terms of the empirical time complexity and the overall regret.

strengths_and_weaknesses: - Strengths

Improved regret guarantees the problem with standard assumptions and with additional assumptions. 

Computationally efficient algorithm (G-ESTS) is proposed.

- Weaknesses

Explore then commit type algorithm (although two stages are sharing some data, I think it's true for subspace extractions.) is not practical.

questions: ### Major question

With the constant upper bounds on the matrix norm, S_f, can D_{rr} be kept constant independent of d?
Intuitively, I feel that since the magnitude of the element of the matrix is suppressed by 1/d, etc., the size of the eigenvalue also depends on d for wide range of instances.
I would like to know if there are many examples that are not dependent on d.

### minor 

line 180, k-dimensional?

line 194, x_t, should be x_k?

improvement from (d_1 + d_2)^{3/2} \sqrt{rT} to (d_1 + d_2)r \sqrt{T} is only in d_1 and d_2? for some regime, dependence on r is disimproved?

line 253, experments

line 244, why you say O(\sqrt{kT}) in theorem statement but O(k\sqrt{T}) in the footnote?

 LowGLM-UCB,  (P)LowGLM-UCB,  PLowGLM-UCB: namings are a little bit confusing. 

It looks to me that G-ESTS is better than G-ESTT in every aspect. Is there any reason why you present G-ESTT too, instead of only presenting G-ESTS? Is there any advantage of G-ESTT over G-ESTS?

Why numerically, the algorithm is only compared with LowESTR?






limitations: See questions above.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes two efficient algorithms called G-ESTT and G-ESTS for generalized low-rank matrix bandit problems. Both algorithms achieve the optimal regret bound up to logarithm terms. G-ESTT extends the two-stage algorithm LowESTR to the nonlinear reward setting, and G-ESTS further drops all negligible entries to get a low-dimensional bandit, significantly reducing the computational costs.

strengths_and_weaknesses: Strengths:

1. The paper is mostly clear.
2. The technical contribution is solid. The proposed algorithms achieve the optimal regret up to logarithm terms. In addition, the G-ESTS algorithm is very efficient.


Weaknesses:
1. The paper only contains experiments with synthetic data. It would be better if real data experiments were included.
2. Some details need more clarifications (see Question part).
questions: 1. Since G-ESTT adopt the similar two-stage framework as LowESTR, I hope the authors can provide some intuitive explanation why G-ESTT can improve the regret bound by $\sqrt{d}$.
2. Assumption 3.3 seems proposed for fixed action set. If the action set is time-varying, should the sampling distribution be also time-varying?
3. In the experiments, Which sampling distribution is used in stage 1? the accuracy for subgradient methods?
4. SGD-TS algorithm is designed for the finite arm setting. I hope the authors can provide some efficient generalized linear bandit algorithms for infinite arms.
5. The proposed algorithms only achieves the optimal regret when $d_1=d_2$. What is the lower bound of the low-rank matrix bandits where $d_1$ is far from $d_2$? If the lower bound is $O(r\sqrt{d_1d_2T})$ rather than $O((d_1+d_2)r\sqrt{T})$, the proposed algorithms are suboptimal in this case.
6. What is the lower bound of generalized low-rank matrix bandit problem with finite arm? 

limitations: no potential negative societal impact
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper deals with the generalized low-rank matrix bandit problem, where for each time the learner choose one action with its own feature matrix, and receives a noisy reward by the inner product of the chosen action feature matrix and a hidden matrix $\Theta^*$ with know rank $r$. 

This paper uses ingenious Stein's method based approach to estimate the subspace even more accurately compare to the previous approaches, and this is the core originality of this paper. Thanks to this new estimation, the author invented the algorithms G-ESTT and G-ESTS, which shows $O(dr\sqrt{T}/D_{rr})$ regret bound which matches to the known regret lower bound of the generalized linear bandit problem. The second algorithm, G-ESTS, removes the redundant dimensional parts in calculation and still theoretically performs well. 

The author also shows the practicality of their algorithm by the experiment. 
strengths_and_weaknesses: 1) Originality:
1-1) Strength 

Their strength is the new subspace estimation method, which is based on a different approach called Stein's method. As far as I know, there was no similar work using Stein's method in this field. 

They also provide a bold subtraction approach (in ESTS). Previous papers with similar structure with this paper usually keep caring of the redundant dimensions, $(r+1: d_1, r+1:d_2)$, for the rest of the bandit calculation (mainly for the theoretical safety). This paper proves that the learner don't need to care the redundant dimensions anymore. 

This paper also introduces Stein's method for the matrix completion, which provides more accurate estimation than the previous approaches.

1-2) Weakness:

This paper is basically follows the similar structure with ESTR (Jun et al, 2019, Lu et al, 2021) and shares the similar drawback. 
Most importantly, the regret bound depends on the size of the minimum eigenvalue of $\Theta^*$. 
This is of course not intuitive - it's like, for the traditional multi-armed bandit sense, the regret increases when the reward of the minimum reward arm is small. Usually the gap between the optimal and sub-optimal is important in the regret analysis of the bandit, not the minimum one. 
I think this is a kind of the hidden dimensional dependency for the result of this paper, and should be improved in the future.



2) Quality - Problematic

Overall, the proof seems correct for the core part(Theorem 4.1 and Theorem 4.2 - assuming their re-using the data is not problematic) so their claim is supported by theoretical analysis. It also provides several theoretical discussions in the Appendix, like Appendix J. 

However, I feel quite suspicious about reusing the data. In line 195-206, they advertise that they need no more projection or additional sampling by reusing the data from Stage 1. However, I doubt about the independence. The samples in Stage 1 already affects the coordinates, and this re-organizing coordinate affects the calculation of ${L}_t^{\Lambda} (\theta)$, especially about the last regularizer term $\|\theta\|_\Lambda$. The new coordinate is decided by $X_i (i=1, \cdots t)$ and every calculation is based on this new coordinate rotation. $\Lambda$ penalizes some of the new coordinates where the experiment results from $X_i (i=1, \cdots t)$ shows high regret. Are you sure that you can guarantee the independence of the result and okay to mix the data from the 1st stage and 2nd stage?

I believe that this is the point that the author should clarify. 


Plus, I am not clear how to get the distribution $\mathcal{D}$ if only action sets are given. If it is difficult to create such distribution, then Assumption 3.3 is not trivial, which makes this paper weaker. 


3) Clarity: 

Basically, the paper describes what they do with some clarity, but of course there are some typos and abuse of notations. I think these are minor, and I believe these drawbacks will be fixed after this paper is accepted. 
- The use of $S$ is very confusing. Sometimes it is the bound of $\|\Theta^*\|$, and sometimes it is the score function when the distribution is 'obvious'. I was spending quite a time for finding the line 119. 
- In line 152, I want the writers to clarify that they will apply the function entrywise. 
- In line 175 and Eq. (8), I believe this result is not that obvious. At least make a section in the Appendix will be great (or at least the exact place of reference)
- In Eq. (10), the time index for two summation ($T_1$ and $t$) confuses the reader. I believe it might be the first exploration stage and the second bandit stage, but it confuses me first. 
- In Lemma B.2, what is g?
- In the last equation of line 457, it seems like the index is missing in the summation.
- In line 458, first inequality, $n$ to $T_1$

Not about clarity, but it is known that if X is $\sigma$-subgaussian, then $var(X)\leq \sigma^2$. See the Lemma 5.4 of the book 'Bandit Algorithm', Lattimore and Szepesvari




4) Significance:

4-1) Strength

This paper proves the matching upper bound compare to the lower bound proved by Lu et al (2017), and finishes the argument what is the optimal regret order for the generalized low-rank bandit. It also introduces a new method called Stein's method to this field. 

4-2) Weakness

This matrix bandit field itself is a relatively small field, so it would be better if the author explains how his ingenious approach can be extended to other larger fields. 
questions: Main question (will change my opinion)

about the reusing the data

I feel quite suspicious about reusing the data. In line 195-206, they advertise that they need no more projection or additional sampling by reusing the data from Stage 1. However, I doubt about the independence. The samples in Stage 1 already affects the coordinates, and this re-organizing coordinate affects the calculation of $ {L}_t^{\Lambda} (\theta) $, especially about the last regularizer term $\|\theta\|_\Lambda$. The new coordinate is decided by $X_i ( i=1, \cdots t)$ and every calculation is based on this new coordinate rotation. $\Lambda$ penalizes some of the new coordinates where the experiment results from $X_i ( i=1\cdots t)$ shows high regret. Are you sure that you can guarantee the independence of the result and okay to mix the data from the 1st stage and 2nd stage?

I believe that this is the point that the author should clarify. 



Other questions

1) Could you tell me intuitively why the Stein's method works better to estimate matrix completion compare to the previous approaches? I read your proof and understand that your proof will be correct (about theorem 2), but I want to get some hunch about why it shows more accurate estimation ($\frac{dr}{T}$) in terms of Frobenius norm than the previous approach ($\frac{\sqrt{d^3r}}{T}$). 

2) This paper assumes that we already got a distribution $\mathcal{D}$ which satisfies a certain assumption. It would be great if this paper describes how to get such a distribution from a given action set. I know that you described something in Line 129-135, but it doesn't make sense to me, even after I read your Appendix I. You said, 

1-find the convex hull of $\mathcal{X}$ which contains the ball of radius R
2-$p_ij$ is now centered gaussian with variance $\frac{R^2}{d_1 d_2}$

Are you sure that sample from $\mathcal{D}$ always lies in $\mathcal{X}$? For example, imagine a thin shell action set with out-radius R and inner radius 0.99R. Then there might be almost no hope that your distribution lies in this shell, right? In fact, there's no detail description about the sampling method in Appendix I. Please let me know if there's a detail I missed.

There are several papers related with this exploration planning in the linear bandit field, especially using something like G-Optimality. I want this level clear, if possible. 

3) Is the minimum eigenvalue condition really necessary in this problem? Could you introduce any related works where this term is inevitable? At least (Jang et al, 2021) didn't have the minimum eigenvalue term in the algorithm as far as I remember. 
limitations: 1) There is a hidden factor in regret which is the 'minimum eigenvalue' term. It is not intuitive to me that when minimum eigenvalue is extremely small, this matrix can be additional dimensional dependency which makes this paper weaker. 

2) The way to draw the samples should be suggested. The author should prove that their assumption is really a mild one.
review_title: null

Meta-review: metareview: This paper proposes computationally efficient algorithms for low-rank generalized linear bandit with regret and runtime guarantees that improves over state of the art results. All reviewers think that the technical contributions of this paper is solid, especially the insight that one can directly apply Stein's method for accurate subspace estimation without matrix estimation. Accept. 

The authors are encouraged to include the additional experiments in the rebuttal in the final version. 
confidence: Certain
Decision: Accept