Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new model for contextual bandit problems with high dimensional contextual vector space and action space. Making use of singular value decomposition techniques over low-rank representation matrix, the Hi-CCAB algorithm in essence solves a regularized regression problem to find the best empirical parameter estimates till the end of horizon. Theoretical analysis provides guarantee on the Hi-CCAB algorithm, and empirical evaluation on real-time datasets corroborate with the claims.  
strength_and_weaknesses: Strength:

1. The paper is well-written, with all the sections coherently organized. The contents are largely easy to follow.

2. The intuition and the generalization value of the Hi-CCAB algorithm are also well-explained.

3. Empirical analysis of the algorithm is consistent with the theoretical claims.

Weaknesses:

1. While the overall picture/intuition of the algorithm, it is unclear how the $T^{-\frac{1}{13}}$ bound is achieved by the descriptions of the paper alone. Since the validity of the algorithm hinges on effective SVD/PCA algorithm, it would be helpful to specify(at least on a high-level) what is meant by 'carefully leveraging the independent parts of dependent variables' and what method is actually used.

2. The empirical section is a bit lacking. The only benchmark being used is the naive algorithm. While current results do suggest that the Hi-CCAB converges, it is unclear how it compares to other heuristics in bandit literature (e.g. $\epsilon$-greedy or UCB-based algorithms), and a comparison between well-known algorithms will be helpful too.
   
clarity,_quality,_novelty_and_reproducibility: The paper is largely clear, with all the results clearly stated. While empirical results are relatively lacking, the description is detailed enough for reproducibility. 
summary_of_the_review: My rating of this paper would be a 6, although I'd be happy to adjust my scores if the author address my concerns.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a low-rank representation matrix to address the high-dimensional continuum-armed and high-dimensional contextual bandit problem motivated by assortment pricing problems. The idea is to use an interleaved two-phases algorithm where the first step is to learn a low-rank representation matrix to capture the low-dimensional structure of both the high-dimensional arms and high-dimensional covariates, and a second step to expand the action space. On the theory side, a "consistency" result is given ($\lim_{T->\infty} \frac{R_T}{T^{12/13}} = 0$), and on the practical side, experiments on and instant-noodle assortment pricing dataset are provided.
strength_and_weaknesses: Strength:
- The proposed model can be reduced to some classic bandit problems (such as stochastic multi-armed bandit, linear bandit, continuum bandit without context, etc).
- Very original dataset that corresponds to the purpose of the paper.
- The policy learning phase which expands the action space is quite interesting to deal with the continuum arm space. And the two phases (low-rank representation learning + policy learning) although interleaved, seem to be quite modular.

Weaknesses/questions/remarks:
- Could you elaborate on the choice of $w^{3/2}$?
- The theoretical part is not very strong in the sense that we do not really know how to assess Theorem 1. I would suggest the authors to interpret a bit Theorem 1 since it is not very common to look at the 'time-averaged regret', so some interpretation would be appreciated. In particular, could elaborate on the order $1/13$, and how is it related to the dimensions?
- On the experiment side, as I mentioned I find the proposed two-step algorithm quite modular. That's a good point, but at the same it means that we can also try other kind of contextual bandit algorithms (or even kernel/graph/combinatorial bandit algorithms), at least as some benchmark to compare with. 
- Another point on the experiment - as the authors claim that the proposed model covers also some other more classic bandit models, a small sanity check (both experimentally and theoretically actually) that could've been done is to check the performance of the proposed algorithm under these classic models.
- Literature review is somehow not very thorough (at least on the bandit side, contextual bandits, continuum bandits, rank-1 bandits etc), but that's a minor point.
clarity,_quality,_novelty_and_reproducibility: Clarity and quality:
The main text is well written, though I didn't check all the detail in the appendix.

Novelty:
The main novelty comes from the policy learning phase in my opinion, which is enforced by a low-rank matrix learning process.

Reproducibility:
If I'm not missing something, the reproducibility is not highlighted enough in terms of data collection. But it should be ok if the data is made available later. Otherwise, the experiments detail is given.
summary_of_the_review: The idea is in general interesting, in particular the policy learning phase. However, I think there could be a set of things to be done to make the paper more complete as I already mentioned in the Strength And Weaknesses section.

___________________________________________

I decide to increase a bit my score after rebuttal since the authors have made an effort to address some of the points made by other reviewers and myself. Those are, however, some major revisions (that are not supposed to be made during the rebuttal phase, otherwise that's like extending the deadline).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers the problem of a contextual bandit with both a high-dimensional action space and a high-dimensional covariate space. The author(s) propose a new bandit model describing the aforementioned problem, and provide a learning algorithm under the model.  Theoretical results are developed for the algorithm and the effectiveness of the algorithm is demonstrated with an assortment pricing case study.
strength_and_weaknesses: Strengths:
The paper studies an interesting and relevant problem and proposes a model that may be applied to a broader class of problems. 

Weaknesses:
1. The novelty and contribution of this paper are limited, especially the theoretical guarantee. 
2. The writing of the paper can be improved.

Detailed comments:
1. The first sentences in the abstract are essentially saying "we formulate a bandit problem as a bandit problem".
2. Line 5 of the abstract: "contextual" -> "context"
3. On page 3, is the concept "approximately low rank" defined?
4. In (1), are the contexts stochastic (they appear to be so from the definition of the regret)?
5. On page 5, it is not justified why in the healthcare example one would expect a low-rank matrix.
6. Theorem 1: 
 (1) the result is not very informative in that one can not see the dependence on $d_x$, $d_a$ and $d$ (i.e., how using low-rank representation learning can address the issue of high dimensionality).
 (2) As T goes to infinity, are $d_x$ and $d_a$ also going to infinity? Since the difficulty of high-dimensionality mainly
stems from the fact that $d\ge T$. It seems to me from the proof that at least $d_x$ is treated as fixed as $T \rightarrow \infty$. Please correct me if I am wrong.


clarity,_quality,_novelty_and_reproducibility: The novelty and contribution of this paper are limited, especially the theoretical guarantee, and the writing of the paper can be improved.
summary_of_the_review: In general, I think the paper considers an interesting problem and proposes an appropriate model describing the problem. The paper however can be improved with improved theoretical results and presentation.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a general framework to solve the high dimensional continuum armed bandit problem and high dimensional contextual bandit problem jointly. This research problem is significant and the proposed model is novel. I agree that the proposed problem has broad scope of applications. For this problem, the paper propose an efficient algorithm called Hi-CCAB, by adopting the low-rank matrix estimator. Experimental study shows the proposed method can improve the naive approach by 4 times for the cumulative reward. 
strength_and_weaknesses:  However, I have the following concerns about the exploration manner, related works and experimental design. 
(1)	Although the proposed model is based the low rank representation matrix assumption, I cannot get the reason why the epsilon term is bounded. Previous works usually assume a sub-gaussian distribution for the error term. I suggest the authors to explain why the low-rank assumption is enough to bound the epsilon. 

(2)	The paper gives two different manner (2 different gaussian distribution) for exploration in each step. Theorem 1 shows the regret bound based on the first one. What about the another one? Is it possible for us to propose a general regret bound which is independent on the distribution used in the exploration?

(3)	There are some important related works are missing. Recently the direction of proposing deep learning based model for high dimensional contextual bandit problem is very hot, especially for the complex non-linear model assumption. For example, 
[1] Zhou D, Li L, Gu Q. Neural contextual bandits with ucb-based exploration[C]//International Conference on Machine Learning. PMLR, 2020: 11492-11502.
[2] Chen Y, Xie M, Liu J, et al. Interconnected Neural Linear Contextual Bandits with UCB Exploration[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Cham, 2022: 169-181.
[3] Jacot, A., Gabriel, F., Hongler, C.: Neural tangent kernel: convergence and generalization in neural networks. In: NIPS, pp. 8580–8589 (2018)
If we concatenated the continuum arm space and contextual vector totally as a large feature vector, we can use these existing methods to solve it. Thus the paper should be compared to them. 

(4)	The experiment study is a toy. Only one navie method is compared to Hi-CCB with the simulation in a small dataset. Thus it is very hard to support the conclusion. I suggest the authors to justify by some public large data for real problem. In fact, we can compare with baselines in each of special case problems.

Minor problem:
(1)	All figures are blur. 

clarity,_quality,_novelty_and_reproducibility: 1. The paper is well written but the figures are unclear. 
2. The formulated problem is relatively novel.
summary_of_the_review: 1. The problem is significant and interesting but the assumption remained to be listed clear. 
2. The experimental study should be improved. The current version is not convincing. 
3. The exploration manner should be explained and regret bound could be proved accordingly.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper considers the problem of contextual bandits with both a high-dimensional action space and a high-dimensional covariate space.  Assuming the existence of a low-rank representation matrix, the authors proposed Hi-CCAB algorithm that applies low-rank matrix estimator (SVD) and provided regret bound of the proposed algorithm. The reviewers agree that the considered problem is interesting. However, reviewers raised shared concerns including (1) the design of exploration and the regret bound ($O(T^{13/15})$ in the revised version) are not clearly explained; (2) lacking experiments; and (3) literature review should be improved. The authors have improved some of the aspects during response period but it requires further major revision. I therefore recommend rejecting the paper. Given the interesting problem setting, the authors are encouraged to revise the paper according to reviews and submit it to the next venue.
justification_for_why_not_higher_score: The reviewers share concerns on (1) the design of exploration and the regret bound are not clearly explained; (2) lacking experiments; and (3) literature review should be improved.  While the authors improved the paper and one reviewer increased score from 3 to 5, the overall rating is still lower than borderline.
Decision: Reject