Contextual Multinomial Logit Bandits with General Value Functions

Summary

This paper considers MNL bandits with a general value function. The authors first examine the case of stochastic contexts and rewards. They suggest an epoch-based algorithm with an offline regression oracle. With uniform exploration, the algorithm achieves a regret bound, specifically $T^{2/3}$ for finite and linear classes. By utilizing better exploration, it achieves $\sqrt{T}$ for these classes. Next, they consider adversarial contexts and rewards. With uniform exploration, the algorithm achieves a regret bound of $T^{5/6}$ for finite or linear classes. With better exploration, it achieves $T^{3/4}$. Lastly, by using Thompson sampling, it achieves a $\sqrt{T}$ regret bound. Importantly, the suggested algorithms do not depend on $\kappa$, implying better dependency on $B$.

Strengths

- This paper first considers a general value function for MNL bandits. - They propose algorithms for stochastic or adversarial context and rewards and provide regret analysis. - The regret bound has better dependency on $B$ (without including $\kappa$) compared to previously suggested ones.

Weaknesses

1. The regret bound has supper linear dependency on $K$ for $\sqrt{T}$ in Corollayr 3.8, 4.7, 4.8. 2. It does not provide regret lower bounds so it is hard to know the tightness of the achieved regret upper bounds.

Questions

1. Is there any insight about how regret bounds do not include the dependency on $\kappa$ for linear class? Or does it include $\kappa$ when it is applied to the standard contextual MNL model? 2. Feel-good Thompson sampling algorithm seems to outperform other algorithms including stochastic or adversarial cases. Is there a benefit to using epoch-based algorithms over the Thompsom sampling method?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

I could not find a discussion on the limitations of this work.

Summary

This paper addresses the problem of contextual multinomial logit (MNL) bandits with general value functions across both stochastic and adversarial settings. The authors develop a suite of algorithms for different settings and with different computation-regret trade-offs. The application to the linear case surpasses previous works in terms of both statistical and computational efficiency.

Strengths

1. **Novelty of the Setting**: This paper is the first to explore contextual MNL bandits with general value functions, representing a significant expansion in the scope of MNL bandit problems. The setting is both novel and interesting. 2. **Innovative Techniques**: The introduction of several new techniques to tackle the complexities introduced by general value functions is commendable. The methods may inspire the following works and be useful in other areas. 3. **Improved Efficiency**: The application of these methods to linear cases shows improvements over previous works in both statistical and computational efficiency, making this a valuable contribution to the field.

Weaknesses

1. **Computational Inefficiency**: The Feel-Good Thompson sampling algorithm, as discussed, lacks computational efficiency, even for linear cases, which could limit its practical applicability. 2. **Lack of Experimental Validation**: The absence of empirical experiments to verify the theoretical claims weakens the paper's impact. Experimental results are crucial for validating the effectiveness and practicality of the proposed methods.

Questions

1. Zhang and Sugiyama (2023) developed a computationally efficient algorithm for MLogB bandit problem. As MLogB and MNL are similar, how might their approach be adapted to the MNL bandit problem addressed in this paper to enhance computational efficiency? 2. The authors claim that to ensure that no regret is possible, they make Assumption 1 in Line 96. Does this imply that achieving no regret is impossible in unrealizable scenarios? Could the authors provide some intuition about the reason? Ref: Yu-Jie Zhang and Masashi Sugiyama. Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost. In NeurIPS 2023.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

This paper introduces a couple of algorithms for contextual multinomial logit bandits under two different assumptions: i) stochastic contexts and rewards; ii) adversarial contexts and rewards. The theoretical analysis for algorithms for these two setups is pretty solid. Despite the contribution of this study, I believe that this paper needs more work to be done for acceptance.

Strengths

The setups for this work are pretty inclusive, representing that the contributions of the work can be significant. The literature review is also solid as well.

Weaknesses

The paper seems incomplete, possibly due to page limits. Some algorithms and results are not fully described, and there is a lack of experimental validation to support the theoretical findings. The authors should better organize and present their work, focusing on the most important results. Additionally, many terms and mathematical notations are used without proper definitions or introductions. In spite of repeated appearances of log loss regression, its definition has not been stated. The definitions of Err_log, Reg_log, and ERM are missing. For the function class F, what is the definition of |F| in Lemma 3.1? I think that many things other than these are missing.

Questions

What is the relationship between \pi and q_m? I am interested in how to apply the feel-good TS [30] for this setup.

Rating

4

Confidence

5

Soundness

2

Presentation

2

Contribution

3

Limitations

Thank the authors for mentioning some limitations in the manuscript. The reviewer also agreed that solving eq (5) with polynomial time complexity is not easy work.

Summary

The paper presents three primary contributions for the contextual multinomial logit bandits considering both stochastic and adversarial contexts and rewards. - a suite of algorithms proposed each with a different computation-regret trade-off. - advances existing regrets by removing the dependence on certain problem-dependent constants. - extends existing works to study a general value function class (1-Lipschitz function class).

Strengths

- This seems to be the first contextual multinomial logit bandit paper considering adversarial context and reward with online regression oracle. I think the community will find this interesting. - The paper is generally well-written and technically solid.

Weaknesses

- No experiments and simulation results are provided. But to be fair, there are other theoretical papers without experimental illustrations. - For stochastic contexts and adversarial rewards, [20] show there exists an efficient algorithm achieving $O(\sqrt{T})$ regret. The adversarial reward setup is more general than the stochastic reward. So it is fair to compare it to corollary 3.5. Algorithm 1 has a larger regret upper bound $O( T^{\frac{2}{3}})$.

Questions

- Is this the first MNL bandit paper considering adversarial context and reward with online regression oracle? - Could you please address the second point in Weakness? - It is understandable that Algorithm 1 uses a doubling trick. But removing sampling history when feeding to offline regression oracle (4th line in Algorihtm 1) is not sensible in my opinion. Could you address this issue without affecting much of the analysis? - Since the paper studied MNL bandit with a general value function class (1-Lipschitz function class), do you think the regret guarantee can be characterized via eluder dimension? The next two questions are related. - It is claimed after Corollary 3.5 that Algorithm 1 achieves a smaller regret dependence on $B$. Why is $B$ a parameter related to regret or $\textbf{Err}_{\log}$? According to the definition of linear class in Lemma 3.1, it is equivalent to assigning weight $e^{\theta^\top x_i}$ to item $i$ and $e^B$ to no-purchase. Since it is required that $\lVert x_i \rVert_2 \leq 1$ and $\lVert \theta \rVert_2 \leq B$, it seems that all $B > 0$ are equivalent. - It is understandable the paper follows [5, 9, 18] to assume the no-purchase option is the most likely outcome. Is this a necessary assumption without which the algorithm could fail? Is it possible to relax the assumption to something like "the probability (or the weight in equation 1) of no-purchase is lower bounded by some $\Delta>0$"? I could imagine that the regrets are related to $\Delta$ (other than $B$ ) since it can be hard to learn $f$ with a large probability of the no-purchase option. Some minor issues: - In line 173, should "$\epsilon \rightarrow \epsilon_m$"? - The optimal choice of $\epsilon_m$ and $\gamma_m$ are given in Appendix. I suggest including them in the Algorithm sections to make the main paper self-contained. - If extending contextual MNL bandits to a general value function class setup is a major contribution, I would suggest to move the paragraph into the main paper.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors adequately addressed the limitations.

Thank you for your rsponse.

I thank the authors for their response and have no further questions.

Response to rebuttal

We thank the authors for their response. I am maintaining my score since it is the first MNL bandit paper considering adversarial context and reward with online regression oracle. However, I hope the authors could address the following issues or give better explanation. - Q3: A iid requirement is incorrect. There is no identical distribution. I gues the author means conditional independent given the recommendation actions. So the entire history can be used in my opinion. - Q5: I still believe $B$ should not be included in the regret upper bound and used in comparison with other algorithm. It is a free parameter and reparameterization does not change the problem definition. A larger $B$ will not affect log loss since $\theta$ will also scale up. If this is right, the comparison with [20] should either be removed or revised. - Q6: This is just a suggestion. The paper could benefit from introducing our discussion on $\Delta$ into the problem definition and analysis. An intuitive explaination on how it affects regret could give readers a better understanding of the MNL bandit problem.