Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies multinomial logistic (MNL) regression bandits, a generalization of binary logistic bandits. It differs from previous works on MNL bandits by considering a different decision-making process. That is, the authors do not address the combinatorial action selection of previous MNL bandits, but rather study the problem setting where the agent offers a single item, but with K different outcomes. 

The paper introduces a UCB-based algorithm for this problem, for which the authors establish a sub-linear regret bound. By building on recent advances in logistic bandits, they improve the prohibitive impact of the constant \kappa from both the design of their algorithm and its theoretical guarantees.
main_review: The paper is well-written and easy to understand. The problem setting is stylistic but well-motivated. I am convinced that this variant of the MNL problem is worth attention from the research community. My biggest concern, however, is the technical contribution to the community. 

What is the technical novelty that the authors have shown on top of the existing techniques in the logistic bandits shown in Faury et al. (2020)? Generalization to the multinomial setting from logistic setting using Faury et al. (2020) appears to be fairly straightforward. Can you elaborate on what is technically difficult in such a generalization?

Also, the paper does not mention a recent work on MNL contextual bandits Agrawal et al. (2020) which studies the combinatorial setting, hence a different problem, but still leverages the work of Faury et al. (2020) to establish improved regret bounds.

- Faury et al. (2020), Improved Optimistic Algorithms for Logistic Bandits
- Agrawal et al. (2020), A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit, 
limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper presents MNL-UCB Algorithm for contextual MNL bandits problem. At every step, the algorithm estimates a K-tuple of parameter vectors in the confidence region. Specifically, they prove that the regret of MNL-UCB scales as \tilde{O}(dK\sqrt{\kappa}\sqrt{T}) where $\kappa$ is a parameter that captures the degree of (non)-smoothness of the MNL model. It improves the constant from linear in \kappa to \sqrt{\kappa}. They further improved algorithm that achieves a regret bound with problem-dependent constant \kappa being pushed into a second order term.

Compared to the most existing work, a major difference is that each choice is associated with a different parameter so a matrix of parameters needs to be learned.

main_review: Contextual MNL is a recent hotly studied topic. 

My biggest concern is the lack of comparison with an existing work. I want to bring one paper into attention: A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit. The main difference between two papers is whether different choices share the same parameters. However, the analyses are very similar in two settings and the analysis is similar to the generalized linear bandits. Moreover, regarding the regret bound, the improvement is also similar: it improves the constant term from \kappa to \sqrt{\kappa} and it meanwhile pushes the constant term into a second order term. Can you clarify 

1) The technical difficulty/contribution of this paper (e.g. how it differs from the existing work);

2) What's the connection between two constants (kappa in your paper and kappa in their paper)?

3) What is the regret lower bound? Is the regret optimal with respect to the order of K? I saw the short comments in line 275-285, but can you provide a rigorous argument for that conclusion?

The writting is good, but the contribution needs to be clearly emphasized.

Minor: 1) The notation \bar{\theta}_* can be simplified to \theta_*;

2) Please define \otimes before formula (8);



limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies multinomial logistic regression bandit problem, where the number of outcomes can be greater than two. This is an extension of the well-studied generalized linear bandit problem with two outcomes (e.g., clicks and no-clicks). The authors first propose the problem setup with real-life motivated scenarios and then propose a UCB based algorithm to minimize cumulative regret. The authors analyze its performance and derive an upper bound of \tilde{O}(dK\sqrt{\kappa T}), where d is the dimension of the action space, (K + 1) is the number of outcomes, T is the number of interactions, and \kappa is the degree of non-smoothness, which is inherent to the multi-nomial problem. At the end, the authors provide a simulation based study which supports their theoretical insights.  
main_review: Strengths:
1. Relevant and practical extension of an important problem. 
2. The theoretical analysis and presentation is unique (some things can be clarified; see detailed comments)

Weaknesses:
1. The paper does not contain experiments with real-datasets and no comparisons with baselines. 
2. The are a few concerning questions that confuse the reader; hence presentation can be improved (see detailed comments).

Detailed Feedback:

1. I am a bit confused with the bound that the authors have mentioned in the abstract and in the main text. They seem to be inconsistent. Can you please clarify? Also, when mentioning the bounds, please mention what the parameter stands for, e.g., d, T?

2. Equation 2: I believe it should be \forall i \in [K] instead of \forall i \in [K] \cup {0}.

3. There seems to be some mistake in the way expected reward is defined in line 82. There should be some argument in \mu that should depend on the vector \rho, but I do not see it. Then, the domain of \mu in line 83 should also be defined properly. 

4. Why is it necessary to have all the \rho_i >=0? I see an option like "never show me this ad" generating a positive reward to be contradictory? More so, when compared to not-clicking that generates a reward of 0. 

5. Equation 6: What is x_* in the definition of instantaneous regret?

6. The analysis largely depends on the regularization parameter $\lambda$. I wonder how the analysis will change if in equation 7, one chooses to work without regularization.
Also, there is notation abuse. \lambda_max/\lambda_min are used for eigen values and \lambda is used for regularization as well.

7. Right at the point where the authors make assumption 2, it is not clear to me why A will have positive eigen values. Can you please clarify?

8. In Lemma 1, I was confused about what V_t stands for. The authors explain its definition much later. It would be better to reorganize that bit.

9. The presentation of analysis is good. However, I would recommend moving the Lemmas which are used to prove other major results to the appendix, and instead add experiments with real-data in the paper. My major reason for giving the current score is because of its weak experiments. 

10. The authors provide intuitive reasons of why there should be a linear dependence in K. However, they have not provided any proof in that regard. Thus, the usage of the word 'optimal' is imprecise in my opinion.

11. There has been a blatant use of vspace/vskip in the entire paper. If the paper is accepted, I would recommend avoiding their large usage. It just destroys the aesthetics of the paper. 

Minor:
1. Line 30: statistic --> statistics?
limitations_and_societal_impact: No, the authors have not mentioned limitations and societal impacts of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers a version of stochastic contextual bandits where the rewards are drawn from a discrete distribution governed by a multionimal logit model. This setting is motivated by applications in online advertising where the user may give various feedbacks in the face of a recommendation beyond a binary ‘clicked’ or ‘did not click’ – e.g. ‘show me again later’, ‘never show me again’. The authors propose and analyse a UCB algorithm for this problem with the confidence sets being based on the work of Faury et al. (2020, ICML) and the regret analysis being based on that of Abbasi-Yadkori et al. (2011, NeurIPS). The particular advantage of utilising the concentration results of Faury et al is that the regret of the resulting algorithm scales favourably (square root order) with respect to a parameter $\kappa$ characterising the smoothness of the logit function around the true parameter. A further algorithm whose dependence on $\kappa$ is relegated to lower order terms w.r.t. the horizon is also developed – however this approach is computationally intractable. In the related (binary) logistic bandit setting, some popular algorithms have been shown to have exponential order dependence on this parameter and the design of algorithms which are robust to its value is useful. It may be useful to note that this version of a multinomial bandit is different from the combinatorial problem in the dynamic assortment selection literature (e.g. Agrawal et al (2017, 2019)) where the different outcomes represent different items.



main_review: I feel that this is a somewhat borderline paper. The extension of the logistic bandit to the multinomial logit setting is one that would be of genuine interest, and the analyses and proposed algorithm seem to be sound. The issue is that the developments are somewhat marginal. Some detailed theoretical work is required get the correct form of the UCB terms to hold over multiple parameter vectors simultaneously, but it seems that a good deal of the effort lies in combining new concentration theory (in this instance from Faury et al. (2020))  with the regret analyses of Abbasi-Yadkori et al. (2011). This is a credible and often used approach within this literature, but its familiarity does bring with it the question of whether there is sufficient novelty to merit publication at a top venue such as NeurIPS, and not an alternative venue. I have no doubt that there are many venues where this solid piece of research would easily clear the acceptance bar.

ORIGINALITY: The headline results are new in and of themselves, in so far as the literature has not combined the novel concentration results and regret analyses in the context of this variant of an MNL-bandit. As discussed above, a large component of the analysis is focussed on the combining of existing tools – a perfectly useful piece of work but one that perhaps scores lower in the originality aspect.

QUALITY: As far as I can tell, the theory is accurate and the paper is generally written well. The algorithm is not compared to any (even naïve) competitors so it is hard to gauge its efficacy. We can however see that the variation in its performance with respect to particular problem parameters mirrors the implications of the theory. Where I think the paper could be improved through relatively little effort is through making yet more explicit the connections to the preceding work. The following questions occurred to me while reading the manuscript but did not have answers which I could easily discern. I feel the discussion and my understanding would be improved further by addressing them. 
1.	Faury et al. (2020) can, according to line 119, drop the dependence on $\kappa$ entirely. Why is this not possible (or perhaps not pursued?) here?
2.	Line 221 asserts the main technical contributions of the paper. Are these ‘main’ in the sense that they are the most challenging, the largest departure from existing techniques, or the most likely to be useful elsewhere? In any of these cases, why not sell this contribution more prominently among your contributions?
3.	In what sense, precisely is the ‘improved algorithm’ computationally intractable? I did not find an explicit discussion of this in the requisite appendix.

CLARITY: I feel the paper is generally clear and well written. As a technical paper with a lot of theoretical angles to introduce in a short page limit it is occasionally more quite concise, but I think it is sufficiently clear for the intended audience.

SIGNIFICANCE: As discussed above, this seems like a pragmatic and realistic extension of logistic bandits to a setting that is likely to arise in online advertising. The analysis is solid and accurate as far as I can tell. This is a nice piece of work, suitably complete for publication (somewhere) and will be of interest to those working in this area.
limitations_and_societal_impact: yes - this has been considered by the authors.
review_title: null

Meta-review: This paper proposes a UCB-based algorithm for multinomial logit bandits. Its initial scores were 6, 6, 5, and 5; and they did not change during the discussion. The reviewers liked the rebuttal of the authors and agreed that this paper would a good contribution to NeurIPS. The main factor in this decision was the importance of the application. On the other hand, the paper builds heavily on Faury et al. (2020) and contains no experiments. In my opinion, this paper is borderline plus and I support its acceptance.
Decision: Accept (Poster)