Contextual Multinomial Logit Bandits with General Value Functions

Q1: Is there any insight about how regret bounds do not include the dependency on 𝜅 for linear class? Or does it include 𝜅 when it is applied to the standard contextual MNL model?

A: The intuition on why we do not have $\kappa$ dependency is that most previous MNL works (e.g. [7,20,23]) adopt a UCB-type approach, which first approximates the true weight parameter $\theta$ via MLE and constructs a confidences set based on this approximation. The $\kappa$ dependence will unavoidably appear from this approximation step. Different from previous approaches, we reduce the learning problem to a regression problem, and show that the regret directly depends on the regression error. This key step enables us to remove the dependency on $\kappa$.

Q2: 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 Thompson sampling method?

A: As shown in Table 1, while Feel-good Thompson sampling outperforms other algorithms in terms of regret upper bound, it is not computationally efficient (even for a small $K$) since it is unclear how to sample the value function at each round efficiently. On the other hand, our other algorithms, including those epoch-based algorithms, are computationally efficient (at least for small $K$).

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

A: We do discuss the limitations of our work in various places (as acknowledged by other reviewers), such as the assumption on the no-purchase option, the inefficiency of solving Eq. (5) when K is large (Lines 214-215), and the disadvantage of FGTS algorithm (Lines 322-326),

For the $\kappa$, it is still not clear how to avoid this term. For the regression with linear class, ERM seems to minimize log-loss to estimate parameters as in the previous MNL model, which includes approximate parameter. Could you provide any helpful comments regarding this? I'm also wondering about that the $\epsilon$-covering number does not need to include $\kappa$.

Q1: Computational Inefficiency: The Feel-Good Thompson sampling algorithm, as discussed, lacks computational efficiency, even for linear cases, which could limit its practical applicability.

A: We acknowledge that the Feel-Good Thompson sampling is not efficient theoretically. However, empirically, as mentioned in [30], one can apply stochastic gradient Langevin dynamic (SGLD) to approximately sample a value function.

Q2: [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?

A: While MLogB and MNL share some common components, their setups are in fact quite different: MNL considers the case where multiple items (decision) are chosen at each round and one of these items is selected according a multinomial distribution, while MLogB considers the case where a single item (decision) is chosen at each round but the outcome is one of the $K+1$ different possible outcomes (including the no-purchase outcome) following a multinomial distribution. Since the computational inefficiency for MNL usually comes from the fact that the number of possible subsets is large, we do not see how ideas from MLogB can be utilized to improve the computational efficiency of our algorithms.

Q3: 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?

A: Making a realizability assumption is standard for bandit problems with function approximation [10, 11, 14, 29, 31], usually for the purpose of obtaining efficient algorithms via reduction to regression, but it does not imply that no regret is impossible without it. In fact, for contextual bandits, applying the classical (but inefficient) Exp4 algorithm [Auer et al., 2002] achieves the optimal regret even without the realizability assumption.

[Auer et al., 2002]: Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing, 2002.

Q1: The paper seems incomplete, possibly due to page limits. Some algorithms and results are not fully described. Additionally, many terms and mathematical notations are used without proper definitions or introductions.

A: We strongly disagree with this comment. Could the reviewer kindly point out what algorithms and results are not fully described in this paper? For your examples of “terms and mathematical notations used without proper definitions or introductions”, they are in fact all explicitly defined (see below).

Q2: In spite of repeated appearances of log loss regression, its definition has not been stated.

A: This is not true. The definition of log loss regression is in Assumption 2 (offline) and Assumption 3 (online), with the definition of log loss in line 77.

Q3: The definitions of Err_log, Reg_log, and ERM are missing.

A: $\text{Err}_{\log}$ is defined in Assumption 2 and meant to be an abstract generalization error bound of the offline regression oracle, whose concrete form depends on its three arguments: $n$ (the number of samples), $\delta$ (the failure probability), and $\mathcal{F}$ (the function class) and is instantiated clearly in Lemma 3.1 and Lemma D.1 for three examples.

Similarly, $\text{Reg}_{\log}$ is defined in Assumption 3 and meant to be an abstract regret bound of the online regression oracle. Again, its concrete form for three examples are provided in Lemma 4.1 and Lemma D.1.

We also emphasize that deriving regret bounds with a general generalization error or regret bound of the regression oracle and then instantiating them for concrete examples is very common in this line of work; see [10, 11, 14, 25, 27, 29, 31].

ERM, “empirical risk minimizer” (line 119), is explicitly defined in Lemma 3.1 (line 123).

Q4: For the function class $\mathcal{F}$, what is the definition of $|\mathcal{F}|$ in Lemma 3.1?

A: $|\mathcal{F}|$ represents the cardinality of the finite set $\mathcal{F}$ (which is a rather standard notation).

Q5: What is the relationship between $\pi$ and $q_m$?

A: $q_m: (\mathcal{X}\times r) \mapsto \Delta(\mathcal{S})$ is a stochastic policy (mapping from a context-reward pair to a distribution over subsets (line 136)) that Algorithm 1 decides in each epoch m, while $\pi: (\mathcal{X}\times r) \mapsto \mathcal{S}$ is a deterministic policy (mapping from a context-reward pair to a subset (line 143)) that appears in our analysis. We are not very certain about what specific “relationship” the reviewer is asking about.

Q6: I am interested in how to apply the feel-good TS [30] for this setup.

A: All details on applying feel-good TS to our setup can be found in Appendix E (as mentioned in Sec 4.2).

Q1: For stochastic contexts and adversarial rewards, [20] show there exists an efficient algorithm achieving $𝑂(\sqrt {𝑇})$ 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^{2/3})$.

A: Note that we did compare to [20] in the discussion after Corollary 3.5 (Line 195 more specifically) and highlighted that the regret bound of [20] depends on $\kappa$ which can be exponential in $B$ in the worst case, while our bound only has polynomial dependence on $B$. We will add that our bound indeed has a worse dependence on $T$ as suggested.

Q2: Is this the first MNL bandit paper considering adversarial context and reward with online regression oracle?

A: Yes, to the best of our knowledge, our work is the first one considering the case where both the context and the reward can be adversarial (with or without regression oracles).

Q3: It is understandable that Algorithm 1 uses a doubling trick. But removing sampling history when feeding to offline regression oracle (4th line in Algorithm 1) is not sensible in my opinion. Could you address this issue without affecting much of the analysis?

A: While it might seem sensible to feed all the sampling history to the offline regression oracle due to the stochasticity of contexts and rewards, it does not work since the oracle requires i.i.d. inputs of context-subset-purchase tuples (not i.i.d. context-reward), and different epochs of our algorithm create different distributions over these tuples.

Q4: 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?

A: Our regret bounds explicitly depend on the generalization error of ERM oracle in the stochastic environment, and the online regression regret (Algorithm 2) or the log partition function (Algorithm 3) in the adversarial environment. It is unclear to us how these quantities are directly related to the eluder dimension of a function class.

Q5: It is claimed after Corollary 3.5 that Algorithm 1 achieves a smaller regret dependence on $𝐵$. Why is $𝐵$ a parameter related to regret or $\text{Err}_{\log}$? According to the definition of linear class in Lemma 3.1, it is equivalent to assigning weight to item 𝑖 and $𝑒^𝐵$ to no-purchase. Since it is required that $||x_i||_2\leq 1$ and $\|\|\theta\|\|_2\leq B$, it seems that all $𝐵>0$ are equivalent.

A: Your reparameterization is correct. However, a larger parameter $B$ makes the lowest possible weight for each item, $e^{-B}$ under your parameterization, smaller, which in turns makes the scale of the log loss larger and naturally increases the generalization error $\text{Err}_{\log}$.

Q6: 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 $𝐵$) since it can be hard to learn $𝑓$ with a large probability of the no-purchase option.

A: If the weight for no-purchase is lower bounded by $\Delta\in(0,1)$ instead of $1$, all our regret bounds still hold with an extra factor of $1/\Delta$ (explained below). Note that this is the opposite to what the reviewer suggested — while a large no-purchase probability seemingly makes it harder to learn $f^\star$ at first glance, it in fact makes it easier because it leads to a better reverse Lipschitzness of $\mu$, and consequently the difference in value is better controlled by the difference in log loss. As an extreme example, suppose that the no-purchase weight is 0. Then, no matter what value an item has, it will always be purchased by the customer if the selected subset contains only this item, revealing no information to the learner at all.

To see why our bounds hold with an extra factor of $1/\Delta$, note that the only modification needed is Lemma B.3 (reverse Lipschitz Lemma): in this case we need to show the reverse Lipschitzness for $h(a) = a/(\Delta+1^\top a)$, and via a similar calculation, it can be shown that $\Omega(\Delta^2/d^4)\|\|a-b\|\|^2 \leq \|\|h(a)-h(b)\|\|^2.$ The remaining analysis remains the same.

Thanks for pointing this out; we will add this discussion to the next version.

Thanks for the other suggestions and pointing out the typos. We will incorporate these in the next revision.

Thanks to the authors for their response and for making these points clear. Now it is clear how $B$ affects regret and what iid means here. I hope the authors can explain the following questions in the revised paper. At least they are not very intuitive to me.

• Why IID is necessary for the algorithm? We can still compute $Err_{\log}$ given $S$. It is known IID assumption with fixed $q_m$ is not a requirement for Thompson sampling. So it is not very intuitive to me. What aspects of the problem make it necessary here?

• The relationship between $B$ and $\Delta$ still gives me contradictory information. Bigger $B$ and $\Delta$ result in a lower probability of item $i$ being selected. Why does the regret increase with $B$ but decrease with $\Delta$?

I hope these questions are helpful. Again, I'll maintain my rating on this paper.

We thank the reviewer for the questions again. They are indeed very helpful, and we will add more explanation to the paper. Specifically:

Why IID is necessary for the algorithm? We can still compute $\text{Err}_{\log}$ given $S$. It is known IID assumption with fixed $q_m$ is not a requirement for Thompson sampling. So it is not very intuitive to me. What aspects of the problem make it necessary here?

• It is necessary to have i.i.d. data in our algorithm design solely because we assume that our oracle requires i.i.d. data as inputs. It is completely possible that to solve the problem itself, using the entire history is a feasible solution, but note that the weaker the oracle assumption we make, the stronger our result is, so we choose to assume that the oracle only works with i.i.d. data.

The relationship between $\Delta$ and $B$ still gives me contradictory information. Bigger $B$ and $\Delta$ result in a lower probability of item $i$ being selected. Why does the regret increase with $B$ but decrease with $\Delta$?

• Technically, $\Delta$ and $B$ have opposite effects because a larger $\Delta$ makes it easier for the learner to identify the value difference from the realized item selection, while a larger $B$ makes the regression on the item selection probability harder. This is a great question though, and we will add more intuitive explanations to the paper.